Ana and Beto play on a grid of . 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 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 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 hitting the wall:**
- The only way Beto cannot continue his path is if he hits the upper or rightmost wall.
- Without loss of generality (WLOG), assume hits the rightmost wall.
4. **Constructing the second path :**
- Beto then starts from the bottom right corner and attempts to draw a blue path going only up and left, avoiding red edges.
- Similar to , can only end when it hits the upper or leftmost wall.
5. **Intersection of paths and :**
- Since hits the rightmost wall and hits the leftmost wall, the paths and 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.