Car Talk Puzzle Solution?
Mike Booth has a brilliant answer to the fiendish Car Talk puzzle. He’s allowing me to blog it in the interest of “open source puzzling.” But I’d ask you not to enter it into the contest as your own, you slimy bastards. Here goes:
One of the prisoners is chosen to be the Scorekeeper and he gets these special instructions:
“The very first time you enter the switch room, turn switch B off. If switch B is already off, flip switch A (just to waste time). Once this first trip is over you are ready to start keeping score in your head. Your score starts at 1.
From now on, follow these instructions:
If switch B is on, turn it off and add 1 to your score.
If switch B is off, turn it on and subtract 1 from your score.
Eventually your score will reach 23. When it does, tell the warden that everyone has visited the switch room.”Each of the other 22 prisoners gets these instructions:
“You are going to be sending a signal to the Scorekeeper to tell him that you’ve visited the switch room. But you can’t send the signal until you know that the Scorekeeper is listening.
When you first enter the switch room, flip switch A — but look at switch B and see if it is OFF or ON. Remember the position of switch B.
The next few times you enter the switch room, look to see if switch B has changed position. Once switch B changes position, you will know that the Scorekeeper is listening, and you can send the signal at your next opportunity. Until then, keep on flipping switch A every time. To send the signal, turn switch B from OFF to ON. If you can’t do that (because switch B is already ON) flip switch A and wait for another opportunity to send the signal. After you’ve sent the signal, don’t touch switch B again — just keep flipping switch A every time.
Remember, you are NEVER allowed to turn switch B off, and you are only allowed to turn it on ONCE.”
This strategy works because every player touches switch B exactly once, except for the Scorekeeper who is allowed to move it back and forth (but who keeps an account of how many moves he makes). In this system, Switch A isn’t very useful — it’s just something to do while waiting for a chance to use Switch B — and that makes me suspect that there’s a more elegant answer out there. I’ll wait and see.
So, one of the hints was that sixth grader could do this? There’s never a sixth grader around when you need one though!
Gee, we thought our answer was more elegant! Even with 6th grade spelling of “they’re”!
Gee, we thought our answer was more elegant! Even with 6th grade spelling of “they’re”!
I did a little analysis on the possible solutions, and came up with this:
On running 10,000 trials using random selection order:
The Flip Twice solution (the “official” one, I guess”) took an average of 1128 visits.
The solution posted here (sending “noise” on Switch B) took an average of 716 visits! Apparently it’s more efficient, if not more elgant.
In the interest of curiosity, the solution where you have each prisoner flip it only once, with a possible error of off by 1 worked 10,000 out of 10,000 times, with an average of 579 visits. This works because the chance of 1 person not getting selected to visit over the amount of time it takes to send all these messages back and forth is slim.
And the simple solution of the first prisoner to be selected 20 times Declares worked all but 4 times (That’s 0.04 %) in only 302 visits. I’d take those odds. =)
If you want the Java source code to run these sims, drop me an email!
[comment removed by editor]
One possible solution could be for the prisoners to communicate via even or odd numbers (the positions of the switches can be interpreted as bits which could be in 4 positions – 00, 01, 10, 11 – which translate to 0,1,2,3 with 0 & 2 even and 1 & 3 odd).
However, since only two switches are available, only one person can keep the score. This has to be decided upfront when they meet.
The way it could work is the following
If you are the score keeper
turn the switch position from even to odd if it is even
leave the switch position to odd if it is already odd
If you are a non-score keeper
turn the switch position to even if this is your first visit when the switch position is already at odd
leave the switch position at even if it is already even
Please note that even if this is the first visit and the switch is already ON, there is still a need to indicate to the score keeper to increment the counter. So the rule to be discussed during the strategy session is the following
Only the score keeper can change the state from even to odd. If the switch is even, the score keeper will increment his counter by 1 (and turn the switch position to odd)
All the others can change the state from odd to even only if the position is odd and this is their first visist after the position is already odd. This is to differentiate between cases where multiple prisoners could all visit for the first time one after the other.
If this is not the first visit, the user will leave the position at odd itself.
Assuming a random distribution, after a certain number of visits, if the score keepers counter reads 22, that means that everyone including himself has visited at least once.
Donate!
I don’t see why the score keeper needs to subtract 1 on seeing the switch B in state OFF. It seems fine without this step.
Hall of Poker brings you the excitement of playing online poker games with real live people or play texas holdem for fun.
all these solutions are wrong, because how do u know that the scorekeeping is actually listening?
The very first solution(at the very top) is wrong because
1. B is Off originally, so the scorekeeper toggles A, when does the rest people actually know that the score keeper started listening? they never know cause they can never get the signal.
2nd solution is also wrong because.
let’s say it’s odd to start with, one of the prisoner turns it into even. The scorekeeper starts he doesn’t know whether the switches started even or someone turned it, but he will turn it into odd anyhow. He will always miss the count by one. And since everyone can only turn even once, he’ll get stuck at 22.
But if it’s even to start with, the scorekeeper can turn it to odd, and then he will have an accurate count. So this will only work if it’s even to start with.
check the solution here
http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/solutions/July2002.html
how to make 2nd solution work
you’re right – he will get stuck at 22 because we do not know the original position.
basically, the keeper needs to know when to start counting. Somehow, the keeper needs to know.
We really don’t need both switches. This is correct. I say the first person to come in turns B to “on”, signifying his presense, and proceeds to vandalize A. that way, the scorekeeper knows to start counting, and everyone else knows that the counting has begun.
– or, if that’s too harsh for you, let A be used by the scorekeeper to tell people to start, and B used by the people to tell the Keeper they’ve visited.
In order to make sure that the score keeper is listeneing, just make sure that you (non-scorekeeper) should watch switch A go from on to off and then off to on at least once. Since switch A is turned on only by the scorekeeper, you can be sure that Neo has started to keep the score…
Car Talk Puzzle Solution?
More info can be found on my page…
What if a scorekeeper was elected to switch the light AT THE BEGINNING of the game and that every prisoner including the scorekeeper, had only, say, 2 chances of switching the light? All the answers above are true if and only if the scorekeeper goes to the switch room more than twice and not only at the beginning of the game.
I agree. Score keeper doesn’t work because there is not defined order, or repetition period, or times a certain person would switch a switch. Because there are only four states, and no way of knowing whether you (prisoner) are the first in the room or not, the only way to “predict” that all 23 have switched the switch, is to use statistics and probability. That is right most of the time, but if your life is bet on the outcome…