Alice and Bob are play a game in a $(2n)*(2n)$ chess boared.Alice starts from the top right point moving 1 unit in every turn.Bob starts from the down left square and does the same.The goal of Alice is to make a closed shape ending in its start position and cannot reach any point that was reached before by any of players .if a players cannot move the other player keeps moving.what is the maximum are of the shape that the first player can build with every strategy of second player.
Problem
Source: Iran third round combinatorics problem 1
Tags: combinatorics
alirezabgi
04.05.2019 16:38
the answer is n * n Does anybody want my solution??
EfthymiosN
12.07.2019 21:23
alirezabgi wrote: the answer is n * n Does anybody want my solution?? ? Yeah post it. The answer is $n(n+1)$ btw.
puntre
17.05.2021 18:18
Does anyone have a solution to this one?
VicKmath7
02.07.2021 22:42
Bumping it again. Solution?
cadaeibf
03.07.2021 11:44
The minimum amount of turn in which B can block A is $4n-3$, since it suffices for him to arrive to the cell next to the top right that A didn't initially go through, and so A has at most $4n-3+1=4n-2$ moves he can use. Assume A does $a$ moves to the left (and necessarily $a$ to the right) and $b$ moves down (and necessarily $b$ up); if so, we must have $2a+2b=4n-2\implies a+b=2n-1$. Horizontally, he can at most cover $a+1$ columns and vertically at most $b+1$ columns, so the maximum theoretical area is $(a+1)(b+1)$. Now by amgm $(a+1)(b+1)\leq (n-\frac 12)^2$, and the closest case to equality is $a=n-1$ and $b=n$ (or viceversa), which gives an area of $n(n+1)$, so we now must only show that it can be done. Let us use coordinates $(x,y)$ ($1\leq x,y\leq 2n$) to describe the cells. With no problem A can get in a straight line to $(n+1,2n)$ and then to $(n+1,n+1)$, since in the meanwhile B can only cover a Manhattan distance of $2n-3$. Now, A can go down (that cell couldn't have been reached with $2n-2$ moves by B). But now A has always the advantage over B (since he moves first) and so he can just return in a straight line going to $(2n,n)$ and finally back to $(2n,2n)$. Therefore the maximum area A can cover is $n(n+1)$.
Mehrshad
30.07.2022 20:08
cadaeibf wrote:
The minimum amount of turn in which B can block A is $4n-3$, since it suffices for him to arrive to the cell next to the top right that A didn't initially go through, and so A has at most $4n-3+1=4n-2$ moves he can use.
Without loss of generality I assume that Alice's first move is to the point $(2n-1,2n)$. So she must finally reach the point $(2n,2n-1)$. Bob can safely in a straight line go to the point $(2n-1,1)$ and then to $(2n-1,2)$. Now Bob can go up until he sees that in his turn(before the turn) at least one of the points $B+(0,1)$ or $B+(0,2)$ or $B+(1,0)$ be reached by Alice. ($A$ is Alice's position and $B$ is bob's position. Also assume that $B=(2n-1,y)$.
Case 1: $B+(1,0)$ be reached.
In this case, Alice is on the$2n$th column and she couldn't enter it from the downside because she couldn't enter this column via points $(2n,1),(2n,2),\ldots,(2n,y-1)$. So Alice had entered this cell from its upside and she can't go to her start position.
Case 2: $B+(0,1)$ be reached.
In this case, Bob can go one unit to the right and block Alice which I'll check it later. By the way, after that move, it's not important to me how Bob do his next moves.
Case 3: $B+(0,2)$ be reached.
In this case similar to case 2, Bob can go 1 unit up and then It can be shown that Bob can go to the right in his next move or Alice can't reach her start position.
I define $h\coloneqq\begin{dcases}y&\text{Case 1 or 2 the first time occurs}\\y+1&\text{Case 3 occurs}\end{dcases}$
We know that the path Alice had passed to reach $(2n-1,h+1)$ is at most $(2n-3+h)+1$ because Alice had reached that point earlier than when Bob had reached the point $(2n-1,h)$. After that Alice had gone a path to the point $(2n,2n)$. Every path that Alice could choose doesn't generate an area for her bigger than when she just returns in a straight line going to $(2n,h+1)$ and finally back to $(2n,2n)$. The path I considered has a length of exactly $2n-h$. So Alice's replaced path has at most $4n-2$ moves. The rest of my solution is the same as @cadaeibf.
.