Sum of numbers on cards decreases

Question

Alice and Bob play a game with $n$ cards. Alice writes the numbers $1,2,\ldots,n$ once each, and so does Bob (on the same set of cards). Then, they take turns choosing cards according to some specified sequence. In each turn, the player picks the card with his/her smallest number. At the end of the game, Alice notes the sum of her numbers on her cards.

Afterwards, the specified sequence is modified by moving some of Alice's turns earlier (no other kind of modification is allowed), and the game is repeated in the same way. Is it true that Alice necessarily gets a smaller or equal sum than before?

Example: Alice writes $1, 2, 3, 4$, Bob writes $1, 3, 4, 2$. Originally the sequence is Bob, Alice, Bob, Alice. Bob chooses the 1st card, Alice the 2nd, Bob the 4th (because Bob's number on the 4th card is smaller than on the 3rd), and Alice the 3rd, so Alice gets $2+3=5$. Afterwards, suppose the sequence is modified by moving Alice's first turn to the front, so it is now Alice, Bob, Bob, Alice. Alice chooses the 1st card, Bob the 4th, Bob the 2nd, and Alice the 3rd, so Alice gets $1+3=4$.

To prove that it is true, it would be enough to show that for every $k$, Alice gets a smaller or equal number in her $k$-th turn of the original game than in her $k$-th turn of the modified game. Can this be done possibly by induction?

Answer 1

The theorem is true; Alice's score can only decrease. I don't have an elegant proof, but I can exhaust all cases by careful examination.

Preliminaries: Let's index the cards using Alice's order so that Alice will always choose the leftmost unchosen card. Capital letters like $A_i$ and $B_j$ refer to some specific move during a game. Corresponding lowercase letters like $a_i$ and $b_j$ refer the index of the card that will be chosen during moves $A_i$ and $B_j$, respectively. So if $b_j=4$, it means that during Bob's move $B_j$, Bob will choose the card with index 4 (in terms of Alice's index, by convention.)

As a base case, consider the sequence $\cdots BA$. We are going to swap the order of the final two moves $B$ and $A$. Note that we can simply ignore any of the cards that have been chosen/drawn already; they cannot be affected by this swap. Because this is the end of the game, there are only two unchosen cards.

• Was $a<b$? In this case, the cards are laid out like $a\;b$. Swapping $B$ and $A$ won't matter because both players will prefer their original positions still. Hence Alice's score remains the same.

• Was $b>a$? Then the cards are laid out like $b\;a$. After the swap, Alice will greedily prefer the leftmost unoccupied card and Bob will take the other. Alice chose a strictly lower card after the swap; hence Alice's score will decrease, QED.

As an inductive case, consider the sequence $\cdots BA^{k+1}B\cdots $, which we are going to swap to make $\cdots ABA^{k}B\cdots$. Note that because we started with an interleaved moveset of $A$ and $B$, and we only allow leftward movement of $A$'s, we have certain invariants. In particular, if a sequence of moves allows Alice $k$ consecutive moves, then afterwards, Bob must have at least $k$ moves remaining.

Let's call the indexes of these moves $b, a_0,\ldots,a_k, \hat b$, respectively.

• Was $a_0<b$? The situation looks like this: $\quad a_0\ldots\ldots\ldots b$. If so, then as before, swapping the move order has no effect on the players' preferences and the rest of the game continues exactly as it did initially, with no score change.

• Was $a_0>b$? Because Alice always chooses the leftmost unoccupied card, it must have looked like this: $b \; a_0 a_1a_2\ldots a_k \cdots\cdots\cdots \hat b $. Hence after the swap, Alice will greedily take the leftmost spot in the first move. What will Bob do now? The situation looks like $a_0^\prime \cdots\cdots\cdots\cdots$. There are surprisingly constrained choices.

  • Perhaps Bob's first move is somewhere in the middle of $a_1\ldots a_k$ now that Bob has a chance to move there before Alice does, disrupting where one of the $A_1\ldots A_k$ formerly went. This is not a problem, as all of the $A_i$ can simply slide leftward toward the vacancy that Bob left behind: $$a_0^\prime \underbrace{a_1^\prime}_{\text{was }b} a_2^\prime a_3^\prime\ldots b^\prime \ldots a_k^\prime$$ If you calculate it out, Alice simply gains a lower card at $b$, in exchange for losing a higher card at some $a_i$. Hence Alice's score has decreased. Because all of the same cards were taken after the swap as before, the rest of the game actually continues exactly as before after we finish doing $ABA^k$. Hence Alice's score has only decreased.

  • The only other possibility is that Bob's first move is $\hat b$. It takes some careful consideration to see why. We knew from the original game that Bob preferred $b$ as first pick; but if all of $a_0\ldots a_k$ and $b$ were occupied, Bob's choice was $\hat{b}$ among all remaining cards. After the swap, $b$ is indeed occupied, and we have already considered the case that Bob prefers $a_0\ldots a_k$ when $b$ is already occupied. Hence by Bob's previously expressed preferences, Bob's first move post-swap will be to take $\hat b$.

    Hence when Alice moves, Alice will be able to shift the $A_1\ldots A^k$ leftward, creating a potential new vacancy at $a_k$. $a_0^\prime\underbrace{a_1^\prime}_{\text{was }b}a_2^\prime\ldots a_k^\prime \square\cdots\cdots b^\prime $.

    If this is the case, then for this particular game with Alice and Bob's specific numberings/preferences, the move order $\cdots A\dot{B}A^kB\cdots $ is actually equivalent to $\cdots A^{k+1}B\hat{B}\cdots$— we can "shunt" the $\dot{B}$ all the way down to the end.

    We can now close the inductive step. Bob has just taken $\hat{b}$. Bob's next move might be to fill the vacancy. In this case, the rest of the game must continue the same as it did before from this point on, because we have again succeeded at picking all the same cards as we did in the pre-swap game (Alice and Bob picked different ones than they did before, perhaps, but the point is all the same cards have all been removed from play; we're at a strategically equivalent point going forward.) Hence Alice's score will remain diminished until the end of the game, QED.

    Alternatively—

To be continued.