Enigmatic Code

Programming Enigma Puzzles

Enigma 1290: Marbled patterns

From New Scientist #2448, 22nd May 2004 [link]

I laid out a row of identical saucers and gave my nephew some marbles, all the same. I then set him the following problem:

“If I ask you to place all the marbles in the saucers, with at least one marble in each, in how many ways can this be done?”

After some thought he came to the correct conclusion that there were between a thousand and ten thousand such arrangements, and then he gave up. So I then asked him the following simpler question:

“How many of these arrangements will be symmetrical, in the sense that if I reversed the order of the saucers the pattern remains the same?”

This time he gave the correct answer of 20.

What was the correct answer to the first question?

Note: I am waiting for a phone line to be connected at my new house, so I only have sporadic access to the internet at the moment.

[enigma1290]

Advertisements

5 responses to “Enigma 1290: Marbled patterns

  1. Jim Randell 29 September 2014 at 1:51 pm

    If there is one saucer then there is only one possible arrangement, and it is symmetrical.

    If there are two saucers then there can be at most one symmetrical arrangement, when there are an even number of marbles, with half in each saucer.

    So, this program, which looks for numbers of marbles and saucers with 20 symmetrical arrangements, starts looking from 3 saucers.

    When considering s saucers it looks for m marbles (with m > s) such that there are between 1,000 and 10,000 arrangements (the number of arrangements is strictly increasing with the number of marbles).

    It constructively determines the number of arrangements by counting and runs in 221ms

    from itertools import count
    from collections import defaultdict
    from enigma import irange, cached, printf
    
    # how many arrangements of m marbles in s saucers (m >= s)
    @cached
    def A(m, s):
      # if s = 1 or s = m, there is only one arrangement
      if s == 1 or s == m: return 1
      # choose a number of marbles for the first saucer
      # and arrange the remaining marbles
      return sum(A(m - m1, s - 1) for m1 in irange(1, m - s + 1))
    
    # and how many symmetrical arrangements
    def S(m, s):
      # if there's only s == 1 or s == m there's only 1 arrangement
      if s == 1 or s == m: return 1
      (m2, rm) = divmod(m, 2)
      (s2, rs) = divmod(s, 2)
      # if there's an even number of saucers
      if rs == 0:
        # we need an even number of marbles
        if rm == 1: return 0
        # arrange half the marbles in half the saucers
        return A(m2, s2)
      else:
        # choose how many marbles to place in the central saucer
        # and arrange half the remaining marbles in half the saucers
        return sum(A((m - m1) // 2, s2) for m1 in irange(2 - rm, m - s + 1, step=2))
    
    # accumulate results by A(m, s)
    r = defaultdict(list)
    
    # consider increasing numbers of saucers
    for s in count(3):
      # and possible numbers of marbles (m > s)
      for m in count(s + 1):
        # there should be between 1000 and 10000 arrangements
        a1 = A(m, s)
        if a1 < 1000: continue
        if a1 > 10000: break
        # and 20 symmetrical arrangements
        a2 = S(m, s)
        if a2 != 20: continue
        printf("[{s} saucers, {m} marbles, A={a1}, S={a2}]")
        r[a1].append((m, s))
      # we are done when there are no arrangements below 10000
      if m == s + 1: break
    
    # display the results
    for k in sorted(r.keys()):
      printf("A={k} [{s}]", s=' '.join("m=" + str(m) + ',s=' + str(s) for (m, s) in r[k]))
    

    Solution: The answer to the first question is 1716. (i.e. there are 1716 different ways of arranging the marbles in the saucers).

    This can be achieved with 14 marbles and either 7 or 8 saucers.

    • Jim Randell 29 September 2014 at 1:51 pm

      Here’s an analytic solution:

      It turns out that for 3 saucers the number of arrangements follows the triangular numbers:

      A(n + 3, 3) = T(n + 1) = (n + 2)(n + 1)/2 = C(n + 2, 2)

      For 4 saucers it follows the tetrahedral numbers:

      A(n + 4, 4) = C(n + 3, 3)

      And in general it follows the n-dimensional triangular numbers:

      A(m, s) = C(m – 1, s – 1)

      For the symmetrical case we get:

      S(m, s) = C(m/2 – 1, s/2 – 1) if s is even and m is even
      S(m, s) = C(m/2 – 1, (s – 1)/2) if s is odd and m is even
      S(m, s) = C((m – 1)/2, (s – 1)/2) if s is odd and m is odd
      S(m, s) = 0 if s is even and m is odd

      So if S(m, s) = 20 we need to find p and q where C(p, q) = 20.

      Possible values for (p, q) are (6, 3), (20, 1), (20, 19).

      Case 1: (p, q) = (6, 3) corresponds to (m, s) = (14, 8), (14, 7), (13, 7).

      And A(14, 8) = 1716, A(14, 7) = 1716, A(13, 7) = 924.

      This gives rise to two solutions: (m, s) = (14, 8), (14, 7) in each case A(m, s) = 1716.

      Case 2: (p, q) = (20, 1) corresponds to (m, s) = (42, 4), (42, 3), (41, 3).

      And A(42, 4) = 10660, A(42, 3) = 820, A(41, 3) = 780.

      This gives rise to no further solutions.

      Case 3: (p, q) = (20, 19) corresponds to (m, s) = (42, 40), (42, 39), (41, 39).

      And A(42, 40) = 820, A(42, 39) = 10660, A(41, 39) = 780.

      This also gives rise to no further solutions.

  2. Julian Gray 17 December 2014 at 3:23 pm

    Did anyone else find that 19 marbles and 5 saucers produces 20 palindromic arrangements? I did it the hard way (I’m a mere engineer, or rather I was, and I cannot match Jim’s analytical and programming skills).

  3. Jim Randell 17 December 2014 at 9:11 pm

    If you want to see the possible arrangements here is my program adjusted to print them out:

    from enigma import irange, printf
    
    # generate arrangements of m marbles in s saucers
    def A(m, s):
      if s == 1:
        # 1 saucer, put all the marbles in it
        yield [m]
      elif s == m:
        # same number of saucers and marbles, 1 in each
        yield [1] * s
      else:
        # choose a number of marbles for the first saucer
        for m1 in irange(1, m - s + 1):
          # and arrange the remaining marbles
          for r in A(m - m1, s - 1):
            yield [m1] + r
    
    # generate symmetrical arrangements
    def S(m, s):
      if s == 1:
        # 1 saucer, put all the marbles in it
        yield [m]
      elif s == m:
        # same number of saucers and marbles, 1 in each
        yield [1] * s
      else:
        (m2, rm) = divmod(m, 2)
        (s2, rs) = divmod(s, 2)
        # if there's an even number of saucers
        if rs == 0:
          # we need an even number of marbles
          if rm == 0:
            # arrange half the marbles in half the saucers
            for r in A(m2, s2):
              # and mirror it
              yield r + r[::-1]
        else:
          # there's an odd number of saucers
          # choose how many marbles to place in the central saucer
          for m1 in irange(2 - rm, m - s + 1, step=2):
            # and arrange half the remaining marbles in half the saucers
            for r in A((m - m1) // 2, s2):
              # and mirror it
              yield r + [m1] + r[::-1]
    
    import sys
    m = (14 if len(sys.argv) < 2 else int(sys.argv[1]))
    s = ( 7 if len(sys.argv) < 3 else int(sys.argv[2]))
    fn = ('S' if len(sys.argv) < 4 else sys.argv[3])
    
    assert not(m < s) and fn in ('A', 'S')
    printf("{fn}(m={m}, s={s})")
    fn = (A if fn == 'A' else S)
    
    n = 0
    for r in fn(m, s):
      n += 1
      printf("{n}: {r}")
    

    For example, for the 36 symmetrical (S) arrangements of 19 marbles in 5 saucers:

    % python enigma1290z.py 19 5 S
    S(m=19, s=5)
     1: [1, 8, 1, 8, 1]
     2: [2, 7, 1, 7, 2]
     3: [3, 6, 1, 6, 3]
     4: [4, 5, 1, 5, 4]
     5: [5, 4, 1, 4, 5]
     6: [6, 3, 1, 3, 6]
     7: [7, 2, 1, 2, 7]
     8: [8, 1, 1, 1, 8]
     9: [1, 7, 3, 7, 1]
    10: [2, 6, 3, 6, 2]
    11: [3, 5, 3, 5, 3]
    12: [4, 4, 3, 4, 4]
    13: [5, 3, 3, 3, 5]
    14: [6, 2, 3, 2, 6]
    15: [7, 1, 3, 1, 7]
    16: [1, 6, 5, 6, 1]
    17: [2, 5, 5, 5, 2]
    18: [3, 4, 5, 4, 3]
    19: [4, 3, 5, 3, 4]
    20: [5, 2, 5, 2, 5]
    21: [6, 1, 5, 1, 6]
    22: [1, 5, 7, 5, 1]
    23: [2, 4, 7, 4, 2]
    24: [3, 3, 7, 3, 3]
    25: [4, 2, 7, 2, 4]
    26: [5, 1, 7, 1, 5]
    27: [1, 4, 9, 4, 1]
    28: [2, 3, 9, 3, 2]
    29: [3, 2, 9, 2, 3]
    30: [4, 1, 9, 1, 4]
    31: [1, 3, 11, 3, 1]
    32: [2, 2, 11, 2, 2]
    33: [3, 1, 11, 1, 3]
    34: [1, 2, 13, 2, 1]
    35: [2, 1, 13, 1, 2]
    36: [1, 1, 15, 1, 1]
    

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: