Take- Away game 1
Logic
Level
4
Here are the rules of a very simple game of removing chips from a pile of chips.
- There are two players. We label them I and II.
- There is a pile of 186 chips in the center of a table.
- A move consists of removing one, two, or three chips from the pile. At least one chip must be removed, but no more than three may be removed.
- Players alternate moves with Player I starting.
- The player that removes the last chip wins. (The last player to move wins. If you can’t move, you lose.)
If you were player I what is the least number of moves it will take you to win the game?
Assume the two players are extremely intelligent and don't play with luck.
The answer is 47.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
If player I has a strategy for winning the game this means that he has at least one way of playing such that for any moves the second player will make he will make the other player lose which means that in order to understand how such a strategy would look like when thinking (or conceiving) a winning strategy prior to this it should be understood when does a player certainly lose. For a player to be certain that he loses observe that he must be given a number of chips such that no matter how many chips he chooses to take the other player will win in the next move which can only happen if the player that loses receives a number of chips such that for any available number of chips he can take (say k) he gives to the other player a number of chips he can take in just one move. This can only happen if for the smallest number of chips player II will take he gives a number of chips player I can take in one move and for the biggest number of chips he can take player II can't win meaning that that number that a player should receive such that he loses the game should be in his last move of k+1 which respects both conditions stated. Now observe further that if the number of chips player II should receive such that he loses the game is k+1 or in the case of the problem of 4 chips then this can be generalized for each step of the game meaning in order to make player II to receive 4 chips player I should give 8 chips to player II such that he is certain will give him 4 and so on. This means that at each step of the game a player , supposing the players are "extremely intelligent" and therefore play optimally not losing the opportunity to win the game , will be in a losing position if he receives a number of chips which is a multiple of 4 because for any of his move he will arrive at the final losing position. Considering this is known by both players and that player I being the first can decide whether player II is in a losing position or not it means that he has a winning strategy and also that this is the only possible strategy because if player I will choose not to give player II a losing number of chips player II will have if he plays optimally a winning strategy. In other words player I is forced to put player II in a losing position if he wants to be assured that wins. As this is the only optimal strategy and there are no more other strategies such that the number of moves necessary for winning the game could be varied for a strategy player I will take the minimal number of moves is dependent on the number of moves of this first and only strategy. Calculating for the number of 186 chips this number will be of 46.5 which means that since the number of moves must be an integer the minimum number is of 47 moves.