OliForum Matematico

Alcune palline sono distribuite in 2n+1 sacchetti. Supponiamo che,tolto un qualunque sacchetto, sia possibile dividere i rimanenti in due gruppi di n sacchetti, in modo tale che ciascun gruppo contenga lo stesso numero di palline. Dimostrare chi sacchetti hanno tutti lo stesso numero di palline.

P.S. mi linkate il post dove alcuni utenti avevano risolto i vecchi cesenatico? Non riesco a trovarlo...

Violenza mode: ON

Siano $x_1;...;x_{2n+1}$ il numero di palline contenute nei sacchetti. Poiché se ad ogni $2n+1$-upla di $x_i$ aggiungo una costante ad ogni termine la condizione si conserva, supponiamo wlog che $x_{2n+1}=0$.

Ora: consideriamo la matrice $2n$ per $2n$, in cui in ogni riga ci stanno rispettivamente $n$ uni, $n-1$ meno uni (o viceversa) e $1$ zero e dove nell'$i$-esima riga consideriamo la condizione ottenuta sulle varie $x$ togliendo il sacchetto $2n+1-i$.

Dimostriamo che il determinante di questa matrice è un intero (ovvio, è formata da termini interi) nonzero. Per farlo, dimostreremo che è dispari. Supponiamo quindi wlog che gli uni siano meno uni (tanto stiamo essenzialmente ragionando modulo $2$). Ricordiamo ora che la nostra matrice è fatta da uni ovunque tranne che su una diagonale, in cui ci sono zeri.

Supponiamo ora per assurdo che esistano interi $a_1;a_2;...;a_{2n}$ e vettori $v_1;...;v_{2n}$ tali che $a_i \in \{ 0;1 \}$ e che $v_i$ sia un vettore di dimensione $2n$ formato da tutti uni tranne che da uno zero in posizione $i$.

Supponiamo che il vettore $\sum{i=1}^{2n} a_iv_i$ sia "nullo modulo $2$ in ogni sua componente (eh?)" (perché non c'è la F bella in sto cazzo di latex?) per qualche scelta di $a_i$ tutti non contemporaneamente nulli. Poiché la somma delle componenti dei vari $v_i$ è dispari, sicuramente il numero di $a_i$ uguali a $1$ dev'essere pari. Pertanto, consideriamo il vettore $w=[1;...;1]$, di dimensione $2n$ e $w_i=v_i+w$. Allora $\sum{i=1}^{2n} a_iv_i$ è nullo se e solo se $\sum{i=1}^{2n} a_iw_i$ è nullo, poiché appunto aggiungendo un numero pari di volte $w$ non succede nulla di particolare. Ma come è fatta la matrice per i nostri $w_i$? È fatta solo da zeri, eccetto una diagonale formati da uni. Ma allora il determinante di questa matrice è uno, pertanto esiste una sola scelta di $a_i$ che annulla $\sum{i=1}^{2n} a_iw_i$ (che è ovviamente la scelta di annullarli tutti), che quindi è l'unica che annulla $\sum{i=1}^{2n} a_iv_i$, quindi essenzialmente i vettori $v_1;...;v_{2n}$ sono linearmente indipendenti quindi ci sta una sola soluzione, che è ovviamente $x_i=0$ per ogni $i$.

Quindi: poiché se $x_{2n+1}=0$ allora $x_i=0$ per ogni $i$ e il problema è invariante per traslazione, allora $x_i$ è costante al variare di $i$, da cui segue la tesi.

Grazie Giove!

Ehm...

Anche per me la soluzione di Troleito era molto difficile da capire, tant'è che non ci ho nemmeno provato... la tua, simone, mi sembra più facile, anche per chi non è esperto

Uhm, non ho letto bene tutta la tua soluzione, anche perché dovresti poterti fermare alle prime righe!
Ovvero, detta $ M $ la matrice $2n\times 2n $ dove nella riga $ i $ ci sono: uno 0 in posizione $ i $, $ n-1 $ meno uni nelle posizioni dei sacchetti in gruppo con $ x_{2n+1} $, $ n $ uni per gli altri sacchetti nell'altro gruppo; chiamiamo poi $ v $ il vettore colonna degli $ x_i $.
Alllora sappiamo che $ M\cdot v=0 $; ma $\det M\neq0 $, quindi l'unica soluzione è quella con tutti zeri...

Drago96 ha scritto:ma $\det M\neq0 $

Eh beh, questa è tutta la mia parte dopo

Dipende che modo per calcolare il determinante usiamo... se dici "facciamo le somme dei prodotti delle diagonali" allora è immediato, no?
Poi boh, non so nemmeno come si dimostrano queste cose, ne abbiamo solo accennto a scuola e non ho approfondito molto...

Uhm, non c'è una formula facile che lega il determinante a prodotti di diagonali per $n>3$...

Mi è stato fatto notare...
Grazie, approfondirò come si deve allora!

E una dimostrazione come quella di simone? Andrebbe bene in gara, senza dover ricorrere alle matrici?

matpro98 ha scritto:E una dimostrazione come quella di simone? Andrebbe bene in gara, senza dover ricorrere alle matrici?

Sì, andrebbe pure meglio in gara, visto che le matrici sono pure roba extraolimpica (e quindi KKKKKKKASTA). Comunque l'ho scritta comunque tanto per, così, per fare un po' il figo

Troleito br00tal ha scritto:Comunque l'ho scritta comunque tanto per, così, per fare un po' il figo

Se quello che so su di te è vero, non ne hai bisogno

Beh insomma, c'è gente decisamente più potente di me in giro, tanti, Però mi commuovi ç_ç

Sono riuscito a far commuovere te... adesso mi sento potente io...

Però simone ha fatto una bella soluzione anche se non è il superfigo della matematica e merita anche lui tanto affetto