Man, I meant to blog one more time before the go congress, but blogging is so hard. Anyway, solution time. Puzzle from last time was another hat one. The solution is rather similar to puzzles I have posted here before, but it still took me a little while to get it.
As always, it is easier to start with the two person, two colour case. Suppose the two colours are white and black, and we have two rooms. Label the two rooms white and black and go into the room that corresponds to the hat colour of the other person. If you both have the same colour, you will go to the same room, but if you have different hat colours you will go to different rooms.
Naturally, a strategy for the more general case must just be a function that maps from the hats you see to the room you go to. Lets try two hat colours and N people next.
We have two rooms again, call one room even and one odd. If you see an odd number of black hats, go to the odd room, if you see an even number of black hats, go to the even room. Then, if the total number of black hats is even, white-hatted people will go to the even room and black-hatted people will go to the odd room. Naturally it works the other way if the total number of black hats is odd. One could also arrive at this strategy by assigning the rooms numbers 0 and 1 and call white 0 and black 1. Then add the hat colours you see mod 2 and go to that room.
This generalizes to the strategy for N people and K colours. First number the hat colours 0 through K-1 and number the rooms 0 through K-1. Then add the hats colours you see together mod K and go to that room. We can see this strategy works by considering the sum of all the hats (call that S), then a person with hat colour x will go to the room S-x mod K. If two people with hat colours x and y go to the same room, then S-x=S-y mod K and so x=y mod K and so x=y, two people go to the same room means they have the same hat colour, so this solution works.
Generalizing this to the case of countably infinite hat colours is trivial, you can just use the same solution and forget the mod K stuff. Each hat is a natural number, and add together the hats you see and go to that room.
With infinite logicians it is a bit more tricky. In this case there are infinitely many of them to add together, so you can't just go to the 'infinity room' and be done with it. Since we have been handed the Axiom of Choice, we might as well make use of it.
What can one do with the Axiom of Choice? In most cases, the most efficient thing to do is the same old equivalence class thing. Let us construct an equivalence class of hat sequences. Two sequences are said to be the same if they differ in only finitely many places. Now we can use the axiom of choice to construct a set S which contains exactly one element from each equivalence class. Since each logician can see all but their own hat, they can all determine what equivalence class we are in, and thus can select an element x in S that differs from the real sequence of hats in finitely many places. We will add together those finitely many hats to construct our solution.
Alright, so everybody sees most of the full sequence of hats yi and they all have agreed on a sequence xi that differs from the sequence yi in finitely many places, they must now choose a room to go to. Let us suppose that all the hats are correct. Then it is simple, you just go to the room that xi says you go and it will all work (the hats and the rooms have both been numbered as naturals). Now, let us suppose that person j is wearing the wrong hat colour, that is xj ≠ yj but all the other xi=yi. Now he is going to go to the room suggested by the hat xj, which is xj-yj too many, so everybody else must also go xj-yj too many also. It is possible for this number to be negative, so first we must number the rooms as integers instead of naturals. So, the strategy is that when you are person n and you see hat j wrong, you go to room xn+xj-yj. Naturally, if you see more than one wrong hat, just add up xi-yi of all the hats that are wrong (there are only finitely many) and add that to your own xn and go to that room.
Tanya Khovanova has a complaint with this solution that even though the Axiom of Choice allows you to select the set S that we will use for the solution, it does not guarantee that there is a method of distributing the set S to a collection of people. If they cannot distribute the set S, they cannot guarantee that they all have the same one (and I would suppose they almost certainly do not, but that is a bit of an odd statement to make). I am not sure if I agree with her on this point, but I generally am against the Axiom of Choice in the first place, so it is a bit of a non-issue for me. At any rate, I suppose one could distinguish another axiom where you have the Axiom of Choice, and you may actually describe the set it gives you, then this puzzle simply needs that more powerful axiom, to solve.
Hats Again
Time for new puzzles that Mark told me but he actually got from Tanya Khovanova's math blog:
You can assume that the logicians know what colours are available. If you like, you can also generalize to N logicians and K hat colours, its not much harder. What is harder is allowing N and K to be infinite, you will need the axiom of choice in this case, but its also an interesting puzzle.
1000 logicians are going to play a game against The Adversary. The Adversary has a collection of hats that come in 6 different colours. There are also 6 rooms. The Adversary is going to gather all the logicians together and put a hat on each of their heads, and then the logicians must simultaneously decide what room they are going to enter. After the logicians have each gone to their chosen rooms, each room must have logicians with only one colour of hat. The logicians may strategize before the hats are assigned, find a strategy that guarantees that each room will have a unique hat colour in it. Standard hat rules apply, of course.
You can assume that the logicians know what colours are available. If you like, you can also generalize to N logicians and K hat colours, its not much harder. What is harder is allowing N and K to be infinite, you will need the axiom of choice in this case, but its also an interesting puzzle.
Flip A Coin
About time for the solution to the lowest number game from last time. I tried solving out the harder version myself, but I didn't manage to get anywhere, more about that later.
Before I construct the strategy, I want to point out a somewhat neat theorem about the game and discuss an incorrect strategy. One idea is just to pick 1 with probability 1/2 and 2 with probability 1/2, since this is a zero sum game, every wins zero on average if they all do the same thing. Seems like a reasonable idea, but you can beat this by always picking 3. There is a 50% chance that the other players will pick the same number as eachother and you just win, the rest of the time, they pick different numbers and you lose. Thus your average winnings are 0.5x$2-0.5x$1, which is more than zero. This hints at an interesting idea, there is no number that is the largest number players can pick in a symmetric equilibrium. Suppose each player has a strategy S which is a series of probabilities P(n) for picking number n. Suppose there is a largest number K that S suggest you will ever pick (that is, P(n)=0 for n>K). Now, you generate your random number, and it says you should play K. I say you should play K+1. If K was going to win, so will K+1 (it would only win if the opponents were about to pick the same number). But it is possible K+1 will win and K will not (specifically if both other opponents pick K). Thus it is advantageous for you to change strategy S into a slightly different strategy, and so it is not an equilibrium.
Alright, to find the actual solution, let us assume that we are going to search for a symmetric Nash equilibrium. I think there is a theorem that symmetric games always have at least one symmetric equilibrium, but I cannot find any such theorem online. Anyway, we must find a list of P(n) that is the chance a player picks n, and we know there is no K such that P(n)=0 for n>K (that doesn't actually help us, but I think its neat).
OK, suppose we had P(n), what properties would it have? First of all, no player would do any better by deviating from the strategy. Let us also assume that they will do no worse (so we get equalities instead of inequalities). Second, we know that when everybody plays P(n) they have expected winnings of zero (just by symmetry and it being a zero sum game).
Suppose 2 of the players are playing the strategy suggested by P(n) and the third player decides to write down 1. What are his expected winnings? They are:
That is, he wins $2 if both opponents do not pick 1, and he loses $1 if one picks 1 while the other does not and this can happen two ways. In other cases he wins nothing and loses nothing. Setting this to zero (player 3 does no worse to unilaterally change his strategy), we see that P(1)=1/2.
What happens if he instead changes his strategy to just write down 2? His expected winnings are now given by
That is, he wins $2 if both opponents pick 1 or if they both pick numbers larger than 2. He loses $1 if one opponent picks 1 and the other does not (can happen in two ways) and he loses $1 if one opponent picks 2 and the other picks larger than 2 (can happen 2 ways). Setting this to zero and solving for P(2) we get P(2)=1/4.
This suggests P(n)=1/2n is the solution we are looking for. This can be confirmed by looking at what happens if the third player writes down A. His winnings are
Σn to A means sum n from 1 to A. These terms can be explained the same as the A=2 case as before. Subbing in P(n)=1/2n we find that this equals zero for all A and so this strategy is a Nash equilibrium.
Actually, this strategy is quite easy to perform in real life, you simply flip a coin until it comes up heads and write down the number of flips it took, this gives the correct P(n).
For the case where ties result in everybody losing their dollar, the game is more difficult, since it is no longer zero sum, there is a chance of money exiting the system. You can try something similar where your expected winning each round is the sum of P(n)3 (which is a third of the total amount of money lost each round, on average), but then you cannot iteratively solve for each P(n) as we did, you just have infinitely many coupled equations.
The 4 player game (with friendly ties) also has this problem, since a player playing 1 wins if nobody else picked 1, but also does not lose if the other two players pick the same number, so the sum over P(n)2 shows up in your first equation. The 4 player game also has annoying Nash equilibria like two players pick 1 and the other two pick 2.
Anyway, enough about that game.
Before I construct the strategy, I want to point out a somewhat neat theorem about the game and discuss an incorrect strategy. One idea is just to pick 1 with probability 1/2 and 2 with probability 1/2, since this is a zero sum game, every wins zero on average if they all do the same thing. Seems like a reasonable idea, but you can beat this by always picking 3. There is a 50% chance that the other players will pick the same number as eachother and you just win, the rest of the time, they pick different numbers and you lose. Thus your average winnings are 0.5x$2-0.5x$1, which is more than zero. This hints at an interesting idea, there is no number that is the largest number players can pick in a symmetric equilibrium. Suppose each player has a strategy S which is a series of probabilities P(n) for picking number n. Suppose there is a largest number K that S suggest you will ever pick (that is, P(n)=0 for n>K). Now, you generate your random number, and it says you should play K. I say you should play K+1. If K was going to win, so will K+1 (it would only win if the opponents were about to pick the same number). But it is possible K+1 will win and K will not (specifically if both other opponents pick K). Thus it is advantageous for you to change strategy S into a slightly different strategy, and so it is not an equilibrium.
Alright, to find the actual solution, let us assume that we are going to search for a symmetric Nash equilibrium. I think there is a theorem that symmetric games always have at least one symmetric equilibrium, but I cannot find any such theorem online. Anyway, we must find a list of P(n) that is the chance a player picks n, and we know there is no K such that P(n)=0 for n>K (that doesn't actually help us, but I think its neat).
OK, suppose we had P(n), what properties would it have? First of all, no player would do any better by deviating from the strategy. Let us also assume that they will do no worse (so we get equalities instead of inequalities). Second, we know that when everybody plays P(n) they have expected winnings of zero (just by symmetry and it being a zero sum game).
Suppose 2 of the players are playing the strategy suggested by P(n) and the third player decides to write down 1. What are his expected winnings? They are:
2(1-P(1))2-P(1)(1-P(1))-P(1)(1-P(1))
That is, he wins $2 if both opponents do not pick 1, and he loses $1 if one picks 1 while the other does not and this can happen two ways. In other cases he wins nothing and loses nothing. Setting this to zero (player 3 does no worse to unilaterally change his strategy), we see that P(1)=1/2.
What happens if he instead changes his strategy to just write down 2? His expected winnings are now given by
2P(1)2+2(1-P(1)-P(2)2)-2P(1)(1-P(1))-2P(2)(1-P(1)-P(2))
That is, he wins $2 if both opponents pick 1 or if they both pick numbers larger than 2. He loses $1 if one opponent picks 1 and the other does not (can happen in two ways) and he loses $1 if one opponent picks 2 and the other picks larger than 2 (can happen 2 ways). Setting this to zero and solving for P(2) we get P(2)=1/4.
This suggests P(n)=1/2n is the solution we are looking for. This can be confirmed by looking at what happens if the third player writes down A. His winnings are
2Σn to A-1 P(n)2+2(1-Σn to AP(n))2-2Σn to A P(n)(1-Σj to nP(j))
Σn to A means sum n from 1 to A. These terms can be explained the same as the A=2 case as before. Subbing in P(n)=1/2n we find that this equals zero for all A and so this strategy is a Nash equilibrium.
Actually, this strategy is quite easy to perform in real life, you simply flip a coin until it comes up heads and write down the number of flips it took, this gives the correct P(n).
For the case where ties result in everybody losing their dollar, the game is more difficult, since it is no longer zero sum, there is a chance of money exiting the system. You can try something similar where your expected winning each round is the sum of P(n)3 (which is a third of the total amount of money lost each round, on average), but then you cannot iteratively solve for each P(n) as we did, you just have infinitely many coupled equations.
The 4 player game (with friendly ties) also has this problem, since a player playing 1 wins if nobody else picked 1, but also does not lose if the other two players pick the same number, so the sum over P(n)2 shows up in your first equation. The 4 player game also has annoying Nash equilibria like two players pick 1 and the other two pick 2.
Anyway, enough about that game.
Lowest Number Game
So, most of the puzzles Mark has been feeding me lately have actually come from a single website, rather than from his crazy new hypothetical officemates. For 'credit where credit is due' purposes, I will direct your attention to Tanya Khovanova’s Math Blog, which still has a few more puzzles on it that I am going to put up here, but that can wait. First, a game that I learned about some time ago, but never knew before that it had such an interesting analysis:
This is a fairly standard game, and some people actually play it with large groups, it works out pretty well. The 3 player game is quite solvable though, and has a fairly cool solution. I suppose you could also change ties to "everybody loses their $1" and see what change it makes, I haven't done that yet. I guess there might be multiple equilibria in the strategy space, so the puzzle is to find any of them.
Three people each put $1 on the table. They then each simultaneously write down a positive integer. The integers chosen are then revealed and whoever wrote down the lowest unique one wins the $3. If everybody wrote down the same integer, then they each get their $1 back. Find the equlibrium strategy for this game.
This is a fairly standard game, and some people actually play it with large groups, it works out pretty well. The 3 player game is quite solvable though, and has a fairly cool solution. I suppose you could also change ties to "everybody loses their $1" and see what change it makes, I haven't done that yet. I guess there might be multiple equilibria in the strategy space, so the puzzle is to find any of them.
Two At Most
Time to post the solution to the follow-up coin problem from last time. The solution isn't hard to come by, and is basically an extension of the first move of the solution from last time. Last time the first measurement was the 1,2,3 against the 6 and since they balanced, you knew for a fact that the 6 was in fact the 6 (it is the only single coin that can weigh as much as three others). This time you weigh the 1,2,3,4,5 against the 7,8. They will come out balanced, but there is no way the left side weighs less than 15 and no way the right side weighs more than 15, so they must each be exactly those weights. This leaves the 6 uniquely identified.
Actually, this question has an interesting generalization, if we have N coins with masses 1 through N and we know their masses, how many measurements of a balance scale does it take to prove the mass of one of the coins? It is easy to prove that you can always do it in three or fewer measurements as follows: N can be written as a sum of 3 triangle numbers (this is a result of the Fermat polygonal number theorem, though for triangle numbers it was initially shown by Gauss). Call these numbers A, B, and C, assume that A ≥ B ≥ C. Weigh 1,2,3,4...k against A such that they balance (we know such a k exists, A is triangular), the balancing proves that the weights on the right has a mass at least A. Next weight 1,2,3,4,...m and A against (B+A), (B+A) being the single mass of mass B+A, and m is defined by 1+2+3+4+...+m=B. When they balance it proves that B+A is at least B+A. Finally weigh the 1,2,3,...j and (B+A) against N, where j is defined by 1+2+3+4+..+j=C. When they balance it proves that N is at least N. But N is at most N, so N is identified.
Actually, two weighings is always sufficient to prove that you can find one mass, this was proven in a paper entitled Baron Munchhausen’s Sequence, which also contains the proof from the previous paragraph. The proof is rather long though, and there is little sense in reproducing it here.
Actually, this question has an interesting generalization, if we have N coins with masses 1 through N and we know their masses, how many measurements of a balance scale does it take to prove the mass of one of the coins? It is easy to prove that you can always do it in three or fewer measurements as follows: N can be written as a sum of 3 triangle numbers (this is a result of the Fermat polygonal number theorem, though for triangle numbers it was initially shown by Gauss). Call these numbers A, B, and C, assume that A ≥ B ≥ C. Weigh 1,2,3,4...k against A such that they balance (we know such a k exists, A is triangular), the balancing proves that the weights on the right has a mass at least A. Next weight 1,2,3,4,...m and A against (B+A), (B+A) being the single mass of mass B+A, and m is defined by 1+2+3+4+...+m=B. When they balance it proves that B+A is at least B+A. Finally weigh the 1,2,3,...j and (B+A) against N, where j is defined by 1+2+3+4+..+j=C. When they balance it proves that N is at least N. But N is at most N, so N is identified.
Actually, two weighings is always sufficient to prove that you can find one mass, this was proven in a paper entitled Baron Munchhausen’s Sequence, which also contains the proof from the previous paragraph. The proof is rather long though, and there is little sense in reproducing it here.
Probably Correct
Alright, Canada day seems like a good time to post the solution for the labeled masses problem. Working on it yourself you probably found it is best to assume that the coins are labeled correctly and attempt to prove that rather than something else. Any method that would actually prove the coins are labeled correctly would also show that they are labeled incorrectly if they are not (if it didn't do that, one would hardly accept that it proves they are labeled correctly). Actually, this gives us something of a rewording of the problem, which I will later transform into the followup problem. Assume the coins are unlabeled, but you know which coin is which, you must prove to an audience (of mathematical puzzle solvers) that you know which coin is which using only 2 measurings.
Anyway, moving on to the solution (to the problem as initial worded). Its tricky to do anything involving weighing 1 coin against 2 right away, since if you weigh 1+2 against 3, even if it balances you cannot be sure that it was not the 1+3 against 4 or the 2+4 against the 6 or something. You could also try having 4 coins on one side, but that cannot work since on the second measurement you must split up those 4 coins or you cannot tell them apart. Perhaps something involving 2 vs. 2 works, but I didn't find anything. The thing that does work is to weigh the 1+2+3 against the 6. If it is imbalanced, we are done, if it is balanced then you have identified the 6 (it is the only one that can have as much mass as 3 others combined) and you have identified a group that is the {1,2,3}, since they are the only 3 light enough that a single coin could balance them.
So, in one measurement we have identified the {1,2,3}, the {4,5} and the {6}. The next measurement is to do the 6 and the 1 against the 5 and the 3.
If they are labeled correctly, the 5+3 should be heavier than the 6+1 (so, if that doesn't happen we are done). Since the 6 is identified, and the 1 must weight at least 1, the 6+1 must weigh at least 7, but since the 5+3 came out heavier, the 5 could not be any lighter and neither could the 3, so the 5 and 3 are correct. By a similar logic, the 5+3 cannot together weight more than 8, so the 1 cannot afford to be any heavier if the 6+1 is to be less than 8, thus the 1 must be the 1. That leaves the 2 and 4 both uniquely identified.
This completes the solution. I cannot prove that there aren't any other solutions, but I greatly doubt their existence.
Next, the follow-up:
You may assume that the audience knows that the coins have masses 1 through 8, but they do not know which one is which. After one measurement, the mathemagician must be able to select a single coin and say "I have now proven this one is the x" for some value of x. You may also assume the audience is a bunch of mathematicians, they will not be tricked by some sort of lies.
Anyway, moving on to the solution (to the problem as initial worded). Its tricky to do anything involving weighing 1 coin against 2 right away, since if you weigh 1+2 against 3, even if it balances you cannot be sure that it was not the 1+3 against 4 or the 2+4 against the 6 or something. You could also try having 4 coins on one side, but that cannot work since on the second measurement you must split up those 4 coins or you cannot tell them apart. Perhaps something involving 2 vs. 2 works, but I didn't find anything. The thing that does work is to weigh the 1+2+3 against the 6. If it is imbalanced, we are done, if it is balanced then you have identified the 6 (it is the only one that can have as much mass as 3 others combined) and you have identified a group that is the {1,2,3}, since they are the only 3 light enough that a single coin could balance them.
So, in one measurement we have identified the {1,2,3}, the {4,5} and the {6}. The next measurement is to do the 6 and the 1 against the 5 and the 3.
If they are labeled correctly, the 5+3 should be heavier than the 6+1 (so, if that doesn't happen we are done). Since the 6 is identified, and the 1 must weight at least 1, the 6+1 must weigh at least 7, but since the 5+3 came out heavier, the 5 could not be any lighter and neither could the 3, so the 5 and 3 are correct. By a similar logic, the 5+3 cannot together weight more than 8, so the 1 cannot afford to be any heavier if the 6+1 is to be less than 8, thus the 1 must be the 1. That leaves the 2 and 4 both uniquely identified.
This completes the solution. I cannot prove that there aren't any other solutions, but I greatly doubt their existence.
Next, the follow-up:
A mathemagician has 8 coins, with masses 1 through 8, he knows which coin is which. He intends to prove to an audience that he knows the correct mass of at least one of the coins using a single measurement of a balance scale. What measurement can he perform to prove the mass of any one of the coins?
You may assume that the audience knows that the coins have masses 1 through 8, but they do not know which one is which. After one measurement, the mathemagician must be able to select a single coin and say "I have now proven this one is the x" for some value of x. You may also assume the audience is a bunch of mathematicians, they will not be tricked by some sort of lies.
Subscribe to:
Posts (Atom)
