Updates from June, 2024 Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 5:08 pm on 13 June 2024 Permalink | Reply
    Tags:   

    Teaser 2577: Number waves 

    From The Sunday Times, 12th February 2012 [link] [link]

    I challenged Sam to find a 9-digit number using all of the digits 1 to 9, such that each digit occupying an even position was equal to the sum of its adjacent digits. (For example, the digit occupying position four would be equal to the sum of the digits occupying positions three and five). Sam produced a solution that was exactly divisible by its first digit, by its last digit, and by 11.

    What was his number?

    [teaser2577]

     
    • Jim Randell's avatar

      Jim Randell 5:08 pm on 13 June 2024 Permalink | Reply

      Here is a solution using the [[ SubstitutedExpression ]] solver from the enigma.py library.

      It runs in 77ms. (Internal runtime of the generated program is 230µs).

      #! python3 -m enigma -rr

# suppose the number is: ABCDEFGHI
#                  pos = 123456789

SubstitutedExpression

--digits="1-9"

# even positions are the sum of the adjacent digits
"A + C = B"
"C + E = D"
"E + G = F"
"G + I = H"

# solution is divisible by A, I and 11
"ABCDEFGHI % A = 0"
"ABCDEFGHI % I = 0"
"ABCDEFGHI % 11 = 0"

--answer="ABCDEFGHI"

      Solution: Sam’s number was: 143968275.

      Like

      • Ruud's avatar

        Ruud 7:49 pm on 15 June 2024 Permalink | Reply

        No a priori knowledge, just brute force:

        from istr import istr

for i in istr.concat(istr.permutations(istr.digits("1-"), 9)):
    if (
        i[1] == i[0] + i[2]
        and i[3] == i[2] + i[4]
        and i[5] == i[4] + i[6]
        and i[7] == i[6] + i[8]
        and i.divisible_by(11)
        and i.divisible_by(i[0])
        and i.divisible_by(i[8])
    ):
        print(i)

        Note that this requires the latest-soon to be published- version of istr.

        Like

    • GeoffR's avatar

      GeoffR 6:56 pm on 13 June 2024 Permalink | Reply 

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

var 1..9:a; var 1..9:b; var 1..9:c;
var 1..9:d; var 1..9:e; var 1..9:f;
var 1..9:g; var 1..9:h; var 1..9:i;

constraint all_different([a,b,c,d,e,f,g,h,i]);

var 123456789..987654321:N == a*pow(10,8) + b*pow(10,7) + c*pow(10,6) 
+ d*pow(10,5) + e*pow(10,4) + f*pow(10,3) + g*pow(10,2) + h*pow(10,1) + i;
 
constraint N mod a == 0;
constraint N mod i == 0;
constraint N mod 11 == 0;

constraint a + c == b /\ c + e == d /\ e + g == f /\ g + i ==h;

solve satisfy;
 
output [ "His number was " ++ show(N)];

% His number was 143968275
% ----------
% ==========
% Finished in 461 msec - Chuffed Solver

      Like

    • Frits's avatar

      Frits 7:01 pm on 13 June 2024 Permalink | Reply 

           
#! python3 -m enigma -r
 
# suppose the number is: ABCDEFGHI
#                  pos = 123456789
 
SubstitutedExpression
 
--digits="1-9"

# divisibility of 11 rule, abs(sum odd digits - sum even digits) is 0 or a 
# multiple of 11, sum odd: A + C + E + G + I, sum even: A + 2.(C + G + E) + I
 
"(11 if C + E < 11 else 22) - (C + E) = G"
 
# even positions are the sum of the adjacent digits
"A + C = B"
"C + E = D"
"E + G = F"
"G + I = H"
 
# solution is divisible by A and I
"ABCDEFGHI % A = 0"
"ABCDEFGHI % I = 0"
 
--answer="ABCDEFGHI"

      Like

      • Frits's avatar

        Frits 9:23 pm on 13 June 2024 Permalink | Reply

        You only need to know three digits (like the 1st, 3rd and 5th digits).

        from functools import reduce

# convert digit sequences to number
d2n = lambda s: reduce(lambda x,  y: 10 * x + y, s)

dgts8 = set(range(1, 9))
dgts9 = dgts8 | {9}

for C in dgts8:
  for E in dgts8 - {C}:
    # 11 divisibility rule
    G = (11 if C + E < 11 else 22) - (C + E)
    D, F = C + E, E + G
    # different digits
    if len(r1 := dgts9 - {C, E, G, D, F}) != 4: continue
    for A in r1:
      B = A + C
      if len(r2 := sorted(r1 - {A, B})) != 2: continue
      H, I = r2[1], r2[0]
      if H != G + I: continue
      
      ABCDEFGHI = d2n([A, B, C, D, E, F, G, H, I])
      if ABCDEFGHI % A: continue
      if ABCDEFGHI % I: continue
      print("answer:", ABCDEFGHI)

        Like

    • Ruud's avatar

      Ruud 6:44 am on 16 June 2024 Permalink | Reply

      This version does not require the divisible_by method:

      from istr import istr

for i in istr.concat(istr.permutations(istr.digits("1-"), 9)):
    if i[1] == i[0] + i[2] and i[3] == i[2] + i[4] and i[5] == i[4] + i[6] and i[7] == i[6] + i[8] and i % 11 == 0 and i % i[0] == 0 and i % i[8] == 0:
        print(i)

      Like

  • Unknown's avatar

    Jim Randell 4:42 pm on 7 June 2024 Permalink | Reply
    Tags:   

    Teaser 3220: Graffiti 

    From The Sunday Times, 9th June 2024 [link] [link]

    Six pupils were in detention having been caught painting graffiti on the school wall. The teacher decided to show them some examples of abstract art and produced seven different pictures in order ABCDEFG for them to study for a few minutes. Teacher took them back, showed them again upside down and in random order, and asked them to write down which of ABCDEFG each one was.

    The answers were:

    Helen: A B C D E F G
Ian:   A B C F E D G
Jean:  A D F G C E B
Kevin: A D B F C E G
Lee:   A F C G E D B
Mike:  C A F B E D G

    It transpired that each picture had been correctly identified by at least one pupil, and everyone had a different number of correct answers.

    What was the correct order for the upside down ones?

    [teaser3220]

     
    • Jim Randell's avatar

      Jim Randell 4:54 pm on 7 June 2024 Permalink | Reply

      This Python program runs in 55ms. (Internal runtime is 786µs).

      from enigma import (cproduct, seq_all_different, join, printf)

# guesses
guesses = "ABCDEFG ABCFEDG ADFGCEB ADBFCEG AFCGEDB CAFBEDG".split()

# count number of correct answers
correct = lambda xs, ys: sum(x == y for (x, y) in zip(xs, ys))

# consider possible correct orderings (each is correctly placed by someone)
for order in cproduct(set(xs) for xs in zip(*guesses)):
  if not seq_all_different(order): continue
  # each pupil got a different number of correct answers
  if not seq_all_different(correct(order, guess) for guess in guesses): continue
  # output solution
  printf("order = {order}", order=join(order))

      Solution: The correct order was: C A F G E D B.

      So the number of correct identifications for each pupil were:

      H = 1 (E)
      I = 2 (D E)
      J = 3 (B F G)
      K = 0
      L = 4 (B D E G)
      M = 5 (A C D E F)

      There are factorial(7) = 5040 possible orders that the paintings could be presented in, but as we know that each must appear in the correct position for one of the pupils we only need to look for positions that have received a guess, and using the disjoint cartestian product of the possible positions brings the number of candidate orderings down to 15.

      Like

      • Jim Randell's avatar

        Jim Randell 10:21 am on 8 June 2024 Permalink | Reply

        I had a look at a more efficient way to generate the disjoint cartesian product of a sequence of sets (where no value can appear in more than one position).

        It is possible to implement this fairly directly using the [[ exact_cover() ]] function from the enigma.py library, but it was slightly faster to implement a specific algorithm.

        The following Python program has an internal runtime of 331µs.

        from enigma import (peek, seq_all_different, join, printf)

# guesses
guesses = "ABCDEFG ABCFEDG ADFGCEB ADBFCEG AFCGEDB CAFBEDG".split()

# count number of correct answers
correct = lambda xs, ys: sum(x == y for (x, y) in zip(xs, ys))

# disjoint cartestian product of a bunch of sets, any value may only appear in one position
def disjoint_cproduct(ss):
  ss = dict(enumerate(set(xs) for xs in ss))
  return _disjoint_cproduct(ss, [None] * len(ss))

# ss = remaining sets to process
# vs = selected values
def _disjoint_cproduct(ss, vs):
  # final slot?
  if len(ss) == 1:
    j = peek(ss.keys())
    for x in ss[j]:
      vs[j] = x
      yield tuple(vs)
  else:
    # choose a slot with the fewest options
    j = min(ss.keys(), key=(lambda j: len(ss[j])))
    for x in ss[j]:
      ss_ = dict((k, v.difference([x])) for (k, v) in ss.items() if k != j)
      vs[j] = x
      yield from _disjoint_cproduct(ss_, vs)

# consider possible correct orderings (each is correctly placed by someone)
for order in disjoint_cproduct(zip(*guesses)):
  # each pupil got a different number of correct answers
  if not seq_all_different(correct(order, guess) for guess in guesses): continue
  # output solution
  printf("order = {order}", order=join(order))

        Expect to see [[ disjoint_cproduct() ]] appearing in the next update to enigma.py. (Note: It is available from version 2024-06-07).

        Like

    • Frits's avatar

      Frits 6:41 pm on 7 June 2024 Permalink | Reply 

      guesses = "ABCDEFG ABCFEDG ADFGCEB ADBFCEG AFCGEDB CAFBEDG".split()
M, N = len(guesses), len(guesses[0])
 
# count number of correct answers
correct = lambda xs, ys: sum(x == y for (x, y) in zip(xs, ys))

# candidate correct pictures per slot
sols = sorted([(set(g[i] for g in guesses), i) for i in range(N)], 
               key=lambda x: len(x[0]))
# save the original order
order = [x[1] for x in sols]

# get a sequence of different pictures
def solve(ps, k, ss=[]):
  if k == 0:
    yield ss
  else:
    for n in ps[0][0]:
      if n in ss: continue
      yield from solve(ps[1:], k - 1, ss + [n])

# get a sequence of <N> different pictures     
for s in solve(sols, N):
  # put solution in the right order
  sol = ''.join(x for x, y in sorted(zip(s, order), key=lambda z: z[1]))
  # check for different numbers of correct answers
  if len(set(correct(sol, g) for g in guesses)) != M: continue
  print("answer", sol)

      Like

      • Frits's avatar

        Frits 1:36 pm on 8 June 2024 Permalink | Reply

        I assumed choosing slots with the fewest options was more efficient but without it the program is slightly faster. Jim’s disjoint_cproduct program is definitely faster compared to the version with “j = min(ss.keys())”.

        Like

        • Ruud's avatar

          Ruud 7:24 pm on 8 June 2024 Permalink | Reply

          It’s because the number of combinations of 4 out of 15 is the same as the number of combinations of 11 out of 15. Both are 1365.

          Like

    • Ruud's avatar

      Ruud 7:27 pm on 7 June 2024 Permalink | Reply

      Here’s my version:

      from itertools import permutations

guesses = ["A B C D E F G".split(), "A B C F E D G".split(), "A D F G C E B".split(), "A D B F C E G".split(), "A F C G E D B".split(), "C A F B E D G".split()]
for correct in permutations("A B C D E F G".split()):
    counts = set()
    for guess in guesses:
        count = sum(1 for c0, c1 in zip(correct, guess) if c0 == c1 and c0 != " ")
        counts.add(count)
    if len(counts) == 6:
        print(" ".join(correct))

      Like

    • Rob's avatar

      Rob 5:39 pm on 16 June 2024 Permalink | Reply

      Jim’s solution shows CAFGEBD provides Jean (ADFGCEB) with 3 correct matches (BFG). It seems there are only 2 correct matches (BF) in which case the solution does not meet the criterion of “everyone having a different number of correct answers”
      The correct solution is CAFGEDB

      Like

  • Unknown's avatar

    Jim Randell 5:20 pm on 6 June 2024 Permalink | Reply
    Tags:   

    Teaser 2573: Prime cricketers 

    From The Sunday Times, 15th January 2012 [link] [link]

    George and Martha support their local cricket team and keep records of all the results. At the end of last season, they calculated the total number of runs scored by each of the 11 players. George commented that the totals were all different three-digit palindromic primes. Martha added that the average of the 11 totals was also a palindromic prime.

    What were the two highest individual totals?

    [teaser2573]

     
    • Jim Randell's avatar

      Jim Randell 5:21 pm on 6 June 2024 Permalink | Reply

      Very straightforward constructive solution.

      This Python program runs in 57ms. (Internal runtime is 877µs).

      from enigma import (primes, is_npalindrome, subsets, div, printf)

# 3-digit palindromic primes
scores = list(n for n in primes.between(100, 999) if is_npalindrome(n))

# choose 11 different scores
for ss in subsets(scores, size=11):
  # calculate the mean
  avg = div(sum(ss), 11)
  # which is also in scores
  if avg and avg in scores:
    # output solution
    printf("{avg} -> {ss}")

      Solution: The two highest individual totals are 787 and 919.

      The full list of totals is:

      101, 131, 151, 181, 191, 313, 353, 373, 383, 787, 919
      mean = 353

      Like

    • Ruud's avatar

      Ruud 6:41 pm on 6 June 2024 Permalink | Reply

      Very similar to @Jim Randell’s solution, but without enigma:

      import sympy
from itertools import combinations

palindromic_primes_with_length_3 = []
for i in range(1, 1000):
    prime = sympy.prime(i)
    prime_as_str = str(prime)
    if len(prime_as_str) > 3:
        break
    if len(prime_as_str) == 3 and str(prime_as_str) == str(prime_as_str)[::-1]:
        palindromic_primes_with_length_3.append(prime)

solutions = set()
for scores in combinations(palindromic_primes_with_length_3, 11):
    average_score = sum(scores) / 11
    if average_score in palindromic_primes_with_length_3:
        solutions.add((scores, int(average_score)))
print(solutions)

      Like

      • Frits's avatar

        Frits 11:28 am on 7 June 2024 Permalink | Reply

        Sympy also has a primerange() method.

        Like

    • GeoffR's avatar

      GeoffR 8:16 pm on 6 June 2024 Permalink | Reply 

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

var 100..999:A; var 100..999:B; var 100..999:C; var 100..999:D;
var 100..999:E; var 100..999:F; var 100..999:G; var 100..999:H;
var 100..999:I; var 100..999:J; var 100..999:K; 

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

predicate is_prime(var int: x) = 
 x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) ((i < x) -> (x mod i > 0));
 
constraint A div 100 == A mod 10 /\ is_prime(A);
constraint B div 100 == B mod 10 /\ is_prime(B);
constraint C div 100 == C mod 10 /\ is_prime(C);
constraint D div 100 == D mod 10 /\ is_prime(D);
constraint E div 100 == E mod 10 /\ is_prime(E);
constraint F div 100 == F mod 10 /\ is_prime(F);
constraint G div 100 == G mod 10 /\ is_prime(G);
constraint H div 100 == H mod 10 /\ is_prime(H);
constraint I div 100 == I mod 10 /\ is_prime(I);
constraint J div 100 == J mod 10 /\ is_prime(J);
constraint K div 100 == K mod 10 /\ is_prime(K);

var 1000..9999:asum;
var 100..999:average;

constraint asum  == A+B+C+D+E+F+G+H+I+J+K;
constraint average == asum div 11 /\ asum mod 11 == 0;

constraint is_prime(average);

constraint card( {average} intersect {A,B,C,D,E,F,G,H,I,J,K}) == 1;

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

solve satisfy;

output["Scores are " ++ show([A,B,C,D,E,F,G,H,I,J,K])
++ "\n" ++ "Average = " ++ show(average) ];

% Scores are [101, 131, 151, 181, 191, 313, 353, 373, 383, 787, 919]
% Average = 353
% ----------
% ==========

      Like

      • GeoffR's avatar

        GeoffR 9:39 am on 7 June 2024 Permalink | Reply

        Shorter code, but still slow.

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

% Eleven cricket scores
var 100..999:A; var 100..999:B; var 100..999:C; var 100..999:D;
var 100..999:E; var 100..999:F; var 100..999:G; var 100..999:H;
var 100..999:I; var 100..999:J; var 100..999:K; 
 
constraint all_different([A,B,C,D,E,F,G,H,I,J,K]);

var 100..999:average;
 
predicate is_pr_pal(var int: x) = 
 x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) 
 ((i < x) -> (x mod i > 0)) /\ x div 100 == x mod 10;
 
constraint sum([is_pr_pal(A), is_pr_pal(B),is_pr_pal(C), is_pr_pal(D),
 is_pr_pal(E), is_pr_pal(F), is_pr_pal(G), is_pr_pal(H),
 is_pr_pal(I), is_pr_pal(J), is_pr_pal(K)]) == 11;
   
constraint average == (A+B+C+D+E+F+G+H+I+J+K) div 11
/\ (A+B+C+D+E+F+G+H+I+J+K) mod 11 == 0;
 
constraint is_pr_pal(average);
 
constraint card( {average} intersect {A,B,C,D,E,F,G,H,I,J,K}) == 1;
 
constraint increasing( [A,B,C,D,E,F,G,H,I,J,K]);
 
solve satisfy;
 
output["Scores are " ++ show([A,B,C,D,E,F,G,H,I,J,K])
++ "\n" ++ "Average = " ++ show(average) ];

        Like

    • GeoffR's avatar

      GeoffR 9:57 pm on 6 June 2024 Permalink | Reply 

      
from enigma import is_prime
from itertools import combinations

scores = [x for x in range(100,999) if is_prime(x) \
          if x // 100 == x % 10 ]

for s in combinations(scores, 11):
    av, r = divmod(sum(s), 11)
    if r != 0: continue
    if av in scores and av //100 == av % 10:
        print(f"Average = {av}")
        print(f"Scores = {s}")

      Like

      • Ruud's avatar

        Ruud 10:20 am on 7 June 2024 Permalink | Reply

        You can leave out the av // 100 == av % 10 test in the final if condition, as that’d guaranteed by the membership of scores.

        Like

    • Frits's avatar

      Frits 10:17 am on 7 June 2024 Permalink | Reply

      Same number of iteratons. It also works if scores would have had exactly 11 items.

      from itertools import combinations

# prime numbers from 101-999
P = [3, 5, 7]
P += [x for x in range(11, 100, 2) if all(x % p for p in P)]
P = [x for x in range(101, 1000, 2) if all(x % p for p in P)]
# 3-digit palindromic primes
scores = {p for p in P if p // 100 == p % 10}
assert (ln := len(scores)) >= 11

t = sum(scores)

# choose scores outside the 11
for ss in combinations(scores, ln - 11):
  # calculate the average
  avg, r = divmod(t - sum(ss), 11)
  # which is also in scores
  if r or avg not in scores: continue
  print("answer", sorted(scores.difference(ss))[-2:])

      Like

  • Unknown's avatar

    Jim Randell 4:48 pm on 2 June 2024 Permalink | Reply
    Tags:   

    Brain-Teaser 443: Space ship 

    From The Sunday Times, 2nd November 1969 [link]

    Says Bell at the pub:

    I’ve been reading about a space ship. They fly the thing round playing the usual Cops and Robbers stuff, but the way they name the crew is interesting. Using A, B, C and so on right up to I, no gaps, they make, once only, every possible pair of different letters; so there’s no AA, BB and so on, and they take no notice of the order in a pair; s0 BC is the same as CB.

    Four, including AD and BC, are on a list of officers and on that list no letter appears more than once. All the rest are just proles but do they have an A initial they call themselves A proles.

    All proles work in shifts with the same number on each shift — not just two shifts; more than that — and at the end of a shift every prole hands over to another whose initials are each one farther on in the alphabet than his own, so AB would hand over to BC. Of course I is followed by A.

    The shifts are picked so that when all shifts have been worked, every prole has been on duty once only.

    Now you tell me who’s on the first shift. I want the biggest possible list. Easier than it looks. Usual prize. One pint.

    Which A proles, if any, are on the first shift?

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

    [teaser443]

     
    • Jim Randell's avatar

      Jim Randell 4:48 pm on 2 June 2024 Permalink | Reply

      A manual solution follows from a bit of analysis:

      There are C(9, 2) = 36 names, and 4 officers, so there are 32 proles, which we must form into shifts, and we want the shifts to be as large as possible (and more than 2 of them).

      So we are looking at:

      4 shifts, each of 8 proles; or:
      8 shifts, each of 4 proles

      If we start with a name we can consider the successor names until we get back to where we started, which forms the names into 4 groups:

      AB → BC → CD → DE → EF → FG → GH → HI → AI (→ AB) [adjacent letters]
      AC → BD → CE → DF → EG → FH → GI → AH → BI (→ AC) [separated by 1 letter (or 6)]
      AD → BE → CF → DG → EH → FI → AG → BH → CI (→ AD) [separated by 2 letters (or 5)]
      AE → BF → CG → DH → EI → AF → BG → CH → DI (→ AE) [separated by 3 letters (or 4)]

      Any officer (in bold) must be preceded by a member of the final shift and working backwards gives us members of previous shifts, giving a chain that is 8 long, which consists of 1 member for each of 8 shifts, or 2 members for each of 4 shifts.

      Each officer must appear in a different group, and as we have used ABCD, we must choose 2 officers from EFGHI.

      In the final group only EI is available to be an officer, so the remaining officer must be FH in the second group.

      And so we can construct 4 shifts, each of 8 proles:

      shift 4: (AB, EG, CI, DH) + (FG, AC, EH, DI)
      shift 3: (AI, DF, BH, CG) + (EF, BI, DG, CH)
      shift 2: (HI, CE, AG, BF) + (DE, AH, CF, BG)
      shift 1: (GH, BD, FI, AE) + (CD, GI, BE, AF)

      (And the two halves could be split to make 8 shifts, each of 4 proles = (1b, 2b, 3b, 4b, 1a, 2a, 3a, 4a)).

      Solution: AE and AF are on the first shift.

      Here is a program that performs the same steps:

      It runs in 64ms. (Internal runtime is 351µs).

      from enigma import (
  irange, subsets, diff, tuples, repeat, join,
  intersect, disjoint_union, cache, printf
)

# letters
letters = "ABCDEFGHI"

# construct possible crew names
names = list(x + y for (x, y) in subsets(letters, size=2))

# constrict successor names
adj = dict(tuples(letters, 2, circular=1))
succ = cache(lambda xs: join((adj[x] for x in xs), sort=1))

# group names into successor chains
def group(names):
  while names:
    # make the chain for the next name
    g = list(repeat(succ, names[0], 8))
    yield g
    names = diff(names, g)

# collect groups
gs = list(group(names))

# choose an officer from each group
def officers(gs, offs=[]):
  # are we done?
  if not gs:
    yield offs
  else:
    g = gs[0]
    # AD and BC are officers
    xs = intersect([{'AD', 'BC'}, g])
    if not xs:
      # choose officers that don't include ABCD
      xs = list(x for x in g if not intersect(['ABCD', x]))
    # process the candidates
    for x in xs:
      offs_ = offs + [x]
      if disjoint_union(offs_):
        yield from officers(gs[1:], offs_)

# choose the officers
for offs in officers(gs):
  # find the first shift
  shift = set()
  for (g, off) in zip(gs, offs):
    j = g.index(off)
    shift.update(g[(j + i) % 9] for i in [-4, -8])
  shift = sorted(shift)
  # output shifts 1-4
  for k in irange(1, 4):
    printf("shift {k} = {shift}", shift=join(shift, sep=" "))
    if k == 4: break
    # hand on to the next shift
    shift = list(succ(x) for x in shift)

      Like

  • Unknown's avatar

    Jim Randell 4:36 pm on 31 May 2024 Permalink | Reply
    Tags:   

    Teaser 3219: Number funnel 

    From The Sunday Times, 2nd June 2024 [link] [link]

    Betty, being a keen mathematician, has devised a game to improve her children’s maths additions. She constructed an inverted triangular tiling of hexagonal shapes, with nine hexagons in the top row, eight in the second row etc., reducing to one at the bottom. Then, completing the top row with 0s and 1s, she asks them to complete each row below by adding in each hexagon shape the numbers in the two hexagons immediately above it.

    In the last game she noticed that if the top row is considered as a base-2 [binary] number, then this is exactly four and a half times the bottom total.

    What is the bottom total?

    [teaser3219]

     
    • Jim Randell's avatar

      Jim Randell 4:50 pm on 31 May 2024 Permalink | Reply

      If we suppose that the top row must have at least one of each binary digit present, then a single answer is found.

      This Python program runs in 64ms. (Internal runtime is 986µs).

      from enigma import (irange, tuples, repeat, nsplit, ediv, peek, printf)

# process a row
process = lambda ns: list(x + y for (x, y) in tuples(ns, 2))

# consider possible start row values (must be a multiple of 9)
for n in irange(0, 511, step=9):
  # this is 4.5 times the target
  t = ediv(n * 2, 9)
  # perform the process
  top = nsplit(n, 9, base=2)
  bot = peek(repeat(process, top, 8), 8)
  if bot == [t]:
    # output solution
    printf("{n} -> {t}; {top} -> {bot}")

      Solution: The final total is 102.

      The initial row is the binary representation of 4.5 × 102 = 459, which gives the following rows:

      (1, 1, 1, 0, 0, 1, 0, 1, 1)
      (2, 2, 1, 0, 1, 1, 1, 2)
      (4, 3, 1, 1, 2, 2, 3)
      (7, 4, 2, 3, 4, 5)
      (11, 6, 5, 7, 9)
      (17, 11, 12, 16)
      (28, 23, 28)
      (51, 51)
      (102)

      Like

      • Ruud's avatar

        Ruud 7:56 pm on 31 May 2024 Permalink | Reply

        This my version

        from istr import istr

for s9 in istr.concat(istr.product((0, 1), repeat=9)):
    as_binary = int(s9, 2)
    if as_binary % 4.5 == 0:
        target = int(as_binary / 4.5)
        s = s9[:]
        while len(s) > 1:
            s = [i + j for i, j in zip(s, s[1:])]
        if s[0] == target:
            print(f'from {s9} to {target}')

        Like

      • NigelR's avatar

        NigelR 11:11 am on 1 June 2024 Permalink | Reply

        No external dependencies and a recursive approach for the shapes. I started at the high end for the top row and worked down as it might have been faster if I’d stopped once a valid solution was found. As it is, it makes no difference but it confirms a unique solution.

        #return bottom row from top row r
def blox(r):
  #are we at the bottom row?
  if len(r)==1: return r
  #find the next row down
  else: return blox(nxt(r))

#return next row down from list of current row
nxt = lambda r: [(r[i]+r[i+1]) for i in range(0,len(r)-1)]

#top row must be less than 512 and divisible by 9
for top in range (504,0,-9):
  r1 = [int(y) for y in format(top,'09b')]
  #have we found a solution?
  if (bot:=blox(r1)[0])*9/2 == top:
      print(f"top row was {top}, bottom row was {bot}")

        Like

    • Jim Randell's avatar

      Jim Randell 4:51 pm on 1 June 2024 Permalink | Reply

      Here is a solution based on a bit of analysis:

      We have:

      9 × (final value) = 2 × (binary interpretation of top row)

      And we can write each of these in terms of the 0,1 values in the top row.

      So we can extract the coefficients of these top row values in the equation:

      (9 × (final value)) − (2 × (binary interpretation of top row)) = 0

      Some of them are positive, and some of them are negative. (And it turns out there are 2 negative values and 7 positive values).

      So we assign 0,1 values to the variables in the top row with negative coefficients (there are only 3 interesting cases), and then try to express the resulting value using the 0,1 quantities of the positive values.

      We can address this manually, or programatically.

      The following program has an internal runtime of 250µs, so it is slightly faster (although more complicated) than just applying the procedure to each of the possible top row values:

      from enigma import (irange, nCr, subsets, dot, express, nconcat, printf)

# we have: 9 * (final value) = 2 * (binary representation)

# calculate coefficients in the final value (= pascal_row(8))
pascal_row = lambda n: tuple(nCr(n, r) for r in irange(0, n))
pr8 = pascal_row(8)
lhs = tuple(9 * x for x in pr8)

# calculate coefficients in the binary representation
rhs = tuple(2**n for n in irange(9, 1, step=-1))

# calculate coefficients in <lhs> - <rhs> = 0
cs = tuple(a - b for (a, b) in zip(lhs, rhs))

# collect indices for positive and negative values
jps = sorted((j for (j, x) in enumerate(cs) if x > 0), key=cs.__getitem__)
jns = list(j for (j, x) in enumerate(cs) if x < 0)

# things we could work around, but don't need to
assert not (len(jns) > len(jps))
assert len(jps) + len(jns) == len(cs)
assert len(set(cs[j] for j in jps)) == len(jps)

# the positive and negative values
ps = list(cs[j] for j in jps)
ns = list(cs[j] for j in jns)

# choose 0,1 values for the negative values
for vs in subsets((0, 1), size=len(jns), select='M'):
  # calculate total for the negative values
  t = -dot(vs, ns)
  # express the same total using the positive values
  for qs in express(t, ps, qs=[0, 1]):
    # construct top row
    top = [None] * 9
    for (j, v) in zip(jns, vs): top[j] = v
    for (j, v) in zip(jps, qs): top[j] = v
    # output solution
    n = nconcat(top, base=2)
    bot = dot(top, pr8)
    printf("{top} {n} -> {bot}")

      Manually:

      We are looking to solve:

      −503a + −184b + 124c + 440d + 598e + 488f + 244g + 68h + 7i = 0

      The coefficients are all different, so we can uniquely identify a 0,1 valued variable with the corresponding coefficient.

      This boils down to choosing two subsets such that:

      sum(choose({503, 184})) = sum(choose({598, 488, 440, 244, 124, 68, 7}))

      There is a trivial solution where an empty set is chosen on both sides.

      Otherwise we have:

      LHS = 184 → not possible.
      LHS = 503 → not possible
      LHS = 184 + 503 = 687 → RHS = 488 + 124 + 68 + 7 = 687

      The final case corresponds to: a = 1, b = 1, c = 1, d = 0, e = 0, f = 1, g = 0, h = 1, i = 1.

      And so the top row is (1, 1, 1, 0, 0, 1, 0, 1, 1) and the bottom row is (102).

      Like

      • Frits's avatar

        Frits 5:42 pm on 2 June 2024 Permalink | Reply

        I needed to print the variables to see understand the method.
        I had forgotten that “dot” stands for “vector product”.

        Thanks for the “key=cs.__getitem__” construct. I didn’t know that.

        Like

        • Jim Randell's avatar

          Jim Randell 10:27 am on 3 June 2024 Permalink | Reply

          @Frits: dict has the get() function which makes the equivalent look neater for dictionaries:

          # sort keys by value
ks = sorted(d.keys(), key=d.get)

          Or I suppose you could use [[ key=(lambda i: seq[i]) ]] for sequences.

          Like

      • Frits's avatar

        Frits 11:19 pm on 2 June 2024 Permalink | Reply

        @Jim, is there a reason why express() doesn’t support negative quantities? The code would have been more compact.

        Like

        • Jim Randell's avatar

          Jim Randell 8:02 am on 3 June 2024 Permalink | Reply

          @Frits: Allowing negative quantities should be possible, but in general there is no guarantee of termination if non-positive denominations are used in [[ express() ]].

          It feels like solving an integer equation where the variables take on (0, 1) values could have a specialised solver (I think an ILP solver would work). But I used [[ express() ]] in this instance to save having to write one.

          Like

        • Frits's avatar

          Frits 12:38 pm on 3 June 2024 Permalink | Reply

          A minimal modification to Enigma’s express_quantities() is sufficient to make this program work (assuming the denominations are ordered). I don’t see how this subroutine can keep running without terminating.

          from enigma import (irange, nCr, dot, nconcat, printf)

# express total <t> using denominations <ds>, quantities chosen from <qs>
def express_quantities(t, ds, qs, ss=[]):
  if any(x for x in ss) and t == 0:
    if not ds:
      yield ss
    elif 0 in qs:
      yield ss + [0] * len(ds)
  elif ds:
    d = ds[0]
    for q in qs:
      if d * q > t: break
      for r in express_quantities(t - d * q, ds[1:], qs, ss + [q]): yield r
 
# we have: 9 * (final value) = 2 * (binary representation)
 
# calculate coefficients in the final value (= pascal_row(8))
pascal_row = lambda n: tuple(nCr(n, r) for r in irange(0, n))
pr8 = pascal_row(8)
lhs = tuple(9 * x for x in pr8)
 
# calculate coefficients in the binary representation
rhs = tuple(2**n for n in irange(9, 1, step=-1))
 
# calculate coefficients in <lhs> - <rhs> = 0
cs = tuple(a - b for (a, b) in zip(lhs, rhs))

# express the same total using the positive values
for top in express_quantities(0, cs, qs=[0, 1]):
  # construct top row
  # output solution
  n = nconcat(top, base=2)
  bot = dot(top, pr8)
  
  printf("{top} {n} -> {bot}")

          Like

          • Jim Randell's avatar

            Jim Randell 11:20 am on 4 June 2024 Permalink | Reply

            @Frits: But you asked about express() not express_quantities().

            Think about expressing a value using denominations of (-1, 0, +1) where you can use as many of each as you like.

            Of course with finite sets of denominations and quantities there is only a finite number of possible arrangements.

            Like

      • Jim Randell's avatar

        Jim Randell 3:27 pm on 4 June 2024 Permalink | Reply

        Or, using a single call to express():

        from enigma import (irange, nCr, express, nconcat, dot, printf)

# solve the binary equation: sum(n[i] * x[i]) = 0, for x[i] in [0, 1]
# return the sequences of binary x[] values
def solve(ns):
  # collect the coefficients (all different absolute values)
  m = dict()  # value -> index
  ts = set()  # set of negative values
  for (i, n) in enumerate(ns):
    assert n != 0  # coefficients must be non-zero
    k = abs(n)
    if n < 0: ts.add(k)
    m[k] = i
  ds = sorted(m.keys())
  assert len(ds) == len(ns)  # coefficients must all be different
  # express the sum of the negative values using 0,1 quantities
  for qs in express(sum(ts), ds, qs=[0, 1]):
    # return the values in the required order
    xs = [None] * len(ns)
    for (d, q) in zip(ds, qs):
      xs[m[d]] = (1 - q if d in ts else q)
    yield xs

# calculate coefficients for the final value (= pascal_row(8))
pascal_row = lambda n: tuple(nCr(n, r) for r in irange(0, n))
pr8 = pascal_row(8)
lhs = tuple(9 * x for x in pr8)

# calculate coefficients in the binary representation
rhs = tuple(2**n for n in irange(9, 1, step=-1))

# calculate coefficients in <lhs> - <rhs> = 0
ns = tuple(a - b for (a, b) in zip(lhs, rhs))

# solve the 0,1-equation with coefficients <ns> to give the top row
for top in solve(ns):
  # output solution
  n = nconcat(top, base=2)
  bot = dot(pr8, top)
  printf("{top} {n} -> {bot}")

        Like

    • Hugo's avatar

      Hugo 2:12 pm on 9 June 2024 Permalink | Reply

      If the numbers in the top row are a, b, c, d, e, f, g, h, i,
      then the value at the bottom has coefficients as given by the appropriate row of Pascal’s triangle: a + 8b + 28c + 56d + 70e + 56f + 28g + 8h + i.
      An exhaustive search is still needed, but my program (in Basic) found a solution immediately.

      This puzzle opens up the possibility of a whole family of puzzles, with factors other than 4.5. There could also be a different number of digits in the top row.

      Where do Jim’s negative values come from? The top row contains only 0s and 1s; each subsequent row is formed by addition, never subtraction.

      A further puzzle for me is Frits’ mention of dot for a vector product.
      I don’t speak Python, but normally dot is for a scalar product and cross for a vector product.

      Like

    • Hugo's avatar

      Hugo 8:48 am on 10 June 2024 Permalink | Reply

      I see now what Jim was doing: equating nine times the value of the bottom number and twice the value of the binary number, 256a + 128b + 64c + 32d + 16e + 8f + 4g + 2h + i.
      The mental leap was too much for me! I had evaluated them separately.

      Like

    • GeoffR's avatar

      GeoffR 3:16 pm on 12 June 2024 Permalink | Reply 

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

var 0..1:a; var 0..1:b; var 0..1:c;
var 0..1:d; var 0..1:e; var 0..1:f;
var 0..1:g; var 0..1:h; var 0..1:i;

var 1..512:top;
var 1..512:btm;

% top is abcdefghi in binary
constraint top == a*pow(2,8) + b*pow(2,7) + c*pow(2,6)
+ d*pow(2,5) + e*pow(2,4) + f*pow(2,3) + g*pow(2,2) + h*2 + i;

% 9th row Pascal Triangle coefficients
constraint btm == a + 8*b + 28*c + 56*d + 70*e + 56*f + 28*g + 8*h + i;

constraint 9 * btm == 2 * top;

solve satisfy;

output[ "Top row = " ++ show(top) ++
"\n" ++ "Bottom row = " ++ show(btm)];

% Top row = 459
% Bottom row = 102
% ----------
% ==========

      Like

    • GeoffR's avatar

      GeoffR 4:15 pm on 14 June 2024 Permalink | Reply

      I tried this teaser with ChatGPT trying to find a solution. Despite several hints, it failed, as we have experienced previously.

      I have been experimenting using AI to write poetry in recent months, so I tried a poem for this teaser by feeding the teaser description as a prompt for the poem for ChatGPT. to generate a poem.

      It worked well – poem below:

      The Hexagon Puzzle – ST 3219
      =====================
      A Poem by ChatGPT

      In Betty’s realm, where numbers dance,
      A game of wit and math’s advance,
      Hexagons align in rows so neat,
      A challenge for young minds to meet.

      From nine at the top, they descend,
      Each row a puzzle to comprehend,
      Zeros and ones adorn the crest,
      A binary code, a numeric test.

      With eager eyes, her children trace,
      The patterns woven in this maze,
      Adding the pairs above with care,
      Unveiling sums, a secret to share.

      And as they reach the final row,
      A revelation starts to glow,
      The top row’s binary, a key so bright,
      Unlocks the bottom’s total, a wondrous sight.

      Four and a half times, the answer lies,
      A mathematical truth that never dies,
      In Betty’s game, where numbers reign,
      Hexagons persist, and minds retain.

      Like

  • Unknown's avatar

    Jim Randell 11:05 am on 30 May 2024 Permalink | Reply
    Tags:   

    Brainteaser 1318: May I repeat? 

    From The Sunday Times, 6th December 1987 [link]

    In this letters-for-digits puzzle, as usual, different letters consistently replace different digits. I have thought of a two-digit number and worked out a fraction (in its lowest form) involving my number. The recurring decimal which I get consists of infinite repeats, i.e.:

    ? / MY = 0. REPEAT REPEAT …

    What is the value of PART?

    [teaser1318]

     
    • Jim Randell's avatar

      Jim Randell 11:06 am on 30 May 2024 Permalink | Reply

      This solution uses the [[ farey() ]] function from the enigma.py library, which generates co-prime pairs (i.e. the numerator and denominator of a fraction in its lowest terms), and then uses the [[ recurring() ]] function to determine the representation of the fraction as a recurring decimal.

      It runs in 131ms. (Internal runtime is 55ms).

      from enigma import (farey as coprime_pairs, recurring, format_recurring as fmt, printf)

# consider fractions a/b
for (a, b) in coprime_pairs(98):
  # b is 2 different digits
  if b < 10 or b % 11 == 0: continue
  # check repetend
  (i, nr, rr) = recurring(a, b)
  if nr or len(rr) != 6 or rr[1] != rr[3]: continue
  rs = set(rr)
  if len(rs) != 5 or rs.intersection(str(b)): continue
  # output solution
  PART = rr[2] + rr[4] + rr[0] + rr[5]
  printf("PART = {PART} [{a}/{b} = {f}]", f=fmt((i, nr, rr)))

      Solution: PART = 8015.

      The required fraction is:

      5/39 = 0.(128205)…

      Like

      • Jim Randell's avatar

        Jim Randell 8:56 pm on 30 May 2024 Permalink | Reply

        Here’s my solution based on the observation:

        (MY / k) × REPEAT = 999999

        (Although I don’t assume k is a single digit number).

        It runs in 66ms. (Internal runtime is 502µs).

        from enigma import (irange, divisor_pairs, gcd, nsplit, join, printf)

# (MY / k) * REPEAT = 999999

# MY is a 2-digit divisor of 999999
for (MY, r) in divisor_pairs(999999):
  if MY < 10 or MY % 11 == 0: continue
  if MY > 99: break
  # REPEAT is some multiple of r
  for k in irange(1, MY - 1):
    if gcd(k, MY) > 1: continue
    REPEAT = k * r
    ds = nsplit(REPEAT, 6)
    if ds[1] != ds[3]: continue
    ss = set(ds)
    if len(ss) != 5 or ss.intersection(nsplit(MY)): continue
    # output solution
    PART = join(ds[i] for i in (2, 4, 0, 5))
    printf("PART = {PART} [{k}/{MY} = 0.({REPEAT:06d})...]")

        Like

        • Frits's avatar

          Frits 11:27 am on 31 May 2024 Permalink | Reply

          Nice. Indeed, MY must be a divisor of 999999.

          Like

    • GeoffR's avatar

      GeoffR 2:09 pm on 30 May 2024 Permalink | Reply 

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

var 1..9:R; var 0..9:E; var 0..9:P; var 0..9:A;
var 0..9:T; var 1..9:X; var 1..9:M; var 0..9:Y;

constraint all_different([R,E,P,A,T,M,Y]);

var 10..99:MY == 10*M + Y;
var 100000..999999:REPEAT == 100000*R + 10100*E + 1000*P + 10*A + T;
var 1000..9999:PART == 1000*P + 100*A + 10*R + T;

% function ex Hakan Kjellerstrand 
function var int: gcd(var int: x, var int: y) =
  let {
    int: p = min(ub(x),ub(y));
    var 1..p: g;
    constraint
       exists(i in 1..p) (
          x mod i = 0 /\ y mod i = 0
          /\
          forall(j in i+1..p) (
             not(x mod j = 0 /\ y mod j = 0)
          ) /\ g = i);
  } in g;
  
constraint gcd(X, MY) == 1;

% As X/MY = 0.REPEATREPEAT..
% Multiplying both sides by 1,000,000 gives..
constraint 999999 * X == MY * REPEAT;

solve satisfy;

output ["PART = " ++ show(PART) ++ "\n"
++ "REPEAT = " ++ show(REPEAT) ++ "\n"
++ "X, MY =" ++ show([X, MY])];

% PART = 8015
% REPEAT = 128205
% X, MY =[5, 39]
% ----------
% ==========

      Like

    • Frits's avatar

      Frits 6:41 pm on 30 May 2024 Permalink | Reply

      Following GeoffR’s method.

       
from enigma import divisor_pairs

# 999999 * X == MY * REPEAT 
for X in range(1, 10):
  LHS = 999999 * X
 
  #  fraction X / MY is in its lowest form
  for MY, REPEAT in [(str(x), str(y)) for x, y in divisor_pairs(LHS)
                     if 9 < x < 100 and (x % X or X == 1)]:
    # letter E                 
    if REPEAT[1] != REPEAT[3]: continue
    # different letters
    if len(set(MY + REPEAT)) != 7: continue
   
    print(f"answer: {REPEAT[2]}{REPEAT[4]}{REPEAT[0]}{REPEAT[5]}")

      Like

      • Frits's avatar

        Frits 11:15 am on 31 May 2024 Permalink | Reply

        I did assume a 1-digit question mark. Line 9 should have been:
        if 9 < x < 100 and gcd(x, X) == 1]:

        Like

    • Ruud's avatar

      Ruud 6:33 am on 31 May 2024 Permalink | Reply

      Brute force with istr:

      from istr import istr

for r, e, p, a, t, m, y in istr.permutations(istr.digits(), 7):
    if (m | y) * (r | e | p | e | a | t) % 999999 == 0:
        print(f"{m|y} / {r|e|p|e|a|t}")

      Like

      • Ruud's avatar

        Ruud 6:50 am on 31 May 2024 Permalink | Reply

        Improved prints:

        from istr import istr

for r, e, p, a, t, m, y in istr.permutations(istr.digits(), 7):
    if (m | y) * (r | e | p | e | a | t) % 999999 == 0:
        print(f"{(m | y) * (r | e | p | e | a | t) // 999999} / {m | y} =  0.{r | e | p | e | a | t}...")
        print(f"part = {p | a | r | t}")

        Like

      • Jim Randell's avatar

        Jim Randell 8:40 am on 31 May 2024 Permalink | Reply

        @Ruud: How does this program ensure the fraction (?/MY) is in lowest terms?

        Liked by 1 person

        • Ruud van der Ham's avatar

          Ruud van der Ham 10:26 am on 31 May 2024 Permalink | Reply

          Ok, no guarantee.
          Better would be to do

          
for m, y, r, e, p, a, tin istr.permutations(istr.digits(), 7):
    if (m | y) * (r | e | p | e | a | t) % 999999 == 0:
        print(f"{(m | y) * (r | e | p | e | a | t) // 999999} / {m | y} =  0.{r | e | p | e | a | t}...")
        print(f"part = {p | a | r | t}")
        break

          Although my original code also just result in one solution.
          Alth

          Like

  • Unknown's avatar

    Jim Randell 11:11 am on 28 May 2024 Permalink | Reply
    Tags:   

    Brainteaser 1351: Letters find the largest 

    From The Sunday Times, 24th July 1988 [link]

    Each letter stands for one of the two digits 1 and 2.

    TEN is larger than SIX, which is larger than TWO, which is larger than ONE.

    NINE is larger than FIVE, which is larger than FOUR, which is larger than ZERO.

    EIGHT is larger than SEVEN, which is larger than THREE.

    Which is the larger in each of the following pairs?

    (a) ELEVEN and NINETY;
    (b) TWENTY and EIGHTY;
    (c) FIFTY and SIXTY;
    (d) SEVENTY and HUNDRED;
    (e) EIGHTY and NINETY?

    [teaser1351]

     
    • Jim Randell's avatar

      Jim Randell 11:11 am on 28 May 2024 Permalink | Reply

      Here is a solution using the [[ SubstitutedExpression ]] solver from the enigma.py library.

      It runs in 80ms. (Internal runtime of the generated program is 122µs).

      #! python3 -m enigma -rr

SubstitutedExpression

--digits="1,2"
--distinct=""

"TEN > SIX"
"SIX > TWO"
"TWO > ONE"

"NINE > FIVE"
"FIVE > FOUR"
"FOUR > ZERO"

"EIGHT > SEVEN"
"SEVEN > THREE"

--answer="(ELEVEN < NINETY, TWENTY < EIGHTY, FIFTY < SIXTY, SEVENTY < HUNDRED, EIGHTY < NINETY)"
--template=""

      Solution: We have:

      NINETY > ELEVEN
      EIGHTY > TWENTY
      FIFTY > SIXTY
      SEVENTY > HUNDRED
      NINETY > EIGHTY

      The following letters have fixed values:

      E=2, F=2, G=2, H=1, I=2, N=2, O=1, S=2, T=2, V=1, W=1, X=1, Z=1

      And the letters D, L, R, U, Y can take on either value, and give rise to the 32 possible assignments.

      So:

      NINETY = 22222? > 2?2122 = ELEVEN
      EIGHTY = 22212? > 21222? = TWENTY
      FIFTY = 2222? > 2212? = SIXTY
      SEVENTY = 221222? > 1?2??2? = HUNDRED
      NINETY = 22222? > 22212? = EIGHTY

      Like

    • Ruud's avatar

      Ruud 3:51 pm on 28 May 2024 Permalink | Reply

      Brute force solution:

      from collections import defaultdict
from istr import istr

answers = defaultdict(set)
for t, e, n, s, i, x, w, o, f, v, r, z, g, h, u, l, y, d in istr.product((1, 2), repeat=18):
    if t | e | n > s | i | x > t | w | o > o | n | e:
        if n | i | n | e > f | i | v | e > f | o | u | r > z | e | r | o:
            if e | i | g | h | t > s | e | v | e | n > t | h | r | e | e:
                answers["a"].add(("ninety", "eleven")[e | l | e | v | e | n > n | i | n | e | t | y])
                answers["b"].add(("eighty", "twenty")[t | w | e | n | t | y > e | i | g | h | t | y])
                answers["c"].add(("sixty", "fifty")[f | i | f | t | y > s | i | x | t | y])
                answers["d"].add(("hundred", "seventy")[s | e | v | e | n | t | y > h | u | n | d | r | e | d])
                answers["e"].add(("ninety", "eighty")[e | i | g | h | t | y > n | i | n | e | t | y])

for letter, answer in answers.items():
    print(f"{letter}) {answer}")

      Like

      • Jim Randell's avatar

        Jim Randell 4:49 pm on 28 May 2024 Permalink | Reply

        I get:

        TypeError: tuple indices must be integers or slices, not istr

        Like

        • Ruud's avatar

          Ruud 5:05 pm on 28 May 2024 Permalink | Reply

          @Jim Randell
          Sorry, I forgot to tell that you need istr 1.0.7 to run this code.

          Like

    • Ruud's avatar

      Ruud 8:19 am on 29 May 2024 Permalink | Reply

      As some ‘Spielerei’, I did refactor my original istr-version.
      It uses n2w module to convert ints to ‘spoken’ strings. With that and a helper function, I can formulate all the comparison statements as ints, which make more compact code.

      A bit (?) overengineered, maybe …

      from collections import defaultdict
from istr import istr
import n2w  # this module can convert an integer to a 'spoken' string
from functools import reduce, lru_cache


@lru_cache
def convert(number):
    """just as n2w.convert, but 100 is treated differenr]t as n2w.convert(100) is 'one hundred'"""
    return "hundred" if number == 100 else n2w.convert(number)


def a(number):
    """translates an int into an istr, using the global variables that define the letter value"""
    return reduce(lambda x, y: x | globals()[y], convert(number), istr(""))


def largest(number0, number1):
    return (convert(number1), convert(number0))[a(number0) > a(number1)]


answers = defaultdict(set)
for t, e, n, s, i, x, w, o, f, v, r, z, g, h, u, l, y, d in istr.product((1, 2), repeat=18):
    if a(10) > a(6) > a(2) > a(1):
        if a(9) > a(5) > a(4) > a(0):
            if a(8) > a(7) > a(3):
                answers["a"].add(largest(11, 90))
                answers["b"].add(largest(80, 20))
                answers["c"].add(largest(60, 50))
                answers["d"].add(largest(100, 70))
                answers["e"].add(largest(90, 80))

for letter, answer in answers.items():
    print(f"{letter}) {answer}")

      Like

    • Jim Randell's avatar

      Jim Randell 10:09 am on 29 May 2024 Permalink | Reply

      All comparisons are between values of the same length, so we don’t need to convert the values into numbers, we can just use lexicographic ordering.

      This Python program uses integer keys to refer to the words, but considers the values of the words with all 2^18 possible assignments of symbols, so is much slower than my solution using the [[ SubstitutedExpression ]] solver.

      from enigma import (union, subsets, join, printf)

# words we are interested in (use numbers as short keys)
words = {
  10: 'TEN', 6: 'SIX', 2: 'TWO', 1: 'ONE',
  9: 'NINE', 5: 'FIVE', 4: 'FOUR', 0: 'ZERO',
  8: 'EIGHT', 7: 'SEVEN', 3: 'THREE', 50: 'FIFTY', 60: 'SIXTY',
  11: 'ELEVEN', 90: 'NINETY', 20: 'TWENTY', 80: 'EIGHTY',
  70: 'SEVENTY', 100: 'HUNDRED',
}

# answers we need to find (which is larger?)
qs = [(11, 90), (20, 80), (50, 60), (70, 100), (80, 90)]

# collect symbols used
syms = sorted(union(words.values()))

# collect answers
ans = set()
# assign the symbols to values
for vs in subsets('12', size=len(syms), select='M'):
  m = dict(zip(syms, vs))
  # map the words to values
  w = dict((k, join(m[x] for x in v)) for (k, v) in words.items())
  # check the conditions
  if (w[10] > w[6] > w[2] > w[1] and w[9] > w[5] > w[4] > w[0] and w[8] > w[7] > w[3]):
    # accumulate answers
    ans.add(tuple(max(a, b, key=w.get) for (a, b) in qs))

# output solution
for ks in ans:
  for (q, k) in zip("abcde", ks):
    printf("({q}) {k}", k=words[k])
  printf()

      Like

  • Unknown's avatar

    Jim Randell 4:31 pm on 24 May 2024 Permalink | Reply
    Tags:   

    Teaser 3218: Algorithm Al 

    From The Sunday Times, 26th May 2024 [link] [link]

    On his 35th birthday, maths teacher Al’s three younger half-sisters bought him “The Book of Numbers for Nerds” as a tease. It showed how to find right-angle triangles with whole-number sides using any two unequal odd square numbers. You take half their sum; half their difference; and the square root of their product to get the three sides. Any multiple of such a triplet would also work. He told his sisters this and that their ages were the sides of such a triangle. “Algorithm Al!” they yelled.

    Knowing the age of any one sister would not allow you to work out the other ages with certainty, but in one case you could be sure of her place chronologically (youngest, middle or oldest).

    Give the three sisters’ ages (youngest to oldest).

    [teaser3218]

     
    • Jim Randell's avatar

      Jim Randell 5:33 pm on 24 May 2024 Permalink | Reply

      (See also: Teaser 3017).

      The construction of primitive Pythagorean triples in this way is known as Euclid’s formula [@wikipedia].

      This program collects Pythagorean triples with sides less than 35, and looks for triangles where all sides appear in more than one candidate triangle.

      Of the selected triangles we look for a side that can only appear in one specific position in the ordering (again, considering all candidate triangles). And this identifies the required answer.

      It runs in 63ms. (Internal runtime is 193µs).

      from enigma import (
  defaultdict, pythagorean_triples, multiset, singleton, icount, printf
)

# collect possible triangles
tris = list(pythagorean_triples(34))

# record positions of each side
d = defaultdict(multiset)
for tri in tris:
  for (i, x) in enumerate(tri):
    d[x].add(i)

# check a candidate triangle
def check_tri(tri):
  # each side must appear in multiple triangles
  if not all(d[x].size() > 1 for x in tri): return
  printf("tri = {tri}; all sides occur in multiple triangles")
  # look for sides that can only appear in a single position
  for x in tri:
    k = singleton(d[x].distinct_elements())
    if k is not None:
      printf("-> {x} only appears in pos {k}")
      yield (x, k)

# check triangles, exactly one side appears in a single position
for tri in tris:
  if icount(check_tri(tri)) == 1:
    printf("=> SOLUTION: ages = {tri}")

      Solution: The three ages are: 15, 20, 25.

      There are just five primitive triangles we are interested in:

      euclid(1, 3) = (3, 4, 5)
      euclid(1, 5) = (5, 12, 13)
      euclid(1, 7) = (7, 24, 25)
      euclid(3, 5) = (8, 15, 17)
      euclid(3, 7) = (20, 21, 29)

      Candidate triangles are formed from these, along with multiples such that the largest side does not exceed 34.

      And the only candidate triangles where every side length occurs in another triangle are:

      (12, 16, 20) = (3, 4, 5) × 4
      (15, 20, 25) = (3, 4, 5) × 5

      And of these sides only 25 always appears as the largest side length:

      (7, 24, 25)
      (15, 20, 25)

      Like

    • Frits's avatar

      Frits 5:55 pm on 24 May 2024 Permalink | Reply

      Following the instructions.

       
sols = set()
# odd squares
osqs = [i * i for i in range(1, 68, 2)]
for i, a in enumerate(osqs):
  if a > 33: break
  for b in osqs[i + 1:]:
    # calculate sister's ages
    p = (a + b) // 2
    if p > 34: break
    q = abs(a - b) // 2
    r = int((a * b) ** .5)
    # allow for multiples
    for k in range(1, 35):
      if any(x > 34 for x in [k * p, k * q, k * r]): break
      sols.add(tuple(sorted([k * p, k * q, k * r])))

sides = set(y for x in sols for y in x)
# dictionary of age appearing as y/m/o
d = {s: [sol.index(s) for sol in sols if s in sol] for s in sides}

# group of sisters that qualify
gs = [sol for sol in sols if all(len(d[s]) > 1 for s in sol)]
for sisters in gs:
  if sum([len(set(d[s])) == 1 for s in sisters]) == 1:  # in one case ...
    print("answer:", sisters)

      Like

  • Unknown's avatar

    Jim Randell 8:59 am on 21 May 2024 Permalink | Reply
    Tags:   

    Brain-Teaser 350: Catering crisis 

    From The Sunday Times, 21st January 1968 [link]

    The caterer at our Village Hall is in a quandary, as the Hall has been double-booked for next Saturday — by the Cricket Club and the Darts Club.

    Unfortunately the matter cannot be resolved until the return of the Vicar on Saturday morning. He is quite unpredictable in such decisions, and the caterer must order the food by Friday.

    The Cricketers want 100 sausage rolls and 60 meat pies; the Darts Club wants 50 sausage rolls and 90 meat pies.

    The caterer is empowered to spend exactly £6.00. He buys sausage rolls at 3p and sells at 4p; meat pies cost him 5p and sell at 8p. Any left-overs are disposed of at a loss to a local prep school, which pays 2p per sausage roll and 3p a pie.

    What should the caterer order so that he makes the best safe profit no matter which club gets the booking? And what will that profit be?

    This puzzle is included in the book Sunday Times Brain Teasers (1974). The puzzle text is taken from the book.

    [teaser350]

     
    • Jim Randell's avatar

      Jim Randell 8:59 am on 21 May 2024 Permalink | Reply

      This Python program looks at possible orders of sausage rolls and pies that cost the caterer exactly 600p, and then the amount made if these supplies are available for each club, and records the minimum profit made in each case. We then look for the largest of these profits to find the answer to the puzzle.

      It runs in 58ms. (Internal runtime is 240µs).

      from enigma import (Accumulator, express, printf)

# amount earned for supply <s>, demand <d>, price <p>, disposal price <x>
def amount(s, d, p, x):
  return (d * p + (s - d) * x if s > d else s * p)

# calculate amount earned for a supply (s, p) and a demand (S, P)
# of sausage rolls and pies
def earned(s, p, S, P):
  return amount(s, S, 4, 2) + amount(p, P, 8, 3)

# find the maximum profit
r = Accumulator(fn=max, collect=1)

# the caterer spends 600p
for (s, p) in express(600, [3, 5]):
  # calculate amount earned from each club
  C = earned(s, p, 100, 60)
  D = earned(s, p, 50, 90)
  # record profit
  r.accumulate_data(min(C, D), (s, p, C - 600, D - 600))

# output solution
for (s, p, C, D) in r.data:
  printf("{s} sausages rolls + {p} pies -> cricket = {C} / darts = {D}")

      Solution: The caterer should order 80 sausage rolls and 72 pies. Whichever club arrives he will make a profit of 236p.

      In the originally published puzzle pre-decimal currency was used and the numbers were different:

      The Cricketers want 200 sausage rolls and 120 meat pies; the Darts Club wants 100 sausage rolls and 180 meat pies.

      The caterer is empowered to spend exactly £5 [= 1200 pence].

      And the answer is: 160 sausage rolls, 144 pies. The profit is 472 pence = £1, 19s, 4d.

      Like

      • Frits's avatar

        Frits 10:35 am on 21 May 2024 Permalink | Reply

        This program doesn’t assume that the caterer will spend exactly 600p.

           
from enigma import SubstitutedExpression, Accumulator

# invalid digit / symbol assignments
d2i = dict()
# try to spend close to 600p in order to maximize the profit
for dgt in range(0, 101):
  vs = set()
  if dgt < 50: vs.update('S')
  if dgt < 60: vs.update('P')
  if dgt > 90: vs.update('P')
  d2i[dgt] = vs

# the alphametic puzzle
p = SubstitutedExpression(
  [
    # expenditure close to the maximum
    "595 < S * 3 + P * 5 <= 600",
    # calculate profits for cricketers and darters
    "(pc := S + min(P, 60) * 3 - (P - 60) * 2 * (P > 60))",
    "(pd := min(S, 50) + P * 3 - (S - 50) * 1 * (S > 50))",
  ],
  answer="min(pc, pd), S, P",
  base=101,
  d2i=d2i,
  distinct="",
  reorder=0,
  verbose=0,    # use 256 to see the generated code
)

# find the maximum profit
r = Accumulator(fn=max).accumulate_from(ans for (_, ans) in p.solve())

# output solution
w, s, p = r.value
print(f"he should order {s} sausages and {p} pies for a profit of {w}p")

        Like

        • Frits's avatar

          Frits 10:32 am on 22 May 2024 Permalink | Reply

          Assuming that the caterer will spend exactly 600p and that the caterer will order a sensible amount of sausages S (50, 55, 60, …, 95, 100) the profit (if the cricketers get the booking) can be expressed as: 2.2 * S + 60 and 460 – 2.8 * S if the darters get the booking.

          As the first function is increasing and the latter is decreasing for S the safe profit will be maximized if 2.2 * S + 60 = 460 – 2.8 * S or S = 80.

          Liked by 1 person

    • Lise Andreasen's avatar

      Lise Andreasen 2:17 am on 22 May 2024 Permalink | Reply

      Interesting.

      I approached it differently and arrived at 100 sausage rolls and a profit of 280.

      https://onlinephp.io/c/47cce

      Like

      • Lise Andreasen's avatar

        Lise Andreasen 2:23 am on 22 May 2024 Permalink | Reply

        Oh, hang on. Read the puzzle incorrectly.

        Like

      • Jim Randell's avatar

        Jim Randell 12:44 pm on 24 May 2024 Permalink | Reply

        Sorry. For a short while the numbers were mixed up between the original puzzle and the version published in the book. The puzzle text now reflects the version from the book, rather than the originally published version.

        Like

  • Unknown's avatar

    Jim Randell 8:04 am on 19 May 2024 Permalink | Reply
    Tags:   

    Brainteaser 1315: The nineteenth hole 

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

    A famous English mathematician, J.E. Littlewood, once posed the following puzzle:

    Find a number N (sensibly the smallest) such that, if you shift the first digit to the end, the result is exactly one-and-a-half times N.

    The solution to this being:

    N = 1,176,470,588,235,294.

    Professor Egghead has discovered a similar intriguing fact (not in his bath, nor sitting under a fruit-tree; but while relaxing in the club-house, after a round of golf). It is:

    A smallest positive integer, M, such that, if one again shifts the leading digit to the end, the result is, this time, exactly just one half of M.

    How many digits has M?

    [teaser1315]

     
    • Jim Randell's avatar

      Jim Randell 8:11 am on 19 May 2024 Permalink | Reply

      See: Puzzle #180, Enigma 653, Enigma 924, Teaser 2565, Enigma 1036, Enigma 455, Enigma 1161 (but note these may reveal the answer to this puzzle).

      Normally a parasitic number [ @wikipedia ] involves multiplying the number by a(n integer) value by moving the final digit to the front.

      This puzzle moves the front digit to the end, so we are looking at the inverse of the process involved in parasitic numbers. So if we find a 2-parasitic number, we can start with it, move the front digit (back) to the end, and it is divided by 2.

      For this Python program I adapted my [[ parasitic() ]] function from Enigma 924 to deal with fractional multipliers, and this allows us to solve both problems mentioned in the puzzle text.

      This program runs in 59ms. (Internal runtime is 167µs).

      from enigma import (irange, inf, div, ndigits, first, printf)

# find numbers such that moving the final digit to the front
# result in a multiplication of the original number by k/q
def parasitic(k, q=1, M=inf, base=10):
  assert k < q * base and q < k * base
  b = base * k - q

  # consider n digit numbers
  for n in irange(1, M):
    a = base**n * q - k
    m = base**(n - 1)
    # consider non-zero digits d
    for d in irange(1, base - 1):
      x = div(d * a, b)
      if x is not None and m * base > x >= m:
        yield base * x + d

# find numbers such that moving the first digit to the end
# result in a multiplication of the original number by p/q
# this is the same as finding a (q/p)-parasitic number
for (p, q) in [(3, 2), (1, 2)]:
  # find the lowest number
  for x in first(parasitic(q, p), 1):
    n = div(x * q, p)
    # output solution
    printf("[{p}/{q}] {n} * {p}/{q} = {x} [{k} digits]", k=ndigits(n))

      Solution: M has 18 digits.

      The smallest number is 210526315789473684.

      210526315789473684 × 1/2 = 105263157894736842

      Note that this is the repetend of 4/19 = 0.(210526315789473684)…

      If you don’t mind leading zeros we can apply the same procedure to the result (which also has 18 digits), to get:

      105263157894736842 × 1/2 = 052631578947368421

      See also: OEIS A337922, OEIS A146088.

      Like

    • Frits's avatar

      Frits 3:24 pm on 19 May 2024 Permalink | Reply 

        
# k-digit number n = fp = 2(10p + f) with 19p = (10^(k - 1) - 2)f
# 19p = a999...999b with a = f - 1 and b = 10 - 2f

for k in range(2, 99):
  for f in range(2, 6):
    # check for a multiple of 19
    if (p19 := f * 10**(k - 1) - 2 * f) % 19: continue
    s19 = str(p19)
    a = str(f - 1)
    b = str(10 - 2 * f)
    
    if s19[1:-1] == "9" * (k - 2) and (s19[0], s19[-1]) == (a, b):
      print("answer:", k)
      break
  else:
    continue
  break

      Like

  • Unknown's avatar

    Jim Randell 4:33 pm on 17 May 2024 Permalink | Reply
    Tags:   

    Teaser 3217: Peace in rest 

    From The Sunday Times, 19th May 2024 [link] [link]

    George and Martha regularly read the obituaries in the national press; as well as the date of death, the date of birth of the person discussed is always shown. “That is interesting!” commented Martha as she looked at the three obituaries displayed one morning. Two of them have palindromic dates of birth (e.g., 13/11/31, 21/6/12). “Very unlikely, indeed!” agreed George.

    Assuming that birth dates are expressed as day (1-31), month (1-12) year (00-99), what is the probability of a palindromic birth date in the 20th century (1900 to 1999 inclusive), and will it be greater, equal or less in the 21st century?

    [teaser3217]

     
    • Jim Randell's avatar

      Jim Randell 4:50 pm on 17 May 2024 Permalink | Reply

      Technically the dates of the 20th century are 1st January 1901 – 31st December 2000, but that is not the convention followed in this puzzle. We are interested in the 19xx years and the 20xx years.

      The answer to the second part of the puzzle comes from a fairly straightforward observation.

      However, here is a constructive solution, that counts the palindromic dates in years 19xx and 20xx (assuming the calendar continues as expected, and that birth dates are uniformly distributed).

      There are two ways we can check for palindromes, with or without the separators in the dates. In the following I am assuming that we only check the digits of the date, but the separators can be included at line 11 if required (although this changes the number of palindromic dates found).

      from datetime import (date, timedelta)
from enigma import (repeat, inc, is_palindrome, rdiv, compare, printf)

# return fraction of palindromic dates in years <a> - <b>
def pal(a, b):
  p = t = 0
  for d in repeat(inc(timedelta(days=1)), date(a, 1, 1)):
    if d.year > b: break
    t += 1
    # look for palindromic dates
    s = d.strftime("%-d%-m%y")
    if is_palindrome(s): p += 1
  r = rdiv(p, t)
  printf("{a}..{b} -> {p}/{t} = {r}")
  return r

# calculate fractions for years 19xx and 20xx
(P19, P20) = (pal(1900, 1999), pal(2000, 2099))
r = compare(P20, P19, vs=['less than', 'equal to', 'more than'])
printf("P(20xx) {r} P(19xx)")

      Solution: The proportion of palindromic dates in the years 1900 – 1999 is 7/794. In the years 2000 – 2099 there will be a (slightly) smaller proportion of palindromic dates.

      In each of the 19xx and 20xx years there are a total of 322 palindromic dates. (Each palindromic date can refer to a 19xx date and a 20xx date).

      However, as the year 1900 was not a leap year and the year 2000 was, there is 1 less day in the 19xx years, and so there is a higher proportion of palindromes compared to the 20xx years.

      Note, that if we use the actual definition of 20th and 21st centuries (1901 – 2000 and 2001 – 2100) the result is reversed, as the leap day in 2000 is included in the earlier period.

      Manually, we can count the number of palindromic dates in a 100 year period by considering the following constructions:

      x/y/yx → x = 1..9, y = 1..9 ⇒ 9×9 = 81 dates
      xy/z/yx → xy = 10..31, z = 1..9 ⇒ 22×9 = 198 dates
      x/yz/yx → x = 1..9, yz=10..12 ⇒ 9×3 = 27 dates
      xy/zz/yx → xy = 10..31, zz=11 ⇒ 22×1 = 22 dates

      For a grand total of 81 + 198 + 27 + 22 = 328 dates.

      However not all of these dates are valid, as some months don’t have 31 days. So we can remove the following invalid dates:

      30/2/03
      31/2/13
      31/4/13
      31/6/13
      31/9/13
      31/11/13

      (Note that: 29/2/92 is a valid date).

      And that leaves 322 palindromic dates in a century.

      We can also count the total number of days in a century:

      There are 365×100 = 36500 non-leap days, plus the number of leap days.

      There are 24 leap years per century, plus an extra one when the year is divisibly by 400. So 2000 was a leap year, but 1900 was not.

      Hence, there are 24 leap days in the years 1900..1999, and 25 in the years 2000..2099.

      The proportions are:

      P(1900..1999) = 322/36524 = 7/794 ≈ 0.881612%
      P(2000..2099) = 322/36525 ≈ 0.881588%

      So the proportion of palindromic dates in the years 2000..2099 is slightly smaller than the proportion in the years 1900..1999.

      Like

    • Pete Good's avatar

      Pete Good 4:54 pm on 18 May 2024 Permalink | Reply

      Jim, I tried to run this program in Windows (using the Microsoft Visual Studio environment) but it generates the error INVALID FORMAT STRING because %-d and %-m are not supported by Microsoft. I am therefore hoping that my own C++ program has produced the correct solution!

      Like

      • Jim Randell's avatar

        Jim Randell 5:26 pm on 18 May 2024 Permalink | Reply

        Yes, I think this format is a glibc extension to strftime(). (Although it looks like Windows might use %# instead of %- to suppress zero padding).

        But in Python 3 you can replace line 11 with:

        s = f"{d.day}{d.month}{d.year % 100:02d}"

        (which also seems to be faster).

        or more generally:

        s = str.format("{d}{m}{y:02d}", d=d.day, m=d.month, y=d.year % 100)

        Like

    • Pete Good's avatar

      Pete Good 5:44 pm on 18 May 2024 Permalink | Reply

      Thanks Jim, both of your suggestions work fine in Visual Studio and the program generated the same solution as my C++ program.

      Like

  • Unknown's avatar

    Jim Randell 8:04 am on 16 May 2024 Permalink | Reply
    Tags:   

    Teaser 2615: Gunpowder, treason and plot 

    From The Sunday Times, 4th November 2012 [link] [link]

    Last year I overheard this conversation one day during the first seven days of November:

    Alec: It’s the 5th today, let’s have a bonfire.
    Bill: No, the 5th is tomorrow.
    Chris: You’re both wrong — the 5th is the day after tomorrow.
    Dave: All three of you are wrong.
    Eric: Yesterday was certainly not the 1st.
    Frank: We’ve missed bonfire night.

    If you knew how many of their statements were true, then you could work out the date in November on which this conversation took place.

    What was that date?

    In Britain, Bonfire night is 5th November.

    [teaser2615]

     
    • Jim Randell's avatar

      Jim Randell 8:05 am on 16 May 2024 Permalink | Reply

      A straightforward puzzle to solve, either manually or programatically.

      This Python program evaluates the statements on each of the 7 possible days, and looks for situations where the number of true statements uniquely identifies a single day.

      from enigma import (irange, group, seq2str, printf)

# calculate statement values for date <d>
def statements(d):
  # A: "It is the 5th today ..."
  A = (d == 5)
  # B: "The 5th is tomorrow ..."
  B = (d + 1 == 5)
  # C: "The 5th is the day after tomorrow ..."
  C = (d + 2 == 5)
  # D: "A, B, C are all wrong ..."
  D = not (A or B or C)
  # E: "Yesterday was not the 1st ..."
  E = (d - 1 != 1)
  # F: We have missed bonfire night (the 5th) ..."
  F = (d > 5)
  return [A, B, C, D, E, F]

# group dates by the number of true statements
g = group(irange(1, 7), by=(lambda d: statements(d).count(True)))

# look for groups with a single member
for (k, vs) in g.items():
  if len(vs) == 1:
    printf("{k} true -> {vs} November", vs=seq2str(vs, sort=1, enc=""))

      Solution: The conversation took place on 2nd November.

      There is only 1 true statement, and it is made by Dave.

      Like

    • Frits's avatar

      Frits 10:31 am on 16 May 2024 Permalink | Reply 

      # the number of correct statements 
fn = lambda d: sum([d == 5, d == 4, d == 3, d < 3 or d > 5, d != 2, d > 5])
 
seen, sols = set(), dict()
# now find a count that is unique
for d in range(1, 8):
  if (c := fn(d)) in seen:
    try:
      del sols[c]
    except KeyError:
      pass
  else:
    sols[c] = str(d)  
    seen.add(c)  
    
print(f"answer: November {' or '.join(sols.values())}")

      Like

    • Lise Andreasen's avatar

      Lise Andreasen 7:06 pm on 16 May 2024 Permalink | Reply

      T = the date today.
      A: T = 5.
      B: T = 4.
      C: T = 3.
      D: T != 3, 4, 5.
      E: T != 2.
      F: T = 6 v T = 7.
      Of A, B, C and D, 1 is true, 3 are false.
      There can therefore be 1, 2 or 3 true statements.
      With 3 true statements, both E and F are true. T could be 6 or 7.
      With 2 true statements, either E or F is true. If E is true, T = 2. If F is true, T could be 1, 3, 4 or 5.
      With 1 true statement, both E and F are false. T = 2. This is the only option leading to 1 answer. Therefore there was 1 true statement and it’s 2nd November.

      Like

    • GeoffR's avatar

      GeoffR 1:54 pm on 17 May 2024 Permalink | Reply 

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

var 1..7: T; % Date conversation took place

% A - F statements
constraint sum([T==5, T==4, T==3, T!=3 \/ T!=4 \/ T!=5,
T!=2, T==6 \/ T==7]) == 1;

solve satisfy;

output [" T = " ++ show(T)];

% T = 2;
%---------
%=========

      Like

  • Unknown's avatar

    Jim Randell 10:16 am on 14 May 2024 Permalink | Reply
    Tags:   

    Brain-Teaser 950: Magic moments 

    From The Sunday Times, 5th October 1980 [link]

    Joe decided to utilise the garden see-saw to demonstrate the principles of balance, and of moments to, his family. Alf, Bert, Charlie, Doreen, Elsie and Fiona weighed 100, 80, 70, 60, 50 and 20 kilos respectively. The seesaw had three seats each side, positioned 1, 2 and 3 metres from the centre.

    They discovered many ways of balancing using some or all of the family.

    In one particular combination, with at most one person on each seat, one of the family not on the seesaw observed that the sum of the moments of all of the people on the seesaw was a perfect square.

    “That’s right”, said Joe, “but, as you can see, it doesn’t balance — and what’s more, there’s nowhere you can sit to make it balance”.

    “Wrong”, was the reply. “I could sit on someone’s lap”.

    “True,” said Joe, “but only if you sit at the end”.

    Which two would then be sitting together, and who else, if anyone, would be on the same side of the see-saw?

    [To find the moment due to each person, multiply their distance from the centre by their weight. The sum of the moments on one side should equal the sum of those on the other if balance is to be achieved].

    This puzzle is included in the book The Sunday Times Book of Brainteasers (1994).

    [teaser950]

     
    • Jim Randell's avatar

      Jim Randell 10:16 am on 14 May 2024 Permalink | Reply

      Participants can be uniquely identified by their weights.

      This Python program finds possible seating arrangements on the see-saw.

      It runs in 72ms. (Internal runtime is 13ms).

      from enigma import (subsets, is_square, div, printf)

# weights and positions
weights = [100, 80, 70, 60, 50, 20]
poss = [+1, +2, +3, -1, -2, -3]

# there is at least one member not seated
for ws in subsets(weights, min_size=2, max_size=len(weights) - 1, select='C'):
  # allocate positions (including +3)
  for ps in subsets(poss, size=len(ws), select='P'):
    if +3 not in ps: continue
    # find the total sum of the moments
    ms = sum(w * abs(p) for (w, p) in zip(ws, ps))
    if not is_square(ms): continue
    # weight required at +3 to balance the see-saw
    x = -sum(w * p for (w, p) in zip(ws, ps))
    w = div(x, +3)
    # is it the weight of a missing person?
    if not (w in weights and w not in ws): continue
    # output solution
    printf("ws={ws} ps={ps} ms={ms} x={x} w={w}")

      Solution: Doreen would join Fiona at the end of the see-saw. Elsie is also seated on the same side.

      The seating arrangement is as follows:

      Without D the moments are (kg.m):

      L = 70×3 + 80×1 = 290
      R = 20×3 + 50×1 = 110

      They don’t balance, but they do sum to 400 = 20^2.

      With D the moments on the right become:

      R = (20 + 60)×3 + 50×1 = 290

      and the see-saw balances.

      Like

    • Frits's avatar

      Frits 2:26 pm on 14 May 2024 Permalink | Reply 

        
from enigma import express
from itertools import product
 
# weights and positions
weights = [100, 80, 70, 60, 50, 20]
names = ["Alf", "Bert", "Charlie", "Doreen", "Elsie", "Fiona"]

# possible squares divisible by 10 
for sq in [100, 400, 900]:
  # decompose square into weights
  for e in express(sq, weights, min_q=0, max_q=3):
    # someone is sitting at the end and one place is empty
    if all(x for x in e) or 3 not in e: continue
    # at most one person on each seat
    if any(e.count(i) > 2 for i in range(1, 4)): continue
   
    # one of the family not on the seesaw to sit at the end on someone's lap
    for i, seat in enumerate(e):
      if seat: continue # not an empty seat
      e1 = e[:i] + [3] + e[i + 1:] 
      
      # multiply elements by 1 or -1 times the weight and 
      # see if they sum to zero
      for prod in product([-1, 1], repeat=len([x for x in e1 if x])):
        if prod[0] > 0: continue    # avoid symmetric duplicates
        # weave in zeroes
        p = list(prod)
        p = [p.pop(0) if x else 0 for x in e1]
        
        # is the seesaw in balance?
        if sum([x * y * weights[i] 
               for i, (x, y) in enumerate(zip(p, e1))]) != 0: continue
        # new persion must be sitting on someone's lap at the end
        someone = [j for j in range(6) if j != i and e1[j] == 3 and 
                                          p[j] == p[i]]
        if not someone: continue
        print(f"{names[i]} would join {names[someone[0]]}",
              f"at the end ofthe see-saw.")
        oths = [j for j in range(6) if p[j] == p[i] and 
                                       j not in {i, someone[0]}]
        if not oths: continue
        ns = [names[o] for o in oths]
        oths = ns[0] + " is" if len(oths) == 1 else ' and '.join(ns) + " are"
        print(f"{oths} also seated on the same side.")

      Like

  • Unknown's avatar

    Jim Randell 4:34 pm on 10 May 2024 Permalink | Reply
    Tags:   

    Teaser 3216: Quel carve-up! 

    From The Sunday Times, 12th May 2024 [link] [link]

    A French farmer’s estate is shaped like a right-angled triangle ABC on top of a square BCDE. The triangle’s hypotenuse is AB, and its shortest side, AC, has length 1 kilometre. Nearing retirement, the farmer decides to sell off the square of land and, obeying the Napoleonic law of succession, divide the triangle into three equal plots, one for each of his two children and a third for him and his wife in retirement. His surveyor discovers, surprisingly, that his remaining triangle of land can be divided neatly into three right-angled triangles, all identical in shape and size (allowing for reflections / rotations).

    How many hectares did the farmer sell?

    (1 hectare = area of 100m × 100m plot).

    [teaser3216]

     
    • Jim Randell's avatar

      Jim Randell 5:05 pm on 10 May 2024 Permalink | Reply

      I found it easiest to start from the end:

      For the final dissection we need to find 3 identical right-angled triangles that can fit together to form a triangle.

      It is possible to do this such that the combined triangle is a larger version of the small triangles.

      We can fit three identical (30°, 60°, 90°) triangles together to form a larger (30°, 60°, 90°) triangle as shown.

      So this can serve as a dissection of the original triangular plot, and also the farmer’s allocated plot.

      The ratio of the sides in the (30°, 60°, 90°) triangle are 1 : √3 : 2.

      So, if the shortest side has length 1 km, the remaining non-hypotenuse side has length √3 km, and this is the same as the side of the square plot.

      Hence the square plot has an area of 3 km², and there are 100 hectares per square kilometre:

      Solution: The farmer sold 300 hectares.

      Although this is not the only possible arrangement.

      The first dissection only has to be into 3 equal area triangles (so they don’t have to be identical), so here is another possible arrangement (where the first dissection can be made by dividing BC into three equal parts):

      Like

  • Unknown's avatar

    Jim Randell 7:33 pm on 9 May 2024 Permalink | Reply
    Tags:   

    Teaser 2610: Odd ages 

    From The Sunday Times, 30th September 2012 [link] [link]

    Recently Alex, Bernard and Charles were comparing their ages in years. Alex’s age was an odd two-digit number and Bernard’s age was a whole number percentage more than that. On the other hand, Charles’s age was also an odd two-digit number but Bernard’s age was a whole number percentage less than that. They were surprised to find that the percentage was the same in both cases.

    What were their three ages?

    [teaser2610]

     
    • Jim Randell's avatar

      Jim Randell 7:34 pm on 9 May 2024 Permalink | Reply

      Supposing the 3 are all different ages (so the percentage is non-zero).

      A’s age is an odd 2-digit number, and C’s age is a (larger) odd 2-digit number, and so B’s age is between them, hence also a 2-digit number.

      For percentage p we have:

      A (100 + p) / 100 = B
      C (100 − p) / 100 = B
      ⇒
      p = 100 (C − A) / (C + A)

      The following Python program runs in 67ms. (Internal runtime is 463µs).

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

# ages for A and C (2-digit, odd)
for (A, C) in subsets(irange(11, 99, step=2), 2):
  # calculate percentage
  p = div(100 * (C - A), C + A)
  if p is None: continue
  # calculate B
  B = div(A * (100 + p), 100)
  if B is None: continue
  # output solution
  printf("A={A} B={B} C={C} [p={p}%]")

      Solution: Alex is 15. Bernard is 21. Charles is 35.

      And the percentage in question is 40%:

      15 + 40% = 15 × (1 + 0.4) = 21
      35 − 40% = 35 × (1 − 0.4) = 21

      Like

    • Frits's avatar

      Frits 10:06 am on 10 May 2024 Permalink | Reply 

      for a in range(11, 100, 2):
  # determine valid percentages, maximum percentage = (99 - 12) / 99 = 0.87878
  for p in [p for p in range(2, 88, 2) if (p * a) % 100 == 0]:
    b = a + (p * a) // 100
    c, r = divmod(100 * b, 100 - p)
    if c > 99: break
    if r or c % 2 == 0: continue
    print("answer:", (a, b, c))

      Like

    • GeoffR's avatar

      GeoffR 10:35 am on 10 May 2024 Permalink | Reply 

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

var 11..99:A; var 11..99:B; var 11..99:C;
var 1..95:p; % Percentage

constraint all_different([A, B, C]);
constraint sum([A mod 2 == 1, B mod 2 == 1, C mod 2 == 1]) == 3;
constraint 100*A + p*A == 100*B;
constraint 100*C - p*C == 100*B;

solve satisfy;

output["[Alex, Bernard, Charles] = " ++ show([A, B, C]) ];
 
% [Alex, Bernard, Charles] = [15, 21, 35]
% ----------
% ==========

      Like

  • Unknown's avatar

    Jim Randell 3:02 pm on 7 May 2024 Permalink | Reply
    Tags:   

    Teaser 2617: A case of ambiguity 

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

    Every schoolchild knows that it is possible for two triangles to have two of their lengths-of-sides in common and one of their angles in common without the two triangles being identical or “congruent”.

    This can happen when the common angle is not included between the two common sides. I have found such a pair of non-congruent triangles with all the lengths of the sides being a whole number of centimetres and with the longest side of each triangle being 10cm in length.

    What are the lengths of the other two sides of the smaller triangle?

    [teaser2617]

     
    • Jim Randell's avatar

      Jim Randell 3:02 pm on 7 May 2024 Permalink | Reply

      Each triangle has a longest side of 10, so the remaining two sides must be 1 – 9, so there aren’t that many triangles to consider.

      This Python program considers the side lengths of possible triangles and uses the cosine rule to calculate the internal angles, and then looks for two different triangles that share an angle.

      It runs in 72ms. (Internal runtime is 664µs).

      from enigma import (fraction as Q, irange, intersect, call, cache, printf)

# return values as cosines (using cosine rule)
cosA = lambda x, y, z: Q(y*y + z*z - x*x, 2*y*z)

# find the angles of a triangle with sides x, y, z
@cache
def _angles(x, y, z):
  # is it a valid triangle?
  if x + y > z:
    return {cosA(x, y, z), cosA(y, z, x), cosA(z, x, y)}
angles = lambda *ss: call(_angles, sorted(ss))

# choose the shared side a
for a in irange(1, 9):
  # choose the shorter remaining side b
  for b in irange(1, 8):
    angles1 = angles(a, b, 10)
    if not angles1: continue
    # choose the longer remaining side c
    for c in irange(b + 1, 9):
      angles2 = angles(a, c, 10)
      if not angles2 : continue
      # check for a common angle
      if intersect([angles1, angles2]):
        # output solution
        printf("({a}, {b}, 10) -> {angles1}; ({a}, {c}, 10) -> {angles2}")

      Solution: The other two sides of the smaller triangle are: 4cm and 8cm.

      The triangles look like this:

      And the common angle α is acos(13/20) ≈ 49.46°.

      Like

    • Frits's avatar

      Frits 5:46 pm on 7 May 2024 Permalink | Reply

      We also have 10^2 – 8^2 = 4 * 9.

      See (here).

      Like

      • Jim Randell's avatar

        Jim Randell 4:41 pm on 8 May 2024 Permalink | Reply

        This result follows directly from using the cosine rule on the shared angle of both triangles:

        Suppose the base of the triangle is d, and we can make two triangles with the same angle α using sides b, a and c, a.

        Then, using the cosine rule on both triangles:

        cos(α) = (d² + b² − a²)/2db = (d² + c² − a²)/2dc
        ⇒
        c(d² + b² − a²) = b(d² + c² − a²)
        (c − b)(d² − a²) − bc(c − b) = 0
        (c − b)(d² − a² − bc) = 0
        [b ≠ c] ⇒
        bc = d² − a² = (d − a)(d + a)

        Which gives a straightforward program:

        from enigma import (irange, divisors_pairs, printf)

d = 10
for a in irange(1, d - 1):
  for (b, c) in divisors_pairs(d*d - a*a):
    if b < c < d:
      printf("triangles = ({d}, {a}, {b}) ({d}, {a}, {c})")

        Like

    • GeoffR's avatar

      GeoffR 6:37 pm on 8 May 2024 Permalink | Reply 

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

var 1..9:A; var 1..9:B; var 1..9:C;
int: D == 10;  % Two triangles are ABD and ACD

constraint B * C == D * D - A * A;
constraint B < C /\ C < D;

solve satisfy;
output ["Two triangles are " ++ show([A,B,D]) ++ " and " ++ show([A,C,D]) ];

% Two triangles are [8, 4, 10] and [8, 9, 10]
% ----------
% ==========

      Like

  • Unknown's avatar

    Jim Randell 12:29 pm on 5 May 2024 Permalink | Reply
    Tags: ,   

    Brain-Teaser 748: [Cutting corners] 

    From The Sunday Times, 16th November 1975 [link]

    Young Bob had been given a carpentry set and with it a rectangular board (whose diagonal measured less than 1½ metres) on which to practise using his saw.

    With straight cuts of successively greater length and aggregating to an exact number of metres, he first proceeded to saw dissimilar triangular pieces off each corner of the board in turn, the remaining quadrilateral piece being put aside for another day.

    All the 12 sides of the sawn-off pieces measured exact and different numbers of centimetres.

    What were the length and width of the board? (in cms).

    As set this puzzle has multiple solutions, however if we interpret “less than 1½ meters” to mean “less than 150 cm, but more than 149 cm”, then we get a unique solution that is the same as that published in the newspaper.

    This puzzle was originally published with no title.

    [teaser748]

     
    • Jim Randell's avatar

      Jim Randell 12:30 pm on 5 May 2024 Permalink | Reply

      Perhaps the puzzle originally said “just less than 1½ metres”, but the “just” got lost somewhere.

      The following program assembles pairs of Pythagorean triangles point-to-point. This gives us candidate widths and heights for the board. We then find two pairs with the same width that fit together to make a rectangle as specified.

      By “dissimilar” triangles I am assuming that no pair of triangles is mathematically similar (i.e. none of them are multiples of the same primitive Pythagorean triangle).

      The program runs in 108ms. (Internal runtime is 40ms).

      from enigma import (
  defaultdict, pythagorean_triples, subsets, cproduct,
  seq_all_different, hypot, rev, ordered, ratio, cached, printf
)

# diagonal limit
D = 150

# possible triangles (x, y) -> z
tris = dict(((x, y), z) for (x, y, z) in pythagorean_triples(D - 1))

# primitive triangle
primitive = cached(lambda t: ratio(*t))

# assemble pairs of triangles: <combined-width> -> (<h1>, <h2>) -> (<w1>, <w2>)
pairs = defaultdict(lambda: defaultdict(set))
for (k1, k2) in subsets(tris.keys(), size=2):
  for ((w1, h1), (w2, h2)) in cproduct((k, rev(k)) for k in (k1, k2)):
    w = w1 + w2
    if w < D:
      (k, v) = ((h1, h2), (w1, w2)) if h1 < h2 else ((h2, h1), (w2, w1))
      pairs[w][k].add(v)

# choose a width and height for the initial rectangle
for (w, h) in subsets(pairs.keys(), size=2):
  z = hypot(w, h)
  if not (D - 1 < z < D): continue

  # choose a pair of triangles for the base
  for k1 in pairs[w]:
    (h1, h2) = k1
    # calculate the corresponding matched pair
    k2 = (h4, h3) = (h - h2, h - h1)
    if not (k2 > k1 and k2 in pairs[w]): continue
    for ((w1, w2), (w4, w3)) in cproduct(pairs[w][k] for k in (k1, k2)):
      # assemble the triangles
      (x1, y1, x2, y2, x3, y3, x4, y4) = (h1, w1, w2, h2, h4, w4, w3, h3)
      (z1, z2, z3, z4) = (tris[ordered(x, y)] for (x, y) in [(x1, y1), (x2, y2), (x3, y3), (x4, y4)])
      # sum of cuts is a multiple of 100
      T = z1 + z2 + z3 + z4
      if T % 100 != 0: continue
      # sides are all different
      ts = (t1, t2, t3, t4) = ((x1, y1, z1), (x2, y2, z2), (x3, y3, z3), (x4, y4, z4))
      if not seq_all_different(t1, t2, t3, t4): continue
      # triangle are dissimilar
      if not seq_all_different(primitive(ordered(*t)) for t in ts): continue
      # output solution
      printf("{w} x {h} -> {z:.2f}; {t1} {t2} {t3} {t4} T={T}")

      Solution: The board was: 28 cm × 147 cm.

      And here is how the triangles fit together:

      If we just look for any diagonal that is less than 150cm (which is a direct interpretation of the published puzzle text), then we find the following 23 solutions (ordered by length of diagonal):

      # Z = diagonal; T = total length of cuts
 28 × 147: Z=149.64 (12, 35, 37) (15, 112, 113) (16, 63, 65) (13, 84, 85) T=300
 51 × 140: Z=149.00 (15, 20, 25) (35, 120, 125) (36, 77, 85) (16, 63, 65) T=300
 87 × 120: Z=148.22 (7, 24, 25) (72, 96, 120) (80, 84, 116) (15, 36, 39) T=300
 48 × 140: Z=148.00 (15, 20, 25) (35, 120, 125) (33, 56, 65) (13, 84, 85) T=300
 60 × 135: Z=147.73 (9, 12, 15) (90, 48, 102) (126, 32, 130) (45, 28, 53) T=300
103 × 105: Z=147.09 (5, 12, 13) (60, 91, 109) (100, 75, 125) (45, 28, 53) T=300
 95 × 112: Z=146.86 (20, 21, 29) (60, 91, 109) (75, 100, 125) (35, 12, 37) T=300
 83 × 120: Z=145.91 (18, 24, 30) (28, 96, 100) (65, 72, 97) (55, 48, 73) T=300
100 × 105: Z=145.00 (9, 40, 41) (72, 65, 97) (91, 60, 109) (28, 45, 53) T=300
 90 × 112: Z=143.68 (20, 48, 52) (40, 42, 58) (92, 69, 115) (72, 21, 75) T=300
 60 × 129: Z=142.27 (3, 4, 5) (33, 56, 65) (126, 32, 130) (96, 28, 100) T=300
 69 × 124: Z=141.90 (9, 40, 41) (13, 84, 85) (60, 91, 109) (56, 33, 65) T=300
 85 × 111: Z=139.81 (5, 12, 13) (20, 99, 101) (80, 39, 89) (65, 72, 97) T=300
 93 × 104: Z=139.52 (20, 21, 29) (65, 72, 97) (84, 13, 85) (39, 80, 89) T=300
 92 × 104: Z=138.85 (5, 12, 13) (39, 80, 89) (99, 20, 101) (65, 72, 97) T=300
 59 × 124: Z=137.32 (7, 24, 25) (12, 35, 37) (117, 44, 125) (112, 15, 113) T=300
 76 × 114: Z=137.01 (15, 36, 39) (9, 40, 41) (99, 20, 101) (105, 56, 119) T=300
 80 × 111: Z=136.82 (5, 12, 13) (20, 99, 101) (75, 100, 125) (60, 11, 61) T=300
 84 × 108: Z=136.82 (3, 4, 5) (18, 80, 82) (105, 36, 111) (90, 48, 102) T=300
 95 ×  96: Z=135.06 (16, 63, 65) (60, 32, 68) (80, 18, 82) (36, 77, 85) T=300
 93 ×  95: Z=132.94 (11, 60, 61) (56, 33, 65) (84, 13, 85) (39, 80, 89) T=300
 67 ×  72: Z= 98.35 (9, 12, 15) (48, 55, 73) (63, 60, 87) (24, 7, 25) T=200
 56 ×  78: Z= 96.02 (8, 15, 17) (16, 63, 65) (48, 36, 60) (40, 42, 58) T=200

      and we see the published solution is the first of these (longest diagonal).

      Like

    • Hugo's avatar

      Hugo 3:36 pm on 5 May 2024 Permalink | Reply

      His saw cuts (each of which became the hypotenuse of a triangle) were progressively longer as he moved round the board to each corner in turn. Did you take that into account?

      Like

      • Jim Randell's avatar

        Jim Randell 4:45 pm on 5 May 2024 Permalink | Reply

        I didn’t check that the cut lengths can form an increasing sequence (going clockwise or anticlockwise around the board), as I decided he could just make the four cuts in ascending order, however they are arranged.

        But if you do require this there are still 9 different solutions with diagonals <150 cm (including the published one).

        Like

    • Hugo's avatar

      Hugo 7:43 am on 6 May 2024 Permalink | Reply

      I think we can reduce it to a single solution if we add the words
      “The board had the smallest possible area, consistent with what has been said.”

      Like

  • Unknown's avatar

    Jim Randell 3:34 pm on 3 May 2024 Permalink | Reply
    Tags:   

    Teaser 3215: Darts league 

    From The Sunday Times, 5th May 2024 [link] [link]

    In our darts league, each team plays each other once. The result of each match is decided by the number of legs won, and each match involves the same number of legs. If both teams win the same number of legs, the match is drawn. The final league table shows the games won, drawn or lost, and the number of legs won for and against the team. The Dog suffered the most humiliating defeat, winning only one leg of that match. Curiously, no two matches had the same score.

    What was the score in the match between The Crown and The Eagle?

    [teaser3215]

     
    • Jim Randell's avatar

      Jim Randell 4:30 pm on 3 May 2024 Permalink | Reply

      Each team plays 4 matches and 80 legs, so each match has 20 legs. A and B draw, so their match is 10-10.

      D has a 1-19 match, so the scores in the other matches are between 2 and 18 (excluding 10), which is 16 values distributed between 16 different slots, so each value appears exactly once.

      Here is a solution using the [[ SubstitutedExpression ]] solver from the enigma.py library.

      The following run file executes in 83ms. (Internal runtime is 4.4ms).

      #! python3 -m enigma -rr

SubstitutedExpression

# suppose the matches (X v Y) and scores for X are:
#
#  A v B = Q
#  A v C = R
#  A v D = S
#  A v E = T
#  B v C = U
#  B v D = V
#  B v E = W
#  C v D = X
#  C v E = Y
#  D v F = Z

--base=20 # allow scores of 1-19
--digits="1-19"
--code="v = lambda x: 20 - x" # opponent's score

# scores for each match for each team
--macro="@A = [Q, R, S, T]"
--macro="@B = [v(Q), U, V, W]"
--macro="@C = [v(R), v(U), X, Y]"
--macro="@D = [v(S), v(V), v(X), Z]"
--macro="@E = [v(T), v(W), v(Y), v(Z)]"

# total legs for each team
"sum(@A) == 55"  # A
"sum(@B) == 43"  # B
"sum(@C) == 37"  # C
"sum(@D) == 41"  # D
"sum(@E) == 24"  # E

# A and B drew (10-10)
--assign="Q,10"

# all matches have different scores
"seq_all_different(ordered(x, v(x)) for x in [Q, R, S, T, U, V, W, X, Y, Z])"

# D won 1 leg in one game, and this was the worst score
"1 in { v(S), v(V), v(X), Z }"
--invalid="1|19,RTUWY"

# won, drawn, lost
--code="""
def wdl(ss):
  vs = list(compare(s, 10) for s in ss)
  return (vs.count(1), vs.count(0), vs.count(-1))
"""

"wdl(@A) == (2, 1, 1)"  # A
"wdl(@B) == (1, 1, 2)"  # B
"wdl(@C) == (2, 0, 2)"  # C
"wdl(@D) == (3, 0, 1)"  # D
"wdl(@E) == (1, 0, 3)"  # E

# answer is the score in CE
--answer="(Y, v(Y))"
--template=""

      Solution: The score in the Crown vs Eagle match was 16-4.

      There are two possible sets of scores in the matches:

      A v B = 10-10
      A v C = 8-12 / 18-2
      A v D = 19-1
      A v E = 18-2 / 8-12
      B v C = 17-3 / 7-13
      B v D = 9-11
      B v E = 7-13 / 17-3
      C v D = 6-14
      C v E = 16-4
      D v E = 15-5

      Like

      • Frits's avatar

        Frits 2:48 pm on 4 May 2024 Permalink | Reply

        Another idea would be to start the first variables Q, R, S and T with “D vs …” so we can use base=19 and digits=”1-18″.

        Like

    • Frits's avatar

      Frits 7:40 pm on 3 May 2024 Permalink | Reply 

       
# decompose number <t> into <k> increasing numbers (between <mn> and <mx>)
# so that sum(<k> numbers) equals <t> 
def decompose(t, k=4, mn=2, mx=19, s=[]):
  if k == 1:
    if s[-1] < t <= mx:
      yield s + [t]
  else:
    for n in range(mn if not s else s[-1] + 1, mx + 1):
      if 2 * k * n + k * (k - 1) > 2 * t: break
      yield from decompose(t - n, k - 1, mn, mx, s + [n])

# general checks
def check(s, grp):
  s_ = set(s) - {10}
  # all matches have different scores (we have not won/lost from ourselves)
  if any(20 - x in s for x in s_) : return False
  # different scores (except draw)
  if any(s_.intersection(g) for g in grp): return False
  # we have not played more than once against the same opponent
  return all(sum(20 - x in g for x in s) < 2 for g in grp)

sols = set()
# points for The Dog (three victories)
for D in decompose(41 - 1, 3, 11):
  D += [1]                       # winning only one leg of that match
  # points for The Anchor
  for A in decompose(55):
    if A[1] != 10: continue                             # A: 2W/1D/1L
    if not check(A, [D]): continue
    # points for Eddy
    for E in decompose(24):
      if 10 in E or E[2] > 10 or E[3] < 11: continue    # E: 1W/3L
      if not check(E, [D, A]): continue
      # points for The Crown
      for C in decompose(37):
        if 10 in C or C[1] > 10 or C[2] < 10: continue  # C: 2W/2L
        if not check(C, [D, A, E]): continue
        # now we know points for The Bull
        B = set(range(1, 20)).difference(D + A + E + C) | {10}
        if not check(B, [D, A, E, C]): continue          
       
        # collect score in the match between The Crown and The Eagle
        for c in C:
          if 20 - c in E:
            sols.add(c)
            
for c in sols:
  print(f"answer: {c} vs {20 - c}")

      Like

    • Frits's avatar

      Frits 3:04 pm on 5 May 2024 Permalink | Reply

      More compact but less efficient.

       
from itertools import permutations

# wins/draws/losses
wdl = lambda s: [w := 4 - (l := sum(x < 10 for x in s)) - (10 in s), 
                 4 - w - l, l]
v = lambda x: 20 - x    # opponent's score      

AB, AC, AD, AE, DB, DC, DE, EB, EC, BC = [0] * 10
vars = lambda k: [AB, AC, AD, AE, DB, DC, DE, EB, EC, BC][:k]

# general checks
def check(t, v3, scores, vs): 
 # check wins/draws/losses
 if wdl([v := t - sum(v3)] + v3) != scores: return False   
 # all matches have different scores
 if (min(ms := set(tuple(sorted([x, 20 - x])) for x in vs + [v])) >= (1, 19)
     and len(set(ms)) == len(vs) + 1): return v

sols = set()
AB = 10
for AC, AD in permutations(range(2, 20), 2):
  if not(AE := check(55, [AB, AC, AD], [2, 1, 1], vars(3))): continue
  for DB, DC in permutations(range(1, 19), 2):
    if not(DE := check(41, [v(AD), DB, DC], [3, 0, 1], vars(6))): continue
    if 1 not in {v(AD), DB, DC, DE}: continue   # winning only one leg ...      
    for EB in range(2, 19):
      if not(EC := check(24, [v(AE), v(DE), EB], [1, 0, 3], vars(8))): continue
      if not(check(43, [v(AB), v(DB), v(EB)], [1, 1, 2], vars(9))): continue
      sols.add(EC)
      
for s in sols:
  print(f"C vs E: {v(s)} - {s}")

      Like

  • Unknown's avatar

    Jim Randell 10:21 am on 2 May 2024 Permalink | Reply
    Tags:   

    Brain-Teaser 553: Grand Vizier 

    From The Sunday Times, 6th February 1972 [link]

    Sever-Nek, the Grand Vizier, was suspicious of the influence which Azi-Muth. the Sultan’s wily tutor, was gaining over his young pupil, and had determined to have him removed, when chance played into his hands.

    The Sultan had a collection of nearly 2,000 small square tiles, all the same size in various colours, and one day to please his tutor had arranged some of them into a square with a pretty central design and a border. Then he announced that he had made two smaller equal squares using the same pieces. “But that is impossible, said Muth, “there must be some left over”.

    There was one over, and Sever-Nek, happening to pass by put his foot over it. “Surely not”, he said. “His Serene Highness has made a most interesting discovery. No doubt the same thing can be done again. Let us add some extra tiles from the box to those already used”. Nothing loath, the Sultan soon produced a larger square from which he almost made two smaller identical squares. This time he was one tile short.

    “Your Serene Highness must have dropped this one on the floor”, said the Grand Vizier, moving his foot. Allow me to complete the design”. The discomfiture of the outwitted tutor was no less complete than his disgrace.

    How many extra tiles were taken from the box to make the larger square?

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

    [teaser553]

     
    • Jim Randell's avatar

      Jim Randell 10:22 am on 2 May 2024 Permalink | Reply

      We can suppose the requirement for a “pretty central design” is to preclude very small squares. I assumed the initial square was at least 5×5.

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

      from enigma import (irange, inf, sq, is_square, printf)

# record (x, y) where x^2 = 2 y^2 + d for d in [+1, -1]
ss = { +1: [], -1: [] }

for j in irange(2, inf):
  n = sq(j)
  if n > 1000: break

  # look for deltas
  for d in ss.keys():
    i = is_square(2*n + d)
    if i:
      printf("[{d:+d}] {i}^2 = 2x {j}^2 {d:+d}")
      ss[d].append((i, j))

# look for an initial +1, with a size at least 5
for (x1, y1) in ss[+1]:
  if x1 < 5: continue
  # and a larger -1
  for (x2, y2) in ss[-1]:
    if not (x2 > x1): continue
    # calculate the number of extra tiles (remembering one is hidden)
    d = sq(x2) - sq(x1) + 1
    # output solution
    printf("{d} extra tiles [{x1}^2 = 2 {y1}^2 + 1 -> {x2}^2 = 2 {y2}^2 - 1]")

      Solution: 1393 extra tiles were taken to make the larger square.

      The initial square was 17×17 (= 289 tiles), which can be rearranged as two 12×12 squares (= 144 tiles each) with one tile left over (and hidden).

      With an extra 1393 tiles we get a total of 288 + 1393 = 1681 which can be arranged into a 41×41 square.

      The 1681 tiles can also be arranged into two 29×29 squares (= 841 tiles each), except one of them is one tile short, and completed by the hidden tile.

      If a small initial square is allowed then there is a further solution, starting with a 3×3 square (9 tiles), this is rearranged into two 2×2 squares (8 tiles each), with one tile left over. We can then add 41 extra tiles to make a 7×7 square which can split into two 5×5 squares, one of which requires the hidden tile. (Or an extra 1673 tiles could be added to make two 29×29 squares, as above).

      Like

    • John Crabtree's avatar

      John Crabtree 6:13 pm on 2 May 2024 Permalink | Reply

      The sides of the larger and smaller squares are given in the sequences
      https://oeis.org/A001333 Numerators of continued fraction convergents to sqrt(2), and
      https://oeis.org/A001329 Denominators of continued fraction convergents to sqrt(2).
      Then all one needs to do is to find the side of the biggest larger square < sqrt(2000), ie 41, and work from there.

      Like

  • Unknown's avatar

    Jim Randell 5:28 pm on 30 April 2024 Permalink | Reply
    Tags:   

    Teaser 2612: Star signs 

    From The Sunday Times, 14th October 2012 [link] [link]

    Five friends, Abel, Bob, Jedd, Tim and Will, were investigating birthdays. Abel commented that there was just one letter of the alphabet that occurred in both his star sign and in his month of birth.

    After further investigation he found that for any pair of his star sign, his month of birth, his name, and the day of the week on which he was born, just one letter of the alphabet occurred in both. Remarkably, the same turned out to be true for each of the friends.

    Their names are listed alphabetically. What, respectively, are their star signs?

    [teaser2612]

     
    • Jim Randell's avatar

      Jim Randell 5:29 pm on 30 April 2024 Permalink | Reply

      This is a “grouping” style problem (for which there is a solver in enigma.py), but in this case the non-primary values (i.e. signs, month, day) can be re-used, and the signs and months are not independent (i.e. a particular sign spans two consecutive months).

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

      from enigma import grouping

# names
names = "Abel Bob Jedd Tim Will".split()

# map months -> month number
months = "January February March April May June July August September October November December".split()
months = dict((x, i) for (i, x) in enumerate(months, start=1))

# map signs -> valid month numbers
signs = {
  "Aries": {3, 4},
  "Taurus": {4, 5},
  "Gemini": {5, 6},
  "Cancer": {6, 7},
  "Leo": {7, 8},
  "Virgo": {8, 9},
  "Libra": {9, 10},
  "Scorpio": {10, 11},
  "Sagittarius": {11, 12},
  "Capricorn": {12, 1},
  "Aquarius": {1, 2},
  "Pisces": {2, 3},
}

# days
days = "Monday Tuesday Wednesday Thursday Friday Saturday Sunday".split()

# check a (<name>, <sign>, <month>, <day>) group
def check(n, s, m, d, fn=grouping.share_letters(1)):
  # sign/month should match, as well as the shared letters
  return (months[m] in signs[s]) and fn(n, s, m, d)

# find candidate groups (allowing repeated values)
grouping.solve([names, signs.keys(), months.keys(), days], check, distinct=0)

      Solution: The star signs are: Pisces, Virgo, Leo, Virgo, Leo.

      The full solution is:

      Abel: Pisces, March, Sunday
      Bob: Virgo, September, Monday
      Jedd: Leo, July, Monday
      Tim: Virgo, August, Monday
      Will: Leo, July, Wednesday

      Like

    • Ruud's avatar

      Ruud 4:14 am on 2 May 2024 Permalink | Reply

      Here’s my solution:

      import itertools


def day_month_to_zodiac(day, month):
    signs = [
        ("capricorn", 19),
        ("aquarius", 18),
        ("pisces", 20),
        ("aries", 19),
        ("taurus", 20),
        ("gemini", 20),
        ("cancer", 22),
        ("leo", 22),
        ("virgo", 22),
        ("libra", 22),
        ("scorpio", 21),
        ("sagittarius", 21),
        ("capricorn",),
    ]
    return signs[month - (day <= signs[month - 1][1])][0]


month_names = "x january febuary march april may june july august september october november december".split()

weekday_names = "monday tuesday wednesday thursday friday saturday sunday".split()

for first_name in "abel bob jedd tim will".split():
    for month, weekday_name in itertools.product(range(1, 13), weekday_names):
        month_name = month_names[month]
        for zodiac_name in (day_month_to_zodiac(1, month), day_month_to_zodiac(31, month)):
            if all(len(set(c0) & set(c1)) == 1 for c0, c1 in itertools.combinations((first_name, month_name, zodiac_name, weekday_name), 2)):
                print(first_name, zodiac_name, month_name, weekday_name)

      Like

    • Frits's avatar

      Frits 11:24 am on 2 May 2024 Permalink | Reply 

       
first_names = "abel bob jedd tim will".split()

zodiac_names = "capricorn aquarius pisces aries taurus gemini cancer " \
               "leo virgo libra scorpio sagittarius".split()

month_names = "january febuary march april may june july august " \
              "september october november december".split()

weekday_names = "monday tuesday wednesday thursday " \
                "friday saturday sunday".split()

# does sequence <x> share exactly one item with all sequences in <g>
share1 = lambda x, g: all(len(set(x).intersection(z)) == 1 for z in g)

sols = []
for m, mo in enumerate(month_names, start=1):
  for zo in (zodiac_names[m - 1], zodiac_names[m % 12]):
    if not share1(zo, [mo]): continue
    for wd in weekday_names:
      if not share1(wd, [mo, zo]): continue
      for nm in first_names:
        if not share1(nm, [mo, zo, wd]): continue
        sols.append((nm, zo))

print(', '.join(x[1] for x in sorted(sols)))

      Like

← Older posts

Newer posts →

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