Maths Olympiad Prep

Library / /18 of 30

Combinatorics Difficulty 5.8 AIME, harder Find the answer

Given an m×nm \times n table consisting of mnmn unit cells. Alice and Bob play the following game: Alice goes first and the one who moves colors one of the empty cells with one of the given three colors. Alice wins if there is a figure, such as the ones below, having three different colors. Otherwise Bob is the winner. Determine the winner for all cases of mm
and nn where m,n3m, n \ge 3.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Consider an m×nm \times n table with mnmn unit cells. Alice and Bob play a game where Alice goes first, and each player colors one of the empty cells with one of the given three colors. Alice wins if there exists a figure with three different colors as depicted in the problem. Otherwise, Bob wins. We aim to determine the winner for all cases where m,n3m, n \geq 3.

Let us analyze the conditions required for Alice to win:

1. Alice must create a specific configuration of cells with three different colors.
2. Bob’s strategy will be to prevent any such configuration from forming.

Now, consider different configurations of mm and nn:

1. Case 1: m5m \geq 5 and n4n \geq 4

In this case, the grid is large enough to allow Alice to create multiple potential configurations for the figure with three different colors. Alice can exploit the extra dimensions (having more rows or columns than the minimum needed) to execute a winning strategy by:

- Placing her colors in positions that form one of the harder-to-block configurations.
- Ensuring at every move, there exists at least one more potential configuration, forcing Bob to block continuously, eventually running out of effective strategies.

Therefore, Alice can indeed find a way to create a diverse-color figure on this board size, thus having a winning strategy.

2. Case 2: m<5m < 5 or n<4n < 4

When m<5m < 5 or n<4n < 4, the table is too small to allow Alice sufficient freedom to create a configuration with three different colors without Bob being able to effectively block all attempts. Bob can efficiently prevent any necessary configuration for Alice to win by maintaining control over the available spaces and colors.

As a result, Bob can stop any winning pattern from forming, and therefore he has a winning strategy.

By analyzing these cases, we determine that:

- Alice has a winning strategy when m5m \geq 5 and n4n \geq 4.
- Bob has a winning strategy otherwise.

Thus, the result is:
when m5,n4 Alice has a winning strategy, otherwise Bob has \boxed{\text{when } m \ge 5, n \ge 4\text{ Alice has a winning strategy, otherwise Bob has}}

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.