Rijul and Rohinee are playing a game on an $n\times n$ board alternating turns, with Rijul going first. In each turn, they fill an unfilled cell with a number from $1,2,\cdots, n^2$ such that no number is used twice. Rijul wins if there is any column such that the sum of all its elements is divisible by $n$. Rohinee wins otherwise. For what positive integers $n$ does he have a winning strategy? Proposed by Rohan Goyal
Problem
Source: India Practice EGMO TST 2025 P1
Tags: combinatorics
05.12.2024 11:33
In last sentence, "he" refers to who?
05.12.2024 11:48
zhaoli wrote: In last sentence, "he" refers to who? Rijul.
05.12.2024 11:54
I claim that Rijul wins $\iff$ $n$ is odd. We consider the following two cases: Case 1: $n$ even. Whenever Rijul places $i$ in the $j$-th column, Rohinee can place \[ \left\{ \begin{array}{l} n^2 + 1-i \text{ if } i \neq0,1 \pmod n\cr i-1 \text{ if } i \equiv1 \pmod n \cr i+1 \text{ if } i \equiv0 \pmod n \end{array} \right. \]in the $j$-th column. This makes the sum of numbers in each column to be $1,2,...,\frac{n}{2} \pmod n$ if said column is filled, and hence cannot be divisible by $n$. So Rijul cannot win in this case. Case 2: $n$ odd. Rijul starts by placing $n$ in column $1$. Then whenever Rohinee places $i$ in the $j$-th column, Rijul can place \[ \left\{ \begin{array}{l} n^2 +2n-i \text{ if } i \neq0 \pmod n\cr n^2-i \text{ otherwise} \end{array} \right. \]in the any column (other than column 1) if $j \neq 1$, and in the $1$st column otherwise. It is clear that this ensure that the sum of elements in the first column is $0 \pmod n$ throughout the game. Hence, Rijul wins in this case. $\blacksquare$
07.12.2024 10:54
We consider everything in mod $n$, so there are $n (1,2,..,n)'$s available for us. (We will be using name Alishalin for Rijul) For odd $n=2k+1$ Alishalin(Rijul) win : Consider middle most row (as number of rows are odd, it will be $(k+1)$th row) and name cells from left to right as $-k,-(k-1),..-1,0,1,2,...,k$. Now alishalin will mark $n$ at $0$ (central cell of square) Now if Rohinee madam play anything other then this middle row say at some row $v \neq k+1$ as value $r$. we consider that cells reflection over middle row (or row $2k+2-v$) and mark $n-r$. and if she mark at middle row some value $r$ at $y$th place, we mark $n-r$ at $-y$th's place. This way, number of times $r$ written will be same as $n-r$. Thus at the end central column have to have all sum with pairs in sum $n$. Hence sum of middle colume will be divisible by $n$. We can always get $n-r$ for $r$ in middle colume, as number of $r$ is equal to $n-r$ by way of filling cells Even $n$, consider middle line, now if alishalin play $x$ at some row $v$, Rohinee will play at reflection of that row above middle line, or $2k+2-v$ as $n+1-x$, so each columm sum of pair is $\equiv 1($mod$ n)$. Therefore total sum will be $1 * (n/2)$ which is not equal to $n$, hence Rohinee wins.
15.12.2024 18:45
Neat problem Headsolved We claim that Alishalin(Rijul) wins iff $n$ is odd. I divide into two cases Case 1: $n=2k$ even. Whenever Alishalin places $i$ in some column, Rohinee must place $n^2+1- i$ in the same column. This ensures that the final sum in each column is $4k^3+k$, which is not divisible by $n=2k$, and thus Rohinee wins in this case Case 2: $n$ odd. Rijul starts by placing $n^2$ in column $1$. Then after that, whenever Rohinee places $x$ in the first colum, Alishalin has to place $n^2-x$ in column 1. This ensures that column one has sum divisible by $n$ at the end of the game. To ensure that Rohinee cant choose a number $x$ such that $n^2-x$ has already been played, Alishalin must always respond to Rohinee's turn of $a$ not in column one with $n^2-a$ again not in column 1. This can be checked to work and not run into any repetition of numbers or other such issues so we are done as Alishalin wins.
01.01.2025 13:53
Solved with sanyalarnab For even $n$ ,Rohinee wins. Her winning strategy:-Whenever Rijul writes a number $i$ in some column. Rohinee writes $n^2+1-i$ in the same column. Firstly we show that it is always possible for Rohinee to make this move. Note that when Rijul writes a number in a column then the number of numbers in that column is odd meaning that there is still empty cell left in that column for Rohinee to write her number (as total number of cells =$n$ which is even).Next note that these $n^2$ numbers comes in pairs i.e. $\{(1,n^2),(2,n^2-1),..,(\frac{n^2}{2},\frac{n^2}{2}+1)\}$. Observe that each pair is initiated by Rijul and terminated by Rohinee just after him. Now we show why Rohinee wins. When grid is filled sum of each column is $\frac{n(n^2+1)}{2}$ which is not divisible by $n$ (since $n$ is even and $n^2+1$ is odd). For odd $n$ ,Rijul wins. His winning strategy:- Rijul writes $n^2$ in first column.If Rohinee writes number $j$ in the first column ,then Rijul also writes $n^2-j$ in the first column.If Rohinee writes number $k$ in remaining $n $x$(n-1)$ grid then Rijul also writes number $n^2-k$ in that $n$ x$(n-1)$ grid. Proving that Rijul can always make this move is similar to above one. This works since when the whole grid is filled, the sum of numbers in the first column is $n^2+\frac{(n-1)(n^2)}{2}$ which is divisible by $n$.
20.01.2025 14:45
claim if odd rijul (A) wins if even Rohini(B) can win a weirdly complicated solution from the others posted here, which i saw and found out how simply they did it while i overcomplicated it but nonetheless it worked
Attachments:
