Maths Olympiad Prep

Library / /341 of 377

Combinatorics Difficulty 5.7 AIME, harder Prove it United States

Problem:

The integers from 11 to nn are written in increasing order from left to right on a blackboard. David and Goliath play the following game: starting with David, the two players alternate erasing any two consecutive numbers and replacing them with their sum or product. Play continues until only one number on the board remains. If it is odd, David wins, but if it is even, Goliath wins. Find the 2011th smallest positive integer greater than 1 for which David can guarantee victory.

Solution

Solution:

Answer: 40224022

If nn is odd and greater than 11, then Goliath makes the last move. No matter what two numbers are on the board, Goliath can combine them to make an even number. Hence Goliath has a winning strategy in this case.

Now suppose nn is even. We can replace all numbers on the board by their residues modulo 22. Initially the board reads 1,0,1,0,,1,01, 0, 1, 0, \ldots, 1, 0. David combines the rightmost 11 and 00 by addition to make 11, so now the board reads 1,0,1,0,,0,11, 0, 1, 0, \ldots, 0, 1. We call a board of this form a "good" board. When it is Goliath's turn, and there is a good board, no matter where he moves, David can make a move to restore a good board. Indeed, Goliath must combine a neighboring 00 and 11; David can then combine that number with a neighboring 11 to make 11 and create a good board with two fewer numbers.

David can ensure a good board after his last turn. But a good board with one number is simply 11, so David wins. So David has a winning strategy if nn is even. Therefore, the 2011th smallest positive integer greater than 11 for which David can guarantee victory is the 2011th even positive integer, which is 40224022.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.