Le tasche piene di sassi e i sacchetti pieni di palline

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
matematto
Messaggi: 20
Iscritto il: 10 gen 2015, 15:32

Le tasche piene di sassi e i sacchetti pieni di palline

Messaggio da matematto » 02 mar 2018, 09:19

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.

Avatar utente
Gerald Lambeau
Messaggi: 335
Iscritto il: 17 mag 2015, 13:32
Località: provincia di Lucca

Re: Le tasche piene di sassi e i sacchetti pieni di palline

Messaggio da Gerald Lambeau » 02 mar 2018, 21:32

Per distrarmi dal fallimento facilmente evitabile della gara a squadre ho deciso di risolvere questo problema.
Supponiamo per assurdo che ce ne siano almeno due diversi. Intanto, chiamando $a_i$ il numero di palline nell'$i$-esimo sacchetto, siccome, detta $S$ la somma di tutti, $S-a_i$ deve essere divisibile per due, allora gli $a_i$ devono avere la stessa parità (quella di $S$).
Ora quindi $2 \mid a_i-a_j$ per ogni scelta di $i$ e $j$; allora, se ce ne sono almeno due diversi, la loro differenza non è $0$, quindi esiste una potenza di $2$ massima che divide questa differenza. Ha perciò senso considerare $i, j$ tali che $v_2(a_i-a_j)=e$ è il minimo possibile; siccome hanno tutti la stessa parità, $e \ge 1$.
Supponiamo wlog $a_i>a_j$, adesso $a_i-a_j=2^e \cdot d$ con $d$ dispari. Consideriamo di togliere il sacchetto $i$ e dividiamo gli altri nei gruppi (1), quello contenente il sacchetto $j$, e (2), entrambi con un numero totale $x$ di palline (ciò è possibile per ipotesi).
Se adesso scambio di posto i sacchetti $i$ e $j$ il gruppo (1) avrà somma $x+2^e \cdot d$, mentre il (2) sempre $x$. Adesso è chiaro che per raggiungere la configurazione voluta nel caso in cui sia il sacchetto $j$ ad essere tolto dobbiamo effettuare alcuni scambi tra i gruppi (1) e (2) (siccome il numero di sacchetti in ogni gruppo deve rimanere il solito, quelli del gruppo (1) che devono andare nel (2) sono tanti quanto quelli per cui vale il viceversa, quindi li accoppiamo e scambiamo le coppie).
Tuttavia, all'equilibrio entrambi i gruppi dovranno avere un totale di $(x+2^e \cdot d+x)/2=x+2^{e-1} \cdot d$ palline, cioè finiti gli scambi dobbiamo ottenere una differenza di $2^{e-1} \cdot d$, ma per come abbiamo scelto $e$ tutti gli scambi causeranno una differenza multipla di $2^e$ e quindi anche una volta fatti tutti il risultato sarà quello di ottenere una differenza multipla di $2^e$, ed essendo $d$ dispari $2^{e-1} \cdot d$ non è raggiungibile, quindi non sarebbe possibile rispettare le ipotesi, assurdo.
Il fatto che la negazione della tesi porti alla negazione delle ipotesi, porta alla tesi.
"If only I could be so grossly incandescent!"

matematto
Messaggi: 20
Iscritto il: 10 gen 2015, 15:32

Re: Le tasche piene di sassi e i sacchetti pieni di palline

Messaggio da matematto » 03 mar 2018, 17:37

Mi dispiace per la gara, comunque buona la soluzione!

Rispondi