[A/L] (2021/22) Induzione - Esercizio 1

[matypist]

[danieldinella]

Il caso base ovvero n = 12 si ottiene da 3 francobolli da 4. Da lì in poi, per incrementare di 1, sostituiamo un 4 con un 5. Infine quando ci troviamo in una situazione di soli 5 mettiamo tutti 4 e aggiungiamo un 4.

[Exyss]

Soluzione analoga a quella di @danieldinella

[LuginiAndrea]

Riformuliamo il problema:
$$\forall n \in \mathbf{N} | n \geq 12 \implies \exists j, k \in \mathbf{N} \textrm{ t.c. } n = 4j + 5k$$
Caso base: $n = 12 \implies n = 4 \times 3 \implies j = 3, k = 0$.
Passo induttivo:
$$n + 1 = 4j + 5k + 1 \textrm{ per induzione } = 4j + \left(4 + 1\right)k + 1$$
$$= 4\left(j-1\right) + \left(4+1\right)k + \left(4 + 1\right) = 4\left(j-1\right) + \left(4+1\right)\left(k+1\right)$$
$$= 4\left(j-1\right) + \left(5\right)\left(k+1\right)$$
Questo è valido se $j \geq 1$
Nel caso $j = 0$
$$n + 1= 5k + 1 \textrm{ per induzione } = 5 \times 3 + 5\left(k-3\right) + 1 = 16 + 5\left(k - 3\right) = 4 \times 4 + 5\left(k-3\right)$$
Dimostriamo che $j = 0 \implies k \geq 3$ (ovvero che una delle due strategie è sempre usabile)
$j = 0$ implica che $n$ è un numero che si può scrivere come $5k$. Il più piccolo numero con tale proprietà e che è $\geq 12$ è $15 =5 \times 3$, di conseguenza qualsiasi altro numero nella forma $5k$ avrà $k > 3$

[ATLANCTIX4]

Soluzione analoga a quella di @danieldinella

il caso base non dovrebbe essere:
3X4cent + 0X5cent = 12?
perche hai scritto 4X4 cent?

[Duvan-Zapat]

Il professor

Soluzione analoga a quella di @danieldinella

Il professore piperno nell'appello di giugno ha detto che la parte induttiva è sbagliata, come mai?