From The Sunday Times, 15th March 1981 [link]
Young Mary, who is good at manipulating figures, was playing with her standard set of dominoes and seeing what numerical structures she could form with them, treating each half-domino as a digit according to its number of spots (“blank” being 0).
Starting with double-6/double-5/double-4 laid end-to-end in a row, she built forwards and downwards from that beginning, placing dominoes across and apparently at random, until she had completed a solid rectangle by slotting into the only remaining gaps, in its farther half, her last two dominoes which were 4-&-blank and 2-&-blank.
Whereupon she called out to me: “Uncle, do come and look! I’ve managed to arrange all my dominoes in a rectangle so that the numbers formed by the four halves in each column are all dissimilar 4-digit squares”.
“Are you quite sure about that?” I temporised.
“Certain,” she replied. “And they’re pretty well in correct order of magnitude too!”.
When I protested that this was quite impossible with dominoes, she said reproachfully: “But Uncle, I never said that ALL the squares appear in the right order, did I? Actually there are just two of them — both among the seven smallest present — which do not; but every single square except those two is definitely just where it would be if all those appearing were strictly in order of magnitude”.
She was perfectly correct. And you don’t need dominoes to figure out …
Which four of Mary’s together formed columns 7 and 8 of her rectangle? (Use figures, e.g. 4-0 = four-&-blank).
This was the final puzzle to use the title Brain-Teaser. The next puzzle was Brain teaser 974.
[teaser973]
Frits are discussing. 
Tony Brooke-Taylor, and 
Pete Good, and 
GeoffR are discussing. 
Mark Valentine are discussing. 
S2T2 
Jim Randell 10:44 am on 4 July 2023 Permalink |
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:
There are 500 different difference values.
The smallest difference is 9 (which happens 322560 times):
And the largest difference is 104691357 (which happens 2 times):
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:
and this has one fewer element than the original sequence.
And the sum of this sequence is simply:
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:
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:
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:
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 |
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 |
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 |
We can reduce the size of the prefix considered at line 14:
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