![]() ![]() Bearing this in mind, it is enough for us to describe how the second prisoner can answer this question for each of the three patterns independently. Moreover if he knew the answer to this question not only for the first of these patterns but for all three patterns then he would know the exact column of the magic square. Now suppose the second prisoner knew whether the magic square was one of the 'X' squares or one of the 'o' squares in the first of these patterns, then he would have narrowed down the column of the magic square to either the left or the right hand side of the board. O o o o X X X X o o X X o o X X o X o X o X o X For this, consider the following three chessboards patterns with the squares marked 'o' or 'X': Not surprisingly the rules for calculating the row index are the same as those for calculating the column index except that everything is just turned sideways so we will content ourselves with a description of how to calculate the column index. He calculates the row and column index independently. ![]() The input for the second player's algorithm is the configuration of coins he sees on the chess board. It is convenient to begin by describing the second player's algorithm. In the case of the first prisoner these indices identify the coin he must turn over, in the case of the second prisoner these indices identify the magic square which he will announce to the jailer. The output of each player's algorithm is the row and column index of a square on the chess board. A strategy consists of a pair of algorithms: one algorithm for the first player and one algorithm for the second player. The prisoners can guarantee their freedom. Obviously I recommend thinking a bit about the puzzle before diving down to the solution but it's up to you, reader. Explicit realisations of particular generalisations.Different points of view on the winning strategy.How to figure out this winning strategy.An elementary winning strategy (without any discussion of its correctness).However after thinking about it for long enough, I eventually found a winning strategy. ![]() When I was first asked this puzzle I thought it was probably impossible for the prisoners to guarantee their freedom and rather rashly declared this to be the case (the person who asked me the puzzle did not know whether or not there was a solution). Of course the question is: what strategy should the prisoners adopt? These rules are explained to both prisoners before the game begins and they are allowed some time together to discuss their strategy. If he is able to do this, both prisoners will be granted their freedom (if not, the poor prisoners will be forced to take up employment at Lee Overlay Partners - a fate that few would relish). The jailer will ask him to identify the magic square. After the first prisoner has left the room, the second prisoner is admitted. The first prisoner must then turn over exactly one of the coins and exit the room. Having done this he will then choose one square of the chess board and declare to the first prisoner that this is the "magic" square. Inside the room the jailer will place exactly one coin on each square of the chess board, choosing to show heads or tails as he sees fit (e.g. The jailer will take one of the prisoners (let us call him the "first" prisoner) with him into the aforementioned room, leaving the second prisoner outside. Two prisoners are at the mercy of a typically eccentric jailer who has decided to play a game with them for their freedom. Shortly after I started working at SIG, somebody at work asked me the following puzzle.Ī room contains a normal 8x8 chess board together with 64 identical coins, each with one "heads" side and one "tails" side. Yet another prisoner puzzle Yet another prisoner puzzle ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |