Si dimostri che dati comunque n interi positivi a_1,.....,a_n
è sempre possibile sceglierne alcuni (eventualmente tutti od uno
solo) in modo che la loro somma sia divisibile per n.
Problema ammissione sssup
-
alexlor8083
- Messaggi: 11
- Iscritto il: 10 ott 2007, 20:23
- Località: Aci Catena
Si dovrebbe risolvere con una classica applicazione del principio di Dirichlet (il meglio conosciuto Pigeonhole Principle).
Consideriamo $ n $ termini del tipo:
$ (a_n + a_{n-1} + a_{n-2} + ... + a_1) $, $ (a_{n-1} + a_{n-2} + a_{n-3}+ ... + a_1) $, $ ( a_{n-2} + a_{n-3}+ ... + a_1) $, ... , $ (a_2 + a_1) $, $ a_1 $.
Se uno di essi e' divisibile per $ n $ abbiamo risolto. Se nessuno e' divisibile, ci saranno $ n $ resti della divisione per $ n $ diversi da zero. Ma di resti della divisione per $ n $ diversi da $ 0 $ ce ne sono $ n-1 $. Quindi, per il Pigeonhole Principle, ci sono almeno due di quei termini elencati prima che hanno resti uguali nella divisione per $ n $.
Se ora prendo il piu' piccolo di questi due termini e lo sottraggo al piu grande ottengo una somma di alcuni dei numeri $ a_i $ che ha resto $ 0 $ nella divisione per $ n $. CVD.
Spero di non essere stato troppo involuto nella descrizione.
Ciao.
Consideriamo $ n $ termini del tipo:
$ (a_n + a_{n-1} + a_{n-2} + ... + a_1) $, $ (a_{n-1} + a_{n-2} + a_{n-3}+ ... + a_1) $, $ ( a_{n-2} + a_{n-3}+ ... + a_1) $, ... , $ (a_2 + a_1) $, $ a_1 $.
Se uno di essi e' divisibile per $ n $ abbiamo risolto. Se nessuno e' divisibile, ci saranno $ n $ resti della divisione per $ n $ diversi da zero. Ma di resti della divisione per $ n $ diversi da $ 0 $ ce ne sono $ n-1 $. Quindi, per il Pigeonhole Principle, ci sono almeno due di quei termini elencati prima che hanno resti uguali nella divisione per $ n $.
Se ora prendo il piu' piccolo di questi due termini e lo sottraggo al piu grande ottengo una somma di alcuni dei numeri $ a_i $ che ha resto $ 0 $ nella divisione per $ n $. CVD.
Spero di non essere stato troppo involuto nella descrizione.
Ciao.