Sunday Times Teaser 2805 – Greek Urns

by Michael Fletcher

Published: 26 June 2016 (link)

I have three Greek urns. I took some balls (consisting of an odd number of red balls and some black balls) and I placed one or more balls in the first urn, one or more in the second, and the rest in the third. If you chose an urn at random and then a ball at random from that urn, then overall there would be a 50 per cent chance of getting a red ball.

Then I moved some black balls from one of the urns to another. In this new situation, if you chose an urn and then a ball there was a 75 per cent chance of getting a red. In fact, with this set of balls and urns it would be impossible to get a higher percentage than that.

How many red balls and how many black balls were there?

3 Comments Leave one →

Brian Gladman permalink


from itertools import count, permutations, product
from fractions import Fraction as RF

# compute the probability of selecting a red by randomly 
# picking an urn and then randomly picking a ball from it
def prob(r, b):
  t = tuple(x + y for x, y in zip(r, b))
  top = r[0] * t[1] * t[2] + t[0] * r[1] * t[2] + t[0] * t[1] * r[2]
  bot = 3 * t[0] * t[1] * t[2]
  return RF(top, bot)

# for holding solutions
soln = set()

# try odd numbers of red balls 
for red in count(1, 2):
  # with increasing numbers of black balls
  for blk in count(1):
    
    # find a distribution of the red balls (tr) and the black balls (tb)
    # between the urns that maximises the probability of picking a red
    max_prob, max_vals = None, None
    
    for r1, b1 in product(range(red + 1), range(blk + 1)):
      for r2, b2 in product(range(r1, red - r1 + 1), range(blk - b1 + 1)):
        tr, tb = (r1, r2, red - r1 - r2), (b1, b2, blk - b1 - b2)
        
        if tr[2] >= tr[1]:
          try:
            p = prob(tr, tb)
            # record the maximum probability of a red and the related
            # urn contents
            if max_prob is None or p > max_prob:
              max_prob = p
              max_vals = (red, blk, tr, tb)
          except ZeroDivisionError:
            continue
            
    # consider numbers of black balls giving probabilities not less than 3/4
    if max_prob and max_prob < RF(3, 4):
      break
    
    # if the maximum probability is 3/4 find out whether moving blacks from
    # one urn to another can reduce this to 1/2
    if max_prob and max_prob == RF(3, 4):
      # set the red and black ball counts for this probability
      (red, blk, tr, tb) = max_vals
      
      # now permute the urns for the one that is unchanged, the one that
      # blacks are moved from and the one that they are moved to
      for u1, u2, u3 in permutations(range(3)):
        # the number of blacks to move
        for tx in range(1, tb[u2] + 1):
          tb2 = tb[u1], tb[u2] - tx, tb[u3] + tx
          # now look for an arrangement that gives a probability of 1/2
          try:
            if prob(tr, tb2) == RF(1, 2):
              soln.add((red, blk, tr, tb, tb2))
          except ZeroDivisionError:
            continue
  
  # do we have a solution?
  if soln:
    # ouput it and exit
    for red, blk, tr, tb, tb2 in soln:
      print('red = {}, black = {},'.format(red, blk), list(zip(tr, tb)), 
            list(zip(tr, tb2)))
    break

from itertools import count, permutations, product

from fractions import Fraction as RF

# compute the probability of selecting a red by randomly

# picking an urn and then randomly picking a ball from it

def prob(r, b):

t = tuple(x + y for x, y in zip(r, b))

top = r[0] * t[1] * t[2] + t[0] * r[1] * t[2] + t[0] * t[1] * r[2]

bot = 3 * t[0] * t[1] * t[2]

return RF(top, bot)

# for holding solutions

soln = set()

# try odd numbers of red balls

for red in count(1, 2):

# with increasing numbers of black balls

for blk in count(1):

# find a distribution of the red balls (tr) and the black balls (tb)

# between the urns that maximises the probability of picking a red

max_prob, max_vals = None, None

for r1, b1 in product(range(red + 1), range(blk + 1)):

for r2, b2 in product(range(r1, red - r1 + 1), range(blk - b1 + 1)):

tr, tb = (r1, r2, red - r1 - r2), (b1, b2, blk - b1 - b2)

if tr[2] >= tr[1]:

try:

p = prob(tr, tb)

# record the maximum probability of a red and the related

# urn contents

if max_prob is None or p > max_prob:

max_prob = p

max_vals = (red, blk, tr, tb)

except ZeroDivisionError:

continue

# consider numbers of black balls giving probabilities not less than 3/4

if max_prob and max_prob < RF(3, 4):

break

# if the maximum probability is 3/4 find out whether moving blacks from

# one urn to another can reduce this to 1/2

if max_prob and max_prob == RF(3, 4):

# set the red and black ball counts for this probability

(red, blk, tr, tb) = max_vals

# now permute the urns for the one that is unchanged, the one that

# blacks are moved from and the one that they are moved to

for u1, u2, u3 in permutations(range(3)):

# the number of blacks to move

for tx in range(1, tb[u2] + 1):

tb2 = tb[u1], tb[u2] - tx, tb[u3] + tx

# now look for an arrangement that gives a probability of 1/2

try:

if prob(tr, tb2) == RF(1, 2):

soln.add((red, blk, tr, tb, tb2))

except ZeroDivisionError:

continue

# do we have a solution?

if soln:

# ouput it and exit

for red, blk, tr, tb, tb2 in soln:

print('red = {}, black = {},'.format(red, blk), list(zip(tr, tb)),

list(zip(tr, tb2)))

break

Here is a manual solution.

To make the probability of withdrawiing a red ball 3/4, \(r+2\) red balls and \(3r\) black balls must be placed in the three urns in the following way: red \((r,1,1)\) and black \((3r,0,0)\).

When \(x\) black balls are moved from urn one to urn two, the distribution of black balls becomes: \((3r-x,x,0)\), making the probability of drawing a red ball: \[(r/(4r-x)+1/(1+x)+1/0))/3\] which must be 1/2. This gives the following quadratic for \(x\):\[x^2-(2r+1)x+6r=0\]with the solution:\[\frac{(2r+1\pm\sqrt{(2r-5)^2-24})}{2}\] For integer \(x\) the expression in the square root must be a perfect square (say \(c\)), giving: \[(2r-5)^2-c^2 = 24\]If \(f\) is a factor of 24, we have:\[\begin{array}{lcl}2r-5+c &=&f \\2r-5-c&=&24/f\end{array}\]which gives the solutions for \(r\) and \(c\) in terms of \(f\) as:\[\begin{array}{lcl}r&=&(24/f+f+10)/4 \\c&=&(24/f-f)/2\end{array}\]Trying the factors of 24 gives only one solution: \(r=5\) and \(c=1\) with \(x=5\) or \(x=6\).

Hence there are 7 red balls and 15 black balls.

Frits permalink

@Brian,

You don’t need to store red and blk in max_vals.
I think you mean formulae 2r – 5 + c = f and c = (f – 24/f) / 2

Regarding first line of the manual solution:

red(r, 3s, t) black(r, s, 0) also has an overall 75 per cent chance for drawing a red (r, s and t all positive).

Jim has published this puzzle as well:

https://s2t2.home.blog/2021/07/22/teaser-2805-greek-urns/

Some of my comments also apply to your program as well (like using r1 > 0)

Reply
- Brian Gladman permalink
  
  Thanks for the correction.
  
  Reply

Sunday Times Teaser 2805 – Greek Urns

by Michael Fletcher

Published: 26 June 2016 (link)

Leave a comment to Brian Gladman Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta