I 100 prigionieri fanno prima a scontare la pena?

[3m0o]

Cento prigionieri sono appena entrati in prigione. Il direttore dice loro che a partire da domani, ognuno di loro sarà messo in una cella isolata, senza poter comunicare tra di loro. Ogni giorno, il direttore sceglierà uno dei prigionieri a caso e uniformemente con reinserimento, e lo metterà in una stanza per gli interrogatori contenente solo una lampadina con un interruttore a levetta. Il prigioniero sarà in grado di osservare lo stato attuale della lampadina (se accesa o spenta). Se lo desidera, può cambiare lo stato della lampadina. Ha anche la possibilità di annunciare che crede che tutti i prigionieri abbiano visitato la stanza. Se questo annuncio è vero, allora tutti i prigionieri vengono liberati, ma se è falso, tutti i prigionieri vengono giustiziati. Il direttore se ne va e i prigionieri si riuniscono per discutere il loro destino. Possono accordarsi su una strategia che garantirà loro la libertà?

Assunzione 1: I prigionieri possono tenere il conto dei giorni
Assunzione 2: La lampadina è inizialmente spenta e i prigionieri lo sanno

Attenzione è leggermente differente da questo:
https://www.matematicamente.it/forum/viewtopic.php?f=12&t=43778&p=321785&hilit=100+prigionieri#p321785

"Titania":Io avrei una soluzione, però mi sembra un po' lunga, spero per loro che ne trovino una più semplice!
Allora:

I prigionieri scelgono uno di loro che avrà il compito di spegnere la lampadina, tutti gli altri potranno solo accenderla.
Ora, ogni volta che un detenuto verrà chiamato e troverà la luce spenta dovrà accenderla, ma solo se chiamato per la prima volta. In tutti gli altri casi dovrà lasciare la situazione invariata. Quello scelto all'inizio dovrà invece spegnere la lampadina tutte le volte che la troverà accesa.
Si avrà la certezza che tutti sono stati chiamati quando il "prescelto" avrà spento la lampadina 99 volte.

a) Dimostrate che la soluzione di Titania ha un tempo medio di circa 28 anni e mezzo.
b) Riuscite a fare meglio ?
c) Riuscite a trovare una soluzione che ci mette in media tra i 9 e gli 11 anni ?

[Quinzio]

Solo per la parte a)
Si parte con la lampadina accesa e 99 prigionieri (in breve pr) su 100 possono spegnerla. Non la puo' spegnere il prescelto.
La probabilita' di estrarre un pr che puo' spegnerla sono 99/100.
Un processo di tale tipo e' un processo bernoulliano e il tempo medio di attesa di un evento (con probabilita' $p$) e' $1/p$.
Quindi il tempo medio di attesa per la prima estrazione e' 100/99.
Poi bisogna aspettare che venga estratto il prescelto, questa volta con probabilita' 1/100, con un tempo medio di attesa di 100.
Per la terza estrazione la probabilita' e' di 98/100, quindi il tempo di attesa e' 100/98.
Poi bisogna aspettare il prescelto con un tempo di attesa medio di 100 giorni.
E cosi' via'...
Quindi in totale avremo $99 \times 100 + 100\sum_{n=1}^{99} 1/n \approx 10417 $ giorni da attendere.
In anni fa circa 28 e mezzo.

[3m0o]

anche se hai invertito i ruoli di spengere/accendere ma non cambia nulla nella sostanza

[veciorik]

A spanne (non sono un matematico) direi che si può risparmiare molto tempo in questo modo:

[*:2hn4xpza]90 accendono la lampadina una sola volta ciascuno, alla prima chiamata in cui la trovano spenta [/*:m:2hn4xpza][*:2hn4xpza]altri 10 la spengono 9 volte, solo se è accesa altrimenti non fanno niente (: aspettano il prossimo turno)[/*:m:2hn4xpza][*:2hn4xpza]9 dei 10 spegnitori, dopo aver eseguito 9 spegnimenti, attendono un paio di turni senza far nulla accertandosi che la lampadina sia spenta, poi la accendono, una sola volta ciascuno[/*:m:2hn4xpza][*:2hn4xpza]il decimo e ultimo spegnitore, eletto all'inizio, la spegne 9 volte dopo la pausa intermedia e, dopo 9 spegnimenti, dichiara che tutti hanno agito (: visitato la stanza di controllo)[/*:m:2hn4xpza][/list:u:2hn4xpza]

[veciorik]

Un ulteriore accorciamento del processo si ottiene aumentando il numero delle fasi:

In precedenza proposi $ \ \ 90a10s+9a1s \ \ $ dove $ \ a \ \ $ e $ \ s \ \ $ indicano i compiti assegnati : $ \ a$=accendere, $ \ s$=spegnere, e $ \ + \ $ una pausa di consolidamento tra le due fasi, per un totale di circa 20 turni ( 9 + 2 + 9 ).

Ora propongo $ \ \ 80a20s+16a4s+3a1s \ \ $ per un totale di circa 15 turni ( 4 + 2 + 4 + 2 + 3 ).

[Quinzio]

@veciorix

E' una buona idea. Infatti anche io avevo pensato a come fare, aumentando il numero dei prescelti e nominando anche un super-prescelto.
Il problema che vedo, purtroppo, e' che non c'e' nessuna garanzia dell'ordine di chiamata.
Potrebbe accadere che viene chiamato un prigioniero comune, che accende.
Poi viene chiamato il super-prescelto, che spegne.
Poi un altro prigioniero, poi il super-prescelto.
Dopo 9 volte il super-prescelto conclude che tutti sono stati chiamati, e lo dichiara, sbagliando.

Siamo d'accordo che sono scenari che diventano via via molto poco probabili, ma qui il requisito e' di avere la certezza che tutti siano stati chiamati.

Piu' di tanti scenari alternativi non esistono secondo me, perche' questa lampadina o e' accesa o e' spenta, piu' di tanto non puo' fare .
Se qualcuno ha la soluzione, potrebbe metterla ormai....

[3m0o]

Soluzioni
Per b)

Chiaramente quella di c) andrebbe bene per b) però ne metto una differente. Non si risparmia molto tempo ma un qualcosina. Invece di scegliere il prescelto a priori lo si sceglie dinamicamente.
Nei primi 100 giorni:
Nessuno accende la lampadina, tranne il primo che entra due volte nella stanza, diciamo al giorno \(k\) e dichiara di essere il prescelto.
Scenario 1:
Se nessuno è entrato due volte al 100 giorno la lampadina è spenta e chi entra può dire che ci sono passati tutti e si liberano. Ma questo è poco probabile.
Scenario 2:
Se qualcuno entra al giorno \(1 < k \leq 100 \) due volte, accende la lampadina e dichiara di essere il prescelto. Tutti gli altri non fanno niente tranne al 100-esimo giorno che la lampadina viene spenta.

A partire dal 101-esimo giorno:
Il prescelto è l'unico che può spegnere la lampadina. Gli altri prigionieri si dividono in due classi

Prigionieri 1: I \(k-2\) prigionieri che sono entrati prima del giorno \(k\), ovvero quelli che hanno osservato la lampadina spenta nei primi 100 giorni, non fanno niente.
Prigionieri 2: I prigionieri che non sono mai entrati nei primi 100 giorni oppure che sono entrati e hanno osservato la lampadina accesa nei primi 100 giorni la accendono solo la prima volta che ci entrano se la trovano spenta e non fanno niente se la trovano accesa.

Il prescelto ora invece di dover contare fino a 99 spegnimenti dovrà contare solo fino a \( 101-k \leq 99\) spegnimenti, perché sa che nei primi \(k-1\) giorni sono entrati esattamente \(k-1\) prigionieri (compreso lui).

Per c)

La domanda è un po' trabocchetto per il runtime
Ma l'idea di veciorik è quella giusta. Il gioco si divide in due turni. Il primo turno dura \( g_1 \) giorni e il secondo turno \(g_2\) giorni. A priori vengono scelti un prescelto e \( x \) assistenti che devono contare fino ad una certa quota \(q\) di prigionieri prefissata, gli altri sono prigionieri normali, che chiamerò semplicemente prigionieri.

Turno 1:
Nei primi \(g_1\) giorni il comportamento è il seguente:
Prigionieri: Se è la prima volta che entra nella stanza e trova la lampadina spenta la accende, se la trova accesa non fa niente. A partire dalla seconda volta che entra non fa nulla.
Assistenti: Ogni volta che un assistente trova la lampadina accesa e non ha ancora raggiunto la quota \(q\) la spegne e ricorda il numero di volte che la spegne. Se ha raggiunto la sua quota \(q\) non fa nulla.
Il prescelto: Non fa nulla

Turno 2:
Alla fine del turno 1 il comportamento è il seguente:
Prigionieri: Non fa nulla
Assistenti: Se un assistente ha raggiunto \(q\) spegnimenti nel turno 1 accende la lampadina, se non ha raggiunto ancora la quota di \(q\) spegnimenti nel turno 1 non fa nulla.
Prescelto: Ogni volta che trova la lampadina accesa la spegne e per ogni spegnimento sa che sono entrati \(q\) prigionieri.

Se alla fine del turno 2 non sono ancora liberi si ripetono i turni 1 e 2 alternandoli fino a quando non escono. Gli assistenti che non sono riusciti a comunicare la loro quota se la ricordano e quindi possono chiaramente arrivare ad esempio a \(2q\), in tal caso al turno successivo possono accendere la lampadina 2 volte.

Non ho calcolato il runtime di questo algoritmo sinceramente ma ho letto che simulazioni al computer con differenti parametri arrivano a stimare un runtime tra i 3500 e i 4000 giorni con 100 prigionieri e quindi circa 9.5 e 11 anni.

NB: Nel ultimo giorno del turno 1 chiaramente può succedere che la lampadina sia accesa e ad entrare sia un prigioniero normale. In tal caso egli la spegne e così si andrebbe a perdere il conto di quello che è entrato e l'ha accesa per ultimo, ma che non sa che non gliel'hanno contata. Quindi chi la spegne dovrà riaccenderla al turno 1 successivo.

[Quinzio]

"3m0o":
Per c)

La domanda è un po' trabocchetto per il runtime
Ma l'idea di veciorik è quella giusta. Il gioco si divide in due turni. Il primo turno dura \( g_1 \) giorni e il secondo turno \(g_2\) giorni. A priori vengono scelti un prescelto e \( x \) assistenti che devono contare fino ad una certa quota \(q\) di prigionieri prefissata, gli altri sono prigionieri normali, che chiamerò semplicemente prigionieri.

Turno 1:
Nei primi \(g_1\) giorni il comportamento è il seguente:
Prigionieri: Se è la prima volta che entra nella stanza e trova la lampadina spenta la accende, se la trova accesa non fa niente. A partire dalla seconda volta che entra non fa nulla.
Assistenti: Ogni volta che un assistente trova la lampadina accesa e non ha ancora raggiunto la quota \(q\) la spegne e ricorda il numero di volte che la spegne. Se ha raggiunto la sua quota \(q\) non fa nulla.
Il prescelto: Non fa nulla

Turno 2:
Alla fine del turno 1 il comportamento è il seguente:
Prigionieri: Non fa nulla
Assistenti: Se un assistente ha raggiunto \(q\) spegnimenti nel turno 1 accende la lampadina, se non ha raggiunto ancora la quota di \(q\) spegnimenti nel turno 1 non fa nulla.
Prescelto: Ogni volta che trova la lampadina accesa la spegne e per ogni spegnimento sa che sono entrati \(q\) prigionieri.

Se alla fine del turno 2 non sono ancora liberi si ripetono i turni 1 e 2 alternandoli fino a quando non escono. Gli assistenti che non sono riusciti a comunicare la loro quota se la ricordano e quindi possono chiaramente arrivare ad esempio a \(2q\), in tal caso al turno successivo possono accendere la lampadina 2 volte.

Non ho calcolato il runtime di questo algoritmo sinceramente ma ho letto che simulazioni al computer con differenti parametri arrivano a stimare un runtime tra i 3500 e i 4000 giorni con 100 prigionieri e quindi circa 9.5 e 11 anni.

NB: Nel ultimo giorno del turno 1 chiaramente può succedere che la lampadina sia accesa e ad entrare sia un prigioniero normale. In tal caso egli la spegne e così si andrebbe a perdere il conto di quello che è entrato e l'ha accesa per ultimo, ma che non sa che non gliel'hanno contata. Quindi chi la spegne dovrà riaccenderla al turno 1 successivo.

C'e' qualcosa che non mi torna, ma probabilmente sono io a non aver capito, anche perche' vedo che il problema e' noto...

Siamo nel turno 1 un po' prima della sua fine e un prigioniero accende la luce.
Nessun assistente viene chiamato e il turno 1 finisce con la lampadina accesa.
Vengono chiamati degli assistenti, che trovano la luce accesa e non fanno nulla.
Dopo qualche giorno viene chiamato il prescelto, che trova la lampadina accesa e pensa erroneamente che sia stata accesa da un assistente e quindi conta $q$ prigionieri, sbagliando.

Come soluzione a questo problema, il primo giorno di ogni turno la luce viene spenta sempre, ma in questo modo un prigioniero che l'ha accesa prima e non e' stato contato da un assistente non ha modo di saperlo.
Pensa erroneamente di essere stato contato e non accende piu' la luce.

Dove sbaglio ?

[3m0o]

Premetto che la soluzione l'ho letta e non è menzionato questo problema. Ci ho pensato anche io a questo problema e credo che basti dire quanto segue.
Se l'ultimo giorno del turno succede che la lampadina è accesa allora:
- Se entra un assistente la spegne e conta +1 alla sua quota.
- Se un qualunque altro prigioniero entra la spegne e la dovrà accendere in un turno dopo. Questo significa che se è un prigioniero che ha già acceso la lampadina fa come se non l'avesse mai accesa, se invece è un prigioniero che non l'ha mai accesa dovrà accenderla una volta in più.

La soluzione dice quanto segue:

To begin the protocol’s description, there are three different possible
roles for a prisoner: head counter, assistant counter, and “drone”. There is exactly one
head counter, and there is some number of assistant counters, while the vast
majority prisoners are still drones regular prisoner with no counting tasks. The head
counter and all assistant counters all have an integer variable in their heads, initialized to
one.
The protocol has two stages, Stage I and Stage II. Each stage lasts for a certain number
of preset days, which we will call s1 and s2 , respectively. In Stage I, each assistant
counter is responsible for counting a quota of q drones. In Stage II, the head counter will
be responsible for counting up the assistant counters who have reached their quota. In
this way, the head counter counts toward n in jumps of size q. If the head counter does
not succeed by the end of Stage II, then we repeat Stage I and Stage II again, still
maintaining all the mental counts from before. In other words, we repeatedly alternate
between Stages I and II until victory is declared.

[Quinzio]

"3m0o":

Premetto che la soluzione l'ho letta e non è menzionato questo problema. Ci ho pensato anche io a questo problema e credo che basti dire quanto segue.
Se l'ultimo giorno del turno succede che la lampadina è accesa allora:
- Se entra un assistente la spegne e conta +1 alla sua quota.
- Se un qualunque altro prigioniero entra la spegne e la dovrà accendere in un turno dopo. Questo significa che se è un prigioniero che ha già acceso la lampadina fa come se non l'avesse mai accesa, se invece è un prigioniero che non l'ha mai accesa dovrà accenderla una volta in più.

Ok, pero'...
Siamo all'ultimo giorno del turno 1, la lampadina e' accesa, ed entra un assistente.
L'assistente dovrebbe spegnerla ma l'ha gia' raggiunto la quota $q$ e quindi non la spegne...

Facendo un minimo di ricerca su internet salta subito fuori quel paper che hai citato.
Il fatto che non citi questo caso particolare e' un po' sospetto.

[3m0o]

Non vedo un problema. La spegne e ha contato \(q+1\), poi se comunica al turno 2 i suoi \(q\), poi al turno dopo riparte con quota \(1\).