Infiniti nanetti

Analisi, algebra lineare, topologia, gruppi, anelli, campi, ...
Rispondi
Avatar utente
3C273
Messaggi: 113
Iscritto il: 10 mag 2007, 17:38

Infiniti nanetti

Messaggio da 3C273 » 13 ago 2007, 16:45

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
Marco ha scritto:Tutto il resto è Combinatoria.
:D

Stoppa2006
Messaggi: 51
Iscritto il: 28 nov 2006, 20:12

Messaggio da Stoppa2006 » 13 ago 2007, 16:50

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

Avatar utente
3C273
Messaggi: 113
Iscritto il: 10 mag 2007, 17:38

Messaggio da 3C273 » 13 ago 2007, 16:52

salva90 ha scritto: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 ??!

Avatar utente
3C273
Messaggi: 113
Iscritto il: 10 mag 2007, 17:38

Messaggio da 3C273 » 13 ago 2007, 17:07

Stoppa2006 ha scritto:Io ho trovato una soluzione con il lemma di Zorn, però non so se è argomento olimpico...
E infatti non sapevo dove postarlo... :wink:
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!!! :lol: :wink:

Avatar utente
salva90
Messaggi: 1314
Iscritto il: 19 ott 2006, 18:54
Località: Carrara

Messaggio da salva90 » 13 ago 2007, 17:43

3C273 ha scritto:
salva90 ha scritto: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 :?
[url=http://www.myspace.com/italiadimetallo][img]http://img388.imageshack.us/img388/4813/italiadimetallogn7.jpg[/img][/url]

pic88
Messaggi: 741
Iscritto il: 16 apr 2006, 11:34
Località: La terra, il cui produr di rose, le dié piacevol nome in greche voci...

Messaggio da pic88 » 13 ago 2007, 20:29

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

Avatar utente
edgar89
Messaggi: 40
Iscritto il: 06 ago 2007, 19:19

Re: Infiniti nanetti

Messaggio da edgar89 » 14 ago 2007, 20:30

3C273 ha scritto: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
Marco ha scritto:Tutto il resto è Combinatoria.
:D
botta di fortuna enorme? :D
Official founder of the ReginaSoft Corporation

Avatar utente
3C273
Messaggi: 113
Iscritto il: 10 mag 2007, 17:38

Re: Infiniti nanetti

Messaggio da 3C273 » 16 ago 2007, 12:12

edgar89 ha scritto:
3C273 ha scritto:[...] Come hanno fatto?
botta di fortuna enorme? :D
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? :twisted: :twisted: :twisted:

pic88
Messaggi: 741
Iscritto il: 16 apr 2006, 11:34
Località: La terra, il cui produr di rose, le dié piacevol nome in greche voci...

Re: Infiniti nanetti

Messaggio da pic88 » 16 ago 2007, 12:55

edgar89 ha scritto:
3C273 ha scritto:[...] Come hanno fatto?
botta di fortuna enorme? :D
Dimostrare che, tirando a caso, muoiono infiniti nani.

killing_buddha
Messaggi: 209
Iscritto il: 20 mag 2007, 12:39

Re: Infiniti nanetti

Messaggio da killing_buddha » 16 ago 2007, 13:02

pic88 ha scritto:
edgar89 ha scritto:
3C273 ha scritto:[...] Come hanno fatto?
botta di fortuna enorme? :D
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
Messaggi: 741
Iscritto il: 16 apr 2006, 11:34
Località: La terra, il cui produr di rose, le dié piacevol nome in greche voci...

Re: Infiniti nanetti

Messaggio da pic88 » 16 ago 2007, 14:37

killing_buddha ha scritto: 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
Site Admin
Messaggi: 4777
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Messaggio da EvaristeG » 16 ago 2007, 15:05

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
Messaggi: 51
Iscritto il: 28 nov 2006, 20:12

Messaggio da Stoppa2006 » 16 ago 2007, 15:58

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.

Avatar utente
MateCa
Messaggi: 98
Iscritto il: 23 ago 2006, 23:27
Località: Camurana

Messaggio da MateCa » 16 ago 2007, 23:20

@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... :D )
In fondo la disposizione non è una forma di comunicazione??? :wink:

Cmq per adesso idee non ne ho... :oops:
Parlare oscuramente lo sa fare ognuno, ma chiaro pochissimi. (G. Galilei)

EvaristeG
Site Admin
Messaggi: 4777
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Messaggio da EvaristeG » 17 ago 2007, 02:01

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.

Rispondi