Updates from May, 2019 Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 8:55 am on 26 May 2019 Permalink | Reply
    Tags:   

    Brainteaser 1575: Quantum scales 

    From The Sunday Times, 15th November 1992 [link]

    The merchants of Mathematica only ever have to weigh things that weigh a whole number of “quantums”, that country’s unit of weight. They have a pair of balancing scales, and four weights. By using these weights (on either side of the balance) they can determine the weight of items weighing 1, 2, 3, 4, 5, … quantums, and they have designed the four weights so that this sequence continues as high as it possibly can with just four weights.

    With their balance and weights they can determine the weight of a Maxpack, but not of anything heavier.

    What is the weight of a Maxpack?

    This puzzle is included in the book Brainteasers (2002). The wording above is taken from the book. It is slightly changed from the original puzzle, to remove an ambiguity.

    [teaser1575]

     
    • Jim Randell's avatar

      Jim Randell 8:55 am on 26 May 2019 Permalink | Reply

      First let’s consider a problem with being able to balance exact weights of 1 … n.

      If we can weigh the numbers 1 … n using k weights, then by adding an extra weight of (2n + 1) we can weigh:

      1 … n (using the original combinations of weights)
      n + 1 … 2n (using (2n + 1) − x, for each x in the original combinations of weights)
      2n + 1 (using the extra weight)
      2n + 2 … 3n + 1 (using (2n + 1) + x, for each x in the original combinations of weight)

      So, with a weight of 1, we can weigh 1 … 1.

      With weights of (1, 3) we can weigh 1 … 4.

      With weights of (1, 3, 9) we can weigh 1 … 13.

      With weights of (1, 3, 9, 27) we can weigh 1 … 40.

      (Each weight is an increasing power of 3, 3⁰ = 1, 3¹ = 3, 3² = 9, 3³ = 27, …).

      And this would be the best we could manage if we had to balance exact weights.

      But in this puzzle we know each object we have to weigh is one of the values 1 … N.

      So there is no point in being able to balance an object with a weight of 1, as if we can make a combination with a weight of 2, and determine that our object is lighter than it, then, as weights are quantised, it can only have a weight of 1.

      In fact, there is no point in having weights of any odd value, as we determine that a weight is between (2k) and (2k + 2), then it can only have a weight of (2k + 1).

      So, by doubling the 4 weights to (2, 6, 18, 54) we can balance exact weights of 2, 4, 6, 8, …, 80.

      And we will be able to determine the weight of any object weighing 1 … 80 units:

      Any object that has an even value from 2 … 80 can be balanced exactly.

      Any object with an odd value from 3 … 79 can be isolated between two even values.

      Any object that weighs less than 2, must have a value of 1.

      The weight of any object that weighs more than 80 units cannot be determined exactly.

      Solution: The weight of a Maxpack is 80 units.

      Like

  • Unknown's avatar

    Jim Randell 12:43 pm on 9 May 2019 Permalink | Reply
    Tags: by: John Walker   

    Brainteaser 1568: Back to the future 

    From The Sunday Times, 27th September 1992 [link]

    Many dates, such as my birthday 27th September 1972, are palindromic when written down in the form day/month/year without breaks, my birthday being 2791972.

    What about palindromic dates in the millennium beginning on 1st January 2000?

    (a) How many palindromic dates will there be in this millennium?

    (b) Of these, which two are closest together?

    The text above is taken from the book Brainteasers (2002), and is different from the originally published puzzle, which is reproduced below:

    With another palindromic date occurring on Tuesday (29.9.1992) I am reminded of a Teaser I set last year in which readers were asked to find the longest sequence of consecutive non-palindromic dates in the next 200 years. Here’s another idea:

    Assuming the standard numerical format of a date as day.month.year with the year as a four-figure number and with no zeros to start the day or month, find the two palindromic dates in the future which are closest together.

    [teaser1568]

     
    • Jim Randell's avatar

      Jim Randell 12:44 pm on 9 May 2019 Permalink | Reply

      This Python program considers dates from 1-1-2000 to 31-12-2999. It runs in 780ms.

      Run: [ @replit ]

      from datetime import (date, timedelta)
from enigma import (repeat, inc, concat, tuples, Accumulator, printf)

# record palindromic dates from 2000 - 2999
ds = list()
for d in repeat(inc(timedelta(days=1)), date(2000, 1, 1)):
  if not (d.year < 3000): break
  s = concat(d.day, d.month, d.year)
  if s == s[::-1]:
    ds.append(d)
printf("[{n} palindromic dates]", n=len(ds))

# find the two dates closest together
r = Accumulator(fn=min)
r.accumulate_data_from((b - a, (a, b)) for (a, b) in tuples(ds, 2))

# output solution
(t, (a, b)) = (r.value, r.data)
printf("{a.day}-{a.month}-{a.year} -> {b.day}-{b.month}-{b.year} ({t.days} days)")

      Solution: (a) There are 323 palindromic dates. (b) The closest pair is: 23-2-2232 and 2-3-2232 (8 days apart).

      Pleasingly the number of palindromic dates is itself a palindrome.

      If we extend the date range to the year 9999 there are 2107 more palindromic dates (assuming the calendar remains the same). And the closest two are:

      29-8-8892 and 2-9-8892 (4 days apart)

      And if we extend the current calendar backwards to year 1 we can manage even better:

      31-10-113 and 3-11-113 (3 days apart)

      Like

    • Lise Andreasen's avatar

      Lise Andreasen 12:20 am on 8 May 2024 Permalink | Reply

      Does your algorithm count 1112111 (to give an example) as one or 2 dates? 1/11/2111 and 11/1/2111.

      Like

      • Lise Andreasen's avatar

        Lise Andreasen 12:30 am on 8 May 2024 Permalink | Reply

        Oh, never mind. Figured it out.

        Like

    • Lise Andreasen's avatar

      Lise Andreasen 12:34 am on 8 May 2024 Permalink | Reply

      It’s possible to count the variations.
      There are 81 dates of the form a/b/22ba.
      There are 27 dates of the form a/bc/2cba.
      There are 192 dates of the form ab/c/2cba.
      There are 22 dates of the form ab/12/21ba.

      Neat algorithm though. 👍🏻

      Like

      • Jim Randell's avatar

        Jim Randell 10:26 am on 8 May 2024 Permalink | Reply

        I don’t know if it is a typo, but these numbers don’t add up to 323.

        I found there should 193 dates of the form ab/c/2cba. (Or maybe you forgot: 29/2/2292).

        Like

        • Lise Andreasen's avatar

          Lise Andreasen 12:53 pm on 8 May 2024 Permalink | Reply

          It was a typo. And it’s probably also a remnant of me getting that leap year date wrong the first time through.

          Like

  • Unknown's avatar

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

    Brainteaser 1567: How many teams? 

    From The Sunday Times, 20th September 1992 [link]

    The teams in our local football league each play each of the others once in a season, earning three points for a win and one point for a draw. After the last Saturday of the season (when all the teams had played one game that day) I worked out the league table (with the teams in alphabetical order). I then consistently replaced digits in the table by letters, using different letters for different digits.

    Here is part of that table, showing some of the entries in three of the rows:

    What is the number of teams in the league? And what is the number TEAMS?

    This puzzle is included in the book Brainteasers (2002). The wording here is taken from the book and is only slightly changed from the original puzzle.

    [teaser1567]

     
    • Jim Randell's avatar

      Jim Randell 8:11 am on 30 April 2019 Permalink | Reply

      If there are n teams in the league, then at the end of the season each team has played all the other (n − 1) teams, and this total number of matches must be represented in the sum of the “won”, “drawn”, “lost” columns in the table.

      H + O + W = n − 1
      M + A + N = n − 1
      T + E + A = n − 1

      If each team played one match on the final Saturday, then there must be an even number of teams. And if n is even, then (n − 1) is odd.

      We are given the points in the third row:

      3T + E = S

      And we are given the “goals against” for two teams. Each “lost” game involves conceding at least one goal, so:

      N ≤ Y, A ≤ M

      (and the values cannot be equal).

      Together these give us enough information to assign values to the letters.

      We can solve these alphametic expressions using the [[ SubstitutedExpression() ]] solver from the enigma.py library.

      The following run file executes in 216ms.

      Run: [ @repl.it ]

      #! python3 -m enigma -rr

SubstitutedExpression

# sums of "won", "drawn", "lost" are the same
"H + O + W == M + A + N == T + E + A"

# sum is odd
"(H + O + W) % 2 = 1"

# points for third row
"3 * T + E = S"

# "lost" <= "goals against"
"N < Y"
"A < M"

# answer: (number of teams, value of TEAMS)
--answer="(H + O + W + 1, TEAMS)"

      Solution: There are 12 teams in the league. TEAMS = 16459.

      The first row has “won”, “drawn”, “lost” values of 0, 3, 8, but we don’t know which order.

      The second row has 5 “won”, 4 “drawn”, 2 “lost”, and 7 “goals against”.

      The third row has 1 “won”, 6 “drawn”, 4 “lost” and 5 “goals against”, giving 9 points.

      There are 12 teams, so there are 66 matches played in total.

      Like

  • Unknown's avatar

    Jim Randell 8:16 am on 25 April 2019 Permalink | Reply
    Tags:   

    Brainteaser 1563: Family sum 

    From The Sunday Times, 23rd August 1992 [link]

    In this puzzle digits have been consistently replaced by letters, with different letters being used for different digits. This addition sum then makes sense:

    also AND is divisible by three.

    What is the number REAGAN?

    This puzzle is included in the book Brainteasers (2002). The wording is only slightly changed from the original puzzle.

    [teaser1563]

     
    • Jim Randell's avatar

      Jim Randell 8:17 am on 25 April 2019 Permalink | Reply

      This puzzle can easily be solved using the [[ SubstitutedExpression() ]] solver from the enigma.py library.

      The following run-file executes in 480ms.

      Run: [ @replit ]

      #! python3 -m enigma -rr

SubstitutedExpression

"RONALD + AND + NANCY = REAGAN"

"AND % 3 = 0"

--answer="REAGAN"

      Solution: REAGAN = 396168.

      The symbols L and C appear in the tens column, but not elsewhere, so their values can be interchanged. This gives rise to the two possible sums:

      308627 + 687 + 86854 = 396168
      308657 + 687 + 86824 = 396168

      Like

      • Jim Randell's avatar

        Jim Randell 8:41 am on 9 June 2023 Permalink | Reply

        For a faster solution we can use the [[ SubstitutedExpression.split_sum ]] solver.

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

        Run: [ @replit ]

        #! python3 -m enigma -rr

SubstitutedExpression.split_sum

"RONALD + AND + NANCY = REAGAN"

--extra="AND % 3 = 0"

--answer="REAGAN"

        Like

    • GeoffR's avatar

      GeoffR 12:20 pm on 25 April 2019 Permalink | Reply 

      % A Solution in MiniZinc
include "globals.mzn";
 
var 0..9: R; var 0..9: O; var 0..9: N; var 0..9: A;  var 0..9: L; 
var 0..9: D; var 0..9: C; var 0..9: Y; var 0..9: E;  var 0..9: G; 

constraint R != 0 /\ A != 0 /\ N != 0;
constraint all_different( [R,O,N,A,L,D,C,Y,E,G]);

var 100..999: AND = 100*A + 10*N + D;
var 10000..99999: NANCY = 10000*N + 1000*A + 100*N + 10*C + Y;

var 100000..999999: RONALD = 100000*R + 10000*O + 1000*N 
+ 100*A + 10*L + D;

var 100000..999999: REAGAN = 100000*R + 10000*E + 1000*A 
+ 100*G + 10*A + N;

constraint AND mod 3 == 0;

constraint RONALD + AND + NANCY == REAGAN;

solve satisfy;

output [show(RONALD) ++ " + " ++ show(AND) ++ " + " ++ 
show(NANCY) ++ " = " ++ show(REAGAN)];

% 308657 + 687 + 86824 = 396168
% time elapsed: 0.02 s
% ----------
% 308627 + 687 + 86854 = 396168
% time elapsed: 0.02 s
%----------
%==========

      Like

    • Frits's avatar

      Frits 1:44 pm on 9 June 2023 Permalink | Reply 

        
column 3: x + N + A = .A with x = 1,2,3 so N = 8,9,0

column 2: y + O + N = E so either:

N = 9, is not possible
N = 8 and O = 0 and x = 2  
N = 0 causes y to be zero but then O = E

--> N = 8, O = 0, E = 9 and x = 2

column 4:
z + A + A + N = 2G so z + A + A >= 21 - 8 so A = 6,7

using AND is divisible by three:
(A, D, Y) is either (6, 7, 4) or (7, 3, 2)
(A, D, Y, L+C) is either (6, 7, 4, 7) or (7, 3, 2, 9)
(A, D, Y, {L, C}) is either (6, 7, 4, {2, 5}) or (7, 3, 2, {4, 5})

(A, G) = (6, 1) as A = 7 causes G to be 3 (which is same as D)

so (N, O, E, A, D, Y, G) = (8, 0, 9, 6, 7, 4, 1) with {L, C} = {2, 5}
This leaves R = 3

      Like

  • Unknown's avatar

    Jim Randell 12:51 pm on 21 April 2019 Permalink | Reply
    Tags:   

    Brainteaser 1557: An alphabetical jigsaw 

    From The Sunday Times, 12th July 1992 [link]

    I have some jigsaw pieces which fit together to form a 5-by-5 square with the letters all the right way up. Here is an attempt to make the jigsaw:

    The attempt has failed because the last piece does not fit the right way up. In fact it is possible to make the 5-by-5 jigsaw so that the 25 different letters spell six words in reading order.

    What is this arrangement?

    This puzzle appears in the book Brainteasers (2002). The wording above is taken from the book, but is only slightly changed from the original puzzle.

    [teaser1557]

     
    • Jim Randell's avatar

      Jim Randell 12:52 pm on 21 April 2019 Permalink | Reply

      There are two parts to the program. The first is concerned with fitting the pieces into the grid. The second part is then reading the letters in the grid as a collection of words.

      This Python program runs in 6.6s, but most of the time is taken up with collecting the word list. I used a collection of allowable Scrabble words, which gives 49,595 viable words.

      Run: [ @replit ] (using just the selected words)

      from itertools import product
from collections import (Counter, defaultdict)
from enigma import (irange, find, chunk, flatten, join, printf)

(X, Y) = (1, 7)

pieces = [
  { 0: 'H', Y: 'Z', X + Y: 'F', X + Y + Y: 'X' },
  { 0: 'P', X: 'S', X + X: 'C' },
  { 0: 'I', Y: 'J', Y + Y: 'O' },
  { 0: 'G', X: 'Y', X + Y: 'M' },
  { 0: 'T', Y: 'V', Y + Y: 'N' },
  { 0: 'E', Y: 'K', X + Y: 'W' },
  { 0: 'U', Y: 'R', X + Y: 'D' },
  { 0: 'A', X: 'L', X + Y: 'B' },
]

# create the empty grid
grid = [None] * (Y * Y)
for (x, y) in product(irange(1, 5), irange(1, 5)):
  grid[x + y * Y] = '.'

# fit piece p into grid g at index i
# return new grid or None
def fit(g, p, i):
  g = g.copy()
  for (k, v) in p.items():
    x = g[i + k]
    # non-usable square?
    if x != '.': return None
    g[i + k] = v
  return g

def solve(ps=pieces, g=grid):
  # are we done?
  if not ps:
    # return the completed (unpadded) grid
    yield list(r[1:-1] for (i, r) in enumerate(chunk(g, Y), start=1) if 1 < i < Y)
  else:
    # find an empty square
    i = find(g, '.')
    if i != -1:
      for (j, p) in enumerate(ps):
        g2 = fit(g, p, i)
        if g2 is not None:
          yield from solve(ps[:j] + ps[j + 1:], g2)

# list of words to examine
file = "words.txt"

# collect letters from the pieces
letters = Counter()
for p in pieces: letters.update(p.values())

# collect words that can be formed from the letters
words = defaultdict(list)
for w in open(file).readlines():
  w = w.strip().upper()
  if not (Counter(w) - letters):
    words[w[0]].append(w)

printf("[collected {n} words from {file}]", n=sum(len(v) for v in words.values()))

# form text t into a sequence of words
def check(t, s=[]):
  if not t:
    yield s
  else:
    for w in words[t[0]]:
      if t.startswith(w):
        yield from check(t[len(w):], s + [w])


# fit the pieces into the grid
for g in solve():
  # attempt to form the letters into words
  wss = list(check(join(flatten(g))))
  if wss:
    # output the grid
    for r in g:
      printf("{r}", r=join(r, sep=" "))
    # output the words
    for ws in wss:
      if len(ws) == 6:
        printf("words: {ws}", ws=join(ws, sep=", "))
    printf()

      Solution: The completed jigsaw looks like this:

      So the 6 words are: GYP, SCHMALTZ, FIB, VEX, JUNK, WORD.

      There are 64 ways to fit the pieces into the grid, but only one of them makes a set of viable words.

      There are 2 fifteen letter words in the list that can be made from the collection of letters in the puzzle: DERMATOGLYPHICS, UNCOPYRIGHTABLE.

      Like

  • Unknown's avatar

    Jim Randell 8:31 am on 18 April 2019 Permalink | Reply
    Tags:   

    Brainteaser 1547: Doing the rounds 

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

    This week, I share a find-the-next-row puzzle that is doing the rounds of dons’ whiteboards:

    1
    1 1
    2 1
    1 2 1 1
    ?

    To avoid invasion of ivory towers, I will give you the answer:

    1 1 1 2 2 1

    with the explanation that, starting with the initial 1, each subsequent row is obtained by reading the previous row. Thus, row five is formed (with reference to row four) from one “one”, followed by one “two”, and terminating with two “one”s.

    However, I do have four questions about the first billion rows of this sequence.

    1. What is the largest digit that can be found anywhere?
    2. What is the largest number of ones that can occur consecutively in any single row?
    3. Repeat (2), looking for twos instead.
    4. Repeat (2), looking for threes instead.

    Multiply each answer by its question number and send in the total.

    This puzzle is included in the book Brainteasers (2002), in which it appears in the following form:

    Read me!

    Consider the sequence:

    1
    11
    21
    1211
    111221
    312211
    …

    You might like to try and work out the next few terms before reading on and trying the rest of this Teaser.

    In fact, having started with 1, each subsequent term simply reads the previous line. So, for example, after 111221 we note that this consists of:

    three ones, two twos, one one

    i.e. the next term is simply:

    312211

    Here are some questions about the first billion terms of this sequence:

    (a) What is the largest number of consecutive ones in any term?
    (b) What is the largest number of consecutive twos in any term?
    (c) What is the largest number of consecutive threes in any term?
    (d) What is the largest digit which can be found in any term?

    [teaser1547]

     
    • Jim Randell's avatar

      Jim Randell 8:33 am on 18 April 2019 Permalink | Reply

      This Python program generates the first few terms of the sequence. To do the first 12 terms takes 80ms.

      Run: [ @replit ]

      from enigma import (repeat, chunk, arg, printf)

# transform the input sequence s, by counting the runs of digits
def transform(s):
  r = list()
  while s:
    x = s[0]
    for (j, y) in enumerate(s):
      if j > 0 and y != x:
        r.extend([j, x])
        s = s[j:]
        break
    else:
      r.extend([j + 1, x])
      break
  return r

# how many sequences to examine
N = arg(12, 0, int)

# record max runs (in the previous term)
m = dict()

# repeatedly apply the transform, starting with [1]
for (i, s) in enumerate(repeat(transform, [1]), start=1):
  if N < 15: printf("({i}) -> {s}")

  # each transformed sequence consists of (n, d) pairs
  # telling us there were n runs of digit d in the previous term
  if i > 1:
    for (n, d) in chunk(s, 2):
      if n > m.get(d, 0):
        m[d] = n

  if not (i < N): break

# output solutions
for k in sorted(m.keys()):
  printf("digit {k} -> {n} times", n=m[k])
printf("max digit = {k}")

      Together with some analysis we can now answer the questions:

      First we note that we can’t split runs of the same digit, so if we have (for example) five d‘s, …ddddd…., they will appear in the next sequence as …(5d)…, and not as …(2d)(3d)… etc.

      So in any transformed sequence we cannot have two pairs appearing consecutively for the same digit, i.e. …(xd)(yd)… would not appear, because it would be …({x+y}d)…

      So, we certainly cannot have a sequence of four consecutive digits …(dd)(dd)… appearing in a transformed sequence.

      But neither can we have …(xd)(dd)(dy)… appearing, as that also has two pairs appearing consecutively for the same digit.

      So we cannot have a run of more than three consecutive digits in any transformed sequence.

      Which means in any transformed sequence we will not see a digit greater than 3.

      Running the program we see that in the first 12 sequences we have three 1’s appearing in sequence 5:

      (5) → [1, 1, 1, 2, 2, 1]

      and three 2’s appearing in sequence 7:

      (7) → [1, 3, 1, 1, 2, 2, 2, 1]

      but we only manage two 3’s in sequence 11:

      (11) → [1, 1, 1, 3, 1, 2, 2, 1, 1, 3, 3, 1, 1, 2, 1, 3, 2, 1, 1, 3, 2, 1, 2, 2, 2, 1]

      And in fact we can see that it is not possible to achieve three 3’s.

      If we think about the first sequence in which …333… appears, then the digits must be paired as …(33)(3x)… (as …(x3)(33)… is not possible), but then the (33) indicates that the sequence before this one must have had a run of three 3’s (followed by three of another digit). But this is a contradiction. So we cannot find a first sequence with three 3’s.

      So that answer to puzzle from the book is:

      Solution: (a) 3; (b) 3; (c) 2; (d) 3.

      And solution for the original puzzle is: 1×3 + 2×3 + 3×3 + 4×2 = 26.

      To consider the first 40 sequences take my program 5.5s, and the 40th sequence has 63,138 digits, so it is not suitable for attempting to examine the first billion terms.

      The sequence is known as the “look and say” sequence [@wikipedia].

      Like

  • Unknown's avatar

    Jim Randell 11:01 am on 7 April 2019 Permalink | Reply
    Tags: ,   

    Brainteaser 1542: Precisely what do I mean? 

    From The Sunday Times, 29th March 1992 [link]

    There is a row of 10 boxes and each box contains one object, which is a knife, a fork or a spoon. Each of the three utensils is in at least one box. Here are five true statements to help you answer the questions below:

    1. A knife is in more boxes than a spoon is in;
    2. A spoon is in more boxes than a fork is in;
    3. A knife is not in precisely five boxes;
    4. A spoon is not in precisely three boxes;
    5. A fork is not in precisely half the number of boxes a spoon is in.

    How many boxes contain a knife?

    How many boxes contain a spoon?

    This puzzle is included in the book Brainteasers (2002), in which it appears in the following (slightly different) form:

    There is a row of ten boxes and each box contains one object, which is a knife, a fork or a spoon. There is at least one of each utensil. Here are five true statements to help you work out how many of each there are:

    • A knife is in more boxes than a spoon is in;
    • A spoon is in more boxes than a fork is in;
    • A knife is not in precisely five boxes;
    • A spoon is not in precisely three boxes;
    • A fork is not in precisely half the number of boxes a spoon is in.

    How many of each utensil are there?

    However I think both these formulations are flawed, in that under any reasonable interpretation there are no solutions. In the comments I present a variation that can be solved.

    [teaser1542]

     
    • Jim Randell's avatar

      Jim Randell 11:05 am on 7 April 2019 Permalink | Reply

      Having read the solution given in the book, I think the spirit of the puzzle can be maintained by phrasing it slightly differently:

      The National Museum of Cutlery in the small country of Ambiguity has an exhibit consisting of a row of ten boxes.

      Each box contains one object, which is either a knife, a fork or a spoon. There is at least one of each utensil.

      On a recent visit I heard five natives make the following true statements:

      1. A knife is in more boxes than a spoon is in.
      2. A spoon is in more boxes than a fork is in.
      3. A knife is not in precisely five boxes.
      4. A spoon is not in precisely three boxes.
      5. A fork is not in precisely half the number of boxes a spoon is in.

      How many of each utensil are there?

      And here is my solution:

      Suppose there are K knives, F forks and S spoons, each number has a value from 1 to 9.

      Looking at the statements:

      “A knife is in more boxes than a spoon is in”, seems to be an oddly worded way of saying: “there are more knives than spoons”:

      K > S

      Similarly: “A spoon is in more boxes than a fork is in”, seems to be saying:

      S > F

      We then have three statements of the form: “an X is not in precisely N boxes”

      I think there are two reasonable interpretations of this:

      (a) “The number of boxes containing an X, is not exactly N”

      i.e.:

      X ≠ N

      or:

      (b) “There are exactly N boxes, containing an object that is not an X”

      i.e.:

      10 − X = N

      The following Python 3 program considers these possible interpretations for the last three statements. It runs in 80ms.

      Run: [ @repl.it ]

      from enigma import (irange, join, printf)

# decompose <t> into <k> increasing values
def decompose(t, k, m=1, s=[]):
  if k == 1:
    if not (t < m):
      yield s + [t]
  else:
    for x in irange(m, t):
      yield from decompose(t - x, k - 1, x + 1, s + [x])

# consider interpretations for:
# "the number of boxes containing an <x> is <n>/<d>"
def interpretations(x, n, d=1):
  # (a) "the number of boxes containing an <x> is exactly <n>/<d>"
  if d * x != n: yield 'a'
  # (b) "there are exactly <n>/<d> boxes containing an object that is not an <x>"
  if d * (10 - x) == n: yield 'b'

# find possible values for F < S < K
for (F, S, K) in decompose(10, 3):
  # consider possible interpretations for the last three statements
  ss = list(join(interpretations(*args)) for args in [(K, 5), (S, 3), (F, S, 2)])
  # each must have some interpretation
  if not all(ss): continue
  # output solution
  printf("F={F} S={S} K={K} {ss}")

      Solution: There is 1 fork, 4 spoons, 5 knives.

      The constraint (F < S < K) narrows the solution down to 4 possibilities:

      F=1, S=2, K=7
      F=1, S=3, K=6
      F=1, S=4, K=5
      F=2, S=3, K=5

      Only in the case (F=1, S=4, K=5) do the last three statements all have viable interpretations. These are:

      3. “A knife is not in precisely 5 boxes” = “There are exactly 5 boxes containing an object that is not a knife”
      4. “A spoon is not in precisely 3 boxes” = “The exact number of boxes containing a spoon is not 3”
      5. “A fork is not in precisely half the number of boxes a spoon is in” = “The exact number of boxes containing a fork is not half the exact number of boxes containing a spoon”

      or:

      3. “10 − K = 5”
      4. “S ≠ 3”
      5. “F ≠ S / 2”

      We can see each of these is a true statement, but they do not all use the same interpretation of the statement form. (Statement 3 uses the (b) interpretation. Statements 4, 5 use the (a) interpretation). This is why I changed the puzzle wording, so that the statements are made by different people. To have them made by the same person implies a consistent interpretation and gives no viable solutions.

      Like

  • Unknown's avatar

    Jim Randell 7:37 am on 4 April 2019 Permalink | Reply
    Tags: by: Donald Entwisle   

    Brainteaser 1538: Times square 

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

    Alf: Listen to this: “SUN times DAY equals TIMES“.

    Beth: Sounds like a lot of nonsense to me.

    Alf: Let me write it down for you. Like this:

    SUN × DAY = TIMES

    In this sum are 10 different letters representing digits 0 to 9 and in my answer SUN minus DAY is a perfect square. That should help you.

    Beth: That’s a tall order, but I’ll have a go. Where’s my calculator.

    Beth did find Alf’s solution. What was their number for TIMES?

    This puzzle is included in the book Brainteasers (2002), in which it appears in the following modified form:

    With the usual letters-for-digits convention:

    SUN – DAY

    is the square of a prime, and:

    SUN × DAY = TIMES

    What number is TIMES?

    (We do not actually need to know that the square is the square of a prime, but it cuts down the work considerably).

    [teaser1538]

     
    • Jim Randell's avatar

      Jim Randell 7:38 am on 4 April 2019 Permalink | Reply

      The wording (but not most of the meaning) of this Teaser was changed considerably for the book. In the original puzzle we were told that (SUN − DAY) was a square number, but not that it was the square of a prime.

      The puzzle can be solved using the [[ SubstitutedExpression() ]] solver from the enigma.py library.

      This run file executes in 235ms.

      Run: [ @repl.it ]

      #! python -m enigma -rr

SubstitutedExpression

--answer="TIMES"

"is_prime(is_square(SUN - DAY))"

"SUN * DAY = TIMES"

      Solution: TIMES = 50862.

      We can remove the call to [[ is_prime() ]] to solve the original puzzle. The answer is the same.

      Without the subtraction constraint at all, the multiplication sum has three solutions:

      % python enigma.py SubstitutedExpression "SUN * DAY = TIMES"
(SUN * DAY = TIMES)
(219 * 308 = 67452) / A=0 D=3 E=5 I=7 M=4 N=9 S=2 T=6 U=1 Y=8
(294 * 173 = 50862) / A=7 D=1 E=6 I=0 M=8 N=4 S=2 T=5 U=9 Y=3
(254 * 378 = 96012) / A=7 D=3 E=1 I=6 M=0 N=4 S=2 T=9 U=5 Y=8
[3 solutions]

      Like

  • Unknown's avatar

    Jim Randell 7:10 am on 30 March 2019 Permalink | Reply
    Tags:   

    Brainteaser 1510: Sum puzzle 

    From The Sunday Times, 18th August 1991 [link]

    In this addition sum nine digits are each represented by a different letter and the remaining one digit it represented in various places by nine letters.

    When the 47-figure number:

    INTHISADDITIONSUMNINEDIGITSAREEACHREPRESENTEDBY

    is added to the 46-digit number:

    ONELETTERANDONEDIGITISREPRESENTEDBYNINELETTERS

    the answer is the 47-figure number:

    TDODRRITECIPADAABSDLOTRSORANOHMIAGSAOTUDAYDOEOE

    What is the SOLUTION?

    The text of this puzzle is taken from the book Brainteasers (2002), so may differ from the originally published puzzle.

    [teaser1510]

     
    • Jim Randell's avatar

      Jim Randell 7:11 am on 30 March 2019 Permalink | Reply

      Potentially we could just feed the entire sum as a single expression to the [[ SubstitutedExpression() ]] solver from the enigma.py library, but generating and considering all the possibilities for the 15 digits in the terms of the sum is going to take some time.

      So to help it along I provided some additional expressions, which are the sums formed taking some of the columns (in pairs, to reduce the amount of typing), linked together by carries. After 9 pairs we have mentioned each letter at least once, and the solver finds the solution in less than 200ms.

      This run-file executes in 183ms.

      Run: [ @replit ]

      #! python -m enigma -rr

SubstitutedExpression

--distinct=""
--answer="SOLUTION"

# use lowercase symbols for carries
--symbols="ABCDEGHILMNOPRSTUYabcdefghi"
--invalid="0,IOT"
--invalid="2-9,abcdefghi"

# neaten up the output
--template=""
--solution="ABCDEGHILMNOPRSTUY"

# the entire sum
"INTHISADDITIONSUMNINEDIGITSAREEACHREPRESENTEDBY + ONELETTERANDONEDIGITISREPRESENTEDBYNINELETTERS = TDODRRITECIPADAABSDLOTRSORANOHMIAGSAOTUDAYDOEOE"

# verify the digit count in the solution
--code="v = lambda ds: sorted(ds.count(d) for d in irange(0, 9))"

"v([A, B, C, D, E, G, H, I, L, M, N, O, P, R, S, T, U, Y]) == [1, 1, 1, 1, 1, 1, 1, 1, 1, 9]"

# to speed things up we break down the sum in a sequence of partial
# sums starting from the rightmost column (in groups of 2)
"BY + RS + 0 = aOE"
"ED + TE + a = bOE"
"NT + ET + b = cYD"
"SE + EL + c = dDA"
"RE + IN + d = eTU"
"EP + YN + e = fAO"
"HR + DB + f = gGS"
"AC + TE + g = hIA"
"EE + EN + h = iHM"
# by this stage we have used all the letters at least once

      Solution: SOLUTION = 78665482

      The assignment of letters to digits is:

      A=9 D=0 E=3 I=4 N=2 O=8 R=1 S=7 T=5; {BCGHLMPUY}=6

      so the sum is:

        42564790045482766242304645791339661361373253066
+  8236355319208230464547136137325306624236355317
  -----------------------------------------------
= 50801145364690996706851781928664967985609608383
  ===============================================

      This is the only solution, even if the 18 symbols are grouped together differently (i.e. not 9 symbols standing for 1 digit each, and 9 all standing for the same remaining digit).

      Like

      • Jim Randell's avatar

        Jim Randell 3:50 pm on 27 April 2023 Permalink | Reply

        Instead of splitting the sum manually we can use the [[ SubstitutedExpression.split_sum ]] solver from the enigma.py library to do it for us.

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

        Run: [ @replit ]

        #! python3 -m enigma -rr

SubstitutedExpression.split_sum

--distinct=""
--invalid="0,IOT"
--answer="SOLUTION"
--split=4

# the entire sum
"INTHISADDITIONSUMNINEDIGITSAREEACHREPRESENTEDBY + ONELETTERANDONEDIGITISREPRESENTEDBYNINELETTERS = TDODRRITECIPADAABSDLOTRSORANOHMIAGSAOTUDAYDOEOE"

# verify the digit count in the solution (9 digits have 1 symbol, 1 digit has 9 symbols)
--code="check = lambda ds: multiset.from_seq(ds.count(d) for d in irange(0, 9)) == {1: 9, 9: 1}"
--extra="check([A, B, C, D, E, G, H, I, L, M, N, O, P, R, S, T, U, Y])"

# neaten up the output
--template=""

        Like

  • Unknown's avatar

    Jim Randell 7:01 am on 26 March 2019 Permalink | Reply
    Tags:   

    Brainteaser 1505: Waste not … 

    From The Sunday Times, 14th July 1991 [link]

    The “tangram” is an ancient Chinese puzzle. It consists of seven pieces which can be formed into a square (as shown) and into many other artistic shapes.

    The middle-sized triangle, the square and the parallelogram are all twice the area of the smaller triangles, and half the area of the larger ones. All the angles are 45, 90 or 135 degrees. And in my version the lengths of the shorter sides of the largest triangles are 7 cm.

    I have a thin rectangular sheet of card 70 cm by 91 cm from which I wish to cut as many such sets of tangrams as possible with the minimum amount of wastage.

    How many complete sets can I make?

    The text of this puzzle is taken from the book Brainteasers (2002), so may differ from the puzzle originally published in the newspaper.

    [teaser1505]

     
    • Jim Randell's avatar

      Jim Randell 7:03 am on 26 March 2019 Permalink | Reply

      The Tangram square shown, has sides measuring 7√2 cm. Which gives it an area of 98 cm².

      The 70 cm × 91 cm piece of card has an area of 6370 cm².

      So there is potentially enough card to make 65 complete sets with no wastage.

      However the square shown does will not fit into the length or width of the card an exact number of times.

      My solution is cut the card into 7 cm × 7 cm squares. This divides the card into 10 × 13 = 130 squares.

      We then rearrange the Tangram into two squares:

      These squares also measure 7 cm × 7cm.

      So, we then cut 65 of the squares using pattern A, and the remaining 65 sets using pattern B, giving us 65 complete Tangram sets.

      Solution: We can make 65 sets, with no wastage.

      Like

    • Lise Andreasen's avatar

      Lise Andreasen 7:28 am on 19 April 2024 Permalink | Reply

      Neat.

      Like

  • Unknown's avatar

    Jim Randell 7:08 am on 21 March 2019 Permalink | Reply
    Tags:   

    Teaser 1986: Protracted calculation 

    From The Sunday Times, 8th October 2000 [link]

    In the circle illustrated the numbers represent the sizes of the sectors:

    By combining adjacent ones it is possible to find sectors in this circle of sizes 1, 2, 3, … all the way up to 13 (13 being the whole circle). For example:

    7 = 4 + 1 + 2.

    In a similar fashion, given a circle divided into five sectors in a particular way, it is possible to combine adjacent sectors to give sizes 1, 2, 3, … up to the biggest possible in the circumstances.

    What, in increasing order, are the sizes of the five sectors?

    The text of this puzzle is taken from the book Brainteasers (2002), the wording differs only slightly from the puzzle originally published in the newspaper.

    [teaser1986]

     
    • Jim Randell's avatar

      Jim Randell 7:09 am on 21 March 2019 Permalink | Reply

      If the circle is divided into k sectors, then for each starting sector (and there are k of them) we can make a contiguous region consisting of 1, 2, 3, …, (k − 1) sectors. We don’t make a region of k sectors because that is the whole circle, so we add that in separately giving a total number of arrangements of:

      n(k) = k(k − 1) + 1 = k² − k + 1

      To make the arrangements correspond to the numbers 1, 2, 3, … n(k), the whole circle needs to correspond to the value n(k), and there needs to be a single sector corresponding to the number 1. So we place the number 1 in the first sector, and then distribute the remaining (n(k) − 1) between the remaining (k − 1) sectors.

      This Python 3 program finds the solution in 83ms.

      Run: [ @replit ]

      from itertools import permutations
from enigma import (irange, arg, printf)

# generate (non-empty) tuples of adjacent sectors
def sectors(k):
  # consider n consecutive sectors
  for n in irange(1, k - 1):
    # possible start sector
    for i in irange(0, k - 1):
      yield tuple((i + j) % k for j in irange(0, n - 1))
  # the whole circle
  yield tuple(irange(0, k - 1))

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

# number of sectors to divide the circle into
k = arg(5, 0, int, prompt="number of sectors")
assert k > 1

# make a list of adjacent sectors
ss = list(sectors(k))
t = len(ss)
printf("[k={k}: {t} arrangements]")

# put 1 at sector 0, and decompose the remainder
for d in decompose(t - 1, k - 1, 2):
  for p in permutations(d):
    if p[0] > p[-1]: continue
    s = (1,) + p
    # calculate the values of adjacent sectors
    vs = set(sum(s[i] for i in x) for x in ss)
    if len(vs) == t:
      printf("{s}")

      Solution: The five sectors have values: 1, 2, 3, 5, 10 (in numerical order).

      They can be arranged like this:

      As well as the example given it is also possible to make a circle with 4 sectors using the values: 1, 3, 2, 7.

      The program is suitable for experimenting with small values of k. (One simple way to improve the program is to note that as well as a 1 sector, we will also need a 2 sector in the remaining decomposition).

      Here are the number of solutions for various values of k:

       k  n(k)  solutions
 1     1    1
 2     3    1
 3     7    1
 4    13    2
 5    21    1
 6    31    5
 7    43    0
 8    57    6
 9    73    4
10    91    6
11   111    0
12   133   18
13   157    0
14   183   20
...

      (See: OEIS A058241 [ link ]).

      We’ve come across the following formula before:

      n(k) = k^2 − k + 1

      Specifically in the exploration of Teaser 2907, where it is the number of elements in a finite projective plane of order (k − 1).

      The fact that there is no solution for (k = 7, n = 43), (k = 11, n = 111) and (k = 13, n = 157) makes me wonder if there is a link with projective planes, as finite projective planes of order 6, 10, and 12 (probably) do not exist.

      For a more efficient way to generate “magic circles” see my comment on Enigma 985.

      Like

      • Frits's avatar

        Frits 11:47 am on 13 June 2022 Permalink | Reply

        @Jim,

        You might use (and in Enigma 985):

           
for x in irange(m, t - n * (n - 1) // 2):

        in decompose() as we need different numbers. It doesn’t seem to make much of a difference in the performance.

        Like

        • Jim Randell's avatar

          Jim Randell 11:29 am on 14 June 2022 Permalink | Reply

          @Frits: If I were to re-write the code now I would probably just use [[ decompose() ]] from enigma.py (and [[ tuples() ]] to generate the adjacent sectors). [See: @replit]

          from enigma import (irange, tuples, decompose, arg, printf)

# generate (non-empty) tuples of adjacent sectors
def sectors(k):
  # the whole circle
  t = tuple(irange(k))
  # consider n consecutive sectors
  for n in irange(1, k - 1):
    yield from tuples(t, n, circular=1)
  # and the whole circle
  yield t

# number of sectors to divide the circle into
k = arg(5, 0, int)
assert k > 1

# make a list of adjacent sectors
ss = list(sectors(k))
t = len(ss)
printf("[k={k}: {t} arrangements]")

# put 1 at sector 0, and 2 somewhere, and decompose the remainder
for d in decompose(t - 3, k - 2, increasing=0, sep=1, min_v=3, fn=list):
  # insert 2 somewhere
  for i in irange(0, (0 if k == 2 else k - 3)):
    s = list(d)
    s.insert(i, 2)
    if s[0] > s[-1]: continue
    # insert 1 at sector 0
    s.insert(0, 1)
    # calculate the value for adjacent sectors
    vs = set(sum(s[i] for i in x) for x in ss)
    if len(vs) == t:
      printf("{s}", s=tuple(s))

          But using magic_circles.py gives a much shorter and faster program:

          from enigma import (arg, printf)
from magic_circles import magic_circle

# number of sectors to divide the circle into
k = arg(5, 0, int, prompt="number of sectors")
assert k > 1

# find magic k-circles
for s in magic_circle(k):
  # output solution
  printf("{s}")

          Like

  • Unknown's avatar

    Jim Randell 6:59 am on 14 March 2019 Permalink | Reply
    Tags: by: Fred Neville   

    Brainteaser 1795: Dicey columns 

    From The Sunday Times, 9th February 1997 [link]

    A boy amused himself by building three separate columns of some equal-sized dice. In each column each die was placed squarely on the one below it. He then looked at the tops of the columns, read each as a digit, and then read the digits together to form one long number.

    For example, had the tops been:

    then he would have read 113.

    He was surprised to find that the number which he read equalled the total number of visible spots all around and on top of his three columns of dice. He also multiplied together the three numbers from the tops of the columns and found that the answer equalled the total number of dice which he had used.

    What was that total number of visible spots?

     

    For a more challenging Teaser try to find a corresponding situation with more than three columns of dice. There is only one other possibility.

     

    The text of this puzzle is taken from the book Brainteasers (2002), so may differ from the puzzle originally published in the newspaper.

    In fact, the puzzle published in the paper was the more challenging variation.

    [teaser1795]

     
    • Jim Randell's avatar

      Jim Randell 7:01 am on 14 March 2019 Permalink | Reply

      Suppose the tops of the three columns show A, B, C.

      Opposite faces on a die sum to 7, so each die shows 14 spots on the vertical sides, and the top dice also show A, B, C, so if there are n dice the total number of spots visible is:

      14n + (A + B + C) = ABC

      (where ABC is an alphametic expression).

      Also the number of dice is given by:

      n = A × B × C

      which gives us the following alphametic expression to solve:

      (14 × A × B × C) + (A + B + C) = ABC

      where A, B, C are limited to be digits from 1 to 6.

      This can easily be solved using the [[ SubstitutedExpression() ]] solver from the enigma.py library.

      Run: [ @repl.it ]

      >>> python enigma.py SubstitutedExpression --distinct="" --digits="1-6" "14 * (A * B * C) + (A + B + C) = ABC"
(14 * (A * B * C) + (A + B + C) = ABC)
(14 * (1 * 3 * 3) + (1 + 3 + 3) = 133) / A=1 B=3 C=3
[1 solution]

      Solution: The total number of visible spots was 133.

      So there are 9 dice in total (3 columns of 3 dice each).

      In the book the puzzle then goes on to suggest:

      For a more challenging Teaser try to find a corresponding situation with more than three columns of dice. There is only one other possibility.

      We can try the same thing with four dice, showing A, B, C, D:

      >>> python enigma.py SubstitutedExpression --distinct="" --digits="1-6" "14 * (A * B * C * D) + (A + B + C + D) = ABCD"
(14 * (A * B * C * D) + (A + B + C + D) = ABCD)
(14 * (2 * 5 * 3 * 6) + (2 + 5 + 3 + 6) = 2536) / A=2 B=5 C=3 D=6
[1 solution]

      So the solution to this extra puzzle is with 180 dice (4 columns of 45 dice each), showing 2536 visible spots.

      There are no solutions for 5 dice, at least not reading the numbers on top of the dice as a base 10 number. If we read them as a base 8 number then there are 5 solutions with 5 dice (and 1 with 4 dice, and 4 with 3 dice). (You can try it by adding a [[ --base=8 ]] argument to the commands).

      Like

      • Jim Randell's avatar

        Jim Randell 2:43 pm on 14 March 2019 Permalink | Reply

        Writing:

        (14 × A × B × C) + (A + B + C) = 100 × A + 10 × B + C

        we can simplify this to:

        (99 × A + 9 × B) / (14 × A × B) = C

        So we only needs to consider values of A and B to derive C:

        % python enigma.py SubstitutedExpression --distinct="" --digits="1-6" "div(99 * A + 9 * B, 14 * A * B) = C
(div(99 * A + 9 * B, 14 * A * B) = C)
(div(99 * 1 + 9 * 3, 14 * 1 * 3) = 3) / A=1 B=3 C=3
[1 solution]

        The improvement in run time (if any) is negligible.

        However, this gives us a manual way to solve the puzzle.

        C is an integer between 1 and 6, and as the denominator of the expression for C has a divisor of 7 then so must the numerator. In fact it must be the case that 7 divides (11A + B). So for any given value of A there is only a single value for B that is possible, from which we can calculate potential values for C:

        A = 1 → B = 3 → C = 3 (Solution)
        A = 2 → B = 6 → C = 3/2
        A = 3 → B = 2 → C = 15/4
        A = 4 → B = 5 → C = 63/40
        A = 5 → B = 1 → C = 36/5
        A = 6 → B = 4 → C = 15/8

        And only one value for A gives a viable value for C.

        Like

    • GeoffR's avatar

      GeoffR 7:29 pm on 8 August 2019 Permalink | Reply

      For three columns of dice:

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

var 1..6: t1; var 1..6: t2; var 1..6: t3;  % top numbers on 3 dice
var 1..20: n;  % number of dice per column

% total number of visible spots for 3 columns
constraint 3 * (2 * 7 * n) + t1 + t2 + t3 == 100*t1 + 10*t2 + t3;

% the three numbers from the tops of the three columns mutiplied
% together give the total number of dice
constraint t1 * t2 * t3 == 3 * n;

solve satisfy;

output ["Total number of visible spots = " ++ 
show(3 * (2 * 7 * n) + t1 + t2 + t3)
++"\nTotal number of dice = " ++ show(n * 3) ];

% Total number of visible spots = 133
% Number of dice = 9
% ----------
% ==========

      For four columns of dice:

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

% top numbers on four dice
var 1..6: t1; var 1..6: t2; var 1..6: t3; var 1..6: t4;
var 1..75: n;  % number of dice per column

% total number of visible spots for four columns
constraint 4 * (2 * 7 * n) + t1 + t2 + t3 + t4 
== 1000*t1 + 100*t2 + 10*t3 + t4;

% the four numbers from the tops of the four columns mutiplied
% together give total number of dice
constraint t1 * t2 * t3 * t4 == 4 * n;

solve satisfy;

output ["Total number of visible spots = " ++ 
show(4 * (2 * 7 * n) + t1 + t2 + t3 + t4)
++"\nTotal Number of dice = " ++ show(n * 4)
++"\nTop die numbers are " ++ show(t1) ++ ", " ++ show(t2)
++ ", " ++ show(t3) ++ " and " ++ show(t4) ];

% Total number of visible spots = 2536
% Total Number of dice = 180
% Top die numbers are 2, 5, 3 and 6
% ----------
% ==========

      Like

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