Prisoners Dilemma

OK, one of these days I'm going to run out of puzzles. As it is, I think I am reaching the point where all my puzzles either are really simple or require the axiom of choice to solve. Anyway, this puzzle for this week is still a good one. I have learned this one many times in different incarnations, but this particular version was told to me by Bart:

There is a prison with 100 prisoners and a warden who likes to play bizzare games with them. In this particular game there is a room with two light switches in it. The light switches do not do anything, and can only be in the states up or down. Each day, the warden may select a prisoner and place them in the room. While in the room, the prisoner must flip exactly one of the switches and then is released from the room back to their cell. The prisoners are unable to leave any sort of messages in the room besides the positions of the light switches (the warden will always return the room the its initial state except for the switches).

On any day, any prisoner may declare "we have all been in the room at least once." If this declaration is made and is correct, the prisoners win and will all be released. If the declaration is made and incorrect, the prisoners lose and are killed.

It is promised that given enough time, each prisoner will enter the room arbitrarily many times. The prisoners may plan ahead of time, but then will never get to see eachother again until the game is over. Find a strategy that guarantees the prisoners victory.

Note that the prisoners do not know the initial configuration of the switches, and must always flip exactly one switch when they are in the room (you can make an easier version of this puzzle by modifying these facts). Also note that the warden does not have to place a prisoner in the room each day, so if you are in the room one day and in there again some days later, you do not know how many people have been in the room since. Finally, to make precise the statement that "given enough time, each prisoner will enter the room arbitrarily many times," I mean: For each prisoner P, for each integer N, there exists an integer K such that before day K prisoner P will have visited the room more than N times.

You may assume that the warden is an adversary, capable of meddling with any strategy to maximum effect (up to the rules of the problem). Also, do not worry about the finite lifetimes of the prisoners, that would just make this stupid, I suppose the prisoners are immortal or something.

Smashed Computers

Time to solve the broken computers problem. The solution isn't very hard to come by if you try to solve the lower N cases first. For N=1 and N=2, the problem is trivial (there aren't any broken computers), so the first real case is N=3. Label the computers A, B, and C:

Have computer A run a diagnostic on computer B. If it says B is working, then it is, if it says B is broken, then C is working.

This is simple enough, as if A says B is broken then either A or B is broken, if A says B is working then either B is working or both are broken. But we know there is only 1 broken computer.

Note that we do not need to worry about cases with even values of N since over half the computers are working, you can just throw one computer out the window and have one more diagnostic than you actually need without hurting your majority of working computers.

Anyway, our N=3 case gives us two hints for the main solution. One, if you have a chain of computers N₁ to N_k where each one says the next one is working (specifically N_i says N_i+1 is working) then either they are all broken or the final one is working. So, if k>N/2 they cannot all be broken and so N_k is working. Next, if you have a computer that says another computer is broken, at least one of them is broken so you can throw both out the window and not lose your majority of working computers.

So, thats basically the solution:

Create a chain of computers, at each stage have the computer at the end of the chain run a diagnostic on a new computer. If the new computer is said to be working, add it to the end of the chain. If it is said to be broken, discard it along with the computer that ran the diagnostic on it. If the chain is ever empty, select a new computer to start the chain. If the chain is ever longer than half the computers you have left, the computer at the end is working.

You basically can prove by induction that this will work for N computers. The worst case with throwing computers away is that you lose a step in the chain so you actually spend two diagnostics. However, you got rid of two computers, so you have simply reduced to the case N-2 and have N-4 diagnostics. Since the solution works in the base case of N=3, it works all the way up odd values of N.

Broken Computers

OK, seems like my chain of counterfeit coin puzzles has come to an end. New puzzle time, I first learned this one on the forums at xkcd:

You have N computers, some of which are broken and some are not, and you do not know which ones are broken. You may have any computer run a diagnostic on any other computer to find out if it is working. If the computer running the diagnostic is working it will tell you correctly if the second computer is working. If the computer running the diagnostic is broken, it will give you a random answer.
It is guaranteed that over half the computers are working, find a strategy that is guaranteed to locate a working computer using no more than N-2 diagnostics.

By "it will give you a random answer", I mean that it will say 'this computer is working' or 'this computer is broken' each with 1/2 probability. It is worth nothing that strictly more than half the computers are working, so if there are 10 computers it is guaranteed that at least 6 are working.

Yep, Counterfeit Masses

So, its time for the solution to the final counterfeit masses problem. First, its worth nothing that the statement in the problem that you must determine if the counterfeit coin is heavy or light is irrelevant. Every coin in the collection must at some point step on the scale (as the counterfeit might not even be present at all), and since by the end you will know which coin was counterfeit and it was on the scale at some point, you know if it is heavy or light. Next, note that the "possible existence" of the counterfeit coin is essentially meaningless, as you can treat a problem with N coins and a guaranteed counterfeit equivalent to a problem with N-1 coins with a possible counterfeit by throwing one coin out the window. All that crap is really just to make the problem sound harder.

So we really only need to worry about having 41 coins with a guaranteed counterfeit and a 1 coin reserve and 4 weighings at our disposal. You will recall that with 4 weighings and an infinite reserve we could only do 41 coins at best, so apparently a 1 coin reserve is as strong as an infinite one.

One trick that makes this problem easy is just to always proceed as if it actually has a solution. We know that we will begin by weighing N coins against N-1 other coins plus the reserve coin (we might as well use the thing), and leave the other 41-(2N-1) coins to the side. But, if the N vs. N measurement comes out equal, we will have a "large" reserve and have to solve the problem with 42-2N coins with only 3 measurements. We know that at most then, 42-2N can be equal to 14, so N=14 (or more, but why make our lives harder). So, we have step one:

1. Weigh 14 coins against 13 coins plus the reserve coin.

If this comes out balanced, we know what to do. So, lets assume the 14 come out heavy (if they are light, just switch the notion of light and heavy), so we have 14 possibly heavy coins and 13 possibly light coins. Now, we have a reserve of 15 coins (the exact size is meaningless actually, we only need about 10 of them as we will see), and we will set aside M of our "heavy" coins and perform some measurement on the others. If that measurement comes out balanced, we will have 2 measurements left and M heavy coins, so we know that we should set M=9 at most, or we can't win if the next measurement is balanced. So, lets do that:

2. Weigh the 5 of the possibly heavy coins with 9 possibly light against the other 4 possibly light and 10 reserve, the other 9 possibly heavy coins are set aside.

If this comes out balanced, we can solve the remaining problem easily. If the 5 heavy and 9 light come out light, it must be the 9 light causing it (no heavy coins on the other side). If the 5 heavy and 9 light come out heavy, we now have 5 possibly heavy coins and 4 possibly light coins with a large reserve and 2 measurements left. Set 3 heavy aside (as if the next measurement is balanced, we can solve them with our 1 remaining measurement), and

3. Weigh 3 possibly light coins with 2 possibly heavy coins against 1 possibly light coin and 4 reserve coins, the other 3 possibly heavy coins are set aside.

If this is balanced, we know what to do. If the 3 light and 2 heavy come out light, then the 3 light caused it (no heavy on the other side). If the 3 light and 2 heavy come out heavy then we are down to 2 heavy and 1 light with one measurement left. This is easy enough:

4. Weigh one possibly light and one possibly heavy against 2 reserve coins, with the other possibly heavy coin set aside.

The cases of "balanced", "heavy", and "light" each now point to a unique coin.

It is easy to use this method to solve the (3^N+1)/2 coin case with N measurements and 1 reserve coin. So it is true that any nonzero reserve handed to you at the start is of equal strength. The technique of solving the problem by assuming the solution exists can actually get you pretty far in logic puzzles, in a few cases you can actually find a solution to a problem and not be able to prove that there actually is a solution. It works for logic puzzles because there typically is a solution, but I suppose mathematical research demands a bit of a higher level of rigor.