Ask if he knows if one of Porthos or Aramis got at least two gold coins. If Athos got two of the three gold coins, he knows the answer is no. If Athos got no gold coins, then given that all three were given out he knows that the answer is yes. If Athos got one gold coin then he will not be sure.Of course, you can switch "gold" for "silver" in that solution if you like. Anyway, simple, like I said, but I sort of thought it was neat. I would love to hear any alternate solutions, I haven't thought of any but they probably exist.
Just One
OK, time for the solution to the coins puzzle from last time.
Not much derivation to do, so I'll just sort of post my solution:
Coins Again
Alright, new puzzle time. I have a bit of a backlog of decent puzzles, so its important for me to waste them as soon as possible so I go back to not blogging again.
I got this one off of Tanya Khovanova's math blog, well, sort of, I misread the puzzle and solved a variant, but I think the variant is better so I'm going with it:
Athos, Porthos, and Aramis were rewarded with six coins: three gold and three silver. Athos got two coins. Athos doesn’t know what coins the others got, but he knows his own coins and he knows all the coins were given out. Ask him one question to which he can answer “Yes,” “No,” or “I do not know,” so that you will be able to figure out his coins.My misread was that in the initial puzzle, instead of "Athos got two coins", it was "Each got two coins". My solution worked for both, and I somehow feel that my version is harder (being that you have less information), but its not clear that taking away information from Athos (which my variant also did) actually makes it harder. Anyway, yeah, its simple, solve it out.
One Way Or The Other
Solution time! Puzzle last time was that game about breaking chocolate.
I know of two ways to come about the solution, the one is easy and elegant (and was how I solved it initially), while the other is a bit more roundabout and uses a bunch of game theory that I think is sort of cool. Anyway, I'm going to do the long game theory version first, if you want to just read the elegant quick solution, skip to the second last paragraph.
First of all, I'm going to set up a bit about game theory of impartial games, games where both players always have the same options available to them (other games are called partizan, chess and go are partizan games with one player playing black and the other white, I cannot move your pawn). I will also be focused exclusively on the type of game where the players alternate turns in the usual way. It is clear that for any impartial game, in any position either the active player has a winning strategy or the inactive player does. As is standard, we will call the former kind of position an "N-position" (for next player wins) and the latter a "P-position" (for previous player wins). It is clear that from any position you always want to move to P-positions, when possible.
At this point will be looking just at games that use the "normal play" rule that is, if you have no moves available on your turn you lose the game (as opposed to the "misère play" rule where having no legal moves is a win). So the game state with no legal moves is a P-position. Generally speaking, if from a game state you can move to a P-position, then that game state must be an N-position (since P-position moves are winning moves, having a P move available means that the active player has a winning strategy). On the other hand, if all the legal moves from a game state are N-positions (including the specific case of no legal moves), then that game state must be a P-position. So if a player has used this to completely map out the game space (first by labeling the end state P then moving outward labeling things P or N) that player will always try to move to a P-position, the opponent will have to choice to move to an N-positon, from which a new move to a P-position is available, and eventually the game must end with the winning player being the one who can move the game into P-positions (the end state also being a P-position).
Next we must figure out how game types combine when you add them together as we do in the breaking chocolate game. Suppose we start the breaking chocolate gmae from a 5x6 position and we move to the 5x2 + 5x4 position, what does that "+" mean? It means that we can make a move in either game. So, if G and H are both games, then G+H is the game where you can legally move in either G or in H, you must move in one of them, but not in both. Convince yourself that this addition is associative, that is (G+H)+J is the same as G+(H+J), it is also commutative but that is trivial.
Now we can prove something, I claim that if G is a P-position and if H is a P-position, then G+H is also a P-position (yay, a theorem), the proof is to simply show the strategy. If G is a P-position, then the inactive player has a response to any move the active player can make, and the inactive player can guarantee that it is the active player will run out of moves first (note how much more difficult it is if we used misère play instead, the fact is normal play is much easier to analyise in most cases). All this is true about H as well, so by simply always responding to the opponents moves in G with moves in G and respond to moves in H with moves in H you can always get to another position of the form P+P. So, we see that:
Good good.
Next, I claim that if G is an N-position and H is a P-position then G+H is an N-position. To prove this I simply need to show that there is a legal move in G+H to a state that is a P-position. We know that there is a legal move in G to a game state K with K being a P-position, but then K+H is a P-position by the previous theorem. So we see that there is a legal move in G+H to a P-position, specifically the move from G to K. So, we have:
Actually, we can quite generally show that if H is a P-position, then for any game G, G+H=G because you can just use your strategy in G and always respond to opponent moves in H with moves in H.
Alright, it is natural to wonder about N+N next, unfortunately you can come up with situations in actual games where N+N can be P and other games where N+N can be N. You can show that any game plus itself is a P-position, because in G+G you can always answer your opponents move in one with the same move in ther other, so they will run out of moves first, so G+G is a P-position, but if G and H are both N-positions, but not the same N-position, you can't prove much.
Alright, now for the chocolate game, I will prove the following statement for some arbitrary AxB position (I would have used NxM, but N is being used for something else here, and that notation is more standard):
The proof will be by induction, we can see this are true if AxB is 1x1, now to prove it by indution suppose we have want to prove this statement for a particular AxB and we are going to assume it is true for all ixB (with i less than A) and all Axj (with j less than B).
Now, I must show that AxB can reach a P-position if either A or B are even, this is easy, just move to (A/2)xB+(A/2)xB or Ax(B/2)+Ax(B/2), whichever exists. Then you mirror the opponent from there and cannot run out of moves first, so AxB can reach a P-position, it must be an N-position. Now if A and B are both odd, a generic legal move is to RxB+SxB with R even and S odd. But then RxB is an N-position and SxB is a P-position by the induction assumption and we know that N+P=N, so any legal move leads to an N-position meaning AxB must have been a P-position.
This completes the proof of the theorem, so we know from any start position if it is a P-position or an N-position so we can clearly say who wins and how (and the typical winning move is to break even sides directly in half), now I will show that that is totally unneeded and if you are in a winning position you can just make random moves and you won't ruin it.
Consider, at the start of the game we have a single block of chocolate on the table (of size NxM), each move causes one break in an existing piece of chocolate, increasing the number of blocks of chocolate on the table by exactly 1. The game ends when there are NxM blocks of chocolate on the table, so exactly NxM-1 moves have gone by, no matter what people chose as their moves there were exactly NxM-1 moves in all cases. The first player wins if NxM is even as there will be an odd number of moves, and the second player wins if NxM is odd as there will be an even number of moves.
Anyway, game theory is cool, but this game is really trivial. The P and N-position things come up alot in other games though, for example the game where you are removing sticks from a pile of N sticks but you cannot remove more than 4 (or K) at a time. You can also be a bit more general and use the Sprague–Grundy theorem to make any impartial game under the normal play condition into nim, but that takes more work (though not much more).
I know of two ways to come about the solution, the one is easy and elegant (and was how I solved it initially), while the other is a bit more roundabout and uses a bunch of game theory that I think is sort of cool. Anyway, I'm going to do the long game theory version first, if you want to just read the elegant quick solution, skip to the second last paragraph.
First of all, I'm going to set up a bit about game theory of impartial games, games where both players always have the same options available to them (other games are called partizan, chess and go are partizan games with one player playing black and the other white, I cannot move your pawn). I will also be focused exclusively on the type of game where the players alternate turns in the usual way. It is clear that for any impartial game, in any position either the active player has a winning strategy or the inactive player does. As is standard, we will call the former kind of position an "N-position" (for next player wins) and the latter a "P-position" (for previous player wins). It is clear that from any position you always want to move to P-positions, when possible.
At this point will be looking just at games that use the "normal play" rule that is, if you have no moves available on your turn you lose the game (as opposed to the "misère play" rule where having no legal moves is a win). So the game state with no legal moves is a P-position. Generally speaking, if from a game state you can move to a P-position, then that game state must be an N-position (since P-position moves are winning moves, having a P move available means that the active player has a winning strategy). On the other hand, if all the legal moves from a game state are N-positions (including the specific case of no legal moves), then that game state must be a P-position. So if a player has used this to completely map out the game space (first by labeling the end state P then moving outward labeling things P or N) that player will always try to move to a P-position, the opponent will have to choice to move to an N-positon, from which a new move to a P-position is available, and eventually the game must end with the winning player being the one who can move the game into P-positions (the end state also being a P-position).
Next we must figure out how game types combine when you add them together as we do in the breaking chocolate game. Suppose we start the breaking chocolate gmae from a 5x6 position and we move to the 5x2 + 5x4 position, what does that "+" mean? It means that we can make a move in either game. So, if G and H are both games, then G+H is the game where you can legally move in either G or in H, you must move in one of them, but not in both. Convince yourself that this addition is associative, that is (G+H)+J is the same as G+(H+J), it is also commutative but that is trivial.
Now we can prove something, I claim that if G is a P-position and if H is a P-position, then G+H is also a P-position (yay, a theorem), the proof is to simply show the strategy. If G is a P-position, then the inactive player has a response to any move the active player can make, and the inactive player can guarantee that it is the active player will run out of moves first (note how much more difficult it is if we used misère play instead, the fact is normal play is much easier to analyise in most cases). All this is true about H as well, so by simply always responding to the opponents moves in G with moves in G and respond to moves in H with moves in H you can always get to another position of the form P+P. So, we see that:
P+P=P
Good good.
Next, I claim that if G is an N-position and H is a P-position then G+H is an N-position. To prove this I simply need to show that there is a legal move in G+H to a state that is a P-position. We know that there is a legal move in G to a game state K with K being a P-position, but then K+H is a P-position by the previous theorem. So we see that there is a legal move in G+H to a P-position, specifically the move from G to K. So, we have:
N+P=N
Actually, we can quite generally show that if H is a P-position, then for any game G, G+H=G because you can just use your strategy in G and always respond to opponent moves in H with moves in H.
Alright, it is natural to wonder about N+N next, unfortunately you can come up with situations in actual games where N+N can be P and other games where N+N can be N. You can show that any game plus itself is a P-position, because in G+G you can always answer your opponents move in one with the same move in ther other, so they will run out of moves first, so G+G is a P-position, but if G and H are both N-positions, but not the same N-position, you can't prove much.
Alright, now for the chocolate game, I will prove the following statement for some arbitrary AxB position (I would have used NxM, but N is being used for something else here, and that notation is more standard):
AxB is a P-position if both A and B are odd and is an N-position if either A or B is even
The proof will be by induction, we can see this are true if AxB is 1x1, now to prove it by indution suppose we have want to prove this statement for a particular AxB and we are going to assume it is true for all ixB (with i less than A) and all Axj (with j less than B).
Now, I must show that AxB can reach a P-position if either A or B are even, this is easy, just move to (A/2)xB+(A/2)xB or Ax(B/2)+Ax(B/2), whichever exists. Then you mirror the opponent from there and cannot run out of moves first, so AxB can reach a P-position, it must be an N-position. Now if A and B are both odd, a generic legal move is to RxB+SxB with R even and S odd. But then RxB is an N-position and SxB is a P-position by the induction assumption and we know that N+P=N, so any legal move leads to an N-position meaning AxB must have been a P-position.
This completes the proof of the theorem, so we know from any start position if it is a P-position or an N-position so we can clearly say who wins and how (and the typical winning move is to break even sides directly in half), now I will show that that is totally unneeded and if you are in a winning position you can just make random moves and you won't ruin it.
Consider, at the start of the game we have a single block of chocolate on the table (of size NxM), each move causes one break in an existing piece of chocolate, increasing the number of blocks of chocolate on the table by exactly 1. The game ends when there are NxM blocks of chocolate on the table, so exactly NxM-1 moves have gone by, no matter what people chose as their moves there were exactly NxM-1 moves in all cases. The first player wins if NxM is even as there will be an odd number of moves, and the second player wins if NxM is odd as there will be an even number of moves.
Anyway, game theory is cool, but this game is really trivial. The P and N-position things come up alot in other games though, for example the game where you are removing sticks from a pile of N sticks but you cannot remove more than 4 (or K) at a time. You can also be a bit more general and use the Sprague–Grundy theorem to make any impartial game under the normal play condition into nim, but that takes more work (though not much more).
Subscribe to:
Posts (Atom)
