I 7 nani e la strega cattiva

Ipazia · Inviato: Lun Feb 05, 2007 3:58 pm Oggetto: I 7 nani e la strega cattiva

C'erano una volta i 7 nani. La strega cattiva voleva vendicarsi perchè avevano aiutato Biancaneve, quindi decise di rapirli. Si appostò fuori dalla miniera, ma ne rapì solo 6 perchè quel giorno Dotto invece di andare in miniera a lavorare era andato in biblioteca a studiare. Dotto si accorse che i suoi amici erano stati rapiti e seguendo le tracce li trovò in una gabbia a casa della strega cattiva... spiando dalla finestra, sentì quello che la strega diceva ai 6 nanetti:
"Voglio mangiarvi per colazione domani mattina, ma siccome non voglio che la gente pensi di me che sono cattiva ho deciso di lasciarvi una possibilità di sopravvivere. Stasera vi metterò in celle separate, e metterò in testa a ciascuno di voi un cappello colorato, rosso oppure verde. Potrebbero essere tutti rossi o tutti verdi, oppure 2 rossi e 4 verdi, completamente a caso. Nessuno di voi può vedere gli altri, e non potete vedere nemmeno il cappello che avete in testa voi stessi. Fatto questo, a ciascuno di voi darò un'informazione: vi dirò quanti cappelli rossi e quanti verdi ci sono in testa agli altri 5 nani, escludendo quello che avete in testa voi. Per esempio, se i cappelli fossero messi così:
Brontolo - ROSSO
Cucciolo - VERDE
Mammolo - ROSSO
Eolo - ROSSO
Pisolo - ROSSO
Gongolo - VERDE
io direi a Brontolo che, escluso il suo cappello, ci sono 3 rossi e 2 verdi (attenzione, dirò quanti sono, ma NON chi li indossa), a Cucciolo direi che escluso il suo cappello ci sono 4 rossi e 1 verde, ecc. ecc.
Ovviamente nessuno di voi sentirà quello che dico agli altri, e non potete comunicare in nessun modo tra di voi. A questo punto, darò a ciascuno di voi un foglietto col suo nome, e ciascuno deve scrivere sul foglietto un colore, rosso oppure verde. Non può lasciare in bianco nè scrivere altro. Io controllerò che non abbiate imbrogliato e poi metterò i foglietti nel mio armadio; domani mattina verificherò le vostre risposte e se TUTTI avete indovinato il colore del vostro cappello vi lascerò andare, altrimenti, se anche uno solo ha sbagliato, vi mangio x colazione."
A questo punto i nanetti erano preoccupatissimi, perchè sapevano che, pur avendo informazioni sui cappelli degli altri, non potevano comunque indovinare con certezza il loro colore! Ma Dotto aveva sentito tutto dalla finestra e quando la strega se ne andò disse:
"Che cattiva la strega! Ma noi la fregheremo: io adesso vado a nascondermi nell'armadio dove la strega riporrà i foglietti. Voi, quando la strega vi darà le informazioni, fate così così e così bla bla bla........ bla bla bla e in questo modo ognuno di voi deciderà se scrivere rosso o verde. Mi raccomando fate come vi ho detto io, e ricordatevi che non potete scrivere nient'altro che rosso o verde altrimenti la strega vi uccide... State tranquilli, perchè io stanotte, da dentro l'armadio, prenderò i vostri foglietti e li correggerò tutti, in modo che quando domani la strega controllerà, troverà scritto su ogni foglietto il colore giusto!"
"Ma Dotto, tu non potrai vedere i nostri cappelli e non sentirai quello che ci dice la strega, leggerai solo il colore che ciascuno di noi ha scritto... come farai a capire i colori giusti e a correggere i biglietti?"
"Non preoccupatevi! Voi fate come vi ho detto per decidere se scrivere rosso o verde, e al resto ci penso io!!!"
E così fu... dovete vedere com'era arrabbiata la strega quando ha visto che tutti i colori dei cappelli erano stati "indovinati"!!!
E i 7 nani vissero felici e contenti.

_______________________________________________________________

LA DOMANDA:

1)COS'HA DETTO DI FARE DOTTO AI NANI, E COME FA POI LUI A CORREGGERE I FOGLIETTI?
_______________________________________________________________

ESTENSIONI DEL PROBLEMA PER CHI SI APPASSIONA:

2)GENERALIZZARE AL CASO DI n NANI (+ Dotto, il nano correttore): PER QUALI VALORI DI n LA STRATEGIA FUNZIONA? - abbastanza semplice una volta fatto il punto (1)
3)NEL PUNTO (2) SI SCOPRE CHE CI SONO DEI VALORI DI n PER CUI LA STRATEGIA TROVATA NON FUNZIONA: DIMOSTRARE CHE PER QUEI VALORI NON ESISTE NESSUNA STRATEGIA CHE FUNZIONA - problema interessantissimo, di cui ora abbiamo una bellissima dimostrazione, ma molto più complicato dei punti (1) e (2)
4)NEL PUNTO (3) E' STATO DIMOSTRATO CHE CI SONO VALORI DI n PER CUI NON ESISTE UNA STRATEGIA CHE FUNZIONA, OVVERO I NANI NON POSSONO AVERE LA CERTEZZA DI INDOVINARE. TROVARE UNA STRATEGIA CHE MASSIMIZZA LA PROBABILITA' DI INDOVINARE - stessa difficoltà del punto (2), si può risolvere anche senza aver risolto il punto (3)
5)CON LA STRATEGIA TROVATA NEL PUNTO (4), QUAL E' IL LIMITE DELLA PROBABILITA' DI INDOVINARE PER n CHE TENDE A INFINITO? - facile una volta risolto il punto (4) per chi conosce un po' di calcolo combinatorio... è soprattutto una cosa curiosa
6)GENERALIZZARE AL CASO DI n NANI E k COLORI POSSIBILI DEI CAPPELLI: CHE STRATEGIA SI PUO' UTILIZZARE? PER QUALI COPPIE (n,k) LA STRATEGIA FUNZIONA? DIMOSTRARE CHE PER LE ALTRE COPPIE NON ESISTE NESSUNA STRATEGIA CHE FUNZIONA (punto NON ancora risolto). PER LE COPPIE IN CUI NON ESISTE UNA STRATEGIA CHE FUNZIONA, TROVARE UNA STRATEGIA CHE MASSIMIZZA LA PROBABILITA' DI INDOVINARE E CALCOLARNE IL LIMITE PER n CHE TENDE A INFINITO.
_________________
Ciao!

.:Ipazia:.

carpao · Frequentatore del Forum Registrato: Sep 23, 2003 Messaggi: 434

Ipazia · Inviato: Lun Feb 05, 2007 4:32 pm Oggetto:

Carpao, tu sempre al volo, eh?! Me lo aspettavo... ma meno male che ci sono altri punti da risolvere! Ti aspetto per il punto (3)! Comunque complimenti!
_________________
Ciao!

.:Ipazia:.

carpao · Inviato: Lun Feb 05, 2007 4:54 pm Oggetto:

Ipazia · Inviato: Lun Feb 05, 2007 5:43 pm Oggetto:

Oh oh non cominciamo! Non minacciare Brontolo, ci tengo ai miei nanetti! non voglio farli ammazzare! Niente spargimenti di sangue per favore! Qui si dividono gioie e dolori, non voglio vittime sacrificali!
Per quanto riguarda il resto, le tue considerazioni non fanno una piega... diciamo che il punto (1) e (2) sono risolti. Per quanto riguarda il punto (3) la strada è ancora lunga! solo 2 precisazioni, anche se credo sia già chiaro:

1) ti assicuro che la probabilità di indovinare è più del 50% anche senza fare ammazzare il povero brontolo!!! a patto di usare la strategia giusta... Smile

2) quando chiedo di dimostrare che non esiste nessuna strategia che funziona, intendo proprio nessuna, e quindi bisogna tenere in considerazione anche la possibilità che dotto dica cose diverse ai vari nani (dopotutto, sul foglietto c'è il loro nome).

Ciao ciao!
_________________
Ciao!

.:Ipazia:.

carpao · Inviato: Lun Feb 05, 2007 5:57 pm Oggetto:

carpao · Inviato: Mar Feb 06, 2007 1:23 pm Oggetto:

cominciamo la soluzione punto 4.

prendo da parte cucciolo e dico mettiti un attimo seduto.. da te vengo dopo... perche' sei il piu' importante

e rivolgendosi agli altri da' le stesse istruzioni che avevo dato l'altra volta...

poi va da cucciolo e gli dice... tu che sei il piu' piccolo mi dovrai dire invece quale tra i due numeri che ti dice la strega e' piu' grande...
cioe' se ci sono piu' rossi scrivi rosso, se ci sono piu' verdi scrivi verdi...
e cucciolo che e' piu' furbo di quello che sembri...
si accorge subito che potrebbero essere anche uguali... essendo gl altri nani in numero pari....
in questo caso - gli dice Dotto - scrivi quello che ti piace di piu... rosso o verde fa lo stesso

Dotto infatti sa che solo in questo caso non gli sara' possibile essere sicuro della risposta... e quindi in questi casi avra' il 50% delle probabilita' in ogni caso... qualunque cosa gli dica cucciolo

per il punto 5 ...

a questo punto basta fare il calcolo delle combinazioni...
considerando i due (M) colori e i K nani (esclusi dotto e cucciolo) abbiamo:

disposizioni possibili -> 2^K

dotto nella mia strategia ne distingue (2+K-1)! / K! (2-1)! -> K+1

di queste K+1 solo una gli crea problemi...
quante disposizioni esistono di questa?

guardando il triangolo di tartaglia e' la nostra colonna centrale...

N numero nani (senza dotto e cucciolo)
X numero di disposizioni che non riesco a riconoscere
D numero di disposizioni totale (2^N)
P probabilità che capiti una configurazione brutta
la probabilità che ho quindi di sbagliare e' 50% di P

Ipazia · Inviato: Mar Feb 06, 2007 2:30 pm Oggetto:

carpao · Inviato: Mar Feb 06, 2007 4:36 pm Oggetto:

Ipazia · Inviato: Mar Feb 06, 2007 5:05 pm Oggetto:

Ma come! una lunga (e probabilmente noiosa) riunione sarebbe stata ADATTISSIMA per riflettere sui nanetti!!! Occhiolino

Alla prossima!
_________________
Ciao!

.:Ipazia:.

carpao · Inviato: Mar Feb 06, 2007 5:11 pm Oggetto:

lpcr · Utente Non Attivo Registrato: Jan 17, 2007 Messaggi: 190

molto bello, non vorrei si perdesse!
up!

doppiaGGi · Inviato: Mar Mar 20, 2007 10:24 pm Oggetto:

A che punto siamo?
Qualcuno ha provato a fare il punto 3?
Purtroppo dopo aver dimostrato che con 2n+1 (2n+2 se consideriamo anche il correttore) nani e 2 colori non vi è strategia vincente persino Ipazia sembra aver perso interesse a questo enigma.

Qualcuno ha già provato la dimostrazione di impossibilità? Avete ottenuto qualcosa?
_________________
doppiaGGi Linguaccia

____________
"Il y a des esprits qui vont à l'erreur par toutes les vérités; il en est de plus heureux qui vont aux grandes vérités par toutes les erreurs"
J. Joubert

lpcr · Utente Non Attivo Registrato: Jan 17, 2007 Messaggi: 190

Io sto (anzi stavo perchè è da un pò che non ci provo) cercando di mostrare che per (n-1,k)!=1 non si può fare, ma è solo una congettura. Per gli altri casi è possibile.
_________________
I biologi pensano di essere biochimici.
I biochimici pensano di essere chimici.
I chimici pensano di essere fisici.
I fisici pensano di essere Dio.
Dio pensa di essere un matematico.

doppiaGGi · Inviato: Mer Mar 21, 2007 12:51 pm Oggetto:

Io ho risolto il caso k=2 (direi elegantemente)
ed il caso k=3 con n sufficientemente grande ma nessuno ha voluto piu' parlarne.....
Il fatto e' che la dimostrazione, per ora, e' di difficile estensione
_________________
doppiaGGi Linguaccia

____________
"Il y a des esprits qui vont à l'erreur par toutes les vérités; il en est de plus heureux qui vont aux grandes vérités par toutes les erreurs"
J. Joubert