Enigmatic Code

Programming Enigma Puzzles

Enigma 183: The heart has its reasons

From New Scientist #1328, 21st October 1982 [link]

Romeo and Juliet sometimes play a little game of deduction. They extract all the hearts from a pack of cards, discard the ace, shuffle the other 12 and take one each. They look at their own but do not show the other.

Anyone who can prove that his/her own card is the higher must say so at once and scores five points. Anyone who can name the other’s card must do so at once and scores 10 points. The maximum possible score is thus 15. As soon as one player performs either or both of these feats, the other has one further chance to score and the game stops. Neither may lie or suppress information and each knows the other to be a perfect logician. (Any actual proving is done after the game).

Being sporting, they often say a bit more than the mere grunt which the rules require for a player who is in no position to score. For instance, Romeo opened a recent game by remarking:

“I do not know which of us has the higher card.”

“Nor do I,” said Juliet.

“Nor do I,” said Romeo.

“Nor do I,” said Juliet.

“Nor do I,” said Romeo.

At this point Juliet scored and Romeo went on to win the game.

Which card did Romeo hold?

I think this puzzle is flawed, in that there is not a unique answer for the card that Romeo holds.

[enigma183]

Advertisements

6 responses to “Enigma 183: The heart has its reasons

  1. Jim Randell 12 April 2014 at 8:28 am

    I think this puzzle is flawed. Both by hand and by program I get three possible ways for Romeo and Juliet to select their cards for the situation described in the problem to arise, which gives rise to two possible cards for Romeo.

    This Python program runs in 40ms.

    # possible statements are:
    # 1 = "I don't know who has the higher card"
    # 2 = "I have the higher card" (5 points)
    # 3 = "Your card is..." (10 points)
    # 0 = None of the above
    #
    # so possible utterances are: 0, 1, 2, 3, 2+3 = 5
    # with corresponding scores:  0, 0, 5, 10, 15
    #
    # only one person is able to declare the higher card, but both can
    # name the others card
    #
    # so, the possible sequences of utterances we're interested in are:
    # R1 J2 R3 J4 R5 J6 R7
    #  1  1  1  1  1  2  3
    #  1  1  1  1  1  3  5
    # (as J6 must score, and R7 must score more than J6)
    
    from itertools import product
    from enigma import irange, diff, printf
    
    # possible cards
    cards = list(irange(2, 13))
    
    # Xs and Ys are the possibilities for X and Y
    # it's X's turn and he is to make utterance sX
    def turn(Xs, Ys, sX):
      # accumulate possible values for X
      xs = list()
      # consider possiblities for X
      for X in Xs:
        # X knows that Y can't have his card
        ys = diff(Ys, [X])
        if len(ys) < 1: continue
        # so what are the possible utterances?
        s = 0
        if len(ys) == 1:
          # X can name Y's card
          s += 3
        if X > max(ys):
          # X has the higher card
          s += 2
        elif not(X < min(ys)):
          # X doesn't know who has the higher card
          s += 1
        if s == sX:
          xs.append(X)
      return xs
    
    # play a game with the required utterances and return the
    # resulting possibilities for the cards
    def play(ss):
      Xs = Ys = cards
      for s in ss:
        (Xs, Ys) = (Ys, turn(Xs, Ys, s))
      # return the cards in the right order (player 1 first)
      return ((Ys, Xs) if len(ss) % 2 else (Xs, Ys))
    
    # consider both possible sequences of utterances
    for ss in ((1, 1, 1, 1, 1, 2, 3), (1, 1, 1, 1, 1, 3, 5)):
      for (R, J) in product(*play(ss)):
        printf("R={R} J={J} {ss}")
    

    Solution: Romeo holds 7 or 8. The published answer is 8.

    There are three ways of selecting the cards:

    1. Romeo has 7, Juliet has 9. Juliet declares the higher card for 5 points. Romeo declares Juliet’s card and wins by 10 points to 5.
    2. Romeo has 8, Juliet has 9. Juliet declares the higher card for 5 points. Romeo declares Juliet’s card and wins by 10 points to 5.
    3. Romeo has 8, Juliet has 7. Juliet declares Romeo’s card for 10 points. Romeo declares the higher card, and Juliet’s card and wins by 15 points to 10.

    If anyone can see a way of eliminating the possibility of Romeo holding 7 please let me know.

  2. Brian Gladman 13 April 2014 at 2:43 pm

    I probably have this wrong but …

    At the point just before Juliet’s score both know that Romeo has 7 or 8 and Juliet has 6, 7, 8 or 9. To score at this point Juliet must know that she has the highest card so must have either 8 or 9. If Romeo has 7 he can’t declare Juliet’s card as he doesn’t know whether it is 8 or 9. But he does declare it so he must hold 8 and Juliet must hold 9.

    • Brian Gladman 13 April 2014 at 2:55 pm

      Thinking some more … if Juliet holds 8 she can announce Romeo’s card as 7 but she doesn’t so she holds 9, which Romeo can hence deduce.

    • Jim Randell 13 April 2014 at 3:29 pm

      The way I saw it was that we get to a point where (to an external observer) Romeo’s card has been narrowed down to 7 or 8, and Juliet’s card has been narrowed down to 6, 7, 8 or 9. (Of course each player knows what their own card is).

      Juliet scores at this point.

      – If she was holding 6 she would know Romeo’s card must be higher, but she would not be able to name Romeo’s card, and cannot prove her card is higher (as it isn’t), so she cannot score in this case.

      – If she were holding 7, then she would know that Romeo’s card must be 8, so she can declare this for 10 points. But she cannot prove her card is higher (as it isn’t).

      – If she were holding 8, then she would know that Romeo’s card must be 7, so she can declare this for 10 points, and can also prove that her card is higher and score an additional 5 points, for an unbeatable 15 points altogether.

      – If she were holding 9, then she can prove her card is higher and declare this for 5 points. But she cannot name Romeo’s card.

      So Juliet is holding 7 (and scores 10 points) or 9 (and scores 5 points).

      Romeo now goes on to win the game.

      – If Juliet scored 10 points, then she is holding the 7, and Romeo is holding the 8. He can name Juliet’s card (for 10 points) and show that his card his higher (for 5 points) and so score 15 points and win the game.

      – If Juliet scored 5 points, then she is holding the 9, and Romeo is holding 7 or 8. In either case he can name Juliet’s card (for 10 points), but he cannot show his card is higher (as it isn’t), but still wins the game by 10 points to 5.

      Which gives me the same three ways of selecting the cards that I found above:

      1. Juliet holds 7, Romeo holds 8. Juliet names Romeo’s card for 10 points. Romeo names Juliet’s card and shows his is higher for 15 points.

      2 and 3. Juliet holds 9, Romeo holds 7 or 8. Juliet can show her card is higher for 5 points. Romeo can name Juliet’s card for 10 points.

      • Brian Gladman 13 April 2014 at 3:50 pm

        I agree, I wrongly assumed that Juliet’s score was for highest card but it doesn’t say this. Maybe it should have.

        • Jim Randell 14 April 2014 at 10:43 am

          I think there is a way of salvaging the puzzle. If the problem had said “At this point Juliet named Romeo’s card, but Romeo went on to win the game” (instead of “At this point Juliet scored and Romeo went on to win the game”) then we could narrow it down to: Juliet holds 7, Romeo holds 8 (which does give the required answer).

          If Juliet scores by declaring the higher card then she must be holding 9, but Romeo could be holding 7 or 8, so it still doesn’t give us a unique answer for Romeo.

          I wonder if anyone noticed this problem at the time though. I didn’t find a correction published in the subsequent issues of New Scientist.

          In the course of constructing this archive of puzzles I’ve found several that appear to be flawed, and only a few of them have had published corrections.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: