17numeri

[jordan]

dimostrare che comunque si scelgano 17 numeri interi A1, A2, ..., A17 è possibile selezionarne due, ad esempio Ai e Aj, in modo che Ai + Ai+1 + Ai+2 + ... + Aj sia congruo 0 modulo 17 ps spero che questo non sia anche in quella rivista:-)

[Zoidberg]

Se 2 numeri tra i 17 dati hanno lo stesso resto si possono scegliere quelli come Ai e Aj...

Infatti Ai = 17*k e Aj=17*s
quindi posso scrivere la somma come
Ai + Ai+1 + Ai+2 + ... + Aj = Ai * 17 * (s - k) + 1 + 2 + 3 + ... + [17 * (s - k)-2] + [17 * (s - k)-1]
sommando il primo con l'ultimo, il secondo col penultimo si arriva ad un risultato multiplo di 17.

Se nessuno tra i numeri ha lo stesso resto vorrà dire che i numeri apparterranno ciascuno ad ognuna delle 17 classi di resto.
In questo caso potrò prendere come Ai e Aj il numero congruo 1 e quello congruo 16, oppure quello congruo 2 e quello congruo 15, e cosi via...
La dimostrazione è quasi uguale a sopra e non ho voglia di farla, anche perchè non so usare il latex e viene oltremodo brutta!

[jordan]

se due numeri Ai e Aj hanno la stessa classe di resto non è detto che quella classe sia 0...

[darkcrystal]

Penso che intendesse $ A_i + A_{i+1} + ... + A_{j-1} + A_j $...

Con questa interpretazione, basta considerare la somma degli elementi da a_1 a a_1, da a_1 a a_2, ..., da a_1 a a_17. Se una è zero mod 17 ho vinto, se no ce ne sono due con la stessa congruenza, e prendo la differenza (che è ancora la somma di termini consecutivi), ed è congrua a 0

Ciao!

[jordan]

darkcrystal, perfect

[Zoidberg]

se due numeri Ai e Aj hanno la stessa classe di resto non è detto che quella classe sia 0...

si è vero, ho considerato solo quel caso.
Se la classe è n dalla somma raccolgo 17*n e mi ricollego al caso congruo 0

[jordan]

x darkcristal, avevo letto veloce la tua soluzione...cioe..quello che devi dimostrare è che se fai tutte le somme da A1 a A2, da A1 a A3, e tutte quelle possibili..allo ci sta una sicuramente ke è multipla di 17!!!!

[darkcrystal]

Bah, ammesso di aver capito il problema, resto convinto della mia soluzione: proverò a rispiegarla... se faccio tutte le somme $ a_1, a_1+a_2, a_1+a_2+a_3, ..., a_1+...+a_{17} $, ottengo 17 numeri diversi. O uno di questi è zero modulo 17, e ho finito, oppure, per il pigeonhole, ne ho due con lo stesso resto mod 17. Ma allora la differenza fra questi due (che è ancora una somma di termini consecutivi, perchè in pratica tolgo la più "corta" dalla più "lunga", ottenendo così una somma dei termini che stavano nell'una ma non nell'altra, che sono consecutivi) è uno zero mod 17.

Spero sia più chiara.

Ciao!

[Marco]

x darkcristal, avevo letto veloce la tua soluzione...cioe..quello che devi dimostrare è che se fai tutte le somme da A1 a A2, da A1 a A3, e tutte quelle possibili..allo ci sta una sicuramente ke è multipla di 17!!!!

Beh, ma questo è evidentemente falso. Prendi $ a_1=1 $ e tutti gli altri 0...

[jordan]

mistake: x marco, fai la somma A2+A3 oppure A2+A3+...+A17 fa zero no?a me risulta che 0 è congruo zero mod 17..!!

[Marco]

Beh, che c'entra? Mica sono della forma
$ $\sum_{i=1}^k a_k $...

[3C273]

se faccio tutte le somme $ a_1, a_1+a_2, a_1+a_2+a_3, ..., a_1+...+a_{17} $, ottengo 17 numeri diversi. O uno di questi è zero modulo 17, e ho finito, oppure, per il pigeonhole, ne ho due con lo stesso resto mod 17. Ma allora la differenza fra questi due (che è ancora una somma di termini consecutivi, perchè in pratica tolgo la più "corta" dalla più "lunga", ottenendo così una somma dei termini che stavano nell'una ma non nell'altra, che sono consecutivi) è uno zero mod 17.

Non capisco cosa ci sia che non va nella dimostrazione di darkcrystal... cioè,

se faccio tutte le somme $ a_1, a_1+a_2, a_1+a_2+a_3, ..., a_1+...+a_{17} $, ottengo 17 numeri diversi.

questo non è vero, non sono per forza diversi (v. esempio di marco), ma non importa... il seguito della dimostrazione funziona benissimo lo stesso mi sembra, o sbaglio?

[moebius]

Anche secondo me la dimostrazione è corretta, a patto di sostituire la frase con: 'ottengo 17 numeri che hanno ovviamente al piu' 17 resti diversi modulo 17'. Ma non stento a credere che dark pensasse questo mentre sbagliava a scrivere