100 detenuti

[Lucignolo]

ci sono 100 detenuti in una carcere. Il direttore propone una sfida, se i detenuti vincono sono tutti liberi, se perdono restano in carcere.

Li chiamerà uno alla volta estraendo da un urna contenente i loro nomi (con reinserimento del nome) in una stanza in cui c'è solo una lampadina, l'unica cosa che il detenuto estratto può fare è cambiare lo stato della lampadina, da accesa a spenta (oppure lasciarlo invariato). Un detenuto, una volta entrato nella stanza può dire se ci sono passati già tutti almeno una volta o non dire niente. Se parla ed è effettivamente così allora vincono tutti, se sbaglia perdono tutti. Dopodiché il detenuto ritorna nella sua cella e il direttore ripete l'estrazione.
Detto questo li lascia organizzare un po' di tempo tutti assieme e poi li divide in celle separate e inizia le estrazioni.

Precisazioni:
_i detenuti non sanno quando un altro detenuto viene chiamato e non sanno se le estrazioni vengono fatte a tempi regolari
_sanno che la lampadina inizialmente è spenta
_il direttore li estrae a caso (non può estrarre volutamente sempre lo stesso)
_si suppone che entro un certo numero, anche grande, di estrazioni vengano comunque estratti tutti
_la soluzione esiste e non è una cavolata
_i detenuti non possono toccare la lampadina, solo accenderla o spegnerla (quindi non posso sapere se è accesa da tanto o da poco)

Quala strategia devono seguire i detenuti per vincere?

[delfo52]

questo, stranamente, pare assente nella sterminata biblioteca di B5. O forse è stato discusso con altri personaggi...

[delfo52]

semplifico con 3 detenuti.
Si accordano che A sarà l'unico che accenderà , tutte le volte che vedrà la lampadina spenta. B e C la spegneranno, ma solo la prima volta che troveranno la luce accesa.
A, quando vedrà la lampadina accesa la seconda volta, dopo averla accesa e spenta (alla prima e alla ennesima entrata), avrà la sicurezza che sia B che C sono stati chiamati
Con 100, si rischia che qualche carcerato passi a miglior vita prima che sia finito il giochetto...

[Lucignolo]

eh si... circa 10.000 sorteggi...

[Lucignolo]

la biblioteca come si sfoglia come si cercano tutti i quiz?

[delfo52]

dal portale, c'è in alto la finestrella per la ricerca. oppure si naviga nelle varie sezioni, che è sempre un piacere. amo le barzellette… e c'è anche qualche cosa di mio, sulla storia dei numeri

[Bruno]

La quarantena condiziona sempre più

Grazie delle proposte, Lucignolo

[Lucignolo]

grazie a questo forum!
il prossimo quesito però non date la soluzione lasciate che tutti si cimentino
le soluzioni andrebbero messe in una sezione separata

[Bruno]

Lucignolo, il bello di questo forum è che ognuno è libero di partecipare e di dire la propria sul problema proposto, scrivendo eventualmente la soluzione.
Chi vuole cimentarsi può farlo e non guardare i risultati altrui: la variabilità delle risposte, degli approcci, è sempre molto istruttiva
Fra parentesi, in molti problemi dare un'occhiata alle soluzioni degli altri stimola a cercare vie risolutive diverse.

[Lucignolo]

pensavo che si potrebbe migliorare la soluzione
mi pare troppo aspettare 10-12.000 estrazioni
ovviamente il tempo non conta nella risoluzione
ma sto pensando a come poter dimezzare i tempi

[franco]

Nel frattempo spiegatemela un po' meglio perchè non l'ho capita ...

Sempre nel caso di 3 soli detenuti.

1° sorteggiato A, accende la lampadina.
2° sorteggiato B, la spegne.
3° sorteggiato A, accende di nuovo.
4° sorteggiato A (ancora!) trova la lampadina accesa: cosa deve fare? C ancora non è passato!

[Lucignolo]

A, accende la lampadina, sarà il primo che toccherà qualcosa, quando lo sorteggeranno

B e C la spegneranno quando la troveranno accesa, ma solo la prima volta che passeranno

A, conterà un detenuto per ogni volta che la trova spenta, fino ad arrivare a 100-1 nel caso del quiz

A, quando la troverà accesa per un numero pari a 100-1 nel caso del quiz o 3-1 nel caso dell'esempio di A,B,C allora potrà dire "son passati tutti"

questa è la soluzione di Delfo, che prevede (ho fatto dei test) dalle 8000 alle 12000 estrazioni per arrivare a termine, e il passaggio di almeno 100 volte a detenuto presso la stanza della lampadina... una media di 10.000 estrazioni... per avere la certezza matematica!

possiamo migliorare?

[Gianfranco]

Bello questo problema, grazie Lucignolo!
Credo che non sia -ancora- nell'archivio di BASE Cinque.
Ho ripassato il problema del collezionista (coupon collector) che credo sia equivalente a questo.
Se non erro, il numero atteso di estrazioni per chiamare tutti i prigionieri è:
3 prigionieri -> 5,5 estrazioni
100 prigionieri -> 518,7... estrazioni
Naturalmente questo è un valore medio perciò le estrazioni in realtà possono variare da n. prigionieri all'infinito(?).
In generale, se il numero dei prigionieri è n, il numero atteso di estrazioni E(n) è:
$\large E(n)=n\cdot\sum_{i=1}^n {\frac{1}{i}} $
---
Non ho fatto progressi nella soluzione del problema, ma questi numeri possono aiutare a valutare l'efficienza di un strategia.

[Pasquale]

Salvo errori, la simulazione su 3 giocatori mi dà una media di circa 13 estrazioni da fare, calcolata su un milione di reiterazioni dell'algoritmo qui di seguito riportato.
Attivando le righe disattivate , si può addivenire alla media, ma in tal caso sarà meglio disattivare le righe 50 e 60. Se queste sono attive, meglio disattivare le altre numerate.
Un controllo di Gianfranco, più allenato sul Decimal, potrà risultare utile.

!'Quesito delle 100 lampadine ridotte a 3

!'1 è l'unico che accende soltanto e l'unico che parla
!'2 spegne solo la prima volta che viene sortito,
!' mentre negli altri casi lascia tutto com'è
!'3 si regola come il 2

DIM g(3) !'conteggio delle estrazioni per ogni giocatore, valido solo per sapere se il 2 o il 3 hanno mai spento

!'10 LET c=0
!'20 FOR m=1 TO 1000000
!'30 MAT g=ZER
LET cont=0 !'conteggio totale delle estrazioni
LET spegn=0 !'conteggio persone diverse entrate nel locale
LET luce=0 !'luce 0=spenta, luce1=accesa

RANDOMIZE
DO
LET x=1+INT(RND*3)'estrazione concorrente
LET cont=cont+1

IF x=1 AND luce=0 THEN
LET luce=1
LET g(1)=g(1)+1
IF spegn=2 THEN EXIT DO
ELSEIF x=2 AND luce=1 THEN
IF g(2)=0 THEN
LET luce=0
LET spegn=spegn+1
LET g(2)=g(2)+1
ELSEIF g(2)>0 THEN
LET g(2)=g(2)+1
END IF
ELSEIF x=3 AND luce=1 THEN
IF g(3)=0 THEN
LET luce=0
LET spegn=spegn+1
LET g(3)=g(3)+1
ELSEIF g(3)>0 THEN
LET g(3)=g(3)+1
END IF
END IF

LOOP
LET spegn=spegn+1
!'40LET c=c+cont
50 PRINT "Nel locale sono entrate";spegn;"persone diverse,"
60 PRINT "dopo";cont;"estrazioni totali."
!'NEXT M
!'PRINT "media estrazioni:";c/1000000

END

[Gianfranco]

Salvo errori, la simulazione su 3 giocatori mi dà una media di circa 13 estrazioni da fare, calcolata su un milione di reiterazioni dell'algoritmo qui di seguito riportato.

Ciao Pasquale, il tuo programma implementa abbastanza fedelmente l'algoritmo di Enrico. Tuttavia è costruito su misura per 3 persone ed è complicato generalizzarlo a n persone.
Ho rivisto e semplificato il tuo programma mantenendo il tuo stile ma la media questa volta risulta circa 7,5 estrazioni.

Codice: Seleziona tutto

LET c=0
DIM g(100) !'vettore 0/1 delle persone entrate nella stanza
LET np=1000 !'numero di prove, per calcolare la media
RANDOMIZE

FOR m=1 TO np
   MAT g=ZER
   LET cont=0 !'conteggio totale delle estrazioni
   LET spegn=0 !'conteggio persone distinte entrate nel locale
   LET luce=0 !'luce 0=spenta, luce 1=accesa
    
    
   !'Bisogna aspettare che "1" sia estratto per la prima volta e accenda la luce
   DO UNTIL x=1     
      LET x=1+INT(RND*3)!'estrazione di una persona
      LET cont=cont+1 !'conteggio estrazioni
      IF x=1 THEN LET luce=1
      !'PRINT x;
   LOOP
    
   !'Ora "1" deve contare 2 spegnimenti    
   DO UNTIL spegn=2     
      LET x=1+INT(RND*3)!'estrazione di una persona
      LET cont=cont+1 !'conteggio estrazioni
      !'PRINT x;
       
      IF x=1 AND luce=0 THEN !'se è la persona "1" e la luce è spenta
         LET luce=1 !'accende la luce
         LET spegn=spegn+1 !'incrementa il conteggio
      END IF
       
      IF x=2 AND luce=1 THEN !'se entra una persona e la luce è accesa
         IF g(x)=0 THEN !'se la persona entra per la prima volta
            LET luce=0 !'spegne la luce
            LET g(x)=1 !'e non la spegnerà mai più
         END IF
      END IF
       
      IF x=3 AND luce=1 THEN !'idem
         IF g(x)=0 THEN 
            LET luce=0
            LET g(x)=1
         END IF
      END IF 
       
   LOOP
   LET c=c+cont
   !'PRINT cont;c
    
   !'50    PRINT "Nel locale sono entrate";spegn;"persone diverse,"
   !'60    PRINT "dopo";cont;"estrazioni totali."
NEXT M
print
PRINT "media estrazioni:";c/np

END

---
La mia soluzione a questo problema è quasi equivalente a quella di Enrico ma filosoficamente diversa.
---
La strategia di Enrico è:
"A" mette un segno (accende la lampadina se è spenta) ogni volta che manca e gli altri lo cancellano (spengono la lampadina se è accesa) una sola volta ciascuno, quando lo trovano.
"A" conta quante volte è stato cancellato il suo segno.
In questo modo il conteggio inizia quando "A" entra nella stanza la seconda volta.
Con questa tecnica, la media delle estrazioni sembra essere 7,5 circa.
---
La mia versione è questa:
Ciascuna persona che entra nella stanza per la prima volta, lascia un segno se manca (accende la lampadina se è spenta).
"A" invece, cancella il segno (spegne la lampadina se è accesa) e aggiunge 1 al suo conteggio.
In questo modo il conteggio inizia quando "A" entra nella stanza per la prima volta (a meno che non sia lui il primo).
---
Comunque, con la mia versione, la media di estrazioni sembra essere 10,5 circa.