A colouring game on a grid

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

A colouring game on a grid

G H J

Reveal topic tags

combinatorics proposed

winning strategy

L

G H BBookmark kLocked kLocked NReply

Source: Baltic Way 2024, Problem 8

The post below has been deleted. Click to close.

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

9029 posts

#1 h Nov 16, 2024, 5:06 PM

Y by

Let $a$ , $b$ , $n$ be positive integers such that $a + b \leq n^2$ . Alice and Bob play a game on an (initially uncoloured) $n\times n$ grid as follows:
- First, Alice paints $a$ cells green.
- Then, Bob paints $b$ other (i.e.uncoloured) cells blue.
Alice wins if she can find a path of non-blue cells starting with the bottom left cell and ending with the top right cell (where a path is a sequence of cells such that any two consecutive ones have a common side), otherwise Bob wins. Determine, in terms of $a$ , $b$ and $n$ , who has a winning strategy.

Z K Y

The post below has been deleted. Click to close.

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

3 posts

#2 h Dec 11, 2024, 10:21 AM

Y by

Denote each cell as (i, j) for row i, column j, so bottom left is (1,1), top right is (n, n)
We say all a(i, j) build a wall when i+j=k+1, k is integer and 1<=k<=2n-1. There are 2n-1 walls.
It's obvious that a path from (1,1) to (n, n) will across all walls: considering the sum of i, j of each cell on a "path", every step you move on the path, the sum +1 or -1, and the start number is 2, the end number is 2n, so each of 2~2n mush appears on the path("discrete version of IVT", not sure if it's the name in English)
1.obviously, if a>=2n-1, Alice can paint a green path from (1,1) to (n, n). Alice Win
2. if a<2n-1, there must be some "walls" whose all cells are not colored by Alice(as there are 2n-1 walls), we call them "non-green" walls. The max of their minimum length is [a/2]+1. So,
2.1. if b>= [a/2]+1, Bob can pick the non-green wall whose length is minimum, and color all of its cells to blue, and Bob Win.
2.2. if b<[a/2]+1, Alice can color the bottom row cells from(1, 1) to (1, [a/2]), and the right column cells form (n, n) to (n, [a/2]+1). Before Bob paints any cell, there are at least [a/2]+1 uncolored paths to connect these 2 green tiles, and these paths are not crossing each others. (I just don't know how to insert a pic here, so hopefully below ASCII chart (for n=5, a=6) can show the idea, I use '.' and '|' to show the paths, 'x' is placeholder to make the chart looks ok):
.........G
| .......G
| | .....G
| | |xxx|
GGG..|
To cut off all of these paths, Bob needs paint at least [a/2]+1 cells, one cell for each path. it means if b<[a/2]+1, Alice will Win.
In summary, Bob will win only if (a<2n-1)&&(b>= [a/2]+1) is true, otherwise, Alice will win.

Z K Y

The post below has been deleted. Click to close.

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

math-olympiad-clown

17 posts

math-olympiad-clown

#3 h Mar 30, 2025, 2:33 PM

Y by

is this ok? :wacko:

:wacko:

we separate the question into two cases
Case1. a+b=n^2 , in this case it's obvious to see that a must be greater than 2n-2 due to connectivity.

Case2. a+b<n^2
2-1 : if Alice has more than 2n-1 green blocks then obviously Alice wins.

2-2: if a is smaller than 2n-1 and b is greater than n-1 then Bob wins
(because Bob can "cut" any diagonal in any squares in the diagram and a is smaller than 2n-1 implies a is not absolutely connected by green bolcks)

2-3 : if a is smaller than 2n-1 and b=k which is smaller than n ,then we deduce that a must at least be 2k.

We call the absolutely connected green blocks from the bottom left corner "left dragon" and define the "right dragon" analogously.
now we define another noun called "HP" which is the number of non-coloring blocks surrounded by the dragon.
because the dragon must be absolutely connected , the "HP" of a dragon will be less than the number of its length+1 . we go back to the situation, b=k and if a is smaller than 2k, that means there must be a dragon which its length is at most k-1 so its "HP" will be at most k . then when Bob started to play , he can use all the blue blocks to suffocate the dragon , hence Bob wins.
and its easy to construct the example for a=2k and b=k and no dragon got suffocated.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a