Easy 1993

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
NicolasRossi
Messaggi: 48
Iscritto il: 18 mar 2013, 22:33
Località: Senise (PZ)

Easy 1993

Messaggio da NicolasRossi » 17 set 2013, 18:37

Si consideri una scacchiera 10 X 10 e in ogni sua casella siano indicati ordinatamente i numeri da $1$ a $100$ incominciando dalla prima casella in alto a sinistra, andando verso destra fino a terminare la prima riga e poi proseguendo con la seconda riga sempre da sinistra a destra, fino
ad arrivare alla centesima casella in basso a destra. Supponiamo ora di cambiare i segni a $50$ di questi numeri con la condizione che in ogni riga e in ogni colonna ci siano tanti numeri positivi quanti negativi. Si dimostri che, dopo tale cambiamento, la somma di tutti i numeri è zero.
"Per tre cose vale la pena di vivere: la matematica, la musica, l'amore." [cit.]

_Ipazia_
Messaggi: 50
Iscritto il: 23 feb 2013, 15:23

Re: Easy 1993

Messaggio da _Ipazia_ » 18 set 2013, 18:59

Provo..
Chiamo $ n $ la somma (in valore assoluto) di tutti i numeri negativi della tabella, $ p $ la somma dei numeri positivi. devo dimostrare che, con la disposizione richiesta, $ n=p $.
Inizio considerando la tabella riga per riga: nell'ultima riga ogni numero può essere scritto come $ 90+x $ , con $ x $ che varia da 1 a 10. Quindi inizio a distribuire il 90 fra $ n $ e $ p $. siccome in ogni riga ci sono 5 numeri negativi e 5 positivi, necessariamente diventa $ 5*90 $ va in $ p $, e sempre $ 5*90 $ in $ n $. Faccio lo stesso ragionamento per le altre righe, riscrivendo ogni numero con $ x + 90,80...10,0 $ (a seconda della riga). Quindi $ p $ e $ n $ diventeranno $ p=n=90*5+80*5+70*5+60*5+50*5+40*5+30*5+20*5+10*5 $ e nella tabella mi resteranno, in ogni riga, i numeri da 1 a 10. Per distribuire questi numeri considero le colonne: della prima colonna 5 numeri andranno in $ p $ e 5 in $ n $ e così per le altre colonne. Siccome i numeri in ogni colonna sono fra loro uguali, $ p $ e $ n $ si manterranno uguali, come volevasi dimostrare! E' giusto?
ps: mi rendo conto della pessima esposizione ( :oops: ) , sto imparando ora a scrivere le dimostrazioni, mi potete aiutare? :)
“SE ASCOLTO DIMENTICO, SE GUARDO IMPARO, SE FACCIO CAPISCO”

Gottinger95
Messaggi: 481
Iscritto il: 01 lug 2011, 22:52

Re: Easy 1993

Messaggio da Gottinger95 » 18 set 2013, 22:45

Ciao Ipazia! Io avevo pensato alla stessa dimostrazione, e avevo in mente due formalizzazioni. Visto che volevi una mano in questa parte, te le propongo tutte e due :)

Versione non formale:
Possiamo immaginare di scomporre la nostra scacchiera in due scacchiere sovrapposte: una è fatta da 10 righe con i numeri da 1 a 10, l'altra da 10 colonne con i numeri da 0 a 9. Il numero nella scacchiera originaria è naturalmente 10 volte il numero scritto nella seconda più il numero scritto nella prima.
Consideriamo la prima scacchiera. Visto che in ogni colonna devo prendere 5 numeri positivi e 5 negativi, e che in ogni colonna i numeri sono uguali, la somma di tutti gli elementi è 0. Discorso analogo vale per l'altra scacchiera. Perciò la somma dei numeri nella prima scacchiera (che è 0) più 10 volte la somma dei numeri nella seconda scacchiera (che è 0) è 0.

Versione formale:
Sia \(f(i,j)\) il numero scritto nella casella \((i,j)\) con il segno che abbiamo scelto, con centro di riferimento nel vertice in alto a sinistra della scacchiera. Vale \(f(i,j) = 10j+i+1\).
Siano:
1. \(a_i\): la somma di tutte le coordinate \(j\) (cambiate di segno se il numero nella casella \((i,j)\) è cambiato di segno) alla riga \(i\);
2. \(b_j\): la somma di tutte le coordinate \(i\) (cambiate di segno bla bla) alla colonna \(j\);

Facendo un double-counting su righe e colonne (ricordando che in ogni colonna metà sono cambiati di segno) abbiamo che
\(\displaystyle \sum_{i=1}^{2n}{a_i} = \sum_{j=1}^{2n}{ nj -nj} = 0\)
E ugualmente
\(\displaystyle \sum_{j=1}^{2n}{b_j} = \sum_{i=1}^{2n}{ nj -nj} = 0\)
Perciò
\(\displaystyle \sum_{0 \leq i,j \leq 2n-1}{f(i,j)} = \sum_{i=1}^{2n}{a_i} + 10 \sum_{j=1}^{2n}{b_j} = 0\)
I termini noti (cioè 1) delle \(f\) non vanno considerati perchè metà erano positivi, metà erano negativi, quindi si semplificano.
-----------------------------------
Diciamo che con questa versione si capisce facilmente che l'unica cosa importante era la configurazione dei + e dei - e che il numero fosse una combinazione lineare delle coordinate. Perciò non importa nè che fosse \(2n = 10\), nè che le dimensioni della scacchiera fossero 2 (chi ci impedisce di ripetere un ragionamento simile su tante dimensioni), nè che \(f(i,j) = 10j+i+1\) (e non per esempio \(f(i,j) = 1986 i + 1990 j +2002\), le date di nascita delle mie sorelle).

Spero di essere stato d'aiuto! :D
-----------------------------------
Nota, che puoi anche non leggere e sono solo delir..ehm generalizzazioni del problema.

Ti dirò di più: diciamo che nel problema abbiamo assegnato alle caselle i coefficienti \(+1\) e \(-1\) in modo che in ogni riga e in ogni colonna ci fossero lo stesso numero di +1 e -1; ma quello che abbiamo effettivamente usato nel double counting era che la somma dei coefficienti assegnati in una certa riga o in una certa colonna fosse 0! Quindi si potrebbe formulare il problema in termini più generali così:

Siano \(a_1, \ldots, a_{k+1} \in \mathbb{R}\) assegnati. Consideriamo un ipercubo \(2n\) x \(\ldots\) x \(2n\) di dimensione \(k\), che chiamiamo \(S\) (si dirà così? boh!).
Ad ogni casella \(X = (x_1, \ldots, x_k)\) con \(X \in S\) assegniamo due numeri:
1. \(f(X) = a_1x_1 + \ldots + a_k x_k+a_{k+1}\);
2. \(g(X)\) che per adesso è misterioso.
Sappiamo che, fissati \(k-1\) numeri \(y_1, \ldots, y_{k-1}\), si ha \(\displaystyle \sum_{i=1}^{2n}{g(y_1, \ldots, y_{k-1}, i)} = 0\) (non so come scrivere che si possono fissare qualsiasi \(k-1\) numeri nell'argomento, non per forza i primi \(k-1\), ma insomma il succo è quello).
Dimostrare che
\(\displaystyle \sum_{X \in S}{f(X)g(X)} = 0\)

Questo è un po' meno intuitivo del problema originale, ma la dimostrazione è identica a quella che ho scritto, solo con qualche lettera in più negli argomenti. Per un'ulteriore generalizzazione, in cui non usiamo il fatto che \(S\) è un ipercubo, ho postato il problema qui nella sezione di combinatoria :D
In definitiva: una dimostrazione pulita dà modo di capire più in profondità un problema, i.e. cosa serve e cosa non serve.
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe

NicolasRossi
Messaggi: 48
Iscritto il: 18 mar 2013, 22:33
Località: Senise (PZ)

Re: Easy 1993

Messaggio da NicolasRossi » 19 set 2013, 00:28

Esatto. In pratica posso sostituire ad ogni numero contenuto in una casella la sua cifra dell'unità. Sommo lungo le colonne e ho la tesi.

Ringrazio Gottinger per la generalizzazione... Domani ci do un occhiata ;)
"Per tre cose vale la pena di vivere: la matematica, la musica, l'amore." [cit.]

_Ipazia_
Messaggi: 50
Iscritto il: 23 feb 2013, 15:23

Re: Easy 1993

Messaggio da _Ipazia_ » 19 set 2013, 21:21

Bene, bel problemino!
@Gottinger95 : grazie mille per la dimostrazione formale! è proprio ciò che dovrei imparare a fare :) interessante anche che il ragionamento si possa ripetere anche su più dimensioni... solo con qualche aggiustatina!
“SE ASCOLTO DIMENTICO, SE GUARDO IMPARO, SE FACCIO CAPISCO”

EvaristeG
Site Admin
Messaggi: 4780
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Re: Easy 1993

Messaggio da EvaristeG » 20 set 2013, 09:00

_Ipazia_ ha scritto:Provo..
...
ps: mi rendo conto della pessima esposizione ( :oops: ) , sto imparando ora a scrivere le dimostrazioni, mi potete aiutare? :)
In realtà quello che hai scritto andava praticamente bene, come dimostrazione. Al più, per scriverlo allo stesso modo, ma più comprensibile, potevi iniziare dalle unità :) (i numeri piccoli sono più facili!)

Tipo: se sommo i numeri su una colonna, questi avranno tutti la stessa cifra delle unità e metà di loro col segno più, metà col segno meno, quindi nella somma si cancelleranno e dunque posso sostituire tutte le cifre dell'unità con $0$ senza cambiare al somma della singola colonna; se lo faccio in ogni colonna, mi viene un quadrato pieno di multipli di 10 e dunque posso dividere tutto per 10. Ora ho un quadrato che ha tutti $\pm0$ sulla prima riga, tutti $\pm1$ sulla seconda riga fino a tutti $\pm9$ sulla decima riga, ancora con la regola che compaiono $5$ più e $5$ meno su ogni riga. Per lo stesso ragionamento di prima, la somma di ogni riga è $0$ e dunque la somma tutti gli elementi è $0$. Ma allora in quella originale la somma è $10\cdot 0=0$.

_Ipazia_
Messaggi: 50
Iscritto il: 23 feb 2013, 15:23

Re: Easy 1993

Messaggio da _Ipazia_ » 20 set 2013, 14:02

EvaristeG ha scritto: In realtà quello che hai scritto andava praticamente bene, come dimostrazione. Al più, per scriverlo allo stesso modo, ma più comprensibile, potevi iniziare dalle unità :) (i numeri piccoli sono più facili!)

Tipo: se sommo i numeri su una colonna, questi avranno tutti la stessa cifra delle unità e metà di loro col segno più, metà col segno meno, quindi nella somma si cancelleranno e dunque posso sostituire tutte le cifre dell'unità con $0$ senza cambiare al somma della singola colonna; se lo faccio in ogni colonna, mi viene un quadrato pieno di multipli di 10 e dunque posso dividere tutto per 10. Ora ho un quadrato che ha tutti $\pm0$ sulla prima riga, tutti $\pm1$ sulla seconda riga fino a tutti $\pm9$ sulla decima riga, ancora con la regola che compaiono $5$ più e $5$ meno su ogni riga. Per lo stesso ragionamento di prima, la somma di ogni riga è $0$ e dunque la somma tutti gli elementi è $0$. Ma allora in quella originale la somma è $10\cdot 0=0$.
Capito, grazie per il consiglio!
“SE ASCOLTO DIMENTICO, SE GUARDO IMPARO, SE FACCIO CAPISCO”

Rispondi