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]

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()
```