OliForum Matematico

Posto uno dei problemi più belli che conosco.

Ci sono 10 persone che devono essere condannate a morte, disposte in fila, in modo che il decimo veda tutti, il nono tutti tranne il decimo e così via, fino al prima che non vede nessuno. Ognuno ha un cappello bianco o nero, che logicamente non vede. A turno, partendo dal decimo, ognuno dice o bianco o nero. Si salva chi dice il colore del proprio cappello.

Sapendo che si sono messi d'accordo prima per decidere una strategia che ne salvi il più possibile, determinare quanti è possibile salvarne.

Se i primi cinque dicessero, in ordine, il colore dei cappelli degli altri cinque, se ne salverebbero sicuramente 5 e gli altri al 50% di possibilità... ma mi sa che non è la soluzione più vantaggiosa..
Comunque, bell'indovinello

Purtroppo esistono soluzioni migliori!

I cappelli non sono 5 bianchi e 5 neri vero?
Comunque altra soluzione:
Possono mettersi d'accordo che bianco vuol dire "stesso colore" e nero "colore diverso".
Il 10 direbbe bianco se il 9 avesse lo stesso colore dell'8, che entrambi vedono. Quindi il 9 direbbe il colore per salvarsi (se il 10 ha detto bianco, dice il colore dell'8, se il 10 ha detto nero, dice l'altro colore) e anche l'8 dice il colore per salvarsi(se il 10 aveva detto bianco, dice lo stesso colore del 9..). Poi il 7 farebbe la stessa cosa che ha fatto il 10 e salverebbe il 6 e 5... il 4 salverebbe il 3 e il 2.. Quindi quelli salvati sicuramente sarebbero 6

Possono essere quanti vogliono.

Bene, ma non basta !

Possono decidere che se il primo(che vedono tutti) è bianco dicono bianco per "stesso colore" e nero per "colore diverso", altrimenti viceversa, così il primo, ascoltando se, quando i colori sono gli stessi, viene detto bianco o nero, può sapere di che colore è e salvarsi. I salvati salgono a 7

Al massimo se ne salvano 9, è chiaro: mostrare che sicuramente 9 è possibile davvero salvarli

Azz ero arrivato a 7 sicuri... Mmmm... Vediamo se si può andare oltre...

Se sono fortunati si salvano anche tutti e 10!
(domanda: se seguono la strategia che permette loro di salvarne 9, quand'è che si salvano tutti?)

Bonus: e se i cappelli fossero di 3 colori diversi?
Altro bonus: e se i cappelli fossero di $n$ colori diversi?

Allora, speriamo che questa sia quella buona:
il 10 guarda i cappelli dall'1 all'8 (che vede anche il 9) se in quei numeri il bianco c'è un numero pari di volte, allora dice bianco per dire che il cappello del 9 è bianco e nero per nero.. invece se c'è un numero dispari di volte dice il contrario del colore del 9. Quindi il 9, che può vedere dall'1 all'8, se il bianco c'è un numero pari di volte sa che il suo cappello è del colore che ha detto il 10, altrimenti sa che è il contrario.Quindi dice il suo colore e si salva. A questo punto tutti sanno se dall'1 all'8 il bianco c'è un numero pari o dispari di volte (se il 9 e il 10 hanno detto la stessa cosa è pari altrimenti dispari). Quindi l'8 vede dall'1 al 7 e, se dall'1 all'8 il bianco deve essere pari e i bianchi che vede sono dispari sa che deve essere bianco lui, o viceversa, e si salva. Il 7 sapeva già se il bianco era pari dall'1 all'8 e, in base a quanto ha detto l'8, sa anche se è pari dall'1 al 7 (per esempio se era pari e l'8 ha detto bianco diventa dispari..). Quindi facendo lo stesso ragionamento dell'8 si salva pure lui e così via.
Spero che sia giusto, ma non riesco comunque a generalizzare per $ n $ colori, illuminatemi
E seguendo la strategia per salvarne 9 mi pare che si salvino tutti se il bianco (o il nero) è presente un numero pari di volte..

Ok. La soluzione si semplifica dicendo che il 10 dice bianco se c'è un numero pari di cappelli bianchi tra gli altri 9 condannati, neri se c'è un numero dispari di cappelli bianchi. Ora il 9 vede la parità dei bianchi dall'1 all'8, se è la stessa di quanto affermato dal 10 vorrà dire che ha in testa un cappello nero e quindi dirà nero, se è diversa avrà in testa un cappello bianco e ovviamente dirà bianco. E così via si procede fino all'1 senza più sbagliare.
La soluzione si generalizza ovviamente al caso di m condannati in maniera uguale.
Per il caso con n colori invece serve qualche idea in più.
Chi si cimenta (dando poi la possibilità di mettere il bonus con infiniti condannati e far finire il tutto in matematica non elementare)?

ndp15 ha scritto:Per il caso con n colori invece serve qualche idea in più.

Non mi pare, anche qui funziona la somma modulo n

ndp15 ha scritto:Chi si cimenta (dando poi la possibilità di mettere il bonus con infiniti condannati e far finire il tutto in matematica non elementare)?

Anche qui si salverebbero tutti tranne il primo? :O

jordan ha scritto:

ndp15 ha scritto:Per il caso con n colori invece serve qualche idea in più.

Non mi pare, anche qui funziona la somma modulo n

Lo so, solo che il passaggio dall'utilizzare nella strategia semplicemente la parità, all'utilizzare (a questo punto chiediamo come) le classi di resto modulo n, magari non è immediato.

jordan ha scritto:

ndp15 ha scritto:Chi si cimenta (dando poi la possibilità di mettere il bonus con infiniti condannati e far finire il tutto in matematica non elementare)?

Anche qui si salverebbero tutti tranne il primo? :O

Sì. Cioè sì mettendo qualche condizione.
Precisamente:
Disponiamo i condannati in fila. Se i condannati sono infiniti, ma in quantità numerabile, e concediamo loro la capacità di memorizzare strategie infinite, un ottimo udito ed un'ottima vista (per ascoltare tutto quello che viene detto dietro di loro ed osservare tutto quello che c'è davanti a loro), riescono a trovare una strategia che li salvi tutti tranne al più il primo?
Sì ricordi che i condannati credono in ZFC

ndp15 ha scritto:.. e concediamo loro la capacità di memorizzare strategie infinite..

Suona interessante! Sono sicuro che riuscirà a farmi addormentare nel giro di due minuti

Ci provo. Anche se premetto che potrei dire qualche strafalcione sulle classi di modulo.
A ogni colore si assegna un valore.. al primo colore 0, poi 1, 2...n. L'ultimo (quello che vede tutti) fa la somma di questi valori modulo n. Il risultato dovrà appartenere a una delle n classi di modulo n. Si accordano di far corrispondere un colore a ogni classe. Quindi l'ultimo dice il colore della classe somma mod n. Il penultimo quindi calcola la somma (nel modo di prima) che vede davanti a sè e calcola quanto manca a raggiungere la classe di modulo che invece vedeva l'ultimo. Quel numero che manca è quello corrispondente al suo colore. Così fanno tutti e si salvano, indipendentemente da quanti sono.