Prison Switcharoo
cartalk.com
cartalk.com
On the other hand, the harder one is really considerably harder! Here it is, _The Two-Bulb Room_:
“Each of n prisoners will be sent alone into a room, infinitely often, but in some arbitrary order determined by their jailer. There are two lights in the room, each with its own binary switch. There will be no means of communication other than these switches, whose initial states are not known. The prisoners again have a chance to confer in advance.
Again, we want to ensure that some prisoner will eventually be able to deduce that everyone has visited the room. What, you did it before with only _one_ switch? Ah, but this time, every prisoner must follow the same set of rules.”
The second difference is the one that makes this problem genuinely difficult, though: “Ah, but this time, every prisoner must follow the same set of rules.” In other words, the agreed strategy has to be the SAME for every prisoner.
Easy: If the warden grabs a prisoner once a night, then the prisoners set up a system according to the passage of days.
Each prisoner starts with four "tokens." This means that in a prison population of 23 prisoners, there are 92 tokens in total for the prisoners.
We'll call the switches A and B. Starting off, A signifies 1 token. When you turn the switch on, you are putting a token into the switch. When you turn it off, you are taking one. B signifies 2 tokens.
When a prisoner visits the office, he looks to see if he can grab some tokens. If neither are on, then he puts in some tokens of his own. He will try to put as many tokens as possible in. So, for example, if he has 4 tokens, he will put in two.
Of course, if he has insufficient tokens, he does nothing.
After a predetermined period of time, the switches double in "worth." Switch A is now worth 2 tokens, and Switch B is worth 4. This will double again to 8 and 4, then 16 and 8, and so on, until they reach 64 and 32. If someone is able to accumulate 92 tokens, then it's apparent that everyone has visited the room at least once. Otherwise, it then starts over at 1 and 2.
We need four tokens for every prisoner because of a few possible extra tokens. If A and B are both on, then there are three extra tokens in the system. If you have fewer than four tokens per prisoner, it becomes possible to accumulate the required number without having everyone be in the room. You also can't have fewer tokens, because it would require that a prisoner collect tokens that might not actually be there.
Hard: If no one can figure out the passage of time, then they have to stay at 1 and 2. This will take much longer for someone to eventually accumulate all of the tokens, especially since all of them are trying to accumulate.
Edit: Here's a horribly written Python program that shows this process in action: http://codepad.org/iY121Ui3
... but this time, every prisoner must follow
the same set of rules.Did I miss something?
If switch A starts out in the ON position it would equal one 'fake' prisoner. If the counter just counts one extra (which equals p - 1 (himself) + 1 (fake prisoner) = p) it should be enough, no?
The prisoners meet together and designate a leader. The leader will maintain a tally. They also designate one of the switches to not matter. The prisoners then use the following strategy:
When a prisoner is lead to the room, if the designated switch is off and it is the prisoner's first time flipping the relevant switch, it is turned on. Else, flip the irrelevant switch. If the prisoner is the designated leader, and the relevant switch is on, he adds a count to his tally and turns the relevant switch off. Otherwise he just flips the irrelevant switch. This way, once the leader has seen the light be on a sufficient number of times he can definitively say that they have all been in the room.
Ah, but what's a sufficient number of times? The unknown initial state is what tripped me for a bit. :)
The switches are not connected to anything, correct me if I am wrong but how will you find out light is on sufficient number of times
What other sources of word/math/logic puzzles are out there?
The answer includes a major (and I believe flawed) assumption, which is that the visits will be uniformly distributed. However, the puzzle states that "I may choose the same guy three times in a row".
The Counter could visit the switch room 44 times without flipping the switch if such visits were the first 44 chosen. After everyone visits (which would be 1,012 visits since "given enough time, everyone will eventually visit the switch room as many times as everyone else"), the Counter will be no closer to knowing the truth.
Of course, it is true that the greater the number of visits the greater the probability that the Counter's final visit will fall after everyone has visited, but there is no guarantee.
Regardless of how many visits you assume for each prisoner, there will always remain a probability that the Counter's visits will be clustered early in the visitations. In such a scenario, the Counter's role becomes useless and all prisoners will die in prison.
If no announcement is made when someone dies, however, you've got a problem.
That case only requires flipping switch a off 22 times after the first day.
Obviously, removing that single bit of information makes the solution much harder to find, but adding then later removing it makes discovering the solution a more iterative thing. Which is desirable if, for example, you're giving these puzzles to your kids.
Deleted comment
Or, if you want to look at it more realistically, the run-time is limited by their lifespans I suppose. But given that they're prisoners who all presumably have life sentences, then they'll just play until they die, since the alternative is to simply be in prison until then anyway.
In this case, the problem asked for a precise solution, which was given in the resolution example, with no thought at all to that nagging little probability problem. So in order to "solve" this, I would have to know that everybody is basically supposed to disregard certain aspects of the problem. That's gotcha-type stuff that I always get wrong.
At #5 in your example, P1 would need to flick switch B.
I say mostly because the bit where one switch must be toggled and there are 2 switches makes it a bit different from 23C2. I don't think the difference is useful, though; the set of solutions is probably the same as the solution set for 23C2.
This problem is very clever, and there is a very clever way to solve this, assuming everyone plays nice. However, that solution assumes perfect collusion. These are prisoners we're talking about, so at least in some cases, we have to assume there may be bad actors involved. I mean this is a cute problem assuming the following:
1. All the prisoners have perfect memory (for this problem)
2. All the prisoners actually want to live.
3. The warden is telling the truth
4. The guards are all honest.
These are all the type of assumption that gets websites hacked. So what is the attack surface here?
* One of the prisoners decides this is a fun way to suicide
* One of the prisoners is in gang A, and one is in gang B. They value gang honor above their own life, and need to take out the other.
* A guard has decided that this is a great way to off some "scum"
* A prisoner forgets the algorithm, or hits the wrong switch, or other form of human error.
* As if_by_whisky points out: someone dies before the full run.
* The warden just wants to mess with people before feeding them to alligators, and just states "wrong" whenever someone declares all have visited.
* A prisoner can't handle the stakes, and cracks and makes the declaration early.
* The leader messes up the count.
There are probably a lot more.
Further, the warden is making assumptions that we can't be sure are true. Prisons are notorious for being bad at doing the actual security thing. Are there ways for prisoners to collude and do extra error checking on their end? Can a guard be bribed to help share state? Is there a way to get other prisoners involved in message passing, even if they manage to prevent direct collusion between the selected 23?
I don't know a way around all of these. In fact I'm pretty sure there a some combinations where everyone is just fucked. But, what can be done to add robustness to this problem? It seems pretty silly for prisoners (likely malicious actors as a generalization) will follow the rules and stay within the constraints the warden sets out.
I ask, because I've solved plenty of things in a nice elegant way, that were trivially broken by not assuming everything will play nicely in the environment. Similarly I've broken plenty of "awesome solutions" by asking questions about assumptions. The difference between the algorithmic solution and the real world is sometimes surprisingly large. Just some food for thought :)
It's fine if you think games are stupid, maybe try to get to the point a little quicker though.
Also, if you want to take a game theory approach, you're wrong about the warden. If the warden is just playing a sadistic mind game, and wants to fuck with the players before feeding them to the alligators, the correct "solution" to the game for the players (should they catch on to the warden), is to never declare, thus extending the game infinitely, or barring that maximally, before the warden bores of the game and offs them.
Give current society and the normal constraints on these popular games the answer to all the above are incredibly obvious, the answers you ask can be deducted. (No prisoner can die, if they could it would have been hinted at)
It's like claiming you can't do cryptic crosswords because the questions are not clear or don't follow proper English.
Although I imagine you are just trying to be difficult :)
Oh almost forgot the smiley to indicate something or another sarcastic... :)
"In theory, there is no difference between theory and practice. In practice, there is"
There's no option for the prisoners to go to the switch room at the outset; they've just arrived at the prison and don't know where it is. So it would not be possible to meet up there, they have to wait for the prison guards to take them there individually.