Recent Updates Page 26 Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 9:14 am on 13 April 2023 Permalink | Reply
    Tags:   

    Teaser 2697: Gimme five! 

    From The Sunday Times, 1st June 2014 [link] [link]

    In the list of words below each different letter consistently represents a different digit. Each of the coded numbers has the property that the sum of its digits is divisible by (but not equal to) the number it spells out:

    THREE
    FIVE
    EIGHT
    NINE
    TEN
    ELEVEN
    THIRTEEN

    What number does FIVE represent?

    [teaser2697]

     
    • Jim Randell's avatar

      Jim Randell 9:15 am on 13 April 2023 Permalink | Reply

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

      The following run file executes in 70ms. (Internal runtime of the generated program is 3.0ms).

      #! python3 -m enigma -rr

SubstitutedExpression

"div(T + H + R + E + E, 3) > 1"
"div(F + I + V + E, 5) > 1"
"div(E + I + G + H + T, 8) > 1"
"div(N + I + N + E, 9) > 1"
"div(T + E + N, 10) > 1"
"div(E + L + E + V + E + N, 11) > 1"
"div(T + H + I + R + T + E + E + N, 13) > 1"

--template="THREE FIVE EIGHT NINE TEN ELEVEN THIRTEEN"
--answer="FIVE"

      Solution: FIVE = 8237.

      We have:

      THREE = 45177
      FIVE = 8237
      EIGHT = 72654
      NINE = 9297
      TEN = 479
      ELEVEN = 707379
      THIRTEEN = 45214779

      Like

    • GeoffR's avatar

      GeoffR 10:24 am on 14 April 2023 Permalink | Reply 

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

% Leading digits of numbers
var 1..9:T; var 1..9:F; var 1..9:E; var 1..9:N;
% Other digits in numbers
var 0..9:I; var 0..9:H; var 0..9:R;
var 0..9:G; var 0..9:V; var 0..9:L;
 
constraint all_different([T, F, E, N, I, H, R, G, V, L]);

% For each number, sum of its digits is divisible by (but not equal to) the number it spells out
constraint (T + E + N) mod 10 == 0 /\ (T + E + N) div 10 > 1;
constraint (N + I + N + E) mod 9 == 0 /\ (N + I + N + E) div 9 > 1;
constraint (T + H + R + E + E) mod 3 == 0 /\ (T + H + R + E + E) div 3 > 1;
constraint (F + I + V + E) mod 5 == 0 /\ (F + I + V + E) div 5 > 1;
constraint (E + I + G + H + T) mod 8 == 0 /\ (E + I + G + H + T) div 8 > 1;
constraint (E + L + E + V + E + N) mod 11 == 0 /\ (E + L + E + V + E + N) div 11 > 1;
constraint (T + H + I + R + T + E + E + N) mod 13 == 0 /\ (T + H + I + R + T + E + E + N) div 13 > 1;

solve satisfy;

% Digits of numbers in teaser
output ["[T,H,R,E,E ] = " ++ show([T,H,R,E,E ] )
++ "\n" ++ "[F,I,V,E] = " ++ show ([F,I,V,E] )
++ "\n" ++ "[E,I,G,H,T] = " ++ show([E,I,G,H,T] )
++"\n" ++ "[N,I,N,E] = " ++ show([N,I,N,E])
++"\n" ++ "[T,E,N] = " ++ show ([T,E,N] )
++ "\n" ++ "[E,L,E,V,E,N] = " ++ show ([E,L,E,V,E,N] )
++ "\n" ++ "[T,H,I,R,T,E,E,N] = " ++ show ([T,H,I,R,T,E,E,N] )
];

% [T,H,R,E,E ] = [4, 5, 1, 7, 7]
% [F,I,V,E] = [8, 2, 3, 7]   - so FIVE = 8237 (answer)
% [E,I,G,H,T] = [7, 2, 6, 5, 4]
% [N,I,N,E] = [9, 2, 9, 7]
% [T,E,N] = [4, 7, 9]
% [E,L,E,V,E,N] = [7, 0, 7, 3, 7, 9]
% [T,H,I,R,T,E,E,N] = [4, 5, 2, 1, 4, 7, 7, 9]
% ----------
% ==========
% Finished in 180msec

      Like

  • Unknown's avatar

    Jim Randell 9:41 am on 11 April 2023 Permalink | Reply
    Tags:   

    Teaser 2703: Bastille Day 

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

    Three towns in France issue their own car licence plates. Argentan’s numbers consist of the digits 1 to 9 in some order, Beaurepaire’s consist of the digits 1 to 8 in some order, and Corbigny’s consist of the digits 1 to 7 in some order. All three towns only use numbers divisible by 11 and all such possible plates have been issued. Tomorrow is Bastille Day and, in order to minimise chaos, only cars with licence numbers divisible by 5 will be allowed in.

    In the form “one in …”

    (a) What proportion of Argentan’s cars will be allowed into Argentan?

    (b) What proportion of Beaurepaire’s cars will be allowed into Beaurepaire?

    (c) What proportion of Corbigny’s cars will be allowed into Corbigny?

    [teaser2703]

     
    • Jim Randell's avatar

      Jim Randell 9:42 am on 11 April 2023 Permalink | Reply

      I assumed each valid number plate is a rearrangement of all allowable digits (each appearing exactly once).

      This Python program constructs the valid plates, and counts those divisible by 5. It runs in 189ms.

      from enigma import (irange, subsets, nconcat, fraction, printf)

# solve the puzzle
qs = dict(A=irange(1, 9), B=irange(1, 8), C=irange(1, 7))
for k in sorted(qs.keys()):
  ds = qs[k]
  # count plates divisible by 11 (t) and those divisible by 5 (n)
  t = n = 0
  for s in subsets(ds, size=len, select='P'):
    p = nconcat(s)
    if p % 11 == 0:
      t += 1
      if p % 5 == 0:
        n += 1
  # find the fraction
  (a, b) = fraction(n, t)
  # output solution
  printf("{k}: {t} plates, {n} divisible by 5 = {a}/{b}")

      Solution: (a) 1 in 11; (b) 1 in 8; (c) 1 in 8.

      The counts for total number of plates, and permitted plates are:

      A: total = 31680, permitted = 2880 (1 in 11)
      B: total = 4608, permitted = 576 (1 in 8)
      C: total = 576, permitted = 72 (1 in 8)

      Like

  • Unknown's avatar

    Jim Randell 10:12 am on 9 April 2023 Permalink | Reply
    Tags: , ,   

    Teaser 2161: Love hearts 

    From The Sunday Times, 15th February 2004 [link]

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

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

    How many red hearts are on the card?

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

    [teaser2161]

     
    • Jim Randell's avatar

      Jim Randell 10:13 am on 9 April 2023 Permalink | Reply

      I recently revisited Enigma 82 and Enigma 144 and this puzzle can also be solved using similar techniques.

      The number of cells for an arrangement with n rows is obviously tri(n).

      And if the number of red, pink and white hearts are {k − 1, k, k + 1} (in some order), then we can only find a solution when:

      tri(n) = 3k

      And so we can skip cases where tri(n) is not divisible by 3, i.e. n = 4, 7, 10, 13, …

      Once we calculate the possible configurations that give equilateral triangles we can determine a minimum hitting set for these configurations, and all the remaining cells can then be coloured red without giving a configuration that has three reds forming an equilateral triangle, and this is the maximum possible number of reds.

      If this number in in the set {k − 1, k, k + 1} then we have a viable solution, and the cells that form the hitting set can be divided into an appropriate number of pink and white cells.

      This Python program uses the MiniZinc implementation of the minimum hitting set problem and can be used to examine the puzzle for various values of n. The first solution presents itself at n = 11, which the program solves in 3m35s (using the “scip” solver).

      from enigma import (irange, subsets, div, empty, arg, printf)
from utils_mzn import hitting_set

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

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

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

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

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

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

r = T - len(hs)  # max number of red hearts
printf("maximum red hearts = {r}")
printf("*** {x}SOLUTION ***", x=('' if r in ss else 'NOT A '))

      Solution: The smallest solution has 22 red hearts (with 11 rows of circles), but 25 red hearts is also possible (with 12 rows of circles).

      t = tris; r = reds
 n     t    seq        r  [scip  ] [highs ]
 2     1    0,1,2      2           [ 188ms] [SOLUTION]
 3     5    1,2,3      4           [ 194ms]
 4    15    -          6           [ 188ms]
 5    35    4,5,6      8           [ 206ms]
 6    70    6,7,8     10           [ 242ms]
 7   126    -         12  [ 481ms] [ 449ms]
 8   210    11,12,13  14  [ 1.41s] [  1.5s]
 9   330    14,15,16  17  [ 4.77s] [  7.6s]
10   495    -         20  [ 14.0s] [ 37.5s]
11   715    21,22,23  22  [ 3m02s] [13m14s] [SOLUTION]
12  1001    25,26,27  25  [28m29s] [ 2h15m] [SOLUTION]
13  1365    -         28  [ 8h18m] [35h21m]
14  1820    34,35,36  31

      t = OEIS A000332
      r = OEIS A240114

      The numbers in seq appear to be growing more rapidly than the numbers in r, so it seems likely these are the only solutions.

      The solution at n = 2 is disallowed as the puzzle text implies that n > 3 (and also as it requires one of the colours to have no corresponding cells).

      Here are some example maximal layouts for various n values:

      The published solution is that there were 16 red hearts.

      And so the numbers of red, pink, white hearts must be 14, 15, 16 to make a total of 45 cells, hence the arrangement has 9 rows.

      However, as we have seen above, the maximum number red hearts for an arrangement with 9 rows is actually 17, so we do not get a solution at n = 9.

      It is possible that the setter(s) assumed that the “inverted-V” shape that we see in solutions for n = 4, 5, 6, which gives a solution with 2(n − 1) red cells, would provide a maximal solution for larger n.

      Like

      • Frits's avatar

        Frits 8:49 pm on 15 April 2023 Permalink | Reply

        @Jim,

        I had a look at [ http://www.hakank.org/minizinc/hitting_set.mzn ] and tried the N=11 case in the MiniZinc program.

        Your model ran for 10 min 52 secs:

        solve minimize(sum(x));
....
constraint x[52] + x[54] + x[61] > 0;
constraint x[9] + x[21] + x[29] > 0;
....
constraint x[2] + x[9] + x[58] > 0;

        The model with predicate hitting_set ran for 6 min 20 secs:

        solve :: int_search(x, most_constrained, indomain_min, complete) minimize k;
....

n = 715;
v = [
{52, 61, 54},
{9, 29, 21},
....
{9, 2, 58}
];

        I guess it’s the “exists” statement in the predicate hitting_set that makes the difference.

        Like

        • Jim Randell's avatar

          Jim Randell 12:04 pm on 16 April 2023 Permalink | Reply

          @Frits: Thanks for the link. I did some tests (with MiniZinc 2.7.2), but found that in general my original formulation ran slightly faster than hakank’s model.

          However, I did download the “scip” solver, and found that it was able to solve the N=11 case in 3m15s, and the N=12 case in just 29m.

          Like

      • Jim Randell's avatar

        Jim Randell 11:58 am on 5 May 2023 Permalink | Reply

        It is possible to install commercial solvers that integrate with MiniZinc and are able to use multiple CPUs.

        The CPLEX solver can be installed from IBM (registration required), and this enables the cplex solver in MiniZinc (you may need to tell it where CPLEX is using the --cplex-dll parameter). You can then use the --parallel <n> parameter to enable multithreading.

        The free version of CPLEX is limited to models with 1000 variables/constraints, but this is sufficient for this problem up to N = 11, which is where the first solution is found. I found CPLEX could solve this using 4 threads in an elapsed time of 42.6s.

        Installing the gurobipy package via pip provides a license to use the Gurobi solver for models with up to 2000 variables/constraints. This is a bit trickier as the free version doesn’t integrate directly with MiniZinc, but I wrote a utils_gurobi.py module to provide the same interface via gurobipy.

        It solves (using 8 threads) the N = 11 case in 22.5s, and the N = 12 case in 9m07s, and the N = 13 case in 2h41m. And it should be able to do the N = 14 case.

        The Gurobi solver uses more CPU time than the (single-threaded) SCIP solver, but because it is able to use multiple CPUs the elapsed time is shorter.

        Like

        • Jim Randell's avatar

          Jim Randell 2:09 pm on 12 May 2023 Permalink | Reply

          Update: I ran the N = 14 case using the Gurobi solver. It took >161 hours (elapsed time), and used >750 hours total CPU time, a lot of RAM, and basically tied up my machine for a week.

          The size of the minimum hitting set is 74, which means the maximum number of red hearts is 31.

          The configuration found looks like this:

          Like

        • Frits's avatar

          Frits 4:57 pm on 12 May 2023 Permalink | Reply

          @Jim, are you going to publish utils_gurobi.py?

          Like

    • Frits's avatar

      Frits 2:14 pm on 13 May 2023 Permalink | Reply

      Or calling print_triangle(hs) for a graphical representation.

         
def print_triangle(s):
  # from top to bottom
  for r in range(N - 1, -1, -1):
    # in row r only (N - r) elements may be printed
    print(((r // 2) * "  " + (" " if r % 2 else "")), end=" ")
    for c in range(N - r):
      print("." if (r, c) in s else "R", end=" ")  
    print()

      Like

  • Unknown's avatar

    Jim Randell 3:57 pm on 7 April 2023 Permalink | Reply
    Tags:   

    Teaser 3159: King coin 

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

    The new King’s currency has 64 Minims (circular coins) per Suttas (notes). Each coin’s value is proportional to its face area, and is a whole number of cm in diameter, starting with 1 cm for 1 Minim.

    The King only wanted denominations such that his citizens can pay any amount below 1 Suttas using no more than a certain number of coins for the transaction. This number is the smallest possible, given the above conditions. His mint suggested that if just two values could require an extra coin, they could reduce the number of denominations needed.

    The King agreed and placed one of each minted denomination flat and face up in a rectangular display, with each coin’s edge resting along the display’s base. The order of the coins minimised the width of the display, with the smallest coin to the right of the centre.

    What are the diameters in cm, from left to right?

    [teaser3159]

     
    • Jim Randell's avatar

      Jim Randell 4:59 pm on 7 April 2023 Permalink | Reply

      A bit involved. Once we have found the set of denominations suggested by the mint, we then have to determine the minimal width arrangement of the coins (which is not quite as straightforward as it might first appear).

      This Python program runs in 70ms. (Internal runtime is 9.1ms).

      from enigma import (Accumulator, irange, sq, subsets, sqrt, find, printf)

# the 1 denomination is given
# possible remaining denominations (squares less than 64)
ps = dict((sq(i), i) for i in irange(2, 7))

# for each set of coins record values from 1 - 63 that can be made with just
# k coins, and record the smallest possible maximum value
ts = set(irange(1, 63))
d = dict()
K = Accumulator(fn=min, collect=1)
for ss in subsets(ps.keys()):
  # make the set of coins
  cs = (1,) + ss
  # values that can be made with up to k coins
  k = 0
  vs = {0}
  r = { k: vs }
  while ts.difference(vs):
    vs = vs.union(ts.intersection(v + x for v in vs for x in cs))
    k += 1
    r[k] = vs
  # record this set of values
  d[cs] = r
  K.accumulate_data(k, cs)

# find the smallest max number of coins required
# and the sets that achieve this
(k, css) = (K.value, K.data)
printf("change in {k} coins = {css}")

# calculate the total width (without overlaps) from a sequence of radii
dist = lambda a, b: 2 * sqrt(a * b)  # = sqrt(sq(a + b) - sq(a - b))
def width(rs):
  xs = list()
  for (i, r) in enumerate(rs):
    if i == 0:
      xs.append(r)
    else:
      x = max(xs[j] + dist(a, r) for (j, a) in enumerate(rs[:i]))
      xs.append(x)
  # calculate the width
  (a, b) = (min(x - r for (x, r) in zip(xs, rs)), max(x + r for (x, r) in zip(xs, rs)))
  w = b - a
  # and check the 1 coin is (entirely) in the right half of the arrangement
  i = find(rs, 1)
  if i != -1 and not (xs[i] - 1 > a + 0.5 * w): return None
  return w

# consider sets of coins
for (cs, r) in d.items():
  # must manage change in (k + 1) coins
  if not (max(r.keys()) == k + 1): continue
  # must be a (strict) subset of one of the sets that achieve change in k coins
  ss = set(cs)
  if not any(len(ss) < len(xs) and ss.issubset(xs) for xs in css): continue
  # find the values that require 5 coins
  xs = r[k + 1].difference(r[k])
  # there must be exactly 2 of them
  if len(xs) != 2: continue
  printf("reduced set = {cs}; change in {k1} coins = {xs}", k1=k + 1, xs=sorted(xs))

  # consider possible arrangements of coin radii
  W = Accumulator(fn=min, collect=1)
  for rs in subsets(list(ps.get(x, x) for x in cs), size=len, select='P'):
    w = width(rs)
    if w:
      W.accumulate_data(w, rs)

  # output solution
  for rs in W.data:
    printf("-> minimal width arrangement = {rs}")

      Solution: The diameters of the coins (left to right) are: 4cm, 2cm, 6cm, 1cm, 3cm.

      So they are arranged as follows:

      Note that the 1cm diameter coin does not contribute to the overall width of the display, as it fits in the gap between the 6cm and 3cm coin, but it is (wholly) in the right hand side of the display.

      The width of the minimum arrangement (distance between the red lines) is: 14.04cm.

      The smallest number of coins for which all change amounts can be given is 4.

      This can be achieved using the following denominations:

      (1, 4, 9, 16, 25, 36)
      (1, 4, 9, 16, 36, 49)
      (1, 4, 9, 16, 25, 36, 49)

      The last of these is a set consisting of all possible coins, and this must be able to change all amounts using the smallest possible number of coins.

      So the King could have suggested any of these sets.

      The mint then suggested a reduced set of coins, which all change amounts can be made in at most 4 coins, except for 51 and 59 (which require 5 coins).

      This set is:

      (1, 4, 9, 16, 36)
      51 = 1× 1 + 2× 9 + 2× 16 (5 coins)
      59 = 3× 9 + 2× 16 (5 coins)

      The names “Minim” and “Suttas” were chosen as together they use the letters from “numismatist” (i.e. a collector of coins).

      >>> multiset("minim" + "suttas") == multiset("numismatist")
True

      Like

    • Brian Gladman's avatar

      Brian Gladman 6:56 pm on 8 April 2023 Permalink | Reply

      Nice work on the “circles width” algorithm Jim. I initially missed the subtleties involved here which make what seems at first to be an easy task surprisingly difficult.

      Like

      • Jim Randell's avatar

        Jim Randell 10:30 pm on 8 April 2023 Permalink | Reply

        Yes, it is quite a tricky one. It took me a couple of goes to come up with a routine to calculate the minimum width correctly, which was not as simple as I had originally thought it would be.

        Like

    • Hugo's avatar

      Hugo 7:27 pm on 16 April 2023 Permalink | Reply

      That’s a relief not to have to keep 49-minim coins in my pocket.
      Even the 36-minim coin is rather large,
      but at least this one isn’t as silly as Teasers 1812 and 2926,
      where the value of a coin is proportional to its diameter.

      We see why, in the real world, it’s more usual to have the value of a coin proportional to its weight (which is likely to rise as the cube of the diameter), and with several series (e.g. copper, nickel-silver, and some other alloy).

      Like

    • Hugo's avatar

      Hugo 1:49 pm on 17 April 2023 Permalink | Reply

      The horizontal distance between the centres of the coins of diameter 6 and 1 is √6 ≈ 2.449.
      The horizontal distance between the centres of the coins of diameter 1 and 3 is √3 ≈ 1.732.
      The horizontal distance between the centres of the coins of diameter 6 and 3 is √18 ≈ 4.263,
      which is slightly greater than the sum of the other two, so the smallest coin has room to rattle.
      Add on √8 ≈ 2.828 and √12 ≈ 3.464 and the radii 2 and 1.5 of the outer coins,
      and we get about 14.035 between Jim’s red lines (all in cm, of course).

      It’s basically a simple calculation, thanks to Pythagoras,
      but I still managed to get the wrong configuration.
      The clever bit, I reckon, was spotting the anagram of numismatist.

      Like

  • Unknown's avatar

    Jim Randell 9:26 am on 6 April 2023 Permalink | Reply
    Tags:   

    Teaser 2691: Hot × buns 

    From The Sunday Times, 20th April 2014 [link] [link]

    I have consistently replaced each of the digits 0 to 9 by a different letter to turn some numbers into words. It turns out that the number EASTER is exactly divisible by each of:

    (a) the number of days in a week;
    (b) the number of days in a year;
    (c) the seasonal product HOT × BUNS.

    What numbers do HOT and BUNS represent?

    This puzzle is included in the book The Sunday Times Brain Teasers 2 (2020), however the “×” sign is missing in condition (c).

    [teaser2691]

     
    • Jim Randell's avatar

      Jim Randell 9:26 am on 6 April 2023 Permalink | Reply

      I assume there are (a) 7 days a week; and (b) 365 days a year.

      We can solve the puzzle using the [[ SubstitutedExpression ]] solver from the enigma.py library.

      The following run file executes in 74ms. (Internal runtime of the generated program is 11ms).

      #! python3 -m enigma -rr

SubstitutedExpression

"EASTER % 7 = 0"
"EASTER % 365 = 0"
"EASTER % (HOT * BUNS) = 0"

      Solution: HOT = 147; BUNS = 3285.

      And this is the only solution to the alphametic expression: EASTER % (HOT * BUNS) = 0.

      So it seems conditions (a) and (b) are just there to make things a bit easier.

      Like

    • GeoffR's avatar

      GeoffR 5:38 pm on 6 April 2023 Permalink | Reply 

      from itertools import permutations

for H, O, T in permutations ('1234567890', 3):
    if H == '0': continue
    HOT = int(H + O + T)
    # Find remaining seven digits
    q1 = set('1234567890').difference([H, O, T])
    for p2 in permutations(q1):
        E, A, S, R, B, U, N = p2
        if '0' in (E, B):continue
        BUNS = int(B + U + N + S)
        EASTER = int(E + A + S + T + E + R)
        if EASTER % 7 == 0 and EASTER % 365 == 0 \
           and EASTER % (HOT * BUNS) == 0:
           print(f"HOT = {HOT}, BUNS = {BUNS}, EASTER = {EASTER}")
    
# HOT = 147, BUNS = 3285, EASTER = 965790

      Like

  • Unknown's avatar

    Jim Randell 9:13 am on 4 April 2023 Permalink | Reply
    Tags:   

    Teaser 2706: Spinners 

    From The Sunday Times, 3rd August 2014 [link] [link]

    I have three “spinners” each with five evenly-spaced numbers on. All the numbers on the spinners are positive whole numbers and the sum of the five numbers on each spinner is the same. The first spinner has numbers 3, 3, 3, 3, 3 and the second has numbers 2, 2, 2, 3, 6. My friend chooses a spinner and I choose one of the remaining pair. Then we each spin to choose a number: sometimes it’s a draw, otherwise the higher number wins – and we repeat this many times. He gets very annoyed because (whichever spinner he chooses) I am always more likely to win.

    What are the five numbers on the third spinner?

    [teaser2706]

     
    • Jim Randell's avatar

      Jim Randell 9:14 am on 4 April 2023 Permalink | Reply

      We have encountered non-transitive games before. (See: Enigma 287, Enigma 1126, Tantalizer 428).

      This Python program runs in 59ms. (Internal runtime is 3.5ms).

      from enigma import (Rational, multiset, decompose, printf)

Q = Rational()
h = Q(1, 2)

# play X against Y, return chance of X beating Y
def play(X, Y):
  (X, Y) = map(multiset.from_seq, (X, Y))
  (nX, nY) = (X.size(), Y.size())
  (xs, ys) = (sorted(X.keys()), sorted(Y.keys()))
  # accumulate wins for X
  p = 0
  for x in xs:
    pX = Q(X.count(x), nX)
    for y in ys:
      if not (x > y): break
      pY = Q(Y.count(y), nY)
      p += pX * pY
  return p

# given spinners
A = (3, 3, 3, 3, 3)
B = (2, 2, 2, 3, 6)
# confirm A beats B
assert play(A, B) > h

# look for a third spinner C such that B beats C and C beats A
for C in decompose(15, 5, increasing=1, sep=0):
  if play(B, C) > h and play(C, A) > h:
    printf("{C}")

      Solution: The numbers on the third spinner are: 1, 1, 4, 4, 5.

      We have:

      A = (3, 3, 3, 3, 3)
      B = (2, 2, 2, 3, 6)
      C = (1, 1, 4, 4, 5)

      A beats B 60% of the time.
      B beats C 52% of the time.
      C beats A 60% of the time.

      Like

  • Unknown's avatar

    Jim Randell 9:26 am on 2 April 2023 Permalink | Reply
    Tags: by: V. Bryant   

    Brainteaser 1099: Jackpot! 

    From The Sunday Times, 28th August 1983 [link]

    Our local maths club has an appropriate slot machine. It consists of the digits from 1 to 9 in a row and each of them has a star below it which can light up. The machine always has some of the stars lit up and the idea is to read the number formed by the lit-up digits. So, for example, in the situation illustrated the number is 14689.

    There are four possible jackpots which this machine pays out. To have a go you observe the lit-up number, place 10p in the slot (which causes a different selection of digits to light), and observe the new number. (The machine is then ready for the next go). The jackpots are the “Fair Share” which is won if the number showing after putting in your 10p is precisely half the number which was showing before. The “Rare Square” which is won if the number showing after putting in your 10p is the square of the number showing before. The “Cute Root” which requires that the number before you place in the 10p is the square of the number showing afterwards. And the “Rum Sum” which is won if the number showing after you place in your 10p is the sum of the digit which were lit up before.

    One member had a very successful session yesterday. He placed four 10ps in the machine in order to have  four consecutive goes. And the sequence of five different selections of lit-up digits which he observed resulted in him winning all four jackpots.

    What number was showing immediately before he put in his first 10p?

    This puzzle is included in the book Microteasers (1986).

    [teaser1099]

     
    • Jim Randell's avatar

      Jim Randell 9:26 am on 2 April 2023 Permalink | Reply

      In order to arrive at a unique solution I had to (reasonably) assume that “some of the stars” means “at least 2 of the stars”.

      This Python program runs in 63ms. (Internal runtime is 7.8ms).

      from enigma import (irange, subsets, nconcat, dsum, diff, printf)

# possible displayed numbers
# = numbers with at least 2 different digits in increasing order
ns = list(subsets(irange(1, 9), min_size=2, fn=nconcat))

# record prize pairs
prize = { 1: set(), 2: set(), 3: set(), 4: set() }

# collect prize numbers
for n in ns:
  tw = 2 * n
  if tw in ns:
    prize[1].add((tw, n))
  sq = n * n
  if sq in ns:
    prize[2].add((n, sq))
    prize[3].add((sq, n))
  ds = dsum(n)
  if ds in ns:
    prize[4].add((n, ds))

# find a sequence of numbers that give prizes in <ks>
def solve(ks, ss):
  if not ks:
    yield ss
  else:
    x = ss[-1]
    for k in ks:
      for (y, z) in prize[k]:
        if x == y and z not in ss:
          yield from solve(diff(ks, {k}), ss + [z])

# choose a starting pair
for (k, vs) in prize.items():
  for (a, b) in vs:
    # solve for the remaining prizes
    for ss in solve(diff(prize.keys(), {k}), [a, b]):
      printf("{ss}")

      Solution: The machine was initially showing: 134689.

      So we have:

      134689 -(sqrt)-> 367 -(dsum)-> 16 -(sq)-> 256 -(half)-> 128

      Like

    • Frits's avatar

      Frits 6:35 pm on 2 April 2023 Permalink | Reply

      Starting from Jim’s program but not using enigma.py and using a dictionary of slot machine numbers .

         
from itertools import combinations

dsum = lambda n: sum(int(x) for x in str(n))

# number of different selections of lit-up digits
N = 5
 
# possible slot machine numbers
ns = list(int("".join(str(y) for y in x)) 
          for n in range(2, 10) for x in combinations(range(1, 10), n))
 
# dictionary of slot machine numbers and following jackpots
d = {n : list([0] * (N - 1)) for n in ns}
 
# collect dictionary elements
for n in ns:
  tw = 2 * n
  if tw in ns:
    d[tw][0] = n
  sq = n * n
  if sq in ns:
    d[n][1] = sq
    d[sq][2] = n
  ds = dsum(n)
  if ds in ns:
    d[n][3] = ds
 
# only keep slot machine numbers after which a jackpot may occur  
d = {k: v for k, v in d.items() if v != [0] * (N - 1)}    

# find a sequence of N slot machine numbers with N - 1 different jackpots
def solve(k, ss, types=[]):
  if len(ss) == N:
    yield ss
  else:
    for t, v in enumerate(d[k]):
      # type of jackpot already processed?
      if t in types: continue 
      if ((len(ss) == N - 1 and v in ns) or v in d):
        # number may not have been used before
        if v not in ss: 
          yield from solve(v, ss + [v], types + [t])
 
# check slot machine numbers after which a jackpot may occur 
for k in d.keys():
  # check if N - 1 different jackpots can follow
  for ss in solve(k, [k]):
    print(f"{ss}")

      Like

  • Unknown's avatar

    Jim Randell 3:57 pm on 31 March 2023 Permalink | Reply
    Tags:   

    Teaser 3158: Digital trio 

    From The Sunday Times, 2nd April 2023 [link] [link]

    “I have a couple of subtraction problems for you”, George told Martha.

    Look:

    N1 − N2 = N3
    N3 − N4 = N5

    Can you solve them if I tell you that N1, N3 and N5 are all three-digit whole numbers whose sum is less than 2000, the same three non-zero digits appearing in all three numbers but no digit being repeated within any of those numbers? N2 and N4 are both two-digit whole numbers [each] using two of the three digits mentioned above, and the first digit of N1 is not equal to the first digit of N2.

    What is N1?

    [teaser3158]

     
    • Jim Randell's avatar

      Jim Randell 4:14 pm on 31 March 2023 Permalink | Reply

      I used the following interpretation for the numbers. Each of the 3-digit numbers is an arrangement of the same 3 different digits. And each of the 2-digit numbers is an arrangement of two of those 3 digits (but the 2-digit numbers are not necessarily rearrangements of each other).

      We can solve this puzzle using the [[ SubstitutedExpression ]] solver from the enigma.py library.

      This run file executes in 82ms. (The internal runtime of the generated program is 15ms).

      #! python3 -m enigma -rr

SubstitutedExpression

#    ABC  (N1)
#  -  DE  (N2)
#  -----
#  = FGH  (N3)
#  -  IJ  (N4)
#  -----
#  = KLM  (N5)

--digits="1-9"
--distinct="ABC,DE,FGH,IJ,KLM,AD"

# N1 - N2 = N3
"ABC - DE = FGH"

# N3 - N4 = N5
"FGH - IJ = KLM"

# N1 + N3 + N5 < 2000"
"ABC + FGH + KLM < 2000"

# N1, N3, N5 have the same digits
"{A, B, C} == {F, G, H}"
"{A, B, C} == {K, L, M}"

# N2 and N4 are subsets of the 3 digits
"{D, E}.issubset({A, B, C})"
"{I, J}.issubset({A, B, C})"

--answer="ABC"

      Solution: N1 = 594.

      Like

    • GeoffR's avatar

      GeoffR 9:36 am on 1 April 2023 Permalink | Reply 

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

% Digits for three 3-digit numbers and two 2-digit numbers
var 1..9:A; var 1..9:B; var 1..9:C;
var 1..9:F; var 1..9:G; var 1..9:H;
var 1..9:K; var 1..9:L; var 1..9:M;
var 1..9:D; var 1..9:E;
var 1..9:I; var 1..9:J;

% Three 3-digit numbers and two 2-digit numbers
var 100..999:ABC == 100*A + 10*B + C;  % N1
var 100..999:FGH == 100*F + 10*G + H;  % N3
var 100..999:KLM == 100*K + 10*L + M;  % N5
var 10..99: DE == 10*D + E;  % N2
var 10..99: IJ == 10*I + J;  % N4

% Teaser number/digit constraints
constraint ABC + FGH + KLM < 2000;
constraint {A,B,C} == {F,G,H} /\ {A,B,C} == {K,L,M};
constraint {D,E} subset {A,B,C};
constraint {I,J} subset {A,B,C};
constraint A != D;

% Main equations
constraint ABC - DE == FGH;  % N1 - N2 = N3
constraint FGH - IJ == KLM;  % N3 − N4 = N5

solve satisfy;

output["N1 - N2 = N3 is " ++ show(ABC) ++ " - " ++ show(DE) ++ " = " ++ show(FGH)
++ "\n" ++ "N3 − N4 = N5 is " ++ show(FGH) ++ " - " ++ show(IJ) ++ " = " ++ show(KLM) ];

      Like

    • GeoffR's avatar

      GeoffR 5:26 pm on 1 April 2023 Permalink | Reply 

      
from itertools import permutations, combinations

from enigma import Timer
timer = Timer('ST3158', timer='E')
timer.start()

# choose three digits from 1..9
for DIG3 in combinations('123456789', 3):
  # Lists for two and three digit numbers
  DL2, DL3 = [], []
  A, B, C = DIG3
  # Form possible 3-digit numbers for N1, N3 and N5
  ABC, ACB, BAC = int(A + B + C), int(A + C + B), int(B + A + C)
  BCA, CAB, CBA = int(B + C + A), int(C + A + B), int(C + B + A)
  DL3 = [ABC, ACB, BAC, BCA, CAB, CBA]
  for N1, N3, N5 in permutations(DL3, 3):
    if N1 + N3 + N5 >= 2000:
      continue
    
    # Form possible 2-digit numbers for N2 and N4
    AB, AC, BA = int(A + B), int(A + C), int(B + A)
    BC, CB, CA = int(B + C), int(C + B), int(C + A) 
    DL2 = [AB, AC, BA, BC, CB, CA]
    for N2, N4 in permutations(DL2, 2):
      # check 1st digits of N1 and N2 are different
      if N1 // 100 == N2 // 10:
        continue
      # Check two sums given are valid
      if N1 - N2 == N3 and N3 - N4 == N5:
        print(f"1st sum is {N1} - {N2} = {N3}")
        print(f"2nd sum is {N3} - {N4} = {N5}")

# timer outside looping
timer.stop()      
timer.report()

      @ Jim: I guess it is OK to use the timer in enigma.py in the IDLE interface
      under Windows?
      I finished the timer outside all the looping and timed it
      on an I7 laptop (110 ms) and an I9 desktop (42ms)

      Like

  • Unknown's avatar

    Jim Randell 10:07 am on 30 March 2023 Permalink | Reply
    Tags: by: Jon Ashman   

    Teaser 2256: Stack of primes 

    From The Sunday Times, 11th December 2005 [link]

    The digits 0 to 9 are printed unambiguously on 10 discs and they are placed on a flat surface to form a triangular arrangement with one disc in the top row, two in the next row, three in the next row and four along the bottom row.

    No row begins with a zero, each row viewed as a single number is a prime; the sum of the digits in each row is a prime (with no two rows giving the same sum); all three corner digits are prime; and the sum of the digits around the perimeter of the triangle is prime. (Readers are reminded that 1 is not a prime).

    Draw a picture of the triangular stack.

    [teaser2256]

     
    • Jim Randell's avatar

      Jim Randell 10:11 am on 30 March 2023 Permalink | Reply

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

      The following run file executes in 68ms. (Internal runtime of the generated program is 3.1ms).

      #! python3 -m enigma -rr

SubstitutedExpression

# each row is prime
"is_prime(A)"
"is_prime(BC)"
"is_prime(DEF)"
"is_prime(GHIJ)"

# the sum of the digits in each row is prime
"is_prime(B + C)"
"is_prime(D + E + F)"
"is_prime(G + H + I + J)"

# and the sum of each row is different
"all_different(A, B + C, D + E + F, G + H + I + J)"

# all three corner digits are prime
"is_prime(G)"
"is_prime(J)"

# the sum of the digits around the perimeter is prime
"is_prime(45 - E)"

--template="(A) (BC) (DEF) (GHIJ)"
--solution=""

      Solution: The stack looks like this:

      Like

    • GeoffR's avatar

      GeoffR 12:05 pm on 30 March 2023 Permalink | Reply 

      
from enigma import is_prime, nsplit, all_different

#     A
#    B C
#   D E F
#  G H I J

for A in (2, 3, 5, 7):
  # 2nd row of pyramid
  for BC in range(10, 100):
    if not is_prime(BC):continue
    B, C = nsplit(BC)
    if not all_different(A, B, C):continue
    if not is_prime(B + C):continue
    
    # 3rd row of pyramid
    for DEF in range(100, 999):
      if not is_prime(DEF):continue
      D, E, F = nsplit(DEF)
      if not all_different(D, E, F):continue
      if not all_different(A, B, C, D, E, F):continue
      if not is_prime(D + E + F):continue
      
      # 4th row of pyramid
      for GHIJ in range(1000, 9999):
        if not is_prime(GHIJ):continue
        G, H, I, J = nsplit(GHIJ)
        if not all_different(G, H, I, J):continue
        if not is_prime(G + H + I + J):continue
        
        # All digits 0..9 are different
        if not all_different(A,B,C,D,E,F,G,H,I,J):continue
        # all three corner digits are prime (A already prime)
        if is_prime(G) and is_prime(J): 
          # the sum of each row is different
          if not all_different(A, B + C, D + E + F, G + H + I + J):
            continue
          # the sum of the digits around the perimeter is prime
          if is_prime(A + C + F + J + I + H + G + D + B):
            print(f"A={A}, BC={BC}, DEF={DEF}, GHIJ={GHIJ}")

# A=2, BC=61, DEF=487, GHIJ=5903

      @Jim: Why are 6 and 9 underlined in your diagram of the pyramid?

      Like

      • Jim Randell's avatar

        Jim Randell 12:14 pm on 30 March 2023 Permalink | Reply

        @GeoffR: This is to disambiguate the 6 and 9 discs, otherwise one could be used the wrong way up. The other digits don’t have this issue.

        Like

  • Unknown's avatar

    Jim Randell 9:14 am on 28 March 2023 Permalink | Reply
    Tags: ,   

    Teaser 2707: Good Times 

    From The Sunday Times, 10th August 2014 [link] [link]

    The Good Times bus company has a route from Timesboro to Teaseboro which passes through six other towns on its direct route. The distances from each town to the next are different whole numbers of miles, the largest of the seven distances being six miles more than the shortest. I worked out the average of those seven distances and my friend worked out the average distance between any two of the eight towns. Our answers used the same two digits but in reverse orders.

    How far is it from Timesboro to Teaseboro?

    [teaser2707]

     
    • Jim Randell's avatar

      Jim Randell 9:15 am on 28 March 2023 Permalink | Reply

      I am assuming all distances are measured along the road.

      The 7 distances between the towns are different whole numbers, where the largest of the values is 6 more than the smallest. So the distances, when ordered numerically, must form a sequence of 7 consecutive integers.

      We will denote them (x − 3, …, x + 3).

      The total of these distances (and the required answer) is: 7x.

      And the mean distance is: x.

      We can choose a 2-digit value for x (the mean of the distances), and then look for an arrangement of the distances that gives the mean pairwise distance to be the reverse of x.

      This Python program runs in 205ms.

      from enigma import (C, irange, multiset, subsets, tuples, printf)

# count the number of pairwise distances between the 8 towns
n = C(8, 2)

# count the number of times each segment occurs in the total distance
m = multiset()
for k in irange(1, 7):
  for s in tuples(irange(7), k):
    m.update(s)

# calculate total distance between pairs in <ss>
pair_dist = lambda ss: sum(s * m[i] for (i, s) in enumerate(ss))

# consider the digits a, b
for (a, b) in subsets(irange(1, 9), size=2, select='P'):
  # x is the mean of the segment lengths
  # y is the reverse of x
  (x, y) = (10 * a + b, 10 * b + a)

  # choose an order for the segments
  for ss in subsets(irange(x - 3, x + 3), size=7, select='P'):
    if pair_dist(ss) == n * y:
      # total distance is 7x
      printf("d={d} [x={x} y={y} ss={ss}]", d=7 * x)
      break  # we only need one example

      Solution: The total distance is 98 miles.

      For example the distances could be: (13, 15, 12, 11, 14, 16, 17) miles, to give a total distance of 98 miles. (But there are other arrangements of these distances which also work).

      The mean distance is 98/7 = 14 miles.

      If we label the distances (a, b, c, d, e, f, g) then there are 28 ways of choosing pairs of distances, and the total of these pairwise distances is given by:

      T = 7(a + g) + 12(b + f) + 15(c + e) + 16d

      (In the program this is determined by lines 6-10).

      So in this case we get: T = 1148, and so the pairwise mean is: 1148/28 = 41 miles.

      And we can use this analysis to produce a faster program.

      If the arrangement of distances is:

      (x + a, x + b, x + c, x + d, x + e, x + f)

      where (a, …, f) are the offsets (−3, …, 3) in some order.

      Then the pairwise mean is given by:

      3x + (7(a + g) + 12(b + f) + 15(c + e) + 16d)/28

      And so we can find arrangements of (a, …, f) that are multiples of 28, and these will give integer pairwise distances.

      We can then look for instances where a 2-digit mean distance (= x) along with a viable set of offsets gives a pairwise mean that is the reverse of x.

      from enigma import (irange, subsets, dot, div, printf)

# find ordering of offsets, that give an integer pairwise mean
rs = dict()
for vs in subsets(irange(-3, +3), size=7, select='P'):
  k = div(dot([7, 12, 15, 16, 15, 12, 7], vs), 28)
  if k is not None:
    rs[k] = vs

# consider digit reversed pairs of 2-digit numbers
for (a, b) in subsets(irange(1, 9), size=2, select='P'):
  # x is the mean of the segment lengths
  # y is the reverse of x
  (x, y) = (10 * a + b, 10 * b + a)

  # look for corresponding offsets
  for (k, vs) in rs.items():
    if 3 * x + k == y:
      ss = list(x + v for v in vs)
      printf("d={d} [x={x} y={y} ss={ss}]", d=7 * x)

      Like

  • Unknown's avatar

    Jim Randell 2:16 pm on 26 March 2023 Permalink | Reply
    Tags: by: J. G. Pratt   

    Brainteaser 1159: Number unobtainable 

    From The Sunday Times, 18th November 1984 [link]

    Our little village is furious because they have ‘improved’ our telephones. In other words they closed our local exchange, added several extra non-zero figures to the beginning of each person’s old number, and then put us into Hogglestock’s exchange. We used to have only a few figures in each of our phone numbers but now with umpteen of them (more than three times as many as before) it is quite beyond me to remember any of the new ones.

    However, I thought I had found a way to work out my own number. My old one was a prime, its digits were different and they came in ascending order. The amazing thing is that those facts are true of the added figures as well, and also of the complete new number! But all the commotion has left me in such a state that I’m not sure if I can work out my number correctly.

    What is my new number?

    [teaser1159]

     
    • Jim Randell's avatar

      Jim Randell 2:17 pm on 26 March 2023 Permalink | Reply

      The digits of the phone number are in increasing order, but do not start with 0, so there can be no zeros in the entire number.

      Also the new number has more than 3× the number of digits that the old one. So the added prefix is more than twice the length of the original number.

      If the original number only has 1 digit, then the added prefix must have more than 2 (i.e. 3 or more digits).

      If the digits are all different then the final number can have no more than 9 digits, and it must be more than 3× longer than the original number, so the original number can only have 1 or 2 digits. So the prefix must have 3 – 8 digits.

      This Python program runs in 58ms. (Internal runtime is 2.1ms).

      from enigma import (irange, subsets, nconcat, is_prime, wrap, cache, printf)

# generate k-length increasing numbers, that satisfy fn
# return (<n>, <first-digit>)
@cache
@wrap(list)
def generate(k, fn=is_prime):
  for ds in subsets(irange(1, 9), size=k, select='C'):
    n = nconcat(ds)
    if fn(n):
      yield (n, ds[0])

# consider p-length prefix
for p in irange(3, 8):
  for (pn, _) in generate(p):
    pd = pn % 10
    # consider s-length suffix
    for s in irange(1, (p - 1) // 2):
      for (sn, sd) in generate(s):
        if not (pd < sd): continue
        n = pn * 10**s + sn
        if not is_prime(n): continue
        # output solution
        printf("{pn} + {sn} -> {n}")

      Solution: The new number is: 1234789.

      The prefix is 12347, and the original number was 89.

      It doesn’t seem that hard to remember. Just dial the numbers in order, skipping 56.

      Like

    • Frits's avatar

      Frits 10:47 am on 27 March 2023 Permalink | Reply

      As we have more than three times as many figures as before and the original number had multiple digits we can conclude that the original number must have two digits (no zeroes allowed) .

      from enigma import SubstitutedExpression, is_prime

# invalid digit / symbol assignments
d2i = dict()
for d in range(0, 10):
  vs = set()
  if d == 0: vs.update('CDEFGHI')
  # G and I must be odd
  if d % 2 == 0: vs.update('GI')
  # ABCDEFGHI is increasing
  for i in range(1, 9):
    # set maximum
    if d > i: vs.update("ABCDEFGHI"[i-1])
    # set minimum
    if d < i - 1: vs.update("ABCDEFGHI"[i])
    
  d2i[d] = vs

if 0:
  print("Allowed values")
  for s in "ABCDEFGHI":   
    print(s, ":", end=" ")
    for k, vs in d2i.items():
      if s not in vs:
        print(k, end="")
    print()    
  
def check(n):
  # n has to be a prime number
  if not is_prime(n): return False
  
  # with increasing digits
  s = str(n)
  if "".join(sorted(s)) != s: return False
  return True

# the alphametic puzzle
p = SubstitutedExpression(
  [
    "check(HI)",
    "check(ABCDEFG)",
    "check(ABCDEFGHI)",
    "A == 0 or A < B",
  ],
  answer="ABCDEFGHI",
  d2i=d2i,
  # only A and B may be the same digit (if zero)
  distinct=("ACDEFGHI", "BCDEFGHI"),
  env=dict(check=check),
  #reorder=0,
  verbose=0,    # use 256 to see the generated code
)

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

      Like

      • Jim Randell's avatar

        Jim Randell 11:40 am on 27 March 2023 Permalink | Reply

        If we accept that the suffix is 2-digits, then the prefix must 5- or 6-digits (neither 1234567 nor 123456789 is prime), so we can just consider 8-digit numbers that have an optional leading zero:

        #! python3 -m enigma -rr

SubstitutedExpression

# prefix is ABCDEF (A may be 0), suffix is GH
--invalid=""

# digits are increasing
"A < B" "B < C" "C < D" "D < E" "E < F" "F < G" "G < H"

# suffix, prefix and entire number are prime
"is_prime(GH)"
"is_prime(ABCDEF)"
"is_prime(ABCDEFGH)"

# output solution
--answer="ABCDEFGH"

        Like

  • Unknown's avatar

    Jim Randell 4:32 pm on 24 March 2023 Permalink | Reply
    Tags:   

    Teaser 3157: End-of-season analysis 

    From The Sunday Times, 26th March 2023 [link] [link]

    In our local football league each team plays each other once every season. The winner of a game is awarded one point, the loser no points and each team half a point if the game is drawn.

    In the end-of-season analysis, it was found that for each team, exactly half of the points that they were awarded had been awarded for their games against the 15 teams with the lowest number of points.

    How many teams were in the league?

    [teaser3157]

     
    • Jim Randell's avatar

      Jim Randell 5:40 pm on 24 March 2023 Permalink | Reply

      Here is a non-constructive analysis, that finds the only viable answer, but doesn’t show that there is an allocation of points that allows the puzzle to work:

      Equivalently we work in “half-points”, with 2 for a win and 1 for a draw.

      If there are (k + 15) teams (i.e. the bottom 15 teams and k top teams), then the table of points is a (k + 15) × (k + 15) matrix, such that:

      pts(i, i) = 0
      pts(i, j) + pts(j, i) = 2, where i ≠ j

      The sum of the entries in each row in the matrix gives the total points for the corresponding team, and last 15 rows represent the matches against the bottom 15 teams, whereas the first k rows represent the matches against the top k teams, so for each row these sections must have the same sum.

      In the 15 × 15 bottom right sub-matrix, we get an upper triangle with T(14) = 105 elements that sum to: B.

      And a lower triangle that sums to: 210 − B.

      Together the total number of points for the sub-matrix is 210. And this is the total number of points gained by the bottom 15 teams in their matches among themselves. And this accounts for half the points gained by the bottom 15 teams, so the total number of points gained by the bottom 15 teams against the top k teams is also 210, and this the total value of the entries in the k × 15 sub-matrix on the bottom left.

      Hence in total the bottom 15 teams scored 420 points. And the lowest number of points that the best of the bottom teams can achieve is 28 points. (If they all have the same number of points. If any of them score less than this the best of the bottom teams must have more points to compensate).

      Now, considering the top right 15 × k sub-matrix, the entries in this must sum to 30k − 210, and this must have the same value as the k × k top left sub-matrix. Which has entries that sum to 2 T(k − 1) = k² − k.

      Hence:

      k² − k = 30k − 210
      k² − 31k + 210 = 0
      (k − 10)(k − 21) = 0

      So: k = 10; or k = 21.

      In the case k = 10, the total number of points shared between the top 10 teams is 180, so the largest amount the team in 10th place can have is 18 points, but this is not enough.

      However if k = 21, the total number of points shared between the top 21 teams is 840, and the largest amount the team in 21st place can have is 40 points, and this is larger than the lowest number of points the best of the bottom teams can achieve.

      So this case gives the only viable answer to the puzzle. And I wrote a MiniZinc model to verify that a viable table can be constructed.

      Solution: There were 36 teams in the league.

      Here is one possible allocation of half-points:

       1: [0 0 0 0 2 2 2 2 2 0 0 2 0 2 2 2 2 2 2 2 2   0 2 2 2 2 2 2 2 2 2 2 2 2 2 2] → 56
 2: [2 0 0 2 0 2 0 0 2 2 1 0 2 0 0 2 2 2 2 2 2   2 1 0 2 2 2 2 2 0 2 2 2 2 2 2] → 50
 3: [2 2 0 0 0 0 2 0 1 2 1 2 0 0 1 2 2 2 2 2 2   2 2 0 0 2 2 2 2 2 2 1 2 2 2 2] → 50
 4: [2 0 2 0 0 0 0 0 0 0 0 2 2 2 2 0 1 0 2 2 2   0 2 2 2 0 0 2 0 2 1 2 0 2 2 2] → 38
 5: [0 2 2 2 0 0 2 0 2 2 0 0 0 2 0 0 0 0 2 2 1   2 0 0 0 0 2 2 2 1 2 2 2 2 2 0] → 38
 6: [0 0 2 2 2 0 0 0 0 0 1 0 1 0 0 2 2 2 1 2 2   2 2 2 1 0 0 2 2 0 0 2 2 2 0 2] → 38
 7: [0 2 0 2 0 2 0 0 0 0 0 2 2 1 0 0 0 2 2 2 2   2 2 2 0 2 1 0 2 2 2 1 1 0 2 0] → 38
 8: [0 2 2 2 2 2 2 0 0 0 0 0 0 0 2 1 0 2 0 2 0   2 2 2 0 2 2 0 2 2 1 2 0 0 0 2] → 38
 9: [0 0 1 2 0 2 2 2 0 0 0 0 0 0 2 0 2 0 2 2 2   2 0 0 2 2 0 2 1 0 2 2 2 0 2 2] → 38
10: [2 0 0 2 0 2 2 2 2 0 0 0 0 0 2 0 0 0 2 1 2   2 2 2 2 2 2 0 2 1 2 0 2 0 0 0] → 38
11: [2 1 1 2 2 1 2 2 2 2 0 0 0 0 0 0 0 2 0 0 0   0 0 2 2 1 0 2 2 2 0 0 2 2 2 2] → 38
12: [0 2 0 0 2 2 0 2 2 2 2 0 0 0 1 2 0 0 0 0 2   2 0 2 2 0 2 2 0 0 0 1 2 2 2 2] → 38
13: [2 0 2 0 2 1 0 2 2 2 2 2 0 0 0 0 0 0 0 0 2   2 2 0 0 2 2 2 2 0 2 1 0 2 0 2] → 38
14: [0 2 2 0 0 2 1 2 2 2 2 2 2 0 0 0 0 0 0 0 0   0 0 2 2 2 2 0 1 2 0 0 2 2 2 2] → 38
15: [0 2 1 0 2 2 2 0 0 0 2 1 2 2 0 0 2 1 0 0 0   2 2 1 2 0 0 2 0 0 2 2 0 2 2 2] → 38
16: [0 0 0 2 2 0 2 1 2 2 2 0 2 2 2 0 0 0 0 0 0   2 1 2 2 0 0 1 0 2 2 2 0 1 2 2] → 38
17: [0 0 0 1 2 0 2 2 0 2 2 2 2 2 0 2 0 0 0 0 0   2 2 0 1 2 2 0 0 2 2 2 0 0 2 2] → 38
18: [0 0 0 2 2 0 0 0 2 2 0 2 2 2 1 2 2 0 0 0 0   0 1 2 2 2 0 0 1 1 0 2 2 2 2 2] → 38
19: [0 0 0 0 0 1 0 2 0 0 2 2 2 2 2 2 2 2 0 0 0   0 0 2 2 0 2 0 2 2 1 0 2 2 2 2] → 38
20: [0 0 0 0 0 0 0 0 0 1 2 2 2 2 2 2 2 2 2 0 0   0 1 0 0 2 2 2 2 2 0 0 2 2 2 2] → 38
21: [0 0 0 0 1 0 0 2 0 0 2 0 0 2 2 2 2 2 2 2 0   0 2 2 1 2 2 2 0 2 2 2 2 0 0 0] → 38

22: [2 0 0 2 0 0 0 0 0 0 2 0 0 2 0 0 0 2 2 2 2   0 0 2 2 0 1 0 0 0 1 2 2 2 2 2] → 32
23: [0 1 0 0 2 0 0 0 2 0 2 2 0 2 0 1 0 1 2 1 0   2 0 0 0 2 2 0 0 2 0 2 2 2 0 2] → 32
24: [0 2 2 0 2 0 0 0 2 0 0 0 2 0 1 0 2 0 0 2 0   0 2 0 1 0 0 0 2 0 0 2 2 2 2 2] → 30
25: [0 0 2 0 2 1 2 2 0 0 0 0 2 0 0 0 1 0 0 2 1   0 2 1 0 0 0 0 0 0 2 2 2 2 2 2] → 30
26: [0 0 0 2 2 2 0 0 0 0 1 2 0 0 2 2 0 0 2 0 0   2 0 2 2 0 0 0 0 1 0 0 2 2 2 2] → 30
27: [0 0 0 2 0 2 1 0 2 0 2 0 0 0 2 2 0 2 0 0 0   1 0 2 2 2 0 0 0 2 0 0 2 0 2 2] → 30
28: [0 0 0 0 0 0 2 2 0 2 0 0 0 2 0 1 2 2 2 0 0   2 2 2 2 2 2 0 0 0 2 0 1 0 0 0] → 30
29: [0 0 0 2 0 0 0 0 1 0 0 2 0 1 2 2 2 1 0 0 2   2 2 0 2 2 2 2 0 0 0 0 0 1 2 0] → 30
30: [0 2 0 0 1 2 0 0 2 1 0 2 2 0 2 0 0 1 0 0 0   2 0 2 2 1 0 2 2 0 0 0 0 2 0 2] → 30
31: [0 0 0 1 0 2 0 1 0 0 2 2 0 2 0 0 0 2 1 2 0   1 2 2 0 2 2 0 2 2 0 0 0 0 0 2] → 30
32: [0 0 1 0 0 0 1 0 0 2 2 1 1 2 0 0 0 0 2 2 0   0 0 0 0 2 2 2 2 2 2 0 0 0 2 0] → 28
33: [0 0 0 2 0 0 1 2 0 0 0 0 2 0 2 2 2 0 0 0 0   0 0 0 0 0 0 1 2 2 2 2 0 0 2 2] → 26
34: [0 0 0 0 0 0 2 2 2 2 0 0 0 0 0 1 2 0 0 0 2   0 0 0 0 0 2 2 1 0 2 2 2 0 0 2] → 26
35: [0 0 0 0 0 2 0 2 0 2 0 0 2 0 0 0 0 0 0 0 2   0 2 0 0 0 0 2 0 2 2 0 0 2 0 0] → 20
36: [0 0 0 0 2 0 2 0 0 2 0 0 0 0 0 0 0 0 0 0 2   0 0 0 0 0 0 2 2 0 0 2 0 0 2 0] → 16

      In general if there are n bottom teams we are looking for integer roots of:

      k² − (2n + 1)k + n(n − 1) = 0, where k ≥ n

      Which gives solutions:

      n = i (i + 1) / 2 = tri(i) [number of bottom teams]
      k = (i + 1) (i + 2) / 2 = tri(i + 1) [number of top teams]
      t = (i + 1)² [total number of teams in the league]
      for positive integers i

      And the answer to this puzzle is found when i = 5.

      Like

  • Unknown's avatar

    Jim Randell 10:34 am on 23 March 2023 Permalink | Reply
    Tags:   

    Teaser 2710: Sterling achievement 

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

    Some people were asked to donate one pound each to charity. They all used only “silver” coins (5p, 10p, 20p, 50p) to make up their pound and no two of them used the same combination. I also donated a pound using silver coins, but it was inevitable that my combination of coins would be a repeat of one already used. When all the coins were sorted into the different denominations we found that we had a whole number of pounds in each denomination.

    Which coins did I use to make my pound?

    [teaser2710]

     
    • Jim Randell's avatar

      Jim Randell 10:34 am on 23 March 2023 Permalink | Reply

      There are a couple of routines in enigma.py to calculate ways of expressing amounts using specified denominations (e.g. coins or stamps). In this case using the more sophisticated [[ Denominations() ]] algorithm gives a (slightly) faster solution than the simple [[ express() ]] function.

      This Python program runs in 51ms. (Internal runtime is 261µs).

      from enigma import (Denominations, ceil, ediv, printf)

# express 100 using denominations of 5, 10, 20, 50
ds = (5, 10, 20, 50)
qss = Denominations(ds).express(100)  # or: express(100, ds)

# sum the quantities
tqs = list(sum(qs) for qs in zip(*qss))

# determine extra coins required to make the total of each
# denomination a whole number of pounds
for (d, q) in zip(ds, tqs):
  t = d * q
  x = ceil(t, 100) - t
  n = ediv(x, d)
  printf("{n} x {d}p = {x}p [{q} x {d}p coins = {t}p]")

      Solution: 6× 5p; 3× 10p; 2× 20p.

      There are 49 different ways to make 100p using 5p, 10p, 20p, 50p.

      And if we sum them all we get:

      294× 5p = 1470p
      147× 10p = 1470p
      63× 20p = 1260p
      14× 50p = 700p

      The setters donation makes the total of the 5p and 10p coins up £15, and the 20p coins up to £13, and the 50p coins were already at £7. Making a grand total of £50.

      Like

  • Unknown's avatar

    Jim Randell 9:29 am on 21 March 2023 Permalink | Reply
    Tags:   

    Teaser 2701: Flipping ages! 

    From The Sunday Times, 29th June 2014 [link] [link]

    At a recent family party the ages of the ten people present formed an arithmetic progression (i.e. the difference between each person’s age in years and the age of the next oldest person was always the same). My age was like my wife’s but with the digits in reverse order. Likewise, my sister’s age was the reverse of my mother’s, my son’s age was the reverse of my grandson’s, and my daughter’s age was the reverse of my granddaughter’s. Furthermore, the product of my brother’s age and the age of his son equalled the year of birth of one of the people at the party.

    What were the ages of my brother, my sister and myself (in that order)?

    [teaser2701]

     
    • Jim Randell's avatar

      Jim Randell 9:30 am on 21 March 2023 Permalink | Reply

      This Python program chooses the 4 pairs of ages that are the mutually reversed, and then extends this set of 8 numbers to 10 numbers in arithmetic progression (if possible). It then allocates the given relationships between the numbers (it looks for viable parent/child ages where the parent is between 16 and 50 years older than the child).

      Runtime is 282ms.

      from enigma import (irange, subsets, union, tuples, mgcd, call, divisor, div, decompose, diff, printf)

# collect pairs that are the reverse of each other
pairs = set((10 * a + b, 10 * b + a) for (a, b) in subsets(irange(1, 9), size=2))

# generate arithmetic progressions based on the given numbers
def generate(ns):
  ns = sorted(ns)
  (a, z) = (ns[0], ns[-1])
  # find potential common differences
  for d in divisor(call(mgcd, (y - x for (x, y) in tuples(ns, 2)))):
    # calculate number of terms
    k = div(z - a, d)
    if k is None or k > 9: continue
    k += 1
    # pad the sequence to bring it to 10 terms
    for (pa, pz) in decompose(10 - k, 2, increasing=0, sep=0, min_v=0):
      # construct the new sequence
      ns = list(irange(a - pa * d, z + pz * d, step=d))
      yield ns

# check for viable parent, child age
check = lambda parent, child: 15 < parent - child < 51

# choose 4 pairs
for ps in subsets(pairs, size=4):
  ss = union(ps)
  for ns in generate(ss):
    # the additional ages are brother and nephew
    (nep, bro) = diff(ns, ss)
    if not check(bro, nep): continue
    # and their product is the birth year of one of the party
    year = bro * nep
    x = 2014 - year
    if not { x, x - 1 }.intersection(ns): continue

    # choose the pairs
    for ((sis, mum), (gson, son), (gdtr, dtr), other) in subsets(ps, size=4, select="P"):
      # check parent/child relationships
      if not (check(mum, sis) and check(mum, bro)): continue
      if not (check(son, gson) or check(dtr, gson)): continue
      if not (check(son, gdtr) or check(dtr, gdtr)): continue
      # the remaining pair is (me, wife) (in some order)
      for (me, wife) in subsets(other, size=2, select="P"):
        # check parent/child relationships
        if not (check(mum, me) and check(me, son) and check(me, dtr)): continue
        if not (check(wife, son) and check(wife, dtr)): continue
        # output solution
        printf("{ns}")
        printf("-> me={me} wife={wife}")
        printf("-> sis={sis} mum={mum}")
        printf("-> son={son} gson={gson}")
        printf("-> dtr={dtr} gdtr={gdtr}")
        printf("-> bro={bro} nep={nep}; year={year}")
        printf()

      Solution: Brother = 60. Sister = 69. Self = 78.

      The arithmetic progression is (15, 24, 33, 42, 51, 60, 69, 78, 87, 96).

      And the pairs are:

      me = 78; wife = 87
      sister = 69; mother = 96
      child = 51; grandchild = 15
      child = 42; grandchild = 24
      brother = 60; nephew = 33

      And the product of the ages of the brother and nephew give 1980. And if the 33 year-old nephew has not yet celebrated his birthday in 2014, his year of birth is 1980.

      But we can’t tell how the child/grandchild pairs correspond to the son/grandson and daughter/granddaughter pairs.

      Like

  • Unknown's avatar

    Jim Randell 7:46 am on 19 March 2023 Permalink | Reply
    Tags:   

    Brainteaser 1057: Palindromic primes 

    From The Sunday Times, 31st October 1982 [link]

    Teacher was introducing his class to the binary system of notation (wherein the unit values attaching to successive digits from right to left of any integer are 1, 2, 4, 8, 16, etc., as against 1, 10, 100, 1000, etc., in the decimal system).

    He went on to explain that many arithmetical relationships are equally valid in both the binary and decimal systems. And gave as the simplest example:

    10 × 11 = 110

    which in the binary system represents 2 × 3 = 6, pointing out this difference however – that while both factors 10 and 11 are primes in the binary system, only 11 is prime in the decimal system.

    Developing this theme he observed that very often such relationships could be described as “pan-palindromic”, in the sense that both of the factors, as well as their product, are numerical palindromes (i.e. each of the three integers reads the same forwards as backwards). His first example was:

    1001 × 10101 = 10111101

    (which in the binary system represents 9 × 21 = 189), and he pointed out how this time neither factor was a prime using either the binary or decimal system (being patently divisible by 11 and 3 respectively).

    He contrasted this with another example:

    111 × 1001001 = 111111111

    which in the binary system represents: 7 × 73 = 511, where both factors are primes in the binary system, but neither of them are in the decimal system (both being divisible by 3).

    To test how well his pupils were taking in all this, he told them to proceed on their own and write down any binary palindromes they could find, of less than twelve digits, which simultaneously, in both binary and decimal systems, factorised into just two different palindromic primes.

    What should they have written down?

    [teaser1057]

     
    • Jim Randell's avatar

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

      This Python program considers numbers that are binary palindromes (with < 12 digits), and that have exactly 2 different prime factors, which are themselves binary palindromes. It then checks that if the multiplication sum is interpreted in decimal, instead of binary, that it still works, and the decimal factors are also prime.

      Total runtime is 64ms. (Internal runtime is 713µs).

      from enigma import (irange, inf, nsplit, rev, nconcat, factor, is_npalindrome, is_prime, printf)

# generate numbers that are binary palindromes < 12 digits
def generate():
  for n in irange(1, inf):
    # split n into digits
    ds = nsplit(n, base=2, fn=list)
    k = len(ds)
    if k > 6: break
    # mirror the digits to make a palindrome
    ds.extend(rev(ds))
    if k < 6: yield nconcat(ds, base=2)
    ds.pop(k)
    yield nconcat(ds, base=2)

# start with a number that is a binary palindrome
for n in generate():
  # find the prime factorisation
  fs = factor(n)
  if not (len(fs) == 2 and len(set(fs)) == 2): continue
  (a, b) = fs
  # check the factors are themselves binary palindromes
  if not (is_npalindrome(a, base=2) and is_npalindrome(b, base=2)): continue
  # check the multiplication works if the binary factorisation is interpreted as decimal
  (nx, ax, bx) = (nconcat(nsplit(x, base=2), base=10) for x in (n, a, b))
  if not (ax * bx == nx): continue
  # check the factors are prime if interpreted as decimal
  if not (is_prime(ax) and is_prime(bx)): continue
  # output solution
  printf("{a:b} * {b:b} = {n:b} [base 2] -> {a} * {b} = {n} [base 10]")

      Solution: The sum is: 11 × 101 = 1111.

      In decimal both 11 and 101 are prime.

      In binary this corresponds to: 3 × 5 = 15, and both 3 and 5 are prime.

      Like

  • Unknown's avatar

    Jim Randell 4:30 pm on 17 March 2023 Permalink | Reply
    Tags:   

    Teaser 3156: Balancing act 

    From The Sunday Times, 19th March 2023 [link] [link]

    A circus elephant standing on one end of a see-saw pivoted at the centre was balanced by a troupe of fewer than 20 acrobats, each of equal weight, standing on the other end. The elephant moved forwards and several acrobats jumped off to maintain balance. The elephant moved backwards and some of them climbed back on to the end to rebalance.

    The elephant always moved a prime number of feet and there was always a prime number of acrobats on the see-saw. If I told you how far backwards the elephant moved you could work out the numbers of acrobats.

    (In equilibrium, the product of weight and distance from pivot point must be the same on both sides).

    How far did the elephant move backwards, and how many acrobats are there in the troupe?

    [teaser3156]

     
    • Jim Randell's avatar

      Jim Randell 5:24 pm on 17 March 2023 Permalink | Reply

      I think it is necessary to assume that the elephant did not return to its original position. (i.e. “some of them” is interpreted as “some (but not all) of them”).

      So we suppose that we start off with a see-saw of length 2d and a unit weight acrobats on one end (a is a prime number, less than 20). They are balanced by an elephant of weight a on the other end.

      The elephant then moves forwards (towards the pivot) p feet (p is a prime number), and some of the acrobats jump off, leaving b acrobats balancing the elephant (b is a prime number, less than a):

      a . (d − p) = b . d

      The elephant then moves backwards (away from the pivot) q feet (q is a prime number, less than p), and some of the acrobats remount to make c acrobats balancing the elephant (c is a prime number, between b and a):

      a . (d − p + q) = c . d

      From these two equations we can determine p in terms of q and a, b, c:

      p . (c − b) = q . (a − b)

      There are only a certain number (a, b, c) values, so we can look at possible values for q, and see if there is only a single set of (a, b, c) values that give a viable value of p.

      This Python program runs in 62ms. (Internal runtime is 285µs).

      from enigma import (primes, subsets, div, inf, fdiv, printf)

# collect possible (a, b, c) numbers of acrobats
abcs = list((a, b, c) for (b, c, a) in subsets(primes.between(2, 20), size=3))

# consider the distance the elephant moves back = q
for q in primes.irange(2, inf):
  # find viable p values
  ps = list()
  for (a, b, c) in abcs:
    p = div(q * (a - b), c - b)
    if p and p > q and p in primes:
      ps.append((a, b, c, p))
  if len(ps) == 1:
    (a, b, c, p) = ps[0]
    printf("q={q} -> a={a} b={b} c={c} p={p}; d={d:g}", d=fdiv(a * q, c - b))
    break

      Solution: The elephant moved backwards 11 ft. There are 19 acrobats in the troupe.

      The see-saw is 19 feet either side of the pivot (i.e. end to end length is 38 feet).

      And initially there are 19 acrobats on one end, balanced by an elephant that weighs the same as 19 acrobats on the other end.

      The elephant moves forward by 17 ft, so it is 2 ft from the pivot, and this is balanced by 2 acrobats 19 ft from the pivot (19 × 2 = 2 × 19).

      The elephant then moves backwards by 11 ft, so it is 13 ft from the pivot. And this is balanced by 13 acrobats 19 ft from the pivot (19 × 13 = 13 × 19).

      There are 16 candidate solutions.

      q=2 ⇒ 6 candidates
      q=3 ⇒ 6 candidates
      q=5 ⇒ 3 candidates
      q=11 ⇒ 1 candidate

      So the answer is found from q = 11.

      Like

      • Jim Randell's avatar

        Jim Randell 11:53 am on 18 March 2023 Permalink | Reply

        Even shorter (and exhaustive):

        q / p = (c − b) / (a − b)

        and both p and q are primes, so can be determined from their ratio.

        from enigma import (primes, subsets, fraction, filter_unique, item, fdiv, printf)

# generate candidates (p, q, a, b, c)
def candidates():
  for (b, c, a) in subsets(primes.between(2, 20), size=3):
    (q, p) = fraction(c - b, a - b)
    if primes.is_prime(q) and primes.is_prime(p):
      yield (p, q, a, b, c)

# find solutions unique by q (= item 1)
for (p, q, a, b, c) in filter_unique(candidates(), item(1)).unique:
    printf("q={q} -> a={a} b={b} c={c} p={p}; d={d:g}", d=fdiv(a * q, c - b))

        Like

    • Jim Randell's avatar

      Jim Randell 8:27 am on 18 March 2023 Permalink | Reply

      @GeoffR: I think 5 is also a prime.

      And there are additional candidate solutions where the length of the see-saw is not an even integer number of feet. But the length of the see-saw can be eliminated from the equations to keep the remaining variables integers. (Although it would be possible to also specify the see-saw length as an integer number of inches).

      Like

    • GeoffR's avatar

      GeoffR 10:00 am on 18 March 2023 Permalink | Reply 

      
from itertools import permutations
from enigma import is_prime

from collections import defaultdict
nums = defaultdict(list)

primes = (2, 3, 5, 7, 11, 13, 17, 19)

for acrobats in permutations(primes, 3):
  # A1 = full acrobat troupe
  # A2 = acrobats after elephant moves forward
  # A3 = acrobats after elephant then moves backwards
  A1, A2, A3 = acrobats
  if A1 > A2 and A1 > A3 and A2 < A3:
    # for intial balancing of elephant v. troupe
    # elephants weight = weight of acrobat troupe
    E = A1
    # assume max. half seesaw length = 25 ft.
    for dist in permutations(range(1, 26), 3):
      half_see_saw, p1, p2 = dist
      if p2 < p1 and is_prime(p1) and is_prime(p2):
        # Taking moments about centre pivot
        if (half_see_saw - p1) * E == half_see_saw * A2:
          if (half_see_saw - p1 + p2) * E ==  half_see_saw * A3:
            # index dictionary on distance elephant moved backwards
            nums[p2] += [(p1, p2, A1, A2, A3)]

# find a single solution
for k,v in nums.items():
    if len(v) == 1:
      print(f"Distance elephant moves backward = {k} ft.")
      print(f"Number of acrobats in troupe = {v[0][2]}.")

      Like

  • Unknown's avatar

    Jim Randell 8:43 am on 16 March 2023 Permalink | Reply
    Tags:   

    Teaser 2711: Megan’s house 

    From The Sunday Times, 7th September 2014 [link] [link]

    Megan’s class has been learning about primes and squares. So their teacher challenged each of them to use some of the digits 1 to 9 to write down three two-figure squares and a two-figure prime without using any digit more than once. They all succeeded in doing this and in Megan’s case the left-over digit was her house number. If you knew her house number it would be possible to work out the four two-figure numbers that she wrote down.

    What were they?

    [teaser2711]

     
    • Jim Randell's avatar

      Jim Randell 8:43 am on 16 March 2023 Permalink | Reply

      We can use the [[ SubstitutedExpression() ]] solver from the enigma.py library to find viable allocations of the 9 digits to three 2-digit squares, a 2-digit prime, and the remaining digit. We can then use the [[ filter_unique() ]] function to select those allocations that are unique by the remaining digit.

      This Python program runs in 57ms. (Internal runtime is 4.4ms).

      from enigma import (SubstitutedExpression, irange, filter_unique, item, printf)

# squares: AB, CD, EF; prime: GH
p = SubstitutedExpression(
  [
    "is_square(AB)", "is_square(CD)", "is_square(EF)", "A < C < E",
    "is_prime(GH)",
  ],
  digits=irange(1, 9),
  answer="(X, AB, CD, EF, GH)"
)

# if we knew X, we could deduce the 2-digit numbers
rs = filter_unique(p.answers(verbose=0), item(0)).unique

# output solution
for (X, sq1, sq2, sq3, pr) in rs:
  printf("X={X} -> squares = ({sq1}, {sq2}, {sq3}), prime = {pr}")

      Solution: The four 2-digit numbers were: 16, 25, 49 (squares), and 83 (prime).

      So Megan’s house number is 7.

      Like

    • GeoffR's avatar

      GeoffR 11:56 am on 16 March 2023 Permalink | Reply 

      from enigma import is_square, is_prime
from itertools import permutations
from collections import defaultdict
nums = defaultdict(list)

for p1 in permutations('123456789'):
    a, b, c, d, e, f, g, h, i = p1
    ab, cd, ef = int(a + b), int(c + d), int(e + f)
    if ab < cd < ef :
        if is_square(ab) and is_square(cd) and is_square(ef):
            gh = int(g + h)
            if is_prime(gh):
                nums[i] += [(ab, cd, ef, gh)]
            
for k, v in nums.items():
    if len(v) == 1:
        print(f"Megan's house number was {k}.")
        print(f"Her four 2-digit numbers were {v}.")
        
# Megan's house number was 7.
# Her four 2-digit numbers were [(16, 25, 49, 83)].

      Like

    • GeoffR's avatar

      GeoffR 11:41 am on 17 March 2023 Permalink | Reply

      The basis of this teaser can be seen by printing the python dictionary in this solution, with the house number as the key. All house numbers, except 7, have multiple solutions for the four 2-digit numbers.

      8 [(16, 25, 49, 37), (16, 25, 49, 73), (25, 36, 49, 17), (25, 36, 49, 71)]
      7 [(16, 25, 49, 83)]
      9 [(25, 36, 81, 47), (25, 64, 81, 37), (25, 64, 81, 73)]
      4 [(25, 36, 81, 79), (25, 36, 81, 97)]
      6 [(25, 49, 81, 37), (25, 49, 81, 73)]
      3 [(25, 49, 81, 67), (25, 64, 81, 79), (25, 64, 81, 97)]

      Like

  • Unknown's avatar

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

    Teaser 2713: Very similar triangles 

    From The Sunday Times, 21st September 2014 [link] [link]

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

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

    [teaser2713]

     
    • Jim Randell's avatar

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

      (See also: Enigma 1198).

      For a triangle with sides (a, b, c) (in order), we must have: a + b > c.

      The triangle is then scaled up to give another similar triangle (f.a, f.b, f.c) (f > 1).

      And two of the sides are the same, which must be: f.a = b, f.b = c.

      Hence:

      f = b/a = c/b
      a.c = b²

      So we can choose a value for b, and then look for a, c sides that multiply to give b².

      This Python program runs in 52ms. (Internal runtime is 288µs).

      from enigma import (irange, hypot, intf, divisors_pairs, div, sqrt, printf)

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

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

# choose a value for b
for b in irange(1, intf(hypot(X, Y))):
  # calculate possible a, c values from divisors of b^2
  for (a, c) in divisors_pairs(b, 2):
    if not (a < b < c and a + b > c): continue
    # calculate d
    d = div(b * c, a)
    if d is None: continue
    if area(a, b, c) + area(b, c, d) > A4: continue
    # output solution
    printf("({a}, {b}, {c}) -> ({b}, {c}, {d})")

      Solution: The smaller triangle has sides of length 8, 12, 18 cm.

      And the larger triangle has sides of length 12, 18, 27 cm.

      The dimensions of the second triangle are 1.5 times those of the first.

      Here is a diagram of the two triangles, set on a sheet of A4 paper:

      Like

  • Unknown's avatar

    Jim Randell 11:51 am on 11 March 2023 Permalink | Reply
    Tags:   

    Teaser 3155: Increasing temperature 

    From The Sunday Times, 12th March 2023 [link] [link]

    I have written down an above-freezing temperature, a whole number of degrees Celsius, in which the digits are all different and are in decreasing order. I have then calculated the Fahrenheit equivalent. It is also a whole number whose digits are all different, but here the digits are in increasing order.

    If I told you the first digit of the Celsius temperature, then you would not be able to calculate the temperature. However, bearing that in mind, if I now told you the final digit of the Celsius temperature, then it would be possible to calculate it.

    You should now be able to work out the Celsius and Fahrenheit temperatures.

    What are they?

    [teaser3155]

     
    • Jim Randell's avatar

      Jim Randell 12:02 pm on 11 March 2023 Permalink | Reply

      This Python program runs in 56ms. (Internal runtime is 3.4ms).

      from enigma import (
  irange, subsets, nconcat, div, nsplit, tuples,
  filter_unique, join, printf
)

# generate temperatures (C, F) with C digits in decreasing order,
# F digits in decreasing order, return the digits of (C, F)
def generate():
  # make the C temperature
  for cs in subsets(irange(9, 0, step=-1), min_size=1, select='C'):
    C = nconcat(cs)
    if C == 0: continue
    # convert to Fahrenheit
    F = div(9 * C + 160, 5)
    if F is None: continue
    # check digits are in increasing order
    fs = nsplit(F)
    if not all(a < b for (a, b) in tuples(fs, 2)): continue
    # return (C, F) temperatures
    printf("[C={C} F={F}]")
    yield (cs, fs)

# collect possible temperatures
ss = list(generate())

# selection function for the i'th digit of (C, F)
digit = lambda i, k: (lambda x: x[i][k])

# we cannot work out the temperature knowing the first digit of C
ss = filter_unique(ss, digit(0, 0)).non_unique

# but now we can work it out knowing the last digit of C
ss = filter_unique(ss, digit(0, -1)).unique

# output solution
for (C, F) in ss:
  printf("answer: C={C} F={F}", C=join(C), F=join(F))

      Solution: The temperatures are: 75 C and 167 F.

      In total there are 7 possible temperatures:

      20 C = 68 F
      65 C = 149 F
      70 C = 158 F
      75 C = 167 F
      730 C = 1346 F
      865 C = 1589 F
      7520 C = 13568 F

      (As F = (9/5)C + 32, only C temperatures that are divisible by 5 can have a corresponding F temperature that is an integer, so the last digit of a C temperature will always be 0 or 5).

      The only temperatures that cannot be determined from the first digit are those beginning with 7, i.e.: 70, 75, 730, 7520.

      And of these there is only one that ends in 5, i.e.: 75, and so this gives us the required answer.

      Like

  • Unknown's avatar

    Jim Randell 10:57 am on 9 March 2023 Permalink | Reply
    Tags:   

    Teaser 2712: New tricks 

    From The Sunday Times, 14th September 2014 [link] [link]

    I am currently experiencing the joy of seeing Liam, my first grandchild, developing lots of new tricks. With this in mind I have written down four odd numbers and then consistently replaced different digits by different letters to give:

    SIT
    CRAWL
    WALK
    TALK

    In fact the largest of these numbers is the sum of the other three.

    Find the numerical value of TRICK.

    [teaser2712]

     
    • Jim Randell's avatar

      Jim Randell 10:57 am on 9 March 2023 Permalink | Reply

      We can use the [[ SubstitutedExpression ]] solver from the enigma.py library to solve this puzzle. And as it is a simple addition sum we can use the [[ split_sum() ]] helper function for a faster run time.

      The following run file executes in 64ms. (Internal runtime of the generated program is 117µs).

      #! python3 -m enigma -rr

SubstitutedExpression.split_sum

"SIT + WALK + TALK = CRAWL"

# T, K, L are odd
--invalid="0,CKLSTW"
--invalid="2|4|6|8,KLT"

--answer="TRICK"

      Solution: TRICK = 50619.

      There are two possibilities for the original sum (but both give the same value for TRICK):

      SIT + WALK + TALK = CRAWL
      265 + 4739 + 5739 = 10743
      765 + 4239 + 5239 = 10243

      The values of A and S are 2 and 7 (in some order).

      Like

    • GeoffR's avatar

      GeoffR 1:05 pm on 9 March 2023 Permalink | Reply 

      
from itertools import permutations

# Find numbers WALK and TALK 
for p1 in permutations('1234567890', 5):
    W, A, L, K, T = p1
    if '0' in (W, T, K):continue
    if int(K) % 2 == 0 or int(T) % 2 == 0: continue
    WALK, TALK = int(W + A + L + K), int(T + A + L + K)
    q1 = set('1234567890').difference(p1)
    
    # Find numbers SIT, CRAWL and TRICK
    for p2 in permutations(q1, 4):
        S, I, C, R = p2
        if '0' in (C, S):continue
        if int(L) % 2 == 0:continue
        SIT = int(S + I + T)
        CRAWL = int(C + R + A + W + L)
        if SIT + WALK + TALK == CRAWL:
            TRICK = int(T + R + I + C + K)
            print(f"TRICK = {TRICK}")
            print(f"{SIT} + {WALK} + {TALK} = {CRAWL}")

# TRICK = 50619
# 765 + 4239 + 5239 = 10243
# 265 + 4739 + 5739 = 10743

      Like

    • GeoffR's avatar

      GeoffR 10:08 am on 10 March 2023 Permalink | Reply 

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

var 1..9:S; var 0..9:I; var 1..9:T; var 1..9:W; var 0..9:A; 
var 1..9:L; var 1..9:K; var 1..9:C; var 0..9:R;

constraint all_different ([S, I, T, W, A, L, K, C, R]);
constraint T mod 2 == 1 /\ L mod 2 == 1 /\ K mod 2 == 1;

var 100..999: SIT = 100*S + 10*I + T;
var 1000..9999:WALK = 1000*W + 100*A + 10*L + K;
var 1000..9999:TALK = 1000*T + 100*A + 10*L + K;
var 10000..99999:CRAWL = 10000*C + 1000*R + 100*A + 10*W + L;
var 10000..99999:TRICK = 10000*T + 1000*R + 100*I + 10*C + K;

constraint SIT + WALK + TALK == CRAWL;

solve satisfy;
output ["TRICK = " ++ show(TRICK) ];

% TRICK = 50619
% ----------
% ==========

      Like

← Older posts

Newer posts →

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