Let m and n be positive integers greater than 1. In each unit square of an m ˆ n grid…
- User
Let m and n be positive integers greater than 1. In each unit square of an m ˆ n grid lies a coin with its tail-side up. A move consists of the following steps:
- select a 2 ˆ 2 square in the grid;
- flip the coins in the top-left and bottom-right unit squares;
- flip the coin in either the top-right or bottom-left unit square. Determine all pairs pm, nq for which it is possible that every coin shows head-side up after a finite number of moves.
- Assistant
To solve this problem, we need to determine for which pairs ((m, n)) it's possible to flip coins in the specified manner and turn all coins to heads. The key lies in examining the parity and invariance in the problem.
Understanding the Moves
In each move, we flip 3 coins:
- The top-left coin ((a)) and the bottom-right coin ((d)) in the chosen (2 \times 2) square.
- Then, either the top-right ((b)) or bottom-left ((c)) coin.
Parity Analysis
Since we're flipping 3 coins each time, the total number of heads changes by 1 (mod 2) with each move. That means the parity of the number of heads alternates with each move.
Grid Coloring and Invariances
We can color the grid in a checkerboard pattern (like a chessboard) where black and white squares alternate. This coloring helps us examine the behavior of the coins on black and white squares separately.
Let:
- (S) be the sum (mod 2) of the coins on black squares.
- (T) be the sum (mod 2) of the coins on white squares.
In each move:
- (S) remains unchanged because we flip an even number of black squares.
- (T) changes by 1 because we flip an odd number of white squares.
Determining Feasibility
For all coins to be heads, both (S) and (T) must match the sums (mod 2) of the total number of black and white squares. We find:
-
When (mn) is a multiple of 4 ((mn \equiv 0 \mod 4)):
- The number of white squares is even.
- (T) can be made to match the required parity.
- The goal configuration is attainable.
-
When (mn) is not a multiple of 4:
- The parity of (T) will not match what's needed.
- The goal configuration is unattainable.
Conclusion
The necessary and sufficient condition for turning all coins to heads is that the total number of coins, (mn), is divisible by 4.
**Answer: Exactly all integer pairs with m × n divisible by 4; that is, all m and n where mn is a multiple of 4.