Two players - Andriy and Olesya play the following game. On a table there is a round cake, which is cut by one of the players into $2n$ ($n>1$) sectors (pieces), pairwise distinct in weights. Weight of each piece is known to both players. Then they take pieces according to the following rules. At first, Olesya takes $1$ piece, then Andriy takes $2$ pieces such that the remaining pieces form a sector. Then they in turns take $2$ pieces such that after each turn the remaining pieces form a sector. In their last move, one of the players takes one last piece. Each of the players aims to get more of a cake than the opponent. For which $n$ can Olesya cut the cake such that she wins if in her first move she takes the smallest piece? Proposed by Bohdan Rublyov
Problem
Source: Ukrainian mathematical olympiad 2018 11.4
Tags: Game Theory, combinatorics
23.07.2018 08:53
Not quite a piece of cake...
23.07.2018 20:28
srr.....
23.07.2018 21:25
I'm not very sure what the poster in #3 is trying to say in the case where $2 \mid n$, but something must have gotten wrong there because I think the answer is for all $n \ne 2, 4$. Instead of a cake, we'll deal with a circle of positive reals (representing the weights of the sectors). Note that we can add an arbitrary constant to each real without affecting any strategy considerations, so I'll go ahead and subtract the minimum from each value, so the new minimum is $0$. Since $A$ is forced to start with this piece, we can just consider the game from there on. In effect, we've got a line of $2n-1$ distinct reals ($a_1, a_2, ..., a_{2n-1}$), and we're taking $2$ at a time from the ends, except for the last move, in which the last player just takes the remaining number. As before, anyone with strictly greater than half of the total wins. For $n$ odd, $A$ can let $a_3$ be $10^N$ for some really large $N$, and the other numbers be negligible, like $1, 2,...$ etc., such that $a_3$ is strictly greater than half the total. If $B$ ever takes $a_1$, $A$ can take $a_3$ on the next move and win ($B$ can't take $a_1$ and $a_3$ on the same move, and she can't stop $A$ from taking $a_3$). Hence $B$ can only take from the right (the end with the higher indices). $A$ will follow, also just taking the $2$ rightmost numbers. Due to the parity of $n$, it will be $B$'s move when only $a_1, a_2, ..., a_5$ are left. $A$ will then take $a_3$ on the next move. For $n = 2$, $B$ just takes the two largest numbers. She can take any of the $3$ possible pairs of numbers, so she can do so. For $2 \mid n$, $n \ge 6$, $A$ can let $a_3 = 10^{N}+2, a_{2n-3} = 10^{N} + 1, a_5 = 10^{N}$ for some big $N$, and the rest be around $1$. We want $N$ to be big enough so the other numbers don't matter, so the total is approximately $3 \cdot 10^{N}$. Whatever $B$ takes on her first move ($(a_1, a_2), (a_1, a_{2n-1}), (a_{2n-1}, a_{2n-2})$), $A$ can either take $a_3$ and leave the right end with $a_{2n-1}$ taken, or take $a_{2n-1}$ and leave the left end with $a_1$ taken. $B$ is then forced to take whichever of $a_3$ and $a_{2n-3}$ hasn't been taken, else $A$ will, bringing his total up to $2 \cdot 10^{N}$, which is way more than half the total. This leaves the board with $3$ numbers taken from both ends. $A$ then takes $a_5$, which, again, brings his total up to $2 \cdot 10^{N}$. Finally, for $n = 4$, some casebash. Suppose $A$ has a winning strategy. We call $(a,b,c)$, for $a, b, c \in [1, 7]$, a winner if the sum of $a_a, a_b, a_c$ is strictly greater than half the total, and a loser otherwise. This means that, regardless of what $B$ takes, $A$'s three numbers must end up being a winner. Also, $B$ cannot have a winner as a subset of the $4$ numbers she collects, else clearly $A$ would have less than half the total. If $B$ takes $(1, 2)$, $A$ cannot stop her from taking $5$ her next turn, so $(1, 2, 5)$ must be a loser. Similarly, $(1, 4, 7)$ and $(3, 6, 7)$ are losers. If $B$ starts with $(1, 2)$, $A$ must respond with $(3,4)$, else $B$ can force him to end with $(3, 6, 7)$, a loser. After this, $B$ can force him to take whichever of $a_5, a_6, a_7$ is the lowest. Hence, $(3, 4, 5)$, $(3, 4, 6)$ and $(3, 4, 7)$ are all winners. By symmetry, $(1, 4, 5)$, $(2, 4, 5)$ and $(3, 4, 5)$ are all winners. But then, if $B$ starts with $(1, 7)$, $A$ can't stop her from taking either $(1, 4, 5)$ (which necessitates him taking $(5, 6)$), or $(3, 4, 7)$ (which necessitates him taking $(2,3)$). Hence $B$ can always pick up a winner, and thus, well, wins.