Enigmatic Code

Programming Enigma Puzzles

Enigma 1240: Stack ’em high

From New Scientist #2396, 24th May 2003 [link]

Joe’s daughter likes puzzles just as much as her father and spends quite some time designing her own.

Last weekend, while just fiddling with some standard dice, she worked out that she could stack them, one on one, so that the total obtained from the numbers on one face of the stack was the same for all four faces when she used the following rule:

Take the number on one face of the first dice, add to it twice the number on the corresponding face on the second dice, three times the number on the third dice, and so on.

She made a stack and showed it to her father. After some thought and a few calculations, Joe told her that by adding a few more dice his total would be six times hers.

How many extra dice did Joe have in mind?

[enigma1240]

Advertisements

3 responses to “Enigma 1240: Stack ’em high

  1. Jim Randell 17 April 2015 at 7:55 am

    If we consider one face of the stack, (a1, a2, …, an). Then the opposite face is (7 – a1, 7 – a2, …, 7 – an).

    These two faces must have the same sum, S, (using the measure given in the problem):

    S = 1×a1 + 2×a2 + … + n×an = 1×(7 – a1) + 2×(7 – a2) + … + n×(7 – an)

    S = a1 + 2×a2 + … + n×an = (7/2) T(n)

    So the sum only depends on the number of layers in the stack:

    S(n) = (7/2) T(n)

    and is only achievable for those n when T(n) is even.

    This Python 3 program looks for possible numbers as a candidate solution, and then constructs an example stack. It runs in 54ms.

    from itertools import count
    from enigma import printf
    
    # generate possible stack sizes and sums for joe and daughter
    def generate():
      # record sums, ss: sum -> n
      ss = dict()
    
      # consider stacks of size n
      t = 0
      for n in count(1):
        t += n
        # the sum is 7/2 T(n)
        (s, r) = divmod(7 * t, 2)
        if r > 0: continue
        ss[s] = n
        # have we already found a stack with a sum of s/6 
        (s6, r) = divmod(s, 6)
        if r > 0: continue
        n6 = ss.get(s6, 0)
        if n6 > 0:
          yield ((n, s), (n6, s6))
    
    # possible layers in the stack (F, B, L, R)
    faces = (
      (1, 6, 2, 5), (1, 6, 5, 2), (2, 5, 1, 6), (2, 5, 6, 1), (5, 2, 1, 6), (5, 2, 6, 1), (6, 1, 2, 5), (6, 1, 5, 2),
      (1, 6, 3, 4), (1, 6, 4, 3), (3, 4, 1, 6), (3, 4, 6, 1), (4, 3, 1, 6), (4, 3, 6, 1), (6, 1, 3, 4), (6, 1, 4, 3),
      (2, 5, 3, 4), (2, 5, 4, 3), (3, 4, 2, 5), (3, 4, 5, 2), (4, 3, 2, 5), (4, 3, 5, 2), (5, 2, 3, 4), (5, 2, 4, 3),
    )
    
    # first layer
    faces0 = faces[::8]
    
    # generate stacks of size <n>, starting with <s>, face sums <ss>
    def stack(n, s, ss, flag=True):
      # are we done?
      m = len(s)
      if m == n:
        (F, B, L, R) = ss
        if F == B == L == R:
          yield s
      elif m < n:
        # add a layer
        m += 1
        for f in (faces0 if flag else faces):
          # calculate the new sums
          ss2 = tuple(x + m * y for (x, y) in zip(ss, f))
          yield from stack(n, s + [f], ss2, False)
    
    # find solution stacks for joe and his daughter
    def solve(nj, nd, td):
      # find a stack for the daughter...
      for sd in stack(nd, [], (0, 0, 0, 0)):
        # ... that can be extend to give a stack for joe
        for sj in stack(nj, sd, (td, td, td, td)):
          yield (sd, sj)
    
    # find the first solution
    for ((n, s), (n6, s6)) in generate():
      printf("joe stacks {n}, sum = {s} / daughter stacks {n6}, sum = {s6}")
    
      for (sd, sj) in solve(n, n6, s6):
        printf("daughter = {sd}")
        printf("-> joe = {sj}")
        printf()
        break
      else:
        continue
    
      break
    

    Solution: Joe had 5 extra dice in mind.

    The daughter stacked 3 dice, to give a face sum of 21.

    Joe stacked 8 dice (an extra 5), to give a face sum of 126.

    One example of such a stack is:

       1  2  3 | 4  5  6  7  8
               
    F: 1  1  6 | 1  1  1  6  6
    B: 6  6  1 | 6  6  6  1  1
    L: 2  2  5 | 2  2  2  5  5
    R: 5  5  2 | 5  5  5  2  2

    There are essentially 7 different ways that the daughter could build her stack of 3, and for each of these there are 278 essentially different ways Joe could complete it to give a stack of 8. (If we count reflections/rotations separately this count can by multiplied up considerably).

    The next smallest pair that give a possible solution are when the daughter stacks 143 dice, with a face sum of 36036, and Joe stacks 351 dice (an extra 208), to give a face sum of 216216. But I don’t think such large towers of dice would be feasible.

    Like the example solution given above for 3 and 8, if we can split (1, …, 143) in to two sets that each sum 5148, and (144, …, 351) in to two sets that each sum 25740, then we can easily construct a solution. In both cases the required sum can be achieved from consecutive subsets. The first set can be split into (3, …, 101) and its complement. The second can be split into (155, …, 274) and its complement. So certainly solutions exist.

    In fact if we run the program looking for candidate solutions (without attempting to construct the corresponding towers we get the following values):

       daughter            daughter      joe                  joe
        stacks               sum        stacks                sum
    
           3                  21           8                  126
         143               36036         351               216216
        1420             3531185        3479             21187110
        3380            19998615        8280            119991690
       33463          1959660206       81968          11757961236
     1377883       3322485144251     3375111       19934910865506
    13639640     325569637696170    33410159     1953417826177020
    32459560    1843840368743030    79509360    11063042212458180

    And all of these can be solved using the consecutive subsets approach, so perhaps the problem should have limited the number of dice available to some upper limit less than 143.

  2. Julian Gray 19 April 2015 at 8:46 am

    Or maybe the dice could be specified as 2 cm cubes!

  3. Brian Gladman 21 April 2015 at 5:05 pm

    This solution uses my Python library of number theory algorithms at http://ccgi.gladman.plus.com/wp/?page_id=1500 (the latest version will be needed as I have just updated it as a result of doing this enigma). It is massive overkill to solve what is a simple variant of Pell’s equation but it is there so it might as well be used.

    from sys import exit
    from itertools import permutations
    from number_theory import Qde
    
    # Consider the opposite face sums of N dice with faces x1, x2, .., xn:
    #
    #   x1 + 2.x2 + ... + n.xn = 1.(7 - x1) + 2.(7 - x2) + ... + n.(7 - xn)
    # 
    # which simplifies to:
    # 
    #   (x1 + 2.x2 + ... + n.xn) = 7.(1 + 2 + ... + n) = 7.n.(n + 1) / 4
    #
    # If the daughter's stack has N dice and Joe's M dice (in total):
    #
    #   M.(M + 1) = 6.N.(N + 1)
    #
    # which simplifies to give the quadratic diopphantine equation:
    #
    #    (2.M + 1)^2 - 6.(2.N + 1)^2 = -5
    
    # produce values for M, N and the related face sums 
    def stack_values():
      # the quadratic diophantine equation has two solution classes
      # that have to be interleaved to give increasing size solutions
      s1, s2 = (iter(x) for x in Qde(6, -5))
      # ignore the first solution (1, 1) for the first class
      _ = next(s1)
      while True:
        x, y = next(s1)
        # convert the solution to M and N, and the related sums    
        m, n = (y - 1) // 2, (x - 1) // 2
        u, r = divmod(7 * m * (m + 1), 4)
        v, s = divmod(7 * n * (n + 1), 4)
        if not (r or s):
          yield (m, n, u, v)
        s1, s2 = s2, s1
    
    # given two faces, return the third face anti-clockwise
    # on a western die (clockwise if same is False)
    def die_third_face(first, second, same=True):
      if second in (first, 7 - first):
        raise ValueError
      t, f = min(first, 7 - first), min(second, 7 - second)
      c1 = ((f - t) % 3 == (1 if same else 2))
      c2 = (first < 4) == (second < 4)
      return 6 - t - f if c1 == c2 else t + f + 1
    
    # list the possible combinations of dice faces in the order
    # Front, Back, Left, Right
    faces = []
    for top in range(1, 7):
      for left in set(range(1, 7)).difference([top, 7 - top]):
        front = die_third_face(top, left)
        faces += [(front, 7 - front, left, 7 - left)]
    
    # find a stack of 'e' dice (in 'dice') that give the face
    # sum 'target', starting with 's' dice already placed and
    # the initial face sums in 'sums'
    
    def solve_stack(s, e, target, sums, dice):
      # do we have the right number of dice?
      if s == e:
        # with the right target face sums?
        if all(x == target for x in sums):
          yield dice
      else:
        # add another die
        for f in faces:
          # compute the new face sums
          nsums = [x + (s + 1) * y for x, y in zip(sums, f)]
          # and continue to add more dice if necessary
          yield from solve_stack(s + 1, e, target, nsums, dice + [f])
    
    # produce target values for our stack (daughter 'nd' dice (sum 'sd')
    # Joe 'nj' dice sum 'sj')
    for nd, nj, sd, sj in stack_values():
      print('Daughter: {} dice (sum {}), Joe: {} dice (sum {}), example stacks:'
            .format(nd, sd, nj, sj))
      # try each of the three possible base dice
      for base in ((1, 6, 2, 5), (2, 5, 3, 4), (3, 4, 1, 6)):
        # find solutions for the daughter's stack
        for dd in solve_stack(1, nd, sd, base, [base]):
          print('  Daughter: {}'.format(dd))
          sums = [sd + (nd + 1) * x for x in base]
          # compute the initial sums for Joe's stack
          sms = [sd + (nd + 1) * x for x in base]
          # find solutions for Joe's stack
          for dj in solve_stack(nd + 1, nj, sj, sms, [base]):
            print('  Joe: {}'.format(dj))
            break
      break
    

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: