Enigmatic Code

Programming Enigma Puzzles

Enigma 1676: Pick ‘n’ mix

From New Scientist #2842, 10th December 2011 [link]

There is always the same number of sweets – fewer than 50 – in a box of Tweets. Some are red and the rest are green. The proportion of reds is always the same.

Two lads, Dip and Flip, had a box each last week and a box each this week. Dip picks sweets at random from his box without looking in. Last week, when he had just eaten his last red one, he noticed he had just one green left. This week, when he had eaten his last red sweet, there were two greens left. Last week’s situation is four times as likely as this week’s.

Until he runs out of one colour, Flip picks his sweets by tossing a coin: heads he eats a red one and tails he eats a green one. Last week he had just eaten his last red one and he counted the number of green ones left. This week, when he had eaten his last red sweet there was one more green sweet left than in the previous week. In fact, having last week’s number left is four times as likely as having this week’s.

Tell me how many red sweets and how many green ones make up a box of Tweets.

[enigma1676]

Advertisements

3 responses to “Enigma 1676: Pick ‘n’ mix

  1. Jim Randell 8 December 2011 at 12:17 pm

    This Python program runs in 140ms:

    from fractions import Fraction
    from enigma import C, irange, printf
    
    def dip(r, g):
      n = r + g
      # we need to choose r-1 reds and g-1 greens
      # then there's a 1/2 chance of choosing the remaining red next
      rg  = Fraction(C(r, r - 1) * C(g, g - 1), C(n, n - 2)) / 2
      # we need to choose r-1 reds and g-2 greens
      # then there's a 1/3 chance of choosing the remaining red next
      rgg = Fraction(C(r, r - 1) * C(g, g - 2), C(n, n - 3)) / 3
      return (rg, rgg)
    
    def flip(r, g, gs):
      n = r + g
      # we need to get r-1 reds in n-1-gs flips
      # and there's a 1/2 chance of getting the red next
      rgs  = Fraction(C(n - 1 - gs, r - 1), 2 ** (n - 1 - gs)) / 2
      # we need to get r-1 reds in n-2-gs flips
      # and there's a 1/2 chance of getting the red next
      rgs1 = Fraction(C(n - 2 - gs, r - 1), 2 ** (n - 2 - gs)) / 2
      return (rgs, rgs1)
    
    
    for n in irange(3, 49):
      for r in irange(1, n - 2):
        g = n - r
    
        (rg, rgg) = dip(r, g)
        if rg != 4 * rgg: continue
    
        for gs in irange(1, g - 1):
          (rgs, rgs1) = flip(r, g, gs)
          if rgs != 4 * rgs1: continue
    
          printf("total={n}, red={r}, green={g}")
          printf("dip: P(rg)={rg}, P(rgg)={rgg}")
          printf("flip: gs={gs}, P(rgs)={rgs}, P(rgs1)={rgs1}")
    

    Solution: There are 22 red sweets and 8 green sweets in a box.

    • Jim Randell 8 December 2011 at 12:54 pm

      Simplifying the equations for dip and flip lets you search the solution space much more effectively (runtime: 30ms).

      from itertools import count
      from enigma import printf
      
      # solving the equation for dip:
      # C(r, r-1)C(g, g-1) / 2C(n, n-2) = 4C(r, r-1)C(g, g-2) / 3C(n, n-3) (where n=r+g)
      # gives: n = 4g - 2
      
      # solving the equation for flip:
      # C(n-1-gs, r-1) / 2^(n-gs) = 4C(n-2-gs, r-1) / 2^(n-1-gs) (where n=r+g)
      # gives: gs = n - (8r - 1)/7
      
      for g in count(2):
        n = 4 * g - 2
        if not(n < 50): break
        r = n - g
      
        (d, m) = divmod(8 * r - 1, 7)
        if m > 0: continue
        gs = n - d
      
        printf("total={n}, red={r}, green={g} [gs={gs}]")
      
  2. Jim Randell 9 December 2011 at 10:55 am

    This program is a constructive demonstration that the answer is indeed 30 sweets composed of 22 red and 8 green. It constructs all possible ways of taking the sweets out of the box and counts the probabilities associated with each desired outcome.

    But it is a bit slow to use over the entire solution space to determine the answer (just running this check takes 45s (using PyPy)).

    from fractions import Fraction
    from enigma import irange, printf
    
    class Dip:
    
      def __init__(self, r, g):
        self.red = r
        self.green = g
        self.rg = 0
        self.rgg = 0
    
      def dip(self, r, g, h, p):
        # is there only one colour left?
        if r == 0 or g == 0:
          h += ('g' * g if g else 'r' * r)
          if h.endswith('rg'): self.rg += p
          elif h.endswith('rgg'): self.rgg += p
        else:
          # otherwise there is a choice of colours
          # I could choose a red one
          self.dip(r - 1, g, h + 'r', p * Fraction(r, r + g))
          # or I could choose a green one
          self.dip(r, g - 1, h + 'g', p * Fraction(g, r + g))
    
      def check(self):
        self.rg = 0
        self.rgg = 0
        self.dip(self.red, self.green, '', Fraction(1, 1))
        if self.rg == 4 * self.rgg:
          printf("dip: P(rg)={self.rg}, P(rgg)={self.rgg}")
    
    class Flip:
    
      def __init__(self, r, g):
        self.red = r
        self.green = g
        self.gs = None
    
      def flip(self, r, g, h, p):
        # is there only one colour left?
        if r == 0 or g == 0:
          h += ('g' * g if g else 'r' * r)
          i = len(h) - h.rfind('r') - 1
          if i > 0:
            self.gs[i] += p
        else:
          # otherwise there is a choice of colours
          # I could choose a red one
          self.flip(r - 1, g, h + 'r', p / 2)
          # or I could choose a green one
          self.flip(r, g - 1, h + 'g', p / 2)
    
      def check(self):
        self.gs = dict((i, 0) for i in irange(1, self.green))
        self.flip(self.red, self.green, '', Fraction(1, 1))
        for i in irange(1, self.green - 2):
          if self.gs[i] == 4 * self.gs[i + 1]:
            printf("flip: gs={i}, P(rgs)={rgs}, P(rgs1)={rgs1}", rgs=self.gs[i], rgs1=self.gs[i + 1])
    
    
    # this is a constructive demonstration that r = 22, g = 8 is indeed the solution
    (r, g) = (22, 8)
    printf("total={n}, red={r}, green={g}", n = r + g)
    
    dip = Dip(r, g)
    dip.check()
    
    flip = Flip(r, g)
    flip.check()
    

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: