79 interi consecutivi
-
Ponnamperuma
- Messaggi: 411
- Iscritto il: 10 lug 2006, 11:47
- Località: Torino
79 interi consecutivi
Dimostrare che, dati 79 interi positivi consecutivi, ce n'è almeno uno la cui somma delle cifre è divisibile per 13. [Fonte: Mathlinks]
La grandezza dell'uomo si misura in base a quel che cerca e all'insistenza con cui egli resta alla ricerca. - Martin Heidegger
MIND torna!! :D
MIND torna!! :D
-
darkcrystal
- Messaggi: 706
- Iscritto il: 14 set 2005, 11:39
- Località: Chiavari
Chiamiamo S(n) la funzione "somma cifre di n" e F(n) la funzione "Ultima cifra di n (congruenza mod 10)"
Consideriamo il primo intero (chiamiamolo n) tale che F(n)=0. Questo e i 9 successivi coprono esattamente 10 classi di resto per la somma delle cifre modulo 13. Se quindi S(n) è congrua a 4 o più modulo 13, o a 0, abbiamo "vinto" perchè uno dei 9 successivi ha somma delle cifre divisibile per 13.
Altrimenti consideriamo n,n+10,n+20,n+30,n+40,n+50,n+60 che sono tutti tra i 79 (cioè: siccome esistono almeno 7 interi che finiscono per 0, preso il più piccolo gli altri sono quelli detti).
Quando c'è il riporto la somma delle cifre cambia in modo "imprevedibile", ma per il resto aumenta di 1. Quindi se tra questi sette non c'è mai riporto o il riporto è tra i primi 3 (o gli ultimi 3 per simmetria), allora abbiamo 4 classi di resto consecutive per cui almeno una sarà diversa da (1,2,3) e di nuovo considerando quel valore e i nove successivi ne troviamo uno la cui somma cifre sia divisibile per 13. Se invece quello con riporto fosse esattamente il 4°, non cambia molto perchè considerando tale valore e i 3 successivi abbiamo ancora 4 classi di resto, per cui una è diversa da (1,2,3) e si conclude.
Del resto si vede che 79 è il bound minimo perchè si potrebbe avere, chiamato A il primo elemento della sequenza, F(A)=1, F(A+9)=0, S(A+9)=1, S(A+19)=2, S(A+29)=3, S(A+39)=1 (riporto), S(A+49)=2, S(A+59)=3, S(A+69)=4, S(A+78 )=13 e quindi servono tutti e 79.
Consideriamo il primo intero (chiamiamolo n) tale che F(n)=0. Questo e i 9 successivi coprono esattamente 10 classi di resto per la somma delle cifre modulo 13. Se quindi S(n) è congrua a 4 o più modulo 13, o a 0, abbiamo "vinto" perchè uno dei 9 successivi ha somma delle cifre divisibile per 13.
Altrimenti consideriamo n,n+10,n+20,n+30,n+40,n+50,n+60 che sono tutti tra i 79 (cioè: siccome esistono almeno 7 interi che finiscono per 0, preso il più piccolo gli altri sono quelli detti).
Quando c'è il riporto la somma delle cifre cambia in modo "imprevedibile", ma per il resto aumenta di 1. Quindi se tra questi sette non c'è mai riporto o il riporto è tra i primi 3 (o gli ultimi 3 per simmetria), allora abbiamo 4 classi di resto consecutive per cui almeno una sarà diversa da (1,2,3) e di nuovo considerando quel valore e i nove successivi ne troviamo uno la cui somma cifre sia divisibile per 13. Se invece quello con riporto fosse esattamente il 4°, non cambia molto perchè considerando tale valore e i 3 successivi abbiamo ancora 4 classi di resto, per cui una è diversa da (1,2,3) e si conclude.
Del resto si vede che 79 è il bound minimo perchè si potrebbe avere, chiamato A il primo elemento della sequenza, F(A)=1, F(A+9)=0, S(A+9)=1, S(A+19)=2, S(A+29)=3, S(A+39)=1 (riporto), S(A+49)=2, S(A+59)=3, S(A+69)=4, S(A+78 )=13 e quindi servono tutti e 79.
"Solo due cose sono infinite: l'universo e la stupidità dell'uomo, e non sono tanto sicuro della prima" - Einstein
Membro dell'EATO
Membro dell'EATO