Easy Combinatorial Game Problem in Taiwan TST

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

Easy Combinatorial Game Problem in Taiwan TST

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2025 Taiwan TST Round 1 Independent Study 1-C

The post below has been deleted. Click to close.

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

11 posts

#1 h Mar 5, 2025, 5:05 AM • 1 Y

Y by Rounak_iitr

Alice and Bob are playing game on an $n \times n$ grid. Alice goes first, and they take turns drawing a black point from the coordinate set
$\{(i, j) \mid i, j \in \mathbb{N}, 1 \leq i, j \leq n\}$ There is a constraint that the distance between any two black points cannot be an integer. The player who cannot draw a black point loses. Find all integers $n$ such that Alice has a winning strategy.

Proposed by chengbilly

This post has been edited 1 time. Last edited by chengbilly, Mar 5, 2025, 5:09 AM

Z K Y

The post below has been deleted. Click to close.

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

58 posts

#2 h Mar 5, 2025, 7:20 PM

Y by

1) $n = 2k+1$
Let's put center of coordinates in $(k+1;k+1)$ .
Alice will mark $(0,0)$ . Then if Bob marks $(a,b)$ then
$a^2+b^2$ is not a square. Alice can mark $(-a,-b)$ since points are symmetrical with respect to $(0,0)$ , then we only need to check if distance from $(-a,-b)$ to $(a,b)$ is an integer.
But $d^2 = (2a)^2 + (2b)^2 = 4(a^2+b^2)$ is not a square. So if $n = 2k+1$ then Alice wins.
2) $n=2k$
Lets put the center of coordinates in $(k+0,5;k+0,5)$ .

If Alice marks $(a+0,5;b+0,5)$ then Bob should mark $(-a-0,5;-b-0,5)$ . Points are symmetrical with respect to the point $(0,0)$ . So we only need to check if $d^2$ is not a square.
But $d^2 = (2a+1)^2 + (2b+1)^2 \equiv 2 (mod 4)$ . So $d^2$ is not a square. So if $n = 2k$ then Bob wins.

This post has been edited 1 time. Last edited by CHESSR1DER, Mar 5, 2025, 7:21 PM

Z K Y

The post below has been deleted. Click to close.

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

44 posts

#3 h Mar 6, 2025, 2:00 AM • 1 Y

Y by Hamzaachak

Yet another symmetry problem.
For $n$ odd, Alice plays center of the grid, and then copy (do symmetric of ) Bob's moves.
For $n$ even, Bob plays symmetric of Alice's moves.

Z K Y

The post below has been deleted. Click to close.

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

nguyenhuybao_06

39 posts

nguyenhuybao_06

#4 h Mar 6, 2025, 2:13 AM

Y by

Actually, if $n=2k+1,$ Alice can play any point, but follow the rule; then she'll win. And if $n=2k,$ Bob can play any point, but follow the rule; then he'll win. Cuz the problem is equivalent to: pick any point and draw all point on its row and column by black. The game must end after $n$ turns.

Z K Y

The post below has been deleted. Click to close.

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

58 posts

#5 h Mar 6, 2025, 7:48 AM

Y by

nguyenhuybao_06 wrote:

Cuz the problem is equivalent to: pick any point and draw all point on its row and column by black. The game must end after $n$ turns.

Its not equal to this as for example points $(0,0)$ and $(3,4)$ both can't be marked.

Z K Y

The post below has been deleted. Click to close.

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

221 posts

#6 h Mar 6, 2025, 12:03 PM

Y by

$\cdots$

This post has been edited 2 times. Last edited by GreekIdiot, May 7, 2025, 4:08 PM

Z K Y

The post below has been deleted. Click to close.

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

58 posts

#7 h Mar 6, 2025, 1:43 PM

Y by

Quote:

Consider $(a,b)=(3,4)$ then notice $a^2+b^2=25$ is a perfect square
Same goes for all pythagorean triples

If $a^2+b^2$ is a square, then Bob can't mark it as (0,0) already marked.

Z K Y

The post below has been deleted. Click to close.

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

cursed_tangent1434

625 posts

cursed_tangent1434

#8 h Mar 6, 2025, 3:22 PM

Y by

Extremely standard idea, but the problem is quite enjoyable nevertheless. We claim that Alice wins if and only if $n$ is odd and Bob wins if and only if $n$ is even. We tackle each of these cases separately. Let a violating pair denote a pair of points which have an integer distance between them.

Case 1 : $n$ is odd. In this case, let the center square $O$ of the grid denote cell $\left(\frac{n+1}{2},\frac{n+1}{2}\right)$ . Alice's strategy is simple. In here first move she draws a black point at the center square, and then reflects Bob's move across the center square.

To see why this works, assume that Alice cannot copy Bob's move after a certain point. If Bob draws a black point at $P$ , then $P'$ must be either already colored black or an integer distance away from a black point. The former is impossible due to the symmetric nature of the moves until this point. For the latter to be possible the violating pair must be either $(P',O)$ , $(P,P')$ or $(P',Q)$ where $Q \not \in \{P,P',O\}$ . Clearly if $(P',O)$ is a violating pair by symmetry so is $(P,O)$ implying that Bob performed an illegal move in his previous move. Further if $(P,P')$ is a violating pair so must be $(P,O)$ since an easy calculation yields that $PP'=2PO$ . Further, if $(P',Q)$ were a violating pair, then $(P,Q')$ must be a violating pair where $Q'$ is the reflection of $Q$ across the center square. But by the nature of the algorithm, $Q'$ must already be marked which implies that Bob's previous move was illegal.

Thus, as long as Bob has a legal move, so does Alice and since the number of cells on the board is odd, it is Bob who runs out of legal moves first.

Case 2 : $n$ is even. This case is almost entirely similar however the center point $O$ is now defined as the center of the square formed by points $\left(\frac{n}{2},\frac{n}{2}\right)$ , $\left(\frac{n}{2},\frac{n}{2}+1\right)$ , $\left(\frac{n}{2}+1,\frac{n}{2}\right)$ and $\left(\frac{n}{2}+1,\frac{n}{2}+1\right)$ . Bob now simply performs the symmetric move to Alice's across the center point in each move. If he is unable to do this at any point, say after Alice draws the black point $P$ then either $(P,P')$ or $(P,'Q)$ for $Q\ne P$ must be a violating pair. In the later case, the reflection of $Q$ across the center point $Q'$ must already have been marked due to the nature of the given algorithm implying that $(P,Q')$ is already a violating pair invalidating Alice's final move.

In the former case, note that the horizontal and vertical distances between points $P$ and $P'$ are odd by symmetry. Applying the Pythagorean Theorem results in $PP' = \sqrt{a^2+b^2}$ for odd positive integers $a$ and $b$ which implies that the quantity under the square root is $2\pmod{4}$ which can never be a perfect square. Thus, this distance is not an integer and hence it cannot be a violating pair. Thus, as long as Alice has a legal move, so does Bob and since the number of cells on the board is even, it is Alice who runs out of legal moves first.

Z K Y

The post below has been deleted. Click to close.

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

457 posts

#9 h Apr 30, 2025, 3:31 AM

Y by

solution

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a