6° problema olimpiadi della matematica 2013
Buonasera a tutti,ne approfitto per ringraziare in anticipo tutti quelli che dedicheranno anche solo un po' di tempo a questo messaggio.veniamo al problema che è reperibile attraverso questo indirizzo http://olimpiadi.dm.unibo.it/wp-content ... co2013.zip
Qui però ne riporto il testo anticipando che non capisco la prima parte della soluzione.
Due maghi si esibiscono nel seguente numero. All’inizio il primo mago rinchiude il secondo mago in una cabina
dove non possa n´e vedere n´e sentire nulla. Per iniziare il gioco, il primo mago invita Daniele, un membro del
pubblico, a porre su ogni casella di una scacchiera n × n, a propria discrezione, una pedina bianca o nera.
Dopodich´e chiede a Daniele di indicargli una casella C a sua scelta. A questo punto, il primo mago sceglie una
casella D (non necessariamente diversa da C) e sostituisce la pedina che si trova su D con una dell’altro colore
(bianca con nera o nera con bianca).
Viene quindi aperta la cabina in cui era rinchiuso il secondo mago. Osservando la scacchiera, il secondo mago
riesce a indovinare qual `e la casella C. Per quali n i due maghi possono attuare una strategia tale che il loro
numero riesca sempre?
soluzione
Risolveremo un problema leggermente più generale: supponiamo che la scacchiera possa avere un
numero qualunque N di caselle, non necessariamente un quadrato. Mostreremo che i maghi hanno una strategia
se e solo se N `e potenza di due. Nel caso particolare N = n^2, segue che n deve essere potenza di due.
Qui inizia la parte che non capisco
Se c’`e una strategia, allora N `e potenza di due : Contiamo il numero Dc delle disposizioni di pedine che
il secondo mago associa a una determinata casella c. Da ogni possibile disposizione iniziale il primo mago può
raggiungere una di queste tramite precisamente una modifica, quindi ogni possibile disposizione deve essere
raggiungibile partendo da una delle disposizioni associate a c e cambiando precisamente una pedina. Siccome
ci sono N possibili cambi di pedina, Dc maggiore o uguale 2^N/N. D’altro canto la somma dei numeri Dc al variare di c fra le N possibili caselle `e minore di o uguale a 2^N. Ne segue che Dc = 2^N/N per ogni casella c, quindi N divide 2^N.
Ora riporto quello che capisco: data una scacchiera con N pedine esistono un massimo 2^n possibili combinazioni
Il secondo mago quando vede la scacchiera es N=4 (1 pedina bianca ,2 nera ,3 bianca ,4 nera) sa che questa composizione può derivare solo da 4 possibili scacchiere :1 nera,nera,bianca,nera;2 bianca ,bianca,bianca,nera;
3 bianca ,nera,nera,bianca; 4bianca,nera,bianca,bianca.
Ora non capisco la natura di Dc, ne cosa sia : "la somma dei numeri Dc al variare di c fra le N possibili caselle" che è minore o uguale a 2^N. potete farmi qualche esempio semplice per aiutarmi a capire meglio?
grazie ancora
Qui però ne riporto il testo anticipando che non capisco la prima parte della soluzione.
Due maghi si esibiscono nel seguente numero. All’inizio il primo mago rinchiude il secondo mago in una cabina
dove non possa n´e vedere n´e sentire nulla. Per iniziare il gioco, il primo mago invita Daniele, un membro del
pubblico, a porre su ogni casella di una scacchiera n × n, a propria discrezione, una pedina bianca o nera.
Dopodich´e chiede a Daniele di indicargli una casella C a sua scelta. A questo punto, il primo mago sceglie una
casella D (non necessariamente diversa da C) e sostituisce la pedina che si trova su D con una dell’altro colore
(bianca con nera o nera con bianca).
Viene quindi aperta la cabina in cui era rinchiuso il secondo mago. Osservando la scacchiera, il secondo mago
riesce a indovinare qual `e la casella C. Per quali n i due maghi possono attuare una strategia tale che il loro
numero riesca sempre?
soluzione
Risolveremo un problema leggermente più generale: supponiamo che la scacchiera possa avere un
numero qualunque N di caselle, non necessariamente un quadrato. Mostreremo che i maghi hanno una strategia
se e solo se N `e potenza di due. Nel caso particolare N = n^2, segue che n deve essere potenza di due.
Qui inizia la parte che non capisco
Se c’`e una strategia, allora N `e potenza di due : Contiamo il numero Dc delle disposizioni di pedine che
il secondo mago associa a una determinata casella c. Da ogni possibile disposizione iniziale il primo mago può
raggiungere una di queste tramite precisamente una modifica, quindi ogni possibile disposizione deve essere
raggiungibile partendo da una delle disposizioni associate a c e cambiando precisamente una pedina. Siccome
ci sono N possibili cambi di pedina, Dc maggiore o uguale 2^N/N. D’altro canto la somma dei numeri Dc al variare di c fra le N possibili caselle `e minore di o uguale a 2^N. Ne segue che Dc = 2^N/N per ogni casella c, quindi N divide 2^N.
Ora riporto quello che capisco: data una scacchiera con N pedine esistono un massimo 2^n possibili combinazioni
Il secondo mago quando vede la scacchiera es N=4 (1 pedina bianca ,2 nera ,3 bianca ,4 nera) sa che questa composizione può derivare solo da 4 possibili scacchiere :1 nera,nera,bianca,nera;2 bianca ,bianca,bianca,nera;
3 bianca ,nera,nera,bianca; 4bianca,nera,bianca,bianca.
Ora non capisco la natura di Dc, ne cosa sia : "la somma dei numeri Dc al variare di c fra le N possibili caselle" che è minore o uguale a 2^N. potete farmi qualche esempio semplice per aiutarmi a capire meglio?
grazie ancora
Risposte
Pensa a cosa fa il secondo mago: esce dal suo nascondiglio e, solo osservando la scacchiera, deve individuare senza possibilità di errore una precisa tra le $N$ caselle.
Cioè i due maghi, prima del trucco, si sono dovuti mettere d'accordo in una maniera tale da associare a ogni possibile "situazione sulla scacchiera" una precisa casella.
Il numero $D_c$ conta quante diverse "situazioni sulla scacchiera" indicano la casella $c$.
Ora, data una casella $c$ (quella dello spettatore) e data una "situazione qualsiasi sulla scacchiera", deve essere sempre possibile, per il primo mago, cambiare una delle pedine in modo tale da raggiungere una delle $D_c$ situazioni che, quando viste dal secondo mago, gli indicano che la casella scelta è proprio $c$.
Vista al contrario, la stessa cosa si può dire anche così:
A partire da una delle $D_c$ situazioni associate a una certa casella $c$, deve essere possibile, cambiando esattamente una pedina, di raggiungere una "situazione qualsiasi sulla scacchiera".
In quanti modi si può cambiare una delle pedine? $N$, siccome questo è il numero di pedine.
Quante "situazioni" possono essere raggiunte cambiando una pedina, a partire da una di quelle $D_c$? Sono $N\cdot D_c$
Quante "situazioni" sono possibili in tutto? $2^N$, siccome ognuna delle $N$ pedine può essere bianca o nera.
Quindi, "traducendo" la frase scritta in blu, deve accadere che $N\cdot D_c>=2^N$
Equivalentemente, $D_c >= 2^N / N$
Ora, variando $c$ tra tutte le caselle della scacchiera, quanto varrà la somma tra tutti i $D_c$? Al massimo $2^N$, siccome questo è il numero di TUTTE le configurazioni possibili.
Da questo segue che la disuguaglianza scritta prima diventa un'uguaglianza, cioè $D_c = 2^N / N$
Altrimenti la somma totale tra tutti i $D_c$ sarebbe maggiore di $2^N$.
$D_c$ è un numero intero, quindi $N$ deve essere divisore di $2^N$.
Segue che $N$ deve essere una potenza di due.
Cioè i due maghi, prima del trucco, si sono dovuti mettere d'accordo in una maniera tale da associare a ogni possibile "situazione sulla scacchiera" una precisa casella.
Il numero $D_c$ conta quante diverse "situazioni sulla scacchiera" indicano la casella $c$.
Ora, data una casella $c$ (quella dello spettatore) e data una "situazione qualsiasi sulla scacchiera", deve essere sempre possibile, per il primo mago, cambiare una delle pedine in modo tale da raggiungere una delle $D_c$ situazioni che, quando viste dal secondo mago, gli indicano che la casella scelta è proprio $c$.
Vista al contrario, la stessa cosa si può dire anche così:
A partire da una delle $D_c$ situazioni associate a una certa casella $c$, deve essere possibile, cambiando esattamente una pedina, di raggiungere una "situazione qualsiasi sulla scacchiera".
In quanti modi si può cambiare una delle pedine? $N$, siccome questo è il numero di pedine.
Quante "situazioni" possono essere raggiunte cambiando una pedina, a partire da una di quelle $D_c$? Sono $N\cdot D_c$
Quante "situazioni" sono possibili in tutto? $2^N$, siccome ognuna delle $N$ pedine può essere bianca o nera.
Quindi, "traducendo" la frase scritta in blu, deve accadere che $N\cdot D_c>=2^N$
Equivalentemente, $D_c >= 2^N / N$
Ora, variando $c$ tra tutte le caselle della scacchiera, quanto varrà la somma tra tutti i $D_c$? Al massimo $2^N$, siccome questo è il numero di TUTTE le configurazioni possibili.
Da questo segue che la disuguaglianza scritta prima diventa un'uguaglianza, cioè $D_c = 2^N / N$
Altrimenti la somma totale tra tutti i $D_c$ sarebbe maggiore di $2^N$.
$D_c$ è un numero intero, quindi $N$ deve essere divisore di $2^N$.
Segue che $N$ deve essere una potenza di due.
Grazie per la disponibilità e per la risposta chiara e precisa.ora è tutto un po' più chiaro
Invidio ludovico1987 perché a me continua a non essere chiaro. Chiedo quindi a milizia96 o qualche altro volenteroso di spiegarmi le cose riferendosi a questo particolare caso: ci sono 4 caselle ed in tutte Daniele ha messo una pedina bianca; poi ha indicato la casella 1. Con quale strategia i due maghi possono comunicarsi quella scelta? E se Daniele ne avesse indicata un'altra o se avesse usato anche qualche pedina nera?
Attenzione: finora abbiamo solo dimostrato che è necessario che $N$ sia una potenza di 2.
Non abbiamo ancora verificato che questa condizione sia anche sufficiente ...
Non abbiamo ancora verificato che questa condizione sia anche sufficiente ...
Effettivamente la risposta ufficiale iniziava con "Se c’è una strategia", ma mi sembra insensato dimostrare che una condizione è necessaria per ottenere qualcosa di non ottenibile. Vero che non ci sono contraddizioni matematiche, ma è come se dimostrassimo che per essere invulnerabili è necessario essere biondi.
Comunque, grazie per la risposta.
Comunque, grazie per la risposta.
Guarda che il senso c'è.
Proprio perché noi abbiamo intenzione di dimostrare che la strategia esiste se e solo se $N$ è potenza di $2$.
Noi abbiamo fatto: se $N$ non è potenza di $2$, allora non esiste la strategia.
Quello che dobbiamo ancora fare: se $N$ è potenza di $2$, allora esiste la strategia.
Per concludere è necessario dimostrare entrambe le cose: noi abbiamo incominciato con la prima.
Proprio perché noi abbiamo intenzione di dimostrare che la strategia esiste se e solo se $N$ è potenza di $2$.
Noi abbiamo fatto: se $N$ non è potenza di $2$, allora non esiste la strategia.
Quello che dobbiamo ancora fare: se $N$ è potenza di $2$, allora esiste la strategia.
Per concludere è necessario dimostrare entrambe le cose: noi abbiamo incominciato con la prima.
Per $N=2$ una strategia può essere: se nella casella 1 c'è una pedina bianca, C è la 1; altrimenti C è la 2. Per tutti gli altri casi non riesco però ad immaginare nessuna strategia, e quindi ritengo impossibile dimostrare che "se N è potenza di 2, allora esiste la strategia" e resto del mio parere sull'insensatezza.
In realtà è possibile dimostrare che la strategia esiste per ogni $N$ potenza di $2$.
Solo che io ho già letto la soluzione ufficiale, quindi mi sembra giusto lasciare campo libero a qualcuno che volesse cimentarsi.
Comunque non è detto che bisogna proprio trovare una strategia per ogni $N$ potenza di $2$. Basta dimostrare che esiste (nel senso: sai che c'è ma non sai com'è).
Solo che io ho già letto la soluzione ufficiale, quindi mi sembra giusto lasciare campo libero a qualcuno che volesse cimentarsi.
Comunque non è detto che bisogna proprio trovare una strategia per ogni $N$ potenza di $2$. Basta dimostrare che esiste (nel senso: sai che c'è ma non sai com'è).
Pienamente d'accordo: lasciamo campo libero a chi vuole cimentarsi. A me basta che mi mostrino che c'è una strategia per $N=4$, indicandomela.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo