Infiniti cappelli

[Martino]

Tu e altre infinite persone indossate un cappello. Ogni cappello è rosso oppure verde. Ogni persona vede il colore del cappello di ogni altra persona, ma non vede il colore del proprio; a parte questo, non ci si può scambiare informazioni (ma si può fissare una strategia prima della comparsa dei cappelli). Simultaneamente, ognuno prova a indovinare il colore del proprio cappello. Si vince se solo un numero finito di persone si sbaglia. Trovare una strategia vincente

[FE7]

Se si fissasse una strategia per cui ogni persona ha il compito di accoppiare altre due persone con cappelli di colore diverso in modo che ognuno sappia che la persona che gli sta di fronte ha il cappello di colore diverso dal suo? Forse questo sarebbe scambiarsi informazioni?

[Martino]

Non funziona perché se uno accoppia in modo prestabilito due persone con cappelli di colore diverso è come se stesse dicendo a queste due persone che hanno cappelli di colore opposto e quindi è come se gli stesse dicendo il colore del loro cappello.

[Giso1]

Mettersi d'accordo per accoppare tutti quelli col cappello verde vale?

[Martino]

Accoppare o accoppiare?

[Giso1]

Accoppare e accoppiare!
Prima di dare i cappelli si formano delle coppie,e ci si mette d'accordo di dire tutti (o almeno i superstiti) "rosso".
Una volta indossati i berretti, se il mio compagno ha il cappello verde...lo accoppo così rimangono solo rossi!

[Cmax1]

L'accoppiamento mi sembra una buona idea.
Non so se le regole consentono qualcosa come numerare i partecipanti, e concordare preventivamente una strategia per cui iniziando da 1 si sceglie il numero più basso con il cappello rosso. Coloro che vengono saltati nell'ordinamento sanno di avere il cappello verde. Il prescelto si accoppia con il successivo cappello rosso, e così via.
Certo, richiede un tempo infinito di realizzazione, e che io sappia solo Chuck Norris ha completato un simile conteggio (due volte) ...
Alla fine, se ci si arriva, l'unico che non sa il colore del suo cappello è il numero 1.

[FE7]

ma cosi mi sembra che sia di nuovo uno "scambiarsi informazioni"

[Cmax1]

Beh, cavillando sul significato di "scambiare" ...
Comunque presuppone anche la numerabilità, che a quanto pare non è richiesta. Spinto dalla curiosità, confesso di aver cercato la soluzione:

http://www.uwyo.edu/moorhouse/handouts/hats_sol.pdf

Non credo l'avrei trovata da solo, non sono nemmeno sicuro di averla capita pienamente.

[Martino]

A me piace un sacco

[Epimenide93]

Ho resistito alla tentazione di leggere la soluzione, ma non trovo idee per attaccare concretamente il problema. Un suggerimento?

[Martino]

Un suggerimento:

Un'assegnazione di cappelli è una funzione dall'insieme X delle persone all'insieme I={rosso,verde} (cioè è un elemento di [tex]I^X[/tex]). Data una tale assegnazione f, ogni persona x conosce f(y) per ogni y diverso da x ma non conosce f(x). Quindi non conosce f ma "quasi", conosce f a meno di un numero finito di valori.

[FE7]

Data una assegnazione f, ci sono due possibilità: 1) l'assegnazione è completamente a caso, e allora non riesco proprio a trovare un modo in cui si possa dare una risposta che non sia a sua volta dire un colore a caso senza cadere nello scambio di informazioni
2) se non è a caso, allora ha un criterio, e conoscendo f a meno di un unico valore è come conoscere il criterio per tutti i valori (es: "tutti quelli coi capelli rossi hanno cappello rosso gli altri verdi") quindi basta che ciascuno dica il colore che secondo il "criterio f" dovrebbe corrispondergli, in questo modo la strategia è vincente.
Siccome penso proprio che la risposta sia sbagliata ma il problema è carino resisto ancora un po' dal leggere la soluzione e chiedo un altro suggerimento se è possibile.

[Martino]

Un altro suggerimento:

Nell'insieme [tex]I^X[/tex] delle funzioni da X = l'insieme delle persone a I = l'insieme {rosso,verde} possiamo dire che due funzioni [tex]f,g[/tex] sono "equivalenti" se [tex]f(x)=g(x)[/tex] a meno di un numero finito di valori x, cioè se l'insieme [tex]\{x \in X\ :\ f(x) \neq g(x)\}[/tex] è finito. Questa è una relazione di equivalenza, indichiamo con [tex][f][/tex] la classe di equivalenza di [tex]f \in I^X[/tex]. Allora alla comparsa dei cappelli, cioè di una certa configurazione (funzione) [tex]f[/tex], una data persona x non conosce f ma certamente conosce [tex][f][/tex]. La persona x dovrà quindi scegliere una [tex]g \in [f][/tex] ...

[FE7]

Dopo il secondo suggerimento mi pare di aver capito! Bisogna fare una strategia secondo cui ci si accorda preventivamente scegliendo una funzione in ogni classe di equivalenza in modo che ogni persona scelga il colore da dire in base a quella e solo quella funzione per ogni classe. Quindi una volta comparsa l'assegnazione di cappelli, tutti vedranno la funzione a meno di un elemento, quindi potranno tutti risalire alla classe di equivalenza corretta, a quel punto tutti diranno il colore in base a una stessa funzione di quella classe che hanno tutti concordato e quindi potrà sbagliare solo un insieme finito di persone visto che le due funzioni differiscono per un insieme finito di valori

[Martino]

Esatto, e osserva che

serve l'assioma della scelta

[FE7]

Ah! giusto è vero. Anzi, sono andato adesso a vedere la soluzione e pare che l'uso delll'assioma della scelta fosse proprio la cosa più importante da dire nella soluzione!! Questo problema è veramente molto bello

[gygabyte017]

Ciao, c'è una cosa che non mi è del tutto chiara: fissata una $f$ e quindi fissata la sua classe di equivalenza, con che criterio si accordano per scegliere un rappresentante prefissato? Non riesco a trovarne uno... In altre parole: data una $[f]$, come possono definire una $F$ che la mappa $F([f]) = \bar f$ in un rappresentante ben determinato e univoco? Sicuramente esiste, ma per mettersi d'accordo i tizi devono "esplicitare" una $F$ in qualche modo...

[FE7]

Ciao. forse non ho capito la tua domanda ma per come ho inteso è proprio a quello che serve l'assioma della scelta

[gygabyte017]

Sì, se non ho capito male dovrei aver capito, il riepilogo è il seguente:
chiamiamo $X$ l'insieme delle funzioni, $f \in X$ una di esse, $X_{f}$ l'insieme delle funzioni nella stessa classe di equivalenza di $f$, e $\bar X = {X_{f}, f \in X}$ l'insieme di tutte le classi.
I cappelli vengono assegnati tramite una funzione $f \in X$.
Ogni persona del gioco, per come è definita la classe di equivalenza, riesce a risalire univocamente all'insieme $X_{f}$.
Ora, tutte le persone devono scegliere nell'insieme $X_{f}$ un rappresentante che sia uguale per tutti per vincere.
Come lo scelgono? L'assioma della scelta mi dice che data la famiglia di insiemi $\bar X$ esiste una funzione $F$ tale che $AA X_{f} \in \bar X$, $F(X_{f}) = g \in X_{f}$.
La $F$ è l'unica cosa che le persone devono concordare prima.

Corretto?

[FE7]

sì è corretto