Recent Updates Page 43 Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 9:25 am on 11 May 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 763: Old Father Prime 

    From The Sunday Times, 29th February 1976 [link]

    Albert Prime will be joining us again today [*] for the 15th celebration of the anniversary of his birth since he was home on leave during the 1914-18 war.

    On that occasion, his son David’s age plus his brother Bert’s age was equal to his brother Charlie’s age; [and] Bert’s age plus Charlie’s age was equal to Albert’s age.

    All the ages except Albert’s were prime numbers and Albert’s was the cube of David’s. All four were born on 29th February in different years and the ages above are taken by counting how many 29th Februarys they have celebrated (for example, a man born on 29th February 1956 has an age of 5 today [*]).

    In what year was Albert born?

    Note: [*] This puzzle was originally published on 29th February 1976.

    This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980).

    The puzzle text above is taken from the book.

    [teaser763]

     
    • Jim Randell's avatar

      Jim Randell 9:26 am on 11 May 2021 Permalink | Reply

      B, C, D are prime, and A = D³ = B + C, also: B + D = C.

      So, given a value for D we can calculate the other values as follows:

      A = D³
      B = (A − D) / 2
      C = B + D

      And then determine the birth years.

      This Python program runs in 51ms.

      from datetime import date
from enigma import (primes, cb, div, printf)

# find the year of the k'th 29th February before year y
def year(k, y):
  while True:
    try:
      d = date(y, 2, 29)
      if k == 0: return y
      k -= 1
    except ValueError:
      pass
    y -= 1

# choose a value for D
for D in primes.between(2, 100):
  # calculate A
  A = cb(D)
  if A > 100: break
  # calculate B
  B = div(A - D, 2)
  if B not in primes: continue
  # calculate C
  C = B + D
  if C not in primes: continue
  printf("[A={A} B={B} C={C} D={D}]")

  # calculate birth years
  y = year(15, 1976)
  assert 1914 <= y <= 1918
  (a, b, c, d) = (year(x, y) for x in (A, B, C, D))
  printf("born: A={a} B={b} C={c} D={d} [y={y}]")

      Solution: Albert was born in 1880.

      Charlie was born in 1892. Bert was born in 1904. David was born in 1908.

      Note that 1900 was not a leap year.

      In 1916, Albert celebrated his 8th anniversary leap day (he was 36). Charlie celebrated his 5th anniversary leap day (he was 24). Bert celebrated his 3rd anniversary leap day (he was 12). David celebrated his 2nd anniversary leap day (he was 8).

      The fact: B + D = C and these values are all primes, implies that one of them must be 2. D is the obvious candidate, and the other values follow immediately. (D has to be a prime, whose cube is also relatively small, so there are very few options for D anyway).

      The only remaining wrinkle is remembering to skip the year 1900 when counting 8 leap years back from 1916.

      Like

  • Unknown's avatar

    Jim Randell 9:21 am on 9 May 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 33: Postal purchases 

    From The Sunday Times, 5th November 1961 [link]

    A rectangular sheet of postage stamps (i.e., one with each row containing the same number of stamps) was sold in such a way that each successive customer bought either a complete row or a complete column, thereby leaving the sheet rectangular after each purchase.

    The 2nd customer bought 6 stamps more than the 4th and half as many again as the 6th customer. The 5th customer bought twice as many stamps as the 12th. After the 7th customer had made his purchase exactly one-third of the original sheet had been sold.

    What was the size of the original sheet of stamps? And what was the total number of stamps bought by the first 12 customers?

    [teaser33]

     
    • Jim Randell's avatar

      Jim Randell 9:21 am on 9 May 2021 Permalink | Reply

      (See also: Enigma 460).

      This Python program runs in 51ms.

      Run: [ @replit ]

      from enigma import (irange, inf, printf)

# make k purchases from an (x, y) rectangle
def solve(k, x, y, t, ss=[]):
  # perform checks:
  n = len(ss)
  # the 2nd purchase is divisible by 3 and is greater than 6
  if n == 2 and not (ss[1] > 6 and ss[1] % 3 == 0): return
  # the 4th purchase is the 2nd less 6
  if n == 4 and not (ss[3] == ss[1] - 6): return
  # the 5th purchase is divisible by 2
  if n == 5 and not (ss[4] % 2 == 0): return
  # the 6th purchase is (2/3) the 2nd
  if n == 6 and not (ss[5] * 3 == ss[1] * 2): return
  # after the 7th purchase 1/3 of the original sheet is sold
  if n == 7 and not (sum(ss) * 3 == t): return
  # the 12th purchase is half the 5th
  if n == 12 and not (ss[11] * 2 == ss[4]): return

  # are we done?
  if k == 0:
    yield ss
  else:
    if y > 1:
      # buy a row of x stamps
      yield from solve(k - 1, x, y - 1, t, ss + [x])
    if x > 1:
      # buy a column of y stamps
      yield from solve(k - 1, x - 1, y, t, ss + [y])

# diagonal enumeration of (x, y) pairs, x > y
def pairs(a, b):
  # consider the sum of the dimensions
  for t in irange(a, b):
    # values for y
    for y in irange(1, t // 2):
      yield (t - y, y)

def run():
  # consider (x, y) rectangles
  for (x, y) in pairs(12, inf):
    # attempt 12 purchases
    for ss in solve(12, x, y, x * y):
      yield (x, y, ss)

for (x, y, ss) in run():
  printf("x={x} y={y}: {ss} -> {t}", t=sum(ss))
  break

      Solution: The original sheet consisted of 21 × 18 stamps (= 378 stamps in total). Between them, the 12 customers purchased 208 stamps.

      The individual purchases were (1st – 12th): 21, 21, 21, 15, 20, 14, 14, 18, 18, 18, 18, 10.

      The following diagram shows one way the original sheet could have been sold. Each purchase is numbered, and the number of stamps bought is given in brackets.

      Initially there are 378 stamps in the sheet.

      After the first 7 purchases (shown in red) the yellow and green squares remain. A total of 252 stamps, which is 2/3 of the original 378 stamps, so 1/3 have been sold.

      After all 12 purchases (red and yellow) only the green squares remain. A total of 170 stamps, so 208 stamps have been sold in all.

      Like

      • Frits's avatar

        Frits 10:41 am on 1 June 2021 Permalink | Reply

        You can already skip (x, y) combinations in run() if x * y is not a multiple of 3.

        Like

    • Frits's avatar

      Frits 11:20 am on 2 June 2021 Permalink | Reply

      Only one (x, y) rectangle is possible (without even considering purchases as the 6th).
      Second question is not dealt with.

      from enigma import irange
  
# the 2nd purchase is divisible by 3 and is greater than 6
# the 4th purchase is the 2nd less 6
# the 5th purchase is divisible by 2
# the 6th purchase is (2/3) the 2nd
# after the 7th purchase 1/3 of the original sheet is sold
# the 12th purchase is half the 5th
 
# diagonal enumeration of (x, y) pairs, x > y
def pairs(a, b):
  # consider the sum of the dimensions
  for t in irange(a, b):
    # values for y
    for y in irange(1, t // 2):
      yield (t - y, y)
      
for (x, y) in pairs(12, 196):              # assume x < 100
  # consider x, y with y + 3 <= x <= y + 7 (purchase 2 and 4 rules)
  # and                x % 3 != 2          (purchase 2 rule)
  # purchase 7 rule makes x * y a multiple of 3
  if (x * y) % 3 or x < y + 3 or x > y + 7 or x % 3 == 2: continue
  
  # 2nd purchase comes from initial long side
  # 4th purchase comes from initial short side 
  for a in range(1, 7): 
    b = 7 - a
    # after the 7th purchase 1/3 of the original sheet is sold
    if (x - a) * (y - b) * 3 != 2 * (x * y): continue
       
    # if only 2nd purchase made from initial long side (b = 1)
    if b == 1:
      # 1st purchase is made from the initial short side 
      if (x - 1) % 3: continue
      
      # if y is odd then the 5th purchase is odd, impossible
      if y % 2: continue
      
      # purchases 3 - 7 must be equal to 2nd purchase - 6 (and even)
      # so 2nd purchase must be even as well
      if x % 2: continue
      
    
    # if only 4th purchase made from initial short side (a = 1)
    if a == 1:
      # x must be three higher than y (the 4th purchase is the 2nd less 6)
      if x != y + 3: continue
    
    # if initial long side is a multiple of 3 
    if x % 3 == 0: 
      # the 1st purchase must be made from the long side 
      # after the first 2 purchases the short side has decremented with 2
      if x > y + 4: continue    # 4th purchase rule
      
      if x == y + 4:
        # the 3rd purchase must be made from the initial short side 
        # (difference between sides may not become higher than 6)
        # so both sides after 4 purchases have decremented with 2
        if x % 2 and y % 2: continue    # 5th purchase must be even
   
    print(f"{(x, y) = } {(a, b) = } remaining {(x - a), (y - b) = }")

# (x, y) = (21, 18) (a, b) = (3, 4) remaining (x - a), (y - b) = (18, 14)

      Like

  • Unknown's avatar

    Jim Randell 4:37 pm on 7 May 2021 Permalink | Reply
    Tags:   

    Teaser 3059: Nine blocks to the diner 

    From The Sunday Times, 9th May 2021 [link] [link]

    “Sure, I can help. From this hotel it’s nine blocks to the diner; from there it’s five blocks to the library, and then six blocks back here. I guess instead you could come back from the diner to the museum — that’s four blocks — and then seven blocks back here. Or three blocks to the gallery and then eight blocks back here.”

    “So the diner’s straight along here?”

    “No sir, it’s not straight along one road for any of these trips; I just meant so many edges of blocks. The city’s on a square grid, and all these places are on corners, but, fact is, none of them is on the same street or avenue as any other one.”

    How many blocks between the library and the museum, museum and gallery, and gallery and library?

    [teaser3059]

     
    • Jim Randell's avatar

      Jim Randell 5:28 pm on 7 May 2021 Permalink | Reply

      Here’s a quick solution using the [[ SubstitutedExpression ]] solver from the enigma.py library. It runs in 127ms.

      Run: [ @replit ]

      #! python3 -m enigma -rr

# suppose:
#   (X, Y) = hotel
#   (A, B) = diner
#   (C, D) = library
#   (E, F) = museum
#   (G, H) = gallery

SubstitutedExpression

--digits="0-7" # smallest grid with solutions

# each location has x, y co-ordinates different from all the other locations
--distinct="ACEGX,BDFHY"

# distance metric (work around PEP 3113)
--code="dist = ulambda('(a, b), (x, y): abs(a - x) + abs(b - y)')"

# 9 blocks from hotel (X, Y) to diner (A, B)
"dist((X, Y), (A, B)) = 9"

# 5 blocks from diner (A, B) to library (C, D)
"dist((A, B), (C, D)) = 5"

# 6 blocks from library (C, D) to hotel (X, Y)
"dist((C, D), (X, Y)) = 6"

# 4 blocks from diner (A, B) to museum (E, F)
"dist((A, B), (E, F)) = 4"

# 7 blocks museum (E, F) to hotel (X, Y)
"dist((E, F), (X, Y)) = 7"

# 3 blocks from diner (A, B) to gallery (G, H)
"dist((A, B), (G, H)) = 3"

# 8 blocks from gallery (G, H) to hotel (X, Y)
"dist((G, H), (X, Y)) = 8"

# eliminate some duplication
"min(A, C, E, G, X) = 0"
"min(B, D, F, H, Y) = 0"

# answer is the distances between:
#   library (C, D) and museum (E, F)
#   museum (E, F) and gallery (G, H)
#   gallery (G, H) and library (C, D)
--answer="(dist((C, D), (E, F)), dist((E, F), (G, H)), dist((G, H), (C, D)))"

# [optional] tidy up output
--template="(X, Y) (A, B) (C, D) (E, F) (G, H)"
--solution=""

      Solution: It is 7 blocks from the library to the museum. It is 7 blocks from the museum to the gallery. It is 4 blocks from the gallery to the library.

      Here is a possible layout:

      Reflections and rotations of this layout also provide viable solutions, to give the 8 different layouts found by the program.

      Like

      • Jim Randell's avatar

        Jim Randell 7:00 pm on 7 May 2021 Permalink | Reply

        And here is a standalone Python program that finds the same solution. It runs in 54ms.

        Run: [ @replit ]

        from collections import namedtuple
from enigma import (irange, multiset, printf)

# x/y coordinates
P = namedtuple('P', 'x y')

# distance metric between 2 points
def dist(p, q):
  return abs(p.x - q.x) + abs(p.y - q.y)

# generate positions at a distance d from point p
def position(d, p):
  for dx in irange(0, d):
    dy = d - dx
    yield P(p.x + dx, p.y + dy)
    yield P(p.x + dx, p.y - dy)
    yield P(p.x - dx, p.y + dy)
    yield P(p.x - dx, p.y - dy)

# check x/y co-ordinates are distinct
def check(p, *qs):
  return all(p.x != q.x and p.y != q.y for q in qs) 

# record solutions
r = multiset()

# fix the diner at (0, 0)
D = P(0, 0)

# the gallery is 3 blocks from the diner
for G in position(3, D):
  if not check(G, D): continue

  # the hotel is 8 blocks from the gallery ...
  for H in position(8, G):
    if not check(H, G, D): continue
    # ... and 9 blocks from the diner
    if not (dist(H, D) == 9): continue
    
    # the museum is 4 blocks from the diner ...
    for M in position(4, D):
      if not check(M, H, G, D): continue
      # ... and 7 blocks from the hotel
      if not (dist(M, H) == 7): continue

      # the libray is 5 blocks from the diner ...
      for L in position(5, D):
        if not check(L, M, H, G, D): continue
        # ... and 6 blocks from the hotel
        if not (dist(L, H) == 6): continue

        # calculate the required distances
        ds = (dist(L, M), dist(M, G), dist(G, L))

        printf("[ds={ds}; D={D} G={G} H={H} M={M} L={L}]")
        r.add(ds)

# output solution
for (ds, n) in r.most_common():
  printf("ds = {ds} [{n} solutions]")

        The program fixes D at (0, 0) and then looks for possible positions for G at a distance of 3. There are 8 viable positions (think knight moves), and each layout corresponds to one of these positions. So we can eliminate multiple solutions by only considering just one viable position for G.

        Like

    • Tony Brooke-Taylor's avatar

      Tony Brooke-Taylor 1:26 pm on 9 May 2021 Permalink | Reply

      I saved a bit of time by constraining the diner to be in one quadrant relative to the hotel, and the other three destinations to be in either that quadrant or the two adjacent. This still gives two solutions by reflection in y=x but of course all solutions that meet the puzzle’s conditions are identical.

      Like

  • Unknown's avatar

    Jim Randell 9:51 am on 6 May 2021 Permalink | Reply
    Tags:   

    Teaser 2791: Four-square family 

    From The Sunday Times, 20th March 2016 [link] [link]

    My four sons are all under 20 and just one of them is a teenager. Their ages (or, more precisely, the squares of their ages) have some remarkable properties. Firstly, two years ago the square of one of their ages equalled the sum of the squares of the other three ages. Secondly, this year the sum of the squares of two of their ages equals the sum of the squares of the other two ages.

    What, in increasing order, are their ages?

    [teaser2791]

     
    • Jim Randell's avatar

      Jim Randell 9:51 am on 6 May 2021 Permalink | Reply

      The following Python program runs in 48ms.

      Run: [ @replit ]

      from enigma import (irange, subsets, is_square, sq, printf)

# choose the age of the teenager
for d in irange(13, 19):
  # and the ages of the 2 youngests non-teenagers
  for (a, b) in subsets(irange(2, 12), size=2):
    # calculate c: a^2 + d^2 = b^2 + c^2
    c = is_square(sq(a) + sq(d) - sq(b))
    if c is None or c < b or c > 12: continue
    # check the ages 2 years ago: (a-2)^2 + (b-2)^2 + (c-2)^2 = (d-2)^2
    if not (sq(a - 2) + sq(b - 2) + sq(c - 2) == sq(d - 2)): continue
    # output solution
    printf("a={a} b={b} c={c} d={d}")

      Solution: Their current ages are: 4, 8, 11, 13.

      This year we have: 4² + 13² = 185 = 8² + 11².

      Two years ago the ages were: 2, 6, 9, 11, and 2² + 6² + 9² = 121 = 11².

      Like

  • Unknown's avatar

    Jim Randell 8:22 am on 4 May 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 752: Traffic cop 

    From The Sunday Times, 14th December 1975 [link]

    Some years ago I was lecturing to a group of policeman and I set them a traffic problem which they found difficult. Here it is:

    A column of vehicles 10 miles long drives 24 miles at a constant speed and then halts. A policeman on motor-cycle starts at the back of the column as it moves off, he rides to the front, turns round immediately and rides to the back of the column arriving at the moment the vehicles halt.

    Assuming that his speed has been constant throughout: how far has he ridden?

    This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980). The puzzle text above is taken from the book.

    [teaser752]

     
    • Jim Randell's avatar

      Jim Randell 8:23 am on 4 May 2021 Permalink | Reply

      The front of the convoy starts at a distance of 24 miles from the finish. And ends at distance zero.

      The back of the convoy starts at a distance of 34 miles, and ends at a distance of 10 miles.

      If we consider that the motorbike also starts at a distance of 34 miles, goes towards the finish until a distance x miles away (0 < x < 24), and then turns around and continues until it reaches the finish point of the end of the convoy. The distance travelled by the motorbike is:

      (34 − x) + (10 − x) = 44 − 2x

      And in the time taken for the motor bike to travel to the turnaround point the front of the convoy has travelled a distance: (24 − x) miles.

      And after the motorbike has turned around the convoy travels the remaining distance x miles.

      The speeds are constant, so the ratio of the convoy : motorbike distances must be the same in the two parts:

      (24 − x) : (34 − x) = x : (10 − x)
      ⇒
      (24 − x)(10 − x) = x(34 − x)
      240 − 34x + x² = 34x − x²
      x² − 34x + 120 = 0
      (x − 4)(x − 30) = 0

      So the turnaround point was 4 miles before the finish, and:

      Solution: The motorbike travelled a total distance of 36 miles.

      The two parts of the journey are:

      Before turnaround: Convoy travels from 24 miles away to 4 miles away; distance = 20 miles. Motorbike travels from 34 miles away to 4 miles away; distance = 30 miles.

      After turnaround: Convoy travels from 4 miles away to finish; distance = 4 miles. Motorbike travels from 4 miles away to 10 miles away; distance = 6 miles.

      And we see that the motorbike is travelling at 1.5× the speed of the convoy.

      Like

    • John Crabtree's avatar

      John Crabtree 10:40 pm on 4 May 2021 Permalink | Reply

      Let m be the motor-cycle speed and c be the convoy speed.
      The distance travelled by the policeman = d = 24m/c
      Considering the travel times, 10/(m – c) + 10/(m + c) = 24/c
      20mc = 24(m^2 – c^2)
      d^2 – 20d – 24^2 = 0
      d = 10 +/- 26 = 36 miles.

      Like

  • Unknown's avatar

    Jim Randell 7:34 am on 2 May 2021 Permalink | Reply
    Tags: by: C. R. J. Fleming,   

    Brain-Teaser 32: [Square farm] 

    From The Sunday Times, 29th October 1961 [link]

    A, B, & C are sitting in a railway carriage, and A, an Australian, is talking to B about his farm in Australia.

    “It is square”, he says, and tells B the length of its sides: a whole number of miles; “but I am thinking of selling a rectangular part of it whose sides are in length a whole plural number of miles”. He tells B the area of the rectangle: an odd number of square miles.

    B says: “If I knew whether its breadth was less than two-thirds of its length, I could tell you its dimensions”. A tells him that its breadth is more than two-thirds of its length.

    C, a stranger, who had been listening to this conversation, but missed the area of the rectangle, nevertheless correctly deduced its dimensions, although, he reflected, had A‘s farm had sides one mile longer he could not have done so.

    What are the lengths of the sides of  A‘s farm, and of the rectangular part to be sold?

    This puzzle was originally published with no title.

    [teaser32]

     
    • Jim Randell's avatar

      Jim Randell 7:34 am on 2 May 2021 Permalink | Reply

      I think this puzzle is flawed.

      B knows the size of A’s farm (which gives the maximum dimension of the rectangle – assuming the rectangle is aligned with the square), and also the area of the rectangle (which were are told is odd).

      And he must be able to narrow down the options (= non-trivial divisor pairs of the odd area, subject to the maximum dimension) to two possible values, which can then be distinguished by knowing if the breadth of the rectangle is less than 2/3 the length.

      So, for instance an area of 63 has two options:

      63 = 3 × 21 = 7 × 9

      So, if the size of the farm is at least 21 × 21, and B is told an area of 63, this is a candidate solution. (Or 17 × 17 if the rectangle does not have to be aligned with the square).

      If the rectangle is allowed to be a square the next candidate solution is when the size of the farm is at least 25 × 25, and B is told an area of 225:

      225 = 9 × 25 = 15 × 15.

      At 27 × 27, an area of 81 becomes viable:

      81 = 9 × 9 = 3 × 27

      When we get to 33 × 33 we get two further possible solutions:

      99 = 3 × 33 = 9 × 11
      165 = 5 × 33 = 11 × 15

      And so on.

      C knows the size of the farm, but did not hear the area of the rectangle, and so presumably also doesn’t know that the area is odd.

      But even for the minimum possible area of 21 × 21 there are 16 possible areas that have 2 decompositions into viable rectangles, and C has no way to choose between them.

      So let’s suppose that C does know that the area of the rectangle is odd. (Maybe B commented: “Ah, so the area of the rectangle is odd”, and C heard this, but not the actual value of the area).

      For a farm of size 21 × 21 to 24 × 24 there is only one possible area (= 63), and as we know the breadth of the rectangle is more than 2/3 the length, this means it must be 7 × 9. So if C had heard any of these farm areas, they could deduce the area of the rectangle.

      But when we get to 25 × 25 the possibility of a rectangle of area 225 appears (giving a rectangle of 15 × 15, where the breadth is more than 2/3 the length), so C cannot determine which rectangle it is.

      So the solution would seem to be:

      Solution: A’s farm is 24 × 24 miles. The rectangular area is 7 × 9 miles.

      However the published solution is that A’s farm is 25 × 25 miles.

      I suppose the perimeter of the square could be required to be unaffected, but that is not mentioned in the puzzle text. (And if the rectangle doesn’t have to be aligned with the sides of the square we can easily fit a 9×25 rectangle entirely within a 25×25 square, but not within a 24×24 square, which makes 24×24 a more likely answer).

      This Python program runs in 52ms.

      Run: [ @replit ]

      from enigma import (irange, inf, subsets, group, multiply, filter2, unpack, printf)

# solve for an n mile x n mile area
def solve(n):
  # group potential sub-rectangles by area
  d = group(subsets(irange(2, n), size=2, select="R"), by=multiply)

  for k in sorted(d.keys()):
    # k must be odd
    if k % 2 != 1: continue
    vs = d[k]
    # there must be 2 choices for the area
    if len(vs) != 2: continue
    # that are distinquished by known in a < (2/3) b
    (lt, ge) = filter2(unpack(lambda a, b: 3 * a < 2 * b), vs)
    if not (len(lt) == 1 and len(ge) == 1): continue
    printf("[n={n}] {k} -> {vs} -> {lt} + {ge}")
    yield (k, lt[0], ge[0])

ps = list()
for n in irange(1, inf):
  rs = list(solve(n))
  if len(rs) > 1:
    printf("farm = {n1} x {n1}", n1=n - 1)
    if len(ps) == 1:
      (k, _, (a, b)) = ps[0]
      printf("rectangle = {a} x {b} [area = {k}]")
    break
  ps = rs

      Like

  • Unknown's avatar

    Jim Randell 3:43 pm on 30 April 2021 Permalink | Reply
    Tags:   

    Teaser 3058: Total resistance 

    From The Sunday Times, 2nd May 2021 [link] [link]

    A physics teacher taught the class that resistors connected in series have a total resistance that is the sum of their resistances while resistors connected in parallel have a total resistance that is the reciprocal of the sum of their reciprocal resistances, as shown in the diagrams. Each pupil was told to take five 35-ohm resistors and combine all five into a network [using a combination of series and/or parallel connections]. Each pupil then had to calculate theoretically and check experimentally the resistance of his or her network. Every network had a different resistance and the number of different resistances was the maximum possible. The total sum of these resistances was a whole number.

    How many pupils were there in the class and what was the sum of the resistances?

    [teaser3058]

     
    • Jim Randell's avatar

      Jim Randell 4:13 pm on 30 April 2021 Permalink | Reply

      We can make a recursive function to calculate the set of resistances for a collection of k resistors, combined into a circuit using only series and parallel connections (and not “bridge”-type circuits).

      Any permissible circuit is constructed from the connection of two smaller circuits (i.e. circuits using fewer resistors) either in series or in parallel. And we don’t need to keep track of the layout of the smaller circuits, only their resistance values. (Which neatly eliminates the need to remove duplicate circuits). And we can cache these values to avoid recomputing them repeatedly.

      This Python program collects the resistance values of smaller circuits (starting with a single resistor) and combines them to calculate the resistance values of larger circuits. (A unit resistance value is used, which can be multiplied up for circuits consisting of resistors of the same value). It runs in 50ms.

      Run: [ @replit ]

      from enigma import (Rational, irange, cproduct, cached, arg, printf)

Q = Rational()  # implementation of rationals

# series and parallel combinations
S = lambda x, y: x + y
P = lambda x, y: Q(1, Q(1, x) + Q(1, y)) # = Q(x * y, x + y)

# generate arrangements of k unit resistors
@cached
def arrange(k):
  # if there is only 1 resistor
  if k == 1:
    # there is only 1 arrangement
    return {1}
  else:
    # otherwise split the resistors
    s = set()
    for i in irange(1, k // 2):
      # consider the sub-arrangements
      for (x, y) in cproduct([arrange(i), arrange(k - i)]):
        # and combine them in series and parallel
        s.update({S(x, y), P(x, y)})
    return s

# calculate the different resistances of 5 resistors
k = arg(5, 0, int)
R = arg(35, 1, int)
s = arrange(k)
printf("[k={k} R={R}] {n} different values; total = {t}", n=len(s), t=sum(s) * R)

      Solution: There were 22 pupils in the class. The total sum of the constructed resistance values was 1052 ohms.

      See also: OEIS A048211 [ @oeis ]. I have used my program to verify the sequence up to k = 21, but beyond that requires more memory than my machine has.

      The sequence OEIS A000084 [ @oeis ] gives the total number of different series/parallel circuit configurations that can be constructed, but some of them may have the same resistance value.

      For example the following combinations of 4 resistors give the same value:

      (R + R) | (R + R) = R
      (R | R) + (R | R) = R

      For k = 5 there are 24 different circuits that can be constructed, but only 22 different resistance values.

      The sequence OEIS A337516 [ @oeis ] also includes “bridge”-type circuits (the first of which appears at k = 5) and “fork”-type circuits (which appear at k = 7).

      Like

    • Tony Brooke-Taylor's avatar

      Tony Brooke-Taylor 7:27 pm on 30 April 2021 Permalink | Reply

      Jim, I tried to test my manual solution using your code and can’t reconcile your result for k=3. Have you included cases where there can be 1 resistor in parallel?

      Like

      • Tony Brooke-Taylor's avatar

        Tony Brooke-Taylor 7:43 pm on 30 April 2021 Permalink | Reply

        Sorry, I knew I should have thought a bit harder. Of course I realised my error as soon as I submitted my reply…

        Like

      • Jim Randell's avatar

        Jim Randell 7:53 pm on 30 April 2021 Permalink | Reply

        @Tony:

        With 1 resistor we have 1 way: {R}

        With 2 resistors they can be in series or parallel, 2 ways: {R+R, R|R } = { 2R, (1/2)R }

        With 3 resistors we can combine a group of 1 resistors with a group of two resistors in 4 ways: {R+(R + R), R+(R|R), R|(R + R), R|(R|R) } = { 3R, (2/3)R, (1/3)R, (3/2)R }.

        It is interesting to note that if we can make a resistance of r with a circuit of k unit resistors, then we can also make a resistance of 1/r (by interchanging series and parallel connections).

        Like

    • Alex.T.Sutherland's avatar

      Alex.T.Sutherland 4:57 pm on 2 May 2021 Permalink | Reply

      if bridging is allowed then my answer is 23 pupils and total resistance value = 1087.
      if bridging is not allowed 22 pupils = 1052.
      (the bridge network is 35 ohms)

      Like

      • Jim Randell's avatar

        Jim Randell 5:24 pm on 2 May 2021 Permalink | Reply

        Thanks for your comment.

        I think this puzzle is only concerned with networks that are composed from series and parallel connections (as that is all the children are told about, so they wouldn’t know how to calculate the theoretical resistance of other types of circuits). I have now clarified the puzzle text on this point.

        (I try not to directly reveal the solution to prize puzzles until after it is closed to entries).

        Like

    • Hugh Casement's avatar

      Hugh Casement 1:31 pm on 9 May 2021 Permalink | Reply

      >>
      For k = 5 there are 24 different circuits that can be constructed,
      but only 22 different resistance values.
      <<

      2R and ½R are each duplicated, where R = 35 ohms in this case.

      With four resistors it's just R that's duplicated, as Jim said in his original post on 30 Apr.
      Add an extra resistor to each of those circuits, once in series and once in parallel,
      and we have the duplicates for k = 5.

      Sorry if I'm stating the obvious!

      Like

  • Unknown's avatar

    Jim Randell 8:41 am on 29 April 2021 Permalink | Reply
    Tags:   

    Teaser 2788: Red-letter days 

    From The Sunday Times, 28th February 2016 [link] [link]

    The months of my 2016 calendar are headed M, T, W, Th, F, Sa, Su, with the dates 1, 2, 3… in a grid of squares underneath. I have shaded all the days on which I have meetings planned – all of them being on weekdays. For example, in February the days 1, 2, 3, 4, 8 and 9 are shaded: these shaded squares form a connected piece and the product of the numbers is a perfect cube. The same is true of the shaded squares in another month – and in fact it’s the largest possible such cube in the calendar. My last meeting in that month is on my aunt’s birthday.

    What is her birthday?

    [teaser2788]

     
    • Jim Randell's avatar

      Jim Randell 8:42 am on 29 April 2021 Permalink | Reply

      This Python program examines each month to find regions that give the maximum possible cube.

      For each month the grid is filled out, and then we calculate the total number of each possible prime factor available, and any date that contributes a prime factor that occurs fewer than 3 times is removed. We then examine subsets of the remaining numbers that have a product which is a cube, and form a connected region.

      It runs in 421ms.

      Run: [ @replit ]

      from datetime import (date, timedelta)
from enigma import (grid_adjacency, irange, factor, multiset, call, subsets, multiply, is_cube, union, Accumulator, printf)

# enable internal caching for is_cube
is_cube.cache_enabled = 1

# prime factors of numbers from 1 to 31
factors = dict((n, factor(n)) for n in irange(1, 31))

# the adjacency matrix for a 5x5 grid
adj = grid_adjacency(5, 5)

# is a region of the grid connected?
def is_connected(js):
  # start with one of the cells, and try to connect the rest in
  rs = set(js[1:])
  js = js[:1]
  while js and rs:
    js = union(adj[i] for i in js).intersection(rs)
    rs.difference_update(js)
  return not rs

# 1 day increment
day = timedelta(days=1)

# find regions with maximal product
r = Accumulator(fn=max, collect=1)

# consider possible months (although we could skip Feb)
seen = dict()
for m in irange(1, 12):

  # fill out the grid for a particular month
  grid = dict()
  (d, i) = (date(2016, m, 1), None)
  while d.month == m:
    j = d.weekday()
    if j < 5:
      i = (j if i is None else i + 1)
      grid[i] = d.day
    d += day

  # remove dates that cannot be used
  while 1:
    # accumulate all the prime factors of numbers in the grid
    fs = call(multiset.from_seq, (factors[n] for n in grid.values()))
    # remove any numbers with a factor with a count < 3
    ks = list(k for (k, n) in grid.items() if any(fs[f] < 3 for f in factors[n]))
    if not ks: break
    for k in ks: del grid[k]

  # have we already done this month
  k = tuple(sorted(grid.items()))
  if k in seen:
    printf("[month {m} duplicates month {x}]", x=seen[k])
    continue
  seen[k] = m

  printf("[month {m}: {grid}", grid=sorted(grid.values()))

  # find subsets whose product is a cube
  for ks in subsets(grid.keys(), min_size=1):
    p = multiply(grid[k] for k in ks)
    if not (is_cube(p) and is_connected(ks)): continue
    vs = sorted(grid[k] for k in ks)
    r.accumulate_data(p, (m, vs))
    printf("-> {vs} -> {p}^3", p=is_cube(p))

printf("max product = {x}^3", x=is_cube(r.value))
for (m, vs) in r.data:
  printf("month {m} -> {vs}")

      Solution: Her birthday is 27th June.

      Which is a Monday in 2016.

      The largest cube achievable is 15120³ = 3456649728000.

      It occurs in June using dates (1), 3, 6, 7, 8, 9, 10, 14, 15, 16, 20, 21, 27. (Using 1 is optional).

      The maximal cubes found for each month are:

      Jan: 2520³ = 16003008000; (1), 4, 5, 6, 7, 8, 14, 15, 20, 21, 27
      Feb: 120³ = 1728000; 1, 2, 3, 4, 5, 8, 10, 12, 15
      Mar: 168³ = 4741632; (1), 2, 7, 8, 9, 14, 16, 21
      Apr: = Jan
      May: 6³ = 216; 2, 3, 4, 9
      Jun: 15120³ = 3456649728000; (1), 3, 6, 7, 8, 9, 10, 14, 15, 16, 20, 21, 27
      Jul: = Jan
      Aug: 120³ = 1728000; 1, 2, 3, 4, 5, 8, 10, 12, 15 [= Feb]
      Sep: 7560³ = 432081216000; (1), 5, 6, 7, 8, 9, 12, 14, 15, 20, 21, 27
      Oct: 3³ = 27; 27
      Nov: = Mar
      Dec: = Sep

      The following diagram shows the regions that give the maximum cube for each month:

      (1 is optional, except where it is required to keep the region connected, i.e. Aug, Feb).

      Like

    • Frits's avatar

      Frits 6:49 pm on 30 April 2021 Permalink | Reply

      Based on Jim’s program with the idea to find the maximum product as soon as possible.

      from datetime import date, timedelta
from itertools import combinations
from enigma import multiply, is_cube

# exclude days where a prime factor can not occur 3 times per month
ex_days = [11, 13, 17, 19, 22, 23, 26, 29, 31]
# also exclude days on small islands
ex_days += [18, 24, 25, 30]

zeroes = [[0 for x in range(5)] for y in range(5)] 

# calculate minimal number of <s> entries to exceed <mprod>  
def min_entries(s, lim):
  p = 1  
  for i, v in enumerate(s):
    p *= v
    if p > lim: break
  return len(s) - i

# chain as many cells of sequence <s> as possible
def chain_cells(i, j, s, done):
  if i < 0 or i > 4 or j < 0 or j > 4: return []
 
  if done[i][j] == 1: return []
  
  ind = i * 5 + j 
 
  if ind not in s: return []
  
  chain = [ind]
  done[i][j] = 1
  
  # check adjacent cells
  chain += chain_cells(i - 1, j, s, done)
  chain += chain_cells(i + 1, j, s, done)
  chain += chain_cells(i, j - 1, s, done)
  chain += chain_cells(i, j + 1, s, done)
  
  return chain

# 1 day increment
day = timedelta(days=1)
 
(mprod, mentries, bday) = (0, 1, "")

# consider possible months (although we could skip Feb)
seen = dict()
grids = dict()

# build and store grids
for m in range(1, 13):
  # fill out the grid for a particular month
  grid = dict()
  (d, i) = (date(2016, m, 1), None)
  while d.month == m:
    j = d.weekday()
    if j < 5:
      d1 = d.day
      i = (j if i is None else i + 1)
      if d1 not in ex_days:
        grid[i] = d1
    d += day
  grids[m] = grid
  
# start with the month with the most entries  
for m in sorted(grids, key=lambda m: len(grids[m]), reverse=True): 
  grid = grids[m]
  # have we already done this month
  k = tuple(sorted(grid.items()))
  if k in seen:
    continue
  seen[k] = m
 
  allprod = multiply(grid[k] for k in grid)
  
  if mprod:
    d1 = allprod / mprod
    # not enough numbers in grid to exceed mprod
    if d1 < 1:
      continue
    # calculate minimal number of entries to exceed <mprod>  
    mentries = min_entries(grid.values(), d1)
  
  # find subsets whose product is a cube
  for k in range(len(grid), 0, -1):
    if k < mentries: break
    
    for ks in combinations(grid.keys(), k):
      p = multiply(grid[k] for k in ks)
      
      if not(p >= mprod and is_cube(p)): continue
      
      (i, j) = (ks[0] // 5, ks[0] % 5)
      # days have to be connected
      if len(ks) > len(chain_cells(i, j, ks, [x.copy() for x in zeroes])): 
        continue
        
      if p > mprod: 
        mprod = p
        # calculate minimal number of entries to exceed <mprod>  
        mentries = min_entries(grid.values(), allprod / mprod)
        vs = [grid[k] for k in ks]
        bday = str(vs[-1]) + "-" + str(m) + "-2016"
        print(f"month {m}: -> {vs} -> {is_cube(p)}^3")
 
print(f"max product = {is_cube(mprod)}^3")
print(f"birthday {bday}")

      Like

  • Unknown's avatar

    Jim Randell 9:05 am on 27 April 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 744: Job prediction 

    From The Sunday Times, 19th October 1975 [link]

    Professor Knowall has recently become very interested in dreams.

    A friend of mine has been doing some research about the extent to which dreams can be used foretell the future. He persuaded his five employees (Alf, Bert, Charlie, Duggie and Ernie) to help him in his enquiries. They liked the idea of being in the forefront of anything new and their beds seemed a nice cosy place for research.

    They met a year ago, and predicted their jobs now. Thus:

    Alf: “Ernie will not be the Door-Opener.”
    Bert: “Duggie will not be the Bottle-Washer.”
    Charlie: “Alf will not be the Welfare Officer.”
    Duggie: “Ernie will be the Bottle-Washer.”
    Ernie: “Bert’s prediction will be true.”

    Their jobs now are those of Bottle-Washer, Welfare Officer, Door-Shutter, Door-Opener and Worker.

    The Professor was most interested in this

    “But, my dear Sergeant Bungle”, he said, “how many of these predictions were correct and who made them?”

    In fact only two of the predictions were correct and they were made by the men who became the Welfare Officer and the Worker.

    What are all their jobs now?

    This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980). The puzzle text above is taken from the book.

    [teaser744]

     
    • Jim Randell's avatar

      Jim Randell 9:05 am on 27 April 2021 Permalink | Reply

      This Python program runs in 49ms.

      Run: [ @replit ]

      from enigma import subsets, printf

jobs = ("BW", "WO", "DS", "DO", "W")

# consider assignments of jobs
for (A, B, C, D, E) in subsets(jobs, size=len, select="P"):

  # evaluate the statements:
  # A: "E will not be DO"
  sA = (E != "DO")
  # B: "D will not be BW"
  sB = (D != "BW")
  # C: "A will not be WO"
  sC = (A != "WO")
  # D: "E will be BW"
  sD = (E == "BW")
  # E: "B's statement is true"
  sE = (sB == True)

  # only 2 of the statements are true, and they were made by WO and W
  ts = set(j for (s, j) in zip([sA, sB, sC, sD, sE], [A, B, C, D, E]) if s)
  if ts != {"WO", "W"}: continue

  # output solution
  printf("A={A} B={B} C={C} D={D} E={E}")

      Solution: Alf is the Worker. Bert is the Door-Opener. Charlie is the Welfare Officer. Duggie is the Bottle-Washer. Ernie is the Door-Shutter.

      Like

    • Frits's avatar

      Frits 10:18 am on 28 April 2021 Permalink | Reply 

      from enigma import SubstitutedExpression

# BW = 1, WO = 2, DS = 3, DO = 4, W = 5
jobs = ("n/a", "BW", "WO", "DS", "DO", "W")

# the alphametic puzzle
p = SubstitutedExpression( [
  # A: "E will not be DO"
  "(E != 4) = V",
  # B: "D will not be BW"
  "(D != 1) = W",
  # C: "A will not be WO"
  "(A != 2) = X",
  # D: "E will be BW"
  "(E == 1) = Y",
  # E: "B's statement is true"
  "(W == 1) = Z",
  
  # only 2 of the statements are true, and they were made by WO and W
  "sorted([V * A, W * B, X * C, Y * D, Z * E]) == [0, 0, 0, 2, 5]",
  ],
  answer="A, B, C, D, E",
  # let values range from 1-5 so the sorted formula is enough 
  # to check that only 2 of the statements are true
  digits=range(0, 6),
  d2i=dict([(0, "ABCDE")]),
  distinct="ABCDE",
  verbose=256
)

# print answers
for (_, ans) in p.solve():
  for i, a in enumerate(ans):
    print(f"{'ABCDE'[i]}={jobs[a]}", end=" ")
  print()  

# A=W B=DO C=WO D=BW E=DS

      Like

      • Frits's avatar

        Frits 10:48 am on 28 April 2021 Permalink | Reply 

         
If E is true:
  B is true
    A is false
      E = DO
      DO talks the truth -- > incorrect
Else:
  E is false 
    B is false
    D = BW
      D is false
        A is true
        C is true
          A = W
          C = WO
          E = DS
          B = DO

        Like

        • John Crabtree's avatar

          John Crabtree 4:30 pm on 29 April 2021 Permalink | Reply

          One does not need to know D’s prediction to solve the teaser. It must be false, which in fact it is.

          Like

  • Unknown's avatar

    Jim Randell 4:55 pm on 23 April 2021 Permalink | Reply
    Tags:   

    Teaser 3057: Cut for partners 

    From The Sunday Times, 25th April 2021 [link] [link]

    George and Martha are playing bridge with an invited married couple. Before play starts, the players have to cut for partners. Each player draws a card from a standard pack and those drawing the two highest-ranking cards play together against the other two. For this purpose, the rank order is ♠ A, ♥ A, ♦ A, ♣ A, ♠ K, ♥ K etc. down to ♦ 3, ♣ 3, ♠ 2, ♥ 2, ♦ 2, ♣ 2 (the lowest).

    George drew the first card, then Martha drew a lower-ranking card. “That is interesting!” commented the male visitor to his wife. “The probability that we shall play together is now P. Had Martha drawn the ♥ 7 instead of her actual card, that chance would have been reduced to P/2, and had she drawn the ♥ 6, the chance would have been reduced to P/3”.

    Which cards did George and Martha draw?

    [teaser3057]

     
    • Jim Randell's avatar

      Jim Randell 5:30 pm on 23 April 2021 Permalink | Reply

      The equations can be solved manually without too much trouble to give a direct solution, but here is a Python program that solves the puzzle. It runs in 45ms.

      Run: [ @replit ]

      from enigma import P, irange, peek, printf

# the cards in order (highest to lowest)
cards = list(v + s for v in "AKQJX98765432" for s in "SHDC")

# index of certain cards we are interested in
(i6H, i7H) = (cards.index(c) for c in ('6H', '7H'))

# count number of pairs where X+Y play together
# given G chose card index g and M chose card index m
N = lambda g, m: P(g, 2) + P(51 - m, 2)

# choose a card for G
for g in irange(0, i7H - 2):

  # count pairs if M had chosen 6H or 7H
  ns = { 3 * N(g, i6H), 2 * N(g, i7H) }
  if len(ns) > 1: continue

  # choose a card for M
  for m in irange(g + 1, i7H - 1):

    # that gives the correct probability
    if N(g, m) in ns:
      # output solution
      printf("G={G} [{g}]; n={n}; M={M} [{m}]", G=cards[g], M=cards[m], n=peek(ns))

      Solution: George’s card is A♣. Martha’s card is 9♠.

      Manually:

      There are 52 cards to start with, and after George has chosen one (at index g in the list of cards) there are 51 remaining.

      Martha chooses a lower card than George (at index m in the list of cards), and now there are 50 cards remaining.

      The other couple (X and Y) then choose cards, and if they are both lower valued than Martha’s card, or higher valued than George’s card then they will play together.

      The number of possible (unordered) pairs of cards for X+Y is: P(50, 2) = 2450, but that is the same in all scenarios, so we can just compare the number of pairs which result in X+Y playing together (n = 2450p).

      The number of pairs which are better than George’s card is: P(g, 2)

      And the number of pairs which are worse than Martha’s card is: P(51 − m, 2)

      If Martha had chosen 6♥ (the card at index 33) the probability is p/3, so:

      P(g, 2) + P(51 − 33, 2) = n / 3

      If Martha had chosen 7♥ (the card at index 29) the probability is p/2, so:

      P(g, 2) + P(51 − 29, 2) = n / 2

      Together these solve to give:

      P(22, 2) − P(18, 2) = n / 6
      ⇒ n = 936
      g² − g − 6 = 0
      (g + 2)(g − 3) = 0
      ⇒ g = 3

      So G chose the card at index 3 = A♣.

      (And the probability is p = 936/2450 ≈ 0.382).

      To find Martha’s card:

      P(g, 2) + P(51 − m, 2) = 936
      m² − 101m + 2556 = 936
      m² − 101m + 1620 = 0
      (m − 20)(m − 81) = 0
      ⇒ m = 20

      So M chose the card at index 20 = 9♠.

      Like

    • Frits's avatar

      Frits 11:45 pm on 23 April 2021 Permalink | Reply 

      from enigma import div

# chance is numerator / denominator
# P = lambda g, m: ((m - 1) * (m - 2)  + (52 - g) * (51 - g)) / (50 * 49)

# range cards: 1 - 52
# H7 is card 23, H6 = 19

suits = ["clubs", "diamonds", "hearts", "spades"]
nums = ["2", "3", "4", "5", "6", "7", "8", "9", "10", 
        "jack", "queen", "king", "ace"]
  
# check values for George
for g in range(25, 53):
  G = (52 - g) * (51 - g)
  
  h7_numerator = (23 - 1) * (23 - 2) + G
  if h7_numerator % 3: continue
  
  h6_numerator = 2 * h7_numerator // 3
  if h6_numerator != (19 - 1) * (19 - 2) + G: continue
  
  m_numerator = 2 * h7_numerator
  
  # (m - 1) * (m - 2) + G = m_numerator, m^2 -3m + (2 + G - m_numerator) = 0
  m = div(3 + (1 + 4 * (m_numerator - G)) ** 0.5, 2)
  if m is None: continue
  m = int(m)
  
  print(f"George and Martha drew {nums[(g - 1) // 4]} of {suits[(g - 1) % 4]}"
        f" and {nums[(m - 1) // 4]} of {suits[(m - 1) % 4]}")

      With more analysis: 

      from enigma import div

# range cards: 1 - 52

suits = ["clubs", "diamonds", "hearts", "spades"]
nums = ["2", "3", "4", "5", "6", "7", "8", "9", "10", 
        "jack", "queen", "king", "ace"]

# numerator of P = (m - 1) * (m - 2) + (52 - g) * (51 - g) 
# P is twice the chance for H7 (card 23)

# (m - 1) * (m - 2) + (52 - g) * (51 - g) = 
# 2 * ((23 - 1) * (23 - 2) + (52 - g) * (51 - g))

# g = 103 / 2 - ((4 * m^2 - 12*m - 3687) ^ 0.5) / 2

# P is three times the chance for H6 (card 19)

# (m - 1) * (m - 2) + (52 - g) * (51 - g) = 
# 3 * ((19 - 1) * (19 - 2) + (52 - g) * (51 - g))

# g = 103 / 2 - ((2 * m^2 - 6*m - 1831) ^ 0.5) / 2

# (4 * m^2 - 12*m - 3687) - (2 * m^2 - 6*m - 1831) = 0
# 2 * m^2 - 6 * m - 1856 = 0
m = div(6 + (36 + 4 * 2 * 1856) ** 0.5, 4)
if m is None: exit() 
m = int(m)

g = div(103 - (4 * m ** 2 - 12 * m - 3687) ** 0.5, 2)
if g is None: exit() 
g = int(g)

print(f"George and Martha drew {nums[(g - 1) // 4]} of {suits[(g - 1) % 4]}"
      f" and {nums[(m - 1) // 4]} of {suits[(m - 1) % 4]}")

      Like

  • Unknown's avatar

    Jim Randell 9:23 am on 22 April 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 737: Regular as clockwork 

    From The Sunday Times, 31st August 1975 [link]

    Our old watchmaker works weekdays 9:30am to 5pm as regular as, well, clockwork. I recently took there to be regulated two “8-day” striking clocks – the sort which fully wound will go nearly 8 days before stopping; they were keeping different times and each was wrong by an exact number of minutes per day, i.e. less than an hour in either case.

    He immediately wound the clocks fully, set them to the right time (which was an exact number of minutes after the hour) and put them up on a shelf for observation.

    The next Monday, when he went to take down the clocks to start regulating them, he found both of them just starting to strike 8 o’clock simultaneously, which was some hours plus an exact number of minutes past the correct time.

    What day and exact time was it when he originally set them?

    This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980). The puzzle text above is taken from the book.

    [teaser737]

     
    • Jim Randell's avatar

      Jim Randell 9:24 am on 22 April 2021 Permalink | Reply

      A clock that gained 1 hour a day would take 12 days (or 12.5 days clock time) to show the right time (but actually be 12 hours fast). Similarly a clock that lost 1 hour a day would take 12 days (or 11.5 day clock time) to show the right time (but actually be 12 hours slow).

      And the clocks we are interested would run out long before they achieved this.

      But if we look at both the clocks it would only take 6 days for them to both show the same time (i.e. have a difference of 12 hours between them).

      This would be achievable with the clocks in the puzzle.

      If the clocks were set at 2 o’clock on Tuesday afternoon, then at 2pm on the following Monday they would both read 8 o’clock (one of them having gained 6 hours, and the other having lost 6 hours). So the puzzle seems reasonable, and the solution is probably close to this, although the clocks we have to consider must only gain or lost at most 59 minutes a day.

      We are interested in when the difference between the clocks is a multiple of 12 hours. For clocks that show a difference of d minutes per day, the time t at which they show a difference that is a multiple k of 12 hours is:

      t = k × 720 × 1440 / d

      We know d is in the range [1, 118], t is less than 8 days. So:

      t < 8 × 1440
      ⇒ 720k < 8d
      ⇒ 90k < d

      Hence k = 1 and d is in the range [91, 118], and t is an exact number of minutes.

      This Python program examines possible (t, d) values, and eliminates t values that make impossible to finish on a Monday. It then looks for gain/loss values for the clocks that give an exact number of minutes when they are both showing the same time, give a start time that is during working hours. It runs in 47ms.

      Run: [ @replit ]

      from enigma import (irange, divisors_pairs, div, sprintf, fdiv, printf)

# working in minutes
R = 12 * 60  # repeat period of clocks
D = 24 * 60  # minutes in a day
W = 7 * D  # minutes in a week

# work hours (9:30am - 5:00pm, Mon(= 0) to Fri(= 4)
work = list([570 + x, 1020 + x] for x in irange(0, 4 * D, step=D))

# check if time is during work hours
def check(t):
  t %= W
  return any(x <= t <= y for (x, y) in work)

def fmt(m):
  (d, m) = divmod(m % W, D)
  day = ("Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun")[d]
  (h, m) = divmod(m, 60)
  return sprintf("{day} {h:02d}:{m:02d}")

# find valid (d, t) pairs
for (d, t) in divisors_pairs(R * D, every=1):
  if d < 91: continue
  if d > 118: break

  # calculate start window, for a finish during Monday's work hours
  a = (work[0][0] - t) % W
  b = (work[0][1] - t) % W
  if not (check(a) or check(b)): continue

  # look for times separated by d that give integer start times
  for x in irange(59, -59, step=-1):
    y = x - d
    if y < -59: break

    # calculate the time differences
    dy = div(t * (D + y), D)
    if dy is None: continue

    # clock Y is slow and showing 8am on Monday (= 480)
    # find out when it was set
    t0 = (480 - dy) % W
    if not check(t0): continue

    # output solution
    printf("start = {t0} [end = {end}; d={d}m t={t:g}d; x={x}m y={y}m]", t0=fmt(t0), end=fmt(t0 + t), t=fdiv(t, D))

      Solution: The clocks were originally set on Monday at 9:48am.

      The difference in the time the clocks show is 100 minutes per day, so after 7.2 days they are different by 720 minutes = 12 hours.

      One clock gains 45 minutes per day, and the other loses 55 minutes per day.

      So after 7.2 days the fast clock has gained 324 minutes (so it thinks it has been running for 7.425 days), and the slow clock has lost 396 minutes (so it thinks it has been running for 6.925 days).

      The slow clock is showing 8am, but it is actually 6h36m later than that, i.e. 2:36pm.

      And the fast clock is showing 8pm, but it is actually 5h24m earlier than that, i.e. 2:36pm.

      So the clocks are showing the same time at 2:36pm on Monday (which is during working hours), so they must have been set 7.2 days before this, i.e. one week and 4h48m earlier = 9:48am the previous Monday (also during working hours).

      Like

    • Frits's avatar

      Frits 10:26 pm on 22 April 2021 Permalink | Reply 

      from enigma import div

# between Friday 17:00 - Monday 09:30 there are 3870 minutes
# between Monday 09:30 - Monday 17:00 there are 3870 + 6660 minutes

# assume 3870 + M minutes have gone by 
# number of days passed = (3870 + M) / 1440

# loop over clock minutes running too slow or too fast
for X in range(1, 60):
  for W in range(1, 60):
    # for variables x, w use values -1, 1 for sign of resp. numbers X and W 
    for x in [-1, 1]:
      for w in [-1, 1]:
        # avoid duplicate solutions
        if x * X >= w * W: continue
       
        # clocks strike at the same time 
        # 480 + X * no_days   (08:00)   or    1200 - X * no_days   (20:00)
        
        # (3 * x + 7) * 120  - x * X * (3870 + M) / 1440 == \
        # (3 * w + 7) * 120  - w * W * (3870 + M) / 1440",
        
        # calculate minutes
        M = div(518400 * (w - x) - (w * W - x * X) * 3870, w * W - x * X)
        if M is None: continue
        
        # maximum range Monday 09:30 - Monday 17:00
        if M > 6660: continue
        
        # gain has to be a whole number
        gain = div(X * (3870 + M),  1440)
        if gain is None: continue
        
        # time = real time (in minutes) the clocks strikes at the same time
        # "480 + gain" or "1200 - gain"
        time = (3 * x + 7) * 120  - x * gain
        
        # clocks were set (3870 + M) / 1440 days before
        # 9:30 = 570 minutes,  17:00 = 1020 minutes
        if not(570 <= (1440 + time - (3870 + M)) % 1440 <= 1020): continue
        
        days = ["Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"]
        
        h = (time - (3870 + M) % 1440) // 60
        m = (time - (3870 + M) % 1440) % 60
        
        d = (3870 + M) // 1440
        day = days[7 - d] 
       
        print(f"day = {day}, exact time {h}:{m}")

      Like

  • Unknown's avatar

    Jim Randell 9:13 am on 20 April 2021 Permalink | Reply
    Tags:   

    Teaser 2787: Crime-writers convention 

    From The Sunday Times, 21st February 2016 [link] [link]

    A group of twelve crime writers attended a convention. They were Bonfiglioli, Durrenmatt, Fyfield, Hiaasen, Highsmith, Hill, Innes, James, Knox, Le Carre, Rendell and Sayers, They sat in one long row on the stage, with Hiaasen further to the left than Hill. It turned out that, for any two sitting next to each other, there was just one letter of the alphabet that occurred (perhaps more than once) in both their surnames.

    List the initial of each author from left to right along the row.

    [teaser2787]

     
    • Jim Randell's avatar

      Jim Randell 9:16 am on 20 April 2021 Permalink | Reply

      This Python program runs in 51ms.

      Run: [ @replit ]

      from enigma import join, printf

names = [
  'bonfiglioli', 'durrenmatt', 'fyfield', 'hiaasen', 'highsmith',
  'hill', 'innes', 'james', 'knox', 'le carre', 'rendell', 'sayers',
]

# add names in rs to ns, so that adjacent names share exactly 1 letter
# ns - names assigned so far
# rs - remaining names
def solve(ns, rs):
  # are we done?
  if not rs:
    yield ns
  else:
    # consider one of the remaining names
    for (i, n) in enumerate(rs):
      # check adjacent names share exactly 1 letter
      if not(ns) or len(set(n).intersection(ns[-1])) == 1:
        # solve for the remaining names
        yield from solve(ns + [n], rs[:i] + rs[i + 1:])

# find lists of names
for ns in solve([], names):
  # check 'hiaasen' is further left than 'hill'
  if not(ns.index('hiaasen') < ns.index('hill')): continue
  # output the names and the initals
  s = list(n[0].upper() for n in ns)
  printf("{s}\n  -> {ns}", s=join(s, sep=' '), ns=join(ns, sep=', '))

      Solution: The initial letters of the surnames are: H K D B L I H R J F H S.

      The order is (left to right):

      Hiaasen
      Knox
      Durrenmatt
      Bonfiglioli
      Le Carre
      Innes
      Hill
      Rendell
      James
      Fyfield
      Highsmith
      Sayers

      Like

  • Unknown's avatar

    Jim Randell 8:17 am on 18 April 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 31: [Birthday weddings] 

    From The Sunday Times, 22nd October 1961 [link]

    Jane said:

    My mother and I were each married on our birthday and each at the same age. I was born four years and a day after my mother’s marriage, and my twins were born four years and a day after my marriage to John, who is three years older than I am, and who shares a birthday with my mother.

    If you write a date, say Christmas Day this year, in a continuous line of figures it looks like this – 25121961. Very well, if you write down our five dates of birth in that way and add the resultant numbers, the total is 8829685.

    When was her wedding day?

    This puzzle was originally published with no title.

    [teaser31]

     
    • Jim Randell's avatar

      Jim Randell 8:18 am on 18 April 2021 Permalink | Reply

      I was wondering when exactly “a year and a day” after 29th February was. It’s probably easiest to imagine there is a zero length 29th February in non-leap years, and then it is easier to calculate these “year and a day” offsets. In the analysis it turns out there is only one possible set of dates anyway.

      Assuming the 5 years of birth are all before 2000, we see that their sum must be a 4-digit number, i.e. 9685. And there is no carry into the sum of the day and month digits, which are 882. So we can deal this these three columns separately.

      As there are 5 birthdays they cannot all be in the same month (as the final digit of the day/month sum would end in 5 or 0). In order for the final digit to be 2, twins birthday must at the beginning of a month, Jane at the end of the previous month, and John and Mum the day before that.

      So the twins could be born on:

      1st Mar: sum = 13 + 13 + 282 + 272 + 272 = 852 (non leap-year)
      1st Mar: sum = 13 + 13 + 292 + 282 + 282 = 882 (leap year)
      1st May: sum = 15 + 15 + 304 + 294 + 294 = 922
      1st Jul: sum = 17 + 17 + 306 + 296 + 296 = 932
      1st Sep: sum = 19 + 19 + 318 + 308 + 308 = 972
      1st Oct: sum = 111 + 111 + 3110 + 3010 + 3010 = 9352

      And only 1st Mar (twins), preceded by 29th Feb (Jane), and 28th Feb (John, Mum), gives the sum 882.

      If the twins were born (on 1st Mar) in year y, then the year of Jane’s marriage is 4 years and 1 day earlier. And Jane is married on her birthday, which is 29th Feb, so (y − 4) (and hence y) must be a leap year.

      If Jane is married at age x years, then her birth date must be (y − x − 4) (also a leap year, so x must be a multiple of 4).

      And John is born on 28th Feb, 3 years earlier, i.e. in year (y − x − 7).

      Jane’s Mum was married exactly 1 year before that, i.e. in year (y − x − 8).

      So she was born in year: (y − 2x − 8).

      And the sum of the 5 birth years is 9685:

      2y + (y − x − 4) + (y − x − 7) + (y − 2x − 8) = 9685
      5y − 4x − 19 = 9685
      x = (5y − 9704) / 4

      Looking at leap years, going backwards from 1960:

      y = 1960: x = 24
      y = 1956: x = 19
      y = 1952: x = 14

      So the only viable candidate for (y, x) is (1960, 24) (as x must be a multiple of 4).

      So the dates we are interested in are:

      1960-03-01 = twins born
      1956-02-29 = Jane and John’s wedding; Jane’s 24th birthday
      1932-02-29 = Jane born
      1929-02-28 = John born
      1928-02-28 = Jane’s Mum’s wedding; Mum’s 24th birthday
      1904-02-28 = Jane’s Mum born

      Adding the 5 birth dates converted to integers we get:

      131960 + 131960 + 2921932 + 2821929 + 2821904 = 8829685

      Solution: Jane’s wedding day was: 29th February 1956.

      Like

  • Unknown's avatar

    Jim Randell 5:04 pm on 16 April 2021 Permalink | Reply
    Tags:   

    Teaser 3056: Rose garden 

    From The Sunday Times, 18th April 2021 [link] [link]

    The six rose bushes in my garden lie on a circle. When they were very small, I measured the six internal angles of the hexagon that the bushes form. These were three-digit whole numbers of degrees. In a list of them, of the ten digits from 0 to 9, only one digit is used more than once and only one digit is not used at all. Further examination of the list reveals that it contains a perfect power and two prime numbers.

    In degrees, what were the smallest and largest angles?

    [teaser3056]

     
    • Jim Randell's avatar

      Jim Randell 5:51 pm on 16 April 2021 Permalink | Reply

      (See also: Teaser 1885).

      The internal angles of a hexagon must sum to 720°, and as they are all 3-digit whole numbers of degrees we see that they are all in the range 100° to 179°. So the repeated digit must be 1. (And with a little bit of analysis we can reduce the range of the angles further).

      Additionally the alternating angles of a cyclic hexagon, must sum to 360°, so the angles must be able to be formed into 2 groups of 3, each group summing to 360°. (In general for cyclic 2n-gon the alternating angles must have the same sum).

      These constraints, along with the other conditions give two possible sets of angles, but they have the same largest and smallest values.

      I assumed the angles were all different (although 111° could potentially be repeated, but there are no solutions where it is).

      This Python 3 program runs in 122ms.

      Run: [ @replit ]

      from enigma import (irange, mgcd, unpack, prime_factor, subsets, multiset, nsplit, printf)

# check digits have no repeats (other than 1)
def digits(ns, ds=None):
  ds = (multiset() if ds is None else ds.copy())
  for n in ns:
    ds.update_from_seq(nsplit(n))
  # check the digits
  if all(v == 1 or k == 1 for (k, v) in ds.items()): return ds

# determine if a number is a prime or an exact power from its prime factorisation
is_prime = lambda fs: len(fs) == 1 and fs[0][1] == 1
is_power = lambda fs, gcd=unpack(mgcd): gcd(e for (p, e) in fs) > 1

# collect candidate primes, powers and others
(primes, powers, others) = (list(), list(), set())
for n in irange(100, 179):
  if not digits([n]): continue
  fs = list(prime_factor(n))
  if is_prime(fs):
    primes.append(n)
  elif is_power(fs):
    powers.append(n)
  else:
    others.add(n)

# decompose <t> into <k> numbers in range [m, M]
# that are not in primes or powers
def decompose(t, k, m=100, M=179, ns=[]):
  # are we done?
  if k == 1:
    if not (t < m or t > M) and t in others:
      yield ns + [t]
  else:
    # choose the next number
    k_ = k - 1
    for n in irange(m, min(M, t - k_ * m)):
      if n in others:
        yield from decompose(t - n, k_, n + 1, M, ns + [n])

# choose the two primes
for (b, c) in subsets(primes, size=2):
  ds1 = digits([b, c])
  if ds1 is None: continue

  # choose the power
  for a in powers:
    ds2 = digits([a], ds1)
    if ds2 is None: continue

    # find the remaining angles
    for xs in decompose(720 - (a + b + c), 3):
      ds3 = digits(xs, ds2)
      if ds3 is None: continue
      # only one of the 10 digits is missing
      if len(ds3.keys()) != 9: continue

      # and the sum of alternate angles must be 360 degrees
      ns = sorted([a, b, c] + xs)
      if any(sum(ss) == 360 for ss in subsets(ns, size=3)):
        printf("min={ns[0]} max={ns[-1]} {ns}")

      Solution: The smallest angle is 101°. The largest angle is 146°.

      Measuring angles in degrees. The 6 angles are all integers between 101 and 179 (100 is ruled out because of the repeated 0 digit).

      And they must form two groups of 3 that add up to 360, so the largest possible angle is 360 − 101 − 111 = 148.

      This limits the possible powers to: 121, 125, 128.

      So, whichever power is chosen the digit 2 will be used.

      The primes are therefore limited to: 101, 103, 107, 109, 113, 131, 137, 139.

      So, whichever primes are chosen one will contain the digit 0 and one will contain the digit 3 (so 103 cannot be chosen).

      Which means the remaining three angles cannot contain the digits 0, 2, or 3.

      The remaining angles are therefore limited to: 111, 114, 115, 116, 117, 118, 119, 141, 145, 146, 147, 148.

      There are no pairs from the permissible remaining angles that pair with 121 to give 360, so the power is either 125 or 128.

      For a power of 125, there are two sets of angles that can make 360, but only one of them leaves another set of angles that can make 360 according to the constraints:

      (125, 117, 118) + (101, 113, 146)

      For a power of 128, there are four sets of angles that can make 360, but only one of them leaves another set of angles that can make 360 according to the constraints (and it is the same set of additional angles as the previous solution):

      (128, 115, 117) + (101, 113, 146)

      And in both cases the unused digit is 9 and the minimum and maximum values both lie in the set without the power.

      There are many ways to produce a cyclic hexagon from a set of angles, but here are two diagrams corresponding to the two solutions. For each diagram I have maximised the smallest distance between vertices:

      Like

      • Jim Randell's avatar

        Jim Randell 12:30 pm on 19 April 2021 Permalink | Reply

        Here is a faster version. It builds up sets of 3 angles that sum to 360° and don’t share non-1 digits, and then looks for two of these sets that don’t share non-1 digits, and checks that together they have exactly 1 power and 2 primes.

        It also allows for a 111° angle to appear multiple times (although this doesn’t give any further solutions).

        It runs in 51ms.

        Run: [ @replit ]

        from enigma import (irange, mgcd, unpack, prime_factor, subsets, nsplit, union, printf)

# check digits have no repeats (other than 1), return set of digits used
def digits(ns):
  ds = set()
  for n in ns:
    for d in nsplit(n):
      if d == 1: continue
      if d in ds: return
      ds.add(d)
  return ds

# determine if a number is a prime or an exact power from its prime factorisation
is_prime = lambda fs: len(fs) == 1 and fs[0][1] == 1
is_power = lambda fs, gcd=unpack(mgcd): gcd(e for (p, e) in fs) > 1

# max and min possible angles
(m, M) = (101, 148)

# collect candidate primes, powers and others
(primes, powers, others) = (set(), set(), set())
for n in irange(m, M):
  if not digits([n]): continue
  fs = list(prime_factor(n))
  if is_prime(fs):
    primes.add(n)
  elif is_power(fs):
    powers.add(n)
  else:
    others.add(n)

# decompose <t> into <k> numbers in range [m, M] chosen from <ns>
def decompose(t, k, ns, m=m, M=M, xs=[]):
  # are we done?
  if k == 1:
    if not (t < m or t > M) and t in ns:
      yield xs + [t]
  else:
    # choose the next number
    k_ = k - 1
    for n in irange(m, min(M, t - k_ * m)):
      if n in ns:
        yield from decompose(t - n, k_, ns, n + 1, M, xs + [n])

# find sets of numbers that give 360
ss = list()
for ns in decompose(360, 3, union([primes, powers, others])):
  # find digits used
  ds = digits(ns)
  if ds:
    ss.append((ns, ds))

# also allow a repeat of 111
ns = [111, 111, 138]
ds = digits(ns)
if ds:
  ss.append((ns, ds))

# choose two sets with no shared digits (other than 1)
for ((ns1, ds1), (ns2, ds2)) in subsets(ss, size=2):
  if ds1.intersection(ds2): continue
  ns = sorted(ns1 + ns2)
  # check there is 1 power and 2 primes
  if not (len(powers.intersection(ns)) == 1 and len(primes.intersection(ns)) == 2): continue
  # output solution
  printf("min={ns[0]} max={ns[-1]} {ns1} + {ns2}")

        Like

    • Frits's avatar

      Frits 10:10 pm on 16 April 2021 Permalink | Reply

      Checks for prime numbers and powers are done a limited number of times so it was not worth to calculate prime numbers and powers (for 101-159) in advance.

      from enigma import SubstitutedExpression, is_prime, unpack, mgcd, prime_factor

# check a number is _not_ an exact power  (see Brain-Teaser 683)
is_no_power = lambda n, gcd=unpack(mgcd): gcd(e for (p, e) in prime_factor(n)) == 1

# main checks for sequence <s>
def check(s):
  # only one digit is missing so we have four 1's and eight others
  s1 = "".join(str(x).zfill(2) for x in s)
  if len(set(s1)) != 9 or s1.count("1") != 4 :
    return False 
 
  # list contains two prime numbers 
  if len([x for x in s if is_prime(100 + x)] ) != 2:
    return False
 
  # list contains one power
  if len([x for x in s if is_no_power(100 + x)]) != 5:
    return False
 
  return True

p = SubstitutedExpression(
  [
   # 1AB + 1CD + 1?? = 360   ?? = 60 - AB - CD
   "AB < CD",
   "CD < 60 - AB - CD",
  
   # 1GH + 1IJ + 1?? = 360   ?? = 60 - GH - IJ
   "GH < IJ",
   "IJ < 60 - GH - IJ",
  
   # limit duplicate solutions
   "AB <= GH",
  
   # main check
   "check([AB, CD, 60 - AB - CD, GH, IJ, 60 - GH - IJ])",
  ],
  answer="(100 + AB, 100 + CD, 160 - AB - CD, \
           100 + GH, 100 + IJ, 160 - GH - IJ)",
  d2i=dict([(0, "CG")] +
           [(2, "AG")] +
           [(k, "ACGI") for k in range(3, 10)]),
  env=dict(check=check),
  distinct="",
verbose=0,
)

# print answer
for (_, ans) in p.solve():
  print(f"min={min(ans)} max={max(ans)} {ans}")

      Like

    • Frits's avatar

      Frits 12:30 pm on 17 April 2021 Permalink | Reply

      Built for speed (hardcoded values).

      # check if sequence <s> contains different digits (except 1)
def diffdgts(s, no1s=0):
  s1 = "".join(str(x).zfill(2) for x in s)
  s2 = s1.replace("1", "")
  if len(set(s2)) != len(s2):
    return False  
  else:
    if no1s and s1.count("1") != no1s:
        return False
    
    # F needs to contain 2 or 3 so don't allow both in A, B, C    
    if len(s) == 3 and "2" in s2 and "3" in s2: 
      return False
      
    return True

# form angles into 2 groups of 3, each group summing to 360  
for A in range(1, 18):
  # F needs to contain 2 or 3 so limit B to 19
  for B in range(max(11, A + 1), 20):
    C = 60 - A - B
    if not diffdgts([A, B, C]): continue
    
    # second group 
    for D in range(max(11, A + 1), 19): 
      for E in range(D + 1, 20):
        F = 60 - D - E
        
        s = [A, B, C, D, E, F]
        if not diffdgts(s, 4): continue
        
        # either 100 + C or 100 + F has to be a power as A, B, C and D < 20
        if len([x for x in [C, F] if x in {21, 25, 28}]) != 1: continue
        
        # list contains two prime numbers (prime numbers < 149)  
        if len([x for x in s if x in {1, 3, 7, 9, 13, 27, 31, 37, 39}] ) != 2:
          continue
     
        ans = [100 + x for x in s]
        print(f"min={min(ans)} max={max(ans)} {ans}")

      Like

    • Frits's avatar

      Frits 1:10 am on 20 April 2021 Permalink | Reply

      Starting with 3 angles which sum to 360 and include a power.
      This list is limited and allows us to derive digits which may not be used in the other list of 3 angles.

      # (prime numbers < 149 and excluding numbers with digit 2)  
primes = {101, 103, 107, 109, 113, 131, 137, 139}

# create a list of 3 angles which sum to 360 and includes a power
pwrs = []
# power 121 is not allowed as it forces 119, 120, 121
for A in [125, 128]:
  # set ranges so that C > B
  for B in range((241 - A), 100 + (161 - A) // 2):
    C = 360 - A - B

    # check for different digits (except 1)
    dABC = [x for n in [A, B, C] for x in [n // 10 - 10, n % 10] if x != 1]
    # the 9 digits must have exact 5 ones as B = 111 is not allowed
    if len(dABC) != 4 or len(set(dABC)) != 4: continue

    pwrs.append([[A, B, C], dABC])


# if digits 3/4, 8 and 9 are used in ABC we can't make 360 with remaining
# digits as you will have to make 10 with 0, 1, 5, 6, 7 (3/4 is for tens)
pwrs = [[p, d] for p, d in pwrs if not ((3 in d or 4 in d) 
                                   and 8 in d and 9 in d)]

# check which digits occur in all power entries
common_dgts = [i for i in range(2, 10) if all(i in d for p, d in pwrs)]

# second group without power
for D in range(101, 115): 
  if (D % 10) in common_dgts: continue
  for E in range(max(111, D + 1), min(231 - D, 120)):
    if (E % 10) in common_dgts: continue
    F = 360 - D - E
    if (F % 10) in common_dgts: continue

    # check for different digits (except 1)
    dDEF = [x for n in [D, E, F] for x in [n // 10 - 10, n % 10] if x != 1]
    if len(dDEF) != 4 or len(set(dDEF)) != 4: continue

    # check if D, E, F complements pwrs (A, B, C)
    for p, d in pwrs:
      # skip if they have digits in common
      if any(x in d for x in dDEF): continue

      s = [D, E, F] + p

      # list contains two prime numbers 
      if len([x for x in s if x in primes]) == 2:
         print(f"{min(s)}, {max(s)} [{s}]")

      Like

  • Unknown's avatar

    Jim Randell 8:22 am on 15 April 2021 Permalink | Reply
    Tags:   

    Teaser 2786: Out of order 

    From The Sunday Times, 14th February 2016 [link] [link]

    I have written down five positive whole numbers whose sum is less than 100. If you wrote the numbers in words, then you would find that each of them begins with a different letter of the alphabet. (Surprisingly, the same is true of the five numbers obtained by increasing each of my five numbers by one). If you write my five numbers in words and put them in alphabetical order, then they will be in decreasing order.

    What (in decreasing order) are my five numbers?

    [teaser2786]

     
    • Jim Randell's avatar

      Jim Randell 8:23 am on 15 April 2021 Permalink | Reply

      The following Python program runs in 50ms.

      Run: [ @replit ]

      from enigma import int2words, irange, seq_all_different, printf

N = 5  # how many numbers in the sequence
T = 100  # sum must be less than this

# map numbers to their initial letter
m = dict((i, int2words(i)[0]) for i in irange(1, T - 1))

# add <k> numbers to <ns> in decreasing numerical order,
# but increasing alphabetical order, that sum less than <t>
def solve(ns, k, t):
  # are we done?
  if k == 0:
    yield ns
  else:
    # add in a lower number
    n0 = ns[-1]
    for n in irange(min(n0 - 1, t - k + 1), k, step=-1):
      # that is later alphabetically
      if m[n] > m[n0]:
        yield from solve(ns + [n], k - 1, t - n)

# check the numbers in ns all start with different letters when offset by i
check = lambda ns, i=0: seq_all_different(m[n + i] for n in ns)

# start with the largest number
for n in irange(5, 89):
  for ns in solve([n], N - 1, T - n):
    # check the starting letters are all different when offset by 1
    if check(ns, 1):
      # output a solution
      printf("{ns} sum={t}", t=sum(ns))

      Solution: The five numbers are: 18, 15, 9, 7, 3.

      So the initial letters are: E, F, N, S, T (which are in alphabetical order).

      Adding one to each term we get: 19, 16, 10, 8, 4; with initial letters: N, S, T, E, F.

      And we can also increment each term again to get: 20, 17, 11, 9, 5; initial letters: T, S, E, N, F.

      Like

    • Frits's avatar

      Frits 2:52 pm on 15 April 2021 Permalink | Reply 

      from collections import defaultdict

upto19 = ['', 'one', 'two', 'three', 'four', 'five', 'six', 'seven',
          'eight', 'nine', 'ten', 'eleven', 'twelve', 'thirteen', 'fourteen',
          'fifteen', 'sixteen', 'seventeen', 'eighteen', 'nineteen']
tens = ['twenty', 'thirty', 'forty', 'fifty', 'sixty', 'seventy', 'eighty',
        'ninety']

# map numbers to their initial letter
m = dict((i, tens[(i - 20) // 10][0] if i > 19 else upto19[i][0])
             for i in range(1, 100))

# letters = sorted(set(m[i] for i in range(1, 90)))

# we have 6 letters of which 'o' only occurs once for number 1
# as 'o' in alphabetical order precedes 's' and 't' we can't use letter 'o'
# thus numbers [E, D, C, B, A] must have letters ['e', 'f', 'n', 's', 't']

d = defaultdict(list)
for i in range(1, 90):
  d[m[i]].append(i)

# list with minimal values (from A to D)
mv = [d['t'][0]]
for i in "snf":
  mv.append([x for x in d[i] if x > max(mv)][0])

# loop from highest number
for E in [x for x in d['e'] if x > mv[3] and x < 100 - sum(mv)]:
  for D in [x for x in d['f'] if x > mv[2] and
            x < min(E, 100 - E - sum(mv[:3]))]:
    for C in [x for x in d['n'] if x > mv[1] and
              x < min(D, 100 - D - E - sum(mv[:2]))]: 
      for B in [x for x in d['s'] if x > mv[0] and
                x < min(C, 100 -  C - D - E - sum(mv[:1]))]:
        for A in [x for x in d['t'] if x < min(B, 100 - B - C - D - E)]:
 
          # check if the numbers start with different letters when offset by 1       
          if len(set(m[E+1] + m[D+1] + m[C+1] + m[B+1] + m[A+1])) == 5:
            print("answer:", (E, D, C, B, A))

      Like

  • Unknown's avatar

    Jim Randell 9:40 am on 13 April 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 30: [Football table] 

    From The Sunday Times, 15th October 1961 [link]

    In a football tournament each country played each other country twice, the scores in all twelve matches being different.

    The records for the top and bottom teams were:

    England beat Wales twice by the same margin as she beat Ireland once.

    The sum of the aggregate number of goals scored against Scotland, who finished second, and Ireland was 20.

    What were the respective scores in the Ireland vs. Scotland matches?

    This puzzle was originally published with no title.

    [teaser30]

     
    • Jim Randell's avatar

      Jim Randell 9:41 am on 13 April 2021 Permalink | Reply

      This seems to be the earliest “football table” Teaser.

      We are told that the sum of Scotland and Ireland’s “goals against” values is 20, which means the total of the “goals against” column must be 38. And so the sum of Scotland and Ireland’s “goals for” values must be 38 − (16 + 8) = 14.

      The following Python program uses the [[ Football() ]] helper class from the enigma.py library. It runs in 1.22s.

      from itertools import product
from enigma import (Football, ordered, chunk, subsets, irange, multiset, join, printf)

# scoring system
football = Football(games="wdl", points=dict(w=2, d=1))

# identify matches with the same scoreline
keys = lambda ss: list(ordered(*s) for s in ss)

# check a sequence of scores, all different and in ordered pairs
check = lambda ss, ps: len(set(ss)) == len(ss) and all(x > y for (x, y) in chunk(ps, 2))

# margin
margin = lambda ss: ss[0] - ss[1]

# record scores in the S vs I matches
rs = multiset()

# scorelines for E (who have won all their matches)
(ew1, ew2, es1, es2, ei1, ei2) = mes = 'w' * 6
for ssE in football.scores(mes, [0] * 6, 16, 3):
  # check scorelines
  ss0 = keys(ssE)
  if not check(ss0, ss0): continue

  # E wins E vs W by same margin, same as exactly one of the E vs I
  (EW1, EW2, ES1, ES2, EI1, EI2) = ssE
  d = margin(EW1)
  if not (d == margin(EW2) and (margin(EI1), margin(EI2)).count(d) == 1): continue

  # W have 2 draws and 2 losses remaining
  for mws in subsets("ddll", size=len, select="mP"):
    for ssW in football.scores(mws, [0] * 4, 8, 15, [EW1, EW2], [1, 1]):
      ss1 = keys(ssW)
      if not check(ss0 + ss1, ss1): continue

      # calculate current goals for/against S and I (so far)
      (WS1, WS2, WI1, WI2) = ssW
      (fS, aS) = football.goals([ES1, ES2, WS1, WS2], [1, 1, 1, 1])
      (fI, aI) = football.goals([EI1, EI2, WI1, WI2], [1, 1, 1, 1])
      # goals against S and I sum to 20 (and goals for S and I sum to 14)
      (ga, gf) = (20 - aS - aI, 14 - fS - fI)
      if ga < 0 or gf < 0: continue

      # choose outcomes for S vs I matches
      (ws1, ws2, wi1, wi2) = mws
      for (si1, si2) in football.games(repeat=2):
        S = football.table([es1, es2, ws1, ws2, si1, si2], [1, 1, 1, 1, 0, 0])
        I = football.table([ei1, ei2, wi1, wi2, si1, si2], [1, 1, 1, 1, 1, 1])
        if not (12 >= S.points >= I.points >= 2): continue

        # chose remaining "for" and "against" goals for S
        for (x, y) in product(irange(0, gf), irange(0, ga)):
          # look for scorelines
          for (SI1, SI2) in football.scores([si1, si2], [0, 0], x, y):
            ss2 = keys([SI1, SI2])
            if not check(ss0 + ss1 + ss2, ss2): continue
            # and check goals "for"/"against" I
            (x_, y_) = football.goals([SI1, SI2], [1, 1])
            if not (x + x_ == gf and y + y_ == ga): continue
            # check S is second and I is third
            if not (S.points > I.points or fS - aS + x - y > fI - aI + x_ - y_): continue
            if not (I.points > 2 or fI - aI + x_ - y_ > -7): continue
            printf("[EW = {EW1} {EW2}; ES = {ES1} {ES2}; EI = {EI1} {EI2}; WS = {WS1} {WS2}; WI = {WI1} {WI2}; SI = {SI1} {SI2}]")
            rs.add((SI1, SI2))

# output solution
for (k, v) in rs.most_common():
  printf("S vs I = {k} [{v} solutions]", k=join(k, sep=", "))

      Solution: The scores in the Scotland vs. Ireland matches were 4-0 and 0-0.

      There are many scenarios which lead to this solution. One of them is:

      E vs W = 3-2, 2-1
      E vs S = 3-0, 2-0
      E vs I = 5-0, 1-0
      W vs S = 2-2, 1-3
      W vs I = 1-4, 1-1
      S vs I = 4-0, 0-0

      Like

    • John Crabtree's avatar

      John Crabtree 4:28 pm on 16 April 2021 Permalink | Reply

      There were 38 goals scored, ie the minimum possible, and so the match scores were 0-0; 1-0; 2-0, 1-1; 3-0, 2-1; 4-0, 3-1, 2-2; 5-0, 4-1, 3-2.
      Wales scored 8 goals, with scores of 2-3 vE, 1-2 vE, 1-1, 2-2, 1-3 and 1-4.
      And so the scores in England’s other games were 1-0 vI, 2-0, 3-0 and 5-0.
      The other two matches were between Ireland and Scotland with scores of 0-0 and 4-0.

      It is interesting to know when these puzzles started. Some of the later ones were much more convoluted

      Like

  • Unknown's avatar

    Jim Randell 9:46 am on 11 April 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 736: Moving NEWS 

    From The Sunday Times, 24th August 1975 [link]

    Four friends and I live in the same town, one of us at the town centre, and the others at places due north, south, east and west of the town centre. Our names are North, South, East, West and Middle, but we do not necessarily live at the places which accord with our names.

    In visiting one another we use the only connecting roads which run north-south and east-west through the town centre.

    Before last year, when North and I exchanged houses (to accommodate his increasing family, mine by then having left home), I lived farther north than West, who lives farther east than Middle, who lives farther west than East. North lived farther east than South. (When visiting East, North had to turn right at the town centre, but I could go straight ahead when visiting North).

    What is my name, and who lives in the north, east, south, west and middle positions respectively?

    This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980). The puzzle text above is taken from the book.

    [teaser736]

     
    • Jim Randell's avatar

      Jim Randell 9:47 am on 11 April 2021 Permalink | Reply

      I think the wording of this puzzle could be improved.

      I initially took: “I could go straight ahead when visiting North”, to mean that the journey I→N involved passing straight through the centre (i.e. was one of: n→s, e→w, s→n, w→e), but with this condition there are no solutions. So instead I used the condition, that the journey I→N does not involve making a turn at the centre, and that gives a unique solution.

      For each of the directions we can use equivalent statements, for example:

      “X is north of Y” ⇔ “(X is northernmost) ∨ (Y is southernmost)”

      This Python program runs in 47ms.

      Run: [ @replit ]

      from enigma import (subsets, printf)

# map slots to locations
m = { 0: "centre", 1: "north", 2: "east", 3: "south", 4: "west" }

# possible turns at the centre
right = {(1, 4), (2, 1), (3, 2), (4, 3)}
#straight = {(1, 3), (2, 4), (3, 1), (4, 2)}

# choose current positions for (N, S, E, W, M)
for (N, S, E, W, M) in subsets((0, 1, 2, 3, 4), size=len, select="P"):

  # "W is east of M"
  if not (W == 2 or M == 4): continue

  # "M is west of E"
  if not (M == 4 or E == 2): continue

  # "N (was I) is north of W"
  if not (N == 1 or W == 3): continue

  # choose current position for I (not N; not W)
  for I in (S, E, M):
    oldN = I
    oldI = N
    oldS = (N if I == S else S)
    oldE = (N if I == E else E)
    
    # "N was east of S"
    if not (oldN == 2 or oldS == 4): continue

    # "N -> E was a right turn"
    if not ((oldN, oldE) in right): continue

    # "I -> N was straight ahead"
    #if not ((oldI, oldN) in straight): continue
    if (oldI, oldN) in right or (oldN, oldI) in right: continue

    # output solution
    printf("I={I}; N={N} S={S} E={E} W={W} M={M}",
     I="NSEWM"[(N, S, E, W, M).index(I)],
     N=m[N], S=m[S], E=m[E], W=m[W], M=m[M],
    )

      Solution: You are South. The current map is as shown:

      (Previously North and South were swapped over).

      And it can be seen that the journey from South (I) to North does not involve making a turn at the centre, but it also doesn’t involve passing through the centre.

      Like

    • John Crabtree's avatar

      John Crabtree 5:58 pm on 11 April 2021 Permalink | Reply

      Looking at the original map:
      M lived west of W and E, and so M lived at [w]
      N lived east of S, and so N lived at [e]
      N turned right to visit E, and so E lived at [n]
      I lived north of W, and I cannot be E, and so I, South, lived at [m] and W lived at [s].

      Swapping S and N gives the current map, as shown by Jim. Logically it is the only possible arrangement.

      Like

      • John Crabtree's avatar

        John Crabtree 12:21 am on 12 April 2021 Permalink | Reply

        I mixed up the tenses in my comment above. Please read the following before the above:

        I cannot be W, N or E. If I were M, I would have to be in [w] after the swap to live west of E and W. Then N must be in [w] before the swap, which is invalid as he lived east of S. And so I am South. E, M and W did not change positions.

        Like

  • Unknown's avatar

    Jim Randell 8:11 pm on 9 April 2021 Permalink | Reply
    Tags:   

    Teaser 3055: Proceed to checkout 

    From The Sunday Times, 11th April 2021 [link] [link]

    The dartboard at the Trial and Arrow pub is rather different from the standard one: there are only 3 sectors, each with a positive whole number label, and no central bullseye scoring region. There are still double and treble rings: for instance, if the sector label is 3, a dart in that sector can score 3, 6 or 9.

    As usual, scores are counted down from a starting value, the idea being to finish (“check out”) by reaching exactly zero. Players take turns throwing three darts, or fewer if they check out before that. Unusually, the checkout doesn’t have to finish on a double.

    The lowest impossible checkout is the smallest value that can’t be achieved in one turn; on this board that value is 36.

    What are the sector labels?

    [teaser3055]

     
    • Jim Randell's avatar

      Jim Randell 8:42 pm on 9 April 2021 Permalink | Reply

      (See also: Puzzle #06).

      In order to have a score of 1 there must be a “1” sector. This Python program considers sets of three sectors of the form (1, a, b), and calculates the lowest score not achievable with 3 darts, until it finds a value of 36. It runs in 54ms.

      Run: [ @replit ]

      from enigma import union, subsets, irange, inf, peek, printf

# find the lowest score not achievable with k darts and values vs
def lowest(vs, k):
  # scores with 1 dart
  scores = union((v, 2 * v, 3 * v) for v in vs)
  # scores with up to k darts
  ss = set(sum(s) for s in subsets(scores, max_size=k, select="R"))
  # find the lowest score that cannot be made
  return peek(n for n in irange(0, inf) if n not in ss)

# find 3 sectors with lowest impossible score of x
def solve(x, k=3):
  # consider sectors [1, a, b], where a + b = t
  for t in irange(5, inf):
    for a in irange(2, (t - 1) // 2):
      vs = [1, a, t - a]
      if lowest(vs, k) == x:
        yield vs

for vs in solve(36):
  printf("sectors = {vs}")
  break

      Solution: The sector labels are: 1, 5, 22.

      Like

    • Frits's avatar

      Frits 3:08 pm on 10 April 2021 Permalink | Reply 

      from enigma import SubstitutedExpression
from itertools import combinations_with_replacement

# find the lowest score not achievable with 3 darts
# only consider values less equal to <n>
def low(vs, n):
  s = {p for v in vs for i in range(1, 4) if (p := v * i) <= n}
  s = set(su if (su := sum(c)) <= n else 0
             for c in combinations_with_replacement(s, 3))
            
  for x in range(10, n + 1):
    if x not in s:
      return x

  return 99      # high number

p = SubstitutedExpression(
  [
   # look for sectors [1, X, YZ], Y >= X
   # X < 11 as otherwise 10 will be the lowest impossible checkout
  
   # with 2 sectors [1, X] we can never make number Y = 6X + 4
   # with 2 sectors [1, X] we can't make number Y = 4X + 4 unless X < 5
   "YZ < 4 * X + 5 + (X < 5) * 2 * X",
 
   "YZ > max(X, 4)",                # max total [1, X, YZ] >= 35

   # The lowest impossible checkout is 36
   "low([1, X, YZ], 36) == 36",
  ],
  answer="1, X, YZ",
  # exclude X = 4, 6 and 9 as they are factors of 36
  # exclude X = 7 as 5 * 7 + 1 = 36
  # exclude X = 10 as 3 * 10 + 6 * 1 = 36
  # highest value for Y is 2 (as of YZ = 30 you can make 36)
  d2i=dict([(0, "X")] + [(1, "X")] + [(3, "Y")] + [(4, "YX")] + [(5, "Y")] +
  [(k, "YX") for k in range(6, 8)] +
  [(8, "Y")] +
  [(9, "YX")]),
  env=dict(low=low),
  distinct="",   # allow variables with same values
  reorder=0,
  verbose=0,
)

# print answer
for (_, ans) in p.solve():
  print(f"The sectors are: {ans}")

      Like

    • Frits's avatar

      Frits 9:04 pm on 12 April 2021 Permalink | Reply 

      # sector candidates which can go with 1 without immediately making 36 
cands = [X for X in range(2, 36) if X * 9 != 36 and
         not any((29 if i < 4 else 32) < X * i < 37 for i in range(1, 7))]  

# consider the 2nd sector, it must be less than 11 
# as otherwise 10 will be the lowest impossible checkout
for X in [c for c in cands if c < 11]:
  one = [0, 1, 2, 3, X, 2 * X, 3 * X]
  two = {o1 + o2 for o1 in one for o2 in one}   
  
  mi = max(5, X + 1)
  # determine lowest score which can't be made with 3 darts in sectors [1, X]
  if X > 7:
    ma = 15 + (X - 8)
  elif X > 4:  
    ma = 4 * X + 4
  else:
    ma = 6 * X + (4 if 4 % X else 5) 
  
  # one dart in sector Y
  candsY = [Y for Y in cands if mi <= Y <= ma and 
            all(36 - i not in two for i in [Y, 2 * Y, 3 * Y])]
  
  # two darts in sector Y scoring at least 4 * Y
  candsY = [Y for Y in candsY if
            all(36 - i not in one for i in [4 * Y, 5 * Y, 6 * Y])]
  
  # if X > 2 and Y > 18 then number Y + 3 * X + 4 is no checkout
  candsY = [Y for Y in candsY if X == 2 or Y < 18 or Y + 3 * X + 4 > 35]   
  
  if candsY:
    three = {t + o for t in two for o in one}  
    remaining = [x for x in range(ma, 36) if x not in three]  
   
  for Y in candsY:
    if all(r - Y in two for r in remaining):
      print(f"The sectors are: 1, {X} and {Y}")

      Like

  • Unknown's avatar

    Jim Randell 12:05 pm on 8 April 2021 Permalink | Reply
    Tags:   

    Teaser 2789: Uncle’s gift (2) 

    From The Sunday Times, 6th March 2016 [link] [link]

    Last month I told you about Uncle Bill’s gifts to his nephews. Uncle Ben has also sent a whole number of pounds (less than fifty) to be shared among his three nephews Tom, Dick and Harry. Each has received a different whole number of pounds, with Tom receiving the most and Harry the least, but with Tom getting less than twice as much as Harry. Each boy’s fraction of the total gift, when expressed as a decimal, consists of three different digits recurring (as in 0.abcabc…), and each boy’s decimal uses the same three digits.

    How much did Tom, Dick and Harry get from Uncle Ben?

    [teaser2789]

     
    • Jim Randell's avatar

      Jim Randell 12:06 pm on 8 April 2021 Permalink | Reply

      A similar puzzle to Teaser 2785.

      In fact we can just change the selection criteria at line 21 of my original program for Teaser 2785 to give a program that solves this puzzle.

      This Python program runs in 64ms.

      Run: [ @replit ]

      from enigma import (irange, divc, divf, recurring, subsets, arg, printf)

M = arg(49, 0, int)

# consider the total amount
for t in irange(6, M):

  # look for amounts that give 3 recurring digits
  r = dict()
  for n in irange(divc(t, 5), min(t - 3, divf(2 * t, 3))):
    (i, nr, rr) = recurring(n, t)
    if nr or len(rr) != 3: continue
    r[n] = rr

  # now find three amounts that sum to t
  for (H, D, T) in subsets(sorted(r.keys()), size=3):
    if H + D + T != t: continue
    # "Tom gets less than twice as much as Harry"
    if not (T < 2 * H): continue
    # and check the recurring digits are all the same
    if not (set(r[H]) == set(r[D]) == set(r[T])): continue
    printf("total={t}; Harry={H} [0.({rH})...], Dick={D} [0.({rD})...], Tom={T} [0.({rT})...]", rH=r[H], rD=r[D], rT=r[T])

      Solution: Tom got £ 16, Dick got £ 12, and Harry got £ 9. In total they received £ 37.

      And the fractions are:

      T: 16 / 37 = 0.(432)…
      D: 12 / 37 = 0.(324)…
      H: 9 / 37 = 0.(243)…

      And, again, we can find further solutions, using the same fractions, at multiples of these amounts.

      The next essentially different solution occurs at £ 111, where we have the original solution multiplied by 3, but also:

      T: 47 / 111 = 0.(423)…
      D: 38 / 111 = 0.(342)…
      H: 26 / 111 = 0.(234)…

      Like

    • John Crabtree's avatar

      John Crabtree 4:17 pm on 9 April 2021 Permalink | Reply

      There is not much change to the manual solution either.
      The fractions are of the form of abc / 999 = abc / (27 * 37)
      The three digits are 2, 3 and 4, with one of each in each column.
      If the sum were £27, abc = 0 mod 37, but 9 * 37 = 333
      And so the sum = £37, abc = 0 mod 27.
      And so, by inspection, 9 * 27 = 243, and then 12 * 27 = 324 and 16 * 27 = 432
      The solution follows.

      Like

  • Unknown's avatar

    Jim Randell 10:52 am on 6 April 2021 Permalink | Reply
    Tags:   

    Teaser 2785: Uncle’s gift (1) 

    From The Sunday Times, 7th February 2016 [link] [link]

    Uncle Bill has sent a whole number of pounds (less than fifty) to be shared among his three nephews Tom, Dick and Harry. Each has received a whole number of pounds, with Tom receiving the most and Harry the least, but with Tom getting less than twice as much as Harry. Each boy’s fraction of the total gift, when expressed as a decimal, consists of three digits recurring (as in 0.abcabc…), and the nine digits that appear in the three decimals are all different. (Uncle Ben also sent some money, but I’ll tell you about that next month).

    How much did Tom, Dick and Harry get from Uncle Bill?

    [teaser2785]

     
    • Jim Randell's avatar

      Jim Randell 10:53 am on 6 April 2021 Permalink | Reply

      This Python program uses the [[ recurring() ]] function from the enigma.py library. It runs in 69ms.

      Run: [ @replit ]

      from enigma import (irange, divc, divf, recurring, subsets, arg, printf)

M = arg(49, 0, int)

# consider the total amount
for t in irange(6, M):

  # look for amounts that give 3 recurring digits
  r = dict()
  for n in irange(divc(t, 5), min(t - 3, divf(2 * t, 3))):
    (i, nr, rr) = recurring(n, t)
    if nr or len(rr) != 3: continue
    r[n] = rr

  # now find three amounts that sum to t
  for (H, D, T) in subsets(sorted(r.keys()), size=3):
    if H + D + T != t: continue
    # "Tom gets less than twice as much as Harry"
    if not (T < 2 * H): continue
    # and check the recurring digits are all different
    if len(set(r[H] + r[D] + r[T])) != 9: continue
    printf("total={t}; Harry={H} [0.({rH})...], Dick={D} [0.({rD})...], Tom={T} [0.({rT})...]", rH=r[H], rD=r[D], rT=r[T])

      Solution: Tom got £ 15, Dick got £ 14, and Harry got £ 8. In total they received £ 37.

      The fractions are:

      T: 15 / 37 = 0.(405)…
      D: 14 / 37 = 0.(378)…
      H: 8 / 37 = 0.(216)…

      There are further solutions at multiples of these amounts (the fractions, of course, remain unchanged).

      The next essentially different solution occurs with a total of £ 333, where we can have the original solution multiplied by 9, but also:

      T: 136 / 333 = 0.(408)…
      D: 125 / 333 = 0.(375)…
      H: 72 / 333 = 0.(216)…

      T: 135 / 333 = 0.(405)…
      D: 106 / 333 = 0.(318)…
      H: 92 / 333 = 0.(276)…

      T: 136 / 333 = 0.(408)…
      D: 105 / 333 = 0.(315)…
      H: 92 / 333 = 0.(276)…

      Like

    • Frits's avatar

      Frits 2:57 pm on 8 April 2021 Permalink | Reply 

      from collections import defaultdict

alldiff = lambda seq: len(seq) == len(set(seq))

# ceil a positive number
ceil = lambda n: int(n) if n == int(n) else int(n) + 1

# if we have P/Q = 0.abcabc…
# then there must be an R so that R * Q = 999
# 999 is 27 * 37

d = defaultdict(list)

# whole number of pounds is less than fifty (and more than 5)
for N in [27, 37]:          # skip 9 as 1/9 = 0.111111...

 d[N] = [[0, 0]]
 # collect abc's where i / N = 0.abcabc...
 for i in range(1, N):
   d[N].append([i, str(i / N)[2:5]])

 # min Harry: H + (H + x) + (H + y) = N and H + y < 2 * H  with 0 < x < y
 #            introduce y = H - p, x = H - q with 0 < p < q
 #            5 * H - p - q = N so H >= N / 5 + 0.6
 minH = ceil(N / 5 + 0.6)

 # max Harry: H + (H + x) + (H + y) = N --> H <= (N - 3)/3
 maxH = (N - 3) // 3
 maxH = min((N - 3) // 3, 2 * minH - 1)

 for H in d[N][minH:maxH + 1]:
   if not alldiff(H[1]): continue
   for D in d[N][H[0] + 1:(N - H[0] - 1) // 2 + 1]:
     if not alldiff(H[1] + D[1]): continue

     # remainder is Tom's number
     T = N - H[0] - D[0]
     if T >= 2 * H[0] or T <= D[0]: continue
     if not alldiff(H[1] + D[1] + d[N][T][1]): continue

     print(f"Tom, Dick, Harry: {T}, {D[0]}, {H[0]}")

      Like

    • John Crabtree's avatar

      John Crabtree 4:15 pm on 9 April 2021 Permalink | Reply

      The fractions are of the form of abc / 999 = abc / (27 * 37).
      The sum of the “abc”s is 999. The individual digits are 0 or 9, and 1 to 8.
      The “a”s must be 2, 3 and 4. Then the “b”s are 0, 1 and 7, and the “c”s are 5, 6 and 8.
      If the sum were £27, abc = 0 mod 37, but 5 * 37 = 185 and 15 * 37 = 535.
      And so the sum = £37, and abc = 0 mod 27
      And so, by inspection, 15 * 27 =405, and then 8 * 27 = 216 and 14 * 27 = 378
      The solution follows.

      Like

    • Frits's avatar

      Frits 10:51 am on 10 April 2021 Permalink | Reply

      Based on Jim’s unpublished program (in code section of replit).

      This time not using the fact that XY must be 27 or 37.

      #!/usr/bin/env python3 -m enigma -r

# Harry = 0.(EFG)...  EFG = HA * PQ
# Dick  = 0.(JKL)...  JKL = DI * PQ
# Tom   = 0.(RST)...  RST = TO * PQ
#
# where XY * PQ = 999   (skip XY = 9 as 1/9 = 0.111111...)
#
# each gets an integer share of XY (< 50)

SubstitutedExpression

--distinct=""
# HA is maximal if Dick and Tom have values HA + 1 and HA + 2 
# so HA < 16 and TO < 30
--invalid="2|3|4|5|6|7|8|9,H"
--invalid="3|4|5|6|7|8|9,T"
--invalid="0|5|6|7|8|9,X"

# XY * PQ = 999
"div(999, XY) = PQ"                # exact division

# HA is minimal if Dick and Tom have values 2 * HA - 2 and 2 * HA - 1
# HA is maximal if Dick and Tom have values HA + 1 and HA + 2
"3 * XY + 9 <= 15 * HA <= 5 * XY - 15"

# TO > DI means TO > XY - HA - TO so 2 * TO > XY - HA
# Tom got less then twice as much as Harry
# TO is maximal if Dick is HA + 1 so TO <= XY - 2 * HA - 1
"XY - HA < 2 * TO <= min(4 * HA - 2, 2 * XY - 4 * HA - 2)"

# together they give the entire amount
"XY - HA - TO = DI"

# EFG, JKL and RST must use different digits
"len(set(str(HA * PQ) + str(DI * PQ) + str(TO * PQ))) == 9"

# (Total, Tom, Dick, Harry)
--answer="XY, TO, DI, HA"
--verbose=16
--reorder=0

      Like

← Older posts

Newer posts →

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel
Design a site like this with WordPress.com
Get started