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

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
alex.96
Messaggi: 5
Iscritto il: 22 mag 2014, 18:28
Località: Como

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

Messaggio da alex.96 » 03 ago 2015, 15:49

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)

Avatar utente
Lasker
Messaggi: 438
Iscritto il: 02 mag 2013, 20:47
Località: Udine

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

Messaggio da Lasker » 03 ago 2015, 16:33

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.
"Una funzione generatrice è una corda da bucato usata per appendervi una successione numerica per metterla in mostra" (Herbert Wilf)

"La matematica è la regina delle scienze e la teoria dei numeri è la regina della matematica" (Carl Friedrich Gauss)

Sensibilizzazione all'uso delle potenti Coordinate Cartesiane, possano seppellire per sempre le orride baricentriche corruttrici dei giovani: cur enim scribere tre numeri quando se ne abbisogna di due?

PRIMA FILA TUTTI SBIRRI!

Rispondi