Maths Olympiad Prep

Library / /6 of 13

Combinatorics Difficulty 6.5 National Olympiad Prove it Italy

Problem:

Alberto and Barbara play the following game. On a table there are 1999 matches: in turn each player must remove from the table a number of matches of their choice, provided it is greater than or equal to one, and less than or equal to half the number of matches that are on the table at that moment. The player who leaves only one match on the table loses. Barbara is the first to play.
Determine for which of the two players there exists a winning strategy and describe such a strategy.

Solution

Solution:

The winning strategy can be determined by working backwards. Whoever leaves only one match on the table loses. Whoever leaves two wins, because they force the other player to leave only one. Whoever leaves 3 or 4 loses, because on the following move the other player can leave two. Whoever leaves 5, on the other hand, wins, because they force the other player to leave 3 or 4, which we have seen to be losing moves. Similarly one sees that leaving 6,7,8,96,7,8,9 or 1010 is a losing move (it allows the other player to leave 55), while leaving 1111 is winning.

This reasoning can be repeated indefinitely: if leaving kk matches is a winning move, then leaving a number between k+1k+1 and 2k2k (inclusive) is losing, while leaving 2k+12k+1 is winning. In conclusion the "winning numbers" can easily be determined starting from two and exploiting recursively the fact just observed that if kk is winning, then 2k+12k+1 is also winning. The "winning numbers" less than 19991999 are therefore: 2,5,11,23,47,95,191,383,767,15352, 5, 11, 23, 47, 95, 191, 383, 767, 1535. Barbara can therefore win by following this strategy: on the first move she leaves 15351535 matches on the table, the second time it is her turn she leaves 767767, the third time 383383, and so on. Proceeding in this way, the tenth time it is her turn she will leave 22 on the table, and on the following move Alberto will lose.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.