There is a queue of $n{}$ girls on one side of a tennis table, and a queue of $n{}$ boys on the other side. Both the girls and the boys are numbered from $1{}$ to $n{}$ in the order they stand. The first game is played by the girl and the boy with the number $1{}$ and then, after each game, the loser goes to the end of their queue, and the winner remains at the table. After a while, it turned out that each girl played exactly one game with each boy. Prove that if $n{}$ is odd, then a girl and a boy with odd numbers played in the last game. Proposed by A. Gribalko
Problem
Source: All-Russian MO 2023 Final stage 10.4
Tags: combinatorics, All Russian Olympiad, graph theory, game, ilostthegame
starchan
18.05.2023 11:24
Solved with L567, M.V. Adhitya and Siddharth03
Construct a $n \times n$ stone donut, with $n^2$ cells. We treat the matches as cells $(i, j)$ of this donut, and in one move we either move right or up. The given conditon is the same as a valid sequence of moves which covers everything in the donut exactly once, starting with the sugar sprinkle at $(1, 1)$. Further, on all cells except for the last one (which we shall now refer to as the salty cell) we engrave $R$ or $U$ depending on the direction we went from that cell.
Claim 1: Across all bread crusts formed by cells $(i, j)$ for fixed $(i+j) \bmod n$ avoiding the salty cell, the characters engraved on these are identical.
Proof: Suppose otherwise. Then there must be some cell $(i, j)$ with $R$ engraved on it such that it's successor $(i+1, j-1)$ has $U$ engraved on it. But then these cells both fight over the sugar sprinkle on $(i+1, j)$; resulting in the Fourth Shinobi World War, contradiction.
Claim 2: The salty cell lies on the main bread crust.
Proof: Suppose otherwise. Then all cells on the main bread crust have the same character engraved on them. But the top-left cell and the bottom-right cell must have $R, U$ engraved on them respectively, so as to avoid fighting over the sprinkle at $(1, 1)$. In fact this also shows that the cells on the main bread crust are engraved with $R$s, then the salty cell and $U$s.
Consider the main bread crust. We shall call cells lying on this (other than the salty one) sugary cells henceforth. For each $1 \leq i \leq n$ with $(1-i, i)$ not salty, let $(1-k_i, k_i)$ be the first other sugary cell visited upon following the directions from $(1-i, i)$. It is easy to see that the number of $U$s encountered along the path from $(1-i, i)$ determines the value of $k_i$. But because of Claim 1, this number is fixed across all values of $i$ below the salty cell and then decreases by one above it. This is because an extra $U$ is contributed to each sugary cell below the salty one. If we let $a$ denote the height of the salty cell and $b$ the number of $U$s encountered, the problem reduces to showing the following
Reformulation:
Let $G$ be a digraph over $\{1, 2, \dots, n\}$ and let $a, b$ be in $\{1, 2, \dots, n\}$ such that for all vertices $1 \leq i < a$ we have an edge $i \mapsto i+b+1$ and for all vertices $a < i \leq n$ we have an edge $i \mapsto i+b$ (everything modulo $n$). Then if $G$ is hamiltonian, $a$ is odd.
Proof: If $a > b$, we can replace $a$ with $n+1-a$ and $b$ with $n+1-b$ and reverse the hamiltonian $G$ to reduce to $a \leq b$. Becuase there is no edge leading out of $a$, it must be the end of the Hamiltonian path, and because there is no edge leading into $b+1$. When $a \leq b$ we look at the process modulo $n-1$, with $a$ "deleted". We add exactly $b$ each time. Observe that before $a$ we must have visited $n+a-b-1$. Thus, we obtain that $n+a-b-1 \equiv (n-1)b \pmod {(n-1)}$, imypling that $a-b \equiv 0 \pmod {(n-1)}$. Now since adding $b$ covers all residues, we must have $\gcd(b, n-1) = 1$. Since $a \equiv b \pmod {(n-1)}$ we have that $a$ and $n-1$ are relatively prime as well. Since $n-1$ is even, $a$ is odd.
Now, coming back to the original problem, the salty cell was $(a, n+1-a)$. Since $a$ is odd, both coordinates are odd and we are done.
Stone Donut is a $n \times n$ board wrapping around itself. A bread crust is a diagonal of the board. The main bread crust is the one with $i+j \equiv 1 \bmod n$. A sugar sprinkle was used instead of a cell at some places.
CANBANKAN
27.05.2023 09:44
starchan wrote:
Reformulation:
Let $G$ be a digraph over $\{1, 2, \dots, n\}$ and let $a, b$ be in $\{1, 2, \dots, n\}$ such that for all vertices $1 \leq i < a$ we have an edge $i \mapsto i+b+1$ and for all vertices $a < i \leq n$ we have an edge $i \mapsto i+b$ (everything modulo $n$). Then if $G$ is hamiltonian, $a$ is odd.
Proof: If $a > b$, we can replace $a$ with $n+1-a$ and $b$ with $n+1-b$ and reverse the hamiltonian $G$ to reduce to $a \leq b$. Becuase there is no edge leading out of $a$, it must be the end of the Hamiltonian path, and because there is no edge leading into $b+1$. When $a \leq b$ we look at the process modulo $n-1$, with $a$ "deleted". We add exactly $b$ each time.
Consider $n=5, a=2, b=3, i=5$. Since $2\le i\le 5$, $i\to i+b$ it should go to 3. How will this path work when $2$ is deleted? It seems like it only jumps $b-1$ steps? I'd feel like a troll if this argument is actually correct; I bumped into the same idea and was sure it was wrong by checking some small counterexamples.
a22886
27.05.2023 13:38
Use the $n\times n$ directed path interpretation(as in #2). The path connects every member on the line $x+y=n+1$, and regard it as a (transitive) permutation on $[n]$. Calculate the sign of this permutation ($+1$ as it only have one orbit) in terms of the endpoint.
CANBANKAN
28.05.2023 19:23
Rephrased problem: Let $n$ be an odd integer. Consider a hamilton path on $(\mathbb{Z}/n\mathbb{Z})^2$ where I can only go to $(x+1,y)$ or $(x,y+1)$ from $(x,y)$. A hamilton path started on $(0,0)$. Prove that if it ends on $(a,b)$ where $0\le a,b<n$, then $a,b$ are even.
By analyzing $x+y$ in $\mathbb{Z}/n\mathbb{Z}$, we can see the destination square has $x+y=-1$. Say $(x,y)$ points right if $(x,y)$ goes to $(x+1,y)$, and say it points up otherwise.
Fix $j \in \{0,\cdots, n-2\}$, all squares $(x,y)$ on the line $x+y=j$ in $\mathbb{Z}/n\mathbb{Z}$, point in the same direction (possibly depending on $j$).
Fix $j$. Suppose $x+y=j$ and WLOG $(x,y)$ points up to $(x,y+1)$. Since $(x-1, y+1)$ is not the end point, it must point to something, namely $(x-1,y+2)$ since it can't point to $(x,y+1)$. We can then induct on $k$ to see that $(x_e-k, y_e+k)$ points to $(x_e-k, y_e+k+1)$. This works because all points on $x+y=j$ need to point to something as they are not the endpoint.
Now suppose $(x,y)$ where $x+y=n-1$ is the endpoint. WLOG $x,y\ne 0$, or we are done. Thus $(0,n-1)$ points right since nothing points to $(0,0)$. By induction on $k$ we can see that $(k,n-1-k)$ points right for $k=1,2,\cdots,x-1$. Also $(n-1,0)$ points up since nothing points to $(0,0)$. By induction on $k$ we can see that $(n-1-k,k)$ points up for $k=1,\cdots,y-1$.
Hence I arrive at the following problem:
Consider a path on $\mathbb{Z}/n\mathbb{Z}$ starting at 0, and from $x$ I go to $x+a+1$ if $R(x+a,n) \in \{0,\cdots,x_e-1\}$, and go to $x+a$ otherwise if $x+a$ is among $\{x_e+1, \cdots, n-1\}$. I need to make sure this path visits all elements of $\mathbb{Z}/n\mathbb{Z}$ in $n$ numbers (counting the initial 0).
As suggested by a22886, consider a permutation of $\{0,1,\cdots,n-1\}$ with the hamilton path and $x_e-a\to 0$. Since this permutation is an odd cycle, it's an even permutation. However, it is also $\pi_1 \circ \pi_2$ where $\pi_2(x)=x+a$ and $\pi_1 = (0 1 \cdots x_e)$. Hence $sgn(\pi_1) sgn(\pi_2) = 1$. Note that $\pi_2$ decomposes $\mathbb{Z}/n\mathbb{Z}$ into cycles of length $\gcd(a,n)$ which is odd, so $\pi_2$ is an even permutation. $sgn(\pi_1) = (-1)^{x_e}$, so $x_e$ is even.
Sourorange
10.06.2023 13:34
starchan wrote: Solved with L567, M.V. Adhitya and Siddharth03
Construct a $n \times n$ stone donut, with $n^2$ cells. We treat the matches as cells $(i, j)$ of this donut, and in one move we either move right or up. The given conditon is the same as a valid sequence of moves which covers everything in the donut exactly once, starting with the sugar sprinkle at $(1, 1)$. Further, on all cells except for the last one (which we shall now refer to as the salty cell) we engrave $R$ or $U$ depending on the direction we went from that cell.
Claim 1: Across all bread crusts formed by cells $(i, j)$ for fixed $(i+j) \bmod n$ avoiding the salty cell, the characters engraved on these are identical.
Proof: Suppose otherwise. Then there must be some cell $(i, j)$ with $R$ engraved on it such that it's successor $(i+1, j-1)$ has $U$ engraved on it. But then these cells both fight over the sugar sprinkle on $(i+1, j)$; resulting in the Fourth Shinobi World War, contradiction.
Claim 2: The salty cell lies on the main bread crust.
Proof: Suppose otherwise. Then all cells on the main bread crust have the same character engraved on them. But the top-left cell and the bottom-right cell must have $R, U$ engraved on them respectively, so as to avoid fighting over the sprinkle at $(1, 1)$. In fact this also shows that the cells on the main bread crust are engraved with $R$s, then the salty cell and $U$s.
Consider the main bread crust. We shall call cells lying on this (other than the salty one) sugary cells henceforth. For each $1 \leq i \leq n$ with $(1-i, i)$ not salty, let $(1-k_i, k_i)$ be the first other sugary cell visited upon following the directions from $(1-i, i)$. It is easy to see that the number of $U$s encountered along the path from $(1-i, i)$ determines the value of $k_i$. But because of Claim 1, this number is fixed across all values of $i$ below the salty cell and then decreases by one above it. This is because an extra $U$ is contributed to each sugary cell below the salty one. If we let $a$ denote the height of the salty cell and $b$ the number of $U$s encountered, the problem reduces to showing the following
Reformulation:
Let $G$ be a digraph over $\{1, 2, \dots, n\}$ and let $a, b$ be in $\{1, 2, \dots, n\}$ such that for all vertices $1 \leq i < a$ we have an edge $i \mapsto i+b+1$ and for all vertices $a < i \leq n$ we have an edge $i \mapsto i+b$ (everything modulo $n$). Then if $G$ is hamiltonian, $a$ is odd.
Proof: If $a > b$, we can replace $a$ with $n+1-a$ and $b$ with $n+1-b$ and reverse the hamiltonian $G$ to reduce to $a \leq b$. Becuase there is no edge leading out of $a$, it must be the end of the Hamiltonian path, and because there is no edge leading into $b+1$. When $a \leq b$ we look at the process modulo $n-1$, with $a$ "deleted". We add exactly $b$ each time. Observe that before $a$ we must have visited $n+a-b-1$. Thus, we obtain that $n+a-b-1 \equiv (n-1)b \pmod {(n-1)}$, imypling that $a-b \equiv 0 \pmod {(n-1)}$. Now since adding $b$ covers all residues, we must have $\gcd(b, n-1) = 1$. Since $a \equiv b \pmod {(n-1)}$ we have that $a$ and $n-1$ are relatively prime as well. Since $n-1$ is even, $a$ is odd.
Now, coming back to the original problem, the salty cell was $(a, n+1-a)$. Since $a$ is odd, both coordinates are odd and we are done.
Stone Donut is a $n \times n$ board wrapping around itself. A bread crust is a diagonal of the board. The main bread crust is the one with $i+j \equiv 1 \bmod n$. A sugar sprinkle was used instead of a cell at some places.
Nice solution. But...... Can you define salty and sugar further?
CANBANKAN
10.06.2023 20:19
Sourorange wrote: starchan wrote: Solved with L567, M.V. Adhitya and Siddharth03 /quote] Nice solution. But...... Can you define salty and sugar further? The solution is not correct, as I've pointed out.
zewsx00
24.06.2023 11:02
CANBANKAN wrote: Rephrased problem: Let $n$ be an odd integer. Consider a hamilton path on $(\mathbb{Z}/n\mathbb{Z})^2$ where I can only go to $(x+1,y)$ or $(x,y+1)$ from $(x,y)$. A hamilton path started on $(0,0)$. Prove that if it ends on $(a,b)$ where $0\le a,b<n$, then $a,b$ are even.
By analyzing $x+y$ in $\mathbb{Z}/n\mathbb{Z}$, we can see the destination square has $x+y=-1$. Say $(x,y)$ points right if $(x,y)$ goes to $(x+1,y)$, and say it points up otherwise.
Fix $j \in \{0,\cdots, n-2\}$, all squares $(x,y)$ on the line $x+y=j$ in $\mathbb{Z}/n\mathbb{Z}$, point in the same direction (possibly depending on $j$).
Fix $j$. Suppose $x+y=j$ and WLOG $(x,y)$ points up to $(x,y+1)$. Since $(x-1, y+1)$ is not the end point, it must point to something, namely $(x-1,y+2)$ since it can't point to $(x,y+1)$. We can then induct on $k$ to see that $(x_e-k, y_e+k)$ points to $(x_e-k, y_e+k+1)$. This works because all points on $x+y=j$ need to point to something as they are not the endpoint.
Now suppose $(x,y)$ where $x+y=n-1$ is the endpoint. WLOG $x,y\ne 0$, or we are done. Thus $(0,n-1)$ points right since nothing points to $(0,0)$. By induction on $k$ we can see that $(k,n-1-k)$ points right for $k=1,2,\cdots,x-1$. Also $(n-1,0)$ points up since nothing points to $(0,0)$. By induction on $k$ we can see that $(n-1-k,k)$ points up for $k=1,\cdots,y-1$.
Hence I arrive at the following problem:
Consider a path on $\mathbb{Z}/n\mathbb{Z}$ starting at 0, and from $x$ I go to $x+a+1$ if $R(x+a,n) \in \{0,\cdots,x_e-1\}$, and go to $x+a$ otherwise if $x+a$ is among $\{x_e+1, \cdots, n-1\}$. I need to make sure this path visits all elements of $\mathbb{Z}/n\mathbb{Z}$ in $n$ numbers (counting the initial 0).
As suggested by a22886, consider a permutation of $\{0,1,\cdots,n-1\}$ with the hamilton path and $x_e-a\to 0$. Since this permutation is an odd cycle, it's an even permutation. However, it is also $\pi_1 \circ \pi_2$ where $\pi_2(x)=x+a$ and $\pi_1 = (0 1 \cdots x_e)$. Hence $sgn(\pi_1) sgn(\pi_2) = 1$. Note that $\pi_2$ decomposes $\mathbb{Z}/n\mathbb{Z}$ into cycles of length $\gcd(a,n)$ which is odd, so $\pi_2$ is an even permutation. $sgn(\pi_1) = (-1)^{x_e}$, so $x_e$ is even.
Nice solution!
Sourorange
16.07.2023 07:00
CANBANKAN wrote: Sourorange wrote: starchan wrote: Solved with L567, M.V. Adhitya and Siddharth03 /quote] Nice solution. But...... Can you define salty and sugar further? The solution is not correct, as I've pointed out. Yep I think so. Thanks CBK!
thewizard369
21.07.2023 02:51
i find the problems from russian olympiad really intersting . they are banned or not from the imo by the way
IAmTheHazard
29.07.2023 03:52
Almost the same setup as AIME I 2023/14, although more is needed to solve this problem
CANBANKAN
29.07.2023 06:19
Much more. AIME I 23/14 is the easy part of the problem.
cursed_tangent1434
03.04.2024 20:10
Solved with kingu who came up with the idea of representing the games as ordered pairs and simply thinking of switches. Why is our solution much simpler than the previous solutions? We represent each game as an ordered pair $(G,B)$ where $G$ is the number of the girl playing and $B$ the number of the boy. For example, the first game will correspond to the pair $(1,1)$. Claim : If the final game is $(g,b)$ then, $g\equiv b \pmod{2}$. Proof : We observe that after each game, the game changes from $(x,y) \to (x',y')$ such that $x'+y' \equiv x+y+1 \pmod{n}$ throughout all possibilities. This means, at the final position, $(g,b)$ we must have $g+b \equiv 1 \pmod{n}$ (since we start with a sum of 2, and there are $n^2$ games). Now, since $g+b \geq2$ and $g+b\leq2n$, we must have $g+b=n+1$, which is an even number. Thus, it follows that $g\equiv b \pmod{2}$ as claimed. Now, we only need to exclude the case when $g\equiv b \equiv 0 \pmod{2}$. For this, we make the simple observation that, after $n$ loses for each side (girls or boys - separately) then, the player of that side who is playing the current match becomes $1$. Thus, if at the end of all $n^2$ matches if the girls suffered $M \equiv m \pmod{n}$ loses and the boys suffered $K\equiv k \pmod{n}$ loses we immediately notice that $m+k \equiv 0 \pmod{n}$ since there are total $n^2$ matches for someone to lose. Now, assume that it is possible for $g$ to be even. It immediately follows that $m$ is odd (we start from 1 and the final player number must be $m+1 \pmod{n}$). Then, we have that $m\geq 1$ and $m\leq n-2$. So, $m+k \geq 2$ and $m+k \leq 2n-2$. But since we established before that $m+k \equiv 0 \pmod{n}$, we must have $m+k =n$ from which it follows that $k$ is even, since $m$ is odd. But this means, the final player number of the boys $b = k+1$ which is obviously odd. But this is a clear contradiction to our previous claim. Thus, our assumption must have been false and it is indeed impossible for $g$ to be even. The only remaining possibility is for both $g$ and $b$ to be odd which is indeed what we desired to have.
Zhaom
20.10.2024 08:44
For the match between girl $j$ and boy $k$ with $j,k\in\left\{1,2,\cdots,n\right\}$, we will associate it with $(j,k)$ with the positive $x$ direction being right and the positive $y$ direction being up. Then, the sequence of games corresponds to a nonintersecting path on the $n$ by $n$ grid of $(j,k)$ with $j,k\in\left\{1,2,\cdots,n\right\}$ covering all elements with $(j,k)$ going to $(j,k+1)$ or $(j+1,k)$ for $j,k\in\left\{1,2,\cdots,n\right\}$ wrapping around from $n+1$ to $1$ if $j+1=n+1$ or $k+1=n+1$ starting on $(1,1)$. We want to show that the path ends on $(j,k)$ for $j$ and $k$ odd positive integers at most $n$. Consider deleting the connections between two consecutive games if they wrap around. Then, we end up with some number of nonintersecting paths which go only right and up which cover the grid. For each path, let its lower left endpoint be its start and let its upper right endpoint be its end. Furthermore, consider the graph on the endpoints of all paths so that two endpoints are connected if and only if they correspond to consecutive games such that the original path wraps around or they are endpoints of the same new path. This must be a single path. Also, we will say that a path is after another one if it corresponds to games played later. Claim $1$. We have that the start of any path is on the left or bottom edge of the grid including all relevant corners and the end of any path which is not the last path is on the right or top edge of the grid including the upper right corner and no other corners. Proof. The start of the first path is the lower left corner. Then, the start of any subsequent path must be the result after wrapping around, so the start of any path is on the left or bottom edge of the grid including all relevant corners. From the end of any path which is not the last path, we must be able to wrap around. This cannot include the upper left or bottom right corners since wrapping around would result in going to the lower left corner, which corresponds to the first game, a contradiction, so the end of any path which is not the last path is on the right or top edge of the grid including the upper right corner and no other corners. Claim $2$. There are exactly $n$ paths. Proof. Consider the diagonal $A$ of points of the grid from the top left to the bottom right corners and consider the diagonal $B$ of points of the grid directly above the points of diagonal $A$, so that there are $n$ points in $A$ and $n-1$ points in $B$. Note that each path intersects $A$ at at most $1$ point. Since the paths must cover $A$ there must be at least $n$ paths. However, each path other than the last one must intersect $B$ at at least $1$ point, so the number of paths other than the last one must be at most $n-1$. This implies that there must be exactly $n$ paths. Now, note that for equality to hold for claim $2$, each path must intersect $A$ at exactly $1$ point and the last path must not intersect $B$. This implies that the last path ends on a point in $A$. Now, consider the set of all starts of paths. Number these counterclockwise starting from the top left corner from $1$ to $n$. For each start of a path that is not the lower left corner, number the end of a path which corresponds to the previous game played before wrapping around with the same number. Let the lower left corner be numbered with $a$ and let the start of the last path be numbered with $b$. Now, we see that since the paths cover the grid and do not intersect, we must connect the $k$th start of a path other than the one numbered with $b$ going counterclockwise from the top left with the $k$th numbered end of a path going clockwise from the top left. In particular, let $f$ be the permutation of $1,2,\cdots,n$ so that $f(x)=y$ if the path with start numbered $x$ has an end numbered $y$ for $x=1,2,\cdots,n$ with $x\ne{}b$ and $f(b)=a$. Then, we must have that $f$ is the result of performing the permutation $\sigma$ sending $1,2,3,\cdots,n$ to $a+1,a+2,\cdots,n,1,2,\cdots,a$ and then the permutation swapping $b$ and $n$ and fixing all other positive integers at most $n$. Now, note that $f$ must be a cycle of length $n$ since traversing the sequence of games must traverse $a,f(a),\cdots,f^{n-1}(a)$ as the starts of paths in that order. This implies that $f$ is even. Since $\sigma$ is even since it has $a(n-a)\equiv0\pmod{2}$ inversions, the permutation swapping $b$ and $n$ must be even. This implies that $b$ is odd. Now, consider the intersections of the paths with starts numbered $1,2,\cdots,n$ with $A$. Since the paths do not intersect, these intersections must be in order starting from the top left corner and ending with the bottom right corner. This implies that the intersection of the path with a start numbered $b$, which is the last path, must intersect $A$ at $(b,n+1-b)$, so the girl and boy with numbers $b$ and $n+1-b$, respectively, must play in the last game. Since $b$ and $n+1-b$ are both odd, we are done.