Cesenatico 1990/6

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
matty96
Messaggi: 343
Iscritto il: 21 apr 2010, 14:30
Località: Matelandia di Calabria (CS)

Cesenatico 1990/6

Messaggio da matty96 » 16 apr 2014, 17:00

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...
<<Se avessi pensato (se pensassi) che la matematica è solo tecnica
e non anche cultura generale; solo calcolo e non anche filosofia,
cioè pensiero valido per tutti, non avrei fatto il matematico (non
continuerei a farlo)>> (Lucio Lombardo Radice, Istituzioni di
Algebra Astratta).
Mathforum
$ \displaystyle\zeta(s)=\sum_{n=1}^\infty \frac {1}{n^s} $

Avatar utente
Troleito br00tal
Messaggi: 683
Iscritto il: 16 mag 2012, 22:25

Re: Cesenatico 1990/6

Messaggio da Troleito br00tal » 16 apr 2014, 20:24

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!

Avatar utente
simone256
Messaggi: 452
Iscritto il: 07 mag 2012, 16:10
Località: Crema

Re: Cesenatico 1990/6

Messaggio da simone256 » 16 apr 2014, 22:37

Ehm... :?:
Testo nascosto:
Propongo questa che non so se funziona perché per me quella di Troleito è aramaico :| :
Come detto all'inizio una disposizione che funziona è invariante allorché sottraiamo lo stesso numero di palline da ogni sacchetto; togliamo quindi $ m $ palline da ogni sacchetto dove $ m $ era il numero di palline che conteneva il sacchetto con meno palline all'inizio. Ora abbiamo almeno un sacchetto con $ 0 $ palline e altri sacchetti con un numero intero positivo o nullo di palline.
Ipotizziamo che in un sacchetto il numero di palline sia dispari: togliamo il sacchetto con $ 0 $ palline e dividiamo in due gruppi le palline restanti, il numero totale di palline deve quindi essere pari. Togliamo ora il sacchetto con un numero dispari di palline, il numero rimanente di palline è dispari pertanto non possiamo "dividere" i sacchetti.
Allora tutti i sacchetti hanno un numero pari di palline, se dimezziamo il numero in ogni sacchetto la disposizione sarà ancora valida; allo stesso modo però il numero di palline in ogni sacchetto deve essere ancora e ancora e ancora e.... Pari! L'unico numero divisibile infinite volte per $ 2 $ è proprio lo $ 0 $ quindi nello stato finale (e anche nel secondo passaggio dopo aver sottratto $ m $) tutti i sacchetti avranno $ 0 $ palline e inizialmente avevano tutti dentro lo stesso numero $ m $ di palline.
$ \mbox{ }\mbox{ } $And God said : $ \displaystyle c^2 \mu_0 \varepsilon_0 =1 $,
and then there was light.


$ \mbox{ }\mbox{ } $Tsune ni shinen kufu seyo

matpro98
Messaggi: 452
Iscritto il: 22 feb 2014, 18:42

Re: Cesenatico 1990/6

Messaggio da matpro98 » 16 apr 2014, 22:58

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 ;)

Avatar utente
Drago96
Messaggi: 1140
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Cesenatico 1990/6

Messaggio da Drago96 » 17 apr 2014, 09:04

Uhm, non ho letto bene tutta la tua soluzione, anche perché dovresti poterti fermare alle prime righe! :P
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...
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

Avatar utente
Troleito br00tal
Messaggi: 683
Iscritto il: 16 mag 2012, 22:25

Re: Cesenatico 1990/6

Messaggio da Troleito br00tal » 18 apr 2014, 22:01

Drago96 ha scritto:ma $\det M\neq0 $
Eh beh, questa è tutta la mia parte dopo

Avatar utente
Drago96
Messaggi: 1140
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Cesenatico 1990/6

Messaggio da Drago96 » 18 apr 2014, 22:07

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...
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

fph
Site Admin
Messaggi: 3613
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Cesenatico 1990/6

Messaggio da fph » 18 apr 2014, 22:46

Uhm, non c'è una formula facile che lega il determinante a prodotti di diagonali per $n>3$...
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Avatar utente
Drago96
Messaggi: 1140
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Cesenatico 1990/6

Messaggio da Drago96 » 18 apr 2014, 22:51

Mi è stato fatto notare... :)
Grazie, approfondirò come si deve allora!
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

matpro98
Messaggi: 452
Iscritto il: 22 feb 2014, 18:42

Re: Cesenatico 1990/6

Messaggio da matpro98 » 18 apr 2014, 23:05

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

Avatar utente
Troleito br00tal
Messaggi: 683
Iscritto il: 16 mag 2012, 22:25

Re: Cesenatico 1990/6

Messaggio da Troleito br00tal » 18 apr 2014, 23:21

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

matpro98
Messaggi: 452
Iscritto il: 22 feb 2014, 18:42

Re: Cesenatico 1990/6

Messaggio da matpro98 » 18 apr 2014, 23:34

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 ;)

Avatar utente
Troleito br00tal
Messaggi: 683
Iscritto il: 16 mag 2012, 22:25

Re: Cesenatico 1990/6

Messaggio da Troleito br00tal » 18 apr 2014, 23:51

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

matpro98
Messaggi: 452
Iscritto il: 22 feb 2014, 18:42

Re: Cesenatico 1990/6

Messaggio da matpro98 » 18 apr 2014, 23:59

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

Avatar utente
simone256
Messaggi: 452
Iscritto il: 07 mag 2012, 16:10
Località: Crema

Re: Cesenatico 1990/6

Messaggio da simone256 » 19 apr 2014, 00:27

Però simone ha fatto una bella soluzione anche se non è il superfigo della matematica e merita anche lui tanto affetto :cry:
$ \mbox{ }\mbox{ } $And God said : $ \displaystyle c^2 \mu_0 \varepsilon_0 =1 $,
and then there was light.


$ \mbox{ }\mbox{ } $Tsune ni shinen kufu seyo

Rispondi