Expert Riddle

[riosluts]

I bet noone will get this extremely hard riddle


100 prisoners are imprisoned in solitary cells. Each cell is windowless and soundproof. There's a central living room with one light bulb; the bulb is initially off. No prisoner can see the light bulb from his or her own cell. Each day, the warden picks a prisoner equally at random, and that prisoner visits the central living room; at the end of the day the prisoner is returned to his cell. While in the living room, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting the claim that all 100 prisoners have been to the living room. If this assertion is false (that is, some prisoners still haven't been to the living room), all 100 prisoners will be shot for their stupidity. However, if it is indeed true, all prisoners are set free and inducted into MENSA, since the world can always use more smart people. Thus, the assertion should only be made if the prisoner is 100% certain of its validity.

Before this whole procedure begins, the prisoners are allowed to get together in the courtyard to discuss a plan. What is the optimal plan they can agree on, so that eventually, someone will make a correct assertion?

[buddyjuf]

each prisoner twists the lightbulb 1 time

when a prisoner enters, he can check which one he is but undoing the twists and counting the number

he then redoes thes number of twists + 1, to show that he was there

the prisoner that sees that the lightbulb has been twisted 99 times can claim that he is the 100th person to be in that room

[Arousal Design]

so basically the riddle is, how can the prisoners deduce from the toggled light bulb that everyone was in the room...


what bdjuf said.

[HomeTown_Hero]

42

[WicKed NinJas]

Originally posted by Arousal Design
so basically the riddle is, how can the prisoners deduce from the toggled light bulb that everyone was in the room...


what bdjuf said.

ahhh..the riddle in the riddle...lol

[serious]

Originally posted by riosluts
I bet noone will get this extremely hard riddle


100 prisoners are imprisoned in solitary cells. Each cell is windowless and soundproof. There's a central living room with one light bulb; the bulb is initially off. No prisoner can see the light bulb from his or her own cell. Each day, the warden picks a prisoner equally at random, and that prisoner visits the central living room; at the end of the day the prisoner is returned to his cell. While in the living room, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting the claim that all 100 prisoners have been to the living room. If this assertion is false (that is, some prisoners still haven't been to the living room), all 100 prisoners will be shot for their stupidity. However, if it is indeed true, all prisoners are set free and inducted into MENSA, since the world can always use more smart people. Thus, the assertion should only be made if the prisoner is 100% certain of its validity.

Before this whole procedure begins, the prisoners are allowed to get together in the courtyard to discuss a plan. What is the optimal plan they can agree on, so that eventually, someone will make a correct assertion?

is the answer reasonable or is it a trick question, like some bs that they can't see the lightbulb but they can see the light from it

[riosluts]

so do you guys give up. its a really hard one. and im not surprised if noone got it

[buddyjuf]

Originally posted by riosluts
so do you guys give up. its a really hard one. and im not surprised if noone got it

alright tell us

[grumpy]

the first one that goes in turn off the light. when he is called again..noone else may touch the switch.the light will be still off so he knows everybody has been in.

[riosluts]

Here's the answer that ive got


As before, the prisoners choose an 'announcer' among them.
Then they agree on the following procedure:

- each prisoner keeps a counter, which is initially 1.
- the bulb has a value assosiated with it, which is
- 0 for night number 0
- 1 for nights number 1... 800
- 2 for nights number 801...1600
- 4 for nights number 1601...2400
- 8 for nights number 2401...4540
- 2 for nights number 4541...5340
- 1 otherwise.
(day 1 shall be the day when the first prisoner enters
the room; the night number n shall be between the days
n and n+1).
- now, when a prisoner enters the room, he does the following:
- check if the bulb burns and add the value of bulb (for the previous
night) to their counter if that's the case.
- if the counter is 100 (this usually only happens for the
'announcer'), announce that every prisoner has been to the
room.
- for days 1..2400, if the binary representation of the counter
contains 1 in the digit corresponding to the value of the
bulb for the next night, switch on the bulb, switch it off otherwise.
- for days 2401 and the following days, if their counter is greater or
equal to the value of the bulb for the next night, switch on
the bulb, and switch it off otherwise.
- the 'announcer' switches the bulb off for days 801 and all following days.
- if the bulb is burning, reduce their counter by the value of the
bulb for the next night.

The idea here is to calculate the sum (which is known from the beginning)
of all the counters of the prisoners to a single prisoner (usually the
'announcer'). The sum
[value of bulb if it's burning] + counters of all prisoners
remains constant throughout the process, and all counters of the
prisoners remain non-negative. This means that if the counter
ever reaches 100 for a prisoner, all other prisoners have to
have been to the living room.

The speedup results from the fact that the chance that after the first
800 days, every prisoner's count is either 0 or 2, and that after the
first 1600 days every prisoner's count is either 0 or 4, and that after
the first 2400 days, every prisoner's count is either 0 or 8 except for
the 'announcer', and that after at most 4540 days, the 'announcer''s
count reaches 100 is pretty high.

Computer simulation of 500,000 runs gives:
average standard min max
deviation
3948.319 628.189 2850 10000

The parameters in the procedure were hand-tuned; so there
is no reason to believe that they're optimal.

Btw, for those who're interested:

A method which requires 4.2 Mio days on average is the following:

- assign each prisoner a number 0..99.
- again, each prisoner keeps a counter which is initially 0 though
(and serves a different purpose than the counter above)
- on each day, the prisoner entering the room does the following:
- let n be the day number, minus 1, modulo 100.
- if the bulb is off and n equals their number, set their counter
to n+1. announce that everyone has been to the room if
their number is 99.
- else, if the bulb is off and n is greater than our counter, set our
counter to n.
- switch on the bulb if our counter is less than or equal to n; switch
it off otherwise.

The problem here is, that to increase the maximum counter by one,
someone who knows the current maximum counter must enter the room
on a day with n=counter-1, and, on the following day, the prisoner
with the number equal to the current maximum counter must enter the
room.

[riosluts]

Originally posted by grumpy
the first one that goes in turn off the light. when he is called again..noone else may touch the switch.the light will be still off so he knows everybody has been in.

But what if he is called on the first day and the 3rd day. 98 prissoners still werent in the room

[grumpy]

more simple...after 100 days they all have been there.

[grumpy]

Originally posted by riosluts



But what if he is called on the first day and the 3rd day. 98 prissoners still werent in the room

true...back to the drawing board.

[Ironhorse]

Originally posted by grumpy
more simple...after 100 days they all have been there.

haha the simplest answer always works, I feel for riosluts, all that math

[hoe_vender]

I must be high

[BigFish]

the can get together and devise a plan where each time a prisoner is in the room, he takes a single shit in the corner. eventually, when that one prisoner enters and counts the 100 pieces of shit, then he can assert that 100 prisoners have been in the living room.

[serious]

Originally posted by Ironhorse


haha the simplest answer always works, I feel for riosluts, all that math

the prisoners are called at random so it could tkae much longer than 100 days

[grumpy]

I have found the source of the riddle and its not realy a riddle. The besy sequence will take 29 years. Its a theoritical problem from stanford.


the link riddle

[reynold]

Damn, I'm too lazy to read that long riddle.
But I guess, I can't get it either.
Oh well, good luck to those whose
trying to sort it out.

[rickholio]

Relatively easy.

- One prisoner is designated as the 'caller'. He'll be the one saying everyone has visited. The first time he goes in, he turns the light off.

- Every other prisoner will turn the light on if it is their first time in an unlit room.

- Every time the 'caller' arrives to the room, he turns off the light and increments his count. When he reaches 99, he can declare and everyone goes free.

No major math insanity, just a little planning.

[Arousal Design]

Originally posted by BigFish
the can get together and devise a plan where each time a prisoner is in the room, he takes a single shit in the corner. eventually, when that one prisoner enters and counts the 100 pieces of shit, then he can assert that 100 prisoners have been in the living room.

omg thats fuckin hilarious....

almost spit out my asia plum arizona green tea