L'enigma dei nani e l'assioma della scelta

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

FrancescoVeneziano
Nuovo utente
Nuovo utente
Messaggi: 7
Iscritto il: gio dic 22, 2005 11:43 am
Località: Graz
Contatta:

L'enigma dei nani e l'assioma della scelta

Messaggio da FrancescoVeneziano »

No! non cacciatemi da Base5 :-)

Quelle che vi propongo sono varianti della bella ricreazione 222 del maggio 2002, "L'enigma dei nani".

Non ricopio il testo del problema ma vi ricordo i punti salienti:
I nani possono mettersi d'accordo ed hanno una memoria di ferro.
I nani possono ascoltare quello che viene detto dai compagni che li precedono, e vedere i cappelli dei nani che li seguono.

1) Trovare una strategia che funzioni per N nani e C colori dei cappelli, garantendo la salvezza di almeno N-1 nani.

2) Se i nani 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?

3) Come nel punto 2 abbiamo infiniti nani, ma questa volta non hanno la possibilità di ascoltare quello che viene detto dietro di loro (sono sordi). Possono trovare una strategia che li salvi tutti tranne al più un numero finito? (ci sono due varianti, diciamo 3a) se i nani conoscono la loro posizione nella fila, 3b) se non hanno modo di conoscerla)

4*) Dimostrare che l'esistenza delle strategie richeste nei punti 3 è equivalente all'assioma della scelta.

Questi problemi dimostrano drammaticamente la forza dell'assioma della scelta, dall'apparenza così innocua, e quanto il suo uso sia una questione di vita o di morte per un matematico.
Wir müssen wissen. Wir werden wissen.

Pasquale
Livello 12
Livello 12
Messaggi: 2853
Iscritto il: mer mag 25, 2005 2:14 am

Messaggio da Pasquale »

Oh hai visto? Eccolo qua! C'è. Ciao Francesco, ben trovato!
_________________

$\text { }$ciao Immagine ciao
E' la somma che fa il totale (Totò)

Admin
Amministratore del sito
Amministratore del sito
Messaggi: 869
Iscritto il: mer apr 20, 2005 3:47 pm
Località: Benevento

Messaggio da Admin »

Che bello risentirti!
mi sa che dobbiamo fare più spesso l'appello! :D

Ciao
Admin
Pietro Vitelli (Amministratore del Forum)
"Un matematico è una macchina che converte caffè in teoremi" Paul Erdös
www.pvitelli.net

Br1
Livello 6
Livello 6
Messaggi: 465
Iscritto il: mer feb 21, 2007 5:53 pm
Località: Bologna

Messaggio da Br1 »

Saluto anch'io Francesco, per quanto mi sia
aggregato a Base 5 qualche tempo dopo i
suoi più frequenti interventi (e imperdibili,
ne ho letti alcuni) :D

Bello il problema! Ad occhio, però, mi sa
che sia molto al di là dei miei mezzi...

Vedremo :wink:
Bruno

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Messaggio da Gianfranco »

Ciao Francesco, e bentornato!

Veramente robusto e filosofico questo problema, specialmente nel punto 4. Io dovrò rifletterci molto tempo... l'ultima volta che ho utilizzato l'assioma di scelta è stato nel 1977 circa.

Nel frattempo trascrivo l'enigma dei nani nella versione da te ricordata.

Ricordo che l'enigma dei nani fu inviato a BASE Cinque da Paolino89 e Gonario Nieddu.
Dieci nani vengono catturati da una tribu di feroci cannibali che decidono di mangiarli per il pranzo del giorno successivo.
Il capotribu decide tuttavia di lasciare ai nani una chance per salvarsi.
Il giorno seguente alla loro cattura, i nani verranno messi in fila indiana e sul capo di ciascuno verrà messo un cappello di colore bianco o nero.
Ogni nano, ovviamente, può vedere il colore dei cappelli dei nani che si trovano davanti a lui ma non il proprio né quelli dietro.
I nani avranno salva la vita se (a cominciare dall'ultimo della fila, cioè quello che vede davanti a sé nove cappelli, fino al primo della fila, che davanti a sé non ha nessuno) indovineranno il colore del cappello che hanno sulla testa.
Durante la notte i nani studiano uno stratagemma affinché si salvino più nani possibile.

La domanda è: qual è il migliore stratagemma e quanti nani si possono salvare con certezza?

Ricordate che i cappelli non devono essere necessariamente 5 bianchi e 5 neri: la loro distribuzione e proporzione è assolutamente casuale. Inoltre, durante la cerimonia, i nani non possono comunicare fra loro. Possono pronunciare, uno dopo l' altro, solo il colore del proprio cappello. Dopo che ciascun nano ha pronunciato il presunto colore del cappello, quelli successivi (sapendo se è stato ucciso o no) sono al corrente della esattezza o meno della risposta (quindi del colore effettivo del cappello di quel nano).
Gianfranco

apritisesamo
Livello 2
Livello 2
Messaggi: 25
Iscritto il: mer mag 25, 2005 1:03 am

Messaggio da apritisesamo »

Scusate l'intromisssione, sono uno dei nani.
Ammazzatemi pure, ma non cancellate la mia memoria. Immagine

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Messaggio da Gianfranco »

Per ora, con N nani e C colori, posso salvare N-C+1 nani.

Gianfranco

Sancho Panza
Livello 4
Livello 4
Messaggi: 151
Iscritto il: gio ott 12, 2006 9:01 pm

Messaggio da Sancho Panza »

Ritengo che la soluzione per N nani e C colori si ricava generalizzando quella per 10 nani e 2 colori.
Cioè ispirandomi alla soluzione di A.P. presente sul sito di Base5


Durante la notte si accordano associando ad ogni colore un valore compreso tra 0 e (C-1)

il primo a parlare fa la somma di tutti i cappelli che vede e dice il resto della divisione per C, $\frac{1}{C}$ di probabilità di salvezza, quello davanti a lui somma di nuovo e capisce il colore del suo cappello (differenza modulo C tra il valore detto dal nano precedente e la somma calcolata ), lo stesso fanno quelli davanti, che hanno tenuto a mente i colori già detti.

(N-1) salvi di sicuro, il primo al $\frac{1}{C}$%


Per le altre domande vorrei capire cosa si intende dicendo che i nani sono infiniti in quantità numerabile, il numero dei nani presenti è un numero intero e i numeri interi sono numerabili.
Quindi, perché nella domanda è specificato che la quantità deve essere numerabile?

Un’altra domanda, suppongo che per il caso generale si debba considerare una distribuzione dei colori casuale ed aperiodica (quindi non rappresentabile tramite un numero razionale); la mia supposizione è corretta?

Br1
Livello 6
Livello 6
Messaggi: 465
Iscritto il: mer feb 21, 2007 5:53 pm
Località: Bologna

Messaggio da Br1 »

Sancho Panza ha scritto:Per le altre domande vorrei capire cosa si intende dicendo che i nani sono infiniti in quantità numerabile, il numero dei nani presenti è un numero intero e i numeri interi sono numerabili.
Quindi, perché nella domanda è specificato che la quantità deve essere numerabile?
Leggo di corsa e potrei non averti capito, Sancho, ma
penso questo: l'insieme di tutti i sottoinsiemi ottenibili
su $\mathbb{N}$, per esempio, ha la stessa cardinalità del continuo
e quindi non è numerabile.
Se i nani fossero tanti così... non potrebbero esser
messi in corrispondenza biunivoca con i numeri interi.
Probabilmente, questo è il senso di quanto Francesco
ha precisato. E sottolineo 'probabilmente' :roll:
Bruno

Pasquale
Livello 12
Livello 12
Messaggi: 2853
Iscritto il: mer mag 25, 2005 2:14 am

Messaggio da Pasquale »

Credo che i nani possano pronunciare solo il nome di un colore fra C prestabiliti e niente altro (potrebbe essere anche C=N).
_________________

$\text { }$ciao Immagine ciao
E' la somma che fa il totale (Totò)

FrancescoVeneziano
Nuovo utente
Nuovo utente
Messaggi: 7
Iscritto il: gio dic 22, 2005 11:43 am
Località: Graz
Contatta:

Messaggio da FrancescoVeneziano »

La strategia di Sancho Panza per il problema 1) è corretta e salva almeno N-1 nani.

Quando dico che i nani sono infiniti in quantità numerabile intendo che sono infiniti "come i numeri naturali" e non, per esempio, infiniti "come i numeri reali".
Se non avete familiarità con questi concetti, basta che pensiate, come sicuramente avreste fatto in ogni caso, ad una fila infinita di nani numerati in ordine 0, 1, 2, ...

La distribuzione dei cappelli potrebbe anche essere periodica; ai nani serve una strategia che funzioni per tutte le possibili configurazioni.

I colori possibili sono C, che nel testo del mio problema è un numero finito; tuttavia una volta risolto il problema con un numero finito di colori ci si rende conto che le doti profetiche dell'assioma della scelta conferiscono ai nani con una buona memoria la possibilità di salvarsi "quasi tutti" (tutti tranne un numero finito) anche se i possibili colori fossero infiniti, persino (rullo di tamburi) più che numerabili.
Wir müssen wissen. Wir werden wissen.

panurgo
Livello 9
Livello 9
Messaggi: 1521
Iscritto il: sab nov 19, 2005 3:45 pm
Località: Padova

Messaggio da panurgo »

Il problema è che mi sembra difficile che infiniti nani possano arrivare a mettersi d'accordo in un tempo finito... :wink:
il panurgo

Principio di Relatività: $\mathbb{m} \not \to \mathbb{M} \, \Longleftrightarrow \, \mathbb{M} \not \to \mathbb{m}$
"Se la montagna non va a Maometto, Maometto NON va alla montagna"

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Messaggio da Gianfranco »

Bravo Sancho!
Io avevo in mente un'altra strategia meno efficiente.

Ecco due idee vaghe che mi sono venute in mente nel caso di infiniti nani, sempre associando ai colori i numeri da 0 a C-1:

a) una stategia potrebbe funzionare a tappe di lunghezza fissa o variabile: il primo nano salva i successivi k1 nani, l'ultimo di questi salva se stesso e i successivi k2 nani e così via...

b) la sequenza delle cifre associate ai cappelli dei nani forma un numero. Se immaginiamo di mettere un 0,... all'inizio, otteniamo un numero decimale compreso fra 0 e 1. Potrebbe essere razionale o irrazionale... Se i nani potessero scoprire che numero è, sarebbero a posto. Ogni nano però dovrebbe sapere quale posto occupa nella fila.

Mah! Boh!

Gianfranco

delfo52
Livello 9
Livello 9
Messaggi: 1556
Iscritto il: mer mag 25, 2005 4:19 pm
Località: bologna

Messaggio da delfo52 »

propongo la mia strategia, come "la peggiore" cioè quella a prova di stupido, che non presenta ostacoli e difficoltà anche con un numero di nani infinito-infinito-come i numeri reali.
La "resa" in termini di nani sopravvissuti non è entusiasmante: 50% garantito più un tot legato al numero dei colori (e alla distribuzione).
Banalmente, ogni nano in posizione dispari dichiara il colore del nano immediatamente davanti a lui. I nani pari si salvano, mentre dei dispari, in teoria se ne salva 1/numero dei colori.
Nel caso di un numero finito di nani, questa quota di nani dispari che la scampano può scostarsi dalla teorica; nel caso di un numero infinito, forse il dato è comunque corretto (se qualcuno incontra Cantor, chieda a lui per conferma)
Enrico

franco
Livello 9
Livello 9
Messaggi: 1438
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Messaggio da franco »

I nani potrebbero accordarsi associando ogni colore ad una lingua;
Il primo nano tira a indovinare il proprio colore e lo dice utilizzando la lingua associata al colore del secondo, il quale a quel punto conoscerà il proprio colore e lo dirà utilizzando la lingua associata al colore del successivo ....

Vabbè, lo so che è una stupidata ma visto che non ci arrivavo con la logica ho provato col pensiero laterale!

Mi autoinfliggo 10 minuti di vergogna :oops: :oops: :oops:

Ciao
Franco

ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician

Rispondi