Maths Olympiad Prep

Library / /411 of 520

Combinatorics Difficulty 7.3 National olympiad, round 2 Prove it

In each 20072 2007^{2} unit squares on chess board whose size is 2007×2007 2007\times 2007,
there lies one coin each square such that their "heads" face upward.
Consider the process that flips four consecutive coins on the same row, or flips four consecutive coins on the same column.
Doing this process finite times, we want to make the "tails" of all of coins face upward, except one that lies in the i ith row and j jth column.
Show that this is possible if and only if both of i i and j j are divisible by 4 4.

Solution

1. Initial Setup and Definitions:
- Consider a 2007×20072007 \times 2007 chessboard where each unit square contains a coin with heads facing upward.
- We can flip four consecutive coins in the same row or column.
- We aim to make all coins show tails except for one coin at position (i,j)(i, j).

2. Analyzing the Parity of Rows and Columns:
- Let r1,r2,r3,r4r_1, r_2, r_3, r_4 be the number of heads in rows that are 1mod41 \mod 4, 2mod42 \mod 4, 3mod43 \mod 4, and 0mod40 \mod 4 respectively.
- Initially, r1=r2=r3=r4=2007r_1 = r_2 = r_3 = r_4 = 2007 since all coins are heads up.

3. Effect of Flips on Parity:
- Each flip of four consecutive coins in a row or column changes the number of heads in that row or column by ±4\pm 4.
- This means the parity (odd or even nature) of the number of heads in each row or column is preserved modulo 2.

4. Parity Constraints:
- After any sequence of flips, the parities of r1,r2,r3,r4r_1, r_2, r_3, r_4 must remain equal modulo 2.
- Therefore, it is impossible to have a lone head in a row or column that is 1,2,1, 2, or 3mod43 \mod 4 because it would violate the parity condition.

5. Constructing the Desired Configuration:
- To show the converse, we need to demonstrate that it is possible to achieve the configuration with a lone head at (i,j)(i, j) where both ii and jj are divisible by 4.
- Start by making all coins tails except for the coin at (4,4)(4, 4):
- Flip all rows from 4 to 2007 using vertical flips.
- For the first three rows, flip all columns from 4 to 2007 using horizontal flips.
- This leaves a 3×33 \times 3 square of heads in the upper left corner.
- Use four vertical flips to leave three heads at (4,1)(4, 1), (4,2)(4, 2), and (4,3)(4, 3).
- One horizontal flip will leave a single head at (4,4)(4, 4).

6. Generalizing the Position of the Lone Head:
- From the position (4,4)(4, 4), we can move the lone head a distance of four using two adjacent flips.
- This allows us to move the lone head to any (i,j)(i, j) where i0mod4i \equiv 0 \mod 4 and j0mod4j \equiv 0 \mod 4.

True \boxed{\text{True}}

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.