This is a reformulation of problem number 3 from the 2018 European Girls Math Olympiad. It took me several days to come up with a complete solution, and I'm wondering if there is an easier way.
Consider a solitaire game with $n$ cards, labeled $1$ though $n$. The cards are shuffled and placed in a line, face up.. If the card labeled $k$ has at least $k$ cards to its left, you are allowed to jump it $k$ places to the left, inserting it into the line. There are no other legal moves.
For example, if $n=7,$ and the layout is $2753146,$ you can jump the $3$, giving $3275146,$ or the $1,$ giving $2751346,$ or the $4$, giving $2475316,$ or the $6,$ giving $6275314.$
The problem is:
1) Show that the game cannot go on forever. Eventually, you must reach a position in which no moves are possible.
2) What is the maximum possible number of jumps in a game with $n$ cards, if the initial position is as advantageous as possible, and you make the best moves?
We have to do three things:
1) Prove that the game cannot last forever.
2) Establish an upper bound on the number of jumps.
3) Construct a game with the maximum number of jumps.
Early on, I decided that the maximum number of jumps is $2^n-(n+1).$ It's not hard to come up with a game of this length. Start with the cards in decreasing order from left to right, and jump until they are in increasing order. To do this, recursively sort the last $n-1$ cards in $2^{n-1}-n$ jumps, then jump the cards from back to front, arriving at the order $$n-1,n-2,\dots,1,n$$ and then recursively reverse the first $n-1$ cards again.
To show that the game cannot go on for ever, I proved the result for a more general game, where the cards are labeled with any $n$ distinct positive integers. Let $N\ge n$ be the largest label. If $N$ is in the rightmost position, it can never move, and the result follows by induction. If $N$ is not in the rightmost position, it is enough to show that the game cannot last forever without $N$ moving to the right, that is, without a card jumping from $N'$s right to its left. This is true by induction trivially for the cards to $N'$s left, and if the $k$ cards to $N'$ right can jump among themselves forever, then the $K-$card game comprising those cards can also last forever, contradicting the induction hypothesis.
The part that gave me the most trouble was establishing that $2^n-(n+1)$ is an upper bound. I realized early on that is the long path I'd constructed, $k$ jumps $2^{n-k}-1$ times. Of course, proving this is true in general is enough to establish the upper bound. It took me quite a while to see how to approach it, but finally I realized that when $k$ jumps, since it moves $k$ positions, it must jump over a number greater than $k$, and that if $K>k,$ then $k$ jumps over $K$ at most $2^{n-K}$ times. I proved this by induction on $n-k$. After $k$ first jumps over $K>k,\ K$ is on the right of $k$. In order for $k$ to jump over $K$ another time, $K$ must first jump over $k$. Then induction hypothesis implies that $K$ jumps at most $2^{n-K}-1$ times, so $k$ can jump over $K$ at most $2^{n-K}$ times.
Do you see a simpler way to do this problem, particularly to establish the upper bound? (Of course, I realize that part 2) implies part 1), but when I was working the problem it seemed natural to prove part 1) independently.)
Notice every time a card jumps, it must jump over a card with higher index. Also, two cards will maintain their relative orientation at least until the rightmost one jumps.
Let $s_k$ denote the maximum amount of jumps the card $n+1-k$ can make, $k\in\{1, 2,\dots, n\}$. Then $s_1=0$ and $$s_{k+1} \le \underbrace{k}_{~~~~~~~~amount~of\\higher-index~cards}+\underbrace{\sum_{j=1}^k s(j)}_{amount~of~times~an\\~higher-index~card\\~~~~~~~~~can~jump}$$ I claim $s_k\le 2^{k-1}-1$. In fact, this is true for $s_1$ and, if $s_j\le 2^j-1,~\forall j\le k$, then $$s_{k+1} \le k+\sum_{j=1}^ks(j)\le k+\sum_{j=1}^k(2^{j-1}-1) = 2^k-1$$ Now, of course, we can see that no game can have more then $$\sum_{j=1}^n s(j)\le \sum_{j=1}^n (2^{j-1}-1) = 2^{n}-(n+1)$$ jumps, and we can show this is, in fact, the desired maximum with the configuration $$n, n-1, \dots, 2, 1.$$