N interi positivi
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?
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?
Risposte
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.
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.
"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.
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)$
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$
Lo puoi fare solo se $c sube b$
"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$
Già hai ragione posso usare solo la somma...
Dato il tuo insieme di interi [tex]\{a_1,...,a_n\}[/tex] prova ad applicare il principio dei cassetti alle somme [tex]b_i = a_1 + ... + a_i[/tex] per [tex]i = 1 , ... , n[/tex].
"Martino":
Dato il tuo insieme di interi [tex]\{a_1,...,a_n\}[/tex] prova ad applicare il principio dei cassetti alle somme [tex]b_i = a_1 + ... + a_i[/tex] per [tex]i = 1 , ... , n[/tex].
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..
Considera le somme [tex]b_i = a_1 + \ldots + a_i[/tex]. In altre parole [tex]b_1=a_1[/tex], [tex]b_2=a_1+a_2[/tex], ..., [tex]b_n = a_1+\ldots+a_n[/tex]. Ottieni un insieme [tex]\{b_1,\ldots,b_n\}[/tex]. Ora se uno tra i [tex]b_i[/tex] è zero modulo [tex]n[/tex] hai finito, quindi puoi escludere questo caso. Ma allora hai [tex]n[/tex] numeri non divisibili per [tex]n[/tex], quindi appartengono ad al più [tex]n-1[/tex] classi resto modulo [tex]n[/tex] e quindi esistono di sicuro due indici diversi [tex]i < j[/tex] tali che [tex]b_i \equiv b_j \mod n[/tex]. Considera la differenza [tex]b_j-b_i[/tex], cosa puoi dire?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo