Enigmatic Code

Programming Enigma Puzzles

Enigma 1126: Enigmatic dice

From New Scientist #2282, 17th March 2001 [link]

George has been winning free drinks at his local pub using a trick with four non-standard dice. Each face of each die is marked with one of the numbers 1 to 9, not necessarily all different. One of the nine numbers does not appear on any die, but each die has the same total of its six faces.

George allows you to choose one die, then he chooses one of the others. The two selected die are thrown simultaneously, and the one who throws the smaller number buys the drinks. Draws are impossible.

His friends have discovered that if they choose the red die, George chooses the yellow — if they choose yellow, George chooses green — if they choose green, George chooses blue — and if they choose blue, George chooses red! George expects (statistically) to win exactly two throws in every three with any of these pairs of dice.

We can conveniently represent the markings on a die as a six-digit number, with the digits in ascending order. You can check that 334455 beats 222288 two-to-one, but George’s set does not include either of these dice. The red die includes at least one lucky seven. There is only one set of four dice which will do the trick.

List the six numbers for each of the four colours.

[enigma1126]

Advertisements

7 responses to “Enigma 1126: Enigmatic dice

  1. Jim Randell 3 March 2017 at 7:25 am

    Update: This comment has been updated to correct an error in my program which was discarding some solutions. Thanks to Brian for finding the bug.

    We have previously explored a non-transitive game in Enigma 287.

    This Python program runs in 486ms.

    from itertools import product, combinations_with_replacement
    from collections import defaultdict
    from enigma import compare, irange, printf
    
    # determine outcomes for dice a and b
    # A, B - are sequences of 6 numbers representing the dice
    # returns a triple (<A wins>, <B wins>, <draws>)
    def dice(A, B):
      s = [0, 0, 0] # [<B wins>, <draw>, <A wins>]
      for (a, b) in product(A, B):
        s[compare(a, b) + 1] += 1
      return (s[2], s[0], s[1])
    
    # check the example given
    assert dice((3, 3, 4, 4, 5, 5), (2, 2, 2, 2, 8, 8)) == (24, 12, 0)
    
    # make a non-transitive set of n dice from ds
    def solve(ds, n, s=[]):
      if n == 0:
        # check the loop
        if dice(s[0], s[-1]) == (24, 12, 0):
          yield s
      else:
        # choose the next die
        for d in ds:
          if s:
            # remove duplicate solutions
            if s[0] > d: continue
            # each dice should beat the previous one
            if dice(d, s[-1]) != (24, 12, 0): continue
          yield from solve(ds, n - 1, s + [d])
    
    # record dice by the total sum
    ds = defaultdict(list)
    for d in combinations_with_replacement(irange(1, 9), 6):
      ds[sum(d)].append(d)
    
    # find non-transitive sets
    for (k, vs) in ds.items():
      if len(vs) < 4: continue
      for s in solve(vs, 4):
        # check criteria:
        # 334455 and 222288 are not included in the set
        if (3, 3, 4, 4, 5, 5) in s or (2, 2, 2, 2, 8, 8) in s: continue
        # one number does not appear on any of the dice
        xs = set().union(*s)
        if len(xs) != 8: continue
        # but (at least) one die has 7 on it
        if 7 not in xs: continue
    
        printf("sum = {k}: {s}")
    

    Solution: The numbers on the dice are:

    Red = (1 1 7 7 7 7)
    Yellow = (2 2 2 8 8 8)
    Green = (3 3 3 3 9 9)
    Blue = (4 4 4 6 6 6)

    The digit 5 does not appear on any of the dice.

    Each die has a total face sum of 30.

    Without the restriction that exactly one digit remains unused there are three further arrangements for the Blue die that work with the remaining dice to give a non-transitive set:

    Blue = (4 4 5 5 6 6) – all digits are used
    Blue = (4 5 5 5 5 6) – all digits are used
    Blue = (5 5 5 5 5 5) – digits 4 and 6 are unused

    Removing the restriction that 7 must appear on (at least) one of the dice does not add any more sets. Nor does removing the exclusion of the dice given as an example (which both have a total face sum of 24).

    Update: The following has been updated to correct an error in my program which was discarding some solutions. Thanks to Brian for finding the bug.

    Using the last of the above options for the Blue die allows the set to be expanded to four sets of 5 non-transitive dice:

    (1 1 7 7 7 7) (2 2 2 8 8 8) (3 3 3 3 9 9) (4 4 4 4 6 8) (5 5 5 5 5 5)
    (1 1 7 7 7 7) (2 2 2 8 8 8) (3 3 3 3 9 9) (4 4 4 4 7 7) (5 5 5 5 5 5)
    (1 1 7 7 7 7) (2 2 2 8 8 8) (3 3 3 3 9 9) (5 5 5 5 5 5) (2 4 6 6 6 6)
    (1 1 7 7 7 7) (2 2 2 8 8 8) (3 3 3 3 9 9) (5 5 5 5 5 5) (3 3 6 6 6 6)

    The first two sets have an extra die inserted between Green and Blue, the second two sets have the extra die inserted between Blue and Red.

    More details on non-transitive dice: [ https://en.wikipedia.org/wiki/Nontransitive_dice ].

  2. Hugh Casement 3 March 2017 at 1:14 pm

    Is a ring of six (or even more) dice possible?

    • Jim Randell 3 March 2017 at 2:19 pm

      Update: See my clarification comment below.

      With the restrictions that there should be no draws and each die should win twice as often as it loses against the previous die, then the 4 sets of 4 dice and the 2 sets of 5 dice given above are the only solutions.

      If however we only require each die to be “better” than the previous die, then are many solutions for sets of 3, 4 and 5 dice, and a few solutions for sets of 6 dice.

      And if we allow draws (which are resolved in the game by rolling again, until someone eventually wins) then we can get sets with larger numbers of dice.

      • Brian Gladman 3 March 2017 at 7:24 pm

        Jim, Are you sure about lines 27/28 in your code? I don’t apply this constraint and I get four dice sequences for five non-transitive dice (with draws and 2/3 chance of winning).

        • Jim Randell 3 March 2017 at 10:00 pm

          Yes, you are right. I’d intended that line to remove duplicate solutions by requiring the “lowest” (lexicographically ordered) die to appear first, but it’s more restrictive than that. It should be checking s[0] (not s[-1]).

          Correcting this there are 4 sets of 5 non-transitive dice with no draws and the best die winning 2 out of 3 games. There are also 4 sets of 6 non-transitive dice under the same condition.

          I shall correct my comment above.

      • Jim Randell 4 March 2017 at 9:52 am

        To clarify my earlier comment on larger sets of non-transitive dice, in the light of the error in my program which was discarding some solutions. (Thanks to Brian for finding it).

        If we are looking for sets of different dice with the same total face sum that form a non-transitive loop, where there are no draws and each dice beats the previous one two out of three times, then there are four sets of 4 dice, four sets of 5 dice and four sets of 6 dice. Each set has a total face sum of 30.

        Each set of dice includes the following three dice (the Red, Yellow and Green dice from the solution to the puzzle):

        T = (1 1 7 7 7 7) (2 2 2 8 8 8) (3 3 3 3 9 9)

        The sets are then:

        T + (4 4 4 6 6 6)
        T + (4 4 5 5 6 6)
        T + (4 5 5 5 5 6)
        T + (5 5 5 5 5 5)

        T + (4 4 4 4 6 8) (5 5 5 5 5 5)
        T + (4 4 4 4 7 7) (5 5 5 5 5 5)
        T + (5 5 5 5 5 5) (2 4 6 6 6 6)
        T + (5 5 5 5 5 5) (3 3 6 6 6 6)

        (The second and fourth of these also satisfy the condition that exactly one of the digits remain unused).

        T + (4 4 4 4 6 8) (5 5 5 5 5 5) (2 4 6 6 6 6)
        T + (4 4 4 4 6 8) (5 5 5 5 5 5) (3 3 6 6 6 6)
        T + (4 4 4 4 7 7) (5 5 5 5 5 5) (2 4 6 6 6 6)
        T + (4 4 4 4 7 7) (5 5 5 5 5 5) (3 3 6 6 6 6)

        There are no larger sets.

        However, if we don’t require all the dice to be different we can make larger sets by just going round the loop more than once, and as the sets above have dice in common we can join multiple different loops together to make longer loops (for example, joining at set of 4 and a set of 5 to make a set of 9).

  3. Brian Gladman 3 March 2017 at 7:10 pm

    This is similar to Jim’s version but has (at least) one subtle difference.

    from itertools import combinations_with_replacement, product
    from collections import defaultdict
    
    # return true if die <a> beats die <b> by 2 to 1 with no draws
    def wins(a, b):
      wdl = [0] * 3
      for x, y in product(a, b):
        wdl[0 if x > y else 1 if x == y else 2] += 1
      return wdl == [24, 0, 12]
    
    # find a sequence of  non-transitive dice which each die
    # beats the previous die in the sequence and the first die
    # beats the last one
    def find(dice, n, ds):
      # if we have all the dice needed
      if len(ds) == n:
        # ... return the sequence if the first die beats the last
        if wins(ds[0], ds[-1]):
          yield ds
      else:
        # add another die
        for d in dice:
          # ... if it wins over the previous die in the sequence
          if wins(d, ds[-1]):
            yield from find(dice.difference([d]), n, ds + [d])
    
    # form the set of possible dice indexed on their face sums
    dice = defaultdict(set)
    for ds in combinations_with_replacement(set(range(1, 10)), 6):
      dice[sum(ds)].add(ds)
    
    # consider sets of dice with the same face sums
    for s, ds in dice.items():
      # we need four dice (the face sum 24 is excluded)
      if s != 24 and len(ds) >= 4:
        for d in ds:
          # we need a (red) die with a face value of 7 
          if 7 in d:
            # find sequences of four non-transitive dice
            for d4 in find(ds, 4, [d]):
              # find a sequence with one unused digit
              if len(set(range(1, 10)).difference(set().union(*d4))) == 1:
                print('Red {}, Yellow {}, Green {}, Blue {}'.format(*d4))
    

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: