Paint and Optimize: A Grid Strategy Problem

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Paint and Optimize: A Grid Strategy Problem

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Iran 2025 second round p2

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

103 posts

#1 h Apr 20, 2025, 4:25 AM

Y by

Ali and Shayan are playing a turn-based game on an infinite grid. Initially, all cells are white. Ali starts the game, and in the first turn, he colors one unit square black. In the following turns, each player must color a white square that shares at least one side with a black square. The game continues for exactly 2808 turns, after which each player has made 1404 moves. Let $A$ be the set of black cells at the end of the game. Ali and Shayan respectively aim to minimize and maximise the perimeter of the shape $A$ by playing optimally. (The perimeter of shape $A$ is defined as the total length of the boundary segments between a black and a white cell.)

What are the possible values of the perimeter of $A$ , assuming both players play optimally?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1541 posts

#2 h Apr 20, 2025, 5:18 AM

Y by

The answer is $2 \cdot 1404 + 6 = 2814$ .

Ali's strategy is to place their second cell to form an $L$ , and then always fill black cells with two neighbors. This only breaks down if the currently colored black squares are an $2a \times b$ rectangle. Then if we consider the last time occurs then there's at most $2a + 2b + 2\cdot (1404 - ab) < 2814$ . Else, Ali adds at most $6$ to the perimeter and Shayan $2$ each turn giving the result.

Shayans strategy is to place each of their moves to add $2$ , with Ali's first two moves must add $2$ and $4$ the result follows.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

910 posts

#3 h Apr 21, 2025, 6:50 PM

Y by

Answer: $2814$

Solution. We show two strategies, one for Ali to ensure that the perimeter of $A$ is at most $2814$ , regardless of how Shayan plays, and one for Shayan to ensure that the perimeter of $A$ is at least $2814$ , regardless of how Ali plays. This is clearly sufficient to show that if both players play optimally, the perimeter of $A$ will be $2814$ .

Strategy for Ali: Let $I$ be an index starting at $0$ . Each time someone colors a square increase $I$ be the number of black squares that are adjacent to that square. For Ali's second move, he should play so that the black squares form an $L$ -tromino. Thus after three turns, $I=2$ . We claim that for each of the following $1402$ pairs of turns where Shayan plays and then Ali plays, Ali can guarantee that $I$ increases by at least $3$ during their pair of turns. Each move will increase $I$ by at least $1$ . If Shayan's move increases $I$ by at least $2$ , then we are done. If Shayan's move increases $I$ by exactly $1$ , then the resulting colored squares can not form a rectangle (notice the rectangle can not be a stick because of Ali's second move). Then it is always possible for Ali to color a square that will increase $I$ by at least $2$ (otherwise the shape cannot have holes and the boundary would be rectangular). Thus after these $1402$ pairs of turns, $I$ has increased by at least $4206$ . For Shayan's final move, $I$ will increase by at least one more. To finish, $\text{Perimeter}(A)=4\cdot \#\text{black squares}-2\cdot I\leq 4\cdot 2808-2\cdot 4209=2814$
Strategy for Shayan: Let $I$ be an index counting the sum of the height and width of the smallest axis-aligned rectangle containing all of the black cells. After Ali's second move, it will always be that $I=4$ . Then for each of Shayan's next moves he can always increase $I$ by $1$ by coloring a square directly below one of the lowest existing black squares. Thus by the end, Shayan can ensure that $I$ is at least $1407$ . Then shooting a laser through each unit on the perimeter of the rectangle must hit different edges along the perimeter of $A$ . Thus to finish, $\text{Perimeter}(A)\geq 2I\geq 2814$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a