Recent Updates Page 53 Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 12:59 pm on 21 May 2020 Permalink | Reply
    Tags:   

    Teaser 2864: Sequence of squares 

    From The Sunday Times, 13th August 2017 [link] [link]

    I started with a rectangle of paper. With one straight cut I divided it into a square and a rectangle. I put the square to one side and started again with the remaining rectangle. With one straight cut I divided it into a square and a rectangle. I put the square (which was smaller than the previous one) to one side and started again with the remaining rectangle. I kept repeating this process (discarding a smaller square each time) until eventually the remaining rectangle was itself a square and it had sides of length one centimetre. So overall I had divided the original piece of paper into squares. The average area of the squares was a two-figure number of square centimetres.

    What were the dimensions of the original rectangle?

    [teaser2864]

     
    • Jim Randell's avatar

      Jim Randell 1:00 pm on 21 May 2020 Permalink | Reply

      If we start with the 1×1 cm square and replace the removed squares, we find the sequence of sizes of squares is:

      1, 1, 2, 3, 5, 8, 13, 21, …

      i.e. a Fibonacci sequence. [ @Wikipedia ]

      So we can start with the two 1×1 cm squares and build up the original rectangle square by square, until find one where the mean area of the squares is a two digit integer as required.

      This Python program runs in 82ms.

      Run: [ @repl.it ]

      from enigma import printf

# initial a x b rectangle, n = number of squares, A = total Area
(a, b, n, A) = (1, 1, 2, 2)
while True:
  # calculate the mean area of the squares
  (m, r) = divmod(A, n)
  if m > 99: break
  # construct the rectangle
  (a, b) = (b, a + b)
  if r == 0 and m > 9:
    # output solution, when m is a 2 digit integer
    printf("[n={n}] rectangle = {a} x {b}, mean area = {m}")
  # move on to the next square
  A += b * b
  n += 1

      Solution: The original rectangle was 13 cm × 21 cm.

      So in total 6 cuts were made, producing 7 squares.

      The total area of the 7 squares is 273 sq cm, so the mean area is 39 sq cm.

      Manually:

      If:

      F(n) = nth Fibonacci number
      S(n) = sum of squares of F(n) = F(n) F(n + 1)
      M(n) = mean of squares of F(n) = F(n) F(n + 1) / n

      Then we can calculate:

       n  F(n)  S(n)  M(n)
 1    1     1    1
 2    1     2    1
 3    2     6    2
 4    3    15    3.75  
 5    5    40    8
 6    8   104   17.3...
 7   13   273   39
 8   21   714   89.25
 9   34  1870  207.7...
10   55  ...

      And the answer is apparent.

      If we draw a quarter circle through each square we can make a Fibonacci Spiral:

      Liked by 1 person

  • Unknown's avatar

    Jim Randell 5:13 pm on 15 May 2020 Permalink | Reply
    Tags:   

    Teaser 3008: Three-fruit fractions 

    From The Sunday Times, 17th May 2020 [link] [link]

    The owner of the old curiosity shop repaired an antique mechanical fruit machine having three wheels of identical size and format. Afterwards each wheel was independently fair, just as when new. Each wheel’s rim had several equal-sized zones, each making a two-figure whole number of degrees angle around the rim. Each wheel had just one zone showing a cherry, with other fruits displayed having each a different single-figure number (other than one) of zone repetitions.

    Inside the machine were printed all the fair chances (as fractions) of getting three of the same fruit symbol in one go. Each of these fractions had a top number equal to 1 and, of their bottom numbers, more than one was odd.

    What was the bottom number of the chance for three cherries?

    [teaser3008]

     
    • Jim Randell's avatar

      Jim Randell 7:26 am on 16 May 2020 Permalink | Reply

      I assumed the wheels are identical duplicates of each other, which gives a unique solution.

      This Python 3 program runs in 49ms.

      from enigma import (Rational, irange, divisors_pairs, seq2str, printf)

Q = Rational()

# decompose <t> into numbers between 2 and 9
def decompose(t, m=2, M=9, s=[]):
  if not (t < m or t > M):
    yield s + [t]
  for x in irange(m, min(t - m, M)):
    yield from decompose(t - x, x + 1, M, s + [x])

# each wheel is divided into n equal sized divisions
# each spanning d degrees
for (n, d) in divisors_pairs(360, every=1):
  if d < 10: break
  if d > 99: continue

  # probability of 3 cherries
  p = Q(1, n)**3

  # consider the number of other fruits (all different and between 2 and 9)
  for ns in decompose(n - 1):
    # calculate the probabilities of getting 3 of each of the other fruits
    ps = list(Q(x, n)**3 for x in ns)
    # probabilities are all 1/N
    if not all(x.numerator == 1 for x in ps): continue
    # and more than one N is odd
    if sum(x.denominator % 2 == 1 for x in ps) < 2: continue

    # output solution
    printf("{n} divisions, {d} degrees -> 1 + {ns}; p={p}, ps={ps}", ns=seq2str(ns), ps=seq2str(ps))

      Solution: There is a 1 / 5832 chance of getting 3 cherries.

      Each wheel is divided into 18 sectors. Each sector subtends 20°.

      There are 4 fruits, each is allocated 1, 2, 6, 9 sectors on each wheel.

      The probabilities for each of the 4 fruits are: 1/5832 (= 1/18³), 1/729 (= 1/9³), 1/27 (= 1/3³), 1/8 (= 1/2³).

      Like

  • Unknown's avatar

    Jim Randell 10:42 am on 12 May 2020 Permalink | Reply
    Tags:   

    Teaser 2865: Seventh heaven? 

    From The Sunday Times, 20th August 2017 [link] [link]

    I have a modern painting by the surrealist artist Doolali. It is called “Seventh Heaven” and it consists of a triangle with green sides and a red spot on each of its sides. The red spots are one seventh of the way along each side as you pass clockwise around the triangle. Then each of the red spots is joined by a straight blue line to the opposite corner of the triangle. These three blue lines create a new triangle within the original one and the new triangle has area 100 sq cm.

    What is the area of the green triangle?

    [teaser2865]

     
    • Jim Randell's avatar

      Jim Randell 10:43 am on 12 May 2020 Permalink | Reply

      We have encountered similar problems to this before (see: Enigma 1313, Enigma 320, Enigma 1076).

      The generalisation of this puzzle is known as Routh’s Theorem [ @wikipedia ], which states that the ratio of the area of the central triangle to the original triangle, where the sides are divided in the ratios 1:x, 1:y, 1:z is given by the formula:

      R = (xyz − 1)² / ((xz + x + 1)(xy + y + 1)(yz + z + 1))

      I made a note giving the areas of the various subdivisions here [ rouths-theorem.pdf ].

      For this puzzle we have: x = y = z = 6, which gives the ratio as:

      R = (x − 1)² / (x² + x + 1) = 25/43

      The smaller triangle has an area of 100, so the larger triangle has an area of: 100 × 43/25 = 172.

      Solution: The area of the green triangle is 172 sq cm.

      Or using a program:

      from enigma import (rational, printf)

# ratio ABC/XYZ in Routh's theorem
def routh(x, y, z):
  a = x * y * z - 1
  b = (x * y + y + 1) * (y * z + z + 1) * (z * x + x + 1)
  return rational(a * a, b)

# compute the ratio of the area of the inner and outer triangles
R = routh(6, 6, 6)

# output the solution, given the inner triangle has area 100
printf("outer triangle = {x} [R={R}]", x=100 / R)

      Like

  • Unknown's avatar

    Jim Randell 3:59 pm on 7 May 2020 Permalink | Reply
    Tags:   

    Teaser 3007: Paving stones 

    From The Sunday Times, 10th May 2020 [link] [link]

    James has decided to lay square block paving stones on his rectangular patio. He has calculated that starting from the outside and working towards the middle that he can lay a recurring concentric pattern of four bands of red stones, then three bands of grey stones, followed by a single yellow stone band. By repeating this pattern and working towards the centre he is able to finish in the middle with a single line of yellow stones to complete the patio.

    He requires 402 stones to complete the first outermost band. He also calculates that he will require exactly 5 times the number of red stones as he does yellow stones.

    How many red stones does he require?

    [teaser3007]

     
    • Jim Randell's avatar

      Jim Randell 4:33 pm on 7 May 2020 Permalink | Reply

      Assuming an x by y rectangle, with x > y.

      If there are k repeats of the (red, grey yellow) bands, then y = 16k − 1.

      And the first band of red stones requires 2x + 2y − 4 = 402 stones, so x + y = 203.

      Here is a constructive program that counts the number of stones in each band. It runs in 78ms.

      from enigma import irange, inf, printf

# calculate the number of stones with <k> repeats
# and the initial band being <x> by <y>
def stones(k, y, x):
  d = dict(R=0, G=0, Y=0)
  for i in ("RRRRGGGY" * k):
    if y < 2:
      d[i] += x * y
      break
    d[i] += 2 * (x + y - 2)
    x -= 2
    y -= 2
  return (d['R'], d['G'], d['Y'])

# consider the number of repeats of the bands
for k in irange(1, inf):
  y = 16 * k - 1
  x = 203 - y
  if not(x > y): break
 
  # calculate the number of stones needed
  (R, G, Y) = stones(k, y, x)
 
  # output solution
  if 5 * Y == R:
    printf("k={k}, y={y} x={x}; R={R} G={G} Y={Y}")

      Solution: James requires 5520 red stones.

      The patio consists of 6 red/grey/yellow layers, finishing with a single row of 14 yellow stones:

      The number of stones required is: red = 5520, grey = 3636, yellow = 1104; total = 10260.

      The outer band measures 108×95 stones.

      Like

    • Jim Randell's avatar

      Jim Randell 9:33 am on 10 May 2020 Permalink | Reply

      Each band requires 8 fewer stones than the previous band, so we can just start with the outermost band (402 stones) and work our way in. When we get to the number blocks for the yellow band we can adjust the number to account for a single line to see if we have reached the middle of the design, and if not carry on. We don’t need to do any analysis to work out the dimensions of the patio, or consider the number of repeats.

      This gives us a simpler, and slightly shorter, program.

      Run: [ @repl.it ]

      from enigma import irange, chunk, printf

# number of blocks in outer band
n = 402

# record Red, Grey, Yellow blocks required
R = G = Y = 0

# work inwards in chunks of 8 bands
# each band has 8 less blocks than the previous band
for s in chunk(irange(n, 1, step=-8), 8):
  if len(s) < 8: break
  (r1, r2, r3, r4, g1, g2, g3, y) = s
  R += r1 + r2 + r3 + r4
  G += g1 + g2 + g3
  # the middle is a single row
  m = 1 + y // 2
  if 5 * (Y + m) == R:
    printf("R={R} G={G} Y={Y}", Y=Y + m)
  # otherwise, carry on
  Y += y

      Like

  • Unknown's avatar

    Jim Randell 10:54 am on 7 May 2020 Permalink | Reply
    Tags: ,   

    Teaser 2869: Cubic savings 

    From The Sunday Times, 17th September 2017 [link] [link]

    In 2009 George and Martha had a four-figure number of pounds in a special savings account (interest being paid into a separate current account). At the end of the year they decided to give some of it away, the gift being shared equally among their seven grandchildren, with each grandchild getting a whole number of pounds. At the end of the following year they did a similar thing with a different-sized gift, but again each grandchild received an equal whole number of pounds. They have repeated this procedure at the end of every year since.

    The surprising thing is that, at all times, the number of pounds in the savings account has been a perfect cube.

    What is the largest single gift received by any grandchild?

    [teaser2869]

     
    • Jim Randell's avatar

      Jim Randell 10:54 am on 7 May 2020 Permalink | Reply

      This puzzle is marked as flawed, as there are two possible solutions.

      I assumed the number of grandchildren remained constant (at 7) during the eight years in question (2009 – 2016).

      The amounts in the savings account are perfect cubes, that differ by multiples of 7, so we can collect cubes by their residue modulo 7, and consider the sets for each residue to look for 9 amounts that satisfy the remaining conditions.

      This Python program runs in 76ms.

      Run: [ @replit ]

      from enigma import (group, powers, mod, subsets, tuples, printf)

# group the cubes (up to 4 digits) in descending order, by their residue mod 7
cubes = group(powers(21, 1, 3, step=-1), by=mod(7))

# choose values for the eight gifts made (2009 - 2016)
for s in cubes.values():
  for vs in subsets(s, size=9):
    if s[0] < 1000: continue
    # and calculate the sequence of gifts
    gs = tuple((a - b) // 7 for (a, b) in tuples(vs, 2))
    if len(set(gs)) != len(gs): continue # gift amounts are all different
    # output solutions
    m = max(gs)
    printf("{vs} -> {gs}, max = {m}")

      Solution: There are two solutions. The largest amount is received by a grandchild is £ 292, or £ 388.

      If we start with 5832 (= 18³) in the savings account, and then give presents of (248, 103, 292, 86, 31, 64, 8, 1) to each grandchild then the amounts remaining in the savings account are:

      5832 (= 18³)
      4096 (= 16³)
      3375 (= 15³)
      1331 (= 11³)
      729 (= 9³)
      512 (= 8³)
      64 (= 4³)
      8 (= 2³)
      1 (= 1³)

      However, starting with 8000 (= 20³) and giving (163, 278, 388, 67, 104, 112, 13, 14), leaves amounts of:

      8000 (= 20³)
      6859 (= 19³)
      4913 (= 17³)
      2197 (= 13³)
      1728 (= 12³)
      1000 (= 10³)
      216 (= 6³)
      125 (= 5³)
      27 (= 3³)

      One way to rescue the puzzle is to exclude 1 as an amount given to the grandchildren (or remaining in the account).

      Another way is to require that none of the amounts given to any grandchild is itself a perfect cube.

      Either of these restrictions eliminate the first solution, leaving a unique answer of £ 388.

      Like

    • GeoffR's avatar

      GeoffR 8:28 am on 10 May 2020 Permalink | Reply 

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

% Yearly account balances
var 1000..9999: S1; var 1..9999: S2; var 1..9999: S3;
var 1..9999: S4; var 1..9999: S5; var 1..9999: S6;
var 1..9999: S7; var 1..9999: S8; var 1..9999: S9;

% yearly gifts 2009 - 2016
var 1..1400: G1; var 1..999: G2; var 1..999: G3;
var 1..999: G4; var 1..999: G5; var 1..999: G6;
var 1..999: G7; var 1..999: G8; 

% All yearly gifts are different values
constraint all_different ([G1, G2, G3, G4, G5, G6, G7, G8]);

% Set of cubes up to a maximum of four digits
set of int: cube = {n * n * n | n in 1..21};

% S1 is largest yearly account balance
constraint increasing([S9,S8,S7,S6,S5,S4,S3,S2,S1]);

% All yearly account balances are cubes
constraint S1 in cube /\  S2 in cube /\  S3 in cube 
/\ S4 in cube /\  S5 in cube /\  S6 in cube
/\ S7 in cube /\  S8 in cube /\ S9 in cube;

% Yearly amounts to distribute amongst seven grandchildren
constraint (S1 - S2) mod 7 == 0 /\ (S2 - S3) mod 7 == 0 /\ 
(S3 - S4) mod 7 == 0 /\ (S4 - S5) mod 7 == 0
/\ (S5 - S6) mod 7 == 0 /\ (S6 - S7) mod 7 == 0 
/\ (S7 - S8) mod 7 == 0 /\ (S8 - S9) mod 7 == 0;

% Yearly total gifts to each of seven grandchildren
constraint G1 == (S1 - S2) div 7 /\ G2 == (S2 - S3) div 7
/\ G3 == (S3 - S4) div 7 /\ G4 == (S4 - S5) div 7
/\ G5 == (S5 - S6) div 7 /\ G6 == (S6 - S7) div 7
/\ G7 == (S7 - S8) div 7 /\ G8 == (S8 - S9) div 7;

% Maximum yearly gift
var 10..1000: maxv;
maxv = max([G1, G2, G3, G4, G5, G6, G7, G8]);
 
solve satisfy;

output ["Yearly account balances: " ++ 
show([S1, S2, S3, S4, S5, S6, S7, S8, S9])] ++ 
["\nYearly gifts(£): " ++ show ([G1, G2, G3, G4, G5, G6, G7, G8])]
++ ["\nMax gift = " ++ show(maxv)] ;

% Yearly account balances: [5832, 4096, 3375, 1331, 729, 512, 64, 8, 1]
% Yearly gifts(£): [248, 103, 292, 86, 31, 64, 8, 1]
% Max gift = 292
% ----------
% Yearly account balances: [8000, 6859, 4913, 2197, 1728, 1000, 216, 125, 27]
% Yearly gifts(£): [163, 278, 388, 67, 104, 112, 13, 14]
% Max gift = 388
% ----------
% ==========

      Like

  • Unknown's avatar

    Jim Randell 9:07 am on 5 May 2020 Permalink | Reply
    Tags:   

    Teaser 2870: Lucky dip 

    From The Sunday Times, 24th September 2017 [link] [link]

    My bank PIN consists of four different digits in decreasing order. I used this PIN to help me choose my six lottery numbers. I wrote down all the two-figure numbers that used two different digits from the PIN. Just six of those numbers were in the range from 10 to 49 and so they were my lottery choices. In fact the sum of the six is a perfect square. If you knew that square it would now be possible to work out my PIN.

    What is my PIN?

    [teaser2870]

     
    • Jim Randell's avatar

      Jim Randell 9:08 am on 5 May 2020 Permalink | Reply

      This Python program runs in 87ms.

      Run: [ @repl.it ]

      from enigma import (subsets, irange, is_square, filter_unique, unpack, nconcat, printf)

# record (<PIN digits>, <2 digit numbers>, <square root of the sum of 2 digit numbers>)
rs = list()

# choose the 4 digits (in decreasing order)
for ds in subsets(irange(9, 0, step=-1), size=4, select="C"):
  # collect 2-digt numbers between 10 and 49
  ns = tuple(n for n in map(nconcat, subsets(ds, size=2, select="P")) if 9 < n < 50)
  # there are exactly 6 of them
  if len(ns) != 6: continue
  # and their sum is a perfect square
  s = is_square(sum(ns))
  if s is None: continue
  printf("[ds = {ds}, ns = {ns}, s = {s}]")
  rs.append((ds, ns, s))

# find PIN digits unique by s
(rs, _) = filter_unique(rs, unpack(lambda ds, ns, s: s), unpack(lambda ds, ns, s: ds))

# output solutions
for (ds, ns, s) in rs:
  printf("PIN = {pin}, numbers = {ns}, sum = {s}^2", pin=nconcat(ds), ns=sorted(ns))

      Solution: The PIN is 5420.

      There are 5 candidate PINs:

      5420, numbers = (45, 42, 40, 25, 24, 20), sum = 14²
      7320, numbers = (37, 32, 30, 27, 23, 20), sum = 13²
      7410, numbers = (47, 41, 40, 17, 14, 10), sum = 13²
      8621, numbers = (28, 26, 21, 18, 16, 12), sum = 11²
      9521, numbers = (29, 25, 21, 19, 15, 12), sum = 11²

      Only the first of these has a unique sum.

      Like

    • GeoffR's avatar

      GeoffR 5:04 pm on 5 May 2020 Permalink | Reply 

      from itertools import permutations

from collections import defaultdict
D = defaultdict(list)

def is_sq(n):
  c = int(n**(1/2) + 0.5)
  return (c**2 == n) 

for P1 in permutations (range(10),4):
  a, b, c, d = P1
  # choose four different digits in decreasing order
  if a > b > c > d:
    t = 1000*a + 100*b + 10*c + d   # PIN
    # find numbers in range 10...49 from 4 digits
    for P2 in permutations((a, b, c, d), 2):
      x, y = P2
      n = 10 * x + y
      if 10 <= n <= 49:
        D[t] += [n]

for k,v in D.items():
  # find 6 lottery numbers
  if len(v) == 6:
    # check sum of 6 numbers is a square
    t2 = v[0] + v[1] + v[2] + v[3] + v[4] + v[5]
    if is_sq(t2):
      print(k, v, t2)

# 5420 [45, 42, 40, 25, 24, 20] 196 << PIN = 5420
# 7320 [37, 32, 30, 27, 23, 20] 169
# 7410 [47, 41, 40, 17, 14, 10] 169
# 8621 [28, 26, 21, 18, 16, 12] 121
# 9521 [29, 25, 21, 19, 15, 12] 121

      Like

  • Unknown's avatar

    Jim Randell 10:47 am on 3 May 2020 Permalink | Reply
    Tags:   

    Brain-Teaser 519: Badberg clock 

    From The Sunday Times, 23rd May 1971 [link]

    At the village of Badberg, hidden away in the Alps, there is a town clock of a certain antiquity. The maker was a wealthy but inexpert amateur. After the ornate instrument had been installed it was found that the great hands stood still during the equal intervals between each stroke of the hour on the massive bell. Naturally, the clock was always slow.

    The placid villagers became accustomed to the erratic behaviour of their timepiece; only after the death of its donor did his nephew dare to tackle the problem. Finding it impossible to alter the striking mechanism, he ingeniously modified the movement to run at a higher constant speed so that the hands showed the correct time at least when the clock struck certain hours.

    Unfortunately, the hands still stop for the same period between successive strokes of the bell, but the villages can now see and hear the correct time every six hours.

    At what hours does the clock make its first stroke correctly?

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

    [teaser519]

     
    • Jim Randell's avatar

      Jim Randell 10:47 am on 3 May 2020 Permalink | Reply

      The clock only pauses between the strokes, so at 1 o’clock it doesn’t pause. At 2 o’clock it pauses for 1 interval. At 3 o’clock, 2 intervals. And so on until 12 o’clock when it pauses for 11 intervals. So the total time lost in a 12 hour period is 66 intervals.

      And the speed of the clock is adjusted so that the time lost in these 66 intervals is made up during the 12 hours. So we need to find adjacent 6 hour periods each containing 33 intervals. And there are only 6 pairs of periods to consider.

      Run: [ @repl.it ]

      from enigma import irange, tuples, printf

# "clock" arithmetic
clock = lambda n, m=12: (n % m) or m

# interval count for each hour
ps = list(irange(0, 11))

# find a consecutive sequence of 6 intervals that is half the total
t = sum(ps)
for (i, s) in enumerate(tuples(ps, 6)):
  if sum(s) * 2 == t:
    (h1, h2) = (i + 1, i + 7)
    printf("{h1}, {h2}", h1=clock(h1), h2=clock(h2))

      Solution: The clock is correct at 4 o’clock and 10 o’clock.

      In striking 4, 5, 6, 7, 8, 9 o’clock the clock pauses for 3 + 4 + 5 + 6 + 7 + 8 = 33 intervals.

      In striking 10, 11, 12, 1, 2, 3 o’clock the clock pauses for 9 + 10 + 11 + 0 + 1 + 2 = 33 intervals.

      Like

  • Unknown's avatar

    Jim Randell 5:53 pm on 1 May 2020 Permalink | Reply
    Tags:   

    Teaser 3006: Raffle tickets 

    From The Sunday Times, 3rd May 2020 [link] [link]

    At our local bridge club dinner we were each given a raffle ticket. The tickets were numbered from 1 to 80. There were six people on our table and all our numbers were either prime or could be expressed as the product of non-repeating primes (e.g. 18 = 2×3×3 is not allowed). In writing down the six numbers you would use each of the digits 0 to 9 once only. If I told you the sum of the six numbers (a perfect power) you should be able to identify the numbers.

    List the numbers (in ascending order).

    [teaser3006]

     
    • Jim Randell's avatar

      Jim Randell 6:14 pm on 1 May 2020 Permalink | Reply

      This Python program runs in 172ms.

      Run: [ @repl.it ]

      from enigma import irange, inf, is_duplicate, factor, seq_all_different as all_different, filter_unique, iroot, printf

# find numbers with different prime factors, and no repeated digits
ns = list()
for n in irange(1, 80):
  if is_duplicate(n): continue
  fs = factor(n)
  if fs and all_different(fs):
    ns.append(n)

# find sets of k numbers, that use the digits 0-9 exactly once
def generate(ns, k, ds=set(), s=[]):
  # are we done?
  if k == 0:
    if len(ds) == 10:
      yield tuple(s)
  else:
    # add in another number
    for (i, n) in enumerate(ns, start=1):
      t = str(n)
      if ds.intersection(t): continue
      yield from generate(ns[i:], k - 1, ds.union(t), s + [n])

# find 6-sets that are unique by sum
(ss, _) = filter_unique(generate(ns, 6), sum)

# find powers for n
def powers(n, p=1):
  for k in irange(p, inf):
    x = iroot(n, k)
    if x ** k == n:
      yield (x, k)
    if x == 1: break

# output solution
for s in ss:
  t = sum(s)
  ps = list(powers(t, 2))
  printf("{s} -> {t} {ps}")

      Solution: The numbers are: 2, 3, 41, 58, 69, 70.

      The sum is 243 (= 3^5).

      We can find 78 different sets of 6 numbers that use the digits 0-9 exactly once, but only the set given above has a unique sum (which is the largest possible sum).

      Like

    • GeoffR's avatar

      GeoffR 11:25 am on 5 May 2020 Permalink | Reply

      The programme found four solutions, but only the first is a correct unique solution
      ie Tickets: 2, 3, 41, 58, 69, 70.

      There is anpother duplicate solution with a total of 216, but the programme did not find it. Two other potential solutions also had a total of 225, so do not give a unique solution.

      The programme would only run under the Chuffed solver in a reasonable time.

      
% A Solution in MiniZinc
include "globals.mzn";
 
var 0..9:A; var 0..9:B; var 0..9:C; var 0..9:D;
var 0..9:E; var 0..9:F; var 0..9:G; var 0..9:H;
var 0..9:I; var 0..9:J;

constraint all_different ([A,B,C,D,E,F,G,H,I,J]);

% total of six factors
var 100..400: total;

% perfect powers possible between 100 and 400
constraint total == pow(2,8) \/ total == pow(3,4) \/ total == pow(3,5) 
\/ total == pow(5,3) \/ total == pow(6,3) \/ total == pow(7,3)
\/ total == pow(12,2) \/ total == pow(13,2) \/ total = pow(14,2)
\/ total == pow(15,2) \/ total == pow(17,2) \/ total = pow(18,2);

% numbers are A, B, CD, EF, GH, IJ
total = A + B + CD + EF + GH + IJ;
var 11..80: CD = 10*C + D;
var 11..80: EF = 10*E + F;
var 11..80: GH = 10*G + H;
var 11..80: IJ = 10*I + J;

% Possible prime factors for CD, EF, GH and IJ
var 2..79: a1; var 2..79: a2; var 2..79: a3;
var 2..79: b1; var 2..79: b2; var 2..79: b3;
var 2..79: c1; var 2..79: c2; var 2..79: c3;
var 2..79: d1; var 2..79: d2; var 2..79: d3;

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

constraint is_prime (A) /\ is_prime(B);

% CD is prime or has two or three different prime factors
constraint (is_prime(CD))
\/ 
(a1 != a2 /\ CD == a1 * a2 /\ is_prime(a1) /\ is_prime(a2))
\/  
(a1 != a2 /\ a1 != a3 /\ a2 != a3 /\ CD == a1 * a2 * a3 /\ 
is_prime(a1) /\ is_prime(a2) /\ is_prime(a3));

% EF is prime or has two or three different prime factors
constraint (is_prime(EF))
\/ 
(b1 != b2 /\ EF == b1 * b2 /\ is_prime(b1) /\ is_prime(b2))
\/  
(b1 != b2 /\ b1 != b3 /\ b2 != b3 /\ EF == b1 * b2 * b3 /\ 
is_prime(b1) /\ is_prime(b2) /\ is_prime(b3));

% GH is prime or has two or three different prime factors
constraint (is_prime(GH))
\/ 
(c1 != c2 /\ GH == c1 * c2 /\ is_prime(c1) /\ is_prime(c2))
\/  
(c1 != c2 /\ c1 != c3 /\ c2 != c3 /\ GH == c1 * c2 * c3 /\ 
is_prime(c1) /\ is_prime(c2) /\ is_prime(c3));

% IJ is prime or has two or three different prime factors
constraint (is_prime(IJ))
\/ 
(d1 != d2 /\ IJ == d1 * d2 /\ is_prime(d1) /\ is_prime(d2))
\/  
(d1 != d2 /\ d1 != d3 /\ d2 != d3 /\ IJ == d1 * d2 * d3 /\ 
is_prime(d1) /\ is_prime(d2) /\ is_prime(d3));

constraint increasing([A ,B, CD, EF, GH, IJ]);

solve satisfy;

output ["Tickets: " ++ show(A) ++ ", " ++ show(B) ++ ", " 
++ show(CD) ++ ", " ++ show(EF) ++ ", " ++ show(GH) ++ ", "
++ show(IJ) ++ ", total = " ++ show(total) ];


% Tickets: 2, 3, 41, 58, 69, 70, total = 243  <<< Correct Solution
% time elapsed: 0.03 s
% ----------
% Tickets: 2, 3, 14, 58, 69, 70, total = 216 << A duplicate solution exists
% time elapsed: 0.03 s
% ----------
% Tickets: 2, 5, 38, 41, 69, 70, total = 225 - duplicate 
% time elapsed: 0.03 s
% ----------
% Tickets: 2, 5, 30, 41, 69, 78, total = 225 _ duplicate
% time elapsed: 0.03 s
% ----------
% ==========

      Like

  • Unknown's avatar

    Jim Randell 11:56 am on 30 April 2020 Permalink | Reply
    Tags:   

    Teaser 2876: Bonfire toffee 

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

     In this subtraction sum I have consistently replaced digits with letters, different letters being used for different digits:

    BONFIRE – TOFFEE = TREATS

    What is the number of ENTRIES?

    [teaser2876]

     
    • Jim Randell's avatar

      Jim Randell 11:56 am on 30 April 2020 Permalink | Reply

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

      >>> python -m enigma SubstitutedExpression "TREATS + TOFFEE = BONFIRE" --answer="ENTRIES"
(TREATS + TOFFEE = BONFIRE) (ENTRIES)
(769470 + 758899 = 1528369) (9276390) / A=4 B=1 E=9 F=8 I=3 N=2 O=5 R=6 S=0 T=7
(769870 + 754499 = 1524369) (9276390) / A=8 B=1 E=9 F=4 I=3 N=2 O=5 R=6 S=0 T=7
ENTRIES = 9276390 [2 solutions]

      Solution: ENTRIES = 9276390.

      There are two possible sums, the values for A and F being interchangeable:

      769470 + 758899 = 1528369
      769870 + 754499 = 1524369

      Like

  • Unknown's avatar

    Jim Randell 8:29 am on 28 April 2020 Permalink | Reply
    Tags:   

    Teaser 2593: Spell it out! 

    From The Sunday Times, 3rd June 2012 [link] [link]

    I have written down a very large number (but with fewer than twenty-five digits). If you spell out each of its digits as a word, then for each digit its last letter is the same as the first letter of the next digit (the last letter of the last digit being the same as the first letter of the first digit). One example of such a number would be 83821.

    Neither my number nor the sum of its digits is a palindromic number (but in fact the original number is one more than a palindrome).

    What is my number?

    [teaser2593]

     
    • Jim Randell's avatar

      Jim Randell 8:30 am on 28 April 2020 Permalink | Reply

      This Python program runs in 99ms.

      Run: [ @repl.it ]

      from enigma import (int2words, irange, is_palindrome, nsplit, printf)

# digits as words
words = list(int2words(d) for d in irange(0, 9))

# possible next numbers
succ = dict()
for (d1, w1) in enumerate(words):
  succ[d1] = list(d2 for (d2, w2) in enumerate(words) if w1[-1] == w2[0])

# find numbers that form a loop according to relationship r
def solve(ns, k, r=succ):
  # check the numbers form a loop
  if ns[0] in r[ns[-1]]:
    yield ns
  # can we add another number
  if len(ns) < k:
    for n in r[ns[-1]]:
      yield from solve(ns + [n], k)

# consider possible initial digits
for n in succ.keys():
  # find loops with length less than 25
  for ns in solve([n], 24):
    # the number itself is 1 more than a palindrome
    if not (ns[0] + 1 == ns[-1] and is_palindrome(ns[1:-1])): continue
    # the sum of the digits is not a palindrome
    t = sum(ns)
    if is_palindrome(nsplit(t)): continue
    # output solution
    printf("{ns} -> {t}")

      Solution: The number is 183838383838383838382.

      The number is 21 digits long. And the digit sum is (8 + 3) × 9 + (1 + 8 + 2) = 110.

      Like

  • Unknown's avatar

    Jim Randell 9:19 am on 26 April 2020 Permalink | Reply
    Tags: by: Jonathan Welton   

    Brainteaser 1814: Clear heads 

    From The Sunday Times, 22nd June 1997 [link]

    “I have affixed a card to each of your foreheads”, explained the professor of logic to his three most able students. All three were perfect logicians capable of instantly deducing the logical consequences of any statement.

    He continued: “You can see the others’ cards, but none of you can see your own. On each card is written a positive whole number and one of the numbers is the sum of the other two”.

    The professor turned to the first student, Albert: “From what you can see and what you have heard, can you deduce the number on your card?”. Albert could not.

    The professor then asked Bertrand the same question. He could not deduce the number on his card.

    Likewise, when asked next, Charles could not deduce the number on his card.

    The professor then asked Albert the same question again and this time Albert was able to deduce that the number on his card was 50.

    What number was on Bertrand’s card, and what number was on Charles’s card?

    This puzzle is included in the book Brainteasers (2002). The puzzle text above is taken from the book.

    [teaser1814]

     
    • Jim Randell's avatar

      Jim Randell 9:20 am on 26 April 2020 Permalink | Reply

      Each person can see two numbers, and knows their own number must be either the sum or difference of these two numbers.

      So when A is asked, the only way he would be able to narrow this choice down to a single number is if B and C’s numbers are the same, as the difference would be zero, and this is not allowed, so he would know his own number was the sum of B and C’s numbers. So A will be able to declare at the first question only if the set numbers is of the form (2n, n, n).

      Similarly, when B is asked, he will be able to declare if the set of numbers is of the form (n, 2n, n).

      But we also know that if B sees (2n, ?, n) that his own number must be 3n or n, but it cannot be n, as A would have declared if the numbers were (2n, n, n). So B can also declare if the sets of numbers are of the form (2n, 3n, n).

      When C is asked, he can declare if the numbers of the form: (n, n, 2n), (2n, n, 3n), (n, 2n, 3n), (2n, 3n, 5n).

      A is then asked again, and this time declares. So the numbers must fit one of the following patterns:

      (3n, 2n, n)
      (4n, 3n, n)
      (3n, n, 2n)
      (4n, n, 3n)
      (5n, 2n, 3n)
      (8n, 3n, 5n)

      Of these patterns, only one gives integer values when the first element is 50:

      (5n, 2n, 3n) = (50, 20, 30)

      Solution: Bertrand’s number was 20. Charles’s number was 30.

      Here is a Python program that generates the appropriate patterns for each question, and then determines what sequences of numbers match the patterns for the 4th question. It runs in 73ms.

      Run: [ @repl.it ]

      from enigma import irange, inf, flatten, div, printf

# update pattern p, element i becomes the sum of the other elements
def update(p, i):
  p = list(p)
  p[i] = sum(p) - p[i]
  return p

# produce patterns that lead to declarations for A, B, C, A, B, C, ...
def declare():
  ds = list()
  for i in irange(0, inf):
    ps = list()
    # initial seeds
    if i < 3: ps.append(update([1, 1, 1], i))
    # add in alternatives from the previous rounds
    j = i % 3
    for p in flatten(ds):
      ps.append(update(p, j))
    yield ps
    # keep the previous 2 rounds
    ds.append(ps)
    if len(ds) > 2: ds.pop(0)

# find declaration patterns that correspond to the 4th question
for (i, ps) in enumerate(declare(), start=1):
  printf("[{i} -> {ps}]")
  if i == 4: break

# given A calculate B and C from the patterns
A = 50
for (a, b, c) in ps:
  (B, C) = (div(b * A, a), div(c * A, a))
  if B and C:
    printf("A={A} B={B} C={C}")

      Like

  • Unknown's avatar

    Jim Randell 5:07 pm on 24 April 2020 Permalink | Reply
    Tags:   

    Teaser 3005: Tubular bales 

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

    Ten equal-length, rigid tubes, each a different prime-valued external radius from 11 mm to 43 mm, were baled, broadside, by placing the 43 mm and 11 mm tube together and the third tube, not the largest remaining, touching both of these. Each subsequent tube touched the previous tube placed and the 43 mm tube. A sub-millimetre gap between the final tube placed and the 11 mm tube, made a near perfect fit.

    The radius sum of the first three tubes placed against the 43 mm tube was a multiple of one of the summed radii. Curiously, that statement remains true when each of “four”, “five”, “seven” and “eight” replaces “three”. For “two” and “six” tubes placed their radius sum was a multiple of an as yet unplaced tube’s radius.

    What radius tube, in mm, was placed last?

    [teaser3005]

     
    • Jim Randell's avatar

      Jim Randell 5:30 pm on 24 April 2020 Permalink | Reply

      This Python program runs in 78ms.

      from enigma import (primes, printf)

# numbers available to to use
rs = list(primes.between(11, 44))
assert len(rs) == 10

# check n is a multiple of some element of ms
check = lambda n, ms: any(n % m == 0 for m in ms)

# solve for the specified numbers
# ns = unused numbers
# ss = used numbers
def solve(ns, ss):
  # are we done?
  if not ns:
    yield ss
  else:
    # what number placement is this?
    k = len(ss) + 1
    t = sum(ss)
    # choose the next number to use
    for (i, n) in enumerate(ns):
      # 2nd: not the largest available
      if k == 2 and n == ns[-1]: continue
      t_ = t + n
      # 3rd, 4th, 5th, 7th, 8th: multiple of a used number
      ss_ = ss + [n]
      if k in (3, 4, 5, 7, 8) and not check(t_, ss_): continue
      # 2nd, 6th: multiple of an unused number
      ns_ = ns[:i] + ns[i + 1:]
      if k in (2, 6) and not check(t_, ns_): continue
      # solve for the remaining numbers
      yield from solve(ns_, ss_)

# collect possible final numbers
fs = set()
for ss in solve(rs[1:-1], rs[:1]):
  fs.add(ss[-1])
  printf("{ss}")

# output solution
printf("final number = {fs}")

      Solution: The 37 mm tube was placed last.

      The conditions placed on the ordering of the numbers means that although there are four possible orders that the tubes could be assembled in, the answer to the puzzle (the radius of the final tube) is the same in all cases.

      So it is not necessary to check that the placement results in a gap of less than 1 mm, but if you do, you find all 4 orderings result in a gap less than 1 mm (and one of them is an almost perfect fit).

      Here is a diagram of the packing (11, 23, 17, 41, 29, 31, 19, 13, 37) around the 43 tube. This has the largest gap of 0.66 mm.

      Here is a list of 4 packings, and the corresponding gaps:

      (11, 23, 17, 41, 29, 31, 13, 19, 37) → gap = 0.36 mm
      (11, 23, 17, 41, 29, 31, 19, 13, 37) → gap = 0.66 mm
      (11, 23, 17, 41, 31, 29, 13, 19, 37) → gap = 0.000055 mm
      (11, 23, 17, 41, 31, 29, 19, 13, 37) → gap = 0.41 mm

      The third one has a gap of just 55 nm, which is about half the diameter of a single coronavirus particle, and probably quite a lot smaller than the tolerance of the tubes.

      Perhaps the puzzle was intended to be set with the radii of the tubes measured in centimetres, then there would be only one arrangement that had a sub-millimetre gap.

      Like

  • Unknown's avatar

    Jim Randell 9:24 am on 23 April 2020 Permalink | Reply
    Tags:   

    Teaser 2591: Shilly Chalet 

    From The Sunday Times, 20th May 2012 [link] [link]

    George and Martha are running a holiday camp and their four daughters are staying there. To keep the peace they have been given chalets in different areas. Amelia’s chalet number is between 1 and 99, Bertha’s is between 100 and 199, Caroline’s between 200 and 299, and Dorothy’s between 300 and 399.

    George commented that the difference between any two of the four chalet numbers is either a square or a cube. Martha added that the same could be said for the sum of the chalet numbers of the three youngest daughters.

    Who is the eldest daughter and what is her chalet number?

    [teaser2591]

     
    • Jim Randell's avatar

      Jim Randell 9:25 am on 23 April 2020 Permalink | Reply

      Programatically it is straightforward to check all the possibilities.

      This Python program runs in 141ms.

      Run: [ @repl.it ]

      from enigma import (is_square, is_cube, irange, cached, printf)

# check for a square or a cube
check = cached(lambda n: is_square(n) or is_cube(n))

# choose a value for A
for A in irange(1, 99):
  # choose a value for B
  for B in irange(100, 199):
    if not check(B - A): continue
    # choose a value for C
    for C in irange(200, 299):
      if not (check(C - A) and check(C - B)): continue
      # choose a value for D
      for D in irange(300, 399):
        if not (check(D - A) and check(D - B) and check(D - C)): continue
        # check the total excluding the eldest
        T = A + B + C + D
        for (n, x) in zip("ABCD", (A, B, C, D)):
          if not check(T - x): continue
          # output solution
          printf("A={A} B={B} C={C} D={D}; eldest={n}")

      Solution: Amelia is the eldest daughter. Her chalet is number 93.

      The chalet numbers are:

      A=93, B=193, C=218, D=318

      And: B + C + D = 729 = 27^2 = 9^3.

      This sum is both a square and a cube.

      So, if you interpret “either … or …” to be an exclusive or (one or the other, but not both), then the puzzle has no solutions.

      Like

    • GeoffR's avatar

      GeoffR 10:45 am on 24 April 2020 Permalink | Reply 

      
% A Solution in MiniZinc
include "globals.mzn";
 
var 1..99:A;       % Amelia
var 100..199:B;    % Bertha
var 200..299:C;    % Caroline
var 300..399:D;    % Dorothy

set of int: sq = {n * n | n in 2..32};  
set of int: cb = {n * n * n | n in 2..10};

% difference between any chalet numbers is either a square or a cube
constraint (B-A) in sq \/ (B-A) in cb;
constraint (C-A) in sq \/ (C-A) in cb;
constraint (C-B) in sq \/ (C-B) in cb;
constraint (D-C) in sq \/ (D-C) in cb;
constraint (D-B) in sq \/ (D-B) in cb;
constraint (D-A) in sq \/ (D-A) in cb;

% sum of three youngest daughters chalet numbers is a square or a cube
constraint ((A+B+C) in sq \/ (A+B+C) in cb)
\/  ((A+B+D) in sq \/ (A+B+D) in cb)
\/  ((B+C+D) in sq \/ (B+C+D) in cb);

solve satisfy;

% A = 93;
% B = 193;
% C = 218;
% D = 318;
% % time elapsed: 0.06 s
% ----------
% ==========
% sum of three youngest daughters chalets is a square or a cube
% A + B + C = 93 + 193 + 218 = 504 - not a square or a cube
% A + B + D = 93 + 193 + 318 = 604 - not a square or a cube
% B + C + D = 193 + 218 + 318 = 729 - is both a square and a cube

% Therefore, Ameila is the eldest daughter with chalet number 93

      Like

    • GeoffR's avatar

      GeoffR 11:46 am on 24 April 2020 Permalink | Reply 

      sq = [x * x for x in range(2,32)]
cb = [x * x * x for x in range(2,10)]

# form a set of square and cube numbers
sc = set(sq) | set(cb)

for a in range(1,100):
  for b in range(100,200):
    if (b-a) in sc:
      for c in range(200,300):
        if (c-a) in sc and (c-b) in sc:
          for d in range(300,400):
            if (d-c) in sc and (d-b) in sc and (d-a) in sc:
              if (a+b+d) in sc:
                print('Eldest daughter Caroline has chalet', c)
              if (b+c+d) in sc:
                print('Eldest daughter Ameila has chalet', a)
              if (a+c+d) in sc:
                  print('Eldest daughter Bertha has chalet', b)
              if (a+b+c) in sc:
                  print('Eldest daughter Dorothy has chalet', d)

# Eldest daughter Ameila has chalet 93

      Like

  • Unknown's avatar

    Jim Randell 8:21 am on 21 April 2020 Permalink | Reply
    Tags: by: Brian Young   

    Brain-Teaser 518: [Prophecies] 

    From The Sunday Times, 16th May 1971 [link]

    An interesting fragment tells us what took place at the meeting of the Five Prophets:

    “If Hosea hath prophesied truth, Micah and Obadiah will die in the same city; if Micah hath prophesied truth, Joel and Obadiah will die in the same city. It is the saying of Joel that three of the five prophets shall die in Babylon; and Nahum declareth to Hosea that the two of them shall die in different cities.”

    It is well known that those who prophesy correctly die in Jerusalem, whereas those who make false prophecies die in Babylon.

    So how many of these five will die in Jerusalem?

    This puzzle was originally published with no title.

    [teaser518]

     
    • Jim Randell's avatar

      Jim Randell 8:22 am on 21 April 2020 Permalink | Reply

      There are only 2^5 (= 32) possibilities, so we can examine them all.

      This Python program runs in 79ms.

      from enigma import subsets, printf

# check statement made by X
check = lambda X, s: (X == "J") == bool(s)

# consider where each will die
for (H, J, M, N, O) in subsets("BJ", size=5, select="M"):

  # how many die in J?
  n = (H, J, M, N, O).count('J')

  # "H: M and O will die in the same city"
  if not check(H, M == O): continue

  # "M: J and O will die in the same city"
  if not check(M, J == O): continue

  # "J: [exactly] three of the five prophets shall die in B"
  if not check(J, n == 2): continue

  # "N: N and H shall die in different cities"
  if not check(N, N != H): continue

  # output solution
  printf("n={n} [H={H} J={J} M={M} N={N} O={O}]")

      Solution: One of them will die in Jerusalem.

      There are two solutions:

      H: false, B
      J: false, B
      M: false, B
      N: false, B
      O: [true], J

      H: false, B
      J: false, B
      M: true, J
      N: false, B
      O: [false], B

      We are not given a prophesy by O, to verify whether it is true or not, but we can infer where he must die in order for the prophecies we are given to be consistent, and from that whether he makes prophecies that are true or false.

      In the first case he must die in Jerusalem, so must make true prophecies. And in the second case he must die in Babylon, and so must make false prophecies.

      Like

      • John Crabtree's avatar

        John Crabtree 8:18 pm on 22 April 2020 Permalink | Reply

        Let the prophesies be #1, #2, #3 and #4 by H, M, J and N respectively.
        From #4, H dies in Babylon.
        Then from #1, one, and only one, of M and O die in Babylon.
        Then from #2, J dies in Babylon.
        Then from #3, four prophets, including N, die in Babylon.
        And so one prophet (Micah or Obadiah) dies in Jerusalem.

        Liked by 1 person

  • Unknown's avatar

    Jim Randell 4:27 pm on 17 April 2020 Permalink | Reply
    Tags:   

    Teaser 3004: Going up 

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

    In our football league, the teams all play each other once, with three points for a win and one for a draw. At the end of the season, the two teams with most points are promoted, goal difference being used to separate teams with the same number of points.

    Last season’s climax was exciting. With just two games left for each team, there were several teams tied at the top of the league with the same number of points. One of them, but only one, could be certain of promotion if they won their two games. If there had been any more teams on the same number of points, then none could have guaranteed promotion with two wins.

    How many teams were tied at the top of the league, and how many of the remaining matches involved any of those teams?

    [teaser3004]

     
    • Jim Randell's avatar

      Jim Randell 9:33 am on 18 April 2020 Permalink | Reply

      I supposed there were several teams, A, B, C, …, tied at the top. And we are looking for situations where team A is looking at a guaranteed promotion, if they win both their games.

      Obviously any of the other teams tied at the top of the table would also be in with a chance of promotion if they win both their games (as they will have the same maximum number of points as A).

      But if one of the teams were to win a match by an enormous number of goals, it would give them an unassailable goal difference. So A can only be guaranteed a win if there are fewer than three teams tied at the top after the games are played (so the goal difference rule doesn’t come into it).

      So we need to look at numbers of teams, such that there is an arrangement of remaining matches, where A (and only A) is guaranteed a promotion if they win both their matches, but if there were one more team then there would be no such arrangement of matches.

      This Python program is a bit slow (it takes 8.9s), but it does find what seems to be a reasonable answer. I may see if I can come up with a more efficient program later.

      from enigma import (cproduct, multiset, irange, join, printf)

# generate matches for teams <ts> tied at the top
# ts = teams tied at the top
# ss = number of matches to be played by teams in <ts>
# team Z is used to denote any other team not in <ts>
def matches(ts, ss, ms=[]):
  # are we done?
  if not ss:
    yield ms
  else:
    # choose a team
    ks = sorted(ss.keys())
    t = ks.pop(0)
    # choose an opponent
    ks.append('Z')
    for x in ks:
      m = (t, x)
      if x == 'Z' or not (ms and m < ms[-1]):
        yield from matches(ts, ss.difference(m), ms + [m])

# find teams that can be guaranteed promotion
# ts = teams tied at the top
# ms = remaining matches
def solve(ts, ms):
  # find wins where 2 wins guarantees A a place in the top 2
  (inc, exc) = (set(), set())
  # choose winning teams for each match
  for wins in cproduct(ms):
    # collect teams with 2 wins
    m = multiset.from_seq(wins)
    ws = list(t for (t, n) in m.items() if n == 2 and t != 'Z')
    if len(ws) < 3:
      # a guaranteed win
      inc.update(ws)
    else:
      # not a guaranteed win
      exc.update(ws)
      if exc.issuperset(ts): return set()
  # return those teams that are guaranteed a win in all situations
  return inc.difference(exc)

# format a sequence of matches
fmt = lambda ms: join((x + "v" + y for (x, y) in ms), sep=", ", enc="()")

# consider teams labelled A, B, C, ... (Z is used to denote "other" teams)
# record teams where there is a set of matches that guarantees only team A a promotion
r = dict()
for n in irange(2, 25):
  teams = "ABCDEFGHIJKLMNOPQRSTUVWXY"[:n]
  ss = multiset.from_seq(teams * 2)
  for ms in matches(teams, ss):
    # does this set of matches guarantee a promotion for only A?
    ws = solve(teams, ms)
    if len(ws) == 1 and 'A' in ws:
      printf("n={n}: {ms} -> {ws}", ms=fmt(ms), ws=join(sorted(ws)))
      r[n] = ms
      break # we only need one set of matches
  if n not in r:
    printf("n={n}: <none>")
    # are we done?
    k = n - 1
    if k in r:
      ms = r[k]
      printf("{k} -> {ms}; {m} matches", m=len(ms), ms=fmt(ms))
      break

      Solution: There are 6 teams tied at the top. 7 of the remaining matches involve at least one of those teams.

      For six teams at the top:

      If A plays B and C and wins both matches, then neither B nor C can achieve the maximum number of points, so they are out of contention.

      And there are three more teams at the top, D, E, F, and they all play each other, then only one of them can achieve 2 wins, to tie with A at the top of the table.

      So A is guaranteed to finish in the top 2 if they win both their games, and get promotion.

      Introducing a seventh team, G, would mean that a third team could get two wins, so A‘s promotion would not be guaranteed.

      Like

  • Unknown's avatar

    Jim Randell 12:02 pm on 16 April 2020 Permalink | Reply
    Tags:   

    Brainteaser 1808: Next choice 

    From The Sunday Times, 11th May 1997 [link]

    Much nonsense is written about the lottery. It is true that there are about 14 million different choices of six numbers from 1 to 49, but often surprise is expressed when the winning six include at least two consecutive numbers. In common with a lot of people, when I choose my numbers I make sure that they are well spread out, thus fitting in with the usual conception that it is unlikely that consecutive numbers will be drawn.

    This set me thinking about what proportion of the 14 million possible choices of 6 numbers actually contained no two consecutive numbers. The answer is surprising and neat. So, in percentages, to the nearest whole number, what proportion of the choices include no consecutive numbers?

    This puzzle is included in the book Brainteasers (2002). The puzzle text above is taken from the book.

    [teaser1808]

     
    • Jim Randell's avatar

      Jim Randell 12:02 pm on 16 April 2020 Permalink | Reply

      We have already tackled a very similar puzzle with Enigma 1029 (also set by Victor Bryant under the pseudonym Susan Denham).

      The number of ways to choose 6 numbers from 49 is:

      C(49, 6) = 49! / (6! (49 − 6)!) = 13,983,816

      The number of ways to choose 6 non-consecutive numbers from 49 is:

      C(49 − 5, 6) = 44! / (6! (44 − 6)!) = 7,059,052

      This is approximately 50.48% of the total number of choices. So there are slightly more non-consecutive choices than consecutive choices.

      Solution: Approximately 50% of choices are non-consecutive.

      Like

  • Unknown's avatar

    Jim Randell 8:49 am on 14 April 2020 Permalink | Reply
    Tags:   

    Teaser 2650: Squares of oblongs 

    From The Sunday Times, 7th July 2013 [link] [link]

    I gave to each of Ruby and Annie a set of “Oblongs”. Each set consisted of nine pieces of card of sizes 1×2, 2×3, 3×4, 4×5, 5×6, 6×7, 7×8, 8×9 and 9×10. The idea was to use some or all of the cards to make various shapes in jigsaw fashion. I asked them to make a square using some of their own pieces. Ruby made the smallest square possible with her set and Annie made the largest square possible with hers. Then I collected up all the unused pieces of card.

    What (in increasing order) were the sizes of these unused pieces?

    [teaser2650]

     
    • Jim Randell's avatar

      Jim Randell 8:49 am on 14 April 2020 Permalink | Reply

      See also: Enigma 10, Enigma 1491, Enigma 1251.

      I packaged up the rectangle packer I wrote for Enigma 1491 into a separate module: rectpack.py.

      This Python program looks for subsets of the tiles that have an area that can be made into a square, and then tries to pack them into the square. It runs in 110ms.

      Run: [ @replit ]

      from rectpack import pack
from enigma import (irange, subsets, is_square, Accumulator, diff, printf)

# available tiles
tiles = list((i, i + 1) for i in irange(1, 9))

# find the smallest and largest squares
rs = [ Accumulator(fn=min), Accumulator(fn=max) ]

# choose subsets of the tiles
for ts in subsets(tiles, min_size=2):
  # is the area a square number
  t = sum(a * b for (a, b) in ts)
  x = is_square(t)
  if x is None: continue

  # attempt to fit the rectangles into the square
  for ps in pack(x, x, ts):
    printf("{t} = {x}^2 -> {ts}")
    printf("-> {ps}")
    for r in rs: r.accumulate_data(x, ts)
    break  # only need one packing

# output solution
printf("min = {rs[0].value}^2, {rs[0].data}")
printf("max = {rs[1].value}^2, {rs[1].data}")

# unused tiles
us = diff(tiles, rs[0].data) + diff(tiles, rs[1].data)
printf("unused = {us}", us=sorted(us))

      Solution: The unused pieces are: 1×2, 2×3, 8×9.

      The smallest square that can be made is a 16×16 square using all the pieces except 1×2 and 8× 9.

      The largest square that can be made is a 18×18 square using all the pieces except 2×3.

      These are in fact the only two sets of pieces that can be assembled into squares.

      Like

  • Unknown's avatar

    Jim Randell 11:43 am on 12 April 2020 Permalink | Reply
    Tags:   

    Brain-Teaser 517: [Rugby table] 

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

    The final table of the inter-zone Rugby championships of Pongoland reads:

    Each tribe used only one goal-kicker; C’s kicked most points and A’s least. C had only one penalty scored against them.

    The only types of score were:

    try converted to goal (5 points)
    try unconverted (3 points)
    penalty goal (3 points)

    How were the two sides’ scores made up in the match Aboma vs. Bwaga?

    This puzzle was originally published with no title.

    [teaser517]

     
    • Jim Randell's avatar

      Jim Randell 11:44 am on 12 April 2020 Permalink | Reply

      It seems that the points scored by the kicker are: 2 points for a conversion; 0 points for a try; 3 points for a penalty goal.

      I wrote a MiniZinc model to solve the problem:

      %#! minizinc -a

% xYZ = number of score type x (= c (5), t (3), p (3)) by Y against Z

var 0..2: cAB;
var 0..4: tAB;
var 0..4: pAB;
var 0..2: cBA;
var 0..4: tBA;
var 0..4: pBA;

var 0..3: cAC;
var 0..5: tAC;
var 0..5: pAC;
var 0..1: cCA;
var 0..3: tCA;
var 0..3: pCA;

var 0..2: cBC;
var 0..4: tBC;
var 0..4: pBC;
var 0..1: cCB;
var 0..3: tCB;
var 0..3: pCB;

% total points
function var int: points(var int: c, var int: t, var int: p) = 5 * c + 3 * t + 3 * p;

% kicked points
function var int: kicks(var int: c, var int: t, var int: p) = 2 * c + 3 * p;

% point values in the table
constraint points(cAB, tAB, pAB) + points(cAC, tAC, pAC) = 18;
constraint points(cBA, tBA, pBA) + points(cCA, tCA, pCA) = 12;

constraint points(cBA, tBA, pBA) + points(cBC, tBC, pBC) = 14;
constraint points(cAB, tAB, pAB) + points(cCB, tCB, pCB) = 13;

constraint points(cCA, tCA, pCA) + points(cCB, tCB, pCB) = 9;
constraint points(cAC, tAC, pAC) + points(cBC, tBC, pBC) = 16;

% A won both their games, C lost both their games
constraint points(cAB, tAB, pAB) > points(cBA, tBA, pBA); % A beat B
constraint points(cAC, tAC, pAC) > points(cCA, tCA, pCA); % A beat C
constraint points(cBC, tBC, pBC) > points(cCB, tCB, pCB); % B beat C

% kicked points: C > B > A
constraint kicks(cAB, tAB, pAB) + kicks(cAC, tAC, pAC) < kicks(cBA, tBA, pBA) + kicks(cBC, tBC, pBC);
constraint kicks(cBA, tBA, pBA) + kicks(cBC, tBC, pBC) < kicks(cCA, tCA, pCA) + kicks(cCB, tCB, pCB);

% C had 1 penalty scored against them
constraint pAC + pBC = 1;

solve satisfy;

      Solution: Aboma scored 2 conversions (for 10 points). Bwaga scored 1 try and 1 penalty (for 6 points)

      The results are:

      A vs. B: 10 pts (2c) vs. 6 pts (t + p)
      A vs. C: 8 pts (c + t) vs. 6 pts (2p)
      B vs. C: 8 pts (c + p) vs. 3 pts (p)

      A’s kicker made 6 points.
      B’s kicker made 8 points.
      C’s kicker made 9 points.

      Like

  • Unknown's avatar

    Jim Randell 5:27 pm on 9 April 2020 Permalink | Reply
    Tags:   

    Teaser 3003: All that glitters 

    From The Sunday Times, 12th April 2020 [link] [link]

    My aunt has a collection of sovereigns, and she set me a challenge:

    “You can have the coins if you can work out the dates, which (in increasing order) are equally spaced and all in the 20th century. The number of coins is an odd prime. The highest common factor of each pair of dates is an odd prime. The sum of the number of factors of each of the dates (including 1 and the date itself) is an odd prime.”

    I worked out the dates, though the gift was much less valuable than I’d hoped.

    What were the dates?

    [teaser3003]

     
    • Jim Randell's avatar

      Jim Randell 5:46 pm on 9 April 2020 Permalink | Reply

      I assumed the dates we are looking for are the years in the 20th century for each coin.

      This Python program runs in 93ms.

      Run: [ @repl.it ]

      from enigma import (primes, subsets, irange, inf, gcd, tau, printf)

primes.extend(100)  # primes up to 100

# check a number is an odd prime
check = lambda n: n > 2 and n in primes

# choose years for the first 2 coins
for (a, b) in subsets(irange(1901, 1999), size=2):
  if not check(gcd(a, b)): continue

  # consider a sequence with n terms
  d = b - a
  for n in primes.irange(3, inf):
    z = a + (n - 1) * d
    if z > 2000: break
    s = list(irange(a, z, step=d))

    # gcd of each pair is an odd prime
    if not all(check(gcd(x, y)) for (x, y) in subsets(s, size=2)): break

    # sum of the number of divisors of each year is an odd prime
    if not check(sum(tau(x) for x in s)): continue

    # output solution
    printf("a={a} b={b}, d={d} -> n={n}: {s}")

      Solution: The dates of the coins were: 1903, 1936, 1969.

      Manually (as suggested by Robert):

      Most number have divisors that come in pairs, so have an even number of divisors. The exception is the square numbers, which have an odd number of divisors (see: Puzzle #08).

      So, in order for the sum of the divisors of the dates to be odd, the list of dates must include an odd number of square numbers. And in the range 1901 – 2000 there is only one square number, 1936. So that must be one of the dates.

      1936 factorises as: (2^4)(11^2), so the other dates must have a GCD with 1936 of 11.

      For numbers less than 1936, we get: 1925, 1903. For numbers greater than 1936 we get: 1947, 1969, 1991.

      Looking for arithmetic sequences containing 1936, with a number of elements that is an odd prime we get:

      d=11: (1925, 1936, 1947); divisor sum = 35
      d=33: (1903, 1936, 1969); divisor sum = 23

      Only the second of these has a divisor sum that is prime, and gcd(1903, 1969) = 11 so this satisfies all the required conditions and gives the answer.

      Like

    • Robert Brown's avatar

      Robert Brown 9:08 pm on 9 April 2020 Permalink | Reply

      The only numbers with odd numbers of factors are perfect squares. There is only one of these in the 20th century, and that date has only has one factor >1 that’s an odd prime. Quite easy to find the answer by inspection.

      Like

  • Unknown's avatar

    Jim Randell 12:29 pm on 9 April 2020 Permalink | Reply
    Tags:   

    Teaser 2862: Algebria’s standard 

    From The Sunday Times, 30th July 2017 [link] [link]

    The Algebrian rectangular flag is highly symbolic. Each of its sides is an even number of inches long and a diagonal divides it into two triangles, one blue and one green, representing its two founding tribes. The length of the diagonal (in inches) is the number of states in Algebria, and the area of the flag (in square inches) is the twentieth century year in which the country obtained independence.

    How many states are there in Algebria, and in which year did the country obtain independence?

    [teaser2862]

     
    • Jim Randell's avatar

      Jim Randell 12:30 pm on 9 April 2020 Permalink | Reply

      If the dimensions of the flag are X and Y (and the diagonal is Z), then the area XY is between 1901 and 2000.

      X and Y are even (say X = 2x, Y = 2y), which limits xy to be between 476 and 500.

      Originally I looked at the possible areas to find viable x, y, z values, but the following Python program uses the [[ pythagorean_triples() ]] generator from the enigma.py library to find x, y, z values that can be scaled up to give an appropriate flag. It runs in 76ms.

      Run: [ @replit ]

      from enigma import (pythagorean_triples, irange, inf, printf)

# consider primitive pythagorean triples
for (x, y, z) in pythagorean_triples(501, primitive=1):
  # and scale up to an appropriate size
  for k in irange(2, inf, step=2):
    (X, Y, Z) = (k * x, k * y, k * z)
    A = X * Y
    if A < 1901: continue
    if A > 2000: break
    printf("X={X} Y={Y} Z={Z} A={A} [x={x} y={y} z={z} k={k}]")

      Solution: There are 68 states in Algebria. It gained independence in 1920.

      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