Numeri buoni

[Omar93]

Un intero $ n $ si dice buono se lo possiamo scrivere come $ n=a_1+a_2+a_3+.......+a_k $,dove$ a_1,a_2,........,a_k $ sono degli interi positivi(non necessariamente distinti) che soddisfano $ \frac{1}{a_1} +\frac{1}{a_2}+...........+\frac{1}{a_k} = 1 $
Sapendo che i numeri interi da 33 a 73 sono buoni,dimostrare che ogni intero maggiore o uguale a 33 è buono.

[exodd]

Osservazioni:
- 1 e 4 sono numeri buoni
- se a e b sono numeri buoni, allora lo è anche 2(a+b)
- se a,b e c sono numeri buoni, allora lo è anche 2a+3b+6c

Passo 1) Guadagnamo i numeri pari

Induzione forte
Passo iniziale: 74=2(36+1) e 76=2(34+4)
passo induttivo: (n>76)
- caso n=2(mod 4)
n può essere scritto come n=2(1+a), con a numero pari maggiore di 36. Dato che, per induzione, tutti i numeri pari maggiori di 36 e minori di n sono buoni, allora anche n è buono
- caso n=0(mod 4)
n può essere scritto come n=2(4+a), con a numero pari maggiore di 36. Come prima, n è un numero buono

quindi tutti i numeri pari sono buoni

Passo 2) Guadagnamo i dispari

Induzione forte
Passo iniziale: 75=2*33+6*1+3*1
Passo induttivo: (n>74)
sappiamo che n dispari si può scrivere come 2a+3+6, con a numero maggiore di 32 e minore di n (e quindi buono).
Dato che n+2=2(a+1)+3+6, e che a+1<n+2, allora anche a+1 è buono, e di conseguenza lo sarà anche n+2