Infiniti nanetti

[3C273]

Propongo questo problema (a mio avviso stupefacente) che mi ha fatto moebius...
In una stanza ci sono infiniti nanetti. Ognuno ha in testa un cappello bianco oppure nero. Ovviamente ciascuno vede i cappelli degli altri ma non il proprio, e ovviamente non possono comunicare in nessun modo. A un certo punto, tutti contemporaneamente devono comunicare il colore del cappello che ritengono di avere in testa. Quale strategia permette ai nanetti di commettere al massimo un numero finito di errori? Ovvero: tutti i nanetti indovinano il colore del cappello che hanno in testa tranne al più un numero finito. Come hanno fatto?

PS: onestamente ha ben poco a che fare con la combinatoria, ma non sapevo dove metterlo... non l'ho messo in mate ricreativa perchè la soluzione è molto rigorosa, ma se c'è una sezione più adatta spostatelo per favore! io mi sono appellata al fatidico

Tutto il resto è Combinatoria.

[Stoppa2006]

Io ho trovato una soluzione con il lemma di Zorn, però non so se è argomento olimpico...

[3C273]

io dico solo che è stato ampiamente discusso qui e a cesenatico

mi spiace, non mi ero accorta che era già stato discusso sul forum, e dire che avevo provato a fare "cerca"... non l'ho trovato! un link? sono curiosa di leggere la discussione! grazie...

EDIT: ho le allucinazioni? che fine ha fatto il messaggio di salva ??!

[3C273]

Io ho trovato una soluzione con il lemma di Zorn, però non so se è argomento olimpico...

E infatti non sapevo dove postarlo...
comunque se ragioni in termini di assioma della scelta invece che di lemma di zorn (anche se poi sono equivalenti) la soluzione ha un aspetto molto più olimpico... nel senso che semmai (in generale) le difficoltà stanno nel fare le cose senza l'assioma della scelta, ma utilizzarlo senza porsi troppe domande viene (fin troppo) naturale... Va be' è inutile che mi arrampico sugli specchi, la verità è che come ho scritto non sapevo dove metterlo!!!

[salva90]

io dico solo che è stato ampiamente discusso qui e a cesenatico

mi spiace, non mi ero accorta che era già stato discusso sul forum, e dire che avevo provato a fare "cerca"... non l'ho trovato! un link? sono curiosa di leggere la discussione! grazie...

EDIT: ho le allucinazioni? che fine ha fatto il messaggio di salva ??!

infatti l'ho cancellato... non era proprio lo stesso problema, sebbene molto simile

[pic88]

Questi sono i classici problemi di cui tutti hanno già parlato ma di cui non si leggerà mai una soluzione

[edgar89]

Propongo questo problema (a mio avviso stupefacente) che mi ha fatto moebius...
In una stanza ci sono infiniti nanetti. Ognuno ha in testa un cappello bianco oppure nero. Ovviamente ciascuno vede i cappelli degli altri ma non il proprio, e ovviamente non possono comunicare in nessun modo. A un certo punto, tutti contemporaneamente devono comunicare il colore del cappello che ritengono di avere in testa. Quale strategia permette ai nanetti di commettere al massimo un numero finito di errori? Ovvero: tutti i nanetti indovinano il colore del cappello che hanno in testa tranne al più un numero finito. Come hanno fatto?

PS: onestamente ha ben poco a che fare con la combinatoria, ma non sapevo dove metterlo... non l'ho messo in mate ricreativa perchè la soluzione è molto rigorosa, ma se c'è una sezione più adatta spostatelo per favore! io mi sono appellata al fatidico

Tutto il resto è Combinatoria.

botta di fortuna enorme?

[3C273]

[...] Come hanno fatto?

botta di fortuna enorme?

Ehm... se i nanetti lo facessero una volta sola potrebbe essere come dici tu... però adesso i nanetti per dimostrarti che non è solo fortuna ripeteranno il gioco infinite volte, e sbaglierà sempre solo un numero finito di loro!!!

Dai, se ho capito bene dai messaggi precedenti si è già parlato tanto di questo problema, ma una soluzione precisa non è saltata fuori... o almeno ci sarà qualcuno che non la conosce! quindi forza, scrivete le vostre idee, garantisco che la soluzione (una volta trovata) non è per nulla complicata! E soprattutto... non sembra assurdo che i nanetti possano farcela? Non sembra assurdo che da un certo nanetto in poi TUTTI indovinino il loro colore avendo visto solo i colori degli altri e non avendo nessuna informazione sul proprio?

[pic88]

[...] Come hanno fatto?

botta di fortuna enorme?

Dimostrare che, tirando a caso, muoiono infiniti nani.

[killing_buddha]

[...] Come hanno fatto?

botta di fortuna enorme?

Dimostrare che, tirando a caso, muoiono infiniti nani.

Questo è semplice perchè è pari pari al paradosso del cielo: tirando in una qualunque direzione, il mio proiettile colpirà infiniti nani, perchè infiniti nani stanno su ognuna delle infinite rette immaginare che formano il fascio che ha per centro la mia posizione!

[pic88]

Questo è semplice perchè è pari pari al paradosso del cielo: tirando in una qualunque direzione, il mio proiettile colpirà infiniti nani, perchè infiniti nani stanno su ognuna delle infinite rette immaginare che formano il fascio che ha per centro la mia posizione!

LOL

Io dicevo sul serio!

[EvaristeG]

A parte che nel problema classico i nani sono in fila e parlano uno per volta, provo a dare una soluzione buffa.

I nani si beneordinano prima di entrare nella stanza.
Il Primo si mette contro una parete; il Secondo, se il Primo ha un cappello nero, gli si mette dietro, sennò anche lui contro una parete. E così via, il Terzo si dispone secondo il colore del cappello del Secondo. In generale, se il nano $ \alpha $ trova una fila che comincia dal nano $ \beta $ e contiene tutti quelli tra se stesso e $ \beta $ e non vi compare un cappello bianco (che, se compare, sta all'ultimo posto), allora vi si aggiunge.
Questo assicura che ogni fila ha un minimo (perchè i nani erano bene ordinati) e ha un massimo, a meno che non sia l'ultima fila, eventualmente (cioè contenga tutti i nani da un certo $ \gamma $ in poi).
Ogni fila ha un massimo in quanto, se c'è una fila che parte dal nano $ \alpha $ e non ha massimo (ed esiste però un nano $ \beta $ maggiore di ogni altro nano della fila), allora ogni nano nella fila ha un cappello nero (se uno ce l'ha bianco, lì termina la fila e lui è il massimo), ma allora alla fila deve appartenere anche il minimo nano tra quelli maggiori a tutti gli elementi della fila, che dunque è un massimo per la fila.
Dopo essersi disposti in questo modo, ogni nano controlla: se non ha nessuno dietro (nessun successore nella propria fila) dice "Bianco", altrimenti dice "Nero".
L'unico che può morire in questo modo è l'eventuale massimo del buon ordinamento scelto dai nani, che però possono evitare anche questa perdita, scegliendo il primo ordinale che abbia la loro cardinalità.

Ovviamente questa soluzione non sarà quella che pensavate voi, giusto?

[Stoppa2006]

Non credo però che questa soluzione sia olimpica, ma senza Zorn penso non si possa fare:

Supponiamo che i nani siano $ \aleph_{0} $, all'inizio prima di entrare si bene ordinano come $ \omega $, allora le possibili successioni di nani sono $ A=\{f|f:\omega\rightarrow 2\} $. I nani scelgono un buon ordine di A (esiste per Zorn), allora il nano "$ n $", che vede tutti i nani "maggiori" di lui nell'ordinamento di $ \omega $, è incerto su quale sia la $ f $ in $ A $ che rappresenta la successione dei cappelli dei nani, ed è incerto su $ 2^{n} $ possibilità; ovvero il suo e i cappelli di quelli che lo precedono.
Strategia: Ogni nano dice il colore che corrisponde alla minima delle $ 2^{n} $ $ f $ su cui è incerto.
In questo modo moriranno solo un numero finito di nani, infatti sia:
$ f_{i}:\omega\rightarrow 2 $
la sequenza congetturata dall'$ i $-esimo nano, allora poichè:
{Possibili scelte dell'$ i $-esimo nano}$ \subseteq ${Possibili scelte dell'$ i+1 $-esimo nano}
Otteniamo una successione decrescente:
$ f_{0}\geq ...\geq f_{i}\geq f_{i+1}\geq f_{i+2}\geq ... $
Che è una successione decrescente su $ (A;\geq) $ allora è definitivamente costante, supponiamo dal nano $ k $. Allora $ k $ e $ k+1 $ dicono la stessa cosa, ma il nano $ k $ vede il $ k+1 $-esimo, allora dal $ k+1 $-esimo in poi indovinano tutti.

P.S. In questo modo tutti i nani possono annucniare il colore del proprio cappello.

[MateCa]

@EvaristeG:
ho capito qual è la logica del tuo ordinamento, ma non sono sicuro che una strategia del genere possa essere considerata valida. Se è possibile che i nani si dispongano nella stanza in un certo modo, il problema diventa banale (tanto per fare un esempio, basta che i nani si dispongano in due gruppi, dove ogni nano si dispone in un certo gruppo in funzione del colore del cappello di che gli sta davanti. Ogni nano guarda dove si mette il nano a lui successivo e nessuno sbaglia... )
In fondo la disposizione non è una forma di comunicazione???

Cmq per adesso idee non ne ho...

[EvaristeG]

Ma il problema, così come è formulato, non lo vieta ... non c'è nemmeno scritto che possano preventivamente accordarsi su cose come un loro ordinamento o l'ordinamento di un insieme.

Cmq, sta roba viene ora spostata di forza in matematica non elementare.