by: Michael Fletcher

Tagged: by: Michael Fletcher Toggle Comment Threads | Keyboard Shortcuts

Jim Randell 6:48 am on 5 January 2025 Permalink | Reply
Tags: by: Michael Fletcher
Teaser 3250: Very similar triangles
From The Sunday Times, 5th January 2025 [link] [link]

I have a piece of A6 paper on which I draw two triangles. The triangles are very similar in two ways. First of all, they are both the same shape. Not only that, the lengths of two of the sides of one of the triangles are the same as the lengths of two of the sides of the other triangle, but one triangle is larger than the other.

If the sides of the triangles are whole numbers of millimetres and the triangles don’t have any obtuse angles:

What are the lengths of sides of the larger triangle?

Note: A sheet of A6 paper measures 105 mm × 148 mm.

[teaser3250]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell and Tony Smith are discussing. Toggle Comments
- Jim Randell 7:02 am on 5 January 2025 Permalink | Reply
  (See also: Enigma 1198).
  
  This Python program runs in 67ms. (Internal runtime is 1.5ms).
```
from enigma import (irange, hypot, intf, printf)

# consider triangles with sides (a, b, c), (b, c, d)
# we have: ratio(a, b, c) = ratio(b, c, d)
M = intf(hypot(105, 148))  # max length
for a in irange(1, M - 1):
  for b in irange(a + 1, M):
    (c, r) = divmod(b * b, a)
    if c > M: break
    if r != 0: continue
    # check triangle is not obtuse
    if a + b <= c or c * c > a * a + b * b: continue
    (d, r) = divmod(c * c, b)
    if d > M: break
    if r != 0: continue
    # output solution
    printf("{t1} + {t2}", t1=(a, b, c), t2=(b, c, d))
```
  There is only a single candidate solution, and it is easy to demonstrate that the triangles can both fit onto a single piece of A6.
  
  Solution: The sides of the larger triangle are: 80 mm, 100 mm, 125 mm.
  
  And the smaller triangle has sides: 64 mm, 80 mm, 100 mm.
  
  The internal angles of the triangles are (approximately) 40°, 53°, 87°.
  
  Here is a diagram showing both triangles on a piece of A6 paper (dimensions in mm):
  
  LikeLike
- Tony Smith 4:29 pm on 5 January 2025 Permalink | Reply
  
  In fact there is nothing to stop the triangles overlapping.
  
  LikeLike
  - Jim Randell 4:57 pm on 5 January 2025 Permalink | Reply
    
    @Tony: True enough. I was imagining we wanted to cut the triangles out, but that isn’t what the puzzle text says.
    
    LikeLike
Reply Cancel reply
Required fields are marked *

Name *

Email *

Website

Notify me of new comments via email.
Notify me of new posts via email.
Δ

This site uses Akismet to reduce spam. Learn how your comment data is processed.
Jim Randell 1:49 am on 27 October 2024 Permalink | Reply
Tags: by: Michael Fletcher
Teaser 3240: The Case of the Green Cane of Kabul
From The Sunday Times, 27th October 2024 [link] [link]

Inspector Lestrade had a warrant for the arrest of Dr Watson.

“Pray explain,” cried Dr Watson.

“A man was badly beaten earlier tonight near here. The victim told us that the assailant used a green cane. We all know that you received the Green Cane of Kabul for military service and are the only person allowed to carry it.”

“What you say is true, Lestrade”, said Holmes. “However, there are several recipients of the Blue Cane of Kabul living here, and 20% of people seeing blue identify it as green while 20% of people seeing green identify it as blue. It follows that the probability that the colour of the cane used in this attack is blue is 2/3.”

How many recipients of the Blue Cane of Kabul are there in the city?

[teaser3240]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 2:13 am on 27 October 2024 Permalink | Reply
  There are two relevant cases to consider:
  
  (1) The attacker used a green cane, which was correctly identified as green.
  
  (2) The attacker used a blue cane, which was misidentified as green.
  
  And we need the probability of case (2) to be 2/3 (i.e. it is twice the probability of case (1)).
  
  The solution is easily found manually, but this Python program considers possible increasing numbers of blue cane carriers, until the required probability is found.
```
from enigma import (Rational, irange, inf, compare, printf)

Q = Rational()

# B = number of carriers of the blue cane
for B in irange(1, inf):
  # probability attacker used a green cane, identified as green
  pGG = Q(1, B + 1) * Q(4, 5)
  # probability attacker used a blue cane, identified as green
  pBG = Q(B, B + 1) * Q(1, 5)
  # probability that a blue cane was used in the attack
  p = Q(pBG, pGG + pBG)
  r = compare(p, Q(2, 3))
  if r == 0: printf("B={B}")
  if r > 0: break
```
  Solution: There are 8 holders of the Blue Cane.
  
  Manually:
  
  If there are B blue canes, then (assuming each cane holder is equally likely to be the attacker):
  
  P(attacker used blue cane) = B/(B + 1)
  P(attacker used green cane) = 1/(B + 1)
  
  P(attacker used blue cane, identified as green) = (B/(B + 1)) × (1/5) = pBG
  P(attacker used green cane, identified as green) = (1/(B + 1)) × (4/5) = pGG
  
  And we want pBG to be twice pGG.
  
  pBG = 2 pGG
  (B/(B + 1)) × (1/5) = 2 × (1/(B + 1)) × (4/5)
  ⇒ B = 2 × 4 = 8
  
  LikeLike

Jim Randell 6:12 am on 15 September 2024 Permalink | Reply
Tags: by: Michael Fletcher

Teaser 3234: An existential threat thwarted

From The Sunday Times, 15th September 2024 [link] [link]

“Merlin, the Saxons are on the rampage. A group of 90 soldiers is advancing towards Mount Badon. We only have 86 knights that we can muster. I think we are doomed”, said the King.

“Not necessarily, Sire. The strength of an army is proportional to the square of the number of its troops. An army of 100 would defeat an army of 80 yet still have 60 remaining because 100^2 − 80^2 = 60^2. Tell the knights to split into three groups of particular sizes and engage the Saxons in three simultaneous battles. If the Saxons split into three groups of 30, we can prevail.”

After the conflict there were 32 knights and 24 Saxons remaining.

What were the sizes of the three groups the knights split into?

[teaser3234]

Jim Randell 6:21 am on 15 September 2024 Permalink | Reply

I am assuming we are looking for battles where there is an integer number of survivors.

This Python program runs in 68ms. (Internal runtime is 1.4ms).

from enigma import (decompose, ircs, printf)

# battle <xs> against <ys>, looking for integer advantages
def battle(xs, ys):
  rx = ry = 0
  for (x, y) in zip(xs, ys):
    if x > y:
      r = ircs(x, -y)
      if r is None: return (None, None)
      rx += r
    elif y > x:
      r = ircs(y, -x)
      if r is None: return (None, None)
      ry += r
  return (rx, ry)

# split the knights into 3 groups
for ks in decompose(86, 3, increasing=1, sep=0, min_v=1):
  # battle the Knights against the groups of Saxons
  (rK, rS) = battle(ks, (30, 30, 30))
  if rK is None: continue
  # look for scenarios where the Knights prevail
  if not (rK > rS): continue
  # output solution
  printf("{ks} -> {rS} Saxons, {rK} Knights")

Solution: The Knights split into groups of size: 18, 34, 34.

So we have the following battles:

30 Saxons vs. 18 Knights → 24 Saxons remaining
30 Saxons vs. 34 Knights → 16 Knights remaining
30 Saxons vs. 34 Knights → 16 Knights remaining
total: 90 Saxons vs. 86 Knights → 24 Saxons, 32 Knights remaining; Knights prevail

For battles with integer advantages there is one other solution, but in this case the Saxons prevail:

30 Saxons vs. 18 Knights → 24 Saxons remaining
30 Saxons vs. 18 Knights → 24 Saxons remaining
30 Saxons vs. 50 Knights → 40 Knights remaining
total: 90 Saxons vs. 86 Knights → 48 Saxons, 40 Knights remaining; Saxons prevail

So we don’t need to know the number of survivors to solve the puzzle.

Manually:

There are only 6 possible battles that give an integer number of survivors where one of the sides has 30 participants, and the other side has less than 86:

(30, 24) → (18, 0)
(30, 18) → (24, 0)
(30, 30) → (0, 0)
(30, 34) → (0, 16)
(30, 50) → (0, 40)
(30, 78) → (0, 72)

And by inspection, the only way for there to be 24 Saxons and 32 Knights remaining in 3 battles is:

(30, 18) → (24, 0)
(30, 34) → (0, 16)
(30, 34) → (0, 16)

LikeLike

Jim Randell 6:08 pm on 15 September 2024 Permalink | Reply

This is faster (and shorter). Internal runtime is 134µs.

from enigma import (pythagorean_triples, subsets, printf)

# if A beats B and has C survivors then:
#   A^2 - B^2 = C^2
#   B^2 + C^2 = A^2 (i.e. a Pythagorean triple)

# record (<saxons>, <knights>, <remaining-saxons>, <remaining-knights>)
ss = [(30, 30, 0, 0)]  # draw

# find pythagorean triples involving 30
for (x, y, z) in pythagorean_triples(84):
  if z == 30:
    ss.extend([(z, y, x, 0), (z, x, y, 0)])
  if y == 30:
    ss.append((y, z, 0, x))
  if x == 30:
    ss.append(((x, z, 0, y)))

# choose 3 battles
for bs in subsets(ss, size=3, select='R'):
  # calculate initial knights (K) and total survivors (rS, rK)
  (Ss, Ks, rSs, rKs) = zip(*bs)
  (K, rS, rK) = map(sum, (Ks, rSs, rKs))
  if K == 86 and rK > rS:
    printf("Knights = {Ks} -> {rS} Saxons, {rK} Knights [battles = {bs}]")

LikeLike

GeoffR 5:34 pm on 15 September 2024 Permalink | Reply

% A Solution in MiniZinc
include "globals.mzn";

% As the Knights have 32 men left and the Saxons 24 men left after three battles....
% Assume the Saxons win the 1st battle and the Knights the next 2 battles
% Also, the Saxons have 30 men in each of the three battles

% K1 knights in 1st battle, K2 knights in 2nd battle and K3 knights in 3rd battle
var 1..29:K1; var 31..86:K2; var 31..86:K3;

constraint K1 + K2 + K3 == 86; % There are 86 knights in total

predicate is_sq(var int: y) =
  exists(z in 1..ceil(sqrt(int2float(ub(y))))) (
        z*z = y );
        
% Let the Saxons win the 1st battle
constraint 30 * 30 - K1 * K1 == 24 * 24; % Saxons have 24 men left after 3 battles

% Let the Knights win 2nd and 3rd battles
constraint is_sq((K2 * K2 - 30 * 30)) /\ is_sq((K3 * K3 - 30 * 30));

solve satisfy;

output ["The three groups of the knights are " ++ show([K1, K2, K3])];

A manual check on K2 and K3 knights showed there were 32 knights left.

LikeLike

Ruud 10:06 am on 17 September 2024 Permalink | Reply

This code runs in 57 ms on my M4 iPad Pro.

import itertools
import math

for sizes in itertools.product(range(87), repeat=3):
    if sum(sizes) == 86 and sizes == tuple(sorted(sizes)):
        knights = 0
        saxons = 0
        for size in sizes:
            if (diff := math.sqrt(abs((size**2 - 30**2)))).is_integer():
                knights += (size > 30) * int(diff)
                saxons += (size < 30) * int(diff)
            else:
                break
        else:
            if knights > saxons:
                print(f"{sizes=} {knights=} {saxons=}")

LikeLike

Jim Randell 3:37 pm on 30 June 2023 Permalink | Reply
Tags: by: Michael Fletcher
Teaser 3171: What’s happened to our chocolate bar?
From The Sunday Times, 2nd July 2023 [link] [link]

Father Christmas was rewarding his helpers (sprites, elves and fairies). He had 333 helpers, of whom 111 were elves.

He had 28 chocolate bars to give away in proportion to the size of the groups. If the groups’ shares were 9.5, 9.3 and 9.2 then they would actually receive 10, 9 and 9, because the bars can’t be split and the extra bar goes to the group with the highest remainder (for two extra bars, one each would go to the two groups with the highest remainders). In fact the sprites, elves and fairies received 7, 9 and 12 bars respectively.

“I’ve found another chocolate bar”, said Father Christmas, “so now the sprites, elves and fairies will receive 6, 10 and 13 bars respectively.”

“What’s happened to our chocolate bar?” asked the sprites.

How many sprites are there?

[teaser3171]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell, Tony Brooke-Taylor, and Frits are discussing. Toggle Comments
- Jim Randell 3:58 pm on 30 June 2023 Permalink | Reply
  What better time to run a Christmas themed puzzle?
  
  See also: this Matt Parker video [@youtube]
  
  This Python program runs in 61ms. (Internal runtime is 414µs).
  
  Run: [ @replit ]
```
from enigma import (decompose, item, first, printf)

# distribute <k> bars among <ns>
def distribute(k, ns):
  t = sum(ns)
  ds = list()  # allocation
  rs = list()  # (index, remainder)
  # initial allocation
  for (i, n) in enumerate(ns):
    (d, r) = divmod(n * k, t)
    ds.append(d)
    rs.append((i, r))
  # distribute remaining bars
  k -= sum(ds)
  for (i, r) in first(sorted(rs, key=item(1), reverse=1), k):
    ds[i] += 1
  return ds

# total number of helpers
T = 333
# number of elves
E = 111
# choose the number of sprites and fairies
for (S, F) in decompose(T - E, 2, increasing=1, sep=2, min_v=1):

  # calculate the distributions of 28 and 29 bars
  if distribute(28, [S, E, F]) != [7, 9, 12]: continue
  if distribute(29, [S, E, F]) != [6, 10, 13]: continue

  # output solution
  printf("S={S} E={E} F={F}")
```
  Solution: There are 76 sprites.
  
  There are 76 sprites, 111 elves, 146 fairies (= 333 helpers in total).
  
  With 28 chocolate bars the distribution is:
  
  S → 6.39 bars
  E → 9.33 bars
  F → 12.27 bars
  
  After allocating the 6, 9, 12 bars there is 1 bar left over, which goes to the sprites, as they have the largest remainder, giving a final allocation of 7, 9, 12 bars (28 in total).
  
  With 29 the distribution is:
  
  S → 6.62 bars
  E → 9.67 bars
  F → 12.71 bars
  
  After allocating the 6, 9, 12 bars there are 2 bars left over, which go to the fairies and the elves, as they have the largest remainders, giving a final allocation of 6, 10, 13.
  
  We can look at the “fairness” of the allocations by considering the amount of chocolate per helper.
  
  If each bar weighs 100g, then in the first case there is 2800g of chocolate, and 333 helpers, so a completely fair allocation would be 8.41g per helper.
  
  The actual allocations are:
  
  S → 7 bars = 9.21g / sprite (= avg + 0.80g)
  E → 9 bars = 8.11g / elf (= avg − 0.30g)
  F → 12 bars = 8.22g / fairy (= avg − 0.19g)
  
  So the sprites get an above average share this allocation, and the elves and fairies get below average.
  
  In the second allocation there is 2900g of chocolate, giving a fair allocation of 8.71g per helper.
  
  And the actual allocations are:
  
  S → 6 bars = 7.89g / sprite (= avg − 0.82g)
  E → 10 bars = 9.01g / elf (= avg + 0.30g)
  F → 13 bars = 8.90g / fairy (= avg + 0.19g)
  
  In this allocation the sprites get a below average share, and the elves and fairies get above average.
  
  Manually:
  
  Adding 1 bar to the total causes S’s proportion of the chocolate to go down and E’s and F’s proportions to go up. So in the first case there was 1 remaining bar which went to S, and in the second case there were 2 remaining bars which went to E and F.
  
  In the first case the sum of the remainders come to 1 bar, so the largest remainder (S’s) must be more than 1/3:
  
  (S/333)×28 > 6 + 1/3
  S > (19/3)×(333/28) ≈ 75.32
  S ≥ 76
  
  In the second case the sum of the remainders come to 2 bars, so the smallest remainder (S’s) must be less than 2/3:
  
  (S/333)×29 < 6 + 2/3
  S < (20/3)×(333/29) ≈ 76.55
  
  And the only value in these two ranges is: S = 76.
  
  LikeLike
  - Jim Randell 11:21 am on 1 July 2023 Permalink | Reply
    Here is a different approach that calculates bounds on the population sizes of the different groups using the distributions of chocolate bars given in the puzzle text. It then tries population sizes within the calculated bounds to see which give the required distributions.
    
    It also has an internal runtime of less than 1ms.
    
    Run: [ @replit ]
```
from enigma import (irange, inf, divc, divf, cproduct, item, first, printf)

# distribute <k> bars among <ns>
def distribute(k, ns):
  t = sum(ns)
  ds = list()  # allocation
  rs = list()  # (index, remainder)
  # initial allocation
  for (i, n) in enumerate(ns):
    (d, r) = divmod(n * k, t)
    ds.append(d)
    rs.append((i, r))
  # distribute remaining bars
  k -= sum(ds)
  for (i, r) in first(sorted(rs, key=item(1), reverse=1), k):
    ds[i] += 1
  return ds

# find divisions of population <t> that give distributions <dss>
def solve(t, dss):
  # calculate bounds for each group
  (mn, mx) = (dict(), dict())
  for ds in dss:
    k = sum(ds)
    for (i, d) in enumerate(ds):
      # if this distribution was rounded up
      x = divc((d - 1) * t, k)
      if x > mn.get(i, 0): mn[i] = x
      # if this distribution was rounded down
      x = divf((d + 1) * t - 1, k)
      if x < mx.get(i, inf): mx[i] = x
  # choose populations
  for ns in cproduct(irange(mn[i], mx[i]) for i in sorted(mn.keys())):
    if sum(ns) != t: continue
    # check distributions
    if all(distribute(sum(ds), ns) == ds for ds in dss):
      yield ns

# solve for the specified distributions
for (S, E, F) in solve(333, [[7, 9, 12], [6, 10, 13]]):
  if E != 111: continue
  printf("S={S} E={E} F={F}")
```
    It turns out that the condition that E = 111 is not needed, as there is only one set of population sizes that gives the required distributions with the given total population size. (i.e. line 41 is optional).
    
    Although knowing E = 111 allows a straightforward manual solution.
    
    LikeLike
    - Frits 1:43 pm on 1 July 2023 Permalink | Reply
      Without using the mn and mx boundaries and E = 111 this program runs in 100ms.
      
      I wonder if manual solvers would have an elegant way of solving if E = 111 was omitted.
      
      from enigma import SubstitutedExpression # calculate distribution with population numbers <s> def dist(n, s, t): guaranteed = [(n * x) // t for x in s] n_leftovers = n - sum(guaranteed) remainders = sorted([((n * x) % t, i) for i, x in enumerate(s)]) # add leftovers to the people with the highest remainders for i in range(n_leftovers): guaranteed[remainders[2 - i][1]] += 1 return guaranteed # the alphametic puzzle p = SubstitutedExpression( [ "(total := 333)", "(sprites := ABC) < (elves := DEF)", "total - sprites - DEF = GHI", "elves < (fairies := GHI)", "dist(28, [sprites, elves, fairies], total) == [7, 9, 12]", "dist(29, [sprites, elves, fairies], total) == [6, 10, 13]", ], answer="sprites", d2i=dict([(k, "ADG") for k in range(4, 10)]), distinct="", env=dict(dist=dist), reorder=0, verbose=0, # use 256 to see the generated code ) # print answers for ans in p.answers(): print(f"answer: {ans}")
      
      @Jim, notice I had to postpone the assignment of fairies and that in the calculation of GHI I could use variables sprites or elves but not both of them.
      
      LikeLike
      - Frits 2:54 pm on 1 July 2023 Permalink | Reply
        
        or without GHI
        
        # the alphametic puzzle p = SubstitutedExpression( [ "total := 333", "(sprites := ABC) < (elves := DEF)", "fairies := total - sprites - elves", "elves < fairies", "dist(28, [sprites, elves, fairies], total) == [7, 9, 12]", "dist(29, [sprites, elves, fairies], total) == [6, 10, 13]", ], answer="sprites, elves, fairies", d2i=dict([(k, "AD") for k in range(2, 10)]), distinct="", env=dict(dist=dist), reorder=0, verbose=0, # use 256 to see the generated code )
        
        LikeLike
      - Tony Brooke-Taylor 11:25 am on 2 July 2023 Permalink | Reply
        
        I think it is possible to infer bounds for the number of sprites without knowing 111, simply by recognising that with 28 bars, the sprites have the largest remainder (implying > 1/3) while with 29 bars, the sprites have the smallest remainder (implying < 2/3). Only 1 integer value for the number of sprites fits between these bounds.
        
        LikeLike
        
        Jim Randell 11:41 am on 2 July 2023 Permalink | Reply
        
        @Tony: Very neat.
        
        LikeLike
- Frits 6:51 pm on 30 June 2023 Permalink | Reply
  Not many iterations.
```
 
T, E, N = 333, 111, 28
RS = [[7, 9, 12], [6, 10, 13]]

# in 1st round the sprites win against the elves 
# N.S / T > RS[1][0] + 1/3
# in 2nd round the sprites lose against the elves 
# (N + 1).S / T < RS[1][0] + 2/3

for s in range((RS[1][0] * T + T // 3) // N + 1, 
               (RS[1][0] * T + 2 * T // 3) // (N + 1) + 1):
  f = T - E - s
 
  # play 2 rounds
  for rnd in range(2):
    n = N + rnd
    guaranteed = [(n * x) // T for x in (s, E, f)]
    n_leftovers = n - sum(guaranteed)

    remainders = sorted([((n * x) % T, i) for i, x in enumerate([s, E, f])])
    
    # add leftovers to the people with the highest remainders
    for i in range(n_leftovers):
      guaranteed[remainders[2 - i][1]] += 1
    # check with actual distribution  
    if guaranteed != RS[rnd]: break
  else:  # no break  
    print("answer:", s)  
```
  LikeLike
Jim Randell 7:47 am on 14 March 2023 Permalink | Reply
Tags: by: Michael Fletcher
Teaser 2713: Very similar triangles
From The Sunday Times, 21st September 2014 [link] [link]

Two triangles are “similar” if they are the same shape (but not necessarily the same size). I cut out two similar (but not identical) triangles from a piece of A4 paper, all the sides of the triangles being whole numbers of centimetres in length. In fact the two triangles were extra similar in the sense that two of the sides of the first triangle were the same lengths as two of the sides of the second triangle.

What were the lengths of the sides of the smaller triangle?

[teaser2713]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 7:47 am on 14 March 2023 Permalink | Reply
  (See also: Enigma 1198).
  
  For a triangle with sides (a, b, c) (in order), we must have: a + b > c.
  
  The triangle is then scaled up to give another similar triangle (f.a, f.b, f.c) (f > 1).
  
  And two of the sides are the same, which must be: f.a = b, f.b = c.
  
  Hence:
  
  f = b/a = c/b
  a.c = b²
  
  So we can choose a value for b, and then look for a, c sides that multiply to give b².
  
  This Python program runs in 52ms. (Internal runtime is 288µs).
  
  Run: [ @replit ]
```
from enigma import (irange, hypot, intf, divisors_pairs, div, sqrt, printf)

# area of a triangle
def area(a, b, c):
  return 0.5 * sqrt((a + b + c) * (a + b - c) * (c + a - b) * (b + c - a))

# dimensions of an A4 sheet (cm)
(X, Y) = (21.0, 29.7)
A4 = X * Y

# choose a value for b
for b in irange(1, intf(hypot(X, Y))):
  # calculate possible a, c values from divisors of b^2
  for (a, c) in divisors_pairs(b, 2):
    if not (a < b < c and a + b > c): continue
    # calculate d
    d = div(b * c, a)
    if d is None: continue
    if area(a, b, c) + area(b, c, d) > A4: continue
    # output solution
    printf("({a}, {b}, {c}) -> ({b}, {c}, {d})")
```
  Solution: The smaller triangle has sides of length 8, 12, 18 cm.
  
  And the larger triangle has sides of length 12, 18, 27 cm.
  
  The dimensions of the second triangle are 1.5 times those of the first.
  
  Here is a diagram of the two triangles, set on a sheet of A4 paper:
  
  LikeLike
Jim Randell 8:48 am on 29 September 2022 Permalink | Reply
Tags: by: Michael Fletcher
Teaser 2747: Marble jar
From The Sunday Times, 17th May 2015 [link] [link]

At our local fete one of the games consisted of guessing the number of marbles in a jar: some of the marbles were red and the rest were blue. People had to guess how many there were of each colour.

The organiser gave me a couple of clues. Firstly, he told me that there were nearly four hundred marbles altogether. Secondly, he told me that if, when blindfolded, I removed four marbles from the jar, then the chance that they would all be red was exactly one in a four-figure number.

How many red marbles were there, and how many blue?

[teaser2747]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 8:49 am on 29 September 2022 Permalink | Reply
  If there are T marbles in total (T = “nearly 400”) and R of them are red, then the probability of removing 4 red marbles is:
  
  P = (R / T) × ((R − 1) / (T − 1)) × ((R − 2) / (T − 2)) × ((R − 3) / (T − 3))
  P = (R × (R − 1) × (R − 2) × (R − 3)) / (T × (T − 1) × (T − 2) × (T − 3))
  
  And this probability is “one in a four-figure number”, so the largest it can be is 1/1000 and the smallest is 1/9999.
  
  The following Python program considers total numbers of marbles from 399 down to 350, and then looks for numbers of red marbles that give an appropriate value for P.
  
  It runs in 57ms. (Internal run time is 1.2ms).
  
  Run: [ @replit ]
```
from enigma import (irange, printf)

# consider total number of marbles (nearly 400)
for T in irange(399, 350, step=-1):
  # denominator of P
  d = T * (T - 1) * (T - 2) * (T - 3)
  # R = number of red marbles
  for R in irange(4, T):
    # numerator of P
    n = R * (R - 1) * (R - 2) * (R - 3)
    # calculate p = 1/P
    (p, x) = divmod(d, n)
    if p > 9999: continue
    if p < 1000: break
    if x == 0:
      # output solution
      printf("red = {R}, blue = {B}; total = {T} -> P = 1/{p}",B=T - R)
```
  Solution: There were 45 red marbles and 342 blue marbles.
  
  So, 387 marbles in total. And the probability of choosing 4 red is 1/6176.
  
  LikeLike
Jim Randell 9:10 am on 28 July 2022 Permalink | Reply
Tags: by: Michael Fletcher
Teaser 2726: Christmas star
From The Sunday Times, 21st December 2014 [link] [link]

I asked Peter to place the numbers 1 to 10 at the ten intersection points of the Christmas star so that in each of the five lines the four numbers added to the same total. He found that this was impossible so instead he did it with the numbers 1 to 9 together with just one of those digits repeated. In his answer there was just one line in which that digit did not appear.

[In ascending order] what were the four numbers in that line?

[teaser2726]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 9:12 am on 28 July 2022 Permalink | Reply
  (See also: Enigma 1063).
  
  I assume were are talking about a layout like this:
  
  There are 5 lines, and each of the numbers appears on two of the lines.
  
  If we add the lines we will be counting each number twice, and the total will be 5 times the common sum, T.
  
  So, if X is the repeated digit we have:
  
  2 × (1 + 2 + … + 9 + X) = 5 × T
  T = 18 + (2/5)X
  
  Hence: X = 5, and T = 20.
  
  To remove duplicate solutions we can suppose the line that doesn’t include X is (B, C, D, E) and that B < E.
  
  The following run file executes in 98ms.
  
  Run: [ @replit ]
```
#! python3 -m enigma -rr

# suppose the line with no repeated digit is BCDE

SubstitutedExpression

--digits="1-9"
--distinct="BCDE"

# the 5 lines have the same sum (= 20)
"A + C + F + I = 20"
"A + D + G + J = 20"
"B + C + D + E = 20"
"B + F + H + J = 20"
"E + G + H + I = 20"

# all 9 digits are used
"len({A, B, C, D, E, F, G, H, I, J}) = 9"

# 5 is in all the lines except BCDE
"5 not in {B, C, D, E}"
"5 in {A, C, F, I}"
"5 in {A, D, G, J}"
"5 in {B, F, H, J}"
"5 in {E, G, H, I}"

# remove duplicate solutions
"B < E"

--answer="ordered(B, C, D, E)"
--template=""
```
  Solution: The four numbers on the line without the repeated digit are: 1, 3, 7, 9.
  
  There are 12 essentially different layouts, here is one:
  
  LikeLike
Jim Randell 9:59 am on 30 June 2022 Permalink | Reply
Tags: by: Michael Fletcher
Teaser 2720: Better tetra
From The Sunday Times, 9th November 2014 [link] [link]

I have four tetrahedral dice. Each has four identical triangular faces and on each face of each die is one of the numbers 1, 2, 3 or 4 (repeats being allowed on a die). No die uses the same four numbers and, for each die, the sum of its four numbers is ten.

I play a game with my friend. My friend chooses a die first and then I choose one of the remaining three dice. We each throw our chosen die and score the face-down number: sometimes it’s a draw, otherwise the higher number wins. I can choose my die so that I am always more likely to win.

So my friend changes the rules. We now throw our chosen die twice, add the two numbers, and the higher total wins.

Now he knows that there is one die he can choose that makes him more likely to win the game.

What are the four numbers on the winning dice?

The wording for this puzzle has been modified from the originally published version.

[teaser2720]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Frits and Jim Randell are discussing. Toggle Comments
- Jim Randell 10:00 am on 30 June 2022 Permalink | Reply
  (See: [@youtube]).
  
  We assume that the dice are chosen in such a way that each player is aware of which die has been chosen. (So, for example, they may be different colours and arranged on the table, but not be hidden a bag and chosen by putting your hand in and selecting one at random).
  
  When we compare 2 dice, we say that one is “better” than the other, if it is more like to win a game against the other die.
  
  There are 5 possible dice (i.e. 5 possible decompositions of 10 into the numbers 1, 2, 3, 4), but the set only contains 4 of these.
  
  It turns out there is only one possible set of 4, where whatever die A chooses B can always choose a better die.
  
  And from this set we can look to see if there is die which is better when played against each of the other dice.
  
  This Python program runs in 61ms. (Internal runtime is 593µs).
  
  Run: [ @replit ]
```
from enigma import (decompose, subsets, multiset, product, printf)

# return wins for X and Y in a game with k throws?
def play(X, Y, k):
  # generate scores for X and Y
  (sX, sY) = (multiset.from_seq(sum(ss) for ss in subsets(ns, size=k, select="M")) for ns in (X, Y))
  # count wins for X, wins for Y
  wX = wY = 0
  for ((x, nx), (y, ny)) in product(sX.items(), sY.items()):
    if x > y:
      wX += nx * ny
    elif y > x:
      wY += nx * ny
  return (wX, wY)

# is X better than Y in a game with k throws?
def better(X, Y, k):
  (wX, wY) = play(X, Y, k)
  return wX > wY

# generate possible dice
ns = list(decompose(10, 4, increasing=1, sep=0, min_v=1, max_v=4))

# choose a set of 4 dice, and solve the puzzle
for ds in subsets(ns, size=4):

  # with 1 throw, whatever die A chooses, B can always choose a better die
  if not all(any(better(B, A, 1) for B in ds if B != A) for A in ds): continue
  printf("dice = {ds}")

  # with 2 throws, A can choose a die that is better than the others
  for A in ds:
    if not all(better(A, B, 2) for B in ds if B != A): continue
    printf("-> A = {A}")
```
  Solution: The best die in the second game is: (1, 3, 3, 3).
  
  The four dice are:
  
  (1, 1, 4, 4)
  (1, 3, 3, 3)
  (2, 2, 2, 4)
  (2, 2, 3, 3)
  
  And we have:
  
  (1, 1, 4, 4) is beaten by (2, 2, 2, 4)
  (2, 2, 2, 4) is beaten by (2, 2, 3, 3) and (1, 3, 3, 3)
  (2, 2, 3, 3) is beaten by (1, 3, 3, 3)
  (1, 3, 3, 3) is beaten by (1, 4, 4, 4)
  
  So whichever die is chosen first, there is always a choice from the other three that is better.
  
  LikeLike
- Frits 5:54 pm on 30 June 2022 Permalink | Reply
  Apparently we can also compare lists with the less than operator in Python.
```
   
from itertools import product
from enigma import SubstitutedExpression

# number of times x wins from y if die is thrown once
play1 = lambda x, y: sum([p > q for p, q in product(x, y)])

# number of times x wins from y if die is thrown twice
def play2(x, y):
  # add the score of two throws
  x2 = [p + q for p, q in product(x, x)]
  y2 = [p + q for p, q in product(y, y)]
  
  return sum([p > q for p, q in product(x2, y2)])


# the alphametic puzzle
p = SubstitutedExpression(
  [
   "A <= B <= C",
   "10 - A - B - C = D",
   "C <= D",
   
   "E <= F <= G",
   "10 - E - F - G = H",
   "G <= H",
   "(A, B, C, D) < (E, F, G, H)",
   
   "I <= J <= K",
   "10 - I - J - K = L",
   "K <= L",
   "(E, F, G, H) < (I, J, K, L)",
   
   "M <= N <= O",
   "10 - M - N - O = P",
   "O <= P",
   "(I, J, K, L) < (M, N, O, P)",
   
   # with 1 throw, whatever die my friend chooses (x), 
   # I can always choose a better die (y), resulting in 4 wins
   "sum([any(play1(y, x) > play1(x, y) \
         for y in [(A,B,C,D), (E,F,G,H), (I,J,K,L), (M,N,O,P)] if y != x) \
         for x in [(A,B,C,D), (E,F,G,H), (I,J,K,L), (M,N,O,P)]]) == 4",
  ],
  answer="(A,B,C,D), (E,F,G,H), (I,J,K,L), (M,N,O,P)",
  env=dict(play1=play1),
  distinct="",
  digits=range(1, 5),
  reorder=0,
  verbose=0,    # use 256 to see the generated code
)

# check if my friend can win with the die thrown twice
for _, s in p.solve():
  for s1 in s:
    if all(play2(s1, s2) > play2(s2, s1) for s2 in s if s1 != s2):
      print("answer:", s1)
```
  LikeLike
Jim Randell 10:05 pm on 13 February 2022 Permalink | Reply
Tags: by: Michael Fletcher
Teaser 2739: Funny dice
From The Sunday Times, 22nd March 2015 [link] [link]

I have two cube-shaped dice, one red and one blue, with a positive whole number on each face. When I throw the dice and add up the two numbers, the most likely total is 7. The next most likely totals are 6 and 8, the next are 5 and 9, the next are 4 and 10, the next are 3 and 11, and the least likely are 2 and 12. However, my dice are not standard: indeed, the total of the six numbers on the red dice is higher than the total of those on the blue dice.

What are the six numbers on the red dice?

[teaser2739]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Hugh+Casement and Jim Randell are discussing. Toggle Comments
- Jim Randell 10:05 pm on 13 February 2022 Permalink | Reply
  See also: Teaser 3098, Enigma 382, Enigma 646b.
  
  We assume that the 6-sided dice are “fair” (i.e. when one is thrown each face has a 1/6 chance of showing), and also that each of the mentioned values (2-12) is an achievable throw with the pair.
  
  The probability of each combination must be expressible as n/36 and the sum of the probabilities must be 1.
  
  If we consider the lowest possible probabilities:
  
  2, 12 = 1/36
  3, 11 = 2/36
  4, 10 = 3/36
  5, 9 = 4/36
  6, 8 = 5/36
  7 = 6/36
  
  Then we find this accounts for 36/36, so must be the required distribution, and is the same distribution as a pair of standard dice.
  
  So the dice we are looking for are a non-standard pair with the same throw distribution as a standard pair.
  
  There is only one such value for 6-sided dice, known as the Sicherman dice.
  
  We can use the [[ sicherman() ]] function I wrote for Teaser 3098 to solve this problem.
  
  This Python program runs in 46ms (internal run time is 841µs).
  
  Run: [ @replit ]
```
from enigma import printf
from sicherman import sicherman

for (d1, d2) in sicherman(6):
  if sum(d1) != sum(d2):
    printf("{d1} + {d2}")
```
  Solution: The numbers on the red die are: 1, 3, 4, 5, 6, 8.
  
  And the numbers on the blue die are: 1, 2, 2, 3, 3, 4.
  
  LikeLike
- Hugh+Casement 7:12 am on 14 February 2022 Permalink | Reply
  
  We are told ” the least likely are 2 and 12″ but there is no stipulation that they have to occur at all.
  I found eight sets where only sums from 3 to 11 can occur, with frequencies in the order given.
  So for me the puzzle is ill-defined — that’s apart from the misuse of the plural ‘dice’.
  
  LikeLike

Jim Randell 4:15 pm on 4 February 2022 Permalink | Reply
Tags: by: Michael Fletcher

Teaser 3098: Wonky dice

From The Sunday Times, 6th February 2022 [link] [link]

I have two octahedral (eight-faced) dice. There are positive whole numbers (not necessarily all different) on each of their faces. I throw the two dice and add the two numbers that are showing on the top faces. The probability of a total of 2 is 1/64, the probability of a total of 3 is 2/64 and so on. The probabilities of the totals are the same as for a pair of standard octahedral dice (each numbered 1 to 8). Interestingly, however, the highest number on the first die is 11.

What are the eight numbers (in ascending order) on the second die?

[teaser3098]

Jim Randell 4:32 pm on 4 February 2022 Permalink | Reply
(See also: Enigma 382, Enigma 646b).

Using the routines I wrote for Enigma 382 we can find pairs of non-standard octahedral dice that score the same as a standard pair. (The octahedral equivalent of the Sicherman dice [@wikipedia]).

It’s not quick though. The following Python program runs in 30s.
```
from enigma import printf
from dice import (throws, dice)

# a standard pair of octahedral dice
d = (1, 2, 3, 4, 5, 6, 7, 8)
standard = throws(d, d)

# find equivalent non-standard pairs 
for (d1, d2) in dice(8, set(standard), s=1, k=0):
  if not (d1[-1] == 11 or d2[-1] == 11): continue
  if throws(d1, d2) == standard:
    printf("{d1} + {d2}")
```
Solution: The numbers on the second die are: 1, 2, 2, 3, 3, 4, 4, 5.

Without the stipulation that one of the dice has a score of 11 on it there are 3 non-standard pairs that give the same distribution of scores as a standard pair:

(1, 2, 2, 3, 5, 6, 6, 7) + (1, 3, 3, 5, 5, 7, 7, 9)
(1, 2, 3, 3, 4, 4, 5, 6) + (1, 2, 5, 5, 6, 6, 9, 10)
(1, 2, 2, 3, 3, 4, 4, 5) + (1, 3, 5, 5, 7, 7, 9, 11)

The solution is given by the final pair of dice.

LikeLike
- Jim Randell 7:34 pm on 4 February 2022 Permalink | Reply
  With a bit of analysis we can get a much faster program.
  
  The only way to throw 2 is 1 + 1, and for the distribution to be the same as a standard dice, there can only be one 1 on each die.
  
  One die has an 11 on it, which means the maximum possible for the other die is 5. (And there can only be one each of these).
  
  So the dice are:
  
  (1, (2-10)×6, 11) + (1, (2-4)×6, 5)
  
  Limiting the dice considered to just these possibilities gives a faster program.
  
  The following Python program runs in 98ms.
  
  Run: [ @replit ]
```
from enigma import (irange, multiset, printf)

# generate possible throws from a pair of dice
def throws(d1, d2, fn=multiset, op=lambda a, b: a + b):
  return fn(op(a, b) for a in d1 for b in d2)

# a standard pair of octahedral dice
d = (1, 2, 3, 4, 5, 6, 7, 8)
standard = throws(d, d)

# add faces to dice d1 and d2
# n = number of faces on each die
# d1 = dice 1 (so far)
# d1_min, d1_max = min/max values for d1
# d2 = dice 2 (so far)
# d2_min, d2_max = min/max values for d2
# ts = target throws
def solve(n, d1, d1_min, d1_max, d2, d2_min, d2_max, ts):
  if d1.size() == 8:
    if d2.size() == 8:
      # check throws
      if throws(d2, d1) == ts:
        yield (d2, d1)
    else:
      # swap dice over
      yield from solve(n, d2, d2_min, d2_max, d1, d1_min, d1_max, ts)
  else:
    # add face to d1
    for x in irange(d1_min, d1_max):
      d1_ = d1.copy().add(x)
      if throws(d1_, d2).issubset(ts):
        yield from solve(n, d1_, x, d1_max, d2, d2_min, d2_max, ts)
    
# find equivalent non-standard pairs
d1 = multiset.from_seq([1, 5])
d2 = multiset.from_seq([1, 11])
for (d1, d2) in solve(8, d1, 2, 4, d2, 2, 10, standard):
  printf("{d1} + {d2}", d1=sorted(d1), d2=sorted(d2))
```
  LikeLike
  - Frits 5:43 pm on 10 July 2023 Permalink | Reply
    
    @Jim,
    
    Unfortunately your variable d1_min is fixed. If you could set d1_min to the second highest value (with a minimum of 2) the program would be more efficient. A similar change to a recursive program on PuzzlingInPython [https://brg.me.uk/?p=7660#comment-3853] resulted in a 9 times faster program.
    
    LikeLike
    - Jim Randell 10:51 pm on 10 July 2023 Permalink | Reply
      
      @Frits: I think my program already does what you are suggesting.
      
      LikeLike
      - Frits 11:21 pm on 10 July 2023 Permalink | Reply
        
        @Jim, I’m sorry, you are right.
        
        LikeLike
- Jim Randell 10:47 am on 5 February 2022 Permalink | Reply
  The Mathematical justification section on the Wikipedia page for Sicherman dice [link], shows how to construct the factorisation of the generating polynomial for an n-sided standard die using cyclotomic polynomials [link].
  
  We can then look at non-standard ways to combine these factors into pairs of polynomials, such that each polynomial represents a valid 8-sided die, and their product represents the throws of a standard pair of dice. And we are interested in the case where the largest number on one of those dice is 11.
  
  Here is a routine that generates the nth cyclotomic polynomial, using the [[ Polynomial ]] class from the enigma.py library. (Although for this puzzle it is sufficient to find the cyclotomic polynomials for n = 2, 4, 8, which are all powers of a prime, and so easily determined).
```
from enigma import (Polynomial, prime_factor, multiples, irange)

# return the nth cyclotomic polynomial (can be @cached)
def cyclotomic(n):
  if n < 1: return None
  if n == 1: return Polynomial([-1, 1]) # x - 1
  fs = list(prime_factor(n))
  if len(fs) == 1:
    (p, e) = fs[0]
    if e == 1: return Polynomial([1] * n) # prime
    # power of a prime
    q = n // p
    return Polynomial.from_pairs((k * q, 1) for k in irange(0, p - 1))
  else:
    p = Polynomial.from_pairs([(0, -1), (n, 1)]) # x^n - 1
    for d in multiples(fs):
      if d < n:
        (p, r) = p.divmod(cyclotomic(d))
    return p
```
  We can then use this to write a routine that generates pairs of dice that have the same distribution of throws as a pair of standard dice. (For 6-sided dice, the non-standard pair is known as the Sicherman dice):
```
from enigma import (Polynomial, multiset, divisors, subsets, printf)

# find pairs of n-sided dice with the same distribution as a standard pair
def sicherman(n):

  # polynomial p(x) = x must be present on all dice
  x = Polynomial([0, 1])

  # make a die from a collection of polynomial (factor, multiplicity) pairs
  def die(ps):
    fs = multiset.from_pairs(ps)
    p = x * Polynomial.multiply(fs)
    if sum(p) == n and all(c >= 0 for c in p):
      return tuple(sorted(multiset.from_pairs(p.to_pairs())))

  # find the remaining factors of the generating polynomial of a standard die
  fs = list(cyclotomic(d) for d in divisors(n) if d > 1)

  # choose 0, 1, 2 copies of each factor
  for ms in subsets((0, 1, 2), size=len(fs), select="M"):
    # make the first die
    d1 = die(zip(fs, ms))
    if d1:
      # make the second die
      d2 = die((f, 2 - m) for (f, m) in zip(fs, ms))
      if d2 and not (d1 > d2):
        # return the pair
        yield (d1, d2)
```
  And finally we can solve the puzzle, by looking for a pair of 8-sided dice, with the same throw distribution as a pair of standard dice, but where one of the dice has a largest value of 11.
  
  This Python program runs in 47ms (internal run time is just 883µs).
  
  Run: [ @replit ]
```
# solve the puzzle
for (d1, d2) in sicherman(8):
  if d1[-1] == 11 or d2[-1] == 11:
    printf("{d1} + {d2}")
```
  LikeLike
- Frits 11:53 am on 10 July 2023 Permalink | Reply
  
  @Jim,
  
  Where can I find your dice package (except as separate functions in Enigma 382) ?
  
  LikeLike
  - Jim Randell 12:12 pm on 10 July 2023 Permalink | Reply
    
    The code is available on [ @replit ].
    
    LikeLike
A.T.Surherland 9:34 am on 16 February 2022 Permalink | Reply

Refer to a paper by Duane M Bourne,Auburn University,Auburn on the above subject.
This paper lists the octahedral answer plus other configurations..

LikeLike

Frits 12:45 pm on 13 July 2023 Permalink | Reply

Jim mentioned 3 non-standard pairs that give the same distribution of scores as a standard pair. These have symmetrical properties. The (1, 8) ,(2,7), (3,6) and (4,5) positional numbers of dice 1 and 2 all add up to 18.

The following program tries to limit unnecessary work by controlling the range of each number on a die.

 
from itertools import product

# check die (1, (2-10)×6, 11) + (1, (2-4)×6, 5) 

# chances            2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16
# for standard dice  1, 2, 3, 4, 5, 6, 7, 8,  7,  6 , 5,  4,  3,  2 , 1
N, E1 = 8, 11
E2 = 2 * N - E1

# chance dictionary
d = {i: N - abs(i - N - 1) for i in range(2, 2 * N + 1)}

# check for standard chance distribution
def check(s1, s2):
  cd = [0] * (2 * N + 1)
  for m in s1:
    for n in s2:
      if cd[(mn := m + n)] >= d[mn]:
        return False
      cd[mn] += 1
  return True     

# minima range ([2, 2, 3, 3, 3, 4])  
mn1 = sum([[i] * i for i in range(2, 5)], [])[:N - 2]
mn2 = sum([[i] * i for i in range(2, 5)], [])[:N - 2]
# maxima range ([8, 9, 9, 9, 10, 10] and [2, 3, 3, 3, 4, 4])
mx1 = sum([[i] * (E1 - i + 1) for i in range(E1 - 3, E1)], [])[2 - N:]
mx2 = sum([[i] * (E2 - i + 1) for i in range(E2 - 3, E2)], [])[2 - N:]

# try to further lower the maxima for 1st die
# total sum of numbers on both dice is 2 * tri(N)
# minimal sum of 2nd die is 1 + E2 + sum(mn2) = 23
# maximal value of 2nd digit is (N * (N + 1) - 23 - 1 - E1) / 6 = 6.17
# maximal value of 3rd digit is (N * (N + 1) - 23 - 12 - 2) / 5 = 7
# maximal value of 4th digit is (N * (N + 1) - 23 - 12 - 2 - 2) / 4 = 8.x
# maximal value of 5th digit is (N * (N + 1) - 23 - 12 - 2 - 2 - 3) / 3 = 10
mx = N * (N + 1) - (sum(mn2) + 1 + E2 + 1 + E1) 
mx1 = [min((mx - sum(mn2[:i])) // (N - 2 - i), mx1[i]) for i in range(6)]

# die 1: [A, B, C, D, E, F, H]
A, H = 1, E1
# product can be used instead of 6 separate loops as 2nd die ranges are compact
# (and don't allow for decreasing variables)
for n6 in product(*[range(mn2[i], mx2[i] + 1) for i in range(6)]):
  die2 = (1, ) + n6 + (E2, )
  sum2 = sum(die2)
  # skip if B gets too high (total numbers on dice will exceed N * (N + 1))
  m = (rB := N * (N + 1) - sum([A, H]) - sum2) // 6
  for B in range(mn1[0], min(m, mx1[0]) + 1):
    if not check([A, B, H], die2): continue
    for C in range(B, min((rC := rB - B) // 5, mx1[1]) + 1):
      if not check([A, B, C, H], die2): continue
      for D in range(max(mn1[2], C), min((rD := rC - C) // 4, mx1[2]) + 1):
        if not check([A, B, C, D, H], die2): continue
        for E in range(max(mn1[3], D), min((rD - D) // 3, mx1[3]) + 1):
          if not check([A, B, C, D, E, H], die2): continue
          for F in range(E, mx1[4] + 1):
            G = N * (N + 1) - sum([A, B, C, D, E, F, H]) - sum2
            if not F <= G < H: continue
            if not check([A, B, C, D, E, F, G, H], die2): continue
            print("answer:", sorted(die2))

LikeLike

Jim Randell 9:41 am on 14 September 2021 Permalink | Reply
Tags: by: Michael Fletcher
Teaser 2822: Losing weight
From The Sunday Times, 23rd October 2016 [link] [link]

The members of our local sports club are split into two groups. Originally the groups had the same number of members, and the first group contained member Waites who weighed 100kg (and indeed that was the average weight of the members of the first group). Then the club trainer decided that the groups were overweight and that, for each of the next ten weeks, for each group the average weight of the members should be reduced by one kilogram.

This was achieved by simply transferring a member from the first group to the second group each week, and Waites was the tenth member to be transferred.

How many members are there in the club?

[teaser2822]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 9:42 am on 14 September 2021 Permalink | Reply
  This Python program considers the number of members in each group, and performs the transfers to see if the conditions of the puzzle are met.
  
  It runs in 54ms.
  
  Run: [ @replit ]
```
from enigma import irange, inf, printf

# S = starting average weight of group A
# K = number of transfers from A -> B
# W = weight of transfer number K
(S, K, W) = (100, 10, 100)

# suppose each group has n members
for n in irange(K + 1, inf):
  m = 2 * n
  printf("n={n} ({m} members)")
  # initial total weight of the group is...
  t0 = S * n
  # K members of the group are transferred
  for k in irange(1, K):
    # the total weight becomes
    t1 = (S - k) * (n - k)
    w = t0 - t1
    # average weights for group A and group B
    (a, b) = (S - k, w + n + k - 1)
    printf("{k}: transfer = {w}, A avg {a0} -> {a}, B avg {b0} -> {b}", a0=a + 1, b0=b + 1)
    t0 = t1

  if w == W:
    printf("*** SOLUTION: n={n} ({m} members) ***")
    break
  printf()
```
  Solution: There are 38 members in the club.
  
  The average weight in Group 1 decreases by 1 kg per week from 100 to 90, and the average weight in Group 2 decreases by 1 kg per week from 138 to 128. After 10 weeks there are 9 members in Group 1 and 29 members in Group 2.
  
  Analytically:
  
  If we suppose each group has n members, the the total weight of Group 1 starts out at 100n.
  
  After the first transfer the average weight of Group 1 is 99 kg, so the total weight is 99(n − 1).
  
  And the difference between these two totals accounts for the weight of the first person transferred:
  
  w[1] = 100n − 99(n − 1)
  w[1] = n + 99
  
  After second transfer the average weight of Group 1 is 98kg, so the weight of the second person transferred is:
  
  w[2] = 99(n − 1) − 98(n − 2)
  w[2] = n + 97
  
  In general at the kth transfer, we have:
  
  w[k] = (100 − k + 1)(n − k + 1) − (100 − k)(n − k)
  w[k] = n + 101 − 2k
  
  And we are told the weight of the 10th person transferred is 100 kg:
  
  w[10] = 100
  n + 101 − 20 = 100
  n = 19
  
  So, there are 2n = 38 members in total.
  
  LikeLike
Jim Randell 12:00 pm on 24 August 2021 Permalink | Reply
Tags: by: Michael Fletcher
Teaser 2813: Katy’s piggy banks
From The Sunday Times, 21st August 2016 [link] [link]

Our granddaughter Katy has two piggy banks containing a mixture of 10p and 50p coins, making a grand total of 10 pounds. The first piggy bank contains less than the other, and in it the number of 50p coins is a multiple of the number of 10p coins.

Katy chose a coin at random from the first piggy bank and then put it in the second. Then she chose a coin at random from the second and put it in the first. She ended up with the same amount of money in the first piggy bank as when she started. In fact there was a 50:50 chance of this happening.

How much did she end up with in the first piggy bank?

[teaser2813]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Linda, John Crabtree, and Jim Randell are discussing. Toggle Comments
- Jim Randell 12:01 pm on 24 August 2021 Permalink | Reply
  The following Python program all possible distributions of coins between the two piggy banks. It runs in 57ms.
  
  Run: [ @replit ]
```
from enigma import (Rational, irange, express, div, printf)

Q = Rational()

# consider the amount in the first piggy bank (less than 5 pounds)
for s1 in irange(0, 490, step=10):
  for (t1, f1) in express(s1, [10, 50]):
    # f1 is a (proper) multiple of t1
    d = div(f1, t1)
    if d is None or d < 2: continue
    n1 = f1 + t1

    # and the amount in the second piggy bank
    s2 = 1000 - s1
    for (t2, f2) in express(s2, [10, 50]):
      n2 = f2 + t2

      # probability of withdrawing a 50p from both banks
      p1 = Q(f1, n1) * Q(f2 + 1, n2 + 1)

      # probability of withdrawing a 10p from both banks
      p2 = Q(t1, n1) * Q(t2 + 1, n2 + 1)

      # together they should make 1/2
      if p1 + p2 == Q(1, 2):
        printf("s1={s1} ({f1}, {t1}), s2={s2} ({f2}, {t2}) [p1 = {p1}, p2 = {p2}]")
```
  Solution: Katy ended up with £3.20 in the first piggy bank.
  
  The first piggy bank had £3.20 in it (2× 10p + 6× 50p; and 6 is a proper multiple of 2).
  
  The second piggy bank had the £6.80 in it (13× 10p + 11× 50p).
  
  We assume the two denominations of coin are equally likely to be chosen.
  
  The same denomination must be chosen in both cases, so the probability of transferring a 50p from the first bank to the second is: 6/8 = 3/4.
  
  And there are now 12× 50p coins and 13× 50p coins in the second piggy bank, so the probability of transferring a 50p from the second bank back to the first is: 12/25.
  
  p1 = (3/4)(12/25) = 9/25
  
  Similarly the probability of moving a 10p back and forth is:
  
  p2 = (1/4)(14/25) = 7/50
  
  Adding these together gives the total probability of the same denomination coin moving back and forth:
  
  p1 + p2 = 9/25 + 7/50 = 1/2
  
  LikeLike
- John Crabtree 4:57 am on 27 August 2021 Permalink | Reply
  
  Let the total in the first bag = 10a + 50ma
  Let the total in the second bag = 10b + 50c
  The probability condition leads to (m – 1)(b – c – 1) = 2, and so m = 2 or 3, and b – c + m = 5
  This leads to c = 16 – ma + (a + 1)(m – 1)/6
  a < 5 and so m = 3 and a = 2.
  
  LikeLike
- Linda 11:27 am on 27 January 2023 Permalink | Reply
  
  This is a brilliant problem
  
  LikeLike

Jim Randell 6:42 am on 22 July 2021 Permalink | Reply
Tags: by: Michael Fletcher

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]

Jim Randell 6:43 am on 22 July 2021 Permalink | Reply

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:

A: (5r + 10b) → P(red) = 1/3
B: (1r + 5b) → P(red) = 1/6
C: (1r + 0b) → P(red) = 1
Total P(red) = (1/3 + 1/6 + 1) / 3 = 1/2

Move 5b from B to A:

A: (5r + 15b) → P(red) = 1/4
B: (1r + 0b) → P(red) = 1
C: (1r + 0b) → P(red) = 1
Total P(red) = (1/4 + 1 + 1) / 3 = 3/4

A: (5r + 9b) → P(red) = 5/14
B: (1r + 6b) → P(red) = 1/7
C: (1r + 0b) → P(red) = 1
Total P(red) = (5/14 + 1/7 + 1) / 3 = 1/2

Move 6b from B to A:

A: (5r + 15b) → P(red) = 1/4
B: (1r + 0b) → P(red) = 1
C: (1r + 0b) → P(red) = 1
Total P(red) = (1/4 + 1 + 1) / 3 = 3/4

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:

((R − 2)r + (B)b) (1r + 0b) (1r + 0b)

(so we require R ≥ 2).

Then for the overall probability of choosing a red to be 3/4 we have:

(1/3)(((R − 2) / (R + B − 2)) + (1/1) + (1/1)) = 3/4
(R − 2) / (R + B − 2) = 1/4
4R − 8 = R + B − 2
B = 3R − 6

Which means for any R value, there is only one corresponding B value.

So the final configuration is:

((R − 2)r + (3R − 6)b) (1r + 0b) (1r + 0b)

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:

((R − 2)r + (3R − 6 − x)b) (1r + xb) (1r + 0b)

And the overall probability of choosing a red is 1/2, so:

(1/3)(((R − 2) / (4R − 8 − x)) + (1 / (1 + x)) + 1) = 1/2
((R − 2) / (4R − 8 − x)) + (1 / (1 + x)) = 1/2
(2R − 4)(1 + x) + 2(4R − 8 − x) = (1 + x)(4R − 8 − x)
10R − 6x + 2Rx − 20 = 4R − 8 − x + 4Rx − 8x − x²
x² + (3 − 2R)x + (6R − 12) = 0

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:

x² + (3 − 2(2k + 3))x + (6(2k + 3) − 12) = 0
x² − (4k + 3)x + (12k + 6) = 0

And using the quadratic formula, we see this has solutions:

2x = (4k + 3) ± sqrt((4k − 3)² − 24)

Both sides are integers, so: (4k − 3)² − 24 must be an odd perfect square, say (2z + 1)²:

(4k − 3)² − 24 = (2z + 1)²
(4k − 3)² − (2z + 1)² = 24
(4k + 2z − 2)(4k − 2z − 4) = 24

The LHS is the product of 2 integers, (a, b) that give 24.

4k + 2z − 2 = a
4k − 2z − 4 = b
⇒ k = (a + b + 6) / 8

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 | Reply

@Jim, Interesting.

We can speed up the general program by (among others):

 
1 - do the n3 checks earlier (lines 32-34)
2 - demand n3 > 0 and all r1, r2, r3 > 0 as otherwise a 75 per cent chance is impossible by moving black balls.
3 - let T start from 6 as (1, 3), (1, 0), (1, 0) is the first viable option to get chance 75 per cent.

LikeLike

Jim Randell 3:03 pm on 22 July 2021 Permalink | Reply

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 | Reply

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

Jim Randell 2:36 pm on 5 November 2020 Permalink | Reply
Tags: by: Michael Fletcher
Teaser 2762: What a gem!
From The Sunday Times, 30th August 2015 [link] [link]

A friend showed me a beautiful gem with shiny flat faces and lots of planes of symmetry. After a quick examination I was able to declare that it was “perfectly square”. This puzzled my friend because none of the faces had four edges. So I explained by pointing out that the gem’s number of faces was a perfect square, its number of edges was a perfect square, and its number of vertices was a perfect square.

How many faces did it have, and how many of those were triangular?

[teaser2762]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 2:37 pm on 5 November 2020 Permalink | Reply
  This is a similar puzzle to Enigma 1376, and we can use a similar program to find possible (vertex, face, edge) counts.
```
from enigma import irange, subsets, printf

# some squares
squares = set(i * i for i in irange(2, 15))

# for a simple polyhedron V + F - E = 2
for (V, F) in subsets(squares, size=2, select="M"):
  E = V + F - 2
  # also 2E >= 3F and 3V
  if 3 * max(V, F) > 2 * E: continue
  # E should be a square
  if E not in squares: continue

  printf("E={E} V={V} F={F}")
```
  We find the candidates are the same, i.e.: (V=9, F=9, E=16).
  
  So we are looking at an elongated square pyramid or an octagonal pyramid. And only the octagonal pyramid has no quadrilateral faces.
  
  Solution: The gem has 9 faces. 8 of the faces are triangular.
  
  And the other face is octagonal:
  
  LikeLike
Jim Randell 2:06 pm on 22 September 2020 Permalink | Reply
Tags: by: Michael Fletcher
Teaser 2755: Female domination
From The Sunday Times, 12th July 2015 [link] [link]

In the village of Alphaville, the number of females divided by the number of males was a certain whole number. Then one man and his wife moved into the village and the result was that the number of females divided by the number of males was one less than before. Now today two more such married couples have moved into the village, but the number of females divided by the number of males is still a whole number.

What is the population of the village now?

[teaser2755]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 2:07 pm on 22 September 2020 Permalink | Reply
  I think this Teaser marks the start of my regular solving (i.e. I solved all subsequent Teasers at the time of their publication). So I should have notes that enable me to fill in the gaps of Teasers set after this one. (Currently I have posted all Teasers from Teaser 2880 onwards, and quite a few earlier ones – there are currently 353 Teasers available on the site). So in some ways it corresponds to Enigma 1482 on the Enigmatic Code site.
  
  This Python program runs in 45ms.
  
  Run: [ @replit ]
```
from enigma import (irange, inf, divisors_pairs, div, printf)

# generate solutions
def solve():
  # consider total population
  for t in irange(2, inf):
    # divide the population into males and females
    for (d, m) in divisors_pairs(t, every=1):
      if d < 2: continue
      # p = initial f / m ratio
      p = d - 1
      f = t - m
      # ratio (f + 1) / (m + 1) = p - 1
      if not ((p - 1) * (m + 1) == f + 1): continue
      # ratio (f + 3) / (m + 3) is an integer
      q = div(f + 3, m + 3)
      if q is None: continue
      # final population (after 3 extra couples have moved in)
      yield (t + 6, m, f, p, q)

# find the first solution
for (pop, m, f, p, q) in solve():
  printf("final population = {pop} [m={m} f={f} p={p} q={q}]")
  break
```
  Solution: The population of the village is now 24.
  
  Initially there were 3 males and 15 females in the village (initial ratio = 15 / 3 = 5).
  
  The addition of one couple gave 4 males and 16 females (new ratio = 16 / 4 = 4).
  
  And the addition of two extra couples gives 6 males and 18 females (final ratio = 18 / 6 = 3).
  
  So the final population is: 6 + 18 = 24.
  
  Manually:
  
  Initially the ratio of females to males is an integer p:
  
  p = f / m
  f = p.m
  
  The ratio changes to (p − 1) with 1 more male and 1 more female:
  
  (p − 1) = (f + 1) / (m + 1)
  (p − 1) = (p.m + 1) / (m + 1)
  (p − 1)(m + 1) = p.m + 1
  p.m + p − m − 1 = p.m + 1
  p = m + 2
  
  And the ratio (f + 3) / (m + 3) is also an integer q:
  
  (p.m + 3) / (m + 3) = q
  ((m + 2)m + 3) / (m + 3) = q
  (m² + 2m + 3) / (m + 3) = q
  (m − 1) + 6 / (m + 3) = q
  
  So (m + 3) is a divisor of 6, greater than 3. i.e. (m + 3) = 6, so m = 3:
  
  m = 3
  p = 5
  f = 15
  q = 3
  
  So the solution is unique.
  
  LikeLike
Jim Randell 3:01 pm on 13 September 2020 Permalink | Reply
Tags: by: Michael Fletcher
Teaser 2731: City snarl-up
From The Sunday Times, 25th January 2015 [link]

I had to drive the six miles from my home into the city centre. The first mile was completed at a steady whole number of miles per hour (and not exceeding the 20mph speed limit). Then each succeeding mile was completed at a lower steady speed than the previous mile, again at a whole number of miles per hour.

After two miles of the journey my average speed had been a whole number of miles per hour, and indeed the same was true after three miles, after four miles, after five miles, and at the end of my journey.

How long did the journey take?

[teaser2731]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell and Frits are discussing. Toggle Comments
- Jim Randell 3:02 pm on 13 September 2020 Permalink | Reply
  My first program looked at all sequences of 6 decreasing speeds in the range 1 to 20 mph. It was short but took 474ms to run.
  
  But it’s not much more work to write a recursive program that checks the average speeds as it builds up the sequence.
  
  This Python 3 program runs in 50ms.
  
  Run: [ @repl.it ]
```
from enigma import (Rational, irange, as_int, catch, printf)

Q = Rational()  # select a rational implementation

# check speeds for distance d, give a whole number average
check = lambda d, vs: catch(as_int, Q(d, sum(Q(1, v) for v in vs)))

# solve for k decreasing speeds, speed limit m
def solve(k, m, vs=[]):
  n = len(vs)
  # are we done?
  if n == k:
    yield vs
  else:
    # add a new speed
    for v in irange(m, 1, step=-1):
      vs_ = vs + [v]
      if n < 1 or check(n + 1, vs_):
        yield from solve(k, v - 1, vs_)

# find a set of 6 speeds, not exceeding 20mph
for vs in solve(6, 20):
  # calculate journey time (= dist / avg speed)
  t = Q(6, check(6, vs))
  printf("speeds = {vs} -> time = {t} hours")
```
  Solution: The journey took 2 hours in total.
  
  The speeds for each mile are: 20mph, 12mph, 6mph, 5mph, 2mph, 1mph.
  
  Giving the following times for each mile:
  
  mile 1: 3 minutes
  mile 2: 5 minutes
  mile 3: 10 minutes
  mile 4: 12 minutes
  mile 5: 30 minutes
  mile 6: 60 minutes
  total: 120 minutes
  
  And the following overall average speeds:
  
  mile 1: 20 mph
  mile 2: 15 mph
  mile 3: 10 mph
  mile 4: 8 mph
  mile 5: 5 mph
  mile 6: 3 mph
  
  LikeLike
- Frits 1:40 pm on 16 September 2020 Permalink | Reply
  With a decent elapsed time.
```
 
from enigma import SubstitutedExpression 

# is average speed a whole number
def avg_int(li):
  miles = len(li)
  time = 0
  # Add times (1 mile / speed)
  for i in range(miles):
    time += 1 / li[i]
  #return miles % time == 0
  return (miles / time).is_integer()

p = SubstitutedExpression([
    "AB <= 20",
    # no zero speeds allowed
    "KL > 0",
    # speeds are descending
    "AB > CD",
    "CD > EF",
    "EF > GH", 
    "GH > IJ",
    "IJ > KL",
    # average speeds must be whole numbers
    "avg_int([AB, CD])",
    "avg_int([AB, CD, EF])",
    "avg_int([AB, CD, EF, GH])",
    "avg_int([AB, CD, EF, GH, IJ])",
    "avg_int([AB, CD, EF, GH, IJ, KL])",
    ],
    verbose=0,
    answer="(AB, CD, EF, GH, IJ, KL, \
            60/AB + 60/CD + 60/EF + 60/GH + 60/IJ + 60/KL)",
    env=dict(avg_int=avg_int), # external functions
    d2i="",            # allow number respresentations to start with 0
    distinct="",       # letters may have same values                     
)

# Solve and print answer
for (_, ans) in p.solve(): 
  print("Speeds:", ", ".join(str(x) for x in ans[:-1]))
  print(f"Minutes: {round(ans[6])}")  

# Output:
#
# Speeds: 20, 12, 6, 5, 2, 1
# Minutes: 120
```
  @Jim, do you discourage the use of / for division?
  
  Is there a better way to check that a division by a float is a whole number?
  I tried divmod(p, r) but sometimes r is close to zero like x E-19.
  (miles % time == 0) also failed.
  
  LikeLike
  - Jim Randell 2:39 pm on 16 September 2020 Permalink | Reply
    
    @Frits
    
    I am careful about my use of / for division, as it behaves differently in Python 2 and Python 3 (and I do generally still attempt to write code that works in both Python 2 and Python 3 – although the day when Python 2 is abandoned completely seems to be getting closer).
    
    But I do tend to avoid using float() objects unless I have to. Floating point numbers are only ever approximations to a real number, so you have to allow some tolerance when you compare them, and rounding errors can build up in complex expressions. (Python recently added math.isclose() to help with comparing floats).
    
    On the other hand, I am a big fan of the Python fractions module, which can represent rational numbers and operate on them to give exact answers. So if I can’t keep a problem within the integers (which Python also will represent exactly) I tend to use fraction.Fraction if possible.
    
    (The only problem is that it is a bit slower, but for applications that need more speed gmpy2.mpq() can be used, which gives a faster implementation of rationals. I might add a Rational() function to enigma.py to search for an appropriate rational implementation).
    
    LikeLike
    - Jim Randell 4:46 pm on 16 September 2020 Permalink | Reply
      I have added code to enigma.py to allow selecting of a class for rational numbers.
      
      So now instead of using:
      
      from fractions import Fraction as Q
      
      You can import the function Rational() from enigma.py and then use it to select a rational implementation:
      
      from enigma import Rational Q = Rational() # or ... Q = Rational(verbose=1)
      
      Setting the verbose parameter will make it display which implementation is being used.
      
      I’ve got gmpy2 installed on my system and this change improved the runtime of my original code from 448ms (using fractions.Fraction under PyPy 7.3.1) to 153ms (using gmpy2.mpq under CPython 2.7.18).
      
      LikeLike
Jim Randell 9:50 am on 12 December 2019 Permalink | Reply
Tags: by: Michael Fletcher
Teaser 2889: Catching the bus
From The Sunday Times, 4th February 2018 [link] [link]

I can travel to town by either the number 12 bus or the number 15 bus. The number 12 bus leaves every 12 minutes and the number 15 bus leaves every 15 minutes. The first number 15 bus leaves soon after the first number 12 bus. I arrive at the bus stop at random and catch the first bus to arrive.

If the probability of me catching the number 15 bus is 2/5 how soon does the first number 15 bus leave after the first number 12 bus?

[teaser2889]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 9:51 am on 12 December 2019 Permalink | Reply
  (See also: Teaser 2904).
  
  If we assume the #12 leaves at t=0, 12, 24, 36, 48, 60 minutes, and the first #15 bus leaves at x minutes after the first #12 bus, then if x < 3 we have the following schedule:
  
  +00: #12 bus
  [x minute wait for #15 bus]
  +x: #15 bus
  [(12 − x) minute wait for #12 bus]
  +12: #12 bus
  [(3 + x) minute wait for #15 bus]
  +(x + 15): #15 bus
  [(9 − x) minute wait for #12 bus]
  +24: #12 bus
  [(6 + x) minute wait for #15 bus]
  +(x + 30): #15 bus
  [(6 − x) minute wait for #12 bus]
  +36: #12 bus
  [(9 + x) minute wait for #15 bus]
  +(x + 45): #15 bus
  [(3 − x) minute wait for #12 bus]
  +48: #12 bus
  [12 minute wait for #12 bus]
  +60: #12 bus
  
  And the pattern repeats in subsequent hours.
  
  If we arrive at a random time during the hour the probability of catching a #15 bus is:
  
  (x + (x + 3) + (x + 6) + (x + 9)) / 60 = 2/5
  (4x + 18) / 60 = 2/5
  2x = 3
  x = 3/2
  
  Which means the first #15 bus leaves 1m30s after the first #12 bus.
  
  However, if 3 < x < 6, then the #15 bus that leaves at (x + 45), departs after the #12 bus that departs at 45 minutes past the hour.
  
  We get:
  
  (x + (x + 3) + (x + 6) + (x − 3)) / 60 = 2/5
  (4x + 6) / 60 = 2/5
  4x = 18
  x = 9/2
  
  Which means the first #15 bus leaves 4m30s after the first #12 bus.
  
  And we also get workable values at 7m30s and 10m30s.
  
  As found by this program which considers possible values (in seconds) for the times of the first #15 bus between the first and second #12 buses.
  
  Run: [ @repl.it ]
```
from enigma import (irange, printf)

# time (in seconds) the #12 bus leaves
times12 = list((x, 12) for x in irange(0, 3600, step=12 * 60))

# consider times that the first #15 bus leaves
# (or 60 * 60 - 1 for further solutions)
for t in irange(1, 12 * 60 - 1): 
  times15 = list((x, 15) for x in irange(t, 3600, step=15 * 60))
  times = times12 + times15
  times.sort()

  # sum the wait times for each type of bus
  w = { 12: 0, 15: 0 }
  x0 = 0
  for (x, n) in times:
    w[n] += x - x0
    x0 = x

  if 3 * w[15] == 2 * w[12]:
    (m, s) = divmod(t, 60)
    printf("t={t} (+{m}m{s}s) [{times}]")
```
  We are told that “the first #15 bus leaves soon after the first #12 bus”, so we can suppose we want the earliest possible value of 1m30s (although 4m30s would also seems to be “soon after” the first #12 bus).
  
  Solution: The first number 15 bus leaves 1m30s after the first number 12 bus.
  
  If the first #15 bus does not have to leave before the second #12 bus then we can get solutions where the #15 buses can run on a timetable of integer minutes, and still satisfy the probability constraint given in the hour from the first #12 bus.
  
  For instance if the first #15 bus leaves at 17m (so the timetable is: 17m, 32m, 47m, and then: 1h2m, 1h17m, 1h32m, 1h47m, …) then the probability of catching a #15 bus in the first hour is 0.4, similarly if the first #15 leaves at 29m.
  
  Here is a graph of “the probability of catching a #15 bus in the first hour” (y-axis) against “time of departure of the first #15 bus” (x-axis).
  
  We see that the probability is 0.4 for times of: 1m30s, 4m30s, 7m30s, 10m30s, 13m30s, 17m, 29m.
  
  LikeLike
Jim Randell 2:15 pm on 12 June 2019 Permalink | Reply
Tags: by: Michael Fletcher
Teaser 2904: Catching another bus
From The Sunday Times, 20th May 2018 [link] [link]

I want to catch a bus into town, and I arrive at the bus stop at a random time.

The number 12 bus runs every 12 minutes, the number 15 bus runs every 15 minutes and the number 20 bus runs every 20 minutes.

All the buses leave the bus stop at an exact number of minutes past the hour and no two buses leave at the same time. Interestingly, given the above information, the probability that I catch a number 12 bus is as small as it possibly could be.

What is the probability that I catch a number 12 bus?

[teaser2904]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 2:16 pm on 12 June 2019 Permalink | Reply
  The period between each type of bus exactly divides 60, so in any hour period the pattern of buses is the same as the previous hour.
  
  So if we make a timetable of the buses, as no buses arrive at the same time, the periods in between buses arriving is spent waiting for the next bus, so by examining the gaps between buses we can determine the proportions of the hour spent waiting for each type of bus.
  
  This Python program runs in 76ms.
  
  Run: [ @repl.it ]
```
from enigma import (irange, update, tuples, Accumulator, unpack, fraction, printf)

# period we are interested in (60 minutes)
T = 60

# generate timetables for a bus leaving at intervals of <t>
# that doesn't coincide with the times in <d>
# yield: (<t0>, <d1>), where:
# t0 = earliest time for the bus
# d1 = updated cumulative timetable
def generate(t, d):
  for t0 in irange(0, t - 1):
    ks = list(irange(t0, T - 1, step=t))
    if any(k in d for k in ks): continue
    yield (t0, update(d, ((k, t) for k in ks)))

# find minimum wait for #12 bus
r = Accumulator(fn=min)

# suppose the #20 bus leaves at t=0
t20 = 0
ts1 = dict((t, 20) for t in irange(t20, T - 1, step=20))

# consider the time the first #15 bus leaves
for (t15, ts2) in generate(15, ts1):

  # consider the time the first #12 bus leaves
  for (t12, ts3) in generate(12, ts2):

    # make the timeline
    ts = sorted(ts3.items(), key=unpack(lambda t, n: t))
    (t, n) = ts[0]
    ts.append((t + T, n))

    # count the total waits for each type of bus
    w = { 12: 0, 15: 0, 20: 0 }
    for ((t1, _), (t2, n)) in tuples(ts, 2):
      w[n] += t2 - t1
    r.accumulate_data(w[12], (t12, t15, t20))

# output minimal solution
(a, b) = fraction(r.value, T)
printf("min P(12) = {a}/{b} [{r.data}]")
```
  Solution: The probability of catching a number 12 bus is 7/20.
  
  If we start the hour when a #20 bus is at the stop, then the #20 buses arrive at: +0, +20, +40, +60.
  
  The first #12 bus arrives at +5 minutes, so has a timetable of: +5, +17, +29, +41, +53.
  
  The first #15 bus arrives at +13 minutes, so has a timetable of: +13, +28, +43, +58.
  
  So the timetable looks like this:
  
  +00: #20 bus
  (5 minute wait for #12 bus)
  +05: #12 bus
  (8 minute wait for #15 bus)
  +13: #15 bus
  (4 minute wait for #12 bus)
  +17: #12 bus
  (3 minute wait for #20 bus)
  +20: #20 bus
  (8 minute wait for #15 bus)
  +28: #15 bus
  (1 minute wait for #12 bus)
  +29: #12 bus
  (11 minute wait for #20 bus)
  +40: #20 bus
  (1 minute wait for #12 bus)
  +41: #12 bus
  (2 minute wait for #15 bus)
  +43: #15 bus
  (10 minute wait for #12 bus)
  +53: #12 bus
  (5 minute wait for #15 bus)
  +58: #15 bus
  (2 minute wait for #20 bus)
  +60: #20 bus
  
  Adding the waiting times for each type of bus we get:
  
  21 minutes for #12 bus
  23 minutes for #15 bus
  16 minutes for #20 bus
  
  So if we arrive at a random time during the hour the probability the next bus is #12 is 21/60 = 7/20.
  
  LikeLike

	Jim Randell on Teaser 2415: [Double shif…
	Jim Randell on Teaser 3305: Things with scale…
	Jim Randell on Teaser 3305: Things with scale…
	Jim Randell on Teaser 2462: [What NOW?]
	Frits on Teaser 2462: [What NOW?]
	ruudvanderham on Teaser 2462: [What NOW?]
	Jim Randell on Teaser 2462: [What NOW?]
	Frits on Teaser 2363: [A round num…

Search

Recent Posts

Recent Comments

Archives

Categories

Subscribe

RSS Links

Site Stats

Meta

Tagged: by: Michael Fletcher Toggle Comment Threads | Keyboard Shortcuts

Jim Randell 6:48 am on 5 January 2025 Permalink | Reply Tags: by: Michael Fletcher

Rate this:

Share:

Jim Randell 7:02 am on 5 January 2025 Permalink | Reply

Tony Smith 4:29 pm on 5 January 2025 Permalink | Reply

Jim Randell 4:57 pm on 5 January 2025 Permalink | Reply

Reply Cancel reply

Jim Randell 1:49 am on 27 October 2024 Permalink | Reply Tags: by: Michael Fletcher

Rate this:

Share:

Jim Randell 2:13 am on 27 October 2024 Permalink | Reply

Jim Randell 6:12 am on 15 September 2024 Permalink | Reply Tags: by: Michael Fletcher

Rate this:

Share:

Jim Randell 6:21 am on 15 September 2024 Permalink | Reply

Jim Randell 6:08 pm on 15 September 2024 Permalink | Reply

GeoffR 5:34 pm on 15 September 2024 Permalink | Reply

Ruud 10:06 am on 17 September 2024 Permalink | Reply

Jim Randell 3:37 pm on 30 June 2023 Permalink | Reply Tags: by: Michael Fletcher

Rate this:

Share:

Jim Randell 3:58 pm on 30 June 2023 Permalink | Reply

Jim Randell 11:21 am on 1 July 2023 Permalink | Reply

Frits 1:43 pm on 1 July 2023 Permalink | Reply

Frits 2:54 pm on 1 July 2023 Permalink | Reply

Tony Brooke-Taylor 11:25 am on 2 July 2023 Permalink | Reply

Jim Randell 11:41 am on 2 July 2023 Permalink | Reply

Frits 6:51 pm on 30 June 2023 Permalink | Reply

Jim Randell 7:47 am on 14 March 2023 Permalink | Reply Tags: by: Michael Fletcher

Rate this:

Share:

Jim Randell 7:47 am on 14 March 2023 Permalink | Reply

Jim Randell 8:48 am on 29 September 2022 Permalink | Reply Tags: by: Michael Fletcher

Rate this:

Share:

Jim Randell 8:49 am on 29 September 2022 Permalink | Reply

Jim Randell 9:10 am on 28 July 2022 Permalink | Reply Tags: by: Michael Fletcher

Rate this:

Share:

Jim Randell 9:12 am on 28 July 2022 Permalink | Reply

Jim Randell 9:59 am on 30 June 2022 Permalink | Reply Tags: by: Michael Fletcher

Rate this:

Share:

Jim Randell 10:00 am on 30 June 2022 Permalink | Reply

Frits 5:54 pm on 30 June 2022 Permalink | Reply

Jim Randell 10:05 pm on 13 February 2022 Permalink | Reply Tags: by: Michael Fletcher

Rate this:

Share:

Jim Randell 10:05 pm on 13 February 2022 Permalink | Reply

Hugh+Casement 7:12 am on 14 February 2022 Permalink | Reply

Jim Randell 4:15 pm on 4 February 2022 Permalink | Reply Tags: by: Michael Fletcher

Rate this:

Share:

Jim Randell 4:32 pm on 4 February 2022 Permalink | Reply

Jim Randell 7:34 pm on 4 February 2022 Permalink | Reply

Frits 5:43 pm on 10 July 2023 Permalink | Reply

Jim Randell 10:51 pm on 10 July 2023 Permalink | Reply

Frits 11:21 pm on 10 July 2023 Permalink | Reply

Jim Randell 10:47 am on 5 February 2022 Permalink | Reply

Frits 11:53 am on 10 July 2023 Permalink | Reply

Jim Randell 12:12 pm on 10 July 2023 Permalink | Reply

A.T.Surherland 9:34 am on 16 February 2022 Permalink | Reply

Frits 12:45 pm on 13 July 2023 Permalink | Reply

Jim Randell 9:41 am on 14 September 2021 Permalink | Reply Tags: by: Michael Fletcher

Rate this:

Share:

Jim Randell 9:42 am on 14 September 2021 Permalink | Reply

Jim Randell 12:00 pm on 24 August 2021 Permalink | Reply Tags: by: Michael Fletcher

Rate this:

Share:

Jim Randell 6:48 am on 5 January 2025 Permalink | Reply
Tags: by: Michael Fletcher

Jim Randell 1:49 am on 27 October 2024 Permalink | Reply
Tags: by: Michael Fletcher

Jim Randell 6:12 am on 15 September 2024 Permalink | Reply
Tags: by: Michael Fletcher

Jim Randell 3:37 pm on 30 June 2023 Permalink | Reply
Tags: by: Michael Fletcher

Jim Randell 7:47 am on 14 March 2023 Permalink | Reply
Tags: by: Michael Fletcher

Jim Randell 8:48 am on 29 September 2022 Permalink | Reply
Tags: by: Michael Fletcher

Jim Randell 9:10 am on 28 July 2022 Permalink | Reply
Tags: by: Michael Fletcher

Jim Randell 9:59 am on 30 June 2022 Permalink | Reply
Tags: by: Michael Fletcher

Jim Randell 10:05 pm on 13 February 2022 Permalink | Reply
Tags: by: Michael Fletcher

Jim Randell 4:15 pm on 4 February 2022 Permalink | Reply
Tags: by: Michael Fletcher

Jim Randell 9:41 am on 14 September 2021 Permalink | Reply
Tags: by: Michael Fletcher

Jim Randell 12:00 pm on 24 August 2021 Permalink | Reply
Tags: by: Michael Fletcher

Jim Randell 6:42 am on 22 July 2021 Permalink | Reply
Tags: by: Michael Fletcher

Jim Randell 2:36 pm on 5 November 2020 Permalink | Reply
Tags: by: Michael Fletcher

Jim Randell 2:06 pm on 22 September 2020 Permalink | Reply
Tags: by: Michael Fletcher

Jim Randell 3:01 pm on 13 September 2020 Permalink | Reply
Tags: by: Michael Fletcher

Jim Randell 9:50 am on 12 December 2019 Permalink | Reply
Tags: by: Michael Fletcher

Jim Randell 2:15 pm on 12 June 2019 Permalink | Reply
Tags: by: Michael Fletcher