Infiniti nanetti

Analisi, algebra lineare, topologia, gruppi, anelli, campi, ...
EvaristeG
Site Admin
Messaggi: 4896
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Messaggio da EvaristeG »

Allora, il colpo lo batto.
Per quel che riguarda l'hint la questione si fa più spinosa, in quanto ora che mi ci sono messo, non riesco a ricostruire la soluzione senza AC ... ora, può essere che fossimo rincoglioniti in 2, ma l'avevo trovata assieme ad un'altra persona, quindi le probabilità di sbagliare erano ragionevolmente basse. (mentre, visto che la cosa risaliva a mesi fa, le probabilità di non ricordarsela sono enormi...)
Il risultato che per ora mi torna è quello che avete trovato anche voi: con l'AC ne muore al più uno.
Avatar utente
moebius
Messaggi: 433
Iscritto il: 08 mag 2005, 19:14

Messaggio da moebius »

Se non vuoi che ti chieda il numero di telefono dell'altra persona vedi di contattarla tu :D
Non si possono mica lasciare i nanetti alla merce' del primo orco che passa :cry:
Fondatore: [url=http://olimpiadi.dm.unipi.it/oliForum/viewtopic.php?t=8899]Associazione non dimenticatevi dei nanetti![/url]
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...
Avatar utente
3C273
Messaggi: 113
Iscritto il: 10 mag 2007, 17:38

Messaggio da 3C273 »

Cavolo, niente da fare... negli ultimi 2 o 3 giorni non ho più pensato ai poveri nanetti di Evariste, ma già ci avevo pensato tantissimo e adesso ci ho pensato ancora un po', e più ci penso e più mi convinco che sia impossibile! Adesso, io spero proprio di sbagliarmi, ma in attesa di buone nuove da parte di Evariste (hai chiesto all'altra persona??!) io vorrei provare a dimostrare che una tale strategia non esiste. Non che sia facile. Credo che la strada migliore anche in questo caso sia cercare di tirar fuori un sottoinsieme di R non misurabile. La dimostrazione che si basa sugli accorciamenti non sembra riadattabile in questo caso. Forse si può lavorare di nuovo con la misura di probabilità come ha fatto moebius? Quando avrò un po' di tempo proverò a pensarci... Ma invito tutti a farlo! E già che ci sono, a costo di rompere immensamente le balle, chiedo di nuovo ad Evariste di pensarci e chiedere anche al suo amico! Forse non si è capito :roll: ma mi dispiacerebbe proprio che questo problema rimanesse senza soluzione!!! :wink:
Avatar utente
moebius
Messaggi: 433
Iscritto il: 08 mag 2005, 19:14

Messaggio da moebius »

Si è costituita l'Associazione non dimenticatevi dei nanetti!
Chiunque voglia aiutare i poveri nanetti a salvarsi può farne parte apportando il proprio contributo alla causa!
Grazie :D
Fondatore: [url=http://olimpiadi.dm.unipi.it/oliForum/viewtopic.php?t=8899]Associazione non dimenticatevi dei nanetti![/url]
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand »

Scusate la mia ingenuità, ma tra tutti i post esiste una soluzione completa del problema originale o no? Oppure volete adesso dimostrare il contrario?
Avatar utente
moebius
Messaggi: 433
Iscritto il: 08 mag 2005, 19:14

Messaggio da moebius »

Dunque... facciamo un po' di ordine. Il problema originale proposta da 3C273 era il seguente:
3C273 ha scritto: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?
A questo è stata data una soluzione che utilizza il lemma di Zorn da Stoppa2006:
Stoppa2006 ha scritto: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.
La soluzione che avevamo in mente io e 3C273 utilizza l'assioma della scelta, che è logicamente equivalente al lemma di Zorn, quindi non aggiunge ne toglie ipotesi per la solvibilità del quesito. In questa forma però la soluzione, almeno secondo noi, risulta essere più "facile" o se volete "comprensibile", abbastanza da rientrare nell'ambito della matematica olimpica ma... de gustibus... Se volete sapere quale sia tale soluzione, questo e' lo sketch:
3C273 ha scritto:Chiaramente per prima cosa ordiniamo i nanetti. Considerazione: se due configurazioni di cappelli (le chiamerò anche successioni di cappelli) sono definitivamente uguali, allora se la successione di risposte dei nanetti va bene per l'una, la stessa successione di risposte va bene anche per l'altra, perchè le due successioni di cappelli differiscono per al più un numero finito di termini. Quindi, che fare? Dividere in xxxxxx di xxxxxxxxxxx... poi sfruttare l'xxxxxxx della xxxxxx...
A questo punto è sorta la domanda... ma esisterà una soluzione che non fa uso dell'assioma della scelta? La risposta "sembra" essere no, nel senso che son state date due prove di questo fatto sostanzialmente differenti, quindi almeno questo dovrebbe essere un fatto assodato.

Ci sono poi state delle varianti proposte da EvaristeG:
EvaristeG ha scritto:1) ci sono n nanetti in fila, il primo vede tutti, il secondo tutti meno il primo etc; hanno in testa cappelli colorati di bianco o di nero. Ognuno, in ordine, dice un colore. Se indovina il proprio cappello vive, sennò muore. Mostrare che si salvano tutti tranne al più uno.
2) stessa cosa ma con m colori.
3) stessa cosa ma con numerabili nani e 2 colori, solo che ne muoiono un numero finito
3bis) mostrare che ne può morire un numero qualunque purchè finito
4) estendere selvaggiamente, con cardinalità arbitrarie di nani e 2 (o un num finito di) colori
5) e con infiniti colori?
Di queste varianti rimane aperta la (3) (e quindi la (3bis)), poichè EvaristeG dice che si ricorda di una soluzione che NON fa uso dell'assioma della scelta (anche se in questo caso sarebbe più corretto dire di una funzione di scelta sulle parti di R).
Quindi la domanda aperta a questo punto è:
E' possibile salvare i nanetti nella situazione (3) senza postulare l'esistenza di una funzione di scelta sulle parti di R?

Vi prego non abbandonate i poveri nanetti al loro destino :cry:
Fondatore: [url=http://olimpiadi.dm.unipi.it/oliForum/viewtopic.php?t=8899]Associazione non dimenticatevi dei nanetti![/url]
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...
Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv »

Ma tra questa versione:
- i nani sono numerabili, messi in fila come N, hanno i cappelli di due colori, non possono parlare, ciascuno vede solo quelli davanti a se
e la versione ancora aperta di EvaristeG, quali sono le differenze?
Avatar utente
moebius
Messaggi: 433
Iscritto il: 08 mag 2005, 19:14

Messaggio da moebius »

Che in quella di Evariste possono parlare "in fila" e tutti sentono quello che dicono.
Altrimenti abbiamo dimostrato che non si può fare senza scelta (si vabbè ci siamo capiti) :D
Fondatore: [url=http://olimpiadi.dm.unipi.it/oliForum/viewtopic.php?t=8899]Associazione non dimenticatevi dei nanetti![/url]
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...
Avatar utente
3C273
Messaggi: 113
Iscritto il: 10 mag 2007, 17:38

Messaggio da 3C273 »

Nella versione originale di questo topic i nanetti parlano tutti insieme, nella versione di Evariste parlano uno dopo l'altro (cioè possono trarre informazioni da ciò che hanno detto i precedenti). In entrambi i casi, si chiede una strategia per cui ne sbaglia al più un numero finito.
Evariste però vuole una soluzione che non richieda di assumere l'esistenza di una funzione di scelta sulle parti di R (altrimenti sappiamo già che, parlando uno dopo l'altro, ne sbaglierebbe al più uno).
Come si fa? Poveri, poveri nanetti! :cry:

EDIT: vabbe', abbiamo risposto in due... :wink:
(D'accordo...) Ambasciat[b]rice[/b]: [url=http://olimpiadi.dm.unipi.it/oliForum/viewtopic.php?t=8899]Associazione non dimenticatevi dei nanetti![/url]
Membro: Club Nostalgici
Avatar utente
moebius
Messaggi: 433
Iscritto il: 08 mag 2005, 19:14

Messaggio da moebius »

3C273 ha scritto:EDIT: vabbe', abbiamo risposto in due... :wink:
Mica ti ho nominato Ambasciatrice a caso :D
Fondatore: [url=http://olimpiadi.dm.unipi.it/oliForum/viewtopic.php?t=8899]Associazione non dimenticatevi dei nanetti![/url]
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...
Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv »

Io provo a fare qualche progresso ma mi sembra tosto...

Consideriamo questo problema (chiamiamolo "nani con hint"):
I nani sono messi in fila, ciascuno può vedere sia quelli davanti sia quelli dietro, e inoltre hanno un bonus. Prima dell'esecuzione, si mettono d'accordo in modo da associare a ciascuna stringa di cappelli (funzione N -> {0,1}) un messaggio scritto in nanese. Quando comincia l'esecuzione, il messaggio corrispondente alla stringa sarà visibile a ciascun nano. L'obiettivo è però che tutti i nani si salvino.

Ora voglio dimostrare che, se esiste una strategia per i nani di EvaristeG, esiste una strategia per i nani con hint.
La strategia è questa. Supponiamo che i nani si trovino davanti la stringa s. Essi conoscono una EvaristeG-strategia, e provano ad applicarla alla stringa s. Visto che ne morirebbero solo finiti, diciamo che quelli dal nano n in poi restano vivi. Allora associano alla stringa s il messaggio: "guarda, il nano 1 ha colore " + s(1) + ", il nano 2 ha colore " + s(2) + ... + " e il nano n-1 ha colore " +
s(n-1) + ", questo ti dovrebbe bastare." (ovviamente tradotto in nanese)
Una volta scelti gli hint in questo modo, la strategia funziona così: se si trovano davanti la stringa s, i primi n-1 nani sanno il loro cappello grazie al messaggio, sanno la loro posizione perchè sento ciò che dicono quelli prima. I nani da n in poi, poichè i nani da 1 a n-1 hanno sicuramente risposto giusto e ad alta voce, conoscono tutti i cappelli tranne il loro. Quindi agiscono come avrebbero agito seguendo la EvaristeG-strategia. È chiaro che resteranno vivi.

Piccola osservazione: siccome si sa che il nanese ha un alfabeto finito, al posto di un messaggio in nanese possiamo metterci un numero naturale.
Altra osservazione: EvaristeG-strategia implica hint-strategia ma non vale l'opposto. Cioè, immaginiamo per un attimo che i reali siano numerabili. Allora ovviamente esisterebbe una hint-strategia (ovvero scrivere l'intera stringa come hint), ma quelli di EvaristeG avranno ancora guai mi sa. Questo per dire che abbiamo sostituito la tesi con una più forte ma più maneggevole. (per ora la tesi sarebbe che non si fa senza scelta... se nel frattempo troviamo una strategia, meglio per loro).

Che sia veramente più maneggevole lo dimostro adesso. Ovvero, i nani con hint si salvano se e soltanto se:
esiste una funzione da (l'insieme delle stringhe numerabili di zeri e uni) a N tale che, se due stringhe sono uguali in tutte le cifre tranne una, allora la loro immagine è diversa.

Se i nani hanno una hint-strategia, allora la funzione stringa -> hint soddisfa quella proprietà. Se infatti due stringhe, diverse solo nella n-esima posizione, avessero lo stesso hint associato, allora l'n-esimo nano risponderebbe allo stesso modo quando si trova in una delle due stringhe, ma in uno dei due casi morirebbe.

Supponiamo esista la funzione f: stringhe -> N con quella proprietà. Allora ciascun nano può ricordarsi, per ogni stringa bucata all'n-esima soluzione, il naturale che, ad essa associata, corrisponde a un suo cappello nero, e il naturale che la fa corrispondere a un suo cappello bianco.

Quindi a questo punto si potrebbe cercare di costruire una tale funzione f, oppure dimostrare che ad esempio anche una funzione f che come immagine ha {0,1} non si può mostrare senza l'assioma della scelta.
Avatar utente
moebius
Messaggi: 433
Iscritto il: 08 mag 2005, 19:14

Messaggio da moebius »

edriv ha scritto:Io provo a fare qualche progresso ma mi sembra tosto...
Solo per questo sei promosso da autoproclamato portinaio a portaborse :D
edriv ha scritto: Consideriamo questo problema (chiamiamolo "nani con hint"):
I nani sono messi in fila, ciascuno può vedere sia quelli davanti sia quelli dietro, e inoltre hanno un bonus. Prima dell'esecuzione, si mettono d'accordo in modo da associare a ciascuna stringa di cappelli (funzione N -> {0,1}) un messaggio scritto in nanese. Quando comincia l'esecuzione, il messaggio corrispondente alla stringa sarà visibile a ciascun nano. L'obiettivo è però che tutti i nani si salvino.

Ora voglio dimostrare che, se esiste una strategia per i nani di EvaristeG, esiste una strategia per i nani con hint.
La strategia è questa. Supponiamo che i nani si trovino davanti la stringa s. Essi conoscono una EvaristeG-strategia, e provano ad applicarla alla stringa s. Visto che ne morirebbero solo finiti, diciamo che quelli dal nano n in poi restano vivi. Allora associano alla stringa s il messaggio: "guarda, il nano 1 ha colore " + s(1) + ", il nano 2 ha colore " + s(2) + ... + " e il nano n-1 ha colore " +
s(n-1) + ", questo ti dovrebbe bastare." (ovviamente tradotto in nanese)
Una volta scelti gli hint in questo modo, la strategia funziona così: se si trovano davanti la stringa s, i primi n-1 nani sanno il loro cappello grazie al messaggio, sanno la loro posizione perchè sento ciò che dicono quelli prima. I nani da n in poi, poichè i nani da 1 a n-1 hanno sicuramente risposto giusto e ad alta voce, conoscono tutti i cappelli tranne il loro. Quindi agiscono come avrebbero agito seguendo la EvaristeG-strategia. È chiaro che resteranno vivi.
Ecco su questo non sono molto d'accordo. Perchè hai modificato le risposte dei nani che avrebbero dovuto sbagliare secondo la EvaristeG-strategia, quindi adesso i nani che applicano la EvaristeG-strategia hanno un set di risposte dei "predecessori" che differisce in un numero finito di posizioni da quello buono (magari i nani dall'n-esimo in poi erano in grado di capire il colore del proprio cappello grazie alle informazioni tratte dalle risposte errate dei precedenti, il cui scopo non era indovinare ma "suggerire").

Magari ho capito male... Il resto del messaggio l'ho letto comunque e modulo queste osservazioni mi sembrava che ci fossero scritte cose sensate e quindi potrebbe essere una possibile strada da seguire.
Quindi spero di aver capito male l'inizio!
Fondatore: [url=http://olimpiadi.dm.unipi.it/oliForum/viewtopic.php?t=8899]Associazione non dimenticatevi dei nanetti![/url]
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...
Avatar utente
moebius
Messaggi: 433
Iscritto il: 08 mag 2005, 19:14

Messaggio da moebius »

Dicono che la notte porta consiglio...
Se modifichiamo l'hint in questo modo:
facciamo associare alla stringa s il messaggio: "guarda, il nano 1 ha colore " + s(1) + " anche se EvaristeG sostiene che il suo colore è " + EG(1) + ", il nano 2 ha colore " + s(2) + " anche se EvaristeG sostiene che il suo colore è " + EG(2) + " + ... + " e il nano n-1 ha colore " + s(n-1) + " anche se EvaristeG sostiene che il suo colore è " + EG(n-1) + ", questo ti dovrebbe bastare." (ovviamente tradotto in nanese) :D

A questo punto i nani dall'n-esimo in poi indovinano tutti seguendo la EvaristeG strategia poichè conoscono le risposte che avrebbero dato i predecessori pensando in EvaristeG-way!

Adesso "basta" far vedere che per costruire una funzione dalle parti di N ad N con la proprietà che due sottoinsiemi hanno immagine diversa se differiscono per un elemento è necessario assumere una qualche scelta.

A morte gli orchi cattivi! Viva i nanetti!
(Orco culo, culo chi non lo dice!... Culo!)
Fondatore: [url=http://olimpiadi.dm.unipi.it/oliForum/viewtopic.php?t=8899]Associazione non dimenticatevi dei nanetti![/url]
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...
Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv »

Sì, ho trascurato quella cosa... io intendevo questo: siccome i nani da n in poi sanno il cappello (vero) dei nani precedenti (perchè lo hanno indovinato), tanto vale che si fossero imparati non solo la loro EvaristeG-strategia, ma anche quella di tutti gli altri nani precedenti. Così possono immaginarsi cosa avrebbe risposto il primo, e quindi cosa avrebbe risposto il secondo, eccetera.

Insomma, devono solo decidere se sprecare neuroni o inchiostro. Noi però dovremo decidere se questo affanno sarà servito a qualcosa per loro :P
Avatar utente
3C273
Messaggi: 113
Iscritto il: 10 mag 2007, 17:38

Messaggio da 3C273 »

Mmm... se ho capito bene il tuo ragionamento, però, il nano T (pur conoscendo anche la EvaristeG strategia dei precedenti) potrebbe non sapere lo stesso cosa i precedenti avrebbero risposto, perchè appunto la loro risposta potrebbe dipendere dal colore del cappello del nano T, che T appunto non conosce... passandogli appunto in questo modo un'informazione utile... Ma forse non ho letto attentamente, potrei sbagliarmi. Invece mi sembra che funzioni quello che ha detto moebius... ma devo rileggere tutto più attentamente quando ho un attimo di tempo in più!!!
In ogni caso... grande edriv perchè tu ci tieni ai nanetti!!! No, sul serio, grande anche perchè tutto sommato questa della "strategia con suggerimento" potrebbe essere una svolta...

(N.B.: T sta per Tontolo :) )
(P.S.: culo! :D )
(D'accordo...) Ambasciat[b]rice[/b]: [url=http://olimpiadi.dm.unipi.it/oliForum/viewtopic.php?t=8899]Associazione non dimenticatevi dei nanetti![/url]
Membro: Club Nostalgici
Rispondi