OliForum Matematico

Direttamente dal festival della letteratura di mantova (ma è un gioco matematico tranquilli): Io, Melkon, Arelt e altri ragazzi l'abbiamo impersonato per 5 giorni al festival a un evento organizzato da Giuseppe Rosolini e Giovanni Filocamo, facendo impazzire per trovare la soluzione mezzo festival. Vederlo è sicuramente molto più di effetto, comunque ve lo descrivo.

"Ci sono n prigionieri ai quali è offerta la possibilità di essere liberati se dimostrano di essere una buona squadra. Vengono messi in fila in modo che l'ultimo veda tutti gli altri, il penultimo quelli davanti a sè e così via fino al primo che non vede nessuno. Gli viene messo in testa un cappellino. I cappelli possono essere di 5 colori diversi: rosso,giallo,bianco,verde e blu* e ce ne sono almeno n per colore in modo che tutte le combinazioni siano possibili. A turno ciascuno deve rispondere alla domanda "Di che colore è il tuo cappello?" e solo uno può sbagliare. Che strategia possono adottare?"

Se mi sono scordata qualcosa Melkon e Arelt mi correggeranno. Buon lavoro!

* I colori potrebbero essere anche in numero diverso, ho messo quelli che usavamo effettivamente

Ovviamente si parte dall'ultimo al primo, vero?

sì, rispondono dall'ultimo al primo

n > 5?

Sapete dove mi hanno detto questo gioco? Ad uno stage all'universita' di Matematica a Genova.
Sapete chi mi ha detto questo gioco? Beh, si, proprio lui, Giuseppe Rosolini!

Bello, bello...

No non è necessariamente n>5, va bene per qualsiasi n anche se chiaramente i casi di n=1 e n=2 non hanno molto senso, lasciando sempre la possibilità di un errore.

@Loth, è carino eh? noi siamo stati 5 giorni a farci mettere cappelli in testa e indovinarne i colori. Ci presentavano come telepati E' stato troppo divertente anche perchè quasi nessuno riusciva a capire il vero metodo.

Francy88 ha scritto:@Loth, è carino eh? noi siamo stati 5 giorni a farci mettere cappelli in testa e indovinarne i colori. Ci presentavano come telepati E' stato troppo divertente anche perchè quasi nessuno riusciva a capire il vero metodo.

I migliori erano i cinnetti che dicevano che sparavamo a caso...

Anche a me l'hanno fatto vedere 'recitato' ed in effetti lascia davvero interdetti!

Ultima domanda: il numero dei cappelli deve essere sempre primo?

No, va bene qualsiasi numero..

l'ipotesi migliore che ci hanno fatto è stata che ogni cappello fa calore in quantità diversa, e noi capiamo il colore ...dal calore...
terribile...

comunque si, è estendibile teoricamente a qualsiasi numero di persone e colori, e il metodo adottato funziona sempre, ovviamente...

ok posto un paio di ideuzze..

Il problema che tratto ora è una generalizzazione di quello proposto; n sono i colori e m le persone.

1) il primo che parla non può sapere nulla sul proprio cappello ed è quindi impossibile una strategia che definisca tutti i cappelli.

2) ciò che il primo a parlare dice deve essere sufficente però a definire il cappello del secondo a parlare.

provo a descrivere una strategia possibile:

Siano n i colori diversi dei cappelli.
Numero gli n colori diversi da uno a n; ora ad ogni cappello è assegnato il numero del suo colore;i cappelli saranno più avanti trattati come se fossere questo numero.
sia $ r(x_i) $ la risposta data dall'i esima persona a parlare; inoltre per $ i \not = 1 $ questa risposta si presuppone corretta.
sia $ f(x_i) $ la somma dei cappelli davanti all'i-esima persona a parlare considerata modulo n.
siano le m persone numerate secondo l'ordine di parola da $ x_1,x_2....x_m $

se definisco $ r(x_1)=f(x_1) $ il primo a parlare può benissimo non definire il proprio colore del cappello..daltronde per quanto detto su non esistono strategie che permettano di definire il suo cappello con certezza.
se pongo $ r(x_2)=f(x_1)-f(x_2) $ sempre considerando il tutto modulo n si definisce il cappello di $ x_2 $ correttamente perchè c'è solo un colore $ c_i $ (modulo n i colori sono diversi) tale che $ f(x_1)=f(x_2)+c_i $(mod n) .
ora si tratta solo di generalizzare

definisco per ricorrenza la successione $ r(x_k) $ come:

$ r(x_1)=f(x_1) $
$ r(x_i)= f(x_{i-1})-f(x_i) $ (quest'ultima analogamente a prima)
ma è facile verificare che (insomma ciò che stà davanti all'k-esimo è ciò che stà davanti al primo - le presone dal secondo fino al k-esimo incluso):
$ f(x_{i-1})=f(x_1)- \sum_{k=2}^{i-1} r(x_k) $
ovvero:

$ r(x_i)=f(x_1)- \sum_{k=2}^{i-1} r(x_k) -f(x_i) $

tutto ciò considerato modulo n permette di definire con certezza (almeno spero) il colore del cappello perchè per definizione i colori hanno rappresentanti diversi modulo n.

inoltre $ f(x_i) $ si può calcolare per definizione (per l'i-esima persona) e $ f(x_1)=r(x_1 $ ) e quindi lo si conosce come daltronde tutte le risposte date prima della propria.
Questa strategia permette di definire tutti i cappelli meno il primo.

PS spero di non avere fatto troppo casino con gli indici..

Non mi sembra che ci siano errori!

complimenti! Lo sapevo che in questo forum non ci avreste messo tanto a risolverlo

Molto carino, anche se non sono ancora sicurissimo di averlo capito.

Ora ho "implementato" l'algoritmo in Excel e più che carino mi viene da dire spettacolare.
Ma l'ha inventato quel prof che citavate?

PS: cosa c'entra col festival della letteratura?