Let $n$ be a positive integer. Anna and Beatrice play a game with a deck of $n$ cards labelled with the numbers $1, 2,...,n$. Initially, the deck is shuffled. The players take turns, starting with Anna. At each turn, if $k$ denotes the number written on the topmost card, then the player first looks at all the cards and then rearranges the $k$ topmost cards. If, after rearranging, the topmost card shows the number k again, then the player has lost and the game ends. Otherwise, the turn of the other player begins. Determine, depending on the initial shuffle, if either player has a winning strategy, and if so, who does.
Problem
Source: MEMO 2022 I2
Tags: combinatorics
Tintarn
03.09.2022 21:26
Anna has a winning strategy iff $k$ is not the smallest of the $k$ topmost cards.
Let $W$ be the set of positions where $k$ is not the smallest of the $k$ topmost cards, and $L$ be the complement.
From any position in $L$ we clearly have to move to a position in $W$ as we have to replace the topmost card $k$ by a larger one and then $k$ will be among the visible cards but smaller than the topmost card.
Conversely, from any position in $W$ we can move to a position in $L$ by just choosing the smallest among the visible cards (which by assumption is not the topmost one) and putting it on the top. This will decrease the number of visible cards and hence the condition for $L$ is satisfied.
This already almost proves that the winnining positions are exactly the set $W$, except that we still need to show that the game terminates.
In fact, it is possible to run into a circle, but what we show is that the player in a $W$ position can force the game to end.
Indeed, let us first notice that the smallest among the visible cards never decreases if we follow the strategy described above. So the only option to run into a circle is that it stabilizes at some number $m>1$ (if $m=1$ we are clearly done).
We then show that the player in a $W$ position can force that the sum of the remaining $m-1$ visible cards after his move always strictly increase. Indeed, suppose the $L$ player chooses $x$ as the new topmost card. Then among the newly visible cards, we get to see at least one card strictly larger than $x$. Now $W$ can choose $m$ as the new topmost cards, $m-2$ of the old visible cards and replace $x$ by the new larger one. So he can indeed make the sum always strictly increase. But of course this is nonsense as it is bounded from above. Done!
Toll
15.01.2024 15:08
Consider the following algorithm: Assume that within the first $k$ cards, $k$ is not the smallest card. let $j$ be the smallest card. The Player whose turn it currently is, call it Player 1, now does the following: Place $j$ on the top, and the remaining cards in decreasing order afterwards. We need the following few little remarks: $\textit{claim 1:}$ $k$ is not the largest card in the first $k$ cards $\textit{proof:}$ If $k$ were the largest card within the first $k$ cards, then $1$ must also be one of those cards. But placing $1$ on top instantly wins $\textit{generalised claim:}$ assume $k$ is the $m$'th largest card. then the smallest card has at most value $m$ $\textit{proof:}$ as there are in total $k$ cards within the first $k$ cards, and $m-1$ of those are bigger than $k$, we conclude that $k-m$ of those are smaller than $k$. However, the claim here immediately follows, since there otherwise wouldn't be enough cards But from this claim, it follows that using the above described algorithm for Player $1$ will always result in Player $2$ having to place a card $i$ with $i>k$ on top. This means, Player $1$ has now more cards to work with. Since this is a monovariant, Player $1$ will at some point have the card with value $1$ in the first $k$ cards, and therefore win Since we initially assumed that $k$ is not the smallest card within the first $k$ cards, call the state that Player $1$ finds himself in $\textit{big}$, and the state Player $2$ finds himself forcefully in, $\textit{small}$ Now apply that algorithm on the game with $A$ and $B$. if $A$ starts with a big state, then he can apply the algorithm and therefore eventually win. If $A$ starts in a small state, then $B$ finds himself in a big state the turn afterwards, and can therefore force a win We conclude: $A$ can win if $k$ is not the smallest card within the first $k$ cards, otherwise $B$ wins