Sunday Times Teaser 3247 – In the Bag


#  r.(r - 1).(r - 2).(r - 3)
#  ------------------------- = an integer (m)
#  c.(c - 1).(c - 2).(c - 3)

pr = lambda n: n * (n - 1) * (n - 2) * (n - 3)

# collect (r, c) pairs indexed on multiples (m)
m2rc = {}
# the number of colours (defined in snooker
# as colours other than red or white)
for c in range(4, 7):
  prr, prc = 6, pr(c)
  # the number of reds
  for r in range(4, 16):
    prr *= r
    m, r_ = divmod(prr, prc)
    if m >= 100:
      break
    if not r_ and m >= 10:
      m2rc[m] = m2rc.get(m, set()) | {(r, c)}
    prr //= (r - 3)
    
# find a multiple that does not identify the
# red and colour content of the bag
for m, s_rc in m2rc.items():
  if len(s_rc) > 1:
    for r, c in s_rc:
      # consider the possible white ball   
      for w in (0, 1):
        s = r + c + w
        # check that the probability of all colours
        # is of the form 1 / (an _integer)
        dprc, r_ = divmod(pr(s), pr(c))
        if not r_:
          print(f"{s} balls ({r = } {c = }) "
                f"[P(r, {s}) = {m}/{dprc}, P(c, {s}) = 1/{dprc}].")

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

# r.(r - 1).(r - 2).(r - 3)

# ------------------------- = an integer (m)

# c.(c - 1).(c - 2).(c - 3)

pr = lambda n: n * (n - 1) * (n - 2) * (n - 3)

# collect (r, c) pairs indexed on multiples (m)

m2rc = {}

# the number of colours (defined in snooker

# as colours other than red or white)

for c in range(4, 7):

prr, prc = 6, pr(c)

# the number of reds

for r in range(4, 16):

prr *= r

m, r_ = divmod(prr, prc)

if m >= 100:

break

if not r_ and m >= 10:

m2rc[m] = m2rc.get(m, set()) | {(r, c)}

prr //= (r - 3)

# find a multiple that does not identify the

# red and colour content of the bag

for m, s_rc in m2rc.items():

if len(s_rc) > 1:

for r, c in s_rc:

# consider the possible white ball

for w in (0, 1):

s = r + c + w

# check that the probability of all colours

# is of the form 1 / (an _integer)

dprc, r_ = divmod(pr(s), pr(c))

if not r_:

print(f"{s} balls ({r = } {c = }) "

f"[P(r, {s}) = {m}/{dprc}, P(c, {s}) = 1/{dprc}].")

This now includes a suggestion from Frits which improves the speed from 18.6 to 17.3 microseconds.

Reply

John Z permalink


from itertools import combinations
from collections import defaultdict

#dictionary indexed by whole number that we are told
res = defaultdict(tuple)
count = 0
for red in range(4, 16):
  for colours in range(4, 7):
    for white in range(2):
      ballsinbag = 'R' * red + 'C' * colours + 'W' * white

      draws = tuple(combinations(ballsinbag, 4))

      fourred = draws.count(('R', 'R', 'R', 'R'))

      fourcolour = draws.count(('C', 'C', 'C', 'C'))

      rcq, rcr = divmod(fourred, fourcolour)

      if rcr == 0 and 9 < rcq < 100: #

        res[rcq] += (
          (red, colours, white, len(draws) % fourcolour == 0),)


for rr in res.values():
  redcount = set()
  for cc in rr:
    redcount |= {cc[0]}
  if len(redcount) > 1:
    
    ans = [a for a in rr if a[3]][0] # four colour prob = 1 / n
    print(f'Total balls: {sum(ans) - 1} Reds: {ans[0]} Colours: {ans[1]}')

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

from itertools import combinations

from collections import defaultdict

#dictionary indexed by whole number that we are told

res = defaultdict(tuple)

count = 0

for red in range(4, 16):

for colours in range(4, 7):

for white in range(2):

ballsinbag = 'R' * red + 'C' * colours + 'W' * white

draws = tuple(combinations(ballsinbag, 4))

fourred = draws.count(('R', 'R', 'R', 'R'))

fourcolour = draws.count(('C', 'C', 'C', 'C'))

rcq, rcr = divmod(fourred, fourcolour)

if rcr == 0 and 9 < rcq < 100: #

res[rcq] += (

(red, colours, white, len(draws) % fourcolour == 0),)

for rr in res.values():

redcount = set()

for cc in rr:

redcount |= {cc[0]}

if len(redcount) > 1:

ans = [a for a in rr if a[3]][0] # four colour prob = 1 / n

print(f'Total balls: {sum(ans) - 1} Reds: {ans[0]} Colours: {ans[1]}')

Reply

Frits permalink

@John,

You work with a “redcount” set. The requirements suggest you should work with something like a “redcolourcount’ set.

Reply
John Z permalink

and are clearly not going to win any speed competitions.

Reply

Frits permalink

Also taking into account the number of white balls.


from math import prod
from fractions import Fraction as RF
from collections import defaultdict

# 15 red balls, 6 'colours' (not red) and a white ball
n_balls = 15 + 6 + 1
d = defaultdict(list)
# I have placed a number of balls in a bag
for n in range(8, n_balls + 1):
  for n_whites in (0, 1):
    for n_reds in range(4, min(n - n_whites, 16)):
      n_colours = n - n_reds - n_whites
      if not 3 < n_colours < 7: continue
      # the chance of them all being red or colour
      p_red = prod(RF(n_reds - i, n - i) for i in range(4))
      p_colour = prod(RF(n_colours - i, n - i) for i in range(4))
      
      # the chance of them all being red is a two-digit whole number times
      # the chance of them all being colours
      times, r = divmod(p_red, p_colour)
      if times > 99: break
      if not r and times > 9:
        d[times] += [((n_reds, n_colours), n, p_colour)]
 
for k, vs in d.items():
  # if I told you this whole number you would not be able to determine the
  # numbers of reds and colours in the bag
  if len(set(rc for rc, n, p in vs)) == 1: continue
  for rc, n, p in vs:
     if p.numerator == 1:
       print(f"answer: {n} balls with {rc[0]} of them red")

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

from math import prod

from fractions import Fraction as RF

from collections import defaultdict

# 15 red balls, 6 'colours' (not red) and a white ball

n_balls = 15 + 6 + 1

d = defaultdict(list)

# I have placed a number of balls in a bag

for n in range(8, n_balls + 1):

for n_whites in (0, 1):

for n_reds in range(4, min(n - n_whites, 16)):

n_colours = n - n_reds - n_whites

if not 3 < n_colours < 7: continue

# the chance of them all being red or colour

p_red = prod(RF(n_reds - i, n - i) for i in range(4))

p_colour = prod(RF(n_colours - i, n - i) for i in range(4))

# the chance of them all being red is a two-digit whole number times

# the chance of them all being colours

times, r = divmod(p_red, p_colour)

if times > 99: break

if not r and times > 9:

d[times] += [((n_reds, n_colours), n, p_colour)]

for k, vs in d.items():

# if I told you this whole number you would not be able to determine the

# numbers of reds and colours in the bag

if len(set(rc for rc, n, p in vs)) == 1: continue

for rc, n, p in vs:

if p.numerator == 1:

print(f"answer: {n} balls with {rc[0]} of them red")

Reply

Frits permalink

A faster version without the Fraction import.


from math import prod
from collections import defaultdict

# return chance as a tuple (numerator, denominator)
def P(x, y):
  return (prod(x - i for i in range(4)), prod(y - i for i in range(4)))
  
# 15 red balls, 6 'colours' (not red) and a white ball
n_balls = 15 + 6 + 1
d = defaultdict(list)
# I have placed a number of balls in a bag
for n in range(8, n_balls + 1):
  for n_whites in (0, 1):
    for n_reds in range(4, min(n - n_whites, 16)):
      n_colours = n - n_reds - n_whites
      if not 3 < n_colours < 7: continue
      # the chance of them all being red or colour
      p_red = P(n_reds, n)
      p_colour = P(n_colours, n)
      
      # the chance of them all being red is a two-digit whole number times
      # the chance of them all being colours
      times, r = divmod(p_red[0] * p_colour[1], p_red[1] * p_colour[0])
      if times > 99: break
      if not r and times > 9:
        d[times] += [((n_reds, n_colours), n, p_colour)]
 
for vs in d.values():
  # if I told you this whole number you would not be able to determine the
  # numbers of reds and colours in the bag
  if len(set(rc for rc, _, _ in vs)) == 1: continue
  for rc, n, p_colour in vs:
     # drawing four colours is a one in a whole number chance
     if p_colour[1] % p_colour[0]: continue
     print(f"answer: {n} balls with {rc[0]} of them red")

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

from math import prod

from collections import defaultdict

# return chance as a tuple (numerator, denominator)

def P(x, y):

return (prod(x - i for i in range(4)), prod(y - i for i in range(4)))

# 15 red balls, 6 'colours' (not red) and a white ball

n_balls = 15 + 6 + 1

d = defaultdict(list)

# I have placed a number of balls in a bag

for n in range(8, n_balls + 1):

for n_whites in (0, 1):

for n_reds in range(4, min(n - n_whites, 16)):

n_colours = n - n_reds - n_whites

if not 3 < n_colours < 7: continue

# the chance of them all being red or colour

p_red = P(n_reds, n)

p_colour = P(n_colours, n)

# the chance of them all being red is a two-digit whole number times

# the chance of them all being colours

times, r = divmod(p_red[0] * p_colour[1], p_red[1] * p_colour[0])

if times > 99: break

if not r and times > 9:

d[times] += [((n_reds, n_colours), n, p_colour)]

for vs in d.values():

# if I told you this whole number you would not be able to determine the

# numbers of reds and colours in the bag

if len(set(rc for rc, _, _ in vs)) == 1: continue

for rc, n, p_colour in vs:

# drawing four colours is a one in a whole number chance

if p_colour[1] % p_colour[0]: continue

print(f"answer: {n} balls with {rc[0]} of them red")

Reply

Sunday Times Teaser 3247 – In the Bag

by Andrew Skidmore

Published Sunday December 15 2024 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta