Indice del forum Olimpo Informatico
I Forum di Zeus News
Leggi la newsletter gratuita - Attiva il Menu compatto
 
 FAQFAQ   CercaCerca   Lista utentiLista utenti   GruppiGruppi   RegistratiRegistrati 
 ProfiloProfilo   Messaggi privatiMessaggi privati   Log inLog in 

    Newsletter RSS Facebook Twitter Contatti Ricerca
* QUIZ: I 10 incappucciati
Nuovo argomento   Rispondi    Indice del forum -> Enigmi e giochi matematici
Precedente :: Successivo  
Autore Messaggio
Smjert
Dio maturo
Dio maturo


Registrato: 01/04/06 17:19
Messaggi: 1619
Residenza: Perso nella rete

MessaggioInviato: 10 Gen 2007 19:32    Oggetto: * QUIZ: I 10 incappucciati Rispondi citando

Copio e incollo quello che mi ha mandato un amico.

Allora questo è un indovinello veramente difficile, me lo ha
proposto uno in facoltà mia l'inverno scorso, bisogna starci su. Se
credete di aver trovato la soluzione, ripensateci perchè molto spesso
c'è sempre un'imperfezione. Non posso dirvi dove è stato proposto
l'indovinello perchè sarebbe un indizio implicito, sappiate che
comunque era un contesto internazionale.


Detto questo, ecco l'indovinello:

Allora, ci sono 10 persone condannate a morte. Il boia dice loro che
hanno una possibilità per salvarne qualcuno, partecipando a questo
"gioco".

Loro 10 verranno posti su una scalinata fatta di gradini, uno per
gradino, in fila indiana. Ognuno è in grado di vedere tutti quelli che
stanno davanti, ma ovviamente non quelli dietro. Ad ognuno viene
messo un cappuccio in testa, che può essere nero o bianco, ognuno dei
due casi con un 50% di possibilità. Ad ognuno verrà chiesto di provare
ad indovinare il colore del proprio cappuccio (ovviamente non lo hanno
visto precedentemente). Chi indovina viene salvato, chi sbaglia no. La
risposta viene sentita DA TUTTI gli altri condannati.

Il boia dice loro che posso pure mettersi d'accordo prima
dell'inizio del gioco.

I 10 parlottano tra di loro, ed il boia ascoltando sente il loro
piano: dal momento che nessuno può sapere con certezza che cappuccio
ha in testa, darà come risposta il colore di colui che sta davanti,
così almeno quest'ultimo ha il 100% di probabilità di fare giusto.

In questo modo almeno 5 di loro potranno salvarsi sicuramente(quelli
in posizione pari).

Il boia però si mostra caritatevole, e dice loro di pensarci ancora
un po' su, poichè c'è un modo per salvarne con sicurezza 9....

L'indovinello finisce qui.

Inutile dire che non ci sono trabocchetti o fregature, questo è un
indovinello serio.
Per chi avesse risolto quello famoso dei 3 condannati, con un numero
stabilito di cappucci bianchi e neri, si accorgerà subito che non
serve a nulla come riferimento. Qui i colori sono del tutto random.
Se avete dubbi sul testo (l'ho riscritto io quindi potrei aver
commesso degli errori) chiedete pure chiarimenti. Chi pensa di aver
trovato la soluzione giusta può propormela in inbox.

Vi dico un'ultima cosa: esiste più di una soluzione (io e un mio
amico ne abbiamo trovate due differenti, controllate e ricontrollate e
funzionano).

Buona fortuna!
Top
Profilo Invia messaggio privato HomePage
Salmastro
Dio minore
Dio minore


Registrato: 13/12/06 19:36
Messaggi: 883
Residenza: Casalmico

MessaggioInviato: 10 Gen 2007 21:51    Oggetto: beati gli ultimi Rispondi citando

il primo, la vittima sacrificale, dovrà dare, dunque, con la sua dichiarazione (che sarà o B o N) un'indicazione così potente da salvare tutti. Dato che siamo nel campo del binario, così caro a Ulisse, io credo che
Citazione:
così facendo dovrà divedere gli eventi possibili in due insiemi ed attribuire ad uno il valore B, all'altro N
un buon modo, forse, è quello di guardare i 9 cappelli davanti a lui e verificare se
Citazione:
sono pari (e dice B) o dispari (e dice N). Il secondo conta i neri davanti a se e si regola. Se in tutto sono pari e e ne vede un numero dispari il suo cappello è nero e viceversa. Dal terzo in poi, ai cappelli che vedono i "fortunati" aggiungono le dichiarazioni di quelli che l'hanno preceduto (a parte il primo!),e seguono la stessa tecnica di prima


Funziona?

Salmastro
Top
Profilo Invia messaggio privato AIM Yahoo MSN
Salmastro
Dio minore
Dio minore


Registrato: 13/12/06 19:36
Messaggi: 883
Residenza: Casalmico

MessaggioInviato: 11 Gen 2007 12:12    Oggetto: Re: beati gli ultimi Rispondi citando

Ops: scrivendo e correggendo ho dimenticato una cosa importante e cioè che la "vittima sacrificale" deve guardare i 9 cappelli davanti a lui e verificare se (ecco la dimenticanza) i neri
Citazione:
sono pari (e dice B) o dispari (e dice N). Il secondo conta i neri davanti a sè e così via come nel precedente post.


Funziona, ora?

Salmastro
Top
Profilo Invia messaggio privato AIM Yahoo MSN
gqn77
Eroe in grazia degli dei
Eroe in grazia degli dei


Registrato: 05/07/05 23:35
Messaggi: 161

MessaggioInviato: 11 Gen 2007 12:59    Oggetto: Rispondi citando

Scusa non ho capito una cosa poichè la soluzia dipende da molti fattori.

Per funzionare innanzi tutto la domanda deve essere fatta uno alla volta, ma partono dal quello più in basso o da quello più in alto?

I prigionieri hanno facoltà di scelta nell'ordine da seguire nel fare le domande?
Top
Profilo Invia messaggio privato
Smjert
Dio maturo
Dio maturo


Registrato: 01/04/06 17:19
Messaggi: 1619
Residenza: Perso nella rete

MessaggioInviato: 11 Gen 2007 13:36    Oggetto: Rispondi citando

gqn77 ha scritto:
Scusa non ho capito una cosa poichè la soluzia dipende da molti fattori.

Per funzionare innanzi tutto la domanda deve essere fatta uno alla volta, ma partono dal quello più in basso o da quello più in alto?

La regia mi dice che si parte dall'alto e si va verso il basso.

gqn77 ha scritto:
I prigionieri hanno facoltà di scelta nell'ordine da seguire nel fare le domande?

No, si va in ordine dall'alto al basso.
Top
Profilo Invia messaggio privato HomePage
Salmastro
Dio minore
Dio minore


Registrato: 13/12/06 19:36
Messaggi: 883
Residenza: Casalmico

MessaggioInviato: 11 Gen 2007 17:59    Oggetto: vittima? Rispondi citando

Preciso che l'incappucciato n° 1, in realtà, non è precisamente una "vittima sacrificale", giacchè è vero che salva tutti, ma la sua probabilità di sopravvivenza rimane sempre al 50%. In sostanza è l'unico a non ottenere vantaggi dal patto dei 10.

Mi chiedevo come si fossero messi d'accordo su chi fosse il n° 1 ed in un mio vecchio testo ho letto che di comune accordo tuti si fossero affidati incautamente al più vecchio del gruppo, più furbetto che saggio. L'Anziano infatti decise che avrebbero fatto la classica conta, che la conta sarebbe partita da lui, ma che la somma delle "dita" sarebbe stata preventivamente divisa per un numero K, da lui insindacabilmente deciso, ed infine della somma si sarebbe solo considerato il resto (qualora il resto fosse stato zero, per convenzione si sarebbe considerato quel numero K come resto). Su questo "resto" finale si sarebbe fatta la conta.
Nel testo non era specificato il numero scelto dall'Anziano, ma...

Scherzi a parte, se quanto da me scritto nei due precedenti post è vero, cioè se quella è una soluzione dell'intrigante quesito, allora la mia soluzione funziona per un numero N qualsiasi di incappucciati? A prima vista, mi parrebbe di sì.

Aspetto impaziente repliche.

Salmastro
Top
Profilo Invia messaggio privato AIM Yahoo MSN
Smjert
Dio maturo
Dio maturo


Registrato: 01/04/06 17:19
Messaggi: 1619
Residenza: Perso nella rete

MessaggioInviato: 12 Gen 2007 14:10    Oggetto: Rispondi citando

Ho voluto aspettare ancora un pochino a dare la risposta, perchè altri si cimentassero.
Salmastro la tua risposta è corretta Wink

Per quanto riguarda questo
salmastro ha scritto:
Scherzi a parte, se quanto da me scritto nei due precedenti post è vero, cioè se quella è una soluzione dell'intrigante quesito, allora la mia soluzione funziona per un numero N qualsiasi di incappucciati? A prima vista, mi parrebbe di sì.

devo chiedere.
Top
Profilo Invia messaggio privato HomePage
Smjert
Dio maturo
Dio maturo


Registrato: 01/04/06 17:19
Messaggi: 1619
Residenza: Perso nella rete

MessaggioInviato: 12 Gen 2007 14:29    Oggetto: Rispondi citando

Confermata anche la seconda parte.
Top
Profilo Invia messaggio privato HomePage
Salmastro
Dio minore
Dio minore


Registrato: 13/12/06 19:36
Messaggi: 883
Residenza: Casalmico

MessaggioInviato: 12 Gen 2007 14:46    Oggetto: per Smjert Rispondi citando

sono veramente fiero di averci azzeccato!
ma, tu dicevi che le soluzioni sono più d'una!!
a parte quella banale (pari vs. dispari) ce n'è un'altra da te elaborata?
Dacci una dritta...
Salmastro
Top
Profilo Invia messaggio privato AIM Yahoo MSN
Smjert
Dio maturo
Dio maturo


Registrato: 01/04/06 17:19
Messaggi: 1619
Residenza: Perso nella rete

MessaggioInviato: 12 Gen 2007 14:59    Oggetto: Rispondi citando

Bhe in realtà non è elaborata da me:

Smjert ha scritto:
Copio e incollo quello che mi ha mandato un amico[...]


L'amico dice "comincia dividendoli in gruppi..."
Top
Profilo Invia messaggio privato HomePage
Salmastro
Dio minore
Dio minore


Registrato: 13/12/06 19:36
Messaggi: 883
Residenza: Casalmico

MessaggioInviato: 17 Gen 2007 13:08    Oggetto: non mi muovo! Rispondi citando

Smjert!
dacci una dritta meno criptica

Salmastro
Top
Profilo Invia messaggio privato AIM Yahoo MSN
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 19 Gen 2007 01:25    Oggetto: Rispondi citando

In attesa che l'amico di Smjert (che Smjert riesce a contattare in meno di 19 minuti!) si sbottoni un po' di più, propongo una generalizzazione.

Stessa situazione, stesse regole, stesse persone, stesso boia.
Insomma tutto uguale con una sola variante: i colori dei cappelli non sono solo 2 ma ben 10...
Top
Profilo Invia messaggio privato HomePage
Salmastro
Dio minore
Dio minore


Registrato: 13/12/06 19:36
Messaggi: 883
Residenza: Casalmico

MessaggioInviato: 20 Gen 2007 19:24    Oggetto: non mi riesce!!!! Rispondi citando

no, proprio non mi riesce!!!
...avevo pensato che, essendo dieci i condannati dieci fosse il max di colori per i quali fosse possibile trovare una soluzione. E che la generalizzazione fosse legata a: N condannati, N colori.
Per semplicità invece di colori ho usato nel mio ragionamento i numeri, anzi le cifre: è più facile scrivere le configurazioni!, che per inciso sarebbero
n^(n-1)
(se vale N cond. x N colori)
Per cui 2 cond. e 2 colori: 2 configurazioni (quelle viste dal primo)
per 3 si hanno 9 configurazioni, per 4 ben 64 e così via fino a 10^9.
Come fa il primo a dare una dritta disambigua a tutti?
Avevo pensato alle classi di resti modulo N. E cioè che comunicasse, con lo stabilito codice dei colori, la classe di appartenza della configurazione.
(per esempio: se bianco=0; nero=1; rosso=2
quando il 1° vede rosso-rosso-bianco, "legge" come 220, dice "nero", cioè 1, perchè 1 è il resto della divisione di 220 per il modulo 3
(mi scuserete la notazione assai carente)
E funziona per n=1 (sic); per n=2 e per n=3.
Il teorema di induzione ridotta (detto anche di minima astuzia), mi faceva ben sperare, ma già con n=4 crollava miseramente...
A meno che, non sia necessaria un'astuzia (grande) nel disporre le "matrici" delle configurazioni....
Cosa che, al momento, non sono in grado.
E' una strada percorribile? Vale la pena continuare?
Salmastro
Top
Profilo Invia messaggio privato AIM Yahoo MSN
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 21 Gen 2007 20:44    Oggetto: Rispondi citando

Prova a risolvere questa variante.
Dovrebbe illuminarti.

Il direttore di un carcere ogni giorno si reca nel braccio della morte e fa uscire i condannati mettendoli in fila in modo che ogni condannato veda la schiena di tutti i condannati davanti a sè.
Poi fa incollare sulla schiena di ogni condannato un numero (tutti diversi, tutti uguali, interi, decimali, non importa; basta che siano numeri) e propone il giochino secondo le regole già enunciate.

Chi indovina il proprio numero sopravvive gli altri... scossaaaaa!
Quale strategia garantisce la sopravvivenza a tutti i condannati tranne al primo (che, in questa variante, ha probabilità nulla di azzeccare il suo numero)?
Top
Profilo Invia messaggio privato HomePage
_L_
Semidio
Semidio


Registrato: 27/12/06 23:47
Messaggi: 215
Residenza: Brugherio (MI)

MessaggioInviato: 21 Gen 2007 21:05    Oggetto: Rispondi citando

ulisse ha scritto:
Prova a risolvere questa variante.
Dovrebbe illuminarti.

Il direttore di un carcere ogni giorno si reca nel braccio della morte e fa uscire i condannati mettendoli in fila in modo che ogni condannato veda la schiena di tutti i condannati davanti a sè.
Poi fa incollare sulla schiena di ogni condannato un numero (tutti diversi, tutti uguali, interi, decimali, non importa; basta che siano numeri) e propone il giochino secondo le regole già enunciate.

Chi indovina il proprio numero sopravvive gli altri... scossaaaaa!
Quale strategia garantisce la sopravvivenza a tutti i condannati tranne al primo (che, in questa variante, ha probabilità nulla di azzeccare il suo numero)?

Citazione:

il 1° condannato dice la somma di tutti gli altri numeri
il 2° sottrae dal numero che ha detto il 1° la somma dei numeri che vede
gli altri sottraggono dal numero del 1° i numeri che vedono o che hanno sentito


x la versione a N colori
Citazione:

si assegna un valore a ogni colore
si applica il metodo sopra, sommando modulo N
Top
Profilo Invia messaggio privato HomePage MSN
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 21 Gen 2007 22:13    Oggetto: Rispondi citando

Evviva Evviva Evviva Evviva Evviva

E il caso N = 2
Citazione:
è il bit di parità
Top
Profilo Invia messaggio privato HomePage
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 23 Gen 2007 13:28    Oggetto: Re: non mi riesce!!!! Rispondi citando

salmastro ha scritto:
(...) è più facile scrivere le configurazioni!, che per inciso sarebbero
n^(n-1)
(se vale N cond. x N colori)


Mi era scappato un particolare.
Perché n^(n-1) ?

Se hai n condannati e m colori le possibili configurazioni sono in numero di m^n (esattamente come le schedine del totocalcio con n partite e m possibili risultati).

Quindi nel caso n=m=N abbiamo N^N possibili configurazioni.

Ah. Ho capito ora mentre rispondevo. Dagli n condannati escludi il primo...

In ogni caso perché dici che il tuo ragionamento crolla per n>3 ?
Ecco. Ho capito ora anche questo!

Perché ti sei concentrato solo sull'informazione data dal primo ritenendo che essa, oltre che determinante, sia l'unica utilizzata per individuare il colore del proprio cappello!

Non è così: ogni condannato (dal secondo in poi) deve risolvere un sistema di 9 equazioni in 9 incognite.
8 equazioni sono in una sola incognita e si presentano già risolte: di quelli davanti vedo il colore del cappello e di quelli dietro (primo escluso) ascolto il colore del cappello.
L'ultima equazione è invece da risolvere ed è fornita dal primo condannato.
Egli può fornire una qualsiasi equazione che abbia un'unica limitazione: deve ammettere soluzione unica rispetto a una qualsiasi delle incognite.
Unica perché altrimenti gli altri condannati non possono risolverla, ognuno, univocamente.
Rispetto a una qualsiasi delle incognite perché tutti e 9 i condannati devono poterla risolvere.
Ciò implica (quando comincio così scrivo sempre delle stupidaggini quindi occhio agli strafalcioni!) che l'equazione debba essere in nove incognite, di primo grado e completa.
Se ammettiamo che i condannati possano memorizzare i coefficienti dell'equazione durante la fase di discussione della strategia allora queste sono le sole limitazioni.
Se, invece, non è previsto che vengano concordati i coefficienti allora l'unica equazione che resta è omogenea con tutti i coefficienti pari a 1.

Le soluzioni vanno ricercate in insiemi diversi a seconda delle varianti del quesito.
La variante coi numeri interi sulla schiena richiede che le soluzioni siano in N (insieme dei numeri interi).

Quella con gli n cappelli richiede che le soluzioni siano in Zn (classi di resto modulo n).

O nel mio ragionamento c'è un errore o sono miope perché le mie affermazioni non vedo come si concilino con quelle dell'amico di Smjert che sostiene sia possibile adottare differenti schemi risolutivi (ricordate quel sibillino: "comincia dividendoli in gruppi"?)
Top
Profilo Invia messaggio privato HomePage
Taifu
Semidio
Semidio


Registrato: 24/10/06 10:13
Messaggi: 203

MessaggioInviato: 24 Gen 2007 13:26    Oggetto: Rispondi citando

ulisse ha scritto:
Chi indovina il proprio numero sopravvive gli altri... scossaaaaa!
Quale strategia garantisce la sopravvivenza a tutti i condannati tranne al primo (che, in questa variante, ha probabilità nulla di azzeccare il suo numero)?


Per non rendere nulla la probabilità del primo condannato (altrimenti io mi rifiuterei di farlo!) propongo una variante leggermente migliore:

Citazione:
Si stabilisce a priori un numero a caso, diciamo 666, e il primo condannato somma a tutto quello che vede anche il numero fisso prestabilito. In questo modo il secondo può ancora dedurre con certezza il proprio numero e lo stesso gli altri, ma adesso il primo ha una probabilità maggiore di zero di indovinare il numero che ha sulla schiena.
Per la precisione 1/(N-n+1) detto N il numero massimo e n il numero minimo che il direttore potrà scegliere per i condannati.
Di poco, ma è comunque una strategia migliore.
Top
Profilo Invia messaggio privato
_L_
Semidio
Semidio


Registrato: 27/12/06 23:47
Messaggi: 215
Residenza: Brugherio (MI)

MessaggioInviato: 24 Gen 2007 14:08    Oggetto: Rispondi citando

Taifu ha scritto:
ulisse ha scritto:
Chi indovina il proprio numero sopravvive gli altri... scossaaaaa!
Quale strategia garantisce la sopravvivenza a tutti i condannati tranne al primo (che, in questa variante, ha probabilità nulla di azzeccare il suo numero)?


Per non rendere nulla la probabilità del primo condannato (altrimenti io mi rifiuterei di farlo!) propongo una variante leggermente migliore:

Citazione:
Si stabilisce a priori un numero a caso, diciamo 666, e il primo condannato somma a tutto quello che vede anche il numero fisso prestabilito. In questo modo il secondo può ancora dedurre con certezza il proprio numero e lo stesso gli altri, ma adesso il primo ha una probabilità maggiore di zero di indovinare il numero che ha sulla schiena.
Per la precisione 1/(N-n+1) detto N il numero massimo e n il numero minimo che il direttore potrà scegliere per i condannati.
Di poco, ma è comunque una strategia migliore.

spiacente ma:
1) i numeri possono essere non interi, e la probabilità di azzeccare un numero su un intervallo continuo è nulla
2) N = infinito, n = - infinito
3) la probabilità di indovinare non cambia anche aggiungendo un altro numero
Top
Profilo Invia messaggio privato HomePage MSN
Taifu
Semidio
Semidio


Registrato: 24/10/06 10:13
Messaggi: 203

MessaggioInviato: 24 Gen 2007 14:20    Oggetto: Rispondi

_L_ ha scritto:
Taifu ha scritto:
ulisse ha scritto:
Chi indovina il proprio numero sopravvive gli altri... scossaaaaa!
Quale strategia garantisce la sopravvivenza a tutti i condannati tranne al primo (che, in questa variante, ha probabilità nulla di azzeccare il suo numero)?


Per non rendere nulla la probabilità del primo condannato (altrimenti io mi rifiuterei di farlo!) propongo una variante leggermente migliore:

Citazione:
Si stabilisce a priori un numero a caso, diciamo 666, e il primo condannato somma a tutto quello che vede anche il numero fisso prestabilito. In questo modo il secondo può ancora dedurre con certezza il proprio numero e lo stesso gli altri, ma adesso il primo ha una probabilità maggiore di zero di indovinare il numero che ha sulla schiena.
Per la precisione 1/(N-n+1) detto N il numero massimo e n il numero minimo che il direttore potrà scegliere per i condannati.
Di poco, ma è comunque una strategia migliore.

spiacente ma:
1) i numeri possono essere non interi, e la probabilità di azzeccare un numero su un intervallo continuo è nulla
2) N = infinito, n = - infinito
3) la probabilità di indovinare non cambia anche aggiungendo un altro numero


Mi spiace ma confermo la mia opinione.

Nella realtà il direttore è obbligato a dare dei numeri che, per quanto grandi, non possono essere infiniti e può anche dire un numero non intero ma non me lo vedo che scrive un numero decimale infinito su una schiena "finita". Certo potrebbe usare una penna infinitamente piccola, ma i carcerati dovrebbero poi usare degli occhiali infinitamente grandi...

Per questi motivi la mia strategia, per quanto di poco, diciamo pure di un epsilon piccolo a piacere, è migliore.

Intendiamoci: io nemmeno c'ero arrivato alla soluzione per cui potrei anche starmene zitto... Smile
Top
Profilo Invia messaggio privato
Mostra prima i messaggi di:   
Nuovo argomento   Rispondi    Indice del forum -> Enigmi e giochi matematici Tutti i fusi orari sono GMT + 1 ora
Vai a 1, 2  Successivo
Pagina 1 di 2

 
Vai a:  
Non puoi inserire nuovi argomenti
Non puoi rispondere a nessun argomento
Non puoi modificare i tuoi messaggi
Non puoi cancellare i tuoi messaggi
Non puoi votare nei sondaggi