### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,123)
- misc (2)
- project euler (2)
- puzzle (31)
- site news (43)
- tantalizer (31)
- teaser (3)

### Site Stats

- 168,282 hits

Programming Enigma Puzzles

21 September 2015

Posted by on **From New Scientist #2357, 24th August 2002** [link]

Frances and Matthew are playing a game of cards. There are 30 cards in the game, numbered 1, 2, 3, …, 30 and each player has 15 [cards] at the start of the game. Frances has 5, 6, …, 16 and 28, 29, 30, while Matthew has 1, 2, 3, 4 and 17, 18, …, 27.

The game consists of 15 rounds. In each round the player who won the previous round goes first, except that in the first round Frances goes first. A round consists of the players alternately taking a card from their hand and putting it face up on the table. When all cards are on the table, the last two to be put on the table are compared and the player who put the higher of those two cards wins the round. The two cards that were compared are then discarded from the game and the players pick up their remaining cards; they then play the next round. Frances and Matthew are both superb players, playing as well as anyone could.

Question 1:At the end of the game, how many rounds had Frances won?On another occasion they used 100 cards. Frances started with 28, 29, …, 37 and 61, 62, …, 100, and Matthew with the other fifty cards.

Question 2:At the end of the game, how many rounds had Frances won?On a third occasion they used 200 cards. Frances started with 76, 77, …, 130 and 156, 157, …, 200, and Matthew with the other 100 cards.

Question 3:At the end of the game, how many rounds had Frances won?

**Enigma 1252** is also called “Cards on the table”.

[enigma1201]

Advertisements

%d bloggers like this:

First a bit of analysis to simplify the problem.

As the cards are contiguous numbered blocks we can replace these cards by 4 categories:

Where 4 beats (3, 2, 1); 3 beats (2, 1); 2 beats (1).

If we get to a situation where either player holds only one type of card then the result of the remaining rounds is determined.

So the interesting cases are (for the final card):

The only way M can win is if F plays a 2 card and M plays a 3.

The problem is similar to

Enigma 1321. The following Python program examines the possible games for each initial set-up, and at each stage F plays to maximise her score and M plays to minimise F’s score (and so maximise his own score). It analyses all three cases in 2.1s.Solution:(1) Frances wins 7 of the rounds; (2) Frances wins 40 of the rounds; (3) Frances wins 75 of the rounds.Is it possible to come up with a general strategy for the player who goes first in any round?

For example, either to sacrifice the low-scoring cards in the first few rounds, or else to leave them until the end? Or is it more subtle than that?

I haven’t done a deep analysis, but in the three situations given a strategy for Frances seems to be to finish each round with one of her lower scoring cards (the 2’s in my renaming) until those are exhausted. The strategy for Matthew doesn’t seem to be quite so simple.

Thanks, Jim. I feel there’s a certain advantage in losing a round, because then the opponent goes first in the next round and you can see what you’re up against. But I can well believe Frances and Matthew need somewhat different strategies, because the cards are not evenly distributed.

Using Jim’s notation of reducing the cards to 1,2,3,4, the code below calculates the wins if Matthew follows what I think is an optimum strategy.

Frances’ best strategy when leading is to lead a 2, (otherwise leading a 4 will result in Matthew discarding a 1, and Frances still has the lead).

I have checked that the strategy in my code produces the same result as Jim’s minimax search for all combinations of cards in a deck of 100.

There is probably a simpler formula that expresses the number of wins in terms of N1,N2,N3,N4 (the number of cards of value 1,2,3,4 respectively), but that’s for another post, as is a rigorous proof that the strategy in this code is optimal.