HMMT 二月 2011 · ALGCOMB 赛 · 第 10 题

英文解析

10. The integers from 1 to n are written in increasing order from left to right on a blackboard. Davidand Goliath play the following game: starting with David, the two players alternate erasing any twoconsecutive numbers and replacing them with their sum or product. Play continues until only onenumber on the board remains. If it is odd, David wins, but if it is even, Goliath wins. Find the 2011 thsmallest positive integer greater than 1 for which David can guarantee victory.
    Answer: 4022 If n is odd and greater than 1, then Goliath makes the last move. No matter whattwo numbers are on the board, Goliath can combine them to make an even number. Hence Goliathhas a winning strategy in this case.
    Now suppose n is even. We can replace all numbers on the board by their residues modulo 2. Initiallythe board reads 1 , 0 , 1 , 0 , . . . , 1 , 0. David combines the rightmost 1 and 0 by addition to make 1, so nowthe board reads 1 , 0 , 1 , 0 , . . . , 0 , 1. We call a board of this form a “good” board. When it is Goliath’sturn, and there is a good board, no matter where he moves, David can make a move to restore a goodboard. Indeed, Goliath must combine a neighboring 0 and 1; David can then combine that numberwith a neighboring 1 to make 1 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 1,
    so David wins. So David has a winning strategy if n is even. Therefore, the 2011 th smallest positiveinteger greater than 1 for which David can guarantee victory is the 2011 th even positive integer, whichis 4022. 2