flawed | S2T2

Tagged: flawed Toggle Comment Threads | Keyboard Shortcuts

Jim Randell 8:11 am on 16 January 2026 Permalink | Reply
Tags: by: W S Graff-Baker ( 2 ), flawed
Teaser 2312: Backward step
From The Sunday Times, 14th January 2007 [link]

Seb had just been given his four-digit PIN, and he was afraid that he would not be able to remember it. So he broke all the rules and wrote it in his pocket diary. But to make it “more secure” he did not actually write the PIN; instead, he wrote the digits in reverse order. He was surprised to discover that the new number was a multiple of the correct PIN.

What is his PIN?

Note that without additional requirements there are many solutions to this puzzle. The intended solution seems to come from the requirement that all the digits of the PIN are non-zero.

[teaser2312]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
GeoffR, Ruud, and Jim Randell are discussing. Toggle Comments
- Jim Randell 8:12 am on 16 January 2026 Permalink | Reply
  Here is a solution using the [[ SubstitutedExpression ]] solver from the enigma.py library.
  
  It runs in 82ms. (Internal runtime of the generated code is 1.7ms).
```
#! python3 -m enigma -rr

SubstitutedExpression

# suppose the real PIN is ABCD
"ediv(DCBA, ABCD) > 1"
"D >= A" # [optional]

--distinct=""
--invalid=""
--digits="1-9"
--answer="ABCD"
```
  Solution: The PIN is: 2178.
  
  And so the reversed PIN is: 8712.
  
  And: 8712 = 4 × 2178.
  
  (The multiple solutions to the puzzle as published can be seen by removing the digit restriction on line 11).
  
  Without the restriction to non-zero digits there are 131 solutions, for example (reversed-PIN, PIN):
  
  1000 & 0001
  1010 & 0101
  …
  9801 & 1089
  …
  9990 & 0999
  
  (Although not all these would be surprising).
  
  But only one of these solutions remains if the digits of the PIN must all be non-zero.
  
  The published solution was: “1089 or 2178”.
  
  LikeLike
- Ruud 10:33 am on 16 January 2026 Permalink | Reply
```
import istr
print(*(pin for digits in istr.product(range(1, 10), repeat=4) if (pin:=istr.join(digits))[::-1].divided_by(pin) not in (1, None)))
```
  LikeLike
- GeoffR 7:43 pm on 16 January 2026 Permalink | Reply
```
from enigma import nsplit, is_pairwise_distinct

for pin in range(1234, 9876):
    a, b, c, d = nsplit(pin)
    if 0 in (a, b, c, d): continue
    if is_pairwise_distinct(a, b, c, d):
        rev_pin = 1000*d + 100*c + 10*b + a
        q, r = divmod(rev_pin, pin)
        if r == 0 and q > 1:
           print(f"Pin = {pin}.")
```
  LikeLike
Reply Cancel reply
Required fields are marked *

Name *

Email *

Website

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.
Jim Randell 10:02 am on 11 November 2025 Permalink | Reply
Tags: by: Victor Bryant ( 140 ), flawed
Teaser 2481: [Coach trip]
From The Sunday Times, 11th April 2010 [link]

My wife and I took a coast-to-coast coach tour of the USA, starting at New York and travelling steadily westwards to San Francisco. The coach had rows of seats, each row consisting of a double seat on the left and a double seat on the right. In New Jersey we were in the left-hand seat of the middle row. For each new state we moved two seats clockwise. Just as we were about to move to the best seat (front right) Clive – the courier – told us thereafter to move three seats clockwise for each state. But we did get the best seat later in the holiday.

In which state were we sitting in the best seat?

This puzzle was originally published with no title.

[teaser2481]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 10:03 am on 11 November 2025 Permalink | Reply
  I’m not sure how this puzzle is meant to work, as it surely depends on the route taken.
  
  I tried using Google and Apple Maps to give routes from New York to San Francisco, and the 4 suggested routes visited the following states:
  
  NY → NJ → PA → OH → IN → IL → IA → NE → WY → UT → NV → CA (I80)
  NY → NJ → PA → WV → OH → IN → IL → MO → NE → WY → UT → NV → CA (I70/I80)
  NY → NJ → PA → WV → OH → IN → IL → MO → OK → TX → NM → AZ → CA (I40/I5)
  NY → NJ → PA → MD → WV → VA → TN → AR → OK → TX → NM → AZ → CA (I40/I5)
  
  And these are just the “direct” routes. On a coach tour it is quite possible that it takes a less direct route, and visits more states.
  
  This Python program considers possible numbers of seats on the coach and looks for configurations where the front right seat is missed the first time (when the increment changes from +2 to +3) but hit subsequently. It then checks what that means for the four routes given above.
```
from enigma import (irange, seq_get, seq2str, printf)

# possible routes from New York to San Francisco
routes = list(x.split() for x in [
  "NY NJ PA OH IN IL IA NE WY UT NV CA", # I80
  "NY NJ PA WV OH IN IL MO NE WY UT NV CA", # I70/I80
  "NY NJ PA WV OH IN IL MO OK TX NM AZ CA", # I40/I5
  "NY NJ PA MD WV VA TN AR OK TX NM AZ CA", # I40/I5
])

# suppose the coach has n rows in front of the middle row and n rows
# behind it, so (2n + 1) rows in total, and (4n + 2) seats, which we
# will number 0 .. 4n + 1, going clockwise starting from the left hand
# seat, middle row

def solve(n):
  # layout of the coach
  rows = 2 * n + 1
  seats = 2 * rows
  best = n + 1
  # we start in seat 0, and move 2 each state
  k = 0
  i = 2
  # consider visiting state j (starting at 1 = NJ)
  for j in irange(2, 50):
    # move to the next seat
    k = (k + i) % seats
    # are we going to get the best seat?
    if k == best:
      if i == 2:
        # we start to move 3 seats instead
        i += 1
        k += 1
      else:
        # we got the best seats in state j
        printf("{rows} rows; {seats} seats; best @ {j}")
        # check against the routes
        for route in routes:
          r = seq_get(route, j)
          if r is not None:
            printf("-> {route} @ {r}", route=seq2str(route))

# consider possible coach configurations
for n in irange(1, 20):
  solve(n)
```
  There appear to be two possible scenarios:
  
  (1) In a coach with 7 rows of seats (= 28 individual seats).
  
  The seats are laid out as follows (viewed from above):
```
[01] - [02] = front
[03] - [04]
[05] - [06]
[07] - [08]
[09] - [10]
[11] - [12]
[13] - [14] = back
```
  In NJ (state 1) the setter is in seat 07 and proceeds as follows:
  
  07 (+2) 03 (+3) 04 (+3) 10 (+3) 13 (+3) 07 (+3) 01 (+3) 06 (+3) 12 (+3) 11 (+3) 05 (+3) 02 [best]
  
  Which means being in the best seat in state 12.
  
  The shortest route given above only has 10 states after NJ, so is not possible, and for the remaining three routes this is the final state, California.
  
  (2) In a coach with 11 rows of seats (= 44 individual seats).
  
  The seats are laid out as:
```
[01] - [02] = front
[03] - [04]
[05] - [06]
[07] - [08]
[09] - [10]
[11] - [12]
[13] - [14]
[15] - [16]
[17] - [18]
[19] - [20]
[21] - [22] = back
```
  In NJ (state 1) the setter is in seat 11 and proceeds as follows:
  
  11 (+2) 07 (+2) 03 (+3) 04 (+3) 10 (+3) 16 (+3) 22 (+3) 17 (+3) 11 (+3) 05 (+3) 02 [best]
  
  Which means being in the best seat in state 11.
  
  For the routes given this could be California, Nevada, or Arizona.
  
  And if the route were to visit more states there are further solutions.
  
  The next is in a coach with 23 rows of seats (= 92 individual seats), and happens in state 22 (which would require a less direct route, possibly revisiting states).
  
  If the list of states visited had been given as:
  
  NY → NJ → PA → OH → IN → IL → IA → NE → WY → UT → NV → CA (I80)
  
  (i.e. the most direct of the suggested routes).
  
  Then the only possible solution is a coach with 11 rows of seats, and the setter gets the best seat in state 11 = California.
  
  And the published solution is “California”, so perhaps this is what the setter had in mind.
  
  LikeLike
Jim Randell 8:07 am on 1 August 2025 Permalink | Reply
Tags: by: Danny Roth ( 84 ), flawed
Teaser 2472: [Running from a train]
From The Sunday Times, 7th February 2010 [link]

George and Martha stood on the platform as the train approached at a steady 20 metres per second. Both platform and train were 100 metres long. The train was programmed to decelerate steadily as it reached the start of the platform. A boy slipped off the platform onto the track. He could run at 2 metres per second. “Run to your left — you’re nearer that end of the platform”, shouted Martha. “No, run to the other end, away from the train”, said George. Either action would just avert disaster.

How far ahead of the train did he fall?

This puzzle was originally published with no title.

Although this puzzle can be solved, the published solution was incorrect.

[teaser2472]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 8:08 am on 1 August 2025 Permalink | Reply
  
  I am assuming the train does not start any kind of emergency braking procedure, and so begins decelerating at the start of the platform, and ends (with the train stationary) aligned with the end of the platform.
  
  In the first scenario the boy runs towards the train (which hasn’t begun to slow down yet). If he reaches the start of the platform (and dodges around it) after x seconds, just as the train arrives at the start of the platform, then he has run a distance of 2x metres, and the train has travelled 20x metres.
  
  In the second scenario, the boy runs away from the train. After x seconds the train arrives at the start of the platform and starts to decelerate, such that its speed will be 0 when it arrives at the end of the platform (which is 100 m long).
  
  The train starts at 20 m/s and after 100 m it reaches 0 m/s, the deceleration of the train is thus:
  
  [v² = u² + 2as]
  0 = (20)^2 + 2a . 100
  ⇒
  a = −2 [m/s^2]
  
  And the velocity of the train after time t from the start of the platform is:
  
  [v = u + at]
  v = 20 − 2t
  
  So it takes the train 10 s to decelerate to 0 m/s.
  
  We are interested in the time it takes for the train to decelerate to 2 m/s (after which the boy will outpace it, and get to the end of the platform before the train).
  
  This happens at:
  
  v = 2
  ⇒
  t = 9
  
  i.e. 9 seconds after the train reaches the start of the platform.
  
  The distance along the platform travelled by the train in these 9 seconds is:
  
  [s = ut + (1/2)at²]
  d = 20 . 9 + (1/2)(−2)(9^2) = 99 [m]
  
  So there is 1 m of platform left.
  
  And the boy has to run a distance of (99 − 2x) m in the time it takes the train to decelerate to 2 m/s.
  
  The time taken for the boy to do this is:
  
  t = (99 − 2x) / 2
  
  And the time taken for the train to arrive at the same point is:
  
  t = x + 9
  
  If disaster is just averted, these times are equal:
  
  (99 − 2x) / 2 = (x + 9)
  ⇒
  x = 81/4 = 20.25
  
  So the boy falls a distance 2x from the start of the platform = 40.5 m.
  
  And at that time the train is 20x away from the start of the platform = 405 m.
  
  Hence:
  
  Solution: The boy falls at a distance of 445.5 m in front of the train.
  
  Here is a time/distance graph of the situation:
  
  The train enters from the top along the solid blue line (constant speed), and then as it passes the start of the platform it follows the dashed blue line (constant deceleration), until it stops at the end of the platform.
  
  The scenarios for the boy are indicated by the red lines.
  
  The upper red line is the path taken by the boy running toward the start of the platform (and the oncoming train), to arrive at the start at the same time as the train.
  
  And the lower red line is the path take by the boy running towards the end of the platform (away from the train).
  
  Zooming in on the final section we see that at 29.25 seconds the train catches up with the boy, as they are both going 2 m/s. The boy then outpaces the train to reach the end of the platform 0.5 seconds later, and the train finally stops at the end of the platform 0.5 seconds after that.
  
  Whichever direction the boy chooses to run in, he has to start as soon as he lands, and so he doesn’t have time to listen to advice from either Martha or George.
  
  However, the published answer was 440 m.
  
  This gives us:
  
  20x + 2x = 440
  ⇒
  x = 20
  
  Which means the boy fell 40 m from the start of the platform.
  
  If we plot the distance/time graph associated with these values we see that although the train and the boy coincide at the end of the platform when the train is stationary, they also coincide 4 m before the end of the platform, when the boy is hit by the moving train. So this does not provide a viable solution to the puzzle.
  
  Looking closer at the end we see at 28 seconds the train hits the boy, 2 seconds before they would both have arrived at the end of the platform.
  
  At the point of impact the train would be travelling at 4 m/s (≈ 9 mph).
  
  If the puzzle had been set so that, instead of trying to escape from the train, the boy was just trying to race the train to get to one end of the platform before the train does, then the published solution would work, and the boy and train would arrive simultaneously regardless of which end of the platform the boy chose to run to.
  
  I couldn’t find any correction to the published solution in The Sunday Times digital archive.
  
  LikeLike
Jim Randell 6:24 am on 13 July 2025 Permalink | Reply
Tags: by: John Owen ( 33 ), flawed
Teaser 3277: Croquet equipment
From The Sunday Times, 13th July 2025 [link] [link]

Our non-standard croquet lawn has six hoops, at positions A to F, and a central peg at P. The equipment storage box is in the southwest corner at S, and the lawn is symmetrical in both the east-west and north-south directions. The diagram is not to scale, but D is south of the projected line from S to E.

Also AB is half the width of the lawn. When setting out the equipment, I walk along the route SEFDPCBAS. All of the distances on my route between positions are whole numbers of feet (less than 60), and both D and E are whole numbers of feet north of the south boundary.

What is the total distance of my route?

[teaser3277]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Hugo, Jim Randell, and Frits are discussing. Toggle Comments
- Jim Randell 8:46 am on 13 July 2025 Permalink | Reply
  I get two solutions, so here is a straightforward solution to make sure I haven’t missed any thing.
  
  But if we disallow distances of 60ft or more between any two positions on the walk (not just adjacent positions), then we can eliminate the larger of these solutions.
  
  This Python program runs in 65ms. (Internal runtime is 5ms).
```
from enigma import (irange, ihypot, printf)

M = 59  # max length of a path segment

# let AB = EF = 2x
for x in irange(1, M // 2):
  # e = distance E north from southern edge
  for e in irange(1, M):
    SE = ihypot(x, e)
    if SE is None or SE > M: continue

    # d = distance D is north of EF
    for d in irange(1, e - 1):
      FD = ihypot(x, d)
      if FD is None or FD > M: continue

      # p = distance P north of D
      for p in irange(1, M):
        SA = ihypot(x, e + d + p + p + d)
        if SA is None or SA > M: continue

        # total distance walked
        T = SE + SA + 2*FD + 4*x + 2*p
        printf("T={T} [SE={SE} FD={FD} SA={SA}; x={x} e={e} d={d} p={p}]")
```
  Solution: There are two viable solutions to the puzzle: 142 ft, and 220 ft.
  
  Apparently the size of a croquet lawn is not fixed, but it should be a rectangle with sides in the ratio of 1.25.
  
  The first of the solutions involves a playing area of 48 ft × 44 ft (ratio = 1.09).
  
  And all positions on the route are within 60 ft of S (as indicated by the dotted line).
  
  The second of the solutions involves a playing area of 96 ft × 42 ft (ratio = 2.29).
  
  And B and F are further than 60 ft from S.
  
  The published solution is: “142 feet”.
  
  But a correction was issued with Teaser 3280:
  
  There were in fact two possible answers: 142 and 220 feet.
  Either was accepted as correct.
  
  .
  
  LikeLike
  - Frits 11:38 am on 13 July 2025 Permalink | Reply
    
    @Jim, shouldn’t we have: e + d + p = 2.x ?
    
    LikeLike
    - Jim Randell 11:56 am on 13 July 2025 Permalink | Reply
      
      @Frits: Why?
      
      LikeLike
      - Frits 12:18 pm on 13 July 2025 Permalink | Reply
        
        I assumed that the lawn was square (but that isn’t specified).
        
        LikeLike
  - Jim Randell 4:19 pm on 13 July 2025 Permalink | Reply
    Alternatively, using the [[ pythagorean_triples() ]] function from the enigma.py library.
    
    The following Python program has an internal runtime of 122µs.
```
from enigma import (defaultdict, pythagorean_triples, subsets, div, printf)

M = 59  # maximum length of a path segment

# collect (<other>, <hypot>) sides for pythagorean triples
t = defaultdict(list)
for (x, y, z) in pythagorean_triples(M):
  t[x].append((y, z))
  t[y].append((x, z))

# consider possible x values
for x in sorted(t.keys()):
  if 2 * x > M: break
  # FD, SE, SA all have base x, and increasing vertical sides
  ts = sorted(t[x])
  for ((d, FD), (e, SE), (a, SA)) in subsets(ts, size=3):
    p = div(a - e - 2*d, 2)
    if p is None or p < 1: continue

    # total distance walked
    T = SE + SA + 2*FD + 4*x + 2*p
    printf("T={T} [SE={SE} FD={FD} SA={SA}; x={x} e={e} d={d} p={p}]")
```
    LikeLike
- Hugo 10:34 am on 21 July 2025 Permalink | Reply
  
  If hoop P has coordinates (0, 0) then it seems
  A is at (12, -13), B is at (12, 13)
  C is at (0, 8), D is at (0, -8)
  E is at (-12, -13), F is at (-12, 13)
  S is at (-24, -22).
  
  It would have been kind of them to tell us that all the distances, including x and y separations, are integers.
  
  LikeLike

Jim Randell 7:08 am on 24 November 2024 Permalink | Reply
Tags: by: Peter Good ( 27 ), flawed

Teaser 3244: Borderline case

From The Sunday Times, 24th November 2024 [link] [link]

Jack has a set of 28 standard dominoes: each domino has a spot pattern containing 0 to 6 spots at either end and every combination ([0-0], [0-1] and so on up to [6-6]) is represented in the set. He laid them end-to-end in several strips and arranged each strip so it formed the border of an empty square. Adjacent dominoes in each strip shared the same spot pattern where they were joined and the total number of spots on each strip was the square of the number of dominoes in that strip. More than half of the doublets were in the longest strip and there was a doublet in just one of the two shortest strips. This doublet was the largest possible in a strip of this size.

Which dominoes were in the shortest strip that doesn’t contain a doublet?

I think this puzzle is poorly worded. But I give an interpretation of the text that does give a unique answer to the puzzle in the comments below.

[teaser3244]

Jim Randell 11:25 am on 24 November 2024 Permalink | Reply

Initially I thought that the dominoes were formed into a collection of [straight linear] strips, and then these strips were used (as is) to make the border of a (single) square.

However, after working on the puzzle for some time I was not able to find a solution using this interpretation (or variations thereof).

You can see my thoughts in the chat page [ here ].

However, I think I have now found an alternative interpretation that does lead to a unique answer to the puzzle.

To me the use of the term “strip” implied that a selected set of dominoes were formed into a straight linear arrangement, whereas it seems that they need to be formed into a square loop. So in the following I just used the term “pile”.

The set of 28 dominoes is formed into a collection of piles, such that for each pile:

+ The total sum of the pips is the square of the number of the dominoes in that pile.

+ The dominoes in each pile can be arranged to form a closed loop that is the outline of a square, and where two dominoes meet the pip values on the adjoining ends are the same.

Additional requirements for the collection of piles are:

+ There is a single pile that is identifiably the largest pile, and it contains more than half of the double tiles.

+ There are (exactly) two piles that are identifiably the smallest piles. One of these piles contains a double tile, and this double is the largest possible double that can occur in a pile of that size (constructed subject to the conditions above).

+ The other smallest pile does not have a double in it, and the required answer is a list of dominoes that make up this pile.

I have verified that under this interpretation there is a unique answer to the puzzle, and have posted my code below.

Solution: [see below]

LikeLike
- Rob Bellis 8:48 am on 26 November 2024 Permalink | Reply
  
  hello Jim
  
  Is there any reason why the square cound not be bounded by 2 x 8 tiles and 2 x 6 tiles (to enclose a 6×6 square) ?
  If each side length 6 was constructed of a 2 +4 tile strings then the sum of the squares would = 168 which is the total domino spots .
  
  LikeLike
  - Jim Randell 8:56 am on 26 November 2024 Permalink | Reply
    
    In my initial interpretation of the puzzle I did look at attempting to make the outline of a single 14×14 square from a collection of straight strips, but it was not possible using 26 of the dominoes (for example: [7] + [4, 3] + [4, 2] + [4, 2]).
    
    In the (presumably) intended interpretation, enclosing a 6×6 square would require 14 dominoes, so to form an allowable loop there would have to be 14^2 = 196 pips in the selection. But there are only 168 pips in the entire set of dominoes, so the squares must be smaller than this.
    
    LikeLike
NigelR 5:38 pm on 24 November 2024 Permalink | Reply

A single domino doesn’t seem to satisfy being a border of an empty square. However, the wording would seem to allow a single strip being part of more than one square. Perhaps we are looking for a more complex shape than one or more detached squares?

LikeLike

Jim Randell 11:12 am on 25 November 2024 Permalink | Reply

This Python 3 program solves the interpretation of the puzzle given above in my first comment.

It assumes the two smallest piles are the same size.

It runs in 851ms.

from enigma import (
  defaultdict, irange, inf, first, subsets, sq, express, flatten,
  rev, remove, trim, cproduct, multiset, join, printf
)

# we represent a domino by a tuple (x, y)

# format a collection of dominoes
fmt = lambda ds: join((join(d, sep='-', enc="[]") for d in ds), sep=' ')

# number of pips on a domino
pips = sum

# a complete set of dominoes
ds = set(subsets(irange(0, 6), size=2, select='R'))

# normal form of dominoes
normalise = lambda d: tuple(sorted(d))
normal = lambda *ss: (normalise(d) for d in flatten(ss, fn=iter))

# invalid pips (sorts before all valid pips)
X = -1

# generate loops with <k> dominoes and <t> pips, from dominoes <ds>
# <m> = min starting domino
def loops(k, t, ds, m=(X, X), ss=[]):
  # are we done?
  if k == 0:
    # remove duplicate loops
    if normalise(ss[1]) > normalise(ss[-1]): return
    # check all pips are used, and a loop is formed
    if t == 0 and ss[0][0] == ss[-1][-1]:
      yield (ss, ds)
  elif not (t > 12 * k):
    # choose the next domino
    for d in ds:
      nd = normalise(d)
      if nd < m or (ss and normalise(ss[0]) > nd): continue
      p = pips(d)
      if p > t: continue
      if (not ss) or (d[0] == ss[-1][-1]):
        yield from loops(k - 1, t - p, remove(ds, d, rev(d)), m, ss + [d])

# make a collection of loops with length <ks>, from dominoes <ds>
def piles(ks, ds, rs=[]):
  # are we done?
  if not ks:
    yield (rs, ds)
  else:
    k = ks[0]
    m = (normalise(rs[-1][0]) if rs and k == len(rs[-1]) else (X, X))
    for (ss, ds_) in loops(k, sq(k), ds, m):
      yield from piles(ks[1:], ds_, rs + [ss])

# find the doubles in a set of dominoes
doubles = lambda ds: sorted(x for (x, y) in ds if x == y)

# max or X
max_ = lambda xs: (max(xs) if xs else X)

# total number of pips
tpips = sum(pips(d) for d in ds)
printf("[{n} dominoes, total pips = {tpips}]", n=len(ds))

# piles have an even number of dominoes, minimum 4
ns = first(irange(4, inf, step=2), count=(lambda x: sq(x) < tpips))
printf("[pile sizes = {ns}]")

# initial set of dominoes in either orientation
dss = set(flatten({d, rev(d)} for d in ds))

# collect results
rs = multiset()

# look for possible numbers of piles (at least 3)
for qs in express(tpips, list(sq(n) for n in ns)):
  if sum(qs) < 3: continue
  # form the pile sizes (in order)
  ks = flatten([n] * q for (n, q) in zip(ns, qs) if q > 0)
  # use all the dominoes
  if sum(ks) != 28: continue
  # there should be 2 identifiable smallest piles, and 1 identifiable largest pile
  if not (ks[0] == ks[1] < ks[2] and ks[-2] < ks[-1]): continue
  # the largest pile has 4 doubles -> a loop of at least 8 dominoes
  if ks[-1] < 8: continue
  printf("[checking {ks} = {n} dominoes]", n=sum(ks))

  # start with the smallest piles (size k)
  (k, gs) = (ks[0], defaultdict(list))
  for (ss, _) in loops(k, sq(k), dss):
    gs[max_(doubles(ss))].append(ss)
  # max possible double in a smallest pile
  m = max(gs.keys())
  assert m != X

  # choose the two smallest piles
  for (ss1, ss2) in cproduct([gs[X], gs[m]]):
    # which must contain distinct dominoes
    xs = set(normal(ss1, ss2))
    if len(xs) < 2 * k: continue

    # choose the largest pile (size K)
    (K, dss_) = (ks[-1], dss.difference(xs, (rev(x) for x in xs)))
    for (ssz, dsz) in loops(K, sq(K), dss_):
      # which must have at least 4 doubles
      if len(doubles(ssz)) < 4: continue

      # fill out the remaining piles
      for (ps, _) in piles(trim(ks, head=2, tail=1), dsz):
        ans = tuple(sorted(normal(ss1)))
        # display the collection of piles
        printf("ss1 = {ss1} -> answer", ss1=fmt(ss1))
        printf("ss2 = {ss2}", ss2=fmt(ss2))
        for (i, ss) in enumerate(ps, start=3):
          printf("ss{i} = {ss}", ss=fmt(ss))
        printf("ss{z} = {ssz}", z=len(ps) + 3, ssz=fmt(ssz))
        printf()
        rs.add(ans)

# output solutions
for (ss, n) in rs.most_common():
  printf("dominoes = {ss} [{n} solutions]", ss=fmt(ss))

Solution: The required dominoes are: [0-1] [0-5] [1-2] [2-5].

Here are the 28 dominoes split into 5 piles, and each pile laid out as a square loop:

[1-0] [0-5] [5-2] [2-1]
[2-0] [0-3] [3-3] [3-2]
[0-0] [0-4] [4-3] [3-5] [5-6] [6-0]
[3-1] [1-4] [4-2] [2-2] [2-6] [6-3]
[1-1] [1-5] [5-5] [5-4] [4-4] [4-6] [6-6] [6-1]

The dominoes that make up the answer to the puzzle are those in the first (top-left) square, which has 4 dominoes and 16 pips in total.

The second (top-right) square uses the double [3-3], which is the largest possible double for a loop with 4 dominoes. It also has 16 pips in total.

Each of the middle squares consists of 6 dominoes, and has 36 pips in total.

The bottom square consists of 8 dominoes, uses 4 doubles ([1-1] [5-5] [4-4] [6-6]), and has 64 pips in total.

There is a further layout that also provides a solution:

[1-0] [0-5] [5-2] [2-1]
[2-0] [0-3] [3-3] [3-2]
[0-0] [0-4] [4-5] [5-3] [3-6] [6-0]
[3-1] [1-6] [6-2] [2-2] [2-4] [4-3]
[1-1] [1-4] [4-4] [4-6] [6-6] [6-5] [5-5] [5-1]

The first two loops are the same as the layout above.

And of course any loop in a solution can be reflected or rotated.

LikeLike

Brian Gladman 2:56 pm on 29 November 2024 Permalink | Reply

@Jim. Your optimisation in this code very is impressive. I have a structurally similar solution but it is painfully slow because it finds the same loops many thousands of times and I have not found a technique for preventing this. I can see that you have managed to do this but I am wondering what principle you have based this on?

LikeLike
- Jim Randell 3:08 pm on 29 November 2024 Permalink | Reply
  
  @Brian: Yes, this was a tricky one to program (even after determining the intended interpretation of the text).
  
  I used several “normal forms” to eliminate duplicate solutions:
  
  + for a domino (x, y) the normal form is when x ≤ y. (Otherwise we might also consider (y, x)).
  
  + for a loop, the normal form is to start with smallest domino (as above), and travel round the loop such that the second domino is less than the final domino. (There are at least 4 dominos in a loop, so these are all different). (Otherwise we could start at any domino, and go round the loop in either direction).
  
  + for a collection of loops of the same size, I require that they are ordered by the first domino. (Otherwise we might find the same loops in a different order).
  
  Together these bring the number of solutions down to two different collections of dominoes.
  
  LikeLiked by 1 person
  - Brian Gladman 5:15 pm on 29 November 2024 Permalink | Reply
    
    Thanks Jim, It looks like eliminating duplicate solutions is as much, if not more work, than finding solutions in the first place!
    
    LikeLike
Frits 11:53 am on 12 December 2024 Permalink | Reply
@Jim,

If you are only interested in the answer then you might split the cproduct for ss1 and ss2 to two separate loops and do some else/continue/break constructs. This will bring down the run time by a factor 3.

Also using a simpler normalise() is faster.
```
normalise = lambda d: d if d[0] <= d[1] else (d[1], d[0])
```
LikeLike

Frits 10:59 am on 12 December 2024 Permalink | Reply

This program runs in 35ms (not as fast as Brian’s recursive program).
A lot of work again.

from enigma import SubstitutedExpression

mx_dom = 6

# sorted tuple
stup = lambda s: tuple(sorted(s))
# generate circular pairs
circular = lambda s: set(stup([x, y]) for x, y in zip(s, s[1:] + s[:1]))

# including (x, y) and (y, x)
allcombs = lambda s: s | set((y, x) for x, y in s)
tri = lambda n: n * (n + 1) // 2

# decompose <t> into at least <mn> non-decreasing square piles
def decompose(t, mn=4, ns=[], fn=lambda x: x * x, ss = ()):
  unpack = lambda f: (lambda x: f(*x))
  if t == 0 and len(ss) >= mn:
    # also require that the two smallest values in <ss> are
    # equal and that there is only one largest value
    if ss[0] == ss[1] and ss[-1] > ss[-2]:
      yield ss
  else:
    for i, s in enumerate(ns):
      if t >= fn(s):
        yield from decompose(t - fn(s), mn, ns[i:], fn, ss + (s, ))

# run the SubstitutedExpression with specific expressions
def run(exprs, answer, d2i, syms, s2d=dict(), reorder=0, verbose=0):
  # eg for strip 'a-b-c-d-e-f-g-h-i-j' a must be different from c and i
  distinct = set(x + y if x < y else y + x for x, y in zip(syms, syms[2:] + syms[:2]))

  p = SubstitutedExpression(
      exprs,
      symbols=syms,
      answer=answer,
      d2i=d2i,
      distinct=distinct,
      env=dict(stup=stup, allcombs=allcombs),
      base=mx_dom + 1,
      s2d=s2d,
      digits=(range(mx_dom + 1)),
      reorder=reorder,
      verbose=verbose,  # use 256 to see the generated code
    )
  return tuple(p.answers())

# solve remaining strips after 3 strips are known
def solve(k, strips, pairs, ss=tuple()):
  if k == 0:
    yield ss
  else:
    s_size = strips[0]
    syms = allsyms[:s_size]
    vars = ','.join(syms)
    varlist = "[" + vars + "]"
    pairs4 = f"list(zip({varlist}, [{vars[2:]},{syms[0]}]))"
    s2d = dict()

    exprs = []

    # check if remaining strips all have the same size
    if len(set(strips)) == 1:
      # let strip begin with lowest remaining domino
      low = next(x for x in dominoes if x not in pairs)
      s2d[syms[0]], s2d[syms[1]] = low[0], low[1]
      first_domino_set = 1
    else:
      first_domino_set = 0
      # start with lowest number
      for i in range(1, s_size - 1):
        exprs.append(f"{syms[0]} <= {syms[i]}")

    # try to speed up the process
    #for i in range(2, 3):
    #  exprs.append(f"({syms[i - 1]}, {syms[i]}) not in {pairs}")

    # calculate last variable: sum(syms) * 2 = s_size^2
    exprs.append(f"{s_size**2 // 2} - sum([{vars[:-2]}]) = {syms[-1]}")

    if not first_domino_set:
      exprs.append(f"{syms[0]} <= {syms[-1]}")
    # ABCD <= ADCB
    exprs.append(f"{syms[1]} <= {syms[-1]}")

    # use different dominoes than already used
    exprs.append(f"allcombs(set(p4 := {pairs4})).isdisjoint({pairs})")

    # all dominoes must be unique
    exprs.append(f"len(set([stup([x, y]) for x, y in p4])) == {s_size}")

    # avoid rotations if list starts with a doublet
    exprs.append(f"{syms[0]} != {syms[1]} or "
                 f"{varlist} <= [{syms[1]},{syms[0]},{','.join(syms[2:][::-1])}]")

    answer = "tuple(" + varlist + ")"

    # limit variable values
    if first_domino_set:
      # other values in <syms> may not be smaller than first value
      # and for strip 'a-b-c-d-e-f-g-h-i-j' a must be different from c and i
      d2i = dict([(k, vars[2:]) for k in range(s2d[syms[0]])] +
                 [(s2d[syms[0]], syms[2] + syms[-2])])
      d2i[s2d[syms[1]]] = d2i.get(s2d[syms[1]], "") + syms[3] + syms[-1]
    else:
      # calculate highest possible starting domino
      ln = len(dominoes)
      mx = next(i for i in range(6, -1, -1)
                if ln - dominoes.index((i, i)) >= s_size)
      d2i = dict([(k, vars[0]) for k in range(mx + 1, mx_dom + 1)])

    # solve one strip
    for r in run(exprs, answer, d2i, syms, s2d, reorder=0, verbose=0):
      yield from solve(k - 1, strips[1:], pairs | circular(r), ss + (r, ))

allsyms = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

# the 28 dominoes
dominoes = tuple((i, j) for i in range(mx_dom + 1) for j in range(i, mx_dom + 1))
# the total number of spots
n_spots = sum(a + b for a, b in dominoes)
rt_spots = int(n_spots**.5)

mn_pile = 4 # at least 4 sides
# sum of spots of <n> largest dominoes must be >= n^2
mx_pile = next(i for i in range(rt_spots - rt_spots % 2 , 2, -2)
               if i * i <= sum(a + b for a, b in dominoes[-i:]))
sols = set()

# generate valid piles of strips
for pile in decompose(n_spots, mn_pile, range(mn_pile, mx_pile + 1, 2)):
  # ----------------------
  # get shortest strips
  # ----------------------
  min_strip = pile[0]
  syms = allsyms[:min_strip]
  vars = ','.join(syms)
  varlist = "[" + vars + "]"
  exprs = []
  pairs1 = f"[stup([x, y]) for x, y in zip({varlist}, [{vars[2:]},{syms[0]}])]"
  for i in range(1, min_strip - 1):
    exprs.append(f"{syms[0]} <= {syms[i]}")

  # calculate last variable: sum(syms) * 2 = min_strip^2
  exprs.append(f"{min_strip**2 // 2} - sum([{vars[:-2]}]) = {syms[-1]}")

  exprs.append(f"{syms[0]} <= {syms[-1]}")
  exprs.append(f"{syms[1]} <= {syms[-1]}")  # ABCD <= ADCB
  # strip should have 0 or 1 doublets
  exprs.append(f"len({{{vars}}}) >= {min_strip - 1}")

  # all dominoes must be unique
  exprs.append(f"len(set({pairs1})) = {min_strip}")

  answr = f"next((x for x, y in {pairs1} if x == y), -1), "
  answr += "tuple(" + varlist + ")"
  # calculate highest possible starting domino
  ln = len(dominoes)
  mx = next(i for i in range(6, -1, -1)
            if ln - dominoes.index((i, i)) >= min_strip)
  d2i = dict([(k, vars[0]) for k in range(mx + 1, 10)])
  # reverse sort on doublet
  answs = sorted(run(exprs, answr, d2i, syms, s2d=dict(),
                     reorder=0, verbose=0), reverse=True)

  mx_doublet = answs[0][0]
  # find strips with 1 doublet
  for ans1 in answs:
    if ans1[0] != mx_doublet or ans1[0] == -1: break
    pairs1 = circular(ans1[1])

    # find strips without a doublet
    for ans2 in answs:
      if ans2[0] != -1: continue
      # first 2 strips have to use different dominoes
      if len(pairs12 := pairs1 | circular(ans2[1])) != 2 * min_strip: continue

      # store potential answer
      sol = tuple((x, y) for x, y in zip(ans2[1], ans2[1][1:] + (ans2[1][0], )))
      if sol in sols: continue

      # get all possible pairs of both strips
      pairs12all = allcombs(pairs12)

      # ---------------------------------
      # find longest strip
      # ---------------------------------
      max_strip = pile[-1]
      syms = allsyms[:max_strip]
      mn_doublets = mx_dom // 2 + 1   # minimum number of doublets required

      exprs = []

      # all dominoes are doublets?
      if (all_doublets := (max_strip == 2 * mn_doublets)):
        # create <vars> like A,A,C,C,E,E,G,G
        vars = ','.join(x + "," + x for x in allsyms[:max_strip][::2])
        varlist = "[" + vars + "]"
        pairs3 = f"list(zip({varlist}, [{vars[2:]},{syms[0]}]))"
        for i in range(2, max_strip - 2, 2):
          exprs.append(f"{syms[0]} < {syms[i]}")

        # calculate last variable: sum(syms) * 2 = max_strip^2
        exprs.append(f"div({max_strip**2 // 2} - sum([{vars[:-4]}]), 2) = {syms[-2]}")
        exprs.append(f"{syms[0]} < {syms[-2]}")
      else:
        vars = ','.join(syms)
        varlist = "[" + vars + "]"
        pairs3 = f"list(zip({varlist}, [{vars[2:]},{syms[0]}]))"
        # start strip with the smallest doublet
        exprs.append(f"{syms[0]} = {syms[1]}")
        for i in range(2, max_strip - 1):
          exprs.append(f"{syms[i - 1]} != {syms[i]} or {syms[0]} < {syms[i]}")
          exprs.append(f"({syms[i - 1]}, {syms[i]}) not in {pairs12all}")

        # calculate last variable: sum(syms) * 2 = max_strip^2
        exprs.append(f"{max_strip**2 // 2} - sum([{vars[:-2]}]) = {syms[-1]}")
        exprs.append(f"{syms[0]} <= {syms[-1]}")
        exprs.append(f"{syms[1]} <= {syms[-1]}")    # ABCD <= ADCB
        exprs.append(f"({syms[-1]}, {syms[0]}) not in {pairs12all}")
        # more than half doublets
        exprs.append(f"len({{{vars}}}) <= {pile[-1] - mn_doublets}")

      # use different pairs
      exprs.append(f"allcombs(set(p3 := {pairs3})).isdisjoint({pairs12all})")
      # all dominoes must be unique
      exprs.append(f"len(set([stup([x, y]) for x, y in p3])) == {max_strip}")

      # avoid rotations if strip starts with a doublet
      if all_doublets:
        exprs.append(f"{varlist} <= [{vars[:3]},{vars[4:][::-1]}]")
      else:
        exprs.append(f"{syms[0]} != {syms[1]} or "
                     f"{varlist} <= [{syms[1]},{syms[0]},{','.join(syms[2:][::-1])}]")

      # eg. the four doublets (3, 3)...(6, 6) have too many spots
      max_smallest_doublet = next(i for i in range(max_strip - mn_doublets, -1, -1)
                                  if 4 * (i * mn_doublets + tri(mn_doublets - 1))
                                  <= max_strip**2)

      # limit first domino
      d2i = dict([(k, vars[0]) for k in range(max_smallest_doublet + 1, 10)])
      if all_doublets:
        # if (0, 0) is present then it has to be the first doublet
        d2i[0] = syms[::2][1:]
        d2i[ans1[0]] = syms # exclude the doublet used in shortest strip
      answr = f"tuple(" + varlist + ")"

      for ans3 in run(exprs, answr, d2i, syms, s2d=dict(), reorder=0, verbose=0):
        pairs123all = allcombs(pairs12 | circular(ans3))
        # solve remaining strips
        for s in solve(len(pile) - 3, pile[2:-1], pairs123all):
          sols.add(sol)
          break # as <sol> only depends on 2nd strip
        else: # no break
          continue
        break

for s in sols:
  print("answer:", s)

LikeLike

Jim Randell 10:18 am on 11 September 2024 Permalink | Reply
Tags: by: M R Carter ( 2 ), flawed
Brain-Teaser 734: Golden orchard
From The Sunday Times, 10th August 1975 [link]

A farmer grows apples in an orchard divided into plots —three to the East and three to the West of a central path. The apples are of two types — for eating (Cox, Laxton, Pearmain) and for cider making (Tremlitt, Coppin, Kingston).

Adjacent plots contain apples of different basic type. The apples are of six colours (red, green, russet, golden, orange, yellow) and of six tastes (sweet, sour, acid, tart, pleasant, bitter).

They ripen at different times, either early or late in July, August and September. Those ripening in early or late September are in plots directly opposite. Those South of Pearmain do not ripen in August. Tart are directly West of the acid variety, which ripens in early August. Yellow apples and those maturing in late September are adjacent. Yellow and orange are of the same type. Orange are North of pleasant and also North of Pearmain. Kingstons are adjacent to golden. Green is South of bitter.

Cox ripen in early July, and Laxtons ripen early in a different month. Tremlitts are red, and Kingstons mature after Coppins, which are not sour.

If cider apples taste unpleasant, what are the characteristics of the apples in North East plot? (Name, colour, taste, ripens).

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

I think the puzzle as published in The Sunday Times and in the book is open to interpretation, and my first attempt using a reasonable interpretation gave two solutions (neither of which are the published solution). After examining the given solution in the book I think the following wording is clearer:

A farmer grows apples in an orchard divided into plots — three to the East and three to the West of a central track. Adjacent plots are separated by a shared fence. The apples are of two basic types — for eating (Cox, Laxton, Pearmain) and for cider making (Tremlitt, Coppin, Kingston).

Neighbouring plots contain apples of different basic type. The apples are of six colours (red, green, russet, golden, orange, yellow) and of six tastes (sweet, sour, acid, tart, pleasant, bitter).

They ripen at different times, either early or late in July, August and September. Those ripening in early or late September are in plots directly opposite each other. Those directly South of Pearmain do not ripen in August. Tart are directly West of the acid variety, which ripens in early August. Yellow apples and those maturing in late September are in adjacent plots. Yellow and orange are of the same basic type. Orange are directly North of Permain, which are pleasant. Kingstons and golden are in adjacent plots. Green is directly South of bitter.

Cox ripen in early July, and Laxtons ripen early in a different month. Tremlitts are red, and Kingstons mature after Coppins, which are not sour.

If cider apples are neither pleasant nor sweet, what are the characteristics of the apples in North-East plot?

[teaser734]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 10:20 am on 11 September 2024 Permalink | Reply
  When I first tackled this puzzle (using the text from the 1981 book, and what I considered to be the most reasonable interpretation of the text), I found two solutions. And neither of them matched the published solution.
  
  According to the solution published in The Sunday Times [link] there were:
  
  A load of wrong answers (and some unacceptable multi-entries) in diffuse permutations brightly offset by an authentic minority including the winner …
  
  However, I think the wording of the puzzle is too vague to permit a single solution.
  
  Having looked at the answer in the book, I constructed the alternative wording, which I hope is clearer.
  
  Using the [[ SubstitutedExpression ]] solver from the enigma.py library, we can assign the characteristics to the plots.
  
  This run-file executes in 81ms. (Internal runtime of the generated code is 1.2ms).
```
#! python3 -m enigma -rr

SubstitutedExpression

# plots are:
#
#   1 || 2
#   --++--
#   3 || 4
#   --++--
#   5 || 6
#
# we need to assign each of the six characteristics from each group
# to a different plot number
#
# Eating: A = Cox; B = Laxton; C = Permain
# Cider: D = Tremlitt; E = Coppin; F = Kingston
#
# Colour: G = red; H = green; I = russet; J = golden; K = orange; L = yellow
#
# Taste: M = sweet; N = sour; P = acid; Q = tart; R = pleasant; S = bitter
#
# Season: T = early Jul; U = late Jul; V = early Aug; W = late Aug; X = early Sep; Y = late Sep

--base=7
--digits="1-6"

--distinct="ABCDEF,GHIJKL,MNPQRS,TUVWXY"

# row adjacency (W, E)
--code="row_adj = {(1, 2), (3, 4), (5, 6)}"

# col adjacency (N, S)
--code="col_adj = {(1, 3), (2, 4), (3, 5), (4, 6)}"

# adjacent plots contain apples of different types
"{A, B, C} in ({1, 4, 5}, {2, 3, 6})"

# those ripening in early/late September (X, Y) are opposite
"ordered(X, Y) in row_adj"

# Southerly neighbour of Permain (C) do not ripen in Aug (V, W)
"C not in {5, 6}"  # implies Permain (C) is not in southernmost row
"(C, V) not in col_adj"
"(C, W) not in col_adj"

# tart (Q) are directly West of acid (P)
"(Q, P) in row_adj"

# acid (P) ripens in early Aug (V)
"P = V"

# yellow apples (L) and those maturing in late Sep (Y) are adjacent
"ordered(L, Y) in col_adj"

# yellow (L) and orange (K) are of the same type
"len(intersect([{L, K}, {A, B, C}])) != 1"

# orange (K) are Northerly neighbours of pleasant (R), and also Northerly neighbours of Permain (C)
"(K, R) in col_adj"
"(K, C) in col_adj"

# Kingston (F) are adjacent to golden (J)
"ordered(F, J) in col_adj"

# green (H) is Southerly neighbour of bitter (S)
"(S, H) in col_adj"

# Cox (A) ripen in early Jul (T)
"A = T"

# Laxtons (B) ripen early in [not Jul] (V, X)
"B in {V, X}"

# Tremlitts (D) are red (G)
"D = G"

# Kingstons (F) mature after Coppins (E)
"[T, U, V, W, X, Y].index(F) > [T, U, V, W, X, Y].index(E)"

# Coppins (E) are not sour (N)
"E != N"

# cider apples do not taste pleasant (R) or sweet (M)
"R not in {D, E, F}"
"M not in {D, E, F}"

# make sure all the variables are filled out
"true(A, B, C, D, E, F, G, H, I, J, K, L, M, N, P, Q, R, S, T, U, V, W, X, Y)"

--template="(A B C D E F) (G H I J K L) (M N P Q R S) (T U V W X Y)"
--solution=""
--denest=-1
```
  And the following Python program can be used to make the output more friendly:
```
from enigma import (SubstitutedExpression, join, printf)

p = SubstitutedExpression.from_file("teaser734b.run")

# labels for the characteristics
label = dict(
  # Type:
  A="Cox", B="Laxton", C="Permain", D="Tremlitt", E="Coppin", F="Kingston",
  # Colour:
  G="red", H="green", I="russet", J="golden", K="orange", L="yellow",
  # Taste:
  M="sweet", N="sour", P="acid", Q="tart", R="pleasant", S="bitter",
  # Season:
  T="early Jul", U="late Jul", V="early Aug", W="late Aug", X="early Sep", Y="late Sep",
)

# solve the puzzle
for s in p.solve(verbose=0):
  # collect the characteristics for each plot
  d = dict((k, list()) for k in [1, 2, 3, 4, 5, 6])
  for k in sorted(s.keys()):
    d[s[k]].append(label.get(k))
  # output the solution
  for k in sorted(d.keys()):
    printf("{k} -> {v}", v=join(d[k], sep="; "))
  printf()
```
  Solution: The North-East plot contains Cox, russet in colour, sweet in taste, and ripens in early July.
  
  The full solution is:
  
  LikeLike

Jim Randell 12:52 am on 25 August 2024 Permalink | Reply
Tags: by: Victor Bryant ( 140 ), flawed

Teaser 3231: In his prime

From The Sunday Times, 25th August 2024 [link] [link]

Once, on my grandson’s birthday, I asked him the following five questions:

1. How many days are there in this month?
2. How many Mondays are there in this month?
3. How many “prime” days (i.e. 2nd, 3rd, 5th, …) are there in this month?
4. How many of those prime days are Saturdays?
5. How many letters are there when you spell the month?

The total of the five answers was a prime number.

Then I asked him the same questions the next day. No answer was the same as for the day before, but again the total of the five answers was prime.

When I first asked the questions what was the month and day of the week?

As set this puzzle has multiple solutions. However there is a unique answer for the birthday of the grandson (month and day of month).

[teaser3231]

Jim Randell 1:30 am on 25 August 2024 Permalink | Reply

Assuming the grandson answers each of the questions correctly, if the answer to each question must be different from that of the previous day, then the next day must be in a different month to the birthday.

This Python program works backwards, considering the answers for pairs of adjacent months, until it finds the most recent viable solution. (Assuming the system locale is set to find appropriate day and month names).

It runs in 68ms. (Internal runtime is 2.8ms).

Run: [ @replit ]

from datetime import (date, timedelta)
from enigma import (Record, repeat, inc, first, icount, primes, unpack, tuples, printf)

# increment of 1 day
day1 = timedelta(days=1)
# function to check the weekday of a date
weekday_is = lambda n: (lambda d, n=n: d.isoweekday() == n)

# answer the questions
def results(y, m):
  # days in the month
  ds = first(repeat(inc(day1), date(y, m, 1)), count=(lambda d, m=m: d.month == m))
  # 1. number of days in the month
  r1 = len(ds)
  # 2. number of Mondays
  r2 = icount(ds, weekday_is(1))
  # 3. number of prime days
  pds = list(d for d in ds if d.day in primes)
  r3 = len(pds)
  # 4. number of prime Saturdays
  r4 = icount(pds, weekday_is(6))
  # 5. number of letters in the month name
  r5 = len(ds[0].strftime('%B'))
  return (r1, r2, r3, r4, r5)

# generate result values going back in time
def generate(y, m):
  prev_month = unpack(lambda y, m: (y, m - 1) if m > 1 else (y - 1, 12))
  for (y, m) in repeat(prev_month, (y, m)):
    if y < 1753: break
    rs = results(y, m)
    t = sum(rs)
    yield Record(y=y, m=m, rs=rs, t=t, tprime=(t in primes))

# consider adjacent months for (next-day, birthday)
for (d1, d2) in tuples(generate(2024, 8), 2):
  # both totals are prime and no answers are the same
  if d1.tprime and d2.tprime and not any(x == y for (x, y) in zip(d1.rs, d2.rs)):
    # output solution
    nd = date(d1.y, d1.m, 1)
    bd = nd - day1
    printf("birthday = {bd} ({dow}) {d2.rs}; next day = {nd} {d1.rs}", dow=bd.strftime('%A'))
    break  # only need the most recent solution

Solution: The first time the questions were asked was on a Monday in February.

Actually on Monday, 29th February 2016.

The answers to the questions are: (29, 5, 10, 1, 8) giving a total of 53.

The next day is Tuesday, 1st March 2016.

And the answers to the questions are: (31, 4, 11, 2, 5) also giving a total of 53.

If we go further back the dates: Friday, 29th February 2008 and Saturday, 1st March 2008 also work.

And in fact all viable dates are Monday/Friday 29th February, and Tuesday/Saturday 1st March. So there are two possible answers to the puzzle.

The published solution is: “February, Monday or Friday (apologies for the multiple answers)”.

LikeLike

Jim Randell 10:27 am on 25 August 2024 Permalink | Reply

> [Frits suggests that solutions earlier than the most recent give the same answer]

@Frits: Are you sure?

LikeLike

Jim Randell 7:26 am on 26 August 2024 Permalink | Reply

I interpreted the condition “no answer was the same as for the day before” to mean that each answer given on the second day was different from the answer given to the same question on the previous day (and I think this is the most reasonable interpretation).

However, if we take this condition to mean that there were no values given as answers on the second day that had also been given as answers on the first day, then we do find a unique solution to the puzzle.

Here is my program adapted for this interpretation. (The condition at line 38 is changed).

from datetime import (date, timedelta)
from enigma import (Record, repeat, inc, first, icount, primes, unpack, tuples, intersect, printf)

# increment of 1 day
day1 = timedelta(days=1)
# function to check the weekday of a date
weekday_is = lambda n: (lambda d, n=n: d.isoweekday() == n)

# answer the questions
def results(y, m):
  # days in the month
  ds = first(repeat(inc(day1), date(y, m, 1)), count=(lambda d, m=m: d.month == m))
  # 1. number of days in the month
  r1 = len(ds)
  # 2. number of Mondays
  r2 = icount(ds, weekday_is(1))
  # 3. number of prime days
  pds = list(d for d in ds if d.day in primes)
  r3 = len(pds)
  # 4. number of prime Saturdays
  r4 = icount(pds, weekday_is(6))
  # 5. number of letters in the month name
  r5 = len(ds[0].strftime('%B'))
  return (r1, r2, r3, r4, r5)

# generate result values going back in time
def generate(y, m):
  prev_month = unpack(lambda y, m: (y, m - 1) if m > 1 else (y - 1, 12))
  for (y, m) in repeat(prev_month, (y, m)):
    if y < 1753: break
    rs = results(y, m)
    t = sum(rs)
    yield Record(y=y, m=m, rs=rs, t=t, tprime=(t in primes))

# consider adjacent months for (next-day, birthday)
for (d1, d2) in tuples(generate(2024, 8), 2):
  # both totals are prime and no answers are the same
  if d1.tprime and d2.tprime and not intersect([d1.rs, d2.rs]):
    # output solution
    nd = date(d1.y, d1.m, 1)
    bd = nd - day1
    printf("birthday = {bd} ({dow}) {d2.rs}; next day = {nd} {d1.rs}", dow=bd.strftime('%A'))

Note: Apparently this is not the interpretation intended by the setter. They just didn’t realise that there were multiple solutions to the puzzle.

LikeLike

Ruud 5:05 pm on 26 August 2024 Permalink | Reply

That’s an interesting interpretation that indeed leads to a unique solution.
In my code just change
if all(answer1 != answer2 for answer1, answer2 in zip(counts1, counts2)):
into
if set(counts1) & set(counts2) == set():
to get the unique result.

LikeLike

Frits 12:02 pm on 28 August 2024 Permalink | Reply

@Jim, please add a comment to explain the hardcoded 1753 value

LikeLike
- Jim Randell 12:09 pm on 28 August 2024 Permalink | Reply
  
  @Frits: See [ https://enigmaticcode.wordpress.com/2021/12/10/enigma-911-unlucky-for-some/#comment-11516 ]
  
  LikeLike

Ruud 1:13 pm on 25 August 2024 Permalink | Reply

It is obvious that the birthday must be at the end of a month to make the answer to the month name different. So we can just search by year/month. As the grandchild still has a living grandfather, I assume that the grandchild must be born after 1939. So I just check for all years between 1940 and 2024 and all months.

It turns out that there are 6 possible solutions in this timeframe. And the month is unique, but the day of the week is ambiguous (there are two possibilities).

import calendar


def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if not n & 1:
        return False

    for x in range(3, int(n**0.5) + 1, 2):
        if n % x == 0:
            return False
    return True


def counts(year, month):
    number_of_days = calendar.monthrange(year, month)[1]
    number_of_mondays = 0
    number_of_prime_days = 0
    number_of_prime_saturdays = 0
    weekday = calendar.weekday(year, month, 1)
    for day in range(1, number_of_days + 1):
        number_of_mondays += weekday == 0
        number_of_prime_days += is_prime(day)
        number_of_prime_saturdays += weekday == 5 and is_prime(day)
        weekday = (weekday + 1) % 7
    number_of_letters = len(calendar.month_name[month])
    return [number_of_days, number_of_mondays, number_of_prime_days, number_of_prime_saturdays, number_of_letters]


for year in range(2024, 1940, -1):
    for month in range(1, 13):
        counts1 = counts(year, month)
        if is_prime(sum(counts1)):
            next_month = (month % 12) + 1
            next_year = year + (month == 12)
            counts2 = counts(next_year, next_month)
            if is_prime(sum(counts2)):
                if all(answer1 != answer2 for answer1, answer2 in zip(counts1, counts2)):
                    day = calendar.monthrange(year, month)[1]
                    print(f"{calendar.month_name[month]:10} {calendar.day_name[calendar.weekday(year,month,day)]} ({year:4}-{month:02}-{day:02})")

LikeLike

Jim Randell 12:29 pm on 5 May 2024 Permalink | Reply
Tags: by: G H Dickson ( 13 ), flawed

Brain-Teaser 748: [Cutting corners]

From The Sunday Times, 16th November 1975 [link]

Young Bob had been given a carpentry set and with it a rectangular board (whose diagonal measured less than 1½ metres) on which to practise using his saw.

With straight cuts of successively greater length and aggregating to an exact number of metres, he first proceeded to saw dissimilar triangular pieces off each corner of the board in turn, the remaining quadrilateral piece being put aside for another day.

All the 12 sides of the sawn-off pieces measured exact and different numbers of centimetres.

What were the length and width of the board? (in cms).

As set this puzzle has multiple solutions, however if we interpret “less than 1½ meters” to mean “less than 150 cm, but more than 149 cm”, then we get a unique solution that is the same as that published in the newspaper.

This puzzle was originally published with no title.

[teaser748]

Jim Randell 12:30 pm on 5 May 2024 Permalink | Reply

Perhaps the puzzle originally said “just less than 1½ metres”, but the “just” got lost somewhere.

The following program assembles pairs of Pythagorean triangles point-to-point. This gives us candidate widths and heights for the board. We then find two pairs with the same width that fit together to make a rectangle as specified.

By “dissimilar” triangles I am assuming that no pair of triangles is mathematically similar (i.e. none of them are multiples of the same primitive Pythagorean triangle).

The program runs in 108ms. (Internal runtime is 40ms).

Run: [ @replit ]

from enigma import (
  defaultdict, pythagorean_triples, subsets, cproduct,
  seq_all_different, hypot, rev, ordered, ratio, cached, printf
)

# diagonal limit
D = 150

# possible triangles (x, y) -> z
tris = dict(((x, y), z) for (x, y, z) in pythagorean_triples(D - 1))

# primitive triangle
primitive = cached(lambda t: ratio(*t))

# assemble pairs of triangles: <combined-width> -> (<h1>, <h2>) -> (<w1>, <w2>)
pairs = defaultdict(lambda: defaultdict(set))
for (k1, k2) in subsets(tris.keys(), size=2):
  for ((w1, h1), (w2, h2)) in cproduct((k, rev(k)) for k in (k1, k2)):
    w = w1 + w2
    if w < D:
      (k, v) = ((h1, h2), (w1, w2)) if h1 < h2 else ((h2, h1), (w2, w1))
      pairs[w][k].add(v)

# choose a width and height for the initial rectangle
for (w, h) in subsets(pairs.keys(), size=2):
  z = hypot(w, h)
  if not (D - 1 < z < D): continue

  # choose a pair of triangles for the base
  for k1 in pairs[w]:
    (h1, h2) = k1
    # calculate the corresponding matched pair
    k2 = (h4, h3) = (h - h2, h - h1)
    if not (k2 > k1 and k2 in pairs[w]): continue
    for ((w1, w2), (w4, w3)) in cproduct(pairs[w][k] for k in (k1, k2)):
      # assemble the triangles
      (x1, y1, x2, y2, x3, y3, x4, y4) = (h1, w1, w2, h2, h4, w4, w3, h3)
      (z1, z2, z3, z4) = (tris[ordered(x, y)] for (x, y) in [(x1, y1), (x2, y2), (x3, y3), (x4, y4)])
      # sum of cuts is a multiple of 100
      T = z1 + z2 + z3 + z4
      if T % 100 != 0: continue
      # sides are all different
      ts = (t1, t2, t3, t4) = ((x1, y1, z1), (x2, y2, z2), (x3, y3, z3), (x4, y4, z4))
      if not seq_all_different(t1, t2, t3, t4): continue
      # triangle are dissimilar
      if not seq_all_different(primitive(ordered(*t)) for t in ts): continue
      # output solution
      printf("{w} x {h} -> {z:.2f}; {t1} {t2} {t3} {t4} T={T}")

Solution: The board was: 28 cm × 147 cm.

And here is how the triangles fit together:

If we just look for any diagonal that is less than 150cm (which is a direct interpretation of the published puzzle text), then we find the following 23 solutions (ordered by length of diagonal):

# Z = diagonal; T = total length of cuts
 28 × 147: Z=149.64 (12, 35, 37) (15, 112, 113) (16, 63, 65) (13, 84, 85) T=300
 51 × 140: Z=149.00 (15, 20, 25) (35, 120, 125) (36, 77, 85) (16, 63, 65) T=300
 87 × 120: Z=148.22 (7, 24, 25) (72, 96, 120) (80, 84, 116) (15, 36, 39) T=300
 48 × 140: Z=148.00 (15, 20, 25) (35, 120, 125) (33, 56, 65) (13, 84, 85) T=300
 60 × 135: Z=147.73 (9, 12, 15) (90, 48, 102) (126, 32, 130) (45, 28, 53) T=300
103 × 105: Z=147.09 (5, 12, 13) (60, 91, 109) (100, 75, 125) (45, 28, 53) T=300
 95 × 112: Z=146.86 (20, 21, 29) (60, 91, 109) (75, 100, 125) (35, 12, 37) T=300
 83 × 120: Z=145.91 (18, 24, 30) (28, 96, 100) (65, 72, 97) (55, 48, 73) T=300
100 × 105: Z=145.00 (9, 40, 41) (72, 65, 97) (91, 60, 109) (28, 45, 53) T=300
 90 × 112: Z=143.68 (20, 48, 52) (40, 42, 58) (92, 69, 115) (72, 21, 75) T=300
 60 × 129: Z=142.27 (3, 4, 5) (33, 56, 65) (126, 32, 130) (96, 28, 100) T=300
 69 × 124: Z=141.90 (9, 40, 41) (13, 84, 85) (60, 91, 109) (56, 33, 65) T=300
 85 × 111: Z=139.81 (5, 12, 13) (20, 99, 101) (80, 39, 89) (65, 72, 97) T=300
 93 × 104: Z=139.52 (20, 21, 29) (65, 72, 97) (84, 13, 85) (39, 80, 89) T=300
 92 × 104: Z=138.85 (5, 12, 13) (39, 80, 89) (99, 20, 101) (65, 72, 97) T=300
 59 × 124: Z=137.32 (7, 24, 25) (12, 35, 37) (117, 44, 125) (112, 15, 113) T=300
 76 × 114: Z=137.01 (15, 36, 39) (9, 40, 41) (99, 20, 101) (105, 56, 119) T=300
 80 × 111: Z=136.82 (5, 12, 13) (20, 99, 101) (75, 100, 125) (60, 11, 61) T=300
 84 × 108: Z=136.82 (3, 4, 5) (18, 80, 82) (105, 36, 111) (90, 48, 102) T=300
 95 ×  96: Z=135.06 (16, 63, 65) (60, 32, 68) (80, 18, 82) (36, 77, 85) T=300
 93 ×  95: Z=132.94 (11, 60, 61) (56, 33, 65) (84, 13, 85) (39, 80, 89) T=300
 67 ×  72: Z= 98.35 (9, 12, 15) (48, 55, 73) (63, 60, 87) (24, 7, 25) T=200
 56 ×  78: Z= 96.02 (8, 15, 17) (16, 63, 65) (48, 36, 60) (40, 42, 58) T=200

and we see the published solution is the first of these (longest diagonal).

LikeLike

Hugo 3:36 pm on 5 May 2024 Permalink | Reply

His saw cuts (each of which became the hypotenuse of a triangle) were progressively longer as he moved round the board to each corner in turn. Did you take that into account?

LikeLike
- Jim Randell 4:45 pm on 5 May 2024 Permalink | Reply
  
  I didn’t check that the cut lengths can form an increasing sequence (going clockwise or anticlockwise around the board), as I decided he could just make the four cuts in ascending order, however they are arranged.
  
  But if you do require this there are still 9 different solutions with diagonals <150 cm (including the published one).
  
  LikeLike
Hugo 7:43 am on 6 May 2024 Permalink | Reply

I think we can reduce it to a single solution if we add the words
“The board had the smallest possible area, consistent with what has been said.”

LikeLike

Jim Randell 4:39 pm on 16 February 2024 Permalink | Reply
Tags: by: Howard Williams ( 43 ), flawed
Teaser 3204: Pressing problem
From The Sunday Times, 18th February 2024 [link] [link]

The Mint’s machine can press circular coins from square plates of precious metal in straight rows with no gaps between coins. Currently, the coins are pressed with the same number of coins in each column and row, with their centres lying on the same vertical and horizontal straight lines.

As newly appointed Warden of the Mint, Newton set about reviewing its operational efficiency. He found that more rows can be squeezed into the same plate by shifting some rows so that each coin in it touches two coins in the row above; each of these rows will have one fewer coin in it. With this method, the best that can be done is to produce exactly 8 per cent more coins per plate.

How many more coins per plate can be produced in this way?

Note: The intention of this puzzle is that the size of the plate allows the rows and columns of the coins in the original (square-packed) configuration to fit exactly with no extra metal around the edges. Without this condition the puzzle has multiple solutions.

[teaser3204]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell, Pete Good, NigelR, and 1 other are discussing. Toggle Comments
- Jim Randell 4:59 pm on 16 February 2024 Permalink | Reply
  Note: See my comment below for a better program that solves the intended puzzle (and can also be used to find the multiple solutions for the original puzzle where the plate can have non-integer sizes).
  
  If the coins have diameter of 1, then in hexagonal packing the distance between the centres of alternate rows is (√3)/2.
  
  This Python program considers increasing sized squares until we achieve an 8% better yield from hexagonal packing vs. square packing.
  
  It runs in 56ms. (Internal runtime is 342µs).
  
  Run: [ @replit ]
```
from enigma import (irangef, inf, intf, divf, sqrt, printf)

r34 = sqrt(3, 4)

# pack the coins in a square of side <x>
# return (<number in square packing>, <number in hex packing>)
def pack(x):
  n = intf(x)  # number of rows in square packing
  ns = n * n
  h = divf(x - 1, r34) + 1  # number of rows in hex packing
  nh = n * h
  if x % 1 < 0.5: nh -= divf(h, 2)
  return (ns, nh)

# consider increasing sheet size
for x in irangef(1.0, inf, step=0.01):
  if not (x % 1 < 0.5): continue
  (ns, nh) = pack(x)
  # does hex packing give 8% more coins? (nh/ns = 1.08)
  if 100 * nh == 108 * ns:
    printf("{d} additional coins [x={x:.2f}: ns={ns} nh={nh}]", d=nh - ns)
    break
```
  Solution: [see my comment below]
  
  LikeLike
  - Frits 12:31 pm on 17 February 2024 Permalink | Reply
    
    @Jim, as must be a divisible by 25 I thought you would use a different step.
    
    The puzzle doesn’t ask for the first solution (you use “break”).
    I am always in favour of exploring the full solution space. I still have to figure out if we can use a break based on logic
    
    LikeLike
    - Jim Randell 12:55 pm on 17 February 2024 Permalink | Reply
      
      @Frits: You can remove the [[ break ]] to look for further solutions. But eventually you reach a point where the hexagonal packing is always better than an 8% improvement so you can stop then (without finding any further layouts – although there is a range of square sizes that give the required solution).
      
      LikeLike
- NigelR 9:35 am on 18 February 2024 Permalink | Reply
  
  It seems odd – bordering on bizarre – that, to make this teaser work in the way that most seem to be interpreting it, you have to assume that the original sheet is bigger than it needs to be by 0.33 of the coin diameter, or some 6.6%. By extension, and also noting that the puzzle is curiously worded: ‘… by shifting some rows…’ rather than: ‘…by shifting alternate rows..’, there are several solutions possible. For example, strictly consistent with the teaser as worded and using the same assumption, there is a valid solution for a much larger plate but leaving the first n rows unchanged. Only the last few rows are shifted, with a full row being added on the bottom. This yields the same required increase in coin number, but with the original sheet being oversized by a smaller percentage!
  
  LikeLike
  - Jim Randell 9:53 am on 18 February 2024 Permalink | Reply
    
    @NigelR: Would that be “best that can be done” with that size of square though?
    
    I supposed the size of square depends on the pressing machine rather than the coins, as it may be used to make coins of several different sizes. And presumably the unused metal is then recycled into new plates.
    
    LikeLike
    - NigelR 11:10 am on 18 February 2024 Permalink | Reply
      
      @Jim: Point taken – while my scheme would yield the right gain in coin number, it would not be optimal so is not a valid solution. I’m still troubled by the apparently arbitrary size of the original plate….!!
      
      LikeLike
- Frits 10:43 am on 18 February 2024 Permalink | Reply
  I followed the same method as Jim and Brian but am not convinced that this is a correct approach as the wording of the puzzle isn’t fully clear to me.
```
from fractions import Fraction as RF

# final number of coins = 27/25 * n^2 so n must be a multiple of 5
n = 5
while True:
 
  # final situation: m rows with m * n - m / 2 coins and m > n
  # (starting with a row of n coins followed by a row of n - 1 coins, etc)

  # we may have a solution if m * n - m / 2 equals 1.08 * n^2
  # or m = (54 * n^2) / (50 * n - 25)
  # or m = 1.08 * n + 27 / (100 * n - 50) + 0.54

  # assume diameter coin is 1
  # height of <m> packed rows: 1 + (m - 1) * sqrt(0.75)
  # squeeze as many rows as possible (sheet is less than (n + 1) x (n + 1):
  # n + 1 - sqrt(0.75) <= height of m rows < n + 1
 
  # n + 1 - sqrt(0.75) <= 1 + (m - 1) * sqrt(0.75) < n + 1
 
  # n <= m * sqrt(0.75)

  # as 1.08 * sqrt(0.75) < 1 every increment of 1 of n will result in
  # an increment of the height of less than 1
  # thus as soon for a certain <n> the height is less than <n> we can
  # stop processing

  # final number of rows
  m = RF(54 * n**2, 50 * n - 25)
  # whole number of rows?
  if m.denominator == 1:
    # if we can't squeeze in one more row
    if n + 1 - 3**.5 / 2 <= (h := 1 + (m - 1) * 3**.5 / 2) < n + 1:
      print(f"answer: {m * n - m // 2 - n**2} coins")
 
  # when can we stop processing?
  if not (2 * n <= m * 3**.5):
    break

  n += 5
```
  LikeLike
- Pete Good 5:40 pm on 19 February 2024 Permalink | Reply
  
  Jim,
  I solved this teaser analytically by deriving two quadratic equations for the number of coins pressed after Newton’s change. The first equation assumes that an even number of rows can be pressed and the second one assumes that an odd number of rows can be pressed. The first quadratic equation has a whole number solution and the second has none. The solution follows directly from this result.
  
  LikeLike
- Jim Randell 12:58 pm on 20 February 2024 Permalink | Reply
  
  It seems the way the setter intended the puzzle to work is that that square plate is an exact number of coin diameters across, and the alternate packing consists of some (but not necessarily every other) shifted, shorter rows.
  
  I have added a note to the puzzle text.
  
  LikeLike
  - Jim Randell 1:40 pm on 20 February 2024 Permalink | Reply
    Here is a Python program that solves the intended puzzle:
    
    Run: [ @replit ]
```
from enigma import (Accumulator, irange, irangef, inf, sqrt, intf, divf, printf)

r3 = sqrt(3)

# consider increasing sheet size
for x in irangef(1.0, inf, step=1.0):
  n = intf(x)
  ns = n * n  # square packing

  # find maximal packing for some shifted rows
  acc = Accumulator(fn=max)
  f = x % 1
  # max number of rows in hex packing
  m = divf(x - 1, 0.5 * r3) + 1
  # consider the number of shifted rows
  for s in irange(0, divf(m, 2)):
    # calculate the number of unshifted rows we can fit in
    u = s + intf(x - 1 - s * r3) + 1
    nh = u * n + s * (n - 1 if f < 0.5 else n)
    acc.accumulate_data(nh, (u, s))
  (nh, (u, s)) = (acc.value, acc.data)

  # can we fit in 8% more coins?
  if 100 * nh == 108 * ns:
    printf("{d} additional coins [x={x:.2f} u={u} s={s}: ns={ns} nh={nh}]", d=nh - ns)
    break
```
    Solution: 32 additional coins per plate can be produced.
    
    If the coins have diameter 1 and the plate measures 20 × 20, then the original square packing produces 400 coins per sheet.
    
    However, by shifting 8 of the rows, we have room for 2 more unshifted rows, for a total of 432 coins, and this is an 8% increase over the original packing.
    
    And this is the only solution if the size of the plate is constrained to be an exact multiple of the coin diameter.
    
    However if size of the plate is not so constrained there are 2 further solutions.
    
    If we change the step at line 6 to allow non-integer square sizes (and remove the break statement), we can find the three sizes of square that give us a possible solution. The smallest is that found by my original program, and the largest is an integer sized square that gives the intended answer.
    
    Here is a diagram of square packing and hexagonal packing with a 5.4 × 5.4 sheet:
    
    This is a full hexagonal packing, where every other row is shifted (and this was how I originally interpreted the puzzle, and was the solution found by my original program above).
    
    We get 25 coins/sheet using square packing and 27 coins/sheet using hexagonal packing, an 8% increase.
    
    The minimal size square that gives this configuration is: (5√3)/2 + 1 ≈ 5.3301…
    
    But for squares of size 5.5 or larger the alternate rows in the hexagonal packing do not have to be reduced by one coin (as specified by the puzzle text). So the square size must be in the range 5.33… < x < 5.50.
    
    And with a 10.47 × 10.47 square, the square packing gives 100 coins, but by shifting 2 rows we have room for an extra row:
    
    This alternate packing has 108 coins, which is also an 8% increase.
    
    LikeLike
Jim Randell 9:28 am on 7 September 2023 Permalink | Reply
Tags: by: Andrew Skidmore ( 85 ), flawed
Teaser 2645: One square
From The Sunday Times, 2nd June 2013 [link] [link]

I have consistently replaced digits by letters, using different letters for different digits, and in this way I have found that:

(FIVE − FOUR)² = ONE

Now, if I were to tell you whether or not THREE is divisible by 3, and whether or not FOUR is divisible by 4, then you could work out FIVE.

What number is FIVE?

Note: As originally published this puzzle has no solution (and was reproduced in this flawed form in the book The Sunday Times Brain Teasers Book 2 (2020)).

However the additional information that “FIVE is greater than FOUR” allows the published answer to be found.

[teaser2645]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell and Frits are discussing. Toggle Comments
- Jim Randell 9:29 am on 7 September 2023 Permalink | Reply
  With the extra condition that “FIVE is greater than FOUR” we find the published answer.
  
  So maybe the setter intended to say: “… I have found that FIVE − FOUR is a positive number, whose square is ONE” (or: “the square root of ONE is equal to FIVE – FOUR“).
  
  This Python program runs in 147ms.
  
  Run: [ @replit ]
```
from enigma import (SubstitutedExpression, group, unpack, item, peek, seq2str, printf)

# the alphametic problem (with an additional condition)
p = SubstitutedExpression(
  ["sq(FIVE - FOUR) = ONE", "FIVE > FOUR"],
  answer="(THREE, FOUR, FIVE)",
)

# collect the answers, and record values of FIVE (= item(2))
# by (THREE divisible by 3, FOUR divisible by 4).
fn = unpack(lambda n3, n4, n5: (int(n3 % 3 == 0), int(n4 % 4 == 0)))
d = group(p.answers(verbose=0), by=fn, f=item(2), fn=set)

# output the collections, and find the solution
for (k, vs) in d.items():
  if len(vs) == 1:
    printf("(d3, d4) = {k} -> FIVE = {v} [*** SOLUTION ***]", v=peek(vs))
  else:
    printf("(d3, d4) = {k} -> FIVE = {vs}", vs=seq2str(vs, sort=1, enc="{}"))
```
  Solution: FIVE = 5901.
  
  If we are told THREE is not divisible by 3, and FOUR is divisible by 4, then the only possible assignments are:
  
  FIVE = 5901, FOUR = 5872, ONE = 841, THREE = 36211
  FIVE = 5901, FOUR = 5872, ONE = 841, THREE = 63211
  
  Any of the other of the divisibility possibilities lead to multiple candidate values for FIVE, so this gives the answer.
  
  However if we do not require FIVE > FOUR, then we find many further possible solutions to the alphametic problem:
  
  FIVE = 1496, FOUR = 1520, ONE = 576, THREE = 38066
  FIVE = 1496, FOUR = 1520, ONE = 576, THREE = 83066
  
  FIVE = 3791, FOUR = 3820, ONE = 841, THREE = 56011
  FIVE = 3791, FOUR = 3820, ONE = 841, THREE = 65011
  
  FIVE = 5791, FOUR = 5820, ONE = 841, THREE = 36011
  FIVE = 5791, FOUR = 5820, ONE = 841, THREE = 63011
  
  FIVE = 6791, FOUR = 6820, ONE = 841, THREE = 35011
  FIVE = 6791, FOUR = 6820, ONE = 841, THREE = 53011
  
  FIVE = 8496, FOUR = 8520, ONE = 576, THREE = 13066
  FIVE = 8496, FOUR = 8520, ONE = 576, THREE = 31066
  
  And so we cannot work out the value of FIVE.
  
  We can see these candidates by removing the [[ "FIVE > FOUR" ]] on line 5 of the program.
  
  LikeLike
  - Frits 12:32 pm on 8 September 2023 Permalink | Reply
    The reported run time 147ms was probably with PyPy (I get 423ms with CPython).
    
    With this program CPython performs better than PyPY.
```
from enigma import (SubstitutedExpression, group, unpack, item, peek, seq2str, printf)

# invalid digit / symbol assignments
d2i = dict()
for d in range(0, 10):
  vs = set()
  if d == 0: vs.update('OFT')
  # if E is odd then R is even and if E is even then R is even as well
  if d % 2: vs.update('R')
  # a number that ends in 2, 3, 7 or 8 is not a perfect square
  if d in {2, 3, 7, 8}: vs.update('E')
  d2i[d] = vs
 
# the alphametic problem (with an additional condition)
p = SubstitutedExpression(
  [ # FIVE > FOUR
    "I > O", 
    "sq(IVE - OUR) = ONE",],
  answer="(FOUR, FIVE, THREE)",
  #answer="(FOUR, FIVE, \
  #         R + 2*E + sum(i for i in range(10) if i not in {F,I,V,E,O,U,R,N}))",
  d2i=d2i,
  verbose=0
)
 
# collect the answers, and record values of FIVE (= item(1))
# by (THREE divisible by 3, FOUR divisible by 4).
fn = unpack(lambda n4, n5, n3: (int(n3 % 3 == 0), int(n4 % 4 == 0)))
d = group(p.answers(), by=fn, f=item(1), fn=set)
 
# output the collections, and find the solution
for (k, vs) in d.items():
  if len(vs) == 1:
    printf("(d3, d4) = {k} -> FIVE = {v} [*** SOLUTION ***]", v=peek(vs))
  else:
    printf("(d3, d4) = {k} -> FIVE = {vs}", vs=seq2str(vs, sort=1, enc="{}"))   
```
    LikeLike
    - Jim Randell 12:13 pm on 9 September 2023 Permalink | Reply
      
      @Frits: Yes, 147ms was with PyPy 7.3.12. With CPython 3.12 I get an overall runtime of 255ms.
      
      Although, if you are solving the rescued problem you can use the expression [[ "is_square(ONE) + FOUR = FIVE" ]] which is a bit faster, and it is even faster to use [[ "is_square(ONE) + OUR = IVE" ]] (93ms with CPython 3.12).
      
      LikeLike
Jim Randell 4:29 pm on 18 August 2023 Permalink | Reply
Tags: by: Mark Valentine ( 17 ), flawed
Teaser 3178: Drying boards
From The Sunday Times, 20th August 2023 [link] [link]

Chef Ignacio liked to prop his two identical thin rectangular chopping boards against the shelf at the end of his counter to dry. He placed the top of the first one flush with the shelf corner and rested the second on the first, as shown in the diagram. To aid drying, he positioned the second to maximise the air volume in the bounded region below it. The length of each board is an even number of cm (less than 26cm). The distance between the bases of the two boards was a whole number of mm.

What is this distance?

It seems that the setter intends that the height of the shelf above the counter is an exact (but not specified) number of mm. Without this requirement we can find multiple potential solutions.

[teaser3178]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Frits and Jim Randell are discussing. Toggle Comments
- Jim Randell 5:30 pm on 18 August 2023 Permalink | Reply
  
  I am assuming the distance between the bases of the boards is the separation between the edges that touch the counter top.
  
  At the moment I don’t understand how we can work out a unique answer without knowing more information, say, the height of the shelf above the surface of the counter, or the angle of one of the boards.
  
  Solution: [See my comment below]
  
  LikeLike
  - Jim Randell 8:26 am on 19 August 2023 Permalink | Reply
    I have now found a single solution using the additional assumption that the height of the shelf above the counter is an exact whole number of millimetres. It seems it is likely this is what the setter intended.
    
    If the first board makes an angle θ with the surface (0° < θ < 90°), then the maximum cross-sectional area under the second board is achieved when it makes an angle θ/2 with the surface (and the bounded area is an isosceles triangle).
    
    With the length of the board and the height of the shelf we can calculate the angle θ, and hence θ/2. Then cos(θ/2) is the ratio of half the board length to the required separation.
    
    I used the half-angle formula:
    
    $\cos \left( \frac{\theta}{2} \right)\; =\; \sqrt{\frac{1\; +\; \cos \left( \theta \right)}{2}}$
    
    This Python program runs in 56ms. (Internal runtime is 1.7ms).
    
    Run: [ @replit ]
```
from enigma import (Rational, irange, is_square_q, div, as_int, printf)

Q = Rational()

# solve for a board of length x (mm)
for x in irange(20, 240, step=20):

  # and a shelf of height h (mm)
  for h in irange(1, x - 1):

    # separation between the boards on the counter = y (mm)
    d = is_square_q(x * x - h * h)
    if d is None: continue
    q = is_square_q(Q(d + x, 2 * x))
    if q is None: continue
    y = Q(x, 2 * q)
    # check for integer value
    y = as_int(y, include="+", default=None)
    if y is None: continue

    # output solution
    printf("x={x} h={h} -> y={y}")
```
    Solution: The boards are 125 mm apart.
    
    The boards are 200 mm in length (x = 200), and the shelf is height 192 mm above the counter top (h = 192).
    
    So the first board makes a (56, 192, 200) = 8× (7, 24, 25) right-angled triangle.
    
    And we have:
    
    cos(θ) = 7/25
    ⇒
    θ ≈ 73.74°
    
    And we calculate cos(θ/2) as:
    
    cos(θ/2) = √((1 + cos(θ))/2)
    = √((1 + 7/25)/2)
    = √(16/25)
    = 4/5
    ⇒
    θ/2 ≈ 36.87°
    
    And the required separation is:
    
    y = (x/2) / cos(θ/2)
    y = 100 / (4/5)
    y = 125
    
    If the height of the shelf h is unconstrained, then we can find an appropriate value to give any (reasonable) answer we choose.
    
    For a board of length x and a required separation distance y, we calculate the angle of θ (between 0° and 90°) as:
    
    cos(θ/2) = x/2y
    
    Then the required height h for this scenario is given by:
    
    h = x sin(θ)
    
    For example:
    
    x = 240, y = 140
    ⇒
    cos(θ/2) = 6/7
    θ ≈ 62.01°
    h ≈ 211.92 mm
    
    LikeLike
    - Frits 12:29 pm on 19 August 2023 Permalink | Reply
      I had to make two assumptions, not one, to get to the same answer.
      
      Luckily my initial derived rule for maximal air volume remains true.
      
      from enigma import Rational Q = Rational() M = 26 # length of each board in cm is smaller than M # air volume in the bounded region is maximal if line perpendicular to # the 2nd board splits the 2nd board in half (isoceles triangle) # board length in mm for b in range(20, 10 * M, 20): # assume shelf height is a whole number of mm for h in range(1, b): # assume the distance from corner to 1st board touching # the counter <a> is a whole number of mm a = (b**2 - h**2)**(1/2) if not (a == (a := int(a))): continue # using cosine half-angle formula the following must be true d2 = Q(b**2 + a * b, 2 + 4 * Q(a, b) + Q(2 * a**2, b**2)) if d2.denominator != 1: continue # distance <d> must be a whole number of mm if (d := d2.numerator**(1/2)) != int(d): continue print("answer:", int(d), "mm")
      
      LikeLike
      - Frits 10:12 pm on 19 August 2023 Permalink | Reply
        
        line 17 is not really necessary.
        
        LikeLike
    - Jim Randell 1:04 pm on 19 August 2023 Permalink | Reply
      For a shorter/faster program we can use [[ pythagorean_triples() ]] from the enigma.py library (and a bit of analysis).
      
      This Python program has an internal runtime of 316µs.
      
      Run: [ @replit ]
      
      from enigma import (pythagorean_triples, div, is_square, printf) # generate pythagorean triples for the first board (in mm) for (a, b, x) in pythagorean_triples(240): if x % 20 != 0: continue for (d, h) in [(a, b), (b, a)]: # calculate the separation of the boards (in mm) y = is_square(div(x**3, 2 * (d + x))) if y is None: continue # output solution (in mm) printf("x={x} h={h} -> y={y}")
      
      Analysis:
      
      Using the identity:
      
      2 cos²(θ/2) = 1 + cos(θ)
      
      we have:
      
      cos(θ/2) = x / 2y
      cos(θ) = d / x
      
      hence:
      
      x²/2y² = 1 + d/x
      ⇒
      y² = x³ / 2(d + x)
      
      And x and y are integers, hence d is also an integer, so (d, h, x) is a Pythagorean triple.
      
      LikeLiked by 1 person
Jim Randell 4:29 pm on 26 May 2023 Permalink | Reply
Tags: by: Peter Good ( 27 ), flawed
Teaser 3166: All their marbles
From The Sunday Times, 28th May 2023 [link] [link]

In their art class, Jack and Jill each had a box of spherical glass marbles. Each box contained marbles of at least three different sizes, and the radius of every marble was a whole number of cm.

Jack placed three marbles of equal size from his box onto a desk, and placed each of the other [sizes] in turn on top so that all four marbles touched each other and formed a triangular pyramid. He worked out the height of each pyramid (from desk to top of top marble) and obtained a different whole number of cm each time.

Jill was also able to do this with her marbles but they were all of different sizes to Jack’s.

None of the pyramids was higher than 30cm.

List all of the different marble radii in ascending order.

[teaser3166]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell and Frits are discussing. Toggle Comments
- Jim Randell 5:53 pm on 26 May 2023 Permalink | Reply
  Presumably “at least three” is “exactly three”, otherwise there would be multiple solutions.
  
  But I think this puzzle is flawed. We don’t find 2 possible sets of marbles that satisfy the specified conditions of the puzzle. Although by increasing the maximum allowable pyramid height we can find a solution to the puzzle as worded. But these involve quite sizeable marbles (using mm instead of cm would make the puzzle more reasonable).
  
  By calculating the height h of the the (not regular) tetrahedron formed by the centres of the spheres we can determine the height of a pyramidal configuration of spheres, and reject non-viable configurations. And we can then look for disjoint sets of three spheres (a base size and two viable top sizes) for Jack and Jill that give valid configurations.
  
  Run: [ @replit ]
```
from enigma import (
  irange, subsets, sq, is_square, group, item, delete,
  cproduct, disjoint_union, arg, printf
)

MAX_H = arg(30, 0, int)  # max pyramid height
MAX_R = (MAX_H - 1) // 2  # max sphere radius

# calculate integer height of a pyramid configuration
# with base spheres radius <R> and top sphere radius <r>
def height(R, r):
  if R % 3 != 0: return
  # vertical height between centres of spheres = h
  h = is_square(sq(r) + 2 * R * r - sq(R) // 3)
  if h is None: return
  H = h + R + r
  # check it is a valid pyramid
  if not (H > 2 * R): return
  return H

# generate possible base/top radii
def generate():
  # consider possible radii
  for (R, r) in subsets(irange(1, MAX_R), size=2, select="P"):
    # calculate height of the pyramid = H
    H = height(R, r)
    # check it forms a pyramid with H not exceeding MAX_H
    if H is None or H > MAX_H: continue
    printf("[R={R} r={r} -> H={H}]")
    yield (R, r)

# group top radii by base radius
g = group(generate(), by=item(0), f=item(1))
# discard sets with fewer than 3 different sizes
g = delete(g, (k for (k, vs) in g.items() if len(vs) < 2))

# look for 2 disjoint sets of 3 radii
for ((k1, vs1), (k2, vs2)) in subsets(g.items(), size=2):
  for (ts1, ts2) in cproduct(subsets(vs, size=2) for vs in (vs1, vs2)):
    ss = disjoint_union([ts1, ts2, [k1, k2]])
    if ss is None: continue
    # output solution
    printf("radii = {ss} [base = {k1} + tops = {ts1}; base = {k2} + tops = {ts2}]", ss=sorted(ss))
```
  My interpretation of the puzzle text is that in order for the marbles to form a structure that could be described as a triangular pyramid, the uppermost point of the top marble in the arrangement must project above the uppermost points of the three marbles forming the base. So that three planar triangles, each supported by two of the base marbles and the top marble, would form the inclined faces of a triangular based pyramid that exactly encloses the marbles.
  
  However, with this interpretation, there is no solution to the puzzle with the restrictions given.
  
  If we increase the maximum allowed height of the arrangements (to between 72 and 95), we can find a unique solution using valid pyramids:
  
  set 1 = (7, 12, 14) [base = 12, top = 7 → height = 32; base = 12, top = 14 → height 48]
  set 2 = (13, 18, 21) [base = 18, top = 13 → height 54; base = 18, top = 21 → height 72]
  
  And this gives an answer of: (7, 12, 13, 14, 18, 21).
  
  The marbles are quite large though, so perhaps this would work better if the radii were specified in millimetres instead of centimetres.
  
  Another way to find a solution is to abandon the requirement for a “triangular pyramid” arrangement, and just place the three base marbles on the desk, touching each other in a triangular arrangement, and then place the fourth marble on top of these. And we measure the elevation of the uppermost point of the top marble above the desk. (We don’t care if this is below the level of the uppermost points of the base marbles, or at the same level).
  
  And using such arrangements we can get a unique solution within the height restriction given in the puzzle text:
  
  set 1 = (1, 6, 7) [base = 6, top = 1 → height 8; base = 6, top = 7 → height 24]
  set 2 = (2, 4, 12) [base = 12, top =2 → height 16; base = 12, top 4 → height 24]
  
  Which gives an answer of: (1, 2, 4, 6, 7, 12).
  
  And it seems likely this is the intended solution.
  
  The published solution is: “1, 2, 4, 6, 7 and 12 cm”.
  
  LikeLike
  - Frits 9:52 pm on 26 May 2023 Permalink | Reply
    
    @Jim, using r = R in your height formula I don’t recognize the published height of a tetrahedron with 2 layers (2r(1 + sqrt(2/3)).
    
    No idea yet how to find the formula myself.
    
    LikeLike
    - Jim Randell 10:01 pm on 26 May 2023 Permalink | Reply
      
      That is exactly what you get from my formula when R = r:
      
      H = 2r + √(r² +2r² − r²/3)
      H = 2r + √(8r²/3)
      H = 2r + 2r√(2/3)
      H = 2r(1 + √(2/3))
      
      The formula itself comes from a bit of trigonometry on a triangle whose hypotenuse connects the centres of the top sphere and one of the base spheres.
      
      LikeLike
      - Frits 10:38 pm on 26 May 2023 Permalink | Reply
        
        OK, I thought “h” was the height of the pyramid.
        
        LikeLike
      - Frits 11:01 pm on 26 May 2023 Permalink | Reply
        
        I verified your formula (using the formula for the distance between the centre of an equilateral triangle and any of its vertices)
        
        LikeLike
  - Jim Randell 10:59 pm on 27 May 2023 Permalink | Reply
    
    If we ignore all the stuff about making “pyramids”, and just arrange 3 marbles of the same size in a triangular arrangement on the desk, with each marble touching the other two, and then place a different size fourth marble on top of these three marbles in the hollow between the lower three marbles. We can then measure the distance between the surface of the desk and the top of the fourth marble. And it is this distance we require to be an integer.
    
    With this wording the puzzle does have a unique solution, with distances not exceeding 30cm, and it is quite possible these are the sets the setter was intending us to find.
    
    My program (above) can be adapted for this scenario by removing the validity check at line 18.
    
    I’ve also uploaded a more generic program that allows you to experiment with various criteria for valid configurations. [@replit]
    
    LikeLike

Jim Randell 4:34 pm on 14 April 2023 Permalink | Reply
Tags: by: Edmund Marshall ( 10 ), flawed

Teaser 3160: Hymn number anagrams

From The Sunday Times, 16th April 2023 [link] [link]

At Church on Sunday, the hymn board showed just four different hymn numbers, each having the same three, different, non-zero digits, but in a different order. I noticed that the first hymn number was a perfect square, and that there was at least one other perfect square, formed from the same three digits, which did not appear on the board. The sum of the four hymn numbers was a prime number. If I told you the first digit of that prime number, you would be able to tell me the first hymn number on the board.

What was the first hymn number on the board?

[teaser3160]

Jim Randell 5:02 pm on 14 April 2023 Permalink | Reply
As worded there are multiple answers to this puzzle.

However we can get a unique answer if we are told the last digit of the prime sum (not the first digit).

This Python program runs in 64ms. (Internal runtime is 503µs).

Run: [ @replit ]
```
from enigma import (
  irange, sq, nsplit, ordered, group, item, subsets,
  nconcat, is_prime, filter_unique, unpack, printf
)

# generate possible 3-digit squares, and their digits (ordered)
def squares():
  # consider 3-digit squares
  for i in irange(10, 31):
    n = sq(i)
    # there should be 3 different non-zero digits
    ds = nsplit(n, fn=set)
    if len(ds) != 3 or 0 in ds: continue
    # return (<square>, <digits>)
    yield (n, ordered(*ds))

# generate candidate solutions
def generate():
  # group possible squares by their digits
  g = group(squares(), by=item(1), f=item(0), fn=set)

  # choose a set of digits with (at least) 2 squares
  for (ds, sqs) in g.items():
    if len(sqs) < 2: continue
    # construct all rearrangements of the digits
    rs = list(nconcat(ss) for ss in subsets(ds, size=len, select='P'))
    # choose 4 of the candidates
    for ns in subsets(rs, size=4):
      # at least one square must be unused
      if sqs.issubset(ns): continue
      # at least one square must be present
      fs = sqs.intersection(ns)
      if not fs: continue
      # the sum should be a prime
      t = sum(ns)
      if not is_prime(t): continue
      # yield solutions (<first>, <sum>, <all>)
      for n in fs:
        printf("[first={n} hymns={ns} sum={t}; unused={xs}]", xs=sorted(sqs.difference(ns)))
        yield (n, t, ns)

# if we knew the first digit of the total, we could deduce the number of the first hymn
f = unpack(lambda n, t, ns: nsplit(t)[0])  # first digit of total
g = unpack(lambda n, t, ns: n)  # first hymn number
ss = filter_unique(generate(), f, g).unique

# output solution
for (n, t, ns) in ss:
  printf("prime = {t} -> hymns = {ns}, first = {n}")
```
Solution: There are two possibilities: 256 and 961.

There are only two sets of 3 distinct digits that can form multiple squares:

{1, 6, 9} → 169 (=13²), 196 (= 14²), 961 (= 31²)
{2, 5, 6} → 256 (=16²), 625 (= 25²)

And these lead to the 5 possible arrangements of hymns that fit the requirements:

first = 256; rest = 265, 526, 562; sum = 1609; unused square = 625
first = 256; rest = 265, 526, 652; sum = 1699; unused square = 625
first = 961; rest = 196, 619, 691; sum = 2467; unused square = 169
first = 196; rest = 619, 691, 961; sum = 2467; unused square = 169
first = 961; rest = 619, 691, 916; sum = 3187; unused square = 169, 196

If we are told the first digit of the sum is 1, then we see the first hymn must be 256. (We can also determine that two of the three other hymns are 265 and 526, but without more information we can’t determine if the remaining hymn is 562 or 652).

And if we are told the first digit of the sum is 3, then we see the first hymn must be 961. (In this case we can determine that the other three hymn are 619, 691 and 916).

These are the two possible answers.

It is possible we are meant to read “if I told you the first digit [of the sum], you would be able to tell me the first hymn number on the board” to mean that although we can deduce the first hymn number on the board, we cannot deduce with certainty all of the other three numbers. And this removes one of the viable answers, leaving a unique solution to the puzzle.

But I think if this was the intended interpretation, the puzzle text should have been worded more clearly.

LikeLike
- Jim Randell 7:49 am on 23 April 2023 Permalink | Reply
  
  The solution published in today’s issue of The Sunday Times is: 961.
  
  LikeLike

Frits 7:19 pm on 14 April 2023 Permalink | Reply

from enigma import SubstitutedExpression, is_square_p, is_prime
from itertools import combinations as comb

# return number of perfect squares in a sequence of numbers
def n_squares(seq):
  return sum(is_square_p(x) for x in seq)

# the alphametic puzzle
p = SubstitutedExpression(
  [
    # first item ABC must be a perfect square
    "n_squares([ABC])",
    # there was at least one other perfect square
    "n_squares(r5 := [ACB, BAC, BCA, CAB, CBA])",
    
    # the sum of the four hymn numbers is a prime number
    # (choose c for the 2 numbers not displayed on the board)
    "len(primes := [p for c in comb(r5, 2) if n_squares(c) \
         if is_prime(p := (ABC + sum(x for x in r5 if x not in c)))]) > 0",
  ],
  answer="ABC, primes",
  env=dict(n_squares=n_squares, comb=comb),
  digits=range(1, 10),
  reorder=0,    # advisable when using assignment statements
  verbose=0,    # use 256 to see the generated code
)

d = dict()
# process answers
for (_, ans) in p.solve():
  # store first hymn number for first digit of prime number
  for p in ans[1]:
    d[str(p)[0]] = d.get(str(p)[0], set()) | {ans[0]}

print("answers:", [vs.pop() for k, vs in d.items() if len(vs) == 1])

LikeLike

Jim Randell 10:22 pm on 14 April 2023 Permalink | Reply

@Frits: That’s a clever use of assignment expressions. I hadn’t thought about how they could be useful in [[ SubstitutedExpression ]] recipes. Although, as you say, you need [[ reorder=0 ]].

LikeLike

GeoffR 5:04 pm on 16 April 2023 Permalink | Reply

I also found two solutions with different digits of the first hymn number.
The method of solution is described at the start of the program.

# Method
# I noticed that the first hymn number was a perfect square,
# and that there was at least one other perfect square,
# formed from the same three digits, which did not appear on the board.
# ... so 1 or 2 squares not on the hymn board and 1 square on the board.

from math import isqrt
from collections import defaultdict
from itertools import product, combinations
from enigma import is_prime, all_different

HYMNS = defaultdict(list)
# Dictionary key is sum of first four numbers (a prime)
# Dictionary value is a tuple of the six 3-digit numbers

def is_sq(n):
  return (isqrt(n) ** 2 == n)
    
def sq_count (n1, n2, n3, n4, n5, n6):
  try:
    cnt = 0
    for c in [n1, n2, n3, n4, n5, n6]:
      if is_sq(c):
        cnt += 1
      # 2 or 3 squares in 6 numbers
      if cnt == 2 or cnt == 3:
        return cnt
  except:
    print("Error in counting squares")
    return

# Assumed 2 or 3 squares in the 6 no. 3-digit numbers 
for sq_cnt in range(2, 4):
  for c1, c2, c3 in product(range(1, 10), repeat=3):
    if all_different(c1, c2, c3):
      # find 6 no. 3-digit numbers
      ABC, DEF = 100*c1 + 10*c2 + c3, 100*c1 + 10*c3 + c2
      GHI, JKL = 100*c2 + 10*c1 + c3, 100*c2 + 10*c3 + c1
      MNO, PQR = 100*c3 + 10*c1 + c2, 100*c3 + 10*c2 + c1
      # count number of squares in these 6 numbers
      sq_cnt = sq_count(ABC,DEF,GHI,JKL,MNO,PQR)
      
      # The number of squares in the 6 numbers is either 2 or 3
      # check for 2 squares in 6 numbers        
      if sq_cnt == 2:
        # the first 4 hymn nos. contain 1 square only (i.e. 1st)
        # .. and the last 2  numbers 1 square only
        for p1 in combinations((ABC, DEF,GHI,JKL,MNO,PQR), 6):
          if is_sq(ABC):
            # 4 hymn numbers are ABC, DEF, GHI, JKL
            if all(not is_sq(x) for x in (DEF,GHI,JKL)):
              if is_prime(ABC + DEF + GHI + JKL):
                  HYMNS[ABC+DEF+GHI+JKL] += [(ABC,DEF,GHI,JKL,MNO,PQR)]
                
      # check for 3 squares in 6 numbers        
      if sq_cnt == 3:
        for p1 in combinations((ABC,DEF,GHI,JKL,MNO,PQR), 6):
          # squares are 1st, 5th and 6th 3-digit numbers
          #... as first 4 numbers assumed 1 square only(i.e 1st)
          if is_sq(ABC) and is_sq(MNO) and is_sq(PQR):
            if is_prime(ABC + DEF + GHI + JKL):
              HYMNS[ABC+DEF+GHI+JKL] += [(ABC,DEF,GHI,JKL,MNO,PQR)]

# Find the four numbers on the hymn board                   
for k, v in HYMNS.items():
    print(f"The first hymn number on the board was {v[0][0]}.")
    print(f"HYMN NUMBERS: {v[0][0]}, {v[0][1]}, {v[0][2]}, {v[0][3]}.")
    print()

LikeLike

GeoffR 7:17 pm on 17 April 2023 Permalink | Reply

Much shorter code in MiniZinc ,with same two possible answers.

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

var 1..9:a; var 1..9:b; var 1..9:c; 
constraint all_different([a, b, c]);
 
predicate is_sq(var int: y) =
exists(z in 1..ceil(sqrt(int2float(ub(y))))) (z*z = y );

predicate is_prime(var int: x) = 
x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) 
((i < x) -> (x mod i > 0));
  
% ABC, DEF, GHI and JKL are Hymn Board numbers - ABC is 1st number
var 100..999:ABC = 100*a + 10*b + c;
var 100..999:DEF = 100*a + 10*c + b;
var 100..999:GHI = 100*b + 10*a + c;
var 100..999:JKL = 100*b + 10*c + a;
% MNO and PQR are possible squares off the Hymn Board
var 100..999:MNO = 100*c + 10*a + b;
var 100..999:PQR = 100*c + 10*b + a;

constraint is_sq(ABC); % 1st number on Hymn Board is a square
% One or both numbers off the Hymn Board are squares
constraint (is_sq(MNO) \/ is_sq(PQR)) \/ (is_sq(MNO) /\ is_sq(PQR));
constraint not is_sq(DEF) /\ not is_sq(GHI) /\ not is_sq(JKL);

% The sum of the numbers on the Hymn Board is a prime
constraint is_prime(ABC + DEF + GHI + JKL);

solve satisfy;
% Four Hymn numbers are ABC, DEF,GHI and JKL
output [  "[ABC, DEF, GHI, JKL, MNO, PQR] =" 
++ show( [ABC, DEF, GHI, JKL, MNO, PQR]  )];

LikeLike

Jim Randell 10:12 am on 9 April 2023 Permalink | Reply
Tags: by: Christopher Higgins ( 7 ), by: Hugh Bradley ( 7 ), flawed
Teaser 2161: Love hearts
From The Sunday Times, 15th February 2004 [link]

Bobby has made a Valentine’s card for his girlfriend Chin-We. He drew some increasing rows of touching circles, like those shown, but with more rows. Then he put a red heart in as many circles as possible without three of their centres forming an equilateral triangle. Then he put a pink heart in some of the remaining circles, and a white heart in the rest.

When Bobby counted the number of hearts of red, of pink and of white, he got three totals which (not necessarily in that order) formed three consecutive numbers.

How many red hearts are on the card?

Although the puzzle can be solved, the published solution was incorrect, and there are in fact two possible correct answers.

[teaser2161]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Frits and Jim Randell are discussing. Toggle Comments
- Jim Randell 10:13 am on 9 April 2023 Permalink | Reply
  I recently revisited Enigma 82 and Enigma 144 and this puzzle can also be solved using similar techniques.
  
  The number of cells for an arrangement with n rows is obviously tri(n).
  
  And if the number of red, pink and white hearts are {k − 1, k, k + 1} (in some order), then we can only find a solution when:
  
  tri(n) = 3k
  
  And so we can skip cases where tri(n) is not divisible by 3, i.e. n = 4, 7, 10, 13, …
  
  Once we calculate the possible configurations that give equilateral triangles we can determine a minimum hitting set for these configurations, and all the remaining cells can then be coloured red without giving a configuration that has three reds forming an equilateral triangle, and this is the maximum possible number of reds.
  
  If this number in in the set {k − 1, k, k + 1} then we have a viable solution, and the cells that form the hitting set can be divided into an appropriate number of pink and white cells.
  
  This Python program uses the MiniZinc implementation of the minimum hitting set problem and can be used to examine the puzzle for various values of n. The first solution presents itself at n = 11, which the program solves in 3m35s (using the “scip” solver).
```
from enigma import (irange, subsets, div, empty, arg, printf)
from utils_mzn import hitting_set

# distance metric (cosine rule)
# returns the square of the distance
def dist(p, q):
  ((px, py), (qx, qy)) = (p, q)
  (a, b) = (abs(px - qx), abs(py - qy))
  c = (1 if (px < qx) != (py < qy) else -1)
  return a * a + b * b - a * b * c

# specify number of rows
N = arg(9, 0, int)

# enumerate the cells
n = N - 1
vs = set((a, b) for a in irange(0, n) for b in irange(0, n - a))

# find the set of equilateral triangles
tris = set()
for (a, b, c) in subsets(vs, size=3):
  # is the triangle equilateral
  if dist(a, b) == dist(b, c) == dist(a, c):
    tris.add((a, b, c))

T = len(vs)
t = len(tris)
x = div(T, 3)
ss = ({x - 1, x, x + 1} if x is not None else empty)
printf("[N={N} -> {T} cells, {t} equilateral triangles, sequence = {ss}]", ss=sorted(ss))

# find a minimum hitting set for the equilateral triangles
hs = hitting_set(tris, solver="minizinc --solver scip")
printf("minimum hitting set size = {n}", n=len(hs))

r = T - len(hs)  # max number of red hearts
printf("maximum red hearts = {r}")
printf("*** {x}SOLUTION ***", x=('' if r in ss else 'NOT A '))
```
  Solution: The smallest solution has 22 red hearts (with 11 rows of circles), but 25 red hearts is also possible (with 12 rows of circles).
```
t = tris; r = reds
 n     t    seq        r  [scip  ] [highs ]
 2     1    0,1,2      2           [ 188ms] [SOLUTION]
 3     5    1,2,3      4           [ 194ms]
 4    15    -          6           [ 188ms]
 5    35    4,5,6      8           [ 206ms]
 6    70    6,7,8     10           [ 242ms]
 7   126    -         12  [ 481ms] [ 449ms]
 8   210    11,12,13  14  [ 1.41s] [  1.5s]
 9   330    14,15,16  17  [ 4.77s] [  7.6s]
10   495    -         20  [ 14.0s] [ 37.5s]
11   715    21,22,23  22  [ 3m02s] [13m14s] [SOLUTION]
12  1001    25,26,27  25  [28m29s] [ 2h15m] [SOLUTION]
13  1365    -         28  [ 8h18m] [35h21m]
14  1820    34,35,36  31
```
  t = OEIS A000332
  r = OEIS A240114
  The numbers in seq appear to be growing more rapidly than the numbers in r, so it seems likely these are the only solutions.
  
  The solution at n = 2 is disallowed as the puzzle text implies that n > 3 (and also as it requires one of the colours to have no corresponding cells).
  
  Here are some example maximal layouts for various n values:
  
  The published solution is that there were 16 red hearts.
  
  And so the numbers of red, pink, white hearts must be 14, 15, 16 to make a total of 45 cells, hence the arrangement has 9 rows.
  
  However, as we have seen above, the maximum number red hearts for an arrangement with 9 rows is actually 17, so we do not get a solution at n = 9.
  
  It is possible that the setter(s) assumed that the “inverted-V” shape that we see in solutions for n = 4, 5, 6, which gives a solution with 2(n − 1) red cells, would provide a maximal solution for larger n.
  
  LikeLike
  - Frits 8:49 pm on 15 April 2023 Permalink | Reply
    @Jim,
    
    I had a look at [ http://www.hakank.org/minizinc/hitting_set.mzn ] and tried the N=11 case in the MiniZinc program.
    
    Your model ran for 10 min 52 secs:
```
solve minimize(sum(x));
....
constraint x[52] + x[54] + x[61] > 0;
constraint x[9] + x[21] + x[29] > 0;
....
constraint x[2] + x[9] + x[58] > 0;
```
    The model with predicate hitting_set ran for 6 min 20 secs:
```
solve :: int_search(x, most_constrained, indomain_min, complete) minimize k;
....

n = 715;
v = [
{52, 61, 54},
{9, 29, 21},
....
{9, 2, 58}
];
```
    I guess it’s the “exists” statement in the predicate hitting_set that makes the difference.
    
    LikeLike
    - Jim Randell 12:04 pm on 16 April 2023 Permalink | Reply
      
      @Frits: Thanks for the link. I did some tests (with MiniZinc 2.7.2), but found that in general my original formulation ran slightly faster than hakank’s model.
      
      However, I did download the “scip” solver, and found that it was able to solve the N=11 case in 3m15s, and the N=12 case in just 29m.
      
      LikeLike
  - Jim Randell 11:58 am on 5 May 2023 Permalink | Reply
    
    It is possible to install commercial solvers that integrate with MiniZinc and are able to use multiple CPUs.
    
    The CPLEX solver can be installed from IBM (registration required), and this enables the cplex solver in MiniZinc (you may need to tell it where CPLEX is using the --cplex-dll parameter). You can then use the --parallel <n> parameter to enable multithreading.
    
    The free version of CPLEX is limited to models with 1000 variables/constraints, but this is sufficient for this problem up to N = 11, which is where the first solution is found. I found CPLEX could solve this using 4 threads in an elapsed time of 42.6s.
    
    Installing the gurobipy package via pip provides a license to use the Gurobi solver for models with up to 2000 variables/constraints. This is a bit trickier as the free version doesn’t integrate directly with MiniZinc, but I wrote a utils_gurobi.py module to provide the same interface via gurobipy.
    
    It solves (using 8 threads) the N = 11 case in 22.5s, and the N = 12 case in 9m07s, and the N = 13 case in 2h41m. And it should be able to do the N = 14 case.
    
    The Gurobi solver uses more CPU time than the (single-threaded) SCIP solver, but because it is able to use multiple CPUs the elapsed time is shorter.
    
    LikeLike
    - Jim Randell 2:09 pm on 12 May 2023 Permalink | Reply
      
      Update: I ran the N = 14 case using the Gurobi solver. It took >161 hours (elapsed time), and used >750 hours total CPU time, a lot of RAM, and basically tied up my machine for a week.
      
      The size of the minimum hitting set is 74, which means the maximum number of red hearts is 31.
      
      The configuration found looks like this:
      
      LikeLike
    - Frits 4:57 pm on 12 May 2023 Permalink | Reply
      
      @Jim, are you going to publish utils_gurobi.py?
      
      LikeLike
      - Jim Randell 12:16 am on 13 May 2023 Permalink | Reply
        
        @Frits: Certainly.
        
        I’ve put it up here. [@github] (or [@replit])
        
        LikeLike
- Frits 2:14 pm on 13 May 2023 Permalink | Reply
  Or calling print_triangle(hs) for a graphical representation.
```
   
def print_triangle(s):
  # from top to bottom
  for r in range(N - 1, -1, -1):
    # in row r only (N - r) elements may be printed
    print(((r // 2) * "  " + (" " if r % 2 else "")), end=" ")
    for c in range(N - r):
      print("." if (r, c) in s else "R", end=" ")  
    print() 
```
  LikeLike
Jim Randell 9:14 am on 7 February 2023 Permalink | Reply
Tags: by: Robin Nayler ( 16 ), flawed
Teaser 2692: Runners-up
From The Sunday Times, 27th April 2014 [link] [link]

In our local football league each team plays each other team twice each season, once at home and once away. The teams get three points for a win and one point for a draw. All games are on Saturdays at 3pm, and yesterday all the teams played their last game, so the final league table has now been published. Our team were runners-up, but we should have won! We were just one point behind the winners and, although they won two-thirds of their games, our team won more. Furthermore, looking at our drawn games, I notice that the league winners lost twice as many games as we drew.

How many games did the league winners win, draw and lose?

[teaser2692]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 9:15 am on 7 February 2023 Permalink | Reply
  This puzzle should have been worded more carefully to eliminate multiple solutions.
  
  If there are n teams in the league, then each team plays each of the other (n − 1) teams both at home and away, so each team plays (2n − 2) matches.
  
  The fact that all teams can play at one time tells us that n must be even (so the teams can all be paired up).
  
  We are not told how long the season is, but if we suppose that it lasts less than 1 year, then as the teams play 1 match per week, we can suppose than n ≤ 26 (otherwise it would not be possible to fit all the matches in).
  
  I am assuming that “the league winners lost twice as many games as we drew” implies that the numbers involved are non-zero (otherwise it would be a bit of an odd way to phrase it), but this does not give a unique solution.
  
  The following Python program runs in 52ms. (Internal runtime is 190µs).
  
  Run: [ @replit ]
```
from enigma import (irange, inf, div, printf)

# consider number of teams in the league (must be even)
for n in irange(2, inf, step=2):
  # total number of matches played by each team
  played = 2 * (n - 1)
  if played > 52: break
  # the winners won 2/3 of their matches
  w1 = div(2 * played, 3)
  if w1 is None: continue

  # consider the number of draws for the runners up (at least 1)
  for d2 in irange(1, played):
    # the winners lost twice this amount
    l1 = 2 * d2
    # calculate the draws and points for the winners
    d1 = played - w1 - l1
    if d1 < 0: break
    pts1 = 3 * w1 + d1
    # calculate the points, wins for the runners up
    pts2 = pts1 - 1
    w2 = div(pts2 - d2, 3)
    if w2 is None or not (w2 > w1): continue
    l2 = played - w2 - d2
    if l2 < 0: continue
    # some sanity checks
    if not (w1 + l2 < played - 2 and w2 + l1 < played - 2): continue
    # output solution
    printf("n={n} d2={d2}: played={played}; (w, d, l, pts) #1 ({w1}, {d1}, {l1}, {pts1}); #2 ({w2}, {d2}, {l2}, {pts2})")
```
  There are two candidate solutions:
  
  16 teams in the league; each team plays 30 matches.
  
  winners: w=20, d=8, l=2, pts=68; runners up: w=22, d=1, l=7, pts=67
  winners: w=20, d=6, l=4, pts=66; runners up: w=21, d=2, l=7, pts=65
  
  The published answer (“20, 6 and 4”) corresponds to the second of these scenarios.
  
  It has been suggested that “looking at our drawn games” necessarily implies that the runners-up must have more than one drawn match (eliminating the first of the above solutions), but I think if this was the intention a clearer choice of words would be necessary.
  
  LikeLike
Jim Randell 4:29 pm on 6 January 2023 Permalink | Reply
Tags: by: John Owen ( 33 ), flawed
Teaser 3146: Curling league
From The Sunday Times, 8th January 2023 [link] [link]

In our curling league (between 4 and 26 teams), each team plays each other once. Teams are ranked according to the number of wins (draws are impossible). If any teams are tied on wins, ranking is only possible if those teams have different numbers of wins in their mutual games. For example, in a three-way tie if A beats B, B beats C and A beats C, the ranking is ABC, but if C beats A (or A has not yet played C), then ranking is impossible, as A and B have one win each.

At one point (each team had played G games), ranking the teams as above was possible. However, if each team had played G-1 games, a ranking would have been impossible, irrespective of results. With one more team in the league, the minimum number of games needed to allow a ranking is G+2.

How many teams are in the league and what was the value of G?

Note: The setter of the puzzle is expecting a solution where the league has at least 5 and no more than 25 teams. (Which I would have phrased as “between 5 and 25 teams”).

See Teaser 3146: Curling league [revised] for a revised version of this puzzle.

[teaser3146]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell, Frits, and Brian Gladman are discussing. Toggle Comments
- Jim Randell 5:42 pm on 6 January 2023 Permalink | Reply
  I wrote a quick program to start attacking this puzzle starting with the smallest number of teams and working upwards, although I didn’t expect my program to run in a reasonable time as the number of teams grew.
  
  However I found that a situation that satisfies the conditions described in the puzzle presented itself very quickly, which makes me wonder if I have missed something.
  
  The following Python program runs in 57ms (it stops when the first solution is found). (Internal run time is 4.3ms).
  
  Run: [ @replit ]
```
from enigma import (
  irange, group, item, div, subsets, multiset,
  cproduct, seq_all_different, cache, printf
)

# labels for <n> teams; 1..n
teams = lambda n: irange(1, n)

# a match is represented by (<winning-team>, <losing-team>)

# check a set of matches for <n> teams is orderable
def orderable(n, ms):
  # extract the winners
  (ws, _) = zip(*ms)
  # and count the number of wins for each team
  w = dict((t, ws.count(t)) for t in teams(n))
  # group teams with the same number of wins together
  g = group(w.items(), by=item(1), f=item(0), fn=sorted)
  # look for tied groups
  for (_, ts) in g.items():
    if len(ts) < 2: continue
    # collect the mutual games amongst the group
    ws_ = list(x for (x, y) in ms if x in ts and y in ts)
    # and check they are all different
    if not seq_all_different(ws_.count(t) for t in ts): return False
  # looks good
  return True

# choose <p>-subsets of potential matches <ps>, with <k> matches played per team
def choose(n, ps, p, k):
  for ss in subsets(ps, size=p):
    m = multiset.from_seq(*ss)
    if all(m.count(t) == k for t in teams(n)):
      yield ss

# find orderable sets of wins for <n> teams, each having played <k> matches
def wins(n, k):
  # calculate the number of played matches
  p = div(n * k, 2)
  if p is None: return
  # construct the possible matches
  ps = list(subsets(teams(n), size=2))
  # choose a p-subset with k matches played per team
  for ss in choose(n, ps, p, k):
    # now choose the winning team in each match
    for ms in cproduct([(x, y), (y, x)] for (x, y) in ss):
      # is this set of matches orderable?
      if orderable(n, ms):
        yield ms

# check if <n> teams, each played <k> games is orderable
@cache
def check(n, k):
  if not (n > k > 0): return None
  for r in wins(n, k):
    printf("[n={n} k={k} -> {r}]")
    return True
  printf("[n={n} k={k} -> None]")
  return False

# solve the puzzle
def solve():
  # n = number of teams in the league
  for n in irange(5, 27):
    # k = number of matches played by each team
    # look for minimum k that is orderable
    for k in irange(1, n - 1):
      # can we find an orderable set of wins?
      r = check(n, k)
      # find the smallest k that gives an orderable set
      if r:
        printf("-> n={n}: min_k = {k}")
        (T, G) = (n - 1, k - 2)
        # look to see if (T, G) is possible and (T, G - 1) is not possible
        if check(T, G) is True and check(T, G - 1) is False:
          # output solution
          printf("=> T = {T}; G = {G}")
          printf("##### SOLUTION FOUND -> league has {T} teams; games played = {G} #####")
          # we are done
          return
        break
    printf()

solve()
```
  There are two solution to this puzzle:
  
  Solution: There are either 4 teams in the league, and G = 2. Or there are 16 teams in the league and G = 6.
  
  My program quickly finds the first of these solutions, but would take a long time to find the second one (and to exhaustively check the entire solution space).
  
  But the program I wrote for the revised puzzle [link] does find both solutions in a reasonable time.
  
  Here is a description of the solution with 4 teams:
  
  It is possible for each of the 4 teams (A, B, C, D) to have played 2 games. For example:
  
  A beat B
  A beat C
  B beat D
  D beat C
  
  And we see the teams are ranked:
  
  1st: A (2 wins)
  2nd: B (1 win, but B beat D)
  3rd: D (1 win, but D lost to B)
  4th: C (0 wins)
  
  It is not possible to rank the teams if they have only played one game. As there will only have been 2 games played, involving all 4 teams. 2 of the teams will have 1 win (and cannot be ranked, as they have not played each other), and the other will have 0 wins (likewise).
  
  If there were 5 teams in the league (A, B, C, D, E) then it is not possible for each of the teams to have played an odd number of games (as each game requires 2 teams), but it is possible for each team to play 4 games, for example:
  
  A beat B
  A beat C
  A beat D
  A beat E
  B beat C
  B beat D
  B beat E
  C beat D
  C beat E
  D beat E
  
  The teams are ranked:
  
  1st: A (4 wins)
  2nd: B (3 wins)
  3rd: C (2 wins)
  4th: D (1 win)
  5th: E (0 wins)
  
  All that remains is to show that it is not possible to find a set of matches with 2 wins per team, and the program can do this for us:
```
>>> from enigma import first
>>> first(wins(5, 2))
[]
```
  LikeLike
  - Frits 12:35 pm on 7 January 2023 Permalink | Reply
    
    @Jim, nice solution. It is not easy to solve this week.
    
    How can you be sure this is the only solution? So you might give an incorrect answer (for “our curling league”).
    
    One thing I can deduce is that if k = n-1 then we can always find an orderable set of wins.
    
    LikeLike
    - Jim Randell 12:44 pm on 7 January 2023 Permalink | Reply
      
      My program gets bogged down as n increases, so it just stops at the first viable solution, and I haven’t been able to check all values up to n = 26.
      
      There may be an analytical way to show that there is only a single solution. Although if there are multiple solutions we won’t be able to tell which of them the setter had in mind.
      
      LikeLike
    - Jim Randell 11:32 am on 9 January 2023 Permalink | Reply
      
      I’ve put a more efficient (but more complex) version of my program up on the page for the revised version of this puzzle [link].
      
      And we see that the original formulation of the puzzle has 2 solutions.
      
      LikeLike
  - Jim Randell 10:26 am on 8 January 2023 Permalink | Reply
    
    Apparently the setter of this puzzle is expecting a solution for this puzzle with the number of teams in the league in the interval [5..25]. If this is the case, I think the wording should have been chosen more carefully.
    
    LikeLike
- Brian Gladman 2:48 pm on 7 January 2023 Permalink | Reply
  
  Congratulations on getting a solution for this one Jim. At the moment I don’t have one 😦
  
  LikeLike
- Brian Gladman 10:50 am on 8 January 2023 Permalink | Reply
  
  John Owen has just clarified on the Sunday Times discussion group site that “between 4 and 26” means “5 or more and at most 25”.
  
  LikeLike
  - Jim Randell 2:49 pm on 8 January 2023 Permalink | Reply
    
    @Brian: This change certainly makes things trickier, as my program gets bogged down before it can check leagues with 10 or more teams.
    
    Although I would have expected this condition to be expressed as “between 5 and 25 teams”.
    
    LikeLike
  - Frits 4:14 pm on 8 January 2023 Permalink | Reply
    
    Nice to encounter a teaser which doesn’t seem to get solved (within a reasonable time) by brute force. My adapted version (with recursion) of Jim’s program is getting too slow at n=10.
    
    It isn’t easy to find a way to simplify the problem so it can be solved.
    
    LikeLike
Jim Randell 2:04 pm on 24 July 2022 Permalink | Reply
Tags: by: C Skeffington Quin ( 11 ), flawed
Brain-Teaser 159: Fallen leaves
From The Sunday Times, 26th April 1964 [link]

Three leaves fall from a book. The total of the page numbers remaining in the second half of the book is now three times the total of the page numbers remaining in the first half.

The total of the page numbers on the fallen leaves lies between 1050 and 1070, and is the highest which could have produced this effect.

How many numbered pages did the book contain originally?

I found many solutions, which improve on the published answer. So I have marked the puzzle as flawed.

This puzzle is included in the book Sunday Times Brain Teasers (1974).

[teaser159]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 2:06 pm on 24 July 2022 Permalink | Reply
  I think this puzzle is flawed, as I found many solutions that seem to satisfy the puzzle text, and are different from the published solution.
  
  If we suppose the book consists of n leaves (= 2n pages), and that the leaves are 1|2, 3|4, …, (2n − 1)|(2n).
  
  And the two halves of the book are pages 1 – n and (n + 1) – (2n).
  
  Then the initial sum of page numbers in each half of the book are:
  
  first half = sum(1 .. n) = n(n + 1)/2
  second half = sum(n+1 .. 2n) = n(3n + 1)/2
  
  Now, if the three leaves removed are (2a − 1)|(2a), (2b − 1)|(2b), (2c − 1)|(2c).
  
  Then the total of the page numbers removed is t = 4(a + b + c) − 3, and this is in the range 1050 – 1070.
  
  So (a + b + c) is in the range 264 – 268, and we want this to take on the highest possible value (i.e. 268 if possible, which corresponds to t = 1069).
  
  If the sum of the removed pages in the first and second halves is t1, t2 (t1 + t2 = t), then we have:
  
  n(3n + 1)/2 − t2 = 3(n(n + 1)/2 − t1)
  n = 3.t1 − t2
  
  This Python program starts looking for values of t from 268 down to 264, and stops when it finds a value that gives viable books. It runs in 74ms. And it finds many possible solutions.
  
  Run: [ @replit ]
```
from enigma import (irange, decompose, printf)

# solve with leaves removed (even page numbers given)
def solve(*vs):
  # calculate the removed page numbers
  (x, y, z) = (2 * v for v in vs)
  ps = (x - 1, x, y - 1, y, z - 1, z)
  # split the pages at index i
  for i in irange(2, 4):
    t1 = sum(ps[:i])
    t2 = sum(ps[i:])
    # calculate the number of leaves (so there are 2n pages)
    n = 3 * t1 - t2
    if n < 3 or ps[-1] > 2 * n: continue
    # and check the split occurs between the halves
    if i > 0:
      if ps[i - 1] > n: continue
    if i < 6:
      if not (ps[i] > n): continue
    yield (n, ps, t1, t2)

# record solutions (number of pages = twice the number of leaves)
ss = set()

# t = a + b + c
for t in irange(268, 264, step=-1):
  # calculate possible a, b, c values
  for (a, b, c) in decompose(t, 3):
    for (n, ps, t1, t2) in solve(a, b, c):
      printf("[t={t}: a={a} b={b} c={c} -> {ps}; t1={t1} t2={t2}; n={n}]")
      ss.add(2 * n)
  # are we done?
  if ss:
    printf("pages = {ss}", ss=sorted(ss))
    break
```
  Solution: The book could have: 310, 318, 342, 350, 374, 406, 438, 470, 502, 534, 566, 598, 630, 662, 694, 6414 pages.
  
  Here is one of the solutions found:
  
  If the book has 203 leaves = 406 pages, numbered 1|2, 3|4, …, 203|204, …, 405|406.
  
  Then the sum of the page numbers in the first half of the book is: sum(1..203) = 20706.
  
  And the sum of the page numbers in the second half of the book is: sum(204..406) = 61915.
  
  (Note that if leaf 203|204 is removed, that is one page from each half of the book).
  
  Now, if pages 1|2, 157|158, 375|376 are removed (total = 1069, the largest possible value).
  
  Then the pages removed from the first half are: 1, 2, 157, 158; sum = 318, so the sum of the remaining pages in the first half is 20706 − 318 = 20388.
  
  And the pages removed from the second half are: 375, 376; sum = 751, so the sum of the remaining pages in the second half is 61915 − 751 = 61164.
  
  And: 61164 = 3 × 20388, as required.
  
  The published solution (and that given in the 1974 book) is that the book initially had 302 pages (i.e. 151 leaves), and the removed pages are 75|76, 151|152, 301|302. Which gives a total of 1057.
  
  But I have shown above that this is not the largest total possible.
  
  It was also noted: “Only 4 correct answers in a very small entry”. So it seems I wasn’t the only one that had issues with this puzzle.
  
  The solution in the book only considers 3 ways that leaves can be removed: 1 from the first half + 2 from the second half; 2 from the first half + 1 from the second half; 1.5 from each half. In terms of pages these are 2+4, 3+3, 4+2, but my program also considers 0+6, 1+5, 5+1, 6+0. However the example I give is a 4+2 combination, which should be accounted for by the published solution. But it has arrived at the conclusion that the maximum viable total of the numbers on the removed pages for a book with x leaves is 7x, so 1057 is the maximum possible (with 151 leaves), but I think this is faulty reasoning.
  
  (The only thing I can think of is that the two halves of the book are considered after the leaves have been removed. (Although the solution given in the book doesn’t seem to support this). But even with this interpretation there are multiple solutions with a total of 1069 – any that removes 3 pages from the first half and three from the second half will leave the boundary unchanged).
  
  LikeLike
Jim Randell 4:32 pm on 20 May 2022 Permalink | Reply
Tags: by: Peter Good ( 27 ), flawed
Teaser 3113: The plumber’s buckets
From The Sunday Times, 22nd May 2022 [link] [link]

A plumber was trying to empty a tank containing 100 litres of water using three buckets, each marked with a different whole number of litres capacity between 10 and 20 litres. He calculated that he could exactly empty the tank, but only by using all three buckets and completely filling each bucket a different number of times.

He filled and emptied each bucket the calculated number of times but the tank still contained 6 litres of water, because the smallest bucket had a dent that reduced its capacity by 3 litres.

What were the marked capacities of the three buckets?

The version of this puzzle that appears in the book The Sunday Times Teasers Book 2 (2023) is as follows (with modified sections underlined):

A plumber was trying to empty a tank containing 100 litres of water using three buckets, each marked with a different whole number of litres capacity between 10 and 20 litres. He calculated that he could exactly empty the tank, but only by using all three buckets.

He then emptied the tank as calculated, filling each bucket a different number of times, but then found the tank still contained 6 litres of water, because the smallest bucket had a dent that reduced its capacity by 3 litres.

What were the marked capacities of the three buckets?

This corresponds to my own re-wording of the puzzle given in the comments.

[teaser3113]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Frits, GeoffR, bencooperjamin, and 4 others are discussing. Toggle Comments
- Jim Randell 4:51 pm on 20 May 2022 Permalink | Reply
  Perhaps I misread this puzzle, but I couldn’t find a solution that fits the text.
  
  However, I did find a solution where the dent reduces the capacity of the largest bucket (not the smallest) by 3 litres. This is my preferred way to “rescue” the puzzle, as it is a minimal change to the text, and the dent would be less noticeable in the largest bucket. However, another way to rescue the puzzle (but with a different solution) is if the capacity of the smallest bucket is reduced by 2 litres (not 3 litres).
  
  This Python program runs in 58ms.
  
  Run: [ @replit ]
```
from enigma import (
  irange, subsets, express, seq_all_different as all_different,
  singleton, printf
)
 
# choose the labelled capacities of the buckets
for bs in subsets(irange(10, 20), size=3):
  # there is only one way to use the buckets
  qs = singleton(express(100, bs))
  if qs is None: continue
  # each bucket is used
  if 0 in qs: continue
  # the number of uses are all different
  if not all_different(qs): continue
  # largest [was: smallest] bucket must be used twice
  if qs[-1] != 2: continue
  printf("bs={bs} qs={qs}")
```
  Solution: The puzzle, as originally worded, has no solution.
  
  If we look for combinations of (correctly labelled) buckets that can be used (completely filling each bucket a number of times) to empty a 100 litre tank, such that all three buckets must be used, each of them a different number of times, we find there are 5 viable combinations (buckets × uses):
  
  (11, 18, 19) × (4, 1, 2)
  (12, 17, 18) × (1, 2, 3)
  (12, 17, 18) × (4, 2, 1)
  (13, 15, 19) × (1, 2, 3)
  (15, 18, 19) × (3, 2, 1)
  
  (And if we require there to be only a single way to use the buckets we can discard the (12, 17, 18) combination, leaving only 3 viable combinations).
  
  The original text asked for a combination where the smallest bucket was used twice, but as we see there are no such combinations.
  
  In my rescued version, where the largest bucket (not the smallest) has the dent, the solution is that the buckets are labelled (11, 18, 19) litres (although they are actually (11, 18, 16) litres).
  
  The published solution was that the buckets are labelled (13, 17, 19) litres (although they are actually (10, 17, 19) litres). Which corresponds to my re-wording of the puzzle given below.
  
  However we can use (correctly labelled) buckets (13, 17, 19) to empty the tank in the following ways:
  
  1× 13 + 4× 17 + 1× 19 = 100
  2× 13 + 1× 17 + 3× 19 = 100
  
  So it is not true to say that it can “only [be done] by using all three buckets and completely filling each bucket a different number of times”. (The first line achieves the required result using two of the buckets the same number of times). Hence the requirement for rewording of the puzzle.
  
  But if we suppose “the calculated number of times” requires that there is only one possible way to fill the buckets, then the reworded puzzle also has no solutions. (As there are 2 ways to use these (correctly labelled) buckets to empty the tank).
  
  It is possible that the setter intended that when the plumber sat down to work out how many times to use the buckets, he only considers using each bucket a different number of times. He tried using just one bucket and found it was not possible, then he tried using combinations of two buckets and found none of those were possible, and finally he tried using all three buckets and found that there was a single way they could be used. And he then proceeded to use this calculated number of ways, but when he finished there was 6 litres remaining in the tank, because the smallest bucket’s capacity was reduced by 3 litres from the labelled capacity.
  
  In this scenario, there are 9 candidate bucket combinations, and only one of them has the smallest bucket having 2 uses, so this gives a unique solution, and it is the published solution.
  
  The published solution is: “13, 17 and 19 litres”.
  
  LikeLike
  - Jim Randell 5:58 pm on 20 May 2022 Permalink | Reply
    This might be a stricter interpretation of the puzzle text, which finds a couple more candidate solutions. But still doesn’t find a solution that fits the text.
    
    Instead I have coded it to find the same solution I found above.
    
    There remains an issue as to whether “he filled and emptied each bucket the calculated number of times” is intended to imply that there is only a single way of filling the buckets (each a different non-zero number of times), or he chose one from multiple viable ways. Fortunately this does not change the answer to my “rescued” version of the puzzle.
    
    This Python program runs in 56ms. (Internal run time is 1.58ms).
    
    Run: [ @replit ]
```
from enigma import (irange, subsets, express, seq_all_different as all_different, printf)

# find viable ways to use the buckets
def buckets(t, bs):
  rs = list()
  for qs in express(t, bs):
    # each bucket is used
    if 0 in qs: return []
    # the numbers of uses are all different
    if not all_different(qs): return []
    # is viable
    rs.append(qs)
  return rs

# choose the labelled capacities of the buckets
for bs in subsets(irange(10, 20), size=3):
  # find viable ways to use the buckets
  for qs in buckets(100, bs):
    # largest [was: smallest] bucket must be used twice
    if qs[-1] != 2: continue
    # output solution
    printf("bs={bs} qs={qs}")
```
    The interpretation of the puzzle text where there is just a single way to fill the buckets can be implemented at line 13 by only returning the list of candidates if it has a length of 1. But this doesn’t change the answer found.
    
    LikeLike
  - Frits 5:59 pm on 20 May 2022 Permalink | Reply
    
    Correct, with SubstitutedExpression I end up with 3 options (the third solution would be if the capacity of the smallest bucket is reduced by 1.5 litres).
    
    LikeLike
  - Jim Randell 8:26 am on 21 May 2022 Permalink | Reply
    It has been suggested to me that the intended interpretation of this puzzle is more like this (with {{ changed sections }} in double braces):
    
    A plumber was trying to empty a tank containing 100 litres of water using three buckets, each marked with a different whole number of litres capacity between 10 and 20 litres. {{ He calculated that by completely filling each bucket a number of times, he could exactly empty the tank, but only by using all three buckets. }}
    
    He filled and emptied each bucket the calculated number of times, {{ each bucket being used a different number of times. But when he finished }} the tank still contained 6 litres of water, because the smallest bucket had a dent that reduced its capacity by 3 litres.
    
    What were the marked capacities of the three buckets?
    
    To solve this formulation of the puzzle we can take my program and just move the “different number of times” test (line 10 in the program above is moved to line 18 below):
    
    Run: [ @replit ]
```
from enigma import (irange, subsets, express, seq_all_different as all_different, printf)

# find viable ways to use the buckets
def buckets(t, bs):
  rs = list()
  for qs in express(t, bs):
    # each bucket is used
    if 0 in qs: return []
    # is viable
    rs.append(qs)
  return rs

# choose the labelled capacities of the buckets
for bs in subsets(irange(10, 20), size=3):
  # find viable ways to use the buckets
  for qs in buckets(100, bs):
    # the numbers of uses are all different
    if not all_different(qs): continue
    # smallest bucket must be used twice
    if qs[0] != 2: continue
    # output solution
    printf("bs={bs} qs={qs}")
```
    LikeLike
  - Mark Valentine 12:00 pm on 22 May 2022 Permalink | Reply
    
    I think the text is absolutely fine. Clearly you need three different bucket sizes, where no two (or one) of which can combine to make exactly 100. Then from these triples you apply the condition for the smallest bucket size.
    
    LikeLike
    - Jim Randell 12:27 pm on 22 May 2022 Permalink | Reply
      
      @Mark: You also need to check that the numbers of uses of each bucket are all different. And where this requirement is placed in the puzzle text makes a difference.
      
      The original puzzle text has no solutions. My revised text does have a unique solution. (And it seems that this revised text corresponds to the intended puzzle).
      
      LikeLike
      - Mark Valentine 9:00 pm on 22 May 2022 Permalink | Reply
        
        Ok to be fair I didn’t check for uniqueness . Just stopped at a solution. so will defer.
        
        LikeLike
- Hugh+Casement 9:47 am on 21 May 2022 Permalink | Reply
  
  I don’t see that changing the passages in double braces makes any difference!
  
  Does the clue lie in “but only by using all three buckets” ?
  That is to say, no (different) integer multiples of any two undented buckets would sum to 100 litres.
  
  LikeLike
  - Jim Randell 10:03 am on 21 May 2022 Permalink | Reply
    
    There is a subtle difference between “but only using all three buckets” and “but only using all three buckets, each a different number of times” that stops the puzzle from working in the originally published formulation.
    
    The “using all three buckets” requirement means we can’t use buckets with capacity 10 or 20, as then we could exactly empty the tank using just one of them. Similarly if a collection of buckets includes a pair that can be used to exactly empty the tank then that is also disallowed.
    
    LikeLike
    - Hugh+Casement 12:23 pm on 21 May 2022 Permalink | Reply
      
      Yes, but he used the buckets the calculated number of times.
      
      LikeLike
- J Slusar 6:55 pm on 21 May 2022 Permalink | Reply
  
  But what is wrong with buckets marked 13, 14 and 15 filling the smallest twice, the middle one once and the larger one 4 times? The total would have been 100, but the reduced capacity of the smaller bucket would mean 6 litres remained in the tank?
  
  LikeLike
  - Jim Randell 10:01 pm on 21 May 2022 Permalink | Reply
    
    Thanks for the comment.
    
    I think this combination is ruled out by the requirement that “he could exactly empty the tank, but only by using all three buckets and completely filling each bucket a different number of times”.
    
    With (13, 14, 15) there are three ways we can make 100:
    
    100 = 0×13 + 5×14 + 2×15
    100 = 1×13 + 3×14 + 3×15
    100 = 2×13 + 1×14 + 4×15
    
    The first of these means that you don’t have to use all three buckets, and the second means that you don’t have to use each bucket a different number of times. So the requirement is not met.
    
    LikeLike
- bencooperjamin 1:46 am on 23 May 2022 Permalink | Reply
  
  Doesnt work because 5*14 +2*15=100 ie the tank can be emptied with only 2 of the buckets.
  
  LikeLike
- GeoffR 12:34 pm on 23 May 2022 Permalink | Reply
  I finally managed to find a program solution, which agrees with Jim’s last posting i.e 3rd posting (21 May 2022).
```
% A Solution in MiniZinc
include "globals.mzn";

int: Tank == 100;   % litres

% Three buckets - capacity ranges in litres
var 10..20:B1; var 10..20:B2; var 10..20:B3; 

% Three different size buckets are required
constraint B1 < B2 /\ B2 < B3;

% No of times buckets B1, B2 and B3 are emptied
var 1..10:n1;  var 1..10:n2;  var 1..10:n3; 

constraint all_different([n1, n2, n3]);

% Smallest bucket B1 must be emptied twice due to a 3L dent
constraint n1 == 2;

% Tank emptying constraints for one and two buckets
% Tank cannot be emptied with any single bucket
constraint forall(i in 1..10) ( Tank mod (B1 * i) != 0 );
constraint forall(i in 1..10) ( Tank mod (B2 * i) != 0 );
constraint forall(i in 1..10) ( Tank mod (B3 * i) != 0 );

% Buckets B1 and B2 cannot empty tank on their own
constraint forall(i in 1..10, j in 1..10) (
      Tank mod (i * B1 + j * B2) != 0);

% Buckets B1 and B3 cannot empty tank on their own
constraint forall(i in 1..10, j in 1..10) (
      Tank mod (i * B1 + j * B3) != 0);
      
% Buckets B2 and B3 cannot empty tank on their own
constraint forall(i in 1..10, j in 1..10) (
      Tank mod (i * B2 + j * B3) != 0);

% Empty the tank with three buckets B1, B2 and B3
constraint Tank mod (n1 * B1 + n2 * B2 + n3 * B3) == 0;

solve satisfy;

output [" Capacities of three buckets (B1, B2, B3) = " 
++ show([B1, B2, B3 ] )
++ "\n" ++ " No of times each bucket emptied (n1, n2, n3) = "
 ++ show([n1, n2, n3 ]) ];
```
  LikeLike
- Frits 10:39 am on 25 May 2022 Permalink | Reply
  To simplify restraints you can use:
```
   
constraint forall(i in 0..10, j in 0..10, k in 0..10) (
i * B1 + j * B2 + k * B3 != Tank \/ i * j * k > 0);
```
  LikeLike
Jim Randell 4:35 pm on 25 March 2022 Permalink | Reply
Tags: by: Peter Good ( 27 ), flawed
Teaser 3105: Roman primes
From The Sunday Times, 27th March 2022 [link] [link]

Romulus played a game using several identical six-sided dice. Each die face shows a different single-character Roman numeral. He rolled two dice and was able to form a prime number in Roman numerals by arranging the two characters. Romulus rolled more dice and, after each roll, formed a prime number with one more character, rearranging the sequence as needed, until he could no longer form a prime number less than 100. He was using standard notation where a character before another that is 5 or 10 times larger is subtracted from the larger one, e.g., IX = 9.

After playing many games he realised that there were exactly three primes less than 100 that could not occur in any of the sequences.

In decimal notation and in ascending order, what were those prime numbers?

I found two different scenarios that fit the puzzle text, but lead to two different answers. So I have marked the puzzle as flawed.

[teaser3105]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell, Hugh+Casement, and Robert Brown are discussing. Toggle Comments
- Jim Randell 5:28 pm on 25 March 2022 Permalink | Reply
  To represent numbers from 1 to 99 using Roman numerals requires five characters I, V, X, L, C. So we know those must be on the dice. The other symbol is probably D (= 500), which lets us express numbers up to 899 (with sufficient dice; it takes 12 to make 888 = DCCCLXXXVIII).
  
  I’m assuming that Romulus rolls 2 dice, arranges them to make the first prime in the sequence. Then rolls another single die, and arranges the 3 dice (without changing the numerals shown by the first two) to make the second prime, and so on. Rolling a single new die at each step until he is unable to rearrange the dice to make a prime, or he runs out of dice.
  
  Then we can find a scenario where there are three primes that cannot occur in any sequence.
  
  This Python program runs in 51ms.
  
  Run: [ @replit ]
```
from enigma import (primes, int2roman, group, join, multiset, printf)

# primes less than 100
prms = list(primes.between(2, 99))

# record primes by their roman numeral content
d = group(prms, by=(lambda n: join(sorted(int2roman(n)))))

# find length n extensions of ks in d
def extend(d, ks, n):
  ss = list(multiset.from_seq(k) for k in ks)
  for k in d.keys():
    if len(k) == n:
      s = multiset.from_seq(k)
      if any(s.issuperset(s_) for s_ in ss):
        yield k
  
# generate possible throws with increasing lengths
def generate(d, n=2):
  # start with length n sequences
  ks = list(k for k in d.keys() if len(k) == n)
  while ks:
    yield (n, ks)
    # find keys that are one longer
    n += 1
    ks = list(extend(d, ks, n))

# start with the complete set of primes
ps = set(prms)
for (n, ks) in generate(d, 2):
  # and remove those reachable after n dice
  for k in ks:
    ps.difference_update(d[k])
  # we have a solution if there are 3 primes remaining
  if len(ps) == 3:
    printf("{n} dice -> {ps}", ps=sorted(ps))
```
  Solution: The prime numbers are: 5, 37, 83.
  
  This is the solution in the scenario where Romulus has 6 dice, with the symbols I, V, X, L, C, and one other.
  
  5 (= V) only requires 1 die, so cannot be constructed using 2-6 dice.
  
  83 (= LXXXIII) requires 7 dice, so cannot be constructed using 2-6 dice.
  
  37 (= XXXVII) can be constructed using 6 dice, but there is no predecessor prime using 5 dice.
  
  Possible predecessor numbers for 37 are: 27, 32, 34, 46. None of which are prime.
  
  However I was able to find another scenario (see below), where Romulus has more than 6 dice, with the symbols I, V, X, L, and two others, that do not include C.
  
  In this scenario 5 and 37 cannot be constructed (as above), but 83 can be constructed using 7 dice.
  
  However the standard representation of 97 in Roman numerals is XCVII, which cannot be constructed if the symbol C is not available. (In fact none of the numbers in [90, 499] can be constructed with these dice).
  
  So the solution in this scenario is: 5, 37, 97.
  
  It seems that this second scenario is what the setter had in mind (it is the published answer), although it seems less plausible to me.
  
  Perhaps the following would have been a better representation of the intended puzzle:
  
  Romulus found a box containing a large number of identical six-sided dice. Each die face shows a different Latin character, and Romulus found that when he rolled some of the dice he was sometimes able to rearrange them so that the top faces formed a Roman numeral (using standard notation).
  
  He played a game where he rolled two dice and was able to form a prime number by arranging the two characters. He then rolled another die and was able to arrange the three dice to form another prime number. He carried on rolling extra dice (one die each time), until he could no longer arrange the dice to form a prime number less than 100.
  
  After playing many games he realised that there were exactly three primes less than 100 that could not occur in any of the sequences.
  
  In decimal notation and in ascending order, what were those prime numbers?
  
  The published solution is: “5, 37 and 97”.
  
  LikeLike
- Robert Brown 7:39 am on 26 March 2022 Permalink | Reply
  
  When the text says ‘after many games’ I assumed that some of these would start with II (=2) and some with XI (=11). Clearly cannot find 5 (V) as it is length 1, but I only have one more prime which cannot be made with one of the two starting pairs.
  
  LikeLike
  - Jim Randell 8:57 am on 26 March 2022 Permalink | Reply
    
    @Robert: It looks like you are 2/3 of the way to the answer.
    
    There is a scenario that satisfies the wording of the puzzle text, and there are three primes that are not constructible. And each of the three primes is non-constructible for a different reason.
    
    LikeLike
- Jim Randell 12:51 pm on 26 March 2022 Permalink | Reply
  I think there is potentially an alternative scenario that also gives three non-constructible primes:
  
  If the dice have the symbols I, V, X, L, D, M on them (so not C), then one of the primes is not constructible (using “standard” Roman numerals), no matter how many dice are used.
  
  We can modify the program for this scenario by only considering primes that don’t include C when constructing the dictionary d:
```
# record constructible primes by their roman numeral content
d = group(prms, by=(lambda n: join(sorted(int2roman(n)))), st=lt(90))
```
  Or here is a version of my code that tries all possible combinations of 6 of the 7 symbols I, V, X, L, C, D, M for the dice [ @replit ], it finds three possibilities corresponding to the two scenarios outlined above.
```
from enigma import (primes, int2roman, group, join, multiset, subsets, printf)

# primes less than 100
prms = list(primes.between(2, 99))
  
# find length n extensions of ks in d
def extend(d, ks, n):
  ss = list(multiset.from_seq(k) for k in ks)
  for k in d.keys():
    if len(k) == n:
      s = multiset.from_seq(k)
      if any(s.issuperset(s_) for s_ in ss):
        yield k

def generate(d, n=2):
  # start with length n sequences
  ks = list(k for k in d.keys() if len(k) == n)
  while ks:
    yield (n, ks)
    # find keys that are one longer
    n += 1
    ks = list(extend(d, ks, n))

# solve the puzzle for allowable symbols
def solve(symbols):

  # record primes their roman numeral content
  d = group(prms, by=(lambda n: join(sorted(int2roman(n)))))

  # remove keys with invalid symbols
  d = dict((k, v) for (k, v) in d.items() if symbols.issuperset(k))
  
  # start with the complete set of primes
  ps = set(prms)
  for (n, ks) in generate(d, 2):
    # remove those reachable after n dice
    for k in ks:
      ps.difference_update(d[k])
    # we have a solution if there are 3 primes remaining
    if len(ps) == 3:
      printf("{syms}: {n} dice -> {ps}", syms=join(sorted(symbols)), ps=sorted(ps))

# choose 6 symbols for the dice
for syms in subsets('IVXLCDM', size=6, fn=set):
  solve(syms)
```
  I think I prefer the original scenario given above, where a sufficient number of dice can be used to give the numbers from 1 to 899. A set of dice without C would only be able to go consecutively up to 89 (the next smallest constructible number would be 500). D and M don’t come into play until 400 and 900 respectively.
  
  LikeLike
  - Jim Randell 9:58 am on 1 April 2022 Permalink | Reply
    
    Depending on the shape of the glyphs used on the dice, it may be possible to use a V on its side to represent C, which would leave only 2 primes non-constructible in this second scenario (unless the number of dice is limited – and then we get the same solution as my first scenario).
    
    LikeLike
- Hugh+Casement 1:21 pm on 26 March 2022 Permalink | Reply
  
  I came to the same conclusion as Robert. I feel the setter of this puzzle has played a trick on us, but Jim rumbled it (before he came up with the alternative scenario ). It would have been neater, to my mind, if the puzzle text had stated that there were just two primes less than 100 that could not occur.
  
  LikeLike
  - Jim Randell 3:58 pm on 26 March 2022 Permalink | Reply
    
    There’s definitely some trickery going on, as what you might expect to be the normal interpretation does not give 3 non-constructible primes.
    
    We would need to have more information about the symbols or number of dice to work out which scenario the setter had in mind.
    
    LikeLike
Jim Randell 10:24 am on 20 February 2022 Permalink | Reply
Tags: by: F. V. Rowden, flawed
Brain-Teaser: Saturday’s child
From The Sunday Times, 22nd December 1957 [link]

“How old are you, John?”, I asked my friend. He replied: “My father, his elder brother and I were all born in the summer, and we were all born on the same day of the week. Although our anniversaries are on different dates, this year they all fell on a Saturday”.

“That’s very interesting”, I said, “but it isn’t very helpful, is it?”

“It should be helpful”, said John, “because when I tell you that the years of our birth are all prime numbers there is no possible doubt about my age”.

After argument, John convinced me he was right.

How old are John, his father and his uncle?

This one of the occasional Holiday Brain Teasers published in The Sunday Times prior to the start of numbered Teasers in 1961. A prize of £5 was offered.

[teaser-1957-12-22] [teaser-unnumbered]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 10:25 am on 20 February 2022 Permalink | Reply
  The following Python program runs in 47ms.
  
  Run: [ @replit ]
```
from collections import defaultdict
from datetime import date, timedelta
from enigma import Primes, subsets, printf

# consider possible prime birth years
years = set(Primes(1957).irange(1835, 1956))

# find Saturdays in the summer of 1957
d = date(1957, 6, 1)
while d.isoweekday() != 6:
  d += timedelta(days=1)

r = defaultdict(set)
while d.month < 9:
  # record previous years by day of the week
  for y in years:
    b = date(y, d.month, d.day)
    r[b.isoweekday()].add(y)

  d += timedelta(days=7)

for (k, vs) in r.items():
  if len(vs) < 3: continue

  # select 3 birth years (Uncle, Father, John)
  for (U, F, J) in subsets(sorted(vs), size=3):
    # siblings are within 20 years
    if not (F - U < 21): continue
    # John's father is 18-40 years older than him
    if not (17 < J - F < 41): continue

    age = lambda x: 1957 - x
    printf("U = {U} ({u}); F={F} ({f}); J={J} ({j})", u=age(U), f=age(F), j=age(J))
```
  I found multiple solutions to this puzzle:
  
  John’s uncle was born in 1861. In 1957 he would be 96.
  John’s father was born in 1867 (6 years later). In 1957 he would be 90.
  John was born in 1889 (22 years later again). In 1957 he would be 68.
  
  John’s uncle was born in 1861. In 1957 he would be 96.
  John’s father was born in 1867 (6 years later). In 1957 he would be 90.
  John was born in 1901 (34 years later again). In 1957 he would be 56.
  
  John’s uncle was born in 1861. In 1957 he would be 96.
  John’s father was born in 1867 (6 years later). In 1957 he would be 90.
  John was born in 1907 (40 years later again). In 1957 he would be 50.
  
  John’s uncle was born in 1873. In 1957 he would be 84.
  John’s father was born in 1879 (6 years later). In 1957 he would be 78.
  John was born in 1913 (34 years later again). In 1957 he would be 44.
  
  The published solution is that John was 44, his father 78, and his uncle 84. Which is the last of the above solutions.
  
  If we assume that the actual dates of birth were not on Saturdays, then this is the only remaining solution. However I don’t think the puzzle text can be read to include this additional restriction. (In fact, the title of the puzzle, “Saturday’s child”, implies that they were all born on a Saturday, and so would exclude the final solution).
  
  This might account for comment given with the solution (5th January 1958):
  
  “More than 600 readers sent in their solution, but there was a fair proportion of erroneous answers.”
  
  LikeLike

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

Search

Recent Posts

Recent Comments

Archives

Categories

Subscribe

RSS Links

Site Stats

Meta

Tagged: flawed Toggle Comment Threads | Keyboard Shortcuts

Jim Randell 8:11 am on 16 January 2026 Permalink | Reply Tags: by: W S Graff-Baker ( 2 ), flawed

Rate this:

Share:

Jim Randell 8:12 am on 16 January 2026 Permalink | Reply

Ruud 10:33 am on 16 January 2026 Permalink | Reply

GeoffR 7:43 pm on 16 January 2026 Permalink | Reply

Reply Cancel reply

Jim Randell 10:02 am on 11 November 2025 Permalink | Reply Tags: by: Victor Bryant ( 140 ), flawed

Rate this:

Share:

Jim Randell 10:03 am on 11 November 2025 Permalink | Reply

Jim Randell 8:07 am on 1 August 2025 Permalink | Reply Tags: by: Danny Roth ( 84 ), flawed

Rate this:

Share:

Jim Randell 8:08 am on 1 August 2025 Permalink | Reply

Jim Randell 6:24 am on 13 July 2025 Permalink | Reply Tags: by: John Owen ( 33 ), flawed

Rate this:

Share:

Jim Randell 8:46 am on 13 July 2025 Permalink | Reply

Frits 11:38 am on 13 July 2025 Permalink | Reply

Jim Randell 11:56 am on 13 July 2025 Permalink | Reply

Frits 12:18 pm on 13 July 2025 Permalink | Reply

Jim Randell 4:19 pm on 13 July 2025 Permalink | Reply

Hugo 10:34 am on 21 July 2025 Permalink | Reply

Jim Randell 7:08 am on 24 November 2024 Permalink | Reply Tags: by: Peter Good ( 27 ), flawed

Rate this:

Share:

Jim Randell 11:25 am on 24 November 2024 Permalink | Reply

Rob Bellis 8:48 am on 26 November 2024 Permalink | Reply

Jim Randell 8:56 am on 26 November 2024 Permalink | Reply

NigelR 5:38 pm on 24 November 2024 Permalink | Reply

Jim Randell 11:12 am on 25 November 2024 Permalink | Reply

Brian Gladman 2:56 pm on 29 November 2024 Permalink | Reply

Jim Randell 3:08 pm on 29 November 2024 Permalink | Reply

Brian Gladman 5:15 pm on 29 November 2024 Permalink | Reply

Frits 11:53 am on 12 December 2024 Permalink | Reply

Frits 10:59 am on 12 December 2024 Permalink | Reply

Jim Randell 10:18 am on 11 September 2024 Permalink | Reply Tags: by: M R Carter ( 2 ), flawed

Rate this:

Share:

Jim Randell 10:20 am on 11 September 2024 Permalink | Reply

Jim Randell 12:52 am on 25 August 2024 Permalink | Reply Tags: by: Victor Bryant ( 140 ), flawed

Rate this:

Share:

Jim Randell 1:30 am on 25 August 2024 Permalink | Reply

Jim Randell 10:27 am on 25 August 2024 Permalink | Reply

Jim Randell 7:26 am on 26 August 2024 Permalink | Reply

Ruud 5:05 pm on 26 August 2024 Permalink | Reply

Frits 12:02 pm on 28 August 2024 Permalink | Reply

Jim Randell 12:09 pm on 28 August 2024 Permalink | Reply

Ruud 1:13 pm on 25 August 2024 Permalink | Reply

Jim Randell 12:29 pm on 5 May 2024 Permalink | Reply Tags: by: G H Dickson ( 13 ), flawed

Rate this:

Share:

Jim Randell 12:30 pm on 5 May 2024 Permalink | Reply

Hugo 3:36 pm on 5 May 2024 Permalink | Reply

Jim Randell 4:45 pm on 5 May 2024 Permalink | Reply

Hugo 7:43 am on 6 May 2024 Permalink | Reply

Jim Randell 4:39 pm on 16 February 2024 Permalink | Reply Tags: by: Howard Williams ( 43 ), flawed

Rate this:

Share:

Jim Randell 4:59 pm on 16 February 2024 Permalink | Reply

Frits 12:31 pm on 17 February 2024 Permalink | Reply

Jim Randell 12:55 pm on 17 February 2024 Permalink | Reply

NigelR 9:35 am on 18 February 2024 Permalink | Reply

Jim Randell 9:53 am on 18 February 2024 Permalink | Reply

NigelR 11:10 am on 18 February 2024 Permalink | Reply

Frits 10:43 am on 18 February 2024 Permalink | Reply

Pete Good 5:40 pm on 19 February 2024 Permalink | Reply

Jim Randell 12:58 pm on 20 February 2024 Permalink | Reply

Jim Randell 8:11 am on 16 January 2026 Permalink | Reply
Tags: by: W S Graff-Baker ( 2 ), flawed

Jim Randell 10:02 am on 11 November 2025 Permalink | Reply
Tags: by: Victor Bryant ( 140 ), flawed

Jim Randell 8:07 am on 1 August 2025 Permalink | Reply
Tags: by: Danny Roth ( 84 ), flawed

Jim Randell 6:24 am on 13 July 2025 Permalink | Reply
Tags: by: John Owen ( 33 ), flawed

Jim Randell 7:08 am on 24 November 2024 Permalink | Reply
Tags: by: Peter Good ( 27 ), flawed

Jim Randell 10:18 am on 11 September 2024 Permalink | Reply
Tags: by: M R Carter ( 2 ), flawed

Jim Randell 12:52 am on 25 August 2024 Permalink | Reply
Tags: by: Victor Bryant ( 140 ), flawed

Jim Randell 12:29 pm on 5 May 2024 Permalink | Reply
Tags: by: G H Dickson ( 13 ), flawed

Jim Randell 4:39 pm on 16 February 2024 Permalink | Reply
Tags: by: Howard Williams ( 43 ), flawed

Jim Randell 9:28 am on 7 September 2023 Permalink | Reply
Tags: by: Andrew Skidmore ( 85 ), flawed

Jim Randell 4:29 pm on 18 August 2023 Permalink | Reply
Tags: by: Mark Valentine ( 17 ), flawed

Jim Randell 4:29 pm on 26 May 2023 Permalink | Reply
Tags: by: Peter Good ( 27 ), flawed

Jim Randell 4:34 pm on 14 April 2023 Permalink | Reply
Tags: by: Edmund Marshall ( 10 ), flawed

Jim Randell 10:12 am on 9 April 2023 Permalink | Reply
Tags: by: Christopher Higgins ( 7 ), by: Hugh Bradley ( 7 ), flawed

Jim Randell 9:14 am on 7 February 2023 Permalink | Reply
Tags: by: Robin Nayler ( 16 ), flawed

Jim Randell 4:29 pm on 6 January 2023 Permalink | Reply
Tags: by: John Owen ( 33 ), flawed