## Alice and Bob’s card game

Posted by Chris on July 3, 2014 – 8:35 am

Two perfect logicians, Alice and Bob, play a game with 2n blank cards. The cards are numbered with random positive integers and laid out in a row. Alice goes first. She takes a card from either end of the row. The value of that card is added to her score. Bob then takes a card from either end of the remaining row and adds its value to his score. This continues until all the cards have been taken.

Show that Alice can always match or beat Bob’s score.

July 4th, 2014 at 3:46 am

Just a quick question Chris, can they see the value on the cards….? I am assuming they can, or I am going back to the drawing board!

July 4th, 2014 at 3:50 am

There is no hope to talk about strategies if the players don’t see the cards and take them randomly They should definitely have them faced up…

July 4th, 2014 at 6:26 am

I confirm Slavy’s reply – all the numbers are showing.

July 4th, 2014 at 5:16 pm

This problem took me almost an hour, which was quite embarrassing given my education and being a keen chess player Good job, Chris! Bad job, me!

July 5th, 2014 at 8:44 pm

Only an hour. I still haven’t cracked it. Your chess clue fills me with panic. I now suspect that there is no simple strategy and that the entire set of cards has to be considered.

This was a British Maths Olympiad, round 1 question.

July 6th, 2014 at 3:25 am

Yes Chris, you need to consider the entire set of cards. Induction doesn’t work (or at least I failed there). The “chess clue” is more about the board itself than the pieces.

July 8th, 2014 at 2:57 am

Hint: there are two disjoint sets of n elements that Alice could take completely if she wants. She counts the points in each of them and chooses the bigger one. Which are the sets?

July 8th, 2014 at 1:05 pm

And here is a second question: what if there are 2n+1 cards ? What condition ensures that Alice has at least as much as Bob ?

July 12th, 2014 at 6:32 am

OK. I assume the problem got cold already, so let me sketch a proof. Let’s number the cards in order from 1 to 2n. We consider the sets O and E – the first one consists of the cards with odd numbers, while the second one is its compliment and consists of the cards with even numbers. One can even think of the O cards being painted white, while the E cards being painted black. Before start, Alice computes the value of both the sets and chooses to play with the better one. Let’s assume it’s O. At first step she takes card 1. Bob’s both options are even numbers now (2 or 2n) so he takes one of them. This again opens an O card for Alice and so on…

Zorglub’s question is much harder to crack. Of course, one can come up with some very restrictive conditions that are sufficient but very far away from necessary, so I won’t discuss it, yet. The funny part is that although Alice takes a card more, I’m not sure that her position is stronger than Bob’s. For example if both the end cards are of low value and cannot compensate the difference between the values of the corresponding sets O and E of the remaining 2n cards – then Bob is winning…

July 12th, 2014 at 7:23 am

Hi Slavy. I had given up. I should have said so. I love your answer. I now suspect that Zorglub might have known that solution.

July 12th, 2014 at 2:58 pm

Great solution Slavy, once I got that your O and E sets referred to the positions of the cards in the row and not their values.

With 2n+1 cards, after Alice takes the first card Bob is now in the situation that Alice was with 2n cards. If he can find a winning margin between the values in the O and E sets that is greater than the value of the card that Alice took then victory is his for the taking. Alice can only win if her first card has a value greater than the difference between the remaining O and E cards and she then sticks to either O or E throughout the game.

July 12th, 2014 at 5:25 pm

Sorry for that, Wiz! I could have expressed the idea clearer (especially true when using a digit for a set name – O). The odd number case is much trickier, because Bob has the power to chose the O or E set at every step! So even if at the beginning Alice has the opportunity to take the “right” card so that Bob doesn’t immediately win, we has the power to switch from O to E (and vice versa) whenever he likes! So, as I said, amazingly enough, being allowed to take a card less and to play after your opponent, puts you in a much stronger position than to be second again but in a “fair card-picking” game!

July 15th, 2014 at 1:50 pm

When I wrote the 2n+1 generalization, I had the same solution as proposed by Wiz in post 11. Once that Alice picks her first card, Bob has a 2n problem and I assumed that he either picked the O or the E of the remaining cards. That is not an unreasonable assumption, because Bob’s outcome will be Max(O,E). If Bob does not respect his strategy, he might end up with less than that.