mathematics - Picking up stones

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.

2. Could the boy have lost the seventh game? Why or why not?

Answer

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.