n interi positivi

[BorisM]

Si dimostri che dati comunque $n$ interi positivi $a_{1}, a_{2}, ... a_{n}$ è sempre possibile sceglierne alcuni (eventualmente tutti od uno solo) in modo che la loro somma sia divisibile per n.

Avevo iniziato dicendo che naturalmente se vi è un $a_{i}\equiv 0 (mod n)$ sono apposto perchè naturalmente sceglierò quel numero.
Un altro caso potrebbe essere che tutti gli $a_{n}$ sono uguali ed è facile verificare che in questo caso scegliendoli tutti raggiungo il mio obbiettivo.
Ipotiziamo però che non ci siano $a_{i}\equiv 0 (mod n)$ e che siano tutti diversi tra loro. Sempre analizzando le classi resto avrò $n$ numeri congrui a $0,1,2...n-1 (mod n)$ quindi la mia dimostrazione si riduce alla domanda:
Dati $n$ numeri minori di $n$ è possibile sceglierne alcuni in modo tale che la loro somma sia $n$ ?
Qui mi blocco e non riesco ad andare avanti.. qualcuno sa darmi qualche dritta?

[onlyReferee]

Ciao BorisM
Nell'ultimo caso da te proposto, ossia che gli $a_1, a_2, ..., a_n$ siano tutti diversi e minori di $n$, puoi sfruttare la nota successione $\sum_{i = 1}^n i = {n (n + 1)} / 2$. Ovviamente per essere rigorosi qui abbiamo tutti i numeri inferiori ad $n$ e pertanto la stessa va riscritta come $\sum_{i = 1}^{n - 1} i = {n (n + 1)} / 2 - n = {n^2 + n -2n} / 2 = {n(n - 1)} / 2$. Ovviamente tale quantità è divisibile per $n$.
Resta però da considerare il caso, escludendo quelli da te già trattati, in cui vi siano alcuni degli $a_i$ (non tutti) uguali tra loro.

[BorisM]

Ciao BorisM
Nell'ultimo caso da te proposto, ossia che gli $a_1, a_2, ..., a_n$ siano tutti diversi e minori di $n$, puoi sfruttare la nota successione $\sum_{i = 1}^n i = {n (n + 1)} / 2$. Ovviamente per essere rigorosi qui abbiamo tutti i numeri inferiori ad $n$ e pertanto la stessa va riscritta come $\sum_{i = 1}^{n - 1} i = {n (n + 1)} / 2 - n = {n^2 + n -2n} / 2 = {n(n - 1)} / 2$. Ovviamente tale quantità è divisibile per $n$.
Resta però da considerare il caso, escludendo quelli da te già trattati, in cui vi siano alcuni degli $a_i$ (non tutti) uguali tra loro.

Ti ringrazio per la risposta, comunque sia penso di essere giunto ad una soluzione un pò più generale ragionando in questo modo:
Se si hanno $a_{n}$ interi ciò significa che il numero di sottoinsiemi possibili è $2^n$. Le classi resto possibili sono $0,1,2,...(n-1)$ e poichè $2^n>(n-1)$ come si può facilmente dimostrare per induzione, si ha per il principio dei cassetti che almeno 2 sottoinsiemi chiamiamoli $b$ e $c$ appartengano ad una stessa classe resto ovvero:
$b\equiv c (mod n)$
Quindi basterà semplicemente prendere il sottoinsieme $d=b-c$ che sarà sicuramente $d\equiv 0(mod n)$

[Gi8]

Ma se ad esempio $b= {a_1,a_2,a_3}$ e $c={a_4,a_5}$ non puoi fare $d=b-c$.
Lo puoi fare solo se $c sube b$

[BorisM]

Ma se ad esempio $b= {a_1,a_2,a_3}$ e $c={a_4,a_5}$ non puoi fare $d=b-c$.
Lo puoi fare solo se $c sube b$

Già hai ragione posso usare solo la somma...

[Martino]

Dato il tuo insieme di interi \( \displaystyle \{a_1,...,a_n\} \) prova ad applicare il principio dei cassetti alle somme \( \displaystyle b_i = a_1 + ... + a_i \) per \( \displaystyle i = 1 , ... , n \) .

[BorisM]

Dato il tuo insieme di interi \( \displaystyle \{a_1,...,a_n\} \) prova ad applicare il principio dei cassetti alle somme \( \displaystyle b_i = a_1 + ... + a_i \) per \( \displaystyle i = 1 , ... , n \) .

Scusa se ti rispondo solo ora ma ero sprovvisto di PC
Se non erro posso scegliere gli $a_{n}$ in $\frac{2n!}{n!n!}$ che è maggiore di $n$ per $n>1$
Ho quindi $n-1$ classi resto...
E qui mi blocco ma ciò non significa che io abbia almeno una somma di $a_{n}$ tale che sia multipla di $n$.
Quindi mi ritrovo un pò con il problema che avevo prima e non riesco ad andare avanti..

[Martino]

Considera le somme \( \displaystyle b_i = a_1 + \ldots + a_i \) . In altre parole \( \displaystyle b_1=a_1 \) , \( \displaystyle b_2=a_1+a_2 \) , ..., \( \displaystyle b_n = a_1+\ldots+a_n \) . Ottieni un insieme \( \displaystyle \{b_1,\ldots,b_n\} \) . Ora se uno tra i \( \displaystyle b_i \) è zero modulo \( \displaystyle n \) hai finito, quindi puoi escludere questo caso. Ma allora hai \( \displaystyle n \) numeri non divisibili per \( \displaystyle n \) , quindi appartengono ad al più \( \displaystyle n-1 \) classi resto modulo \( \displaystyle n \) e quindi esistono di sicuro due indici diversi \( \displaystyle i < j \) tali che \( \displaystyle b_i \equiv b_j \mod n \) . Considera la differenza \( \displaystyle b_j-b_i \) , cosa puoi dire?