Dividiamo i sacchetti

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
ale.G
Messaggi: 63
Iscritto il: 22 nov 2010, 15:14
Località: Lunghezza

Dividiamo i sacchetti

Messaggio da ale.G » 02 dic 2011, 19:43

Alcune palline sono distribuite in $2n+1$ sacchetti. Supponiamo che, tolto un qualunque sacchetto, sia possibile suddividere i rimanenti in due gruppi di $n$ sacchetti, in modo che ciascun gruppo contenga lo stesso numero complessivo di palline. Dimostrare che i sacchetti contengono tutti lo stesso numero di palline.
I tuoi problemi te li puoi anche tenere: a me, invece, non dispiacerebbe avere un camper come questo !

mattteo
Messaggi: 41
Iscritto il: 18 ott 2011, 16:52

Re: Dividiamo i sacchetti

Messaggio da mattteo » 02 dic 2011, 21:47

Spero vada bene:
-Supposto che il sacchetto con meno palline abbia $ x $ palline, allora togliamo x palline a ogni sacchetto, notando che così facendo la tesi di partenza vale ancora, in quanto ogni coppia di n sacchetti che veniva confrontata prima perde $ n*x $ sacchetti, lasciando vera l'uguaglianza. Avremo così un sacchetto senza palline.
-Se togliamo un sacchetto con un numero di palline pari, allora il numero di sacchetti con un numero di palline dispari deve essere pari, poichè i due gruppi di sacchetti hanno ugual numero di palline e quindi la loro somma è pari.
Se togliamo un sacchetto con un numero dispari di palline, allora il numero di sacchetti restanti con un numero di palline dispari deve essere pari e quindi i sacchetti dispari devono essere dispari. Cio è impossibile perche il numero totale di sacchetti deve anche essere pari. L'unico caso possibile è che non ci sia neanche un sacchetto dispari, e quindi tutti i sacchetti devono essere con un numero di palline pari.
-Chiamiamo $ a_k $ il numero di palline del k-esimo sacchetto. Possiamo vedere la tesi come un sistema di $ 2n+1 $ equazioni con $ 2n+1 $ incognite, che sono gli $ a_k $. Possiamo dividere in ogni equazione ogni membro per 2, e quindi ogni termine. Ogni numero resta intero perchè i numeri sono tutti pari e le equazioni restano vere. Possiamo quindi affermare che possiamo dimezzare il numero di palline in ogni sacchetto lasciando inalterata la tesi.
-Se dopo la divisione per 2 ogni sacchetto ha pari palline ripetiamo il procedimento fino a quando non ci sarà almeno un sacchetto con palline in numero dispari. Ma se ciò avverrà abbiamo dimostrato che è impossibile che la tesi sia vera con dei sacchetti con un numero dispari di palline. L'unico numero che diviso per 2 per "infinite" volte resta pari è 0, e quindi ogni sacchetto ha 0 palline.
-Ricordiamo ora che abbiamo tolto x palline da ogni sacchetto. Abbiamo quindi dimostrato che ogni sacchetto ha x palline, che è la tesi

Avatar utente
kalu
Messaggi: 297
Iscritto il: 23 nov 2010, 16:52
Località: Pisa

Re: Dividiamo i sacchetti

Messaggio da kalu » 05 dic 2011, 17:08

Sia $ S $ il numero totale di palline. Siano $ x $ e $ y $ le quantità di palline presenti in due generici sacchetti. Voglio dimostrare per induzione che $ x \equiv y $ (mod $ 2^n $) $ \forall n $ (da cui seguirebbe immediatamente che $ x=y $).
Caso $ n=1 $.
Escludiamo il sacchetto contenente $ x $ palline: rimangono $ S-x $ palline (che deve essere pari). Escludendo invece $ y $, ne rimangono $ S-y $ (ancora pari). Quindi $ 2 \mid (S-x)-(S-y) $, da cui $ x \equiv y $ (mod $ 2 $).
Passo induttivo.
Supponiamo che $ x \equiv y \equiv \alpha $(mod $ 2^n $) (il che significa che tutti i sacchetti contengono un numero di palline congruo ad $ \alpha $, dal momento che $ x $ e $ y $ sono generici). Escludiamo $ x $, e suddividiamo nei due gruppi le restanti palline. Il primo gruppo contiene $ n $ sacchetti tutti congrui ad $ \alpha $, quindi contiene in totale $ k2^n+ \alpha n $ palline per qualche intero $ k $. L'altro gruppo ne contiene altrettante. Possiamo quindi scrivere $ S-x=2(k2^n+ \alpha n) $. Analogamente, escludendo $ y $, abbiamo che $ S-y=2(h2^n+ \alpha n) $ per qualche $ h $. $ y-x=(S-x)-(S-y)=2(k2^n+ \alpha n)-2(h2^n+ \alpha n)=(h-k)2^{n+1} $.
Pota gnari!

Rispondi