Pagina 1 di 1

sommando i multipli di $a$ e $b$, $ah + bk = c$

Inviato: 03 ago 2015, 15:49
da alex.96
Sia $f(a, b)$ con $a, b \in \mathbb{N}^{+}$ e $MCD(a,b) = 1$ il numero dei numeri che non sono somma di opportuni multipli di $a$ e multipli di $b$.
Chiamiamo $g(a, b)$ il massimo numero che non è la somma di nessuna coppia di multipli di $a$ e multipli di $b$.

Quindi, per esempio, $f(7, 4) = 9$ perchè sono solo 9 (1, 2, 3, 5, 6, 9, 10, 11, 13, e 17) i numeri che non sono ottenibili dalla somma di mulipli di 7 e 4. Oltre il 17 è facile dimostrare che non ne esistano altri, infatti
$18 = 7*2 + 4*1$,
$19 = 7*1 + 4*3$,
$20 = 7*0 + 4*5$,
$21 = 7*3 + 4*0$
Sono 4 numeri successivi e somme di multipli di 4 e 7. Se al primo aggiungo 4 ottengo 22, se al secondo aggiungo 4 ottengo 23 ... se poi all'ultimo aggiungo 4 ottengo 25, poi ancora, se a 22 (che è "buono") aggiungo ancora 4 ottengo 26, e così via posso ottenere ogni numero maggiore di 17, quindi ho trovato anche $g(7, 4) = 17$.

Dimostrare che :
A. $f(a, b) = \frac{(a-1)(b-1)}{2}$
B. $g(a, b) = (a-1)(b-1) - 1$

(In realtà ho scoperto queste formule un po' per caso, ne ho cercato una dimostrazione ma senza troppo successo. Non posso essere sicuro che siano corrette. Le ho provate con il computer per $a < b \leq 500$, e sono verificate per tutti questi valori, quidi spero che valgano per ogni intero. Ovviamente averle provate con il computer non è una dimostrazione)

Re: sommando i multipli di $a$ e $b$, $ah + bk = c$

Inviato: 03 ago 2015, 16:33
da Lasker
Sì, sono entrambe vere e note, si tratta del teorema chicken mcnuggets; nel link c'è pure una dimostrazione, ma provare a trovarla da soli potrebbe essere interessante (il fatto non è particolarmente impossibile, e a memoria l'idea per risolverlo in generale non è molto diversa da quella che hai avuto per il caso particolare), è un problema "olimpico" e credo di averlo già visto passare sul forum.