Teaser 2805: Greek urns
From The Sunday Times, 26th June 2016 [link] [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 ball 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?
[teaser2805]
Frits and 
GeoffR and 
Hugh Casement, 
Iain Turner, and 1 other are discussing. 
John Crabtree, 
Jim Olson and 
Tony Brooke-Taylor, and 
S2T2 
Jim Randell 6:43 am on 22 July 2021 Permalink |
The following Python program runs in 126ms.
Run: [ @replit ]
from enigma import Rational, irange, inf, printf Q = Rational() # return ((r1, b1), (r2, b2), (r3, b3)) from R red, B black balls # as (P1, P2) where # P1 = configuration with P = 1/2 # P2 = configuration with P = 3/4 def solve(R, B): # record probabilities: P1 = 1/2, P2 = 3/4, P3 > 3/4 (P1, P2) = (list(), list()) # place n1 balls in urn 1 T = R + B for n1 in irange(1, T - 2): # how many are red? for r1 in irange(0, min(R, n1)): # and the rest are black b1 = n1 - r1 # probability of choosing a red ball from urn 1 p1 = Q(r1, n1) # place n2 balls in urn 2 (n2 <= n1) for n2 in irange(1, min(n1, T - n1)): # how many are red? for r2 in irange(0, min(R - r1, n2)): # and the rest are black b2 = n2 - r2 # probability of choosing a red ball from urn 2 p2 = Q(r2, n2) # and urn 3 (n3 <= n2) n3 = T - n1 - n2 if n3 > n2: continue r3 = R - r1 - r2 b3 = n3 - r3 if b3 < 0: continue p3 = (0 if n3 == 0 else Q(r3, n3)) # total probability of drawing a red ball p = Q(p1 + p2 + p3, 3) if p == Q(1, 2): P1.append(((r1, b1), (r2, b2), (r3, b3))) elif p == Q(3, 4): P2.append(((r1, b1), (r2, b2), (r3, b3))) elif p > Q(3, 4): return # look for a viable pair from P1 x P2 for ((r1, b1), (r2, b2), (r3, b3)) in P1: for ((r1_, b1_), (r2_, b2_), (r3_, b3_)) in P2: # the number of red balls in each urn must be the same if not(r1_ == r1 and r2_ == r2 and r3 == r3_): continue # and one of the sets of blacks is the same if not(b1 == b1_ or b2 == b2_ or b3 == b3_): continue # viable configuration yield (((r1, b1), (r2, b2), (r3, b3)), ((r1_, b1_), (r2_, b2_), (r3_, b3_))) # find the first viable red/black configuration def run(): # total number of balls for T in irange(2, inf): # number of red balls is odd for R in irange(1, T - 1, step=2): # and the rest are black B = T - R # look for solutions with R reds, B blacks n = 0 for (((r1, b1), (r2, b2), (r3, b3)), ((r1_, b1_), (r2_, b2_), (r3_, b3_))) in solve(R, B): printf("({r1}r + {b1}b) ({r2}r + {b2}b) ({r3}r + {b3}b) -> ({r1_}r + {b1_}b) ({r2_}r + {b2_}b) ({r3_}r + {b3_}b)") n += 1 if n > 0: printf("R={R} B={B} [T={T}; {n} configurations]") return run()Solution: There were 7 red balls, and 15 black balls.
Possible configurations are:
The program stops after the first red/black configuration it finds, but we can let it look for further solutions, but it gets a bit slow for T > 100 (and doesn’t find any further solutions).
Assuming the maximum probability of choosing a red ball for R red balls and B black balls is given by the following configuration:
(so we require R ≥ 2).
Then for the overall probability of choosing a red to be 3/4 we have:
Which means for any R value, there is only one corresponding B value.
So the final configuration is:
All the black balls are in one urn, so we can suppose x of them were moved from an urn containing (1r + xb), making the original configuration:
And the overall probability of choosing a red is 1/2, so:
So for any R value, there are at most 2 viable x values.
This allows us to quickly check for higher solutions (but we don’t find any):
from enigma import irange, quadratic, printf for R in irange(3, 1000, step=2): B = 3 * R - 6 # look for x values for x in quadratic(1, 3 - 2 * R, 6 * R - 12, domain="Z"): if x > 0: printf("R={R} B={B}; x={x}")Continuing with the analysis, we can show there are no higher solutions.
R is an odd integer, say R = 2k + 3, for some non-negative integer k. Then:
And using the quadratic formula, we see this has solutions:
Both sides are integers, so: (4k − 3)² − 24 must be an odd perfect square, say (2z + 1)²:
The LHS is the product of 2 integers, (a, b) that give 24.
So by looking at the finite set of pairs of integers whose product is 24, we can determine all possible values of k, and hence of R, B, x, and verify that the solutions found above are the only possible solutions.
from enigma import divisors_pairs, div, quadratic, printf # find sum of integer pairs that multiply to x def pairs(n): for (a, b) in divisors_pairs(n): s = a + b yield s yield -s # find possible values for k for s in pairs(24): k = div(s + 6, 8) if k is None or k < 0: continue R = 2 * k + 3 B = 3 * R - 6 # and corresponding values for x for x in quadratic(1, 3 - 2 * R, 6 * R - 12, domain="Z"): if x > 0: printf("R={R} B={B}; x={x} [k={k} s={s}]")LikeLike
Frits 11:02 am on 22 July 2021 Permalink |
@Jim, Interesting.
We can speed up the general program by (among others):
LikeLike
Jim Randell 3:03 pm on 22 July 2021 Permalink |
Yes. It’s more efficient to use a [[
decompose()]] type function to distribute the balls.The following Python program only take 75ms, and can check up to T = 128 in a few minutes.
Run: [ @replit ]
from enigma import Rational, irange, inf, printf Q = Rational() # decompose t into k ascending numbers def decompose(t, k, m=1, ns=[]): if k == 1: if not(t < m): yield ns + [t] else: k_ = k - 1 for n in irange(m, t - k_ * m): yield from decompose(t - n, k_, n, ns + [n]) # return ((r1, b1), (r2, b2), (r3, b3)) from R red, B black balls as (P1, P2) where # P1 = configurations with P = 1/2 # P2 = configurations with P = 3/4 def solve(R, B): # record probabilities: P1 = 1/2, P2 = 3/4, P3 > 3/4 (P1, P2) = (list(), list()) # choose a distribution for the number of balls in each urn for (n3, n2, n1) in decompose(R + B, 3): # how many red balls in urn1? for r1 in irange(0, min(R, n1)): # and the rest are black b1 = n1 - r1 # probability of choosing a red ball from urn 1 p1 = Q(r1, n1) # how many red balls in urn2? for r2 in irange(0, min(R - r1, n2)): # and the rest are black b2 = n2 - r2 # and urn 3 (n3 <= n2) r3 = R - r1 - r2 b3 = B - b1 - b2 if b3 < 0: continue # probabilities of choosing a red ball from urn 2 and urn 3 p2 = Q(r2, n2) p3 = (0 if n3 == 0 else Q(r3, n3)) # total probability of drawing a red ball p = Q(p1 + p2 + p3, 3) if p == Q(1, 2): P1.append(((r1, b1), (r2, b2), (r3, b3))) elif p == Q(3, 4): P2.append(((r1, b1), (r2, b2), (r3, b3))) elif p > Q(3, 4): return # look for a viable pair from P1 x P2 for ((r1, b1), (r2, b2), (r3, b3)) in P1: for ((r1_, b1_), (r2_, b2_), (r3_, b3_)) in P2: # the number of red balls in each urn must be the same if not(r1_ == r1 and r2_ == r2 and r3 == r3_): continue # and one of the sets of blacks is the same if not(b1 == b1_ or b2 == b2_ or b3 == b3_): continue # viable configuration yield (((r1, b1), (r2, b2), (r3, b3)), ((r1_, b1_), (r2_, b2_), (r3_, b3_))) # find the first viable red/black configuration def run(): # total number of balls for T in irange(2, inf): for R in irange(1, T - 1, step=2): # and the rest are black B = T - R # look for solutions with R reds, B blacks n = 0 for (((r1, b1), (r2, b2), (r3, b3)), ((r1_, b1_), (r2_, b2_), (r3_, b3_))) in solve(R, B): printf("({r1}r + {b1}b) ({r2}r + {b2}b) ({r3}r + {b3}b) -> ({r1_}r + {b1_}b) ({r2_}r + {b2_}b) ({r3_}r + {b3_}b)") n += 1 if n > 0: printf("R={R} B={B} [T={T}; {n} configurations]") return run()LikeLike
Frits 5:21 pm on 22 July 2021 Permalink |
The following Python program runs in 1 second for numbers 0-19 and 100ms for numbers 0-9 (with PyPy).
from enigma import SubstitutedExpression # the alphametic puzzle p = SubstitutedExpression( [# (red, black) balls: (AB, GH), (CD, IJ), (EF, KL)) # (AB / (AB + GH) + CD / (CD + IJ) + EF / (EF + KL)) / 3 = 0.50 # "2 * (AB * (CD + IJ) * (EF + KL) + \ CD * (AB + GH) * (EF + KL) + \ EF * (AB + GH) * (CD + IJ)) == 3 * (AB + GH) * (CD + IJ) * (EF + KL)", "AB > 0", "CD > 0", "EF > 0", # odd number of red balls "(AB + CD + EF) % 2", # force only one red if there are no blacks "KL > 0 or EF == 1", # (AB / (AB + GH - XY) + CD / (CD + IJ + XY) + EF / (EF + KL)) / 3 = 0.75 # move XY black balls form one urn to another "0 < XY <= GH", "4 * (AB * (CD + IJ + XY) * (EF + KL) + \ CD * (AB + GH - XY) * (EF + KL) + \ EF * (AB + GH - XY) * (CD + IJ + XY)) == \ 9 * (AB + GH - XY) * (CD + IJ + XY) * (EF + KL)", # no higher chance than 0.75 "not any(4 * (AB * (CD + IJ + x) * (EF + KL) + \ CD * (AB + GH - x) * (EF + KL) + \ EF * (AB + GH - x) * (CD + IJ + x)) > \ 9 * (AB + GH - x) * (CD + IJ + x) * (EF + KL) \ for x in range(1, GH + 1))", ], answer="AB + CD + EF + GH + IJ + KL, AB + CD + EF, \ ((AB, GH), (CD, IJ), (EF, KL)), ((AB, GH - XY), (CD, IJ + XY), (EF, KL))", accumulate=min, verbose=0, # checks numbers 0-19 d2i=dict([(k, "ACEGIKX") for k in range(2, 10)]), distinct="", # allow variables with same values ) # solve the puzzle r = p.run() # print answer ans = list(r.accumulate) print(f"smallest solution: {ans[1]} red balls and " f"{ans[0] - ans[1]} black balls")LikeLike