OliForum Matematico

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!

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

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.

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

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.

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

facendo la differenza di cosa?

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.

ma la consegna dice somma, non differenza

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)!

grazie eucla adesso capisco

EUCLA ha scritto: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?

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 $

Uh, vero! grazie!