Enigmatic Code

Programming Enigma Puzzles

Enigma 352: In the bag

From New Scientist #1501, 27th March 1986 [link]

Yesterday, I was presented with an unusual box containing 13 painted Easter eggs. Each egg was either red, white or blue and there was at least one egg of each colour. If I had been in a dark room, the minimum number of eggs I would have had to withdraw from the box to be certain of picking at least three eggs of the same colour was the same as the number of blue eggs in the box.

Being superstitious, I decided against leaving 13 eggs in the box and transferred a number to a black bag. This bag may not have been empty before I added the coloured eggs. If it wasn’t, then it contained one or more black eggs and nothing else. However, two things are certain. One is that if I were in a dark room, the minimum number of eggs I would now have to withdraw from the box to be sure of having at least three eggs of the same colour is the same as the number of blue eggs in the bag. The second is that the chances of picking out a white egg from the bag with one attempt are the same as the chances of picking out a white egg from the box with one attempt.

But I am in a dark room. Trying to deduce the contents of that black back without turning the light on and looking is keeping me awake late into the night.

How many red, white, blue and black (if any) eggs are there in the bag?

[enigma352]

Advertisements

2 responses to “Enigma 352: In the bag

  1. Jim Randell 8 July 2016 at 8:26 am

    I used a constructive way of finding the minimum number of eggs that need to be chosen to be sure of getting three the same colour.

    This Python 3 program runs in 140ms.

    from enigma import irange, printf
    
    # R, W, B > 0, R + W + B = 13
    
    # find the minimum number of choices required to choose 3 eggs the same colour
    def choose3(*rs):
    
      # return a copy of list s, but with value x at index i
      def update(s, i, x):
        s = list(s)
        s[i] = x
        return s
    
      # generate choices with 3 or fewer eggs the same colour
      def _choose3(rs, ns):
        yield ns
        if 3 not in ns:
          for (i, r) in enumerate(rs):
            if r > 0:
              yield from _choose3(update(rs, i, r - 1), update(ns, i, ns[i] + 1))
    
      # record total number of eggs chosen
      # into cs if there are 3 the same colour and xs otherwise
      (cs, xs) = (set(), set())
      for ns in _choose3(rs, [0] * len(rs)):
        n = sum(ns)
        (cs if 3 in ns else xs).add(n)
    
      # return the smallest total that guarantees 3 eggs the same colour
      ns = sorted(cs.difference(xs))
      return (ns[0] if ns else None)
    
    # consider initial values for R, W, B in the box
    # there's at least one of each colour so B is one of 5, 6, 7
    for B in (5, 6, 7):
      for R in irange(1, 12 - B):
        W = 13 - (R + B)
    
        # check the number of eggs needed to draw to be sure of having
        # three the same colour is the same as the number of blues
        if choose3(R, W, B) != B: continue
    
        # choose R, W, B eggs to go in the bag
        # there must be at least one white in the bag and the box
        for W1 in irange(1, W - 1):
          for R1 in irange(0, R):
            for B1 in irange(0, B):
              # calculate the number of black eggs X, such that chances of
              # white are the same in the bag and the box
              N = R1 + W1 + B1
              (d, r) = divmod((13 - N) * W1, W - W1)
              if r > 0 or d < N: continue
              X = d - N
    
              # check the minimum number of eggs to draw from the box to
              # be sure of three the same colour is the same as the number
              # of blues in the bag
              if choose3(R - R1, W - W1, B - B1) != B1: continue
    
              # output a solution
              printf("box: R={R} W={W} B={B} -> bag: R={R1} W={W1} B={B1} X={X}")
    

    Solution: There are 2 red, 3 white, 4 blue and 3 black eggs in the bag.

    We start off with 2 red, 4 white and 7 blue eggs in the box (13 eggs in total as required).

    The minimum number of eggs chosen unseen to guarantee three the same colour is 7 (because after 6 we can end up with 2 red, 2 white and 2 blue eggs, but the next choice guarantees three eggs the same colour), which is the same as the number of blue eggs.

    2 red, 3 white and 4 blue eggs are then placed in the bag, which already contains 3 black eggs. Leaving 0 red, 1 white and 3 blue eggs in the box.

    The minimum number of eggs chosen unseen from the box to guarantee three the same colour is 4 (all of them, because I have to withdraw the 3 blue eggs, and I might pick the white egg at some point), and this is the same as the number of blue eggs in the bag.

    The chance of choosing a white egg from the bag is 3/12 = 1/4, and the chance of choosing a white egg from the box is 1/4.

  2. Brian Gladman 9 July 2016 at 12:16 am
    from itertools import count, combinations, permutations, product
    
    # partition the integer <n> into <m> non-zero parts (in sort order)
    def partition(n, m, seq=[]):
      if not n:
        if not m:
          yield seq
      else:
        for i in range(1 if not seq else seq[-1], n + 1):
          yield from partition(n - i, m - 1, seq + [i])
    
    # for the numbers of red, white and blue eggs in the triple
    # p, find the minimum number of eggs to withdraw to ensure
    # three of the same colour
    def min_for_three(p):
      # a list of the eggs (red = 1, white = 2, blue = 3)
      p = sum([[i + 1] * p[i] for i in range(len(p))], [])
      # increase the number to withdraw ...
      for nbr in count(3):
        # ... until all ways of withdrawing this number of eggs 
        #     always gives three of the same colour
        for c in combinations(p, nbr):
          if all(c.count(x) < 3 for x in p):
            break
        else:
          return nbr
    
    # try all ways of dividing the 13 eggs between red, white and blue
    for p in partition(13, 3):
      # blue is the minimum to withdraw to guarantee three of the same colour 
      blue = min_for_three(p)
      if blue in p:
        # now permute the other two values for red and white
        rw = [v for i, v in enumerate(p) if i != p.index(blue)]
        for red, white in permutations(rw):
          rwb_box = red, white, blue
          
          # try all ways of moving red, white and blue eggs into the bag
          # (but make sure of a white in the bag and one left in the box)
          for rwb_bag in product(range(red + 1), range(1, white), range(blue + 1)):
            
            # find the numbers of red, white and blue eggs left in the box
            rwb_left = tuple(x - y for x, y in zip(rwb_box , rwb_bag))
    
            # there must be at least three of one colour left in the box        
            if any(x >= 3 for x in rwb_left):
              
              # the minimum withdrawn from the box to guarantee three of one
              # colour is the same as the number of blue eggs in the bag 
              if min_for_three(rwb_left) == rwb_bag[2]:
                bag_eggs = sum(rwb_bag)
                
                # the probability of drawing a white from the bag is:
                #     white_in_bag / (total_rwb_in_bag + black)
                # the probability of drawing a white from the box is:
                #     white_left_in_box / (total_left_in_box)
                # equating these gives the number of blacks
                q, rem = divmod(rwb_bag[1] * (13 - bag_eggs), white - rwb_bag[1])
                black = q - bag_eggs
                if not rem and black >= 0:
                  f1 = ('{} red, {} white, {} blue and {} black eggs'
                        ' (from {} red, {} white and {} blue).')
                  print(f1.format(*rwb_bag, black, *rwb_box))
    

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: