Competition problem — Combinatorics

Combinatorics Difficulty 5.9 AIME, harder Prove it United States

Problem:

Fix a positive integer $n$ . Two players, Phil and Ellie, play the following game. First, Phil fills the squares of an $n \times n$ chessboard with nonnegative integers less than $n$ . Then, Ellie chooses three squares making an L, as in any of the following pictures:

Ellie adds 1 to each of the three squares making the L, except that if the number $n$ appears in a square, it is immediately replaced by 0. Ellie wins if, after modifying finitely many L's in this way, she can change all the numbers on the board into 0's; otherwise Phil wins.
Which player has a winning strategy if

a. $n=12$ ?

b. $n=2012$ ?

Solution

Solution:

a.
Phil wins in this case. Consider the sum of all the numbers on the board. If Ellie adds 1 to three squares making an $\mathrm{L}$ , the sum increases by 3, and when a 12 is replaced by a 0, the sum decreases by 12. So the sum always increases and decreases by multiples of 3. So if Phil ensures that the initial sum is not a multiple of 3 (e.g. by putting a 1 in one square and 0's in all the others), then Ellie will never be able to make the sum 0.

b.
Ellie wins in this case. Consider four squares making a $2 \times 2$ square:

$c$	$d$
$a$	$b$

Suppose that Ellie chooses each of the L's

\{b, a, c\}

\{a, b, d\}

\{a, c, d\}

671 times and the

\mathrm{L}

\{b, d, c\}

670 times. Then each of the squares

b, c, d

will be incremented exactly 2012 times, and so their values will remain the same after the operation. However, the square

a

will be incremented 2013 times; thus its value will be increased by 1 or, if it was initially 2011, replaced by 0. In a similar manner, Ellie can increment the value of any single square on the board and thus change all the numbers to 0's.

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.