46

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
nassus95
Messaggi: 79
Iscritto il: 14 giu 2012, 11:06

46

Messaggio da nassus95 »

Fra i numeri 1,2,...,37 scegliamo a caso 10 numeri. Dimostrare che tra questi 10 numeri ne esistono 4 distinti tali che la somma di 2 di loro è uguale alla somma degli altri 2.
Avatar utente
Troleito br00tal
Messaggi: 683
Iscritto il: 16 mag 2012, 22:25

Re: 46

Messaggio da Troleito br00tal »

Lavoriamo per assurdo.

Siano $a_1<a_2<...<a_{10}$ i numeri scelti. Le possibili differenze $a_i-a_j$ con $i>j$ tra questi numeri sono $\frac{9 \cdot 10}{2}=45$. Le possibili differenze saranno tutti numeri compresi tra $1$ e $36$.

Ora: sistemiamo un po' di cose. Se tra le $45$ vi sono almeno $3$ differenze uguali, abbiamo vinto: siano $b_1>b_2;c_1>c_2;d_1>d_2$ tali che $b_1-b_2=c_1-c_2=d_1-d_2$. Ora, se $b_2 \not = c_1$ la tesi segue banalmente su $\{ b_1;b_2;c_1;c_2 \}$; pertanto, $b_2=c_1; c_2=d_1; d_2=b_1$. Ma questo è assurdo, poiché $b_1>b_2=c_1>c_2=d_1>d_2=b_1$.

Pertanto abbiamo ora $45$ differenze, con al più $2$ differenze uguali. Per pigeon hole, vi saranno quindi almeno $9$ coppie di differenze uguali. Come prima, se una coppia di differenze non ha alcun elemento in comune, abbiamo vinto. Se due coppie distinte di differenze hanno lo stesso elemento in comune in comune, abbiamo nuovamente vinto: siano $x_1-k=k-x_2$ e $y_1-k=k-y_2$. Effettivamente $\{ x_1;x_2;y_1;y_2 \}$ verifica la tesi. Pertanto le $9$ coppie di differenze uguali hanno tutte un elemento in comune distinto tra loro. Ma questo è assurdo, poiché vi sarebbe una coppia che dovrebbe avere come elemento in comune $a_1$ oppure $a_{10}$, che sono elementi che non hanno $a_i$ minore oppure $a_i$ maggiore. Da questo segue la tesi.
nassus95
Messaggi: 79
Iscritto il: 14 giu 2012, 11:06

Re: 46

Messaggio da nassus95 »

Ottimo :D
Vai pure
Rispondi