- Time
- Post link
Riddles — Page 10
- Time
- Post link
#1 they are all assigned one token, and a counter will collect all these tokens as to be able to assert that they have all entered the central living area.
#2 During the first 100 days:
If it is their first time in the living room and the light is off to leave it off. They then remove their token.
If it is their second time in the living room and the light is off to turn it on and assign themselves the role of the counter. The count (number of tokens) is equal to the day number minus one (since he's been in the room twice).
If the light is on, do nothing regardless until day 100, in which case switch it off.
This gives a bit of a head-start, on average the initial count is 12. Meaning there are now on average 11 people with no token, 88 people with one token each and the counter with 12 tokens.
I will also give you my main concept, which I came up with myself and is a huge advantage if you couldn't think of it yourself.
The concept is if we were to assert that a prisoner releases his token, wherever possible for the counter to collect by turning the light on, then we expect the counter and everyone else to enter the room once every time a token is released. Meaning there is conceptually 100 room entries per token release. Reducing this ratio should be our main concern.
I believe I've worked out the perfect strategy, but I have to do some pretty heavy number-crunching until I can make it optimal.
Afterwards I believe I could then produce an optimal strategy with the rather nasty alteration:
The procedure ends not when a prisoner asserts that all prisoners have entered the room, rather the prisoner must assert that all other prisoners now know and have asserted that all prisoners have entered the central living room.
Ooooh that's nasty, I shouldn't have thought of it. But it can be done.
- Time
- Post link
????????????????????????????????????????????? - Time
- Post link
Quote
Originally posted by: DanielB
I know it's a particularly nasty riddle. I'll give you the same thing I got that gave me a head-start (I've worked off this idea).... the prisoners agree that:
#1 they are all assigned one token, and a counter will collect all these tokens as to be able to assert that they have all entered the central living area.
#2 During the first 100 days:
If it is their first time in the living room and the light is off to leave it off. They then remove their token.
If it is their second time in the living room and the light is off to turn it on and assign themselves the role of the counter. The count (number of tokens) is equal to the day number minus one (since he's been in the room twice).
If the light is on, do nothing regardless until day 100, in which case switch it off.
This gives a bit of a head-start, on average the initial count is 12. Meaning there are now on average 11 people with no token, 88 people with one token each and the counter with 12 tokens.
I will also give you my main concept, which I came up with myself and is a huge advantage if you couldn't think of it yourself.
The concept is if we were to assert that a prisoner releases his token, wherever possible for the counter to collect by turning the light on, then we expect the counter and everyone else to enter the room once every time a token is released. Meaning there is conceptually 100 room entries per token release. Reducing this ratio should be our main concern.
I believe I've worked out the perfect strategy, but I have to do some pretty heavy number-crunching until I can make it optimal.
Afterwards I believe I could then produce an optimal strategy with the rather nasty alteration:
The procedure ends not when a prisoner asserts that all prisoners have entered the room, rather the prisoner must assert that all other prisoners now know and have asserted that all prisoners have entered the central living room.
Ooooh that's nasty, I shouldn't have thought of it. But it can be done.
why doesnt my way work.
- Time
- Post link
--Vizzini (Wallace Shawn), The Princess Bride
-------------------------
Kevin A
Webmaster/Primary Cynic
kapgar.typepad.com
kapgar.com
- Time
- Post link
- Time
- Post link
So I can surely decrete: mathematically impossible, UNLESS the prisoners can comunicate with each other, or if the prisoners cannot go into the room more than once.
- Time
- Post link
For instance, say days 1-99 are treated thus (all prisoners initially hold one conceptual token):
If the light is off:
1. And it is your first time in the room, remove your token and leave the light off.
2. And it is your second time in the room, designate yourself the counter, and count Days-1 as your initial count. Turn the light on.
If the light is on do nothing.
On day 100:
If the light is off:
1. And it is your first time in the room, then everyone has been in the room. Demand freedom.
2. And it is your second time in the room, designate yourself the counter, and count Days-1 (=99) as your initial count. Leave the light off in this instance since it is day 100.
If the light is on:
Turn it off.
That method gives you a head-start. On average the initial count is 12, however it is not an optimal head-start. For instance there is no reason to dedicate the first 100 days to it, in fact the first 20 days would be more than enough. It is so improbably that your initial count will be more than 20 you may as well save the other 60 days for better use.
Like I said, that concept I didn't think of initially myself. However my concept is that the more people you have on zero tokens the faster you will be able to transfer all the tokens to the counter. If you were to designate the first 20 days to this step you would instead have:
For instance, say days 1-19 are treated thus (all prisoners initially hold one conceptual token):
If the light is off:
1. And it is your first time in the room, remove your token and leave the light off.
2. And it is your second time in the room, designate yourself the counter, and count Days-1 as your initial count. Turn the light on.
If the light is on do nothing.
On day 20:
If the light is off:
1. And it is your first time in the room, then designate yourself the counter and start the count at 20. Leave the light off.
2. And it is your second time in the room, designate yourself the counter, and start the count at 19. Leave the light off.
That works much better, you can also improve your chances by having a special case for days 2 and 3 - that is, there is a 1% chance that the same person will be chosen twice in a row, if this happens you could insert the rules for days 2 and 3:
Day 2:
If it is your second time in the room, switch the light on but do not designate yourself the role of counter.
Day 3:
If the light is on, and it is your third time in the room (0.1% chance) then designate yourself the role of counter and start the count at 1.
If the light is on, and it is your second time in the room then designate yourself the role of counter and start the count at 2.
You get away with this because according to the rules for this period if on the third day the light is on, you know with certainty only one person had been in the room before you. On the forum which discussed this riddle over 3 years, no one ever mentioned that (at least I don't think so, I didn't go through all of it). What no one figured out, on the forum that discussed this riddle (in over 3 years), is that you can give yourself a further head-start by repeating this step! I couldn't believe it either. I know the average for repeating it goes down and down, but you only need to designate a certain number of days to it.
I would designate 20 more days for repeating it (possibly 1 or 2 days less). Thus:
The rules for days 21-39:
If the light is off:
And you are not the counter, and you have one token then remove your token and leave the light off.
And you are not the counter, and you have no tokens, then turn the light on and your new token count = days - 21.
And you are the counter then switch the light on and amend your count days - 21. Turn the light on.
I do not yet know the optimal number of times to repeat this, but I imagine it might be 3 or 4 times. The whole idea is to get as many people onto zero tokens as quickly as possible. Yes, you will have people with counts of any possible number, but they can be transferred to the counter in larger clumps at later times.
People on zero tokens are passive, that means when they enter the room they don't have to get rid of any tokens by switching the light on, and they don't have to collect any tokens by turning the light off. This is a huge advantage. by the end of 80 or 100 days, I imagine you could have average it to ~20 people on zero tokens (that is just an estimate at this stage). Compare that to running it once with 100 days allocated to it - which has an average of just 11 people on zero tokens. You've got a huge head-start.
Anyhow, that's not as far as I've got, but that's as far as hints from me come. I'm sure you can easily take this in the right direction to find the optimal plan now (something that apparantly no one from the original site could find).
- Time
- Post link
I still don't see how you transfer the counts to the counter.
- Time
- Post link
QuoteWell yes, for the most part. They could be recorded on paper or something in each prisoner's cell, if he has memory problems - I'll talk about the transfers later.
Originally posted by: Warbler
I think I understand it a little the "tokens" are imaginary right?
- Time
- Post link
- Time
- Post link
QuoteThey're using the light bulb to comunicate and transfer the tokens.
Originally posted by: ricarleite
Transfers?? Well, like I said, and I'm PRETTY sure of myself: if the prisoners absolutely cannot comunicate with each other, with no "token transfer" or anything like that, then it's IMPOSSIBLE to solve this one.
- Time
- Post link
But WHY did the other prisoner set the light off? Basically, what you said is: the last prisoner set the light off if he has been into the room before, but this can lead to an error. Let's asume only ONE prisoner is called for 5 straight days, and he sets the light off when he is called again the last day. So another prisoner gets called, it is the 6th day and the light is off, so he claims to be the last one, and is wrong.
I say it's mathematically impossible, DanielB says it can be done. Anyone else here might want to give an opinion, so we can decide once and for all if this one has a solution?
- Time
- Post link
- Time
- Post link
that the first time they enter the room while the light is off to remove their token and leave the light off,
the second time someone enters the room while the light is off to turn it on and deisgnate himself the role of counter.
then for the rest of that period the light remains on, to signal to the others that a counter has been chosen, and to ensure there is no error. Therefore on the last day - say day five, there are two posabilities. Either the light is on because the counter turned it on some time before, or it is off because there is no counter.
If it is off and it is your first time in the room, then you know everyone else was in the room. If it is off and it is your second time in the room you know one person is left to enter the room. if it is on you don't know how many people entered the room, but you know the counter counted all the ones to enter while the light was still off.
- Time
- Post link
- Time
- Post link
As I said before I'm completly sure that it is "logically" impossible, but I'll try to think of a way to improve your solution - even though I'll never get to 100% accuracy, it might lead to an error, even though the chances of getting it right are huge.
I must say it was one of the most intriguing logical problems I've ever seen.
I'll ask this one to some people I know, see if they can come up with a better answer - chances are they won't. - Time
- Post link
- Time
- Post link
- Time
- Post link
b = 0;
function PrisonerRiddle(a, b){
//a = status of the lamp
//b = number of days
b = b + 1;
if b < 100 then PrisonerRiddle(a, b);
else
//do stuff
//the solution would be something like:
if a == 0 then print("I am the last prisoner!");
end if
}
Come to think of it, I think I can do it creating threads for the prisoners, and all of them accessing the function. Which brings me to another riddle proposed by a "operating systems" profesor back in college, which I've solved by programming threads in Java. It's an easy one, and it goes like this:
Imagine that there are five filosofers sitting on a round table, each with a plate with spaghetti on it. These filosofers eat the spaghetti using 2 forks at the same time. Now, between each plate there is only one fork, so that a filosofer can see his plate, a fork on the left side, and a fork on the right side. OK? Now, every filosofer will start eating his spaghetti at a random time, eat it for a random time, and stop eating it at a random time, the proceed to eat again, ad infinitum. When a filosofer decides to eat the spaghetti, he'll reach for BOTH forks and proceed to eat. The problem is, if a filosofer grabs a fork, let's say, on his left side, the filosofer to his left can't grab his RIGHT fork, get it? Now, if a filosofer wants to eat, and he can't get both of his right and left forks, he'll just stay there, waiting for the fork. Unfortunally, this can lead to a lock up if every filosofer grabs one fork. Now, you gotta decide a special rule so that this scenario never happens, and the filosofers never lock up.
- Time
- Post link
Also, you'll notice the light is on at the bottom. All this means (in this instance) is that one token is currently being held by the light - so that when you add up the tokens they should tally. 21 (counter) + 1x9 + 1x6 + 1x2 + 61x1 + 1 (light bulb) = 100. I should note the example portrayed in the screenshot is not an average count at the end of those 4 cycles, it's just a random case. The get averages button does nothing yet.
- Time
- Post link
As you know, the average after 1 cycle is 11 people on zero. The average after 2 cycles is 14 people on zero. The average after 3 cycles is 17 people on zero. The average after 4 cycles is 19 people on zero. Now if after phase 1 you have the counter on only 1 or 2 (there's a total 1% chance of this) then it means you might want a fifth cycle.
Optimise the day numbers for each cycle.
There is a 0.545% chance that after the first cycle you reach 30+ people on zero. So, allocate 30 days for it.
If you reach 11 people on zero after the first cycle then there is a 0.509% chance that after the second cycle you have 31+ people on zero. So allocate 20 days for it.
If you reach 14 people on zero after the second cycle then there is a 0.518% chance after the third cycle that you have 32+ people on zero. So allocate 18 days for it.
If you reach 17 people on zero after the third cycle then there is a 0.576% chance after the fourth cycle you have 34+ people on zero. So allocate 16 days for it.
If you reach 19 people on zero after the fourth cycle then there is a 0.564% chance after the fifth cycle you have 34+ people on zero. So allocate 15 days for it.
Complete. Allocate 5 cycles for phase 1 as above. Phase 2 coming next....
- Time
- Post link
- Time
- Post link
- Time
- Post link