Piccioni milanesi!

[enomis_costa88]

Questo era l'ultimo quesito della gara dell'unimi, penso sia estremamente importante e istruttivo averne visto almeno uno analogo una volta nella vita.

Dati n numeri interi dimostrare che posso sempre sceglierne alcuni la cui somma sia multipla di n.

Buon lavoro!

[=Betta=]

Scusami, ma non ho proprio capito... Ma gli n numeri devono essere consecutivi? E cos' è che dev'essere multiplo di n?

[edriv]

Se non ha detto che sono consecutivi, vuol dire che possono essere anche non consecutivi...

Se dice che la somma di alcuni di quei numeri dev'essere multipla di n... sarà quella a dover essere multipla di n. Insomma, esiste un sottoinsieme di quell'insieme di interi tale che la somma di tutti i numeri che contiene è un multiplo di n.

[HiTLeuLeR]

Ma com'è che in queste gare made in Italy non si propongono mai (?) problemi originali?

[uchiak]

vediamo....
se divido a_1 , a_1 + a_2,...., a_1+....+a_n per n e trovo un resto zero il problema è risolto, sennò per il cassetto ce ne sono due con lo stesso resto e facendo la differenza risolvo il problema.

[Lupacante]

ce ne sono due con lo stesso resto e facendo la differenza risolvo il problema.

facendo la differenza di cosa?

[EUCLA]

Volendo riscriverla meglio...

Sia la successione di $ n $ numeri dati: $ a_1,a_2,...,a_n $

Sia $ \displaystyle B_t=\sum_{i=1}^{t}a_i $. I vari $ B $ formano ancora una successione di $ n $ numeri.

I resti modulo $ n $ sono $ n $, tra cui uno è lo $ 0 $

Caso 1: esiste $ B\equiv 0 \pmod n $

Caso 2: un tale $ B $ non esiste, allora due tra gli $ n \ B $ dovranno avere per pigeonhole la stessa congruenza modulo $ n $.

Ne faccio la differenza fra questi due che hanno la stessa congruenza, ottengo una cosa divisibile per $ n $ come richiesto.

[Lupacante]

ma la consegna dice somma, non differenza

[EUCLA]

Allora, la differenza che dicevamo la fai tra i $ B $

Ad esempio prendi $ B_2\equiv a \pmod n, B_{4}\equiv a \pmod n $

Per costruzione dei $ B $: $ B_{2}=a_1+a_2, B_{4}=a_1+a_2+a_3+a_4 $

La loro differenza è una somma (ed è congrua a 0 modulo n)!

[Lupacante]

grazie eucla adesso capisco

[Cassa]

Allora, la differenza che dicevamo la fai tra i $ B $

Ad esempio prendi $ B_2\equiv a \pmod n, B_{4}\equiv a \pmod n $

Per costruzione dei $ B $: $ B_{2}=a_1+a_2, B_{4}=a_1+a_2+a_3+a_4 $

La loro differenza è una somma (ed è congrua a 0 modulo n)!

Come fai ad affermare che ci saranno sempre 2 somme con la stessa congruenza ad n?

[EUCLA]

Hai inizialmente $ n $ possibili congruenze.
Se però togli la possibilità che un $ B $ sia 0 modulo n, ne rimangono n-1.
Hai $ n \ B $, $ n-1 $ possibili congruenze → (piccioni)→ $ \exists B_a,B_b \vert B_a\equiv B_b \pmod n $

[Cassa]

Uh, vero! grazie!