Pagina 1 di 1

"Esercizi sul principio dei cassetti" - N.9 Somma multipla di 5

Inviato: ven ago 10, 2007 9:38 am
da Admin
Admin ha scritto:9. Somma multipla di 5
In un qualunque gruppo di 17 numeri naturali se ne trovano 5 la cui somma è divisibile per 5.
Dividiamo i naturali secondo le classi di resto modulo 5;
abbiamo:

$C_5(0)\/=\/\{\/0,\/5,\/10,\/15,\/20,\/...\/\}\\ C_5(1)\/=\/\{\/1,\/6,\/11,\/16,\/21,\/...\/\}\\ C_5(2)\/=\/\{\/2,\/7,\/12,\/17,\/22,\/...\/\}\\ C_5(3)\/=\/\{\/3,\/8,\/13,\/18,\/23,\/...\/\}\\ C_5(4)\/=\/\{\/4,\/9,\/14,\/19,\/24,\/...\/\}$

Ora, affinchè nel nostro gruppo di naturali non ve ne siano 5 la cui somma sia divisibile per 5, non possiamo sceglierne più di 4 per ogni classe di resto;
questo perchè comunque prendiamo 5 numeri di una stessa classe di resto, la loro somma è divisibile per 5; infatti se abbiamo:

$a_1\/\equiv\/1\/\pmod 5\\ a_2\/\equiv\/1\/\pmod 5\\ a_3\/\equiv\/1\/\pmod 5\\ a_4\/\equiv\/1\/\pmod 5\\ a_5\/\equiv\/1\/\pmod 5$

si ha che:

$a_1\/+\/a_2\/+\/a_3\/+\/a_4\/+\/a_5\/\equiv\/1\/+\/1\/+\/1\/+\/1\/+\/1\/\pmod 5\hspace{30}\Rightarrow\hspace{30}a_1\/+\/a_2\/+\/a_3\/+\/a_4\/+\/a_5\/\equiv\/0\/\pmod 5$

Per cui, scegliendo 4 numeri per ognuna delle classi di resto $C_5(1)$, $C_5(2)$, $C_5(3)$, $C_5(4)$, riusciamo ad arrivare a 16 interi naturali;
a questo punto, scegliendo il 17° naturale in una delle classi $C_5(1)$, $C_5(2)$, $C_5(3)$, $C_5(4)$, si ha una classe con 5 numeri, la cui somma quindi è divisibile per 5;
scegliendo invece il 17° naturale nella classe $C_5(0)$, si ottengono ugualmente 5 numeri la cui somma è divisibile per 5; infatti ad es., avremmo:

$a_1\/\equiv\/2\/\pmod 5\\ a_2\/\equiv\/3\/\pmod 5\\ a_3\/\equiv\/2\/\pmod 5\\ a_4\/\equiv\/3\/\pmod 5\\ a_5\/\equiv\/0\/\pmod 5$

per cui,

$a_1\/+\/a_2\/+\/a_3\/+\/a_4\/+\/a_5\/\equiv\/2\/+\/3\/+\/2\/+\/3\/+\/0\/\pmod 5\hspace{30}\Rightarrow\hspace{30}a_1\/+\/a_2\/+\/a_3\/+\/a_4\/+\/a_5\/\equiv\/0\/\pmod 5$

SE&O

Admin

Re: "Esercizi sul principio dei cassetti" - N.9 Somma multipla di 5

Inviato: mar set 09, 2014 9:54 pm
da gnugnu
La dimostrazione è ineccepibile.
17 è, però, una quantità decisamente grande. Per essere certi che esista un sottoinsiema di 5 numeri aventi somma multipla di 5 bastano un gruppo di "candidati" più piccolo di quello proposto.

Re: "Esercizi sul principio dei cassetti" - N.9 Somma multipla di 5

Inviato: sab set 13, 2014 12:25 am
da Gianfranco
gnugnu, hai ragione, quasi certamente il limite di 17 numeri è troppo largo.
Qual è il limite minimo?
Questo è un altro problema, perciò l'ho riportato nel Forum generale.