teaser-book-2021 | S2T2

Updates from March, 2020 Toggle Comment Threads | Keyboard Shortcuts

Jim Randell 5:09 pm on 6 March 2020 Permalink | Reply
Tags: by: Andrew Skidmore ( 85 )
Teaser 2998: Football league
From The Sunday Times, 8th March 2020 [link] [link]

In our league three points are awarded to a team for a win and one point goes to each team in a drawn match. In each division, the teams play each other twice per season.

Comparison of the results of the two divisions at the end of last season showed that:

(a) Division II had one more team than Division I.

(b) The same total number of points was awarded in each division.

(c) For the division with the larger number of drawn matches, that number was equal to the number of matches not drawn in the other division.

(d) The number of drawn matches in one division was a multiple of the (3-digit) number of drawn matches in the other.

How many teams were in Division II?

The puzzle text has been reworded slightly to reduce ambiguity.

[teaser2998]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell, Robert Brown, and GeoffR are discussing. Toggle Comments
- Jim Randell 5:54 pm on 6 March 2020 Permalink | Reply
  If there are n teams in a division, and each team plays each other team twice, then the total number of matches played is:
  
  2 C(n, 2) = n(n − 1)
  
  So, if Division I has n teams the total number of matches played is:
  
  t1 = n(n − 1)
  
  And Division II has n + 1 teams, so the total number of matches played is:
  
  t2 = (n + 1)n
  
  These totals are divided into drawn matches and not-drawn matches. If the division with the lower number of drawn matches has x drawn matches (x is a 3-digit number), then the other division has kx draws (where k > 1), and this means the original division has kx not-drawn matches.
  
  So the total number of matches for the division with the lower number draws is also expressible as (k + 1)x, and the total number of points is:
  
  pts = 2x + 3kx = (2 + 3k)x
  
  If the division with the higher number of draws (kx draws) has y not-draws, then we also have:
  
  pts = 2kx + 3y
  
  This Python 3 program runs in 73ms.
  
  Run: [ @repl.it ]
```
from enigma import (irange, inf, printf)

# check the total number of matches works
# tl = total number of matches for the division with the fewer draws
# th = total number of matches for the other division
# d = division with fewer draws
# return: (pts, (n1, t1, md1, mn1), (n2, t2, md2, mn2))
def check(d, tl, th, nl, nh):
  # divide the total into (k + 1) and x
  for k in irange(2, inf):
    (x, r) = divmod(tl, k + 1)
    if x < 100: break
    if r > 0 or x > 999: continue
    # calculate the number of points
    pts = (2 + 3 * k) * x
    y = th - k * x
    if 2 * k * x + 3 * y != pts: continue
    # return solution
    s = ((nl, tl, x, k * x), (nh, th, k * x, y))
    yield (pts,) + (s if d == 1 else s[::-1])

# find number of teams in each division
def solve():
  for n in irange(2, inf):
    (t1, t2) = (n * (n - 1), (n + 1) * n)
    yield from check(1, t1, t2, n, n + 1)
    yield from check(2, t2, t1, n + 1, n)

# output the first solution
for (pts, (n1, t1, md1, mn1), (n2, t2, md2, mn2)) in solve():
  printf("pts={pts} -> D1: n={n1} t={t1} md={md1} mn={mn1}; D2: n={n2} t={t2} md={md2} mn={mn2}")
  break
```
  Solution: There were 20 teams in Division II.
  
  There were 19 teams in Division I, giving a total of 342 matches. 114 of the matches were drawn, and the remaining 228 were won outright, giving a total number of points of 2×114 + 3×228 = 912.
  
  The 20 teams in Division II played a total of 380 matches. 228 of the matches were drawn (twice the number of drawn matches in Division I, and the same as the number of not-drawn matches in Division I), and the remaining 152 were won outright, giving a total number of points of 2×228 + 3×152 = 912.
  
  LikeLike
- Robert Brown 11:11 am on 7 March 2020 Permalink | Reply
  
  I found the first solution working by hand on the back of an envelope! But there are many solutions, and I don’t see anything in the text restricting the size of the divisions.
  
  LikeLike
  - Jim Randell 11:13 am on 7 March 2020 Permalink | Reply
    
    @Robert: Are you sure you are using all the information? I found there was only one solution (even though my program only outputs the first solution it finds, but I did have it check for divisions with up to 5000 teams).
    
    LikeLike
    - Jim Randell 12:02 pm on 7 March 2020 Permalink | Reply
      Some analysis allows us to fully explore the solution space, and confirm that there is only a single solution.
      
      We can derive the following expressions for x and k:
      
      x = n (n − 7) / 2
      k = (n + 5) / (n − 7)
      
      The values for n are thus limited by the acceptable values for x and k.
      
      Here is a Python 3 program that determines possible values for n:
      
      from enigma import (irange, inf, div, printf) for n in irange(8, inf): x = div(n * (n - 7), 2) if x < 100: continue if x > 999: break k = div(n + 5, n - 7) if k is None or k < 2: continue (t1, t2) = ((n - 1) * n, n * (n + 1)) printf("pts={(2 + 3 * k) * x} -> D1: n={n} t={t1} md={x} mn={k * x}; D2: n={n + 1} t={t2} md={k * x} mn={t2 - k * x}")
      
      Or the solution can be determined analytically:
      
      Restricting the value of n to positive integers, we have the following:
      
      x is a 3-digit number:
      
      100 ≤ n (n − 7) / 2 ≤ 999
      19 ≤ n ≤ 48
      
      k is a non-trivial integer multiplier:
      
      (n + 5) / (n − 7) ≥ 2
      n ≤ 19
      
      From which we see there is only a single possible value for n, which gives us the solution, and the values of the other parameters can be calculated.
      
      LikeLike
- GeoffR 11:09 am on 8 March 2020 Permalink | Reply
```
% A Solution in MiniZinc
include "globals.mzn";

var 1..50: Nteams;   % Division 2 teams
var 1..50: Mteams;   % Division 1 teams

var 100..999: Nnon_draw; var 100..999: Ndraw;
var 100..999: Mnon_draw; var 100..999: Mdraw;

% Number of matches for both divisions
constraint  Nteams * (Nteams - 1) == Nnon_draw + Ndraw;
constraint  Mteams * (Mteams - 1) == Mnon_draw + Mdraw;

% (a) Division 2 held one more team than Division I
constraint Nteams == Mteams + 1;

% (b) The same total number of points was awarded in each division
constraint Mnon_draw * 3 + Mdraw * 2 = Nnon_draw * 3 + Ndraw * 2;

% (c) For the division with the larger number of draws (drawn matches), 
% that number was equal to the number of matches not drawn in the other division.
constraint  Ndraw == Mnon_draw;

% (d) The number of draws in one division was a multiple 
% of the (3-digit) number of draws in the other
constraint Mdraw mod Ndraw == 0 \/ Ndraw mod Mdraw == 0; 

solve satisfy;

output [ "Division 2 teams = " ++ show(Nteams) ++ " No."
++ "\n" ++ "Division 1 teams = " ++ show(Mteams)  ++ " No."
++ "\n" ++ "Div2 draw = " ++ show(Ndraw) ++ ", Div2 non-draw = " ++ show(Nnon_draw) 
++ "\n" ++ "Div1 draw = " ++ show(Mdraw) ++ ", Div1 non-draw = " ++ show(Mnon_draw) 
 ];
```
  LikeLike
- Robert Brown 1:46 pm on 8 March 2020 Permalink | Reply
  
  I had made the classic error of awarding 1 point per draw to each division. As the points are awarded to teams, you get 2 points for every drawn match. Sorry about that!
  
  LikeLike
  - Jim Randell 10:27 am on 10 March 2020 Permalink | Reply
    
    I’ve modified the wording of the puzzle to (hopefully) clarify things.
    
    LikeLike
Reply Cancel reply
Required fields are marked *

Name *

Email *

Website

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Jim Randell 5:10 pm on 28 February 2020 Permalink | Reply
Tags: by: Stephen Hogg ( 62 )

Teaser 2997: Cemetery lottery symmetry

From The Sunday Times, 1st March 2020 [link] [link]

Our local cemetery conservation lottery tickets have four numbers for a line. Using eight different numbers, my two lines have several symmetries. For each line: just one number is odd; there is one number from each of the ranges 1-9, 10-19, 20-29 and 30-39, in that order; the sum of the four numbers equals that sum for the other line; excluding 1 and the numbers themselves, the 1st and 2nd numbers share just one factor — as do the 2nd and 3rd (a different factor) and the 3rd and 4th (another different factor) and, finally, the 4th and 1st.

Printed one line directly above the other, my top line includes the largest of the eight numbers.

What is the bottom line?

[teaser2997]

Jim Randell 5:31 pm on 28 February 2020 Permalink | Reply

This Python program runs in 129ms. (Internal runtime is 65ms).

Run: [ @replit ]

from enigma import (defaultdict, irange, subsets, gcd, divisors, intersect, singleton, printf)

# check x and y share a single divisor (not 1, x, y)
def divisor(x, y):
  return singleton(intersect(divisors(n) for n in (x, y)).difference([1, x, y]))

# collect sets of 4 numbers by sum
ns = defaultdict(list)

# consider possible values for the units digits
for (a, b, c, d) in subsets(irange(0, 9), size=4, select="M"):
  # a cannot be 0
  if a == 0: continue
  # only one of them is odd
  if sum(x % 2 == 1 for x in (a, b, c, d)) != 1: continue
  # construct the numbers
  b += 10
  c += 20
  d += 30
  # each consecutive pair shares a single divisor
  s = list(divisor(x, y) for (x, y) in ((a, b), (b, c), (c, d), (d, a)))
  if None in s: continue
  if len(set(s[:3])) != 3: continue

  ns[a + b + c + d].append((a, b, c, d))

# consider possible sums
for (t, vs) in ns.items():
  # choose two lines
  for (p, q) in subsets(vs, size=2):
    if len(set(p + q)) != 8: continue
    # the largest number is on the top line
    if max(q) > max(p): (p, q) = (q, p)
    printf("{p} / {q}")

Solution: The numbers on the bottom line are: 6, 15, 20, 34.

The numbers on the top line are: 4, 14, 21, 36.

These are the only two candidate lines that have the same sum (they both sum to 75).

There are three other candidate lines, but they all have different sums.

The full list of candidate lines is:

sum=69: (4, 14, 21, 30)
sum=73: (8, 14, 21, 30)
sum=75: (4, 14, 21, 36) (6, 15, 20, 34)
sum=79: (6, 15, 20, 38)

LikeLike

Frits 12:26 pm on 24 December 2020 Permalink | Reply

from enigma import SubstitutedExpression

# check if four combinations of 2 digits all have one common factor
def one_common_factor(s):
  # build list where nth and (n+1)th entry of <s> have only one common factor
  li = [a[0] for a in list(factors(x, y) for x, y in zip(s, s[1:] + s[:1])) 
        if len(a) == 1]
  # first three numbers in a list of four must be different
  return len(li) == 4 and len(set(li[:3])) == 3
  
# return common factors of <x> and <y> except 1 and numbers it self  
factors = lambda x, y: [i for i in range(2, min(x, y) // 2 + 1) 
                        if x % i == 0 and y % i == 0]
 
# the alphametic puzzle
p = SubstitutedExpression(
  [
  # top line      A, 10 + D, 20 + F, 30 + H
  # bottom line   I, 10 + K, 20 + M, 30 + O
   
  # the sum of the four numbers equals that sum for the other line
  "A + D + F + H == I + K + M + O",
  
  # just one number per line is odd
  "sum(x % 2 == 1 for x in (A, D, F, H)) == 1",
  "sum(x % 2 == 1 for x in (I, K, M, O)) == 1",
  
  # my top line includes the largest of the eight numbers
  "H > O",
  
  # the 1st and 2nd numbers share just one factor as do the 2nd and 3rd 
  # (a different factor) and the 3rd and 4th (another different factor) 
  # and, finally, the 4th and 1st.
  "one_common_factor([A, 10 + D, 20 + F, 30 + H])",
  "one_common_factor([I, 10 + K, 20 + M, 30 + O])",
  
  # eight different numbers
  "A != I",
  "D != K",
  "F != M",
  "H != O",
  ],
  answer="(A, 10 + D, 20 + F, 30 + H), (I, 10 + K, 20 + M, 30 + O)",
  # exclude single digit prime numbers
  d2i=dict([(k, "AI") for k in range(0, 4)] + [(5, "AI")] + [(7, "AI")]),
  env=dict(one_common_factor=one_common_factor),
  distinct="",
  verbose=0)   

# print answers 
for (_, ans) in p.solve():
  print(f"{ans}")
  
# ((4, 14, 21, 36), (6, 15, 20, 34))

LikeLike

Jim Randell 5:22 pm on 21 February 2020 Permalink | Reply
Tags: by: Victor Bryant ( 139 )

Teaser 2996: Piece it together

From The Sunday Times, 23rd February 2020 [link] [link]

I have some jigsaw-type pieces each consisting of one, two, three or four 1cm-by-1cm squares joined together without overlapping. The pieces are black on one side and white on the other, and they are all different. I have used all my pieces to simultaneously make some different-sized white squares in jigsaw fashion, with each square using more than one piece. Even if you knew what all my pieces were like, you would not be able to determine the sizes of my squares.

How many pieces do I have?

[teaser2996]

Jim Randell 8:55 pm on 21 February 2020 Permalink | Reply

(See also: Enigma 321).

There are only a limited number of 1-sided, 1-, 2-, 3-, 4-onimoes, and as the pieces are all different this gives us an upper limit to the total area of the squares.

It is fairly straightforward to narrow the required answer down to one of two values on the back of an envelope. But it is fun to make a constructive solution from scratch, so here goes…

The following program looks for possible total areas that can be made into multiple different squares.

We then select pieces with the appropriate area and attempt to construct the different sets of squares.

This Python 3 program is adapted from my initial solution to Enigma 321. It’s not hugely fast, but it does solve the problem in 19s.

from itertools import product
from copy import deepcopy
from enigma import (irange, inf, subsets, diff, first, printf)

# possible pieces in all possible orientations
pieces = [

  # 1 square - 1x1 block ["O1"]
  (
    [(0, 0)],
  ),

  # 2 squares - 2x1 block ["I2"]
  (
    [(0, 0), (1, 0)],
    [(0, 0), (0, 1)],
  ),

  # 3 squares - linear, 3x1 block ["I3"]
  (
    [(0, 0), (1, 0), (2, 0)],
    [(0, 0), (0, 1), (0, 2)],
  ),

  # 3 squares - L shape ["V3"]
  (
    [(0, 0), (1, 0), (1, 1)],
    [(1, 0), (0, 1), (1, 1)],
    [(0, 0), (1, 0), (0, 1)],
    [(0, 0), (0, 1), (1, 1)],
  ),

  # 4 squares - 4x1 block, ["I4"]
  (
    [(0, 0), (1, 0), (2, 0), (3, 0)],
    [(0, 0), (0, 1), (0, 2), (0, 3)],
  ),

  # 4 squares - square, 2x2 block ["O4"]
  (
    [(0, 0), (1, 0), (0, 1), (1, 1)],
  ),

  # 4 squares - T shape ["T4"]
  (
    [(1, 0), (0, 1), (1, 1), (2, 1)],
    [(0, 0), (0, 1), (1, 1), (0, 2)],
    [(0, 0), (1, 0), (2, 0), (1, 1)],
    [(1, 0), (0, 1), (1, 1), (1, 2)],
  ),

  # and now the chiral ones

  # 4 squares - Z shape ["Z4"]
  (
    [(0, 1), (1, 1), (1, 0), (2, 0)],
    [(0, 0), (0, 1), (1, 1), (1, 2)],
  ),

  # 4 squares - S shape ["Z4'", "S4"]
  (
    [(0, 0), (1, 0), (1, 1), (2, 1)],
    [(1, 0), (1, 1), (0, 1), (0, 2)],
  ),

  # 4 squares - L shape ["L4"]
  (
    [(0, 0), (0, 1), (0, 2), (1, 2)],
    [(0, 0), (1, 0), (2, 0), (2, 1)],
    [(1, 0), (1, 1), (1, 2), (0, 2)],
    [(0, 0), (0, 1), (1, 1), (2, 1)],
  ),

  # 4 squares - L shape ["L4'", "R4"]
  (
    [(0, 0), (1, 0), (1, 1), (2, 1)],
    [(0, 1), (1, 1), (2, 1), (2, 0)],
    [(0, 0), (0, 1), (0, 2), (1, 2)],
    [(0, 0), (0, 1), (1, 0), (2, 0)],
  ),
]

# try to place piece <p> at <x>, <y> in grid <grid> of dimensions <a>, <b>
# using label <n>
def place(p, y, x, n, grid, a, b):
  g = deepcopy(grid)
  for (dy, dx) in p:
    (py, px) = (y + dy, x + dx)
    try:
      q = g[py][px]
    except IndexError:
      return None
    if q is not None:
      return None
    g[py][px] = n
  return g

# try to fit pieces <ps> into grid <grid> of dimensions <a>, <b>
def fit(ps, n, grid, a, b):
  if not ps:
    yield grid
  else:
    # choose a piece
    for p in ps[0]:
      # try to place the piece at x, y
      for (y, x) in product(irange(0, a - 1), irange(0, b - 1)):
        g = place(p, y, x, n, grid, a, b)
        if g is not None:
          yield from fit(ps[1:], n + 1, g, a, b)

# select at least <n> pieces from <ps> with a total area of <k>
def select(ps, k, n):
  for i in irange(n, len(ps)):
    f = 0
    for s in subsets(ps, size=i):
      t = sum(len(p[0]) for p in s) 
      if t == k:
        yield s
      if not (t > k):
        f += 1
    if f == 0: break

# fit the pieces <ps> into squares with sides <squares>
def fit_squares(ps, squares, ss=[]):
  # are we done?
  if not ps:
    yield ss
  else:
    # try to fill the next square
    s = squares[0]
    # choose pieces with the right area
    for fs in select(ps, s * s, 2):
      # create an s x s empty grid and assemble the pieces in it
      grid = list([None] * s for _ in irange(1, s))
      for g in fit(fs, 1, grid, s, s):
        # fit the remaining squares
        yield from fit_squares(diff(ps, fs), squares[1:], ss + [g])

# find an example fit of the pieces <ps> into each of the list of squares <ss>
def solve(ps, ss):
  fs = list()
  for s in ss:
    f = first(fit_squares(ps, s))
    if not f: return
    fs.extend(f)
  return fs


# express n as a sum of increasing squares (minimum: m)
def sum_of_squares(n, m=1, s=[]):
  if n == 0:
    if len(s) > 1:
      yield s
  else:
    for i in irange(m, inf):
      i2 = i * i
      if i2 > n: break
      yield from sum_of_squares(n - i2, i + 1, s + [i])

# consider increasing total area of the squares
T = sum(len(p[0]) for p in pieces)
for n in irange(4 + 9, T):
  sqs = list(sum_of_squares(n, 2))
  if len(sqs) < 2: continue
  printf("total area = {n} -> squares = {sqs}")

  # choose some of the squares
  for ss in subsets(sqs, min_size=2):

    # make a set of polyominoes with the appropriate total area
    for ps in select(pieces, n, 2 * max(len(s) for s in ss)):

      # try and fit them into the squares
      fs = solve(ps, ss)
      if fs is None: continue

      # output solution (number of pieces), and constructed squares
      printf("  {m} pieces", m=len(ps))
      for (s, f) in zip(ss, fs):
        printf("  {s} -> {f}")
      printf()

There is only a single candidate area that can be expressed as the sum of different, non-unit squares in multiple ways.

There are two sets of pieces that can be assembled into the required squares, but they both have the same number of pieces (one set is a mirror image of the other), and so this gives the answer.

Solution: There are 9 jigsaw pieces.

The 9 pieces have a total area of 29, and can be assembled into a set of (2×2, 3×3, 4×4) squares, or a set of (2×2, 5×5) squares.

Here is a solution using the 9 pieces: O1, I2, I3, V3, I4, O4, L4, L4′, Z4.

Note that we can’t turn the pieces over, so L4 and its mirror image (L4′) are different pieces (you cannot rotate one of them to give the same shape as the other), as are Z4 and its mirror image (Z4′).

And here is another solution using the 9 pieces: O1, I2, I3, V3, I4, O4, L4, L4′, Z4′.

The second set uses Z4′ instead of Z4. These pieces are mirror images of each other, so any solution for the first set also gives a solution for the second set, by reflecting it.

There are no further solutions, even if we were are allowed to have squares that are the same size.

It occurred to me that the squares are the same sizes as the collection of Rubik’s cubes I have available to me, so here are the diagrams made with cubes:

(I’ve only got one 2×2×2 cube, so it has to be shared between the sets of squares).

LikeLike

Jim Randell 10:55 am on 23 February 2020 Permalink | Reply

I encapsulated the code that deals with polyominoes into a separate file [[ polyominoes.py ]] that can be used to solve this puzzle (and Enigma 321), and I switched to using Knuth’s Algorithm X, rather than the simplistic [[ fit() ]].

So the following program runs in a more reasonable 858ms.

Run: [ @repl.it ]

import polyominoes
from enigma import irange, inf, subsets, diff, first, printf

# select at least <n> pieces from <ps> with a total area of <k>
def select(ps, k, n):
  for i in irange(n, len(ps)):
    f = 0
    for s in subsets(ps, size=i):
      t = sum(len(p[0]) for p in s) 
      if t == k:
        yield s
      if not(t > k):
        f += 1
    if f == 0: break

# fit the pieces <ps> into squares with sides <squares>
def fit_squares(ps, squares, ss=[]):
  # are we done?
  if not ps:
    yield ss
  else:
    # try to fill the next square
    s = squares[0]
    # choose pieces with the right area
    for fs in select(ps, s * s, 2):
      # create an s x s empty grid and assemble the pieces in it
      for g in polyominoes.fit(fs, s, s):
        # fit the remaining squares
        yield from fit_squares(diff(ps, fs), squares[1:], ss + [g])

# find an example fit of the pieces <ps> into each of the list of squares <ss>
def solve(ps, ss):
  fs = list()
  for s in ss:
    f = first(fit_squares(ps, s))
    if not f: return
    fs.extend(f)
  return fs


# express n as a sum of increasing squares (minimum: m)
def sum_of_squares(n, m=1, s=[]):
  if n == 0:
    if len(s) > 1:
      yield s
  else:
    for i in irange(m, inf):
      i2 = i * i
      if i2 > n: break
      yield from sum_of_squares(n - i2, i + 1, s + [i])

# available pieces, and total area
pieces = polyominoes.shapes("O1 I2 I3 V3 O4 I4 T4 Z4 Z4' L4 L4'", "ONE_SIDED")

# consider increasing total area of the squares
T = sum(len(p[0]) for p in pieces)
for n in irange(4 + 9, T):
  sqs = list(sum_of_squares(n, 2))
  if len(sqs) < 2: continue
  printf("total area = {n} -> squares = {sqs}")

  # choose some of the squares
  for ss in subsets(sqs, min_size=2):

    # make a set of polyominoes with the appropriate total area
    for ps in select(pieces, n, 2 * max(len(s) for s in ss)):

      # try and fit them into the squares
      fs = solve(ps, ss)
      if fs is None: continue

      # output solution (number of pieces), and constructed squares
      printf("  {m} pieces", m=len(ps))
      for (s, f) in zip(ss, fs):
        printf("  {s} -> {f}")
      printf()

LikeLike

Robert Brown 12:57 pm on 25 February 2020 Permalink | Reply

This teaser reminds me of enigma 1491 (not on your site?) from 2008. Box of tiles 1×3, 2×4, 3×5 etc. Takes tiles out in order, one at a time, and tries to make a rectangle. Required to find a) smallest possible rectangle & b) next largest. Everyone could all do a) by hand, but b) needed a fairly complex program. Ongoing discussions gradually simplified the program algorithm, and ultimately we got it down to a series of steps that could be followed manually – could be done in about 10 minutes. It’s all on the newenigma site, but you need a user name & password to log in!

LikeLike
Robert Brown 1:03 pm on 25 February 2020 Permalink | Reply

Sorry, I misquoted that slightly – should say ‘required to find how many tiles for smallest rectangle’ (which of course has no gaps or overlaps)

LikeLike
- Jim Randell 2:20 pm on 25 February 2020 Permalink | Reply
  
  I remember Enigma 1491. It was a fun puzzle. My notes for it are here [ @enigmaticcode ].
  
  When it was originally published in 2008 I wrote a Perl program to solve it, but that took 50 minutes to run. So while it was running I coded up the same algorithm in C, and that ran in 11 seconds.
  
  When I came to add the puzzle to the Enigmatic Code site in 2012 I wrote a Python program using a slightly different approach, and found that it ran in 9.2s. Now the same program runs in just 2.5s (probably due to improvements in the PyPy environment — I’m still using the same laptop I was using in 2012).
  
  LikeLike

Jim Randell 4:58 pm on 14 February 2020 Permalink | Reply
Tags: by: Howard Williams ( 43 )

Teaser 2995: Pub celebration

From The Sunday Times, 16th February 2020 [link] [link]

While celebrating with friends in the pub, it was my round, and I worked out the number of ways that I could get everybody else’s drink wrong. I could remember the drinks (and they all wanted different drinks), but not who wanted which drink.

More friends arrived (there were fewer than twenty of us in total), and everyone still wanted different drinks. Again assuming that I could remember the drinks but not who wanted which drink, I worked out the number of ways that I could get everybody else’s drink wrong, and found that the number was 206 times the first number. Fortunately, it was no longer my round!

What was the second number?

[teaser2995]

Jim Randell 5:07 pm on 14 February 2020 Permalink | Reply
The number of derangements [ @wikipedia ] of a set of n objects is known as subfactorial(n), denoted !n. (See: Teaser 2779).

This Python program calculates !n recursively. It runs in 72ms.

Run: [ @repl.it ]
```
from enigma import irange, div, cached, printf

# count the number of derangements of n objects (!n)
@cached
def subfactorial(n):
  if n == 0: return 1
  return n * subfactorial(n - 1) + (-1 if n % 2 else 1)

# look for numbers p, q such that !q / !p = 206
for q in irange(2, 19):
  sq = subfactorial(q)
  m = div(sq, 206)
  if m is None: continue
  for p in irange(1, q - 1):
    sp = subfactorial(p)
    if sp == m:
      printf("!{p} = {sp} -> !{q} = {sq}")
```
Solution: The second number is 1854.

Initially the setter has 4 friends (!4 = 9), so there were 5 people in the group.

After the additional people arrived the setter had 7 friends (!7 = 1854 = 206 × 9), so there were 8 people in the group.

Manually we can use use the following recurrence relation to count derangements:

d(0) = 1
d(n) = n . d(n − 1) + {1 if n is even, −1 if n is odd}

This makes it easy to calculate values on a calculator, and is enough to find that d(7) ÷ 206 = d(4).

However beyond d(13) = 2290792932 my physical calculator runs out of digits. The Calculator app on my laptop has just enough digits to “manually” determine that d(19) (which has 17 digits) is also divisible by 206, but the result of the division is not a d value we have already encountered, so the solution is unique. (Of course Python has built-in bigint support, so doesn’t have a problem with the larger numbers).

LikeLike
- Jim Randell 9:24 am on 15 February 2020 Permalink | Reply
  And here is a solution that calculates !n iteratively.
  
  Run: [ @repl.it ]
```
from enigma import inf, div, printf

# generate (n, !n) pairs
def subfactorials(k=inf):
  (n, d, x) = (0, 1, -1)
  while n < k:
    yield (n, d)
    n += 1
    d = n * d + x
    x = -x

ds = list()
for (n, d) in subfactorials(20):
  m = div(d, 206)
  if m is not None:
    for (i, x) in enumerate(ds):
      if x == m:
        printf("!{i} = {m} -> !{n} = {d}")
  ds.append(d)
```
  We only need to check for the smaller case when !n is divisible by 206, which only happens in 2 non-trivial cases for the range of values applicable to the puzzle.
  
  The program also accumulates the sequence of subfactorials in the array [[ ds ]]. (See OEIS A000166 [ @oeis.org ]).
  
  LikeLike

GeoffR 1:09 pm on 17 February 2020 Permalink | Reply


# Uses a recurrent expression identified by Euler:
# i.e. a(n) = n * a(n-1) + (-1) ^ n

from itertools import combinations
from collections import defaultdict

d = defaultdict(list)

# initial values in derangement sequence of drinks wrong
D1, D2, D3 = 0, 1, 2

# further derangement values use Euler's recurrent sequence
# e.g. D4 is derangement value for four people
# ten derangements are sufficient to solve this teaser
# as D10 = 1,334,961 and D19 is 17 digits long

D4 = 4 * D3 + (-1)**4
D5 = 5 * D4 + (-1)**5
D6 = 6 * D5 + (-1)**6
D7 = 7 * D6 + (-1)**7
D8 = 8 * D7 + (-1)**8
D9 = 9 * D8 + (-1)**9
D10 = 10 * D9  + (-1)**10

# form a dictionary with keys as number of friends
# and values as number of ways drinks wrong for each group
d = {2:1, 3:2, 4:D4, 5:D5, 6:D6, 7:D7, 8:D8, 9:D9, 10:D10}

for k1, k2 in combinations(d.keys(),2):
  if k2 > k1 :
    # second number was 206 times the first number
    d1, r1 = divmod( d[k2], d[k1] )
    if d1 == 206 and r1 == 0:
      print (f"1st group of friends = {k1} No.")
      print (f"2nd group of friends = {k2} No.")

LikeLike

Frits 2:22 pm on 3 September 2020 Permalink | Reply

Fooling around after expressing subfactorial formulas (n+1, n+2 and n+3) in terms of !(n-1).

I am pretty sure that for n+4 a term n*(n+1)*(n+2)*(n+3)*(n+4) will occur.
This factor is too high (even for n=2).

 
from enigma import irange, cached
 
# count the number of derangements of n objects (!n)
# an alternative formula is n * subfactorial(n - 1) + (-1 if n % 2 else 1)
@cached
def subfactorial(n):
  if n == 0: return 1
  if n == 1: return 0
  return (n - 1) * (subfactorial(n - 1) + subfactorial(n - 2))
 
# !(n+1) / !(n-1) = n*(n+1) +/- n / !(n-1)
# !(n+2) / !(n-1) = n*(n+1)*(n+2) +/- (n+1)^2 / !(n-1)
# !(n+3) / !(n-1) = n*(n+1)*(n+2)*(n+3) +/- (n*(2n^2+4n+3)) / !(n-1)

minplus = [1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1]

for n in irange(3, 12):
  sn = subfactorial(n-1)
 
  if n*(n+1) + minplus[n]*n // sn == 206: 
    print(f"!{n-1} = {sn} -> !{n+1} = \
{n*(n+1)*sn + minplus[n]*n}")
  
  if n*(n+1)*(n+2) + minplus[n]*(n+1)**2 // sn == 206: 
    print(f"!{n-1} = {sn} -> !{n+2} = \
{n*(n+1)*(n+2)*sn + minplus[n]*(n+1)**2}")
  
  if n*(n+1)*(n+2)*(n+3) + minplus[n]*n*(2*n**2+4*n+3) // sn == 206: 
    print(f"!{n-1} = {sn} -> !{n+3} = \
{n*(n+1)*(n+2)*(n+3)*sn + minplus[n]*n*(2*n**2+4*n+3)}")
    
# Output:
#
# !4 = 9 -> !7 = 1854

LikeLike

Jim Randell 5:22 pm on 7 February 2020 Permalink | Reply
Tags: by: Bill Kinally ( 7 )
Teaser 2994: Consecutive sums
From The Sunday Times, 9th February 2020 [link] [link]

Amelia noticed that 15 is equal to 1+2+3+4+5 or 4+5+6 or 7+8, so there are three possible ways that it can be expressed as the sum of consecutive whole numbers. She then told Ben that she had found a three-digit number which can be expressed as the sum of consecutive whole numbers in just two different ways. “That’s interesting”, said Ben. “I’ve done the same, but my number is one more than yours”.

What is Ben’s number?

[teaser2994]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell, Frits, and Jim Randell are discussing. Toggle Comments
- Jim Randell 5:36 pm on 7 February 2020 Permalink | Reply
  The following Python program runs in 221ms.
  
  Run: [ @replit ]
```
from enigma import (defaultdict, subsets, irange, tri, printf)

# collect consecutive sums for 3-digit numbers
d = defaultdict(list)
for (i, j) in subsets(irange(1, 500), size=2):
  n = tri(j) - tri(i - 1)
  if 99 < n < 1000:
    d[n].append((i, j))

# find consecutive numbers expressible in 2 different ways
for (n, vs) in d.items():
  if len(vs) == 2:
    vs1 = d.get(n + 1, None)
    if vs1 and len(vs1) == 2:
      printf("{n} -> {vs}; {n1} -> {vs1}", n1=n + 1)
```
  Solution: Ben’s number is 289.
  
  289 can be expressed as:
  
  289 = 9 + 10 + 11 + 12 + 13 + 14 + 15 + 16 + 17 + 18 + 19 + 20 + 21 + 22 + 23 + 24 + 25
  289 = 144 + 145
  
  Amelia’s number is 288, which can be expressed as:
  
  288 = 28 + 29 + 30 + 31 + 32 + 33 + 34 + 35 + 36
  288 = 95 + 96 + 97
  
  LikeLike
  - Jim Randell 6:36 pm on 7 February 2020 Permalink | Reply
    Here is a neater program that uses the technique described in the comments of Enigma 1. It runs in 83ms.
    
    Run: [ @replit ]
```
from enigma import (divisors, irange, cache, printf)

S = cache(lambda n: sum(d % 2 for d in divisors(n)))

# find 2 consecutive 3-digit numbers with S(n) == 3
for a in irange(100, 998):
  b = a + 1
  if S(a) == 3 and S(b) == 3:
    printf("{a}, {b}")
```
    Analytically:
    
    In order for the numbers to have exactly 3 odd divisors they must be of the form:
    
    n = (2^k)(p^2)
    
    where p is an odd prime.
    
    And we are looking for two consecutive numbers, so one will be even and one will be odd (k = 0).
    
    We can look for 3-digit numbers manually, or programatically:
```
from enigma import (primes, tuples, printf)

# collect 3-digit numbers with S(n) = 3
ns = list()

# consider p^2 term
for p in primes.between(3, 31):
  n = p * p
  while n < 1000:
    if n > 99: ns.append(n)
    n *= 2
ns.sort()

# find consecutive pairs
for (a, b) in tuples(ns, 2):
  if b == a + 1:
    printf("{a}, {b}")
```
    We find the following 3-digit numbers with exactly 3 odd divisors:
    
    [p=3] 144, 288, 576
    [p=5] 100, 200, 400, 800
    [p=7] 196, 392, 784
    [p=11] 121, 242, 484, 968
    [p=13] 169, 338, 676
    [p=17] 289, 578
    [p=19] 361, 722
    [p=23] 529
    [p=29] 841
    [p=31] 961
    
    And there are only two consecutive numbers in this list:
    
    288 = (2^5)(3^2)
    289 = (2^0)(17^2)
    
    LikeLike
    - Frits 10:52 pm on 3 August 2020 Permalink | Reply
      Over the first 500 million numbers (> 99) only 2 consecutive numbers exist.
      
      from enigma import Primes, printf, irange # collect 3-digit numbers with S(n) = 3 ns = list() test = 500000000 # consider p^2 term for p in Primes(test).irange(3, test): n = p * p #print(n) while n < test**2: if n > 99: ns.append(n) n *= 2 ns.sort() # find consecutive pairs for i in irange(0, len(ns) - 2): if ns[i+1] == ns[i] + 1: printf("{ns[i]}, {ns[i+1]}")
      
      Output:
      
      288, 289
      1681, 1682
      
      LikeLike
      - Jim Randell 10:24 am on 4 August 2020 Permalink | Reply
        
        @Frits: I found some notes (and a program) that I wrote at the time on looking for larger solutions:
        
        For consecutive numbers one of the following equations must hold:
        
        p² − (2^k)q² = +1
        p² − (2^k)q² = −1
        
        where p and q are odd primes.
        
        So we can consider solutions to the following forms of Pell’s Equation:
        
        x² − 2y² = +1
        x² − 2y² = −1
        
        and look for solutions where x is an odd prime and y is an odd prime multiplied by a power of 2.
        
        I have the following code (in a file called pells.py) that uses SymPy to solve Pell’s equations:
        
        try: # newer versions of SymPy from sympy.solvers.diophantine.diophantine import diop_DN except ImportError: # older versions of SymPy from sympy.solvers.diophantine import diop_DN # interleave a sequence of iterators def interleave(ss): while ss: xs = list() for (i, s) in enumerate(ss): try: yield next(s) except StopIteration: xs.insert(0, i) for i in xs: del ss[i] # initial values from a sequence of iterators def initial(ss): for s in ss: try: yield next(s) except StopIteration: pass def solutions(D, N, x, y): # initial solution yield (D, N, x, y) # to go further we need the fundamental solution to (D, 1) if N == 1: (u, v) = (x, y) else: [s] = diop_DN(D, 1) (u, v) = map(int, s) while True: t = (x, y) (x, y) = (u * x + D * v * y, v * x + u * y) if (x, y) == t: break assert x * x - D * y * y == N yield (D, N, x, y) # generate solutions to Pell's equations # # x^2 - D.y^2 = N # # each equation may have multiple infinite families of solutions # # return values are (D, N, x, y), satisfying the above equation # # fn=interleave will generate solutions from each family interleaved # # fn=initial will generate just the first solution from each family # # Python 3 style definition: def pells(*DNs, fn=interleave): def pells(*DNs, **kw): fn = kw.get('fn', interleave) ss = list() for (D, N) in DNs: # consider fundamental solutions for s in diop_DN(D, N): (x, y) = map(int, s) ss.append(solutions(D, N, x, y)) return fn(ss)
        
        Which I then use in the following program:
        
        Run: [ @replit ]
        
        from pells import pells from enigma import (irange, is_prime_mr, drop_factors, first, printf) is_prime = lambda n: is_prime_mr(n, r=10) # look for possible solutions (from the first 60) for (D, N, x, y) in first(pells((2, 1), (2, -1)), 60): # extract p, q p = x if not (p > 2 and is_prime(p)): continue (k, q) = drop_factors(y, 2) if not (q > 2 and is_prime(q)): continue # output solution (a, b) = (x * x, 2 * y * y) printf("{a} - {b} = {N} [p={p} q={q}]")
        
        I used the program to check up to 6,000 solutions to the Pell’s equations (by which time the numbers under consideration are huge), and found the following pairs:
        
        [p² − (2^k)q² = +1]
        
        289 − 288 = 1
        [n=1; p=17 q=3]
        
        [p² − (2^k)q² = −1]
        
        49 − 50 = −1
        [n=1; p=7 q=5]
        
        1681 − 1682 = −1
        [n=2; p=41 q=29]
        
        3971273138702695316401 − 3971273138702695316402 = −1
        [n=14; p=63018038201 q=44560482149]
        
        367680737852094722224630791187352516632102801 − 367680737852094722224630791187352516632102802 = −1
        [n=29; p=19175002942688032928599 q=13558774610046711780701]
        
        LikeLike
        
        Frits 8:51 am on 7 August 2020 Permalink | Reply
        
        @Jim,
        
        On PuzzlingInPython [{broken link removed}] the Pell equation has been reduced to:
        
        (x_{k+1}, y_{k+1}) = (3x_k+4y_k,2x_k+3y_k)
        
        In an overnight run with this formula I checked up to 7000 solutions (only using one core) finding no more than you did.
        
        LikeLike
- Frits 8:10 pm on 3 August 2020 Permalink | Reply
  Where did you find formula n = (2^k)(p^2) ?
  I only found a reference at OEIS A072502 ?
```
from enigma import irange, printf, tau

# The requested numbers appear in OEIS as A072502
# Gary Detlefs suggested the tau equation
S = lambda n: tau(2*n) == (tau(n) + 3)
 
for a in irange(100, 998):
  b = a + 1
  if S(a) and S(b) :
    printf("{a}, {b}")
 
```
  LikeLike
  - Jim Randell 9:58 am on 4 August 2020 Permalink | Reply
    
    @Frits:
    
    If a number is a power of 2 (= 2^n) then it will have only 1 odd divisor: 1.
    
    If a number has exactly 1 odd prime factor (= (2^n)p), then it will have exactly 2 odd divisors: 1, p.
    
    If a number has exactly 2 different odd prime factors (= (2^n)(p.q)), then it will have exactly 4 odd divisors: 1, p, q, p.q.
    
    But if the 2 odd prime factors are the same (so the number is (2^n)(p^2)), then it will have exactly 3 odd divisors: 1, p, p².
    
    LikeLike
- Jim Randell 7:39 am on 14 June 2025 Permalink | Reply
  I’ve written some code for solving the following general quadratic diophantine equation in 2 variables, without using SymPy:
  
  a.X^2 + b.Y^2 = c
  
  The code is available from the enigma_plus repository as pells.py.
  
  The program given above can then be revised to use the new solver:
```
from enigma import (is_prime_mr, drop_factors, merge, ifirst, printf)
import pells

is_prime = lambda n: is_prime_mr(n, r=10)

# look for possible solutions (from the first 60 candidates)
sols = (pells.diop_quad(1, -2, N) for N in [+1, -1])
for (x, y) in ifirst(merge(sols, uniq=1), 60):
  # extract p, q
  p = x
  if not (p > 2 and is_prime(p)): continue
  (k, q) = drop_factors(y, 2)
  if not (q > 2 and is_prime(q)): continue
  # output solution
  (a, b) = (x * x, 2 * y * y)
  printf("{a} - {b} = {N} [p={p} q={q}]", N=a - b)
```
  LikeLike
Jim Randell 5:37 pm on 31 January 2020 Permalink | Reply
Tags: by: Peter Good ( 27 )
Teaser 2993: Baker’s weights
From The Sunday Times, 2nd February 2020 [link] [link]

A baker’s apprentice was given a 1kg bag of flour, scales and weights, each engraved with a different whole number of grams. He was told to separately weigh out portions of flour weighing 1g, 2g, 3g, and so on up to a certain weight, by combining weights on one side of the scales. He realised that he couldn’t do this if there were fewer weights, and the largest weight was the maximum possible for this number of weights, so he was surprised to find after one of these weighings that the whole bag had been weighed out. Upon investigation, he discovered that some of the weights weighed 1g more than their engraved weight. If I told you how many of the weights were too heavy, you would be able to work out what they all were.

What were the actual weights (in ascending order)?

[teaser2993]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell and Robert Brown are discussing. Toggle Comments
- Jim Randell 8:24 am on 1 February 2020 Permalink | Reply
  When I first read the puzzle it didn’t seem to make any sense, or have a solution.
  
  So I set about investigating the parts of the text that are unambiguous:
  
  (a) The apprentice has a set of weights, some of which are mislabelled (weighing 1g more than labelled).
  
  (b) The apprentice is weighing amounts of 1g, 2g, 3g, … until at some point he unexpectedly has used up exactly 1000g of flour.
  
  With k weights we can make (2^k − 1) different non-empty collections of weights. Using weights that are powers of 2 (i.e. 1g, 2g, 4g, 8g, …) allows us to weigh all the amounts between 1 and (2^k − 1).
  
  So we can start weighing out increasing amounts, look at what weights have been used and look at when a collection of mislabelled weights would bring the total amount weighed out to exactly 1000g.
  
  This Python program runs in 77ms.
  
  Run: [ @replit ]
```
from enigma import (multiset, irange, inf, subsets, nsplit, seq_ordered as ordered, filter_unique, item, printf)

# record possible solutions:
# (<number of weighings>, <number of mislabelled weights>, <sequence of weights>)
ss = list()

# record the labels of the weights used
s = multiset()

# consider possible number of weighings, and total expected amount weighed out
t = 0
for n in irange(1, inf):
  t += n
  if t > 1000: break
  # calculate the required weights
  ws = list(2**i for (i, m) in enumerate(reversed(nsplit(n, base=2))) if m)
  printf("{n} -> {t}; {ws}")

  # add in the weights
  s.update_from_seq(ws)
  assert t == sum(k * v for (k, v) in s.items())

  # now consider a subset of the weights that actually weigh 1g more than labelled
  for xs in subsets(s.keys(), min_size=1):
    # the total extra weight being...
    x = sum(s[x] for x in xs)
    # does this bring the total to exactly 1kg?
    if t + x == 1000:
      k = len(xs)
      printf(" -> {xs}; +{x}; {k}")
      ss.append((n, k, ordered(w + (w in xs) for w in s.keys())))

# find solutions unique by the number of mislabelled weights (= item 1)
for (n, k, ws) in filter_unique(ss, item(1)).unique:
  # output solutions
  printf("n={n} k={k} ws={ws}")
```
  Solution: The actual weights were: 2g, 3g, 5g, 9g, 17g, 32g.
  
  So the apprentice has a set of six weights, labelled: 1g, 2g, 4g, 8g, 16g, 32g. Which, if correct, could be used to weigh any integer amount between 1g and 63g.
  
  However, five of the weights are mislabelled. The 1g, 2g, 4g, 8g, 16g weights all weigh 1g more than their label suggests.
  
  After the apprentice has weighed out amounts corresponding to 1g, 2g, 3g, …, 42g using the weights he would expect to have used 903g of flour, but with this set of weights he has actually used a total of 1000g of flour.
  
  The apprentice may have set out to make weights up to 42g (expecting to use 903g of flour), up to 43g (expecting to use 946g of flour), or up to 44g (expecting to use 990g of flour). For higher amounts 1000g of flour would not be enough to complete the task.
  
  There are also potential solutions when apprentice gets to 43g. With the set of six weights he would expect to have weighed out 946g of flour. But there are four combinations of 3 mislabelled weights, which would bring the total to exactly 1000g. (If the (1, 4, 32), (1, 8, 32), (2, 4, 32) or (2, 8, 32) weights are mislabelled).
  
  But we are told that if we knew the number of mislabelled weights we could work out the actual weights in the set. So we must be dealing with the case where 5 of the weights are mislabelled.
  
  The most reasonable scenario seems to be that apprentice was given a 1kg bag of flour and a set of 6 weights, labelled: 1g, 2g, 4g, 8g, 16g, 32g, and asked to weigh out amounts from 1g to 44g.
  
  The total amount to be weighed out is T(44) = 990g, so he would be expecting to have 10g of flour left at the end.
  
  However, after one of the weighings he has used up exactly 1000g of flour (assuming the bag of flour was actually 1000g in the first place).
  
  There 5 ways this can happen:
  
  After weighing 42g using weights (2, 3, 5, 9, 17, 32) [5 mislabelled weights]
  After weighing 43g using weights (2, 2, 5, 8, 16, 33) [3 mislabelled weights]
  After weighing 43g using weights (2, 2, 4, 9, 16, 33) [3 mislabelled weights]
  After weighing 43g using weights (1, 3, 5, 8, 16, 33) [3 mislabelled weights]
  After weighing 43g using weights (1, 3, 4, 9, 16, 33) [3 mislabelled weights]
  
  We are told that if we knew the number of mislabelled weights we could work out which they were, so we must be dealing with the first situation with 5 mislabelled weights.
  
  LikeLike
- Robert Brown 8:45 pm on 1 February 2020 Permalink | Reply
  
  He’s told to weigh portions up to a certain weight, must be <=44 as that uses 990g of flour. Binary set of weights goes up to 63g, so some of the weights could be smaller. Text says 'the largest weight was max possible for this number of weights' – I took this to mean there's a weight engraved 32g, but others seem to think it means the largest portion was the max possible for this number of weights. We all get the same answer, but using my method I didn't need to be told how many of the weights were too heavy. Does your program incorporate this?
  
  LikeLike
  - Jim Randell 8:59 pm on 1 February 2020 Permalink | Reply
    
    @Robert: I originally thought “the largest weight was the maximum possible for this number of weights” would refer to the largest portion that the apprentice was to weigh out. So it would have to be 31g (with 5 weights) or 63g (with 6 weights), but neither of these can give a solution.
    
    In the end I assumed that the set of weights used was labelled as powers of 2 (i.e. 1g, 2g, 4g, 8g, …), and then used the program to look for amounts where we would expect (if the weights were correctly labelled) to have weighed out a cumulative amount less than 1000g, but if some of the weights were 1g heavier than labelled the cumulative amount is actually exactly 1000g.
    
    I found one set with 5 mislabelled weights where this happens, and four sets with 3 mislabelled weights.
    
    The puzzle text says if we knew the number of mislabelled weights we would know what the actual set of weights was, so the answer we want is the the set with 5 mislabelled weights.
    
    I think the wording of the puzzle could have been clearer.
    
    LikeLike
- Robert Brown 3:49 pm on 3 February 2020 Permalink | Reply
  
  Jim: I agree with everything that you say, but Brian Gladman seems to think “the largest weight etc” refers to the “certain weight” that the apprentice was told to use as a limit. He then thinks it’s reasonable to set this to 63g. But the person giving instructions to the apprentice would know this was impossible, as even with correct weight labels, the flour would run out after he weighed 44 portions. Of course we don’t know if that person was aware that some of the weights were wrong, which muddies the waters a bit. But Brian’s telling me that I’m effectively solving a different problem, but as far as I can see, it’s the same problem that you have solved.
  In fact, the four sets with 3 mislabelled weights occur at weighing 43, while the the set with 5 mislabelled weights occur at weighing 42. So I discounted weighing 43, which means that I didn’t need to be told the number of mislabelled weights.
  
  Because the weights we used can give up to 63g, I looked to see what alternatives could give every 1g step up to 44, and found 323 ways to do this, (if the 32g weight is omitted). Beyond my abilities to analyse all of these to see if there’s an alternative solution!
  
  LikeLike
  - Jim Randell 9:46 am on 4 February 2020 Permalink | Reply
    
    I think that “the largest weight was the maximum possible for this number of weights” is a roundabout way of saying that that the weights are powers of 2. In a set of 6 (correctly labelled) weights this would mean that the largest weight was 32g, so the remaining 5 weights have to be able to weigh 1g-31g, which means they also have to be powers of 2.
    
    Using a set of weights that is powers of 2, means that there is only one combination of weights that makes up any specific amount, so when looking for how many times each weight is used in the weighings there is a single answer. Otherwise we may have to consider multiple different ways to make up a specific amount, which could give us different actual weights. So I think this would be a much harder problem (and maybe not have a unique solution).
    
    If we take “the largest weight was the maximum possible for this number of weights” to mean that the largest amount the apprentice was asked to weigh out was the largest possible for the number of weights, then if the set has 6 weights he would have been asked to weight out amounts up to 63g. This also implies that the set of weights is a “powers of 2” set. But also means that the apprentice was being set an impossible task. (Although there is a long tradition of sending apprentices on futile or impossible tasks, and as it turns out he has been given a doctored set of weights, so his task does indeed turn out to be impossible).
    
    I think the most reasonable interpretation is that the apprentice was given a set of 6 weights, labelled 1g, 2g, 4g, 8g, 16g, 32g and asked to weigh out amounts up to 42g, 43g or 44g (but we don’t know which). Each of these would appear to be an achievable task.
    
    As the apprentice weighs out the amounts he finds that the entire bag has been used up after one of the weighings. This is possible in one way after weighing out the 42g portion, and 4 ways after weighing out the 43g portion. We are told that if we knew the number of mislabelled weights, then we could work out which ones they were, so I think we need to take all these cases into account.
    
    So I think the most reasonable scenario was that the apprentice was asked to weigh out amounts up to 44g, a task which initially looks possible, but depending on the actual set of weights means you would run out of flour after weighing the 42g or 43g portion, making it impossible to complete the task.
    
    Of the 5 possible sets of weights that lead to exactly 1000g of flour being used before we get to the 44g weight, one of them involves 5 weights being doctored and four of them involved 3 of the weights being doctored. So the answer we want is the set with 5 weights.
    
    LikeLike

Jim Randell 5:40 pm on 24 January 2020 Permalink | Reply
Tags: by: Stephen Hogg ( 62 )

Teaser 2992: Crystal cleavage calamity!

From The Sunday Times, 26th January 2020 [link] [link]

My “mystic” crystal stood on its triangular end face, with every side of the triangle being less than 10cm. It had three vertical sides and an identical triangular top end face, with the height being under 50cm. Unfortunately, during dusting, it fell and broke in two. The break was a perfect cleavage along an oblique plane that didn’t encroach on the end faces, so I then had two, pointed, pentahedral crystals.

Later, I found that the nine edge lengths, in cm, of one of these were all different whole numbers — the majority prime — and their total was also a prime number. Curiously, the total of the nine, whole-number, edge lengths, in cm, of the other piece was also a prime number.

What was the total for this latter piece?

[teaser2992]

Jim Randell 9:44 am on 25 January 2020 Permalink | Reply
Here’s my first stab at a program. It’s a bit simplistic and slow, but it finds the required solution.

Run: [ @replit ]
```
from enigma import (subsets, irange, diff, ihypot, is_prime, printf)

# choose lengths for the base (a, b, c)
for (a, b, c) in subsets(irange(1, 9), size=3):

  if not (a + b > c and a + c > b and b + c > a): continue

  # choose lengths for the the verticals
  for (x, y, z) in subsets(diff(irange(1, 48), (a, b, c)), size=3, select="P"):

    # calculate the cut lengths
    d = ihypot(a, x - z)
    e = ihypot(b, x - y)
    f = ihypot(c, y - z)
    if d is None or e is None or f is None: continue

    # edge lengths are all different, and the majority prime
    edges = (a, b, c, x, y, z, d, e, f)
    if not len(set(edges)) == 9: continue
    if not sum(is_prime(x) for x in edges) > 4: continue
    # and the total is prime
    t1 = sum(edges)
    if not is_prime(t1): continue

    # consider possible total height
    for h in irange(max(x, y, z) + 1, 49):
      # and the total of the edge lengths of the other piece
      t2 = a + b + c + (h - x) + (h - y) + (h - z) + d + e + f
      if not is_prime(t2): continue

      printf("a={a} b={b} c={c}; x={x} y={y} z={z}; d={d} e={e} f={f}; t1={t1}; h={h} t2={t2}")
```
Solution: The total is 113 cm.

The crystal is a triangular prism. The base of which forms a triangle with sides of 5cm, 7cm, 9cm.

There are two possible sizes for the original crystal – either 44 cm tall or 48 cm tall.

Each of these two sizes can break in two different ways, but in each scenario the sum of the edges of the “other” piece is always 113 cm.

If we think about the triangular prism as a cardboard tube then we can “unroll” it to get the following flat diagram:

The base of the prism consists of a triangle of sides a, b, c, and the overall height of the prism is h.

The fracture is formed by the red line, and the lengths of the fracture line across the vertical faces are d, e, f.

Note that d, e, f are the hypotenuses of right-angled triangles with bases of a, b, c respectively.

And in order for the fracture to line up the lengths of two of the vertical sides of these triangles must sum to the length of the third.

Subject to the fact all the distances are integers such that: a, b, c < 10; h < 50, we can find candidate solutions for a, b, c; d, e, f; x, y, z, such that each takes on a different value, the majority of them are prime, and their total sum is prime.

We can then consider possible values for h that make the edges of the top piece a, b, c; d, e, f; h − x, h − y, h − z also sum to a prime number.

We find there is only one possible shape for the base of the prism (a (5, 7, 9) triangle), and for the corresponding lengths of the fracture lines (13, 25, 15).

There are two possible values for overall height of the prism (44 or 48), and in each case there are two possible sets of x, y, z values, giving us 4 possible solutions.

a=5, b=7, c=9; d=13, e=25, f=15; x=31, y=43, z=19; t1=167; h=44, t2=113
a=5, b=7, c=9; d=13, e=25, f=15; x=31, y=19, z=43; t1=167; h=44, t2=113
a=5, b=7, c=9; d=13, e=25, f=15; x=35, y=47, z=23; t1=179; h=48, t2=113
a=5, b=7, c=9; d=13, e=25, f=15; x=35, y=23, z=47; t1=179; h=48, t2=113

However in each one the sum of the lengths of the edges of the top piece is 113 (the lengths of the edges for the top piece are always: 5, 7, 9; 13, 25, 15; 13, 1, 25).

Here are the diagrams corresponding to the four possible solutions:

LikeLike
- Jim Randell 4:09 pm on 25 January 2020 Permalink | Reply
  Here’s a faster program. It constructs the possible lengths of the fractures (which are the hypotenuses of right-angled triangles) up front, and then uses these to construct possible prism shapes.
  
  It runs in a much more respectable 180ms.
  
  Run: [ @replit ]
```
from enigma import (irange, ihypot, subsets, is_prime, printf)

# form right angled triangles with side p, find q and hypotenuse h
tris = list()
for p in irange(1, 11):
  for q in irange(1, 49):
    h = ihypot(p, q)
    if h is None: continue
    tris.append((p, q, h))

# now consider 3 different p values for the base of the prism
for ((a, q1, d), (b, q2, e), (c, q3, f)) in subsets(tris, size=3):

  # check a, b, c form a triangular base of the prism
  if not (a + b > c and a + c > b and b + c > a): continue

  # choose a slice
  for (m1, m2, m3) in subsets((+1, -1), size=3, select="M"):

    # choose a start point for the fracture
    for x in irange(1, 49):
      y = x + m1 * q1
      z = y + m2 * q2
      if not (0 < y < 50 and 0 < z < 50 and z + m3 * q3 == x): continue

      # edge lengths for the broken piece are all different, and the majority prime
      edges = (a, b, c, x, y, z, d, e, f)
      if not len(set(edges)) == 9: continue
      if not sum(is_prime(x) for x in edges) > 4: continue
      # and the total is prime
      t1 = sum(edges)
      if not is_prime(t1): continue

      # consider possible total height
      for h in irange(max(x, y, z) + 1, 49):
        # calculate the total of the edge lengths of the other piece
        t2 = a + b + c + (h - x) + (h - y) + (h - z) + d + e + f
        if not is_prime(t2): continue

        printf("a={a} b={b} c={c}; d={d} e={e} f={f}; x={x} y={y} z={z}; t1={t1}; h={h} t2={t2}")
```
  LikeLike
  - Frits 4:21 pm on 15 August 2025 Permalink | Reply
    
    Adding the two prime total formulas together leads to 3*h being even or that h must be even.
    
    LikeLike

GeoffR 9:03 am on 30 January 2020 Permalink | Reply

I also found two possible solutions, with the same edge total of the second piece.

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

predicate is_prime(var int: x) = 
x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x)))))
((i < x) -> (x mod i > 0));

% the base triangle edges
var 1..9:a; var 1..9:b; var 1..9:c;

% d is above a, e above b, and f above c
% the cleavage plane triangle edges
var 1..49:d; var 1..49:e; var 1..49:f; 

% the vertical edges of the first lower piece
var 1..49:x; var 1..49:y; var 1..49:z; 

% triangle constraints  
constraint a < b /\ a + b > c /\ b + c > a /\ c + a > b;

% order the vertical edges
constraint x < y /\ y < z;

% all edges different
constraint all_different([a, b, c, d, e, f, x, y, z]);

% height of unbroken crystal
var 1..49: ht;

% edge length sum of base and cleavage triangles
var 10..200: bc_sum = a + b + c + d + e + f;

% the vertical edge sum
var 10..200: v_sum = x + y + z;

% edge length sum of first lower piece
var 20..300: edge_sum1 = bc_sum + v_sum;

% edge length sum of second upper piece
var 20..300: edge_sum2 = bc_sum + 3 * ht - v_sum;

% pythagorean constraints on three prism faces
constraint d * d == a * a + (y - x) * (y - x);
constraint e * e == b * b + (z - x) * (z - x);
constraint f * f == c * c + (z - y) * (z - y);

% more than half  the lower prism edges are prime
constraint ( bool2int(is_prime(a)) + bool2int(is_prime(b))
 + bool2int(is_prime(c)) + bool2int(is_prime(d)) 
 + bool2int(is_prime(e)) + bool2int(is_prime(f)) 
 + bool2int(is_prime(x)) + bool2int(is_prime(y)) 
 + bool2int(is_prime(z)) ) > 4;

constraint is_prime(edge_sum1) /\ is_prime(edge_sum2);   

constraint ht > z;

solve satisfy;

output ["Base triangle sides are: " 
++ show(a) ++ ", " ++ show(b) ++ ", " ++ show(c)]

++ ["\nHeights to fracture plane: " ++
show(x) ++ ", " ++ show(y) ++ ", " ++ show(z)]

++ ["\nSides of fracture plane: "
++ show(d) ++ ", " ++ show(e) ++ ", " ++ show(f)]

++["\nEdge total length of 2nd piece: " ++ show(edge_sum2)];

% Base triangle sides are: 5, 7, 9
% Heights to fracture plane: 23, 35, 47
% Sides of fracture plane: 13, 25, 15
% Edge total length of 2nd piece: 113
% % time elapsed: 0.02 s
% ----------
% Base triangle sides are: 5, 7, 9
% Heights to fracture plane: 19, 31, 43
% Sides of fracture plane: 13, 25, 15
% Edge total length of 2nd piece: 113
% % time elapsed: 0.58 s
% ----------
% ==========

LikeLike

Jim Randell 9:42 am on 22 January 2020 Permalink | Reply
Tags: by: Danny Roth ( 84 )

Teaser 2991: Super Street

From The Sunday Times, 19th January 2020 [link] [link]

George and Martha and their five daughters with their families have moved into six houses in Super Street. I define a “super prime number” as a prime number which has at least two digits adding up to a prime number (e.g. 11 and 23). Similarly for “super squares” (e.g. 36) and “super cubes”. Houses in Super Street are numbered with the lowest 31 super numbers of the above types.

The elderly couple live in the highest-numbered house on the street. They noticed that the last digits of their daughters’ houses were five consecutive digits and the sum of their five house numbers was a perfect square. Furthermore, the ordinal positions (lowest-numbered house is 1 and so on) of all but one of the houses were prime.

Which five houses did the daughters occupy?

[teaser2991]

Jim Randell 9:43 am on 22 January 2020 Permalink | Reply
I took the definition of a “super-p” number n to be as follows:

n has property p;
The digit sum of n also has property p;
n has more than 1 digit.

This seems to be the required interpretation (a possible alternative interpretation gives no solutions).

This Python program runs in 140ms.

Run: [ @replit ]
```
from heapq import merge
from enigma import (nsplit, primes, irange, inf, is_square, is_cube, first, uniq, subsets, tuples, printf)

# generate "super" numbers from iterator <s> must have at least 2
# digits, and the digit sum must satisfy <f>
def sup(s, f):
  for n in s:
    if n < 10: continue
    if f(sum(nsplit(n))):
      yield n

# "super" primes, squares, cubes
sp = sup(primes, primes.is_prime)
ss = sup((x**2 for x in irange(1, inf)), is_square)
sc = sup((x**3 for x in irange(1, inf)), is_cube)

# select the first 31 "super" numbers
ns = first(uniq(merge(sp, ss, sc)), 31)
printf("[ns={ns}]")

# G+M live in the highest numbered house
GM = ns.pop(-1)
printf("GM = {GM}")

# map the remaining numbers to ordinal values (starting at 1)
m = dict((n, i) for (i, n) in enumerate(ns, start=1))

# check a sequence is consecutive
is_consecutive = lambda s: all(a + 1 == b for (a, b) in tuples(s, 2))

# consider numbers of the five daughters
for ds in subsets(ns, size=5):
  # sum of the numbers is a square
  if not is_square(sum(ds)): continue
  # the units digits form a consecutive sequence
  if not is_consecutive(sorted(d % 10 for d in ds)): continue
  # exactly 4 of their ordinals are prime
  if not (sum(primes.is_prime(m[d]) for d in ds) == 4): continue
  # output solution
  printf("ds = {ds}")
```
Solution: The house numbers of the daughters are: 23, 125, 137, 144, 196.

George and Martha live at house number 199 (super-prime).

The daughters live at the following house numbers:

23 (super-prime, 2nd house)
125 (super-cube, 17th house)
137 (super-prime, 19th house)
144 (super-square, 21st house)
196 (super-square, 29th house)

The sum of the house numbers is 625 (= 25²).

And the units digits form the sequence: (3, 4, 5, 6, 7).

The ordinal of house number 144 is not prime, but the rest are.

If we allow single digit “super” numbers, then we get the following solution:

George and Martha live at house number 157 (super-prime).

The daughters live at the following house numbers:

2 (super-prime, 2nd house)
41 (super-prime, 13th house)
100 (super-square, 21st house)
113 (super-prime, 23rd house)
144 (super-square, 29th house)

The sum of the house numbers is 400 (= 20²).

And the units digits form the sequence: (0, 1, 2, 3, 4).

The ordinal of house number 100 is not prime, but the rest are.

LikeLike

Frits 10:59 pm on 22 December 2020 Permalink | Reply

Preprocessing was necessary to get run time under a second. While doing that I also could have stored the generated super numbers.

from enigma import SubstitutedExpression, is_prime, is_square, is_cube

def is_super(n):
  A = n // 100
  B = (n % 100) // 10
  C = n % 10
  return (is_square(n) != None and is_square(A+B+C) != None) or \
         (is_cube(n) != None and is_cube(A+B+C) != None) or \
         (is_prime(n) and is_prime(A+B+C))

# calculate ordinal number (inefficient but infrequently called)         
ord = lambda n: sum(is_super(i) for i in range(11, n)) + 1

(t, min_d2i, sup31) = (0, 0, 0)
# find 31st super number 
for i in range(11, 220):
  if is_super(i): t += 1
  if t == 31:
    min_d2i = (i // 100) + 1
    sup31 = i
    break


# the alphametic puzzle
p = SubstitutedExpression(
  [
  # 5 daughters live at super numbers
  "is_super(ABC)",
  "ABC > 9",
  "is_super(DEF)",
  "DEF > 9",
  "is_super(GHI)",
  "GHI > 9",
  "is_super(JKL)",
  "JKL > 9",
  "is_super(MNO)",
  "MNO > 9",
  
  "ABC < DEF",
  "DEF < GHI",
  "GHI < JKL",
  "JKL < MNO",
  
  # the last digits of their daughters' houses were five consecutive digits
  "max([C, F, I, L, O]) - min([C, F, I, L, O]) == 4",
  
  # all different numbers
  "len([ABC, DEF, GHI, JKL, MNO]) == len(set([ABC, DEF, GHI, JKL, MNO]))",
  
  # the sum of their five house numbers was a perfect square
  "is_square(sum([ABC, DEF, GHI, JKL, MNO]))",
    
  # houses in Super Street are numbered with the lowest 31 super numbers.
  # the elderly couple live in the highest-numbered house on the street. 
  "max([ABC, DEF, GHI, JKL, MNO]) < " + str(sup31),
 
  # the ordinal positions (lowest-numbered house is 1 and so on) 
  # of all but one of the houses were prime.
  "sum([is_prime(ord(ABC)), is_prime(ord(DEF)), is_prime(ord(GHI)), \
is_prime(ord(JKL)), is_prime(ord(MNO))]) == 4",
  
  ],
  answer="ABC, DEF, GHI, JKL, MNO",
  d2i=dict([(k, "ADGJM") for k in range(min_d2i, 10)]),
  env=dict(is_super=is_super, ord=ord),
  # last digits of their daughters' houses are different
  distinct="CFILO",
  verbose=0)   

# print answers 
for (_, ans) in p.solve():
  print(f"{ans}")

LikeLike

Jim Randell 5:07 pm on 10 January 2020 Permalink | Reply
Tags: by: Howard Williams ( 43 )
Teaser 2990: Squares and cubes
From The Sunday Times, 12th January 2020 [link] [link]

Jenny is pleased that she has found two whole numbers with a remarkable property. One of them is a single digit greater than zero while the other one has two digits. The remarkable thing is that the difference of their squares is a perfect cube and the difference of their cubes is a perfect square.

Her sister Sarah is not impressed, however. She has found two three-digit numbers for which the difference of their squares is also a perfect cube and the difference of their cubes is also a perfect square.

In ascending order, what are the four numbers?

[teaser2990]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
GeoffR, Jim Randell, and Frits are discussing. Toggle Comments
- Jim Randell 5:24 pm on 10 January 2020 Permalink | Reply
  We can use the [[ SubstitutedExpression() ]] solver from the enigma.py library to solve this puzzle.
  
  The following Python program runs in 179ms.
  
  Run: [ @replit ]
```
from enigma import (SubstitutedExpression, sprintf as f, cproduct)

# solve for alphametic n1, n2 (where n1 < n2)
def solve(label, n1, n2, **kw):
  p = SubstitutedExpression(
    [ f("is_cube(sq({n2}) - sq({n1}))"), f("is_square(cb({n2}) - cb({n1}))") ],
    distinct="",
    answer=f("({n1}, {n2})"),
    **kw
  )
  ss = list()
  for ans in p.answers(verbose=0):
    print(f("{label}: {ans}"))
    ss.append(ans)
  return ss

# find the answers for each girl
jss = solve("Jenny", "A", "BC", d2i={ 0: "AB" })
sss = solve("Sarah", "ABC", "DEF")

# output solutions
for (js, ss) in cproduct([jss, sss]):
  print(f("numbers = {ns}", ns=js + ss))
```
  Solution: The four numbers are: 6, 10, 384, 640.
  
  Jenny’s numbers are 6 and 10:
  
  10² − 6² = 64 = 4³
  10³ − 6³ = 784 = 28²
  
  Sarah’s numbers are 384 and 640:
  
  640² − 384² = 262144 = 64³
  640³ − 384³ = 205520896 = 14336²
  
  They are related in that Sarah’s numbers are 64 (=2^6) times Jenny’s.
  
  For any (n, m) solution, then (k.n, k.m) is also a solution, where k = z^6.
  
  m^2 − n^2 = x^3
  m^3 − n^3 = y^2
  (k.m)^2 − (k.n)^2 = (k^2)(m^2) − (k^2)(n^2) = (k^2)(m^2 − n^2) = (k^2)(x^3) = ((z^4)x)^3
  (k.m)^3 − (k.n)^3 = (k^3)(m^3) − (k^3)(n^3) = (k^3)(m^3 − n^3) = (k^3)(y^2) = ((z^9)y)^2
  
  This method accounts for the first three solutions (by increasing x):
  
  (6, 10)
  (384, 640) = (6, 10) × 2^6
  (4374, 7290) = (6, 10) × 3^6
  
  but not all solutions are multiples of (6, 10) – the next few are:
  
  (5687, 8954)
  (64350, 70434)
  (24576, 40960) = (6, 10) × 4^6
  (27783, 55566)
  (17576, 52728)
  (93750, 156250) = (6, 10) × 5^6
  (354375, 405000)
  (279936, 466560) = (6, 10) × 6^6
  …
  
  LikeLike
- Jim Randell 10:20 pm on 11 January 2020 Permalink | Reply
  The following Python program generates (n, m) and (x, y) pairs where:
  
  n < m
  m² − n² = x³
  m³ − n³ = y²
  
  It runs in 104ms to solve this puzzle, but the [[ generate() ]] function can be used to generate larger numbers with the required property.
  
  Run: [ @replit ]
```
from enigma import (irange, inf, divisors_pairs, div, is_square, cproduct, printf)

# generate (n, m, x, y) where m^2 - n^2 = x^3, m^3 - n^3 = y^2
def generate(start=1):
  for x in irange(start, inf):
    cube = x**3
    for (a, b) in divisors_pairs(cube):
      m = div(a + b, 2)
      if m is None: continue
      n = m - a
      if n < 1: continue
      y = is_square(cube * m + a * n * n)
      if y is None: continue
      yield (n, m, x, y)

# find the answers for each girl
(jss, sss) = (list(), list())
for (n, m, x, y) in generate():
  if n < 10 and 9 < m < 100:
    printf("Jenny: ({n}, {m}) -> ({x}, {y})")
    jss.append((n, m))
  if 99 < n and m < 1000:
    printf("Sarah: ({n}, {m}) -> ({x}, {y})")
    sss.append((n, m))
  if n > 999:
    break

# output solutions
for (js, ss) in cproduct([jss, sss]):
  printf("numbers = {ns}", ns=js + ss)
```
  LikeLike
- GeoffR 9:32 am on 12 January 2020 Permalink | Reply
```
% A Solution in MiniZinc
include "globals.mzn";

% Jenny's numbers are A and BC
var 1..9:A; var 10..99:BC;

% Sarah's numbers are DEF and GHI
var 100..999:DEF; var 100..999:GHI;
constraint GHI > DEF;

predicate is_cube(var int: c) =
   let {
      var 0..ceil(pow(int2float(ub(c)),(1/3))): z
   } in z*z*z = c;
   
predicate is_sq(var int: c) =
   let {
      var 0..ceil(pow(int2float(ub(c)),(1/2))): z
   } in z*z = c;
   
% Jenny's numbers   
constraint is_cube(BC * BC - A * A);
constraint is_sq(BC * BC * BC - A * A * A);

% Sarah's numbers
constraint is_cube(GHI * GHI - DEF * DEF);
constraint is_sq(GHI * GHI * GHI - DEF * DEF * DEF);

solve satisfy;

output["Four numbers are " ++ show(A) ++ ", " ++ show(BC) 
++ ", " ++ show(DEF) ++ ", " ++ show(GHI)];
```
  LikeLike
- Frits 7:24 pm on 25 July 2020 Permalink | Reply
```
from enigma import SubstitutedExpression, printf

# the alphametic puzzle
p = SubstitutedExpression([
    "A != 0",
    "is_cube((BC * BC) - (A * A))",
    "is_square(BC * BC * BC - A * A * A)",
    "DEF != GHI",
    "is_cube(GHI * GHI - DEF * DEF)",
    "is_square(GHI * GHI * GHI - DEF * DEF * DEF)",
  ],
  answer="(A, BC, DEF, GHI)",
  distinct="", # allow symbols with same values
)

# print answers
for (_, ans) in p.solve(verbose=0):
  printf("answer = {ans}")
```
  I modified the is_cube() function in my enigma.py version to first eliminate almost 95% of the cases. The above code ran approx 3 time faster.
```
if n % 819 not in {
    0,1,8,27,64,90,91,99,118,125,161,181,190,216,252,260,
    287,307,343,350,351,377,378,441,442,468,469,476,512,
    532,559,567,603,629,638,658,694,701,720,728,729,755,
    792,811,818
  }:
    return False
```
  Hi Jim, is there a place where general questions (like why you sometimes do it the hard way) or technical questions (like if the code can be changed to allow p = SubstitutedExpression( […] ) constructs to use comments)?
  
  LikeLike
  - Jim Randell 11:08 pm on 25 July 2020 Permalink | Reply
    
    @Frits: Thanks for your comment. I’ve cleaned up the formatting a bit.
    
    If there are any specific questions about my code I’m happy to try and answer them for you.
    
    I did write a run file for this puzzle that uses a single [[ SubstitutedExpression() ]] recipe (see: [ @repl.it ]), but I preferred to treat the two parts as separate recipes, which would be better if there were multiple solutions (although there aren’t, but I prefer the general approach).
    
    In the end though I wrote a specialised routine to generate numbers with the described behaviour, that can be used to solve this puzzle, and also find larger numbers with the same property. (I put a list up here [ @repl.it ]).
    
    I special cased the [[ is_square() ]] function to do early rejection as it is used a lot in puzzles, but the [[ is_cube() ]] function is just wrapper around [[ is_power() ]], but I’ll look at adding in some early rejection as you suggest.
    
    I’m not sure what you mean about adding comments into the [[ SubstitutedExpression() ]] solver. If you use it in a regular Python program (as you have) you can just use normal Python comments, and if you encapsulate it in a run-file (as I have above), then you can use “shell like” comments, which are discarded when the file is executed by enigma.py.
    
    LikeLike
- Frits 7:49 pm on 26 July 2020 Permalink | Reply
  
  @Jim: Thanks for the quick response.
  
  I am only a beginning developer in Python.
  
  Is there a reason why in the is_square function you don’t check the “is_square.residues” set with the “not in” operator?
  
  You now generate the list “is_square.reject” from the set “is_square.residues”.
  A direct lookup of a list item is of O(1) complexity but as I have understood the set “not in” also has a complexity O(1) (avg). Do you know if collisions can be expected?
  
  I did some performance testing with “get item” for a list and a “not in” for a set (the mod 819 numbers) and saw no difference.
  
  Do you also consider adding a minimize/maximize function within SubstitutedExpression?
  
  I have seen you using the Accumulator function for this need (but outside SubstitutedExpression).
  
  LikeLike
  - Jim Randell 11:00 pm on 26 July 2020 Permalink | Reply
    
    @Frits: I hope you enjoy using Python. I was new to it myself when I started coding Enigma puzzles on Enigmatic Code. But I find it is usually quite succinct and understandable. The enigma.py library represents my accumulation of useful routines and refinements from the last 10 years of solving this kind of puzzle. I hope you find it useful.
    
    With regards to the code in [[ is_square ]] I was looking at it yesterday and couldn’t see any reason for the reject dictionary, so I’ve changed the code to just using residues directly (and also added similar code to the [[ is_cube ]] function, as you suggested. This is available in the 2020-07-27 version of enigma.py. (It was quite old code, and I didn’t use to use set() as much back then).
    
    I have thought once or twice about adding some collection functionality for answers inside the [[ SubstitutedExpression() ]] solver, but it isn’t used in very many alphametic puzzles, and (as you say) it can be achieved using other functionality already present in enigma.py, so it’s never quite made it to the top of my list of things to do.
    
    LikeLike
  - Jim Randell 10:32 am on 29 July 2020 Permalink | Reply
    
    In enigma.py version 2020-07-29 I’ve added a [[ accumulate ]] parameter to the [[ SubstitutedExpression() ]] solver.
    
    The [[ SubstitutedExpression.run() ]] method (formerly called [[ go() ]]) finds and outputs solutions to the alphametic problem specified, and counts the number of solutions. The number of solutions is returned in the [[ n ]] attribute of the return value.
    
    If the [[ answer ]] parameter has been specified, then the result of the specified expression is collection for each solution, and all answers are returned as a [[ multiset() ]] in the [[ answer ]] attribute of the return value.
    
    If, additionally, the [[ accumulate ]] parameter has been specified, then the result of applying the specified function(s) to the collected answers is returned in the [[ accumulate ]] attribute of the return value.
    
    See my comment on Teaser 2947 for an example of this functionality in use.
    
    (I am also working on allowing the [[ verbose ]] parameter to be specified as a collection of flags, rather than a number, but that’s not ready yet).
    
    LikeLike
- Frits 4:08 pm on 13 August 2020 Permalink | Reply
  Generate solver code:
```
from enigma import is_cube, is_square 
from re import findall

not_cube = lambda l, m: not(is_cube(l*l - m*m))
not_square = lambda l, m: not(is_square(l*l*l - m*m*m))

# "DEF" --> "DEF = D*100+E*10+F"
formula = lambda w: w + " = " + "".join(w[i]+"*"+str(10**(len(w)-i-1))+"+"  
                 for i in range(len(w)-1))+w[-1]

# do all elements in a reside in b?
within = lambda a, b: all(i in b for i in a)

# "1-9" --> "range(1,10)"
def rng(s):      
  a = s.split("-", 1)
  return "range("+a[0]+","+str(int(a[1])+1)+")"
  

exprs = []
# 0: loop letter, 1: range, 2: dismiss condition 
exprs.append(["B",  "1-9", ""])
exprs.append(["C",  "0-9", ""])
exprs.append(["A",  "1-9", "not_square(BC, A) or not_cube(BC, A)"])
exprs.append(["D",  "1-9", ""])
exprs.append(["EF", "0-9", ""])
exprs.append(["G",  "1-9", ""])
exprs.append(["HI", "0-9", "DEF == GHI"])
exprs.append(["", "", "not_square(GHI, DEF) or not_cube(GHI, DEF)"])


# Build list of multi-letter words
words = set()
for expr in exprs:
  if expr[2] != "": 
    for w in findall('[A-Z]{2,}', expr[2]):
       words.add(w)

done = []
ex = ind = letters = ""

# Generate nested code
for j in range(0, len(exprs)):
  expr = exprs[j]
  # add range
  if expr[0] != "":
    if '-' in expr[1]: lrange = rng(expr[1])
    else: lrange = expr[1]
    for let in expr[0]:
      ex += ind + "for " + let + " in " + lrange + ":\n"
      ind += "  "
      letters += let
  
      # expand variable if needed
      if len(letters) > 0: 
        for w in words:
          if not(w in done) and within(w, letters):
            ex += ind + formula(w) + "\n"
            done.append(w)

  # add dismiss condition 
  if expr[2] != "": 
    ex += ind +"if " + expr[2] + ": continue\n"
 
  # last exprs element?
  if len(exprs) - j < 2:
    ex += ind + "print(A,BC,DEF,GHI)\n"
    
#print(ex)

print("A BC DEF GHI")
print("------------")
exec(ex)

# A BC DEF GHI
# ------------
# 6 10 384 640
```
  Generated code:
```
for B in range(1,10):
  for C in range(0,10):
    BC = B*10+C
    for A in range(1,10):
      if not_square(BC, A) or not_cube(BC, A): continue
      for D in range(1,10):
        for E in range(0,10):
          for F in range(0,10):
            DEF = D*100+E*10+F
            for G in range(1,10):
              for H in range(0,10):
                for I in range(0,10):
                  GHI = G*100+H*10+I
                  if DEF == GHI: continue
                  if not_square(GHI, DEF) or not_cube(GHI, DEF): continue
                  print(A,BC,DEF,GHI)
```
  Enigma.py sometimes calculates BC too many times as the first 3 loops of the SubstitutedExpression generated code are over A, B and C instead of B, C and A. Option “reorder=1” doesn’t seem to recognize this. The issue is minor.
  
  Example 1:
```
p = SubstitutedExpression(
  [ "is_cube((A * A) + (BC * BC))" ,
    "is_square(BC * BC * BC - A * A * A)" ,     
    "DEF != GHI" ,
    "is_cube(GHI * GHI - DEF * DEF)" ,
    "is_square(GHI * GHI * GHI - DEF * DEF * DEF)" ,
  ],
  answer="(A,BC,DEF,GHI)",
  d2i={ 0: "ABDG" },
  verbose=256,
  reorder=1,
  distinct="",    # allow symbols with same values
)
```
  loops over A, B and C
  
  Example 2:
```
p = SubstitutedExpression(
  [ "is_cube((BC * BC) - (A * A))" ,
    "is_square(BC * BC * BC - A * A * A)" ,     
    "DEF != GHI" ,
    "is_cube(GHI * GHI - DEF * DEF)" ,
    "is_square(GHI * GHI * GHI - DEF * DEF * DEF)" ,
  ],
  answer="(A,BC,DEF,GHI)",
  d2i={ 0: "ABDG" },
  verbose=256,
  reorder=1,
  distinct="",    # allow symbols with same values
)
```
  loops over B,C and A (as BC is the first variable)
  
  LikeLike
  - Jim Randell 11:45 am on 14 August 2020 Permalink | Reply
    
    @Frits:
    
    The [[ reorder ]] parameter only affects the order that the solver considers the expressions. If it is enabled (the default) it will use a heuristic that chooses the next expression by considering how much work is required to give values to the symbols involved in it. If it is disabled the expressions are just considered in the order they are presented.
    
    The solver does no introspection of the expression, other than to determine what symbols are used in it. So when it sees: [[ "is_cube(YZ**2 - X**2)" ]] it just sees it as an expression involving X, Y, Z, and generates the appropriate code. The actual loops will be generated in an arbitrary order.
    
    The [[ verbose ]] level 128 will output the strategy that the solver is using, showing the order the expressions will be evaluated in, and a [x+y] count where x is the number of symbols to consider, and y is the number of additional symbols that can then be determined.
    
    I do have a TODO note in the code for [[ SubstitutedExpression() ]] to look at ordering the symbols in such a way that alphametic words can be constructed as soon as possible, but I don’t think it will give a significant improvement in run times. However, I might look at it again when I have some time.
    
    LikeLike
- Frits 1:03 pm on 14 August 2020 Permalink | Reply
  @ Jim,
  
  Thanks. It might be worthwile to look at list comprehensions for generated code in SubstitutedExpression.
  
  I got a performance improvement when I replaced code like:
```
for S in range(1,10):
          if S in {G,D,L,A}: continue
```
  with
```
notIn = lambda w: [x for x in range(1,10) if x not in w]

and

for S in notIn({D,G,L,A}):
```
  LikeLike
  - Jim Randell 10:44 pm on 15 August 2020 Permalink | Reply
    
    @Frits: Thanks for the suggestion. I’ve done some testing and unfortunately generating code as you suggest doesn’t give a speed improvement for me (compared to the current approach). Performance figures are of course very dependent on the precise nature of the system that you are running the tests on.
    
    LikeLike
- GeoffR 10:00 am on 7 December 2024 Permalink | Reply
```
def is_sq(n):
  if round(n ** 0.5) ** 2 == n:
    return True
  return False

def is_cube(n):
  if round(n ** (1/3)) ** 3 == n:
    return True
  return False

# Jenny's single and 2-digit numbers
for a in range(1, 10):
    for b in range(10, 100):
        c1 = b**2 - a**2
        if not is_cube(c1):continue
        sq1 = b**3 - a**3
        if not is_sq(sq1):continue
        
        # Sarah's two 3-digit numbers
        for n1 in range(100, 999):
            for n2 in range(n1 + 1, 999):
                if not is_cube(n2**2 - n1**2):continue
                if not is_sq(n2**3 - n1**3):continue
                print(f"The four numbers are {a}, {b}, {n1} and {n2}.")

# The four numbers are 6, 10, 384 and 640.
                
```
  LikeLike
Jim Randell 8:55 am on 4 January 2020 Permalink | Reply
Tags: by: Andrew Skidmore ( 85 )
Teaser 2989: Pot luck
From The Sunday Times, 5th January 2020 [link] [link]

Liam had a bag of snooker balls containing 6 colours (not red) and up to 15 red balls. He drew out balls at random, the first being a red. Without replacing this he drew another ball; it was a colour. He replaced this and drew another ball. This was a red (not replaced), and he was able to follow this by drawing another colour. The probability of achieving a red/colour/red/colour sequence was one in a certain whole number.

After replacing all the balls, Liam was able to “pot” all the balls. This involved “potting” (i.e., drawing) red/colour/red/colour… red/colour (always replacing the colours but not the reds), then “potting” the six colours (not replaced) in their correct sequence. Strangely, the probability of doing this was also one in a whole number.

What are the two whole numbers?

[teaser2989]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 9:30 am on 4 January 2020 Permalink | Reply
  This Python program calculates P(k, n), the probability of selecting n consecutive red/colour pairs (with the red not replaced and the colour replaced), if k reds are available initially (and 6 colours).
  
  It runs in 83ms.
  
  Run: [ @replit ]
```
from enigma import (Rational, irange, factorial, printf)

Q = Rational()

# calculate the probability of a red/colour sequence of length n
# with k reds available (and m colours)
def P(k, n, m=6):
  t = k + m
  p = Q(1)
  for _ in irange(1, n):
    p *= Q(k, t)
    k -= 1
    t -= 1
    p *= Q(m, t)
  return p

# consider possible numbers of reds (between 2 and 15)
for k in irange(2, 15):
  # calculate probability of 2 (red, colour) pairs
  p2 = P(k, 2)
  if not (p2.numerator == 1): continue

  # and of k (red, colour) pairs
  pk = P(k, k)

  # the probability of drawing the six colours in order = 1/6!
  p = Q(pk, factorial(6))
  if not (p.numerator == 1): continue

  # output solution
  printf("[k={k}] P({k}, 2) = {p2}; P({k}, {k}) = {pk}; p = {p}")
```
  Solution: The two numbers are 15 and 352,800 (i.e. the probabilities are 1/15 and 1/352,800).
  
  When there are k reds available (and 6 colours) the probability of selecting a red (not replaced) followed by a colour (to be replaced) is:
  
  P(k, 1) = (k / (k + 6)) × (6 / (k + 5)) = 6k / (k + 5)(k + 6)
  
  When there are 4 reds available the probability of select the first red/colour pair is:
  
  P(4, 1) = 4/15
  
  There are now 3 reds available, and the probability of selecting a second red/colour pair is:
  
  P(3, 1) = 1/4
  
  Multiplying these together we get a probability of select two red/colour pairs in a row as:
  
  P(4, 2) = P(4,1) × P(3,1) = 4/15 × 1/4 = 1/15
  
  The probabilities of selecting a third and fourth red/colour pair are:
  
  P(2, 1) = 3/14
  P(1, 1) = 1/7
  
  Combining all these we get:
  
  P(4, 4) = P(4, 1) × P(3, 1) × P(2, 1) × P(1, 1) = 4/15 × 1/4 × 3/14 × 1/7 = 1/490
  
  The probability of selecting the six colours in the correct order is: 1/6! = 1/720.
  
  Giving a probability of “clearing the table” of:
  
  p = P(4, 4) / 6! = 1/352,800
  
  LikeLike
Jim Randell 4:25 pm on 27 December 2019 Permalink | Reply
Tags: by: John Owen ( 33 )
Teaser 2988: Open the box
From The Sunday Times, 29th December 2019 [link] [link]

Game show contestants are shown a row of boxes, each containing a different sum of money, increasing in regular amounts (eg, £1100, £1200, £1300, …), but they don’t know the smallest amount or the order. They open one box then take the money, or decline that and open another box (giving them the same choices, apart from opening the last box when they have to take the money).

Alf always opens boxes until he finds, if possible, a sum of money larger than the first amount. Bert’s strategy is similar, except he opens boxes until he finds, if possible, a sum of money larger than both of the first two amounts. Remarkably, they can both expect to win exactly the same amount on average.

How many boxes are there in the game?

[teaser2988]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 4:37 pm on 27 December 2019 Permalink | Reply
  With k boxes, we always win a base amount, along with some multiple of the increment. So we can just consider the boxes to take on the values from 1 to k.
  
  This Python program considers increasing numbers of boxes, looking at the total winnings for A and B for all possible arrangements of boxes. Until it finds two totals with the same value. It runs in 75ms.
  
  Run: [ @repl.it ]
```
from enigma import (subsets, irange, inf, printf)

# strategy, take the first amount larger than the first n boxes
def strategy(s, n):
  t = max(s[:n])
  for x in s[n:]:
    if x > t: break
  return x

# strategies for A and B
A = lambda s: strategy(s, 1)
B = lambda s: strategy(s, 2)

# play the game with k boxes
def play(k):
  # collect total winnings for A and B
  tA = tB = 0
  # consider possible orderings of the boxes
  for s in subsets(irange(1, k), size=k, select="P"):
    tA += A(s)
    tB += B(s)
  return (tA, tB)

for k in irange(3, inf):
  (tA, tB) = play(k)
  if tA != tB: continue
  printf("{k} boxes")
  break
```
  Solution: There are 6 boxes.
  
  For 3 to 5 boxes A’s strategy is better than B’s. When there are more than 6 boxes B’s strategy is better.
  
  Using prizes with values from 1..k I found that the average winnings for A and B are:
  
  k=3: A = 2.333; B = 2.000
  k=4: A = 3.125; B = 2.917
  k=5: A = 3.900; B = 3.800
  k=6: A = 4.667; B = 4.667
  k=7: A = 5.429; B = 5.524
  k=8: A = 6.188; B = 6.375
  k=9: A = 6.944; B = 7.222
  k=10: A = 7.700; B = 8.067
  k=11: A = 8.455; B = 8.909
  k=12: A = 9.208; B = 9.750
  
  In general we have:
  
  A(k) = (3k − 2) (k + 1) / 4k
  B(k) = (5k − 6) (k + 1) / 6k
  
  So, as k increases the ratio of A’s average approaches 3/4 (= 75.0%) of the maximum available prize. And the ratio of B’s average approaches 5/6 (= 83.3%) of the maximum prize.
  
  From the equations we see that the average winnings are the same when:
  
  (3k − 2)(k + 1) / 4k = (5k − 6)(k + 1) / 6k
  3(3k − 2) = 2(5k − 6)
  9k − 6 = 10k − 12
  k = 6 (for k > 2)
  
  In general a strategy of looking at n values and then taking the next highest value gives average winnings from k boxes according to the following formula:
  
  S(n, k) = ((2n + 1)k² − (n² − n − 1)k − (n² + n)) / (2n + 2)k
  S(n, k) = ((2n + 1)k − n(n + 1)) (k + 1) / 2(n + 1)k
  
  So: A(k) = S(1, k) and B(k) = S(2, k).
  
  LikeLike
Jim Randell 5:21 pm on 20 December 2019 Permalink | Reply
Tags: by: Graham Smithers ( 82 )
Teaser 2987: Table mats
From The Sunday Times, 22nd December 2019 [link] [link]

Beth and Sam were using computers to design two table mats shaped as regular polygons.

The interior angles of Beth’s polygon were measured in degrees; Sam’s were measured in grads. [A complete turn is equivalent to 360 degrees or 400 grads.]

On completion they discovered that all of the interior angles in the 2 polygons had the same numerical whole number value.

If I told you the last digit of that number, you should be able to work out the number of edges in (a) Beth’s table mat and (b) Sam’s table mat.

What were those numbers?

[teaser2987]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
GeoffR and Jim Randell are discussing. Toggle Comments
- Jim Randell 8:53 pm on 20 December 2019 Permalink | Reply
  This Python program determines the regular polygons with integer internal angles for 360 divisions (degrees) and 400 divisions (grads). It then finds the common values, and which of those are unique mod 10. It runs in 77ms.
  
  Run: [ @repl.it ]
```
from enigma import (divisors_pairs, intersect, filter_unique, printf)

# record n-gons by internal angles
# t is the number of subdivisions in a circle
# return map of: <internal angle> -> <number of sides>
def ngons(t):
  r = dict()
  for (d, n) in divisors_pairs(t, every=1):
    if n > 2:
      r[t // 2 - d] = n
  return r

# find n-gons for 360 subdivisions and 400 subdivisions
A = ngons(360)
B = ngons(400)

# find interior angles that match
ss = intersect([A.keys(), B.keys()])

# filter them by the units digit
ss = filter_unique(ss, (lambda x: x % 10))

# output solution
for i in ss.unique:
  printf("angle = {i} -> (a) {a}-gon, (b) {b}-gon", a=A[i], b=B[i])
```
  Solution: (a) Beth’s polygon has 72 sides; (b) Sam’s polygon has 16 sides.
  
  A 72-gon has internal angles measuring 175°. A 16-gon has internal angles measuring 157.5° = 175 grads.
  
  There are 4 numbers which will give regular n-gons for angles expressed in degrees and grads. These are:
  
  120: degrees → 6-gon (hexagon); grads → 5-gon (pentagon)
  150: degrees → 12-gon (dodecagon); grads → 8-gon (octagon)
  160: degrees → 18-gon (octadecagon); grads → 10-gon (decagon)
  175: degrees → 72-gon (heptacontakaidigon?); grads → 16-gon (hexadecagon)
  
  Obviously only the last of these is uniquely identified by the final (units) digit.
  
  LikeLike
- GeoffR 8:53 am on 24 December 2019 Permalink | Reply
  This programme gives four answers to the constraints in the puzzle.
  The first three answers have a common units digit of zero, and the fourth answer has a unique digit of five, which provides the answer to the puzzle. Merry Xmas!
```
% A Solution in MiniZinc
include "globals.mzn";

var 1..400: S;  % Sam's angle (grads)
var 1..360: B;  % Beth's angle (degrees)

var 1..150: n1; % edges to Sam's table mat
var 1..120: n2; % edges to Beth's table mat
constraint n1 != n2;

% Internal angles equal gives 180 - 360/n1 = 200 - 400/n2 
constraint B == 180 - 360 div n1 /\ 360 mod n1 == 0;
constraint S == 200 - 400 div n2 /\ 400 mod n2 == 0;
constraint 180 * n1 * n2 - 360 * n2 == 200 * n1 * n2 - 400 * n1;
 
solve satisfy;

output [" Edges for Sam's table mat = " ++ show(n1) ++ 
", Edges for Beth's table mat = " ++ show(n2)
++ "\n Sam's angle = " ++ show(S) ++ ", Beth's angle = " ++ show(B)];

%  Edges for Sam's table mat = 6, Edges for Beth's table mat = 5
%  Sam's angle = 120, Beth's angle = 120
% ----------
%  Edges for Sam's table mat = 12, Edges for Beth's table mat = 8
%  Sam's angle = 150, Beth's angle = 150
% ----------
%  Edges for Sam's table mat = 18, Edges for Beth's table mat = 10
%  Sam's angle = 160, Beth's angle = 160
% ----------
%  Edges for Sam's table mat = 72, Edges for Beth's table mat = 16
%  Sam's angle = 175, Beth's angle = 175  << unique last digit
% ----------
% ==========
```
  LikeLike
Jim Randell 5:35 pm on 13 December 2019 Permalink | Reply
Tags: by: Stephen Hogg ( 62 )
Teaser 2986: The Prhymes’ Numbers
From The Sunday Times, 15th December 2019 [link] [link]

The Prhymes’ triple live album “Deified” has hidden numerical “tricks” in the cover notes. Track 1, with the shortest duration, is a one-and-a-half minute introduction of the band, shown as “1. Zak, Bob, Kaz 1:30” in the cover notes. The other nineteen tracks each have different durations under ten minutes and are listed similarly with durations in “m:ss” format.

For each of tracks 2 to 20, thinking of its “m:ss” duration as a three-figure whole number (ignoring the colon), the track number and duration value each have the same number of factors. Curiously, the most possible are palindromic; and the most possible are even.

What is the total album duration (given as m:ss)?

[teaser2986]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 9:37 pm on 13 December 2019 Permalink | Reply
  This Python program collect possible numbers corresponding to track times by the number of divisors, and then the required track numbers, also by the number of divisors. It then correlates the lists, maximising the number of palindromes and even numbers. It runs in 78ms.
  
  Run: [ @repl.it ]
```
from itertools import product
from collections import defaultdict
from enigma import irange, nconcat, tau, nsplit, printf

# check a sequence is a palidrome
def is_palindrome(s):
  return len(s) < 2 or (s[0] == s[-1] and is_palindrome(s[1:-1]))

# collect possible track lengths as 3-digit numbers
# recorded by the number of divisors
d = defaultdict(list)
for s in product(irange(1, 9), irange(0, 59)):
  n = nconcat(s, base=100)
  if n < 131: continue # shortest track is 1:30
  d[tau(n)].append(n)

# collect the number of divisors for tracks from 2 to 20
t = defaultdict(list)
for n in irange(2, 20):
  t[tau(n)].append(n)

# accumulate the total album duration (in seconds)
total = 90

# find track lengths for the categories of tracks
for (k, ts) in t.items():
  # find the palindromes and evens
  (ps, es) = (set(), set())
  for n in d[k]:
    if is_palindrome(nsplit(n)): ps.add(n)
    if n % 2 == 0: es.add(n)
  # try and use even palindromes
  ss = ps.intersection(es)
  # otherwise, use the evens _and_ the palindromes
  if not ss: ss = ps.union(es)
  # otherwise use all available numbers
  if not ss: ss = d[k]
  ss = sorted(ss)
  printf("{k} divisors = {n} tracks {ts} -> {ss}", n=len(ts))
  # check there are no other choices
  assert len(ss) == len(ts)

  # add them to the total time
  total += sum(nconcat(nsplit(n, base=100), base=60) for n in ss)

# output duration in minutes, seconds
(m, s) = divmod(total, 60)
printf("album duration = {m:d}m{s:02d}s")
```
  Solution: The total album duration is 106:01 (i.e. 1 hour, 46 minutes, 1 second).
  
  LikeLike

Jim Randell 9:04 pm on 6 December 2019 Permalink | Reply
Tags: by: Angela Newing ( 37 )

Teaser 2985: What’s my (land) line?

From The Sunday Times, 8th December 2019 [link] [link]

My telephone has the usual keypad:

My [11-digit] telephone number starts with 01 and ends in 0. All digits from 2 to 9 are used exactly once in between, and each pair of adjacent digits in the phone number appear in a different row and column of the keypad array.

The 4th and 5th digits are consecutive as are the 9th and 10th and the 8th digit is higher than the 9th.

What is my number?

[teaser2985]

Jim Randell 9:25 pm on 6 December 2019 Permalink | Reply

Suppose the phone number is: 01-ABCDEFGH-0.

We can use the [[ SubstitutedExpression() ]] solver from the enigma.py library to solve this puzzle.

The following run file executes in 146ms.

Run: [ @repl.it ]

#! python -m enigma -rr

SubstitutedExpression

--digits="2-9"

# 4th and 5th digits are consecutive numbers
"abs(B - C) = 1"

# as are 9th and 10th digits
"abs(G - H) = 1"

# 8th digit is greater than the 9th
"F > G"

# assign row/col values to the individual digits
--code="row = [ 4, 1, 1, 1, 2, 2, 2, 3, 3, 3 ]"
--code="col = [ 2, 1, 2, 3, 1, 2, 3, 1, 2, 3 ]"
--code="check = lambda s: all(row[x] != row[y] and col[x] != col[y] for (x, y) in tuples(s, 2))"
# adjacent digits appear in different rows/columns
"check([1, A, B, C, D, E, F, G, H, 0])"

# solution
--code="number = lambda x: sprintf('01{x:08d}0')"
--answer="number(ABCDEFGH)"

Solution: The phone number is 01867295340.

LikeLike

Frits 12:46 pm on 24 September 2020 Permalink | Reply

 
# make sure loop variable value is not equal to previous ones
def domain(v):
  # find already used loop values  ...
  vals = set()
  # ... by accessing previously set loop variable names
  for s in lvd[v]:
    vals.add(globals()[s])
  
  return [x for x in range(2,10) if x not in vals]
  
def check(s):
  # row coord: (1 + (i - 1) // 3)
  # col coord: (1 + (i - 1) % 3)
  
  # Check adjacent fields
  for (x, y) in list(zip(s, s[1:])):
    # check if on same row 
    if (x - 1) // 3 == (y - 1) // 3:
      return False
    # check if on same col 
    if (x - y) % 3 == 0:
      return False  
  return True      

# set up dictionary of for-loop variables
lv = ['A', 'B', 'C', 'G', 'H', 'F', 'D', 'E']
lvd = {v: lv[:i] for i, v in enumerate(lv)}

sol = set()

# Solve puzzle by testing all posssible values
for A in {5, 6, 8, 9}:
  for B in domain('B'):
    if not check([A, B]): continue
    for C in domain('C'):
      if abs(B - C) != 1: continue
      if not check([B, C]): continue
      for G in domain('G'):
        for H in domain('H'):
          if abs(G - H) != 1: continue
          if not check([G, H]): continue
          for F in domain('F'):
            if F < G: continue
            if not check([F, G]): continue
            for D in domain('D'):
              for E in domain('E'):
                if not check([C, D, E, F]): continue
                sol.add((A, B, C, D, E, F, G, H))

print("  ABCDEFGH ")             
for s in sol:
  print(f"01{''.join(str(x) for x in s)}0")  

# Output:
#
#   ABCDEFGH
# 01867295340

LikeLike

Jim Randell 4:48 pm on 29 November 2019 Permalink | Reply
Tags: by: Victor Bryant ( 139 )

Teaser 2984: Shuffle the cards

From The Sunday Times, 1st December 2019 [link] [link]

In the classroom I have a box containing ten cards each with a different digit on it. I asked a child to choose three cards and to pin them up to make a multiplication sum of a one-figure number times a two-figure number. Then I asked the class to do the calculation.

During the exercise the cards fell on the floor and a child pinned them up again, but in a different order. Luckily the new multiplication sum gave the same answer as the first and I was able to display the answer using three of the remaining cards from my box.

What was the displayed answer?

[teaser2984]

Jim Randell 5:05 pm on 29 November 2019 Permalink | Reply
If the original sum is A × BC, then none of the digits in the second sum can be in their original positions, so the second sum is one of: B × CA or C × AB.

We can use the [[ SubstitutedExpression() ]] solver from the enigma.py library to solve this one.

Run: [ @repl.it ]
```
#! python -m enigma -rr

SubstitutedExpression

# initial sum
"A * BC = DEF"

# but it also works in a different order
"DEF in (B * CA, C * AB)"

# required answer
--answer="DEF"
```
Solution: The result of the two multiplications is 130.

The two sums are: 2×65 and 5×26, but we don’t know which was the original one.

LikeLike
- Jim Randell 9:42 pm on 2 December 2019 Permalink | Reply
  If we consider the two possible pairs of sums:
  
  A × BC = DEF ∧ B × CA = DEF
  A × BC = DEF ∧ C × AB = DEF
  
  Rewriting the first with A = X, B = Y, C = Z and the second with A = Y, B = Z, C = X, we get:
  
  X × YZ = DEF ∧ Y × ZX = DEF
  Y × ZX = DEF ∧ X × YZ = DEF
  
  Which are the same, so we can solve the puzzle with an even simpler one liner:
```
% python -m enigma SubstitutedExpression "X * YZ = DEF" "Y * ZX = DEF" --answer="DEF"
(X * YZ = DEF) (Y * ZX = DEF) (DEF)
(5 * 26 = 130) (2 * 65 = 130) (130) / D=1 E=3 F=0 X=5 Y=2 Z=6
DEF = 130 [1 solution]
```
  LikeLike

GeoffR 7:41 pm on 4 December 2019 Permalink | Reply


from time import perf_counter_ns
start = perf_counter_ns()

from itertools import permutations

for p in permutations((1,2,3,4,5,6,7,8,9),3):
    a, b, c = p    # choose 3 positive digits

    # Original displayed answer
    s = a * (10 * b + c)
    
    # 1st alternative position for digits to give same product
    if s == b * (10 * c + a):
        if len (set((a, b, c, s//100, s//10%10, s%10))) == 6:
          print(f"1.Original displayed answer = {s} ({a}*{10*b+c})")
          print(f"2nd displayed answer = {s} ({b}*{10*c+a})")
          print(f"1st digit={a}, 2nd digit={b}, 3rd digit={c}")
          print(f"{(perf_counter_ns() - start) / 1e6:.3f} milliseconds")

    # 2nd alternative positions for digits to give same product
    if s == c * (10 * a + b):
        if len (set((a, b, c, s//100, s//10%10, s%10))) == 6:
          print(f"2.Original displayed answer = {s} ({a}*{10*b+c})")
          print(f"2nd displayed answer = {s} ({c}*{10*a+b})")
          print(f"1st digit={a}, 2nd digit={b}, 3rd digit={c}")
          print(f"{(perf_counter_ns() - start) / 1e6:.3f} milliseconds")

# 2.Original displayed answer = 130 (2*65)
# 2nd displayed answer = 130 (5*26)
# 1st digit=2, 2nd digit=6, 3rd digit=5
# 49.703 milliseconds
#
# 1.Original displayed answer = 130 (5*26)
# 2nd displayed answer = 130 (2*65)
# 1st digit=5, 2nd digit=2, 3rd digit=6
# 88.180 milliseconds

LikeLike

GeoffR 4:54 pm on 5 December 2019 Permalink | Reply

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

var 1..9: A; var 1..9: B; var 1..9: C; var 1..9: D;
var 0..9: E; var 0..9: F;

constraint all_different([A, B, C, D, E, F]);

var 10..99: BC = 10*B + C;
var 10..99: CA = 10*C + A;
var 10..99: AB = 10*A + B;
var 100..999: DEF = 100*D + 10*E + F;

% Original sum
constraint A * BC == DEF;

% Sums with digits in a different order
constraint B * CA == DEF \/ C * AB == DEF;

solve satisfy;

output ["Displayed Sum is " ++ show(A) ++ " X " ++ show(BC)
++ " = " ++ show(DEF) ];

% Displayed Sum is 2 X 65 = 130
% Displayed Sum is 5 X 26 = 130
% ==========

LikeLike

Jim Randell 5:08 pm on 22 November 2019 Permalink | Reply
Tags: by: Danny Roth ( 84 )

Teaser 2983: Maths for dessert

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

George and Martha have their five daughters round the dinner table. After the meal, they had ten cards numbered 0 to 9 inclusive and randomly handed two to each daughter. Each was invited to form a two-digit number. The daughter drawing 0 obviously had no choice and had to announce a multiple of ten.

However, the others each had the choice of two options. For example if 3 and 7 were present, either 37 or 73 would be permissible. George added up the five two-digit numbers (exactly one being divisible by 9) and Martha noticed that three of the individual numbers divided exactly into that total.

What was the total of the remaining two numbers?

[teaser2983]

Jim Randell 5:16 pm on 22 November 2019 Permalink | Reply

This Python program runs in 76ms.

Run: [ @repl.it ]

from enigma import (partitions, irange, cproduct, filter2, ordered, printf)

# form numbers from digits a and b
def numbers(a, b):
  if a > 0: yield 10 * a + b
  if b > 0: yield 10 * b + a

# deal out the 10 cards in pairs
for ps in partitions(irange(0, 9), 2):
  # exactly one of the numbers is divisible by 9
  if sum((a + b) % 9 == 0 for (a, b) in ps) != 1: continue
  # form the numbers from the pairs
  for ns in cproduct(numbers(*p) for p in ps):
    # exactly three of the numbers divide into the total
    t = sum(ns)
    (ds, rs) = filter2((lambda n: t % n == 0), ns)
    if len(ds) != 3: continue
    # output solution
    printf("sum{rs} = {s} [numbers = {ns}, total = {t}]", rs=ordered(*rs), s=sum(rs), ns=ordered(*ns))

Solution: The sum of the numbers that do not divide into the total is 147.

The numbers are: 14, 28, 50, 63, 97.

Of these only 63 is divisible by 9.

The sum of the numbers is 252, which is divisible by 14, 28, and 63.

And the remaining numbers (50 and 97) sum to 147.

LikeLike

GeoffR 9:47 am on 25 November 2019 Permalink | Reply


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

var 1..9:A; var 1..9:B; var 1..9:C;
var 1..9:D; var 1..9:E; var 1..9:F;
var 1..9:G; var 1..9:H; var 1..9:I;

% Make J the zero digit
int: J == 0;

constraint all_different ([A,B,C,D,E,F,G,H,I,J]);
  
% Five 2-digit numbers 
var 10..99: AB = 10*A + B;
var 10..99: CD = 10*C + D;
var 10..99: EF = 10*E + F;
var 10..99: GH = 10*G + H;
var 10..99: IJ = 10*I + J;

var 10..400: all_dig; 
var 10..200: dig2;   % sum of the remaining two numbers

constraint all_dig = AB + CD + EF + GH + IJ;

% One of the five 2-digit numbers is divisible by 9
constraint sum ( [ AB mod 9 == 0, CD mod 9 == 0, 
EF mod 9 == 0, GH mod 9 == 0, IJ mod 9 == 0 ] ) = 1;

% Three of the 2-digit numbers divide the five digit total
constraint all_dig mod AB == 0 /\ all_dig mod CD == 0 
/\ all_dig mod EF == 0 /\ all_dig mod GH != 0 /\ all_dig mod IJ != 0;

% Sum of two digits which do not divide the five digit total
constraint  dig2 == GH + IJ ;

solve satisfy;

output [ "Total of the remaining two numbers = " ++ show(dig2)
++ "\nTotal of five 2-digit numbers = " ++ show(all_dig)++ "\n"
++"The five numbers are " ++ show(AB) ++ ", " ++ show(CD) ++ ", " 
++ show(EF) ++ ", " ++ show(GH) ++ " and " ++ show(IJ) ];

% Total of the remaining two numbers = 147
% Total of five 2-digit numbers = 252
% The five numbers are 28, 14, 63, 97 and 50

LikeLike

GeoffR 7:56 am on 28 November 2019 Permalink | Reply


from itertools import permutations

for p in permutations('1234567890'):
  a, b, c, d, e, f, g, h, i, j = p
  
  ab, cd, ef = int(a + b), int(c + d), int(e + f)
  gh, ij = int(g + h), int(i + j)

  # check all five numbers are 2-digit numbers
  n5 = (ab, cd, ef, gh, ij)
  if all( x < 100 and x >= 10 for x in n5):
    tot = ab + cd + ef + gh + ij

    # two conditions to check
    if (sum(1 for y in n5 if y % 9 == 0) == 1 
      and sum(1 for z in n5 if tot % z == 0) == 3) :
         
      if (tot % ab == 0 and tot % cd == 0 and tot % ef == 0
        and tot % gh != 0 and tot % ij != 0) :
        print(f"Three factors are {ab}, {cd} and {ef}" )
        print(f"Two remaining numbers are {gh} and {ij} (total {gh+ij})")
        break    # to stop repeated answers

# Three factors are 14, 28 and 63
# Two remaining numbers are 50 and 97 (total 147)

LikeLike

Jim Randell 5:15 pm on 15 November 2019 Permalink | Reply
Tags: by: Graham Smithers ( 82 )
Teaser 2982: Antique tea pot
From The Sunday Times, 17th November 2019 [link] [link]

My local antiques dealer marks each item with a coded price tag in which different digits represent different letters. This enables him to tell the whole number of pounds he paid for the item. I bought a tea pot from him tagged MOE.

Inside the tea pot was a scrap of paper which I used to work out his code. The letters AMOUNT I SPENT had been rearranged to make the multiplication sum above.

How much did he pay for the tea pot?

[teaser2982]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
GeoffR and Jim Randell are discussing. Toggle Comments
- Jim Randell 5:18 pm on 15 November 2019 Permalink | Reply
  The multiplication is straightforward to solve manually.
  
  Programatically, we can solve this puzzle using the [[ SubstitutedExpression() ]] solver from the enigma.py library.
  
  The following run file executes in 145ms.
  
  Run: [ @repl.it ]
```
#! python -m enigma -rr

SubstitutedExpression

"MAN * PIN = TOOTIN"

"MAN * N = TUON"
"MAN * I = AASA"
"MAN * P = TMEP"

--answer="MOE"
```
  Solution: MOE = 350, so the teapot cost £ 350.
  
  The corresponding digits for AMOUNT I SPENT are 235961 7 84061.
  
  LikeLike
- GeoffR 3:03 pm on 16 November 2019 Permalink | Reply
```
% A Solution in MiniZinc
include "globals.mzn";    

%       M A N
%    X  P I N 
%    ---------
%     T U O N
%   A A S A
% T M E P
%------------
% T O O T I N
%-------------

var 0..9: A; var 0..9: M; var 0..9: O; var 0..9: U;
var 0..9: N; var 0..9: T; var 0..9: I;
var 0..9: S; var 0..9: P; var 0..9: E;

constraint M > 0 /\ P > 0 /\ T > 0 /\ A > 0;

var 100..999: MAN = 100*M + 10*A + N;
var 100..999: PIN = 100*P + 10*I + N;
var 100..999: MOE = 100*M + 10*O + E;

var 1000..9999: TUON = 1000*T + 100*U + 10*O + N;

var 10000..99999: AASA = 11010*A + 100*S;

var 100000..999999: TMEP = 100000*T + 10000*M
+ 1000*E + 100*P;

var 100000..999999: TOOTIN = 100100*T + 11000*O
+ 10*I + N;

constraint MAN * PIN == TOOTIN;
constraint N * MAN == TUON;
constraint I * MAN * 10 == AASA;
constraint P * MAN * 100 == TMEP;

solve satisfy;

output [ "MOE = £" ++ show(MOE) ++ "\n" ++
"Main sum is " ++ show(MAN) ++ " X " ++
show(PIN) ++ " = " ++ show(TOOTIN) ];
```
  LikeLike
Jim Randell 4:53 pm on 8 November 2019 Permalink | Reply
Tags: by: Howard Williams ( 43 )
Teaser 2981: Faulty pedometer
From The Sunday Times, 10th November 2019 [link] [link]

Judith is a keen walker who uses a five-digit pedometer to record her number of steps. Her pedometer is inaccurate as some of the counters consistently move on to 0 early by missing out one or more digits. For instance, one of them might roll over from 7 to 0 every time instead of from 7 to 8, missing out digits 8 and 9. She is, however, well aware of this and can work out the correct number of steps.

After walking her usual distance, the pedometer shows 37225 steps but she knows that the true number is 32% less than this. A second distance she walks requires a 30% reduction in the number displayed to give the true number of steps.

How many steps is the second distance?

[teaser2981]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 7:38 am on 9 November 2019 Permalink | Reply
  Originally I thought the pedometer would be accumulating steps (so the second reading would add some steps to the first reading), but I could not find a solution where the second reading should be reduced by 30% (although I did get an answer where it was reduced by 28%).
  
  So I considered the problem where the pedometer is reset to zero before the start of each walk, and doesn’t wrap around. This gives a unique solution.
  
  This Python program finds possible bases for the 32% reduction, and then uses those bases to look for values with a 30% reduction. It runs in 161ms.
  
  Run: [ @repl.it ]
```
from enigma import (div, irange, nconcat, printf)

# find k bases that give a reading of R for actual value N
def bases(R, N, k, bs=[]):
  if k == 0:
    if R == N:
      yield bs
  else:
    (r, d) = divmod(R, 10)
    for b in irange(d + 1, 10):
      (n, x) = divmod(N, b)
      if x == d:
        yield from bases(r, n, k - 1, bs + [b])

# turn actual value n into a reading according to bases bs
def reading(n, bs):
  ds = list()
  for b in bs:
    (n, d) = divmod(n, b)
    ds.insert(0, d)
  if n > 9: return
  ds.insert(0, n)
  return nconcat(ds)

# solve the puzzle
# R = initial reading
# p = percentage of R for actual reading
# q = percentage for next reading
def solve(R, p, q):
  N = div(R * p, 100)
  printf("[reading = {R} -> actual = {N}]")

  # compute bases for the first 4 digits
  for bs in bases(R, N, 4):
    printf("[bases = {bs}]")

    # find an actual value for the next reading
    for n in irange(1, 99999):
      # calculate the required reading
      r = div(n * 100, q)
      if r is None: continue
      # calculate the reading from the bases
      r2 = reading(n, bs)
      if r2 is None: break
      if r == r2:
        yield (n, r, bs)

# solve for the required parameters
for (n, r, bs) in solve(37225, 68, 70):
  printf("steps = {n} [reading={r}, bases={bs}]")
```
  Solution: The second distance was 10080 steps.
  
  The units digit skips 9.
  
  The tens digit operates normally.
  
  The hundreds digit skips 9.
  
  The thousands digit skips 8 and 9.
  
  The ten thousands digit must be able to read as far as 3 correctly (in order for the initial reading to be 37225).
  
  So, initially, 25313 steps gives a reading of 37225.
  
  25313 = (((3 × 8) + 7) × 9 + 2) × 10 + 2) × 9 + 5
  
  and:
  
  25313 = 0.68 × 37225
  
  And then a value of 10080 steps gives a reading of 14400.
  
  10080 = (((1 × 8) + 4) × 9 + 4) × 10 + 0) × 9 + 0
  
  and:
  
  10080 = 0.70 × 14400
  
  LikeLike
Jim Randell 4:32 pm on 1 November 2019 Permalink | Reply
Tags: by: John Owen ( 33 ), by: Susan Bricket ( 17 )
Teaser 2980: Egyptian weights and measures
From The Sunday Times, 3rd November 2019 [link] [link]

We were wondering why ancient Egyptians chose to represent arbitrary fractions as sums of distinct unit fractions of the form 1/n (thus 5/7 = 1/2 + 1/5 + 1/70). One of us recalled long ago watching our greengrocer use four brass weights of 1/2, 1/4, 1/8, 1/16 lb to weigh any number of ounces up to 15 by stacking some of them on one side of her balancing scales. We wanted to make a metric equivalent, a set of distinct weights of unit fractions of a kilo, each weighing a whole number of grams, to weigh in 10g steps up to 990g.

Naturally, we wanted to use as little brass as possible, but we found that there were several possible such sets. Of these, we chose the set containing the fewest weights.

List, in increasing order, the weights in our set.

[teaser2980]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 5:03 pm on 1 November 2019 Permalink | Reply
  Possible weights are the divisors of 1000.
  
  This Python program looks for subsets that permit all the required weights to be made, and then selects those sets with the minimal possible weight. It runs in 501ms.
  
  Run: [ @repl.it ]
```
from enigma import (divisors, inf, subsets, printf)

# find weights that are unit fractions of 1000
weights = divisors(1000)
weights.remove(1000)

# find minimal weight sets of weights that can be used to weigh all
# multiples of 10 from 10 to 990
(w, rs) = (inf, list())

# choose a set of weights
for ws in subsets(weights, min_size=7):
  k = sum(ws)
  if k < 990 or k > w: continue

  # collect amounts
  amounts = set()
  # choose a subset of the weights to use
  for s in subsets(ws, min_size=1):
    # calculate the total weight
    t = sum(s)
    # is it a multiple of 10 between 10 and 990?
    if 9 < t < 991 and t % 10 == 0:
      amounts.add(t)

  # can we make 99 different amounts?
  if len(amounts) == 99:
    if k < w: (w, rs) = (k, list())
    rs.append(ws)
    printf("[{k} = {ws} ({n})]", n=len(ws))

# and find the minimum number weights in the set
n = min(len(ws) for ws in rs)

# output solutions
for ws in rs:
  if len(ws) == n:
    printf("min = {w}; set of {n} weights = {ws}")
```
  Solution: There are 10 weights in the set: 2g, 5g, 8g, 10g, 25g, 40g, 50g, 100g, 250g, 500g.
  
  The total weight of the set is 990g (which is obviously the minimum possible total to be able to weigh up to 990g).
  
  There are 4 viable sets of weights that have a total weight of 990g:
  
  set of 10 weights = (2, 5, 8, 10, 25, 40, 50, 100, 250, 500)
  set of 11 weights = (1, 2, 4, 8, 10, 25, 40, 50, 100, 250, 500)
  set of 12 weights = (1, 2, 4, 5, 8, 10, 20, 40, 50, 100, 250, 500)
  set of 13 weights = (1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 125, 200, 500)
  
  When I initially read the puzzle I solved it allowing weights to be placed on both sides of the scales, and I found two sets of 7 weights which can be used to achieve the required values, where both sets weigh 990g in total:
  
  set of 7 weights = (5, 20, 40, 50, 125, 250, 500)
  set of 7 weights = (5, 20, 40, 100, 125, 200, 500)
  
  LikeLike

Jim Randell 8:00 pm on 25 October 2019 Permalink | Reply
Tags: by: Graham Smithers ( 82 )

Teaser 2979: Mischievous Sam

From The Sunday Times, 27th October 2019 [link] [link]

I set Sam a question, the answer to which was a 3-digit number, with the digits increasing by 1 from first to last (e.g. 789).

Sam eventually produced a 3-digit answer, but only 2 of his digits were correct and in the correct position. The third digit was wrong.

Investigating further I found that Sam had the correct answer but, for devilment, decided to change it into a different (single-digit) base.

If I were to tell you which of his 3 digits was the wrong one, you should be able to tell me:

(a) the correct answer, and;
(b) the base used by Sam.

What are they?

[teaser2979]

Jim Randell 10:36 pm on 25 October 2019 Permalink | Reply
There are only 7 possible 3-digit decimal results, and each of these can only be expressed as a 3-digit number in a limited number of single digit integer bases, so the search space is very small.

The following Python program runs in 82ms.

Run: [ @repl.it ]
```
from enigma import (defaultdict, irange, tuples, nconcat, cbrt, intc, nsplit, int2base, printf)

# record numbers by the position of the incorrect digit
r = defaultdict(list)

# consider sequences of 3 consecutive increasing digits
for ds in tuples(irange(1, 9), 3):
  n = nconcat(ds)

  # consider the digits of n in other bases
  for b in irange(intc(cbrt(n)), 9):
    bs = nsplit(n, base=b)

    # find the positions of digits that differ
    ps = list(i for (i, (b, d)) in enumerate(zip(bs, ds)) if b != d)
    if len(ps) != 1: continue

    printf("[{n} = {m} (base {b}) -> {ps}]", m=int2base(n, b))
    r[ps[0]].append((n, b))

# find unique solutions
for (k, vs) in r.items():
  if len(vs) != 1: continue
  # output solution
  (n, b) = vs[0]
  printf("incorrect {k} -> {n} = {m} (base {b})", m=int2base(n, b))
```
Solution: (a) The correct answer is 123; (b) Sam used base 8.

The only possible solutions are:

123 → 323 (base 6)
123 → 173 (base 8)
456 → 556 (base 9)

The first and third of these differ from the decimal representation in the first (most significant) digit. Which leaves the second (which differs in the second digit) as the solution.

If we allow bases higher than 9 we find there is one further potential candidate solution:

789 → 489 (base 13)

But this differs from the decimal representation in the first digit, so would not change the answer to the puzzle.

LikeLike

GeoffR 7:54 pm on 28 October 2019 Permalink | Reply

I used a number base calculator to give an assisted manual solution.

Link: https://www.rapidtables.com/convert/number/base-converter.html?x=456&sel1=10&sel2=9


# Teaser 2979

# Number base calculator gives this table
# which includes one value with two digits the same
#
# Base10  Base4  Base5  Base6  Base7  Base8  Base9
# ------------------------------------------------
# 123     n/a    443    323    234    173    146
#-----------------------------------------------
# 234     n/a    n/a    n/a    453    352    280
#-----------------------------------------------
# 345     n/a    n/a    n/a    n/a    531    423
#-----------------------------------------------
# 456     n/a    n/a    n/a    n/a    710    556
#-----------------------------------------------
# 567     n/a    n/a    n/a    n/a    n/a    700
#-----------------------------------------------
# 678     n/a    n/a    n/a    n/a    n/a    833
#-----------------------------------------------
# 789     n/a    n/a    n/a    n/a    n/a    n/a
#-----------------------------------------------

# n/a means 3-digit value not available for given base

LikeLike

GeoffR 11:34 am on 3 November 2019 Permalink | Reply


from time import perf_counter_ns
start = perf_counter_ns()

def nbr_to_base(num, base):
  dgts = []
  while num:
    num, r = divmod(num, base)
    dgts.append(r)
  return ''.join(str(x) for x in reversed(dgts))

def diff_pos(n1, n2):
  # Split each of two numbers into three digits
  a, b, c = n1 // 100, n1 // 10 % 10, n1 % 10
  d, e, f = n2 // 100, n2 // 10 % 10, n2 % 10

  # check 2 of the 3 digits are in correct position
  # and only one digit is in the wrong position in Sam's number
 
  # check if 1st and 2nd digits are in correct position
  if a == d and b == e and c != f:
    return 3
 
  # check if 1st and 3rd digits are in correct position
  if a == d and c == f and b != e:
    return 2
 
  # check if 2nd and 3rd digits are in correct position
  if b == e and c == f and  a != d:
    return 1
  
  return 0

# 3-digit numbers with digits increasing by 1 from first to last
for num in (123, 234, 345, 456, 567, 678, 789):
  for nb in range(4, 10):
    N = nbr_to_base(num, nb)
    if 100 < int(N) < 1000:
      dp = diff_pos(num, int(N))
      if dp:      
        print(f"Answer {num} ({N} in base {nb}) differs in position {dp}", end='')
        print(f" (in {(perf_counter_ns() - start) / 1e6:.3f} milliseconds)")

# Answer 123 (323 in base 6) differs in position 1 (in 8.936 milliseconds)
# Answer 123 (173 in base 8) differs in position 2 (in 16.619 milliseconds)
# Answer 456 (556 in base 9) differs in position 1 (in 35.507 milliseconds)

The first and third solutions both give the incorrect digit as the first position, so we cannot tell the incorrect digit from these two solutions.

The second solution gives a single position for the incorrect digit position, so this is the answer i.e Answer 123 (173 in base 8) differs in position 2.

LikeLike

Frits 12:05 pm on 8 April 2021 Permalink | Reply

I wanted to test the filter_unique function with a complex lambda function otherwise Jim’s line 16 approach could have been used. The “correct” function is taken from Mastermind puzzles.

# calculate the number of dead-right's
correct = lambda xs, ys: sum(x == y for (x, y) in zip(xs, ys))

# ceil a positive number
ceil = lambda n: int(n) if n == int(n) else int(n) + 1
    
# convert from integer to any base number            
def int2base(n, b, D="0123456789abcdefghijklmnopqrstuvwxyz"):
  return D[0] if not n else (int2base(n // b, b)).lstrip(D[0]) + D[n % b]
 
# return all entries where f(x) occurs only once
#                 or where f(x) occurs more than once
def filter_unique(seq, f=lambda x: x, mode="unique"):
  d = dict()
  for s in seq:
    d[f(s)] = f(s) in d

  if mode == "unique":      # occuring only once
    return [s for s in seq if not d[f(s)]]
  else:                     # occuring more than once
    return [s for s in seq if d[f(s)]]
      
li = [] 
# 3-digit numbers with digits increasing by 1 from first to last
for n in (123, 234, 345, 456, 567, 678, 789):
  # limit the used bases so they result in a 3 digit number
  for b in range(ceil(n ** (1 / 3)), int(n ** 0.5) + 1):
    N = int2base(n, b)
   
    # Sam eventually produced a 3-digit answer
    if not N.isdigit(): continue
   
    # if 2 digits are correct the other must be incorrect
    if correct(str(n), N) == 2:      
      li.append((str(n), N, b))

f = filter_unique(li, lambda s: [i for i, x in enumerate(s[0]) 
                                          if x not in s[1]][0])
                          
if len(f) == 1:
  print(f"correct answer = {f[0][0]}, Sam's base = {f[0][-1]}")

LikeLike

	Frits on Teaser 3304: Roaming bull
	Jim Randell on Teaser 3304: Roaming bull
	Jim Randell on Teaser 3304: Roaming bull
	Frits on Brain teaser 983: Superch…
	GeoffR on Teaser 2312: Backward ste…
	Ruud on Teaser 2312: Backward ste…
	Jim Randell on Teaser 2312: Backward ste…
	Jim Randell on Brain teaser 983: Superch…

Search

Recent Posts

Recent Comments

Archives

Categories

Subscribe

RSS Links

Site Stats

Meta

Updates from March, 2020 Toggle Comment Threads | Keyboard Shortcuts

Jim Randell 5:09 pm on 6 March 2020 Permalink | Reply Tags: by: Andrew Skidmore ( 85 )

Rate this:

Share:

Jim Randell 5:54 pm on 6 March 2020 Permalink | Reply

Robert Brown 11:11 am on 7 March 2020 Permalink | Reply

Jim Randell 11:13 am on 7 March 2020 Permalink | Reply

Jim Randell 12:02 pm on 7 March 2020 Permalink | Reply

GeoffR 11:09 am on 8 March 2020 Permalink | Reply

Robert Brown 1:46 pm on 8 March 2020 Permalink | Reply

Jim Randell 10:27 am on 10 March 2020 Permalink | Reply

Reply Cancel reply

Jim Randell 5:10 pm on 28 February 2020 Permalink | Reply Tags: by: Stephen Hogg ( 62 )

Rate this:

Share:

Jim Randell 5:31 pm on 28 February 2020 Permalink | Reply

Frits 12:26 pm on 24 December 2020 Permalink | Reply

Jim Randell 5:22 pm on 21 February 2020 Permalink | Reply Tags: by: Victor Bryant ( 139 )

Rate this:

Share:

Jim Randell 8:55 pm on 21 February 2020 Permalink | Reply

Jim Randell 10:55 am on 23 February 2020 Permalink | Reply

Robert Brown 12:57 pm on 25 February 2020 Permalink | Reply

Robert Brown 1:03 pm on 25 February 2020 Permalink | Reply

Jim Randell 2:20 pm on 25 February 2020 Permalink | Reply

Jim Randell 4:58 pm on 14 February 2020 Permalink | Reply Tags: by: Howard Williams ( 43 )

Rate this:

Share:

Jim Randell 5:07 pm on 14 February 2020 Permalink | Reply

Jim Randell 9:24 am on 15 February 2020 Permalink | Reply

GeoffR 1:09 pm on 17 February 2020 Permalink | Reply

Frits 2:22 pm on 3 September 2020 Permalink | Reply

Jim Randell 5:22 pm on 7 February 2020 Permalink | Reply Tags: by: Bill Kinally ( 7 )

Rate this:

Share:

Jim Randell 5:36 pm on 7 February 2020 Permalink | Reply

Jim Randell 6:36 pm on 7 February 2020 Permalink | Reply

Frits 10:52 pm on 3 August 2020 Permalink | Reply

Jim Randell 10:24 am on 4 August 2020 Permalink | Reply

Frits 8:51 am on 7 August 2020 Permalink | Reply

Frits 8:10 pm on 3 August 2020 Permalink | Reply

Jim Randell 9:58 am on 4 August 2020 Permalink | Reply

Jim Randell 7:39 am on 14 June 2025 Permalink | Reply

Jim Randell 5:37 pm on 31 January 2020 Permalink | Reply Tags: by: Peter Good ( 27 )

Rate this:

Share:

Jim Randell 8:24 am on 1 February 2020 Permalink | Reply

Robert Brown 8:45 pm on 1 February 2020 Permalink | Reply

Jim Randell 8:59 pm on 1 February 2020 Permalink | Reply

Robert Brown 3:49 pm on 3 February 2020 Permalink | Reply

Jim Randell 9:46 am on 4 February 2020 Permalink | Reply

Jim Randell 5:40 pm on 24 January 2020 Permalink | Reply Tags: by: Stephen Hogg ( 62 )

Rate this:

Share:

Jim Randell 9:44 am on 25 January 2020 Permalink | Reply

Jim Randell 4:09 pm on 25 January 2020 Permalink | Reply

Frits 4:21 pm on 15 August 2025 Permalink | Reply

GeoffR 9:03 am on 30 January 2020 Permalink | Reply

Jim Randell 9:42 am on 22 January 2020 Permalink | Reply Tags: by: Danny Roth ( 84 )

Rate this:

Share:

Jim Randell 9:43 am on 22 January 2020 Permalink | Reply

Frits 10:59 pm on 22 December 2020 Permalink | Reply

Jim Randell 5:07 pm on 10 January 2020 Permalink | Reply Tags: by: Howard Williams ( 43 )

Rate this:

Share:

Jim Randell 5:24 pm on 10 January 2020 Permalink | Reply

Jim Randell 10:20 pm on 11 January 2020 Permalink | Reply

GeoffR 9:32 am on 12 January 2020 Permalink | Reply

Frits 7:24 pm on 25 July 2020 Permalink | Reply

Jim Randell 11:08 pm on 25 July 2020 Permalink | Reply

Jim Randell 5:09 pm on 6 March 2020 Permalink | Reply
Tags: by: Andrew Skidmore ( 85 )

Jim Randell 5:10 pm on 28 February 2020 Permalink | Reply
Tags: by: Stephen Hogg ( 62 )

Jim Randell 5:22 pm on 21 February 2020 Permalink | Reply
Tags: by: Victor Bryant ( 139 )

Jim Randell 4:58 pm on 14 February 2020 Permalink | Reply
Tags: by: Howard Williams ( 43 )

Jim Randell 5:22 pm on 7 February 2020 Permalink | Reply
Tags: by: Bill Kinally ( 7 )

Jim Randell 5:37 pm on 31 January 2020 Permalink | Reply
Tags: by: Peter Good ( 27 )

Jim Randell 5:40 pm on 24 January 2020 Permalink | Reply
Tags: by: Stephen Hogg ( 62 )

Jim Randell 9:42 am on 22 January 2020 Permalink | Reply
Tags: by: Danny Roth ( 84 )

Jim Randell 5:07 pm on 10 January 2020 Permalink | Reply
Tags: by: Howard Williams ( 43 )

Jim Randell 8:55 am on 4 January 2020 Permalink | Reply
Tags: by: Andrew Skidmore ( 85 )

Jim Randell 4:25 pm on 27 December 2019 Permalink | Reply
Tags: by: John Owen ( 33 )

Jim Randell 5:21 pm on 20 December 2019 Permalink | Reply
Tags: by: Graham Smithers ( 82 )

Jim Randell 5:35 pm on 13 December 2019 Permalink | Reply
Tags: by: Stephen Hogg ( 62 )

Jim Randell 9:04 pm on 6 December 2019 Permalink | Reply
Tags: by: Angela Newing ( 37 )

Jim Randell 4:48 pm on 29 November 2019 Permalink | Reply
Tags: by: Victor Bryant ( 139 )

Jim Randell 5:08 pm on 22 November 2019 Permalink | Reply
Tags: by: Danny Roth ( 84 )

Jim Randell 5:15 pm on 15 November 2019 Permalink | Reply
Tags: by: Graham Smithers ( 82 )

Jim Randell 4:53 pm on 8 November 2019 Permalink | Reply
Tags: by: Howard Williams ( 43 )