Cappelli, saggi e un dittatore mooooolto cattivo
il seguente problema è più o meno noto a tutti:
un dittatore moooolto cattivo decide di liberarsi di gran parte dei saggi del suo regno, ma concedo loro un'ultima possibilità di salvarsi: li mette in fila indiana e ad ognuno di essi mette in testa un cappello, o bianco o nero, senza che essi sappiano di che colore sia. decide allora di salvare solo quei saggi che indovinano il colore del loro cappello. L'unica informazione che hanno i saggi (che sono, diciamo, 100) è che vedono il colore del cappello di coloro che li seguono (il primo saggio vede gli altri 99, il secondo gli altri 98...) e sentono la risposta di coloro che li precedono.
Stabilire un metodo che consente di salvare più saggi possibili.
come ho già detto la soluzione è più o meno nota a tutti. Meno nota è però nel caso in cui i cappelli possano essere di n colori distinti.
ancora meno nota è se i saggi sono una infinità numerabile.
in particolare quest'ultima rasenta la follia.. e non chiedetemi di postarla perchè.... semplicemente non me la ricordo.
ciao, ubermensch
un dittatore moooolto cattivo decide di liberarsi di gran parte dei saggi del suo regno, ma concedo loro un'ultima possibilità di salvarsi: li mette in fila indiana e ad ognuno di essi mette in testa un cappello, o bianco o nero, senza che essi sappiano di che colore sia. decide allora di salvare solo quei saggi che indovinano il colore del loro cappello. L'unica informazione che hanno i saggi (che sono, diciamo, 100) è che vedono il colore del cappello di coloro che li seguono (il primo saggio vede gli altri 99, il secondo gli altri 98...) e sentono la risposta di coloro che li precedono.
Stabilire un metodo che consente di salvare più saggi possibili.
come ho già detto la soluzione è più o meno nota a tutti. Meno nota è però nel caso in cui i cappelli possano essere di n colori distinti.
ancora meno nota è se i saggi sono una infinità numerabile.
in particolare quest'ultima rasenta la follia.. e non chiedetemi di postarla perchè.... semplicemente non me la ricordo.
ciao, ubermensch
Risposte
Il problema non mi è noto, ma suppongo che la soluzione sia:
Trasformiamo la sequenza in bianchi=0 e neri=1. Basterà che il primo dica il bit di parità (tanto per lui è indifferente) perchè tutti gli altri a ritroso ricavino il proprio bit (colore) sottraendo la parità precedente alla propria.
Questo si può generalizzare al caso di più colori; il concetto di parità rimane il medesimo.
Nel caso di una infinità numerabile non si può applicare questo metodo; il problema è come calcolare il bit parità...
Ora ci penso un po' su...
Trasformiamo la sequenza in bianchi=0 e neri=1. Basterà che il primo dica il bit di parità (tanto per lui è indifferente) perchè tutti gli altri a ritroso ricavino il proprio bit (colore) sottraendo la parità precedente alla propria.
Questo si può generalizzare al caso di più colori; il concetto di parità rimane il medesimo.
Nel caso di una infinità numerabile non si può applicare questo metodo; il problema è come calcolare il bit parità...
Ora ci penso un po' su...
penso che sia giusto il caso con due colori.. (il primo quindi tira a casaccio il proprio colore e gli altri deducono il loro; per cui si salvano almeno 99 saggi; il primo ha il 50% di possibilità di salvarsi).
Non mi sembra però, per come ho interpretato io la tua soluzione, che possa essere generalizzata ad n colori... potresti spiegare meglio cos'è questo bit di parità? forse ho capito male io..
ciao, ubermensch
Non mi sembra però, per come ho interpretato io la tua soluzione, che possa essere generalizzata ad n colori... potresti spiegare meglio cos'è questo bit di parità? forse ho capito male io..
ciao, ubermensch
Molto rozzamente: se fai la somma di tutte le cifre di un numero di n cifre otterrai un numero la cui ultima cifra è detta parità.
Ad es.
$P(100110)-> 1+0+0+1+1+0= 11$ dunque 1 è la parità.
Se il primo calcola la parità vedendo 100110 il secondo potrà dedurre il proprio bit calcolando la propria parità $P(00110)-> 0$ e sottraendo in modulo quelle quelle precedenti, dunque 1.
Puoi facile vedere che P[n]=P[n-1]+n°cifra dunque n°cifra=P[n]-P[n-1] modulo 2
Vediamo nel caso di numeri decimali, cioè 10 colori; sia data la sequenza X1458373 dove X è il numero del 1° saggio:
1) $P(1458373)-> 1+4+5+8+3+7+3= 31$ dunque 1 è la parità e dirà 1 tanto ha comunque una possibilità su dieci.
2) $P(458373)-> 4+5+8+3+7+3= 30$ dunque 0 è la parità; n°cifra=P[n]-P[n-1] modulo 10; n=1-0=1
cioè 1 è quel numero che sommato alla sua parità gli da la parità precedente; dunque lui è sicuramente 1 (non può essere 11!)
3) $P(58373)-> 5+8+3+7+3= 26$ dunque 6 è la parità ed inoltre 3) sa, facendosi un po' di conti, che P[n-1]=0
n-1°cifra=P[n-1]-P[n-2]=6 n=10-6=4 cioè 4 è quel numero che sommato alla sua parità gli da la parità precedente.
Non sono stato molto chiaro, ma oggi sono molto stanco. Confido nella tua intelligenza.
Ad es.
$P(100110)-> 1+0+0+1+1+0= 11$ dunque 1 è la parità.
Se il primo calcola la parità vedendo 100110 il secondo potrà dedurre il proprio bit calcolando la propria parità $P(00110)-> 0$ e sottraendo in modulo quelle quelle precedenti, dunque 1.
Puoi facile vedere che P[n]=P[n-1]+n°cifra dunque n°cifra=P[n]-P[n-1] modulo 2
Vediamo nel caso di numeri decimali, cioè 10 colori; sia data la sequenza X1458373 dove X è il numero del 1° saggio:
1) $P(1458373)-> 1+4+5+8+3+7+3= 31$ dunque 1 è la parità e dirà 1 tanto ha comunque una possibilità su dieci.
2) $P(458373)-> 4+5+8+3+7+3= 30$ dunque 0 è la parità; n°cifra=P[n]-P[n-1] modulo 10; n=1-0=1
cioè 1 è quel numero che sommato alla sua parità gli da la parità precedente; dunque lui è sicuramente 1 (non può essere 11!)
3) $P(58373)-> 5+8+3+7+3= 26$ dunque 6 è la parità ed inoltre 3) sa, facendosi un po' di conti, che P[n-1]=0
n-1°cifra=P[n-1]-P[n-2]=6 n=10-6=4 cioè 4 è quel numero che sommato alla sua parità gli da la parità precedente.
Non sono stato molto chiaro, ma oggi sono molto stanco. Confido nella tua intelligenza.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo