OliForum Matematico

Siano dati n numeri nessuno dei quali divisibile per n. Si dimostri che la somma di alcuni di essi (da 2 a n) è divisibile per n.

Il problema è semplicissimo, infatti sono arrivato alla soluzione, ma solo in maniera intuitiva, e mi servirebbe una mano per teorizzarla e generalizzarla. Vi spiego la cosa "a parole mie": un numero può essere congruente modulo n al massimo ad n numeri da 0 ad n. Solo che siccome quando è congruente a 0 non si conta (perché sarebbe divisibile per n), abbiamo n-1 diversi tipi di congruenze. Inoltre abbiamo n numeri, per il principio dei cassetti, almeno uno sarà ripetuto. Se tutti gli n numeri sono congruenti ad 1 modulo n, bisogna sommarli tutti per avere un multiplo di n. Con altri casi provo a tentativi (ponendo n uguale ad un numero che scelgo a caso) ed effettivamente mi riesce. Non riesco però a spiegare bene perché, mi aiutate?
Grazie

Posso aiutarti solo per il caso in cui sono tutti uguali...

Ponendoli tutti uguali a $ n+k $, ovviamente sono $ \equiv k \ (mod \ n) $. Sommandoli tutti si ottiene $ k +k +k... \ (n \ volte) = k \cdot n $
Ovviamente $ k \cdot n \equiv k \cdot 0 \equiv 0 $

Io avevo fatto un esercizio simile, ma con n+1 numeri, dimostrando che la differenza di due di essi era divisibile per n... (semplice applicazione dei cassetti, o piccioni)

Drago96 ha scritto:Posso aiutarti solo per il caso in cui sono tutti uguali...

Ponendoli tutti uguali a $ n-k $, ovviamente sono $ \equiv -k \ (mod \ n) $. Sommandoli tutti si ottiene $ -k -k -k... \ (n \ volte) = -k \cdot n $
Ovviamente $ -k \cdot n \equiv -k \cdot 0 \equiv 0 $

Io avevo fatto un esercizio simile, ma con n+1 numeri, dimostrando che la differenza di due di essi era divisibile per n... (semplice applicazione dei cassetti, o piccioni)

sì, infatti è preso da degli esercizi sul pigeonhole ...
comunque non capisco perché metti $ -k $, $ k $ non andrebbe bene lo stesso (e darebbe forse un tocco di "universalità" in più? )

domx ha scritto:sì, infatti è preso da degli esercizi sul pigeonhole ...
comunque non capisco perché metti $ -k $, $ k $ non andrebbe bene lo stesso (e darebbe forse un tocco di "universalità" in più? )

Non so perchè, ma devo aver pensato "minori di n"...
Edito subito...

Ho ragionato un po' su cosa succede quando sono tutti diversi (a parte una coppia che fa parte della stessa classe di resto):
Semplicemente basta prendere $ k_1 \ e \ k_2 \ / \ k_1 + k_2 \equiv 0 \ (mod \ n) $ infatti ci saranno sempre due classi di resto "complementari"

Ora devo pensare un po' a cosa succede quando ci sono più numeri uguali...

sì, la cosa delle classi "complementari" l'avevo pensata anch'io ieri sera, non so perché prima mi sono dimenticato di scriverla...
comunque non sempre ci sono numeri "complementari", eppure riesce sempre...

Siano $ a_1, \dots a_n $ i numeri di partenza e $ b_1, \dots b_n $ una successione con $ b_i=a_1+\dots+a_i $. Suppongo per assurdo che nessuno dei $ b_i $ sia divisibile per n, altrimenti ho finito. Ma allora (per pigeonhole su n-1 resti e n numeri) esistono $ b_k, b_h $ (h>k) tali che valga $ b_k \equiv b_h \pmod n $, ma allora $ b_h-b_k=a_h+a_{h-1}+\dots +a_{k+1} $ è divisibile per n.

Sonner ha scritto:Siano $ a_1, \dots a_n $ i numeri di partenza e $ b_1, \dots b_n $ una successione con $ b_i=a_1+\dots+a_i $. Suppongo per assurdo che nessuno dei $ b_i $ sia divisibile per n, altrimenti ho finito. Ma allora (per pigeonhole su n-1 resti e n numeri) esistono $ b_k, b_h $ (h>k) tali che valga $ b_k \equiv b_h \pmod n $, ma allora $ b_h-b_k=a_h+a_{h-1}+\dots +a_{k+1} $ è divisibile per n.

non riesco a seguirti, potresti rispiegarmi la cosa in maniera più "semplice"?

Ci provo, spero di essere più chiaro

Dunque, considero queste somme (i $ b_i $): $ a_1 $, $ a_1+a_2 $, $ a_1+a_2+a_3 $, $ \dots $, $ a_1+\dots +a_n $.
Caso 1: una di quelle è divisibile per n, allora ho finito
Caso 2: nessuna di quelle è divisibile per n, ma allora almeno due di esse sono congrue modulo n. Infatti ho n-1 resti e n somme $ \rightarrow $ applico il pigeonhole. Quindi abbiamo, per qualche k, h (scelgo h>k): $ a_1+a_2+\dots +a_h \equiv a_1+a_2+\dots +a_k \pmod n \rightarrow a_{k+1}+a_{k+2}+\dots +a_h \equiv 0 \pmod n $ (portando tutto a sinistra). Quindi ho trovato una somma divisibile per n anche in questo caso.

Maledetto me che mi iscrivo all'Oliforum adesso!