21
$\begingroup$

Here is puzzle that was lifted from an old essay of mine, that was adapted from a puzzle in an old puzzle book.

The great shah has invited a young boy into his palace as a student. While he is not busy managing his kingdom, he is a scholar of mathematics and invites the brightest learners from all over the country to his palace to study.

He sits the boy down at a small table, on which is a bag of stones. He then gently pours out the stones and lays them out in rows on the table.

"Here are 42 stones, my son," he tells the boy. "We will play a game with them. First, I will take one, three, or five stones from the pile. Then you will do the same, choosing between one, three, or five stones. We will continue until all the stones are gone. And neither of us may take more stones than there are remaining in the pile. The winner of the game will be the person who takes the last stone."

The boy nods silently at the shah, and turns back to looking at the pile of stones.

The shah starts by taking three stones. "We shall play seven games. If you win exactly six out of seven games against me, my student, you will have a place in my study."

The boy nods again, and looks hard at the stones. Suddenly, a look on his face changes as he realizes that he has a winning strategy.

  1. What is the boy's strategy to win the first six games?

The next part of the story was written in the essay after the first question had already been answered; try to answer the first question before looking at the problem statement of the second.

The boy easily wins all six of the first six games following his strategy. As they prepare for the seventh game, the shah tells the boy, "I can already tell you, boy, that you will win all seven of these games here, not six."

Surely enough, the shah starts by taking one stone, and the boy plays wildly, trying his hardest not to follow his winning strategy from earlier. But no matter how he plays, he cannot find a way to lose this last game and earn his place in the shah's study. As he removes the last stone from the pile, he hangs his head in shame.

The shah looks pitifully at the boy. "Poor child," he says. "If you can tell me why you could not lose this seventh game, you will still have a place in my study."

The boy thinks long and hard again, and suddenly his face lights up again as he turns to the shah and explains why he could not lose the game.

  1. Could the boy have lost the seventh game? Why or why not?
Improve this question
$\endgroup$
4
  • $\begingroup$ possible duplicate of 20 coins on the table $\endgroup$
    – warspyking
    Nov 19, 2014 at 17:25
  • 1
    $\begingroup$ The first part is a duplicate, but the second part is unique to this problem. $\endgroup$
    – user88
    Nov 19, 2014 at 19:00
  • 1
    $\begingroup$ So the boy, on his first move in the seventh game should take 40 stones. When told that is against the rules, he replies, "I guess you're right. I forfeit." $\endgroup$
    – user3294068
    May 30, 2019 at 15:25
  • $\begingroup$ @user3294068 You are more wise than either me or the boy. $\endgroup$
    – user88
    May 31, 2019 at 12:56

4 Answers 4

Reset to default
15
$\begingroup$

Regardless of what one player takes, the other can adjust accordingly so that 6 in total are removed. (1+5, 3+3, 5+1). So as long as the number of remaining stones before the shah's turn is dividable by 6, the student can force a win.

The 'trick' lies in the first turn. Given 42 is a multiple of 6, no matter what opening move the shah makes, he can make the numbers 'work' to a multiple of 6 remaining after his turn.

Now, why can he not lose on the 7th game?

Simple, the game starts with an even number of 42, and the shah always gets to play after an even number of turns. Given that two odd numbers have been subtracted from the pile, the remaining number has to be even. So when there are 0 stones left in the pile, it's the shah's turn, and it was the boy who removed the last stone.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ If you remove the body of the second section and the title of the third section, the explanation is still valid without editing a single word in the body of the third section. $\endgroup$
    – user88
    Nov 7, 2014 at 8:38
  • 2
    $\begingroup$ Joe, you are right. However, I didn't edit this answer as the - in hindsight obvious - key being the 'two odd numers removed is an even number, therefor only student can win' was presented in the answer by Jan Dvorak. I'm not one to try and take credit for others peoples insights. $\endgroup$
    – Tim Couwelier
    Nov 7, 2014 at 9:46
  • 2
    $\begingroup$ I would not say "the key number in this puzzle is '6'". Since any strategy would be a winning one for the boy there can not be any keys to win. Though I figured out the same strategy I don't like this part of this answer because it will mislead people. $\endgroup$
    – klm123
    Nov 7, 2014 at 10:27
  • 1
    $\begingroup$ klm, I think you have a point. Edited out that first line. $\endgroup$
    – Tim Couwelier
    Nov 7, 2014 at 11:04
62
$\begingroup$

That's easy

Since the game starts with an even number of stones and all possible moves remove an odd number of stones, there must be an even number of moves. The shah always moves first, which means that the student always moves last. The student wins no matter what strategy either player chooses.

Improve this answer
$\endgroup$
16
  • 2
    $\begingroup$ The simplest and most elegant explanation :) $\endgroup$
    – oerkelens
    Nov 7, 2014 at 7:56
  • 1
    $\begingroup$ He could have employed any strategy and still win ;-) $\endgroup$
    – John Dvorak
    Nov 7, 2014 at 8:37
  • 3
    $\begingroup$ @JoeZ., this is an awesome answer, and you are saying that it wont be accepted just because Jan Dvorak can not read your mind and guess what strategy among infinite number of possible strategies the boy chose? $\endgroup$
    – klm123
    Nov 7, 2014 at 10:25
  • 1
    $\begingroup$ No; the shah stated beforehand that one cannot take more stones than there are in the pile. $\endgroup$
    – user88
    Nov 7, 2014 at 20:55
  • 4
    $\begingroup$ Frankly, I'm not sure what the fuss is about. I found Jan Dvorak's answer a better and more simple one then mine, so by all means - grant him the accepted answer. Going for 'badges' as an achievement isn't really the spirit of my presence here anyway. $\endgroup$
    – Tim Couwelier
    Nov 10, 2014 at 8:33
4
$\begingroup$

First question is easy.

The boy, each time can take a number of stones, that with stones the shah took previous turn would make 6. Then, since 42 is dividable by 6 the boy will take the last stone.

The second question is easy enough too.

The shah took 1 stone at his first move, then he can apply the previous strategy of the boy (like this is a game with 41 stones only) to insure that the boy will finally remain with 5 stones exactly (41-6x6=5). Then, if the boy takes 1 stone, the shah takes 3 and vice versa. This will force the boy to take the last stone and "win".

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Pity fastest isn't always best, even after edits. $\endgroup$
    – AndrewC
    May 22, 2015 at 2:24
3
$\begingroup$

I know @Jan Dvorak already answer, but I want to share my solution too, because I took the inverse route.

If you want to win, you need 1, 3 or 5 stones in the pile to make the last move.

Otherwise if you have 2, 4 or 6, no matter how many stones you remove {1,3,5} you will create a state where the great shah will win.

So to win you need an odd number in your turn.

Then I realize not matter how the stones are removed, the student always will face a pile of stones with odd number of them. Because the shah move first, the starting number of stones is even, and can only remove odd number of stones.

There for the student always win.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.