100 piccoli prigionieri

[nato_pigro1]

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

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 nuemero, anche grande, di estrazioni vengano comunque estratti tutti
_la soluzione esiste e non è una cavolata
_i detuni 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?

[adaBTTLS1]

può dire se ci sono passati già tutti almeno una volta o non dire niente

non può dire "non ci sono passati tutti" ?

[Titania1]

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.

[Umby2]

Concordo con Titania

Effettivamente sara' molto lunga ....

[nato_pigro1]

"adaBTTLS":

può dire se ci sono passati già tutti almeno una volta o non dire niente

non può dire "non ci sono passati tutti" ?

no, l'unica cosa che può dire è "ci sono passati tutti" oppure non dire niente. E comunque dicendo "non ci sono passati tutti" potrebbe perdere...

@Titania esatto la soluzione è quella.

C'è un modo per ottimizzare il tempo, io però non conosco la soluzione. Forse ha a che fare con scegliere due o più rappresentanti...

[Titania1]

Comunque molto carino...

Se scopri come ottimizzare il tempo facci sapere!

[adaBTTLS1]

no, l'unica cosa che può dire è "ci sono passati tutti" oppure non dire niente. E comunque dicendo "non ci sono passati tutti" potrebbe perdere...

la mia soluzione, molto più banale, prevedeva invece la certezza di vincere proprio dicendo "non ci sono passati tutti".
[anche perché, secondo me, una volta che sono passati tutti, se nessuno dice nulla per tanto tempo, per me avrebbero perso in partenza...]
la aggiungo qui, senza spoiler, visto che ormai si è chiarito che la "vera" soluzione è quella detta da Titania.

con un certo numero di "rappresentanti" (da 2 a 98), gli unici che avrebbero potuto "accendere" la lampadina, ma non sarebbe servito a nulla (accenderla):
gli altri (sempre da 2 a 98) detenuti non fanno nulla e non dicono nulla, per cui la lampada, da spenta, rimane spenta. la prima volta che un rappresentante viene estratto, trova la lampada spenta ed è certo che non è passato alcun altro rappresentante, e quindi non sono passati tutti.

[nato_pigro1]

"adaBTTLS":

no, l'unica cosa che può dire è "ci sono passati tutti" oppure non dire niente. E comunque dicendo "non ci sono passati tutti" potrebbe perdere...

la mia soluzione, molto più banale, prevedeva invece la certezza di vincere proprio dicendo "non ci sono passati tutti".
[anche perché, secondo me, una volta che sono passati tutti, se nessuno dice nulla per tanto tempo, per me avrebbero perso in partenza...]
la aggiungo qui, senza spoiler, visto che ormai si è chiarito che la "vera" soluzione è quella detta da Titania.

con un certo numero di "rappresentanti" (da 2 a 98), gli unici che avrebbero potuto "accendere" la lampadina, ma non sarebbe servito a nulla (accenderla):
gli altri (sempre da 2 a 98) detenuti non fanno nulla e non dicono nulla, per cui la lampada, da spenta, rimane spenta. la prima volta che un rappresentante viene estratto, trova la lampada spenta ed è certo che non è passato alcun altro rappresentante, e quindi non sono passati tutti.

ah ho capito cosa volevi dire, ma non è così il gioco: i detenuti possono solo dire "siamo passati tutti" o non dire niente. Non è che devono dire qualcosa di vero...
Poi chiaramente non è un gioco "reale": anche se ci mettessero un'infinità di tempo non è questo che conta. Il gioco consisteva nel trovare un procedimento algoritmico per essere certi di arrivare a una soluzione. 100 è un numero indicativo, non è questo l'importante, se avessi detto 1000 la soluzione valeva ugualmente indipendentente dal tempo stratosferico che magari sarebbe servito...