7
$\begingroup$

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?

$\endgroup$
10
  • $\begingroup$ So, on Bob's 2nd term, what is left are [for Bob: his 3rd, 4th cards from the original sequence] and [for Alice: her 3rd, 4th cards from the original sequence]. Then, on Bob's 2nd term, he must choose his 4th card, because this card, his 2 is lower than his other remaining card, his 4. This eliminates Alice's 4th card, her 4 (because Bob was forced to take his 4th card). Therefore, on Alice's 2nd turn, all she has left is her 3, so she is forced to take it. Thus, Alice was (in effect) forced to take her 2 and then her 3. Is my understanding correct? $\endgroup$ Oct 1, 2020 at 15:44
  • 1
    $\begingroup$ +1 upvoted - very interesting question. thanks for all of the extra effort. working on it (or perhaps someone else on mathSE will solve it). Now your conjecture, which may or may not be true, seems intuitively reasonable. $\endgroup$ Oct 1, 2020 at 15:49
  • 1
    $\begingroup$ Although I can not solve the problem, I suspect that the conjecture is true. My attack method, which you are welcome to hijack is: assume a sample baseline sequence, like S1 = A,B,B,B,A,A,B,A,B,A. It seems to me that it is sufficient to show that is you select any A-turn in the sequence that has at least 1 B-turn ahead of it (i.e. in S1, that would be the A turns of 5,6,8,10) and permute it with the rightmost B-turn that precedes it, then you have to show that Alice's score does not increase. ...see next comment $\endgroup$ Oct 1, 2020 at 17:13
  • 1
    $\begingroup$ For example, if you happened to select Alice's A-6, the 6th slot in S1, you would permute it with Bob's B-4, the 4th slot in S1. This means that you would have altered S1 into S2 = A,B,B,A,A,B,B,A,B,A. This also means that the cards facing Alice and Bob, just before the 4th turn in the sequence (i.e. Alice's turn in S2), would be identical with the cards before the 4th turn in S1. This is because the first three slots of S1 have not been altered. ...see next comment $\endgroup$ Oct 1, 2020 at 17:15
  • 1
    $\begingroup$ It further seems that if you can demonstrate that this single permutation of one of Alice's turns with the rightmost B-turn that precedes it does not raise her score, then you are done. This is because any allowable permutation on S1 may be viewed as a series of 1 at a time permutations, where the A-turn permutes with the rightmost B-turn that precedes it. This reduces the problem, but still leaves a problem that I personally can not wrap my brain around enough to generate the necessary elegant insight. $\endgroup$ Oct 1, 2020 at 17:15

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I have several questions. 1) How do you show the greedy algorithm is optimal for each player? 2) In the case "Was $a_0<b$?", why do you say "The situation looks like this: $\quad a_0\ldots\ldots\ldots b$." rather than $a_0b$ since after the swap, A should pick $a_0$ and B takes the next turn and should pick $b$ right away. There should not be anything as seems to be indicated by "\ldots" in between $a_0$ and $b$. $\endgroup$
    – Hans
    Oct 15, 2020 at 4:40
  • $\begingroup$ 3) "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$." I do not understand this. After the swap, should the index sequence not be, in terms of the original indices $b\hat b a_0a_1\ldots a_k$? I think I am confused by your indices with the apostrophes: "$a_0^\prime\underbrace{a_1^\prime}_{\text{was }b}a_2^\prime\ldots a_k^\prime \square\cdots\cdots b^\prime $" $\endgroup$
    – Hans
    Oct 15, 2020 at 4:40
  • $\begingroup$ Have you had a chance to review my questions? $\endgroup$
    – Hans
    Oct 16, 2020 at 15:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .