Maths Olympiad Prep

Library / /88 of 520

Combinatorics Difficulty 6.5 National olympiad Find the answer

Ana and Beto play on a grid of 2022×20222022 \times 2022. Ana colors the sides of some squares on the board red, so that no square has two red sides that share a vertex. Next, Bob must color a blue path that connects two of the four corners of the board, following the sides of the squares and not using any red segments. If Beto succeeds, he is the winner, otherwise Ana wins. Who has a winning strategy?

Solution

1. Define the problem and initial conditions:
- Ana and Beto play on a 2022×20222022 \times 2022 grid.
- Ana colors some sides of the squares red such that no square has two red sides sharing a vertex.
- Beto must color a blue path connecting two of the four corners of the board, following the sides of the squares and avoiding red segments.

2. Beto's strategy:
- Beto starts from the bottom left corner and attempts to draw a blue path B1B_1 going only up and right, avoiding red edges.
- At each vertex, if both the up and right edges exist, Beto can always proceed either up or right because Ana's coloring rule ensures that both edges cannot be red simultaneously.

3. **Path B1B_1 hitting the wall:**
- The only way Beto cannot continue his path B1B_1 is if he hits the upper or rightmost wall.
- Without loss of generality (WLOG), assume B1B_1 hits the rightmost wall.

4. **Constructing the second path B2B_2:**
- Beto then starts from the bottom right corner and attempts to draw a blue path B2B_2 going only up and left, avoiding red edges.
- Similar to B1B_1, B2B_2 can only end when it hits the upper or leftmost wall.

5. **Intersection of paths B1B_1 and B2B_2:**
- Since B1B_1 hits the rightmost wall and B2B_2 hits the leftmost wall, the paths B1B_1 and B2B_2 must intersect at some point.
- This intersection implies that Beto can draw a continuous blue path from the bottom left corner to the bottom right corner.

6. Conclusion:
- Since Beto can always find a path from the bottom left corner to the bottom right corner by following the described strategy, he has a winning strategy.

\blacksquare

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.