S2T2 | Solving Sunday Times Teasers

Recent Updates Page 47 Toggle Comment Threads | Keyboard Shortcuts

Jim Randell 8:42 am on 23 February 2021 Permalink | Reply
Tags: by: Richard England ( 9 ), flawed ( 56 )
Teaser 2777: Summing up 2015
From The Sunday Times, 13th December 2015 [link] [link]

I asked Harry and Tom to write down three numbers that between them used nine different digits and which added to 2015. They each succeeded and one of Harry’s three numbers was the same as one of Tom’s. I noticed that Harry’s three numbers included a perfect square and Tom’s included a higher perfect square.

What were those two squares?

[teaser2777]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Frits and Jim Randell are discussing. Toggle Comments
- Jim Randell 8:44 am on 23 February 2021 Permalink | Reply
  As stated there are multiple solutions to the puzzle.
  
  Having tackled similar problems before it seems likely that the intention of the setter is:
  
  “… three numbers that between them used nine different digits, each of them [exactly] once …”
  
  or possibly:
  
  “… three 3-digit numbers that between them used nine different digits …”
  
  Any solution for the latter will appear as a solution for the former, so we will use the first one to solve the puzzle (as it turns out it does give a unique answer).
  
  The following Python code generates possible sums that use a square and 2 other numbers to produce the required total, and where each of 9 digits is used exactly once in the summands.
  
  It then choose sums that use different squares, but have one of the other numbers in common.
  
  It runs in 95ms.
  
  Run: [ @repl.it ]
```
from enigma import (
  cproduct, powers, inf, is_duplicate, irange, concat, multiset,
  group, unpack, subsets, intersect, join, arg, printf
)

# target sum
Y = arg(2015, 0, int)
printf("[Y={Y}]")

# generate (s, a, b) sums, s is square, s + a + b = Y
def generate(Y):
  # consider squares
  for s in powers(0, inf, 2):
    if s > Y: break
    if is_duplicate(s): continue

    # find sums: s + a + b = Y
    t = Y - s
    for a in irange(0, t // 2):
      b = t - a
      # check for sums with 9 different digits
      ds = concat(s, a, b)
      # check for 9 different digits
      if len(ds) == 9 and len(set(ds)) == 9:
        yield (s, a, b)

# group sums by the square
d = group(generate(Y), by=unpack(lambda s, a, b: s))

# collect the squares involved
r = multiset()

# consider squares for Harry and Tom
for (sH, sT) in subsets(sorted(d.keys()), size=2):

  # choose decompositions
  for (dH, dT) in cproduct([d[sH], d[sT]]):

    # that share a number
    if intersect([dH, dT]):
      printf("[H = {dH}; T = {dT}]", dH=join(dH, sep=" + "), dT=join(dT, sep=" + "))
      r.add((sH, sT))

# output solutions
for (k, v) in r.most_common():
  printf("squares = {k} [{v} solutions]", k=join(k, sep=", "))
```
  Solution: Harry’s square was 324. Tom’s square was 784.
  
  There are two ways to arrive at the solution:
  
  Harry: 324 + 785 + 906 = 2015
  Tom: 784 + 325 + 906 = 2015
  
  Harry: 324 + 786 + 905 = 2015
  Tom: 784 + 326 + 905 = 2015
  
  The summands in each sum use all the digits exactly once except for the digit 1.
  
  To see the multiple solutions without the restriction that each of the 9 digits is used exactly once, you can remove line 15 and the [[ len(ds) == 9 ]] clause from line 24.
  
  The same puzzle could have been set in 2019, and had the same answer.
  
  If the puzzle were set in 2022, there would only be one way to arrive at the (different) answer.
  
  LikeLike
- Frits 2:04 pm on 23 February 2021 Permalink | Reply
  I assumed Harry’s and Tom’s squares were not the number they shared (ABCD).
```
from enigma import SubstitutedExpression, is_square

# the alphametic puzzle
p = SubstitutedExpression(
  [
  # Use 4-digit numbers as sum is limited to 2015
  
  # to reduce the output assume EFGH (Harry) and MNOP (Tom) 
  # are both perfect squares
  "is_square(EFGH)",
 
  # use a variable as right hand side to reduce the number of loops
  "2015 - ABCD - EFGH = IJKL",
  
  # nine different digits
  "len(str(ABCD) + str(EFGH) + str(IJKL)) == \
   len(set(str(ABCD) + str(EFGH) + str(IJKL))) == 9",
  
  # Tom's included a higher perfect square
  "MNOP > EFGH and is_square(MNOP)",
 
  # use a variable as right hand side to reduce the number of loops
  "2015 - ABCD - MNOP = QRST",
  
  # nine different digits
  "len(str(ABCD) + str(MNOP) + str(QRST)) == \
   len(set(str(ABCD) + str(MNOP) + str(QRST))) == 9",
  ],
  answer="EFGH, MNOP",
  d2i=dict([(k, "AEIMQ") for k in range(3, 10)]),
  verbose=0,
  distinct="",
)

# Print answers
sols = set(sol for (_, sol) in p.solve())
print(f"answer = {sols}")
```
  LikeLike
Reply Cancel reply
Required fields are marked *

Name *

Email *

Website

Notify me of new comments via email.
Notify me of new posts via email.
Δ
Jim Randell 8:53 am on 21 February 2021 Permalink | Reply
Tags: by: F. Moore ( 2 )
Brain-Teaser 23: [Money sharing]
From The Sunday Times, 27th August 1961 [link]

A man divided 8s. 4d. among his three sons so that the difference between the shares of the eldest and youngest, expressed in halfpence, was a perfect square. The total of Alan’s and Bob’s shared was an exact multiple of 5½d.; the total of Bob’s and Clive’s shares an exact multiple of 6½d.; and the total of Alan’s and Clive’s shares an exact multiple of 9½d.

What was the name of the second son, and what was his share?

This puzzle was originally published with no title.

[teaser23]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
John Crabtree, Jim Randell, Hugh Casement, and 1 other are discussing. Toggle Comments
- Jim Randell 8:55 am on 21 February 2021 Permalink | Reply
  1s = 12d.
  
  Working in half-pennies (hp) the total amount to distribute is 100 d = 200 hp.
  
  And we are told:
  
  11 | (A + B)
  13 | (B + C)
  19 | (A + C)
  
  And the difference between two of the numbers is a square number of half pennies.
  
  The following Python program runs in 53ms.
  
  Run: [ @repl.it ]
```
from enigma import irange, is_square, div, printf

# solve the equations
def solution(middle, AB, AC, BC):
  A = div(AB + AC - BC, 2)
  B = div(AB + BC - AC, 2)
  C = div(AC + BC - AB, 2)
  if not any(x is None or x < 0 for x in (A, B, C)):
    # output solution
    printf("A={A} hp, B={B} hp, C={C} hp; middle = {middle}")

# A + C is some multiple of 19
for AC in irange(19, 200, step=19):

  # B + C is some multiple of 13
  for BC in irange(13, 200, step=13):

    # A + B is some multiple of 11
    # and (A + B) + (B + C) + (A + C) = 2(A + B + C) = 400
    AB = 400 - (AC + BC)
    if AB % 11 > 0: continue

    # one of the differences is a square
    # B - C = (A + B) - (A + C)
    if is_square(abs(AB - AC)): solution('A', AB, AC, BC)
    # A - C = (A + B) - (B + C)
    if is_square(abs(AB - BC)): solution('B', AB, AC, BC)
    # A - B = (A + C) - (B + C)
    if is_square(abs(AC - BC)): solution('C', AB, AC, BC)
```
  Solution: The middle son was Clive. His share was 45d = (3s 9d).
  
  The shares are:
  
  A: 5 hp = 2.5 d
  B: 105 hp = 52.5 d (= 4s 4.5d)
  C: 90 hp = 45 d (= 3s 9d)
  
  And we see:
  
  A + B = 110 hp = 10× 11 hp
  B + C = 195 hp = 15× 13 hp
  A + C = 95 hp = 5× 19 hp
  
  And the difference between the eldest and the youngest is: B − A = 10² hp.
  
  LikeLike
- Frits 11:53 am on 21 February 2021 Permalink | Reply
```
from enigma import SubstitutedExpression, is_square, peek

# the alphametic puzzle
p = SubstitutedExpression(
  [# A = AST, B = BVW, C = CYZ
  
  # start with the most restrictive constraint
  
  # A + C is some multiple of 19
  "(AST + CYZ) % 19 == 0",
  
  # divide 200 half-pennies over 3 sons
  "200 - AST - CYZ = BVW", 
  
  # B + C is some multiple of 13
  "(BVW + CYZ) % 13 == 0",
  
  # A + B is some multiple of 11
  "(AST + BVW) % 11 == 0",
  
  # difference between the eldest and youngest was a perfect square
  "peek(2 - i for (i, (x, y)) in \
   enumerate(zip([AST, CYZ, BVW], [BVW, AST, CYZ])) \
   if is_square(abs(x - y))) = I",
  ],
  answer="I, [AST, BVW, CYZ][I]",
  d2i=dict([(2, "ABC")] + [(k, "ABCI") for k in range(3, 10)]),
  distinct="",
  reorder=0,
  verbose=0)   

for (_, ans) in p.solve():
  print(f"{['Alan', 'Bob', 'Clive'][ans[0]]} with share {ans[1]} half-pennies")
```
  LikeLike
  - Jim Randell 12:49 pm on 21 February 2021 Permalink | Reply
    Here’s an alternative solution using the [[ SubstitutedExpression() ]] solver:
```
from enigma import (SubstitutedExpression, subsets, is_square, printf)

# find candidate (A, B, C) values
p = SubstitutedExpression(
  [ "A + B + C == 200", "(A + B) % 11 = 0", "(B + C) % 13 = 0", "(A + C) % 19 = 0" ],
  base=201,
  distinct=(),
  answer="(A, B, C)",
  template="",
)

# look at possible (A, B, C) values
for (_, vs) in p.solve(verbose=0):
  # the values for the eldest and youngest differ by a square number
  for ((i, x), (j, y)) in subsets(enumerate(vs), size=2):
    if is_square(abs(x - y)):
      # identify the middle son
      m = "ABC"[3 - i - j]
      printf("A={vs[0]} hp, B={vs[1]} hp, C={vs[2]} hp; middle={m}")
```
    LikeLike
- Hugh Casement 1:51 pm on 21 February 2021 Permalink | Reply
  
  Theoretically Alan and Clive could each have received 57 ha’pence and Bob 86.
  Zero is also a square number! However, I doubt that is the intended solution.
  
  LikeLike
  - Jim Randell 2:02 pm on 21 February 2021 Permalink | Reply
    @Hugh: Well spotted!
    
    In my programs, both 0 and None evaluate to false, so using the return value from [[ is_square() ]] as a boolean value will reject 0. (It also doesn’t consider 0 to be allowed as a multiple of 11, 13, 19).
    
    You can explicitly check [[ is_square(...) is not None ]], or just import [[ is_square_p() ]] instead which returns a boolean.
    
    And if you do that you do indeed get two solutions:
```
% python teaser23b.py
A=5 hp, B=105 hp, C=90 hp; middle = C
A=57 hp, B=86 hp, C=57 hp; middle = B
```
    The published solution is: “Clive, 3s 9d”.
    
    Perhaps the setter intended the shares to be three different values.
    
    LikeLike
- John Crabtree 6:58 pm on 22 February 2021 Permalink | Reply
  
  Working in 1/2d, then A + B + C = 200
  A + B = 11p, p ≤ 18
  B + C = 13q, q ≤ 15
  A + C = 19r, r ≤ 10
  Summing the three gives 400 = 11p + 13q + 19r
  Using r as a variable as it has the fewest possible values:
  B = 200 – 19r, p = 8 + 3r mod 13, q = 3 + 7r mod 11 which leads to
  A = 31 + 52r mod 143
  C = 112 + 110r mod 143
  It is then straightforward to manually generate a table of values for A, B and C for each r. r = 1, 2 and 4 give A+B+C = 343. r = 3 and r = 5 to 10 give A+B+C = 200 and include the two solutions noted by Jim.
  
  LikeLike
Jim Randell 4:51 pm on 19 February 2021 Permalink | Reply
Tags: by: Stephen Hogg ( 65 )
Teaser 3048: Nero Scrag from Carregnos
From The Sunday Times, 21st February 2021 [link] [link]

Our holiday rep, Nero, explained that in Carregnos an eight-digit total of car registrations results from combinations of three Greek capital letters after four numerals (e.g. 1234 ΩΘΦ), because some letters of the 24-letter alphabet and some numerals (including zero) are not permitted.

For his own “cherished” registration the number tetrad is the rank order of the letter triad within a list of all permitted letter triads ordered alphabetically. Furthermore, all permitted numeral tetrads can form such “cherished” registrations, but fewer than half of the permitted letter triads can.

Nero asked me to guess the numbers of permitted letters and numerals. He told me that I was right and wrong respectively, but then I deduced the permitted numerals.

List the permitted numerals in ascending order.

[teaser3048]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell, Tony Brooke-Taylor, Frits, and 1 other are discussing. Toggle Comments
- Jim Randell 5:29 pm on 19 February 2021 Permalink | Reply
  Nero Scrag is an anagram of Carregnos, which itself may be written as “car reg nos” = “car registration numbers”.
  
  The wording of the puzzle is a bit convoluted, but I think there is a unique solution.
  
  This Python program runs in 56ms.
  
  Run: [ @repl.it ]
```
from enigma import (irange, ndigits, group, unpack, printf)

# generate candidate solutions
# return (number-of-digits, number-of-letters, total-number-of-digit-tetrads, total-number-of-letter-triads)
def generate():
  # consider number of digits available (< 9)
  for nd in irange(1, 8):
    # number of digit tetrads
    td = nd**4

    # consider number of letters available (< 23)
    for ns in irange(1, 22):
      # number of letter triads
      ts = ns**3

      # total number of possible registrations
      t = td * ts
      # is 8 digits
      if not (ndigits(t) == 8): continue

      # all digit tetrads correspond to a letter triad
      # so remove impossible situations
      if 1111 * nd > ts: continue

      # fewer than half the letter triads correspond to number tetrads
      if not (ts > 2 * td): continue

      printf("[nd={nd} -> td={td}; ns={ns} -> ts={ts}; t={t}]")
      yield (nd, ns, td, ts)

# group candidate solutions by the number of letters (which the setter guessed right)
d = group(generate(), unpack(lambda nd, ns, td, ts: ns))

# look for a group with only two candidates
for (k, vs) in d.items():
  if len(vs) != 2: continue
  # look for candidates with only one set of digits
  for (nd, ns, td, ts) in vs:
    # are the digits forced to be 1..nd?
    if 1111 * (nd + 1) > ts:
      # output solution
      printf("digits = 1..{nd} [nd={nd} ns={ns}]")
```
  Solution: The digits are: 1, 2, 3, 4, 5, 6, 7.
  
  The setter guessed there were 20 letters and 6 digits.
  
  He was right about the number of letters, but wrong about the number of digits.
  
  The only other possibility with 20 letters is 7 digits, so that must be the correct number of digits.
  
  With 20 digits there are 20^3 = 8000 possible letter triads (which can be enumerated from 1 to 8000).
  
  The lowest valued set of 7 digits is 1..7, and the highest numeric tetrad in this case is 7777, which corresponds to an entry in the enumeration of letter triads.
  
  If not all of the digits from 1..7 are permissible, then the highest digit would be 8 or 9, and the highest numeric tetrad would be 8888 or 9999, but neither of these correspond to entries in the enumeration of letter triads. So these situations are not possible.
  
  So we know that the set of permissible digits must be 1..7.
  
  This means there are 2401 digit tetrads and 8000 letter triads.
  
  Every digit tetrad (from 1111 to 7777) corresponds to one of the letter triads, but any letter triad that has an index containing a 0, 8, or 9 does not have a corresponding digit tetrad. (Where we represent the indices with leading zeros to pad them to 4 digits, if necessary). There are 5599 of these, so less than half of the letter triads have a corresponding digit tetrad, as required.
  
  LikeLike
  - Frits 9:10 pm on 19 February 2021 Permalink | Reply
    
    Ah, I see you now have a different answer. I couldn’t understand your previous solution.
    This is a puzzle where I needed your code to understand the puzzle.
    
    LikeLike
    - Jim Randell 7:24 am on 20 February 2021 Permalink | Reply
      
      @Frits: The wording of the puzzle is a bit complicated, but I think it makes sense.
      
      In my original program I got the final check the wrong way round, but I have corrected that now.
      
      LikeLike
  - Jim Randell 8:14 am on 28 February 2021 Permalink | Reply
    
    Here is a more detailed explanation of the logic used in the program:
    
    Some digits (including 0) are not permitted, so there are fewer than 9 digits available.
    
    And some letters are not permitted, so there are fewer than 23 letters available.
    
    If there are nd digits available, then we can make nd^4 possible digit tetrads.
    
    And if there are ns letters (symbols) available, then we can make ns^3 possible letter triads.
    
    The total number of registrations that can be made is therefore: (nd^4) × (ns^3), and this must be an 8-digit number.
    
    Also the letter triads can be enumerated (in lexicographical order) from 1 to ns^3.
    
    And each digit tetrad provides a valid index into the list of enumerated letter triads.
    
    So if d is a permitted digit then the digit tetrad dddd must be an index into the list of letter triads.
    
    So: 1111 × d ≤ ns^3.
    
    And with nd possible digits, that exclude the digit 0, the maximum permitted digit must be at least nd.
    
    So we can skip situations where: 1111 × nd > ns^3, as there are no viable digit sets.
    
    We are also told that fewer than half the letter triads correspond to digit triads.
    
    So: (ns^3) > 2 × (nd^4)
    
    These restrictions limit the possible values of nd and ns.
    
    The setter makes guesses for these values, and gets ns right and nd wrong.
    
    But from this information he is able to deduce, not just the value of nd, but the actual set of permitted digits.
    
    So from his guess for ns, we know there must be 2 possibilities for nd. On being told the candidate he chose was wrong, the setter can deduce that the other candidate must be the correct one.
    
    So now he knows the values of both ns and nd. But he can go further and deduce the actual set of permitted digits.
    
    This means that there can only be one possible set of digits for the values of ns and nd.
    
    The set with the smallest valued digit tetrads will be {1..nd}, and we already know that the value (1111 × nd) indexes into the list of letter triads.
    
    And we want to exclude all other possible sets. A set that excludes just one of the digits 1..nd would have a maximum digit of (nd + 1), and in order for this to be excluded the maximum digit tetrad of (1111 × (nd + 1)) must be larger than the maximum index into the list of letter triads.
    
    i.e.: (1111 × (nd + 1)) > ns^3
    
    In that case only the set of digits {1..nd} forms a viable set, so this provides the answer.
    
    LikeLike
- Brian Gladman 10:44 pm on 19 February 2021 Permalink | Reply
  
  @Jim I have the same logic up to line 30 but I don’t see the rationale for only considering solutions with two candidates (line 36). But it does seem necessary to obtain a unique solution.
  
  LikeLike
  - Jim Randell 10:54 pm on 19 February 2021 Permalink | Reply
    
    @Brian: My reasoning was that when the setter guesses the number of permissible letters and digits, and gets the number of letters right, but the number of digits wrong, he is then able to deduce the correct number of digits. So for the number of letters guessed, there must be only two options for the number of digits. The setter went for the wrong one to begin with, but on being told he was wrong he was able to deduce the correct number, so there was only one other option remaining.
    
    LikeLike
    - Brian Gladman 11:37 pm on 19 February 2021 Permalink | Reply
      
      Thanks Jim. But it is logical for the setter to apply your line 40 logic before he is asked to guess and if he does this he only needs the first of the two answers to deduce the solution. So we have to assume he is acting illogically in order to deduce a unique solution, which seems a bit odd to me.
      
      LikeLike
      - Jim Randell 7:17 am on 20 February 2021 Permalink | Reply
        
        @Brian: But the setter doesn’t know he is going to be able to deduce the set of digits before he makes his guesses. Once he gets the answers however he knows how many letters there are (as he guessed that correctly), and as explained above there is only one candidate remaining for the number of digits, so he knows that too.
        
        He then realises that given those values for the number of digits and number of letters, there is only one possible set of digits that can work, so he can deduce what the digits are (not just how many of them there are).
        
        We aren’t told what guesses the setter made, but the fact that the scenario unrolled as described lets us work out what the setters guesses must have been, and so we can also determine what the set of digits must be, and hence answer the puzzle.
        
        LikeLike
        
        Brian Gladman 12:54 pm on 20 February 2021 Permalink | Reply
        
        Thanks Jim. My logic was originally the same as yours (up to your line 30) but I have now changed it to avoid the assumption (on your line 23) that the number of digits in use and the maximum digit in use are the same. We now arrive at the same answer in different ways.
        
        LikeLike
        
        Jim Randell 1:45 pm on 20 February 2021 Permalink | Reply
        
        @Brian: I don’t assume the maximum digit is the same as the number of digits, only it is at least this value (which it must be, as 0 is excluded).
        
        But I think in your method you also need to consider that the maximum digit could be 9.
        
        LikeLiked by 1 person
        
        Brian Gladman 5:09 pm on 20 February 2021 Permalink | Reply
        
        @Jim. Good point, changed now.
        
        LikeLike
        
        Tony Brooke-Taylor 9:39 am on 21 February 2021 Permalink | Reply
        
        Jim, doesn’t your line 40 forbid cases where the maximum digit (int(ts/1111)) is greater than the number of digits (ns)? I am sure we must apply that condition somewhere to get a unique answer, and it is the only way our subject could have inferred all the digits.
        
        I applied almost exactly the same logic as you but I did a bit of analysis first to reduce the ranges for the two main loops. We only need to explore the space defined by 10^7 <=T<10^8, where T=nd^4*ns^3. Reduces run-time by about half.
        
        LikeLike
        
        Jim Randell 9:54 am on 21 February 2021 Permalink | Reply
        
        @Tony: Yes. That line is there to ensure there is only one possible set of digits at that stage, because if there were more than one the setter would not have been able to deduce what the permissible digits are.
        
        And there is only one set of digits if the maximum digit is constrained to be the same as the number of digits (as 0 is excluded). So the set of digits is {1..nd}.
        
        LikeLike
- Frits 12:58 am on 21 February 2021 Permalink | Reply
  Under the assumption that “some letters” means “at least 2 letters”
```
from collections import defaultdict
from enigma import SubstitutedExpression, divc

# the alphametic puzzle
p = SubstitutedExpression(
  [
  #  N = number of permitted numerals
  # LE = number of permitted letters
  
  # the maximum possible car registration has at least 8 characters:
  # formula: no_numerals ** 4  *  no_letters ** 3 >= 10 ** 7 
  #
  # choose the highest number of permitted letters (twenty two)  
  # to calculate the lowest number of permitted numbers
  "N >= (divc(10 ** 7, 22 ** 3) ** 0.25)",
  "N < 9",
  
  "LE >= (divc(10 ** 7, N ** 4) ** (1 / 3))",
  "LE < 23",
  
  # consider the maximum 4-digits numbers (1111 * highest digit)
  # the smallest must not be greater than the number of letter triads
  "1111 * N <= LE ** 3",
  
  # fewer than half the letter triads correspond to number tetrads
  "LE ** 3 > 2 *( N ** 4)",
  ],
  answer="LE, N, LE ** 3",
  d2i=dict([(0, "N")] + [(k, "L") for k in range(3, 10)]),
  distinct="",
  verbose=0)   

# collect and sort solutions
sols = sorted(y for _, y in p.solve())

# group solutions by number of permitted letters
d = defaultdict(list)
for le, n, ntriads in sols:
  d[le].append([n, ntriads])
  
for k, v in d.items():
  # only with 2 options for the number of permitted numerals 
  # you can still make deductions
  if len(v) != 2: continue
  
  # "I deduced the permitted numerals"
  
  # you can only know the permitted numerals if they are 1...N
  # this must be the last entry in <v>
  
  # check that N+1 is not permitted as a numeral
  if 1111 * (v[1][0] + 1) > v[1][1]:  
    print(f"answer 1...{v[1][0]}")
```
  LikeLike
  - Tony Brooke-Taylor 9:43 am on 21 February 2021 Permalink | Reply
    
    Frits, your lines 15-19 are equivalent to the analysis I referred to in my comment to Jim. I also relaxed the assumption that ‘some’ meant ‘at least two’, and the solution still works.
    
    LikeLike
Jim Randell 9:48 am on 18 February 2021 Permalink | Reply
Tags: by: Graham Smithers ( 87 )
Teaser 2776: Winning months
From The Sunday Times, 6th December 2015 [link] [link]

I have won three Premium Bond prizes and noted the number of non-winning months between my first and second wins, and also the number between my second and third wins. Looking at the letters in the spelling of the months, I have also noted the difference between the numbers of letters in the months of my first and second wins, and also the difference between those of the months of my second and third wins. All four numbers noted were the same, and if you knew that number then it would be possible to work out the months of my wins.

What (in order of the wins) were those three months?

[teaser2776]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 9:48 am on 18 February 2021 Permalink | Reply
  The largest difference in number of letters is 6 (“May” to “September”), so we don’t need to worry about time spans longer than this.
  
  This Python program runs in 52ms.
  
  Run: [ @repl.it ]
```
from enigma import filter_unique, unpack, irange, join, printf

# month names (in English)
months = (
  'January', 'February', 'March', 'April', 'May', 'June',
  'July', 'August', 'September', 'October', 'November', 'December',
)

# month lengths
ls = set(len(x) for x in months)
M = max(ls) - min(ls)

# map (<n>, <month1>) -> <month2>
# where month1 and month2 are separated by n months
# and month2 length is different from month1 by n
d = dict()
for (m1, name) in enumerate(months):
  l1 = len(name)
  for n in irange(0, M):
    m2 = (m1 + n + 1) % 12
    if abs(l1 - len(months[m2])) == n:
      d[(n, m1)] = m2

# now look for elements (n, m1) -> m2 where (n, m2) -> m3
rs = list()
for ((n, m1), m2) in d.items():
  m3 = d.get((n, m2), None)
  if m3 is not None:
    ms = tuple(months[i] for i in (m1, m2, m3))
    rs.append((n, ms))
    printf("[n={n}: {ms}]", ms=join(ms, sep=' -> '))

# find unambiguous solutions by n
rs = filter_unique(rs, unpack(lambda n, ms: n)).unique

# output solutions
for (n, ms) in rs:
  printf("SOLUTION: n={n}, {ms}", ms=join(ms, sep=' -> '))
```
  Solution: The winning months are: February, July, December.
  
  This is the only set of months such that each adjacent pair has 4 months between them, and also differ by 4 letters.
  
  There are ambiguous solutions for values 1 and 5:
  
  1: August → October → December
  1: September → November → January
  
  5: May → November → May
  5: November → May → November
  
  LikeLike
Jim Randell 9:22 am on 16 February 2021 Permalink | Reply
Tags: by: B W M Young ( 10 )
Brain-Teaser 692: First-class post
From The Sunday Times, 20th October 1974 [link]

On Trafalgar Day each of the five Sea Lords will take over a post now occupied by one of the others. Each predicts what will happen; those whose predictions are right will get more senior posts, and those whose predictions are wrong will get more junior posts.

The most junior speaks first:

Fifth Sea Lord: “Two Sea Lords will make a direct exchange.”
Fourth Sea Lord: “The Third Sea Lord will become the Second Sea Lord.”
Third Seal Lord: “A man who makes a true prediction will take over my job.”

Of the First and Second Sea Lords each predicts the same future new post for himself.

Which post is that?

This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980). The puzzle text above is taken from the book.

[teaser692]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
John Crabtree, Jim Randell, and Frits are discussing. Toggle Comments
- Jim Randell 9:23 am on 16 February 2021 Permalink | Reply
  If the First Sea Lord and the Second Sea Lord both predict taking on the same position, I am assuming that the position cannot be that of the First or Second Sea Lord, as then one of them would have made a prediction that was impossible to fulfil (because no-one keeps their position).
  
  This Python program runs in 53ms.
  
  Run: [ @repl.it ]
```
from enigma import subsets, peek, map2str, printf

# positions
pos = (1, 2, 3, 4, 5)

# check <n> makes statement <s> is valid in map <m>
check = lambda m, n, s: (m[n] < n) == bool(s)

# find an index that maps to x
find = lambda m, x: peek(k for (k, v) in m.items() if v == x)

# consider derangements
for s in subsets(pos, size=len, select="D"):
  m = dict(zip(pos, s))

  # check the statements:

  # 5: "two will make a direct exchange"
  if not check(m, 5, (any(m[v] == k for (k, v) in m.items()))): continue

  # 4: "3 -> 2"
  if not check(m, 4, (m[3] == 2)): continue

  # 3: "a man who makes a true prediction (so is promoted) will take
  # over my job (= 3)"
  if not check(m, 3, (find(m, 3) > 3)): continue

  # 1: "1 -> x", 2: "2 -> x"
  for x in pos:
    if x == 1 or x == 2: continue
    if not(check(m, 1, (m[1] == x)) and check(m, 2, (m[2] == x))): continue

    printf("x={x}; {m}", m=map2str(m, arr="->"))
```
  Solution: The First and Second Sea Lords both predicted they would take on the role of Third Sea Lord.
  
  There are two possible maps:
  
  1→4; 2→5; 3→2; 4→1; 5→3
  1→5; 2→4; 3→2; 4→3; 5→1
  
  In both scenarios the First and Second Sea Lords are demoted (so made false predictions), and the Third, Fourth and Fifth Sea Lords are promoted (and so made true predictions).
  
  LikeLike
- Frits 10:54 am on 19 February 2021 Permalink | Reply
```
from enigma import SubstitutedExpression

def twoswap(a, b):
  z = [tuple(sorted((x, y))) for (x, y) in zip(a, b)]
  return len(set(z)) < len(z)

# the alphametic puzzle
p = SubstitutedExpression(
  [
  # (1, 2, 3, 4, 5) --> (V, W, X, Y, Z) 
  
  "sorted([V, W, X, Y, Z]) == [1, 2, 3, 4, 5]",
  
  # 5: "two will make a direct exchange
  "twoswap([1, 2, 3, 4, 5], [V, W, X, Y, Z])",
  
  # 4: "3 -> 2"
  "(X == 2 and Y < 4) or (Y == 5 and X != 2)",
   
  # 3: "a man who makes a true prediction (so is promoted) will take
  # over my job (= 3)"
  "[V, W, X, Y, Z].index(3) > 2 if X < 3 else [V, W, X, Y, Z].index(3) < 3",
  ],
  digits=range(1, 6),
  answer="{3, 4, 5}.difference({V, W})",
  env=dict(twoswap=twoswap),
  # derangement
  # 1: "1 -> x", 2: "2 -> x",  x > 2
  # we only know both statements have to be false
  d2i={1 : "VW", 2 : "VW", 3 : "X", 4 : "Y", 5 : "Z"},
  distinct="VWXYZ",
  verbose=0)   

# print answers 
answs = set([list(y)[0] for _, y in p.solve()])

for ans in answs:
  print(f"post = {ans}")
```
  LikeLike
  - Frits 11:15 am on 19 February 2021 Permalink | Reply
    
    @Jim, do you agree with V > 2 and W > 2 for 1: “1 -> x”, 2: “2 -> x”?
    We only know both statements to be false.
    
    LikeLike
    - Jim Randell 11:39 am on 19 February 2021 Permalink | Reply
      
      @Frits: I don’t see how to determine the required answer from the output of your program.
      
      LikeLike
- John Crabtree 4:37 pm on 19 February 2021 Permalink | Reply
  
  Here are a couple of ways to tackle it manually.
  The 5th SL must be correct. There are three cases to consider:
  3rd wrong, and so the 4th is wrong: 4 -> 5, 3 -> 4, 1/2 -> 3 with no possible exchange
  3rd right, 4th wrong: 3 -> 1, 4 -> 5, 5 -> 3, with no possible exchange
  3rd right, 4th right: 3 -> 2, 4/5 -> 3, 2 -> 4/5 (to allow an exchange), 5/4 -> 1, 1 -> 5/4
  
  1st and 2nd become 4th and 5th or vice versa. Assuming that a SL could not predict his current position, the 1st and 2nd SLs predicted that they would be 3rd Sea Lord.
  
  Using Boolean algebra, where 12 means 1 moves to 2 is true,
  5th SL: the statement is true
  4th SL: (41+43).32 + 45.(31+34) = 1
  3rd SL: (31+32).(43+53) + (34+35).(13+23) = 1
  Multiplying the two and removing impossible terms gives:
  41.32.53 + 43.32 + 45.31.53 + 45.34.(13+23) = 1
  These are the same four possibilities shown in the first solution. The last two do not allow an exchange. From the 5th SL:
  14.41.32.53 + 15.51.43.32 = 1, ie
  14.41.32.53.25 + 15.51.43.32.24 = 1, with the rest as before.
  
  LikeLike

Jim Randell 9:16 am on 14 February 2021 Permalink | Reply
Tags: by: C. W. Mitford

Brain-Teaser 21: [Crossnumber]

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

Across:

1a. Square of a multiple of 11.
5a. A fourth power.
8a. A multiple of 2d.
9a. A cube reversed.
11a. If added to 4d it gives a square.
12a. 3 times a prime number.
14a. A multiple of 11.
16a. A prime number.
17a. A cube, which is also the sum of three cubes.
18a. An even number.
20a. A multiple of 12.
21a. A prime number.
22a. The square of a palindromic number.

Down:

1d. The product of two consecutive numbers (neither a prime).
2d. See 8a.
3d. A cube.
4d. See 11a.
6d. The sum of the digits of 3d.
7d. The square of (6d reversed).
10d. The product of two consecutive odd numbers.
13d. The product of two consecutive even numbers.
15d. A cube.
16d. A square.
19d. An even multiple of (18a + 21a).

This puzzle was originally published with no title.

[teaser21]

Jim Randell 9:18 am on 14 February 2021 Permalink | Reply

I used the [[ SubstitutedExpression ]] solver from the enigma.py library to solve this puzzle.

The following run file executes in 333ms.

(Using the standard Python interpreter we need to provide the additional [[ --denest ]] parameter to work around the limit on statically nested blocks. This is not required if using the PyPy interpreter).

Run: [ @replit ]

#! python3 -m enigma -rr

#  A B C D E F G
#  H I J K L M N
#  P # Q R S # T
#  U V W # X Y Z
#  a b c d e f g
#  h i # # # j k
#  m n p q r s t

SubstitutedExpression

--distinct=""
--reorder=0

# 1a. = ABCD "Square of a multiple of 11"
"is_square({ABCD}) % 11 = 0"

# 11a. = QR "If added to 4d. it gives a square"
# 4d. = DKR "See 11 across"
"is_square({DKR} + {QR})"

# 8a. = HIJ "A multiple of 2d."
# 2d. = BI "See 8 across"
"{HIJ} % {BI} = 0"

# 3d. = CJQWc "A cube"
"is_cube({CJQWc})"

# 6d. = FM "The sum of the digits of 3d."
"dsum({CJQWc}) = {FM}"

# 7d. = GNTZ "The square of (6d. reversed)"
"{MF} ** 2 = {GNTZ}"

# 5a. = EFG "A fourth power"
"is_power({EFG}, 4)"

# 12a. = UVW "Three times a prime number"
"is_prime(div({UVW}, 3))"

# 1d. = AHPU "The product of two consecutive numbers (neither a prime)"
--code="
def check_1d(n):
  k = isqrt(n)
  return n == k * (k + 1) and not(is_prime(k) or is_prime(k + 1))
"
"check_1d({AHPU})"

# 13d. = Vbin "The product of 2 consecutive even numbers"
--code="
def check_13d(n):
  k = isqrt(div(n, 4))
  return n == 4 * k * (k + 1)
"
"check_13d({Vbin})"

# 16a. = ab "A prime number"
"is_prime({ab})"

# 20a. = hi "A multiple of 12"
"{hi} % 12 = 0"

# 16d. = ahm "A square"
"is_square({ahm})"

# 17a. = cde "A cube, which is also the sum of three cubes"
--code="
def check_17a(n, k=3):
  if k == 1:
    return is_cube(n)
  else:
    for x in powers(1, inf, 3):
      if k * x > n: break
      if check_17a(n - x, k - 1): return True
    return False
"
"is_cube({cde}) and check_17a({cde})"

# 10d. = LSXe "The product of 2 consecutive odd numbers"
"is_square(div({LSXe} + 1, 4))"

# 14a. = XYZ "A multiple of 11"
"{XYZ} % 11 = 0"
# 9a. = KLMN "A cube reversed"
"is_cube({NMLK})"

# 21a. = jk "A prime number"
"is_prime({jk})"

# 15d. = Yfjs "A cube"
"is_cube({Yfjs})"

# 19d. = gkt "An even multiple of (18a. + 21a.)"
"div({gkt}, {fg} + {jk}) % 2 = 0"

# 18a. = fg "An even number"
"{fg} % 2 = 0"

# 22a. = npqrs "The square of a palindrome"
"is_palindrome(nsplit(is_square({npqrs})))"

# [optional]
--template="{ABCD} {EFG} | {HIJ} {KLMN} | {P} {QR} {S} {T} | {UVW} {XYZ} | {ab} {cde} {fg} | {hi} {jk} | {m} {npqrs} {t}"
--solution=""
--header=""

Solution: The completed grid looks like this:

LikeLike

Jim Randell 4:56 pm on 12 February 2021 Permalink | Reply
Tags: by: Howard Williams ( 45 )

Teaser 3047: Some permutations

From The Sunday Times, 14th February 2021 [link] [link]

I gave Robbie three different, non-zero digits and asked him to add up all the different three-digit permutations he could make from them. As a check for him, I said that there should be three 3’s in his total. I then added two more [non-zero] digits to the [original three digits] to make [a set of] five digits, all being different, and asked Robbie’s mother to add up all the possible five-digit permutations of these digits. Again, as a check, I told her that the total should include five 6’s.

Given the above, the product of the five digits was as small as possible.

What, in ascending order, are the five digits?

I have changed the text of this puzzle slightly to make it clearer.

[teaser3047]

Jim Randell 5:10 pm on 12 February 2021 Permalink | Reply
(See also: Teaser 2863).

This Python program runs in 64ms.

Run: [ @repl.it ]
```
from enigma import irange, subsets, nconcat, nsplit, diff, multiply, group, printf

# total all permutations of a set of distinct digits
psum = lambda ds: sum(nconcat(*s) for s in subsets(ds, size=len, select="P"))

# count occurrences of digit d in number n
dcount = lambda n, d: nsplit(n).count(d)

# generate solutions
def solve():
  # permissible digits
  digits = irange(1, 9)

  # choose the initial set of 3 digits
  for ds3 in subsets(digits, size=3):
    t3 = psum(ds3)
    # there should be three 3 digits in the total
    if not(dcount(t3, 3) == 3): continue

    # now add 2 more digits to the mix
    for ds in subsets(diff(digits, ds3), size=2):
      ds5 = ds3 + ds
      t5 = psum(ds5)
      # there should be five 6 digits in the total
      if not(dcount(t5, 6) == 5): continue

      printf("[{ds3} -> {t3}; {ds5} -> {t5}]")
      yield ds5

# group solutions by product
d = group(solve(), by=multiply)

# output solutions
if d:
  k = min(d.keys())
  for ds5 in d[k]:
    printf("{ds3} + {ds2}; product = {k}", ds3=ds5[:3], ds2=ds5[3:])
```
Solution: The five digits are: 1, 2, 5, 8, 9.

There are two scenarios with a minimal product of 720:

(1) Robbie was given: 1, 5, 9; Additional digits: 2, 8.
(2) Robbie was given: 2, 5, 8; Additional digits: 1, 9.

The sum of all 3-digit permutations is 3330 (= 222 × 15).

The sum of all 5-digit permutations is 6666600 = (266664 × 25).

In total there are 16 candidate solutions, each with the same sums for the 3-digit and 5-digit permutations.

In general, if we have a set of k different digits, then they can be rearranged in factorial(k) different ways, to form different numbers.

And when these numbers are summed, each digit will appear factorial(k) / k = factorial(k − 1) times in each column.

So we can calculate the total of all permutations without having to generate them all:
```
from enigma import factorial, repdigit

def psum(ds):
  k = len(ds)
  return factorial(k - 1) * repdigit(k) * sum(ds)
```
In particular, for 3-digit numbers this simplifies to [[ 222 * sum(ds) ]] and for 5-digit numbers it simplifies to [[ 266664 * sum(ds) ]].

The program above can be adapted using this analysis to give a solution with a run time of 51ms:
```
from enigma import irange, subsets, nsplit, diff, multiply, Accumulator, inf, factorial, repdigit, printf

# return multiplier for total sum of all permutations of a set of distinct digits
psum = lambda k: factorial(k - 1) * repdigit(k)
psum3 = psum(3)
psum5 = psum(5)

# count occurrences of digit d in number n
dcount = lambda n, d: nsplit(n).count(d)

# collect minimal products
r = Accumulator(fn=min, value=inf, collect=1)

# choose the set of 5 digits
for ds5 in subsets(irange(1, 9), size=5):
  p = multiply(ds5)
  if p > r.value: continue

  # there should be five 6 digits in the total
  t5 = psum5 * sum(ds5)
  if not(dcount(t5, 6) == 5): continue

  # choose a subset of 3 digits
  for ds3 in subsets(ds5, size=3):
    t3 = psum3 * sum(ds3)
    # there should be three 3 digits in the total
    if not(dcount(t3, 3) == 3): continue

    # record the initial set of 3 digits, and the additional 2 digits
    r.accumulate_data(p, (ds3, diff(ds5, ds3)))

# output solutions
if r.count:
  for (ds3, ds2) in r.data:
    printf("{ds3} + {ds2}; product = {r.value}")
```
LikeLike
- Tony Brooke-Taylor 3:11 pm on 13 February 2021 Permalink | Reply
  
  I think it is possible to simplify the problem to a point where the solution can be found manually. I admit I only spotted the simplifications once I had written an algorithm similar to yours Jim.
  
  In the 3-digit problem we can work out manually what the total must be: there is only one multiple of 222 that has three 3’s in it. Eight sets of three digits sum to the correct cofactor, of which four are symmetrical around the value 5.
  
  In the 5-digit problem we can also work out what the total must be: there is only one multiple of 266664 that has five 6’s in it, and I believe this is more obvious if we look at multiples of 11111. Thus we have a unique cofactor in this problem too, and the sum of the extra two digits must be the difference between the two cofactors. Only four pairs of digits make up this sum.
  
  If we combine the four pairs with the eight trios and deduplicate, we get ten possible sets of 5, of which six are symmetrical around the value 5.
  
  By trigonometry, the solution with the minimum product has the greatest distances between the central number and the others. My leap of faith is that we could also have applied this at the 3-digit stage to reduce the number of trios we needed to test.
  
  LikeLike
  - Jim Randell 12:07 pm on 17 February 2021 Permalink | Reply
    @Tony: Once we’ve got the 8 pairs of triples that sum to 15, and we are extending them with a pair that sums to 10 (= (1,9) (2,8) (3, 7) (4,6)), then we only need to consider the first viable pair, as later ones will give a larger product.
    
    So we can exhaustively check the solution space by calculating only 7 products.
    
    Here’s some code that uses this analysis:
```
from enigma import irange, Accumulator, printf

# collect minimal product
r = Accumulator(fn=min, collect=1)

# look for sets of 3 digits (a, b, c) that sum to 15
for a in irange(1, 4):
  for b in irange(a + 1, 6):
    c = 15 - (a + b)
    if not(b < c < 10): continue

    # and now add (d, e) that sum to 10
    for d in irange(1, 4):
      e = 10 - d
      if len({a, b, c, d, e}) != 5: continue

      # collect minimal product
      r.accumulate_data(a * b * c * d * e, ((a, b, c), (d, e)))
      break # only need to check the first viable (d, e) pair

# output solutions
if r.count:
  for (ds3, ds2) in r.data:
    printf("{ds3} + {ds2}; product = {r.value}")
```
    LikeLike
- Frits 10:31 am on 15 February 2021 Permalink | Reply
  @Jim,
  
  If you replace line 23 “t5 = psum(ds5) ” with
```
t5 = 0
for v, w, x, y, z in permutations(ds5):
  t5 += v * 10000 + w * 1000 + x * 100 + y * 10 + z
```
  your code is approx. 4.5 times faster (with Python 3.9.0).
  
  Maybe nconcat is not efficient if called multiple times?
  Subsets only seems to have minor overhead.
  
  LikeLike
  - Jim Randell 12:40 pm on 15 February 2021 Permalink | Reply
    
    @Frits: In a program that runs pretty much instantaneously I am less concerned about coding for execution speed as I am that the program itself should be concise, clear and easy to modify (and, above all, correct).
    
    So using a general utility function like [[ nconcat() ]] makes it clear that I am turning a sequence of digits into a number, even if it is not the fastest way to achieve this.
    
    Although with a bit of analysis we find that we don’t have to construct numbers corresponding to all the permutations of the digits in order to arrive at the sum (and gives a general principle for attacking similar problems), which lets us write a program that runs even faster.
    
    But that is not to say I’m not at all interested in execution speed. I’ll have a look at improving [[ nconcat() ]], and another advantage of using utility functions is that if an improvement is made, every program that uses them gets the benefit.
    
    LikeLike

Frits 11:23 am on 13 February 2021 Permalink | Reply

Basic version, not really optimized for speed.

from itertools import permutations, combinations

sol = set()
for a, b, c in combinations(range(1, 10), 3):
  t1 = 0
  for x, y, z in permutations([a, b, c]):
    t1 += x * 100 + y * 10 + z
 
  # there should be three 3's in the total
  if str(t1).count("3") == 3:
    for d in [q for q in range(1, 9) if q not in {a, b, c}]:
      for e in [q for q in range(d + 1, 10) if q not in {a, b, c}]:
        t2 = 0
        for v, w, x, y, z in permutations([a, b, c, d, e]):
          t2 += v * 10000 + w * 1000 + x * 100 + y * 10 + z
        
        # there should be five 6's in the total
        if str(t2).count("6") == 5:
          # put product up front so we can use if for sorting
          sol.add(tuple([a * b * c * d * e] + sorted([a, b, c, d, e])))
  
if len(sol):  
  print(f"answer = {sorted(sol)[0][1:]}")

LikeLike

Frits 2:07 pm on 18 February 2021 Permalink | Reply

Partly based on Tony’s comments.

from math import prod

# Suppose a < b < c < d < e and (a + b + c + d + e) is a constant
#
# a * b * c * d * e is minimal 
# if sum of distances with respect to c is maximal.
# 
# Proof:
# 
# sum of distances = (c - a) + (c - b) + (d - c) + (e - c) = d + e - a - b
# 
# Suppose we allow d or e to decrease with one and a or b to increase with 
# one, so the sum stays the same. Say d' = d - 1 and b' = b + 1
# 
# b' * d' = (b + 1) * (d - 1) = b * d + (d - b) - 1
# as c is between b and d we can say d - b > 1, thus d' * b' > d * b
# so new product a * b' * c * d' * e  >  old product a * b * c * d * e

# decompose number <t> into <k> different numbers from sequence <ns> 
# so that  sum(<k> numbers) equals <t>
# the result is already sorted on product !!
def decompose(t, k, ns, s=[]):
  if k == 1:
    if t in ns:
      yield s + [t]
  else:
    for (i, n) in enumerate(ns):
      if not(n < t): break
      yield from decompose(t - n, k - 1, ns[i + 1:], s + [n])

digits = [1, 2, 3, 4, 5, 6, 7, 8, 9]

# sum permutations of 3 different digits is 222 * sum(digits)
# last digit of sum can never be a 3 
# so first 3 digits of sum must be all 3's
s3 = 3340 // 222                   # sum of 3 digits
if (s3 * 222) // 10 != 333: 
  exit()                           # no solution

# sum permutations of 5 different digits is 266664 * sum(digits)
sum5 = [x for x in range(s3 + 3, min(s3 + 18, 36)) 
        if str(266664 * x).count("6") == 5] 
        
sol = []        

for s5 in sum5:
  # we look for 5 digits a, b, c, d, e which sum to <s5>
  # and where three of them sum to <s3>
  # (a * b * c * d * e must be minimal)

  # choose <a> as low as possible and <e> as high as possible
  a = max(1, s5 - 30)
  e = min(9, s5 - 10)
  # d - b must be maximal
  b = max(2, s5 - 25 - a + 1)
  d = min(8, max(4, s5 - 15))
  c = s5 - (a + b + d + e)
  
  # check optimal solution 
  if len(list(decompose(s3, 3, [a, b, c, d, e]))) > 0:
    sol.append([prod([a, b, c, d, e]), (a, b, c, d, e)])
  else:
    for abcde in decompose(s5, 5, digits): 
      if len(list(decompose(s3, 3, abcde))) > 0:
        sol.append([prod(abcde), abcde])
        break  # decompose returns entries sorted on product!
  
if len(sol) > 0:  
  sol.sort()   # sort on product
  print("answer = ", sol[0][1])

LikeLike

Jim Randell 9:01 am on 11 February 2021 Permalink | Reply
Tags: by: Eric Emmet ( 10 )

Brain-Teaser 691: That’s torn it …

From The Sunday Times, 13th October 1974 [link]

It was typical of Uncle Bungle that he should have torn up the sheet of paper which gave particulars of the numbers of matches played, won, lost, drawn, etc. of four local football teams who were eventually going to play each other once. The only piece left was as shown (as usual there are 2 points for a win and 1 for a draw):

It will not surprise those who know my Uncle to hear that one of the figures was wrong, but fortunately it was only one out (i.e. one more or less than the correct figure).

Each side had played at least one game, and not more than seven goals were scored in any match.

Calling the teams A, B, C and D (in that order), find the score in each match.

This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980). The puzzle text above is taken from the book.

[teaser691]

Jim Randell 9:02 am on 11 February 2021 Permalink | Reply

(See also: Puzzle 81).

This Python program uses the [[ Football ]] helper class from the enigma.py library. It runs in 198ms.

from enigma import (Football, subsets, cproduct, printf)

# scoring system
football = Football(points=dict(w=2, d=1))

# possible scores in the matches (no match has more than 7 goals scored)
scores = {
  'w': [
    (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0), (7, 0),
    (2, 1), (3, 1), (4, 1), (5, 1), (6, 1),
    (3, 2), (4, 2), (5, 2),
    (4, 3),
  ],
  'd': [(0, 0), (1, 1), (2, 2), (3, 3)],
  'x': [None],
}
scores['l'] = list((b, a) for (a, b) in scores['w'])

# choose outcomes for each of the matches
for (AB, AC, AD, BC, BD, CD) in subsets('wdlx', size=6, select="M"):
  # calculate the points
  A = football.table([AB, AC, AD], [0, 0, 0])
  B = football.table([AB, BC, BD], [1, 0, 0])
  C = football.table([AC, BC, CD], [1, 1, 0])
  D = football.table([AD, BD, CD], [1, 1, 1])

  # each team has played at least one game
  if not all(x.played > 0 for x in [A, B, C, D]): continue

  # count the discrepancies in the points
  dp = abs(A.points - 3) + abs(B.points - 5) + C.points
  if dp > 1: continue

  # choose the scores in C's games
  for (sAC, sBC, sCD) in cproduct([scores[AC], scores[BC], scores[CD]]):
    (fC, aC) = football.goals([sAC, sBC, sCD], [1, 1, 0])
    dC = aC
    if dp + dC > 1: continue

    # choose the scores in A's games
    for (sAB, sAD) in cproduct([scores[AB], scores[AD]]):
      (fA, aA) = football.goals([sAB, sAC, sAD], [0, 0, 0])
      dA = abs(aA - 5)
      if dp + dA + dC > 1: continue

      # remaining game
      for sBD in scores[BD]:
        (fB, aB) = football.goals([sAB, sBC, sBD], [1, 0, 0])
        dB = abs(aB - 6)
        if dp + dA + dB + dC > 1: continue

        (fD, aD) = football.goals([sAD, sBD, sCD], [1, 1, 1])
        dD = abs(aD - 7)
        if dp + dA + dB + dC + dD != 1: continue

        printf("A=({aA} {A.points}) B=({aB} {B.points}) C=({aC} {C.points}) D=({aD} {D.points}) / \\")
        printf("AB={AB}:{sAB} AC={AC}:{sAC} AD={AD}:{sAD} BC={BC}:{sBC} BD={BD}:{sBD} CD={CD}:{sCD}")

Solution: The scores in the played matches are: A vs B = 3-3; A vs D = 3-2; B vs C = 1-0; B vs D = 4-3.

The A vs C and C vs D matches are not yet played.

The incorrect value is C’s “goals against”. It should be 1, not 0.

It is clear that the incorrect value must be one of C’s, as if they have played at least one game they cannot have both 0 points and 0 goals against.

LikeLike

Jim Randell 8:50 am on 9 February 2021 Permalink | Reply
Tags: by: Angela Newing ( 40 )

Teaser 2775: Strictly not

From The Sunday Times, 29th November 2015 [link] [link]

Four celebrities entered a dance competition. Five judges each shared out their eight marks among the four dancers, with each getting a non-zero whole number. Each judge split the eight marks in a different way and then allocated them as follows. Amanda’s marks to Lana and Natasha added to the same total as Barry’s marks to Madge and Paula. Barry gave more marks to Madge than to any other dancer, Charles gave more to Paula than to any other, and Doris gave more to Natasha than to any other. Lana scored more from Edna than from Amanda. All dancers had the same total so the head judge’s scores were used, giving a winner and runner-up.

Who was the head judge, who was the winner and who was the runner-up?

[teaser2775]

Jim Randell 8:51 am on 9 February 2021 Permalink | Reply

Each of the 5 judges gives out 8 points, so 40 points are awarded in total. And there are 4 dancers, and they all receive the same total number of points. So each dancer receives 10 points in total.

Each judge awards a non-zero number of points to each dancer, so the points awarded are between 1 and 5.

I used the [[ SubstitutedExpression ]] solver from the enigma.py library to find possible collections of points awarded by the judges, and the scores are then examined to determine which judges scores identify a clear winner and runner up.

The following run file executes in 80ms.

Run: [ @replit ]

from enigma import (SubstitutedExpression, irange, seq_all_different, ordered, printf)

# consider the points given:
#
#             Lana
#             |  Madge
#             |  |  Natasha
#             |  |  |  Paula
#   Amanda:   A  B  C  D = 8
#   Barry:    E  F  G  H = 8
#   Charles:  I  J  K  L = 8
#   Doris:    M  N  P  Q = 8
#   Edna:     R  S  T  U = 8
#             =  =  =  =
#            10 10 10 10

# check the splits are all different
check_splits = lambda *xs: seq_all_different(ordered(*x) for x in xs)

# construct the alphametic problem
p = SubstitutedExpression([
    # each judge gave out 8 points
    "A + B + C + D = 8",
    "E + F + G + H = 8",
    "I + J + K + L = 8",
    "M + N + P + Q = 8",
    "R + S + T + U = 8",

    # points were split in a different way by each judge
    "check_splits((A, B, C, D), (E, F, G, H), (I, J, K, L), (N, M, P, Q), (R, S, T, U))",

    # "A's marks to L and N had the same sum as B's marks to M and P"
    "A + C == F + H",

    # "B gave more marks to M than to any other"
    "max(E, G, H) < F",

    # "C gave more to P than to any other"
    "max(I, J, K) < L",

    # "D gave more to N than to any other"
    "max(M, N, Q) < P",

    # "L scored more from E than from A"
    "R > A",

    # all dancers had the same total (= 10)
    "A + E + I + M + R = 10",
    "B + F + J + N + S = 10",
    "C + G + K + P + T = 10",
    "D + H + L + Q + U = 10",
  ],
  distinct=(),
  digits=irange(1, 5), # points are in the range 1-5
  env=dict(check_splits=check_splits),
  # answer is the scores from each judge
  answer="((A, B, C, D), (E, F, G, H), (I, J, K, L), (M, N, P, Q), (R, S, T, U))",
  denest=-1, # [CPython] work around statically nested block limit
)

# solve the puzzle, and output solutions
(judges, dancers) = ("ABCDE", "LMNP")
for (_, scores) in p.solve(verbose=0):
  # look for scores that differentiate 1st and 2nd place
  for (j, ss) in zip(judges, scores):
    printf("{j}: {ss}\\")
    (p1, p2, p3, p4) = sorted(ss, reverse=1)
    if p1 > p2 > p3:
      (d1, d2) = (dancers[ss.index(p)] for p in (p1, p2))
      printf(" -> head judge; 1st = {d1}, 2nd = {d2}\\")
    printf()
  printf()

Solution: Doris was the head judge. Natasha was the winner. Lana was the runner-up.

The scores were allocated as follows (L, M, N, P):

A: (2, 2, 2, 2)
B: (2, 3, 2, 1)
C: (1, 1, 1, 5)
D: (2, 1, 4, 1)
E: (3, 3, 1, 1)

There are only 5 different (unordered) ways to divide a score of 8 between 4 dancers, and only one of them (4, 2, 1, 1) gives a clear 1st and 2nd place.

LikeLike

Frits 9:26 pm on 9 February 2021 Permalink | Reply

from collections import defaultdict
 
# consider the points given:
#
#             Lana
#             |  Madge
#             |  |  Natasha
#             |  |  |  Paula
#   Amanda:   A  B  C  D = 8
#   Barry:    E  F  G  H = 8
#   Charles:  I  J  K  L = 8
#   Doris:    M  N  P  Q = 8
#   Edna:     R  S  T  U = 8
#             =  =  =  =
#            10 10 10 10

M = 5  # number of rows
N = 4  # number of columns 

# decompose number <t> into <k> positive numbers from <ns>
# so that sum(<k> numbers) equals <t>
def decompose(t, k, ns, s=[]):
  if k == 1:
    if t in ns:
      yield s + [t]
  else:
    for (i, n) in enumerate(ns):
      if not(n + k - 2 < t): break
      #yield from decompose(t - n, k - 1, ns[i:], s + [n])
      yield from decompose(t - n, k - 1, ns, s + [n])   
      
# combine rows of dictionary <d>
# so that every column total equals <t>
def combineRows(t, k, d, s=[]):
  if k == 1:
    remaining = [t - sum(x) for x in zip(*s)]
    if remaining in d[0]:
      yield s + [remaining]
  else:
    for row in d[k - 1]:
      # for each column ...
      for j in range(N):
        # .. sum already processed numbers
        already = sum([0 if len(s) == 0 else x[j] for x in s]) 
        # and check if there is room for remaining rows
        if not(row[j] + already  + k - 2 < t): 
          already = -1  # skip this row
          break
      if already > -1:
        yield from combineRows(t, k - 1, d, s + [row])         


types = []
d_rows = defaultdict(list)

# create dictionary of possible rows for each type of row
# the points awarded are between 1 and 5
for x in decompose(8, N, range(1, 6)): 
  sortx = sorted(x) 
  if sortx in types:
    type = types.index(sortx)
  else:
    type = len(types)
    types.append(x)
  # append possible row  
  d_rows[type] += [x]
  

# combine rows so that column total always equals 10  
for rows in combineRows(10, M, d_rows): 
  testB, testC, testD = -1, -1, -1
  
  # validate rows
  for i, r in enumerate(rows):
    sr = sorted(r)
    # check if maximum value is unique
    if sr[-1] > sr[-2]:
      
      if sr[-1] == r[1]:    # testB : "max(E, G, H) < F",
        testB = i  
      elif sr[-1] == r[3]:  # testC : "max(I, J, K) < L",
        testC = i
      elif sr[-1] == r[2]:  # testD : "max(M, N, Q) < P",
        testD = i
  
  if -1 in {testB, testC, testD}: continue
  
  # get the other rows
  ix_oth = [x for x in range(M) if x not in {testB, testC, testD}]
  
  # "R > A"
  if rows[ix_oth[0]][0] < rows[ix_oth[1]][0]:
    testA = ix_oth[0]; testE = ix_oth[1]
  elif rows[ix_oth[0]][0] > rows[ix_oth[1]][0]:
    testE = ix_oth[0]; testA = ix_oth[1]
  else:
    continue
  
  # "A + C == F + H"
  if rows[testA][0] + rows[testA][2] != rows[testB][1] + rows[testB][3]:
    continue
  
  # the head judge's scores were used, giving a winner and runner-up
  judges, dancers = "ABCDE", "LMNP"
  for i, r in enumerate(rows):
    sr = sorted(r)
    if sr[1] < sr[2] < sr[3]:
      print(f"head judge: {judges[i]} ")
      print(f"winner    : {dancers[r.index(sr[3])]}")
      print(f"runner up : {dancers[r.index(sr[2])]}")
      print()
     
      for r in rows:
        print(r)

LikeLike

Jim Randell 9:26 am on 7 February 2021 Permalink | Reply
Tags: by: Ptolemaeus ( 5 )
Brain-Teaser 20: The kite
From The Sunday Times, 6th August 1961 [link]

Some problems that look simple enough at first can prove to be remarkably tricky. Consider, for instance, the kite pictured above. The shaded areas are squares of equal size, the sides of each square being 15 inches. The width of the kite from A to B is exactly 42 inches.

What is the length of the kite from C to D?

[teaser20]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
John Crabtree and Jim Randell are discussing. Toggle Comments
- Jim Randell 9:29 am on 7 February 2021 Permalink | Reply
  
  The figure is a right kite [ @wikipedia ], so is composed of 2 identical right-angled triangles joined along their common hypotenuse CD (which is the length we wish to determine).
  
  Writing: AC = BC = a, and AD = BD = b, then the value we wish to determine, CD, is:
  
  CD = √(a² + b²)
  
  We are told the other diagonal, AB, has length 42, hence:
  
  42 = 2ab / √(a² + b²)
  21√(a² + b²) = ab
  
  And the sides of the squares that run from the centre to the edges of the kite are radii of the incircle, so:
  
  15 = ab / (a + b)
  
  Writing: x = ab, y = a + b, we get:
  
  15 = x / y
  x = 15y
  x² = 225y²
  
  Also:
  
  a² + b² = (a + b)² − 2ab = y² − 2x
  
  So:
  
  441(y² − 2x) = x²
  441(y² − 30y) = 225y²
  216y² = 13230y
  4y = 245
  y = 245 / 4
  x = 3675 / 4
  
  So the value of CD is:
  
  CD = √(a² + b²)
  = √(y² − 2x)
  = √(30625 / 16)
  = 175 / 4
  
  Solution: CD = 43.75 inches.
  
  And the lengths of the sides of the kite are 26.25 in and 35 in.
  
  LikeLike
- John Crabtree 10:22 pm on 8 February 2021 Permalink | Reply
  
  Let the mid-point of AB be F, and the point where the squares meet be G
  By Pythagoras, FG = √(2 * 225 – 441) = 3
  Let z be the angle formed by GAF.
  Tan(z) = t = 3 / 21 = 1 / 7
  CD = 21 [tan(45 + z) + tan(45 – z)] = 21 [(1+t)/(1-t) + (1-t)/(1+t))
  = 21 [4/3 + 3/4] = 21 * 25/12 = 43.75 inches.
  AC = 21 * 5/4 = 26.25 in. AD = 21 * 5/3 = 35 in.
  
  LikeLike

Jim Randell 4:52 pm on 5 February 2021 Permalink | Reply
Tags: by: Danny Roth ( 88 )

Teaser 3046: Square phone numbers

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

George and Martha run a business in which there are 22 departments. Each department has a perfect-square three-digit extension number, i.e., everything from 100 (10²) to 961 (31²), and all five of their daughters are employees in separate departments.

Andrea, Bertha, Caroline, Dorothy and Elizabeth have extensions in numerical order, with Andrea having the lowest number and Elizabeth the highest. George commented that, if you look at those of Andrea, Bertha and Dorothy, all nine positive digits appear once. Martha added that the total of the five extensions was also a perfect square.

What is Caroline’s extension?

[teaser3046]

Jim Randell 5:03 pm on 5 February 2021 Permalink | Reply

A simple Python program finds the solution in 67ms.

from enigma import (powers, subsets, concat, is_square, printf)

# possible square numbers
squares = powers(10, 31, 2)

# choose 5 of the squares (in order)
for (A, B, C, D, E) in subsets(squares, size=5):

  # the sum of the numbers is also a square
  if not is_square(A + B + C + D + E): continue

  # A, B, D use the digits 1-9
  ds = concat(A, B, D)
  if '0' in ds or len(set(ds)) != 9: continue

  # output solution
  printf("A={A} B={B} C={C} D={D} E={E}")

Solution: Caroline’s extension is 729.

Manually, you can write out the squares, and then working through the possible candidates for A, B, D, the solution is discovered quite quickly.

LikeLike

GeoffR 7:51 pm on 5 February 2021 Permalink | Reply


% A Solution in MiniZinc
include "globals.mzn";
 
% Andrea, Bertha, Caroline, Dorothy and Elizabeth's numbers
var 100..961:A; var 100..961:B; var 100..961:C;
var 100..961:D; var 100..961:E;

constraint all_different([A, B, C, D, E]);
constraint A < B /\ B < C /\ C < D /\ D < E;

% digits for squares A, B and D
var 1..9:a1; var 1..9:a2; var 1..9:a3;
var 1..9:b1; var 1..9:b2; var 1..9:b3;
var 1..9:d1; var 1..9:d2; var 1..9:d3;

% all 3-digit squares
set of int: sq3 = {n*n | n in 10..31};

predicate is_sq(var int: y) =
exists(z in 1..ceil(sqrt(int2float(ub(y)))))
(z*z = y);
        
% the total of the five extensions was also a perfect square        
constraint is_sq(A + B + C + D + E);

 % all five telephone extensions are 3-digit squares       
constraint A in sq3 /\ B in sq3 /\ C in sq3 /\ D in sq3 /\ E in sq3;

% digit components in squares A, B and D
constraint a1 == A div 100 /\ a2 == A div 10 mod 10 /\ a3 == A mod 10;
constraint b1 == B div 100 /\ b2 == B div 10 mod 10 /\ b3 == B mod 10;
constraint d1 == D div 100 /\ d2 == D div 10 mod 10 /\ d3 == D mod 10;

set of int: all_dig ={1, 2, 3 ,4, 5, 6, 7, 8, 9};
var set of int: S1 == {a1, a2, a3, b1, b2, b3, d1, d2, d3};
constraint all_dig == S1;

solve satisfy;

output ["Caroline's extension is " ++ show(C)
++"\nOther extensions are " ++ show(A) ++ ", " ++ show(B)
++ ", " ++ show(D) ++ ", " ++ show(E) ];

LikeLike

GeoffR 8:44 am on 6 February 2021 Permalink | Reply

from itertools import combinations
from enigma import nsplit, is_square

squares =[x * x for x in range(10, 32)]

for A, B, C, D, E in combinations(squares, 5):
  # five extensions are in numerical order
  if A < B < C < D < E:
    sq_total = A + B + C + D + E 
    if is_square(sq_total):
      # find individual digits of A, B and D
      a1, a2, a3 = nsplit(A)
      b1, b2, b3 = nsplit(B)
      d1, d2, d3 = nsplit(D)
      S1 = set((a1, a2, a3, b1, b2, b3, d1, d2, d3))
      # check this set contains nine positive digits
      if len(S1) == 9 and 0 not in S1:
        print(f"Five extensions are {A}, {B}, {C}, {D}, {E}")

LikeLike

Frits 7:44 pm on 6 February 2021 Permalink | Reply

squares = [x * x for x in range(15, 66)]
ABD_squares = [x * x for x in range(13, 31) 
               if len(set(str(x * x) + "0")) == 4]

for i, a in enumerate(ABD_squares[:-2]):
  for j, b in enumerate(ABD_squares[i + 1:-1]):
    if len(set(str(a) + str(b))) != 6: continue
    for d in ABD_squares[i + j + 2:]:
      if len(set(str(a) + str(b) + str(d))) != 9: continue
      p = squares.index(b)
      q = squares.index(d)
      
      for c in squares[p + 1:q]:
        for e in squares[q + 1:17]:
          if not (a + b + c + d + e) in squares: continue
          print(f"Caroline's extension is {c}.")

LikeLike

Tony Brooke-Taylor 10:21 am on 7 February 2021 Permalink | Reply

import itertools

digits = set([str(j) for j in range(1, 10)])

for M in itertools.combinations([i**2 for i in range(10, 32)], 5):
  if (sum(M)**(1/2))%1 == 0:
    if set(str(M[0])+str(M[1])+str(M[3])) == digits: print("Caroline's extension is", M[2])

LikeLike

Frits 4:21 pm on 7 February 2021 Permalink | Reply

Logic can reduce a,b and d to specific squares.
The version without reduction logic is faster.

from collections import defaultdict

squares = [x * x for x in range(15, 66)]
ABD_squares = [x * x for x in range(13, 31) 
               if len(set(str(x * x) + "0")) == 4]
    
# return first column    
col0 = lambda li: [x[0] for x in li]               

fixed = set()
str_fixed = ""
mut_excl = defaultdict(set)

# reduce candidates in list <ABD_squares>
# by looking for digits occurring once or twice in list <ABD_squares>
for loop in range(9):
  occ = defaultdict(list)
  
  for x in "123456789":
    # add entries to occurence dictionary <occ>
    for i, s in enumerate(ABD_squares):
      s1 = str(s)
      if x not in s1 or s1 in fixed: continue
      # skip if a square digit already occurs in <fixed>
      if any(y in str_fixed for y in s1): continue
      occ[x].append([i, s1])

    if len(occ[x]) == 1:  
      # a square has to occur in <ABD_squares>
      if not occ[x][0][1] in fixed:
        fixed.add(occ[x][0][1])
        str_fixed = "".join(fixed)
        # also update occurrence for other 2 related digits to same square
        for c in occ[x][0][1]:
          if c == x: continue
          occ[c] = occ[x]
    elif len(occ[x]) == 2:
      # we have a square with digits x,e,f and a square with digits x,g,h
      # so e, e, f, f may not occur in another square with resp. g, h ,g, h
      for y in occ[x][0][1]: 
        if y == x: continue
        for z in occ[x][1][1]:
          if z == x: continue
          mut_excl[y].add(z)  
          mut_excl[z].add(y) 

  # check if 2 digits always occur in different squares
  for x1, y1 in occ.items():
    for x2, y2 in occ.items():
      if x1 >= x2: continue
      if len(set(col0(y1) + col0(y2))) != \
         len(col0(y1)) + len(col0(y2)): continue
      # digit x1 and x2 occur in different squares
      # so maintain dictionary <mut_excl>
      mut_excl[x1].add(x2)
      mut_excl[x2].add(x1)

  # reduce squares if a square contains mutually exclusive digits
  ABD_squares = [s for s in ABD_squares 
                 if not any(m in str(s) for y in str(s) 
                            for m in mut_excl[y])
                ]
   
  if len(ABD_squares) == 3: break
  
  
# start with a,b,d and then check c and e
for i, a in enumerate(ABD_squares[:-2]):
  for j, b in enumerate(ABD_squares[i + 1:-1]):
    if len(set(str(a) + str(b))) != 6: continue
    for d in ABD_squares[i + j + 2:]:
      if len(set(str(a) + str(b) + str(d))) != 9: continue
      p = squares.index(b)
      q = squares.index(d)
      
      for c in squares[p + 1:q]:
        for e in squares[q + 1:17]:
          if not (a + b + c + d + e) in squares: continue
          print(f"Caroline's extension is {c}.")

LikeLike

Frits 1:25 pm on 8 February 2021 Permalink | Reply

Not very efficient.

# decompose a number into <k> increasing 3-digit squares a, b, c, d, e
# (a, b, d) has to contain all digits 1-9
def decompose(t, k, m=1, ss=[]):
  if k == 1:
    # check if last number is higher and a square
    if t > ss[-1] and int(t ** 0.5) ** 2 == t:
      yield ss + [t]
  else:
    for i in range(m, 32 - k + 1):
      s = i * i
      if s > t: break
      
      if k in {3, 1} or len(set(str(s) + "0")) == 4:
        yield from decompose(t - s, k - 1, i + 1, ss + [s])
        
# sum first five 3-digit squares is 750 and last five 3-digit squares is 4215
for r in range(28, 65):
  # get five 3-digit squares which add up to square <r * r>
  for x in decompose(r * r, 5, 10): 
    sabd = set(str(1000000 * x[0] + 1000 * x[1] + x[3]))
    if len(sabd) != 9: continue

    print(f"Caroline's extension is {x[2]}.")

LikeLike

Jim Randell 8:47 am on 4 February 2021 Permalink | Reply
Tags: by: D C Pusinelli

Brain-Teaser 688: Job allocation

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

Ashley, Bill, Charles, David, and Edward are (not necessarily in that order), a dustman, a grocer, a miner, a blacksmith, and an artist, and all live on the right hand side of Strife Lane, in even numbered houses. All five are of different ages and no man has reached the age of retirement (65). All of course are upright and honest citizens, and never tell lies. However, I had forgotten what job each man did, where he lived, and how old he was, and so, to help me, each man volunteered the following statements:

Ashley:
(1) The artist lives at No. 10, next to Charles;
(2) Nobody lives next to the grocer, although Bill is only two doors away.

Bill:
(3) I am the only man whose age is indivisible by 9;
(4) I am 4 years older than Ashley;

Charles:
(5) The blacksmith’s age is 5 times his house number;

David:
(6) The miner lives 4 houses higher up the road from me;
(7) The miner’s age is 3 times the dustman’s house number, but he is two-thirds the dustman’s age;

Edward:
(8) The dustman is twice as old as David;
(9) I am the oldest man in the street.

At what number does Ashley live?
How old is the grocer?
Who is the artist?

This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980). The puzzle text above is taken from the book.

[teaser688]

Jim Randell 8:48 am on 4 February 2021 Permalink | Reply

I wrote a MiniZinc model to solve this puzzle, and then used the minizinc.py wrapper to format the output.

This Python program runs in 178ms.

from enigma import irange, printf
from minizinc import MiniZinc

model = """

  include "globals.mzn";

  % indices for A, B, C, D, E
  int: A = 1;
  int: B = 2;
  int: C = 3;
  int: D = 4;
  int: E = 5;

  % house numbers
  array [1..5] of var int: n;

  % even numbers
  constraint forall (i in 1..5) (n[i] > 0 /\ n[i] mod 2 = 0);
  % all different
  constraint all_different(n);

  % ages
  array [1..5] of var 16..64: a;

  % all different
  constraint all_different(a);

  % jobs
  var 1..5: Du;
  var 1..5: Gr;
  var 1..5: Mi;
  var 1..5: Bl;
  var 1..5: Ar;

  % all different
  constraint all_different([Du, Gr, Mi, Bl, Ar]);

  % (1) "the artist lives at number 10, next to C"
  constraint n[Ar] = 10;
  constraint n[C] = 8 \/ n[C] = 12;

  % (2) "nobody lives next to the grocer, although B is only 2 doors away"
  constraint forall (i in 1..5 where i != Gr) (abs(n[Gr] - n[i]) != 2);
  constraint abs(n[Gr] - n[B]) = 4;

  % (3) "B is the only one whose age is not divisible by 9"
  constraint forall (i in 1..5) (a[i] mod 9 != 0 <-> i = B);

  % (4) "B is 4 years older than A"
  constraint a[B] = a[A] + 4;

  % (5) "Bl age is 5x his house number"
  constraint a[Bl] = 5 * n[Bl];

  % (6) "Mi lives 4 houses further up the road than D"
  constraint n[Mi] = n[D] + 8;

  % (7) "Mi's age is 3x Du's house number; but Mi is 2/3 Du's age"
  constraint a[Mi] = 3 * n[Du];
  constraint 3 * a[Mi] = 2 * a[Du];

  % (8) "Du is 2x D's age"
  constraint a[Du] = 2 * a[D];

  % (9) "E is the oldest"
  constraint forall (i in 1..5 where i != E) (a[i] < a[E]);

  solve satisfy;

"""

p = MiniZinc(model)

name = [ "", "Ashley", "Bill", "Charles", "David", "Edward" ]
for (n, a, Du, Gr, Mi, Bl, Ar) in p.solve(result="n a Du Gr Mi Bl Ar"):
  j = { Du: "Dustman", Gr: "Grocer", Mi: "Miner", Bl: "Blacksmith", Ar: "Artist" }
  for i in irange(1, 5):
    printf("{name}: house = {n}; age = {a}; job = {j}", name=name[i], n=n[i], a=a[i], j=j[i])

Solution: Ashley lives at number 18. The grocer is 63. David is the artist.

The complete solution:

Ashley: house = 18; age = 36; job = Miner
Bill: house = 8; age = 40; job = Blacksmith
Charles: house = 12; age = 54; job = Dustman
David: house = 10; age = 27; job = Artist
Edward: house = 4; age = 63; job = Grocer

LikeLike

Frits 11:52 am on 11 February 2021 Permalink | Reply

@Jim, you didn’t code that B’s age may not be not divisible by 9.

LikeLike
- Jim Randell 11:59 am on 11 February 2021 Permalink | Reply
  @Frits: Oh yes.
  
  I’ll update line 48 to:
```
  % (3) "B is the only one whose age is not divisible by 9"
  constraint forall (i in 1..5) (a[i] mod 9 != 0 <-> i = B);
```
  LikeLike

Frits 9:38 pm on 11 February 2021 Permalink | Reply

“if stop: continue”

My first version started looping over house numbers (where a maximum house number had to be specified). Looping over ages first eliminates this problem.

from itertools import permutations

# indices Ashley ... Edward
(A, B, C, D, E) = (0, 1, 2, 3, 4)

#  "B is 4 years older than A (which is a multiple of 9)"
b_ages = [x for x in range(22, 65) if x % 9 != 0 and (x - 4) % 9 == 0]

acde_ages = tuple(permutations(range(18, 65, 9), 4))    

jobs_indices = list(permutations(range(5)))

# update list hn for key <k> if value <v> doesn't exist yet in hn
def update(k, v):
  if v in hn: 
    return False
  else:  
    hn[k] = v
    return True
  
# start with ages divisble by 9
for p4 in acde_ages:
  #  "Bl age is 5x his house number"
  if all(x % 5 != 0 for x in p4): 
    # at least one age must be a multiple of 5
    b_ages = [x for x in b_ages if x % 5 == 0]

  for b in b_ages:
    #  "B is 4 years older than A"
    if b != p4[0] + 4: continue
    
    # b must be placed at 2nd spot
    ag = (p4[0], b) + p4[1:]
    
    #  "E is the oldest"
    if ag[E] != max(ag): continue
    
    #  "Du is 2x D's age"
    if (2 * ag[D]) not in ag: continue
  
    # indices for Du, Gr, Mi, Bl, Ar
    for (Du, Gr, Mi, Bl, Ar) in jobs_indices:
      #  "Mi is 2/3 Du's age"
      if 3 * ag[Mi] != 2 * ag[Du]: continue
      
      #  "Bl age is 5x his house number"
      if ag[Bl] % 5 != 0: continue
      
      #  "Mi's age is 3x Du's house number"
      if ag[Mi] % 3 != 0: continue
     
      #  "Du is 2x D's age"
      if ag[Du] != 2 * ag[D]: continue
      
      # initialize house numbers
      hn = [0, 0, 0, 0, 0]
      
      #  "the artist lives at number 10, next to C"
      hn[Ar] = 10
      if not update(Du, ag[Mi] // 3): continue
      if not update(Bl, ag[Bl] // 5): continue
      
      if hn[C] and hn[C] not in {8, 12} : continue
      
      for loop in range(2):
        #  "Mi lives 4 houses further up the road than D"
        if hn[Mi] == 0 and hn[D]:
          if not update(Mi, hn[D] + 8): break
        elif hn[Mi] and hn[D] == 0:
          hn[D] = hn[Mi] - 8
          if hn[Mi] < 10 or not update(D, hn[Mi] - 8): 
            break
        elif hn[Mi] and hn[D]:  
          if hn[Mi] != hn[D] + 8: break

        # B is only 2 doors away from grocer"
        if hn[B]:
          if hn[Gr]:
            if abs(hn[B] - hn[Gr]) != 4: break
          else:
            Gr_opts = []
            if hn[B] + 4 not in hn: 
              Gr_opts.append(hn[B] + 4)
            if hn[B] > 5 and hn[B] - 4 not in hn:
              Gr_opts.append(hn[B] - 4)
            if len(Gr_opts) == 1:
              if not update(Gr, Gr_opts[0]): break
            elif len(Gr_opts) == 0: break
        else:
          if hn[Gr]:
            B_opts = []
            if hn[Gr] + 4 not in hn: 
              B_opts.append(hn[Gr] + 4)
            if hn[Gr] > 5 and hn[Gr] - 4 not in hn:
              B_opts.append(hn[Gr] - 4)
            if len(B_opts) == 1:
              if not update(B, B_opts[0]): break
            elif len(B_opts) == 0: break
        
        #  "nobody lives next to the grocer"
        if hn[Gr] and any(abs(x - hn[Gr]) == 2 and x != 0 for x in hn): break
        
        #  "the artist lives at number 10, next to C"
        if hn[C] and hn[C] not in {8, 12} :  break
        
      else: # no break
        
        # all house numbers determined? 
        if 0 in hn: continue

        jobs = {Du:  "Dustman", Gr: "Grocer", Mi: "Miner", 
                Bl: "Blacksmith", Ar: "Artist"}

        print("              Ashley", ) 
        print("              |   Bill") 
        print("              |   |   Charles") 
        print("              |   |   |   David") 
        print("              |   |   |   |   Edward") 
        print("house number", tuple(hn))
        print("age         ", ag)
        print("              |   |   |   |  ", jobs[4]) 
        print("              |   |   |  ", jobs[3]) 
        print("              |   |  ", jobs[2]) 
        print("              |  ", jobs[1]) 
        print("             ", jobs[0])

LikeLike

Frits 12:58 pm on 10 August 2021 Permalink | Reply

@Jim,

Did you choose for MiniZinc because it allows for an unrestrained house number range?

LikeLike
- Jim Randell 3:35 pm on 10 August 2021 Permalink | Reply
  
  @Frits: That was probably the main reason. Also using a declarative solver like MiniZinc meant I didn’t have to worry about what order to attack the problem in.
  
  LikeLike
Frits 2:13 pm on 10 August 2021 Permalink | Reply

@Jim,

If I add

var 2..6: q = Ar + 1;

then variable q is not in the result set.

Is this a MiniZinc issue or a wrapper issue?

LikeLike
- Jim Randell 3:29 pm on 10 August 2021 Permalink | Reply
  @Frits:
  
  The wrapper just parses the MiniZinc output and turns it into Python objects. So if MiniZinc doesn’t output a value it is not available in Python.
  
  But you should be able to use a constraint to get the value output by default:
```
var 2..6: q;
constraint q = Ar + 1;
```
  LikeLike

Jim Randell 8:33 am on 2 February 2021 Permalink | Reply
Tags: by: Ian Kay ( 5 )
Teaser 2774: Loaded dice
From The Sunday Times, 22nd November 2015 [link] [link]

I have two traditional-looking dice, but only one of them is fair. In the other there is an equal chance of getting a 1, 2, 3, 4 or 5, but the die is loaded so that a 6 is thrown more than half the time. I threw the two dice and noted the total. It turned out that with my dice the chance of getting that total was double what it would have been with two fair dice.

What (as a simple fraction) is the chance of getting a 6 with the loaded die?

[teaser2774]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
John Crabtree and Jim Randell are discussing. Toggle Comments
- Jim Randell 8:35 am on 2 February 2021 Permalink | Reply
  
  The fair die has a probability of 1/6 of showing any particular face (scores 1-6).
  
  The unfair die has a probability of p of showing 6, and (1 − p) / 5 of showing the other faces (scores 1-5).
  
  If we consider the probability of throwing a total of t (scores 2-12) using both dice:
  
  There are { n = (t − 1) if t ≤ 6; otherwise n = (13 − t) } different ways of achieving the total.
  
  And with two fair dice (which have 36 equally like outcomes) the probability of throwing t is n / 36.
  
  And we want to find when the probability of throwing t with one fair and one unfair dice is twice this value: i.e. when the probability is n / 18.
  
  If t ≤ 6, then neither die can show a 6, so the probability of throwing t is:
  
  P = n ((1 − p) / 5) (1/6)
  
  which we can solve for P = n / 18:
  
  n ((1 − p) / 5) (1/6) = n / 18
  3(1 − p) = 5
  p = −2/3 (not possible)
  
  If t > 6, then 6 can show on the unfair dice, so we have two ways to make the total:
  
  P = [(n − 1) ((1 − p) / 5) (1/6)] + [p (1/6)]
  
  and we can solve this for P = n / 18:
  
  (n − 1) ((1 − p) / 5) (1/6) + p / 6 = n / 18
  3(n − 1)(1 − p) + 15p = 5n
  18p − 3np − 3 = 2n
  p = (2n + 3) / (18 − 3n)
  
  Also for t > 6 we have: n = 13 − t, so:
  
  p = (2(13 − t) + 3) / (18 − 3(13 − t))
  p = (29 − 2t) / (3t − 21)
  
  And we are interested in cases where t = 7 .. 12 and 0.5 < p ≤ 1:
  
  t = 7 ⇒ p = undefined (not possible)
  t = 8 ⇒ p = 13/3 (not possible)
  t = 9 ⇒ p = 11/6 (not possible)
  t = 10 ⇒ p = 1
  t = 11 ⇒ p = 7/12
  t = 12 ⇒ p = 1/3 (not permitted)
  
  So we find there are 2 possible situations:
  
  (1) The loaded die always shows 6, and the setter threw 10.
  The probability of throwing 10 with two fair dice is 1/12.
  The probability of throwing 10 with one fair die and the loaded die is 1/6.
  
  (2) The loaded die has a probability 7/12 of showing 6, and the setter threw 11.
  The probability of throwing 11 with two fair dice is 1/18.
  The probability of throwing 11 with one fair die and the loaded die is 1/9.
  
  I suspect we are to ignore that case where the loaded die always shows 6, as this would be quite obvious. (Although I would have thought a die that shows 6 more than half the time would be fairly obvious anyway). The setter could have explicitly excluded this case by specifying “an equal non-zero chance of scoring 1 – 5″ for the loaded die.
  
  Solution: The probability of scoring 6 with loaded die is 7/12.
  
  LikeLike
- John Crabtree 2:16 am on 4 February 2021 Permalink | Reply
  
  I was fortunate and took the probability of the throwing 6 with the biased die as n times that of any other number ie n>5 and p = n/(n+5).
  I reached t = 10 + 9/(n+2) when Jim’s two situations are immediately apparent.
  
  LikeLike

Jim Randell 5:01 pm on 29 January 2021 Permalink | Reply
Tags: by: Stephen Hogg ( 65 )

Teaser 3045: Let Tel play BEDMAS hold ’em!

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

Awaiting guests on poker night, Tel placed (using only clubs, face-up, in order left-to-right) the Ace (=1) to 9 (representing numerals), then interspersed the Ten, Jack, Queen and King (representing –, +, × and ÷ respectively) in some order, but none together, among these.

This “arithmetic expression” included a value over 1000 and more even than odd numbers. Applying BEDMAS rules, as follows, gave a whole-number answer. “No Brackets or powErs, so traverse the expression, left-to-right, doing each Division or Multiplication, as encountered, then, again left-to-right, doing each Addition or Subtraction, as encountered.”

Tel’s auntie switched the King and Queen. A higher whole-number answer arose. Tel displayed the higher answer as a five-card “flush” in spades (the Jack for + followed by four numeral cards).

Give each answer.

[teaser3045]

Jim Randell 5:51 pm on 29 January 2021 Permalink | Reply

I took “whole number” to be any integer, although you get the same answer if you just use positive integers.

It was fun writing the [[ evaluate() ]] routine to perform the calculations in the described fashion (although it is just standard arithmetic precedence rules).

The following Python program runs in 59ms.

Run: [ @replit ]

from enigma import (Rational, irange, subsets, tuples, peek, as_int, catch, update, multiset, join, printf)

# implementation of rationals
Q = Rational()

# map operators to implementation
fn = {
  '+': (lambda a, b: a + b),
  '-': (lambda a, b: a - b),
  '*': (lambda a, b: a * b),
  '/': (lambda a, b: Q(a, b)),
}

# evaluate the expression <ss>
def evaluate(ss):
  ss = list(ss)
  # precedence order
  for ops in [set('*/'), set('+-')]:
    while True:
      # find the leftmost occurrence of an operator
      i = peek((i for (i, op) in enumerate(ss) if op in ops), default=-1)
      if i == -1: break
      # apply the operation
      assert 0 < i < len(ss) - 1
      n = fn[ss[i]](ss[i - 1], ss[i + 1])
      ss[i - 1:i + 2] = [n]
  assert len(ss) == 1
  return ss[0]

# interleave 2 sequences (until one runs out)
def interleave(s1, s2):
  (i1, i2) = (iter(s1), iter(s2))
  while True:
    try:
      yield next(i1)
      yield next(i2)
    except StopIteration:
      break

# the string of digits
digits = "123456789"
ds = multiset.from_seq(digits)

# slice up the string of digits
n = len(digits)
for ps in subsets(irange(1, n - 1), size=4, fn=list):
  ns = tuple(int(digits[i:j]) for (i, j) in tuples([0] + ps + [n]))
  # at least one number is greater than 1000
  if not any(n > 1000 for n in ns): continue
  # there are more even numbers than odd numbers
  if not (len(ns) > 2 * sum(n % 2 for n in ns)): continue

  # insert the operators
  for ops in subsets("+-*/", size=4, select="P"):
    # make the first expression
    ss1 = list(interleave(ns, ops))
    # evaluate it
    r1 = catch(as_int, evaluate(ss1))
    if r1 is None: continue

    # swap * and /
    ss2 = update(ss1, [(ss1.index('*'), '/'), (ss1.index('/'), '*')])
    r2 = catch(as_int, evaluate(ss2))
    if r2 is None or not(r1 < r2): continue    

    # the result is a positive 4-digit number
    if r2 < 1000 or r2 > 9999: continue
    # that can be represented using the available digits
    if not ds.issuperset(str(r2)): continue

    # output solution
    printf("{ss1} = {r1}; {ss2} = {r2}", ss1=join(ss1, sep=" "), ss2=join(ss2, sep=" "))

Solution: Tel’s answer was 1274. Auntie’s answer was 1289.

The expressions are:

Tel: 1234 + 56 × 7 ÷ 8 − 9 = 1274
Auntie: 1234 + 56 ÷ 7 × 8 − 9 = 1289

There are only 6 ways to split up the digits in the required fashion:

1 | 2 | 34 | 5678 | 9
1 | 2 | 3456 | 78 | 9
12 | 3 | 4 | 5678 | 9
12 | 3456 | 7 | 8 | 9
1234 | 5 | 6 | 78 | 9
1234 | 56 | 7 | 8 | 9

Which lead to 22 expressions that evaluate to a positive integer.

There are 2 further candidate solutions resulting in 4-digit positive numbers, but Tel would not be able to display the result as described:

Tel: 12 × 3 ÷ 4 + 5678 − 9 = 5678
Auntie: 12 ÷ 3 × 4 + 5678 − 9 = 5685

Tel: 1234 − 56 ÷ 7 × 8 + 9 = 1179
Auntie: 1234 − 56 × 7 ÷ 8 + 9 = 1194

LikeLike

Tony Brooke-Taylor 11:02 am on 31 January 2021 Permalink | Reply

I was going mad trying to find my error but when I compared my solution to yours I get the same. I guess the puzzle allows for an Ace in the flush.

LikeLike
- Jim Randell 2:05 pm on 31 January 2021 Permalink | Reply
  
  @Tony: There is only one candidate solution that is positive, and is composed of 4 distinct positive digits. And I was happy enough that this could be represented using the described cards.
  
  Fortunately I don’t know enough about poker to know if this counts as a “5 card flush” or not.
  
  LikeLike

Frits 9:23 pm on 30 January 2021 Permalink | Reply

from enigma import SubstitutedExpression
from itertools import  permutations

def check(li):
  # credit: B. Gladman
  # there must be more even than odd numbers
  if sum([x & 1 for x in li]) > 2:
    return ""
    
  li2 = [str(x) for x in li]  
  for p in permutations("*/+-", 4):
    exp = ''.join(a + b for a, b in zip(li2, p + ('',)))
    ev = eval(exp) 
    if ev % 1 == 0 and ev >= 0:
      exp2 = ''.join(chr(ord(c) ^ 5) if c in '/*' else c for c in exp)
      ev2 = eval(exp2) 
      if ev2 > ev and ev2 % 1 == 0:
        ev2 = int(ev2)
        # larger answer has distinct non-zero digits
        if "0" not in str(ev2) and len(set(str(ev2))) == len(str(ev2)):
          return exp + " ; " + exp2
      
  return ""


# the alphametic puzzle
p = SubstitutedExpression(
  [
  "T + 1 == U or T == 0",
  "S + 1 == T or S == 0",
  "R + 1 == S or R == 0",
  "[x for x in [R, S, T, U] if x > 0][0] == Q + 1",

  "P + 1 == Q or P == 0",
  "O + 1 == P or O == 0",
  "N + 1 == O or N == 0",
  "[x for x in [N, O, P, Q] if x > 0][0] == M + 1",

  "L + 1 == M or L == 0",
  "K + 1 == L or K == 0",
  "J + 1 == K or J == 0",
  "[x for x in [J, K, L, M] if x > 0][0] == H + 1",

  "G + 1 == H or G == 0",
  "F + 1 == G or F == 0",
  "E + 1 == F or E == 0",
  "[x for x in [E, F, G, H] if x > 0][0] == D + 1",

  "C + 1 == D or C == 0",
  "B + 1 == C or B == 0",
  "A + 1 == B or A == 0",
  "[x for x in [A, B, C, D] if x > 0][0] == 1",
  
  # included a value over 1000
  "sum([A > 0, E > 0, J > 0, N > 0, R > 0]) = 1",
  
  "len(check([ABCD, EFGH, JKLM, NOPQ, RSTU])) > 0",
  
  ],
  answer="check([ABCD, EFGH, JKLM, NOPQ, RSTU])", 
  distinct="",
  env=dict(check=check),
  d2i=dict([(0, "DHMQU")] + 
           [(1, "EFGHJKLMNOPQRSTU")] + 
           [(2, "JKLMNOPQRSTU")] + 
           [(3, "NOPQRSTU")] +
           [(4, "RSTU")] +
           [(5, "RSTU")] +
           [(k, "U") for k in range(6, 9)]
           ),

  #reorder=0,
  verbose=0
  )   
  
# Print answer
for (_, ans) in p.solve():
  print(f"{ans}")

LikeLike

Jim Randell 9:19 am on 28 January 2021 Permalink | Reply
Tags: by: N A Phillips ( 5 )

Brain-Teaser 685: Overseas mail

From The Sunday Times, 1st September 1974 [link]

We were visiting the island state of Kimbu and had come to the post-office to send off some parcels to friends at home. The island’s currency is the pim, and the postmaster told us that he had only stamps of five different face-values, as these had to be used up before a new issue of stamps was introduced.

These stamps were black, red, green, violet, and yellow, in descending order of values, the black being the highest denomination and the yellow the lowest.

One parcel required stamps to the value of 100 pims and we were handed 9 stamps; 5 black, one green, and 3 violet. The other two parcels required 50 pims’ worth each, and for these we were given two different sets of 9 stamps.

One consisted of 1 black and 2 of each of the other colours, and the other set contained 5 green and 1 of each of the others.

What would be been the smallest number of stamps needed for a 50-pim parcel, and of which colours?

This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980). The puzzle text above is taken from the book.

[teaser685]

Jim Randell 9:20 am on 28 January 2021 Permalink | Reply
I assumed the denominations of the stamps were all positive integer values.

We can place lower and upper limits on the values of the stamps.

The stamps are ordered: B > R > G > V > Y, which gives minimum values of: 5, 4, 3, 2, 1.

And 5 black stamps are used in making a value of 100, so black must have a value of less than (100 − (3 + 3×2)) / 5 = 18.2.

Similarly, 5 green stamps are used in making a value of 50, so green must have a value of less than (50 − (5 + 4 + 2 + 1)) / 5 = 7.6.

So we can write down the following ranges for each denomination:

B: 5..18
R: 4..17
G: 3..7
V: 2..6
Y: 1..5

And we have three equations relating the values. So choosing values for V and Y will give us a set of 5 simultaneous equations that can be solved to find the other values.

This Python program use the [[ matrix.linear() ]] solver for systems of linear equations from the enigma.py library. It runs in 63ms.

Run: [ @repl.it ]
```
from enigma import (irange, subsets, matrix, as_int, express, group, printf)

# choose values for Y and V
for (Y, V) in subsets(irange(1, 6), size=2):

  # make the equations
  eqs = [
    # B  R  G  V  Y = ???
    ((5, 0, 1, 3, 0), 100), # 100-pim parcel
    ((1, 2, 2, 2, 2),  50), # 1st 50-pim parcel
    ((1, 1, 5, 1, 1),  50), # 2nd 50-pim parcel
    ((0, 0, 0, 0, 1),   Y), # Y value
    ((0, 0, 0, 1, 0),   V), # V value
  ]

  # solve the equations for integer values
  # (either matrix.linear() or as_int() may raise a ValueError)
  try:
    (B, R, G, V, Y) = (as_int(x) for x in matrix.linear(*zip(*eqs)))
  except ValueError:
    continue

  # check ordering
  if not (B > R > G > V > Y > 0): continue

  # find combinations that make 50, grouped by the total number of stamps
  d = group(express(50, [Y, V, G, R, B]), by=sum)
  # output minimal configurations
  k = min(d.keys())
  for (y, v, g, r, b) in d[k]:
    printf("{k} stamps; 50 = {b}x {B} (black), {r}x {R} (red), {g}x {G} (green), {v}x {V} (violet), {y}x {Y} (yellow)")
```
Solution: A 50-pim parcel can be sent using 5 stamps: 2 black, 1 red, 1 green, 1 yellow.

The values of the stamps are:

black = 18 pim
red = 9 pim
green = 4 pim
violet = 2 pim
yellow = 1 pim

So each stamp is half (rounded down) the next highest value.

There are 621 different ways to make 50 using the above denominations.

Here’s a manual derivation of the denominations:

[1] B + 2R + 2G + 2V + 2Y = 50
[2] B + R + 5G + V + Y = 50

Taking 2×[2] − [1] gives:

B + 8G = 50

And we know G is in the range 3 .. 7, and B is in the range 5 .. 18 and G < B:

G = 3 ⇒ B = 26 [not possible]
G = 4 ⇒ B = 18
G = 5 ⇒ B = 10
G = 6 ⇒ B = 2 [not possible]
G = 7 ⇒ B = −6 [not possible]

And:

5B + G + 3V = 100

Where V is in the range 2 .. 6 and V < G:

G = 4, B = 18 ⇒ V = 2
G = 5, B = 10 ⇒ V = 15 [not possible]

So we have: V = 2, G = 4, B = 18.

From which we see Y = 1, and R = 9.

LikeLike
- Jim Randell 5:55 pm on 28 January 2021 Permalink | Reply
  Here’s a solution using the [[ SubstitutedExpression ]] solver from the enigma.py library. It runs in 122ms.
  
  It operates in base 19 as B ≤ 18.
  
  The only other restriction I used was that we already know that 50 is possible with 9 stamps, so I limit the numbers used for any single denomination to 8. (We can also do this in my Python program above, by passing [[ qs=irange(0, 8) ]] to the call to [[ express() ]] and that saves a little bit of time).
  
  We could restrict the other denominations in line with the ranges given above, but it is not necessary for a decent run time.
  
  Run: [ @repl.it ]
```
#! python -m enigma -rr

SubstitutedExpression

--base=19
--symbols="BRGVYbrgvy"
--distinct="BRGVY"

# work out the denominations
"Y > 0"
"V > Y"
"G > V"
"R > G"
"B > R"

"5 * B + G + 3 * V == 100" # 100 pim parcel
"B + 2 * (R + G + V + Y) == 50" # 1st 50 pim parcel
"5 * G + (B + R + V + Y) == 50" # 2nd 50 pim parcel

# find minimal amount to make 50
"b * B + r * R + g * G + v * V + y * Y == 50"

--answer="((b, r, g, v, y), (B, R, G, V, Y))"
--code="fmin = lambda ss: min(ss, key=unpack(lambda ns, ds: sum(ns)))"
--accumulate="fmin"

--verbose=16

# [optional] we already know 50 is possible with 9 stamps
--invalid="9-18,brgvy"
```
  LikeLike

Frits 12:24 pm on 28 January 2021 Permalink | Reply

from enigma import SubstitutedExpression

# the alphametic puzzle
p = SubstitutedExpression(
  [
  # try to avoid looping over BL and RE
  "G > V",
  "V > Y",
  # (5, 0, 1, 3, 0)  100-pim parcel
  "(100 - G - 3*V) // 5 = BL",
  
  # (1, 2, 2, 2, 2)  1st 50-pim parcel
  "(50 - BL) // 2  - (G + V + Y) = RE",
  "RE > G",
  "BL > RE",
  # (1, 1, 5, 1, 1)  2nd 50-pim parcel
  "BL + RE + 5*G + V + Y = 50",
  
  # Pick M blacks, N reds, O greens, P violets and Q yellows
  # we already know a 50-pim parcel can be formed with 9 stamps
  "M + N < 10",
  "M + N + O < 10",
  "M + N + O + P < 10",
  "M + N + O + P + Q < 10",
  
  "M*BL + N*RE + O*G + P*V + Q*Y = 50", 
  ],
  answer="M + N + O + P + Q, M, N, O, P, Q",
  distinct="",
  accumulate=min,
  # BL: 5..18  RE: 4..12  G: 3..7  V: 2..6  Y: 1..5 
  d2i=dict([(0, "GVY")] + 
           [(1, "VG")] + 
           [(2, "RBG")] + 
           [(k, "RB") for k in range(3, 6)] +
           [(6, "YRB")] +
           [(7, "YVRB")] +
           [(k, "YVGRBMNOPQ") for k in range(8, 10)]),

  reorder=0,
  verbose=0
  )   
  
  
# solve the puzzle
r = p.run()

colors = ["black", "red", "green", "violet", "yellow"]
for (x, y) in zip(list(r.accumulate)[1:], colors):
  if x > 0:
    print(x, y)

LikeLike

GeoffR 3:04 pm on 28 January 2021 Permalink | Reply

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

% black, red, green, violet, yellow stamps
% ... using Jim's analysis values for all stamp ranges
var 5..18:B; var 4..17:R; var 3..7: G;
var 2..6: V; var 1..5:Y;

% stamp values all different and in colour descending values
constraint all_different([B, R, G, V, Y]);
constraint B > R /\ R > G /\ G > V /\ V > Y;

% numbers of each colour of stamp to make 50 pim
var 0..9:NumB; var 0..9:NumG; var 0..9:NumV;
var 0..9:NumR; var 0..9:NumY;

% three stamp equations stated in teaser description
% 1. 5 black, one green, and 3 violet stamps for 100 pim
constraint 5*B + G + 3*V == 100;

% two different equations for stamps of 50 pim
% 2. one set consisted of 1 black and 2 of each of the other colours
constraint B + 2*R + 2*G + 2*V + 2*Y == 50;

% 3. other set contained 5 green and 1 of each of other colours 
constraint B + R + 5*G + V + Y == 50;

% General equation to make 50 pims value
constraint NumB*B + NumR*R +  NumG*G + NumV*V + NumY*Y == 50;

% minimise total number of coins used to make 50 units value
solve minimize(NumB + NumR + NumG + NumV + NumY);

output [ "Black stamp value = " ++ show(B) ++ " pim"
++ ", Red stamp value = " ++ show(R) ++ " pim"
++ "\n" ++ "Green stamp value = " ++ show(G) ++ " pim"
++ ", Violet stamp value = " ++ show(V) ++ " pim"
++ "\n" ++ "Yellow stamp value = " ++ show(Y) ++ " pim"
++ "\n"
++ "\n" ++ "Smallest number of stamps needed for a 50-pim parcel" 
++ "\n" ++ "[B, R, G, V, Y] =  "
++ show (NumB),", ",show(NumR),", ",show(NumG),", ",show(NumV),", ",show(NumY) ];

% Black stamp value = 18 pim, Red stamp value = 9 pim
% Green stamp value = 4 pim, Violet stamp value = 2 pim
% Yellow stamp value = 1 pim

% Smallest number of stamps needed for a 50-pim parcel
% [B, R, G, V, Y] =  2, 1, 1, 0, 1
% ----------
% ==========

LikeLike

John Crabtree 12:07 am on 29 January 2021 Permalink | Reply

Eq. 1: 5.B + 0.R + 1.G +3.V + 0.Y = 100
Eq. 2: 1.B + 2.R + 2.G +2.V + 2.Y = 50
Eq. 3 : 1.B + 1.R + 5.G +1.V + 1.Y = 50
10 * Eq. 3 – 5 * Eq. 2 – Eq. 1 gives 39.G – 3.V = 150, or 13.G – V = 50
Assuming integer solutions, G = 4, V = 2 and then B = 18, R + Y = 10 etc

LikeLike

Jim Randell 8:16 am on 26 January 2021 Permalink | Reply
Tags: by: Victor Bryant ( 148 ), flawed ( 56 )
Teaser 2772: Madam I’m Adam
From The Sunday Times, 8th November 2015 [link] [link]

Adam noticed that today’s Teaser number was a four-figure palindrome. He told me that he had written down [a] four-figure palindrome and he asked me to guess what it was. I asked for some clues regarding its prime factors and so he told me, in turn, whether his number was divisible by 2, 3, 5, 7, 11, 13, … Only after he had told me whether it was divisible by 13 was it possible to work out his number.

What was his number?

When this was originally published “another” was used where I have placed “[a]”, but this makes the puzzle unsolvable. However, as presented above, there is a unique solution.

[teaser2772]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Frits and Jim Randell are discussing. Toggle Comments
- Jim Randell 8:17 am on 26 January 2021 Permalink | Reply
  The use of “another” in the puzzle text implies that the palindrome 2772 is excluded from the set of possibilities, but if this is the case the puzzle is not solvable. So instead we just consider that Adam has told the setter that he has written down some 4-digit palindrome (which may be 2772), and the setter has to guess it.
  
  This Python program considers increasing prime numbers p, and looks for palindromes that can be uniquely identified by knowing if it is divisible by primes up to (and including) p.
  
  To solve this puzzle we look up to p = 13, but the maximum prime can be specified on the command line. (We have to go to 859 to be sure of determining the palindrome).
  
  The program runs in 45ms.
```
from enigma import Primes, irange, filter_unique, diff, join, arg, printf

# max prime
N = arg(13, 0, int)

# 4-digit palindromes
palindromes = sorted(1001 * a + 110 * b for a in irange(1, 9) for b in irange(0, 9))
#palindromes.remove(2772) # puzzle text says 2772 is excluded, but that makes it impossible

# palindromes unique by divisibility of primes, but not unique by shorter sequences
r = set()
# consider sequences of primes by increasing length
ps = list()
for p in Primes(N + 1):
  ps.append(p)
  # find unique palindromes by this sequence of primes
  s = filter_unique(palindromes, lambda x: tuple(x % p == 0 for p in ps)).unique
  # unique palindromes we haven't seen before
  s = diff(s, r)
  if s:
    printf("{p} -> {s}", s=join(s, sep=", ", enc="()"))
  # update the list of unique palindromes
  r.update(s)
```
  Solution: The number was 6006.
  
  If 2772 is removed from the set of possible palindromes (by removing the comment from line 8), we see that 8778 would also be uniquely identified by the divisibility values for primes up to 13.
  
  So although the setter would know the answer (because he knows if the number is divisible by 13 or not), we can’t work it out:
  
  6006 → 2=Y, 3=Y, 5=N, 7=Y, 11=Y, 13=Y
  8778 → 2=Y, 3=Y, 5=N, 7=Y, 11=Y, 13=N, [17=N, 19=Y]
  2772 → 2=Y, 3=Y, 5=N, 7=Y, 11=Y, 13=N, [17=N, 19=N]
  
  But, if 2772 is included in the set of possible palindromes, then 8778 and 2772 cannot be distinguished until we are told the answer for divisibility by 19, so the fact that the setter can work out the number at p = 13 means that it must be 6006.
  
  There are two palindromes that can be distinguished with a shorter sequence of answers:
  
  5005 → 2=N, 3=N, 5=Y, 7=Y
  5775 → 2=N, 3=Y, 5=Y, 7=Y
  
  Note that all palindromes are divisible by 11.
  
  LikeLike
- Frits 8:08 pm on 26 January 2021 Permalink | Reply
  With fewer modulo calculations.
```
from collections import Counter
 
# max prime
N = 13

# list of prime numbers
P = [2, 3, 5, 7, 11, 13]
 
# 4-digit palindromes
palindromes = sorted(1001 * a + 110 * b for a in range(1, 10) 
                                        for b in range(0, 10))

# initialize dictionary (divisibility by prime)                                    
d = {key: [] for key in palindromes}
 
singles = []
# consider sequences of primes by increasing length
for p in P:
  # maintain dictionary (divisibility by prime)   
  for x in palindromes:
    d[x].append(x % p == 0)
   
  c = Counter(map(tuple, d.values()))
  # get combinations unique by divisibility of primes
  # but not unique by shorter sequences
  c2 = [k for k, v in c.items() if v == 1 and 
        all(k[:-i] not in singles for i in range(1, len(k)))]
  
  if len(c2) == 1:
    for x in palindromes:
      if d[x] == list(c2[0]):
        print(f"{p} -> {x}")
        if p != N:
          print("Error: palindrome already known before prime", N)
        exit()  
        
  # add "unique by shorter sequences" to singles
  for x in [k for k, v in c.items() if v == 1]:
    singles.append(x)
```
  LikeLike

Jim Randell 10:07 am on 24 January 2021 Permalink | Reply
Tags: by: A. Bowie

Brain-Teaser 19: Hillside Farm

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

My friend, Mr. Little, is a farmer whose chief interest is in sheep, but keeps a number of Shorthorn and Redpoll (polled) cattle too.

Mr. Little is six years older than his wife and 33 years older than his son, George. George is twice as old as Mary, the daughter of the house, whose birthday happens to be today.

There is no tractor at Hillside Farm and Mr. Little does the ploughing behind his two horses leaving a furrow nine inches wide. The number of acres ploughed this year happens to be the same as the number of cats on the farm.

Readers are invited to determine the information required to complete the following “cross-number” puzzle:

Across:

1a: Number of Mr. Little’s Redpoll cows.
3a: Square of the number of Redpoll cows.
5a: Total number of cows.
6a: Mr. Little’s age.
7a: Number of ewes per ram in Mr. Little’s flock. This also happens to be the number of miles walked by Mr. Little in doing this year’s ploughing.
9a: Acreage of rough grass land. (1.5 acres per ewe).
11a: Age of Mrs. Little.
12a: Number of ewes in flock (in scores).
13a: Cube of the number of collies on the farm.

Down:

1d: Area of rectangular farmyard in square yards.
2d: Length of farmyard in yards.
3d: Number of ewes on the farm.
4d: Age at which Mr. Little intends to retire.
7d: Seven times Mr. Little’s age.
8d: Total number of sheep.
10d: Number of rams on the farm.
12d: Total number of horns possessed by all the cattle.

[teaser19]

Jim Randell 10:12 am on 24 January 2021 Permalink | Reply

I didn’t need to use all the information given to solve the puzzle. But I did need to look up what “polled” meant – it means “lacking horns”.

I used the [[ SubstitutedExpression ]] solver from the enigma.py library to solve the puzzle as a collection of alphametic expressions.

The following run file executes in 131ms.

Run: [ @repl.it ]

#! python -m enigma -rr

# consider the grid:
#
#  A B # C D E
#  F G # H I #
#  J # K L # M
#  N P Q R # S
#  # T U # V W
#  # # # X Y Z

SubstitutedExpression

--distinct=""

# 1a. AB = "Number of redpoll cows"
# 3a. CDE = "Square of the number of redpoll cows"
# 5a. FG = "Total number of cows"
# 12d. VY = "Total number of horns possessed by all the cattle"
"AB * AB = CDE"
"AB < FG"
"2 * (FG - AB) = VY"

# 6a. HI = "Mr Little's age" (= wife + 6)
# 11a. TU = "Age of Mrs. Little"
# 7d. KQU = "Seven times Mr Little's age"
# 4d. DI = "Age at which Mr Little intends to retire"
"TU + 6 = HI"
"HI * 7 = KQU"
"HI < DI"

# 7a. KL = "Number of ewes per ram."
# 9a. NPQR = "Acreage of rough grassland. 1.5 acres per ewe"
# 12a. VW = "Number of ewes in flock (in scores)
# 3d. CHLR = "Number of ewes on the farm"
# 10d. PT = "Number of rams on the farm"
# 8d. MSWZ = "Total number of sheep"
"VW * 20 = CHLR"
"2 * NPQR == 3 * CHLR"
"CHLR + PT = MSWZ"
"PT * KL = CHLR"

# 13a. XYZ = "Cube of the number of collies on the farm"
"is_cube(XYZ)"

# 1d. AFJN = "Area of farmyard in square yards"
# 2d. BG = "Length of farmyard in yards"
"AFJN % BG = 0"

# across / down
--template="(AB CDE FG HI KL NPQR TU VW XYZ) (AFJN BG CHLR DI KQU MSWZ PT VY)"
--solution=""

Solution: The completed grid looks like this:

From which we get the following information

Number of redpoll cows = 13
Number of shorthorn cows = 36
(Total number of cows = 49)
(Total number of horns = 72)

Number of ewes = 1540 (= 77× 20)
Number of rams = 35
(Ewes/ram = 44)
(Total number of sheep = 1575)
Area of rough grassland = 2310

Mr. Little’s age = 59
Retirement age = 69
(Mrs. Little’s age = 53)

Area of farmyard = 1482
Length of farmyard = 39
(Width of farmyard = 38)

Number of collies = 5

And from the text we can deduce the following further information:

(George’s age = 26)
(Mary’s age = 13)

(Number of cats = 4)

LikeLike

Frits 2:06 pm on 24 January 2021 Permalink | Reply

 
 consider the grid:

  A B # C D E
  F G # H I #
  J # K L # M
  N P Q R # S
  # T U # V W
  # # # X Y Z

Rules:

AB * AB = CDE
AB < FG
2 * (FG - AB) = VY
TU + 6 = HI
HI * 7 = KQU
HI < DI
VW * 20 = CHLR
2 * NPQR = 3 * CHLR
CHLR + PT = MSWZ
PT * KL = CHLR
is_cube(XYZ)
AFJN % BG = 0


VW * 20 = CHLR -> R=0 C=1 L=even
AB * AB = 1DE --> A=1 
HI>33 and DI>HI ->  CDE in (144, 169, 196)
PT * KL = CHL0 -> T=5 or L=0
1 mile=63360 inches, 1 acre=6272640 square inches
no cats = KL * 63360 * 9 / 6272640 = KL / 11 
KL multiple of 11 -> K=L, K!=0 so T=5
CHL0 + PT = MSWZ -> Z=T so Z=5 -> XYZ=125 
Age George is even so TU and HI are odd
TU HI KQU
51 57 399 U's inconsistent 
53 59 413 OK
55 61 427 U's inconsistent 
57 53 441 U's inconsistent 
59 65 455 U's inconsistent 
So TU=53, HI=59, KQU=413 -> L=4
VW * 20 = 1540 -> VW=77
2 * NPQR = 3 * 1540 -> NPQR=2310
CHLR + PT = MSWZ  -> MSWZ=1575
2 * (FG - AB) = 72 -> FG = AB + 36
HI=59 -> DI>59 and CDE is 169 or 196
so AB/FG is 13/49 or 14/50
1FJ2 % BG = 0 -> AB=13 FG=49 CDE=169
14J2 % 39 = 0 -> J=8

LikeLike

Frits 6:12 pm on 24 January 2021 Permalink | Reply

Similar.

from functools import reduce
 
# convert numbers to digit sequences and vice versa
# Credit: B. Gladman
d2n = lambda s: reduce(lambda x,  y: 10 * x + y, s) 
n2d = lambda n: [n] if n < 10 else n2d(n // 10) + [n % 10] 

# consider the grid:
#
#  A B # C D E
#  F G # H I #
#  J # K L # M
#  N P Q R # S
#  # T U # V W
#  # # # X Y Z

# "VW * 20 = CHLR"
for V in range(1, 10):
  for W in range(10):
    CHLR = d2n([V, W]) * 20
    if len(str(CHLR)) != 4: continue
    (C, H, L, R) = n2d(CHLR)
    
    # "AB * AB = CDE"
    for A in range(1, 10):
      for B in range(1, 10):
        AB = d2n([A, B])
        CDE = AB * AB
        if len(str(CDE)) != 3: continue
        (c, D, E) = n2d(CDE)
        if c != C: continue
        
        # "2 * NPQR == 3 * CHLR"
        NPQR = int(1.5 * (CHLR))
        if len(str(NPQR)) != 4: continue
        (N, P, Q, r) = n2d(NPQR)
        if r != R: continue
        
        # "PT * KL = CHLR"
        for K in range(1, 10):
          PT = CHLR // d2n([K, L])
          if len(str(PT)) != 2: continue
          (p, T) = n2d(PT)
          if p != P: continue
          
          # "CHLR + PT = MSWZ"
          MSWZ = CHLR + PT
          if len(str(MSWZ)) != 4: continue
          (M, S, W, Z) = n2d(MSWZ)
          
          # "2 * (FG - AB) = VY"
          for Y in range(10):
            FG = AB + d2n([V, Y]) // 2
            if len(str(FG)) != 2: continue
            (F, G) = n2d(FG)
            
            # "TU + 6 = HI"
            for U in range(10):
              HI = d2n([T, U]) + 6
              if len(str(HI)) != 2: continue
              (h, I) = n2d(HI)
              if h != H: continue
              
              # "HI < DI"
              if not HI < d2n([D, I]): continue
              
              # "HI * 7 = KQU"
              KQU = HI * 7
              if len(str(KQU)) != 3: continue
              (k, q, u) = n2d(KQU)
              if k != K or q != Q or u != U: continue
              
              # "is_cube(XYZ)"
              for X in [1, 2, 3, 5, 7]:
                XYZ = d2n([X, Y, Z])
                if not XYZ in {125, 216, 343, 512, 729}: continue
                
                # "AFJN % BG = 0"
                for J in range(10):
                  AFJN = d2n([A, F, J, N])
                  if not AFJN % d2n([B, G]) == 0: continue
                  
                  print("CHLR CDE AB PT FG HI KQU MSWZ XYZ")
                  print(CHLR, CDE, AB, PT, FG, HI, KQU, MSWZ, XYZ)
              
                  print("A B C D E F G H I J K L")
                  print(A, B, C, D, E, F, G, H, I, J, K, L)
                  print("M N P Q R S T U V W X Z")
                  print(M, N, P, Q, R, S, T, U, V, W, X, Z)

LikeLike

Jim Randell 5:02 pm on 22 January 2021 Permalink | Reply
Tags: by: Colin Vout ( 39 )

Teaser 3044: Building blocks

From The Sunday Times, 24th January 2021 [link] [link]

The kids had used all the blocks each of them owned (fewer than 100 each) to build triangular peaks — one block on the top row, two on the next row, and so on.

“My red one’s nicer!”

“My blue one’s taller!”

“Why don’t you both work together to make one bigger still?” I said.

I could see they could use all these blocks to make another triangle.

This kept them quiet until I heard, “I bet Dad could buy some yellow blocks to build a triangle bigger than either of ours was, or a red and yellow triangle, or a yellow and blue triangle, with no blocks ever left over.”

This kept me quiet, until I worked out that I could.

How many red, blue and yellow blocks would there be?

[teaser3044]

Jim Randell 5:18 pm on 22 January 2021 Permalink | Reply

The following Python program runs in 43ms.

Run: [ @repl.it ]

from enigma import tri, irange, inf, first, subsets, is_triangular, printf

# generate triangular numbers from tri(a) to tri(b)
tris = lambda a=1, b=inf: (tri(i) for i in irange(a, b))

def solve():
  # collect triangular numbers less than 100
  ts = first(tris(), (lambda x: x < 100))

  # choose (R, B) pairs that sum to another triangular number
  RBs = list(s for s in subsets(ts, size=2) if is_triangular(sum(s)))

  # consider values for Y
  for Y in tris(is_triangular(min(B for (R, B) in RBs)) + 1):
    # look for R, B pairs that work with Y
    for (R, B) in RBs:
      if B < Y and is_triangular(R + Y) and is_triangular(B + Y):
        yield (R, B, Y)

# look for the first solution
for (R, B, Y) in solve():
  printf("R={R} B={B} Y={Y}")
  break

Solution: There were 45 red blocks; 91 blue blocks; 990 yellow blocks.

We have:

R = 45 = T(9)
B = 91 = T(13)
R + B = 136 = T(16)

Y = 990 = T(44)
R + Y = 1035 = T(45)
B + Y = 1081 = T(46)

It makes me wish Python allowed something like a [[ while ... ]] clause in list comprehensions, so they could be terminated early:

ts = (t for t in tris() while t < 100)

This exact syntax was actually proposed [ PEP 3142 ], but not implemented.

I’ve folded the functionality into the [[ first() ]] function in the enigma.py library, so it can take a function and collection of items will stop when the function returns a false value for an item.

LikeLike

Frits 11:11 pm on 22 January 2021 Permalink | Reply

@Jim, I can imagine a similar puzzle in 3D. Didn’t we have such a puzzle before?

LikeLike

Jim Randell 10:58 am on 23 January 2021 Permalink | Reply

Here’s an exhaustive version, based on the observation that if Y = tri(y) then R ≥ y + 1, otherwise it will not be possible to complete an additional row of the Y triangle using R blocks.

It still runs in 46ms.

Run: [ @repl.it ]

from enigma import tri, irange, inf, first, subsets, is_triangular, printf

# generate triangular numbers from tri(a) to tri(b)
tris = lambda a=1, b=inf: (tri(i) for i in irange(a, b))

# collect triangular numbers less than 100
ts = first(tris(), (lambda x: x < 100))

# choose (R, B) pairs that sum to another triangular number
for (R, B) in subsets(ts, size=2):
  if not is_triangular(R + B): continue

  # consider values for Y
  for Y in tris(is_triangular(B) + 1, R - 1):
    if is_triangular(R + Y) and is_triangular(B + Y):
      printf("R={R} B={B} Y={Y}")

This code can also be used to explore larger solutions by increasing the limit at line 7.

There is 1 further solution below 1275:

R = T(23) = 276
B = T(30) = 465
Y = T(90) = 4095

LikeLike

Frits 10:55 pm on 22 January 2021 Permalink | Reply

Nothing has been implemented regarding upper limits of RE and BL, the program runs fast enough (between 31 ms and 46 ms).

from enigma import SubstitutedExpression 

# the alphametic puzzle
p = SubstitutedExpression(
  [
  # number of reds    = RE * (RE + 1)/2
  # number of blues   = BL * (BL + 1)/2
  # number of yellows = YW * (YW + 1)/2
  "RE > 0",
  "BL > 0", 
  
  # My blue one's taller
  "BL > RE",
  
  # fewer than 100 each
  "BL * (BL + 1) // 2 < 100",
  
  # they could use all these blocks to make another triangle
  "RE * (RE + 1) // 2 + BL * (BL + 1) // 2 == JK * (JK + 1) // 2",
  
  # Dad could buy some yellow blocks to build a triangle bigger 
  # than either of ours was, or a red and yellow triangle, 
  # or a yellow and blue triangle, with no blocks ever left over
  "YW > BL",
  
  "YW * (YW + 1) // 2 + RE * (RE + 1) // 2 == CD * (CD + 1) // 2",
  "YW * (YW + 1) // 2 + BL * (BL + 1) // 2 == FG * (FG + 1) // 2",
  
  ],
  answer="RE * (RE + 1) // 2, BL * (BL + 1) // 2, YW * (YW + 1) // 2",
  distinct="",
  reorder=0,
  d2i={},
  verbose=0)   

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

LikeLike

Frits 8:52 am on 23 January 2021 Permalink | Reply

Similar.

from enigma import SubstitutedExpression, is_square 

# the alphametic puzzle
p = SubstitutedExpression(
  [
  # If n is the mth triangular number, then n = m*(m+1)/2
  # and m = (sqrt(8n+1) - 1) / 2

  # number of reds    = RE * (RE + 1)/2
  # number of blues   = BL * (BL + 1)/2
  # number of yellows = YW * (YW + 1)/2
  "RE > 0",
  "BL > 0", 
  
  # My blue one's taller
  "BL > RE",
  
  # fewer than 100 each
  "BL * (BL + 1) // 2 < 100",
  
  # they could use all these blocks to make another triangle
  "is_square(4 * (BL * (BL + 1) + RE * (RE + 1)) + 1)",
  
  # Dad could buy some yellow blocks to build a triangle bigger 
  # than either of ours was, or a red and yellow triangle, 
  # or a yellow and blue triangle, with no blocks ever left over
  "YW > BL",
  
  "is_square(4 * (YW * (YW + 1) + RE * (RE + 1)) + 1)",
  "is_square(4 * (YW * (YW + 1) + BL * (BL + 1)) + 1)",
  
  ],
  answer="RE * (RE + 1) // 2, BL * (BL + 1) // 2, YW * (YW + 1) // 2",
  distinct="",
  reorder=0,
  d2i={},
  verbose=0)   

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

LikeLike

Frits 10:53 am on 23 January 2021 Permalink | Reply

One (ugly) statement, no imports.

The “is_square” method “n**.5 % 1 == 0” will fail for large numbers of n (like 152415789666209426002111556165263283035677490).

print([(r * (r + 1) // 2, b * (b + 1) // 2, y * (y + 1) // 2) 
  # Triangular root <m> of n = m*(m+1)/2  is (sqrt(8n+1) - 1) / 2
  # combinations of red and blue triangular roots and number of blocks < 100
  for (r, b) in [(c1, c2) 
    for c1 in range(1, [m for m in range(1, 50) if m * (m + 1)> 198][0] - 1) 
    for c2 in range(c1 + 1, [m for m in range(1, 50) if m * (m + 1)> 198][0]) 
    # they could use all these blocks to make another triangle
    if (4 * (c1 * (c1 + 1) + c2 * (c2 + 1)) + 1)**.5 % 1 == 0] 
  for y in range(b + 1, 99) 
  # red and yellow triangle, with no blocks ever left over
  # blue and yellow triangle, with no blocks ever left over
  if (4 * (r * (r + 1) + y * (y + 1)) + 1)**.5 % 1 == 0 and
     (4 * (b * (b + 1) + y * (y + 1)) + 1)**.5 % 1 == 0])

LikeLike

Frits 12:44 pm on 23 January 2021 Permalink | Reply

[m for m in range(1, 50) if m * (m + 1)> 198][0]

can be achieved more efficiently (probably) by:

next(filter(lambda m: m * (m + 1)> 198, range(1, 50)))

LikeLike

Jim Randell 8:11 am on 21 January 2021 Permalink | Reply
Tags: by: Richard Furner

Brain-Teaser 683: Powerless

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

I have here two positive single figure numbers, each less than 9. Neither is a factor of the other. I add the larger number to the smaller.

Then, to that total I again add the original larger number, and to the new total I again add the original larger number and may, if I like, continue this process indefinitely, but never shall I obtain a total which is a “power” of any whole number whatsoever.

What are my two numbers?

This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980). The puzzle text above is taken from the book.

[teaser683]

Jim Randell 8:11 am on 21 January 2021 Permalink | Reply

This Python program narrows down the candidate pairs until there is only one left, so if there is a solution this must be it.

It runs in 49ms.

Run: [ @replit ]

from enigma import (subsets, irange, prime_factor, mgcd, unpack, printf)

# check a number is _not_ an exact power
check = lambda n, gcd=unpack(mgcd): gcd(e for (p, e) in prime_factor(n)) == 1

# record totals and pairs of numbers
ss = list((A + B, A, B) for (A, B) in subsets(irange(2, 8), size=2) if B % A != 0)

# for each total that is not an exact power, add in B to the total
while len(ss) > 1:
  ss = list((t + B, A, B) for (t, A, B) in ss if check(t))

# output candidate solutions
for (t, A, B) in ss:
  printf("A={A} B={B}")

Solution: The two numbers are 6 and 8.

To show that this is indeed a solution we need to show that (6 + 8k) can never be a non trivial exact power.

To find a counter example, we are looking for for some positive integers k, a, n, where n ≥ 2, such that:

6 + 8k = a^n
2(3 + 4k) = a^n

Clearly the LHS is a multiple of 2. So the RHS must also be a multiple of 2, so let: a = 2b.

2(3 + 4k) = (2b)^n
2(3 + 4k) = (2^n)(b^n)
3 + 4k = 2^(n − 1)(b^n)

Clearly the RHS is divisible by 2, but the LHS is not divisible by 2.

So (6 + 8k) can never be an exact power of an integer.

Most of the pairs drop out fairly quickly, but (3, 7) hangs in until we get to 2187 = 3 + 312×7 = 3^7.

Leaving (6, 8) as the only remaining candidate.

LikeLike

Jim Randell 11:06 am on 21 January 2021 Permalink | Reply

Here is a more efficient program that reuses the code I wrote for Enigma 1777 to generate powers in numerical order.

Then for each power we remove pairs of numbers that can be used to make that power, until there is only a single pair remaining.

Run: [ @replit ]

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

# generate powers in numerical order (starting from 2 ** 2)
def powers():
  base = { 2: 2 }
  power = { 2: 4 }
  maxp = 2
  primes = Primes(32, expandable=1).generate(maxp + 1)
  while True:
    # find the next power
    n = min(power.values())
    yield n
    # what powers are involved
    ps = list(p for (p, v) in power.items() if v == n)
    # increase the powers
    for p in ps:
      base[p] += 1
      power[p] = pow(base[p], p)
    # do we need to add in a new power?
    if maxp in ps:
      maxp = next(primes)
      base[maxp] = 2
      power[maxp] = pow(2, maxp)

# possible pairs of numbers
ss = list((A, B) for (A, B) in subsets(irange(2, 8), size=2) if B % A != 0)

# consider increasing powers
for n in powers():
  # remove any pairs that can make n
  ss = list((A, B) for (A, B) in ss if div(n - A, B) is None)
  if len(ss) < 2:
    printf("solution: {ss}")
    break

LikeLike

Frits 8:15 pm on 21 January 2021 Permalink | Reply

Python 3.9 introduced multiple arguments version of math.gcd.

Without imports.

def prime_factors(n):
  i = 2
  factors = []
  while i * i <= n:
    if n % i:
      i = 3 if i == 2 else i + 2
    else:
      n //= i
      factors.append(i)
  if n > 1:
    factors.append(n)
    
  return factors
   
def is_a_power(n):
  pf = prime_factors(n)
  if len(pf) < 2: 
    return False
    
  # occurences of digits  
  oc = {pf.count(x) for x in set(pf)}
  if mult_gcd(list(oc)) == 1:
    return False
  return True

# calculate greatest common divisor of multiple numbers  
def mult_gcd(li):
  if len(li) == 1:
    return li[0]

  for i in range(len(li) - 1):
    a = li[i]
    b = li[i+1]
    while b:
      (a, b) = (b, a % b)
    
    if a == 1: return a
    
    li[i+1] = a
  return a  

# record totals and pairs of numbers
ss = [(A + B, A, B) for A in range(2, 8) for B in range(A, 9) if B % A != 0]
 
# for each total that is not an exact power, add in B to the total
while len(ss) > 1:
  ss = list((t + B, A, B) for (t, A, B) in ss if not is_a_power(t))
  
# output candidate solutions
for (t, A, B) in ss:
  print(f"A={A} B={B}")

LikeLike

Jim Randell 8:10 am on 19 January 2021 Permalink | Reply
Tags: by: Andrew Skidmore ( 89 )
Teaser 2771: All Saints Day
From The Sunday Times, 1st November 2015 [link] [link]

I have written down three even numbers and then consistently replaced digits by letters with different letters used for different digits. In this way I get:

ALL
THE
SAINTS

In fact multiplying together the first two of these numbers gives the third.

What number is my SAINT?

[teaser2771]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
GeoffR and Jim Randell are discussing. Toggle Comments
- Jim Randell 8:11 am on 19 January 2021 Permalink | Reply
  We can solve this puzzle using the [[ SubstitutedExpression ]] solver from the enigma.py library.
  
  The following run file executes in
  
  Run: [ @repl.it ]
```
#! python -m enigma -rr

SubstitutedExpression

# all numbers are even
--invalid="1|3|5|7|9,LES"

"ALL * THE = SAINTS"

--answer="SAINT"
```
  Solution: SAINT = 69357.
  
  LikeLike
- GeoffR 10:40 am on 19 January 2021 Permalink | Reply
```
% A Solution in MiniZinc
include "globals.mzn";

var 0..9:A; var 0..9:L; var 0..9:T; var 0..9:H; 
var 0..9:E; var 0..9:S; var 0..9:I; var 0..9:N; 
  
constraint A != 0 /\ T != 0 /\ S != 0;
constraint all_different ([A,L,T,H,E,S,I,N]);

var 100..999: ALL = 100*A + 11*L;
var 100..999: THE = 100*T + 10*H + E;
var 100000..999999: SAINTS = 100001*S + 10000*A + 1000*I + 100*N + 10*T;
var 10000..99999: SAINT == 10000*S + 1000*A + 100*I + 10*N + T;

constraint ALL mod 2 == 0 /\ THE mod 2 == 0 /\ SAINTS mod 2 == 0;
constraint ALL * THE == SAINTS;

solve satisfy;

output ["SAINT = " ++ show(SAINT)
++"\nSum is " ++ show(ALL) ++ " x " ++ show(THE) ++ " = " ++ show(SAINTS)];

% SAINT = 69357
% ----------
% Sum is 988 x 702 = 693576
% ==========
```
  LikeLike

	Frits on Teaser 2455: [Mixing jugs…
	Alex.T.Sutherland on Teaser 3326: Interesting …
	Jim Randell on Teaser 2419: [Measuring j…
	Jim Randell on Teaser 3325: Olive and Do…
	Frits on Teaser 3326: Interesting …
	Ruud on Teaser 3326: Interesting …
	Jim Randell on Teaser 3326: Interesting …
	Jim Randell on Teaser 3326: Interesting …

Search

Recent Posts

Recent Comments

Archives

Categories

Subscribe

RSS Links

Site Stats

Meta

Recent Updates Page 47 Toggle Comment Threads | Keyboard Shortcuts

Jim Randell 8:42 am on 23 February 2021 Permalink | Reply Tags: by: Richard England ( 9 ), flawed ( 56 )

Rate this:

Share:

Jim Randell 8:44 am on 23 February 2021 Permalink | Reply

Frits 2:04 pm on 23 February 2021 Permalink | Reply

Reply Cancel reply

Jim Randell 8:53 am on 21 February 2021 Permalink | Reply Tags: by: F. Moore ( 2 )

Rate this:

Share:

Jim Randell 8:55 am on 21 February 2021 Permalink | Reply

Frits 11:53 am on 21 February 2021 Permalink | Reply

Jim Randell 12:49 pm on 21 February 2021 Permalink | Reply

Hugh Casement 1:51 pm on 21 February 2021 Permalink | Reply

Jim Randell 2:02 pm on 21 February 2021 Permalink | Reply

John Crabtree 6:58 pm on 22 February 2021 Permalink | Reply

Jim Randell 4:51 pm on 19 February 2021 Permalink | Reply Tags: by: Stephen Hogg ( 65 )

Rate this:

Share:

Jim Randell 5:29 pm on 19 February 2021 Permalink | Reply

Frits 9:10 pm on 19 February 2021 Permalink | Reply

Jim Randell 7:24 am on 20 February 2021 Permalink | Reply

Jim Randell 8:14 am on 28 February 2021 Permalink | Reply

Brian Gladman 10:44 pm on 19 February 2021 Permalink | Reply

Jim Randell 10:54 pm on 19 February 2021 Permalink | Reply

Brian Gladman 11:37 pm on 19 February 2021 Permalink | Reply

Jim Randell 7:17 am on 20 February 2021 Permalink | Reply

Brian Gladman 12:54 pm on 20 February 2021 Permalink | Reply

Jim Randell 1:45 pm on 20 February 2021 Permalink | Reply

Brian Gladman 5:09 pm on 20 February 2021 Permalink | Reply

Tony Brooke-Taylor 9:39 am on 21 February 2021 Permalink | Reply

Jim Randell 9:54 am on 21 February 2021 Permalink | Reply

Frits 12:58 am on 21 February 2021 Permalink | Reply

Tony Brooke-Taylor 9:43 am on 21 February 2021 Permalink | Reply

Jim Randell 9:48 am on 18 February 2021 Permalink | Reply Tags: by: Graham Smithers ( 87 )

Rate this:

Share:

Jim Randell 9:48 am on 18 February 2021 Permalink | Reply

Jim Randell 9:22 am on 16 February 2021 Permalink | Reply Tags: by: B W M Young ( 10 )

Rate this:

Share:

Jim Randell 9:23 am on 16 February 2021 Permalink | Reply

Frits 10:54 am on 19 February 2021 Permalink | Reply

Frits 11:15 am on 19 February 2021 Permalink | Reply

Jim Randell 11:39 am on 19 February 2021 Permalink | Reply

John Crabtree 4:37 pm on 19 February 2021 Permalink | Reply

Jim Randell 9:16 am on 14 February 2021 Permalink | Reply Tags: by: C. W. Mitford

Rate this:

Share:

Jim Randell 9:18 am on 14 February 2021 Permalink | Reply

Jim Randell 4:56 pm on 12 February 2021 Permalink | Reply Tags: by: Howard Williams ( 45 )

Rate this:

Share:

Jim Randell 5:10 pm on 12 February 2021 Permalink | Reply

Tony Brooke-Taylor 3:11 pm on 13 February 2021 Permalink | Reply

Jim Randell 12:07 pm on 17 February 2021 Permalink | Reply

Frits 10:31 am on 15 February 2021 Permalink | Reply

Jim Randell 12:40 pm on 15 February 2021 Permalink | Reply

Frits 11:23 am on 13 February 2021 Permalink | Reply

Frits 2:07 pm on 18 February 2021 Permalink | Reply

Jim Randell 9:01 am on 11 February 2021 Permalink | Reply Tags: by: Eric Emmet ( 10 )

Rate this:

Share:

Jim Randell 9:02 am on 11 February 2021 Permalink | Reply

Jim Randell 8:50 am on 9 February 2021 Permalink | Reply Tags: by: Angela Newing ( 40 )

Rate this:

Share:

Jim Randell 8:51 am on 9 February 2021 Permalink | Reply

Frits 9:26 pm on 9 February 2021 Permalink | Reply

Jim Randell 9:26 am on 7 February 2021 Permalink | Reply Tags: by: Ptolemaeus ( 5 )

Rate this:

Jim Randell 8:42 am on 23 February 2021 Permalink | Reply
Tags: by: Richard England ( 9 ), flawed ( 56 )

Jim Randell 8:53 am on 21 February 2021 Permalink | Reply
Tags: by: F. Moore ( 2 )

Jim Randell 4:51 pm on 19 February 2021 Permalink | Reply
Tags: by: Stephen Hogg ( 65 )

Jim Randell 9:48 am on 18 February 2021 Permalink | Reply
Tags: by: Graham Smithers ( 87 )

Jim Randell 9:22 am on 16 February 2021 Permalink | Reply
Tags: by: B W M Young ( 10 )

Jim Randell 9:16 am on 14 February 2021 Permalink | Reply
Tags: by: C. W. Mitford

Jim Randell 4:56 pm on 12 February 2021 Permalink | Reply
Tags: by: Howard Williams ( 45 )

Jim Randell 9:01 am on 11 February 2021 Permalink | Reply
Tags: by: Eric Emmet ( 10 )

Jim Randell 8:50 am on 9 February 2021 Permalink | Reply
Tags: by: Angela Newing ( 40 )

Jim Randell 9:26 am on 7 February 2021 Permalink | Reply
Tags: by: Ptolemaeus ( 5 )

Jim Randell 4:52 pm on 5 February 2021 Permalink | Reply
Tags: by: Danny Roth ( 88 )

Jim Randell 8:47 am on 4 February 2021 Permalink | Reply
Tags: by: D C Pusinelli

Jim Randell 8:33 am on 2 February 2021 Permalink | Reply
Tags: by: Ian Kay ( 5 )

Jim Randell 5:01 pm on 29 January 2021 Permalink | Reply
Tags: by: Stephen Hogg ( 65 )

Jim Randell 9:19 am on 28 January 2021 Permalink | Reply
Tags: by: N A Phillips ( 5 )

Jim Randell 8:16 am on 26 January 2021 Permalink | Reply
Tags: by: Victor Bryant ( 148 ), flawed ( 56 )

Jim Randell 10:07 am on 24 January 2021 Permalink | Reply
Tags: by: A. Bowie