Following GeoffR’s method.
Frits, 
Ruud, 
GeoffR, and 1 other are discussing. 
Hugo, 
from enigma import divisor_pairs
# 999999 * X == MY * REPEAT
for X in range(1, 10):
LHS = 999999 * X
# fraction X / MY is in its lowest form
for MY, REPEAT in [(str(x), str(y)) for x, y in divisor_pairs(LHS)
if 9 < x < 100 and (x % X or X == 1)]:
# letter E
if REPEAT[1] != REPEAT[3]: continue
# different letters
if len(set(MY + REPEAT)) != 7: continue
print(f"answer: {REPEAT[2]}{REPEAT[4]}{REPEAT[0]}{REPEAT[5]}")
LikeLike
I did assume a 1-digit question mark. Line 9 should have been:
if 9 < x < 100 and gcd(x, X) == 1]:
LikeLike
Brute force with istr:
from istr import istr
for r, e, p, a, t, m, y in istr.permutations(istr.digits(), 7):
if (m | y) * (r | e | p | e | a | t) % 999999 == 0:
print(f"{m|y} / {r|e|p|e|a|t}")
LikeLike
Improved prints:
from istr import istr
for r, e, p, a, t, m, y in istr.permutations(istr.digits(), 7):
if (m | y) * (r | e | p | e | a | t) % 999999 == 0:
print(f"{(m | y) * (r | e | p | e | a | t) // 999999} / {m | y} = 0.{r | e | p | e | a | t}...")
print(f"part = {p | a | r | t}")
LikeLike
Ok, no guarantee.
Better would be to do
for m, y, r, e, p, a, tin istr.permutations(istr.digits(), 7):
if (m | y) * (r | e | p | e | a | t) % 999999 == 0:
print(f"{(m | y) * (r | e | p | e | a | t) // 999999} / {m | y} = 0.{r | e | p | e | a | t}...")
print(f"part = {p | a | r | t}")
break
Although my original code also just result in one solution.
Alth
LikeLike
From The Sunday Times, 24th July 1988 [link]
Each letter stands for one of the two digits 1 and 2.
TEN is larger than SIX, which is larger than TWO, which is larger than ONE.
NINE is larger than FIVE, which is larger than FOUR, which is larger than ZERO.
EIGHT is larger than SEVEN, which is larger than THREE.
Which is the larger in each of the following pairs?
(a) ELEVEN and NINETY;
(b) TWENTY and EIGHTY;
(c) FIFTY and SIXTY;
(d) SEVENTY and HUNDRED;
(e) EIGHTY and NINETY?
[teaser1351]
Here is a solution using the [[ SubstitutedExpression ]] solver from the enigma.py library.
It runs in 80ms. (Internal runtime of the generated program is 122µs).
#! python3 -m enigma -rr SubstitutedExpression --digits="1,2" --distinct="" "TEN > SIX" "SIX > TWO" "TWO > ONE" "NINE > FIVE" "FIVE > FOUR" "FOUR > ZERO" "EIGHT > SEVEN" "SEVEN > THREE" --answer="(ELEVEN < NINETY, TWENTY < EIGHTY, FIFTY < SIXTY, SEVENTY < HUNDRED, EIGHTY < NINETY)" --template=""
Solution: We have:
NINETY > ELEVEN
EIGHTY > TWENTY
FIFTY > SIXTY
SEVENTY > HUNDRED
NINETY > EIGHTY
The following letters have fixed values:
E=2, F=2, G=2, H=1, I=2, N=2, O=1, S=2, T=2, V=1, W=1, X=1, Z=1
And the letters D, L, R, U, Y can take on either value, and give rise to the 32 possible assignments.
So:
NINETY = 22222? > 2?2122 = ELEVEN
EIGHTY = 22212? > 21222? = TWENTY
FIFTY = 2222? > 2212? = SIXTY
SEVENTY = 221222? > 1?2??2? = HUNDRED
NINETY = 22222? > 22212? = EIGHTY
LikeLike
Brute force solution:
from collections import defaultdict
from istr import istr
answers = defaultdict(set)
for t, e, n, s, i, x, w, o, f, v, r, z, g, h, u, l, y, d in istr.product((1, 2), repeat=18):
if t | e | n > s | i | x > t | w | o > o | n | e:
if n | i | n | e > f | i | v | e > f | o | u | r > z | e | r | o:
if e | i | g | h | t > s | e | v | e | n > t | h | r | e | e:
answers["a"].add(("ninety", "eleven")[e | l | e | v | e | n > n | i | n | e | t | y])
answers["b"].add(("eighty", "twenty")[t | w | e | n | t | y > e | i | g | h | t | y])
answers["c"].add(("sixty", "fifty")[f | i | f | t | y > s | i | x | t | y])
answers["d"].add(("hundred", "seventy")[s | e | v | e | n | t | y > h | u | n | d | r | e | d])
answers["e"].add(("ninety", "eighty")[e | i | g | h | t | y > n | i | n | e | t | y])
for letter, answer in answers.items():
print(f"{letter}) {answer}")
LikeLike
@Jim Randell
Sorry, I forgot to tell that you need istr 1.0.7 to run this code.
LikeLike
@Ruud: Thanks. It works with the new version of istr.
LikeLike
As some ‘Spielerei’, I did refactor my original istr-version.
It uses n2w module to convert ints to ‘spoken’ strings. With that and a helper function, I can formulate all the comparison statements as ints, which make more compact code.
A bit (?) overengineered, maybe …
from collections import defaultdict
from istr import istr
import n2w # this module can convert an integer to a 'spoken' string
from functools import reduce, lru_cache
@lru_cache
def convert(number):
"""just as n2w.convert, but 100 is treated differenr]t as n2w.convert(100) is 'one hundred'"""
return "hundred" if number == 100 else n2w.convert(number)
def a(number):
"""translates an int into an istr, using the global variables that define the letter value"""
return reduce(lambda x, y: x | globals()[y], convert(number), istr(""))
def largest(number0, number1):
return (convert(number1), convert(number0))[a(number0) > a(number1)]
answers = defaultdict(set)
for t, e, n, s, i, x, w, o, f, v, r, z, g, h, u, l, y, d in istr.product((1, 2), repeat=18):
if a(10) > a(6) > a(2) > a(1):
if a(9) > a(5) > a(4) > a(0):
if a(8) > a(7) > a(3):
answers["a"].add(largest(11, 90))
answers["b"].add(largest(80, 20))
answers["c"].add(largest(60, 50))
answers["d"].add(largest(100, 70))
answers["e"].add(largest(90, 80))
for letter, answer in answers.items():
print(f"{letter}) {answer}")
LikeLike
All comparisons are between values of the same length, so we don’t need to convert the values into numbers, we can just use lexicographic ordering.
This Python program uses integer keys to refer to the words, but considers the values of the words with all 2^18 possible assignments of symbols, so is much slower than my solution using the [[ SubstitutedExpression ]] solver.
from enigma import (union, subsets, join, printf)
# words we are interested in (use numbers as short keys)
words = {
10: 'TEN', 6: 'SIX', 2: 'TWO', 1: 'ONE',
9: 'NINE', 5: 'FIVE', 4: 'FOUR', 0: 'ZERO',
8: 'EIGHT', 7: 'SEVEN', 3: 'THREE', 50: 'FIFTY', 60: 'SIXTY',
11: 'ELEVEN', 90: 'NINETY', 20: 'TWENTY', 80: 'EIGHTY',
70: 'SEVENTY', 100: 'HUNDRED',
}
# answers we need to find (which is larger?)
qs = [(11, 90), (20, 80), (50, 60), (70, 100), (80, 90)]
# collect symbols used
syms = sorted(union(words.values()))
# collect answers
ans = set()
# assign the symbols to values
for vs in subsets('12', size=len(syms), select='M'):
m = dict(zip(syms, vs))
# map the words to values
w = dict((k, join(m[x] for x in v)) for (k, v) in words.items())
# check the conditions
if (w[10] > w[6] > w[2] > w[1] and w[9] > w[5] > w[4] > w[0] and w[8] > w[7] > w[3]):
# accumulate answers
ans.add(tuple(max(a, b, key=w.get) for (a, b) in qs))
# output solution
for ks in ans:
for (q, k) in zip("abcde", ks):
printf("({q}) {k}", k=words[k])
printf()
LikeLike
From The Sunday Times, 26th May 2024 [link] [link]
On his 35th birthday, maths teacher Al’s three younger half-sisters bought him “The Book of Numbers for Nerds” as a tease. It showed how to find right-angle triangles with whole-number sides using any two unequal odd square numbers. You take half their sum; half their difference; and the square root of their product to get the three sides. Any multiple of such a triplet would also work. He told his sisters this and that their ages were the sides of such a triangle. “Algorithm Al!” they yelled.
Knowing the age of any one sister would not allow you to work out the other ages with certainty, but in one case you could be sure of her place chronologically (youngest, middle or oldest).
Give the three sisters’ ages (youngest to oldest).
[teaser3218]
(See also: Teaser 3017).
The construction of primitive Pythagorean triples in this way is known as Euclid’s formula [@wikipedia].
This program collects Pythagorean triples with sides less than 35, and looks for triangles where all sides appear in more than one candidate triangle.
Of the selected triangles we look for a side that can only appear in one specific position in the ordering (again, considering all candidate triangles). And this identifies the required answer.
It runs in 63ms. (Internal runtime is 193µs).
from enigma import (
defaultdict, pythagorean_triples, multiset, singleton, icount, printf
)
# collect possible triangles
tris = list(pythagorean_triples(34))
# record positions of each side
d = defaultdict(multiset)
for tri in tris:
for (i, x) in enumerate(tri):
d[x].add(i)
# check a candidate triangle
def check_tri(tri):
# each side must appear in multiple triangles
if not all(d[x].size() > 1 for x in tri): return
printf("tri = {tri}; all sides occur in multiple triangles")
# look for sides that can only appear in a single position
for x in tri:
k = singleton(d[x].distinct_elements())
if k is not None:
printf("-> {x} only appears in pos {k}")
yield (x, k)
# check triangles, exactly one side appears in a single position
for tri in tris:
if icount(check_tri(tri)) == 1:
printf("=> SOLUTION: ages = {tri}")
Solution: The three ages are: 15, 20, 25.
There are just five primitive triangles we are interested in:
euclid(1, 3) = (3, 4, 5)
euclid(1, 5) = (5, 12, 13)
euclid(1, 7) = (7, 24, 25)
euclid(3, 5) = (8, 15, 17)
euclid(3, 7) = (20, 21, 29)
Candidate triangles are formed from these, along with multiples such that the largest side does not exceed 34.
And the only candidate triangles where every side length occurs in another triangle are:
(12, 16, 20) = (3, 4, 5) × 4
(15, 20, 25) = (3, 4, 5) × 5
And of these sides only 25 always appears as the largest side length:
(7, 24, 25)
(15, 20, 25)
LikeLike
Following the instructions.
sols = set()
# odd squares
osqs = [i * i for i in range(1, 68, 2)]
for i, a in enumerate(osqs):
if a > 33: break
for b in osqs[i + 1:]:
# calculate sister's ages
p = (a + b) // 2
if p > 34: break
q = abs(a - b) // 2
r = int((a * b) ** .5)
# allow for multiples
for k in range(1, 35):
if any(x > 34 for x in [k * p, k * q, k * r]): break
sols.add(tuple(sorted([k * p, k * q, k * r])))
sides = set(y for x in sols for y in x)
# dictionary of age appearing as y/m/o
d = {s: [sol.index(s) for sol in sols if s in sol] for s in sides}
# group of sisters that qualify
gs = [sol for sol in sols if all(len(d[s]) > 1 for s in sol)]
for sisters in gs:
if sum([len(set(d[s])) == 1 for s in sisters]) == 1: # in one case ...
print("answer:", sisters)
LikeLike
From The Sunday Times, 21st January 1968 [link]
The caterer at our Village Hall is in a quandary, as the Hall has been double-booked for next Saturday — by the Cricket Club and the Darts Club.
Unfortunately the matter cannot be resolved until the return of the Vicar on Saturday morning. He is quite unpredictable in such decisions, and the caterer must order the food by Friday.
The Cricketers want 100 sausage rolls and 60 meat pies; the Darts Club wants 50 sausage rolls and 90 meat pies.
The caterer is empowered to spend exactly £6.00. He buys sausage rolls at 3p and sells at 4p; meat pies cost him 5p and sell at 8p. Any left-overs are disposed of at a loss to a local prep school, which pays 2p per sausage roll and 3p a pie.
What should the caterer order so that he makes the best safe profit no matter which club gets the booking? And what will that profit be?
This puzzle is included in the book Sunday Times Brain Teasers (1974). The puzzle text is taken from the book.
[teaser350]
This Python program looks at possible orders of sausage rolls and pies that cost the caterer exactly 600p, and then the amount made if these supplies are available for each club, and records the minimum profit made in each case. We then look for the largest of these profits to find the answer to the puzzle.
It runs in 58ms. (Internal runtime is 240µs).
Lise Andreasen are discussing.
from enigma import (Accumulator, express, printf)
# amount earned for supply <s>, demand <d>, price <p>, disposal price <x>
def amount(s, d, p, x):
return (d * p + (s - d) * x if s > d else s * p)
# calculate amount earned for a supply (s, p) and a demand (S, P)
# of sausage rolls and pies
def earned(s, p, S, P):
return amount(s, S, 4, 2) + amount(p, P, 8, 3)
# find the maximum profit
r = Accumulator(fn=max, collect=1)
# the caterer spends 600p
for (s, p) in express(600, [3, 5]):
# calculate amount earned from each club
C = earned(s, p, 100, 60)
D = earned(s, p, 50, 90)
# record profit
r.accumulate_data(min(C, D), (s, p, C - 600, D - 600))
# output solution
for (s, p, C, D) in r.data:
printf("{s} sausages rolls + {p} pies -> cricket = {C} / darts = {D}")
Solution: The caterer should order 80 sausage rolls and 72 pies. Whichever club arrives he will make a profit of 236p.
In the originally published puzzle pre-decimal currency was used and the numbers were different:
The Cricketers want 200 sausage rolls and 120 meat pies; the Darts Club wants 100 sausage rolls and 180 meat pies.
The caterer is empowered to spend exactly £5 [= 1200 pence].
And the answer is: 160 sausage rolls, 144 pies. The profit is 472 pence = £1, 19s, 4d.
LikeLike
This program doesn’t assume that the caterer will spend exactly 600p.
from enigma import SubstitutedExpression, Accumulator
# invalid digit / symbol assignments
d2i = dict()
# try to spend close to 600p in order to maximize the profit
for dgt in range(0, 101):
vs = set()
if dgt < 50: vs.update('S')
if dgt < 60: vs.update('P')
if dgt > 90: vs.update('P')
d2i[dgt] = vs
# the alphametic puzzle
p = SubstitutedExpression(
[
# expenditure close to the maximum
"595 < S * 3 + P * 5 <= 600",
# calculate profits for cricketers and darters
"(pc := S + min(P, 60) * 3 - (P - 60) * 2 * (P > 60))",
"(pd := min(S, 50) + P * 3 - (S - 50) * 1 * (S > 50))",
],
answer="min(pc, pd), S, P",
base=101,
d2i=d2i,
distinct="",
reorder=0,
verbose=0, # use 256 to see the generated code
)
# find the maximum profit
r = Accumulator(fn=max).accumulate_from(ans for (_, ans) in p.solve())
# output solution
w, s, p = r.value
print(f"he should order {s} sausages and {p} pies for a profit of {w}p")
LikeLike
Assuming that the caterer will spend exactly 600p and that the caterer will order a sensible amount of sausages S (50, 55, 60, …, 95, 100) the profit (if the cricketers get the booking) can be expressed as: 2.2 * S + 60 and 460 – 2.8 * S if the darters get the booking.
As the first function is increasing and the latter is decreasing for S the safe profit will be maximized if 2.2 * S + 60 = 460 – 2.8 * S or S = 80.
Interesting.
I approached it differently and arrived at 100 sausage rolls and a profit of 280.
LikeLike
Oh, hang on. Read the puzzle incorrectly.
LikeLike
Read the numbers in an early version of this page?
LikeLike
Sorry. For a short while the numbers were mixed up between the original puzzle and the version published in the book. The puzzle text now reflects the version from the book, rather than the originally published version.
LikeLike
From The Sunday Times, 15th November 1987 [link]
A famous English mathematician, J.E. Littlewood, once posed the following puzzle:
Find a number N (sensibly the smallest) such that, if you shift the first digit to the end, the result is exactly one-and-a-half times N.
The solution to this being:
N = 1,176,470,588,235,294.
Professor Egghead has discovered a similar intriguing fact (not in his bath, nor sitting under a fruit-tree; but while relaxing in the club-house, after a round of golf). It is:
A smallest positive integer, M, such that, if one again shifts the leading digit to the end, the result is, this time, exactly just one half of M.
How many digits has M?
[teaser1315]
See: Puzzle #180, Enigma 653, Enigma 924, Teaser 2565, Enigma 1036, Enigma 455, Enigma 1161 (but note these may reveal the answer to this puzzle).
Normally a parasitic number [ @wikipedia ] involves multiplying the number by a(n integer) value by moving the final digit to the front.
This puzzle moves the front digit to the end, so we are looking at the inverse of the process involved in parasitic numbers. So if we find a 2-parasitic number, we can start with it, move the front digit (back) to the end, and it is divided by 2.
For this Python program I adapted my [[ parasitic() ]] function from Enigma 924 to deal with fractional multipliers, and this allows us to solve both problems mentioned in the puzzle text.
This program runs in 59ms. (Internal runtime is 167µs).
from enigma import (irange, inf, div, ndigits, first, printf)
# find numbers such that moving the final digit to the front
# result in a multiplication of the original number by k/q
def parasitic(k, q=1, M=inf, base=10):
assert k < q * base and q < k * base
b = base * k - q
# consider n digit numbers
for n in irange(1, M):
a = base**n * q - k
m = base**(n - 1)
# consider non-zero digits d
for d in irange(1, base - 1):
x = div(d * a, b)
if x is not None and m * base > x >= m:
yield base * x + d
# find numbers such that moving the first digit to the end
# result in a multiplication of the original number by p/q
# this is the same as finding a (q/p)-parasitic number
for (p, q) in [(3, 2), (1, 2)]:
# find the lowest number
for x in first(parasitic(q, p), 1):
n = div(x * q, p)
# output solution
printf("[{p}/{q}] {n} * {p}/{q} = {x} [{k} digits]", k=ndigits(n))
Solution: M has 18 digits.
The smallest number is 210526315789473684.
210526315789473684 × 1/2 = 105263157894736842
Note that this is the repetend of 4/19 = 0.(210526315789473684)…
If you don’t mind leading zeros we can apply the same procedure to the result (which also has 18 digits), to get:
105263157894736842 × 1/2 = 052631578947368421
See also: OEIS A337922, OEIS A146088.
LikeLike
# k-digit number n = fp = 2(10p + f) with 19p = (10^(k - 1) - 2)f
# 19p = a999...999b with a = f - 1 and b = 10 - 2f
for k in range(2, 99):
for f in range(2, 6):
# check for a multiple of 19
if (p19 := f * 10**(k - 1) - 2 * f) % 19: continue
s19 = str(p19)
a = str(f - 1)
b = str(10 - 2 * f)
if s19[1:-1] == "9" * (k - 2) and (s19[0], s19[-1]) == (a, b):
print("answer:", k)
break
else:
continue
break
LikeLike
From The Sunday Times, 19th May 2024 [link] [link]
George and Martha regularly read the obituaries in the national press; as well as the date of death, the date of birth of the person discussed is always shown. “That is interesting!” commented Martha as she looked at the three obituaries displayed one morning. Two of them have palindromic dates of birth (e.g., 13/11/31, 21/6/12). “Very unlikely, indeed!” agreed George.
Assuming that birth dates are expressed as day (1-31), month (1-12) year (00-99), what is the probability of a palindromic birth date in the 20th century (1900 to 1999 inclusive), and will it be greater, equal or less in the 21st century?
[teaser3217]
Technically the dates of the 20th century are 1st January 1901 – 31st December 2000, but that is not the convention followed in this puzzle. We are interested in the 19xx years and the 20xx years.
The answer to the second part of the puzzle comes from a fairly straightforward observation.
However, here is a constructive solution, that counts the palindromic dates in years 19xx and 20xx (assuming the calendar continues as expected, and that birth dates are uniformly distributed).
There are two ways we can check for palindromes, with or without the separators in the dates. In the following I am assuming that we only check the digits of the date, but the separators can be included at line 11 if required (although this changes the number of palindromic dates found).
Pete Good and
from datetime import (date, timedelta)
from enigma import (repeat, inc, is_palindrome, rdiv, compare, printf)
# return fraction of palindromic dates in years <a> - <b>
def pal(a, b):
p = t = 0
for d in repeat(inc(timedelta(days=1)), date(a, 1, 1)):
if d.year > b: break
t += 1
# look for palindromic dates
s = d.strftime("%-d%-m%y")
if is_palindrome(s): p += 1
r = rdiv(p, t)
printf("{a}..{b} -> {p}/{t} = {r}")
return r
# calculate fractions for years 19xx and 20xx
(P19, P20) = (pal(1900, 1999), pal(2000, 2099))
r = compare(P20, P19, vs=['less than', 'equal to', 'more than'])
printf("P(20xx) {r} P(19xx)")
Solution: The proportion of palindromic dates in the years 1900 – 1999 is 7/794. In the years 2000 – 2099 there will be a (slightly) smaller proportion of palindromic dates.
In each of the 19xx and 20xx years there are a total of 322 palindromic dates. (Each palindromic date can refer to a 19xx date and a 20xx date).
However, as the year 1900 was not a leap year and the year 2000 was, there is 1 less day in the 19xx years, and so there is a higher proportion of palindromes compared to the 20xx years.
Note, that if we use the actual definition of 20th and 21st centuries (1901 – 2000 and 2001 – 2100) the result is reversed, as the leap day in 2000 is included in the earlier period.
Manually, we can count the number of palindromic dates in a 100 year period by considering the following constructions:
x/y/yx → x = 1..9, y = 1..9 ⇒ 9×9 = 81 dates
xy/z/yx → xy = 10..31, z = 1..9 ⇒ 22×9 = 198 dates
x/yz/yx → x = 1..9, yz=10..12 ⇒ 9×3 = 27 dates
xy/zz/yx → xy = 10..31, zz=11 ⇒ 22×1 = 22 dates
For a grand total of 81 + 198 + 27 + 22 = 328 dates.
However not all of these dates are valid, as some months don’t have 31 days. So we can remove the following invalid dates:
30/2/03
31/2/13
31/4/13
31/6/13
31/9/13
31/11/13
(Note that: 29/2/92 is a valid date).
And that leaves 322 palindromic dates in a century.
We can also count the total number of days in a century:
There are 365×100 = 36500 non-leap days, plus the number of leap days.
There are 24 leap years per century, plus an extra one when the year is divisibly by 400. So 2000 was a leap year, but 1900 was not.
Hence, there are 24 leap days in the years 1900..1999, and 25 in the years 2000..2099.
The proportions are:
P(1900..1999) = 322/36524 = 7/794 ≈ 0.881612%
P(2000..2099) = 322/36525 ≈ 0.881588%
So the proportion of palindromic dates in the years 2000..2099 is slightly smaller than the proportion in the years 1900..1999.
LikeLike
Jim, I tried to run this program in Windows (using the Microsoft Visual Studio environment) but it generates the error INVALID FORMAT STRING because %-d and %-m are not supported by Microsoft. I am therefore hoping that my own C++ program has produced the correct solution!
LikeLike
Yes, I think this format is a glibc extension to strftime(). (Although it looks like Windows might use %# instead of %- to suppress zero padding).
But in Python 3 you can replace line 11 with:
s = f"{d.day}{d.month}{d.year % 100:02d}"
(which also seems to be faster).
or more generally:
s = str.format("{d}{m}{y:02d}", d=d.day, m=d.month, y=d.year % 100)
LikeLike
Thanks Jim, both of your suggestions work fine in Visual Studio and the program generated the same solution as my C++ program.
LikeLike
From The Sunday Times, 4th November 2012 [link] [link]
Last year I overheard this conversation one day during the first seven days of November:
Alec: It’s the 5th today, let’s have a bonfire.
Bill: No, the 5th is tomorrow.
Chris: You’re both wrong — the 5th is the day after tomorrow.
Dave: All three of you are wrong.
Eric: Yesterday was certainly not the 1st.
Frank: We’ve missed bonfire night.If you knew how many of their statements were true, then you could work out the date in November on which this conversation took place.
What was that date?
In Britain, Bonfire night is 5th November.
[teaser2615]
A straightforward puzzle to solve, either manually or programatically.
This Python program evaluates the statements on each of the 7 possible days, and looks for situations where the number of true statements uniquely identifies a single day.
from enigma import (irange, group, seq2str, printf)
# calculate statement values for date <d>
def statements(d):
# A: "It is the 5th today ..."
A = (d == 5)
# B: "The 5th is tomorrow ..."
B = (d + 1 == 5)
# C: "The 5th is the day after tomorrow ..."
C = (d + 2 == 5)
# D: "A, B, C are all wrong ..."
D = not (A or B or C)
# E: "Yesterday was not the 1st ..."
E = (d - 1 != 1)
# F: We have missed bonfire night (the 5th) ..."
F = (d > 5)
return [A, B, C, D, E, F]
# group dates by the number of true statements
g = group(irange(1, 7), by=(lambda d: statements(d).count(True)))
# look for groups with a single member
for (k, vs) in g.items():
if len(vs) == 1:
printf("{k} true -> {vs} November", vs=seq2str(vs, sort=1, enc=""))
Solution: The conversation took place on 2nd November.
There is only 1 true statement, and it is made by Dave.
LikeLike
# the number of correct statements
fn = lambda d: sum([d == 5, d == 4, d == 3, d < 3 or d > 5, d != 2, d > 5])
seen, sols = set(), dict()
# now find a count that is unique
for d in range(1, 8):
if (c := fn(d)) in seen:
try:
del sols[c]
except KeyError:
pass
else:
sols[c] = str(d)
seen.add(c)
print(f"answer: November {' or '.join(sols.values())}")
LikeLike
T = the date today.
A: T = 5.
B: T = 4.
C: T = 3.
D: T != 3, 4, 5.
E: T != 2.
F: T = 6 v T = 7.
Of A, B, C and D, 1 is true, 3 are false.
There can therefore be 1, 2 or 3 true statements.
With 3 true statements, both E and F are true. T could be 6 or 7.
With 2 true statements, either E or F is true. If E is true, T = 2. If F is true, T could be 1, 3, 4 or 5.
With 1 true statement, both E and F are false. T = 2. This is the only option leading to 1 answer. Therefore there was 1 true statement and it’s 2nd November.
LikeLike
% A Solution in MiniZinc include "globals.mzn"; var 1..7: T; % Date conversation took place % A - F statements constraint sum([T==5, T==4, T==3, T!=3 \/ T!=4 \/ T!=5, T!=2, T==6 \/ T==7]) == 1; solve satisfy; output [" T = " ++ show(T)]; % T = 2; %--------- %=========
LikeLike
From The Sunday Times, 5th October 1980 [link]
Joe decided to utilise the garden see-saw to demonstrate the principles of balance, and of moments to, his family. Alf, Bert, Charlie, Doreen, Elsie and Fiona weighed 100, 80, 70, 60, 50 and 20 kilos respectively. The seesaw had three seats each side, positioned 1, 2 and 3 metres from the centre.
They discovered many ways of balancing using some or all of the family.
In one particular combination, with at most one person on each seat, one of the family not on the seesaw observed that the sum of the moments of all of the people on the seesaw was a perfect square.
“That’s right”, said Joe, “but, as you can see, it doesn’t balance — and what’s more, there’s nowhere you can sit to make it balance”.
“Wrong”, was the reply. “I could sit on someone’s lap”.
“True,” said Joe, “but only if you sit at the end”.
Which two would then be sitting together, and who else, if anyone, would be on the same side of the see-saw?
[To find the moment due to each person, multiply their distance from the centre by their weight. The sum of the moments on one side should equal the sum of those on the other if balance is to be achieved].
This puzzle is included in the book The Sunday Times Book of Brainteasers (1994).
[teaser950]
Participants can be uniquely identified by their weights.
This Python program finds possible seating arrangements on the see-saw.
It runs in 72ms. (Internal runtime is 13ms).
from enigma import (subsets, is_square, div, printf)
# weights and positions
weights = [100, 80, 70, 60, 50, 20]
poss = [+1, +2, +3, -1, -2, -3]
# there is at least one member not seated
for ws in subsets(weights, min_size=2, max_size=len(weights) - 1, select='C'):
# allocate positions (including +3)
for ps in subsets(poss, size=len(ws), select='P'):
if +3 not in ps: continue
# find the total sum of the moments
ms = sum(w * abs(p) for (w, p) in zip(ws, ps))
if not is_square(ms): continue
# weight required at +3 to balance the see-saw
x = -sum(w * p for (w, p) in zip(ws, ps))
w = div(x, +3)
# is it the weight of a missing person?
if not (w in weights and w not in ws): continue
# output solution
printf("ws={ws} ps={ps} ms={ms} x={x} w={w}")
Solution: Doreen would join Fiona at the end of the see-saw. Elsie is also seated on the same side.
The seating arrangement is as follows:
Without D the moments are (kg.m):
L = 70×3 + 80×1 = 290
R = 20×3 + 50×1 = 110
They don’t balance, but they do sum to 400 = 20^2.
With D the moments on the right become:
R = (20 + 60)×3 + 50×1 = 290
and the see-saw balances.
LikeLike
from enigma import express
from itertools import product
# weights and positions
weights = [100, 80, 70, 60, 50, 20]
names = ["Alf", "Bert", "Charlie", "Doreen", "Elsie", "Fiona"]
# possible squares divisible by 10
for sq in [100, 400, 900]:
# decompose square into weights
for e in express(sq, weights, min_q=0, max_q=3):
# someone is sitting at the end and one place is empty
if all(x for x in e) or 3 not in e: continue
# at most one person on each seat
if any(e.count(i) > 2 for i in range(1, 4)): continue
# one of the family not on the seesaw to sit at the end on someone's lap
for i, seat in enumerate(e):
if seat: continue # not an empty seat
e1 = e[:i] + [3] + e[i + 1:]
# multiply elements by 1 or -1 times the weight and
# see if they sum to zero
for prod in product([-1, 1], repeat=len([x for x in e1 if x])):
if prod[0] > 0: continue # avoid symmetric duplicates
# weave in zeroes
p = list(prod)
p = [p.pop(0) if x else 0 for x in e1]
# is the seesaw in balance?
if sum([x * y * weights[i]
for i, (x, y) in enumerate(zip(p, e1))]) != 0: continue
# new persion must be sitting on someone's lap at the end
someone = [j for j in range(6) if j != i and e1[j] == 3 and
p[j] == p[i]]
if not someone: continue
print(f"{names[i]} would join {names[someone[0]]}",
f"at the end ofthe see-saw.")
oths = [j for j in range(6) if p[j] == p[i] and
j not in {i, someone[0]}]
if not oths: continue
ns = [names[o] for o in oths]
oths = ns[0] + " is" if len(oths) == 1 else ' and '.join(ns) + " are"
print(f"{oths} also seated on the same side.")
LikeLike
From The Sunday Times, 12th May 2024 [link] [link]
A French farmer’s estate is shaped like a right-angled triangle ABC on top of a square BCDE. The triangle’s hypotenuse is AB, and its shortest side, AC, has length 1 kilometre. Nearing retirement, the farmer decides to sell off the square of land and, obeying the Napoleonic law of succession, divide the triangle into three equal plots, one for each of his two children and a third for him and his wife in retirement. His surveyor discovers, surprisingly, that his remaining triangle of land can be divided neatly into three right-angled triangles, all identical in shape and size (allowing for reflections / rotations).
How many hectares did the farmer sell?
(1 hectare = area of 100m × 100m plot).
[teaser3216]
I found it easiest to start from the end:
For the final dissection we need to find 3 identical right-angled triangles that can fit together to form a triangle.
It is possible to do this such that the combined triangle is a larger version of the small triangles.
We can fit three identical (30°, 60°, 90°) triangles together to form a larger (30°, 60°, 90°) triangle as shown.
So this can serve as a dissection of the original triangular plot, and also the farmer’s allocated plot.
The ratio of the sides in the (30°, 60°, 90°) triangle are 1 : √3 : 2.
So, if the shortest side has length 1 km, the remaining non-hypotenuse side has length √3 km, and this is the same as the side of the square plot.
Hence the square plot has an area of 3 km², and there are 100 hectares per square kilometre:
Solution: The farmer sold 300 hectares.
Although this is not the only possible arrangement.
The first dissection only has to be into 3 equal area triangles (so they don’t have to be identical), so here is another possible arrangement (where the first dissection can be made by dividing BC into three equal parts):
LikeLike
From The Sunday Times, 30th September 2012 [link] [link]
Recently Alex, Bernard and Charles were comparing their ages in years. Alex’s age was an odd two-digit number and Bernard’s age was a whole number percentage more than that. On the other hand, Charles’s age was also an odd two-digit number but Bernard’s age was a whole number percentage less than that. They were surprised to find that the percentage was the same in both cases.
What were their three ages?
[teaser2610]
Supposing the 3 are all different ages (so the percentage is non-zero).
A’s age is an odd 2-digit number, and C’s age is a (larger) odd 2-digit number, and so B’s age is between them, hence also a 2-digit number.
For percentage p we have:
A (100 + p) / 100 = B
C (100 − p) / 100 = B
⇒
p = 100 (C − A) / (C + A)
The following Python program runs in 67ms. (Internal runtime is 463µs).
from enigma import (irange, subsets, div, printf)
# ages for A and C (2-digit, odd)
for (A, C) in subsets(irange(11, 99, step=2), 2):
# calculate percentage
p = div(100 * (C - A), C + A)
if p is None: continue
# calculate B
B = div(A * (100 + p), 100)
if B is None: continue
# output solution
printf("A={A} B={B} C={C} [p={p}%]")
Solution: Alex is 15. Bernard is 21. Charles is 35.
And the percentage in question is 40%:
15 + 40% = 15 × (1 + 0.4) = 21
35 − 40% = 35 × (1 − 0.4) = 21
LikeLike
for a in range(11, 100, 2):
# determine valid percentages, maximum percentage = (99 - 12) / 99 = 0.87878
for p in [p for p in range(2, 88, 2) if (p * a) % 100 == 0]:
b = a + (p * a) // 100
c, r = divmod(100 * b, 100 - p)
if c > 99: break
if r or c % 2 == 0: continue
print("answer:", (a, b, c))
LikeLike
% A Solution in MiniZinc include "globals.mzn"; var 11..99:A; var 11..99:B; var 11..99:C; var 1..95:p; % Percentage constraint all_different([A, B, C]); constraint sum([A mod 2 == 1, B mod 2 == 1, C mod 2 == 1]) == 3; constraint 100*A + p*A == 100*B; constraint 100*C - p*C == 100*B; solve satisfy; output["[Alex, Bernard, Charles] = " ++ show([A, B, C]) ]; % [Alex, Bernard, Charles] = [15, 21, 35] % ---------- % ==========
LikeLike
From The Sunday Times, 18th November 2012 [link] [link]
Every schoolchild knows that it is possible for two triangles to have two of their lengths-of-sides in common and one of their angles in common without the two triangles being identical or “congruent”.
This can happen when the common angle is not included between the two common sides. I have found such a pair of non-congruent triangles with all the lengths of the sides being a whole number of centimetres and with the longest side of each triangle being 10cm in length.
What are the lengths of the other two sides of the smaller triangle?
[teaser2617]
Each triangle has a longest side of 10, so the remaining two sides must be 1 – 9, so there aren’t that many triangles to consider.
This Python program considers the side lengths of possible triangles and uses the cosine rule to calculate the internal angles, and then looks for two different triangles that share an angle.
It runs in 72ms. (Internal runtime is 664µs).
from enigma import (fraction as Q, irange, intersect, call, cache, printf)
# return values as cosines (using cosine rule)
cosA = lambda x, y, z: Q(y*y + z*z - x*x, 2*y*z)
# find the angles of a triangle with sides x, y, z
@cache
def _angles(x, y, z):
# is it a valid triangle?
if x + y > z:
return {cosA(x, y, z), cosA(y, z, x), cosA(z, x, y)}
angles = lambda *ss: call(_angles, sorted(ss))
# choose the shared side a
for a in irange(1, 9):
# choose the shorter remaining side b
for b in irange(1, 8):
angles1 = angles(a, b, 10)
if not angles1: continue
# choose the longer remaining side c
for c in irange(b + 1, 9):
angles2 = angles(a, c, 10)
if not angles2 : continue
# check for a common angle
if intersect([angles1, angles2]):
# output solution
printf("({a}, {b}, 10) -> {angles1}; ({a}, {c}, 10) -> {angles2}")
Solution: The other two sides of the smaller triangle are: 4cm and 8cm.
The triangles look like this:
And the common angle α is acos(13/20) ≈ 49.46°.
LikeLike
This result follows directly from using the cosine rule on the shared angle of both triangles:
Suppose the base of the triangle is d, and we can make two triangles with the same angle α using sides b, a and c, a.
Then, using the cosine rule on both triangles:
cos(α) = (d² + b² − a²)/2db = (d² + c² − a²)/2dc
⇒
c(d² + b² − a²) = b(d² + c² − a²)
(c − b)(d² − a²) − bc(c − b) = 0
(c − b)(d² − a² − bc) = 0
[b ≠ c] ⇒
bc = d² − a² = (d − a)(d + a)
Which gives a straightforward program:
from enigma import (irange, divisors_pairs, printf)
d = 10
for a in irange(1, d - 1):
for (b, c) in divisors_pairs(d*d - a*a):
if b < c < d:
printf("triangles = ({d}, {a}, {b}) ({d}, {a}, {c})")
LikeLike
% A Solution in MiniZinc include "globals.mzn"; var 1..9:A; var 1..9:B; var 1..9:C; int: D == 10; % Two triangles are ABD and ACD constraint B * C == D * D - A * A; constraint B < C /\ C < D; solve satisfy; output ["Two triangles are " ++ show([A,B,D]) ++ " and " ++ show([A,C,D]) ]; % Two triangles are [8, 4, 10] and [8, 9, 10] % ---------- % ==========
LikeLike
From The Sunday Times, 16th November 1975 [link]
Young Bob had been given a carpentry set and with it a rectangular board (whose diagonal measured less than 1½ metres) on which to practise using his saw.
With straight cuts of successively greater length and aggregating to an exact number of metres, he first proceeded to saw dissimilar triangular pieces off each corner of the board in turn, the remaining quadrilateral piece being put aside for another day.
All the 12 sides of the sawn-off pieces measured exact and different numbers of centimetres.
What were the length and width of the board? (in cms).
As set this puzzle has multiple solutions, however if we interpret “less than 1½ meters” to mean “less than 150 cm, but more than 149 cm”, then we get a unique solution that is the same as that published in the newspaper.
This puzzle was originally published with no title.
[teaser748]
Perhaps the puzzle originally said “just less than 1½ metres”, but the “just” got lost somewhere.
The following program assembles pairs of Pythagorean triangles point-to-point. This gives us candidate widths and heights for the board. We then find two pairs with the same width that fit together to make a rectangle as specified.
By “dissimilar” triangles I am assuming that no pair of triangles is mathematically similar (i.e. none of them are multiples of the same primitive Pythagorean triangle).
The program runs in 108ms. (Internal runtime is 40ms).
from enigma import (
defaultdict, pythagorean_triples, subsets, cproduct,
seq_all_different, hypot, rev, ordered, ratio, cached, printf
)
# diagonal limit
D = 150
# possible triangles (x, y) -> z
tris = dict(((x, y), z) for (x, y, z) in pythagorean_triples(D - 1))
# primitive triangle
primitive = cached(lambda t: ratio(*t))
# assemble pairs of triangles: <combined-width> -> (<h1>, <h2>) -> (<w1>, <w2>)
pairs = defaultdict(lambda: defaultdict(set))
for (k1, k2) in subsets(tris.keys(), size=2):
for ((w1, h1), (w2, h2)) in cproduct((k, rev(k)) for k in (k1, k2)):
w = w1 + w2
if w < D:
(k, v) = ((h1, h2), (w1, w2)) if h1 < h2 else ((h2, h1), (w2, w1))
pairs[w][k].add(v)
# choose a width and height for the initial rectangle
for (w, h) in subsets(pairs.keys(), size=2):
z = hypot(w, h)
if not (D - 1 < z < D): continue
# choose a pair of triangles for the base
for k1 in pairs[w]:
(h1, h2) = k1
# calculate the corresponding matched pair
k2 = (h4, h3) = (h - h2, h - h1)
if not (k2 > k1 and k2 in pairs[w]): continue
for ((w1, w2), (w4, w3)) in cproduct(pairs[w][k] for k in (k1, k2)):
# assemble the triangles
(x1, y1, x2, y2, x3, y3, x4, y4) = (h1, w1, w2, h2, h4, w4, w3, h3)
(z1, z2, z3, z4) = (tris[ordered(x, y)] for (x, y) in [(x1, y1), (x2, y2), (x3, y3), (x4, y4)])
# sum of cuts is a multiple of 100
T = z1 + z2 + z3 + z4
if T % 100 != 0: continue
# sides are all different
ts = (t1, t2, t3, t4) = ((x1, y1, z1), (x2, y2, z2), (x3, y3, z3), (x4, y4, z4))
if not seq_all_different(t1, t2, t3, t4): continue
# triangle are dissimilar
if not seq_all_different(primitive(ordered(*t)) for t in ts): continue
# output solution
printf("{w} x {h} -> {z:.2f}; {t1} {t2} {t3} {t4} T={T}")
Solution: The board was: 28 cm × 147 cm.
And here is how the triangles fit together:
If we just look for any diagonal that is less than 150cm (which is a direct interpretation of the published puzzle text), then we find the following 23 solutions (ordered by length of diagonal):
# Z = diagonal; T = total length of cuts 28 × 147: Z=149.64 (12, 35, 37) (15, 112, 113) (16, 63, 65) (13, 84, 85) T=300 51 × 140: Z=149.00 (15, 20, 25) (35, 120, 125) (36, 77, 85) (16, 63, 65) T=300 87 × 120: Z=148.22 (7, 24, 25) (72, 96, 120) (80, 84, 116) (15, 36, 39) T=300 48 × 140: Z=148.00 (15, 20, 25) (35, 120, 125) (33, 56, 65) (13, 84, 85) T=300 60 × 135: Z=147.73 (9, 12, 15) (90, 48, 102) (126, 32, 130) (45, 28, 53) T=300 103 × 105: Z=147.09 (5, 12, 13) (60, 91, 109) (100, 75, 125) (45, 28, 53) T=300 95 × 112: Z=146.86 (20, 21, 29) (60, 91, 109) (75, 100, 125) (35, 12, 37) T=300 83 × 120: Z=145.91 (18, 24, 30) (28, 96, 100) (65, 72, 97) (55, 48, 73) T=300 100 × 105: Z=145.00 (9, 40, 41) (72, 65, 97) (91, 60, 109) (28, 45, 53) T=300 90 × 112: Z=143.68 (20, 48, 52) (40, 42, 58) (92, 69, 115) (72, 21, 75) T=300 60 × 129: Z=142.27 (3, 4, 5) (33, 56, 65) (126, 32, 130) (96, 28, 100) T=300 69 × 124: Z=141.90 (9, 40, 41) (13, 84, 85) (60, 91, 109) (56, 33, 65) T=300 85 × 111: Z=139.81 (5, 12, 13) (20, 99, 101) (80, 39, 89) (65, 72, 97) T=300 93 × 104: Z=139.52 (20, 21, 29) (65, 72, 97) (84, 13, 85) (39, 80, 89) T=300 92 × 104: Z=138.85 (5, 12, 13) (39, 80, 89) (99, 20, 101) (65, 72, 97) T=300 59 × 124: Z=137.32 (7, 24, 25) (12, 35, 37) (117, 44, 125) (112, 15, 113) T=300 76 × 114: Z=137.01 (15, 36, 39) (9, 40, 41) (99, 20, 101) (105, 56, 119) T=300 80 × 111: Z=136.82 (5, 12, 13) (20, 99, 101) (75, 100, 125) (60, 11, 61) T=300 84 × 108: Z=136.82 (3, 4, 5) (18, 80, 82) (105, 36, 111) (90, 48, 102) T=300 95 × 96: Z=135.06 (16, 63, 65) (60, 32, 68) (80, 18, 82) (36, 77, 85) T=300 93 × 95: Z=132.94 (11, 60, 61) (56, 33, 65) (84, 13, 85) (39, 80, 89) T=300 67 × 72: Z= 98.35 (9, 12, 15) (48, 55, 73) (63, 60, 87) (24, 7, 25) T=200 56 × 78: Z= 96.02 (8, 15, 17) (16, 63, 65) (48, 36, 60) (40, 42, 58) T=200
and we see the published solution is the first of these (longest diagonal).
LikeLike
His saw cuts (each of which became the hypotenuse of a triangle) were progressively longer as he moved round the board to each corner in turn. Did you take that into account?
LikeLike
I didn’t check that the cut lengths can form an increasing sequence (going clockwise or anticlockwise around the board), as I decided he could just make the four cuts in ascending order, however they are arranged.
But if you do require this there are still 9 different solutions with diagonals <150 cm (including the published one).
LikeLike
I think we can reduce it to a single solution if we add the words
“The board had the smallest possible area, consistent with what has been said.”
LikeLike
From The Sunday Times, 5th May 2024 [link] [link]
In our darts league, each team plays each other once. The result of each match is decided by the number of legs won, and each match involves the same number of legs. If both teams win the same number of legs, the match is drawn. The final league table shows the games won, drawn or lost, and the number of legs won for and against the team. The Dog suffered the most humiliating defeat, winning only one leg of that match. Curiously, no two matches had the same score.
What was the score in the match between The Crown and The Eagle?
[teaser3215]
Each team plays 4 matches and 80 legs, so each match has 20 legs. A and B draw, so their match is 10-10.
D has a 1-19 match, so the scores in the other matches are between 2 and 18 (excluding 10), which is 16 values distributed between 16 different slots, so each value appears exactly once.
Here is a solution using the [[ SubstitutedExpression ]] solver from the enigma.py library.
The following run file executes in 83ms. (Internal runtime is 4.4ms).
#! python3 -m enigma -rr
SubstitutedExpression
# suppose the matches (X v Y) and scores for X are:
#
# A v B = Q
# A v C = R
# A v D = S
# A v E = T
# B v C = U
# B v D = V
# B v E = W
# C v D = X
# C v E = Y
# D v F = Z
--base=20 # allow scores of 1-19
--digits="1-19"
--code="v = lambda x: 20 - x" # opponent's score
# scores for each match for each team
--macro="@A = [Q, R, S, T]"
--macro="@B = [v(Q), U, V, W]"
--macro="@C = [v(R), v(U), X, Y]"
--macro="@D = [v(S), v(V), v(X), Z]"
--macro="@E = [v(T), v(W), v(Y), v(Z)]"
# total legs for each team
"sum(@A) == 55" # A
"sum(@B) == 43" # B
"sum(@C) == 37" # C
"sum(@D) == 41" # D
"sum(@E) == 24" # E
# A and B drew (10-10)
--assign="Q,10"
# all matches have different scores
"seq_all_different(ordered(x, v(x)) for x in [Q, R, S, T, U, V, W, X, Y, Z])"
# D won 1 leg in one game, and this was the worst score
"1 in { v(S), v(V), v(X), Z }"
--invalid="1|19,RTUWY"
# won, drawn, lost
--code="""
def wdl(ss):
vs = list(compare(s, 10) for s in ss)
return (vs.count(1), vs.count(0), vs.count(-1))
"""
"wdl(@A) == (2, 1, 1)" # A
"wdl(@B) == (1, 1, 2)" # B
"wdl(@C) == (2, 0, 2)" # C
"wdl(@D) == (3, 0, 1)" # D
"wdl(@E) == (1, 0, 3)" # E
# answer is the score in CE
--answer="(Y, v(Y))"
--template=""
Solution: The score in the Crown vs Eagle match was 16-4.
There are two possible sets of scores in the matches:
A v B = 10-10
A v C = 8-12 / 18-2
A v D = 19-1
A v E = 18-2 / 8-12
B v C = 17-3 / 7-13
B v D = 9-11
B v E = 7-13 / 17-3
C v D = 6-14
C v E = 16-4
D v E = 15-5
LikeLike
Another idea would be to start the first variables Q, R, S and T with “D vs …” so we can use base=19 and digits=”1-18″.
LikeLike
# decompose number <t> into <k> increasing numbers (between <mn> and <mx>)
# so that sum(<k> numbers) equals <t>
def decompose(t, k=4, mn=2, mx=19, s=[]):
if k == 1:
if s[-1] < t <= mx:
yield s + [t]
else:
for n in range(mn if not s else s[-1] + 1, mx + 1):
if 2 * k * n + k * (k - 1) > 2 * t: break
yield from decompose(t - n, k - 1, mn, mx, s + [n])
# general checks
def check(s, grp):
s_ = set(s) - {10}
# all matches have different scores (we have not won/lost from ourselves)
if any(20 - x in s for x in s_) : return False
# different scores (except draw)
if any(s_.intersection(g) for g in grp): return False
# we have not played more than once against the same opponent
return all(sum(20 - x in g for x in s) < 2 for g in grp)
sols = set()
# points for The Dog (three victories)
for D in decompose(41 - 1, 3, 11):
D += [1] # winning only one leg of that match
# points for The Anchor
for A in decompose(55):
if A[1] != 10: continue # A: 2W/1D/1L
if not check(A, [D]): continue
# points for Eddy
for E in decompose(24):
if 10 in E or E[2] > 10 or E[3] < 11: continue # E: 1W/3L
if not check(E, [D, A]): continue
# points for The Crown
for C in decompose(37):
if 10 in C or C[1] > 10 or C[2] < 10: continue # C: 2W/2L
if not check(C, [D, A, E]): continue
# now we know points for The Bull
B = set(range(1, 20)).difference(D + A + E + C) | {10}
if not check(B, [D, A, E, C]): continue
# collect score in the match between The Crown and The Eagle
for c in C:
if 20 - c in E:
sols.add(c)
for c in sols:
print(f"answer: {c} vs {20 - c}")
LikeLike
More compact but less efficient.
from itertools import permutations
# wins/draws/losses
wdl = lambda s: [w := 4 - (l := sum(x < 10 for x in s)) - (10 in s),
4 - w - l, l]
v = lambda x: 20 - x # opponent's score
AB, AC, AD, AE, DB, DC, DE, EB, EC, BC = [0] * 10
vars = lambda k: [AB, AC, AD, AE, DB, DC, DE, EB, EC, BC][:k]
# general checks
def check(t, v3, scores, vs):
# check wins/draws/losses
if wdl([v := t - sum(v3)] + v3) != scores: return False
# all matches have different scores
if (min(ms := set(tuple(sorted([x, 20 - x])) for x in vs + [v])) >= (1, 19)
and len(set(ms)) == len(vs) + 1): return v
sols = set()
AB = 10
for AC, AD in permutations(range(2, 20), 2):
if not(AE := check(55, [AB, AC, AD], [2, 1, 1], vars(3))): continue
for DB, DC in permutations(range(1, 19), 2):
if not(DE := check(41, [v(AD), DB, DC], [3, 0, 1], vars(6))): continue
if 1 not in {v(AD), DB, DC, DE}: continue # winning only one leg ...
for EB in range(2, 19):
if not(EC := check(24, [v(AE), v(DE), EB], [1, 0, 3], vars(8))): continue
if not(check(43, [v(AB), v(DB), v(EB)], [1, 1, 2], vars(9))): continue
sols.add(EC)
for s in sols:
print(f"C vs E: {v(s)} - {s}")
LikeLike
From The Sunday Times, 6th February 1972 [link]
Sever-Nek, the Grand Vizier, was suspicious of the influence which Azi-Muth. the Sultan’s wily tutor, was gaining over his young pupil, and had determined to have him removed, when chance played into his hands.
The Sultan had a collection of nearly 2,000 small square tiles, all the same size in various colours, and one day to please his tutor had arranged some of them into a square with a pretty central design and a border. Then he announced that he had made two smaller equal squares using the same pieces. “But that is impossible, said Muth, “there must be some left over”.
There was one over, and Sever-Nek, happening to pass by put his foot over it. “Surely not”, he said. “His Serene Highness has made a most interesting discovery. No doubt the same thing can be done again. Let us add some extra tiles from the box to those already used”. Nothing loath, the Sultan soon produced a larger square from which he almost made two smaller identical squares. This time he was one tile short.
“Your Serene Highness must have dropped this one on the floor”, said the Grand Vizier, moving his foot. Allow me to complete the design”. The discomfiture of the outwitted tutor was no less complete than his disgrace.
How many extra tiles were taken from the box to make the larger square?
This puzzle is included in the book Sunday Times Brain Teasers (1974).
[teaser553]
We can suppose the requirement for a “pretty central design” is to preclude very small squares. I assumed the initial square was at least 5×5.
This Python program runs in 62ms. (Internal runtime is 399µs).
John Crabtree and
from enigma import (irange, inf, sq, is_square, printf)
# record (x, y) where x^2 = 2 y^2 + d for d in [+1, -1]
ss = { +1: [], -1: [] }
for j in irange(2, inf):
n = sq(j)
if n > 1000: break
# look for deltas
for d in ss.keys():
i = is_square(2*n + d)
if i:
printf("[{d:+d}] {i}^2 = 2x {j}^2 {d:+d}")
ss[d].append((i, j))
# look for an initial +1, with a size at least 5
for (x1, y1) in ss[+1]:
if x1 < 5: continue
# and a larger -1
for (x2, y2) in ss[-1]:
if not (x2 > x1): continue
# calculate the number of extra tiles (remembering one is hidden)
d = sq(x2) - sq(x1) + 1
# output solution
printf("{d} extra tiles [{x1}^2 = 2 {y1}^2 + 1 -> {x2}^2 = 2 {y2}^2 - 1]")
Solution: 1393 extra tiles were taken to make the larger square.
The initial square was 17×17 (= 289 tiles), which can be rearranged as two 12×12 squares (= 144 tiles each) with one tile left over (and hidden).
With an extra 1393 tiles we get a total of 288 + 1393 = 1681 which can be arranged into a 41×41 square.
The 1681 tiles can also be arranged into two 29×29 squares (= 841 tiles each), except one of them is one tile short, and completed by the hidden tile.
If a small initial square is allowed then there is a further solution, starting with a 3×3 square (9 tiles), this is rearranged into two 2×2 squares (8 tiles each), with one tile left over. We can then add 41 extra tiles to make a 7×7 square which can split into two 5×5 squares, one of which requires the hidden tile. (Or an extra 1673 tiles could be added to make two 29×29 squares, as above).
LikeLike
The sides of the larger and smaller squares are given in the sequences
https://oeis.org/A001333 Numerators of continued fraction convergents to sqrt(2), and
https://oeis.org/A001329 Denominators of continued fraction convergents to sqrt(2).
Then all one needs to do is to find the side of the biggest larger square < sqrt(2000), ie 41, and work from there.
LikeLike
From The Sunday Times, 14th October 2012 [link] [link]
Five friends, Abel, Bob, Jedd, Tim and Will, were investigating birthdays. Abel commented that there was just one letter of the alphabet that occurred in both his star sign and in his month of birth.
After further investigation he found that for any pair of his star sign, his month of birth, his name, and the day of the week on which he was born, just one letter of the alphabet occurred in both. Remarkably, the same turned out to be true for each of the friends.
Their names are listed alphabetically. What, respectively, are their star signs?
[teaser2612]
This is a “grouping” style problem (for which there is a solver in enigma.py), but in this case the non-primary values (i.e. signs, month, day) can be re-used, and the signs and months are not independent (i.e. a particular sign spans two consecutive months).
This Python program runs in 67ms. (Internal runtime is 4.4ms).
from enigma import grouping
# names
names = "Abel Bob Jedd Tim Will".split()
# map months -> month number
months = "January February March April May June July August September October November December".split()
months = dict((x, i) for (i, x) in enumerate(months, start=1))
# map signs -> valid month numbers
signs = {
"Aries": {3, 4},
"Taurus": {4, 5},
"Gemini": {5, 6},
"Cancer": {6, 7},
"Leo": {7, 8},
"Virgo": {8, 9},
"Libra": {9, 10},
"Scorpio": {10, 11},
"Sagittarius": {11, 12},
"Capricorn": {12, 1},
"Aquarius": {1, 2},
"Pisces": {2, 3},
}
# days
days = "Monday Tuesday Wednesday Thursday Friday Saturday Sunday".split()
# check a (<name>, <sign>, <month>, <day>) group
def check(n, s, m, d, fn=grouping.share_letters(1)):
# sign/month should match, as well as the shared letters
return (months[m] in signs[s]) and fn(n, s, m, d)
# find candidate groups (allowing repeated values)
grouping.solve([names, signs.keys(), months.keys(), days], check, distinct=0)
Solution: The star signs are: Pisces, Virgo, Leo, Virgo, Leo.
The full solution is:
Abel: Pisces, March, Sunday
Bob: Virgo, September, Monday
Jedd: Leo, July, Monday
Tim: Virgo, August, Monday
Will: Leo, July, Wednesday
LikeLike
Here’s my solution:
import itertools
def day_month_to_zodiac(day, month):
signs = [
("capricorn", 19),
("aquarius", 18),
("pisces", 20),
("aries", 19),
("taurus", 20),
("gemini", 20),
("cancer", 22),
("leo", 22),
("virgo", 22),
("libra", 22),
("scorpio", 21),
("sagittarius", 21),
("capricorn",),
]
return signs[month - (day <= signs[month - 1][1])][0]
month_names = "x january febuary march april may june july august september october november december".split()
weekday_names = "monday tuesday wednesday thursday friday saturday sunday".split()
for first_name in "abel bob jedd tim will".split():
for month, weekday_name in itertools.product(range(1, 13), weekday_names):
month_name = month_names[month]
for zodiac_name in (day_month_to_zodiac(1, month), day_month_to_zodiac(31, month)):
if all(len(set(c0) & set(c1)) == 1 for c0, c1 in itertools.combinations((first_name, month_name, zodiac_name, weekday_name), 2)):
print(first_name, zodiac_name, month_name, weekday_name)
LikeLike
first_names = "abel bob jedd tim will".split()
zodiac_names = "capricorn aquarius pisces aries taurus gemini cancer " \
"leo virgo libra scorpio sagittarius".split()
month_names = "january febuary march april may june july august " \
"september october november december".split()
weekday_names = "monday tuesday wednesday thursday " \
"friday saturday sunday".split()
# does sequence <x> share exactly one item with all sequences in <g>
share1 = lambda x, g: all(len(set(x).intersection(z)) == 1 for z in g)
sols = []
for m, mo in enumerate(month_names, start=1):
for zo in (zodiac_names[m - 1], zodiac_names[m % 12]):
if not share1(zo, [mo]): continue
for wd in weekday_names:
if not share1(wd, [mo, zo]): continue
for nm in first_names:
if not share1(nm, [mo, zo, wd]): continue
sols.append((nm, zo))
print(', '.join(x[1] for x in sorted(sols)))
LikeLike
From The Sunday Times, 28th April 2024 [link] [link]
Clark took a sheet of A4 paper (8.27 × 11.69 inches) and cut out a large square with dimensions a whole number of inches. He cut this into an odd number of smaller squares, each with dimensions a whole number of inches. These were of several different sizes and there was a different number of squares of each size; in fact, the number of different sizes was the largest possible, given the above.
It turns out that there is more than one way that the above dissection can be made, but Clark chose the method that gave the smallest number of smaller squares.
How many smaller squares were there?
[teaser3214]
The largest (integral sized) square that can cut from a sheet of A4 is 8 inches × 8 inches. And in order to get multiple different sizes of smaller square we need at least a 3 × 3 square.
I am assuming that when the puzzle refers to “more than one way that the dissection can be made”, it means there are multiple different possible sets of smaller squares. (Not the same set just assembled in a different way to form the larger square).
By using the [[ express() ]] function from the enigma.py library to find candidate dissections, and the rectpack.py library to fit the smaller squares into the larger square, I was able to quickly write a program that runs in a reasonable time.
However, the rectpack.py library wasn’t designed to handle multiple rectangles of the same shape, and was not as efficient as it could be in this case. So I have updated it to cope better with this situation, and the program now runs even faster.
The following Python program runs in 95ms. (Internal runtime is 28ms).
from enigma import (Accumulator, irange, express, multiset, seq_all_different, group, item, printf)
import rectpack
# can we pack the squares?
def pack(n, ms):
rs = list((x, x) for x in ms.elements())
for ps in rectpack.pack(n, n, rs):
return ps # a single packing will do
# find the largest number of different sizes of smaller square [at least 3]
acc = Accumulator(fn=max, value=3, collect=1)
# consider the size of the larger square
for n in irange(8, 3, step=-1):
# consider the areas of smaller squares
ss = list(irange(1, n - 1))
# decompose n^2 into smaller squares
for qs in express(n * n, (i * i for i in ss)):
# there was an odd number of smaller squares
if sum(qs) % 2 != 1: continue
# and there were "several" sizes
k = len(qs) - qs.count(0)
if k < acc.value: continue
ms = multiset.from_pairs(zip(ss, qs))
# and a different number of each size
if not seq_all_different(ms.values()): continue
# attempt to pack the squares
ps = pack(n, ms)
if ps:
# record (<size of large square>, <number of smaller squares>, <packing>)
acc.accumulate_data(k, (n, ms.size(), ps))
if acc.data:
printf("{acc.value} different sizes of smaller squares")
# consider possible sizes of larger square
g = group(acc.data, by=item(0))
for (k, vs) in g.items():
# we need multiple ways to dissect the square
if len(vs) < 2: continue
printf("{k} x {k} square -> {n} dissections", n=len(vs))
# find the minimal number of smaller squares
sm = min(s for (n, s, ps) in vs)
printf("min {sm} smaller squares")
for (n, s, ps) in vs:
if s == sm:
rectpack.output_grid(n, n, ps, end="--")
Solution: There were 13 smaller squares.
The maximum number of different sizes of smaller squares is 4. It is possible to dissect 5×5, 6×6, 7×7, 8×8 using 3 different sizes of smaller squares, but only 8×8 can be dissected into 4 different sizes. So this must be the size of square chosen by Clark.
An 8×8 square can be dissected into 5 different sets of smaller squares of 4 different sizes, and the smallest of these uses 13 smaller squares.
A minimal dissection is shown below:
1 @ 4×4 square [red]
3 @ 3×3 squares [orange]
4 @ 2×2 squares [green]
5 @ 1×1 squares [blue]
= 13 smaller squares
Had the puzzle allowed Clark to start with a 9×9 square this can also be dissected into 4 different sizes of smaller squares (but not 5), and so this would give a further answer to the puzzle:
A 9×9 square can be dissected into 23 different sets of smaller squares of 4 different size, and the smallest of these uses 15 smaller squares.
The program can be used to investigate extensions to the puzzle for squares up to 12 × 12, after which it gets a bit bogged down.
LikeLike
Using SubstitutedExpression to fit pieces into a grid.
The programs runs in 1.25 seconds (8 or 9 times longer than my similar Python-only program on Brian’s site).
from enigma import SubstitutedExpression
symbols = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
symbols += "ÀÁÂÃÄÅÆÇÈÉÊËÌÍÎÏÐÑÒÓÔÕÖØÙÚÛÜÝÞßàáâãäåæçèéêëìíîïð"
# "these were of several different sizes" (let's say more than three)
min_sizes = 4
# decompose <t> into <k> numbers from <ns> so that sum(<k> numbers) equals <t>
def decompose(t, k=1, ns=[], s=[], mn=min_sizes):
if k == 1:
if t in ns and t >= s[-1]:
s_ = s + [t]
cnts = [s_.count(x) for x in set(s_)]
# there was a different number of squares of each size
if len(cnts) >= mn and len(cnts) == len(set(cnts)):
yield (s_, cnts)
else:
for n in ns:
if k * n > t: break
if s and n < s[-1]: continue # sequence is non-decreasing
yield from decompose(t - n, k - 1, ns, s + [n])
sqs = [i * i for i in range(1, 9)]
# determine sum of <min_sizes> lowest squares
mand = sum(x * x for x in range(1, min_sizes + 1))
max_diff_sizes = 0
sols = []
# process sizes of the large square (at least 5x5)
for sq in sqs[::-1][:-4]:
X = int(sq**.5) # width and height of the large square
sqs_ = [x for x in sqs if x < sq]
max_pieces = sq - mand
# start with a high number of pieces
for np in range(max_pieces - (max_pieces % 2 == 0), 3, -2):
# break if triangular root of <np> get's too low
if int(0.5 * ((8 * np + 1)**.5 - 1.0)) < max_diff_sizes: break
# make total <sq> from small squares
for p, cnts in decompose(sq, np, sqs_):
# ignore entries with too few different sizes
if (ln := len(cnts)) >= max_diff_sizes:
pieces = [int(x**.5) for x in p[::-1]]
topleft = [symbols[2 * i:2 * i + 2] for i in range(np)]
sizes = [symbols[2 * np + i] for i in range(np)]
s2d = dict(zip(sizes, pieces))
answer = ', '.join(str('(({' + x[0] + '}, {' + x[1] + '}), \
{' + sizes[i] + '})') \
for i, x in enumerate(topleft) if s2d[sizes[i]] > 1)
answer = f"{answer}"
# invalid digit / symbol assignments
d2i = {i: set() for i in range(len(pieces))}
for i, p in enumerate(pieces):
# make sure we don't cross the boundaries
for d in range(X - p + 1, 10):
vs = set()
vs.update(topleft[i][0])
vs.update(topleft[i][1])
d2i[d] |= vs
placed = [(topleft[0], sizes[0])]
# build expressions
exprs = []
for i in range(1, np):
piece = symbols[2 * i:2 * i + 2]
sz = sizes[i]
if s2d[sz] == 1: break # pieces of dimensions 1 always fit
for tl, s in placed:
# squares may not overlap
exprs.append(f"({{{tl[0]}}} + {{{s}}} <= {{{piece[0]}}} or "
f"{{{piece[0]}}} <= {{{tl[0]}}} - {{{sz}}}) or "
f"({{{tl[1]}}} + {{{s}}} <= {{{piece[1]}}} or "
f"{{{piece[1]}}} <= {{{tl[1]}}} - {{{sz}}})")
placed.append((piece, sz))
#for e in exprs: print(e);
#print()
# the alphametic puzzle
p = SubstitutedExpression(
exprs,
base=X,
answer=answer,
d2i=d2i,
s2d=s2d,
distinct="",
verbose=0, # use 256 to see the generated code
)
# print answers
for ans in p.answers():
if ln > max_diff_sizes:
sols = []
# store data, count of smallest piece first
sols.append((pieces.count(min(pieces)), np, pieces))
break # we need only one solution
max_diff_sizes = len(cnts)
if len(sols) < 2:
print("no multiple dissections have been found")
else:
# print the solution with the the smallest number of smaller squares
for n_smallest, m, pieces in sorted(sols):
print("answer:", m, "\n")
print("pieces:", *[(x, x) for x in pieces], "\n")
break
LikeLike
@Frits: An inventive use of the [[ SubstitutedExpression ]] solver.
But I think the puzzle is asking for a dissection that uses the minimum number of pieces in total, rather than a dissection that has the minimum number of smallest pieces. (Although it turns out these are the same for the given constraints).
LikeLike
Yes, I got confused with the phrase “smallest number of smaller squares”.
I also have a Python only version that first performs the express calls for all “n” using the Boecker-Liptak Money Changing [https://enigmaticcode.wordpress.com/2020/09/21/enigma-946-patterns-of-fruit/#comment-9773] and then reorders this list on the number of different pieces and number of pieces before packing.
The A1 format (n=23) can be done in 165 seconds:
29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 28 28 28 28 28 28 27 27 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 28 28 28 28 28 28 27 27 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 28 28 28 28 28 28 26 26 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 28 28 28 28 28 28 26 26 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 28 28 28 28 28 28 25 25 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 28 28 28 28 28 28 25 25 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 24 24 24 24 24 23 23 23 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 24 24 24 24 24 23 23 23 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 24 24 24 24 24 23 23 23 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 24 24 24 24 24 22 22 22 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 24 24 24 24 24 22 22 22 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 21 21 21 20 19 22 22 22 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 21 21 21 18 18 18 18 18 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 21 21 21 18 18 18 18 18 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 17 17 17 18 18 18 18 18 16 16 16 16 16 16 15 15 15 15 14 14 14 14 13 17 17 17 18 18 18 18 18 16 16 16 16 16 16 15 15 15 15 14 14 14 14 12 17 17 17 18 18 18 18 18 16 16 16 16 16 16 15 15 15 15 14 14 14 14 11 11 11 11 11 11 10 10 10 16 16 16 16 16 16 15 15 15 15 14 14 14 14 11 11 11 11 11 11 10 10 10 16 16 16 16 16 16 9 9 9 9 8 8 8 8 11 11 11 11 11 11 10 10 10 16 16 16 16 16 16 9 9 9 9 8 8 8 8 11 11 11 11 11 11 7 7 7 6 6 5 5 4 3 9 9 9 9 8 8 8 8 11 11 11 11 11 11 7 7 7 6 6 5 5 2 1 9 9 9 9 8 8 8 8 11 11 11 11 11 11 7 7 7
There are combinations of pieces that are hard to for the pack routine.
LikeLike
From The Sunday Times, 22nd February 1998 [link]
“I’ll be pleased to get rid of her!”, exclaimed George, as he and Martha worked out the seating plan for the wedding of their youngest daughter. The 50 guests were to be seated at seven tables (numbered 1 to 7), each table seating at least six but not more than eight. Alter long arguments as to who should be avoiding whom, they came up with a plan. “That’s strange”, commented Martha. “If you take the number at each table and multiply it by the table number and then add the seven products, you get a perfect square — highly inappropriate when all the tables are round!”. George rang the caterer, who was familiar with the details, and told him about this “square” property as well as the number of people to be seated on table 7. “Then the same number of people will be at table 1″, said the caterer”. “Yes”, confirmed George.
How many were to be seated on table 6?
[teaser1849]
This Python program generates all possible arrangements with the “square” property.
And then looks for those which would allow the caterer to deduce the number of guests at table 1, having been told the number of guests at table 7. We then examine the cases where these numbers are equal.
The program runs in 53ms. (Internal runtime is 1.5ms).
from enigma import (decompose, is_square, filter_unique, item, map2str, printf)
# generate possible configurations with the "square" property
def generate():
# distribute the 50 guests among the 7 tables
for ns in decompose(50, 7, increasing=0, sep=0, min_v=6, max_v=8):
# map table numbers to the number of guests seated
m = dict(enumerate(ns, start=1))
# check the "square" property
if is_square(sum(i * n for (i, n) in m.items())):
yield m
# knowing the number at table 7 the caterer deduces the number at table 1
for m in filter_unique(generate(), item(7), item(1)).unique:
# is it the same number?
if m[1] == m[7]:
# output solution
printf("m[6]={m[6]} [m={s}]", s=map2str(m))
Solution: 6 guests were to be seated at table 6.
There are three possible arrangements (table number = number of guests):
(T1=8, T2=8, T3=6, T4=8, T5=6, T6=6, T7=8)
(T1=8, T2=7, T3=8, T4=7, T5=6, T6=6, T7=8)
(T1=8, T2=8, T3=7, T4=6, T5=7, T6=6, T7=8)
In each case the “square” property gives a value of 196 (= 14²).
LikeLike
Here’s my (brute force) solution:
import itertools
import math
import collections
number_at_table1_per_number_at_table7 = collections.defaultdict(set)
number_at_table6_per_number_at_table7 = collections.defaultdict(set)
for number_at_table in itertools.product((6, 7, 8), repeat=7):
if sum(number_at_table) == 50:
total = sum(i * n for i, n in enumerate(number_at_table, 1))
if math.sqrt(total) % 1 == 0:
number_at_table1_per_number_at_table7[number_at_table[6]].add(number_at_table[0])
number_at_table6_per_number_at_table7[number_at_table[6]].add(number_at_table[5])
for i in number_at_table1_per_number_at_table7:
if len(number_at_table1_per_number_at_table7[i]) == 1: # unique!
print(number_at_table6_per_number_at_table7[i])
LikeLike
Allowing for more than one solution.
sign = lambda x: -1 if x < 0 else x > 0
# return a list of items grouped by element <by>
grpby = lambda s, by: [[x for x in s if x[by] == v]
for v in set(x[by] for x in s)]
# decompose number <t> into <k> numbers from <ns> times -1, 0 or 1 so that
# sum(<k> numbers) equals <t> and with the count of positive numbers
# one higher than the count of negative numbers
def decompose2(t, k, ns, s=[], delta=0):
if k == 1:
if abs(t) in ns or t == 0:
if delta + sign(t) == 1:
yield s + [t]
else:
for m in [-1, 0, 1]:
n_ = m * ns[0]
# can we get to delta = 1 in k - 1 moves
if abs(delta + m - 1) <= k - 1:
yield from decompose2(t - n_, k - 1, ns[1:], s + [n_], delta + m)
# 7 * tri(7) = 14^2 and 14^2 is the only feasible square.
# if we substract 7 from the number of guests per table we have a list of
# -1, 0 and 1. Making sure all these -1/0/1 items sum to zero we end up with
# square 14^2 and having one more postive than negative number guarantees
# 50 people at 7 tables.
# group by table 7
for g in grpby(list(decompose2(0, 7, range(1, 8))), -1):
# group by table 1
if len(g2 := grpby(g, 0)) != 1: continue
print("answer:", ' or '.join(set(str(7 + sign(x[-2])) for x in g2[0])))
LikeLike
% A Solution in MiniZinc include "globals.mzn"; % Guests seated at each of the seven tables var 6..8:T1; var 6..8:T2; var 6..8:T3; var 6..8:T4; var 6..8:T5; var 6..8:T6; var 6..8:T7; % Same number of guests on Tables 1 and 7 constraint T1 == T7; % There are 50 guests seated at the seven tables constraint T1 + T2 + T3 + T4 + T5 + T6 + T7 == 50; constraint T1 + 2*T2 + 3*T3 + 4*T4 + 5*T5 + 6*T6 + 7*T7 == tables_total; % LB and UB of tables total % LB of tables total = 6 * (1+2+3+4+5+6+7) = 6 * 28 = 168 % UB of tables total = 8 * (1+2+3+4+5+6+7) = 8 * 28 = 224 var 168..224:tables_total; % Only squares between 168 and 224 are 13^2 (169) and 14^2 (196) constraint tables_total == 13 * 13 \/ tables_total == 14*14; solve satisfy; output["[T1, T2, T3, T4, T5, T6, T7] = " ++ show( [T1, T2, T3, T4, T5, T6, T7] ) ++ ", Tables total = " ++ show (tables_total )]; % [T1, T2, T3, T4, T5, T6, T7] = [8, 8, 7, 6, 7, 6, 8], Tables total = 196 - Soln 1 % ---------- % [T1, T2, T3, T4, T5, T6, T7] = [7, 8, 8, 6, 8, 6, 7], Tables total = 196 - Soln 2 % ---------- % [T1, T2, T3, T4, T5, T6, T7] = [6, 8, 8, 8, 8, 6, 6], Tables total = 196 - Soln 3 % ---------- % [T1, T2, T3, T4, T5, T6, T7] = [7, 8, 8, 7, 6, 7, 7], Tables total = 196 - Soln 4 % ---------- % ==========
As shown, this program gave four potential solutions, which need some manual filtering, as this facilty does not seem available in MiniZinc.
Of the four solutions output, the 2nd and 4th solutions can be discounted, as they have different values for Table No. 6.
The 1st and 3rd solutions have equal numbers of guests on Tables 1 and 7, albeit different, but the same number of 6 guests on Table 6.
Therefore, number of guests on Table 6 = 6.
LikeLike
S2T2 
Jim Randell 5:21 pm on 6 June 2024 Permalink |
Very straightforward constructive solution.
This Python program runs in 57ms. (Internal runtime is 877µs).
from enigma import (primes, is_npalindrome, subsets, div, printf) # 3-digit palindromic primes scores = list(n for n in primes.between(100, 999) if is_npalindrome(n)) # choose 11 different scores for ss in subsets(scores, size=11): # calculate the mean avg = div(sum(ss), 11) # which is also in scores if avg and avg in scores: # output solution printf("{avg} -> {ss}")Solution: The two highest individual totals are 787 and 919.
The full list of totals is:
LikeLike
Ruud 6:41 pm on 6 June 2024 Permalink |
Very similar to @Jim Randell’s solution, but without enigma:
import sympy from itertools import combinations palindromic_primes_with_length_3 = [] for i in range(1, 1000): prime = sympy.prime(i) prime_as_str = str(prime) if len(prime_as_str) > 3: break if len(prime_as_str) == 3 and str(prime_as_str) == str(prime_as_str)[::-1]: palindromic_primes_with_length_3.append(prime) solutions = set() for scores in combinations(palindromic_primes_with_length_3, 11): average_score = sum(scores) / 11 if average_score in palindromic_primes_with_length_3: solutions.add((scores, int(average_score))) print(solutions)LikeLike
Frits 11:28 am on 7 June 2024 Permalink |
Sympy also has a primerange() method.
LikeLike
GeoffR 8:16 pm on 6 June 2024 Permalink |
% A Solution in MiniZinc include "globals.mzn"; var 100..999:A; var 100..999:B; var 100..999:C; var 100..999:D; var 100..999:E; var 100..999:F; var 100..999:G; var 100..999:H; var 100..999:I; var 100..999:J; var 100..999:K; constraint all_different([A,B,C,D,E,F,G,H,I,J,K]); predicate is_prime(var int: x) = x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) ((i < x) -> (x mod i > 0)); constraint A div 100 == A mod 10 /\ is_prime(A); constraint B div 100 == B mod 10 /\ is_prime(B); constraint C div 100 == C mod 10 /\ is_prime(C); constraint D div 100 == D mod 10 /\ is_prime(D); constraint E div 100 == E mod 10 /\ is_prime(E); constraint F div 100 == F mod 10 /\ is_prime(F); constraint G div 100 == G mod 10 /\ is_prime(G); constraint H div 100 == H mod 10 /\ is_prime(H); constraint I div 100 == I mod 10 /\ is_prime(I); constraint J div 100 == J mod 10 /\ is_prime(J); constraint K div 100 == K mod 10 /\ is_prime(K); var 1000..9999:asum; var 100..999:average; constraint asum == A+B+C+D+E+F+G+H+I+J+K; constraint average == asum div 11 /\ asum mod 11 == 0; constraint is_prime(average); constraint card( {average} intersect {A,B,C,D,E,F,G,H,I,J,K}) == 1; constraint increasing( [A,B,C,D,E,F,G,H,I,J,K]); solve satisfy; output["Scores are " ++ show([A,B,C,D,E,F,G,H,I,J,K]) ++ "\n" ++ "Average = " ++ show(average) ]; % Scores are [101, 131, 151, 181, 191, 313, 353, 373, 383, 787, 919] % Average = 353 % ---------- % ==========LikeLike
GeoffR 9:39 am on 7 June 2024 Permalink |
Shorter code, but still slow.
% A Solution in MiniZinc include "globals.mzn"; % Eleven cricket scores var 100..999:A; var 100..999:B; var 100..999:C; var 100..999:D; var 100..999:E; var 100..999:F; var 100..999:G; var 100..999:H; var 100..999:I; var 100..999:J; var 100..999:K; constraint all_different([A,B,C,D,E,F,G,H,I,J,K]); var 100..999:average; predicate is_pr_pal(var int: x) = x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) ((i < x) -> (x mod i > 0)) /\ x div 100 == x mod 10; constraint sum([is_pr_pal(A), is_pr_pal(B),is_pr_pal(C), is_pr_pal(D), is_pr_pal(E), is_pr_pal(F), is_pr_pal(G), is_pr_pal(H), is_pr_pal(I), is_pr_pal(J), is_pr_pal(K)]) == 11; constraint average == (A+B+C+D+E+F+G+H+I+J+K) div 11 /\ (A+B+C+D+E+F+G+H+I+J+K) mod 11 == 0; constraint is_pr_pal(average); constraint card( {average} intersect {A,B,C,D,E,F,G,H,I,J,K}) == 1; constraint increasing( [A,B,C,D,E,F,G,H,I,J,K]); solve satisfy; output["Scores are " ++ show([A,B,C,D,E,F,G,H,I,J,K]) ++ "\n" ++ "Average = " ++ show(average) ];LikeLike
GeoffR 9:57 pm on 6 June 2024 Permalink |
from enigma import is_prime from itertools import combinations scores = [x for x in range(100,999) if is_prime(x) \ if x // 100 == x % 10 ] for s in combinations(scores, 11): av, r = divmod(sum(s), 11) if r != 0: continue if av in scores and av //100 == av % 10: print(f"Average = {av}") print(f"Scores = {s}")LikeLike
Ruud 10:20 am on 7 June 2024 Permalink |
You can leave out the av // 100 == av % 10 test in the final if condition, as that’d guaranteed by the membership of scores.
LikeLike
Frits 10:17 am on 7 June 2024 Permalink |
Same number of iteratons. It also works if scores would have had exactly 11 items.
from itertools import combinations # prime numbers from 101-999 P = [3, 5, 7] P += [x for x in range(11, 100, 2) if all(x % p for p in P)] P = [x for x in range(101, 1000, 2) if all(x % p for p in P)] # 3-digit palindromic primes scores = {p for p in P if p // 100 == p % 10} assert (ln := len(scores)) >= 11 t = sum(scores) # choose scores outside the 11 for ss in combinations(scores, ln - 11): # calculate the average avg, r = divmod(t - sum(ss), 11) # which is also in scores if r or avg not in scores: continue print("answer", sorted(scores.difference(ss))[-2:])LikeLike