Updates from January, 2024 Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 1:33 pm on 23 January 2024 Permalink | Reply
    Tags:   

    Teaser 2669: Extending the garden 

    From The Sunday Times, 17th November 2013 [link] [link]

    George and Martha used to have a square garden with sides of length 10 metres, but they have extended it by adding an acute-angled triangle on each side of the square. The result is that the new garden has eight straight sides, each of which is fenced. The fences are different whole number of metres long, with the shortest being one metre and the longest 13 metres. George remarked that the average length of the fences was also a whole number of metres.

    In increasing order, what were the lengths of the eight fences?

    [teaser2669]

     
    • Jim Randell's avatar

      Jim Randell 1:34 pm on 23 January 2024 Permalink | Reply

      If we consider the side of the 10 metre square to be the base of a triangle, then the vertex of the triangle formed by the new fences must lie above the interior of the base, and outside a semicircle whose diameter is the base.

      This Python program finds possible side configurations (for a shorter and longer site, chosen from 1..13), and then combines 4 of these configurations to find viable sets of triangles.

      It runs in 59ms. (Internal runtime is 3.5ms).

      from enigma import (irange, fdiv, sq, disjoint_union, printf)

# generate possible (a, b) extensions
def sides():
  # consider possible sides (from 1 - 13) to make an acute angled triangle
  # the shorter side
  for a in irange(1, 12):
    # the longer side
    for b in irange(max(a + 1, 11 - a), 13):
      # determine vertex points
      x = fdiv(sq(b) - sq(a), 20)
      # vertex must be above base
      if not (x < 5): continue
      x2 = sq(x)
      y2 = sq(b) - sq(x + 5)
      # vertex must lie outside a radius 5 semicircle
      if not (x2 + y2 > 25): continue
      # this is a viable configuration
      yield (a, b)

# generate solutions
def solve(sides, k, ts=list(), ss=set()):
  # are we done?
  if k == 0:
    # mean is an integer
    if sum(ss) % len(ss) != 0: return
    # smallest side is 1, largest is 13
    ss = sorted(ss)
    if not (ss[0] == 1 and ss[-1] == 13): return
    # viable solution
    yield (ts, ss)
  else:
    # add in another triangle
    for (i, t) in enumerate(sides):
      # all sides are different
      ss_ = disjoint_union([ss, t])
      if ss_:
        yield from solve(sides[i:], k - 1, ts + [t], ss_)

# find solutions
rs = set()
for (ts, ss) in solve(list(sides()), 4):
  printf("{ts} -> {ss}")
  rs.add(tuple(ss))

# output solutions
for ss in rs:
  printf("sides = {ss}")

      Solution: The lengths of the fencing are (in metres): 1, 5, 7, 8, 9, 10, 11, 13.

      There are 2 configurations that use this set of fences:

      (1, 10) (5, 9) (7, 8) (11, 13)
      (1, 10) (5, 11) (7, 8) (9, 13)

      Here are examples of these configurations:

      I did consider adding code to ensure the fences could be arranged such that the two fences meeting at the corner were not co-linear, but from the example diagrams it is clear that this can be done in both cases.

      Like

  • Unknown's avatar

    Jim Randell 10:25 am on 21 January 2024 Permalink | Reply
    Tags: by: Chris Maslanka   

    Brainteaser 1389: A redistribution of wealth 

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

    Etherdred the Every-ready had been unwise enough to promise to distribute among his four unworthy sons the contents of an old oak coffer which had subsequently turned out to contain the over-magnanimous sum of 405,405,135,015 talents and nothing else. As his own abacus had only eight significant but venerable beads, he summoned his astrologer, Easirede the Farsighted, for advice.

    “I feel that once my fee is determined, the rest of the problem will fall into place. Let us suppose His Majesty’s generosity extends to granting me X talents, where X is a whole number. I see that His Majesty has already divided all of the money into four unequal heaps, one for each son. Now, adding undoes subtraction. So let us take X talents from Aardman’s heap and put X on to Beergutt’s heap. Also, multiplying undoes division, so let us divide Ceedigrin’s heap by X and mutliply Dampfish’s by X. Each son will then have the same amount. After X talents has been paid to me from the remainder His Majesty can keep the rest”.

    The redistribution was made as the astrologer suggested and he left the castle only to be robbed of his X talents by a disgruntled Aardman a mile down the road.

    How many talents were received by each son under the new distribution?

    [teaser1389]

     
    • Jim Randell's avatar

      Jim Randell 10:26 am on 21 January 2024 Permalink | Reply

      If we start with T talents, and in the end distribute N to each of the 4 sons, and X to the astrologer, then:

      4N + X ≤ T

      And the initial piles were:

      A = N + X
      B = N − X
      C = NX
      D = N/X

      And these are all different positive integers, which sum to T.

      (N + X) + (N − X) + NX + N/X = T
      ⇒
      N = TX / (X + 1)²

      Hence:

      D = N/X = T / (X + 1)²

      So we can determine values for X by looking at squares that are divisors of T.

      from enigma import (divisors, div, printf)

T = 405405135015

# consider divisors of T
for X in divisors(T):
  if X < 2: continue

  # is the square of X also a divisor?
  X2 = X * X
  if X2 > T: break
  d = div(T, X2)
  if d is None: continue
  X -= 1

  # calculate N
  N = X * d

  # and the initial piles
  ps = (N + X, N - X, N * X, div(N, X))
  if any(p is None or p < 1 for p in ps) or len(set(ps)) != 4: continue
  assert sum(ps) == T

  # output solution
  printf("X={X} -> N={N} ps={ps}")

      Solution: Each son received 135045000 talents.

      So each son receives 0.033% of the total.

      And the astrologer receives a modest 3000 talents, which is 0.00000074% of the total.

      And so Etherdred keeps 99.87% of the total.

      Although A mugged the astrologer, C has lost much more by his scheme.

      If we factorise T we get:

      T = 3 × 5 × 3001³

      So we see that X = 3000 is the only viable candidate.

      Like

  • Unknown's avatar

    Jim Randell 4:31 pm on 19 January 2024 Permalink | Reply
    Tags:   

    Teaser 3200: Puzzling sum 

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

    Liam was given a set of addition sums as part of his homework. The teacher had cleverly chosen sums where the answer, together with the two numbers to be added, used all the digits from 1 to 9 just once (and there were no zeros). For instance, one of the sums was 193 + 275 = 468. I noticed that one of them was particularly interesting in that the two numbers to be added were perfect powers (squares, cubes etc).

    In the interesting sum, what are the two numbers that were to be added?

    [teaser3200]

     
    • Jim Randell's avatar

      Jim Randell 4:48 pm on 19 January 2024 Permalink | Reply

      This Python program uses the [[ SubstitutedExpression() ]] solver from the enigma.py library to consider all possible sums that the teacher could have set, and then looks for those with summands that are perfect powers.

      It runs in 87ms.

      from enigma import (
  SubstitutedExpression, decompose, irange, prime_factor,
  mgcd, unpack, sprintf as f
)

# symbols for the 9 different digits
syms = "ABCDEFGHI"

# check a number is a perfect power (> 1)
def is_ipower(n, gcd=unpack(mgcd)):
  if n == 1: return True
  return gcd(e for (p, e) in prime_factor(n)) > 1

# split the symbols into 2 addends and a result (x + y = z)
for (a, b, c) in decompose(len(syms), 3, increasing=1, sep=0, min_v=1, max_v=4):
  # create the sum
  (x, y, z) = (syms[:a], syms[a:a + b], syms[a + b:])
  # create an alphametic puzzle
  exprs = [ f("{x} + {y} = {z}") ]
  if len(x) == len(y): exprs.append(f("{x0} < {y0}", x0=x[0], y0=y[0]))
  p = SubstitutedExpression(
    exprs,
    digits=irange(1, 9),
    answer=f("({x}, {y}, {z})"),
    verbose='',
  )
  # and solve it
  for (x, y, z) in p.answers():
    if is_ipower(x) and is_ipower(y):
      # output solution
      print(f("{x} + {y} = {z}"))

      Solution: The interesting sum is: 243 + 576 = 819.

      And:

      243 = 3^5
      576 = 24^2

      There are 168 possible sums using the digits 1-9, but only this one has summands that are perfect powers. And all of them are of the form: ABC + DEF = GHI.

      Like

      • Jim Randell's avatar

        Jim Randell 8:10 pm on 19 January 2024 Permalink | Reply

        An alternative approach is just to look for two powers that give a sum with the required properties. (The code to generate powers is borrowed from Teaser 3119).

        This Python program has an internal runtime of 1.2ms.

        from enigma import (Primes, nsplit, printf)

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

# check for valid digits, must be all different and not include 0
valid = lambda ds: 0 not in ds and len(set(ds)) == len(ds)

# collect powers
ps = list()
for p in ipowers():
  ds = nsplit(p)
  if len(ds) > 4: break
  if not valid(ds): continue

  # look for a smaller power to pair with this one
  for (p1, ds1) in ps:
    t = p1 + p
    dst = nsplit(t)
    # check all 9 digits used
    ds9 = ds + ds1 + dst
    n = len(ds9)
    if n < 9: continue
    if n > 9: break
    if not valid(ds9): continue
    # output solution
    printf("{p1} + {p} = {t}")

  # record this power
  ps.append((p, ds))

        I will add the [[ ipowers() ]] function to the enigma.py library (from version 2024-01-19).

        Like

        • Frits's avatar

          Frits 1:53 am on 20 January 2024 Permalink | Reply

          @Jim, did you forget to check dst for zeroes?

          Like

        • Brian Gladman's avatar

          Brian Gladman 6:53 pm on 20 January 2024 Permalink | Reply

          @Jim. That is a very neat subroutine for generating integer powers in order.

          Like

        • Brian Gladman's avatar

          Brian Gladman 9:21 pm on 21 January 2024 Permalink | Reply

          @Jim, I looked at alternatives to your ipowers() routine and found this quite a bit faster:

          from heapq import heappush, heappop

def ipowers(maths=True):
  if maths:
    yield 0
    yield 1
  heap, pv, m = [], None, 2
  heappush(heap, (2 ** 2, 2, 2))
  while True:
    m += 1
    v = 2 ** m
    while heap[0][0] <= v:
      (v1, n1, m1) = heappop(heap)
      if v1 != v and v1 != pv:
        yield v1
        pv = v1
      heappush(heap, ((n1 + 1) ** m1, n1 + 1, m1))
    heappush(heap, (2 ** m, 2, m))

          Like

          • Jim Randell's avatar

            Jim Randell 10:37 am on 22 January 2024 Permalink | Reply

            @Brian: Yes, using a heap is faster (especially in CPython which I think has heaps implemented via a C module).

            So, this is even faster:

            from heapq import (heapify, heappush, heappop)

def ipowers():
  # powers less than 4
  yield 0
  yield 1

  # powers from 4 upwards
  hi = 1
  maxe = 2
  pows = [(4, 2, 2)]
  heapify(pows)
  exps = Primes(35, expandable=1).generate(3)
  while True:
    # find the next power
    (p, b, e) = heappop(pows)
    if p > hi:
      yield p
      hi = p
    heappush(pows, (pow(b + 1, e), b + 1, e))
    # do we need to add in a new exponent?
    if b == 2:
      maxe = next(exps)
      heappush(pows, (pow(2, maxe), 2, maxe))

            Liked by 1 person

            • Brian Gladman's avatar

              Brian Gladman 9:02 am on 23 January 2024 Permalink | Reply

              It is faster if you don’t count the cost of the extra import of Primes() which dwarfs the running cost for low power limits. Including import cost for powers below 1000 I measured 338 microseconds and 2.5 milliseconds on CPython. In my test, it overtakes the non-import version at a power limit of about 10^9.

              Like

            • Jim Randell's avatar

              Jim Randell 1:47 pm on 23 January 2024 Permalink | Reply

              I was more interested in algorithmic efficiency, so I was testing by generating the first 5 million perfect powers, and using primes for exponents was a clear winner on all the Python environments I tested.

              I generally have the enigma module loaded, so there is essentially no overhead in using the primes generator, but the candidate exponents can be any superset of the primes (as the algorithm will discard duplicates), so you can use something like [[ irange(3, inf, step=2) ]] if you don’t want to use primes, and still get a performance improvement.

              Like

    • GeoffR's avatar

      GeoffR 6:55 pm on 19 January 2024 Permalink | Reply 

      from enigma import nsplit

# A manual search for all three digit powers gave the following list
d3_powers = [125, 128, 216, 243, 256, 512, 529, 576, 625, 729, 784, 961]

for r in range(123, 987):  # result of the sum
  g, h, i = nsplit(r)
  if len(set((g, h, i))) != 3:continue
  if r in d3_powers:continue
  
  # find the two summands, which must both be powers
  for n in d3_powers:
    for m in d3_powers:
      if n == m:continue
      a, b, c = nsplit(n)
      d, e, f = nsplit(m)
      if len(set((a, b, c, d, e, f))) == 6:
        if m + n == r:
          if m > n and len(set((a,b,c,d,e,f,g,h,i))) == 9:
            print(f"The sum is {m} + {n} = {r}.")

      Like

    • GeoffR's avatar

      GeoffR 8:27 pm on 19 January 2024 Permalink | Reply

      Seems faster to use the remaining digits, after the two squares, for the addition result.

      
from enigma import nsplit

# A manual search for all three digit powers gave the following list
d3_powers = [125, 128, 216, 243, 256, 512, 529, 576, 625, 729, 784, 961]

# find the two summands, which must both be powers
for n in d3_powers: 
    for m in d3_powers:
      if n == m:continue
      a, b, c = nsplit(n)
      d, e, f = nsplit(m)
      if len(set((a, b, c, d, e, f))) == 6:
        
        # find result of additon from remaining digits
        g, h, i = set(range(1,10)).difference((set((a, b, c, d, e, f))))
        if len(set((g, h, i))) != 3:continue
        r = 100*g + 10*h + i
        if r in d3_powers:continue
        if m + n == r:
          if m > n and len(set((a, b, c, d, e, f, g, h, i))) == 9:
            print(f"The sum is {m} + {n} = {r}.")

      Like

    • GeoffR's avatar

      GeoffR 2:50 pm on 22 January 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;

var 100..999:ABC == 100*A + 10*B + C;
var 100..999:DEF == 100*D + 10*E + F;
var 100..999:GHI == 100*G + 10*H + I;

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

constraint ABC + DEF == GHI;

set of int: powers == {125,128,216,243,256,512,529,576,625,729,784,961};  

constraint ABC > DEF /\ ABC in powers /\ DEF in powers;

solve satisfy;
output ["Sum is " ++ show(ABC) ++ " + " ++ show(DEF) ++ " = " ++ show(GHI)];

      Like

  • Unknown's avatar

    Jim Randell 3:09 pm on 15 January 2024 Permalink | Reply
    Tags:   

    Teaser 2666: Multiple calls 

    From The Sunday Times, 27th October 2013 [link] [link]

    In my office each of the 100 employees has a different two-digit phone number, from 00 to 99. Recently my phone was rewired so that each number button generated an incorrect digit. Trying to phone four of my colleagues resulted in me calling double the intended number, and, for more than ten of my colleagues, trying to phone their number resulted in me calling triple the intended number. Also if I tried to phone any colleague and then asked for their phone number, then phoned that number and asked that person for their number, then phoned that number … and so on, it always took ten calls to contact the person I intended.

    If I tried to phone the numbers 01, 23, 45, 67 and 89 respectively, which numbers would I actually get?

    [teaser2666]

     
    • Jim Randell's avatar

      Jim Randell 3:09 pm on 15 January 2024 Permalink | Reply

      Numbers that map to their double must be in the range 01 – 49, and numbers that map to their triple in the range 01 – 33, and we need more than 10 of them.

      If start with any number we always get a chain of 10 numbers before we reach the intended number. So the reassignment of digits must form a complete (length 10) cycle.

      We could generate all possible complete cycles and look for any that meet the remaining conditions, but this is a slow approach (although quite short to program).

      This Python program considers possible mappings that give 11 or more numbers that map to their triple, and then attempts to fill out the remaining values such that a complete cycle is formed.

      It runs in 73ms. (Internal runtime is 9.9ms).

      from enigma import (irange, diff, subsets, peek, map2str, printf)

digits = list(irange(0, 9))

# check a mapping is a complete cycle
def is_cycle(m):
  if not m: return
  k = peek(m.keys())
  (v, n) = (m[k], 1)
  while v != k:
    v = m[v]
    n += 1
  return n == len(m.keys())

# update a mapping
def update(m, ks, vs):
  m = m.copy()
  for (k, v) in zip(ks, vs):
    # must be a derangement
    if k == v: return
    # existing key
    if k in m:
      if m[k] != v: return
    else:
      # new key
      if v in m.values(): return
      # make the update
      m[k] = v
  return m

# construct mappings with more than 10 triples
def solve(k=0, m=dict(), ts=set()):
  # are we done?
  if k > 33:
    if len(ts) > 10:
      yield m
  else:
    # consider mapping k -> 3k
    m_ = update(m, divmod(k, 10), divmod(3 * k, 10))
    if m_:
      yield from solve(k + 1, m_, ts.union({k}))
    # or not
    if m_ != m:
      yield from solve(k + 1, m, ts)

# look for potential mappings
for r in solve():
  # map remaining keys to remaining values
  ks = diff(digits, r.keys())
  vs = diff(digits, r.values())
  for ss in subsets(vs, size=len, select='P'):
    m = update(r, ks, ss)
    # the map must form a complete cycle
    if not is_cycle(m): continue
    # find doubles and triples
    (ds, ts) = (list(), list())
    for k in irange(0, 49):
      (a, b) = divmod(k, 10)
      v = 10 * m[a] + m[b]
      if v == 2 * k: ds.append(k)
      if v == 3 * k: ts.append(k)
    # we need exactly 4 doubles and more than 10 triples
    if not (len(ds) == 4 and len(ts) > 10): continue
    # output solution
    printf("{m}", m=map2str(m, arr="->", enc=""))
    printf("doubles = {ds}")
    printf("triples = {ts}")
    printf()

      Solution: 01 → 13; 23 → 69; 45 → 20; 67 → 84; 89 → 57.

      So the 4 numbers that map to their doubles are:

      05 → 10
      07 → 14
      15 → 30
      17 → 34

      and the 11 numbers that map to their triples are:

      04 → 12
      06 → 18
      11 → 33
      12 → 36
      13 → 39
      21 → 63
      22 → 66
      23 → 69
      31 → 93
      32 → 96
      33 → 99

      Like

    • Frits's avatar

      Frits 2:34 pm on 19 January 2024 Permalink | Reply

      Nice solution.

      I also tried the same setup starting with mappings of exactly 4 doubles but that was a lot slower.
      I can’t find the “Run” button anymore when using the replit link.

      Like

      • Jim Randell's avatar

        Jim Randell 5:38 pm on 19 January 2024 Permalink | Reply

        It looks like replit have changed their interface so you can no longer directly run someone else’s code. Now you need to fork it to your own account before you can run it.

        This means you can no longer use replit to share code as easily as before, which is a bit annoying.

        Like

  • Unknown's avatar

    Jim Randell 4:54 pm on 12 January 2024 Permalink | Reply
    Tags:   

    Teaser 3199: County cup 

    From The Sunday Times, 14th January 2024 [link] [link]

    In our county football competition, fewer than 100 teams compete in two stages. First, the teams are allocated to more than two equally-sized groups, and in each group there is one match between each pair of teams. The top two teams in each group proceed to the first round of the knockout stage, where a single match between two teams eliminates one of them. If the number of teams entering the knockout stage is not a power of 2, sufficiently many teams are given byes (they don’t have to play in the first round), so that the number of teams in the second round is a power of 2. The knockout stage continues until only one team remains. In one year the competition was played with a single match on every day of the year.

    How many teams were in the competition that year?

    [teaser3199]

     
    • Jim Randell's avatar

      Jim Randell 5:40 pm on 12 January 2024 Permalink | Reply

      (See also: Teaser 2965, Enigma 1067, Enigma 1169, Enigma 1276, Enigma 176, Enigma 1398).

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

      from enigma import (irange, C, printf)

# consider number of groups in stage 1
for k in irange(3, 33):
  # consider number of teams per group
  for g in irange(3, 99 // k):
    # number of matches in stage 1 (in each group each pair plays)
    m1 = k * C(g, 2)
    # stage 2: the top 2 teams from each group progress to knockout
    q = 2 * k
    # number of matches in stage 2 (1 team is eliminated in each match)
    m2 = q - 1
    # total number of matches in the tournament
    t = m1 + m2
    if t in {365, 366}:
      printf("[{n} teams]", n=k * g)
      printf("stage 1: {k} groups of {g} teams = {m1} matches")
      printf("stage 2: {q} teams = {m2} matches")
      printf("total = {t} matches")
      printf()

      Solution: There were 48 teams in the tournament.

      Stage 1 consisted of 3 groups, each with 16 teams. In each group there were 120 matches. So stage 1 consisted of 360 matches.

      Stage 2 consisted of 6 teams (the top 2 teams from each of the 3 groups), so 5 matches were played to find the winner of the tournament. (2 matches in the first round, leaving 4 teams in the second round. 2 matches in the second round (semi-finals), leaving 2 teams to play in the final match).

      In total there were 365 matches.

      If there was an additional match for 3rd/4th place in the tournament there would be 1 extra match, which would bring the total to 366, but this could be played one match per day in a leap year, so the answer remains the same.

      With a bit of analysis:

      If M is the total number of matches, we get:

      k.g(g − 1)/2 + (2k − 1) = M
      ⇒
      k(g(g − 1) + 4) = 2(M + 1)

      And in this case we are looking for solutions where M = 365 or 366.

      So k is a divisor of 732 or 734 (k ≥ 3), and the remainder is g(g − 1) + 4 (which has a minimum value of 10).

      The only options are:

      M=365: k = 3, 4, 6, 12, 61.

      And only one of these gives a viable g value.

      from enigma import (divisors_pairs, quadratic, printf)

# look for total number of matches = M
def solve(M):
  # consider possible k values
  for (k, x) in divisors_pairs(2 * (M + 1), every=1):
    if k < 3 or x < 10: continue
    # look for possible g values
    for g in quadratic(1, -1, 4 - x, domain='Z', include='+'):
      if g < 3: continue
      printf("M={M}: k={k} g={g} -> n={n}", n=k * g)

# consider possible total numbers of matches
solve(365)
solve(366)

      Like

    • Frits's avatar

      Frits 7:29 pm on 12 January 2024 Permalink | Reply 

          
# next higher power (<= 128)
nhp = lambda n: [x for x in [2 ** i for i in range(1, 8)] if x >= n][0]

# we have a least 3 groups of at least 2 players
for n in range(6, 100):
  # the teams are allocated to more than two equally-sized groups
  divpairs = {(i, n // i) for i in range(2, int(n**.5) + 1) if n % i == 0}
  # for divisor pair (a, b) add pair (b, a)
  divpairs |= {(d2, d1) for d1, d2 in divpairs}
  divpairs = [(d1, d2) for d1, d2 in divpairs if d1 > 2]
  
  for ngrps, grpsz in divpairs:
    # number of games in stage 1 = ngrps * (grpsz * (grpsz - 1) // 2)
    # number of byes = next higher power - 2 * ngrps
    # tot = number of games in stage 1 plus (next power - 1 - number of byes)
    if ngrps * (grpsz * (grpsz - 1) // 2 + 2) - 1 in {365, 366}:
      print(f"answer: {n} teams")

      Like

    • Brian Gladman's avatar

      Brian Gladman 10:32 pm on 12 January 2024 Permalink | Reply

      I am not getting a solution (here) because I constrain the number of teams in round two to be a power of two by adding byes. Am I misreading the need for this constraint?

      Like

      • Brian Gladman's avatar

        Brian Gladman 1:21 am on 13 January 2024 Permalink | Reply

        I did misinterpret this.

        Like

      • Jim Randell's avatar

        Jim Randell 9:50 am on 13 January 2024 Permalink | Reply

        Although byes are used in the first round of stage 2 (the knockout stage), you don’t need to worry about them. In a knockout tournament each match eliminates 1 team, so starting with n teams you get down to 1 team after (n − 1) matches. (And if there is a match to determine 3rd/4th place there will be n matches in total).

        Like

        • Brian Gladman's avatar

          Brian Gladman 10:18 am on 13 January 2024 Permalink | Reply

          Thanks Jim, I did eventually figure out how it works. Thanks for correcting my link (but it is not very useful now since I have changed my code).

          Like

        • Guy's avatar

          Guy 11:04 am on 15 January 2024 Permalink | Reply

          Unfortunately, unlike Brian, I’m still confused.
          I think you have an unusual knockout tournament when there is not a power of 2 (eg 6) number of teams. With 6 teams in the Knockout Stage, the two teams in the final game will have played a different number of games in the Knockout Stage.
          The question appears to require that the Knockout Stage must have a power of 2 number of teams. So the number of groups determines the number of Stage One byes required. With 48 teams and 3 groups, you would get 6 teams (2 per Stage One group) through the Stage One route and need additional 2 byes to make up to 8 (next Power of 2) teams for the Knockout Stage. The teams with byes don’t play a game in Stage One. Hence the adjusted, now unequal, Stage One groups would be either 15,15,16 or 14,16,16. Total games would then be 337 (330+7) or 338 (331+7).

          Like

        • Jim Randell's avatar

          Jim Randell 1:41 pm on 15 January 2024 Permalink | Reply

          Here’s an example of how the tournament would work with 10 groups in stage 1 (so there would be 30, 40, 50, …, 90 teams in total).

          2 teams from each group proceed to stage 2 (the knockout stage), so there are 20 teams entering stage 2.

          But 20 is not a power of 2, so in the first round (of stage 2) we play pairs of teams against each other until the number of teams remaining is a power of 2.

          So in the example, 2 teams play, 1 is eliminated and 1 goes through to the second round (of stage 2), and there are 19 teams left in the tournament. This still isn’t a power of two, so another 2 teams play, 1 is eliminated and 1 goes through to the second round. And there are 18 teams left. Another 2 play, and there are 17 teams left. Another 2 play and there are 16 teams left, which is a power of 2.

          So, after 4 matches in round 1 of the knockout stage there are 16 teams remaining. The 12 teams that are still in round 1 are all given byes to round 2, and so there are 16 teams in round 2, so we have 8 matches in round 2, the winners go through to round 3, so there are 4 matches in round 3, 2 matches in round 4, and 1 (the final) match in round 5.

          The total number of matches in the knockout stage was: 4 + 8 + 4 + 2 + 1 = 19.

          But the simpler way to look at it is that one team is eliminated from the tournament with each knockout match, and we start with 20 teams, so after 19 matches there is only 1 team remaining (the winner).

          Like

          • Guy's avatar

            Guy 2:14 pm on 15 January 2024 Permalink | Reply

            OK, finally got it, thank you! Re-reading the question, the first round in “(they don’t have to play in the first round)” refers to first round of Knockout Stage, not the Group Stage. Following you help, it’s annoyingly obvious now.

            [The alternative problem with byes in Group Stage was still fun. Would have 99 teams split into 11 groups, you need to give 10 byes, so a possible arrangement for the 11 groups could be (3, 6, 8, 9, 9, 9, 9, 9, 9, 9, 9). The knockout stage then begins with 32 teams (11×2 from Group Stage plus the 10 byes).]

            Like

  • Unknown's avatar

    Jim Randell 8:39 am on 9 January 2024 Permalink | Reply
    Tags:   

    Teaser 2198: Developing houses 

    From The Sunday Times, 31st October 2004 [link]

    My Uncle Silas is a property developer. He recently bought some properties along a street of fewer than 400 houses. The odd-numbered houses were on the left side of the street, and the even-numbered houses were on the right. He bought eight adjacent houses on the left side of the street and seven adjacent houses on the right side. The sum of the house numbers on the left was a perfect square and was the same as the sum of the house numbers on the right.

    What was the largest house number that he bought?

    1000 Teasers and nearly 20 years ago.

    [teaser2198]

     
    • Jim Randell's avatar

      Jim Randell 8:40 am on 9 January 2024 Permalink | Reply

      I assumed that the houses are numbered consecutively, starting with 1.

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

      from enigma import (irange, tuples, is_square, intersect, printf)

# find <k> numbers from <seq> that sum to a perfect square
def numbers(k, seq):
  # collect sequences by sum
  d = dict()
  for ns in tuples(seq, k):
    s = sum(ns)
    if is_square(s):
      d[s] = ns
  return d

# find 8 adjacent odd numbers that sum to a perfect square
odd = numbers(8, irange(1, 399, step=2))

# find 7 adjacent even numbers that sum to a perfect square
even = numbers(7, irange(2, 399, step=2))

# and look for common sums
for k in intersect([odd.keys(), even.keys()]):
  printf("{k} = {r}^2", r=is_square(k))
  printf("{k} = {ns}", ns=odd[k])
  printf("{k} = {ns}", ns=even[k])
  printf()

      Solution: The largest numbered house bought was number 118.

      The houses bought were:

      odds = (91, 93, 95, 97, 99, 101, 103, 105), sum = 784 (= 28^2)
      evens = (106, 108, 110, 112, 114, 116, 118), sum = 784 (= 28^2)

      If the first odd number is (2a + 1), then the odd numbers are:

      (2a + 1, 2a + 3, 2a + 5, 2a + 7, 2a + 9, 2a + 11, 2a + 13, 2a + 15)
      sum = 16a + 64 = 16(a + 4)

      And this sum is a square, so (a + 4) must be a square number:

      If the first even number is 2b, then the even numbers are:

      (2b, 2b + 2, 2b + 4, 2b + 6, 2b + 8, 2b + 10, 2b + 12)
      sum = 14b + 42

      And the sums are equal:

      16a + 64 = 14b + 42
      b = (8a + 11) / 7

      So we can consider possible square numbers for (a + 4) and look for corresponding b values that are integers.

      This can be investigated manually or programatically:

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

# output a list of numbers, sum, and sqrt(sum)
def output(t, ns):
  s = sum(ns)
  r = is_square(s)
  printf("-> {t} = {ns} = {s} (= {r}^2)")

# consider squares for (a + 4) = i^2
for i in irange(2, inf):
  a = sq(i) - 4
  # calculate b
  (b, r) = divmod(8 * a + 11, 7)
  if 2 * b + 12 > 399: break
  if r != 0: continue
  # output solution
  printf("a={a} b={b}")
  output('odds', list(irange(2 * a + 1, 2 * a + 15, step=2)))
  output('evens', list(irange(2 * b, 2 * b + 12, step=2)))

      There is only one a value that gives an integer value for b:

      sum = 16×49 = 784
      a = 45, b = 53

      Which gives rise to the two sequences given above.

      Like

      • Frits's avatar

        Frits 10:44 pm on 9 January 2024 Permalink | Reply

        b = (8a + 11) / 7 = (8 * (i^2 – 4) + 11) / 7 = (8 * i^2) / 7 – 3

        so i^2 must be divisible by 7 and
        as variable a can be seen to be less than 168.375 only i = 7 is an option
        leading to b = 53 and 2b + 12 = 118

        Like

    • John Crabtree's avatar

      John Crabtree 4:25 am on 10 January 2024 Permalink | Reply

      Let L and R be the integer averages on the left and right sides of the street.
      8L = 7R = n^2, which is less than 2800, ie n < 53.
      n = 0 (mod (4 * 7)) = 0 (mod 28), and so n = 28 and R = 112.
      The highest house number = 112 + 6 = 118.

      Like

    • GeoffR's avatar

      GeoffR 7:33 pm on 12 January 2024 Permalink | Reply 

      
from math import isqrt

def is_sq(x):
   return isqrt(x) ** 2 == x

# Eight odd numbers on left side of the street
for n in range(1, 400, 2):
    L1, L2 = [], []
    L1 = [n, n+2, n+4, n+6, n+8, n+10, n+12, n+14]
    if not is_sq(sum(L1)):
        continue
    # Seven even numbers on right side of the street
    for m in range(2, 402, 2):
       L2 = [m, m+2, m+4, m+6, m+8, m+10, m+12]
       if sum(L2) == sum(L1):
          # Find  the largest house number
          if n+14 > m+12:
             print('Largest house mumber = ', n+14)
          else:
             print('Largest house mumber = ', m+12)
               
# Largest house mumber =  118

      Like

  • Unknown's avatar

    Jim Randell 12:36 pm on 7 January 2024 Permalink | Reply
    Tags:   

    Teaser 2668: Small cubes 

    From The Sunday Times, 10th November 2013 [link] [link]

    Oliver and Megan each had a different- sized cuboid whose sides were all whole numbers of centimetres in length. Their cuboids were painted all over. They each cut their cuboid into one-centimetre cubes, some of which were unpainted, the rest being painted on one or more face. Oliver observed that for both cuboids, the number of cubes with no painted faces was the same as the number with two painted faces. Then Megan added: “I have more cubes than you, and the difference between our totals is equal to the number of your unpainted cubes”.

    How many of Megan’s cubes had just one painted face?

    [teaser2668]

     
    • Jim Randell's avatar

      Jim Randell 12:37 pm on 7 January 2024 Permalink | Reply

      Consider a cubiod with dimensions a × b × c. Then we can calculate the number of cubelets that are painted on the required number of faces:

      3 faces = 8
      2 faces = 4(a + b + c − 6)
      1 face = 2((a − 2)(b − 2) + (a − 2)(c − 2) + (b − 2)(c − 2))
      0 faces = (a − 2)(b − 2)(c − 2)

      providing the smallest dimension is greater than 1.

      And as some of the cubelets are unpainted the cuboids we are interested in must have smallest dimension of at least 3.

      This Python program runs in 56ms. (Internal runtime is 335µs).

      from enigma import (defaultdict, irange, inf, decompose, map2str, printf)

# total number of faces is indicated by key 7
total = 7

# for a cuboid of dimensions a x b x c
# return number of cubelets by faces painted, and the total number of cubelets
def cubelets(a, b, c):
  assert min(a, b, c) > 1
  r = dict()
  r[3] = 8
  r[2] = 4 * (a + b + c - 6)
  r[0] = (a - 2) * (b - 2) * (c - 2)
  t = a * b * c
  r[1] = t - sum(r.values())
  r[total] = t
  return r

def solve():
  # collect cubes by total
  g = defaultdict(list)
  # consider increasing a + b + c dimensions
  for s in irange(3, inf):
    # consider cuboids for M
    for (a, b, c) in decompose(s, 3, increasing=-1, sep=0, min_v=3):
      # calculate number of cubelets
      r = cubelets(a, b, c)
      # we are interested in those cubes where r[0] = r[2]
      if not (r[2] == r[0] > 0): continue

      # consider smaller totals (for O)
      for (k, vs) in g.items():
        # difference between totals
        d = r[total] - k
        if d < 1: continue
        for (r_, (a_, b_, c_)) in vs:
          if r_[0] == d:
            # return (M, O) as (cubelets, dimensions)
            yield ((r, (a, b, c)), (r_, (a_, b_, c_)))
      # record this cuboid
      g[r[total]].append((r, (a, b, c)))

# find possible (M, O) values
for ((r, (a, b, c)), (r_, (a_, b_, c_))) in solve():
  fmt = lambda r: map2str(r, arr='->', enc="")
  printf("M = {a} x {b} x {c} [{r}]; O = {a_} x {b_} x {c_} [{r_}]", r=fmt(r), r_=fmt(r_))
  break  # only need the first answer

      Solution: Megan has 112 cubelets painted on just one face.

      Megan has a cuboid with dimensions: 12 × 5 × 4.

      12 × 5 × 4 = 240 cubelets
      8 painted on 3 faces
      60 painted on 2 faces
      112 painted on 1 face
      60 painted on 0 faces

      Oliver has a cuboid with dimensions: 8 × 6 × 4.

      8 × 6 × 4 = 192 cubelets
      8 painted on 3 faces
      48 painted on 2 faces
      88 painted on 1 face
      48 painted on 0 faces

      And:

      240 − 192 = 48

      If cuboids with a dimensions less than 3 were allowed, then we can find further solutions using cuboids that give 0 unpainted cubelets, such as:

      Oliver = 8 × 6 × 4 (= 192 cubelets, 48 unpainted, 48 painted on 2 faces)
      Megan = 120 × 2 × 1 (= 240 cubelets, 0 unpainted, 0 painted on 2 faces)

      Like

  • Unknown's avatar

    Jim Randell 4:42 pm on 5 January 2024 Permalink | Reply
    Tags:   

    Teaser 3198: The sixth element 

    From The Sunday Times, 7th January 2024 [link] [link]

    Agent J discovered that S.P.A.M.’s IQ booster drug comprises five elements with atomic numbers Z under 92. Some information had been coded as follows: Z1[4;6], Z2[1;4], Z3[4;6], Z4[0;6] and Z5[7;2], where Z5 is lowest and Z3 is highest. Code key: [Remainder after dividing Z by 8; Total number of factors of Z (including 1 and Z). The drug’s name is the elements’ chemical symbols concatenated in encoded list order.

    J subsequently discovered the Z3 and Z5 values. Now MI6 had just fifteen possible sets of atomic numbers to consider. Finally, J sent a sixth element’s prime Z value (a catalyst in the drug’s production, not part of it). She’d heard it was below Z1 and above Z2, without knowing these. MI6 boffins were now sure of the drug’s name.

    Give the catalyst’s atomic number.

    [teaser3198]

     
    • Jim Randell's avatar

      Jim Randell 5:05 pm on 5 January 2024 Permalink | Reply

      This Python program checks that the six Z numbers are all different (although this is not explicitly stated in the puzzle text, but it seems like a reasonable additional requirement).

      It runs in 55ms. (Internal runtime is 711µs).

      from enigma import (
  defaultdict, irange, tau, group, cproduct, primes,
  singleton, printf
)

# map Z numbers to code
code = lambda z: (z % 8, tau(z))

# group Z numbers by code
g = group(irange(1, 91), by=code)

# choose a sequence from the given codes
codes = [(4, 6), (1, 4), (4, 6), (0, 6), (7, 2)]

# collect possible sequences by (z3, z5) values
d = defaultdict(list)
for (z1, z2, z3, z4, z5) in cproduct(g[k] for k in codes):
  if len({z1, z2, z3, z4, z5}) != 5: continue
  # z5 is the lowest
  if not (z5 < min(z1, z2, z3, z4)): continue
  # z3 is the highest
  if not (z3 > max(z1, z2, z4, z5)): continue
  d[(z3, z5)].append((z1, z2, z3, z4, z5))

# knowing z3 and z5 gives 15 possible sequences
for (k, vs) in d.items():
  if len(vs) != 15: continue
  # consider possible prime z6 values
  for z6 in primes.between(1, 91):
    # look for matching sequences
    check = lambda z1, z2, z3, z4, z5: z2 < z6 < z1 and z6 != z4
    zs = singleton(zs for zs in vs if check(*zs))
    if zs is None: continue
    # output solution
    printf("z6={z6} -> zs={zs}")

      Solution: The catalyst has atomic number 47.

      The constituent elements (Z1..Z5) have atomic numbers: 52, 33, 68, 32, 7.

      So, the name of the drug is: TEASERGEN (= Te As Er Ge N).

      And the catalyst (Z6) has atomic number 47 (= Ag (Silver)).

      Like

    • NigelR's avatar

      NigelR 12:48 pm on 7 January 2024 Permalink | Reply

      A bit convoluted but it seems to work!!

      from itertools import product

def is_prime(n):
    if (n % 2 == 0 and n > 2) or n < 2: return False
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0: return False
    return True

factno = lambda n: len([i for i in range(1, n + 1) if n % i == 0])
zvals = lambda a,b: [i for i in range(1,92) if i%8 == a and factno(i) == b] 
#Code values for z1 - z5
Z = [[4,6], [1,4], [4,6], [0,6], [7,2]]
#create dictionary d with lists of possible values for each element
d = {i:zvals(x[0],x[1]) for i,x in enumerate(Z,1)}
#create cand as list with valid sets of element values
cand = []
for x in (dict(zip(d.keys(), values)) for values in product(*d.values())):
    #z3 is highest, z5 is lowest and 5 different elements
    if x[3] != max(vals:= x.values()) or len(set(vals)) != 5 or x[5] != min(vals): continue
    else: cand.append(x)
#remove duplicates and create list of valid x3 & x5
z3z5 = [list(tupl) for tupl in {tuple(item) for item in [[x[3],x[5]] for x in cand]}]
#Find z3z5 entry that has 15 possible sets
res = [x for x in z3z5 if len([y for y in cand if y[3]==x[0] and y[5]==x[1]])==15 ]
if len(res)>1 :
    print('unique solution not found')
    exit()
else:
    res = res[0] #flatten res to list of selected x3 & x5
#strip invalid sets from cand
cand = [x for x in cand if x[3]==res[0] and x[5]==res[1]]
z6lst=[]
#look for possible prime values of z6 between z2 and z1
for x in cand:
    if x[2]>x[1]:continue
    for y in range(x[2]+1,x[1]): 
        if is_prime(y):
            z6lst.append([y,x])
z6set = [x[0] for x in z6lst]
#look for singleton value of z6
z6 = [x for x in z6set if z6set.count(x)==1]
if len(z6)==1:
    z6 = z6[0]
else:
    print('unique solution not found')
    exit()
soltn = [x for x in z6lst if x[0]==z6][0]
print(f'Catalyst atomic number was {soltn[0]}.')
outstr = 'Z' + '  Z'.join([str(i)+' = '+ str(soltn[1][x]) for i,x in enumerate (soltn[1],1)])
print('Element values were: ', outstr,'.')

      Like

  • Unknown's avatar

    Jim Randell 7:51 am on 2 January 2024 Permalink | Reply
    Tags:   

    Teaser 2667: Prime time 

    From The Sunday Times, 3rd November 2013 [link] [link]

    On a picture of a clock face I have written A next to one of the numbers. Then I counted a certain number of “hours” clockwise and wrote B. Then I continued in this pattern, always counting the same number of places clockwise and writing the next letter of the alphabet. In this way each letter corresponds to a number between 1 and 12. I noticed that the two numbers with three letters by them were prime. I also noticed that if I wrote the numbers corresponding to the letters of PRIME in order and read them as one long number, then I got a 6-digit prime.

    Which number corresponds to A and which to B?

    [teaser2667]

     
    • Jim Randell's avatar

      Jim Randell 7:52 am on 2 January 2024 Permalink | Reply

      This Python program runs in 60ms. (Internal runtime is 2.1ms).

      from enigma import (
  str_upper, clock, cproduct, irange, inf, multiset, concat, is_prime,
  map2str, printf
)

# the letters to distribute
letters = str_upper

# calculate clock values (1-12)
fn = clock(12)

# choose a starting number and a step
for (A, n) in cproduct([irange(1, 12), irange(1, 11)]):
  # assign values to the letters
  d = dict((k, fn(v)) for (k, v) in zip(letters, irange(A, inf, step=n)))

  # find the values that correspond to 3 letters
  m = multiset.from_seq(d.values())
  k3s = list(k for (k, v) in m.items() if v == 3)
  # there are exactly 2 values, and each is prime
  if not (len(k3s) == 2 and all(is_prime(k) for k in k3s)): continue

  # collect the values corresponding to PRIME
  vs = list(d[k] for k in 'PRIME')
  # does it form a 6-digit prime number
  p = concat(vs)
  if not (len(p) == 6 and is_prime(int(p))): continue

  # output solution
  printf("A={A} n={n} p={p} [{d}]", d=map2str(d, sep=" ", enc=""))

      Solution: A = 7. B = 2.

      So we start at 7 = A and advance 7 hours for each letter.

      The assignment of letters to values is:

      1 = GS
      2 = BNZ
      3 = IU
      4 = DP
      5 = KW
      6 = FR
      7 = AMY
      8 = HT
      9 = OC
      10 = JV
      11 = EQ
      12 = LX

      The values corresponding to three letters being 2 and 7 (both prime).

      And we have:

      PRIME = 4:6:3:7:11

      Which corresponds to the 6-digit prime 463711.

      Like

  • Unknown's avatar

    Jim Randell 11:17 am on 31 December 2023 Permalink | Reply
    Tags:   

    Brain teaser 988: Pythagoras was never like this 

    From The Sunday Times, 28th June 1981 [link]

    In accordance with tradition the retiring President of the All Square Club set members a special competition. Titled as above, it required new meanings for the signs “+” and  “=” as in:

    6² + 1² = 19²

    indicating that both sides could be taken to represent 361.

    The number 361 was then called a “Special Pythogorean Square” (SPS) and the numbers 36 and 1 its “contributing squares”.

    Other examples given were:

    7² + 27² = 223²
    15² + 25² = 475²

    giving 49729 and 225625 as Special Pythogorean Squares.

    Members were invited to submit series of Special Pythogorean Squares which they could claim to be unique in some way. Each number in their series had to be less than a million, and no two numbers in their series could have the same number of digits.

    After much deliberation the prize was awarded to the member who submitted a series of Special Pythogorean Squares which he correctly claimed was the longest possible list of such numbers all with the same second contributing square.

    What (in increasing order) were the numbers in the winning series?

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

    [teaser988]

     
    • Jim Randell's avatar

      Jim Randell 11:17 am on 31 December 2023 Permalink | Reply

      So we treat “+” and “=” as string operations, being concatenation and equality respectively.

      This Python program generates all SPSs below 1 million, and then constructs maximal length sequences which share the same suffix square.

      It runs in 61ms. (Internal runtime is 2ms).

      from enigma import (
  defaultdict, Accumulator, irange, inf, sq, cproduct, join, printf
)

# generate SPSs
def generate(N):
  # record squares (as strings)
  d = dict()
  for i in irange(0, inf):
    n = sq(i)
    if not (n < N): break
    s = str(n)
    d[s] = i

    # split the square into prefix and suffix
    for j in irange(1, len(s) - 1):
      (pre, suf) = (s[:j], s[j:])
      (pi, si) = (d.get(pre), d.get(suf))
      if pi is None or si is None: continue
      printf("[{n} = {pre} + {suf} -> {i}^2 = {pi}^2 + {si}^2]")
      yield (s, pre, suf)

# collect SPSs: <suffix> -> <length> -> [<SPS>...]
d = defaultdict(lambda: defaultdict(list))
for (s, pre, suf) in generate(1000000):
  d[suf][len(s)].append(s)

# find maximal length sequences sharing the same suffix
r = Accumulator(fn=max, collect=1)
for (suff, v) in d.items():
  r.accumulate_data(len(v.keys()), suff)
printf("maximal sequence length = {r.value}")

# output maximal length sequences
for k in r.data:
  printf("suffix = {k}")
  for ss in cproduct(d[k].values()):
    printf("-> {ss}", ss=join(ss, sep=", ", enc="()"))

      Solution: The winning series was: 49, 169, 3249, 64009, 237169.

      Which are constructed as follows:

      49 = 4 + 9 → 7^2 = 2^2 + 3^2
      169 = 16 + 9 → 13^2 = 4^2 + 3^2
      3249 = 324 + 9 → 57^2 = 18^2 + 3^2
      64009 = 6400 + 9 → 253^2 = 80^2 + 3^2
      237169 = 23716 + 9 → 487^2 = 154^2 + 3^2

      Each has a suffix square of 9.

      Like

      • Frits's avatar

        Frits 4:55 pm on 3 January 2024 Permalink | Reply

        Slower.

            
from enigma import SubstitutedExpression

# the alphametic puzzle
p = SubstitutedExpression(
  [
    # ABC^2 concatenated with DEF^2 = square
    "ABC > 0",
    # RHS must be less than a million
    "(d2 := DEF**2) < 10 ** (6 - len(str(a2 := ABC**2)))",
    "is_square(int(str(a2) +  str(d2)))",
  ],
  answer="ABC, DEF",
  d2i="",
  distinct="",
  reorder=0,
  verbose=0,    # use 256 to see the generated code
)

# store answers in dictionary (key = suffix)
d = dict()
for a, b in p.answers():
  d[b] = d.get(b, []) + [a]

# find maximal length sequences sharing the same suffix
m = len(max(d.values(), key=lambda k: len(k)))

# assume more than one answer is possible
print("answer:", ' or '.join(str(x) for x in
     [sorted(int(str(v**2) + str(k**2)) for v in vs)
             for k, vs in d.items() if len(vs) == m]))

        Like

        • Jim Randell's avatar

          Jim Randell 10:25 pm on 4 January 2024 Permalink | Reply

          @Frits: Would this work if there were multiple SPSs with the same length and suffix?(e.g. if 99856+9 were a valid SPS).

          Like

          • Frits's avatar

            Frits 6:39 pm on 5 January 2024 Permalink | Reply

            @Jim, you are right. This wouldn’t work as I forgot the condition “no two numbers in their series could have the same number of digits”.

            Like

  • Unknown's avatar

    Jim Randell 2:42 pm on 29 December 2023 Permalink | Reply
    Tags:   

    Teaser 3197: Three or four? 

    From The Sunday Times, 31st December 2023 [link] [link]

    Here are some clues about my PIN:

    (a) It has 3 digits (or it might be 4).
    (b) The first digit is 3 (or it might be 4).
    (c) The last digit is 3 (or it might be 4).
    (d) It is divisible by 3 (or it might be 4).
    (e) It differs from a square by 3 (or it might be 4).

    In each of those statements above just one of the guesses is true, and the lower guess is true in 3 cases (or it might be 4).

    That should enable you to get down to 3 (or it might be 4) possibilities for my PIN. But, even if you could choose any one of the statements, knowing which guess was correct in that statement would not enable you to determine the PIN.

    What is my PIN?

    This completes the archive of Teaser puzzles from 2023.

    For my selection of the more interesting puzzles encountered in 2023 see 2023 in review on Enigmatic Code.

    [teaser3197]

     
    • Jim Randell's avatar

      Jim Randell 2:59 pm on 29 December 2023 Permalink | Reply

      See also: Enigma 1609.

      This Python program runs in 75ms. (Internal runtime is 12ms).

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

# check f(v, 3) or f(v, 4) are true (but not both)
def check(v, f):
  (v3, v4) = (f(v, 3), f(v, 4))
  if v3 and not v4: return 3
  if v4 and not v3: return 4
  raise ValueError()

# generate candidate PINs
def generate():
  # consider 3- and 4-digit PINs
  for ds in subsets(irange(0, 9), min_size=3, max_size=4, select='M'):
    # evaluate the statements
    ss = list()
    try:
      # (a) "It has 3 or 4 digits"
      ss.append(check(ds, (lambda x, k: len(x) == k)))
      # (b) "The first digit is 3 or 4"
      ss.append(check(ds, (lambda x, k: x[0] == k)))
      # (c) "The last digit is 3 or 4"
      ss.append(check(ds, (lambda x, k: x[-1] == k)))
      # (d) "It is divisible by 3 or 4"
      n = nconcat(ds)
      ss.append(check(n, (lambda x, k: x % k == 0)))
      # (e) "It differs from a square by 3 or 4
      ss.append(check(n, (lambda x, k: is_square(x - k) or is_square(x + k))))
    except ValueError:
      continue
    # there are 3 or 4 answers of 3
    if not ss.count(3) in {3, 4}: continue
    # this is a viable candidate
    printf("[{ds} = {n} -> {ss}]")
    yield (ds, ss)

# collect possible candidates (<digits>, <statements>)
rs = list(generate())
# there should be 3 or 4 candidates
assert len(rs) in {3, 4}

# for statement <k> generate ambiguous PINs
def ambiguous(rs, k):
  stk = (lambda x: x[1][k])  # value of statement <k>
  pin = (lambda x: x[0])  # PIN
  # find PINs that are ambiguous by statement <k>
  for x in filter_unique(rs, stk, pin).non_unique:
    yield pin(x)

# look for values that are ambiguous at each statement
for ds in intersect(ambiguous(rs, k) for k in irange(5)):
  # output solution
  printf("PIN = {n}", n=join(ds))

      Solution: The PIN is 3603.

      There are 3 candidate numbers:

      (3, 3, 4, 4, 3) → 364
      (4, 3, 3, 3, 3) → 3603
      (4, 4, 3, 3, 3) → 4353

      And only 3603 is ambiguous by every statement.

      Manually:

      The PIN ends in 3 or 4, and is distance 3 or 4 from a perfect square.

      So we can look at squares that end in 0, 1, 6, 9 that are distance 3 or 4 away from a number matching “[34]*[34]”, and check the statements (a) – (e):

      19^2 + 3 = 364 → [3, 3, 4, 4, 3] OK
      20^2 + 3 = 403 → [3, 4, 3, X, 3]
      20^2 + 4 = 404 → [3, 4, 4, 4, 4]
      21^2 + 3 = 444 → [3, 4, 4, X, 3]
      56^2 − 3 = 3133 → [4, 3, 3, X, 3]
      57^2 + 4 = 3253 → [4, 3, 3, X, 4]
      59^2 + 3 = 3484 → [4, 3, 4, 4, 3]
      60^2 + 3 = 3603 → [4, 3, 3, 3, 3] OK
      60^2 + 4 = 3604 → [4, 3, 4, 4, 4]
      61^2 + 3 = 3724 → [4, 3, 4, 4, 3]
      63^2 + 4 = 3973 → [4, 3, 3, X, 4]
      64^2 − 3 = 4093 → [4, 4, 3, X, 3]
      66^2 − 3 = 4353 → [4, 4, 3, 3, 3] OK
      67^2 + 4 = 4493 → [4, 4, 3, X, 4]
      69^2 + 3 = 4764 → [4, 4, 4, X, 3]
      70^2 + 3 = 4903 → [4, 4, 3, X, 3]
      70^2 + 4 = 4904 → [4, 4, 4, 4, 4]

      Which gives the 3 viable candidates.

      Like

    • Frits's avatar

      Frits 4:01 pm on 29 December 2023 Permalink | Reply 

      from enigma import is_square

# does number <n> differ from a square by <k>
nearsq = lambda n, k: any(is_square(n + i) for i in (-k, k)) 

# check number <n> for 5 clues
def check(n):
  s = str(n)
  # 3 or 4 digits
  c1 = 1 if len(s) == 3 else 2 if len(s) == 4 else 0
  if not c1: return []
  
  # first digit is 3 or 4
  c2 = 1 if s[0] == "3" else 2 if s[0] == "4" else 0
  if not c2: return []
  
  # last digit is 3 or 4
  c3 = 1 if s[-1] == "3" else 2 if s[-1] == "4" else 0
  if not c3: return []
  
  # divisible by 3 or 4
  c4 = 1 if n % 3 == 0 and n % 4 else 2 if n % 4 == 0 and n % 3 else 0
  if not c4: return []
  
  # differs from a square by 3 or 4
  c5 = 1 if nearsq(n, 3) and not nearsq(n, 4) else 2 \
         if nearsq(n, 4) and not nearsq(n, 3) else 0
  if not c5: return []
  
  return [c1, c2, c3, c4, c5]
  
sols = []

# check 3 and 4-digit numbers
for n in range(303, 4995):
  # check all 5 clues
  row = check(n)
  if row:
    # 3 or 4 answers of the lower guess
    if not row.count(1) in {3, 4}: continue
    sols.append((n, row))

# 3 or 4 possibilities for my PIN
if len(sols) not in {3, 4}: 
  print("no solution")
  exit(0)    

# create matrix for guesses
mat = [s[1] for s in sols]
tmat = list(zip(*mat))        # transpose matrix

#  remove solutions which have an unique answer for a clue
sols = [n for (n, r) in sols if all(tmat[i].count(r[i]) > 1 for i in range(5))]

if len(sols) != 1: 
  print("no unique solution")
  exit(0) 
  
print("answer:", *sols)

      Like

    • Frits's avatar

      Frits 12:13 am on 30 December 2023 Permalink | Reply

      Fast with PyPy.

          
sqs = []
# determine possible squares
for m, M  in ((299, 498), (2999, 4998)):
  sqs += [x2 for x in range(int(m**.5), int(M**.5) + 1) 
          if m <= (x2 := x * x) <= M and x2 % 10 not in {2, 3, 4, 5}]

# PINs differ from a square by 3 or 4 and are divisible by 3 or 4
pins = [(str(pin), sq) for sq in sqs for k in [-4, -3, 3, 4] 
        if all(str(pin := sq + k)[i] in "34" for i in [-1, 0]) and
           sum([pin % 3 == 0, pin % 4 == 0]) == 1]

# the lower guess is true in 3 or 4 cases 
pins = [(p, r) for (p, sq) in pins 
        if sum(r := [p[0] == '4', 
               p[-1] == '4', 
               len(p) == 4, 
               int(p) % 4 == 0,
               abs(sq - int(p)) == 4]) in {1, 2}] 
               
# 3 or 4 possibilities for my PIN
if len(pins) not in {3, 4}: 
  print("no solution")
  exit(0)                   

# create matrix for guesses
mat = [s[1] for s in pins]
tmat = list(zip(*mat))        # transpose matrix

# remove PINs that have an unique answer for a clue
pins = [n for (n, r) in pins if all(tmat[i].count(r[i]) > 1 for i in range(5))]

if len(pins) != 1: 
  print("no unique solution")
  exit(0) 
  
print("answer:", *pins)

      Like

    • NigelR's avatar

      NigelR 10:07 am on 31 December 2023 Permalink | Reply 

      is_square = lambda n: round(n**(0.5))**2 == n
#conditions return 'l' for lower value (3), 'u' for upper (4), 'f' for neither
g1 = lambda n: 'l' if len((ns:=str(n)))==3 else ('u' if len(ns)==4 else 'f')
g2 = lambda n: 'l' if (ns:=str(n))[0]=='3' else ('u' if ns[0]=='4' else 'f')
g3 = lambda n: 'l' if (ns:=str(n))[-1]=='3' else ('u' if ns[-1]=='4' else 'f')
g4 = lambda n: 'f' if n%12==0 else ('l' if n%3==0 else ('u' if n%4==0 else 'f'))
g5 = lambda n: 'l' if is_square(n-3) or is_square(n+3) else('u' if is_square(n-4) or is_square(n+4) else 'f')

tests = (g1,g2,g3,g4,g5)
res={}
#test either side of square numbers between 300 and 5000
for i in range(18,71):
    for pin in [(isq:= i*i)+3,isq-3,isq+4,isq-4]:
        #use loop not comprehension to allow break on first invalid test
        outc=[]
        for test in tests:
            if (r:=test(pin))=='f':break 
            else: outc.append(r)
        #all tests must pass and  3 or 4 lower guesses are true
        if len(outc)!=5 or outc.count('l') not in {3,4}: continue        
        else: res[pin] = outc  #current value of pin is valid
#remove candidate PINs with unique correct guesses
guesses = [[res[x][y] for x in res] for y in range(5)]
soltn = [x for x in res if not [j for i,j in enumerate(guesses) if j.count(res[x][i])==1]]
if len(soltn)!=1: print('no unique solution found')
else: print('PIN is',soltn[0])

      Like

  • Unknown's avatar

    Jim Randell 4:41 pm on 22 December 2023 Permalink | Reply
    Tags:   

    Teaser 3196: Mind the edge 

    From The Sunday Times, 24th December 2023 [link] [link]

    Kate and Lucy play a pub game on an isosceles triangle table top. They take turns to push a penny from the centre of the table top’s base towards the triangle’s apex, 120cm distant, scoring the sum of their distances from the base, or zero if it ever falls off the table.

    Each player aims to maximise their distance, avoiding the chance that the penny might fall off the table. Their penny has an equal chance of landing anywhere within an error radius around the aimed point. This radius is proportional to the distance aimed. As a skilled player Lucy’s error ratio is half of Kate’s.

    They both expect to score a whole number of cm per push, but to give each an equal chance of winning Kate gets one more push than Lucy. This number of pushes is the largest possible, given the above information.

    How many pushes complete a game between the two?

    Happy Christmas from S2T2!

    For my selection of the more interesting puzzles encountered in 2023 see 2023 in review on Enigmatic Code.

    [teaser3196]

     
    • Jim Randell's avatar

      Jim Randell 5:15 pm on 22 December 2023 Permalink | Reply

      If I understand the puzzle correctly it works like this:

      Suppose the integer distances they are aiming for are L and K (where 0 < K < L < 120), and if L has n turns (so K has (n + 1) turns), then we have:

      n L = (n + 1) K
      ⇒ n = K / (L − K)

      so n is a divisor of K.

      And if L’s target circle has radius r(L):

      r(L) = k L

      for some constant k.

      And K’s circle is given by:

      r(K) = 2k K

      And if θ is half the angle at the apex of the triangle we have:

      sin(θ) = r(L) / (120 − L)
      sin(θ) = r(K) / (120 − K)
      ⇒
      (120 − K) L = 2 K (120 − L)
      K L = 120 (2K − L)
      L = 240 K / (120 + K)

      This Python program finds possible K, L, n values, and looks for maximal n values.

      It run in 55ms (and has an internal runtime of 110µs).

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

# find maximum number of goes
r = Accumulator(fn=max, collect=1)

# consider distance K
for K in irange(1, 118):
  # calculate L
  L = div(240 * K, 120 + K)
  if L is None or not (L < 120): continue
  # calculate n
  n = div(K, L - K)
  if n is None: continue
  # record maximal n
  printf("[K={K} L={L} n={n}]")
  r.accumulate_data(n, (K, L))

# output solution
n = r.value
for (K, L) in r.data:
  printf("K={K} L={L} n={n} -> {t} turns", t=2 * n + 1)

      Solution: The total number of turns in the game is 31.

      L has 15 turns, and K has 16.

      Like

    • Frits's avatar

      Frits 11:56 am on 25 December 2023 Permalink | Reply 

         
from enigma import divisors
 
# consider the distance for Lucy
for L in range(119, 1, -1):
  # Lucy has n pushes, n = 120 / (120 - L), K = 120L / (240 - L)
  if (120 - L) not in divisors(120) or (120 * L) % ((240 - L)): continue
  
  print(f"answer: {240 // (120 - L) + 1} pushes")
  break # maximum reached

      Like

      • Jim Randell's avatar

        Jim Randell 9:24 am on 26 December 2023 Permalink | Reply

        @Frits: A very compact and efficient approach (only 8 cases are considered).

        Here’s a version that prints a bit more information:

        from enigma import (irange, div, printf)

# find values of n in decreasing order
for L in irange(119, 2, step=-1):
  K = div(120 * L, 240 - L)
  if K is None: continue
  n = div(120, 120 - L)
  if n is None: continue
  # output solutions
  printf("L={L} -> K={K} n={n} -> {t} turns", t=2 * n + 1)
  break  # only need largest n

        Like

  • Unknown's avatar

    Jim Randell 7:59 am on 21 December 2023 Permalink | Reply
    Tags: by: Anthony Isaacs   

    Brainteaser 1457: All square 

    From The Sunday Times, 12th August 1990 [link]

    Your task this week is to place a non-zero digit in each of the 16 squares shown:

    When you’ve finished each of the four rows should read across as a four-figure perfect square, and each of the four columns should read down as a four-figure perfect square.

    What is the sum of the 16 digits?

    [teaser1457]

     
    • Jim Randell's avatar

      Jim Randell 8:00 am on 21 December 2023 Permalink | Reply

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

      #! python3 -m enigma -rr

SubstitutedExpression

#  A B C D
#  E F G H
#  I J K L
#  M N P Q

--digits="1-9"
--distinct=""

# rows read as squares
"is_square(ABCD)"
"is_square(EFGH)"
"is_square(IJKL)"
"is_square(MNPQ)"

# columns read as squares
"is_square(AEIM)"
"is_square(BFJN)"
"is_square(CGKP)"
"is_square(DHLQ)"

# [optional] squares must end in 1, 4, 5, 6, 9
--invalid="2|3|7|8,DHLMNPQ"

--answer="sum([A, B, C, D, E, F, G, H, I, J, K, L, M, N, P, Q])"
--template=""

      Solution: The sum of the 16 digits is 56.

      The completed grid is as follows:

      Like

    • GeoffR's avatar

      GeoffR 6:21 pm on 21 December 2023 Permalink | Reply 

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

% A B C D
% E F G H
% I J K L
% M N P Q

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; var 1..9:J; 
var 1..9:K; var 1..9:L; var 1..9:M; var 1..9:N; var 1..9:O; 
var 1..9:P; var 1..9:Q; 

var 16..108:total; % UB = 2*45 + 18
set of int: sq4 = {n*n | n in 34..96}; 
% 97,98,99 have zeroes in squares, as do 32 and 33

% ROWS
var 1156..9216:ABCD == 1000*A + 100*B + 10*C + D;
var 1156..9216:EFGH == 1000*E + 100*F + 10*G + H;
var 1156..9216:IJKL == 1000*I + 100*J + 10*K + L;
var 1156..9216:MNPQ == 1000*M + 100*N + 10*P + Q;
% COLUMNS
var 1156..9216:AEIM == 1000*A + 100*E + 10*I + M;
var 1156..9216:BFJN == 1000*B + 100*F + 10*J + N;
var 1156..9216:CGKP == 1000*C + 100*G + 10*K + P;
var 1156..9216:DHLQ == 1000*D + 100*H + 10*L + Q;
 
% Last digit of squares is 1,4,5,6 or 9.
set of int: dig_end = {1,4,5,6,9};
constraint sum([D in dig_end, H in dig_end, L in dig_end, Q in dig_end]) == 4;
constraint sum([M in dig_end, N in dig_end, P in dig_end]) == 3;

constraint sum([ABCD in sq4, EFGH in sq4, IJKL in sq4, MNPQ in sq4,
AEIM in sq4, BFJN in sq4, CGKP in sq4, DHLQ in sq4]) = 8; 

constraint total = A+B+C+D+E+F+G+H+I+J+K+L+M+N+P+Q;
solve satisfy;

output ["Total of all digits = " ++ show(total) 
++ "\n" ++ show(ABCD) ++ "\n" ++ show(EFGH)
++ "\n" ++ show(IJKL) ++ "\n" ++ show(MNPQ)];

% Total of all digits = 56
% 2116
% 1225
% 1296
% 6561
% ----------
% ==========
% Finished in 442msec.

      Like

    • Frits's avatar

      Frits 12:58 pm on 22 December 2023 Permalink | Reply

      Using permutations is a lot slower (1 second with PyPy).

         
from itertools import permutations

sqs =  {x2 for x in range(32, 100) if '0' not in (x2 := str(x * x))}

for hor in permutations(sqs, 4):
  # check columns, transpose the permutation to get the columns
  if any(''.join(x) not in sqs for x in (zip(*hor))): continue
  for h in hor: print(h)
  print("\nanswer:", sum(int(d) for h in hor for d in h))

      Like

  • Unknown's avatar

    Jim Randell 8:30 am on 19 December 2023 Permalink | Reply
    Tags:   

    Brainteaser 1087: Pennies from heaven 

    From The Sunday Times, 5th June 1983 [link]

    In our club we have three one-armed bandits. The Saturn Skyjacker accepts 10p, 2p and 1p coins, the Mars Marauder accepts 10p and 1p coins, and the Aries Axeman accepts 5p and 2p coins.

    I am the club treasurer, so each week I have the onerous task of emptying the machines and counting the coins. Last week, my efforts were rewarded with the discovery of an interesting series of coincidences. On counting the coins for the Saturn Skyjacker, I found that there were the same number of coins of two of the denominations, and that the number of coins of the third denomination differed from this number by only one. In addition, the total value of all the coins was an exact number of pounds less than one hundred.

    The coins from the Mars Marauder were similarly distributed: the numbers of 10p and 1p coins differed by only one, and the total value was again an exact number of pounds. In fact, this total value was the same as for the Saturn Skyjacker.

    Incredibly, the same was true for coins from the Aries Axeman: the numbers of 5p and 2p coins differed by one, and the total value was the same as for the Mars Marauder and the Saturn Skyjacker.

    What was the total number of coins I emptied that day?

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

    [teaser1087]

     
    • Jim Randell's avatar

      Jim Randell 8:31 am on 19 December 2023 Permalink | Reply

      This Python program runs in 60ms. (Internal runtime is 306µs).

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

# decompose t into k * x and (k +/- 1) * y
def decompose(t, x, y):
  k = div(t - y, x + y)
  if k: yield (k, k + 1)
  k = div(t + y, x + y)
  if k: yield (k, k - 1)

# total number of pounds is less than 100
for t in irange(100, 9900, step=100):
  # can we make this total for (10, 1) and (5, 2)
  for (m, a) in cproduct([decompose(t, 10, 1), decompose(t, 5, 2)]):
    # try to make t from (10, 2, 1) by combining 2 of the values
    for (x, y) in [(12, 1), (11, 2), (3, 10)]:
      for s in decompose(t, x, y):
        # calculate total number of coins
        n = sum(m) + sum(a) + sum(s) + s[0]
        # output solution
        printf("{n} coins [t={t}: m={m} a={a} -> x={x} y={y} s={s}]")

      Solution: The total number of coins is: 3001.

      In the Saturn Skyjacker there were 331× 10p + 330× 2p + 330× 1p = 4300p.

      In the Mars Marauder there were 391× 10p + 390× 1p = 4300p.

      In the Aries Axman there were 614× 5p + 615× 2p = 4300p.

      So in total there were 3001 coins totalling £129.

      Like

    • Frits's avatar

      Frits 2:48 pm on 19 December 2023 Permalink | Reply 

       
# coins (pennies) for Saturn Skyjacker, the Mars Marauder and the Aries Axeman
cs = [{1, 2, 10}, {1, 10}, {2, 5}]

# total number of pounds is less than 100
for t in range(100, 10000, 100):
  # remainder by sum of coin denominations should be equal to one of the 
  # coin denominations or equal to the sum of all coin denominations but one
  if all((t % sum(c)) in c | {sum(c) - x for x in c} for c in cs):
    print("answer:", sum(len(c) * (t // sum(c)) + 
          (1 if (t % sum(c)) in c else len(c) - 1) for c in cs))

      Like

    • GeoffR's avatar

      GeoffR 8:36 pm on 27 December 2023 Permalink | Reply 

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

% Saturn Skyjacker coins are 1p, 2p and 10p
var 1..9999:SS;   % maximum Saturn Skyjacker total(p)

% Assumed UB for SS, MM and AA coin numbers
var 1..1000:s10; var 1..1000:s2; var 1..1000:s1; 

% Two coins hae the same number, differing fron the other denomination by 1
constraint (s10 == s2 /\ abs(s10 - s1) == 1)
\/ (s10 == s1 /\ abs(s10 - s2) == 1)
\/ (s1 == s2 /\ abs(s1 - s10) == 1);

constraint s1*1 + s2*2 + s10*10 == SS;
constraint SS div 100 < 100 /\ SS mod 100 == 0;

% Mars Marauder coins 1p and 10p
var 1..9999:MM; % maximum Mars Marauder total(p)
var 1..1000:m1; var 1..1000:m10;

% Mars Marauder coin numbers differ by 1
constraint abs(m1 - m10) == 1;
constraint MM = m1 * 1  + m10 * 10;
constraint MM div 100 < 100 /\ MM mod 100 == 0;

% Aries Axem coins are 2p and 5p
var 1..9999:AA; % maximum Aries Axem  total(p)
var 1..1000:a2; var 1..1000:a5;

% Aries Axem coin numbers differ by 1
constraint abs(a2 - a5) == 1;
constraint AA = a2 * 2  + a5 * 5;
constraint AA div 100 < 100 /\ AA mod 100 == 0;

% Total amount from three machines is the same
constraint MM == SS /\ MM == AA;

% Total number of coins
var 1..7000:tot_coins == s1 + s2 + s10 + m1 + m10 + a2 + a5;

solve satisfy;

output[" Total number of coins = " ++ show(tot_coins) ++ "\n" ++
" Saturn coins are s1, s2, s10 = " ++ show([s1, s2, s10] ) ++ "\n" ++
" Mars coins m1 and m10 = " ++ show([m1, m10]) ++ "\n" ++
" Aries coins are a2 and a5 = " ++ show([a2, a5]) ++ "\n" ++
" Total value in each machine = £" ++ show(SS div 100) ];

%  Total number of coins = 3001
%  Saturn coins are s1, s2, s10 = [330, 330, 331]
%  Mars coins m1 and m10 = [390, 391]
%  Aries coins are a2 and a5 = [615, 614]
%  Total value in each machine = £43
% ----------
% ==========
% Finished in 506msec.

      Like

  • Unknown's avatar

    Jim Randell 4:44 pm on 15 December 2023 Permalink | Reply
    Tags:   

    Teaser 3195: Garden divide 

    From The Sunday Times, 17th December 2023 [link] [link]

    I have a triangular-shaped garden, the sides of which are an exact number of feet long. To improve its usefulness, I’ve decided to partition it by building a straight fence from one corner to the centre of the opposite side. The length of this fence is exactly 51 feet and the side it attaches to is now 26 feet long each side of the fence.

    What, in ascending order, are the lengths of the other two sides of my garden?

    [teaser3195]

     
    • Jim Randell's avatar

      Jim Randell 5:05 pm on 15 December 2023 Permalink | Reply

      We can use the cosine rule to calculate the missing sides in terms of the cosine of their opposite angles, which are supplementary (i.e. their sum is 180°).

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

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

# the fence is length: a
# and divides the base of the triangle into: b + b = 2b
(a, b) = (51, 26)

# by the cosine rule we have:
#
# x^2 = a^2 + b^2 - 2.a.b.cos(theta)
# y^2 = a^2 + b^2 + 2.a.b.cos(theta)

# consider increasing squares for x
z = sq(a) + sq(b)
for x in irange(a - b + 1, a + b - 1):
  # calculate the 2.a.b.cos(theta) term
  t = z - sq(x)
  # calculate y
  y = is_square(z + t)
  if y is None or y < x: continue
  # output solution
  printf("x={x} y={y}")

      Solution: The other two sides of the garden are: 35ft and 73ft.

      Like

      • Frits's avatar

        Frits 6:18 pm on 15 December 2023 Permalink | Reply 

         
# get 2 squares that sum up to n (with minimum m)
# https://stackoverflow.com/questions/72093402/sum-of-two-squares-in-python
def sum_of_two_squares(n, m):
  i = m
  j = int(n ** (1/2))

  while i < j:
    x = i * i + j * j
    if x == n:
      yield i, j

    if x < n:
      i += 1
    else:
      j -= 1
      
# by the cosine rule we have:
#
# x^2 = a^2 + b^2 - 2.a.b.cos(t)
# y^2 = a^2 + b^2 + 2.a.b.cos(t)

# so x^2 + y^2 = 2 * (a^2 + b^2)
      
(a, b) = (51, 26)      

for xy in sum_of_two_squares(2 * (a**2 + b**2), b):
  print("answer:", xy)

        Like

        • Jim Randell's avatar

          Jim Randell 8:33 pm on 15 December 2023 Permalink | Reply

          In fact there is a [[ sum_of_squares() ]] function already in enigma.py.

          from enigma import (sum_of_squares, sq, printf)

# the fence is length: a
# and divides the base of the triangle into: b + b = 2b
(a, b) = (51, 26)

# x^2 + y^2 = 2(a^2 + b^2)
for (x, y) in sum_of_squares(2 * (sq(a) + sq(b)), 2):
  if a - b < x and y < a + b:
    printf("x={x} y={y}")

          Like

    • GeoffR's avatar

      GeoffR 10:43 am on 16 December 2023 Permalink | Reply 

      # Central fence length (a) and given half side of triangle (b)
a, b = 51, 26 

# Other two sides of triangle are x and y
# Cosine rule gives:  x^2 + y^2 = 2 * (a^2 + b^2)

# Max side of other two triangle sides < 51 + 26 i.e. < 77
# Make x the smallest unknown triangle side
for x in range(5, 77):
  for y in range(x+1, 77):
    # triangle side constraints
    if not x < (a + b):continue
    if not y < (a + b):continue
    if x * x + y * y == 2 * a**2 + 2 * b**2:
       print(f"Other two sides of garden are {x}ft. and {y}ft.")

      Without the triangle constraints there is another integer solution to the equation x^2 + y^2 = 2 * (a^2 + b^2). This is x = 25 and y = 77. This would make the overall triangle sides (25,52,77), which is not possible, so this cannot be the teaser answer.

      Like

  • Unknown's avatar

    Jim Randell 8:38 am on 14 December 2023 Permalink | Reply
    Tags: ,   

    Teaser 2665: Milky ways 

    From The Sunday Times, 20th October 2013 [link] [link]

    Each evening Pat drives his herd of cows into the milking parlour. The cows are ear-tagged 1, 2, 3, … and the parlour is divided into stalls also numbered 1, 2, 3, …, with one stall for each cow. The cows file in and choose empty stalls at random until all the stalls are full. Pat has noticed that very often it happens that no cow occupies a stall with the same number as her tag. Pat worked out the number of different ways this could happen, and also the number of ways that at least one cow could be in a stall with the same number as herself. The two answers were less than a million and Pat noticed that the sum of the digits in each was the same.

    How many cows are in the herd?

    [teaser2665]

     
    • Jim Randell's avatar

      Jim Randell 8:39 am on 14 December 2023 Permalink | Reply

      (See also: Teaser 2995, Teaser 2779).

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

      from enigma import (irange, inf, factorial, subfactorial, dsum, printf)

# consider 3 or more cows
for k in irange(3, inf):
  # calculate the number of possible arrangements
  n = factorial(k)
  # calculate the number of derangements
  d = subfactorial(k)
  # and the number of arrangements that are not derangements
  r = n - d
  if not (max(d, r) < 1000000): break
  # calculate digit sum
  if dsum(d) == dsum(r):
    # output solution
    printf("k={k}: n={n} d={d} r={r}")

      Solution: There were 7 cows in the herd.

      The cows can be arranged in factorial(7) = 5040 different ways.

      Of these subfactorial(7) = 1854 are derangements.

      And the remaining 3186 are not derangements, so at least one cow must have the same number as the stall it is in.

      And dsum(1854) = dsum(3186) = 18.

      If we allow numbers over 1 million, then there are further solutions at k = 46, 52, 94, 115, 124, 274, 313, 346, …

      Like

  • Unknown's avatar

    Jim Randell 3:47 pm on 12 December 2023 Permalink | Reply
    Tags:   

    Teaser 2658: Different views 

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

    Oliver arranged six [identical standard] dice in a neat pile with three in the bottom row, two in the middle row and one at the top. The faces of these dice were digits rather than the corresponding number of dots. Looking down on them, Beth saw that the five partially-visible tops of the dice contained different digits. In the three rows at the front she saw 1-digit, 2-digit and 3-digit primes, whereas from the back she saw three perfect squares. On the left, working down the three sides, she saw a 3-digit square whereas on the right, again working down, she saw a 3-digit prime.

    What was this 3-digit prime?

    [teaser2658]

     
    • Jim Randell's avatar

      Jim Randell 3:47 pm on 12 December 2023 Permalink | Reply

      We need to make some additional assumptions about the dice in order to arrive at a unique solution.

      I assumed that the dice are “standard”, i.e. each has the digits 1-6 on, and they are arranged such that opposite faces sum to 7, and the numbers 1, 2, 3 are arranged anti-clockwise around one of the vertices.

      I used the [[ Cube() ]] class (originally written for Teaser 2835) to generate all possible rotations of a standard die, and then used the [[ SubstitutedExpression ]] solver from the enigma.py library to solve the puzzle.

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

      #! python3 -m enigma -rr

#            C
#         +-----+
#      B S| K/R |V D
#      +--+--+--+--+
#   A T| I/Q | J/P |W E
#   +--+--+--+--+--+--+
#  U| F/N | G/M | H/L |X
#   +-----+-----+-----+
#
#  top   = ABCDE
#  front = FGH, IJ, K
#  back  = LMN, PQ, R
#  left  = STU
#  right = VWX [= answer]

SubstitutedExpression

--digits="1-6"

# visible top faces are all different
# faces of each dice are different
--distinct="ABCDE,AFNU,BIQT,CKRSV,DJPW,EHLX,GM"

# visible front faces form primes
"is_prime(FGH)"
"is_prime(IJ)"
"is_prime(K)"

# visible back faces form squares
"is_square(LMN)"
"is_square(PQ)"
"is_square(R)"

# left (top to bottom) forms a 3-digit square
"is_square(STU)"

# right (top to bottom) forms a 3-digit prime
"is_prime(VWX)"

# answer is the 3 digit prime on the right
--answer="VWX"

# additional checks for standard dice
--code="from cube import Cube"
--code="dice = set()"
--code="dice.update(r.faces for r in Cube(faces=(1, 6, 2, 5, 3, 4)).rotations())" # standard die
--code="is_die = lambda *fs: any(all(x == 0 or x == y for (x, y) in zip(fs, die)) for die in dice)"

# perform check on the six (partial) dice
"is_die(A, 0, F, N, U, 0)"
"is_die(B, 0, I, Q, T, 0)"
"is_die(C, 0, K, R, S, V)"
"is_die(D, 0, J, P, 0, W)"
"is_die(E, 0, H, L, 0, X)"
"is_die(0, 0, G, M, 0, 0)"

--template="(A, 0, F, N, U, 0) (B, 0, I, Q, T, 0) (C, 0, K, R, S, V) (D, 0, J, P, 0, W), (E, 0, H, L, 0, X) (0, 0, G, M, 0, 0)"
--solution=""
--verbose="THA"
--denest

      Solution: The prime when the pile is viewed from the right is: 523.

      From the top the faces form: 31642 (all digits different).

      From the front the faces form: 3, 31, 251 (prime numbers).

      From the back the faces form: 4, 64, 625 (square numbers).

      From the left (top-to-bottom) the faces form: 256 (a square number).

      From the right (top-to-bottom) the faces form: 523 (a prime number).

      The problem can also be solved with six identical dice where the numbers 1, 2, 3 are arranged clockwise around one of the vertices (i.e. “mirror image” dice), and we get the same result.

      But if we are allowed to mix these two types of dice then we can get an additional answer of 653.

      And without the additional constraints (i.e. allowing dice where the digits 1-6 appear in any pattern) we can find many possible solutions.

      Like

    • Frits's avatar

      Frits 2:03 pm on 13 December 2023 Permalink | Reply 

       
from itertools import product

# get rid of numbers with invalid digits 0,7,8 and 9 or 
# with digits occuring more than once
cleanup = lambda s: {x for x in s if len(set(str(x))) == len(str(x)) and
                     not any(d in str(x) for d in '7890')}
oppsides = lambda n: [n, str(7 - int(n))]      

# given two dice faces anti-clockwise at a vertex, find the third
# face anti-clockwise at this vertex (western die if same is true)
def die_third_face(first, second, same=False):
  # credit: B. Gladman
  if second in (first, 7 - first):
    raise ValueError
  t, f = min(first, 7 - first), min(second, 7 - second)
  c1 = ((f - t) % 3 == (1 if same else 2))
  c2 = (first < 4) == (second < 4)
  return 6 - t - f if c1 == c2 else t + f + 1

# determine valid primes up to 1000
P = {3, 5, 7}
P |= {x for x in range(11, 100, 2) if all(x % p for p in P)}
P |= {2} | {x for x in range(101, 1000, 2) if all(x % p for p in P)}
P = cleanup(P)

# determine valid squares up to 1000
sq = cleanup(x * x for x in range(1, 32))
sq3 = [str(x) for x in sq if x > 99]
pr3 = [str(x) for x in P if x > 99]

# valid prime/square combinations
cands = {ln: [(p, s) for s in sq  
         if len(st := str(s)) == ln and 
         (p := (7 * int('111'[:ln]) - int(st[::-1]))) in P and
         all(len(set(str(x))) == len(st) for x in (s, p))] for ln in (1, 2, 3)}         

# check all possible combinations
for (pt, st), (pm, sm), (pb, sb) in product(*cands.values()):
  # filter 3-digit squares to have different digits from front and back faces
  for lft in [s for s in sq3 if all(s[i] not in 
             oppsides(str((pt, pm, pb)[i])[0]) for i in range(3))]:
    # filter 3-digit primes to have correct hundreds digit
    rghts = [x for x in pr3 if x[0] == str(7 - int(lft[0]))]
    # filter 3-digit primes to have different digits from front and back faces
    for rght in [r for r in rghts if all(r[i] not in 
                 oppsides(str((st, sm, sb)[i])[0]) for i in range(3))]:
      # all visible top faces (left to right) could be seen to be different
      tp1 = die_third_face(int(lft) % 10, pb // 100)
      tp2 = die_third_face((int(lft) % 100) // 10, pm // 10)
      tp3 = die_third_face(pt % 10, int(rght) // 100)
      tp4 = die_third_face(pm % 10, (int(rght) % 100) // 10)
      tp5 = die_third_face(pb % 10, int(rght) % 10)
      if len({tp1, tp2, tp3, tp4, tp5}) == 5:
        print("answer:", rght)

      Like

  • Unknown's avatar

    Jim Randell 4:37 pm on 8 December 2023 Permalink | Reply
    Tags:   

    Teaser 3194: A proper lesson 

    From The Sunday Times, 10th December 2023 [link] [link]

    A maths teacher wrote a sequential list of numbers 1, 2, 3, 4, … on the blackboard and asked her pupils to find a pair of positive fractions adding up to 1. The pair was to have the two numerators and two denominators consisting of four different numbers from her list. They found all possible pairs.

    She then told them to group two of the pairs that used eight different numbers from her list, which was just long enough to enable them to do this. The class found all possible groups. One of the groups contained some fractions that were not used by any other group.

    Which of the teacher’s numbers were not used by that group?

    [teaser3194]

     
    • Jim Randell's avatar

      Jim Randell 4:56 pm on 8 December 2023 Permalink | Reply

      This Python program considers increasing maximum values written on the blackboard, and collects new pairs of fractions as they become available, until it is possible to form groups consisting of 2 pairs that use 8 different numbers in the fractions.

      It then examines the groups found to determine which of them contain fractions that only occur in that group, and these groups provide the answer.

      It runs in 53ms. (Internal runtime is 519µs).

      from enigma import (
  irange, inf, fraction, multiset, subsets, flatten, diff, chunk, join, sprintf as f, printf
)

# format a list of numbers as fraction sums
fmt = lambda ns: join((f("{a}/{b} + {c}/{d} = 1") for (a, b, c, d) in chunk(ns, 4)), sep="; ")

# collect possible pairs of fractions a/b + c/d = 1
ps = list()
# consider increasing 1..n values
for n in irange(4, inf):
  np = len(ps)
  # add in a/b, c/n pairs
  for c in irange(1, n - 1):
    (a, b) = (p, q) = fraction(1, 1, -c, n)
    while b < n:
      ns = (a, b, c, n)
      if len(set(ns)) == 4:
        ps.append(ns)
      a += p
      b += q
  if n < 8 or len(ps) == np: continue

  # find possible groups, and count occurrences of fractions
  (gs, m) = (list(), multiset())
  for ns in subsets(ps, size=2, fn=flatten):
    if len(set(ns)) == 8:
      printf("[n={n}: {ns}]", ns=fmt(ns))
      gs.append(ns)
      m.update_from_seq(chunk(ns, 2))
  if not gs: continue

  # find groups that contain fractions that only occur in one group
  for ns in gs:
    if any(m.count(x) == 1 for x in chunk(ns, 2)):
      # output solution
      ans = diff(irange(1, n), ns)
      printf("unused = {ans} [{ns}]", ans=join(ans, sep=", ", enc="()"), ns=fmt(ns))

  # we only need the smallest n that forms groups
  break

      Solution: The unused numbers are 7 and 8.

      The teacher wrote the numbers 1 .. 10 on the board.

      This gives 17 possible pairs of fractions that sum to 1:

      1/2 + 3/6 = 1
      2/4 + 3/6 = 1
      1/3 + 4/6 = 1
      3/4 + 2/8 = 1
      1/2 + 4/8 = 1
      3/6 + 4/8 = 1
      1/4 + 6/8 = 1
      4/6 + 3/9 = 1
      1/3 + 6/9 = 1
      4/5 + 2/10 = 1
      3/5 + 4/10 = 1
      1/2 + 5/10 = 1
      2/4 + 5/10 = 1
      3/6 + 5/10 = 1
      4/8 + 5/10 = 1
      2/5 + 6/10 = 1
      1/5 + 8/10 = 1

      Note that fractions do not have to be in their lowest terms, so 1/2 and 3/6 are considered to be different fractions (with the same value).

      These can be formed into 9 groups that use 8 distinct numbers in the fractions:

      1/2 + 3/6 = 1; 4/8 + 5/10 = 1
      2/4 + 3/6 = 1; 1/5 + 8/10 = 1
      1/2 + 4/8 = 1; 3/6 + 5/10 = 1
      3/6 + 4/8 = 1; 1/2 + 5/10 = 1
      4/6 + 3/9 = 1; 1/2 + 5/10 = 1
      4/6 + 3/9 = 1; 1/5 + 8/10 = 1
      1/3 + 6/9 = 1; 4/5 + 2/10 = 1 [*]
      1/3 + 6/9 = 1; 2/4 + 5/10 = 1
      1/3 + 6/9 = 1; 4/8 + 5/10 = 1

      And it is not possible to form any groups using 1 .. 8 or 1 .. 9, so 1 .. 10 is the smallest set of initial numbers on the blackboard.

      Of the fractions used in these groups, only 4/5 and 2/10 appear in only one group [*], and this group is:

      1/3 + 6/9 = 1; 4/5 + 2/10 = 1

      And so the 2 numbers on the blackboard that are not used in any of these four fractions are 7 and 8.

      Like

    • Frits's avatar

      Frits 10:50 am on 9 December 2023 Permalink | Reply 

       
# numbers 1, 2, 3, ..., n, we need 2 groups with in total 8 different numbers
n = 8   
while True:
  # determine numbers (a, b, c, d) do that a/b + c/d = 1 with c > a
  abcd = set((a, b, c, d)
             for a in range(1, n // 2 + n % 2)
             for b in range(a + 1, n + 1)
             for c in range(a + 1, n + 1)
             if c != b and \
             not (dm := divmod(b * c, b - a))[1] and \
             c < (d := dm[0]) <= n and d != b)
  
  # find 2 groups of <abcd> entries that use 8 different numbers among them
  two_groups = [(s1[:2], s1[2:], s2[:2], s2[2:]) for s1 in abcd for s2 in abcd
                if s1[0] < s2[0] and len(set(s1 + s2)) == 8]  
  
  if not two_groups: 
    n += 1   # try numbers 1, 2, 3, ..., n
    continue
  
  # one of the groups contained some fractions 
  # that were not used by any other group
  all_fractions = [f for g2 in two_groups for f in g2]
  unique_fractions = {f for f in all_fractions if all_fractions.count(f) == 1}
  
  for g2 in two_groups:
    # does a fraction in <g2> only occur in our <g2>?
    if any(f for f in g2 if f in unique_fractions):
      used = set(y for x in g2 for y in x)
      print(f"unused numbers: "
            f"{[i for i in range(1, n + 1) if i not in used]}")
            
  break

      Like

      • Frits's avatar

        Frits 12:36 pm on 9 December 2023 Permalink | Reply

        Slower but more compact.

           
from itertools import permutations
n = 8 
while True:
  # determine different numbers (a, b, c, d, e, f, g, h) so that 
  # a/b + c/d = 1 and e/f + g/h = 1 with c > a, g > e and a < e
  abcdefgh = [((a, b), (c, d), (e, f), (g, h)) 
               for a, b, c, d, e, f, g, h in permutations(range(1, n + 1), 8)
               if a < b and c < d and e < f and g < h and 
               a < c and e < g and a < e and 
               a * d + b * c == b * d and e * h + f * g == f * h]
  
  if not abcdefgh: 
    n += 1   # try numbers 1, 2, 3, ... for a higher n
    continue
  
  # one of the groups contained some fractions 
  # that were not used by any other group
  all_fractions = [fr for f4 in abcdefgh for fr in f4]
  unique_fractions = {f for f in all_fractions if all_fractions.count(f) == 1}
  
  for f4 in abcdefgh:
    # does a fraction in <f4> not occur in any other <abcdefg> entry?
    if any(f for f in f4 if f in unique_fractions):
      used = set(y for x in f4 for y in x)
      print(f"unused numbers: "
            f"{[i for i in range(1, n + 1) if i not in used]}")
            
  break  # we are done

        Like

  • Unknown's avatar

    Jim Randell 10:58 am on 5 December 2023 Permalink | Reply
    Tags:   

    Teaser 2657: Puzzling book 

    From The Sunday Times, 25th August 2013 [link] [link]

    George and Martha have a book of puzzles numbered from 1 to 30. The solutions are also numbered from 1 to 30, but a solution number is not necessarily the same as the number of the puzzle. George and Martha have solved some of the puzzles. If you look at the number of the puzzle and the number of the solution, then the sum of the two is a perfect power of the difference of the two. George has added up the numbers of the solved puzzles and got a three-figure total. Martha has added up the numbers of the solutions of the solved puzzles and got a higher three-figure total. In fact her total used the same nonzero digits as George’s, but in a different order.

    What (in increasing order) are the numbers of the solved puzzles?

    [teaser2657]

     
    • Jim Randell's avatar

      Jim Randell 10:59 am on 5 December 2023 Permalink | Reply

      This Python program generates possible (puzzle-number, solution-number) pairs, and then searches for a collection of these pairs that satisfies the requirements.

      It runs in 66ms. (Internal runtime is 11ms).

      from enigma import (irange, subsets, is_power_of, unpack, nsplit, printf)

# find puzzles <ps>, solutions <ss> from <pairs>, sum(<ps>) = <tp>, sum(<ss>) = <ts>
def solve(pairs, ps=[], ss=[], tp=0, ts=0):
  # is this a valid set of pairs?
  if 99 < tp < ts < 1000:
    (dp, ds) = (nsplit(tp), nsplit(ts))
    if not (0 in dp or 0 in ds or sorted(dp) != sorted(ds)):
      # output solution
      printf("G={tp} M={ts} -> ps={ps} ss={ss}")
  if pairs:
    # try adding in the next pair
    (p, s) = pairs[0]
    (tp_, ts_) = (tp + p, ts + s)
    if tp_ < 999 and ts_ < 1000 and p not in ps and s not in ss:
      solve(pairs[1:], ps + [p], ss + [s], tp_, ts_)
    # without the next pair
    solve(pairs[1:], ps, ss, tp, ts)

# consider possible puzzle/solution numbers
fn = unpack(lambda p, s: is_power_of(p + s, abs(p - s)) is not None)
pairs = list(filter(fn, subsets(irange(1, 30), size=2, select='M')))
solve(pairs)

      Solution: The solved puzzles are: 1, 3, 6, 7, 9, 10, 12, 15, 21, 28.

      The (puzzle-number, solution-number) pairs are:

      (1, 3) → 1 + 3 = 4 = (3 – 1)^2
      (3, 5) → 3 + 5 = 8 = (5 – 3)^3
      (6, 10) → 6 + 10 = 16 = (10 – 6)^2
      (7, 9) → 7 + 9 = 16 = (9 – 7)^4
      (9, 7) → 9 + 7 = 16 = (9 – 7)^4
      (10, 6) → 10 + 6 = 16 = (10 – 6)^2
      (12, 15) → 12 + 15 = 27 = (15 – 12)^3
      (15, 17) → 15 + 17 = 32 = (17 – 15)^5
      (21, 28) → 21 + 28 = 49 = (28 – 21)^2
      (28, 21) → 28 + 21 = 49 = (28 – 21)^2

      The sum of the puzzle numbers is 112 (George’s total).

      And the sum of the solution numbers is 121 (Martha’s total).

      Like

  • Unknown's avatar

    Jim Randell 4:48 pm on 1 December 2023 Permalink | Reply
    Tags:   

    Teaser 3193: Balanced education 

    From The Sunday Times, 3rd December 2023 [link] [link]

    George and Martha are headmaster and secretary of Millimix School.

    There are 1000 pupils divided into 37 classes of at least 27 pupils each; each class has at least 13 members of each sex. Thus with 27 × 37 = 999, one class has an extra pupil. The classes are numbered 1-37.

    Martha noted that, taking the class with the extra pupil, and adding its class number to the number of girls in that class and a power of two, she would arrive at the square of the class number. Furthermore, the class number equalled the number of classes in which the girls outnumbered the boys.

    How many boys are in the school?

    [teaser3193]

     
    • Jim Randell's avatar

      Jim Randell 5:00 pm on 1 December 2023 Permalink | Reply

      Each class has either 27 or 28 pupils.

      For 27 the boy/girl split is either (13, 14) or (14, 13).

      For 28 the split is one of: (14, 14) (13, 15) (15, 13).

      The following Python program runs in 59ms. (Internal runtime is 163µs).

      from enigma import (irange, sq, is_power_of, printf)

# consider possible class numbers for the class with 28 pupils
for n in irange(1, 37):
  # consider the number of girls in the class
  for f in [13, 14, 15]:
    # find the necessary power of 2
    p2 = sq(n) - n - f
    k = is_power_of(p2, 2)
    if k is None: continue
    # calculate total number of boys and girls in the school
    m = 28 - f
    n1 = (n - 1 if f > m else n)
    tm = m + n1 * 13 + (36 - n1) * 14
    tf = f + n1 * 14 + (36 - n1) * 13
    # output solution
    printf("n={n} f={f} -> p2=2^{k} => boys={tm} girls={tf}")

      Solution: There are 512 boys in the school.

      Class #6 has 28 pupils, it has 14 boys and 14 girls, and we have:

      6 + 14 + 2^4 = 6^2

      Of the remaining 36 classes, there are 6 with 14 girls and 13 boys, and 30 with 14 boys and 13 girls.

      So the total number of boys in the school is:

      14 + 6×13 + 30×14 = 512

      And the total number of girls is:

      14 + 6×14 + 30×13 = 488

      Like

      • Jim Randell's avatar

        Jim Randell 2:53 pm on 3 December 2023 Permalink | Reply

        An alternative version using the observation (made by GeoffR) that:

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

        is the product of 2 consecutive integers, so must be even.

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

        from enigma import (irange, sqrtc, printf)

# consider powers of 2
for k in irange(0, 10):
  p = 2**k
  # consider number of girls in the largest class (such that f + p is even)
  for f in ([13, 15] if p % 2 else [14]):
    # calculate n, such that n(n - 1) = f + p
    x = f + p
    n = sqrtc(x)
    if n > 37: continue
    if n * (n - 1) == x:
      # calculate total number of boys and girls in the school
      m = 28 - f
      n1 = (n - 1 if f > m else n)
      tm = m + n1 * 13 + (36 - n1) * 14
      tf = f + n1 * 14 + (36 - n1) * 13
      # output solution
      printf("k={k} n={n} f={f} => boys={tm} girls={tf}")

        Like

    • GeoffR's avatar

      GeoffR 11:57 am on 2 December 2023 Permalink | Reply 

      % A Solution in MiniZinc
include "globals.mzn";
 
var 13..15:g; % number of girls in class with extra pupil
var 1..18:xg; % number of classes with more girls than boys
var 13..540:tot_g; % total girls in the school - UB = 36*15
var 13..540:tot_b; % total boys in the school
var 1..37:c; % class number with extra pupil
var 1..10:x; % a power of 2

constraint c + g + pow(2,x) = c*c;
constraint xg == c;
constraint tot_g == g + xg*14 + (36 - xg)*13;
constraint tot_b == 1000 - tot_g;

solve satisfy;
output ["Total boys in school = " ++ show(tot_b)];

      Like

    • GeoffR's avatar

      GeoffR 1:46 pm on 2 December 2023 Permalink | Reply 

      
for g in range(13, 16):   # girls in class with extra pupil
  for c in range(1, 38):  # class number with extra pupil
    for x in range(1, 11):
      # number of classes with more girls than boys
      #... equals class number with extra pupil
      if g + c + 2**x == c*c:
        tot_g = g + c*14 + (36 - c)*13
        tot_b = 1000 - tot_g
        print(f"Total boys in school = {tot_b}.")

      Like

      • Jim Randell's avatar

        Jim Randell 11:00 am on 3 December 2023 Permalink | Reply

        @GeoffR: Would this give the right answer if there were 15 girls in the largest class?

        Like

    • GeoffR's avatar

      GeoffR 12:10 pm on 3 December 2023 Permalink | Reply

      @JimR: I think the following logic shows that g must be even and of value 14, if my logic is OK.

      The teaser requirements can be expressed as:
      c + g + 2^x = c*c, which reduces to: c*(c – 1) = g + 2^x

      where:
      g = number of girls in class with extra pupil, and c = class number with extra pupil.
      Also x is an integer power of 2.

      Analysis:
      Looking at the equation, it can be seen that:
      1) c * (c-1) will always be of even parity for consecutive integers.
      2) 2^x will always be even , except for 2^0 = 1, which does not give a viable c value.
      3) The RHS of the equation must therefore be even to be of equal parity to the LHS.
      4) This means that both g and 2^x must both be even to maintain parity.
      5) g must be one of (13, 14 or 15), leading to g = 14

      Like

    • GeoffR's avatar

      GeoffR 9:10 am on 5 December 2023 Permalink | Reply

      Using girls = 14 for girls in class with extra pupil (see previous posting) for a one-liner,
      or a two-liner for better readability.

      
print('Boys =',[1000 - (14 + c * 14 + (36 - c)* 13) for x in range(1, 10)
 for c in range(2, 37) if c * (c - 1) == 14 + 2**x].pop())

      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