teaser | S2T2 | Page 22

Updates from August, 2023 Toggle Comment Threads | Keyboard Shortcuts

Jim Randell 9:28 am on 3 August 2023 Permalink | Reply
Tags: by: Graham Smithers ( 84 )
Teaser 2640: Megan’s number
From The Sunday Times, 28th April 2013 [link] [link]

I had ten cards and each was labelled with a different digit. Megan chose three of these cards and arranged them to give a number. Beth then chose some of the remaining cards and also arranged them as a number. Finally Jan took some, or all, of the remaining cards and produced her number.

If Megan multiplied her number by its last digit, she would get Beth’s number, and if Megan multiplied her number by its first digit she would get Jan’s number.

Who has the biggest number and what is it?

[teaser2640]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 9:29 am on 3 August 2023 Permalink | Reply
  It is straightforward to just consider possible 3-digit numbers for Megan. (Although we could reduce the number of candidates with some analysis).
  
  This Python program runs in 50ms. (Internal runtime is 1.4ms).
  
  Run: [ @replit ]
```
from enigma import (irange, is_duplicate, printf)

# Megan's number has 3 different digits
for M in irange(100, 999):
  # Beth's number
  B = M * (M % 10)
  # J's number
  J = M * (M // 100)
  # all digits are distinct
  if is_duplicate(M, B, J): continue

  # who has the maximum number?
  d = { M: 'M', B: 'B', J: 'J' }
  m = max(d.keys())
  printf("max = {x} = {m} [M={M} B={B} J={J}]", x=d[m])
```
  Solution: Beth’s number is the largest. It is 819.
  
  The numbers are:
  
  M = 273
  B = 273 × 3 = 819
  J = 273 × 2 = 546
  
  LikeLike
Reply Cancel reply
Required fields are marked *

Name *

Email *

Website

Notify me of new comments via email.
Notify me of new posts via email.
Δ
Jim Randell 9:11 am on 1 August 2023 Permalink | Reply
Tags: by: Oliver D Anderson ( 2 )
Brainteaser 1636: Bubble sum
From The Sunday Times, 16th January 1994 [link]

My son recently sent me a rather nice GCSE project concerned with non touching soap bubbles. Imagine you are blowing bubbles either separately or into other bubbles. For instance, if you blew three bubbles, you could do this in exactly four ways:

How many configurations are there for nine bubbles?

[teaser1636]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 9:11 am on 1 August 2023 Permalink | Reply
  This program constructs the different arrangement of bubbles. An empty bubble is represented by the empty tuple, and bubbles are enclosed by placing them in a tuple in order. But when the arrangement is printed we don’t print the outermost enclosing brackets of the tuple (which allows for separate bubbles).
  
  This Python program runs in 96ms. (Internal runtime is 37ms).
  
  Run: [ @replit ]
```
from enigma import (decompose, cproduct, uniq, wrap, join, arg, printf)

# generate unique configurations for <n> bubbles
@wrap(uniq)
def bubbles(n):
  if n == 0:
    yield ()
  else:
    # combine two smaller configurations
    for (x, y) in decompose(n, 2, increasing=1, sep=0, min_v=1):
      for (bx, by) in cproduct([bubbles(x), bubbles(y)]):
        yield tuple(sorted(bx + by))
    # or enclose n - 1 bubbles
    for b in bubbles(n - 1):
      yield (b,)

# format a bubble configuration (default: without outermost enclosure)
def fmt(bs, enc=""):
  return join((fmt(b, enc="()") for b in bs), sep=" ", enc=enc)

n = arg(9, 0, int)
printf("[bubbles({n})]")
for (i, bs) in enumerate(bubbles(n), start=1):
  printf("{i}: {bs}", bs=fmt(bs))
```
  Solution: For 9 bubbles there are 719 configurations.
  
  The program is fast enough up to about 15 bubbles (235,381 configurations) without bothering about caching results.
  
  A configuration of bubbles can be represented as a tree, with an arc between bubble X and bubble Y if X directly contains Y. We also add arcs from a root bubble to all outermost bubbles (this does the job of the outermost enclosing tuple in my program above). And for n bubbles this gives us an unlabelled rooted tree with (n + 1) nodes.
  
  So we can count the number of bubble configurations by determining the number of unlabelled rooted trees.
  
  And this is sequence OEIS A000081, which has the following recurrence relation:
  
  $\displaystyle a(n+1) = \frac{1}{n} \sum_{k=1}^{n} \left( \sum_{d | k}^{}{d \cdot a(d)} \right) a(n-k+1)$
  
  Fortunately this is implemented fairly easily:
  
  Run: [ @replit ]
```
from enigma import (irange, divisors, cache, arg, printf)

# the number of different ways to draw diagrams with n bubbles is the
# number of unlabelled rooted trees with (n + 1) nodes = OEIS A000081
@cache
def a(n):
  if n < 2: return n
  r = 0
  for k in irange(1, n - 1):
    r += sum(d * a(d) for d in divisors(k)) * a(n - k)
  return r // (n - 1)

# number of configurations for <n> bubbles
bubbles = lambda n: a(n + 1)

n = arg(9, 0, int)
k = bubbles(n)
printf("{n} bubbles -> {k} arrangements")
```
  And this allows us to calculate much larger numbers (although for very large numbers we need to increase the recursion limit on the Python interpreter).
  
  LikeLike
Jim Randell 11:35 am on 30 July 2023 Permalink | Reply
Tags: by: Victor Bryant ( 146 )
Brain-Teaser 941: A Brain Teaser
From The Sunday Times, 3rd August 1980 [link]

I showed Charlie the division sum illustrated above, and told him that, as usual in this sort of problem, each letter represents one particular digit throughout, and different letters represent different digits. This baffled Charlie, as he has always been hopeless at division, so I reminded him that any division sum can be re-interpreted in terms of multiplication, thus:

A × BRAIN = TEASER

That made Charlie chuckle (he’s a simple lad), but it didn’t help him much. So to assist him with his arithmetic, I reminded him of the fact that:

TEN + TWO is a multiple of 4.

He then had enough information to interpret each letter correctly, but to save him some work I also reminded him that:

NINE and NINETEEN − TEN are multiples of 9

whereas:

NINE + TEN is not a multiple of 2, 3 or 5.

What does ANSWER equal?

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

[teaser941]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
GeoffR and Jim Randell are discussing. Toggle Comments
- Jim Randell 11:36 am on 30 July 2023 Permalink | Reply
  We can solve this puzzle using the [[ SubstitutedExpression ]] solver from the enigma.py library.
  
  The following run file executes in 79ms. (Internal runtime of the generated program is 2.8ms).
```
#! python3 -m enigma -rr

SubstitutedExpression

"A * BRAIN = TEASER"
"(TEN + TWO) % 4 = 0"

"NINE % 9 = 0"
"(NINETEEN - TEN) % 9 = 0"
"all((NINE + TEN) % n > 0 for n in [2, 3, 5])"

--answer="ANSWER"
```
  Solution: ANSWER = 780196.
  
  The initial alphametic division has two solutions:
  
  327026 ÷ 46718 = 7
  397096 ÷ 56728 = 7
  
  However the first of these is eliminated by the requirement: “TEN + TWO is a multiple of four”.
  
  LikeLike
- GeoffR 4:19 pm on 30 July 2023 Permalink | Reply
```
% A Solution in MiniZinc
include "globals.mzn";

var 1..9:A; var 1..9:B; var 0..9:R; var 0..9:I; 
var 1..9:N; var 1..9:T; var 0..9:E; var 0..9:S; 
var 0..9:W; var 0..9:O; 

constraint all_different([A, B, R, I, N, T, E, S, W, O]);

var 100..999:TEN == 100*T + 10*E + N;
var 100..999:TWO == 100*T + 10*W + O;
var 1000..9999:NINE == 1010*N + 100*I + E;
var 10000..99999:BRAIN == 10000*B + 1000*R + 100*A + 10*I + N;
var 100000..999999:TEASER == 100000*T + 10010*E + 1000*A + 100*S + R;
var 100000..999999:ANSWER == 100000*A + 10000*N + 1000*S + 100*W + 10*E + R;
var 10000000..99999999:NINETEEN == 10010001*N + 1000000*I + 1000*T + 10110*E;

constraint A * BRAIN = TEASER;
% TEN + TWO is a multiple of 4.
constraint (TEN + TWO) mod 4 == 0;

% NINE and NINETEEN − TEN are multiples of 9
constraint NINE mod 9 == 0 /\ (NINETEEN - TEN) mod 9 == 0;

% NINE + TEN is not a multiple of 2, 3 or 5.
constraint (NINE + TEN) mod 2 > 0 /\ (NINE + TEN) mod 3 > 0  /\ (NINE + TEN) mod 5 > 0;

 solve satisfy;
 output["ANSWER = " ++ show(ANSWER) ++ "\n"
 ++ "[A, B, R, I, N, T, E, S, W, O]  = " ++ show ([A, B, R, I, N, T, E, S, W, O] )]; 

% ANSWER = 780196
% [A, B, R, I, N, T, E, S, W, O]  = 
% [7, 5, 6, 2, 8, 3, 9, 0, 1, 4]
% ----------
% ==========
```
  LikeLike

Jim Randell 4:38 pm on 28 July 2023 Permalink | Reply
Tags: by: John Owen ( 33 )

Teaser 3175: Blindfold roulette

From The Sunday Times, 30th July 2023 [link] [link]

Our roulette wheel has fewer than 100 equal-sized sectors. Before each game a fixed number (fewer than half) of the sectors are randomly designated winning ones and the others as losing. A player can see which are the winning sectors, then is blindfolded. A ball is then placed at random in a winning sector and the player chooses to spin (S) the wheel or move (M) the ball clockwise by one sector. The game continues from there (the player has the same choices) and ends when the ball lands in a losing sector.

Alf’s longest winning run was MMSM while Bert’s was SSS and Charlie’s was MMMS. Being expert logicians, they had always chosen the option that gave the better chance of the ball landing in a winning sector. Remarkably, the probabilities of achieving each run of success were the same.

How many sectors are there and how many are winning sectors?

[teaser3175]

Jim Randell 6:55 pm on 28 July 2023 Permalink | Reply
This is my first stab at a program that explores the solution space looking for viable solutions. It is not very fast (it runs in 1.31s), and it stops after the first viable solution is found. (A second viable solution is eliminated by rejecting situations where both plays have the same probability).

It works by considering possible the total number of sectors n, and the number of winning sectors w, and then dividing the winning sectors into contiguous clumps, and calculating the corresponding probabilities.

Run: [ @replit ]
```
from enigma import (Rational, irange, decompose, intersect, divf, seq2str, printf)

Q = Rational()

# with <n> sectors, <w> winning in clumps <ws>, find probability of seq <seq>
def prob(n, w, ws, seq):
  P = 1
  # calculate probability of a good spin
  S = Q(w, n)
  # calculate probability of a good move
  zs = ws  # winning zones
  for v in seq:
    z = sum(zs)
    zs = list(x - 1 for x in zs if x > 1)
    M = Q(sum(zs), z)
    # check the sequence
    if v == 'M' and M > S:
      P *= M
    elif v == 'S' and S > M:
      P *= S
      zs = ws
    else:
      return
  return P

# with <n> sectors, <w> winning, collect common probabilities for sequences <ss>
def solve(n, w, ss):
  # collect probabilities
  d = dict((k, set()) for k in ss)
  # break the sectors into k contiguous blocks
  for k in irange(1, w):
    for ws in decompose(w, k, increasing=1, sep=0, min_v=1):
      # calculate the probabilities for A, B, C
      for (k, v) in d.items():
        P = prob(n, w, ws, k)
        if P is not None: v.add(P)
  # return common probabilities
  return intersect(d.values())

# solve the puzzle
def main():
  # consider number of sectors <n>
  for n in irange(9, 99):
    # consider number of winning sectors <w>
    for w in irange(4, divf(n - 1, 2)):
      # find common probabilities
      ps = solve(n, w, ['MMSM', 'SSS', 'MMMS'])
      if ps:
        printf("n={n} w={w} -> P={ps}", ps=seq2str(ps))
        return  # stop at the first solution

main()
```
Solution: There are 54 sectors in total, and 18 winning sectors.

In this case the probability of a good spin is:

P(S) = 18/54 = 1/3

So the probability of B’s run of SSS is:

P(SSS) = (1/3)³ = 1/27

And a configuration where each winning sector is isolated from the other winning sectors makes the probability of a good M move zero, so this is possible (although this is not the only viable configuration to permit this – there are 19 in total).

For A there are 2 possible configurations, one of them is:

(1, 1, 1, 1, 2, 3, 3, 3, 3)

Of the 18 winning sectors there are 9 that have a winning sector as a clockwise neighbour:

P(M) = 9/18 = 1/2 [which is > 1/3]

And of those 9 sectors only 4 of them have 2 neighbouring winning sectors going clockwise:

P(MM|M) = 4/9 = 1/2 [which is > 1/3]

And there are no winning sectors with 3 neighbouring clockwise winning sectors:

P(MMM|MM) = 0 [which is < 1/3]

So at this point A would choose S, which resets the situation back to the start, so the next choice (if he gets one) would be M.

Hence the overall probability of MMSM is:

P(MMSM) = (9/18)×(4/9)×(1/3)×(9/18) = 1/27

which is the same as B’s run.

For C, with a configuration (chosen from 9 possibilities) of:

(2, 2, 2, 2, 2, 4, 4)

We get:

P(M) = 11/18
P(MM|M) = 4/11
P(MMM|MM) = 2/4 = 1/2
⇒
P(MMMS) = (11/18)×(4/11)×(2/4)×(1/3) = 1/27

However if we permit situations where the probabilities of M and S are equal then there is a further solution with 64 total sectors and 16 winning sectors.

The probability of a good S is:

P(S) = 16/64 = 1/4

And choosing a configuration (of 12 the possible configurations) where each winning sector is isolated we get:

P(SSS) = (1/4)³ = 1/64

For A the only possible distribution is:

(1, 1, 2, 2, 2, 2, 3, 3)

which gives:

P(M) = 8/16 = 1/2
P(MM|M) = 2/8 = 1/4 [same as P(S)]
⇒
P(MMSM) = (8/16)×(2/8)×(1/4)×(8/16) = 1/64

And for C there are 14 possible distributions, we choose:

(2, 2, 2, 3, 3, 4)

which gives:

P(M) = 10/16 = 5/8
P(MM|M) = 4/10 = 2/5
P(MMM|MM) = 1/4 [same as P(S)]
⇒
P(MMMS) = (10/16)×(4/10)×(1/4)×(1/4) = 1/64

So in order for the puzzle to have a unique answer, we have to eliminate scenarios where when choosing between M and S that calculated probabilities are the same

LikeLike
- Jim Randell 10:55 am on 30 July 2023 Permalink | Reply
  By analysing the probabilities associated with the given sequences (which I will post later) we can eliminate a lot of the testing done by my program above.
  
  Here it is adapted to include the conditions:
  
  decomposition for A must include a clump of size 3 or more
  decomposition for C must include a clump of size 4 or more
  n² divides w³
  
  (This last condition is the same as suggested by Frits in his comment below).
  
  It calculates the probability for B, and then finds example decompositions for A and C that give the same probability.
  
  This Python program fully explores the solution space and runs in 92ms. (Internal runtime is 27ms).
  
  Run: [ @replit ]
```
from enigma import (Rational, irange, divf, div, decompose, first, printf)

Q = Rational()

# with <n> sectors, <w> winning in clumps <ws>, find probability of seq <seq>
def prob(n, w, ws, seq):
  P = 1
  # calculate probability of a good spin
  S = Q(w, n)
  # calculate probability of a good move
  (zs, d) = (ws, w)  # winning zones
  for v in seq:
    # calculate new zones
    zs = list(x - 1 for x in zs if x > 1)
    n = sum(zs)
    M = Q(n, d)
    # check the sequence
    if v == 'M' and M > S:
      P *= M
      d = n
    elif v == 'S' and S > M:
      P *= S
      (zs, d) = (ws, w)
    else:
      return
  return P

# with <n> sectors, <w> winning, sequence <seq>
# find winning clumps <ws> that give probability <p>
# subject to max(<ws>) >= <m>
def solve(n, w, seq, m, p):
  for k in irange(1, w):
    for ws in decompose(w, k, increasing=1, sep=0, min_v=1):
      if ws[-1] < m: continue
      if prob(n, w, ws, seq) == p:
        yield ws

# consider possible n, w values such that n^2 divides w^3
for n in irange(9, 99):
  for w in irange(4, divf(n - 1, 2)):
    k3 = div(w**3, n**2)
    if k3 is None: continue

    # calculate probability for B (SSS)
    # a split into <w> clumps of size 1 will do
    B = prob(n, w, [1] * w, "SSS")

    # find examples for C (MMMS) and A (MMSM):
    # for A we need at least one clump of size 3 or more
    As = first(solve(n, w, "MMSM", 3, B), 1)
    if not As: continue

    # for C we need at least one clump of size 4 or more
    Cs = first(solve(n, w, "MMMS", 4, B), 1)
    if not Cs: continue

    # output solution
    printf("n={n} w={w} -> P={B}, A={As} C={Cs}")
```
  Here is the analysis:
  
  C was able to make 3 consecutive Ms, so there must have been a block of at least 4 contiguous winning sectors in that game. Hence the wheel must have at least 9 sectors in total.
  
  Similarly in the game where A made 2 consecutive Ms, there must have been a block of at least 3 contiguous winning sectors.
  
  If the wheel has n sectors in all, and w winning sectors, then the probability of winning on a spin is:
  
  P(S) = w/n
  
  (which is less than 50% by definition).
  
  So for B we have:
  
  P(SSS) = w³/n³
  
  regardless of the configuration of the winning sectors.
  
  Except we also require there to be some configuration where:
  
  P(S) > P(M)
  
  But if every winning sector is in a clump of 1 (which is possible as there are fewer than half winning sectors) we have:
  
  P(M) = 0
  
  so the inequality above can be satisfied.
  
  Now if we consider a situation where k1 of the winning sectors are “good” (i.e. they are directly anti-clockwise from another winning sector), then we have:
  
  P(M) = k1/w
  
  For the next move suppose only k2 of the k1 sectors are “good”, we have:
  
  P(MM) = (k1/w)(k2/k1) = k2/w
  
  and so on:
  
  P(MMM) = (k1/w)(k2/k1)(k3/k2) = k3/w
  
  where: (w, k1, k2, k3) form a decreasing sequence.
  
  And so for C we have:
  
  P(MMMS) = (k3/w)(w/n) = k3/n
  
  And this must be the same as P(SSS) above:
  
  k3/n = w³/n³
  k3 = w³/n²
  
  So: n² must divide into w³ (as k3 is an integer).
  
  This narrows us down to just 4 possible (n, w) pairs:
  
  (27, 9)
  (54, 18)
  (64, 16)
  (81, 27)
  
  Which have give the following probabilities for B
  
  (27, 9) → 1/27
  (54, 18) → 1/27
  (64, 16) → 1/64
  (81, 27) → 1/27
  
  And for C gives k3 values of:
  
  (27, 9) → 1
  (54, 18) → 2
  (64, 16) → 1
  (81, 27) → 3
  
  For A we get:
  
  P(MMSM) = k1.k2 / n.w
  
  Giving the following k1.k2 values:
  
  (27, 9) → 9 (not possible)
  (54, 18) → 36 = 12×3 = 9×4
  (64, 16) → 16 = 8×2
  (81, 27) → 81 (not possible)
  
  So there are only 2 pairs to consider, and we need to find appropriate decompositions of the winning sectors for A and C that give the appropriate probability (same as B), and where the choice to play M or S is always that with the larger probability.
  
  LikeLike

Frits 2:01 pm on 29 July 2023 Permalink | Reply

Extra analysis:

for MMMS we have sum(x – 3 for x in ws if x > 3) * n^2 = w^3
for MMSM we have sum(x – 1 for x in ws if x > 1) * sum(x – 2 for x in ws if x > 2) *n^2 = w^4

This adaptation of Jim’s program checks the full solution space in 30ms.

 
from enigma import (Rational, irange, decompose, intersect, divf, seq2str, printf)
 
Q = Rational()
 
# with <n> sectors, <w> winning in clumps <ws>, find probability of seq <seq>
def prob(n, w, ws, seq):
  P = 1
  # calculate probability of a good spin
  S = Q(w, n)
  # calculate probability of a good move
  zs = ws  # winning zones
  for v in seq:
    z = sum(zs)
    zs = list(x - 1 for x in zs if x > 1)
    M = Q(sum(zs), z)
    
    # check the sequence
    if v == 'M' and M > S:
      P *= M
    elif v == 'S' and S > M:
      P *= S
      zs = ws
    else:
      return
    
  return P if P == S**3 else None
 
# with <n> sectors, <w> winning, collect common probabilities for sequences <ss>
def solve(n, w, ss):
  # collect probabilities
  d = dict((k, set()) for k in ss)

  w3byn2, w4byn2 = w**3 // n**2, w**4 // n**2
  
  # break the sectors into k contiguous blocks
  for k in irange(1, w):
    for ws in decompose(w, k, increasing=1, sep=0, min_v=1):
      # we have a solution if P = (w/n)^3 has been found for both MMSM and MMMS
      if d[ss[0]] and d[ss[2]]:
        return d[ss[0]]
      
      fn = lambda s, y: sum(x - y for x in s if x > y) 
      # check if P can be calculated as (w/n)^3
      if (fn(ws, 3) != w3byn2 or d[ss[2]]) and \
         (fn(ws, 1) * fn(ws, 2) != w4byn2 or d[ss[0]]): continue
      
      # calculate only the probabilities for MMSM and MMMS  
      # (as P for SSS equals (w/n)^3 if ws = [1, 1, ..., 1, 1])
      for s in [ss[0], ss[2]]:
        P = prob(n, w, ws, s)
        if P: d[s] = {P}
  # return common probabilities
  return intersect(d.values())
 
# solve the puzzle
def main():
  # consider number of sectors <n>
  for n in irange(9, 99):
    # consider number of winning sectors <w>
    for w in irange(4, divf(n - 1, 2)):
      # skip early if probability for MMSM and MMMS can't be (w/n)^3
      if w**4 % n**2 or w**3 % n**2: continue
      # find common probabilities
      ps = solve(n, w, ['MMSM', 'SSS', 'MMMS'])
      if ps:
        printf("n={n} w={w} -> P={ps}", ps=seq2str(ps))
        # continue to check the full solution space
 
main()

LikeLike

Frits 9:04 pm on 30 July 2023 Permalink | Reply

Trying to perform decomposition with SubstitutedExpression().
In order to not use too many variables the maximum number of decomposition variables is calculated.
The programs runs in 185ms.

 
from enigma import SubstitutedExpression, divf, div

# function used in probability formula for M
fn = lambda s, y: sum(x - y for x in s if x > y) 

symbols = "ABCDEFGHIJKLMNOPQRabcdefghijklmopqrtuvxyx"
syms2 = ["ST", "UV", "WX", "YZ"]

# consider possible n, w values such that n^2 divides w^3
for n in range(9, 100):
  for w in range(4, divf(n - 1, 2) + 1):
    if w**3 % n**2: continue
    
    # try to decompose <w> into  A, B, .. , xx 
    # maximum number of elements to decompose <w>
    mx = (w + 1) - (w**2 // n + 2)
    # maximum number of 2-digit variables needed
    n2 = w // 10
    
    # invalid digit / symbol assignments
    d2i = {d: set() for d in range(10)}
    for i in range(n2 - 1):
      for d in range((w // (n2 - i)) // 10 + 1, 10):
        d2i[d].add(syms2[i][0])
    
    # build expressions
    exprs = []
    for i in range(mx - 1):
      j = mx - n2 - i
      cur = symbols[i] if j > 0 else syms2[-j]
      nxt = symbols[i + 1] if j > 1 else syms2[0] if j == 1 else syms2[(1 - j)]
      
      if i < mx - 2:
        exprs.append(f"{{{cur}}} <= {{{nxt}}}")
      else:
        exp = f"{{{cur}}} <= {{{nxt}}}"  # save for later
        
      # restrict values of single digit variables
      if len(cur) == 1:
        for d in range(w // (mx - i) + 1, 10):
          d2i[d].add(cur)
      else:
        # restrict values by adding an expression
        exprs.append(f"{{{cur}}} <= {w // (mx - i)} ")

    vars = [f"{{{s}}}" for s in symbols[:mx - n2]] 
    vars += [f"{{{s}}}" for s in syms2[:n2]]
    svars = ','.join(vars)
    
    # direct assignment of last variable
    exprs.append(f"{w} - sum([{','.join(vars[:-1])}]) = {vars[-1]}",)
    exprs.append(exp)
    
    exp = ""
    # for MMMS we have sum(x – 3 for x in ws if x > 3) * n^2 = w^3
    exp += f"(c1 := (fn(svars:= [{svars}], 3) * {n**2} == {w**3}) and "
    exp += f"{n} * fn([{svars}], 1) > {w**2} and "
    exp += f"{n} * fn([{svars}], 2) > {w} * fn([{svars}], 1) and "
    exp += f"{n} * fn([{svars}], 3) > {w} * fn([{svars}], 2) and "
    exp += f"{n} * fn([{svars}], 4) < {w} * fn([{svars}], 3)) or "
    
    # for MMSM we have sum(x – 1 for x in ws if x > 1) * 
    #                  sum(x - 2 for x in ws if x > 2) * n^2 = w^4
    exp += f"(c2 := (fn([{svars}], 1) * fn([{svars}], 2) * {n**2} == {w**4}) "
    exp += f"and {n} * fn([{svars}], 1) > {w**2} and "
    exp += f"{n} * fn([{svars}], 2) > {w} * fn([{svars}], 1) and "
    exp += f"{n} * fn([{svars}], 3) < {w} * fn([{svars}], 2))"
    exprs.append(exp)
    
    # the alphametic puzzle
    p = SubstitutedExpression(
      exprs,
      answer="c1, c2, vars",
      d2i=d2i,
      distinct="",
      env=dict(fn=fn),
      reorder=0,
      verbose=0,    # use 256 to see the generated code
    )

    # print answers
    cnts = [0, 0]
    for ans in p.answers():
      #print(f"{ans}")
      if ans[0]: cnts[0] = 1
      if ans[1]: cnts[1] = 1
    
      if cnts == [1, 1]:
        print(f"answer: n={n}, w={w}")
        break

LikeLike

Tony Brooke-Taylor 7:11 pm on 3 August 2023 Permalink | Reply

You can do a lot with Frits’ MMMS result and the limits for n and w, to constrain the search space. I used a slightly different paradigm from Jim’s, considering numbers of winning segments with clockwise winning neighbours, so my nomenclature is a bit different. Also I am coding in Rust now so won’t reproduce my solution here. However, I have written up a solution which can be applied manually in the comments of my code at:

https://github.com/TuonyBT/teaser3175/blob/master/src/main.rs

LikeLike

Frits 9:52 pm on 8 August 2023 Permalink | Reply

There is a different answer (n=64, w=16) when a winning run is supposed to be followed by a loss.

from enigma import (Rational, irange, decompose, intersect, divf, seq2str, printf)

fn = lambda s, y: sum(x - y for x in s if x > y) 
 
Q = Rational()
 
# with <n> sectors, <w> winning in clumps <ws>, find probability of seq <seq>
def prob(n, w, ws, seq, target):
  P = 1
  # calculate probability of a good spin
  S = Q(w, n)
  # calculate probability of a good move
  zs = ws  # winning zones
  for v in seq:
    z = sum(zs)
    zs = list(x - 1 for x in zs if x > 1)
    M = Q(sum(zs), z)
    
    # check the sequence
    if v == 'M' and M > S:
      P *= M
    elif v == 'S' and S > M:
      P *= S
      zs = ws
    else:
      return
  
  P *= (1 - fn(ws, 1) / w) if seq[-1] == 'S' else (1 - fn(ws, 2) / fn(ws, 1)) 
  return P if P == S**3 * (n - w) / n else None
  

# with <n> sectors, <w> winning, collect common probabilities for sequences <ss>
def solve(n, w, ss):
  # collect probabilities
  d = dict((k, set()) for k in ss)

  # probability for winning run SSS
  F =  (n - w) * w**4 / n**3
  
  # maximum number of elements to decompose <w>
  mx = (w + 1) - (w**2 // n + 2)
  # break the sectors into k contiguous blocks
  for k in irange(1, mx):
    for ws in decompose(w, k, increasing=1, sep=0, min_v=1):
      # we have a solution if P = (w/n)^3 has been found for both MMSM and MMMS
      if d[ss[0]] and d[ss[2]]:
        return d[ss[0]]
      
      # check if P can be calculated as F
      if (fn(ws, 3) * w - fn(ws, 1) * fn(ws, 3) != F or d[ss[2]]) and \
         (fn(ws, 1) * fn(ws, 2) - fn(ws, 2)**2 != F or d[ss[0]]): continue
 
      # calculate only the probabilities for MMSM and MMMS  
      # (as P for SSS equals F if ws = [1, 1, ..., 1, 1])
      for s, t in [(ss[0], (w/n)**3 ), (ss[2], (w/n)**3)]:
        P = prob(n, w, ws, s, t)
        if P: d[s] = {P}
  # return common probabilities
  return intersect(d.values())

# fn(a, b) = sum(x – b for x in a if x > b)
# for SSS we have probablility (w/n)**3 * (n - w) / n
# for MMMS we have fn(ws, 3) * w - fn(ws, 1) * fn(ws, 3) = (n - w) * w**4 / n**3
# for MMSM we have fn(ws, 1) * fn(ws, 2) - fn(ws, 2)**2  = (n - w) * w**4 / n**3

# solve the puzzle
def main():
  # consider number of sectors <n>
  for n in irange(9, 99):
    # consider number of winning sectors <w>
    for w in irange(4, divf(n - 1, 2)):
      # skip if probability for MMSM and MMMS can't be (w/n)^3 * (n - w) / n
      if (w**4 * n - w**5) % n**2: 
        continue
      
      # find common probabilities
      ps = solve(n, w, ['MMSM', 'SSS', 'MMMS'])
      if ps:
        printf("\nn={n} w={w} -> P={ps}\n", ps=seq2str(ps))
        # continue to check the full solution space
 
main()

LikeLike

Jim Randell 10:08 pm on 9 August 2023 Permalink | Reply

I interpreted the probabilities as being those of achieving the sequences given, and not being concerned about what happened on the next play.

But I augmented my program to include the probability of a loss on the next play of each run and I got 4 answers to the puzzle:

n=27, w=9, P=2/81
n=54, w=18, P=2/81
n=64, w=16, P=3/256
n=81, w=27, P=2/81

For example, with the first of these we have 27 sectors and 9 of them are winning, so:

The probability of a good spin is 9/27 = 1/3 (and the probability of a bad spin is 2/3).

So for B the probability of (S=win, S=win, S=win, S=lose) is:

P(SSS(S)) = (1/3)×(1/3)×(1/3)×(1 − 1/3) = 2/81

For A the configuration could be (1, 2, 3, 3), giving the probability of (M=win, M=win, S=win, M=win, M=lose) as:

P(MMSM(M)) = (5/9)×(2/5)×(1/3)×(5/9)×(1 − 2/5) = 2/81

For C the configuration could be (1, 4, 4), giving the probability of (M=win, M=win, M=win, S=win, M=lose) as:

P(MMMS(M)) = (6/9)×(4/6)×(2/4)×(1/3)×(1 − 6/9) = 2/81

LikeLike
- Frits 10:57 am on 10 August 2023 Permalink | Reply
  @Jim, you are right. Using rational numbers class Q in line 28/29 also yields 4 answers.
```
   
P *= (1 - Q(fn(ws, 1), w)) if seq[-1] == 'S' else (1 - Q(fn(ws, 2), fn(ws, 1))) 
return P if n * P == S**3 * (n - w) else None
```
  LikeLike

Jim Randell 9:30 am on 27 July 2023 Permalink | Reply
Tags: by: Victor Bryant ( 146 )

Teaser 2632: Times table

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

I have placed the numbers 1 to 16 (in no particular order) in a four-by-four table. As you go across each row of the table (from left to right) the four numbers are increasing, and as you go down each column the four numbers are increasing. If you read the top row as one long number, it is a four-figure number which equals the product of the four numbers in the second row.

What are the four numbers in the second row?

[teaser2632]

Jim Randell 9:31 am on 27 July 2023 Permalink | Reply
We can use the [[ SubstitutedExpression ]] solver from the enigma.py to solve this puzzle.

The following run file executes in 152ms. (Internal runtime for the generated code is 76ms).

Run: [ @replit ]
```
#! python3 -m enigma -rr

SubstitutedExpression

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

--base=17
--digits="1-16"

# rows are increasing
"A < B" "B < C" "C < D"
"E < F" "F < G" "G < H"
"I < J" "J < K" "K < L"
"M < N" "N < P" "P < Q"

# columns are increasing
"A < E" "E < I" "I < M"
"B < F" "F < J" "J < N"
"C < G" "G < K" "K < P"
"D < H" "H < L" "L < Q"

# the top row gives a 4-digit product of the numbers in the second row
"D < 10"
"nconcat(A, B, C, D, base=10) == E * F * G * H"

--answer="(E, F, G, H)"

--template="(A B C D) (E F G H) (I J K L) (M N P Q)"
```
Solution: The numbers in the second row are: 2, 7, 8, 13.

The first two rows are:

(1, 4, 5, 6)
(2, 7, 8, 13)

And we have:

2 × 7 × 8 × 13 = 1456

The bottom two rows are:

(3, 9|10, 10|11|12, 14|15)
(9|10|11, 11|12, 14|15, 16)

So there are 10 ways that the grid can be filled out.

LikeLike
- Frits 3:25 pm on 27 July 2023 Permalink | Reply
  
  @Jim,
  
  Which tags do you use for text in the grey commentary boxes ?
  I can see blockquotes are used in the final html.
  
  LikeLike
  - Jim Randell 3:31 pm on 27 July 2023 Permalink | Reply
    
    @Frits: They are just standard HTML <blockquote>...</blockquote> tags.
    
    LikeLike

Frits 3:06 pm on 27 July 2023 Permalink | Reply

Same concept but with calculating upper and lower bounds.

from enigma import SubstitutedExpression

symbols = "ABCDEFGHIJKLMNPQ"

# (row i, col j) has i * j - 1 lower values  (rows and cols 1-4)
# (row i, col j) has (5 - i) * (5 - j) - 1 higher values   
# position <p> in symbols has rowno p // 4 + 1 and colno p % 4 + 1

# for each symbol determine lower and higher values
lh = [(symbols[p], (p // 4 + 1) * (p % 4 + 1) - 1, 
                   (4 - p // 4 ) * (4 - p % 4) - 1) for p in range(16)]

# invalid digit / symbol assignments
d2i, s2d = dict(), dict()
for d in range(1, 17):
  vs = set()
  if d > 9: vs.update('ABCD')
  
  for s, lw, hi in lh:
    if d <= lw: vs.update(s)
    if d > 16 - hi: vs.update(s)
    
  d2i[d] = vs
  
if 1:
  print("Allowed values:")
  for s in symbols:
    print(s, ":", end=" ")
    c, v = 0, 0
    for k, vs in d2i.items():
      if s not in vs:
        print(k, end=" ")
        c += 1
        v = k
    print()
    if c == 1:
      s2d[s] = v

distinct = ''.join([x for x in symbols if x not in s2d])

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


# the alphametic puzzle
p = SubstitutedExpression(
  [
   "A < B",
   "B < F",
   "A < E",
   "E < F",
   "B < C",
   "C < G",
   "F < G",
   "C < D",
   "D < H",
   "G < H",
   
   # the top row gives a 4-digit product of the numbers in the second row
   "nconcat(A, B, C, D, base=10) == E * F * G * H",
   
   "E < I",
   "F < J",
   "I < J",
   "G < K",
   "J < K",
   "H < L",
   "K < L",
   "I < M",
   "J < N",
   "M < N",
   "K < P",
   "N < P",
   "L < Q",
   "P < Q",
  ],
  answer="((A, B, C, D), (E, F, G, H), (I, J, K, L), (M, N, P, Q))",
  base=17,
  d2i=d2i,
  s2d=s2d,
  distinct=distinct,
  digits=range(1, 17),
  reorder=0,
  verbose=0,    # use 256 to see the generated code
)

# print answers
for ans in p.answers():
  print(f"{ans}")

  
Allowed values:
A : 1
B : 2 3 4 5
C : 3 4 5 6 7 8 9
D : 4 5 6 7 8 9
E : 2 3 4 5
F : 4 5 6 7 8
G : 6 7 8 9 10 11
H : 8 9 10 11 12 13 14
I : 3 4 5 6 7 8 9
J : 6 7 8 9 10 11
K : 9 10 11 12 13
L : 12 13 14 15
M : 4 5 6 7 8 9 10 11 12 13
N : 8 9 10 11 12 13 14
P : 12 13 14 15
Q : 16

LikeLike

GeoffR 7:17 pm on 27 July 2023 Permalink | Reply

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

% ABCD
% EFGH
% IJKL
% MNPQ

% Numbers in the table
var 1..16:A; var 1..16:B; var 1..16:C; var 1..16:D;
var 1..16:E; var 1..16:F; var 1..16:G; var 1..16:H;
var 1..16:I; var 1..16:J; var 1..16:K; var 1..16:L;
var 1..16:M; var 1..16:N; var 1..16:P; var 1..16:Q;
% Read the top row as one long number
var 1000..9999:ABCD == 1000*A + 100*B + 10*C + D;

constraint all_different([A,B,C,D,E,F,G,H,I,J,K,L,M,N,P,Q]);

% The four numbers are increasing in each row
constraint A < B /\ B < C /\ C < D;
constraint E < F /\ F < G /\ G < H;
constraint I < J /\ J < K /\ K < L;
constraint M < N /\ N < P /\ P < Q;

% The four numbers are increasing in each column
constraint A < E /\ E < I /\ I < M;
constraint B < F /\ F < J /\ J < N;
constraint C < G /\ G < K /\ K < P;
constraint D < H /\ H < L /\ L < Q;

% If you read the top row as one long number,  
% it is a four-figure number which equals the product 
% of the four numbers in the second row.
constraint ABCD == E * F * G * H;

solve satisfy;
output [" Four numbers in second row  are " ++ show([E, F, G, H])];

% Four numbers in second row  are [2, 7, 8, 13]
% ----------
% ==========

LikeLike

Jim Randell 11:12 am on 25 July 2023 Permalink | Reply
Tags: by: Robin Nayler ( 17 )

Teaser 2631: Family progression

From The Sunday Times, 24th February 2013 [link] [link]

I have five grandchildren: from oldest to youngest they are Imogen, Madeline, Alex, Matthew and Laurence. They were all born in different years and no two have a birthday in the same month. They were all born before noon and for each grandchild I have noted their time and date of birth as five numbers [in the following order]:

minute, hour, DD, MM, YY

(none of the numbers is zero, but they may have a leading zero).

Surprisingly, for each grandchild the five numbers form an arithmetic progression (i.e. increasing or decreasing by a fixed amount), and also in each case the sum of two of the five numbers equals the sum of the other three.

With the children in the order given above, list the months in which they were born.

[teaser2631]

Jim Randell 11:13 am on 25 July 2023 Permalink | Reply

If (mm, hh, DD, MM, YY) forms an arithmetic progression, then so does its reverse (YY, MM, DD, hh, mm) which is perhaps a more sensible order for date and time.

This Python program considers possible birth date/times that form appropriate sequences (from that start of the year 2000 up to the date of publication of the puzzle). And then collects sequences from 5 different years that occur in 5 different months.

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

from datetime import datetime
from enigma import (irange, cproduct, div, catch, subsets, group, attr, join, printf)

# (abbreviated) month names to use
month = "??? Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec".split()

# only consider dates before this (= publication date of puzzle)
M = datetime(2013, 2, 24)

# generate possible birth dates
def generate():
  # hh is 01-11, MM is 1-12
  # choose values for hh and MM
  for (hh, MM) in cproduct([irange(1, 11), irange(1, 12)]):
    # calculate the common difference
    d = div(MM - hh, 2)
    if not d: continue
    # fill in the remaining values
    (mm, DD, YY) = (hh - d, hh + d, MM + d)
    # does it form a valid date?
    if mm < 1 or YY < 1: continue
    t = catch(datetime, 2000 + YY, MM, DD, hh, mm)
    if t is None or not t < M: continue
    # calculate the sum of the progression
    s = 5 * mm + 10 * d
    # is the sum of 2 of the numbers equal to the sum of the other 3
    if s % 2 == 1: continue
    ns = (mm, hh, DD, MM, YY)
    if not any(2 * sum(ss) == s for ss in subsets(ns, size=2)): continue
    # viable date
    printf("[{t} = {ns}, d={d}, s={s}]")
    yield t

# collect dates by year
g = group(generate(), attr('year'))

# select 5 birth years, oldest to youngest
for ks in subsets(sorted(g.keys()), size=5):
  # select birthdates
  for ds in cproduct(g[k] for k in ks):
    # collect the months
    ms = list(d.month for d in ds)
    # there must be 5 different months
    if len(set(ms)) != 5: continue
    # output solution
    for (i, d) in enumerate(ds, start=1):
      printf("{i} -> {d}")
    printf("months = {ms}", ms=join((month[m] for m in ms), sep=", "))
    printf()

Solution: The months are: March, June, May, July, October.

And the birth date/times are:

Imogen = 2002-03-04 05:06, seq = (06, 05, 04, 03, 02)
Madeline = 2004-06-08 10:12, seq = (12, 10, 08, 06, 04)
Alex = 2006-05-04 03:02, seq = (02, 03, 04, 05, 06)
Matthew = 2008-07-06 05:04, seq = (04, 05, 06, 07, 08)
Laurence = 2012-10-08 06:04, seq = (04, 06, 08, 10, 12)

LikeLike

Frits 3:24 pm on 25 July 2023 Permalink | Reply

Using the new “decl” setting to remember assignment variables when denesting is requested.

from enigma import SubstitutedExpression

# invalid digit / symbol assignments
d2i = dict()
for d in range(0, 10):
  vs = set()
  if d > 1: vs.update('ACEGISTUVW')
  # as half the sum (2.5a + 5k) is an integer the year must be even
  if d % 2: vs.update('BDFHJ')
  # maximum difference between elements is three
  if not (0 < d < 4): vs.update('KLMNO')

  d2i[d] = vs
  
# YY, MM, DD, hh, mm 
# arithmetic progression: 
# AB, AB + -1**S * K, AB + 2 * -1**S * K, .. , AB + 4 * -1**S * K

# year, positive difference and sign
vars = [("AB", "K", "S"), ("CD", "L", "T"), ("EF", "M", "U"), 
        ("GH", "N", "V"), ("IJ", "O", "W")]

exprs, ms = [], ""
# build expressions        
for i, (a, k, s) in enumerate(vars):
  # decreasing ages
  exprs.append(("0" if not i else vars[i - 1][0]) + " < " + a + " <= " + str(8 + i))
  inc = "(-1)**" + s + " * " + k
  ms += a + " + " + inc + ", "

  exprs.append("0 < " + a + " + " +  inc + " <= 12")        # month
  exprs.append("0 < " + a + " + 3 * " + inc + " <= 11")     # hours
  exprs.append("0 < " + a + " + 4 * " + inc + " <= 59")     # minutes
  
  # make half the sum with highest and 1st or 2nd highest number
  y = "(" + s + " and 2.5 * " + a + " + 5 * " + inc 
  y += " in {2 * " + a + " + " + inc + ", 2 * " + a + " + 2 * " + inc + "}) or "
  y += "(not " + s + " and 2.5 * " + a + " + 5 * " + inc 
  y += " in {2 * " + a + " + 6 * " + inc + ", 2 * " + a + " + 7 * " + inc + "})"
  exprs.append(y)
  
# born on 5 different months
exprs.append("len(set(ms := [" + ms[:-1] +"])) == 5")

# the alphametic puzzle
p = SubstitutedExpression(
  exprs=exprs,
  answer="ms, \
          (AB, AB + (-1)**S * K, AB + 2 * (-1)**S * K, AB + 3 * (-1)**S * K, AB + 4 * (-1)**S * K), \
          (CD, CD + (-1)**T * L, CD + 2 * (-1)**T * L, CD + 3 * (-1)**T * L, CD + 4 * (-1)**T * L), \
          (EF, EF + (-1)**U * M, EF + 2 * (-1)**U * M, EF + 3 * (-1)**U * M, EF + 4 * (-1)**U * M), \
          (GH, GH + (-1)**V * N, GH + 2 * (-1)**V * N, GH + 3 * (-1)**V * N, GH + 4 * (-1)**V * N), \
          (IJ, IJ + (-1)**W * O, IJ + 2 * (-1)**W * O, IJ + 3 * (-1)**W * O, IJ + 4 * (-1)**W * O)",
          
  d2i=d2i,
  distinct="",
  decl="global ms",     # new feature for remembering assignment variables
  denest=1,
  verbose=0,            # use 256 to see the generated code
)

# print answers
for ans in p.answers():
  print(f"{ans[0]}")

LikeLike

Jim Randell 11:24 am on 23 July 2023 Permalink | Reply
Tags: by: Aubrey Jacobus
Brainteaser 1091: The nutty pirates
From The Sunday Times, 3rd July 1983 [link]

Five pirates stole a sackful of nuts, and, taking them back to their lair, decided they would divide them equally the next day.

During the night, the chief, not trusting the others, decided he would take his share first. He divided the nuts into five parts and there was one nut left over: this he gave to the pet monkey. Taking his share, he went back to bed.

Each pirate in turn followed his example, i.e. dividing the remaining nuts into five parts, with a remainder of one on each occasion to be given to the monkey. Next morning, they found the remaining nuts were still divisible by five with one nut left over.

Fortunately for this story, the pirates were able to count at a rate of no more than two nuts per second throughout the night.

How many nuts were in the sack at the start?

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

[teaser1091]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 11:25 am on 23 July 2023 Permalink | Reply
  See also: Enigma 258, Puzzle #86, Teaser (1956-12-13).
  
  Presumably we are looking for the smallest solution.
  
  A straightforward approach runs in 63ms. (Internal runtime is 953µs).
  
  Run: [ @replit ]
```
from enigma import (irange, inf, ediv, printf)

# suppose each pirate receives n nuts from the final pile
for n in irange(1, inf):
  try:
    # then the size of the final pile is ...
    N5 = 5 * n + 1
    # the size of the previous pile ...
    N4 = ediv(5 * N5, 4) + 1
    # the size of the previous pile ...
    N3 = ediv(5 * N4, 4) + 1
    # the size of the previous pile ...
    N2 = ediv(5 * N3, 4) + 1
    # the size of the previous pile ...
    N1 = ediv(5 * N2, 4) + 1
    # the size of the initial pile
    N = ediv(5 * N1, 4) + 1
    # output solution
    printf("n={n} -> N={N}")
    break
  except ValueError:
    continue
```
  Solution: There were 15621 nuts in the sack at the start.
  
  The monkey gets 1 nut. Pirate 1 takes 3124 nuts, and leaves 12496.
  
  The monkey gets 1 nut. Pirate 2 takes 2499 nuts, and leaves 9996.
  
  The monkey gets 1 nut. Pirate 3 takes 1999 nuts, and leaves 7996.
  
  The monkey gets 1 nut. Pirate 4 takes 1599 nuts, and leaves 6396.
  
  The monkey gets 1 nut. Pirate 5 takes 1279 nuts, and leaves 5116.
  
  The monkey gets 1 nut. The pirates each take 1023 nuts.
  
  So the nuts for each pirate are:
  
  Pirate 1: 3124 + 1023 = 4147
  Pirate 2: 2499 + 1023 = 3522
  Pirate 3: 1999 + 1023 = 3022
  Pirate 4: 1599 + 1023 = 2622
  Pirate 5: 1279 + 1023 = 2302
  Monkey: 1 + 1 + 1 + 1 + 1 + 1 = 6
  Total: 4147 + 3552 + 3022 + 2622 + 2302 + 6 = 15651
  
  The number of nuts counted in the night is:
  
  15621 + 12496 + 9996 + 7996 + 6396 = 52505
  
  Which at a rate of 2/sec is 26252.5 seconds = 437.54 minutes = 7.29 hours.
  
  In general with M pirates the initial number of nuts is:
  
  N = k.(M^M) − M + 1
  
  And after each of the pirates had performed their procedure the remaining number of nuts is:
  
  R = k.((M − 1)^M) − M + 1
  
  In this case we have M = 5, and (R − 1) is divisible by M.
  
  k=1: N = 3121, R = 1020, (not viable)
  k=2: N = 6246, R = 2044, (not viable)
  k=3: N = 9371, R = 3068, (not viable)
  k=4: N = 12496, R = 4092, (not viable)
  k=5: N = 15621, R = 5116, (viable)
  
  And we get viable solutions whenever k is a multiple of 5, so the next smallest solution is:
  
  k=10: N = 31246, R = 10236
  
  The total number of nuts counted would be 115276, which would take more than 16 hours to count, which could be done if the pirates operated somewhere with sufficiently long nights (which would require them being at a latitude beyond 80°N/S, so is unlikely).
  
  LikeLike

Jim Randell 4:32 pm on 21 July 2023 Permalink | Reply
Tags: by: Edmund Marshall ( 10 )

Teaser 3174: Pensioners’ outing

From The Sunday Times, 23rd July 2023 [link] [link]

A group of pensioners took a trip in a minibus, which had 11 seats for passengers, three on the back row, and two on each of the four other rows. The ages in years of the passengers were all different double-digit integers greater than 64, and for each pair of those ages there was no common factor other than 1. All seats were occupied, and, on any particular row of seats, the digits in the ages of passengers were all different. The sum of the ages of passengers on the back row was the largest possible with these conditions.

What was the age in years of the most elderly passenger sitting on the back row?

[teaser3174]

Jim Randell 5:10 pm on 21 July 2023 Permalink | Reply

This Python program runs in 65ms. (Internal run time is 4ms).

from enigma import (irange, subsets, gcd, is_duplicate, printf)

# possible ages (no repeated digits)
ages = list(n for n in irange(65, 99) if n % 11 > 0)

# find pairs of ages with different digits that are coprime
pairs = list((x, y) for (x, y) in subsets(ages, 2) if gcd(x, y) == 1 and not is_duplicate(x, y))

# extend the pairs to triples
triples = list()
for (x, y) in pairs:
  for z in ages:
    if z > y and gcd(x, z) == 1 and gcd(y, z) == 1 and not is_duplicate(x, y, z):
      triples.append((x, y, z))

# choose <k> more pairs from <ps>
def choose(k, ps, ns, rs):
  if k == 0:
    yield rs
  else:
    # choose the next pair
    for (i, (a, b)) in enumerate(ps):
      # check numbers are all different
      if a in ns or b in ns: continue
      # and are pairwise coprime
      if not all(gcd(a, n) == 1 and gcd(b, n) == 1 for n in ns): continue
      # solve for remaining pairs
      yield from choose(k - 1, ps[i + 1:], ns + (a, b), rs + [(a, b)])

# solve the puzzle
def solve():
  # consider back rows in order (largest sum to smallest sum)
  for r1 in sorted(triples, key=sum, reverse=1):
    # find 4 more pairs to go with these
    yield from choose(4, pairs, r1, [r1])

# find the first solution
for rs in solve():
  printf("rows = {rs}")
  break  # we only need one solution

Solution: The age of the eldest passenger on the back row is 95.

The ages in the rows are:

(73, 86, 95) (back row)
(67, 91)
(71, 89)
(79, 81) or (79, 83)
(83, 97) or (81, 97)

The sum of the ages in the back row being 254.

LikeLike

Frits 1:52 pm on 24 July 2023 Permalink | Reply

from math import gcd

diffdgts = lambda *ns: len(set(s := ''.join(str(n) for n in ns))) == len(s)

# check that element <a> is coprime with elements in <s>
cp = lambda a, s: all(gcd(a, x) == 1 for x in s)
                  
# decompose <t> into <k> increasing numbers from <ns> with all different digits
def decompose(t, k, ns, s=[]):
  if k == 1:
    if t in ns and t > s[-1] and diffdgts(*(s_ := s + [t])):
      yield s_
  else:
    for (i, n) in enumerate(ns):
      if not diffdgts(*(s_ := s + [n])): continue
      yield from decompose(t - n, k - 1, ns[i + 1:], s_)

#  A B
#  C D
#  E F
#  G H
# I J K

sols = set()
# check sum of ages from (90+80+70+6+5+3) to (80+70+60+0+1+3)
for soa in range(254, 213, -1):
  # back row
  for I, J, K in decompose(soa, 3, [x for x in range(65, 99) if x % 11]):
    # check if I, J and K are coprime
    if not cp(I, [J]): continue
    if not cp(K, [I, J]): continue
    
    for A in range(65, 85):
      if not cp(A, sA := [I, J, K]):  continue
      for B in range((A // 10 + 1) * 10, 99):
        if not cp(B, sB := sA + [A]) or not diffdgts(A, B): continue
        for C in range(A + 1, 86):
          if not cp(C, sC := sB + [B]):  continue
          for D in range((C // 10 + 1) * 10, 99):
            if not cp(D, sD := sC + [C]) or not diffdgts(C, D): continue
            for E in range(C + 1, 87):
              if not cp(E, sE := sD + [D]):  continue
              for F in range((E // 10 + 1) * 10, 99):
                if not cp(F, sF := sE + [E]) or not diffdgts(E, F): continue
                for G in range(E + 1, 88):
                  if not cp(G, sG := sF + [F]):  continue
                  for H in range((G // 10 + 1) * 10, 99):
                    if not cp(H, sG + [G]) or not diffdgts(G, H): continue
                    # don't assume there is a unique answer
                    sols.add(K)
            
  if sols:
    print(f"answer: {', '.join(str(s) for s in sols)} in years")
    break   # we don't need to check a lower sum of ages

LikeLike

Jim Randell 8:51 am on 20 July 2023 Permalink | Reply
Tags: by: Graham Smithers ( 84 )
Teaser 2633: Magic mushrooms
From The Sunday Times, 10th March 2013 [link] [link]

Enid and her famous five (Anne, Dick, George, Julian and Timmy) were joined by Pixie in a mushroom hunt. They each picked two varieties, the fourteen overall being:

Bird’s Nest, Beef Steak, Blue Toothed, Cannon Ball, Death Cap, Devil’s Um, Inky Cap, Old Man of the Woods, Parasol, Poison Pie, Stinkhorn, Slippery Jack, Tree Ears and The Gypsy.

For each of these hunters, if you wrote down their name and the two varieties of mushroom they picked, then for any two from the three you would find that there were just two letters of the alphabet that occurred in both.

What mushrooms were picked by: (a) Pixie and (b) Enid?

It seems likely that “Devil’s Um” is a typo for “Devil’s Urn” (which is a type of mushroom), however the answer to the puzzle is the same whichever you use, so I have stuck with the spelling used in the original puzzle and in the 2020 book.

Also, in Enid Blyton’s Famous Five, Timmy is a dog.

[teaser2633]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 8:52 am on 20 July 2023 Permalink | Reply
  The [[ grouping ]] functionality in the enigma.py library was specifically written for puzzles like these.
  
  The following Python program runs in 61ms. (Internal runtime is 909µs).
  
  Run: [ @replit ]
```
from enigma import grouping

names = ["Enid", "Anne", "Dick", "George", "Julian", "Timmy", "Pixie"]

picks = [
  "Bird's Nest", "Beef Steak", "Blue Toothed", "Cannon Ball", "Death Cap",
  "Devil's Um", "Inky Cap", "Old Man of the Woods", "Parasol",
  "Poison Pie", "Stinkhorn", "Slippery Jack", "Tree Ears", "The Gypsy"
]

# form 2-gangs
for gs in grouping.gangs(2, names, picks, grouping.share_letters(2)):
  # output the groups
  grouping.output_gangs(names, gs)
```
  Solution: (a) Pixie picked Devil’s Um/Urn and The Gypsy. (b) Enid picked Blue Toothed and Slippery Jack.
  
  The full solution is:
  
  Enid: Blue Toothed, Slippery Jack [de, ei, el]
  Anne: Beef Steak, Cannon Ball [ae, an, ab]
  Dick: Death Cap, Stinkhorn [cd, ik, ht]
  George: Poison Pie, Tree Ears [eo, er, es]
  Julian: Bird’s Nest, Parasol [in, al, rs]
  Timmy: Inky Cap, Old Man of the Woods [iy, mt, an]
  Pixie: Devil’s Um/Urn, The Gypsy [ei, ep, es]
  
  (Common letters are listed as: [name ∩ pick1, name ∩ pick2, pick1 ∩ pick2]).
  
  LikeLike
Jim Randell 9:14 am on 18 July 2023 Permalink | Reply
Tags: by: John P McCarthy ( 3 )
Brainteaser 1746: Party time
From The Sunday Times, 3rd March 1996 [link]

In the volatile world of Ruritanian politics, each of the three parties can safely expect to lose a fixed proportion of its supporters to each of the other parties from one election to the next. Thus, the Story party would retain a fixed proportion of its supporters, and lose fixed proportions (which may differ) to the Laboured party and to the Mauve Shirts, and so on. Three elections ago, the Story party and the Laboured party each won 40,000 votes and the Mauve Shirts won 20,000. Two elections ago, the Story party and the Mauve Shirts each won 35,000 votes, while the Laboured party won 30,000 votes. In the last election the Story party and the Laboured party each won 35,000 votes and the Mauve Shirts won 30,000. The total electorate in the current election remains at 100,000.

What is the minimum number of votes the Mauve Shirts should expect to win in the current election?

[teaser1746]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell and Hugo are discussing. Toggle Comments
- Jim Randell 9:15 am on 18 July 2023 Permalink | Reply
  See also: Enigma 662.
  
  Given election 1 and election 2 we have 9 variables, of the form XY, that denote the fraction of voters for party X in election 1 that voted for party Y in the election 2.
  
  All votes for each party are redistributed among the three parties, so:
  
  SS + SL + SM = 1
  LS + LL + LM = 1
  MS + ML + MM = 1
  
  and (working in units of 1000 votes) for election 2:
  
  35 = 40 SS + 40 LS + 20 MS
  30 = 40 SL + 40 LL + 20 ML
  35 = 40 SM + 40 LM + 20 MM
  
  and for election 3:
  
  35 = 35 SS + 30 LS + 35 MS
  35 = 35 SL + 30 LL + 35 ML
  30 = 35 SM + 30 LM + 35 MM
  
  and for election 4 we have:
  
  S = 35 SS + 35 LS + 30 MS
  L = 35 SL + 35 LL + 30 ML
  M = 35 SM + 35 LM + 30 MM
  
  where S, L, M must be whole numbers of votes.
  
  The first 3 blocks give us 9 equations in 9 variables, so it looks like we could solve this system and get the answers for the final block.
  
  However if we try to do this, we find that the 9 equations are not enough to solve the system (i.e. we do not have 9 independent equations, so the system of equations is incomplete). And this makes sense, as the puzzle asks us for the minimum number of votes M can expect to win, so the equations will give a range of values for S, L, M.
  
  But we can solve the system by choosing values for some of the variables until the system becomes complete. It turns out that if we give the values for 2 of the variables the rest can be determined.
  
  By dividing the 20k votes for M in the first election into votes that subsequently go to S, L, M, we can determine values for MS, ML, MM and so the remaining values are determined.
  
  This program looks at different ways to allocate the 20k votes in blocks of 1000 votes, and calculates the results of the 4th election, discarding situations where we do not end up with a whole number of votes.
  
  The program runs in 129ms. (Internal runtime is 60ms).
  
  Run: [ @replit ]
```
from enigma import (
  Rational, Matrix, Accumulator, decompose, as_int, seq2str, printf
)

Q = Rational()

eqs = [
  # SS  LS  MS  SL  LL  ML  SM  LM  MM
  (( 1,  0,  0,  1,  0,  0,  1,  0,  0),  1),
  (( 0,  1,  0,  0,  1,  0,  0,  1,  0),  1),
  (( 0,  0,  1,  0,  0,  1,  0,  0,  1),  1),
  ((40, 40, 20,  0,  0,  0,  0,  0,  0), 35),
  (( 0,  0,  0, 40, 40, 20,  0,  0,  0), 30),
  (( 0,  0,  0,  0,  0,  0, 40, 40, 20), 35),
  ((35, 30, 35,  0,  0,  0,  0,  0,  0), 35),
  (( 0,  0,  0, 35, 30, 35,  0,  0,  0), 35),
  (( 0,  0,  0,  0,  0,  0, 35, 30, 35), 30),
]

# validate a fraction in the interval 0 .. 1
def valid(x):
  if x < 0 or x > 1: raise ValueError()
  return x

# record minimum value for M is 4th election
r = Accumulator(fn=min, collect=1)

# choose MS, ML, MM as fractions of N
N = 20
for (a, b, c) in decompose(N, 3, increasing=0, sep=0, min_v=0):

  # add these into the mix
  eqs_ = [
    # SS LS MS SL LL ML SM LM MM
    (( 0, 0, 1, 0, 0, 0, 0, 0, 0), Q(a, N)),
    (( 0, 0, 0, 0, 0, 1, 0, 0, 0), Q(b, N)),
    (( 0, 0, 0, 0, 0, 0, 0, 0, 1), Q(c, N)),
  ]

  try:
    vs = Matrix.linear(eqs + eqs_, field=Q, valid=valid)
  except ValueError:
    continue

  # calculate total votes in the 4th election
  (SS, LS, MS, SL, LL, ML, SM, LM, MM) = vs

  S = 35*SS + 35*LS + 30*MS
  L = 35*SL + 35*LL + 30*ML
  M = 35*SM + 35*LM + 30*MM
  # check the values are integers
  try:
    (S, L, M) = (as_int(1000 * x) for x in (S, L, M))
  except ValueError:
    continue
  printf("[S={S} L={L} M={M} {vs}]", vs=seq2str(vs))
  r.accumulate_data(M, vs)

# output solutions
M = r.value
for vs in r.data:
  printf("M={M} {vs}", vs=seq2str(vs))
```
  Solution: The Mauve Shirts should expect to win at least 30625 votes.
  
  Here is one set of fractions that give the required values:
  
  Note that no-one who votes for M in one election, votes for M in the next election.
  
  But this is not the only set that gives us the minimum value for M, by increasing the value of N at line 29, we can find further viable sets of values, for example:
  
  However, the fractions in the bottom row are always the same:
  
  SM = 3/4, LM = 1/8, MM = 0
  
  Giving the total votes for M in the 4th election:
  
  M = 35000 × 3/4 + 35000 × 1/8
  M = 26250 + 4375
  M = 30625
  
  LikeLike
  - Jim Randell 10:22 pm on 19 July 2023 Permalink | Reply
    
    The equations can be simplified to give:
    
    The values of x and y can be restricted by noting that the value of the fraction in each box is between 0 and 1.
    
    And we can calculate the number of votes for M in the 4th election:
    
    M = 35000 (S→M) + 35000 (L→M) + 30000 (M→M)
    M = 43125 − 12500z
    
    And the maximum value for z (= x + y) is 1, which gives a minimum value for M = 30625.
    
    All that remains is to show that the minimum value is achievable, which we can do by considering an example, and checking that all the numbers of votes remain whole numbers.
    
    With x = 2/5 and y = 3/5 (as mentioned above) we have:
    
    1: S=40000 [→S 6000, →L 4000, →M 30000]
    1: L=40000 [→S 21000, →L 14000, →M 5000]
    1: M=20000 [→S 8000, →L 12000, →M 0]
    
    2: S=35000 [→S 5250, →L 3500, →M 26250]
    2: L=30000 [→S 15750, →L 10500, →M 3750]
    2: M=35000 [→S 14000, →L 21000, →M 0]
    
    3: S=35000 [→S 5250, →L 3500, →M 26250]
    3: L=35000 [→S 18375, →L 12250, →M 4375]
    3: M=30000 [→S 12000, →L 18000, →M 0]
    
    4: S=35625
    4: L=33750
    4: M=30625
    
    With these values it is not possible for another election to follow the same pattern keeping the votes as integers.
    
    But, if we allow fractional votes the situation settles into a steady state with (to 2dp):
    
    S = 35384.62
    L = 33846.15
    M = 30769.23
    
    LikeLike
- Hugo 10:18 am on 18 July 2023 Permalink | Reply
  
  According to my calculations the fewest and most votes that each party can expect are
  L 32500 – 34060, M 30625 – 32965, S 33750 – 36090.
  I’ve forgotten how I got there!
  
  LikeLike
  - Jim Randell 10:16 pm on 19 July 2023 Permalink | Reply
    
    I agree with these values.
    
    I found there are 122,304 splits of votes from the 1st election that allow whole votes in the 4th election.
    
    LikeLike
Jim Randell 12:31 pm on 16 July 2023 Permalink | Reply
Tags: by: W. M. Greenway ( 5 )
Brain-Teaser 207: Prime flats
From The Sunday Times, 11th April 1965 [link]

The number of families living on one floor in a block of flats is prime. Each family consists of a pair of parents and at least one child; the number of people in each family and the total number of people in all families are prime numbers. Every one had recently had a birthday anniversary, and each person’s age is a prime number. No one is older than 40, and every parent was at least 23 before their first child was born. Each of the prime numbers described above occurs exactly twice.

The sum of the ages of each family is a prime number, and a different one in each case. The sum of the ages of everyone is a prime number.

What are the ages of the people in each family?

[Note: In this puzzle the number 1 is counted as a prime number].

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

[teaser207]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Frits and Jim Randell are discussing. Toggle Comments
- Jim Randell 12:32 pm on 16 July 2023 Permalink | Reply
  Parent’s ages are primes in the interval [24, 40], so there are only 3 possibilities: 29, 31, 37.
  
  And children’s ages can be 1 or a prime, in the interval [1, 14], so there are only 7 possibilities: 1, 2, 3, 5, 7, 11, 13.
  
  As each prime can only appear twice there cannot be more than 6 parents, i.e. 3 families, and as the number of families is prime it must be 2 or 3. However, if there were 2 families each with an age sum that was prime, then combining their ages would give an even (non-prime) number. So there must be 3 families.
  
  (For a unique solution it is necessary to exclude the possibility of the number of families being 1. This can be done by noting that the families are referred to in the puzzle text as plural, although I don’t really consider this to be strong enough. So it may have been better to specifically note that there is more than one family, or to specifically allow 1 to be used only as a child’s age).
  
  This Python program generates possible family groups, where the parents ages are chosen from those given above, and the number of children is chosen such that the total number if the family group is prime. Ages are then chosen for the children to give a prime value for total sum of the ages in the family. And the viable family groups are collected together by total age.
  
  We then choose a collection of different total ages for the family groups, such that the combined age of all groups is prime, and the populate the groups with actual ages, such that when all the specified primes are collected together each is used exactly twice.
  
  The program runs in 665ms.
  
  Run: [ @replit ]
```
from enigma import (multiset, subsets, is_prime, group, item, printf)

# available ages for parents and children
aps = multiset.from_seq([29, 31, 37], count=2)
aks = multiset.from_seq([1, 2, 3, 5, 7, 11, 13], count=2)

# generate possible family groups
def generate():
  # choose the ages for the parents
  for ps in subsets(aps, size=2, select='mC'):
    tp = sum(ps)
    # children are at least 23 years younger than the youngest parent
    m = min(ps) - 22
    aks_ = aks.restrict(x for x in aks.keys() if x < m)
    # choose k = the number of children (such that k + 2 is prime)
    for k in (1, 3, 5, 9, 11):
      # choose the ages of the children
      for ks in subsets(aks_, size=k, select='mC'):
        # total of ages in the family
        t = tp + sum(ks)
        if is_prime(t):
          yield (t, ps + ks)

# group families by total age
fams = group(generate(), by=item(0), f=item(1))

# choose family groups with total ages in <ts>
# fs = families chosen so far
# vs = ages used so far
def choose(ts, fs=[], vs=multiset()):
  if not ts:
    # total number of people is prime
    P = vs.size()
    if not is_prime(P): return
    # check primes in the required set appear twice
    # number of families, total number of people, size of each family
    m = vs.combine((len(fs), P), map(len, fs))
    if not m.all_same(2): return
    # return the families
    yield fs
  else:
    # choose a family with total age <t>
    for f in fams[ts[0]]:
      vs_ = vs.combine(f)
      if not vs_.is_duplicate(2):
        yield from choose(ts[1:], fs + [f], vs_)

# the number of families (must be 3)
n = 3
# choose the total ages for each family
for ts in subsets(fams.keys(), size=n, fn=list):
  # total sum of all ages is prime
  T = sum(ts)
  if not is_prime(T): continue
  # choose the family groups from the ages
  ts.sort(reverse=1)
  for fs in choose(ts):
    # output solution
    printf("{n}: {ts}; T={T} -> {fs}")
```
  Solution: The ages in the family groups are: (37, 37; 13, 7, 7), (31, 31; 2, 2, 1), (29, 29; 1).
  
  LikeLike
  - Frits 5:45 pm on 16 July 2023 Permalink | Reply
    
    You can argue that there is no solution.
    
    “Each of the prime numbers described above occurs exactly twice”.
    
    The total number of people in all families only occurs once.
    
    LikeLike
    - Jim Randell 5:52 pm on 16 July 2023 Permalink | Reply
      
      @Frits: There are 13 people in total, and one of the children is aged 13, so the prime number 13 occurs twice.
      
      LikeLike
      - Frits 6:13 pm on 16 July 2023 Permalink | Reply
        
        @Jim, Thanks, I had read it as total number of all ages (227).
        
        I wonder if I can use SubstitutedExpression() as it is not immediately clear what limit to use for the number of children per family (at least <= 12).
        
        LikeLike
      - Frits 1:41 pm on 17 July 2023 Permalink | Reply
        
        A SubstitutedExpression() solution using all letters A-Z takes 1 second with PyPy. As I now tend to use assignment statements with the reorder=0 option the denest option often can’t be used anymore as assignments are not transfered to another nested level.
        
        A quicker version could be made by further analysis.
        The total number of children must be 7 as 5 fails ((1, 1, 3) results in three 3’s) and 11 fails as well (out of 14 candidates we already lose 4 (number of families and three number of family members). The seven children must occur in a (1, 3, 3) distribution.
        
        LikeLike

Jim Randell 4:52 pm on 14 July 2023 Permalink | Reply
Tags: by: Susan Bricket ( 17 )

Teaser 3173: Dots and boxes

From The Sunday Times, 16th July 2023 [link] [link]

In this game, two players take turns drawing a single horizontal or vertical line between two unjoined adjacent dots in a rectangular grid. A player who completes the fourth side of a 1×1 box earns one point and takes another turn. The winner is the one with the most points at the end. A recent game with 4×4 dots (as above) between two beginners, reached a critical position when no box had more than two sides already drawn and the next player was forced to complete the third side of some box. It turned out that this was the shortest possible 4×4 game to reach a critical position. Their next 4×4 game reached a critical position in the largest possible number of turns.

How many turns [did it take to reach the critical position] in each game?

[teaser3173]

Jim Randell 6:26 pm on 14 July 2023 Permalink | Reply

Here is a Numberphile video about strategy in the game [@youtube].

Not very fast (it takes 17.4s), but here is a brute force breadth first search for critical positions. It uses bitmasks to speed things up, but takes no account of symmetry. I’m not convinced this is the best approach to the problem though.

from enigma import (Accumulator, irange, bit_from_positions as bits, dsum2, cache, printf)

# the boxes
boxes = [
  bits({0, 3, 12, 15}),
  bits({1, 4, 15, 18}),
  bits({2, 5, 18, 21}),
  bits({3, 6, 13, 16}),
  bits({4, 7, 16, 19}),
  bits({5, 8, 19, 22}),
  bits({6, 9, 14, 17}),
  bits({7, 10, 17, 20}),
  bits({8, 11, 20, 23}),
]

# the lines
lines = tuple(1 << v for v in irange(24))

# check a position is subcritical
check = cache(lambda ss: all(dsum2(ss & box) < 3 for box in boxes))

# accumulate min/mix critical positions
acc = Accumulator.multi(fns=[min, max])

# initial position
ps = { (0, lines) }

# perform a breadth first search
while ps:
  ps_ = set()
  # consider positions
  for (ss, rs) in ps:
    # for each remaining line try to add it
    for r in rs:
      ss_ = ss | r
      if check(ss_):
        # this is a viable new position, find remaining lines
        rs_ = tuple(x for x in rs if x != r and check(ss_ | x))
        if not rs_:
          # this is a critical position
          acc.accumulate_data(dsum2(ss_), ss_)
        else:
          ps_.add((ss_, rs_))
  ps = ps_

# output solution
for r in acc:
  printf("{fn} critical = {v} [{ss:024b}]", fn=r.fn.__name__, v=r.value, ss=r.data)

Solution: The first game took 8 turns to reach the critical position. The second game took 14 turns to reach the critical position.

There is one size 8 critical position:

There are 138 size 14 critical positions (although this will include rotations/reflections). Here is one of them:

LikeLike

Frits 7:14 pm on 14 July 2023 Permalink | Reply

@Jim, I got the same results with SubstitutedExpression(), 9 seconds with PyPy.
Somehow the denest option doesn’t work (still saying “too many statically nested blocks”).

Your version ran for 46 seconds on my computer with CPython (17 seconds with PyPy).

LikeLike

Frits 7:55 pm on 14 July 2023 Permalink | Reply

Without analysis, to be run with PyPy (takes 9 seconds).

 
from enigma import SubstitutedExpression

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

# do we reach a critical position for any drawn line?
def check(vs):
  for i, v in enumerate(vs):
    if v: continue
    # update v from 0 to 1
    if all(sum(b) < 3 for b in make_boxes(vs[:i] + [1] + vs[i+1:])):
      return False
  # each update reached a critical position 
  return True
      
# return a list of all boxes    
def make_boxes(vs):
  assert len(vs) == 24 
  A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X = vs
  return [(A, D, E, H), (B, E, I, F), (C, F, G, J), \
          (H, K, L, O), (I, L, M, P), (J, M, N, Q), \
          (O, R, S, V), (P, S, T, W), (Q, T, U, X)]

# the alphametic puzzle
p = SubstitutedExpression(
  [ # not yet a critical conditions
    "not any(sum(b) > 2 for b in @boxes)",
    #"not any(sum(b) > 2 for b in make_boxes(@vars))",
    
    # do we reach a critical position for any drawn line?
    "check(@vars)",
  ],
  answer="((A, B, C), (D, E, F, G), (H, I, J), (K, L, M, N), \
           (O, P, Q), (R, S, T, U), (V, W, X))",
  distinct="",
  macro=dict([("boxes", "[(A, D, E, H), (B, E, I, F), (C, F, G, J), \
                          (H, K, L, O), (I, L, M, P), (J, M, N, Q), \
                          (O, R, S, V), (P, S, T, W), (Q, T, U, X)]")] +
             [("vars", "[A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X]")]),
  env=dict(check=check, make_boxes=make_boxes),
  digits=range(0, 2),
  reorder=0,
  denest=1,
  verbose=0,    # use 256 to see the generated code
)

# used for printing a grid
#f = lambda x, m: "  " if not x and m == "h" else " " if not x and m == "v" \
#                 else "--" if m == "h" else "|" 

sols = set()
# print answers
for ans in p.answers():
  
  sols.add(turns := sum(y for x in ans for y in x))
  '''
  # print grid
  print("\nturns", turns)
  for a in ans:
    if len(a) == 3: 
      m = 'h'
      print(f".{f(a[0], m)}.{f(a[1], m)}.{f(a[2], m)}.")
    else:
      m = 'v'
      print(f"{f(a[0], m)}  {f(a[1], m)}  {f(a[2], m)}  {f(a[3], m)}")
  '''

if len(sols) > 1:
  print(f"answer: {min(sols)} and {max(sols)}")

LikeLike

Jim Randell 11:31 pm on 14 July 2023 Permalink | Reply

And here is a depth first search of critical positions that runs in 837ms (without using bitmasks).

Run: [ @replit ]

from enigma import (Accumulator, irange, printf)

# map lines (0..23) to boxes (0..8)
box = [
  [0], [1], [2],
  [0, 3], [1, 4], [2, 5],
  [3, 6], [4, 7], [5, 8],
  [6], [7], [8],
  [0], [3], [6],
  [0, 1], [3, 4], [6, 7],
  [1, 2], [4, 5], [7, 8],
  [2], [5], [8],
]

# indices for lines
n = len(box)

# check all boxes have less than 2 lines
check = lambda bs, js: all(bs[j] < 2 for j in js)

# find critical positions
# k = current line
# bs = count of lines for each box
# ss = lines used
def solve(k, bs, ss=[]):
  # are we done?
  if k == n:
    # check all remaining lines put >2 lines in a box
    for i in irange(n):
      if i not in ss and check(bs, box[i]): return
    # this is a critical position
    yield ss
  else:
    # try to include the next line
    js = box[k]
    if check(bs, js):
      bs_ = list(bs)
      for j in js: bs_[j] += 1
      yield from solve(k + 1, bs_, ss + [k])
    # or not
    yield from solve(k + 1, bs, ss)

# collect min/max size critical positions
acc = Accumulator.multi(fns=[min, max])
for ss in solve(0, [0] * 9):
  acc.accumulate_data(len(ss), ss)

# output solution
for r in acc:
  printf("{fn} critical = {v} {ss}", fn=r.fn.__name__, v=r.value, ss=r.data)

I can formulate the maximum critical position as a minimum hitting set problem, but I don’t see how to do something similar for the minimum critical position.

LikeLike

Frits 1:18 pm on 16 July 2023 Permalink | Reply

Jim’s 2nd program still took 1.7 seconds on my computer (with PyPy 7.3.11) so I wanted to have a faster program (Cpython is faster than PyPY this time). Fasted time (they do vary) I have seen is 140 ms.
Somehow I found it easier to work with non-lines (or gaps or lines to erase).

I avoided to hardcode some analysis (like code for the 4 corner boxes) which resulted in more code.

 
from itertools import combinations

# map lines (0..23) to boxes (0..8)
ln2bxs = [
  [0], [1], [2],
  [0, 3], [1, 4], [2, 5],
  [3, 6], [4, 7], [5, 8],
  [6], [7], [8],
  [0], [3], [6],
  [0, 1], [3, 4], [6, 7],
  [1, 2], [4, 5], [7, 8],
  [2], [5], [8],
]

N = len(ln2bxs)

boxes = [[i for i, b in enumerate(ln2bxs) if n in b] for n in range(9)]

# pick a minimum of <m> elements from <s>
def pickAtLeast(s, m, ns=()):
  if s:
    for i, x in enumerate(s):
      if len(ns) > m - 2:
        yield(ns + (x, ))
      yield from pickAtLeast(s[i + 1:], m, ns + (x, ))  

# fill boxes from <bxs> so that each box has at least <m> non-lines
def processBox(bxs, M, box_ns=[], m=2, ns=set(), skip=set()):
  if not box_ns: 
    if len(ns) == M:
      # check if drawing these non-lines always put >2 lines in a box
      for i in ns:
        # return if all boxes for a non-line have at most one line
        if all(len(ns & set(boxes[b])) > 2 for b in ln2bxs[i]): return
      yield ns 
  else: # still boxes to check/fill?
    
    # selection of elements not yet picked 
    s = [x for x in bxs[box_ns[0]] if x not in ns]
    # we need to pick at least <m> - 4 + len(s) elements from s
    if (num := m - 4 + len(s)) <= 0:
      # try next box
      yield from processBox(bxs, M, box_ns[1:], m, ns, skip)
    else:  
      # pick a minimum of <num> elements from <s>
      for p in pickAtLeast(s, num):
        # skip if a side hasn't been selected before
        # check with maximum number of non-lines per box and don't exceed M
        if any(x in skip for x in p) or \
           len(p) + 4 - len(s) > d[tuple(boxes[box_ns[0]])] or \
           len(p) + len(ns) > M: 
          continue
      
        skip_ = skip | set(s).difference(p)
        yield from processBox(bxs, M, box_ns[1:], m, ns | set(p), skip_)

# assume every line is drawn and try to put in non-lines (ie erase lines)

# if a box has <n> non-shared sides then it can't have more than 4 - <n>
# non-lines otherwise no critical position is reached when drawing a 
# non-shared side in this box  

# determine the maximum number of non-lines per box
d = {tuple(ln): 4 - sum(1 for x in ln if len(ln2bxs[x]) == 1) for ln in boxes}  

box_order = [y for x, y in sorted((x, i) for i, x in enumerate(d.values()))]

# determine the minimum number of lines for the whole grid
min_lines = 0
for k in range(5, 0, -1): 
  # for all <k> box combinations 
  for c in combinations(boxes, k):
    # boxes with no shared sides?
    if len(set(y for x in c for y in x)) == k * 4: 
      # count the guaranteed number of lines per box
      if (n := sum(4 - d[tuple(x)] for x in c)) >= min_lines:
        min_lines = n
  
  # break if no improvement at a lower level
  if (k - 1) * 2 <= min_lines: break

# for each game find the requested number of turns
for g in range(1, 3):
  print("game", g, end = ": ")
  rng = range(N - min_lines, 0, -1) if g == 1 else range(1, N)
  for M in rng: 
    # fill boxes with <M> non-lines so that each box has at least 2 non-lines
    # start with corner boxes 
    for _ in processBox(boxes, M, box_order):
      print(N - M)
      break
    else: # no break  
      continue

    # we have found a critical position
    break
  else:  
    print()

LikeLike

Jim Randell 9:10 am on 13 July 2023 Permalink | Reply
Tags: by: Harold Reiter ( 5 )

Teaser 2192: Digital shuffle

From The Sunday Times, 19th September 2004 [link]

I have tried rearranging the nine digits from one to nine into various expressions of the following form:

What is the largest whole number answer that I can get?

[teaser2192]

Jim Randell 9:11 am on 13 July 2023 Permalink | Reply

This Python program runs in 94ms. Internal runtime is 30ms.

Run: [ @replit ]

from enigma import (Accumulator, irange, subsets, fraction, printf)

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

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

# choose the denominators R, T, V, X in increasing order
for (R, T, V, X) in subsets(digits, size=4, select='C'):
  # allocate the numerators
  for (Q, S, U, W, Y) in subsets(digits.difference((R, T, V, X)), size=5, select='P'):
    # evaluate the expression
    (a, b) = fraction(Q, R,  S, T,  U, V,  W, X,  -Y, 1)
    if b == 1:
      r.accumulate_data(a, (Q, R, S, T, U, V, W, X, Y))

# output solution(s)
for (Q, R, S, T, U, V, W, X, Y) in r.data:
  printf("{Q}/{R} + {S}/{T} + {U}/{V} + {W}/{X} - {Y} = {r.value}")

Solution: The largest possible answer is 12.

9/1 + 7/2 + 8/3 + 5/6 − 4 = 12

LikeLike

Frits 1:11 pm on 13 July 2023 Permalink | Reply

#! python3 -m enigma -r

SubstitutedExpression

# Q/R + S/T + U/V + W/X - Y = AB
"div(Q*T*V*X + R*S*V*X + R*T*U*X + R*T*V*W - R*T*V*X*Y, R*T*V*X) = AB"

--answer="AB"
--distinct="QRSTUVWXY"
--accumulate=max
--invalid="0,QRSTUVWXY"
--verbose=16

LikeLike

Frits 1:20 pm on 13 July 2023 Permalink | Reply

@Jim, is it possible to get a button like crayon on PuzzlingInPython?
It makes it less error prone to post replies.

LikeLike
Jim Randell 2:02 pm on 13 July 2023 Permalink | Reply
Requiring the denominators be ordered makes this approach run about 10× faster:

Run: [ @replit ]
```
#! python3 -m enigma -rr

SubstitutedExpression

--distinct="QRSTUVWXY"
--invalid="0,QRSTUVWXY"
--code="q = Rational()"

"as_int(q(Q, R) + q(S, T) + q(U, V) + q(W, X) - Y) = AB"

"R < T" "T < V" "V < X"

--answer="AB"
--accumulate="max"
```
(Is “crayon” a WordPress plugin? I don’t think it is possible to install plugins on a free WordPress site. It looks like you need to pay £20/month to be able to do that).

LikeLike

Frits 5:48 pm on 13 July 2023 Permalink | Reply

Not using the fact that 5 and 7 can’t be used as denominators.

   
from fractions import Fraction as RF

# Q/R + S/T + U/V + W/X - Y = mx

# available digits
digits = set(range(1, 10))

# maximum sum for <k> fractions choosing numbers from a sorted sequence <s> 
def maxleft(s, k=4):
  assert len(s) >= 2 * k
  return int(sum([RF(s[-1 - x], s[x]) for x in range(k)]))

# check if we can make total m of <k> fractions from digits in set <s> 
def check(s, m, k=4, ns=[]):
  if k == 1:
    ls = list(s)

    if m in {RF(ls[0], ls[1]), RF(ls[1], ls[0])}:
      print("answer:", sum(RF(x[0], x[1]) for x in ns) + m - Y)
      print(f"we can make remaining fraction {m} with digits {s}, other "
            f"fractions = {', '.join(str(x) + '/' + str(y) for x, y in ns)}")
      exit(0)
  else:
    # start with lowest denominators
    for d in (ss := sorted(s)):
      # ascending denominators
      if ns and d < ns[-1][1]: continue
      # start with highest numerators
      for n in ss[::-1]:
        if n != d:
          yield from check(s.difference([n, d]), m - RF(n, d),
                           k - 1, ns + [(n, d)])

# build a descending list of maxima per Y
M = sorted([(maxleft(sorted(digits.difference([Y]))) - Y, Y) 
            for Y in range(1, 10)], reverse=1)

inc = 0
# keep checking until solution gets too low (-9)
while True:
  cnt = 0
  # check Y's with the highest maximum first
  for (mx, Y) in M:
    if mx + Y - inc >= -8:
      cnt += 1
      # check if we can make total from eight remaining digits
      for c in check(digits.difference([Y]), mx + Y - inc):
        pass
        
  if not cnt: break     
  inc += 1

LikeLike

GeoffR 2:05 pm on 14 July 2023 Permalink | Reply

I found two integer solutions for the equation for the largest whole number. The largest of the two integer solutions was 12.


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

var 1..9:Q; var 1..9:R; var 1..9:S; var 1..9:T;
var 1..9:U; var 1..9:V; var 1..9:W; var 1..9:X;
var 1..9:Y; 

% Assumed LB for the sum is 1/9 + 2/8 + 3/7 + 4/6 - 5 = -3.54 (i.e  -4)
% Assumed UB for the sum is 9/1 + 8/2 + 7/3 + 6/4 - 5 = 11.83 (i.e. 12)
var -4..12:Z;   % Z = Q/R + S/T + U/V + W/X - Y

constraint all_different( [Q, R, S, T, U, V, W, X, Y] );

% Equation in integers only (for Z == Q/R + S/T + U/V + W/X - Y) is:
constraint Z*R*T*V*X == Q*T*V*X + S*R*V*X + U*R*T*X + W*R*T*V - Y*R*T*V*X;

solve maximize(Z);

output [" Z = " ++ show(Z) ++ "\n" 
++ "[Q,R,S,T,U,V,W,X,Y,Z] = " ++ show( [Q,R,S,T,U,V,W,X,Y,Z] ) ];

% Z = 11
% [Q,R,S,T,U,V,W,X,Y,Z] = [6, 4, 9, 3, 7, 2, 8, 1, 5, 11]
% ----------
%  Z = 12
% [Q,R,S,T,U,V,W,X,Y,Z] = [5, 6, 8, 3, 7, 2, 9, 1, 4, 12]
% ----------
% ==========

LikeLike

Frits 3:10 pm on 14 July 2023 Permalink | Reply

Highest rational number seems to be 12.95 (9/1 + 8/2 + 7/4 + 6/5 – 3) and
-7.5381 (1/5 + 2/6 + 3/7 + 4/8 – 9) for the lowest.

LikeLike

Jim Randell 9:01 am on 11 July 2023 Permalink | Reply
Tags: by: Danny Roth ( 88 )
Teaser 2629: Random road
From The Sunday Times, 10th February 2013 [link] [link]

George and Martha moved into Random Road, which has 99 houses along just one side. But instead of being numbered 1 to 99 in the usual way, the man given the job of numbering them gave the first house a number equal to his age and then kept adding his age again for each subsequent house, ignoring the hundreds digits and above. (So, had he been 37 then the numbers would have been 37, 74, 11, 48, 85, 22, etc). Luckily each house got a different number. George’s house number was “correct” so he did not immediately notice. He only saw that something was amiss when Martha pointed out that a house next door had a number with the same two digits as theirs, but in reverse order.

What is George’s and Martha’s house number? And how old was the numberer?

[teaser2629]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 9:01 am on 11 July 2023 Permalink | Reply
  The house numbers in positions k = 1 .. 99 are defined as:
  
  a[1] = n
  a[k + 1] = (a[k] + n) mod 100
  
  or:
  
  a[k] = (k.n) mod 100
  
  So numberers with the same age mod 100 will give the same sequence. We can suppose that the numberers age lies in the range 16 – 115, so we can identify the ages by the residue mod 100.
  
  We are looking for a 2-digit house number XY that appears in the “correct” position, i.e.:
  
  a[XY] = XY
  
  And has a neighbouring house whose number is YX:
  
  a[XY ± 1] = YX
  
  I am assuming that 1-digit numbers are represented with a single digit.
  
  This Python program runs in 54ms. (Internal runtime is 1.4ms).
  
  Run: [ @replit ]
```
from enigma import (irange, nreverse, printf)

# find solutions for age <n>
def solve(n):
  # map: position -> house number
  (d, seen) = (dict(), set())
  (p, k) = (1, n)
  while p < 100:
    if k == 0 or k in seen: break
    d[p] = k
    seen.add(k)
    k = (k + n) % 100
    p += 1
  # did we allocate all the houses?
  if p == 100:
    # look for a house with a 2-digit number the same as position
    for (p, k) in d.items():
      if not (k > 9 and k == p): continue
      # look for neighbouring houses with the reverse of the number
      r = nreverse(k)
      if not (r > 9): continue
      if d.get(p - 1, 0) == r: yield (n, (p, k), (p - 1, r))
      if d.get(p + 1, 0) == r: yield (n, (p, k), (p + 1, r))

# consider possible ages (mod 100)
for n in irange(0, 99):
  for (n, (p0, k0), (p1, k1)) in solve(n):
    printf("age = {n} -> pos {p0} = {k0}, pos {p1} = {k1}")
```
  Solution: George and Martha’s house number is 25. The numberer’s age was 73.
  
  We have:
  
  a[25] = (25×73) mod 100 = 1825 mod 100 = 25
  a[24] = (24×73) mod 100 = 1752 mod 100 = 52
  
  The complete mapping is:
  
  (0 → 0), 1 → 73, 2 → 46, 3 → 19, 4 → 92, 5 → 65, 6 → 38, 7 → 11, 8 → 84, 9 → 57, 10 → 30,
  11 → 3, 12 → 76, 13 → 49, 14 → 22, 15 → 95, 16 → 68, 17 → 41, 18 → 14, 19 → 87, 20 → 60,
  21 → 33, 22 → 6, 23 → 79, 24 → 52, 25 → 25, 26 → 98, 27 → 71, 28 → 44, 29 → 17, 30 → 90,
  31 → 63, 32 → 36, 33 → 9, 34 → 82, 35 → 55, 36 → 28, 37 → 1, 38 → 74, 39 → 47, 40 → 20,
  41 → 93, 42 → 66, 43 → 39, 44 → 12, 45 → 85, 46 → 58, 47 → 31, 48 → 4, 49 → 77, 50 → 50,
  51 → 23, 52 → 96, 53 → 69, 54 → 42, 55 → 15, 56 → 88, 57 → 61, 58 → 34, 59 → 7, 60 → 80,
  61 → 53, 62 → 26, 63 → 99, 64 → 72, 65 → 45, 66 → 18, 67 → 91, 68 → 64, 69 → 37, 70 → 10,
  71 → 83, 72 → 56, 73 → 29, 74 → 2, 75 → 75, 76 → 48, 77 → 21, 78 → 94, 79 → 67, 80 → 40,
  81 → 13, 82 → 86, 83 → 59, 84 → 32, 85 → 5, 86 → 78, 87 → 51, 88 → 24, 89 → 97, 90 → 70,
  91 → 43, 92 → 16, 93 → 89, 94 → 62, 95 → 35, 96 → 8, 97 → 81, 98 → 54, 99 → 27
  
  So 25 is in the correct position, and 24 has the number that is the reverse of 25.
  
  50 and 75 are also in the correct position, but are not neighbours of 5 or 57 (respectively).
  
  62 is given the number 26, the reverse of its position.
  
  LikeLike
- Jim Randell 10:22 am on 11 July 2023 Permalink | Reply
  Without checking that each house is assigned a different number there is only one candidate solution (but we can provide an additional check to ensure the answer is viable).
  
  This run file executes in 62ms. (Internal runtime of the generated program is 1.3ms).
  
  Run: [ @replit ]
```
#! python3 -m enigma -rr

# AB = age of the numberer
# XY = George and Martha's house number

SubstitutedExpression

--distinct="XY"
--code="num = lambda n, k: (n * k) % 100"

# G&M's house number is the same as its position
"num(AB, XY) == XY"

# a neighbouring house is numbered YX
"YX in { num(AB, XY - 1), num(AB, XY + 1) }"

# answer is: G&M's number, numberers age
--answer="(XY, AB)"

# check each house is assigned different number
--reorder=0
"seq_all_different(num(AB, k) for k in irange(1, 99))"
```
  LikeLike
Jim Randell 11:28 am on 9 July 2023 Permalink | Reply
Tags: by: Victor Bryant ( 146 )
Brain-Teaser 923: That way I lose
From The Sunday Times, 30th March 1980 [link]

My son and I play a good game on my calculator. I put in a whole number and do various operations on the calculator (always chosen to give whole number answers).

Every now and then I stop. With me looking at the calculator the right way up, and my son looking at it upside-down, we compare what we see. If he sees a number and it is larger than mine, then he wins that round; but if he sees a number and it is smaller than mine, then he loses that round.

So, for example, if 298 is displayed on the machine, then my son sees 862 and wins. On the other hand, if I display a number using a 3, 4 or 7, then my son does not see a number (and neither of us wins).

Recently I displayed a three-figure number on the machine, and my son and I compared what we saw:

“I win” he said.

Then I subtracted 1 and we looked again.

“I win” he said.

Then I halved the number, and again we compared.

“I win” he said.

So I then added slightly over 2000 to that number and multiplied the total by 17, and we looked once more.

“I lose!” he said, laughing.

What number did I initially display on the calculator, and what was the number which I saw finally displayed?

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

[teaser923]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 11:29 am on 9 July 2023 Permalink | Reply
  See also: Enigma 212.
  
  If you’ve looked at Enigma 212 you might expect the exclamation “I lose!” to indicate that the inverted display of the calculator looked like “ILOSE”, i.e. the final number displayed was 35071.
  
  So it was 2063 before it was multiplied by 17. And some number less than 63 when “slightly over” 2000 was added to it.
  
  This Python program looks for numbers slightly over 2000 that give a viable sequence that starts with a 3-digit number.
  
  It runs in 52ms. (Internal runtime is 112µs).
  
  Run: [ @replit ]
```
from enigma import (irange, nsplit, nconcat, catch, div, printf)

# numbers which read as numbers when inverted on a 7-segment display
inverted = { 0: 0, 1: 1, 2: 2, 5: 5, 6: 9, 8: 8, 9: 6 }

# invert a number
_invert = lambda n: nconcat(inverted[x] for x in nsplit(n, reverse=1))
invert = lambda n: catch(_invert, n)

# start from 35071 (~ invert("ILOSE"))
n4 = 35071
n4_ = div(n4, 17)  # reverse "multiply by 17"
assert n4_ is not None
# look for a value "a little over 2000"
for x in irange(2001, 2099):
  n3 = n4_ - x  # reverse "add x"
  if n3 < 1: break
  r3 = invert(n3)
  if r3 is None or not (r3 > n3): continue

  n2 = n3 * 2  # reverse "divide by 2"
  r2 = invert(n2)
  if r2 is None or not (r2 > n2): continue

  n1 = n2 + 1  # reverse "subtract 1"
  r1 = invert(n1)
  if r1 is None or not (r1 > n1) or not (99 < n1 < 1000): continue

  # output solution
  printf("{n1} ({r1}) -> {n2} ({r2}) -> {n3} ({r3}) -> {n4} (ILOSE); x={x}")
  break
```
  Solution: The initial number was: 119. And the final number was: 35071.
  
  So we have:
  
  start → 119; inverted = 611 (son wins)
  −1 → 118; inverted = 811 (son wins)
  ÷2 → 59; inverted = 65 (son wins)
  +2004; ×17 → 35071; inverted = “ILOSE” (nobody wins)
  
  LikeLike

Jim Randell 4:28 pm on 7 July 2023 Permalink | Reply
Tags: by: Victor Bryant ( 146 )

Teaser 3172: Light show

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

My bedside clock displays the time and date using eight digits; for example at 9:43am on 28th June the display would be:

Each digit in the electronic display lights up some (or all) of seven light segments, the above display lighting up a total of 45 segments. [Not counting the dots].

On one occasion recently the displayed digits were all different and the total number of lit segments was prime. The same was true exactly one day later. Then, just one minute after the second occasion, the number of lit segments was the average of the numbers of lit segments on those two previous occasions.

What was that third display?

[teaser3172]

Jim Randell 5:05 pm on 7 July 2023 Permalink | Reply

I assumed that 7 uses 3 segments, and 6 and 9 use 6 segments each.

This Python program runs in 69ms. (Internal runtime is 12.7ms).

Run: [ @replit ]

from datetime import (date, datetime, timedelta)
from enigma import (
  irange, nsplit, flatten, repeat, inc, is_prime, nconcat,
  seq_all_different as all_different, printf
)

# segment count for each digit
#       0  1  2  3  4  5  6  7  8  9
segs = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]

# segment sum
ssum = lambda ds: sum(segs[d] for d in ds)

# split each number into a pair of digits
display = lambda *ns: flatten(nsplit(n, 2) for n in ns)

# display pairs for hours and minutes with different digits
hours = list(display(n) for n in irange(0, 23) if n % 11 != 0)
mins  = list(display(n) for n in irange(0, 59) if n % 11 != 0)

# date for the first time is between 2023-01-01 and 2023-07-08
for d1 in repeat(inc(timedelta(days=1)), date(2023, 1, 1)):
  if d1.day == 8 and d1.month == 7: break
  # find the digits for the date
  d1d = display(d1.day, d1.month)
  if not all_different(d1d): continue
  # segment sum
  d1s = ssum(d1d)
  # find hour and minute values, using different digits
  for h1 in hours:
    if not all_different(d1d + h1): continue
    for m1 in mins:
      if not all_different(d1d + h1 + m1): continue
      # calculate the digit sum for the first time
      n1 = d1s + ssum(h1 + m1)
      if not is_prime(n1): continue

      # now check the segment sum exactly 1 day later is prime
      t1 = datetime(d1.year, d1.month, d1.day, nconcat(h1), nconcat(m1))
      t2 = t1 + timedelta(days=1)
      n2 = ssum(display(t2.hour, t2.minute, t2.day, t2.month))
      if not is_prime(n2): continue

      # and the time 1 minute later gives the mean of the segment sums
      t3 = t2 + timedelta(minutes=1)
      n3 = ssum(display(t3.hour, t3.minute, t3.day, t3.month))
      if n3 * 2 != n1 + n2: continue

      # output solution
      printf("{t1} ({n1}) -> {t2} ({n2}) -> {t3} ({n3})")

Solution: The third time was: 17:00 28.04.

The displays are:

Time 1: 16:59 27.04 = 4:59pm on 27th April, uses 37 segments
Time 2: 16:59 28.04 = 4:59pm on 28th April, uses 41 segments
Time 3: 17:00 28.04 = 5:00pm on 28th April, uses 39 segments

There is only one viable set of times (per year) even if the choice of dates is unrestricted.

LikeLike

Frits 3:28 pm on 8 July 2023 Permalink | Reply

   
from enigma import SubstitutedExpression, catch
from datetime import timedelta, datetime

# number of segments per digit
seq = [('0', 6), ('1', 2), ('2', 5), ('3', 5), ('4', 4), 
       ('5', 5), ('6', 6), ('7', 3), ('8', 7), ('9', 6)]

# dictionary
d = dict(seq)

total = lambda s: sum(d[y] for x in s for y in str(x).zfill(2))

# check valid datetime (mm, dd, hh, tt)
check_dt = lambda s: catch(datetime, 2023, s[0], s[1], s[2], s[3]) is not None

# list external functions
fns = ("total", "check_dt", "datetime", "timedelta")
env = eval("dict(" + ','.join([x + "=" + x for x in fns]) + ")")

# invalid digit / symbol assignments
d2i = dict()
for dg in range(0, 10):
  vs = set()
  if dg > 2: vs.update('A')
  if dg > 3: vs.update('E')
  if dg > 5: vs.update('C')
  if dg > 6: vs.update('H') # until and including June
  d2i[dg] = vs

#         hh.tt dd.mm
# display AB.CD EF.GH

# the alphametic puzzle
p = SubstitutedExpression(
  [
    "AB < 24",                                      # hours
    "EF < 32",                                      # days
    
    "check_dt([GH, EF, AB, CD])",                   # check for valid date
    "(d1 := datetime(2023, GH, EF, AB, CD)) != 1",  # set day 1
    "is_prime(t1 := total((AB, CD, EF, GH)))",      # total must be prime
    
    "(d2 := d1 + timedelta(days=1)) != 1",          # set day 2
    "is_prime(t2 := total((d2.month, d2.day, d2.hour, d2.minute)))",
    
    "(d21 := d2 + timedelta(minutes=1)) != 1",      # set day 2 plus 1 minute
    # t3 is average of t1 and t2
    "2 * total((d21.month, d21.day, d21.hour, d21.minute)) == t1 + t2",
  ],
  answer="(d21.hour, d21.minute, d21.day, d21.month)",
  d2i=d2i,
  s2d=dict(G=0),
  env=env,
  reorder=0,
  verbose=0,    # use 256 to see the generated code
)

fm = lambda n: str(n).zfill(2)
# print answers
for h, t, d, m in p.answers():
  print(f"{fm(h)}.{fm(t)} {fm(d)}.{fm(m)}")

@Jim, is there a better way to set the env variable in a compact way without mentioning the function name twice?

LikeLike

Jim Randell 9:22 am on 9 July 2023 Permalink | Reply
@Frits: You can always pass the entire local environment:
```
env = locals()
```
Or to include just the necessary values you could use:
```
# construct the restriction of dict <d> to keys <ks>
restrict = lambda d, ks: dict((k, d[k]) for k in ks)
env = restrict(locals(), fns)
```
Perhaps I will add [[ restrict() ]] to enigma.py.

LikeLike

Jim Randell 10:32 am on 6 July 2023 Permalink | Reply
Tags: by: E T Tweddell ( 2 )

Brain-Teaser 900: World Cup goal scorers

From The Sunday Times, 5th November 1978 [link]

The Soccotia World Cup soccer squad consists of two goalkeepers and sufficient outfield players to ensure that each of these latter play in exactly two games, of the three scheduled. Each player is also allocated a consecutive number starting with one, including the goalkeepers. Each outfield player is equally capable of playing in defence and attack, but will not change from one role to another during the same game.

The manager selects the teams for each match such that the sum of the numbers of the outfield players remains constant for each game, and such that the sum of the numbers of the four defenders equals one half of the sum of the six attackers.

In each game Soccotia scored one goal, each of which was scored by an attacking player, three different players scoring one goal each.

In the first game, the goal resulted from a five man move involving four passes. The move was started by a defender, who was the only defender in the move. Each pass was made to a player whose number was a fixed integer multiple of the passer.

In the second game, the same four players were chosen to play in defence as in the first game, and the same defender started the five man/four pass move which led to the goal scored in this game. This time however the number of each player receiving the ball exceeded the number of the passer by a fixed integer.

In the third game the five man/four pass move leading to the goal followed the same pattern as that scored in the second game.

What were the numbers of the goalscorers in match order?

News

There are now 900 Teaser puzzles available on the site, so I thought it appropriate to post Teaser 900.

[teaser900]

Jim Randell 10:32 am on 6 July 2023 Permalink | Reply

In each match the team consists of 11 players (1 goalkeeper, 4 defenders, 6 attackers).

In the 3 games with 30 slots for outfield (= non-goalkeeper) players, each member of the squad fills 2 slots, so there are 15 outfield members, and 17 members of the squad in total. So they are numbered from 1-17.

This Python program starts by forming possible geometric and arithmetic sequences from the available numbers, and then selects attackers and defenders for each match based on the specified requirements. Once we have 3 matches we check there are 2 unused numbers for the goalkeepers, and then determine the scorers in each match.

The program runs in 296ms.

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

# numbers 1 .. 17
ns = set(irange(1, 17))

# form possible geometric and arithmetic sequences
gseqs = list()
aseqs = list()
# consider the first 2 terms
for (a, b) in subsets(sorted(ns), size=2):
  # geometric?
  n = div(b, a)
  if n:
    ss = tuple(repeat((lambda x: x * n), a, 4))
    if ns.issuperset(ss): gseqs.append(ss)
  # arithmetic?
  n = b - a
  ss = tuple(repeat((lambda x: x + n), a, 4))
  if ns.issuperset(ss): aseqs.append(ss)

# choose a geometric sequence for the first game
for seq1 in gseqs:
  # the sequence consists of 1d + 4a
  (d1, a1s) = (seq1[0], seq1[1:])
  # choose 2 more attackers to give an even sum (= 2t)
  for atts1 in subsets(ns.difference(seq1), size=2, fn=set):
    atts1.update(a1s)
    t = div(sum(atts1), 2)
    if t is None: continue
    # choose 3 defenders to bring their total to t
    for defs1 in subsets(ns.difference(atts1, {d1}), size=3, fn=set):
      defs1.add(d1)
      if sum(defs1) != t: continue

      # in the second game we have the same 4 defenders
      defs2 = defs1
      h2 = sum(defs2)
      # find an arithmetic sequence that starts with d1 ...
      for seq2 in aseqs:
        if seq2[0] != d1: continue
        # and ends in an attacker
        a2 = seq2[-1]
        if a2 == seq1[-1] or a2 in defs2: continue
        # any player in the sequence that is not a defender is an attacker
        a2s = set(seq2).difference(defs2)
        # find more attackers to give a sum of 2 * t
        for atts2 in subsets(ns.difference(defs2, a2s), size=6 - len(a2s), fn=set):
          atts2.update(a2s)
          if sum(atts2) != 2 * t: continue

          # find out who has already played twice
          m = multiset.from_seq(defs1, atts1, defs2, atts2)
          p2s = set(k for (k, v) in m.items() if v == 2)
          # find an arithmetic sequence for game 3 that doesn't involve p2s
          for seq3 in aseqs:
            if not p2s.isdisjoint(seq3): continue
            # the sequence starts with a defender and ends with an attacker
            a3 = seq3[-1]
            if a3 == seq1[-1] or a3 == seq2[-1]: continue
            d3 = seq3[0]
            # choose 3 more defenders to bring the sum to t
            for defs3 in subsets(ns.difference(p2s, {d3, a3}), size=3, fn=set):
              defs3.add(d3)
              if sum(defs3) != t: continue
              # any player in the sequence that is not a defender is an attacker
              a3s = set(seq3).difference(defs3)
              # find more attackers to give a sum of 2 * h3
              for atts3 in subsets(ns.difference(p2s, defs3, a3s), size=6 - len(a3s), fn=set):
                atts3.update(a3s)
                if sum(atts3) != 2 * t: continue

                # find the goalkeepers (not involved in any match so far)
                gs = ns.difference(defs1, atts1, defs2, atts2, defs3, atts3)
                if len(gs) != 2: continue
                # find the scorers
                ss = (seq1[-1], seq2[-1], seq3[-1])

                # output solution
                fmt = sorted
                printf("1: defs={defs1} atts={atts1} {seq1}", defs1=fmt(defs1), atts1=fmt(atts1))
                printf("2: defs={defs2} atts={atts2} {seq2}", defs2=fmt(defs2), atts2=fmt(atts2))
                printf("3: defs={defs3} atts={atts3} {seq3}", defs3=fmt(defs3), atts3=fmt(atts3))
                printf("goalies = {gs}", gs=fmt(gs))
                printf("scorers = {ss}")
                printf()

Solution: The goalscorers were: 16, 9, 8.

The squad for the first match was:

1: defenders = (1, 3, 11, 13); attackers = (2, 4, 8, 12); sequence = 1 → 2 → 4 → 8 → 16

This is the only possible geometric sequence using the allowed numbers.

The numbers of the defenders sum to 28, and the numbers of the attackers sum to 56.

The squad for the second match was:

2: defenders = (1, 3, 11, 13); attackers = (5, 6, 7, 9, 14, 15); sequence = 1 → 3 → 5 → 7 → 9

And the squad for the third match was one of the following:

3: defenders = (2, 4, 6, 16); attackers = (5, 7, 8, 9, 13, 15); sequence = 4 → 5 → 6 → 7 → 8
3: defenders = (2, 4, 7, 15); attackers = (5, 6, 8, 9, 12, 16); sequence = 4 → 5 → 6 → 7 → 8
3: defenders = (4, 5, 7, 12); attackers = (2, 6, 8, 9, 15, 16); sequence = 4 → 5 → 6 → 7 → 8

Each of the outfield player has played in 3 matches, and the remaining members of the squad, 10 and 17, are the goalkeepers.

The goal scorers are the final players in the three sequences: 16, 9, 8.

LikeLike

Frits 8:22 pm on 6 July 2023 Permalink | Reply

from itertools import combinations

N = 17

# return all arithmetic sequences in sorted seq, len=5 [x, k + x, ... , 4k + x]
def ametric(seq): 
  for x in seq[:-4]:
    for k in range(1, 5):
      if 4 * k + x > seq[-1]: break 
      if all(x + i * k in seq for i in range(5)):
        yield (x, 4 * k + x)                             # yield first and last
        
# decompose <t> into <n> different numbers, min/max, excluding <xs> elements 
def decompose(t, n, xs, m=1, M=17, s=[]):
  if n == 1:
    if m <= t <= M and t not in xs:
      yield s + [t]
  else:
    # still n - 1 numbers to follow with minimal sum m+1 + m+2 + .. + m+n-1
    # or (n - 1)m + n(n-1)/2  
    for x in range(m, min(M + 1, t - (n - 1) * m + n * (n - 1 ) // 2 + 1)):
      if x not in xs:
        yield from decompose(t - x, n - 1, xs, x + 1, M, s + [x])
        
   
# round 1: defs = [fd, x, y, z], atts = {k*fd, k**2fd, k**3fd, k**4fd, a, b}
# geometric sequences
for fd, geo in [(fd, {fd * m**i for i in range(5)}) 
                for fd in range(1, int(N**.25) + 1) 
                for m in range(2, int((N / fd)**.25) + 1)]: 
  s1 = max(geo)                                             # scorer in round 1
  # choose 2 remaining attackers in round 1           
  for a, b in combinations(set(range(1, N + 1)).difference(geo), 2):
    if (a + b) % 2: continue                                    # a + b is even
    atts_1 = geo.difference([fd]) | {a, b}
    sum_atts = sum(atts_1)
    # can we make defender sum (minus fd) from choosing 3 from leftovers?
    for d in decompose(sum_atts // 2 - fd, 3, {fd} | atts_1):
      d = {fd} | set(d)
      sumd = sum(d)
      
      # make an arithmetic sequence [fd, k + fd, ... , 4k + fd]
      for k in range(1, 5):
        # different scorer must be an attacker
        if (s2 := 4 * k + fd) == s1 or s2 in d: continue 
        # already known attackers in round 2  
        atts_2_1 = set(fd + i * k for i in range(5)).difference(d)
        # only one attacker played in both round 1 and round 2
        # so exactly 10 outfield players remain for round 3
        if len(both := atts_1 & atts_2_1) > 1: continue

        # choose remaining attackers in round 2
        for d2 in decompose(sum_atts - sum(atts_2_1), 6 - len(atts_2_1), 
                            d | atts_2_1 | (atts_1 if both else set())):
          atts_2 = atts_2_1 | set(d2)
          # only one attacker played in both round 1 and round 2
          if len(p11 := atts_1 | atts_2) != 11: continue
      
          # pick players who played only one game in round 1 and 2
          p3 = sorted(p for p in p11 if p not in atts_1 or p not in atts_2)
          # sum of the numbers of the outfield players remains constant 
          if sum(p3) != 3 * sumd: continue

          # build list of possible defenders
          defss = list(decompose(sumd, 4, set(range(1, N + 1)).difference(p3)))
         
          # can we make an arithmetic sequence [x, k + x, ... , 4k + x]?
          for (f, s3) in ametric(p3):
            # three different players scoring one goal each
            if s3 in {s1, s2}: continue
            # the sequence starts with a defender and ends with an attacker
            if any(s3 not in defs and f in defs for defs in defss): 
              print(f"answer: {s1}, {s2} and {s3}")

LikeLike

Jim Randell 10:43 am on 4 July 2023 Permalink | Reply
Tags: by: Nick MacKinnon ( 57 )
Teaser 2625: Mind the gap
From The Sunday Times, 13th January 2013 [link] [link]

If you list in increasing order all ten-figure numbers with no repeat digit, then the first is 1023456789 and the last is 9876543210. The differences between consecutive numbers in the list vary wildly but no difference is ever equal to the average of all the differences between the consecutive numbers.

What difference between consecutive numbers comes closest to the average?

[teaser2625]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell and Frits are discussing. Toggle Comments
- Jim Randell 10:44 am on 4 July 2023 Permalink | Reply
  The way [[ subsets(..., select='P') ]] works the numbers will be produced in numerical order, so we don’t need to order them.
  
  The distances between consecutive numbers are recorded in a [[ multiset() ]], so we don’t have to bother processing duplicate values.
  
  But there are a lot of numbers to process, so the program is quite slow.
  
  This Python program runs in 871ms.
  
  Run: [ @replit ]
```
from enigma import (irange, subsets, nconcat, multiset, tuples, rdiv, Accumulator, printf)

# construct pandigitals in numerical order
def generate():
  for ds in subsets(irange(0, 9), size=10, select='P'):
    if ds[0] != 0:
      yield nconcat(ds)

# record the collection of differences between consecutive pandigitals
ds = multiset.from_seq(b - a for (a, b) in tuples(generate(), 2))
# calculate the mean difference
m = ds.avg(div=rdiv)
printf("mean difference = {m}", m=float(m))

# find the closest difference
r = Accumulator(fn=min, collect=1)
for d in ds.keys():
  r.accumulate_data(abs(m - d), d)
# output solution(s)
for d in r.data:
  printf("closest difference = {d} [{n} times]", n=ds[d])
```
  Solution: The difference that comes closest to the mean is 2727.
  
  Which occurs 1872 times, for example in the following pairs:
  
  (1034679852, 1034682579)
  …
  (9865317420, 9865320147)
  
  There are 500 different difference values.
  
  The smallest difference is 9 (which happens 322560 times):
  
  (1023456789, 1023456798)
  …
  (9876543201, 9876543210)
  
  And the largest difference is 104691357 (which happens 2 times):
  
  (1098765432, 1203456789)
  (8796543210, 8901234567)
  
  With some analysis we can get a faster program.
  
  We can calculate the mean difference fairly easily:
  
  In an ordered sequence (a, b, c, …, x, y, z) the sequence of consecutive distances is:
  
  (b − a, c − b, …, y − x, z − y)
  
  and this has one fewer element than the original sequence.
  
  And the sum of this sequence is simply:
  
  sum = z − a
  
  i.e. the difference between the largest pandigital and the smallest pandigital.
  
  So, if we knew the number of pandigitals in the original sequence we can calculate the mean.
  
  There are factorial(10) possible digit sequences, but factorial(9) of them will have a leading zero, so are rejected.
  
  Hence, there are 3265920 pandigitals (and the number of distances is 1 less than this).
  
  And so the mean distance is:
  
  mean distance = (9876543210 − 1023456789) / 3265919 = 2710.7489…
  
  So we see that no individual difference is equal to the mean because the mean is not an integer and all individual differences are. (And in fact they all must be multiples of 9).
  
  Now, if we consider two consecutive pandigitals that are at a distance apart that is close to the mean, then they are going to look something like:
  
  abcde|vwxyz
  abcde|xzyvw
  
  Where there is some shared prefix, and then the remaining digits appear in a different arrangement for the two numbers. And when calculating the difference between them the common prefix disappears.
  
  So the difference for the numbers in the example is then:
  
  xzyvw − vwxyz
  
  And we can calculate the differences by just looking at sets of numbers that are not part of the common prefix, and calculating the closest difference using those set.
  
  We are looking for a difference close to 2711, so we can examine sets of digits that have 5 elements.
  
  This Python program runs in 123ms.
  
  Run: [ @replit ]
```
from enigma import (
  factorial, rdiv, ndigits, Accumulator,
  irange, subsets, nconcat, tuples, printf
)

# calculate the mean distance
m = rdiv(9876543210 - 1023456789, 9 * factorial(9) - 1)
printf("mean difference = {m}", m=float(m))

# record the closest difference to the mean
r = Accumulator(fn=min)

# consider possible sets of digits
k = ndigits(int(m)) + 1
for ds in subsets(irange(0, 9), size=k):
  # find consecutive numbers using this set of digits
  ns = subsets(ds, size=len, select='P', fn=nconcat)
  # find differences between consecutive numbers closest to the mean
  for (a, b) in tuples(ns, 2):
    d = b - a
    r.accumulate_data(abs(m - d), d)

# output solution
printf("closest difference = {r.data}")
```
  LikeLike
- Frits 5:22 pm on 4 July 2023 Permalink | Reply
```
  
from enigma import factorial
from itertools import permutations, combinations

# calculate the mean distance
m = (9876543210 - 1023456789) / (factorial(10) - factorial(9) - 1)
print(f"mean difference = {m}")

mn, md = 9999999, 9999999

# abcde with c > d > e 
# choose last three descending digits
for c in combinations('9876543210', 3):
  # choose first 2 digits
  for p in permutations(set('0123456789').difference(c), 2):
    s = ''.join(p + c)

    # jump within same 10000:  like 32510 to 35012
    if s[1] < '7':
      # jump 3 higher for a difference of 2xxx
      s2 = str(int(s[1]) + 3)
      if s2 not in s[1:]: continue
      new = int(s[0] + s2 + ''.join(sorted(set(s[1:]).difference(s2))))
    else:  
      ints = [int(x) for x in s]
      # we must be able to jump to a higher 10000
      a1 = str(ints[0] + 1)
      if s[0] == '9' or a1 not in s: continue
      # digit 3 higher then 2nd digit must be present
      if str(ints[1] - 7) not in s: continue
      # digits higher than 2nd digit may not occur in last three positions
      if any(str(j) in s[2:] for j in range(ints[1] + 1, 10)): continue
      
      # jump to higher 10000:   like 17420 to 20147
      new = int(a1 + ''.join(sorted(set(s).difference(a1))))
  
    i = int(s)
    # check for closeness to target
    if abs(m - new + i) <= mn:
      mn, md = abs(m - new + i), new - i

print("answer:", md)
```
  LikeLike
  - Frits 1:27 pm on 5 July 2023 Permalink | Reply
    
    With the abcde|vwxyz method we might miss other combinations that can come relatively close to 2710.
    
    like 2345698710, 2345701689 with difference 2979
    
    LikeLike
    - Jim Randell 1:37 pm on 5 July 2023 Permalink | Reply
      We can reduce the size of the prefix considered at line 14:
      
      k = ndigits(int(m)) + 2
      
      Although it turns out the common prefix is size 5 in all 1872 cases, so we are OK.
      
      Originally I allowed 1 digit more than the length of the mean for the suffix, but this does assume that the closest value is going to be reasonably close to the mean value.
      
      LikeLike
Jim Randell 9:17 am on 2 July 2023 Permalink | Reply
Tags: by: Sir James Joint ( 6 )
Brain-Teaser 438: Electric clock
From The Sunday Times, 28th September 1969 [link]

My watch keeps perfect time and so does my electric wall clock until the battery starts to run down. I check the clock every noon, and when I find that it has lost a minute in 24 hours I know that it will slow down by an additional minute each day until the battery is exhausted.

At noon on a day towards the end of August, when I was preparing for a fortnight’s holiday, I noticed that the clock was one minute slow but. I forgot to do anything about it. As I hurried off to catch my train, at noon on 1st September, I saw that the clock was exactly 21 minutes slow. I put it right and left it at that.

Family matters forced me to return earlier than I had expected and on my arrival home I found that the clock was still going. I then noticed that the hands of my watch were exactly overlapping, while the hands of the clock were almost so.

It took me only a minute to fix a new battery, and I at once put the clock on the correct time. In doing so the hands crossed each other three times.

On what date did I return from my holiday?

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

[teaser438]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 9:18 am on 2 July 2023 Permalink | Reply
  The clock is 21 minutes slow on 1st Sep, and as 21 is the 6th triangular number it must be progressing as follows (minutes slow at noon on the specified date):
  
  27th Aug: 1 min (+1)
  28th Aug: 3 min (+2)
  29th Aug: 6 min (+3)
  30th Aug: 10 min (+4)
  31st Aug: 15 min (+5)
  1st Sep: 21 min (+6), corrected to 0 min
  2nd Sep: 7 min (+7)
  3rd Sep: 15 min (+8)
  4th Sep: 24 min (+9)
  5th Sep: 34 min (+10)
  6th Sep: 45 min (+11)
  7th Sep: 57 min (+12)
  8th Sep: 70 min (+13)
  9th Sep: 85 min (+14)
  10th Sep: 99 min (+15)
  11th Sep: 115 min (+16)
  12th Sep: 132 min (+17)
  13th Sep: 150 min (+18)
  14th Sep: 169 min (+19), expected return
  
  A 12 hour clock has overlapping hands at 12:00, and then every 12/11 hours later.
  
  gap = 12/11 hours = 65m27.27s
  
  So we can check times that are multiples of this gap (up to 14 days), and look for times when the hands on the wall clock are separated by a small angle, and it would require 3 crossings of the hands to set to clock to the correct time.
  
  As the clock is set to a time just after the hands have crossed the amount the clock has lost must be greater than 131 minutes. So the earliest possible date of return is 12th Sep. And a return on 14th Sep wouldn’t be an early return, so the answer must be 12th Sep or 13th Sep.
  
  This Python program starts by constructing a continuous function to give the amount the clock is slow at any particular time, and it does this by using polynomial interpolation of the times given above at noon on the 1st to 14th Sep. (And as we might expect, that function turns out to be a quadratic polynomial).
  
  It then looks at times when the hands of a correct clock are overlapping, and calculates the angular distance between the hands on the slow clock. If the hand are less than 10° apart, and setting the clock right requires crossing the hands exactly 3 times, then we have found a solution.
  
  It runs in 66ms. (Internal runtime is 2.4ms).
  
  Run: [ @replit ]
```
from enigma import (Rational, Polynomial, irange, mdivmod, divc, sprintf, printf)

Q = Rational()

# after h hours, loss (in minutes) is t
h = t = 0
ps = [(h, t)]
for i in irange(7, 19):
  h += 24
  t += i
  # remove (<time>, <loss>) (both in hours)
  ps.append((h, Q(t, 60)))

# p: hour -> hours lost
p = Polynomial.interpolate(ps)
printf("[p(x) = {p}]")

# calculate hand positions from time in hours (between 0 and 1)
def pos(t):
  (z, h, m) = mdivmod(t, 12, 1)
  return (Q(h + m, 12), m)

# angular distance between hand positions (between 0 and 1)
def ang(t):
  (h, m) = pos(t)
  d = abs(h - m)
  return min(d, 1.0 - d)

# format a time (in hours)
def fmt(t):
  (d, h, m) = mdivmod(t, 24, 1)
  return sprintf("{d:d}+{h:02d}:{m:05.2f}", m=float(m * 60))

# gap between times of successive overlapping hands
g = Q(12, 11)

# continue forward from noon on 1st Sep in 12/11 hour increments
for i in irange(1, 11 * 28):
  # actual elapsed time (hours)
  h = i * g
  # time lost (hours)
  x = p(h)
  # calculate the number of crossings in setting the clock to the correct time
  k = divc(x, g)
  if k != 3: continue
  # clock elapsed time (hours)
  t = h - x
  # calculate the angular distance between the hands
  d = ang(t)
  # look for distances less than 10 degrees
  if not (0 < 360 * d < 10): continue
  # output solution
  printf("[i={i}] {h} -> {t}; {d:.2f} deg; {k} crossings", h=fmt(h), t=fmt(t), d=float(360 * d))
```
  Solution: You returned home on 12th September.
  
  The polynomial that gives the time lost (in hours) from the time of departure (noon on 1st Sep) is:
  
  p(x) = (1/69120)x^2 + (13/2880)x
  
  If the setter returned home at noon on 12th Sep, then the clock would be 132 minutes slow, so it would be showing 9:48am. And the hands are 6° apart, and the minute hand is slightly behind the hour hand.
  
  The battery is replaced and the clock is set to 12:01pm, which involves the hands crossing at: just before 10, just before 11, 12. So the hands cross 3 times.
  
  And this is the solution given in the book.
  
  However the program finds a “better” solution.
  
  If the setter were to return at 10:54am on 12th Sep (i.e. the previous time the hands on the watch coincide), then the clock would be displaying 8:43am, and the hands are just 1.6° apart, with the minute hand slightly behind the hour hand.
  
  The battery is replaced and the clock set to 10:55am. So the hands cross at: just before 9, just before 10, just before 11. So the hands cross 3 times, and they started out much closer together than the given solution.
  
  I also think that the wording of the puzzle implies that setter returned home at an overlapping time other than noon.
  
  However it doesn’t change the date that the setter returned, so the answer is the same in both cases.
  
  LikeLike
Jim Randell 3:37 pm on 30 June 2023 Permalink | Reply
Tags: by: Michael Fletcher ( 18 )
Teaser 3171: What’s happened to our chocolate bar?
From The Sunday Times, 2nd July 2023 [link] [link]

Father Christmas was rewarding his helpers (sprites, elves and fairies). He had 333 helpers, of whom 111 were elves.

He had 28 chocolate bars to give away in proportion to the size of the groups. If the groups’ shares were 9.5, 9.3 and 9.2 then they would actually receive 10, 9 and 9, because the bars can’t be split and the extra bar goes to the group with the highest remainder (for two extra bars, one each would go to the two groups with the highest remainders). In fact the sprites, elves and fairies received 7, 9 and 12 bars respectively.

“I’ve found another chocolate bar”, said Father Christmas, “so now the sprites, elves and fairies will receive 6, 10 and 13 bars respectively.”

“What’s happened to our chocolate bar?” asked the sprites.

How many sprites are there?

[teaser3171]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell, Tony Brooke-Taylor, and Frits are discussing. Toggle Comments
- Jim Randell 3:58 pm on 30 June 2023 Permalink | Reply
  What better time to run a Christmas themed puzzle?
  
  See also: this Matt Parker video [@youtube]
  
  This Python program runs in 61ms. (Internal runtime is 414µs).
```
from enigma import (decompose, item, first, printf)

# distribute <k> bars among <ns>
def distribute(k, ns):
  t = sum(ns)
  ds = list()  # allocation
  rs = list()  # (index, remainder)
  # initial allocation
  for (i, n) in enumerate(ns):
    (d, r) = divmod(n * k, t)
    ds.append(d)
    rs.append((i, r))
  # distribute remaining bars
  k -= sum(ds)
  for (i, r) in first(sorted(rs, key=item(1), reverse=1), k):
    ds[i] += 1
  return ds

# total number of helpers
T = 333
# number of elves
E = 111
# choose the number of sprites and fairies
for (S, F) in decompose(T - E, 2, increasing=1, sep=2, min_v=1):

  # calculate the distributions of 28 and 29 bars
  if distribute(28, [S, E, F]) != [7, 9, 12]: continue
  if distribute(29, [S, E, F]) != [6, 10, 13]: continue

  # output solution
  printf("S={S} E={E} F={F}")
```
  Solution: There are 76 sprites.
  
  There are 76 sprites, 111 elves, 146 fairies (= 333 helpers in total).
  
  With 28 chocolate bars the distribution is:
  
  S → 6.39 bars
  E → 9.33 bars
  F → 12.27 bars
  
  After allocating the 6, 9, 12 bars there is 1 bar left over, which goes to the sprites, as they have the largest remainder, giving a final allocation of 7, 9, 12 bars (28 in total).
  
  With 29 the distribution is:
  
  S → 6.62 bars
  E → 9.67 bars
  F → 12.71 bars
  
  After allocating the 6, 9, 12 bars there are 2 bars left over, which go to the fairies and the elves, as they have the largest remainders, giving a final allocation of 6, 10, 13.
  
  We can look at the “fairness” of the allocations by considering the amount of chocolate per helper.
  
  If each bar weighs 100g, then in the first case there is 2800g of chocolate, and 333 helpers, so a completely fair allocation would be 8.41g per helper.
  
  The actual allocations are:
  
  S → 7 bars = 9.21g / sprite (= avg + 0.80g)
  E → 9 bars = 8.11g / elf (= avg − 0.30g)
  F → 12 bars = 8.22g / fairy (= avg − 0.19g)
  
  So the sprites get an above average share this allocation, and the elves and fairies get below average.
  
  In the second allocation there is 2900g of chocolate, giving a fair allocation of 8.71g per helper.
  
  And the actual allocations are:
  
  S → 6 bars = 7.89g / sprite (= avg − 0.82g)
  E → 10 bars = 9.01g / elf (= avg + 0.30g)
  F → 13 bars = 8.90g / fairy (= avg + 0.19g)
  
  In this allocation the sprites get a below average share, and the elves and fairies get above average.
  
  Manually:
  
  Adding 1 bar to the total causes S’s proportion of the chocolate to go down and E’s and F’s proportions to go up. So in the first case there was 1 remaining bar which went to S, and in the second case there were 2 remaining bars which went to E and F.
  
  In the first case the sum of the remainders come to 1 bar, so the largest remainder (S’s) must be more than 1/3:
  
  (S/333)×28 > 6 + 1/3
  S > (19/3)×(333/28) ≈ 75.32
  S ≥ 76
  
  In the second case the sum of the remainders come to 2 bars, so the smallest remainder (S’s) must be less than 2/3:
  
  (S/333)×29 < 6 + 2/3
  S < (20/3)×(333/29) ≈ 76.55
  
  And the only value in these two ranges is: S = 76.
  
  LikeLike
  - Jim Randell 11:21 am on 1 July 2023 Permalink | Reply
    Here is a different approach that calculates bounds on the population sizes of the different groups using the distributions of chocolate bars given in the puzzle text. It then tries population sizes within the calculated bounds to see which give the required distributions.
    
    It also has an internal runtime of <1ms.
```
from enigma import (irange, inf, divc, divf, cproduct, item, first, printf)

# distribute <k> bars among <ns>
def distribute(k, ns):
  t = sum(ns)
  ds = list()  # allocation
  rs = list()  # (index, remainder)
  # initial allocation
  for (i, n) in enumerate(ns):
    (d, r) = divmod(n * k, t)
    ds.append(d)
    rs.append((i, r))
  # distribute remaining bars
  k -= sum(ds)
  for (i, r) in first(sorted(rs, key=item(1), reverse=1), k):
    ds[i] += 1
  return ds

# find divisions of population <t> that give distributions <dss>
def solve(t, dss):
  # calculate bounds for each group
  (mn, mx) = (dict(), dict())
  for ds in dss:
    k = sum(ds)
    for (i, d) in enumerate(ds):
      # if this distribution was rounded up
      x = divc((d - 1) * t, k)
      if x > mn.get(i, 0): mn[i] = x
      # if this distribution was rounded down
      x = divf((d + 1) * t - 1, k)
      if x < mx.get(i, inf): mx[i] = x
  # choose populations
  for ns in cproduct(irange(mn[i], mx[i]) for i in sorted(mn.keys())):
    if sum(ns) != t: continue
    # check distributions
    if all(distribute(sum(ds), ns) == ds for ds in dss):
      yield ns

# solve for the specified distributions
for (S, E, F) in solve(333, [[7, 9, 12], [6, 10, 13]]):
  if E != 111: continue
  printf("S={S} E={E} F={F}")
```
    It turns out that the condition that E = 111 is not needed, as there is only one set of population sizes that gives the required distributions with the given total population size. (i.e. line 41 is optional).
    
    Although knowing E = 111 allows a straightforward manual solution.
    
    LikeLike
    - Frits 1:43 pm on 1 July 2023 Permalink | Reply
      Without using the mn and mx boundaries and E = 111 this program runs in 100ms.
      
      I wonder if manual solvers would have an elegant way of solving if E = 111 was omitted.
      
      from enigma import SubstitutedExpression # calculate distribution with population numbers <s> def dist(n, s, t): guaranteed = [(n * x) // t for x in s] n_leftovers = n - sum(guaranteed) remainders = sorted([((n * x) % t, i) for i, x in enumerate(s)]) # add leftovers to the people with the highest remainders for i in range(n_leftovers): guaranteed[remainders[2 - i][1]] += 1 return guaranteed # the alphametic puzzle p = SubstitutedExpression( [ "(total := 333)", "(sprites := ABC) < (elves := DEF)", "total - sprites - DEF = GHI", "elves < (fairies := GHI)", "dist(28, [sprites, elves, fairies], total) == [7, 9, 12]", "dist(29, [sprites, elves, fairies], total) == [6, 10, 13]", ], answer="sprites", d2i=dict([(k, "ADG") for k in range(4, 10)]), distinct="", env=dict(dist=dist), reorder=0, verbose=0, # use 256 to see the generated code ) # print answers for ans in p.answers(): print(f"answer: {ans}")
      
      @Jim, notice I had to postpone the assignment of fairies and that in the calculation of GHI I could use variables sprites or elves but not both of them.
      
      LikeLike
      - Frits 2:54 pm on 1 July 2023 Permalink | Reply
        
        or without GHI
        
        # the alphametic puzzle p = SubstitutedExpression( [ "total := 333", "(sprites := ABC) < (elves := DEF)", "fairies := total - sprites - elves", "elves < fairies", "dist(28, [sprites, elves, fairies], total) == [7, 9, 12]", "dist(29, [sprites, elves, fairies], total) == [6, 10, 13]", ], answer="sprites, elves, fairies", d2i=dict([(k, "AD") for k in range(2, 10)]), distinct="", env=dict(dist=dist), reorder=0, verbose=0, # use 256 to see the generated code )
        
        LikeLike
      - Tony Brooke-Taylor 11:25 am on 2 July 2023 Permalink | Reply
        
        I think it is possible to infer bounds for the number of sprites without knowing 111, simply by recognising that with 28 bars, the sprites have the largest remainder (implying > 1/3) while with 29 bars, the sprites have the smallest remainder (implying < 2/3). Only 1 integer value for the number of sprites fits between these bounds.
        
        LikeLike
        
        Jim Randell 11:41 am on 2 July 2023 Permalink | Reply
        
        @Tony: Very neat.
        
        LikeLike
- Frits 6:51 pm on 30 June 2023 Permalink | Reply
  Not many iterations.
```
 
T, E, N = 333, 111, 28
RS = [[7, 9, 12], [6, 10, 13]]

# in 1st round the sprites win against the elves 
# N.S / T > RS[1][0] + 1/3
# in 2nd round the sprites lose against the elves 
# (N + 1).S / T < RS[1][0] + 2/3

for s in range((RS[1][0] * T + T // 3) // N + 1, 
               (RS[1][0] * T + 2 * T // 3) // (N + 1) + 1):
  f = T - E - s
 
  # play 2 rounds
  for rnd in range(2):
    n = N + rnd
    guaranteed = [(n * x) // T for x in (s, E, f)]
    n_leftovers = n - sum(guaranteed)

    remainders = sorted([((n * x) % T, i) for i, x in enumerate([s, E, f])])
    
    # add leftovers to the people with the highest remainders
    for i in range(n_leftovers):
      guaranteed[remainders[2 - i][1]] += 1
    # check with actual distribution  
    if guaranteed != RS[rnd]: break
  else:  # no break  
    print("answer:", s)  
```
  LikeLike

	Jim Randell on Teaser 2433: [Date of bir…
	Jim Randell on Teaser 3318: Squaring the…
	Ruud on Teaser 3319: Watch out!
	Jim Randell on Teaser 3319: Watch out!
	Ruud on Teaser 3319: Watch out!
	Jim Randell on Teaser 3319: Watch out!
	Ruud on Teaser 2445: [Divisible by…
	Jim Randell on Teaser 2445: [Divisible by…

Search

Recent Posts

Recent Comments

Archives

Categories

Subscribe

RSS Links

Site Stats

Meta

Updates from August, 2023 Toggle Comment Threads | Keyboard Shortcuts

Jim Randell 9:28 am on 3 August 2023 Permalink | Reply Tags: by: Graham Smithers ( 84 )

Rate this:

Share:

Jim Randell 9:29 am on 3 August 2023 Permalink | Reply

Reply Cancel reply

Jim Randell 9:11 am on 1 August 2023 Permalink | Reply Tags: by: Oliver D Anderson ( 2 )

Rate this:

Share:

Jim Randell 9:11 am on 1 August 2023 Permalink | Reply

Jim Randell 11:35 am on 30 July 2023 Permalink | Reply Tags: by: Victor Bryant ( 146 )

Rate this:

Share:

Jim Randell 11:36 am on 30 July 2023 Permalink | Reply

GeoffR 4:19 pm on 30 July 2023 Permalink | Reply

Jim Randell 4:38 pm on 28 July 2023 Permalink | Reply Tags: by: John Owen ( 33 )

Rate this:

Share:

Jim Randell 6:55 pm on 28 July 2023 Permalink | Reply

Jim Randell 10:55 am on 30 July 2023 Permalink | Reply

Frits 2:01 pm on 29 July 2023 Permalink | Reply

Frits 9:04 pm on 30 July 2023 Permalink | Reply

Tony Brooke-Taylor 7:11 pm on 3 August 2023 Permalink | Reply

Frits 9:52 pm on 8 August 2023 Permalink | Reply

Jim Randell 10:08 pm on 9 August 2023 Permalink | Reply

Frits 10:57 am on 10 August 2023 Permalink | Reply

Jim Randell 9:30 am on 27 July 2023 Permalink | Reply Tags: by: Victor Bryant ( 146 )

Rate this:

Share:

Jim Randell 9:31 am on 27 July 2023 Permalink | Reply

Frits 3:25 pm on 27 July 2023 Permalink | Reply

Jim Randell 3:31 pm on 27 July 2023 Permalink | Reply

Frits 3:06 pm on 27 July 2023 Permalink | Reply

GeoffR 7:17 pm on 27 July 2023 Permalink | Reply

Jim Randell 11:12 am on 25 July 2023 Permalink | Reply Tags: by: Robin Nayler ( 17 )

Rate this:

Share:

Jim Randell 11:13 am on 25 July 2023 Permalink | Reply

Frits 3:24 pm on 25 July 2023 Permalink | Reply

Jim Randell 11:24 am on 23 July 2023 Permalink | Reply Tags: by: Aubrey Jacobus

Rate this:

Share:

Jim Randell 11:25 am on 23 July 2023 Permalink | Reply

Jim Randell 4:32 pm on 21 July 2023 Permalink | Reply Tags: by: Edmund Marshall ( 10 )

Rate this:

Share:

Jim Randell 5:10 pm on 21 July 2023 Permalink | Reply

Frits 1:52 pm on 24 July 2023 Permalink | Reply

Jim Randell 8:51 am on 20 July 2023 Permalink | Reply Tags: by: Graham Smithers ( 84 )

Rate this:

Share:

Jim Randell 8:52 am on 20 July 2023 Permalink | Reply

Jim Randell 9:14 am on 18 July 2023 Permalink | Reply Tags: by: John P McCarthy ( 3 )

Rate this:

Share:

Jim Randell 9:15 am on 18 July 2023 Permalink | Reply

Jim Randell 10:22 pm on 19 July 2023 Permalink | Reply

Hugo 10:18 am on 18 July 2023 Permalink | Reply

Jim Randell 10:16 pm on 19 July 2023 Permalink | Reply

Jim Randell 12:31 pm on 16 July 2023 Permalink | Reply Tags: by: W. M. Greenway ( 5 )

Rate this:

Share:

Jim Randell 12:32 pm on 16 July 2023 Permalink | Reply

Frits 5:45 pm on 16 July 2023 Permalink | Reply

Jim Randell 5:52 pm on 16 July 2023 Permalink | Reply

Frits 6:13 pm on 16 July 2023 Permalink | Reply

Frits 1:41 pm on 17 July 2023 Permalink | Reply

Jim Randell 4:52 pm on 14 July 2023 Permalink | Reply Tags: by: Susan Bricket ( 17 )

Rate this:

Share:

Jim Randell 6:26 pm on 14 July 2023 Permalink | Reply

Jim Randell 9:28 am on 3 August 2023 Permalink | Reply
Tags: by: Graham Smithers ( 84 )

Jim Randell 9:11 am on 1 August 2023 Permalink | Reply
Tags: by: Oliver D Anderson ( 2 )

Jim Randell 11:35 am on 30 July 2023 Permalink | Reply
Tags: by: Victor Bryant ( 146 )

Jim Randell 4:38 pm on 28 July 2023 Permalink | Reply
Tags: by: John Owen ( 33 )

Jim Randell 9:30 am on 27 July 2023 Permalink | Reply
Tags: by: Victor Bryant ( 146 )

Jim Randell 11:12 am on 25 July 2023 Permalink | Reply
Tags: by: Robin Nayler ( 17 )

Jim Randell 11:24 am on 23 July 2023 Permalink | Reply
Tags: by: Aubrey Jacobus

Jim Randell 4:32 pm on 21 July 2023 Permalink | Reply
Tags: by: Edmund Marshall ( 10 )

Jim Randell 8:51 am on 20 July 2023 Permalink | Reply
Tags: by: Graham Smithers ( 84 )

Jim Randell 9:14 am on 18 July 2023 Permalink | Reply
Tags: by: John P McCarthy ( 3 )

Jim Randell 12:31 pm on 16 July 2023 Permalink | Reply
Tags: by: W. M. Greenway ( 5 )

Jim Randell 4:52 pm on 14 July 2023 Permalink | Reply
Tags: by: Susan Bricket ( 17 )

Jim Randell 9:10 am on 13 July 2023 Permalink | Reply
Tags: by: Harold Reiter ( 5 )

Jim Randell 9:01 am on 11 July 2023 Permalink | Reply
Tags: by: Danny Roth ( 88 )

Jim Randell 11:28 am on 9 July 2023 Permalink | Reply
Tags: by: Victor Bryant ( 146 )

Jim Randell 4:28 pm on 7 July 2023 Permalink | Reply
Tags: by: Victor Bryant ( 146 )

Jim Randell 10:32 am on 6 July 2023 Permalink | Reply
Tags: by: E T Tweddell ( 2 )

Jim Randell 10:43 am on 4 July 2023 Permalink | Reply
Tags: by: Nick MacKinnon ( 57 )

Jim Randell 9:17 am on 2 July 2023 Permalink | Reply
Tags: by: Sir James Joint ( 6 )

Jim Randell 3:37 pm on 30 June 2023 Permalink | Reply
Tags: by: Michael Fletcher ( 18 )