S2T2 | Solving Sunday Times Teasers

Recent Updates Page 44 Toggle Comment Threads | Keyboard Shortcuts

Jim Randell 9:05 am on 4 April 2021 Permalink | Reply
Tags: by: Dr K Ollerenshaw
Brain-Teaser 29: [Mileage dates]
From The Sunday Times, 8th October 1961 [link]

My birthday was on Sunday last. As I drove my car out of the garage in the morning I noticed that the mileage read the same as the date, 11061 or 1.10.61. The car is driven to the station and back twice every day of the year and is used for no other purpose, the total distance each week being exactly 178 miles. By a coincidence the next occasion when the mileage at some time during the day will read the same as the date will be on my husband’s birthday.

When is this?

This puzzle was originally published with no title.

[teaser29]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 9:05 am on 4 April 2021 Permalink | Reply
  This Python program runs in 61ms.
```
from datetime import (date, timedelta)
from enigma import (Rational, sprintf, first, arg, printf)

Q = Rational()  # rational implementation

# find "special" days
def solve():
  m = 11061  # start mileage
  d = date(1961, 10, 1)  # start date
  i = Q(178, 7)  # daily mileage increment
  j = timedelta(days=1)  # daily date increment

  while m < 311299:
    # calculate mileage at the end of the day
    m_ = m + i
    # write the date as a string
    s = sprintf("{dd}{mm}{yy:02d}", dd=d.day, mm=d.month, yy=d.year % 100)
    # turn them integers
    (a, b, x) = map(int, (m, m_, s))
    # is x in [a, b]?
    if a <= x <= b:
      printf("{d}: {x} in [{a}, {b}]")
      yield (d, a, b)
    (m, d) = (m_, d + j)

# find the first n solutions
n = arg(2, 0, int)
first(solve(), n)
```
  Solution: Sunday, 17th June 1962.
  
  There is one more 5-digit mileage that occurs on a “special” day:
  
  21162 on Friday, 2nd November 1962
  
  And then there are three 6-digit mileages that occur on “special” days in the 1990s:
  
  281090 on Sunday, 28th October 1990
  291191 on Friday, 29th November 1991
  301292 on Wednesday, 30th December 1992
  
  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.
Δ
Jim Randell 6:03 pm on 1 April 2021 Permalink | Reply
Tags: by: Howard Williams ( 44 )
Teaser 3054: Discs a go-go
From The Sunday Times, 4th April 2021 [link] [link]

My kitchen floor is tiled with identically-sized equilateral triangle tiles while the floor of the bathroom is tiled with identically-sized regular hexagon tiles, the tiles being less than 1m across. In both cases the gaps between tiles are negligible. After much experimenting I found that a circular disc dropped at random onto either the kitchen or bathroom floor had exactly the same (non-zero) chance of landing on just one tile.

The length of each side of the triangular tiles and the length of each side of the hexagon tiles are both even triangular numbers of mm (i.e., of the form 1+2+3+…).

What are the lengths of the sides of the triangular and hexagonal tiles?

[teaser3054]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Tony Brooke-Taylor, Jim Randell, and Frits are discussing. Toggle Comments
- Jim Randell 9:50 pm on 1 April 2021 Permalink | Reply
  For a disc of radius x dropped randomly onto the floor, the centre of it will lie in one of the tiles and we want to find out if the entire disc lies within the tile. Which it will do if the centre of the disc lies within a smaller version of the tile that has a perimeter that is a distance of x from the perimeter of the actual tile.
  
  If the triangular tiles have a side t, then the area of one tile is: A = (t²√3)/4
  
  And the inradius is: r = t/(2√3)
  
  The radius of the disc cannot be larger than the inradius of the triangle.
  
  So the smaller version of the triangle has an inradius of: (r − x)
  
  And the corresponding area is: a = (3√3)(r − x)²
  
  The probability of the disc landing entirely within a single tile is then: P = a / A
  
  Similarly for a hexagon with side h:
  
  The area of one hexagonal tile is: B = 3(h²√3)/2 (it is composed of 6 equilateral triangles).
  
  And the inradius is: s = h(√3)/2
  
  Again the radius of the disc cannot be larger than the inradius of the hexagon.
  
  We make a smaller hexagon with inradius = (s − x)
  
  And the corresponding area is: b = (2√3)(s − x)²
  
  And the probability of the disc landing entirely within a single tile is: Q = b / B
  
  This is enough to permit a programmed solution.
  
  The following program finds possible sides for the triangular and hexagonal tiles, and then looks for pairs that can be solved to give a disc that makes the probabilities the same.
  
  It runs in 73ms.
  
  Run: [ @replit ]
```
from itertools import product
from enigma import irange, inf, sqrt, fdiv, find_zero, printf

# root 3
r3 = sqrt(3)

# find the radius of a disc that makes the probabilities equal
def solve(t, h):
  # area of a triangular tile
  A = t * t * r3 * 0.25
  r = fdiv(t, 2 * r3)

  # hexagonal tile
  B = h * h * r3 * 1.5
  s = h * r3 * 0.5

  # find the difference between the probabilities
  def f(x):
    a = 3 * r3 * (r - x) ** 2
    b = 2 * r3 * (s - x) ** 2
    P = fdiv(a, A)
    Q = fdiv(b, B)
    return P - Q

  # find a zero of f
  try:
    r = find_zero(f, 1, min(r, s))
  except ValueError:
    return

  # output solution
  printf("t={t}mm h={h}mm [x={r.v:.2f}mm]")

# generate even triangular numbers
def tris(f):
  t = 0
  for i in irange(1, inf):
    t += i
    if t * f > 1000: break
    if t % 2 == 0: yield t

# collect possible sides for the triangular tiles
ts = list(tris(0.5 * r3))

# collect possible sides for the hexagonal tiles
hs = list(tris(r3))

# select t and h, and look for a solution
for (t, h) in product(ts, hs):
  solve(t, h)
```
  Solution: The triangular tiles have sides of 630mm. The hexagonal tiles have sides of 210mm.
  
  A bit more analysis (see below), shows us that the probabilities are the same when the triangular tiles have sides that are 3 times the sides of the hexagonal tiles. And as long as the disc is small enough to fit inside the tiles its size does not matter.
  
  So we are just looking for a pair of even triangular numbers (t, h) where t = 3h, which can be found manually or with a simple program.
  
  LikeLike
  - Jim Randell 8:27 am on 2 April 2021 Permalink | Reply
    [Note: See my next comment for a better way of approach the problem and deriving the relationship between t and h].
    
    Wolfram Alpha [ link ] simplifies the calculation of x to:
    
    x = (√3)ht / (3h + t)
    
    Which gives a faster program:
```
from itertools import product
from enigma import irange, inf, sqrt, fdiv, printf

# root 3
r3 = sqrt(3)

# find the radius of a disc that makes the probabilities equal
def solve(t, h):
  if 3 * h <= t and t <= 3 * h:
    # output solution
    printf("t={t}mm h={h}mm")

# generate even triangular numbers
def tris(f):
  t = 0
  for i in irange(1, inf):
    t += i
    if t * f > 1000: break
    if t % 2 == 0: yield t

# collect possible sides for the triangular tiles
ts = list(tris(0.5 * r3))

# collect possible sides for the hexagonal tiles
hs = list(tris(r3))

# select t and h, and look for a solution
for (t, h) in product(ts, hs):
  solve(t, h)
```
    LikeLike
    - Frits 10:42 am on 2 April 2021 Permalink | Reply
      
      @Jim,
      
      Could you explain the line 9 formula (which actually says if t == 3 * h)?
      
      If we forget about triangular numbers and we choose t=300 and h=100 and a disc so that exactly 3 discs fit in the triangle (touching the sides) do you now say that both chances are not the same?
      
      LikeLike
      - Jim Randell 11:39 am on 2 April 2021 Permalink | Reply
        
        @Frits: It looks like the size of the disc doesn’t matter, as long as t = 3h the probabilities will be the same. I’ll look again at my equations to see why x didn’t drop out. (Line 9 is just a restatement of the inradius conditions).
        
        John Crabtree pointed me towards a better derivation of the relationship:
        
        If the triangular tiles have a side t, then the area of one tile is: A(t) = T⋅t², where T = (√3)/4
        
        And the inradius is: r = t/(2√3), so the disc has a radius less than this: x < r
        
        We make a smaller triangle with inradius = (r − x), it has sides of length: u = (t − 2(√3)x)
        
        If the centre of the disc lands within this triangle the entire disc will be inside the tile.
        
        So the area of this smaller triangle is: A(u) = T⋅u²
        
        And the probability of the disc falling entirely within the triangle (P) is the ratio of these areas:
        
        P = A(u) / A(t) = (u / t)²
        
        If the hexagonal tiles have a side h, then the area of the hexagon is: B(h) = H⋅h², where H = (3/2)(√3) (as it is composed of 6 equilateral triangles).
        
        And the inradius is: s = h(√3)/2, so the radius of the disc is also less than this: x < s
        
        We make a smaller hexagon with inradius = (s − x), it has sides of length: i = (h − 2x/√3), and the area is: B(i)
        
        So the probability of the disc falling entirely within the hexagon (Q) is the ratio of these two areas:
        
        Q = B(i) / B(h) = (i / h)²
        
        The probabilities are equal when their square roots are equal:
        
        P = Q
        → (u / t) = (i / h)
        → i⋅t = h⋅u
        → (h − 2x/√3)t = h(t − 2(√3)x)
        → ht − 2xt/√3 = ht − 2(√3)xh
        → 2xt/√3 = 2(√3)xh
        → t = 3h
        
        Hence the solution is found when t = 3h (and 0 < x < (√3)h/2), and we just need to find two even triangular numbers in the required range, where one is 3 times the other:
        
        from enigma import (irange, inf, sqrt, divf, printf) # max tile size M = divf(2000, sqrt(3)) # collect even triangular numbers ts = set() t = 0 for i in irange(1, inf): t += i if t > M: break if t % 2 == 0: (h, r) = divmod(t, 3) if r == 0 and h in ts: printf("t={t}mm h={h}mm") ts.add(t)
        
        LikeLike
- Frits 9:55 pm on 1 April 2021 Permalink | Reply
  [corrected]
```
# get triangular root
tri = lambda n: 0.5 * ((8 * n + 1) ** 0.5 - 1.0)

# For the same inner circle the side length of the (smallest outer) triangle
# must be three times the side length of the (smallest outer) hexagon.

# check triangular numbers
for i in range(1, 50):
  lHex = (i * (i + 1)) // 2
  lTri = 3 * lHex
 
  # both sides must be even
  if lHex % 2 or lTri % 2: continue
 
  # the tiles being less than 1m across.
  # length across triangle: lTri, length across hexagon: lHex * sqrt(3)
  if lTri > 999:
    break
 
  if tri(3 * lHex) % 1 == 0 :
    print(f"lengths of the sides of the triangular and hexagonal tiles: "
          f"{lTri} mm and {lHex} mm")
```
  LikeLike
  - Jim Randell 10:36 pm on 1 April 2021 Permalink | Reply
    
    @Frits: I don’t think that can be correct, because the answers have to be even numbers (that are also triangular).
    
    LikeLike
    - Frits 10:53 pm on 1 April 2021 Permalink | Reply
      
      @Jim, I didn’t see that (about even).
      
      I calculated that for the same inner circle the side length of the (smallest outer) triangle must be three times the side length of the (smallest outer) hexagon. I hoped that would answer the probability question as well.
      
      LikeLike
- Jim Randell 6:28 pm on 3 April 2021 Permalink | Reply
  
  Another derivation using sectors of a regular n-gon:
  
  For a regular n-gon with a side length of s, we can consider a 1/n sector.
  
  The angle at the centre is 2θ = 360°/n ⇒ θ = 180°/n
  
  And the area of the entire sector is:
  
  A = s² / 4tan(θ)
  
  Reducing the height of the sector by the radius of the disc x gives:
  
  a = (s/2tan(θ) − x)² tan(θ) = (s − 2x tan(θ))² / 4 tan(θ)
  
  And the probability of the disc landing entirely within the complete tile is P = na/nA = a/A
  
  P = ((s − 2x tan(θ)) / s)² = (1 − (2x/s) tan(θ))²
  
  For the triangle tan(θ) = tan(60°) = √3, and the side length is t.
  
  For the hexagon tan(θ) = tan(30°) = 1/√3, and the side length is h.
  
  And the probabilities are equal when:
  
  (2x/t) tan(60°) = (2x/h) tan(30°)
  h tan(60°) = t tan(30°)
  3h = t
  
  Here’s a graphical demonstration of the probabilities when 3h = t.
  
  On the left, the hexagonal tile (green) fits exactly in the triangular tile (red), and we see that if each small triangle has area Z, then the hexagonal tile has an area 6Z and the triangular tile has an area 9Z.
  
  On the right there is also a smaller version of each tile, that is one radius of the disc away from the perimeter of the corresponding actual tile. If the small triangles have area z, then the small version of the hexagonal tile has an area 6z and the small version of the triangular tile has an area of 9z.
  
  The probability then of the disc falling in the hexagonal tile is 6z / 6Z = z/Z, and the probability of the disc falling in the triangular tile is 9z / 9Z = z/Z. Hence the probabilities are the same for each tile.
  
  LikeLike
- Tony Brooke-Taylor 10:03 am on 4 April 2021 Permalink | Reply
  I finally satisfied myself by working in terms of the vertical height of the triangles. Referring to Jim’s first diagram, for the triangular tiles, the vertical height of the inner triangle has the relationship:
  
  Mt’ = Mt-3x
  
  This is because the triangles are congruent and have the same centroid, the centroid being 1/3 of the way along the vertical height.
  
  For each of the six triangles in the hexagon, the inner triangle has vertical height:
  
  Mh’ = Mh-x
  
  This is because we only need to have a border for the circular disc at the outer edge of the hexagon, or the ‘bottom’ of each triangular sector.
  
  The area of each triangle is proportionate to the square of any relevant length, so we can ignore all constants of proportionality and state that:
  
  (Mt’/Mt)^2 = (Mh’/Mh)^2
  
  implies ((Mt-3x)/Mt)^2 = ((Mh-x)/Mh)^2
  
  This condition is satisfied if we make the substitution Mt=3Mh (or just take square roots of each side of the equation and rearrange).
  
  To find the solution, I just looped over possible values for h out of the set of even triangular numbers, setting the limit assuming the ‘across’ distance was measured from flat to flat, like a spanner.
```
h_lim = 1000/3**(1/3)#limit width of a horizontal tile

i_lim = int(((8*h_lim+1)**(1/2)-1)/2)+1#implied limit of possible triangular numbers

result=[h for h in [member for item in [[i*(i+1)/2,(i+2)*(i+1)/2] for i in range(3,i_lim,4)] for member in item] if ((h*24+1)**(1/2)-1)%2==0]

print("The triangles have side",result[0]*3,"mm; the hexagons",result[0],"mm")
```
  LikeLike
Jim Randell 10:02 am on 1 April 2021 Permalink | Reply
Tags: by: Graham Smithers ( 84 )
Teaser 2782: Spiders
From The Sunday Times, 17th January 2016 [link] [link]

Spiders Beth and Sam wake up in the bottom corner of a cuboidal barn (all of whose sides are whole numbers of metres). They want to reach the opposite bottom corner without actually walking across the floor. Beth decides to walk on one of five possible shortest routes, two of them being around the edge of the floor and the other three being over the walls and ceiling. Sam decides instead to spin a web directly to the point on the ceiling diagonally opposite the starting point and then to drop down into the corner. The total length of his journey is within five centimetres of a whole number of metres.

How high is the barn?

[teaser2782]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 10:04 am on 1 April 2021 Permalink | Reply
  Suppose the cuboid barn has dimensions width = x, length = y, height = z (all of which are positive integer values).
  
  The spiders wish to traverse from one corner of the floor to the diagonally opposite corner, but without crossing the floor.
  
  Beth walks along one of the 5 shortest routes (which presumably means that there are 5 shortest routes that have the same distance travelled).
  
  Two of these routes (p1, p2) are along the edges of the floor:
  
  To see the other routes we can “unfold” the barn (imagine it is a cardboard box), and the shortest paths will appear as straight lines.
  
  We get a route that crosses the front, ceiling and left wall (p3):
  
  And routes that cross the right wall, ceiling, back wall (p4), and right wall, ceiling, left wall (p5).
  
  So the following expressions all give the square of the minimal path length:
  
  [p1, p2] (x + y)² = x² + y² + 2xy
  [p5] (x + 2z)² + y² = x² + y² + 4z² + 4xz
  [p3, p4] (x + z)² + (y + z)² = x² + y² + 2z² + 2xz + 2yz
  
  So, given values for x and y, we can calculate z, and then look for diagonals of the cube (= hypot(x, y, z)) that are within 5cm of a whole number of metres, to give Sam’s path.
  
  This Python program runs in 47ms.
  
  Run: [ @replit ]
```
from enigma import (irange, inf, quadratic, hypot, first, arg, printf)

# generate solutions
def solve(verbose=1):

  # consider increasing lengths
  for y in irange(2, inf):
    # and widths
    for x in irange(1, y - 1):
      # compute corresponding z (using p1, p2 & p5)
      for z in quadratic(4, 4 * x, -2 * x * y, domain="Z"):
        if not (z > 0): continue

        # check against p3, p4
        if not ((x + y) ** 2 == (y + z) ** 2 + (x + z) ** 2): continue

        # calculate the length of diagonal through the cuboid
        h = hypot(x, y, z)
        d = abs(h - int(h + 0.5)) 
        # check it is within 5cm of a whole number of metres
        if d > 0.05: continue

        # lengths of paths for Beth and Sam
        (b, s) = (x + y, h + z)
        if verbose:
          printf("z={z} [x={x} y={y}; h={h:.3f} d={d:.3f}, beth={b} sam={s:.3f}]")

        yield (x, y, z)

# find the first n solutions
n = arg(1, 0, int)
first(solve(), n)
```
  Solution: The barn in 4 metres high.
  
  In fact there is a family of solutions, the program stops after the first (smallest) solution, which is the only reasonable one, where the barn is less 25m high (and the spiders journeys are each less than 100m).
  
  Analytically:
  
  Equating the sum of the first two of the expressions with twice the third, we get:
  
  2x² + 2y² + 4z² + 2xy + 4xz = 2x² + 2y² + 4z² + 4xz + 4yz
  2xy = 4yz
  x = 2z
  
  Then, substituting for x in the first 2 expressions, and equating them:
  
  4z² + y² + 4yz = 16z² + y²
  4yz = 12z²
  y = 3z
  
  Hence the barn has dimensions (2z, 3z, z), and the shortest paths have length 5z.
  
  The diagonal across the barn is: √(x² + y² + z²) = √(14z²) = (√14)z.
  
  And we want to know when this is within 5cm if a whole number of metres.
  
  Here is a shorter and faster program to generate solutions:
  
  Run [ @replit ]
```
from enigma import (irange, inf, sqrt, first, arg, printf)

def solve():
  r14 = sqrt(14)

  for z in irange(1, inf):
    h = z * r14
    d = abs(h - int(h + 0.5))
    if d > 0.05: continue

    (x, y) = (2 * z, 3 * z)
    (b, s) = (x + y, h + z)
    printf("z={z} [x={x} y={y}; h={h:.3f} d={d:.3f}; beth={b} sam={s:.3f}]")

    yield (x, y, z)

# find the first n solutions
n = arg(1, 0, int)
first(solve(), n)
```
  LikeLike

Jim Randell 11:29 am on 30 March 2021 Permalink | Reply
Tags: by: Brig A G H Brousson ( 2 )

Brain-Teaser 730: Miss Brain-Teaser

From The Sunday Times, 13th July 1975 [link]

Five girls entered our Village Beauty Contest. Each of the five judges had to put them into a definite order and then allot fifteen marks between them. The aggregate marks for each girl decided the issue. The judges each gave a different maximum mark and also chose a different girl to be top. No girl had two identical marks in her score.

Joe gave the maximum possible to Rose, and he placed Gwen above Linda. Tom gave Ann one more than Sam did. Pam had no zero in her score and although she finished ahead of Rose she didn’t win. Ann scored the only five that was allotted. Dan placed the girls as closely together as he could.

The judge who put Gwen first put Rose last. Brian succeeded in putting them all in their correct final order.

Who won, and what were her individual marks from each judge?

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

[teaser730]

Jim Randell 11:30 am on 30 March 2021 Permalink | Reply

I think this one is easier to do with a bit of scribbling on the back of an envelope.

But here is a Python program that solves the puzzle in 851ms.

The program groups together the possible sets of scores by the maximum number of marks given. And then selects scores that give a different maximum for each judge. We know Joe gives the absolute maximum, and Dan gives scores that as close together as possible. The distribution of scores is chosen such that no contestant receives the same number of marks from two judges. And then we check the other conditions as we go along.

Run: [ @replit ]

from enigma import (irange, group, Accumulator, diff, update, flatten, tuples, seq_all_different, find, map2str, printf)

# labels for the contestants, and number of contestants (N)
(A, G, L, P, R, N) = irange(0, 5)

# decompose <t> into <k> increasing numbers, minimum <m>
def decompose(t, k, m=0, ns=[]):
  if k == 1:
    if not (t < m):
      yield ns + [t]
  else:
    k_ = k - 1
    for n in irange(m, t - k_ * m):
      yield from decompose(t - n, k_, n + 1, ns + [n])

# collect possible scores, by maximum marks given
scores = group(decompose(15, N), by=max)

# find scores containing the minimim possible difference (for Dan)
r = Accumulator(fn=min, collect=1)
for s in flatten(scores.values()):
  r.accumulate_data(max(b - a for (a, b) in tuples(s, 2)), s)
mds = r.data

# check a (partial) collection of scores
def check(*ss):
  # consider the scores for the judges:
  # each judge places a different contestant first
  fs = set()
  for s in ss:
    f = s.index(max(s))
    if f in fs: return
    # G first -> R last
    if f == G and s.index(min(s)) != R: return
    fs.add(f)
  # consider the scores for the contestants:
  for (i, s) in enumerate(zip(*ss)):
    # A scores the only 5
    if i == A and len(s) == N and 5 not in s: return
    if i > A and 5 in s: return
    # P has no zeros
    if i == P and 0 in s: return
  # looks OK
  return 1

# empty scores
s0 = [None] * N

# generate scores with max marks in <mms>
# <f5> current value of the 5 flag
def generate(mms, f5):
  for (k, vs) in scores.items():
    if k in mms:
      for ss in vs:
        # is a 5 involved?
        s5 = (5 in ss)
        if not (f5 + s5 > 1):
          yield (k, s5, ss)

# assign marks <ms> to score <s> starting at index <k>, respecting <gs>
def _assign(s, gs, ms, k=0):
  # are we done?
  if not ms:
    yield s
  elif s[k] is not None:
    yield from _assign(s, gs, ms, k + 1)
  else:
    # fill out index k
    for (i, v) in enumerate(ms):
      if v not in gs[k]:
        yield from _assign(update(s, [(k, v)]), gs, ms[:i] + ms[i + 1:], k + 1)

# assign marks <ms>, respecting (i, v) pairs, and current sequences <ss>
def assign(ms, ss, ivs=()):
  # find current marks per contestant
  gs = (list(zip(*ss)) if ss else [[]] * N)
  # assign any given values
  s = list(s0)
  for (i, v) in ivs:
    if v in gs[i]: return
    s[i] = v
  # and fill out remaining values
  yield from _assign(s, gs, diff(ms, s))

# select marks for Joe, must include the maximum possible score
mxj = max(scores.keys())
for (_, j5, js) in generate([mxj], 0):
  # Joe gave the max score to R
  for J in assign(diff(js, [mxj]), [], [(R, mxj)]):
    # Joe gave G more marks than L
    if not (J[G] > J[L]): continue
    if not check(J): continue

    # select marks for Dan, as close together as possible
    for ds in mds:
      mxd = max(ds)
      if mxd == mxj: continue
      # is a 5 involved?
      d5 = (5 in ds)
      if j5 + d5 > 1: continue
      for D in assign(ds, [J]):
        if not check(J, D): continue

        # select marks for Sam
        kss = diff(scores.keys(), {mxj, mxd})
        for (mxs, s5, ss) in generate(kss, j5 + d5):
          for S in assign(ss, [J, D]):
            if not check(J, D, S): continue

            # select marks for Tom
            kst = diff(kss, [mxs])
            for (mxt, t5, ts) in generate(kst, j5 + d5 + s5):
              # Tom gave A 1 point more than Sam
              i = find(ts, S[A] + 1)
              if i == -1: continue
              for T in assign(diff(ts, [ts[i]]), [J, D, S], [(A, ts[i])]):
                if not check(J, D, S, T): continue

                # select marks for Brian
                ksb = diff(kst, [mxt])
                for (mxb, b5, bs) in generate(ksb, j5 + d5 + s5 + t5):
                  if d5 + j5 + s5 + t5 + b5 != 1: continue
                  for B in assign(bs, [J, D, S, T]):
                    if not check(J, D, S, T, B): continue

                    # find the totals for the contestants
                    pts = list(sum(s) for s in zip(J, D, S, T, B))
                    if not seq_all_different(pts): continue
                    # P finished ahead of R, but didn't win
                    if not (pts[P] > pts[R] and pts[P] != max(pts)): continue

                    # Brian chose the correct order
                    order = lambda s: sorted(irange(N), key=(lambda i: s[i]), reverse=1)
                    pos = order(pts)
                    if not (order(B) == pos): continue

                    # output solution
                    w = pos[0]
                    ws = tuple(x[w] for x in [J, D, S, T, B])
                    printf("winner={w} {ws}\n\n    A  G  L  P  R\n J={J}\n D={D}\n S={S}\n T={T}\n B={B}\n",
                      w="AGLPR"[w], ws=map2str(zip("JDSTB", ws)),
                    )

Solution: Linda won. Her marks were: Joe = 0, Dan = 3, Sam = 4, Tom = 2, Brian = 8.

The full scores are:

1st: Linda = 17; (J = 0, D = 3, S = 4, T = 2, B = 8)
2nd: Pam = 16; (J = 3, D = 2, S = 1, T = 6, B = 4)
3rd: Rose = 15; (J = 9, D = 1, S = 0, T = 3, B = 2)
4th: Gwen = 14; (J = 2, D = 4, S = 7, T = 0, B = 1)
5th: Ann = 13; (J = 1, D = 5, S = 3, T = 4, B = 0)

LikeLike

Frits 1:52 pm on 30 March 2021 Permalink | Reply

Wow, 142 lines of code.

LikeLike

Jim Randell 4:25 pm on 31 March 2021 Permalink | Reply

With a bit of analysis we can get a neater program (although it’s not really any faster – I timed it at 805ms, so it is still under a second).

Looking at the decompositions of 15 into 5 different numbers we see that the maximum possible mark in any decomposition is 9, and there is only one decomposition corresponding to this maximum, so Joe’s marks must be (in some order):

0, 1, 2, 3, 9

Similarly there is only one decomposition where the marks are consecutive, so this must be Dan’s:

1, 2, 3, 4, 5

So Dan gives out the only 5 (to Ann), and that is his maximum mark. This means we know where the 5 is, and don’t have to worry about tracking it in the code.

And for the three remaining judges they must give maximum marks of 6, 7, 8 and for each maximum there is only one decomposition for each that does not include 5. So the marks from the remaining judges (Sam, Tom and Brian) are (in some order):

0, 2, 3, 4, 6
0, 1, 3, 4, 7
0, 1, 2, 4, 8

The following program awards Joe’s 9 to Rose, and Dan’s 5 to Ann and fills out the remaining marks recursively.

Run: [ @replit ]

from itertools import permutations
from enigma import (irange, diff, update, seq_all_different, map2str, printf)

# available scores (highest to lowest)
# each sums to 15, and has a different max
score = [
  (9, 3, 2, 1, 0),  # this is J's
  (5, 4, 3, 2, 1),  # this is D's
  (8, 4, 2, 1, 0),
  (7, 4, 3, 1, 0),
  (6, 4, 3, 2, 0),
]
# indices for BST (we don't know which is which, yet)
BST = (2, 3, 4)

# labels for the contestants (and number of contestants)
girls = (A, G, L, P, R) = (0, 1, 2, 3, 4)
N = 5

# check map <m>, up to row <k>
def check(m, k, gs):
  mk = m[k]
  # P has no zeros
  if mk[P] == 0: return
  s = score[k]
  # if G is first, R must be last
  if mk[G] == s[0] and mk[R] != s[4]: return
  if k == 0:
    # check for Joe: G > L
    if not (mk[G] > mk[L]): return
  else:
    # no girl recieves the same mark from 2 different judges
    if any(x in y for (x, y) in zip(mk, gs)): return
  # looks OK
  return 1

# associate with each score: m[score-index][contestant] = marks
# <gs> = marks for each contestant so far
# <fs> = contestants that have been awarded a judges highest mark
def solve(m, k=0, gs=[[]] * N, fs=[]):
  # are we done?
  if k == N:
    yield (m, gs)
  else:
    # consider possibilities for score k
    mk = m[k]
    s = score[k]
    mx = max(s)
    # find assigned contestants
    cs = set(i for i in girls if mk[i] is None)
    # map the unassigned scores to the unassigned contestants
    for ms in permutations(diff(s, mk)):
      # make the updated row
      mk_ = update(mk, cs, ms)
      # check the highest score is to a new contestant
      f = mk_.index(mx)
      if f in fs: continue
      # update the map
      m_ = update(m, [(k, mk_)])
      if not check(m_, k, gs): continue
      gs_ = list(xs + [x] for (xs, x) in zip(gs, mk_))
      yield from solve(m_, k + 1, gs_, fs + [f])

# initial map
m0 = list([None] * N for _ in irange(N))
m0[0][R] = 9  # J's highest score goes to R
m0[1][A] = 5  # D's 5 goes to A

# order girls by scores <s> (highest to lowest)
order = lambda s: sorted(girls, key=(lambda g: s[g]), reverse=1)

# consider possible completed maps
for (m, gs) in solve(m0):
  # calculate the total score for each contestant
  pts = list(sum(g) for g in gs)
  if not seq_all_different(pts): continue
  # P finished ahead of R, but didn't win
  if not (pts[P] > pts[R] and pts[P] != max(pts)): continue  
  pos = order(pts)
  # Brian placed the girls in the correct order
  for B in BST:
    if order(m[B]) != pos: continue
    # Tom gave 1 more point to A than Sam
    for (S, T) in permutations(diff(BST, [B])):
      if m[S][A] + 1 != m[T][A]: continue
      # output solution
      w = pos[0]
      ws = tuple(x[w] for x in m)
      js = update("JD???", (B, S, T), "BST")
      printf("winner = {w} {ws}\n\n    A  G  L  P  R\n {m}\n",
        w="AGLPR"[w], ws=map2str(zip(js, ws)), m=map2str(zip(js, m), sep="\n ", enc=""),
      )

In my first program I wrote the [[ assign() ]] stuff to avoid permutations that would fail (which did make it run a bit faster). I didn’t bother for this program.

LikeLike

Frits 12:42 pm on 31 March 2021 Permalink | Reply

Use denest=1 if not running with PyPy.

It would be nice if an intermediate assignment could be added to SubstitutedExpression (for the sumcols list). It is now calculated multiple times.

from enigma import SubstitutedExpression

'''    An Gw Li Pa Ro
  Joe=[A  B  C  D  E]
  Dan=[F  G  H  I  J]
  Sam=[K  L  M  N  O]
  Tom=[P  Q  R  S  T]
Brian=[U  V  W  X  Y] 
''' 

# column totals
sumcols = lambda s: list(map(sum, zip(*s)))

# are list a and b ordered the same?
def same_order(a, b):
  s1 = sorted((x, i) for i, x in enumerate(a))
  s2 = sorted((x, i) for i, x in enumerate(b))
  return all(x[1] == y[1] for x, y in zip(s1, s2))

# the alphametic puzzle
p = SubstitutedExpression(
  [
  # row totals must be 15, choose RHS the variable with the most candidates
  "15 - (A + C + D + E) = B",
  "15 - (F + G + I + J) = H",
  "15 - (K + L + N + O) = M",
  "15 - (P + Q + S + T) = R",
  "15 - (U + V + X + Y) = W",
 
  # Joe placed Gwen above Linda.
  "B > C",
 
  # Dan placed the girls as closely together as he could
  # Dan's scores has to involve a 5 and may not include maximums 6, 7, 8 or 9
  "sorted([G, H, I, J]) == [1, 2, 3, 4]",
 
  # the judge who put Gwen first put Rose last.
  "L != max([K, L, M, N, O]) or O == min([K, L, M, N, O])",
  "Q != max([P, Q, R, S, T]) or T == min([P, Q, R, S, T])",
  "V != max([U, V, W, X, Y]) or Y == min([U, V, W, X, Y])",

  # Tom gave Ann one more than Sam did.
  "K + 1 = P",
 
  # Pam finished ahead of Rose
  "sum([D, I, N, S, X]) > sum([E, J, O, T, Y])",

  # the judges each gave a different maximum mark
  "len(set([9, 5, max([K,L,M,N,O]), max([P,Q,R,S,T]), \
            max([U,V,W,X,Y])])) == 5",
 
  # the judges chose a different girl to be top (Dan in col 0, Joe in col 4)
  "len(set([0, 4, \
  [i for i, x in enumerate([K,L,M,N,O]) if x == max([K,L,M,N,O])][0],\
  [i for i, x in enumerate([P,Q,R,S,T]) if x == max([P,Q,R,S,T])][0],\
  [i for i, x in enumerate([U,V,W,X,Y]) if x == max([U,V,W,X,Y])][0]])) == 5",

  # the aggregate marks for each girl decided the issue
  "len(set(sumcols([[A,B,C,D,E], [F,G,H,I,J], [K,L,M,N,O], [P,Q,R,S,T], \
                    [U,V,W,X,Y]]))) == 5",
 
  # Pam didn't win
  "max(enumerate(sumcols([[A,B,C,D,E], [F,G,H,I,J], [K,L,M,N,O], \
      [P,Q,R,S,T], [U,V,W,X,Y]])), key=(lambda x: x[1]))[0] != 3",
                         
  # Brian succeeded in putting them all in their correct final order
  "same_order(sumcols([[A,B,C,D,E], [F,G,H,I,J], [K,L,M,N,O], [P,Q,R,S,T], \
                       [U,V,W,X,Y]]), [U,V,W,X,Y])",
  ],
  answer="[A,B,C,D,E], [F,G,H,I,J], [K,L,M,N,O], [P,Q,R,S,T], [U,V,W,X,Y],\
          max(enumerate(sumcols([[A,B,C,D,E], [F,G,H,I,J], [K,L,M,N,O], \
                       [P,Q,R,S,T], [U,V,W,X,Y]])), key=(lambda x: x[1]))[0]",
  # no girl had two identical marks in her score
  distinct=("ABCDE", "FGHIJ", "KLMNO", "PQRST", "UVWXY",
            "AFKPU", "BGLQV", "CHMRW", "DINSX", "EJOTY" ),
  env=dict(sumcols=sumcols, same_order=same_order),
  # Pam had no zero in her score, Joe gave maximum to Rose (E = 9)
  # Ann scored the only five (in first column, F = 5))
  # first and last column may not contain maximums 6, 7 and 8
  s2d=dict(E=9, F=5),
  digits=(0, 1, 2, 3, 4, 6, 7, 8),     # remaining digits
  d2i=dict([(0, "EFGHJBPDINSX")] +
       [(k, "EF") for k in range(1, 4)] +
       [(4, "EFJOTYK")] +
       [(k, "FGHIJEOTYAKPU") for k in range(6, 8)] +
       [(8, "FGHIJEOTYKAPUC")]),
  denest=1,      # use denest=1 if not run with PyPy
  verbose=0
)

judges = ["Joe", "Dan", "Sam", "Tom", "Brian"]
girls = ["Agnes", "Gwen", "Linda", "Pam", "Rose"]

for (_, ans) in p.solve():
  print(girls[ans[-1]], "has won")
  print(*[judges[i] + ": " + str(x[ans[-1]]) for i, x in enumerate(ans[:-1])])

LikeLike

Frits 1:29 pm on 31 March 2021 Permalink | Reply

Faster than Jim’s program with PyPy but slower with Python 3.9.2.

from itertools import permutations

# do all columns have different values in the multidimensional array <s> ?
diffcols = lambda s: all(len(set(c)) == len(c) for c in list(zip(*s)))

# are list a and b ordered the same?
def same_order(a, b):
  s1 = sorted((x, i) for i, x in enumerate(a))
  s2 = sorted((x, i) for i, x in enumerate(b))
  return all(x[1] == y[1] for x, y in zip(s1, s2))
  
# decompose <t> into <k> increasing numbers, minimum <m>
def decompose(t, k, m=0, ns=[]):
  if k == 1:
    if not(t < m):
      yield ns + [t]
  else:
    k_ = k - 1
    for n in range(m, t + 1 - k_ * m):
      yield from decompose(t - n, k_, n + 1, ns + [n])
      
def check(s, mult, m, ind, imult):
  if ind in imult:           # the judges chose a different girl to be top
    return False 
 
  if sum(x[0] == 5 for x in mult) > 1: # Ann scored the only five
    return False
  
  if s[1] == m and s[4] != min(s): # the judge who put Gwen first put Rose last
    return False
  
  if not diffcols(mult):     # no girl had two identical marks in her score
    return False 
  
  return True

judges = ["Joe", "Dan", "Sam", "Tom", "Brian"]
girls = ["Agnes", "Gwen", "Linda", "Pam", "Rose"]
scores = list(x for y in [list(permutations(s)) for s in decompose(15, 5)] 
              for x in y)

# Ann scored the only five. Pam had no zero in her score
scores = [x for x in scores if 5 not in x[1:] and 9 not in x[:4] and x[3] != 0]
scores9 = [x for x in scores if x[4] == 9]
scoresnot9 = [(x, max(x)) for x in scores if x[4] != 9]

for D in [x[0] for x in scoresnot9]:
  # Dan placed the girls as closely together as he could
  s = sorted(D)
  if not all(y == (x + 1) for (x, y) in list(zip(s, s[1:]))): continue
  
  mD = max(D)
  # the judge who put Gwen first put Rose last
  if D[1] == mD and D[4] != min(D): continue
  iD = D.index(mD)
  
  for J in scores9:                       # Joe gave maximum to Rose
    iJ = 4                                # last position
    if iJ == iD: continue
    if J[1] < J[2]: continue              # Joe placed Gwen above Linda
    if not diffcols([D, J]): continue     # no identical marks per girl
    
    for S in [x[0] for x in scoresnot9 if x[1] not in {mD}]:
      mS = max(S)
      iS = S.index(mS)
      if not check(S, [D, J, S], mS, iS, {iD, iJ}): continue 
                   
      for T in [x[0] for x in scoresnot9 if x[1] not in {mD, mS}]:            
        if T[0] != S[0] + 1: continue     # Tom gave Ann one more than Sam
        
        mT = max(T)
        iT = T.index(mT)
        if not check(T, [D, J, S, T], mT, iT, {iD, iJ, iS}): continue 
        
        for B in [x[0] for x in scoresnot9 if x[1] not in {mD, mS, mT}]:  
          mB = max(B)
          iB = B.index(mB)
          if not check(B, [D, J, S, T, B], mB, iB, {iD, iJ, iS, iT}): continue 
         
          sumcols = list(map(sum, zip(D, J, S, T, B)))
          if len(set(sumcols)) != 5: continue  # totals must be different
          
          winning = max(sumcols)
          # Pam finished ahead of Rose but she didn’t win.
          if sumcols[3] < sumcols[4] or sumcols[3] == winning: continue

          # Brian succeeded in putting them all in their correct final order
          if not same_order(sumcols, B): continue
          
          # Ann scored the only five 
          if [J[0], D[0], S[0], T[0], B[0]].count(5) != 1: 
            continue
          
          ind = sumcols.index(winning)
          print(girls[ind], "has won")
          print(*[judges[i] + ": " + str(x[ind]) 
                  for i, x in enumerate([J, D, S, T, B])])

LikeLike

Jim Randell 7:03 pm on 31 March 2021 Permalink | Reply

Here is a solution that uses the analysis given above to determine the five sets of scores (but not the orderings of the sets), and then using the [[ SubstitutedExpression() ]] solver from the enigma.py library to find candidate solutions, followed by a check of the remaining conditions. It runs in 208ms.

Run: [ @replit ]

from enigma import (
  SubstitutedExpression, join, encl, seq_all_different, subsets, update, map2str, printf
)

SubstitutedExpression.set_default(denest=-1, verbose=0)

#      ann gwe lin pam ros
# joe:  A   B   C   D   E   += 15 
# dan:  F   G   H   I   J   += 15
# xxx:  K   L   M   N   P   += 15
# yyy:  Q   R   S   T   U   += 15
# zzz:  V   W   X   Y   Z   += 15

# marks from the judges
(joe, dan, xxx, yyy, zzz) = ("ABCDE", "FGHIJ", "KLMNP", "QRSTU", "VWXYZ")
# marks for the contestants
(ann, gwe, lin, pam, ros) = ("AFKQV", "BGLRW", "CHMSX", "DINTY", "EJPUZ")
# indices for top girls
tops = "abcde"

xset = lambda x: join(x, fn=encl, sep=", ", enc="{}")
xseq = lambda x: join(x, fn=encl, sep=", ", enc="()")
xsum = lambda x: join(x, fn=encl, sep=" + ", enc="()")

top = lambda t: t.index(max(t))

p = SubstitutedExpression(
  [
    # we know the marks from each judge (but not the order)
    f"{xset(joe)} == {{0, 1, 2, 3, 9}}",
    f"{xset(dan)} == {{1, 2, 3, 4, 5}}",
    f"{xset(xxx)} == {{0, 1, 2, 4, 8}}",
    f"{xset(yyy)} == {{0, 1, 3, 4, 7}}",
    f"{xset(zzz)} == {{0, 2, 3, 4, 6}}",

    # Joe placed G above L
    "B > C",

    # P finished ahead of R ...
    f"{xsum(pam)} > {xsum(ros)}",

    # ... but didn't win
    f"{xsum(pam)} < max({xsum(gwe)}, {xsum(lin)}, {xsum(ann)})",

    # each judge chose a different top girl
    f"top({xseq(joe)}) = {{a}}",
    f"top({xseq(dan)}) = {{b}}",
    f"top({xseq(xxx)}) = {{c}}",
    f"top({xseq(yyy)}) = {{d}}",
    f"top({xseq(zzz)}) = {{e}}",

    # whichever of xxx, yyy, zzz placed G top, also placed R bottom
    f"implies(max({xseq(xxx)}) == {{L}}, min({xseq(xxx)}) == {{P}})",
    f"implies(max({xseq(yyy)}) == {{R}}, min({xseq(yyy)}) == {{U}})",
    f"implies(max({xseq(zzz)}) == {{W}}, min({xseq(xxx)}) == {{Z}})",
  ],

  # each judge allocates different marks to each girl
  # no girl had the same marks from different judges
  distinct=(joe, dan, xxx, yyy, zzz, ros, gwe, lin, ann, pam, tops),

  # Joe gave 9 to R; Dan gave 5 to A
  s2d=dict(E=9, F=5),

  # so the remaining digits are...
  digits=(0, 1, 2, 3, 4, 6, 7, 8),

  # P had no 0 from any judge ...
  d2i={
    0: pam + dan,
    1: zzz,
    2: yyy,
    3: xxx,
    4: joe,
    6: joe + dan + xxx + yyy + tops,
    7: joe + dan + xxx + zzz + tops,
    8: joe + dan + yyy + zzz + tops,
  },
  
  env=dict(top=top),
)

# order of contestants
girls = (A, G, L, P, R) = (0, 1, 2, 3, 4)

# order girls by scores <s> (highest to lowest)
order = lambda s: sorted(girls, key=(lambda g: s[g]), reverse=1)

# check a candidate solution
def check(s):
  # calcuate the total score for each contestant
  ms = list(list(s[x] for x in xs) for xs in (ann, gwe, lin, pam, ros))
  pts = list(sum(m) for m in ms)
  if not seq_all_different(pts): return
  pos = order(pts)
  # assign xxx, yyy, zzz to B, S, T
  BST = (xxx, yyy, zzz)
  for (B, S, T) in subsets(BST, size=len, select="P"):
    # Tom gave 1 more point to A than Sam
    if s[S[A]] + 1 != s[T[A]]: continue
    # Brian placed the girls in the correct order
    if order(list(s[x] for x in B)) != pos: continue

    # output solution
    w = pos[0]
    ws = ms[w]
    js = "JD" + update("???", (BST.index(x) for x in (B, S, T)), "BST")
    ss = list(list(s[x] for x in xs) for xs in (joe, dan, xxx, yyy, zzz))
    printf("winner = {w} {ws}\n\n    A  G  L  P  R\n {m}\n",
      w="RGLAP"[w], ws=map2str(zip(js, ws)), m=map2str(zip(js, ss), sep="\n ", enc=""),
    )

# run the solver
p.run(check=check)

LikeLike

Jim Randell 9:05 am on 29 March 2021 Permalink | Reply
Tags: by: L. J. Upton
Brainteaser 1040: An uncommon number
From The Sunday Times, 4th July 1982 [link]

Your problem this week is to find an unusual nine-digit number. It comprises the digits from 1 to 9, in some order, each used once and only once.

The number formed by the first digit (reading from the left) is exactly divisible by 1 (which doesn’t tell you a lot!), the number formed by the first two digits is exactly divisible by 2, that formed by the first three digits is exactly divisible by 3, and so on, which the number formed by the first eight digits being divisible by 8, and with the complete number of nine digits being divisible by 9.

It is perhaps surprising that such a number exists, and even more surprising that is should be unique.

What is the number?

This puzzle is included in the books Microteasers (1986) and The Sunday Times Book of Brainteasers (1994).

[teaser1040]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 9:06 am on 29 March 2021 Permalink | Reply
  
  This puzzle has also appeared recently as Puzzle #102, Teaser 3053.
  
  See my comment on Enigmatic Code for the solution.
  
  Here are the results for an n-digit (decimal) number, consisting of some arrangement of the digits 1..n, such that the leftmost k digits are divisible by k, for k = 1..n:
  
  [1] = 1
  [1..2] = 12
  [1..3] = 123; 321
  [1..4] = none
  [1..5] = none
  [1..6] = 123654; 321654
  [1..7] = none
  [1..8] = 38165472
  [1..9] = 381654729
  [1..0] = 3816547290
  
  And taking the final entry, a 10-digit number in base 10, using all 10 digits, such that the leftmost k digits are divisible by k, for k = 1..10; we can extend this to other bases:
  
  base 2: 10
  base 4: 1230; 3210
  base 6: 143250; 543210
  base 8: 32541670; 52347610; 56743210
  base 10: 3816547290
  base 12: none
  base 14: 9C3A5476B812D0
  base 16-30: none
  
  (see: OEIS A11456 [ @oeis ]).
  
  LikeLike
  - Jim Randell 6:01 pm on 29 March 2021 Permalink | Reply
    And if we drop the requirement that digits cannot be reused, we can see that any left prefix of a polydivisible number [ @wikipedia ] must also be polydivisible.
    
    This program generates all possible polydivisible numbers in a given base (and with a given set of digits):
```
from enigma import (irange, int2base, args, printf)

ds = args([10], 0, int)
base = ds.pop(0)
if not ds: ds = list(irange(base))
printf("[base = {base}; digits = {ds}]")

(k, ns) = (1, list(ds))
while ns:
  (k_, ns_) = (k + 1, list())
  
  for n in ns:
    # output current numbers
    printf("{k} -> {n}", n=int2base(n, base=base))
    # can we extend this number?
    if n > 0:
      for d in ds:
        n_ = base * n + d
        if n_ % k_ == 0:
          ns_.append(n_)

  (k, ns) = (k_, ns_)
```
    And we find that the longest base 10 polydivisible number, using the digits 0-9 (although 1 and 9 do not appear), has 25 digits:
    
    3608528850368400786036725
    
    In base 16 there are 3 maximal length (39-digit) polydivisible numbers:
    
    34E4A468166CD8604EC0F8106AB4326098286CF;
    AA44CE207C78FC30003C3CC0D8382E2078D07EF;
    FAE06678C2E884607EB8B4E0B0A0F0603420342
    
    LikeLike
Jim Randell 8:57 am on 28 March 2021 Permalink | Reply
Tags: by: Ptolemaeus ( 5 )
Brain-Teaser 28: Army squares
From The Sunday Times, 1st October 1961 [link]

Kublis Ghen was very particular about his army formations. Originally, each company consisted of a certain number of men who could be drawn up in the form of a perfect square. Nor was this all, for when the companies were drawn up one behind the other (each company being spread out to form a single row) the entire army itself thus constituted a square. It was an army to be proud of, but when the great conqueror determined to attack Thalbazzar he was not content, and summoned his chief of staff: “My army is not big enough”, he declared. “Double it”.

Knowing the temper of his master, the chief of staff saw to it that the size of the army was doubled — exactly. But an unforeseen difficulty arose: the army could no longer form a perfect square — there was just one man too many.

“Kill him”, ordered the conqueror on hearing the news, and the offending supernumerary was duly dispatched, so that the army marched into battle in the form of a square though, of course, its company formations had been completely disorganised.

A million men did Kublis Ghen
Against Thalbazzar thow;

says the poet, but that is an exaggeration.

How many men were in the army that Kublis Ghen threw against Thalbazzar?

[teaser28]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
John Crabtree and Jim Randell are discussing. Toggle Comments
- Jim Randell 8:58 am on 28 March 2021 Permalink | Reply
  If there are k² men in a company, then in order to form a square when each company is in a line there must be as many companies as there are men in a company. So (k²)² men in total.
  
  When the army size is doubled, the remaining number is 1 more than a square:
  
  2(k^4) − 1 = n^2
  
  We can consider possible values of k until (2(k^4) − 1) exceeds 1 million (at k = 27).
  
  This Python program runs in 49ms.
  
  Run: [ @replit ]
```
from enigma import (irange, inf, is_square, printf)

# consider k values
for k in irange(1, inf):
  n = 2 * pow(k, 4) - 1
  if n > 1000000: break
  if is_square(n):
    printf("k={k} -> n={n}")
```
  Solution: There were 57121 men in the army marching into battle.
  
  Each company consisted of 13² = 169 men, which could be formed into a 13×13 square or a 1×169 line.
  
  The 169 companies can then be formed into a 169×169 square = 28561 men in total.
  
  The army size is doubled to 57122 = 239² + 1. And one of these is removed.
  
  So, the army of 57121 men marched into battle as a 239×239 square.
  
  LikeLike
- John Crabtree 4:34 pm on 30 March 2021 Permalink | Reply
  
  2x^2 = y^2 + 1 where x is square. y/x is an approximation to sqrt(2).
  For 2x^2 = y^2 +/- 1, y/x = 1/1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985 etc
  x(k) = x(k-1) + y(k-1). and y(k) = 2 * x(k-1) + y(k-1).
  169 = 13^2, and so there were 239^2 = 57121 men in the army.
  As a check, 2 * 169^2 = 239^2 + 1
  
  LikeLike
Jim Randell 5:01 pm on 26 March 2021 Permalink | Reply
Tags: by: Danny Roth ( 87 )
Teaser 3053: Endless number
From The Sunday Times, 28th March 2021 [link] [link]

George and Martha have a telephone number consisting of nine digits; there is no zero and the others appear once each. The total of the digits is obviously 45, so that the number is divisible by nine. Martha noticed that, if she removed the last (i.e., the least significant) digit, an eight-digit number would remain, divisible by eight. George added that you could continue this process, removing the least significant digit each time to be left with an n-digit number divisible by n right down to the end.

What is their telephone number?

[teaser3053]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Dirk, GeoffR, Hugh Casement, and 3 others are discussing. Toggle Comments
- Jim Randell 5:04 pm on 26 March 2021 Permalink | Reply
  See also: Enigma 339b, Enigma 1643, Enigma 1667, and the recently posed Puzzle #102.
  
  Here’s a solution using the [[ SubstitutedExpression ]] solver from the enigma.py library. It runs in 96ms.
```
#! python3 -m enigma -rr

SubstitutedExpression

--digits="1-9"

"ABCDEFGH % 8 = 0"
"ABCDEFG % 7 = 0"
"ABCDEF % 6 = 0"
"ABCDE % 5 = 0"
"ABCD % 4 = 0"
"ABC % 3 = 0"
"AB % 2 = 0"

--answer="ABCDEFGHI"
```
  Solution: The number is 381654729.
  
  LikeLike
- Frits 10:40 pm on 26 March 2021 Permalink | Reply
  Tested in a Python online editor.
```
from itertools import permutations

print(*["".join(x) for x in permutations("123456789")
      if all(int("".join(x[:i])) % i == 0 for i in range(2, 9))])
```
  LikeLike
  - Tony Brooke-Taylor 9:02 pm on 28 March 2021 Permalink | Reply
    I used a few shortcuts with the aim of minimising wasted iterations. Running my code on Replit takes about 3.5ms, compared with 1.13s for Frits’ sledgehammer approach. On the other hand, mine takes a few more lines!
    
    Hope I manage to paste this in an appropriate format:
```
evens=list(range(2,9,2))
Xs=list(range(2,9,4))
odds=list(range(1,10,2))
odds.remove(5)

#Exploit the fact that the three-digit and six-digit numbers must be divisible by 3, and that the 6-digit number can be expressed as the sum of ABC*1000 and XYZ, so the digits of both ABC and XYZ must sum separately to 3. Let the last three digits be RST. 

#For a four-digit number to be divisible by four, the last two digits must make a number divisible by four. Therefore if the third digit is odd, the fourth must be an odd multiple of 2
for X in Xs:
  vec=[None for i in range(9)]
  vec[4]=5#no zeros allowed, and the five-digit number divisible by 5
  vec[3]=X
  Z=10-X#consequence of sum(X,Y,Z) divisible by three
  vec[5]=Z
  Bs=[i for i in evens if i not in vec]#remaining evens go to 2nd and 8th
  for B in Bs:
    vec[1]=B
    S=Bs[(Bs.index(B)-1)%2]
    vec[7]=S  

#Try each pair of odd numbers (other than 5) in positions 1 and 3, subject to requiring that ABC divisible by 3 (requiring A+B+C divisible by 3)  
    for A in odds:
      Cs=odds.copy()
      Cs.remove(A)
      for C in Cs:
        if sum([A,B,C])%3==0:
          vec[0]=A
          vec[2]=C

#Complementary odds then fall into positions 7 and 9          
          Rs=Cs.copy()
          Rs.remove(C)
          for R in Rs:
            vec[6]=R
            if sum([i*10**(6-vec.index(i)) for i in vec[:7]])%7==0 and sum([i*10**(7-vec.index(i)) for i in vec[:8]])%8==0:
              Ts=Rs.copy()
              Ts.remove(R)
              for T in Ts:
                vec[8]=T
                print("The telephone number is",sum([i*10**(8-vec.index(i)) for i in vec[:9]]))
```
    LikeLike
    - Frits 10:57 am on 29 March 2021 Permalink | Reply
      Hi Tony,
      
      A couple of recommendations:
      
      index() is expensive so line 35 may be written to :
      
      if sum([x * 10**(2 - i) for i, x in enumerate(vec[5:8])]) % 8 == 0 and \ sum([x * 10**(6 - i) for i, x in enumerate(vec[:7])]) % 7 == 0:
      
      You can also use something like “dgts2nbr” as in puzzle [[ https://enigmaticcode.wordpress.com/2017/04/10/enigma-1120-assorted-numbers/ ]]
      
      – line 16-19 can be rewritten to:
      
      for j, B in enumerate(Bs): vec[1] = B vec[7] = Bs[1 - j]
      
      or
      
      for j in range(2): vec[1] = Bs[j] vec[7] = Bs[1 - j]
      
      or
      
      for (B, S) in permutations(Bs): vec[1] = B vec[7] = S
      
      LikeLike
      - Tony 6:01 pm on 29 March 2021 Permalink | Reply
        
        Thanks Frits: now I know about enumerate and reduce. As I’m getting the hang of looping over iterables I had forgotten it is still possible to loop with a counter, so I would probably choose your second approach to lines 16-19. I was trying to avoid using itertools once I realised I only needed to deal with pairs.
        
        LikeLike
- Hugh Casement 12:51 pm on 27 March 2021 Permalink | Reply
  
  Isn’t this effectively the same as Brainteaser 1040 (4 July 1982)?
  
  That one at least spared us George and Martha, who get dragged in again and again for no good reason.
  
  LikeLike
  - Jim Randell 3:36 pm on 27 March 2021 Permalink | Reply
    
    @Hugh: It does seem to be. I suppose it is hard to come up with over 3000 puzzles without some overlap. Or to check that there is no overlap!
    
    LikeLike
    - Hugh Casement 1:14 pm on 30 March 2021 Permalink | Reply
      
      And the recent Puzzle 102 in New Scientist. I call that plagiarism!
      
      LikeLike
- GeoffR 1:39 pm on 20 May 2021 Permalink | Reply
```
from itertools import permutations
from enigma import join

# the number 45 is divisible by nine
i = 9

for p in permutations('123456789', 8):
  a, b, c, d, e, f, g, h = p

  # A geometric pattern to this code  

  if int(a + b + c + d + e + f + g + h) % 8 == 0:
    if int(a + b + c + d + e + f + g) % 7 == 0:
      if int(a + b + c + d + e + f) % 6 == 0:
        if int(a + b + c + d + e) % 5 == 0:
          if int(a + b + c + d) % 4 == 0:
            if int(a + b + c) % 3 == 0:
              if int(a + b) % 2 == 0:
                tel_num = join((a, b, \
                c, d, e, f, g, h, i))
                print('No. is',tel_num)
                # No. is 381654729
```
  LikeLike
- Dirk 9:43 am on 9 July 2021 Permalink | Reply
  
  Teaser 1882 (11/10/1998): Multiple Solutions by Rex Gooch is also linked with brainteaser 1040/3053.
  
  LikeLike
Jim Randell 8:24 am on 25 March 2021 Permalink | Reply
Tags: by: J S Rowley ( 9 )
Brain-Teaser 717: Wrong hands
From The Sunday Times, 13th April 1975 [link]

Waking in the night I glanced at my bed-side clock and thought it indicated just after 2:20. Putting on my spectacles and looking more carefully I saw that it was actually just after 4:10. I had, of course, interchanged the hands at my first glance.

I began to wonder what time around then that my observation would have occurred, to the exact fraction of a minute, if the hands could have been exactly interchanged.

What do you think?

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

[teaser717]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Hugh Casement and Jim Randell are discussing. Toggle Comments
- Jim Randell 8:26 am on 25 March 2021 Permalink | Reply
  
  I we divide the circle of the clock face into 60 sectors, then the minute has travels at 1 sector/minute, and the hour hand at 1/12 sector/minute.
  
  If we suppose the difference (in minutes) between the times is d, then the hour hand has moved a distance d / 12 sectors (which is roughly 1/6 of the circle), and the minute hand has moved distance d sectors (and roughly twice – 1/6 times around the circle):
  
  d = 120 − (d / 12)
  d = 1440 / 13
  d = 110 + 10/13
  
  So the difference between the times is nearly 111 minutes, about what we would expect.
  
  If we suppose the actual time is m minutes after 4 o’clock (i.e. 240 + m minutes), then the minute hand will be showing m minutes, which is m sectors around the circle.
  
  And at the mistaken time = (240 + m − d) the hour hand would be showing the same point:
  
  (240 + m − d) / 12 = m
  240 − d = 11m
  m = (240 − d) / 11
  m = 1680 / 143
  m = 11 + 107/143
  
  Solution: The exact time would be 11 + 107/143 minutes after 4 o’clock.
  
  LikeLike
- Hugh Casement 1:45 pm on 25 March 2021 Permalink | Reply
  
  I make that 11 minutes, 44 and 128/143 seconds,
  mistaken for 20 minutes, 58 and 106/143 seconds (20 and 140/143 minutes) after 2.
  
  There’s a lot to be said for digital clocks, especially in the middle of the night!
  
  LikeLike

Jim Randell 9:07 am on 23 March 2021 Permalink | Reply
Tags: by: Susan Bricket ( 17 )

Teaser 2781: Number time

From The Sunday Times, 10th January 2016 [link] [link]

I have written down some numbers and then consistently replaced digits by capital letters, with different letters used for different digits. In this way my numbers have become:

TRIPLE (which is a multiple of three)
EIGHT (which is a cube)
NINE (which is divisible by nine)
PRIME (which is a prime)

What is the number TIME?

[teaser2781]

Jim Randell 9:08 am on 23 March 2021 Permalink | Reply
We can use the [[ SubstitutedExpression ]] solver from the enigma.py library to solve this puzzle directly.

The following run file executes in 122ms.

Run: [ @replit ]
```
#! python3 -m enigma -rr

SubstitutedExpression

"TRIPLE % 3 = 0"
"is_cube(EIGHT)"
"NINE % 9 = 0"
"is_prime(PRIME)"

--answer="TIME"
```
Solution: TIME = 3901.

There are 4 solutions to the alphametic expressions, but the value for TIME is the same in all of them.

LikeLike

Frits 12:39 pm on 23 March 2021 Permalink | Reply

With a complicated formula for N.

from enigma import is_prime

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

# EIGHT is a cube
for i in range(22, 47):
  s3 = str(i ** 3)
  E = int(s3[0])
  I = int(s3[1])
  T = int(s3[-1])
  if T == 0: continue             
  if E % 2 == 0: continue  # E may not be even (due to PRIME)
  if not alldiff(s3): continue
  
  # NINE is a multiple of 9
  # sumIE plus 2*N must be equal to k*9   (k is 1,2 or 3)
  sumIE = I + E
  N = (9 + 18 * (sumIE > 9) - sumIE) // 2 if sumIE % 2 else (18 - sumIE) // 2  
  if N == 0 or not alldiff(s3 + str(N)): continue   
  
  # TRIPLE is a multiple of 3
  LMPR = [x for x in range(10) if str(x) not in s3 + str(N)]
  candsM = [x for x in LMPR if (sumIE + T + sum(LMPR) - x) % 3 == 0]
   
  for M in candsM:
    LPR = [x for x in LMPR if x != M]
    for L in LPR:
      # PRIME may not be a multiple of 3
      if (sumIE + M + sum(LPR) - L) % 3 == 0: continue
      PR = [x for x in LPR if x != L]
      # consider permutations of PR
      for (P, R) in zip(PR, PR[::-1]):
        if P == 0: continue
        PRIME = 10000*P + 1000*R + 100*I + 10*M + E
        if not is_prime(PRIME): continue
        print(f"TIME={T}{I}{M}{E}")

LikeLike

Jim Randell 10:41 pm on 21 March 2021 Permalink | Reply
Tags: by: Mrs. K. Y. Gunson
Brain-Teaser 27: Foggy birthday
From The Sunday Times, 24th September 1961 [link]

Mr and Mrs Herbert Fogg, in celebration of Herbert’s forty-third birthday, invited three friends, Ann, Bill, and Cuthbert, to dinner.

“Of course, Herbert is quite a bit older than any one of you”, Mrs Fogg declared to the three guests. Herbert frowned.

“It’s odd”, Ann quickly interposed, “if you multiply Bill’s and Cuthbert’s ages together, then divide by Herbert’s age the remainder is just my age”.

“Whereas if you multiply together Ann’s and Cuthbert’s ages, again divide by Herbert’s age, then the remainder is just how old I was a year ago”, added Bill.

“Not so simple for me”, said Cuthbert, the youngest present. “If you multiply together Ann’s and Bill’s ages, divide by Herbert’s, then the remainder is just one and a half times my age”.

“Very interesting”, Herbert reflected. “In fact, from what you have told me it may be possible to find all three of your ages, if I knew how to start!”

Show that Herbert was almost right and find the exact ages of Ann, Bill, and Cuthbert.

[teaser27]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
John Crabtree, Frits, and Jim Randell are discussing. Toggle Comments
- Jim Randell 10:42 pm on 21 March 2021 Permalink | Reply
  This Python program runs in 49ms.
```
from enigma import (irange, printf)

# H's age
H = 43

# choose C's age (the youngest)
for C in irange(10, H - 3, step=2):
  # choose B's age
  for B in irange(C + 1, H - 1):
    # calculate A's age (using A's statement)
    A = (B * C) % H
    if not (A > C and A != B): continue
    # check B's and C's statements
    if not (B - 1 == (A * C) % H): continue
    if not (3 * C == 2 * ((A * B) % H)): continue

    # output solution
    printf("A={A} B={B} C={C}")
```
  Solution: Ann is 27. Bill is 25. Cuthbert is 20.
  
  LikeLike
- Frits 10:02 am on 22 March 2021 Permalink | Reply
```
% A Solution in MiniZinc 
 
% ages
var 11..42:A; var 11..42:B; var 10..38:C; var 43..43:H;
 
constraint C < A /\ C < B /\ A + 2 < H /\ B + 2 < H;
 
constraint (B * C) mod H = A;
constraint (A * C) mod H + 1 = B;
constraint 2 * ((A * B) mod H) = 3 * C;
 
solve satisfy;
 
output [ "Ann is " ++ show(A)]
++ [ "\nBill is " ++ show(B)]
++ [ "\nCuthbert is " ++ show(C)];
```
  LikeLike
- John Crabtree 4:16 pm on 23 March 2021 Permalink | Reply
  
  1. BC = A mod 43
  2. AC = B – 1 mod 43
  3. AB = 3C / 2 mod 43 with C even and C < 30
  Combining Equations 1 and 3 leads to B^2 = 23 mod 43
  Equations 1, 2 and 3 give ABC = A^2 = B^2 – B = 23 – B = 3C^2 / 2
  One can also show that (A ^2 – 23)^2 = 23 mod 43 and (C^2 – 1)^2 = 15 mod 43
  
  The easiest way forward is to start with (C^2 – 1)^2 = 15 mod 43
  (C^2 – 1) = 12 mod 43 (C = 20 or 23), or (C^2 – 1) = 31 mod 43 with no value of C
  And so C = 20
  B = 23 – 3C^2 / 2 mod 43 = 25
  A = BC mod 43 = 27
  This would make for a simple and fast program. It can also be done by hand.
  
  Starting with B^2 = 23 mod 43 gives:
  B = 18, A^2 = 5 mod 43, with no possible values of A < 22
  Also B = 43 – 18 = 25, when A^2 = -2 = 41 mod 43
  ..A = 16 gives 3C / 2 = 13 which is invalid (and C = 23 mod 43)
  ..A = 43 – 16 = 27 gives 3C / 2 = 30, ie C = 20.
  
  Ann is 27, Bill is 25 and Cuthbert is 20.
  
  The information that C is the youngest is redundant, although it does reduce the solution space for a brute force search.
  This is an interesting teaser.
  
  LikeLike
Jim Randell 4:40 pm on 19 March 2021 Permalink | Reply
Tags: by: Stephen Hogg ( 64 )
Teaser 3052: Porcus facit griphus
From The Sunday Times, 21st March 2021 [link] [link]

“Argent bend sinister abased sable in dexter chief a hog enraged proper” blazons our shield (shaped as a square atop a semi-circle, with a 45° diagonal black band meeting the top corner). We’ve three shields. For the first, in centimetres, the top width (L) is an odd perfect cube and the vertical edge height of the band (V) is an odd two-figure product of two different primes. The others have, in inches, whole-number L (under two feet) and V values (all different). For each shield, the two white zones have almost identical areas. All three V/L values, in percent, round to the same prime number.

Give the shortest top width, in inches.

[teaser3052]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Tony Brooke-Taylor, Hugh Casement, Jim Randell, and 1 other are discussing. Toggle Comments
- Jim Randell 6:00 pm on 19 March 2021 Permalink | Reply
  The puzzle is set by Stephen Hogg.
  
  This Python routine calculates the V/L ratio where the areas are equal numerically, and then looks for permissible L values for the shield measured in centimetres.
  
  We then look for integer V values within 10% of the “ideal” value, that have 2 different prime factors, and give a rounded percentage that is a prime.
  
  We then look for multiple shields that have an L value less than 24 inches, and a corresponding V value that give the same rounded percentage.
  
  This Python program runs in 50ms.
  
  Run: [ @replit ]
```
from math import (pi, sqrt, atan2)
from enigma import (find_value, intf, intc, Accumulator, irange, divf, divc, fdiv, group, item_from, is_prime, factor, iroot, powers, printf)

# calculate the difference between the upper and lower areas
def areas(V, L):
  # lower area: triangular bit
  t = L - V
  T = 0.5 * t * t
  # lower area: semi-circular bit
  a = 0.5 * L
  b = a - V
  a2 = a * a
  b2 = b * b
  # solve: x^2 + y^2 = a^2, y = x - b for x, y
  r = sqrt(2 * a2 - b2)
  x = 0.5 * (r + b)
  y = 0.5 * (r - b)
  theta = pi - atan2(y, x)
  # calculate the areas
  upper = a * L
  lower = T + 0.5 * (a2 * theta + b * y)
  # return the difference in areas
  return fdiv(2 * abs(upper - lower), upper + lower)

# find the V/L ratio when the white areas are equal
r0 = find_value((lambda v: areas(v, 1)), 0, 0.25, 0.50).v
printf("[r0 = {r0}]")

# generate (V, L, rounded V/L percentage) values
def generate(Ls):
  for L in Ls:
    # calculate exact V
    v = r0 * L
    # allow a tolerance of 10%
    for V in irange(intc(0.9 * v), intf(1.1 * v)):
      # calculate the rounded V/L percentage
      p = divf(200 * V + L, 2 * L)
      if not is_prime(p): continue
      # return values
      yield (V, L, p)

# group (V, L, p) values by the percentage, for the shields measured in inches
d = group(generate(irange(2, 23)), by=item_from("p", "V, L, p"))

# find the shield measured in centimetres
M = iroot(divc(100, 0.9 * r0), 3)
for (V, L, p) in generate(powers(3, M, 3, step=2)):
  # V is an odd, 2-digit number
  if V % 2 == 0 or V < 10 or V > 99: continue
  # V should have 2 prime factors
  fs = factor(V)
  if not (len(fs) == 2 and len(set(fs)) == 2): continue

  # look for shields measured in inches
  vs = d.get(p)
  if (not vs) or len(vs) < 2: continue

  # output solution
  r = Accumulator(fn=min)
  inch = lambda x: fdiv(x, 2.54)
  printf("V/L ~ {p}%")
  printf("-> 1: L = {L}cm ({Li:.2f}in), V = {V}cm ({Vi:.2f}in) [error = {r:.6f}]", Li=inch(L), Vi=inch(V), r=areas(V, L))
  r.accumulate(inch(L))
  for (Vi, Li, _) in vs:
    printf("-> 2: L = {Li}in, V = {Vi}in [error = {r:.6f}]", r=areas(Vi, Li))
    r.accumulate(Li)
  printf("=> min L = {r:.2g}in", r=r.value)
  printf()
```
  Solution: The shortest L value is: 17 inches.
  
  The measurements for each of the three shields are:
  
  L = 125cm (49.2in), V = 51cm (20.1in)
  L = 17in, V = 7in
  L = 22in, V = 9in
  V/L ≈ 41%
  
  The program calculates a more precise ratio for equal areas: V/L = 0.408083900721218.
  
  In order to calculate the area of the lower white area on the shield, I started with a polynomial approximation based on the three values at V=0, V=L/2, V=L.
  
  This is sufficient to find the answer (as, I suspect, are many other rough estimates).
  
  But for the program above I came up with a a way of calculating the area exactly, based on the following diagram:
  
  The shield is turned upside down and we place x,y axes through the centre of the semicircle.
  
  Then using: a = L/2, b = L/2 − V
  
  The semicircle is part of the circle: x² + y² = a²
  
  The (now) upper line of the stripe is the line: y = x − b
  
  And these meet at: (x, y) = ((r + b)/2, (r − b)/2), where: r = √(2a² − b²)
  
  So we can calculate the angle θ = arctan(y, x)
  
  And the area of the yellow triangle = (1/2)ab sin(θ) = by/2
  
  The orange region is then the area of the sector of the circle that subtends the angle θ, less the area of the yellow triangle.
  
  And once we know the area of the orange region the area of the (formerly) lower region of the shield can be easily determined.
  
  LikeLike
  - Tony Brooke-Taylor 10:13 am on 22 March 2021 Permalink | Reply
    
    I found you can get away with approximating away the arctan term and I eliminated the need to set a tolerance by finding the valid V/L ratios closest to the target prime. However, my code takes 40 times longer to run than yours Jim so I have some other work to do!
    
    LikeLike
    - Tony Brooke-Taylor 10:56 am on 22 March 2021 Permalink | Reply
      
      … so it takes 1/4s to import numpy and 5ms for the rest of my program to run. Now I know why people bother with the math library.
      
      LikeLike
- Robert Brown 8:25 pm on 20 March 2021 Permalink | Reply
  
  The information about equal white zones is redundant. There is only one solution to the metric shield, which defines the prime. Then there are only two possible imperial solutions where v/a rounds to give the same prime. That solves the teaser. It’s good of him to tell us that all 3 solutions have white zones with ‘almost’ identical areas, but it adds nothing to the teaser solution.
  
  LikeLike
  - Jim Randell 9:04 pm on 20 March 2021 Permalink | Reply
    
    @Robert: If we didn’t have the “equal area” constraint what would stop a solution like this:
    
    V/L ≈ 31%
    L = 125cm, V = 39cm
    L = 13in, V = 4in
    L = 16in, V = 5in
    
    I think we need the additional constraint to eliminate such solutions (in this one the areas differ by about 16%).
    
    But you don’t need to be completely accurate. A rough estimate will get you to the answer.
    
    LikeLike
- Hugh Casement 7:04 am on 21 March 2021 Permalink | Reply
  
  I thought I knew a bit about heraldry, but had never come across the term ‘abased’. However, it’s clear that the bend has slipped down so that its upper edge, rather than its centre line, meets the corner of the shield. ‘Enraged’ is surely an invention, n’est-ce pas?
  
  The area of white space must mean before the piglet has flown in. Then it’s a quick back-of-the-envelope calculation — no computer needed. Teasers are seldom so easy.
  
  LikeLike
- Hugh Casement 11:17 am on 21 March 2021 Permalink | Reply
  
  Whatever S. Hogg’s ability to blazon may be, his Latin is shocking!
  As every schoolboy knows, a direct object goes in the accusative: porcus imitat gryphem (for example).
  Better might be porci volent, though I’m not sure how far we can trust the googly translator.
  
  LikeLike
Jim Randell 8:28 am on 18 March 2021 Permalink | Reply
Tags: by: Eric Emmet ( 10 )
Brain-Teaser 702: That’s torn it … again
From The Sunday Times, 29th December 1974 [link]

Last time it was vertical. But no one could accuse Uncle Bungle of being consistent and this time it was horizontal. The way, I mean, in which he tore the piece of paper on which were written the details of the matches between 4 local football teams, A, B, C, and D, who are to play each other once.

All that was left was:

It is not known whether all the matches have been played. And not more than 7 goals were scored in any game.

With the information that it is possible to discover the score in each match, you should be able to discover them.

What was the score in each match?

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

[teaser702]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
John Crabtree and Jim Randell are discussing. Toggle Comments
- Jim Randell 8:29 am on 18 March 2021 Permalink | Reply
  I wasn’t entirely happy about this puzzle, but after some thought I was able to convince myself that there is a way to arrive at a single solution.
  
  We are told that there is enough information to determine the scores in each match (even though on the face of it it seems that we have not), so that fact it is possible to determine the scores means that there must be some ambiguous situations that cannot arise.
  
  We have no information at all about C and D, so any solution that we find will be equally applicable if C and D’s labels are swapped over. But as we are told we can determine the scores in the matches, this must mean swapping the labels of C and D would have no effect on the scores, so C and D must have performed identically.
  
  From this we can see that the C vs D match cannot be won by either of the teams, so it must be a draw, or not yet played. If it were a draw, then it could be 0-0, 1-1, 2-2, 3-3 and we don’t know which. So the C vs D match must be not yet played.
  
  We know A and B have both played each of the other teams (as they have played 3 matches each), so all 6 matches involving A and B must have been played. And so the A vs B and A vs C matches must have identical scores, as must the B vs C and B vs D matches.
  
  So we only need to calculate three scorelines: A vs B (win), A vs (C and D) (draw), B vs (C and D) (win).
  
  This Python program runs in 48ms.
  
  Run: [ @replit ]
```
from itertools import product
from enigma import Football, printf

# possible scores (no more than 7 goals scored per match)
win = [
  (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0), (7, 0),
  (2, 1), (3, 1), (4, 1), (5, 1), (6, 1),
  (3, 2), (4, 2), (5, 2),
  (4, 3),
]
draw = [(0, 0), (1, 1), (2, 2), (3, 3)]

# for computing goals for/against
football = Football()

# CD is not yet played
CD = None

# A has 2 draws (which must be AC = AD) and a win (which must be AB)
# B has 2 wins (which must be BC = BD)
for (AB, AX, BX) in product(win, draw, win):
  # check goals for/against
  if not(football.goals([AB, AX, AX], [0, 0, 0]) == (7, 5)): continue
  if not(football.goals([AB, BX, BX], [1, 0, 0]) == (5, 5)): continue
  # output solution
  printf("AB={AB} AC={AX} AD={AX} BC={BX} BD={BX} CD={CD}")
```
  Solution: A vs B = 3-1; A vs C = 2-2; A vs D = 2-2; B vs C = 2-1; B vs D = 2-1; C vs D = not yet played.
  
  LikeLike
- John Crabtree 7:33 pm on 18 March 2021 Permalink | Reply
  
  At the point where you can say “So we only need to calculate three scorelines”, you are almost home.
  A must beat B by 2 goals, and score an odd number of goals. That fixes the score in A vs B, and the remaining scores follow.
  
  LikeLike
Jim Randell 8:14 am on 16 March 2021 Permalink | Reply
Tags: by: Victor Bryant ( 144 ), flawed ( 54 )
Teaser 2529: [Cost estimates]
From The Sunday Times, 13th March 2011 [link] [link]

A letter to The Times concerning the inflated costs of projects read:

When I was a financial controller, I found that multiplying original cost estimates by 𝛑 used to give an excellent indication of the final outcome.

Interestingly, I used the same process (using 22/7 as a good approximation for 𝛑). On one occasion, the original estimate was a whole number of pounds (less than £100,000), and this method for the probable final outcome gave a number of pounds consisting of exactly the same digits, but in the reverse order.

What was the original estimate?

When originally published the amount was given as “less than £10,000”, which was raised to “less than £100,000” in the following issue. But even with this change the puzzle is still open to interpretation.

This puzzle was originally published with no title.

[teaser2529]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
John Crabtree, Hugh Casement, Frits, and 1 other are discussing. Toggle Comments
- Jim Randell 8:15 am on 16 March 2021 Permalink | Reply
  What the puzzle isn’t clear on is what happens to any fractional part of the new estimate. (Which there would always be if you were to multiply by 𝛑).
  
  If we round down (simply ignoring any fractional part) in the result, then we can get a solution to the original puzzle:
  
  £185 × 22/7 = £581.43 → £581
  
  And we also get the same result if we round to the nearest pound.
  
  And a different unique solution if we round up:
  
  £29 × 22/7 = £91.14 → £92
  
  Raising the limit to £100,000 then we get the following additional solutions:
  
  £22407 × 22/7 = £70422
  
  Rounding to nearest:
  
  £30769 × 22/7 = £96702.57 → £96703
  
  Which we also get if we round up, along with:
  
  £29429 × 22/7 = £92491.14 → £92492
  
  So the only way we can get a unique solution with the revised upper limit is to assume that, before rounding, the new estimate was a whole number of pounds, and so no rounding was necessary. In this case only the pair £22407 → £70422 remain as a candidate solution, and this was the required answer.
  
  This makes a manual solution easier (and a programmed solution a little faster), as we know the original estimate must be a multiple of 7.
  
  The following Python program lets you play with various rounding methods.
```
from enigma import (irange, divf, divc, divr, div, nreverse, printf)

# the new estimate is the original estimate multiplied by 22/7
# choose an appropriate function from the following
# - fn=divf: rounded down
# - fn=divc: rounded up
# - fn=divr: rounded to nearest integer
# - fn=div: exact division
estimate = lambda x, fn=div: fn(x * 22, 7)

# consider the original estimate x
for x in irange(1, 99999):
  # multiply by 22/7 for new estimate n
  n = estimate(x)
  if n is None or n % 10 == 0: continue
  # new estimate is reverse of the original
  if nreverse(n) == x:
    printf("original {x} -> {n}")
```
  Solution: The original estimate was: £22,407.
  
  If the estimates had been constrained to be between £100,000 and £1,000,000 then there is a single solution whichever rounding method is chosen:
  
  £246,477 × 22/7 = £774,642
  
  LikeLike
- Frits 1:04 pm on 17 March 2021 Permalink | Reply
```
# consider original cost abcde w    
# 22 * abcde = 7 * edcba 

# 0 < a < 4 as a * 22 / 7 < 10
# a must be also be even as 22 * abcde is even
# so a = 2 and 5 < e < 10
# 22 * 2bcde = 7 * edcb2 --> e is 7 or 2 --> e is 7 

# equation 22 * 2bcd7 = 7 * 7dcb2

# cost 2-digit number: 
# -- 27 is not divisible by 7
# cost 3-digit number: 4914 <= 22 * 2b7 <= 5544 so 2 < b < 5 
# -- no 2b7 is divisible by 7 for 2 < b < 5 
# cost 4-digit number: 49014 <= 22 * 2bc7 <= 55944 so 1 < b < 6 
# cost 5-digit number: 490014 <= 22 * 2bcd7 <= 559944 so 1 < b < 6 

# ...d7 * 22 ends on 54 + d * 20 --> ends on o4 where o is an odd digit
# b = 2 --> ...22 * 7 = ...54, 54 + d * 20 ends on 54 so d = 0 or 5
# b = 3 --> ...32 * 7 = ...24, wrong
# b = 4 --> ...42 * 7 = ...94, 54 + d * 20 ends on 94 so d = 2 or 7
# b = 5 --> ...52 * 7 = ...64, wrong

# b = 2 --> d = 0 or 5,
# b = 4 --> d = 2 or 7

# 4-digit numbers 2207, 2257, 2427 and 2477 are not not divisible by 7

# divisibility by 11 requires that the difference between 
# the sum of the the digits in odd positions and 
# the sum of all the digits in even positions is 0 or divisible by 11

# 22x07, sum even positions = 2  --> (9 + x - 2) % 11 = 0 -- > x = 4
# 22407 is divisible by 7

# 22x57, sum even positions = 7  --> (9 + x - 7) % 11 = 0 -- > x = 9
# 22957 is not divisible by 7

# 24x27, sum even positions = 6  --> (9 + x - 6) % 11 = 0 -- > x = 8
# 24827 is not divisible by 7

# 24x77, sum even positions = 11 --> (9 + x - 11) % 11 = 0 -- > x = 2
# 24277 is not divisible by 7
     
# so 22407 * 22/7 = 70422  
```
  LikeLike
- John Crabtree 1:40 pm on 18 March 2021 Permalink | Reply
  
  X = abcde, Y = edcba where X * 22 = Y * 7
  and so 2e = 7a mod 10, and so a = 2 and e = 7
  
  By digital roots, the sum of the digits in X = 0 mod 3. X = Y = 0 mod 3
  X = 0 mod 7. Y = 0 mod 11, and so X = 0 mod 11
  And so X = 231*M, Y = 726*M, and M = 7 mod 10
  Or X = 1617 + 2310*N and Y = 5082 + 7260*N
  
  By inspection X cannot have 2, 3 or 4 digits
  70,000 < Y < 80,000 and so N = 9 or 10, which is invalid by inspection.
  N = 9 gives X = 22407 and Y = 70422, which is valid.
  
  If X 6 digits, there are only 14 possible values of N, ie 96 to 109, to check.
  
  LikeLike
  - Frits 12:12 pm on 19 March 2021 Permalink | Reply
    
    @John,
    
    Maybe you used the congruent sign in your analysis and it was replaced by equal signs.
    If so you might try the enclosure of text as mentioned in Teaser 2756.
    If not the analysis is wrong as 0 mod 11 equals 0.
    
    Please elaborate as I am not an expert in modular arithmetic (I gather X must be a multiple of 3, 7 and 11?).
    
    LikeLike
    - John Crabtree 4:16 pm on 19 March 2021 Permalink | Reply
      
      @Frits
      I do not recall the congruence sign from when I was first introduced to modulo arithmetic nearly 50 years ago. I have always used the equals sign (perhaps incorrectly) followed by mod n.
      X = 0 mod 3 means that X is divisible by 3. And so, yes, X is divisible by 3, 7 and 11. As it also ends in 7 the solution space becomes very small. HTH
      
      LikeLike
- Hugh Casement 12:25 pm on 19 March 2021 Permalink | Reply
  
  I meant to post this on St Patrick’s day, before most of the other comments appeared.
  
  I’m sure that an integer solution is intended, so no rounding is necessary.
  The original estimate must therefore be an integer multiple of 7.
  The result is even, so the original estimate (with its digits in reverse order) must start with 2: any larger value would yield a result with more digits.
  The result is a multiple of 11, so the original estimate (using the same digits) must be too.
  Admittedly, that still means a lot of trial & error if we don’t use a computer.
  
  22/7 is a lousy approximation to pi! Much better is 355/113, but I think that can work only if the original estimate is allowed to have a leading zero.
  
  LikeLike
Jim Randell 10:34 am on 14 March 2021 Permalink | Reply
Tags: by: R. R. Brand
Brain-Teaser 26: Farmer’s overdraft
From The Sunday Times, 17th September 1961 [link]

Farmer Green was in the red. On studying his statement (which was entirely in complete £s) he found that the aggregate of the figures in his deposits total was only one-fourth of the aggregate of the figures in his withdrawals total. He also noted that, coincidentally, the latter aggregate equals the balance, in red, that would be shown when he has paid in the £749 cheque which he, fortunately, had received that morning.

What was the overdraft shown on the statement?

[teaser26]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
John Crabtree, Hugh Casement, and Jim Randell are discussing. Toggle Comments
- Jim Randell 10:35 am on 14 March 2021 Permalink | Reply
  This Python program run in 89ms.
  
  Run: [ @replit ]
```
from collections import defaultdict
from enigma import irange, dsum, div, printf

# record number by digit sum
ns = defaultdict(list)

# consider increasing numbers
for n in irange(1, 10000):
  ds = dsum(n)
  ns[ds].append(n)

  # if n is the total amount withdrawn
  # then the total amount deposited is less than this
  # and has a digit sum that is ds/4
  dds = div(ds, 4)
  if dds is None: continue
  for t in ns[dds]:
    # balance (is in red, so is negative), after the cheque is paid in
    red = -(t - n + 749)
    # is the same as the digit sum of the withdrawals
    if red == ds:
      # output solution
      od = ds + 749
      printf("withdrawn = {n}, deposited = {t}, red = {red}; overdraft = {od}")
```
  Solution: The overdraft on the statement is £777.
  
  There are 27 different (widthrawn, deposited) totals, but they all lead to an overdraft on the statement of £777.
  
  LikeLike
- Hugh Casement 1:52 pm on 14 March 2021 Permalink | Reply
  
  I don’t follow this one. We are not told the opening balance on the bank statement, so we can’t tell what the difference between deposits and withdrawals should be.
  
  And one needs to be a mind-reader to deduce that “aggregate of the figures” means sum of the digits! Why can’t the setters of puzzles say what they mean?
  
  LikeLike
- John Crabtree 7:43 pm on 15 March 2021 Permalink | Reply
  
  The overdraft on the statement = W – D = Sum(W) + 749
  And so Sum(D) = – 2 mod 9 = 7 and Sum(W) = 4 * 7 = 28
  The overdraft on the statement = 28 + 749 = £777
  
  LikeLike
Jim Randell 4:57 pm on 12 March 2021 Permalink | Reply
Tags: by: Colin Vout ( 38 )
Teaser 3051: Shipping forecast
From The Sunday Times, 14th March 2021 [link] [link]

“Here is the shipping forecast for the regions surrounding our island.

First, the coastal regions:

Hegroom: E 6, rough, drizzle, moderate.
Forkpoynt: E 7, rough, rain, good.
Angler: NE 7, rough, drizzle, moderate.
Dace: NE 7, smooth, drizzle, moderate.

Now, the offshore regions:

Back: E gale 8, rough, rain, moderate.
Greigh: E 7, smooth, drizzle, poor.
Intarsia: SE 7, rough, drizzle, moderate.
Catter: E gale 8, high, drizzle, moderate.
Eighties: E 7, rough, fair, good.”

In this forecast, no element jumps from one extreme to another between adjacent regions.

The extremes are:

wind direction: SE & NE;
wind strength: 6 & gale 8;
sea state: smooth & high;
weather: fair & rain;
visibility: good & poor.

Each region adjoins four others (meeting at just one point doesn’t count).

Which of the regions does Angler touch?

[teaser3051]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell, Tony Brooke-Taylor, and Frits are discussing. Toggle Comments
- Jim Randell 10:37 pm on 12 March 2021 Permalink | Reply
  (You might like to work out which sea areas this puzzle is spoofing [ @wikipedia ]).
  
  It took me a bit of doodling to come up with a map of the sea areas that satisfied the description. (I’ll put up a diagram of it later – [link]). But once that is done the program is relatively straightforward.
  
  I don’t know that it is the only possible map though, but I assume the setter must have checked that any viable map will give the same solution.
  
  This Python program runs in 58ms.
```
from enigma import (subsets, update, peek, join, map2str, printf)

# suppose the coastal regions are: 0, 1, 2, 3
# and the offshore regions are: 4, 5, 6, 7, 8

# the adjacency map
adj = [
  (1, 3, 6, 8), # 0
  (0, 2, 4, 6), # 1
  (1, 3, 4, 5), # 2
  (0, 2, 5, 8), # 3
  (1, 2, 6, 7), # 4
  (2, 3, 7, 8), # 5
  (0, 1, 4, 7), # 6
  (4, 5, 6, 8), # 7
  (0, 3, 5, 7), # 8
]

# the forecast, region -> (dir, str, sea, wea, vis)
forecast = dict(
  # coastal
  H=('E', 6, 'rough', 'drizzle', 'moderate'),
  F=('E', 7, 'rough', 'rain', 'good'),
  A=('NE', 7, 'rough', 'drizzle', 'moderate'),
  D=('NE', 7, 'smooth', 'drizzle', 'moderate'),
  # offshore
  B=('E', 8, 'rough', 'rain', 'moderate'),
  G=('E', 7, 'smooth', 'drizzle', 'poor'),
  I=('SE', 7, 'rough', 'drizzle', 'moderate'),
  C=('E', 8, 'high', 'drizzle', 'moderate'),
  E=('E', 7, 'rough', 'fair', 'good'),
)

# extremes (in the same order)
extreme = ({'SE', 'NE'}, {6, 8}, {'smooth', 'high'}, {'fair', 'rain'}, {'good', 'poor'})

# check forecast for <k> can be placed at region <r> without giving an extreme pair
# return an updated map, or None
def check(k, r, m):
  for (i, (v0, xs)) in enumerate(zip(forecast[k], extreme)):
    # is there an extreme in the forecast?
    if v0 in xs:
      # check the other extreme is not in any adjacent areas
      for r1 in adj[r]:
        s = m.get(r1, None)
        if s:
          v1 = forecast[s][i]
          if v1 != v0 and v1 in xs: return None
  # looks good, map r -> k
  return update(m, [(r, k)])

# attempt to map regions <rs> to keys <ks>
def assign(rs, ks, m):
  for (r, k) in zip(rs, ks):
    m = check(k, r, m)
    if m is None: break
  return m

# assign the coastal regions (0, 1, 2, 3) -> "ADFH"
for ks in subsets("ADFH", size=len, select="P"):
  m0 = assign((0, 1, 2, 3), ks, dict())
  if m0 is None: continue

  # assign the offshore regions (4, 5, 6, 7, 8) -> "CBEGI"
  for ks in subsets("CBEGI", size=len, select="P"):
    m = assign((4, 5, 6, 7, 8), ks, m0)
    if m is None: continue

    # which region is A?
    r = peek(k for (k, v) in m.items() if v == 'A')

    # output the regions adjacent to A
    adjA = sorted(m[x] for x in adj[r])
    printf("adj[A] = {adjA} {m}", adjA=join(adjA, sep=",", enc="()"), m=map2str(m, arr="->", enc="[]"))
```
  Solution: Angler adjoins Catter, Eighties, Forkpoynt, Hegroom.
  
  The program finds 4 ways to assign the areas to regions of the map. But the map can be drawn to have two axes of symmetry, so there is essentially only one solution (and the other 3 found are just reflections of this).
  
  My initial stetch, with the required connectivity looked like this:
  
  Which I redrew using straight lines to get this map:
  
  Which I think looks more like a map of sea areas. (The point where areas 2, 4, 5, 7 meet could be small outcrop with a lighthouse perhaps).
  
  But it is topologically equivalent to the following diagram, which has horizontal and vertical symmetry:
  
  The four solutions found by the program correspond to the reflections of a single solution:
  
  LikeLike
  - Jim Randell 10:18 am on 21 March 2021 Permalink | Reply
    
    I think the derivations of the sea areas are:
    
    Angler → Fischer
    Back → Forth
    Catter → Dogger
    Dace → Sole
    Eighties → Forties
    Forkpoynt → Tyne
    Greigh → Wight
    Hegroom → Hebrides
    Intarsia → Fair Isle [knitting]
    
    LikeLike
  - Tony Brooke-Taylor 1:19 pm on 17 April 2021 Permalink | Reply
    
    I was curious about the possibility of other viable maps giving different solutions (and cross that I did not come up with the map that seems to work). Several weeks and a crash-course in graph theory later, I developed a routine that generates all possible combinations of 18 allowed borders and then applies constraints until it produces a unique solution. My conclusions are as follow:
    
    Combinations of 18 from the set of 26 allowed borders gives a long-list of 1562275 possibilities.
    
    Only 564 of these contain all 9 regions with 4 borders each.
    
    Only 9 of these are planar. I used Pyladder, which is a Python implementation of the graph planarity algorithm sourced from ‘Efficient Planarity Testing’ by John Hopcroft and Robert Tarjan. See https://github.com/haraldujc/pyladder
    
    As far as I can see, there is no reason why any of these 9 might not, in principle, be valid. They do not all give the same result for Angler. However, if we apply a couple more constraints to the coastal regions, we do get Jim’s solution uniquely:
    1 – one of the 9 only has 2 coastal-coastal borders, so the ‘island’ would be two islands.
    2 – only one of the 9 has exactly 2 coastal borders per coastal region. All of the others have at least one coastal region with either 1 or 3 coastal borders. If we assume that the coastal regions represent quadrants of the island (which makes sense) then they will indeed have two coastal neighbours each. Hence the unique solution has that form.
    
    LikeLike
    - Jim Randell 10:24 am on 21 April 2021 Permalink | Reply
      
      @Tony:
      
      Interesting. I did wonder if there was a programmatic way to generate viable graphs in order to show uniqueness (or otherwise).
      
      I had a brief tussle with planar graphs when solving Enigma 1035.
      
      LikeLike
    - Jim Randell 5:29 pm on 25 October 2021 Permalink | Reply
      Having been looking at packages to manipulate graphs for Teaser 3083, I thought I’d revisit this problem.
      
      I wrote a Python program to generate all possible potential graphs, and output them in “graph6” format. I saved this to a file, so I could use the “nauty” tools on it. [ link ]
      
      The graphs generated have nodes 0-3 as the coastal regions, and nodes 4-8 are the off-shore regions. We generate all possible graphs with 4 connections between each of the nodes to give us a viable adjacency graph for the regions, but then add in an additional region to represent the island (9), which is adjacent to all 4 of the coastal regions.
      
      This program takes 7m22s to generate all possible graphs.
      
      from enigma import (subsets, ordered) # generate graphs with each node connected to K others def generate(K, ns, g=set()): # are we done? if not ns: yield g else: # deal with the next node n = ns[0] k = sum(n in x for x in g) if k <= K: # choose K - k edges to add ns_ = ns[1:] for xs in subsets(ns_, size=K - k): yield from generate(K, ns_, g.union(ordered(n, x) for x in xs)) # "graph6" format for a graph (edge list) import networkx as nx def graph6(g): g6 = nx.to_graph6_bytes(nx.Graph(g), header=0) return g6.decode(encoding="ascii").rstrip() # generate graphs: # 0, 1, 2, 3: are the 4 coastal regions # 4, 5, 6, 7, 8: are the off-shore regions for g in generate(4, [0, 1, 2, 3, 4, 5, 6, 7, 8]): # add in edges from the coastal regions to the island (9) g.update([(0, 9), (1, 9), (2, 9), (3, 9)]) # output in graph6 format print(graph6(g))
      
      And we can process the list of generated graphs as follows:
      
      # generate the graphs, and save those that are isomorphically distinct % python3 teaser3051g.py | shortg > graphs3051.g6 1024380 graphs read from stdin 494 graphs written to stdout # find which of them are planar % planarg graphs3051.g6 | showg 494 graphs read from graphs3051.g6, 1 written to stdout; 0.01 sec. Graph 1, order 10. 0 : 1 2 3 4; 1 : 0 2 6 7; 2 : 0 1 6 8; 3 : 0 4 7 9; 4 : 0 3 8 9; 5 : 6 7 8 9; 6 : 1 2 5 7 8; 7 : 1 3 5 6 9; 8 : 2 4 5 6 9; 9 : 3 4 5 7 8;
      
      Or without the intermediate file, just run:
      
      % python3 teaser3051g.py | shortg | planarg | showg
      
      The initial 1024380 generated graphs are reduced to a set of 494 isomorphically different graphs, and only 1 of these is planar.
      
      From the output we see that nodes 6-9 are the coastal regions, and 5 is the island itself, so 0-4 are the off-shore regions.
      
      And if we take my diagram and relabel it as follows:
      
      We see that the graph corresponds to the adjacency matrix that I started with, and this is the only possible layout.
      
      LikeLike
- Frits 1:39 pm on 14 March 2021 Permalink | Reply
  Without diagram or explanation of analysis (no permission was given).
  Same results as Jim (using same adjacency map).
```
from itertools import permutations

regions = "HFADBGICE"
d = dict()

# coastal regions       low/mid/high = 1/2/3
d["H"] = [2, 1, 2, 2, 2]
d["F"] = [2, 2, 2, 3, 1]
d["A"] = [3, 2, 2, 2, 2]
d["D"] = [3, 2, 1, 2, 2]

# offshore regions      low/mid/high = 1/2/3
d["B"] = [2, 3, 2, 3, 2]
d["G"] = [2, 2, 1, 2, 3]
d["I"] = [1, 2, 2, 2, 2]
d["C"] = [2, 3, 3, 2, 2]
d["E"] = [2, 2, 2, 1, 1]     

# the adjacency map             credit: Jim Randell
adj = [
  (1, 3, 6, 8), # 0
  (0, 2, 4, 6), # 1
  (1, 3, 4, 5), # 2
  (0, 2, 5, 8), # 3
  (1, 2, 6, 7), # 4
  (2, 3, 7, 8), # 5
  (0, 1, 4, 7), # 6
  (4, 5, 6, 8), # 7
  (0, 3, 5, 7), # 8
]

# generate "not bordering" dictionary
nb = {r: [] for r in regions}             # init dictionary      
for i, r1 in enumerate(regions): 
  for j, r2 in enumerate(regions): 
    if j == i: continue
    # check for opposite extremes
    if any(x * y == 3 for (x, y) in zip(d[r1], d[r2])):
      nb[r1] += [r2]
      
# check which region can be the outer region
outer = [r for r in regions[4:] 
          if not any(x for x in nb[r] if x in regions[4:])] 
          
if len(outer) == 1:
  outer = outer[0]
  cdict = {outer: 7}
else:
  outer = ""
  cdict = {}

# check offshore regions (except outer)
for p in permutations("BCEGI".replace(outer, "")):
  o2no = dict(zip(p, (4, 5, 6, 8)))
  
  # regions 4, 6 share a border
  if p[0] in nb[p[2]]: continue     
  
  # regions 5, 8 share a border
  if p[1] in nb[p[3]]: continue
  
  # check coastal regions
  for q in permutations("ADFH"):
    c2no = dict(zip(q, (0, 1, 2, 3)))
  
    # F shares a border with A, also D and H have to share a border
    if q[0] + q[2] in {"AF", "FA", "DH", "HD"} : continue
    
    # A and D don't share a border
    if abs(c2no["A"] - c2no["D"]) != 2: continue
    
    # C shares a border with A
    if c2no["A"] not in adj[o2no["C"]]: continue
 
    # B doesn't share a border with A 
    if c2no["A"] in adj[o2no["B"]]: continue
    
    # B doesn't share a border with H
    if c2no["H"] in adj[o2no["B"]]: continue
    
    # C doesn't share a border with H
    if c2no["H"] in adj[o2no["C"]]: continue
    
    # merge dictionaries (not using | as PyPy doesn't support it yet)
    comb = {**o2no, **c2no, **cdict}
    
    print("".join(k for k, v in comb.items() if v in adj[c2no["A"]]), 
          end = ": ")
    print(", ".join(str(v) + "->" + k 
          for k, v in sorted(comb.items(), key=lambda x: x[1])))
```
  LikeLike
- Tony Brooke-Taylor 11:32 am on 19 March 2021 Permalink | Reply
  
  I’ve spent hours trying to find a unique solution: manually (found a solution but could not prove unique), and with two entirely different approaches to looping and eliminating possibilities. However, I did not try a map that allowed one of the offshore regions to surround the entire space. Without allowing that, the only map I found topologically possible yielded three solutions. Oh well, I can console myself that my objective is to learn Python, not to second-guess problem-setters 🙂
  
  LikeLike
Jim Randell 8:35 am on 11 March 2021 Permalink | Reply
Tags: by: Victor Bryant ( 144 )
Teaser 2780: Calendar dice
From The Sunday Times, 3rd January 2016 [link] [link]

I have tried to make a calendar using some dice. To display the month I want to use three dice, with a capital letter on each of the faces to display:

[J A N] or [F E B] or [M A R] etc.

I chose the capital letters on the dice to enable me to go as far as possible through the year. Furthermore, it turned out that one particular die contained four vowels.

(a) What was the last month that I was able to display?
(b) What were the two other letters on that particular die?

[teaser2780]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell, Hugh Casement, and Frits are discussing. Toggle Comments
- Jim Randell 8:36 am on 11 March 2021 Permalink | Reply
  In upper case the only symbol that can be used for more than one letter is M/W, but W does not appear in the words we are interested in, so we can consider all the symbols to be unique. (In a standard font anyway).
  
  This Python program finds sets of dice that can make the maximum number of months, and then looks for sets that have a die with 4 vowels on. It runs in 1.18s.
  
  Run: [ @repl.it ]
```
from enigma import (subsets, Accumulator, first, diff, join, printf)

vowels = set('AEIOU')
months = "JAN FEB MAR APR MAY JUN JUL AUG SEP OCT NOV DEC".split()

# merge the symbols <ss> to the dice <ds>
def merge(ds, ss):
  rs = list()
  for (d, s) in zip(ds, ss):
    if s in d:
      rs.append(d)
    elif len(d) == 6:
      return
    else:
      rs.append(d + [s])
  return rs

# add words from <ws> to dice in <ds>
# return (<dice>, <number-of-words-remaining>)
def solve(ds, ws):
  # result so far
  yield (ds, len(ws))
  if ws:
    # put letters for the next word on the dice
    for ss in subsets(ws[0], size=len, select="mP"):
      ds_ = merge(ds, ss)
      if ds_:
        yield from solve(ds_, ws[1:])

# start with the first month
ds0 = list([x] for x in months[0])

# find dice with the fewest remaining words
r = Accumulator(fn=min, collect=1)
for (ds, n) in solve(ds0, months[1:]):
  r.accumulate_data(n, ds)

# output result
printf("months = {ms} [{n} sets of dice]",
  ms=join(first(months, len(months) - r.value), sep=" ", enc="[]"),
  n=len(r.data),
)

# look for solutions with 4 vowels on one die
fmt = lambda d: join(d, sep=" ", enc="[]") # format a die
for ds in r.data:
  ds = sorted(sorted(d) for d in ds)
  # find dice with (exactly) 4 vowels
  vs = list(d for d in ds if len(vowels.intersection(d)) == 4)
  if not vs: continue
  printf("dice = {ds}", ds=join((fmt(d) for d in ds), sep=" "))
  for d in vs:
    printf("-> {d} has 4 vowels; consonants = {c}", d=fmt(d), c=fmt(diff(d, vowels)))
```
  Solution: (a) The last month you would be able to display is OCT. (b) The consonants on the die with 4 vowels are R and Y.
  
  There are 108 sets of dice that can make JAN … OCT, but only 4 of them have a die with 4 vowels on:
  
  [A B L N S T] [A E O R U Y] [C F G J M P]
  [A B C L N S] [A E O R U Y] [F G J M P T]
  [A E O R U Y] [A F L N S T] [B C G J M P]
  [A C F L N S] [A E O R U Y] [B G J M P T]
  
  In each case the die with 4 vowels is: [A E O U] + [R Y]
  
  We can see that the vowel I does not occur in any of the words, so the four vowels must be [A E O U], and setting the middle die in our initial set of dice (line 31) to have these 4 symbols on to start with finds just the four sets of dice given above, and runs in 401ms.
  
  However, if we were to use lower case letters, then there are useful symbols that can be used for more than one letter:
  
  b / q
  d / p
  n / u
  
  And by replacing lines 3-4 with:
```
vowels = set('aeion')
months = ['jan', 'feb', 'mar', 'adr', 'may', 'jnn', 'jnl', 'ang', 'sed', 'oct', 'nov', 'dec']
```
  We find there are 10 sets of dice that can make all twelve months. (But none of them have a die containing 4 vowel symbols, so remove line 50 if you want to see them).
  
  LikeLike
- Hugh Casement 1:38 pm on 11 March 2021 Permalink | Reply
  
  If we cheat by using upper-case U turned sideways to make C, will that allow us to make DEC?
  
  LikeLike
  - Jim Randell 1:51 pm on 11 March 2021 Permalink | Reply
    
    @Hugh: It doesn’t let us get to DEC (we can’t fit a D in), but it means we don’t need a C to make OCT, so we free up a letter, which can be V, so we can get as far as NOV.
    
    If we can also use an upside down A to make a V, then we can fit the D in and get to DEC.
    
    I think there is scope for using specialised fonts that would allow some symbols to serve as multiple letters.
    
    LikeLike
- Hugh Casement 5:40 pm on 11 March 2021 Permalink | Reply
  
  Thanks, Jim. I was going to suggest turning the A upside down, though it’s possibly a worse cheat!
  
  I’m sure I’ve come across a variant of this puzzle, possibly by Martin Gardner. I have a vague recollection that all the months could be done except AUG which wasn’t needed because it was during the university long vacation.
  
  LikeLike
  - Jim Randell 8:45 pm on 14 March 2021 Permalink | Reply
    
    @Hugh: Removing AUG from the list in my program finds 6 sets of dice that can make the remaining 11 months.
    
    Also removing FEB has 30 sets of dice that can make the remaining 11 months, and 2 of the sets also have 4 vowels on one die.
    
    LikeLike
- Frits 1:54 pm on 12 March 2021 Permalink | Reply
```
# place the 4 vowels A, E, O and U on die number 2
#
# As either A or U also has to be on die 1 or 3 (in order to form AUG)
# there are only 18 -5 = 13 spots left for consonants

months = ['JAN', 'FEB', 'MAR', 'APR', 'MAY', 'JUN', 
          'JUL', 'AUG', 'SEP', 'OCT', 'NOV', 'DEC']

s = set()
for j in range(12):
  lets = "".join([x for x in months[j] if x not in "AEOU"])
  s = s | set(lets)
  print (f"{months[j]}: {len(list(s))} consonants {''.join(s)} ")

# JAN: 2 consonants JN
# FEB: 4 consonants JNFB
# MAR: 6 consonants JNFBMR
# APR: 7 consonants JNFBMRP
# MAY: 8 consonants JNFBMRPY
# JUN: 8 consonants JNFBMRPY
# JUL: 9 consonants JNFBMRPYL
# AUG: 10 consonants JNFBMRPYLG
# SEP: 11 consonants JNFBMRPYLGS
# OCT: 13 consonants JNFBMRPYLGSCT
# NOV: 14 consonants JNFBMRPYLGSCTV
# DEC: 15 consonants JNFBMRPYLGSCTVD
#
# so NOV and DEC can't be the last month to be displayed
#
# Assume last month to be displayed is OCT
#
# letter pairs on dice 1 and 3 but not on the same die (no order):
# v,G + F,B + C,T + S,P (E only on die 2) + J,N (because JUN and JAN)
# where v is A or U (extra vowel)
#
# suppose v = U -> in same group: P and M (APR and MAR), R and Y (MAR and MAY)
# this is impossible as group 1 and 3 already have 5 candidates
#
# suppose v = A 
# candidates for 2 empty spots on die 2: 
# NOT: F,B + C,T + S,P + J,N + G + L (as U only on die 2)
# leaving R, M, Y
#  -- suppose M and R on die 2: --> we can't form MAR anymore
#  -- suppose M and Y on die 2: --> we can't form MAY anymore
#  -- suppose R and Y on die 2: --> no inconsistency

# place A on die 1

# die 1: A  .  .  .  .  .
# die 2: A  E  O  U  R  Y
# die 3: .  .  .  .  .  .

# P must be on die 3 (APR) --> S on die 1
# M must be on die 3 (MAR)
# G must be on die 3 (AUG)
# L must be on die 1 (as F,B + C,T + J,N are pairs)
# J must be on die 3 (as L is on die 1) --> N on die 1

# die 1: A  S  L  N  .  .
# die 2: A  E  O  U  R  Y
# die 3: P  M  G  J  .  .

# this leaves 4 ways to place B, F, C and T

for x in ("BF", "FB"):
  for y in ("CT", "TC"):
    print("A S L N", x[0], y[0], end="  -  ")
    print("A  E  O  U  R  Y", end="  -  ")
    print("P  M  G  J", x[1], y[1])

# A S L N B C  -  A  E  O  U  R  Y  -  P  M  G  J F T
# A S L N B T  -  A  E  O  U  R  Y  -  P  M  G  J F C
# A S L N F C  -  A  E  O  U  R  Y  -  P  M  G  J B T
# A S L N F T  -  A  E  O  U  R  Y  -  P  M  G  J B C
```
  LikeLike
- Hugh Casement 5:45 pm on 12 March 2021 Permalink | Reply
  
  I still don’t know who published the no-August variant, or where, but I’ve found the solution scribbled in the margin of a book. It’s a wee bit shorter than the proof of Fermat’s last theorem: the three cubes bear the letters
  A B C S U V, D F J M O P, E L N R T Y
  With two further cubes we can make the numbers 01 to 31:
  0 1 2 3 4 5, 0 1 2 6 (which also serves as 9), 7, 8.
  
  LikeLike
Jim Randell 9:37 am on 9 March 2021 Permalink | Reply
Tags: by: John Halsall
Brain-Teaser 699: The deflating mangoes
From The Sunday Times, 8th December 1974 [link]

The Lotaseetas have a rather casual attitude to commerce. Every Monday morning, Ming, the rice-planter, gathers from the grove outside his bungalow a number of mangoes of uniform weight. For the rest of the week he uses these as weights for measuring out the rice on his scales, charging each customer according to the number of mangoes required to balance the weight purchased.

Unfortunately, the mangoes themselves lose a fixed percentage of their weight each day by evaporation. However, Ming roughly compensates for this by using two mangoes as the unit on Wednesdays and Thursdays and three on Fridays. Clearly, Wednesday is a good day for buying rice, and Tuesday is a bad day.

His first customer at precisely 10 o’clock each morning (they are late risers) is Fung, the rice merchant, who always buys the same quantity of rice for his shop. On Monday Fung’s rice cost him 243 cowries. On Friday it cost him 256 cowries.

How much did it cost him on Tuesday?

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

[teaser699]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 9:38 am on 9 March 2021 Permalink | Reply
  
  If each mango weighs m on Monday, and each day its weight reduces to a fraction f⋅m the following day then the weight of each mango (at 10am) on each of the 5 days is:
  
  Mon = m
  Tue = f⋅m
  Wed = (f^2)m
  Thu = (f^3)m
  Fri = (f^4)m
  
  And the units of weight on each day are therefore:
  
  Mon = m
  Tue = f⋅m
  Wed = 2(f^2)m
  Thu = 2(f^3)m
  Fri = 3(f^4)m
  
  And on Monday rice of weight w cost 243, and on Friday the same weight cost 256:
  
  Mon = w / m = 243
  Fri = w / (3(f^4)m) = 256
  w = 243m = 256×3(f^4)m
  f^4 = 243/768 = 81/256
  f = 3/4
  
  So, how much did the rice cost on Tuesday?
  
  Tue = w / f⋅m = Mon / f
  Tue = 243 / (3/4) = 324
  
  Solution: On Tuesday the rice cost 324 cowries.
  
  The costs for each day are:
  
  Mon = 243
  Tue = 324
  Wed = 216
  Thu = 288
  Fri = 256
  avg = 265.4
  
  LikeLike
Jim Randell 9:39 am on 7 March 2021 Permalink | Reply
Tags: by: D. G. Beech
Brain-Teaser 25: [Exam results]
From The Sunday Times, 10th September 1961 [link]

“These examination results show that either the knowledge of mathematics, physics, and chemistry throughout the school is deplorable weak, or the papers were very stiff”, said the headmaster to the staff concerned.

“Unfortunately, I have mislaid the detailed list, but some of the figures are easy to remember. The number of pupils taking the three subjects was 440. In chemistry 200 passed; in physics 210 failed; and in mathematics 220 passed. Of those who passed in chemistry 66 failed in mathematics, whereas of those who passed in mathematics 22 failed in physics. I cannot recall the number of pupils who passed in all three subjects, or the number who failed in all three, but both these numbers were perfect squares”. At this stage the senior mathematics master got out his pencil and paper and started to puzzle it out.

(1) How many pupils failed in all three subjects?
(2) Of those who passed in chemistry, how many also passed in physics?

This puzzle was originally published with no title.

[teaser25]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
John Crabtree, Frits, and Jim Randell are discussing. Toggle Comments
- Jim Randell 9:40 am on 7 March 2021 Permalink | Reply
  For each of the three subjects a student can either pass or fail. So there are 8 regions in the corresponding Venn diagram.
  
  And if we had been given the square numbers for those that passed in all three subject and failed in all three subjects we would have 8 equations in 8 variables, so we would be able to work out the values for each of the variables.
  
  And the missing squares must be less than 15².
  
  The following Python program runs in 79ms.
```
from enigma import (matrix, as_int, subsets, powers, printf)

# solve the equations given values for MPC and X
def solve(MPC, X):

  # set up the equations
  eqs = [
    # X  M  P  C  MP MC PC MPC = k
    ((1, 1, 1, 1, 1, 1, 1, 1), 440),
    ((0, 0, 0, 1, 0, 1, 1, 1), 200),
    ((1, 1, 0, 1, 0, 1, 0, 0), 210),
    ((0, 1, 0, 0, 1, 1, 0, 1), 220),
    ((0, 0, 0, 1, 0, 0, 1, 0),  66),
    ((0, 1, 0, 0, 0, 1, 0, 0),  22),
    ((0, 0, 0, 0, 0, 0, 0, 1), MPC),
    ((1, 0, 0, 0, 0, 0, 0, 0),   X),
  ]

  # solve for non-negative integers
  try:
    (X, M, P, C, MP, MC, PC, MPC) = (as_int(x, "0+") for x in matrix.linear(eqs))
  except ValueError:
    return

  printf("X={X} M={M} P={P} C={C} MP={MP} MC={MC} PC={PC} MPC={MPC}")

# consider possible squares for X and MPC
for (MPC, X) in subsets(powers(0, 14, 2), size=2, select="M"):
  solve(MPC, X)
```
  Solution: (1) 144 pupils failed all three subjects; (2) 143 passed in chemistry and also physics.
  
  We can make a table of the regions of the Venn diagram
```
M P C = 121
M P - =  77
M - C =  13
M - - =   9
- P C =  22
- P - =  10
- - C =  44
- - - = 144
total = 440
```
  LikeLike
- Frits 12:25 pm on 8 March 2021 Permalink | Reply
  Based on Jim’s solution, with some analysis so no “==” operators are used (to avoid loops).
  
  @Jim, the generated code is not efficient as possible as there is a loop for O and Q when CF is already known.
```
from enigma import SubstitutedExpression, is_square

# the alphametic puzzle
p = SubstitutedExpression(
  [
  # X    M     P    C    MP   MC   PC   MPC
  
  #XYZ + MA + PDE + CF + HI + KL + OQ + STU = 440
  #"352 - XYZ - HI - STU = PDE",   # substitute MA + KL = 22 and CF + OQ = 66
  "352 - XYZ - HI - STU >= 0",
 
  #                 CF +      KL + OQ + STU = 200
  "112 + MA = STU",          # substitute CF + KL = 88 - MA - OQ
  
  #XYZ + MA +       CF +      KL            = 210
  "188 - CF = XYZ", 
  
  #      MA +            HI + KL +      STU = 220
  "198 - STU = HI",          # substitute KL = 22 - MA
  
  #                 CF +           OQ       = 66
  "66 - OQ = CF",
  
  #      MA +                 KL            = 22             
  "22 - MA = KL",
  
  "is_square(STU)",
  "is_square(XYZ)",
  ],
  answer="STU, HI, KL, MA, OQ, 352 - XYZ - HI - STU, CF, XYZ",
  d2i=dict([(0, "SX")] +
           [(k, "M") for k in range(3, 7)] +
           [(k, "MCO") for k in range(7, 10)]),
  distinct="",
  verbose=0
  )

for (_, ans) in p.solve():
  print("pupils failed in all three subjects =", ans[0])
  print("Of those who passed in chemistry", ans[0] + ans[4], 
        "also passed in physics")
```
  LikeLike
  - Frits 12:57 pm on 8 March 2021 Permalink | Reply
    
    It can easily be seen that MA has to be 9 (square 121) and CF has to be 19 or 44 (squares 169 and 144).
    
    LikeLike
- John Crabtree 5:15 pm on 10 March 2021 Permalink | Reply
  
  C = 66 – CP and M = 22 – CM.
  From chemistry, CM + CMP = 200 – 66 = 134, with CM <= 22
  And so CMP = 121 and CM = 13.
  From maths, MP = 200 – 22 – CMP = 77
  From physics, P = 230 – MP – CP – CMP = 32 – CP, and so CP <= 32
  From all eight variables, 318 – CP + X = 440, ie X = 122 + CP
  And so X = 144 and CP = 22
  The answers follow directly.
  
  LikeLike
Jim Randell 4:34 pm on 5 March 2021 Permalink | Reply
Tags: by: Victor Bryant ( 144 )
Teaser 3050: Power struggle
From The Sunday Times, 7th March 2021 [link] [link]

Given any number, one can calculate how close it is to a perfect square or how close it is to a power of 2. For example, the number 7 is twice as far from its nearest perfect square as it is from its nearest power of 2. On the other hand, the number 40 is twice as far from its nearest power of 2 as it is from its nearest square.

I have quite easily found a larger number (odd and less than a million!) for which one of these distances is twice the other.

What is my number?

[teaser3050]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell, Frits, and Hugh Casement are discussing. Toggle Comments
- Jim Randell 4:45 pm on 5 March 2021 Permalink | Reply
  A brute force approach in Python can search the solution space in 215ms. If we stop after the first candidate solution is found, then it only takes 72ms.
```
from enigma import (isqrt, irange, printf)

# distance to nearest square
def dist_sq(n):
  x = isqrt(n)
  return min(n - x**2, (x + 1)**2 - n)

# distance to nearest power of 2
def dist_p2(n):
  x = n.bit_length()
  return min(2**x - n, n - 2**(x - 1))

# find solutions
for n in irange(41, 1000000, step=2):
  d1 = dist_sq(n)
  d2 = dist_p2(n)
  if d1 == 2 * d2 or d2 == 2 * d1:
    printf("{n} -> dist_sq = {d1}, dist_p2 = {d2}")
    break  # we only need the first solution
```
  Solution: Your number is 32775.
  
  There aren’t many odd numbers with this property.
  
  The first 5 are:
  
  7
  32775
  134223231
  2147479015
  549756110751
  
  LikeLike
  - Jim Randell 12:18 pm on 6 March 2021 Permalink | Reply
    Here’s an alternative approach that considers numbers at increasing distances from the sets of “markers”.
    
    Also we can see that powers of 2 (greater than 1) are all even, and we are looking for an odd number n > 40, so its distance d to a power of 2 must be odd, and its distance to a square must be 2d. This reduces the number of checks we need to make.
    
    The following Python program runs in 50ms.
```
from enigma import (first, lt, powers, irange, inf, tuples, intersect, printf)

# markers less than 1 million
M = 1000000
count = lt(M)
squares = first(powers(0, inf, 2), count=count)
pow2s = first((2**i for i in irange(0, inf)), count=count)

# generate numbers at a distance <d> from the nearest marker in <ms>
def dist(ms, d):
  for (ml, m, mr) in tuples(ms, 3):
    n = m - d
    if n - ml > d: yield n
    n = m + d
    if mr - n > d: yield n

# generate odd numbers at twice the distance from
# a square than from a power of 2
def solve():
  # consider increasing odd distances to a power of 2
  for d in irange(1, inf, step=2):
    d2 = 2 * d
    # distance d from pow2s, 2d from squares
    for n in intersect([dist(pow2s, d), dist(squares, d2)]):
      printf("[{n} -> dist_p2 = {d}, dist_sq = {d2}]")
      yield n

# find the first odd solution, greater than 40, less than M
for n in solve():
  if 40 < n < M:
    printf("answer = {n}")
    break
```
    LikeLike
  - Jim Randell 9:30 am on 14 March 2021 Permalink | Reply
    This program finds the 5 odd solutions given above, and larger ones (by default it outputs the first 10 it finds), by examining the two squares surrounding each odd power of 2:
```
from enigma import (irange, inf, isqrt, div, first, arg, printf)

# generate candidate solutions
def generate():
  # consider increasing odd powers of 2
  for i in irange(3, inf, step=2):
    p = 2**i
    # and the square below
    n = isqrt(p)
    # look for candidate solutions
    n2 = n * n
    n21 = n2 + 2 * n + 1
    p2 = 2 * p
    # and check viability
    for x in [div(p2 + n2, 3), p2 - n2]:
      if x and x % 2 == 1 and x - n2 < n21 - x:
        printf("[{x} -> dist_p2 = {dp2}, dist_sq = {dsq}]", dp2=abs(p - x), dsq=x - n2)
        yield x
    for x in [div(p2 + n21, 3), p2 - n21]:
      if x and x % 2 == 1 and n21 - x < x - n2:
        printf("[{x} -> dist_p2 = {dp2}, dist_sq = {dsq}]", dp2=abs(p - x), dsq=n21 - x)
        yield x

# find the first N solutions
N = arg(10, 0, int)
first(generate(), N)
```
```
% time python3 teaser/teaser3050d.py 10
[7 -> dist_p2 = 1, dist_sq = 2]
[32775 -> dist_p2 = 7, dist_sq = 14]
[134223231 -> dist_p2 = 5503, dist_sq = 11006]
[2147479015 -> dist_p2 = 4633, dist_sq = 9266]
[549756110751 -> dist_p2 = 296863, dist_sq = 593726]
[8796091840375 -> dist_p2 = 1181833, dist_sq = 2363666]
[140737493172567 -> dist_p2 = 4817239, dist_sq = 9634478]
[2251799795854807 -> dist_p2 = 17830441, dist_sq = 35660882]
[36028797113301975 -> dist_p2 = 94338007, dist_sq = 188676014]
[576460752294331351 -> dist_p2 = 9092137, dist_sq = 18184274]
python3 teaser/teaser3050d.py 10  0.03s user 0.01s system 92% cpu 0.048 total
```
    LikeLike
- Hugh Casement 2:07 pm on 6 March 2021 Permalink | Reply
  
  I assume that “number” means integer: the setters of these puzzles have never been able to tell the difference.
  
  The logarithm of n to base 2, q = ln(n) / ln(2). We round to the nearest integer and take 2^q.
  
  Having written and run a Basic program in about one minute, I decided to look for even numbers.
  There are dozens, starting with 54, 114, 278, 546, 982, 2002, 4182, 8370, …
  The program was ten lines: I never expected Basic to be more compact than Python.
  
  LikeLike
- Frits 1:06 pm on 7 March 2021 Permalink | Reply
  A variation of Jim’s second program (more efficient).
```
from enigma import first, powers, irange, inf, tuples, intersect, printf, \
                   isqrt
# markers less than 1 million
M = 1000000
squares = first(powers(0, inf, 2), count=(lambda x: x < M))
pow2s = first((2 ** i for i in irange(0, inf)), count=(lambda x: x < M))
 
# generate numbers at a distance <d> from the nearest marker in <ms>
def dist(ms, d):
  for (ml, m, mr) in tuples(ms, 3):
    n = m - d
    if n - ml > d: yield n
    n = m + d
    if mr - n > d: yield n
 
# generate odd numbers at twice the distance from
# a square than from a power of 2
def solve():
  # consider increasing odd distances to a power of 2
  for d in irange(1, inf, step=2):
    d2 = 2 * d
    for n in dist(pow2s, d): 
      # is there a square at distance 2d from n?
      if n - d2 in squares or n + d2 in squares:
        # is it the nearest square?
        x = isqrt(n)
        x2 = x * x
        x2n = x2 + 2 * x + 1
        nearest = x2 if n - x2 < x2n - n else x2n
        if nearest in {n - d2, n + d2}:
          printf("[{n} -> dist_p2 = {d}, dist_sq = {d2}]")
          yield n

# find the first odd solution, greater than 40, less than M
for n in solve():
  if 40 < n < M:
    printf("answer = {n}")
    break
```
  LikeLike
  - Jim Randell 2:53 pm on 7 March 2021 Permalink | Reply
    
    @Frits: I thought that a “hybrid” approach of my two programs would probably be faster. Although my second program has an internal runtime of 2.74ms, so I didn’t think it was worth the extra code.
    
    Interestingly when I timed the code you posted it ran slightly slower than my version (3.03ms). It might be faster the other way around (generating distances from squares and then calculating distances from powers of two), as I would assume that [[ int.bit_length() ]] is probably faster than [[ math.isqrt() ]] (certainly the code in enigma.py for [[ isqrt() ]] starts by calling [[ int.bit_length() ]], and then does more stuff. (Although if [[ math.isqrt() ]] is available it just uses that, which should be implemented by native code).
    
    LikeLike
    - Frits 5:01 pm on 7 March 2021 Permalink | Reply
      @Jim, I have tested with the Brian Gladman’s Timer function (which uses perf_counter_ns ) doing 200 runs (jra3 is my variation on your jra2 and jra4 a variation on jra2 the other way around (looking at distances from squares and then checking distances from powers of two)).
      
      PyPy: jra1 1.579 ms jra2 2.629 ms jra3 146.700 us jra4 539.500 us Python 3.9.0: jra1 23.978 ms jra2 5.238 ms jra3 2.547 ms jra4 4.525 ms
      
      I would have been surprised in jra4 was faster than jra3 as the distances from squares generates many elements (like 1900).
      
      LikeLike
      - Jim Randell 12:06 pm on 8 March 2021 Permalink | Reply
        
        @Frits: I suppose it goes to show that different timing strategies produce different results.
        
        For a piece of Python code that is only going to be executed once I think that a 3ms internal runtime is perfectly fine. This run time is dwarfed by the amount of additional time the Python interpreter takes getting ready to run it, so in my preferred measure of execution time both the programs give an external runtime of 50ms.
        
        For code that is going to be executed thousands of times it may be worth shaving a few milliseconds off it, but code that is only executed once I’m not so sure.
        
        I wanted my programs to show two different approaches. My first program defines functions that calculate the two distances and then compares them. But there are nearly 500,000 candidate numbers, so this could involve a lot of calculation.
        
        The second program makes a set of markers, and then looks at numbers that are fixed distances from the markers, so it is essentially a searching strategy. In this case the distances involved in the solution aren’t very large, so the searching strategy wins.
        
        LikeLike
    - Frits 3:05 pm on 8 March 2021 Permalink | Reply
      
      @Jim,
      
      Talking about isqrt:
      
      have you considered using math.sqrt in enigma.py’s isqrt() if math.isqrt is not available (like in an up-to-date PyPy) for numbers under a certain limit? See Brian Gladman’s number_theory.py.
      
      LikeLike
      - Jim Randell 6:46 pm on 8 March 2021 Permalink | Reply
        
        My original version of isqrt() used a float square root to provide an initial guess, and then applied Newton’s method until the result settled down to an integer. (See this comment on Enigma 1759).
        
        But I switched that to a binary technique I found on Wikipedia [ @wikipedia ] which performed better for numbers that overflowed floats.
        
        But looking at it again it turns out that that was because I was choosing a poor initial guess in the overflow case. It turns out you can do a much better guess using the fact that int.bit_length() behaves roughly like log2().
        
        So I think I’ll switch back to using Newton’s method for cases where math.isqrt() is not available.
        
        BTW: For a very fast implementation of isqrt() check out gmpy2.isqrt().
        
        LikeLike
- Hugh Casement 1:20 pm on 7 March 2021 Permalink | Reply
  Isn’t this simpler?
```
defdbl a - z
for n = 41.0 to 999999.0 step 2.0
      p = int(log(n)/log(2.0) + 0.5)
      pp = 2.0^p
      dp = abs(pp - n)
      s = int(sqr(n) + 0.5)
      ss = s*s
      ds = abs(ss - n)
      if dp = 2.0*ds or ds = 2.0*dp then print n pp ss
next n
```
  Turbo Basic has a log2 function, which would have made the third line a bit more compact.
  Of course some expressions could be combined, but at a slight loss of transparency.
  The .0 are not strictly necessary but make sure the numbers are interpreted as floating-point (single-length integers go only to 32767).
  
  LikeLike
  - Jim Randell 1:55 pm on 7 March 2021 Permalink | Reply
    @Hugh: (I put your code into [code] ... [/code] tags so it should look better now).
    
    It is simpler, but it doesn’t calculate accurate values:
    
    e.g. The nearest power of 2 to 46 is 32, which gives a distance of 14:
```
>>> dist_p2(46)
14
>>> f = lambda n: abs(2**intr(log2(n)) - n)
>>> f(46)
18
```
    You have to go much higher before the calculation of the nearest square breaks down (much more than a million), probably due to exceeding the precision of floating point numbers. (e.g. It fails at 10^37).
    
    LikeLike
  - Frits 2:00 pm on 7 March 2021 Permalink | Reply
    Hi Hugh,
    
    Your program suffers from the same problem Erling Torkildsen had at PuzzlingInPython (dp should be 107 iso 149 for n = 363).
```
from math import log2

for n in range(41, 1000000, 2):
  #p = int(log2(n) + 0.5)
  p = round(log2(n))
  pp = 2 ** p
  dp = abs(pp - n)
  #s = int(n ** 0.5 + 0.5)
  s = round(n ** 0.5)
  ss = s * s
  ds = abs(ss - n)
  if n == 363:
    print("n =", n, "p =", p, "pp =", pp, "dp =", dp, "ds =", 
          ds, "s =", s, "ss =", ss)
  if dp == 2 * ds or ds == 2 * dp:
    print(n, pp, ss)
    break

# n = 363 p = 9 pp = 512 dp = 149 ds = 2 s = 19 ss = 361
```
    LikeLike
- Frits 4:52 pm on 9 March 2021 Permalink | Reply
  Looping over the power of 2 entries.
```
# suppose p2 (2 ** p) is the power of 2 is the nearest power 
# let s^2 be the nearest square smaller equal to p2 
# so that s^2 <= p2 <= (s + 1)^2 
# example:  484 <= 512 <= 529 with s = 22 and p2 = 2 ** 9       

#          +--- 2s-1 ---+----- 2s + 1 ----+--- 2s + 3 --+  
#          |            |                 |             |
#  ---- (s - 1)^2 ---- s^2 --- p2 ---- (s + 1)^2 --- (s + 2)^2 ---
#

# even power exponents are also squares so ignore them
for p in range(5, 21, 2):
  p2 = 2 ** p
  s = int(sqrt(p2))
  s2 = s ** 2
 
  # can x be between (s - 1)^2 and s^2 ?
  # then ds is maximal s - 1 and d2 is maximal (s - 1) / 2
  minx = min(p2 - ((s - 1) // 2), s2)

  # make sure minx is odd and ... 
  minx = minx + (minx % 2 == 0) 

  # ... ds is not a multiple of 4 and 
  minx = minx +  2 * (minx % 4 == 1) 
  
  # if s2 is even then first entries have an odd ds
  if s2 % 2 == 0:
    minx += s - 2
    
  # can x be between (s + 1)^2 and (s + 2)^2 ?
  # then ds is maximal s + 1 and d2 is maximal (s + 1) / 2
  maxx = max(p2 + ((s + 1) // 2), s2 + 2 * s + 1)
  
  # if s2 is odd then last entries have an odd ds
  if s2 % 2 :
    maxx -= s + 1
  
  # consider odd x's so that ds is not a multiple of 4
  for x in range(minx, maxx + 1, 4):
    # determine nearest square             
    y = int(sqrt(x))
    y2 = y ** 2
    ds = min(x - y2, y2 + 2 * y + 1 - x)  
    
    # determine nearest power of 2              
    y2min1 = 2 ** (x.bit_length() - 1)   
    d2 = min(2 * y2min1 - x, x - y2min1)
    
    # distance from x to power of 2 is always odd 
    # so ds = 2 * d2 (and not d2 = 2 * ds)
    if ds == 2 * d2:        
      print(f"number is {x}; distance to power of 2: {d2}; to square: {ds}")
      exit() # we only need the first
```
  LikeLike
Jim Randell 8:47 am on 4 March 2021 Permalink | Reply
Tags: by: Susan Bricket ( 17 )
Teaser 2778: Cold turkey
From The Sunday Times, 20th December 2015 [link] [link]

We are having a “cold turkey” party on Boxing Day. Fewer than 100 people have indicated that they are coming, and the percentage of them choosing the vegetarian option is (to the nearest whole number) a single-digit number. My vegetarian aunt might also come. If she does, then (to the nearest whole number) the percentage having the vegetarian option will remain the same.

If she does come, how many people will be there and how many of them will have the vegetarian option?

[teaser2778]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 8:48 am on 4 March 2021 Permalink | Reply
  This Python program runs in 47ms.
  
  Run: [ @repl.it ]
```
from enigma import divf, irange, printf

# percentage a/b to the nearest whole number
percent = lambda a, b: divf(200 * a + b, 2 * b)

# total number of people expected (including aunt)
for n in irange(2, 100):
  # consider number of vegetarians
  for v in irange(1, n):
    # percentage vegetarians (to nearest whole number)
    p = percent(v, n)
    if p > 9: break

    # and if aunt doesn't come, is percentage the same?
    if percent(v - 1, n - 1) == p:
      # output solution
      printf("{n} total; {v} veg [{p}% veg]")
```
  Solution: If the aunt comes there will be 95 people in total. 9 of them vegetarian.
  
  In this case the percentage of vegetarians is 9/95 ≈ 9.47%, which rounds down to 9%.
  
  But if the aunt doesn’t come both the number of guests and the number of vegetarians is reduced by 1, giving a percentage of 8/94 ≈ 8.51%, which rounds up to 9%.
  
  Note that Python 3’s built-in [[ round() ]] function might not do what you expect:
```
% python3.9
>>> round(11.5)
12
>>> round(12.5)
12
>>> round(1.15, 1)
1.1
>>> round(0.115, 2)
0.12
```
  The decimal module allows more control over rounding behaviour.
  
  To keep things predictable, in my program I avoided float approximations by keeping the calculations in the integer domain, and I used the common “round half up” rule.
  
  LikeLike

	GeoffR on Teaser 2442: [Gaming mach…
	Jim Randell on Teaser 2442: [Gaming mach…
	Frits on Teaser 3314: Number unobt…
	Jim Randell on Teaser 3314: Number unobt…
	GeoffR on Teaser 3314: Number unobt…
	Jim Randell on Teaser 3314: Number unobt…
	Jim Randell on Teaser 3310: Building bri…
	Ruud on Teaser 2449: [Numbers of …

Search

Recent Posts

Recent Comments

Archives

Categories

Subscribe

RSS Links

Site Stats

Meta

Recent Updates Page 44 Toggle Comment Threads | Keyboard Shortcuts

Jim Randell 9:05 am on 4 April 2021 Permalink | Reply Tags: by: Dr K Ollerenshaw

Rate this:

Share:

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

Reply Cancel reply

Jim Randell 6:03 pm on 1 April 2021 Permalink | Reply Tags: by: Howard Williams ( 44 )

Rate this:

Share:

Jim Randell 9:50 pm on 1 April 2021 Permalink | Reply

Jim Randell 8:27 am on 2 April 2021 Permalink | Reply

Frits 10:42 am on 2 April 2021 Permalink | Reply

Jim Randell 11:39 am on 2 April 2021 Permalink | Reply

Frits 9:55 pm on 1 April 2021 Permalink | Reply

Jim Randell 10:36 pm on 1 April 2021 Permalink | Reply

Frits 10:53 pm on 1 April 2021 Permalink | Reply

Jim Randell 6:28 pm on 3 April 2021 Permalink | Reply

Tony Brooke-Taylor 10:03 am on 4 April 2021 Permalink | Reply

Jim Randell 10:02 am on 1 April 2021 Permalink | Reply Tags: by: Graham Smithers ( 84 )

Rate this:

Share:

Jim Randell 10:04 am on 1 April 2021 Permalink | Reply

Jim Randell 11:29 am on 30 March 2021 Permalink | Reply Tags: by: Brig A G H Brousson ( 2 )

Rate this:

Share:

Jim Randell 11:30 am on 30 March 2021 Permalink | Reply

Frits 1:52 pm on 30 March 2021 Permalink | Reply

Jim Randell 4:25 pm on 31 March 2021 Permalink | Reply

Frits 12:42 pm on 31 March 2021 Permalink | Reply

Frits 1:29 pm on 31 March 2021 Permalink | Reply

Jim Randell 7:03 pm on 31 March 2021 Permalink | Reply

Jim Randell 9:05 am on 29 March 2021 Permalink | Reply Tags: by: L. J. Upton

Rate this:

Share:

Jim Randell 9:06 am on 29 March 2021 Permalink | Reply

Jim Randell 6:01 pm on 29 March 2021 Permalink | Reply

Jim Randell 8:57 am on 28 March 2021 Permalink | Reply Tags: by: Ptolemaeus ( 5 )

Rate this:

Share:

Jim Randell 8:58 am on 28 March 2021 Permalink | Reply

John Crabtree 4:34 pm on 30 March 2021 Permalink | Reply

Jim Randell 5:01 pm on 26 March 2021 Permalink | Reply Tags: by: Danny Roth ( 87 )

Rate this:

Share:

Jim Randell 5:04 pm on 26 March 2021 Permalink | Reply

Frits 10:40 pm on 26 March 2021 Permalink | Reply

Tony Brooke-Taylor 9:02 pm on 28 March 2021 Permalink | Reply

Frits 10:57 am on 29 March 2021 Permalink | Reply

Tony 6:01 pm on 29 March 2021 Permalink | Reply

Hugh Casement 12:51 pm on 27 March 2021 Permalink | Reply

Jim Randell 3:36 pm on 27 March 2021 Permalink | Reply

Hugh Casement 1:14 pm on 30 March 2021 Permalink | Reply

GeoffR 1:39 pm on 20 May 2021 Permalink | Reply

Dirk 9:43 am on 9 July 2021 Permalink | Reply

Jim Randell 8:24 am on 25 March 2021 Permalink | Reply Tags: by: J S Rowley ( 9 )

Rate this:

Share:

Jim Randell 8:26 am on 25 March 2021 Permalink | Reply

Hugh Casement 1:45 pm on 25 March 2021 Permalink | Reply

Jim Randell 9:07 am on 23 March 2021 Permalink | Reply Tags: by: Susan Bricket ( 17 )

Rate this:

Share:

Jim Randell 9:08 am on 23 March 2021 Permalink | Reply

Frits 12:39 pm on 23 March 2021 Permalink | Reply

Jim Randell 10:41 pm on 21 March 2021 Permalink | Reply Tags: by: Mrs. K. Y. Gunson

Rate this:

Share:

Jim Randell 10:42 pm on 21 March 2021 Permalink | Reply

Frits 10:02 am on 22 March 2021 Permalink | Reply

John Crabtree 4:16 pm on 23 March 2021 Permalink | Reply

Jim Randell 4:40 pm on 19 March 2021 Permalink | Reply Tags: by: Stephen Hogg ( 64 )

Jim Randell 9:05 am on 4 April 2021 Permalink | Reply
Tags: by: Dr K Ollerenshaw

Jim Randell 6:03 pm on 1 April 2021 Permalink | Reply
Tags: by: Howard Williams ( 44 )

Jim Randell 10:02 am on 1 April 2021 Permalink | Reply
Tags: by: Graham Smithers ( 84 )

Jim Randell 11:29 am on 30 March 2021 Permalink | Reply
Tags: by: Brig A G H Brousson ( 2 )

Jim Randell 9:05 am on 29 March 2021 Permalink | Reply
Tags: by: L. J. Upton

Jim Randell 8:57 am on 28 March 2021 Permalink | Reply
Tags: by: Ptolemaeus ( 5 )

Jim Randell 5:01 pm on 26 March 2021 Permalink | Reply
Tags: by: Danny Roth ( 87 )

Jim Randell 8:24 am on 25 March 2021 Permalink | Reply
Tags: by: J S Rowley ( 9 )

Jim Randell 9:07 am on 23 March 2021 Permalink | Reply
Tags: by: Susan Bricket ( 17 )

Jim Randell 10:41 pm on 21 March 2021 Permalink | Reply
Tags: by: Mrs. K. Y. Gunson

Jim Randell 4:40 pm on 19 March 2021 Permalink | Reply
Tags: by: Stephen Hogg ( 64 )

Jim Randell 8:28 am on 18 March 2021 Permalink | Reply
Tags: by: Eric Emmet ( 10 )

Jim Randell 8:14 am on 16 March 2021 Permalink | Reply
Tags: by: Victor Bryant ( 144 ), flawed ( 54 )

Jim Randell 10:34 am on 14 March 2021 Permalink | Reply
Tags: by: R. R. Brand

Jim Randell 4:57 pm on 12 March 2021 Permalink | Reply
Tags: by: Colin Vout ( 38 )

Jim Randell 8:35 am on 11 March 2021 Permalink | Reply
Tags: by: Victor Bryant ( 144 )

Jim Randell 9:37 am on 9 March 2021 Permalink | Reply
Tags: by: John Halsall