Updates from Jim Randell Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 8:10 am on 8 October 2019 Permalink | Reply
    Tags:   

    Brainteaser 1730: Not so usual 

    From The Sunday Times, 12th November 1995 [link]

    As usual Eric was early for his morning train. Two express trains of the same length passed through the station in opposite directions, each at its own constant speed. Out of interest Eric timed them and noted that the faster one took 6 seconds to pass him, while the slower one took 8 seconds.

    As soon as they had passed he saw his travelling companion, Len, 30 yards along the platform. In his conversation later, Eric told Len that he had been standing exactly in line with the point at which the fronts of the trains coincided.

    Len then commented that, by coincidence, he had been standing exactly in line with the point at which the ends of the trains coincided. Eric was delighted because he was now able to work out the speeds of the trains.

    How long were the trains?

    This puzzle is included in the book Brainteasers (2002), under the title “Commuter computer”. The puzzle text above is taken from the book.

    [teaser1730]

     
    • Jim Randell's avatar

      Jim Randell 8:11 am on 8 October 2019 Permalink | Reply

      At time 0s the fronts of the two trains (each of length x yards) are in line with Eric.

      At time 6s, the faster train’s end passes Eric. So it is travelling at (x/6) yards/s.

      At time 8s, the slower train’s end passes Eric. So it is travelling at (x/8) yards/s.

      The ends of the trains pass each other (and Len) at time t, when the faster train has travelled its entire length plus 30 yards, and the slower train has travelled its entire length less 30 yards.

      So:

      tx/6 = x + 30
      tx/8 = x − 30

      These equations are solved to give:

      x = 210, t = 48/7

      Solution: The trains were 210 yards long.

      So the faster train is travelling at 35 yards/s (about 72 mph) and the slower train is travelling at 26.25 yards/s (about 54 mph).

      And the ends of the trains passed each other (and Len) 6/7 seconds after the end of the fastest train passed Eric.

      Like

  • Unknown's avatar

    Jim Randell 8:18 am on 7 October 2019 Permalink | Reply
    Tags:   

    Teaser 2837: Back and forth 

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

    George and Martha have a digital 24-hour clock that always displays the time as four digits (e.g. 2:17am displays as 0217). During one lazy weekend George noted two particular times when the four-digit display was palindromic. He calculated the number of minutes from the first of these times to the second and he discovered that the answer was a three-figure palindrome. When he reported all the details to Martha, she commented that the sum of the eleven digits in the three palindromes was also palindromic.

    What were the two palindromic times?

    [teaser2837]

     
    • Jim Randell's avatar

      Jim Randell 8:19 am on 7 October 2019 Permalink | Reply

      This program considers when there is a corresponding minute for each hour to make a list of palindromic times, and then looks at pairs of times from this list that satisfy the remaining conditions.

      It runs in 44ms.

      Run: [ @repl.it ]

      from itertools import product
from enigma import irange, nsplit, concat, printf

# palindrome check
is_palindrome = lambda s: s[::-1] == s

# record palindromic times
ts = list()
for h in irange(0, 23):
  (a, b) = nsplit(h, 2)
  m = 10 * b + a
  # record time (in minutes) and displayed digits
  if m < 60: ts.append((h * 60 + m, (a, b, b, a)))

# now consider two palindromic times (the second time could be the following day)
for ((t1, ds1), (t2, ds2), t3) in product(ts, ts, (0, 1440)):

  # calculate the difference in minutes
  t = t2 + t3 - t1

  # it should be a 3-digit palindrome
  if not(99 < t < 1000): continue
  ds = nsplit(t)
  if not is_palindrome(ds): continue

  # calculate the sum of the digits, it should also be a palindrome
  s = sum(ds1) + sum(ds2) + sum(ds)
  if not is_palindrome(nsplit(s)): continue

  # output a solution
  printf("{ds1} -> {ds2}{x} = {t} minutes, digit sum = {s}", ds1=concat(ds1), ds2=concat(ds2), x=(" (next day)" if t3 else ""))

      Solution: The two times were 1001 and 0110 (the following day).

      The first time is 10:01am on one day (displayed as 1001), the second time is 1:10am the following day (displayed as 0110). The difference between these times is 15 hours and 9 minutes = 909 minutes. And the sum of the digits in 1001, 0110, 909 is 22.

      Like

    • Frits's avatar

      Frits 11:08 am on 22 December 2020 Permalink | Reply

      Slow solution compared to a similar program with enigma.py’s SubstitutedExpression (resp. 600 ms and 15 ms).

      % A Solution in MiniZinc

% time1 ABBA time2 CDDC
var 0..2:A; var 0..5:B; var 0..2:C; var 0..5:D; 
var 1..9:E; var 0..9:F; 
var 1..4:G;
var 0..23: AB = 10*A + B; var 0..59: BA = 10*B + A;
var 0..23: CD = 10*C + D; var 0..59: DC = 10*D + C;
var 101..999: EFE = 101*E + 10*F;
 
% difference in minutes time1 ABBA time2 CDDC
constraint (CD * 60 + DC - (AB * 60 + BA) + 1440) mod 1440 == EFE;              

% sum of the eleven digits in the three palindromes was also palindromic
constraint 2 * ( A + B + C + D + E) + F == G * 11;
 
solve satisfy;
 
output ["Time 1 = " ++ show(A) ++ show(B) ++ ":" ++ show(B) ++ show(A) ++ 
", Time 2 = " ++ show(C) ++ show(D) ++ ":" ++ show(D) ++ show(C) ++
", Difference  = " ++ show(EFE) ++ ", Sum = " ++ show(G * 11)];
 
% Time 1 = 10:01, Time 2 = 01:10, Difference  = 909, Sum = 22
% ----------
% ==========

      Like

  • Unknown's avatar

    Jim Randell 8:58 am on 6 October 2019 Permalink | Reply
    Tags:   

    Brain-Teaser 504: [Scrumps competition] 

    From The Sunday Times, 7th February 1971 [link]

    The inter-house Scrumps competition has just ended at Marlinghurst School. The four houses play each other once and the scoring is on a league basis (win 2, draw 1, lose 0). Arne played Bach in the 1st round, Chopin in the 2nd and Debussy in the 3rd.

    In the 1st round no two houses scored the same number of “scrumps” (a scrump is a sort of goal scored by forcing an opponent through a hole in the wall).

    In the 2nd and 3rd rounds every house scored exactly twice as many scrumps as its current opponent had scored in the previous round.

    Chopin and Debussy tied on points, but a better scrump average (i.e. ratio of scrumps for to scrumps against) gave Debussy the Pergolesi Bowl. Arne and Bach also tried, but Arne’s lower scrump average put them fourth in the final table.

    Although the total number of scrumps scored in the competition fell short of the school record (55) it was higher than last year’s total (44).

    What was:

    (a) Arne’s scrump average?
    (b) the score in the Bach-Chopin match?

    This puzzle was originally published with no title.

    [teaser504]

     
    • Jim Randell's avatar

      Jim Randell 9:00 am on 6 October 2019 Permalink | Reply

      If we know the scores in the first round (say: a, b, c, d scrumps, scored by A, B, C, D respectively), then the scores in each match are:

      (1) A vs B = a – b; C vs D = c – d
      (2) A vs C = 2c – 2a; B vs D = 2d – 2b
      (3) A vs D = 4b – 4c; B cs C = 4a – 4d

      So the total number of scrumps scored is: 7(a + b + c + d).

      And this lies between 44 and 55, so it must be 49, hence a + b + c + d = 7, and the individual totals must be 0, 1, 2, 4 in some order.

      This Python program runs in 86ms.

      from enigma import (compare, subsets, printf)

# points for team X in the X vs Y match, if the score if x - y
pts = lambda x, y: compare(x, y, vs=(0, 1, 2))

# consider possible scores in round 1
for (a1, b1, c1, d1) in subsets((0, 1, 2, 4), size=len, select="P"):
  # calculate the scores in the other rounds
  (a2, b2, c2, d2) = (2 * x for x in (c1, d1, a1, b1))
  (a3, b3, c3, d3) = (2 * x for x in (d2, c2, b2, a2))

  # calculate the points
  A = pts(a1, b1) + pts(a2, c2) + pts(a3, d3)
  B = pts(b1, a1) + pts(b2, d2) + pts(b3, c3)
  C = pts(c1, d1) + pts(c2, a2) + pts(c3, b3)
  D = pts(d1, c1) + pts(d2, b2) + pts(d3, a3)
  # C and D tied on points for 1st/2nd
  # A and B tied on points for 3rd/4th
  if not (C == D and A == B and C > A): continue

  # calculate goals for/against
  (fA, aA) = (a1 + a2 + a3, b1 + c2 + d3)
  (fB, aB) = (b1 + b2 + b3, a1 + d2 + c3)
  (fC, aC) = (c1 + c2 + c3, d1 + a2 + b3)
  (fD, aD) = (d1 + d2 + d3, c1 + b2 + c3)
  # D had a better average than C
  # B had a better average than A
  if not (fD * aC > fC * aD and fB * aA > fA * aB): continue

  # output solution
  printf("(a) {fA}/{aA}; (b) {b3}-{c3}; [a={a1} b={b1} c={c1} d={d1}; A={A} B={B} C={C} D={D}]")

      Solution: (a) Arne’s scrump average was: 12/17 (≈ 0.71); (b) The score in the Bach-Chopin match was 16 – 0.

      The scores in the three rounds were:

      (1) A vs B = 4 – 1; C vs D = 2 – 0
      (2) A vs C = 4 – 8; B vs D = 0 – 2
      (3) A vs D = 4 – 8; B cs C = 16 – 0

      Like

  • Unknown's avatar

    Jim Randell 5:11 pm on 4 October 2019 Permalink | Reply
    Tags:   

    Teaser 2976: Piece of cake 

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

    Using her special recipe, so that each cubic inch of baked cake weighed one ounce, Mam made the cake for my eighth birthday party. It had a regular octagonal flat top and base, and equal square vertical faces, several inches high exactly.

    Not all (but a majority) of the dozen invited pals came to the party. We each had an equal portion of cake (the largest whole number of ounces possible from it, a two-figure number). Mam had the leftover cake. Curiously, if one more or one fewer pal had turned up and our portions had been worked out in the same way, Mam’s leftover would have been the same in each case, but less than she actually got.

    How large, in ounces, was my portion?

    [teaser2976]

     
    • Jim Randell's avatar

      Jim Randell 5:38 pm on 4 October 2019 Permalink | Reply

      12 people were invited, and more than half but not all came, so between 7 and 11. If we include the setter as well the cake is divided into between 8 and 12 integer portions.

      We can ignore the fractional part of the volume as it is always included in the leftover portion of cake. So we just need to consider the integer part of the remaining portion.

      This Python program runs in 87ms.

      Run: [ @repl.it ]

      from enigma import (sqrt, irange, inf, divf, printf)

# area of an octagon with unit sides
a = 2 * (1 + sqrt(2))

# consider the side of the octagon
for x in irange(1, inf):
  # volume of the cake (discarding the fractional part)
  v = int(a * x**3)
  if v < 80: continue
  if v > 1200: break

  # consider the number of portions
  d = dict()
  for k in irange(7, 13):
    # the (2-digit) amount of cake per portion, and remaining amount
    (p, r) = divmod(v, k)
    if 9 < p < 100: d[k] = r

  # find the actual number of portions
  for (k, r) in d.items():
    try:
      (rm, rp) = (d[k - 1], d[k + 1])
    except KeyError:
      continue
    if not (rm < r and rm == rp): continue
    # output solution
    printf("portion = {p} [x={x} k={k}; ({km} -> {rm}+, {k} -> {r}+, {kp} -> {rp}+)]", p=divf(v, k), km=k - 1, kp=k + 1)

      Solution: The portion size was 54 ounces.

      It seems like quite a large portion, but I suppose any 2-digit number of ounces is quite a weighty piece of cake.

      Of the 12 invited guests, 10 attended, meaning that the cake was divided into 11 integer portions.

      The cake has vertical faces that are squares measuring 5 inches along each side, so would require a round cake tin just over 13 inches in diameter to fit it in. It would weigh just over 603.5 ounces (about 17.1 kg).

      We only need to look at the cases where the cake is between 3 and 6 inches high, and there are four possibilities where the leftover portions would have been equal if one fewer or one more guest had attended:

      height = 3″, portions = 8 @ 16 oz, leftover = 2.37 oz; 7 or 9 portions, leftover = 4.37 oz
      height = 4″, portions = 11 @ 28 oz, leftover = 1.02 oz; 10 or 12 portions, leftover = 9.02 oz
      height = 5″, portions = 9 @ 67 oz, leftover = 0.55 oz; 8 or 10 portions, leftover = 3.55 oz
      height = 5″, portions = 11 @ 54 oz, leftover = 9.55 oz; 10 or 12 portions, leftover = 3.55 oz

      Only the last of these has a hypothetical leftover portion that is smaller than the actual leftover portion, so this gives rise to the solution.

      Like

  • Unknown's avatar

    Jim Randell 9:52 am on 4 October 2019 Permalink | Reply
    Tags:   

    Teaser 2840: Signs of the times 

    From The Sunday Times, 26th February 2017 [link] [link]

    I was taking a gentle morning drive along the straight road to Secombe that passes through Firsk. Before reaching Firsk I passed three signposts, each giving the distances to Firsk and to Secombe (to the nearest mile). All six distances displayed were different and, amazingly, all were perfect squares [less than 100].

    What were the two distances given on the first signpost (furthest from Firsk)?

    I have added the “less than 100” condition to reduce ambiguity in the puzzle.

    [teaser2840]

     
    • Jim Randell's avatar

      Jim Randell 9:54 am on 4 October 2019 Permalink | Reply

      When this puzzle was first published there was some confusion over the correct interpretation. I have added the condition to require the squares to be less than 100 to eliminate multiple solutions.

      The distances on the signposts are rounded to the nearest mile. This Python program uses intervals to find viable solutions. It runs in 47ms.

      Run: [ @repl.it ]

      from enigma import (irange, isqrt, subsets, arg, printf)

# limit to numbers on signs
M = arg(100, 0, int)
printf("[M={M}]")

# possible squares that can appear on the signs
squares = list(i * i for i in irange(1, isqrt(M - 1)))

# possible distances for three signs (in order)
signs = subsets(squares, size=3)

# combine lower/upper bounds into an interval
def interval(v, *vs):
  (l, u) = v
  for (l1, u1) in vs:
    (l, u) = (max(l, l1), min(u, u1))
  return (l, u)

# choose the distances to F and S on the signs
for ((f1, f2, f3), (s1, s2, s3)) in subsets(signs, size=2):

  # check the distances are all different
  if len({f1, f2, f3, s1, s2, s3}) < 6: continue

  # calculate the position of S
  (sl, su) = interval(
    (s1 - f1 - 1, s1 - f1 + 1),
    (s2 - f2 - 1, s2 - f2 + 1),
    (s3 - f3 - 1, s3 - f3 + 1),
  )

  # is it feasible?
  if 0 < sl < su:
    printf("signs = ({f1} {s1}) ({f2} {s2}) ({f3} {s3}), F -> S = ({sl}, {su})")

      Solution: The distances on the first signpost encountered were 49 miles (to Firsk) and 64 miles (to Secombe).

      The distance between F and S is between 15 and 16 miles.

      So if, for example, the distance between F and S was 15.2 miles, and the signposts are at distances of 1.2 miles, 9.4 miles and 48.6 miles from F, then they would read:

      1.2 miles from F, 16.4 miles from S: “F 1, S 16”
      9.4 miles from F, 24.6 miles from S: “F 9, S 25”
      48.6 miles from F, 63.8 miles from S: “F 49, S 64”

      Without the restriction on the squares there are further solutions that use distances of 100 and 121 (and higher values):

      signs = (4, 25) (16, 36) (100, 121); F to S = 20 – 21 miles
      signs = (9, 49) (25, 64) (81, 121); F to S = 39 – 40 miles

      And with even higher values we can solve the puzzle using exact distances:

      signs = (1, 49) (16, 64) (121, 169); F to S = 48 miles

      Like

  • Unknown's avatar

    Jim Randell 3:51 pm on 3 October 2019 Permalink | Reply
    Tags:   

    Brainteaser 1724: Like a lamb 

    From The Sunday Times, 1st October 1995 [link]

    Mary had a little lamb,
    Its fleece was white as snow
    And everywhere that Mary went
    The lamb was sure to go.

    It followed her to school one day,
    But found the maths a bore,
    For lambs, you see, do all their counting
    On a scale of four.

    Thus when a lamb writes two times two
    Its answer looks like 10,
    While our 10 written by a lamb
    Is double-2 again!

    It much distressed them both to find
    They never could agree
    On how to write down any
    Of the numbers after three.

    At last they hit on some for which
    The lamb would only need
    Two figures placed in front of Mary’s,
    Then they were agreed.

    Which two figures?

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

    [teaser1724]

     
    • Jim Randell's avatar

      Jim Randell 3:52 pm on 3 October 2019 Permalink | Reply

      We are to infer from the puzzle text that the lamb counts using base 4, with the standard symbols 0, 1, 2, 3.

      So we need to find numbers in base 4 whose representation in base 10 is the same as the representation in base 4 but with the leftmost 2 digits removed.

      This Python program runs in 221ms.

      Run: [ @repl.it ]

      from enigma import irange, inf, nsplit, nconcat, printf

# base 4 digits for number n
base4 = lambda n: nsplit(n, base=4)

# consider k-digit base 4 numbers, read as base 10 numbers, they need to be (k + 2) digits
for k in irange(1, inf):
  # smallest k-digit base 4 number read as a base 10 number
  if len(base4(10 ** (k - 1))) > k + 2: break
  # largest k-digit base 4 number read as a base 10 number
  if len(base4((10 ** k - 1) // 3)) < k + 2: continue

  # consider possible (k + 2) digit base 4 numbers 
  for n in irange(4 ** (k + 1), 4 ** (k + 2) - 1):
    # represented in base 4
    ds = base4(n)
    # does removing the first two digits give the base 10 representation?
    if nconcat(ds[2:]) == n:
      printf("prefix = {p} [k={k}: {ds} (base 4) = {n} (base 10)]", p=nconcat(ds[:2]), ds=nconcat(ds))

      Solution: The 2-digit prefix is 30.

      The only viable numbers are:

      303320 (base 4) = 3320 (base 10)
      303321 (base 4) = 3321 (base 10)
      303322 (base 4) = 3322 (base 10)
      303323 (base 4) = 3323 (base 10)

      The program considers base 4 numbers that are 5-, 6- and 7-digits long, and looks for corresponding 3-, 4- and 5- digit base 10 numbers.

      Like

  • Unknown's avatar

    Jim Randell 9:11 am on 1 October 2019 Permalink | Reply
    Tags:   

    Brain-Teaser 503: [Exam marks] 

    From The Sunday Times, 31st January 1971 [link]

    When the headmaster came to look up Charley’s marks in the previous term’s exam in Physics and Chemistry, sat by the Science pupils of the 6th (Al, Bill, Charley, Dan, Ed, Frank and George) he found that ink had been spilt on the results sheet and only the following was legible:

    He remembered that the pupils finished in alphabetical order in total marks; that there were no ties in either subject, or overall; and that no pupil occupied the same place in each subject.

    All that he could remember about Charley’s results was that he was placed higher in Chemistry than in Physics.

    What were Charley’s marks in each subject?

    This puzzle was originally published with no title.

    [teaser503]

     
    • Jim Randell's avatar

      Jim Randell 9:13 am on 1 October 2019 Permalink | Reply

      I assumed the exams are marked out of 100, and only whole numbers of marks are awarded.

      I made a MiniZinc model for the puzzle. It finds a single solution in 121ms.

      %#! minizinc --solver chuffed --all

include "globals.mzn";

% label the boys
set of int: Boys = 1..7;
int: A = 1;
int: B = 2;
int: C = 3;
int: D = 4;
int: E = 5;
int: F = 6;
int: G = 7;

% places for each boy in each subject
array [Boys] of var 1..7: pPh;
array [Boys] of var 1..7: pCh;

constraint all_different(pPh);
constraint all_different(pCh);

% marks for each boy in each subject
array [Boys] of var 0..100: mPh;
array [Boys] of var 0..100: mCh;

constraint forall (x, y in Boys where x != y) ((pPh[x] < pPh[y]) -> (mPh[x] > mPh[y]));
constraint forall (x, y in Boys where x != y) ((pCh[x] < pCh[y]) -> (mCh[x] > mCh[y]));

% given values
constraint pPh[A] = 5;
constraint pCh[B] = 2;
constraint pPh[E] = 3;
constraint pCh[G] = 5;
constraint mPh[D] = 70;
constraint mCh[F] = 67;
constraint mPh[G] = 71;

% total marks is 1023
constraint sum (x in Boys) (mCh[x] + mPh[x]) = 1023;

% "the pupils finished in alphabetical order by total marks"
constraint decreasing (x in Boys) (mPh[x] + mCh[x]);

% "there were no ties in either subject, or overall"
constraint all_different(mPh);
constraint all_different(mCh);
constraint all_different (x in Boys) (mPh[x] + mCh[x]);

% "no pupil occupied the same place in both subjects"
constraint forall (x in Boys) (pPh[x] != pCh[x]);

% "C placed higher in Chemistry than Physics"
constraint pCh[C] < pPh[C];

solve satisfy;

      Solution: Charley got 73% in Physics and 75% in Chemistry.

      Here is the complete table:

      Like

  • Unknown's avatar

    Jim Randell 11:58 am on 30 September 2019 Permalink | Reply
    Tags:   

    Teaser 2842: The best policy 

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

    George and Martha’s home insurance policy number is a six-figure number consisting of six different digits. George commented that the number was divisible by each of its digits and also by the sum of its digits. Martha then added that, if you deleted the left-hand digit, then you were left with a five-figure number divisible by the sum of its five digits. If you then deleted that number’s left-hand digit, then you were left with a four-figure number divisible by the sum of its four digits, and so on all the way down.

    What is their policy number?

    [teaser2842]

     
    • Jim Randell's avatar

      Jim Randell 11:59 am on 30 September 2019 Permalink | Reply

      Using copy and paste we can easily make the expressions to feed to the [[ SubstitutedExpression() ]] solver from the enigma.py library.

      The following run file executes in 70ms. (Internal run time of the generated program is 132us).

      Run: [ @replit ]

      #! python -m enigma -rr

# suppose the number is: ABCDEF

SubstitutedExpression

--digits="1-9"
--answer="ABCDEF"

"ABCDEF % A = 0"
"ABCDEF % B = 0"
"ABCDEF % C = 0"
"ABCDEF % D = 0"
"ABCDEF % E = 0"
"ABCDEF % F = 0"
"ABCDEF % (A + B + C + D + E + F) = 0"
"BCDEF % (B + C + D + E + F) = 0"
"CDEF % (C + D + E + F) = 0"
"DEF % (D + E + F) = 0"
"EF % (E + F) = 0"

--template="ABCDEF"

      Solution: The policy number is 384912.

      I also coded up a custom program for this particular problem.

      It runs in 34ms (with an internal run time of 152µs). So the program produced by the [[ SubstitutedExpression ]] solver executes faster than my custom program:

      # permissible digits (0 is disallowed as n % 0 is undefined)
digits = range(1, 10)

# find <k> digit numbers such that each suffix is divisible by the sum
# of the digits in that suffix and the number is divisible by each of
# it's digits individually.
def solve(k, n=0, s=0, ds=[]):
  # are we done?
  if k == 0:
    # check for divisibility by all the digits individually
    if all(n % d == 0 for d in ds):
      print(n)
  else:
    # add a new digit to the front
    for d in digits:
      if d not in ds:
        ds1 = [d] + ds
        n1 = n + d * 10**len(ds)
        s1 = s + d
        if n1 % s1 == 0:
          # and solve for the remaining digits
          solve(k - 1, n1, s1, ds1)

# we need 6 digit numbers
solve(6)

      We can however use this program to investigate numbers of different lengths, and we find that 6 is the maximum possible length.

      Like

  • Unknown's avatar

    Jim Randell 5:04 pm on 29 September 2019 Permalink | Reply
    Tags:   

    Brainteaser 1721: Prime leaps 

    From The Sunday Times, 10th September 1995 [link]

    The history-cum-maths teacher asked the class to name some years which the knew from history lessons. Johnny named 1066, the Battle of Hastings, and 1939, the outbreak of the Second World War. The teacher then asked him to calculate the difference between the two and Johnny got the correct answer of 873.

    The teacher then asked Johnny if this difference was prime and Johnny answered correctly that it was not because, for example, it was divisible by three.

    The teacher then asked the class to find the longest list of years they could from 0, 1, 2, …, 1999, 2000 so that for any two numbers in the list their difference was not prime.

    Which numbers are in the longest such list?

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

    [teaser1721]

     
    • Jim Randell's avatar

      Jim Randell 5:05 pm on 29 September 2019 Permalink | Reply

      First, lets treat the list as a sequence of consecutive integers starting at 0. (We’re only interested in differences, so it doesn’t really matter where we start).

      If we consider the set of numbers (0, 4, 8, 12, 16, …) (i.e. the multiples of 4) then we see the difference between any two numbers is also a multiple of 4, and hence not prime. This allows us to select ⌈n / 4⌉ numbers from a sequence of n numbers.

      And this is the best we can manage. Every segment of size 4 has 1 number (and if there is a shorter segment left over from chopping the sequence into fours, then that also has one number).

      To do better we would have to have a segment of size 4 with (at least) two numbers in it.

      We can’t have … 0 _ 2 _ … or … 0 _ _ 3 … as these have a difference of 2 and 3 respectively, so the only possible segment is … 0 1 _ _ ….

      But any numbers that differ by 1 have to be followed by (or preceded by) 7 gaps:

      So the best we could manage is 2 numbers out of every 9, which is worse than 1 out of every 4.

      So presented with a sequence of 2001 numbers the best we can manage is ⌈2001 / 4⌉ = 501 numbers: (0, 4, 8, 12, 16, …, 1992, 1996, 2000).

      Solution: The longest list contains all exact multiples of 4.

      Considered as years (ignoring the fact that there was no year 0), most of the numbers represent leap years, hence the title of the puzzle.

      Like

    • Lise Andreasen's avatar

      Lise Andreasen 12:18 pm on 5 August 2024 Permalink | Reply

      Elegant.

      Like

  • Unknown's avatar

    Jim Randell 6:14 pm on 27 September 2019 Permalink | Reply
    Tags:   

    Teaser 2975: Hollow cube land 

    From The Sunday Times, 29th September 2019 [link] [link]

    I have a large box of toy building bricks. The bricks are all cubes (the same size), and can be pushed together then dismantled.

    I decided to build the largest cube possible by leaving out all the interior bricks. When my hollow cube was finished I had two bricks left over. I put all the bricks back in the box and gave it to my two children. Each in turn was able to use every brick in the box to construct two hollow cubes, again with all interior bricks removed. Their cubes were all different sizes.

    This would not have been possible had the box contained any fewer bricks.

    How many bricks were in the box?

    [teaser2975]

     
    • Jim Randell's avatar

      Jim Randell 6:57 pm on 27 September 2019 Permalink | Reply

      For n ≥ 2 we can calculate the “hollow cube” number as:

      h(n) = n³ − (n − 2)³ = 6(n − 1)² + 2

      We can then check for values where it is possible to make h(n) + 2 from the sum of two smaller h() numbers, in (at least) two different ways.

      This Python 3 program runs in 81ms.

      Run: [ @replit ]

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

# "hollow cube" numbers (n >= 2)
h = lambda n: 6 * (n - 1)**2 + 2

# solve the puzzle using formula for h(n)
def solve():
  d = dict()
  for n in irange(3, inf):
    # calculate h(n)
    x = h(n)
    printf("[h({n}) = {x}]")
    # can x + 2 be made from the sum of 2 smaller h numbers?
    ss = list(s for s in subsets(d.keys(), size=2) if sum(d[k] for k in s) == x + 2)
    # in 2 different ways?
    if len(ss) > 1:
      printf("t={t} [n={n} x={x}, ss={ss}]", t=x + 2)
      return
    # add the number to the list
    d[n] = x

solve()

      Solution: There were 3754 bricks in the box.

      The setter was able to build a hollow cube measuring 26 units along each side, using up 3752 of the bricks (leaving 2 unused).

      One child produced cubes measuring 8 and 25 units along each side, using up 296 + 3458 = 3754 bricks.

      The other child produced cubes measuring 16 and 21 units along each side, using up 1352 + 2402 = 3754 bricks.

      Analytically:

      We are looking for numbers p, q such that:

      6(n − 1)² + 4 = 6(p − 1)² + 2 + 6(q − 1)² + 2
      (n − 1)² = (p − 1)² + (q − 1)²

      So we can look for Pythagorean triples that share a hypotenuse. The smallest is:

      25² = 7² + 24² = 15² + 20²

      from which we see the setter’s cube measured 26 units, and the children’s were (8, 25) units and (16, 21) units.

      For more than 2 children the smallest solution is with 25354 bricks. The setter built a cube measuring 66 units, and there can be up to 4 children with cubes measuring (17, 64), (26, 61), (34, 57), (40, 53) units. Corresponding to:

      65² = 16² + 63² = 25² + 60² = 33² + 56² = 39² + 52²

      Like

  • Unknown's avatar

    Jim Randell 10:54 am on 27 September 2019 Permalink | Reply
    Tags: ,   

    Brain-Teaser 502: [Duplicated leaves] 

    From The Sunday Times, 17th January 1971 [link]

    A publisher friend of mine told me the following improbable story. He dreamt that on his shelves he had a collection of twelve books of the same edition of the same title. The curious thing about these books was this:

    The book, as published, ran to 300 pages, but eleven of the books on his shelves had each been bound with duplicate leaves inserted. The number of leaves thus duplicated was different in each volume, all except two being even numbers. They went in ascending order from the book on the left (Volume I), the highest being twenty extra leaves in Volume XI.

    The end book on the right (Volume XII) had 200 pages missing. By a strange coincidence, the duplicated sections from the other volumes exactly filled these gaps. In the reconstituted Volume XII the middle pages (143 to 158) came from the middle volume of the faulty books, while half the duplicated pages came before these and an equal number in the latter half of the volume.

    How many pages were duplicated in Volume IV?

    This puzzle was originally published with no title.

    [teaser502]

     
    • Jim Randell's avatar

      Jim Randell 10:55 am on 27 September 2019 Permalink | Reply

      Assuming that 1 “leaf” consists of 2 “pages” (the “front” (odd numbered) page and “back” (even numbered) page).

      We know vol XII has 200 missing pages (= 100 missing leaves), and each is accounted for (exactly) by the duplicate leaves in vols I – XI.

      Of the 100 duplicate leaves vol XI has 20 of them, so the remaining volumes have 80 duplicate leaves between them.

      This Python program examines this scenario. It runs in 104ms.

      from enigma import (irange, printf)

# decompose total t into k different ascending numbers, min value m
def decompose(t, k, m=1, s=[]):
  if k == 1:
    if not (t < m):
      yield s + [t]
  else:
    for x in irange(m, t - (k - 1) * m):
      yield from decompose(t - x, k - 1, x + 1, s + [x])

# there are 80 extra leaves amongst vols I - X
for vs in decompose(80, 10, 1):
  # vol VI has (at least) 8 extra leaves
  if vs[5] < 8: continue
  # and vol XI has exactly 20 extra leaves
  if vs[-1] > 19: continue
  vs.append(20)

  # exactly 2 are odd
  if not (sum(x % 2 == 1 for x in vs) == 2): continue

  # output the number of duplicate leaves for each volume
  printf("{vs}")

      This seems to give 4 possibilities for the numbers of duplicate leaves:

      [1, 2, 3, 4, 6, 8, 10, 12, 16, 18, 20]
      [1, 2, 4, 5, 6, 8, 10, 12, 14, 18, 20]
      [1, 2, 4, 6, 7, 8, 10, 12, 14, 16, 20]
      [2, 3, 4, 5, 6, 8, 10, 12, 14, 16, 20]

      If we’d been asked for the number of duplicate leaves (or pages) in vols VII or VIII there would be a unique solution (10 leaves for vol VII; 12 leaves for vol VIII), but not for vol IV (we have options for 4, 5, 6 duplicate leaves).

      So we need to try an untangle the condition:

      “In the reconstituted Volume XII the middle pages (143 to 158) came from the middle volume of the faulty books, while half the duplicated pages came before these and an equal number in the latter half of the volume.”

      So vol VI must have (at least) 8 duplicate leaves. Which it does in each of our possibilities, so that doesn’t help us.

      The rest of it either doesn’t make sense, or doesn’t seem to be useful.

      “half the duplicate pages” is 50 leaves, so 50 of the duplicate leaves end up making up some of pages 1-142 of vol XII.

      It then goes on to say “and an equal number” (presumably another 50 leaves) “in the latter half of the volume” (presumably pages 151-300), which seems to account for 104 of the 100 missing leaves. So that can’t be right.

      Perhaps it meant “…half the remaining duplicated pages…”, but that just tells us that 46 of the duplicate leaves are used for pages 1-142, and the other 46 are used for pages 159-300, which as we have 92 duplicate leaves to distribute doesn’t seem to help either.

      Another possibility is to ignore the final condition, and take a strict reading of “eleven of the books on his shelves had each been bound with duplicate leaves inserted”, to mean that each book has at least 2 duplicate leaves. This removes the first 3 of the possibilities, leaving:

      I→2, II→3, III→4, IV→5, V→6, VI→8, VII→10, VIII→12, IX→14, X→16, XI→20

      As the only remaining solution, so vol IV has 5 duplicate leaves, and hence 10 duplicate pages. (Which is the published solution).

      We can modify line 13 of the program to [[ decompose(80, 10, 2) ]] to get this single solution.

      Like

  • Unknown's avatar

    Jim Randell 8:46 am on 24 September 2019 Permalink | Reply
    Tags:   

    Teaser 2848: Coffee breaks 

    From The Sunday Times, 23rd April 2017 [link] [link]

    The roads on our estate form a grid consisting of three roads running west-to-east with a number of other roads running south-to-north from the bottom road across the middle road to the top road. I live at the south-west corner of the grid and I work at the north-east corner. Each day I walk to work by one of the various shortest possible routes along the roads: there is a two-figure number of such routes. One quarter of my possible routes pass Caffee Claudius, and one quarter of my routes pass Spenda Coffee (which are on different roads).

    How many of my routes pass both the coffee shops?

    [teaser2848]

     
    • Jim Randell's avatar

      Jim Randell 8:47 am on 24 September 2019 Permalink | Reply

      I considered coffee shops that are located somewhere on the roads between the intersection points of the grid. (If we consider coffee shops at the intersections there are no solutions where the two shops are not on the same road).

      This Python 3 program constructively generates the possible paths in a grid, and then looks for segments of the paths that appear in exactly one quarter of a possible paths. We then select two of these segments for the positions of the coffee shops and count how many paths include both the segments. It runs in 76ms.

      Run: [ @repl.it ]

      from enigma import (irange, inf, div, multiset, tuples, subsets, contains, seq_all_same, printf)

# generate paths from (0, 0) to (x, y)
def paths(x, y, s=[]):
  if x == y == 0:
    yield [(0, 0)] + s
  else:
    if x > 0: yield from paths(x - 1, y, [(x, y)] + s)
    if y > 0: yield from paths(x, y - 1, [(x, y)] + s)

y = 2
for x in irange(1, inf):

  # the total number of different routes
  ps = list(paths(x, y))
  t = len(ps) # t = C(x + y, y)
  if t < 10: continue
  if t > 99: break

  q = div(t, 4)
  if q is None: continue

  printf("[x={x} y={y}] t={t}, q={q}")

  # count the number of paths that use each of the line segments on the grid
  segs = multiset.from_seq(*(tuples(p, 2) for p in ps))

  # find segments that appear q times
  qs = list(k for (k, v) in segs.items() if v == q)
  printf("-> qs={qs}")

  # choose two of them
  for (q1, q2) in subsets(qs, size=2):
    # that don't lie on the same road
    if any(seq_all_same(x) for x in zip(*(q1 + q2))): continue
    # and count the paths that include both segments
    n = sum((contains(p, q1) != -1 and contains(p, q2) != -1) for p in ps)
    printf("-> n={n} [q1={q1} q2={q2}] (*** SOLUTION ***)")

      Solution: Only one route passes both coffee shops.

      There are 7 N-S roads.

      (The coffee shops are indicated by stars. The single route is shown in red).

      The number of routes on an x by y grid is given by: C(x + y, x), or C(x + y, y).

      In this case y = 2, so x must be in the the range 3 … 12 in order for the number of routes to be a 2-digit number.

      For the number of routes to be exactly divisible by 4 we must have x = 6 or 7.

      If x = 7 the number of routes is 36, and there are no segments that are used in exactly 36/4 = 9 shortest routes.

      If x = 6 the number of routes is 28, and only the two vertical segments shown in red on the diagram have 28/4 = 7 shortest routes using them. So these give the locations of the coffee shops, and there is only one shortest route that uses both of them together.

      If we require the coffee shops to be at intersections, then we find the only possible positions are shops at (0, 1) and (6, 1), but these both lie on the y = 1 road, so does not provide a viable solution. Although potentially it does allow a solution where one of the coffee shops is at one of these intersections, and the other one is on a segment between intersections, but it doesn’t change the answer to the puzzle.

      The restriction on there being a 2-digit number of shortest paths limits the range of x to a small number of values, but even without this restriction I didn’t find any further candidate solutions (with segments lying on one quarter of the total number of paths) for x up to 5000.

      However there are further candidate locations if the coffee shops are allowed on the intersections. For example with x = 47 we could have shops at (6, 1), (41, 1), and with x = 286 we could have shops at (41, 1), (245, 1), and with x = 1679 we could have shops at (245, 1), (1434, 1). However when choosing 2 shops these all fall foul of the condition that that the shops be on different roads, so don’t provide viable solutions.

      Like

      • Jim Randell's avatar

        Jim Randell 4:49 pm on 24 September 2019 Permalink | Reply

        Here is a modified version of the program that allows the coffee shops to be on the segments between intersections or at the intersections themselves. Instead of constructing the paths it uses the formula C(x + y, x) to count the number of paths. The answer to the puzzle is the same, however.

        Run: [ @repl.it ]

        from enigma import (cproduct, multiply, C, irange, inf, div, subsets, seq_all_same, printf)

# count the number of paths along a sequence of segments
paths = lambda *ps: multiply(C(x + y, x) for (x, y) in ps)

# grid segment between two points
def seg(p, q):
  ((px, py), (qx, qy)) = (p, q)
  return (qx - px, qy - py)

y = 2
for x in irange(1, inf):

  # the total number of different routes
  t = paths((x, y))
  if t < 10: continue
  if t > 99: break

  q = div(t, 4)
  if q is None: continue

  printf("[x={x} y={y}] t={t}, q={q}")

  # count the number of paths that use each of the line segments and nodes on the grid
  qs = list()
  for (i, j) in cproduct([irange(0, x), irange(0, 2)]):
    # line segment N
    if j < 2 and paths((i, j), seg((i, j + 1), (x, y))) == q:
      qs.append(((i, j), (i, j + 1)))
    # line segment E
    if i < x and paths((i, j), seg((i + 1, j), (x, y))) == q:
      qs.append(((i, j), (i + 1, j)))
    # node
    if paths((i, j), seg((i, j), (x, y))) == q:
      qs.append(((i, j),))

  printf("-> qs={qs}")

  # choose two of them
  for (q1, q2) in subsets(qs, size=2):
    # that don't lie on the same road
    if any(seq_all_same(x) for x in zip(*(q1 + q2))): continue
    # and count the paths that include both segments
    n = paths(q1[0], seg(q1[-1], q2[0]), seg(q2[-1], (x, y)))
    printf("-> n={n} [q1={q1} q2={q2}] (*** SOLUTION ***)")

        One shop is on the line (0, 0) – (0, 1) and the other is on the line (6, 1) – (6, 2), all locations are acceptable apart from (0, 1) together with (6, 1), as then the shops are both on the y = 1 road.

        Like

  • Unknown's avatar

    Jim Randell 12:05 am on 21 September 2019 Permalink | Reply
    Tags:   

    Teaser 2974: Flockbuster 

    From The Sunday Times, 22nd September 2019 [link] [link]

    Wu, Xi, Yo and Ze had different two-figure numbers of sheep and kept them in a walled field divided by fences into a fold each. Maths whizz, Wu, with the largest flock, noticed that together her flock and Ze’s equalled Xi’s and Yo’s combined; and that, as a fraction, the ratio of Yo’s flock to Xi’s had consecutive upper and lower numbers (e.g. 3/4), whereas her flock to Xi’s ratio had those numbers swapped over (e.g. 4/3).

    Overnight, storm-damaged fences led to the same number of sheep in each fold. Wu’s old maths teacher, told just this number and the above relationships, couldn’t be certain how many sheep Wu owned (which would have been true, also, if he’d been told either fraction instead).

    How many sheep did Wu own?

    [teaser2974]

     
    • Jim Randell's avatar

      Jim Randell 12:07 am on 21 September 2019 Permalink | Reply

      This Python program considers possible values for X and Y, from which the values of W and Z (and k) can be derived. It runs in 88ms.

      Run: [ @replit ]

      from enigma import (irange, subsets, div, filter_unique, unpack, intersect, printf)

# collect possible solutions
rs = list()

# choose X and Y (Y < X)
for (Y, X) in subsets(irange(10, 99), size=2):

  # Y / X can be expressed as k / (k + 1)
  k = div(Y, X - Y) 
  if k is None: continue

  # X / W can be expressed as (k + 1) / k
  W = div((k + 1) * X, k)
  if W is None or not (X < W < 100): continue

  # W + Z = X + Y
  Z = X + Y - W
  if (not 9 < Z < W) or Z == Y or Z == X: continue

  # total number of sheep must be divisible by 4
  t = W + X + Y + Z
  if t % 4 != 0: continue

  rs.append((W, X, Y, Z, k, t))
  printf("[Y={Y} X={X}, k={k}, W={W} Z={Z}, t={t}]")

# the total is ambiguous
(_, rs1) = filter_unique(rs, unpack(lambda W, X, Y, Z, k, t: t))

# the fraction is also ambiguous
(_, rs2) = filter_unique(rs, unpack(lambda W, X, Y, Z, k, t: k))

# but together these tell us W
rs = intersect((rs1, rs2))
ws = set(W for (W, X, Y, Z, k, t) in rs)
printf("W = {ws} [{rs}]")

      Solution: Wu owns 99 sheep.

      There are 12 possible values for W, X, Y, Z that fit the description. Here they are are by the total number of sheep, and the value of k, the numerator of the fraction:

      [ 1] t=72 k=4, W=25 Z=11, X=20 Y=16
      [ 2] t=84 k=3, W=32 Z=10, X=24 Y=18
      [ 3] t=144 k=4, W=50 Z=22, X=40 Y=32
      [ 4] t=156 k=6, W=49 Z=29, X=42 Y=36
      [ 5] t=168 k=3, W=64 Z=20, X=48 Y=36
      [ 6] t=200 k=2, W=90 Z=10, X=60 Y=40
      [ 7] t=216 k=4, W=75 Z=33, X=60 Y=48
      [ 8] t=220 k=5, W=72 Z=38, X=60 Y=50
      [ 9] t=220 k=2, W=99 Z=11, X=66 Y=44
      [10] t=252 k=3, W=96 Z=30, X=72 Y=54
      [11] t=272 k=8, W=81 Z=55, X=72 Y=64
      [12] t=312 k=6, W=98 Z=58, X=84 Y=72

      We see that the total number of sheep is only ambiguous when t = 220 (cases 8, 9). So the teacher can narrow down the situation to one of those two cases (all other values of t uniquely identify a single case).

      And the value of k is ambiguous when:

      k = 2 (cases 6, 9)
      k = 3 (cases 2, 5, 10)
      k = 4 (case 1, 3, 7)
      k = 6 (cases 4, 12)

      And case 9 is the only one common to both scenarios so this is the required solution: W=99 Z=11, X=66 Y=44.

      So W + Z = X + Y = 110 and Y/X = X/W = 2/3.

      Like

      • Jim Randell's avatar

        Jim Randell 3:06 pm on 22 September 2019 Permalink | Reply

        Here’s a slightly shorter program that considers values for X, and derives possible values for W, Y, Z, k, t from that.

        Since we know:

        k / (k + 1) = Y / X = X / W

        We also know that:

        X² = Y.W

        So Y and W are divisor pairs of X², and Y < X < W.

        We can then also calculate Z and k and check they satisfy the remaining conditions.

        Run: [ @replit ]

        from enigma import (irange, divisors_pairs, div, filter_unique, unpack, intersect, printf)

# collect possible solutions
rs = list()

# consider 2-digit values for X
for X in irange(10, 99):

  # compute W, Y, Z, k, t
  for (Y, W) in divisors_pairs(X, 2):
    if not (9 < Y < X < W < 100): continue
    Z = X + Y - W
    if not (9 < Z): continue
    k = div(Y, X - Y)
    if k is None: continue
    t = X + Y + W + Z
    if t % 4 != 0: continue

    rs.append((W, X, Y, Z, k, t))
    printf("[X={X}, Y={Y} W={W} Z={Z}, k={k} t={t}]")

# the total is ambiguous
(_, rs1) = filter_unique(rs, unpack(lambda W, X, Y, Z, k, t: t))

# the fraction is also ambiguous
(_, rs2) = filter_unique(rs, unpack(lambda W, X, Y, Z, k, t: k))

# but together these tell us W
rs = intersect((rs1, rs2))
ws = set(W for (W, X, Y, Z, k, t) in rs)
printf("W = {ws} [{rs}]")

        Like

  • Unknown's avatar

    Jim Randell 11:46 am on 20 September 2019 Permalink | Reply
    Tags:   

    Teaser 2871: Five-card trick 

    From The Sunday Times, 1st October 2017 [link] [link]

    I have five cards with a different digit from 1 to 5 on each. I shuffled them and placed them face-down in a row to form a concealed five-figure number. Then I invited each of my six nephews to choose a number less than fifty and they happened to choose six consecutive numbers. Then I explained that there would be a prize for anyone whose number was a divisor of the concealed number. No-one was certain to win but they were all in with a chance until I revealed the final digit of the number, which ruled out two of them from winning. Then I revealed the first digit and that ruled two more out. Then I revealed the whole number and just one nephew won a prize.

    What was the concealed number?

    [teaser2871]

     
    • Jim Randell's avatar

      Jim Randell 11:48 am on 20 September 2019 Permalink | Reply

      This is a similar puzzle to Teaser 2891 (also set by Stephen Hogg), but I think this one is easier to solve.

      This Python program runs in 52ms.

      Run: [ @repl.it ]

      from enigma import (defaultdict, irange, subsets, nconcat, flattened, tuples, printf)
 
# possible divisors
divisors = list(irange(1, 49))
 
# possible numbers made by the cards
# record numbers by the divisors from 1 to 49, final digit, first digit
r = defaultdict(lambda: defaultdict(lambda: defaultdict(set)))
t = 0
for s in subsets(irange(1, 5), size=len, select="P"):
  n = nconcat(s)
  t += 1
  for d in divisors:
    if n % d == 0:
      r[d][s[-1]][s[0]].add(n)
 
# how to flatten r (a nested structure of dicts and sets)
def flatten_test(x):
  if isinstance(x, dict): return x.values()
  if isinstance(x, set): return sorted(x)
 
# extract the leaf values from the structure
def values(x):
  return list(flattened(x, fn=flatten_test))
 
# eliminate divisors that contain all t values ("no-one was certain to win")
# or have no values ("they all have a chance")
ds = list(d for d in divisors if 0 < len(values(r[d])) < t)
 
# choose the 6 numbers for the nephews
for ns in tuples(ds, 6):
  # the numbers must be consecutive
  if ns[-1] != ns[0] + 5: continue
 
  # revealing the final digit eliminates two of them
  for d5 in irange(1, 5):
    e1 = set(n for n in ns if not values(r[n][d5]))
    if len(e1) != 2: continue
 
    # the first digit eliminates two more of them
    for d1 in irange(1, 5):
      if d1 == d5: continue
      e2 = set(n for n in ns if n not in e1 and not values(r[n][d5][d1]))
      if len(e2) != 2: continue
 
      # the whole number works for just one of the remaining nephews
      rs = set(ns).difference(e1, e2)
      for x in set().union(*(values(r[n][d5][d1]) for n in rs)):
        # find the winners
        ws = set(n for n in rs if x in values(r[n][d5][d1]))
        if len(ws) == 1:
          printf("cards = {x} [ns={ns}, e1={e1}, e2={e2}, ws={ws}]")

      Solution: The concealed number is 15324.

      “no-one was certain to win”, eliminates divisors 1 and 3.

      “but they all have a chance”, eliminates: 9, 10, 11, 18, 20, 22, 27, 30, 33, 36, 40, 41, 44, 45.

      Which means the only set of six consecutive possible divisors remaining is: 12, 13, 14, 15, 16, 17.

      Revealing the final digit eliminates 2 of the nephews, so the final digit must be 2 or 4 (if it were 1, 3, 5 at least the three nephews who had chosen even divisors would be eliminated), but if it were 2 only 15 would be eliminated. So the final digit is 4, and the nephews who chose 15 and 16 are eliminated.

      Then the first digit is revealed, and this eliminates another two nephews. So the first digit is 1, which eliminates 13 and 17 as possible divisors (2 eliminates 12, 13, 14; 3 eliminates 13, 14, 17; 5 eliminates 17).

      So the number is 1???4. Only 15324 has one winner – the nephew who chose 12. The other possibility is 13524, which has 12 and 14 as winners.

      Like

  • Unknown's avatar

    Jim Randell 9:52 am on 19 September 2019 Permalink | Reply
    Tags:   

    Brain-Teaser 501: [Missing weight] 

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

    The grain retailer had with his scales a set comprising the smallest number of weights which, use in any way required, enabled him to weigh loads of every exact number of kilos from 1 to 40 kilos.

    One day he mislaid one of his weights and, remembering that the rival shop next door had had an identical set which was no longer in use, he asked to borrow it.

    That set too, however, proved to have one of its weights missing, and so it turned out that, even with all the surviving weights in both sets at his disposal, he could weigh only 25 different loads within the required range of 1-40 kilos.

    What was the retailers missing weight?

    This puzzle was originally published with no title.

    [teaser501]

     
    • Jim Randell's avatar

      Jim Randell 9:53 am on 19 September 2019 Permalink | Reply

      In Brainteaser 1575 we determined that a set of weights consisting of the first four powers of three (1, 3, 9, 27) will allow us to weigh all integer amounts between 1 and 40.

      The borrowed set must be missing the same weight as the original set (otherwise he could just replace the missing weight and weigh 1 … 40 kg again). So there are only 4 options to try.

      This Python program runs in 95ms.

      from enigma import (irange, subsets, printf)

# set of weights for weighing 1 ... 40 kg
weights = (1, 3, 9, 27)

# find values that cannot be weighed with the set of weights
def values(weights):
  # desired values
  ws = set(irange(1, 40))
  # choose a subset of the weights
  for s in subsets(weights):
    # choose a pan for each weight
    for p in subsets((+1, -1), size=len(s), select="M"):
      w = sum(x * y for (x, y) in zip(s, p))
      ws.discard(w)
  return ws 

# choose 3 of the 4 weights
for ws in subsets(weights, size=3):
  # determine the number of missing values using 2 sets of weights
  vs = values(ws * 2)
  # if there 15 missing values...
  if len(vs) == 15:
    # output solution
    printf("{ws} -> {vs}")

      Solution: The missing weight is 9 kg.

      Both sets are missing the 9 kg weight, and there are 15 values that cannot be weighed (9 – 18 kg, 36 – 40 kg).

      If both the 1 kg weights are missing there are 27 values that cannot be weighed (1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 29, 31, 32, 34, 35, 37, 38, 40).

      If both the 3 kg weights are missing there are 18 values that cannot be weighed (3 – 6, 12 – 15, 21 – 24, 30 – 33, 39 – 40)

      If both the 27 kg weights are missing there are 14 values that cannot be weighed (27 – 40).

      Like

  • Unknown's avatar

    Jim Randell 12:19 pm on 18 September 2019 Permalink | Reply
    Tags:   

    Teaser 2891: Nine cut diamonds 

    From The Sunday Times, 18th February 2018 [link] [link]

    An app “shuffles” and “deals” the “ace” (= 1) to “nine” of diamonds in a line, face down. Three numbers under 30 are chosen at random and each will win if it is a factor of the hidden nine-digit value. Keying # reveals the rightmost face-down card. At such a “reveal” the app displays “won”, “lost” or “in-play” for each number. The rightmost face-down cards are revealed singly until all are known.

    For one deal my three numbers didn’t include a prime number and after two “reveals” were all “in-play”. After the third “reveal”, two were “won” and one “lost”.

    At the third “reveal” what three-digit number was displayed?

    [teaser2891]

     
    • Jim Randell's avatar

      Jim Randell 12:22 pm on 18 September 2019 Permalink | Reply

      I found the wording a bit cumbersome. Perhaps something like this would have been better:

      I dealt 9 green cards with the digits 1-9 on them face down to create a hidden 9 digit “pandigital” number. And then dealt three blue cards face up from a set consisting of numbers from 1 to 30. None of the blue cards showed a prime number.

      I then started turning over the green cards from the right hand end of the “pandigital” number. After revealing the final two digits I couldn’t be sure whether any of the numbers on the blue cards divided the whole pandigital number or not, but when I revealed the third digit I knew for sure that 2 of them must divide it and the other one must not.

      What were the final three digits of the pandigital number?

      We can eliminate some of the non-primes below 30 as possible divisors because we know the divisibility is not decided until at least digits of the number are revealed (although doing so does not make a huge difference to the run time).

      For instance we can immediately discard the following divisors:

      1 – all numbers are divisible by 1
      9 – any pandigital composed of the digits 1-9 is divisible by 9
      10 – no pandigital is divisible by 10
      20 – as no pandigital is divisible by 10

      We can also discard the following divisors as the divisibility remains undecided when the final digit of the number is known:

      6 – all pandigitals are divisible by 3, and the final digit will tell us if it is divisibly by 2
      15 – all pandigitals are divisible by 3, the final digit will tell us if it is divisible by 5
      18 – all pandigitals are divisible by 9, the final digit will tell us if it is divisible by 2

      And when the final 2 digits are revealed:

      4 – the final 2 digits tell us if it is divisible by 4
      12 – as all pandigitals are divisible by 3
      25 – the final 2 digits tell us if it is divisible by 25

      This Python program considers the three revealed digits and looks for possible divisors that would behave in the manner described. It runs in 904ms.

      Run: [ @repl.it ]

      from enigma import (defaultdict, irange, is_prime, subsets, nconcat, printf)

# possible digits
digits = set(irange(1, 9))

# non-primes 1-29
numbers = set(x for x in irange(1, 29) if not is_prime(x))

# we can eliminate some numbers based on the fact that divisibility
# of the pandigital is not known until 3 digits have been revealed
# (although it doesn't make that much difference to the runtime)
numbers.difference_update([1, 9, 10, 20], [4, 6, 12, 15, 18, 25])

# n in div[x] = "there is a pandigital ending with x divisible by n"
# n in non[x] = "there is a pandigital ending with x that is not divisible by n"
(div, non) = (defaultdict(set), defaultdict(set))
# consider all pandigitals
for s in subsets(digits, size=len, select="P"):
  x = nconcat(s)
  # find the final 1-, 2-, 3- digits
  ms = tuple(x % m for m in (10, 100, 1000))
  # consider each of the candidate numbers
  for n in numbers:
    # record the number against the suffixes
    # according to whether it divides the pandigital or not
    d = (div if x % n == 0 else non)
    for m in ms: d[m].add(n)

# when 1 digit is revealed
for d1 in digits:
  n1 = d1
  # we need 3 numbers that have witnesses in both div and in non
  s1 = div[n1].intersection(non[n1])
  if len(s1) < 3: continue

  # when 2 digits are revealed
  for d2 in digits:
    if d2 == d1: continue
    n2 = 10 * d2 + n1
    # we need 3 numbers that have witnesses in both div and in non
    s2 = s1.intersection(div[n2], non[n2])
    if len(s2) < 3: continue

    # when 3 digits are revealed
    for d3 in digits:
      if d3 == d1 or d3 == d2: continue
      n3 = 100 * d3 + n2
      # find numbers that definitely divide the hidden number (we need at least 2)
      ds = s2.intersection(div[n3].difference(non[n3]))
      if len(ds) < 2: continue
      # find numbers that definitely don't divide the hidden number (we need at least 1)
      ns = s2.intersection(non[n3].difference(div[n3]))
      if len(ns) < 1: continue
  
      printf("{n3} -> div = {ds}, non = {ns}")

      Solution: The final three digits of the selected number are …528.

      There are 166 sets of divisors that would give “in-play” (x3) when the 1st digit is revealed. This is reduced to 84 when the 2nd digit is revealed, and only one of these gives (“win”, “win”, “lose”) when the 3rd digit is revealed.

      For the first digit there are 165 sets that can go with the even digits (2, 4, 6, 8) and 1 set that goes with the digit 5, although this set doesn’t survive to the 2nd digit reveal. There are 60 sets that are fixed by the reveal of the third digit, but all except the solution give (“lose”, “lose”, “lose”).

      There are only two potential divisors that end up with “win” – these are 8 and 24. And only one divisor that ends up with “lose” – 22. So these are our three chosen divisors.

      There are 720 candidate pandigitals ending …528. The smallest being 134679528, and the largest 976431528.

      Like

    • Steve Taylor's avatar

      Steve Taylor 11:11 pm on 7 January 2023 Permalink | Reply

      Hello Jim,

      My name is Steve, and this is just a hello message.

      I came across your site during lockdown and think it’s tremendous!

      I look forward to discussing Teaser 2891…

      Regards

      Steve

      Like

      • Jim Randell's avatar

        Jim Randell 3:11 pm on 9 January 2023 Permalink | Reply

        @Steve: Welcome to the site. I’m glad you find it useful. Feel free to post any further comments on the puzzles.

        Like

  • Unknown's avatar

    Jim Randell 7:49 am on 17 September 2019 Permalink | Reply
    Tags: ,   

    Teaser 1973: Straw store 

    From The Sunday Times, 9th July 2000 [link]

    Farmer Fermat has more straw than he can safely stack on his usual rectangular storage area. So he extends the shorter sides of the area to equal the longer sides, thereby forming a square. Alongside he adds another square area, whose side is equal to the shorter side of the original rectangle. The total area of the two squares together is 243 square feet larger than the original rectangle.

    He can now stack straw on each square, up to a height equal to the length of the side of each square, effectively forming two cubes, and the total volume in cubic feet is a perfect cube.

    What was the perimeter of the original rectangle?

    [teaser1973]

     
    • Jim Randell's avatar

      Jim Randell 7:50 am on 17 September 2019 Permalink | Reply

      As presented this puzzle has multiple solutions. However if the perimeter of the original rectangle is required to be a whole number of feet, then only one of the solutions remains.

      This Python program finds all the solutions to the puzzle numerically using the [[ find_zero() ]] function from the enigma.py library. It runs in 63ms.

      Run: [ @replit ]

      from enigma import (irange, cb, cbrt, sq, find_zero, catch, printf)

# consider values for t, where T = t^3 is the total volume
for t in irange(1, 100):
  T = cb(t)

  # calculate y (for x in [0, t])
  def Y(x):
    return cbrt(T - cb(x))

  # how close is x^2 + y^2 - xy to 243?
  def f(x):
    y = Y(x)
    return abs((sq(x) + sq(y) - x * y) - 243)

  # find a zero for f
  r = catch(find_zero, f, 0, cbrt(0.5 * T))
  if r is None: continue
  x = r.v
  y = Y(x)
  p = 2 * (x + y)

  # output solution
  printf("t={t}: x={x:.3f}, y={y:.3f}, p={p:.3f}")

      Solution: The (integer) perimeter of the original rectangle was 48 feet.

      Allowing non-integer solutions for the perimeter we get four solutions:

      t=16: x=0.857, y=15.999, p=33.712
      t=17: x=3.258, y=16.960, p=40.436
      t=18: x=6.255, y=17.745, p=48.000
      t=19: x=10.291, y=17.935, p=56.453

      Graphically we get a solution when the ellipse x² + y² − xy = 243 intersects the curve x³ + y³ = t³ for integer values of t.

      For positive x and y we get solutions for t = 16, 17, 18, 19, as shown in the graph below:

      The original rectangle has sides of length x and y, so the perimeter of the original rectangle is 2(x + y). Only t=18 gives an integer value for the perimeter (although the values for x and y are not integers). In this case the exact values are: x, y = 12 ± √33.

      Like

      • Jim Randell's avatar

        Jim Randell 8:39 am on 19 September 2019 Permalink | Reply

        Here is an analytical solution.

        Given the equations:

        x³ + y³ = t³
        x² + y² − xy = 243

        If we consider the product (x + y)(x² + y² − xy) we have:

        (x + y)(x² + y² − xy) = x³ + y³ = t³
        (x + y) = t³ / 243

        We also have:

        (x + y)² = (x² + y²) + 2xy
        (x + y)² = (243 + xy) + 2xy
        (x + y)² = 243 + 3xy
        xy = (x + y)² / 3 − 81

        So for a given value of t we can determine values for x + y and xy, say:

        x + y = a
        xy = b

        These have positive real solutions for x and y when a² ≥ 4b and b ≥ 0

        a² ≥ 4b
        (x + y)² ≥ 4xy
        (x + y)² ≥ (4/3)(x + y)² − 324
        (x + y)² ≤ 973
        (x + y) ≤ √973
        t³ ≤ 243 × √973
        t ≤ 19.643…

        b ≥ 0
        (x + y)² / 3 − 81 ≥ 0
        (x + y)² ≥ 243
        (x + y) ≥ √243
        t³ ≥ 243 × √243
        t ≥ 15.588…

        So t is in the range 16 to 19. And the required perimeter is given by p = 2(x + y) = 2t³ / 243.

        We can consider the 4 candidate values manually and look for an integer solution, or use a short program:

        Run: [ @replit ]

        from enigma import (irange, cb, div, printf)

for t in irange(16, 19):
  p = div(2 * cb(t), 243)
  if p is None: continue
  printf("t={t}: p={p}")

        Like

  • Unknown's avatar

    Jim Randell 9:58 pm on 16 September 2019 Permalink | Reply
    Tags:   

    Brain-Teaser 500: [Succession] 

    From The Sunday Times, 3rd January 1971 [link]

    Joybells rang, fireworks went bang, and merry Bahreinis sang, celebrating not only their 500th Founding Festival, but also the coronation of the new monarch of Bahrein Teza.

    “But”, said our special correspondent, intercepting the Lord High Solutioner as he was hurrying through the Palace gates, “I understand there has been a disturbance concerning rival claimants to the throne?”

    “Yes, yes. A bit of bother. Long story”, replied the LHS. “Afraid I can’t stop now though. Banquet just starting. See you later. Wait! Here’s a copy of the royal genealogical tree. Tells you everything. Succession laws same as your own. Right?”, and he disappeared into the Palace.

    Well, here’s a relevant extract:

    CALCULUS – Son-in-law of NUMERA
    DATA III – Daughter of LOGICUS XI
    DATA – Mother of RIDELLA IV
    DECIMUS – Husband of PUZELA
    LOGICUS X – Father of NUMERA
    LOGICUS XI – Father of RIDELLA IV
    LOGICUS – Son of LOGICUS XI
    MATHUS – Brother-in-law of PUZLUS V
    NUMERA – Aunt of PUZLUS VI
    PUZELA – Cousin of LOGICUS XI
    PUZELA – Daughter-in-law of PUZELA
    PUZLUS V – Father of RIDELLA
    PUZLUS VI – Elder son of PUZLUS V
    RIDELLA IV – Niece of PUZLUS VI
    RIDELLA – Mother of SOLVUS II
    RIDELLA – Wife of LOGICUS XI
    SOLVUS II – Cousin of RIDELLA IV

    So who is crowned and who is the claimant?

    The following was published alongside this puzzle:

    Brain-teased 500 times

    “Tantalising but irresistible” sums up the reaction of thousands of readers to The Sunday Times Brain-teaser, which this week reaches its 500th example since numbering began on February 26, 1961.

    Competitors, from emeritus professors of mathematics to 11-year-olds, with a growing proportion of women, submit their solutions from every county and from 56 oversea States, some never having missed a week. It is calculated that between 40,000/50,000 readers send a solution every year.

    Set by Sunday Times readers, the problems are selected from about 200 a year, vetted for uniqueness of solutions by independent experts (with an occasional oversight) and are published in varying degrees of difficulty; entries then range weekly from around 4,000 to a handful from the master-minds.

    — Anthony French

    This puzzle was originally published with no title.

    [teaser500]

     
    • Jim Randell's avatar

      Jim Randell 9:59 pm on 16 September 2019 Permalink | Reply

      For me this puzzle isn’t well enough defined.

      For instance:

      PUZELA − Daughter-in-law of PUZELA

      Does this mean that PUZELA married her own son? Or is there not a one-to-one correspondence between names and people?

      Maybe each line of the genealogy refers to a different person? If so, there are two PUZELAs and RIDELLAs and we don’t know which is referred to when the names are used again.

      And even if you come up with an answer there seems to be no way to check if it is right.

      However, as I have transcribed the puzzle (and at least glanced at it) I am posting it for completeness, and in case someone else is interested in it.

      The published solution is:

      Crowned = DECIMUS. Claimant = LOGICUS.

      A splendid baffling problem of succession. Did no one spot the Stuart parallel? A mixed bag. 18% right.

      So it doesn’t look like it was that well received at the time.

      Like

    • Lise Andreasen's avatar

      Lise Andreasen 6:26 am on 28 July 2024 Permalink | Reply

      Yeah. Can’t quite make sense of it.

      Like

  • Unknown's avatar

    Jim Randell 8:37 am on 15 September 2019 Permalink | Reply
    Tags:   

    Brainteaser 1712: Squambling 

    From The Sunday Times, 9th July 1995 [link]

    In “squambling” a number, the first (leftmost) digit is squared, the next is cubed, the next raised to the fourth power, and so on. The total of these answers provides a new number, ready for the squambling to begin again.

    For example:

    18 → 1² + 8³ = 513 → 5² + 1³ + 3⁴ = 107
    107 → 2402 → 100 → 1 → 1 → …

    If you take my age and squamble it you get a three-figure number. If you then squamble that answer you get my age next year.

    How old am I?

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

    [teaser1712]

     
    • Jim Randell's avatar

      Jim Randell 8:38 am on 15 September 2019 Permalink | Reply

      This Python program runs in 86ms.

      Run: [ @replit ]

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

squamble = lambda n: sum(d ** n for (n, d) in enumerate(nsplit(n), start=2))

assert squamble(18) == 513

for n in irange(1, inf):
  sn = squamble(n)
  if not (99 < sn < 1000): continue
  s2n = squamble(sn)
  if not (s2n == n + 1): continue
  # output solution
  printf("{n} -> {sn} -> {s2n}")
  break

      Solution: You are 46.

      We have:

      46 → 232 → 47 → … → 43

      After 91 applications of the function we eventually reach a value of 43, which is stable (i.e. squamble(43) = 43).

      The next smallest value at which this occurs is 753:

      753 → 255 → 754

      Like

  • Unknown's avatar

    Jim Randell 3:58 pm on 13 September 2019 Permalink | Reply
    Tags:   

    Teaser 2973: Something in common 

    From The Sunday Times, 15th September 2019 [link] [link]

    I have written down four different numbers. The third number is the highest common factor of the first two (i.e. it is the largest number that divides exactly into both of them). The fourth number is the lowest common multiple of the first two (i.e. it is the smallest number that both of them divide exactly into).

    I can consistently replace digits by letters in my numbers so that the highest common factor is HCF and the lowest common multiple is LCM.

    What are the first two numbers?

    [teaser2973]

     
    • Jim Randell's avatar

      Jim Randell 4:06 pm on 13 September 2019 Permalink | Reply

      The two mystery numbers have a common divisor that is 3 digits, and also the have a common multiple that is 3 digits, so they are both 3 digit numbers themselves.

      Denoting the numbers UVW and XYZ we can use the [[ SubstitutedExpression() ]] solver from the enigma.py library to give a direct interpretation of the the puzzle.

      This run file executes in 989ms.

      Run: [ @repl.it ]

      #! python -m enigma -rr

SubstitutedExpression

--distinct="CFHLM"
--answer="(UVW, XYZ)"

"gcd(UVW, XYZ) = HCF"
"lcm(UVW, XYZ) = LCM"

"all_different(UVW, XYZ, HCF, LCM)"

"UVW < XYZ"

      Solution: The first two numbers are 278 and 417.

      hcf(278, 417) = 139
      lcm(278, 417) = 834

      Like

      • Jim Randell's avatar

        Jim Randell 5:14 pm on 13 September 2019 Permalink | Reply

        Here’s an alternative approach that uses a bit of analysis:

        Each of the mystery numbers must be some small (proper) multiple of HCF, say, A × HCF and B × HCF. And A and B must be co-prime.

        We can then use the fact that:

        hcf(p, q) × lcm(p, q) = p × q

        to give a faster alphametic approach.

        The following run file executes in 173ms.

        Run: [ @repl.it ]

        #! python -m enigma -rr

SubstitutedExpression

--distinct="CFHLM"
--answer="(A * HCF, B * HCF)"

"1 < A < B"
"gcd(A, B) = 1"

"A * B * HCF = LCM"

        Actually it is clear that A × B < 10, so the only options are A = 2, B = 3, giving rise to the following one-line solution:

        % python -m enigma SubstitutedExpression "6 * HCF = LCM" --answer="(2 * HCF, 3 * HCF)"
(6 * HCF = LCM) ((2 * HCF, 3 * HCF))
(6 * 139 = 834) ((2 * 139, 3 * 139)) / C=3 F=9 H=1 L=8 M=4
(2 * HCF, 3 * HCF) = (278, 417) [1 solution]

        Like

    • GeoffR's avatar

      GeoffR 10:09 am on 17 September 2019 Permalink | Reply 

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

var 1..9:H; var 0..9:C; var 0..9:F;
var 1..9:L; var 0..9:M;

var 100..999:N1; var 100..999:N2;
var 100..999:HCF = 100*H + 10*C + F;
var 100..999:LCM = 100*L + 10*C + M;

constraint all_different( [N1, N2, HCF, LCM] );
constraint all_different( [H, C, F, L, M] );

constraint LCM * HCF == N1 * N2;

constraint N1 mod HCF == 0 /\ N2 mod HCF == 0;

solve maximize(HCF);

output [ " First number = " ++ show(N1) ++ "\n"
++ " Second number = " ++ show(N2) ++ "\n"
++ " Highest common factor = " ++ show(HCF) ++ "\n"
++ " Lowest common multiple = " ++ show(LCM) ];

      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