Competition problem — Combinatorics

Library / /72 of 115

Combinatorics Difficulty 7.4 National olympiad, round 2 Find the answer

Let $n \geq 2$ be an integer. An $n \times n$ board is initially empty. Each minute, you may perform one of three moves:
If there is an L-shaped tromino region of three cells without stones on the board (see figure; rotations not allowed), you may place a stone in each of those cells. If all cells in a column have a stone, you may remove all stones from that column. If all cells in a row have a stone, you may remove all stones from that row.

Figure (Asymptote source)

unitsize(20); draw((0,0)--(4,0)--(4,4)--(0,4)--(0,0)); fill((0.2,3.8)--(1.8,3.8)--(1.8, 1.8)--(3.8, 1.8)--(3.8, 0.2)--(0.2, 0.2)--cycle, grey); draw((0.2,3.8)--(1.8,3.8)--(1.8, 1.8)--(3.8, 1.8)--(3.8, 0.2)--(0.2, 0.2)--(0.2, 3.8), linewidth(2)); draw((0,2)--(4,2)); draw((2,4)--(2,0));

For which

n

is it possible that, after some non-zero number of moves, the board has no stones?

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

We are given an $n \times n$ board that starts empty and are allowed to perform certain moves to place and remove stones. The goal is to identify for which values of $n$ it is possible for the board to have no stones after a series of valid moves:

1. Types of Moves:
- L-shaped tromino placement: Place a stone in each cell of an L-shaped tromino if the cells are empty. An L-shaped tromino is a 3-cell configuration shaped like an 'L'.
- Row clearance: Remove all stones from a row if it is completely filled with stones.
- Column clearance: Remove all stones from a column if it is completely filled with stones.

2. Understanding the Problem:
- Start with an empty board.
- Perform valid moves according to the described operations.
- Determine if it's possible to return to an empty board after some moves starting initially from an empty board.

3. Strategy:
- Fill the board with stones using L-shaped tromino placements.
- Carefully clear stones using the row and column removal operations.
- Ensure that the removal operations result in no stones remaining on the board.

4. Solution Approach:
- For any $n \geq 2$ , consider filling the board using L-shaped trominoes. Arrange these L-shaped trominoes in such a manner that the board can potentially be completely covered with stones.
- Once the board is filled enough to allow row or column completion, selectively use row and column removal operations.
- The use of these removal operations reduces the board's fill such that it dynamically allows additional removal operations, potentially leading to an empty board.

5. Key Realization:
- The combination of placing and removing stones effectively enough allows the board to return to zero in terms of stones present.
- This process can be iterated for any $n \geq 2$ such that the final board state is empty.

Hence, for all possible integers $n \geq 2$ , it is feasible through the described moves to have an empty board after a non-zero number of operations:

$\boxed{\text{For all } n \geq 2}$

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