Teaser 3219: Number funnel
From The Sunday Times, 2nd June 2024 [link] [link]
Betty, being a keen mathematician, has devised a game to improve her children’s maths additions. She constructed an inverted triangular tiling of hexagonal shapes, with nine hexagons in the top row, eight in the second row etc., reducing to one at the bottom. Then, completing the top row with 0s and 1s, she asks them to complete each row below by adding in each hexagon shape the numbers in the two hexagons immediately above it.
In the last game she noticed that if the top row is considered as a base-2 [binary] number, then this is exactly four and a half times the bottom total.
What is the bottom total?
[teaser3219]
GeoffR, 
Hugo, 
S2T2 
Jim Randell 4:50 pm on 31 May 2024 Permalink |
If we suppose that the top row must have at least one of each binary digit present, then a single answer is found.
This Python program runs in 64ms. (Internal runtime is 986µs).
Run: [ @replit ]
from enigma import (irange, tuples, repeat, nsplit, ediv, peek, printf) # process a row process = lambda ns: list(x + y for (x, y) in tuples(ns, 2)) # consider possible start row values (must be a multiple of 9) for n in irange(0, 511, step=9): # this is 4.5 times the target t = ediv(n * 2, 9) # perform the process top = nsplit(n, 9, base=2) bot = peek(repeat(process, top, 8), 8) if bot == [t]: # output solution printf("{n} -> {t}; {top} -> {bot}")Solution: The final total is 102.
The initial row is the binary representation of 4.5 × 102 = 459, which gives the following rows:
LikeLike
Ruud 7:56 pm on 31 May 2024 Permalink |
This my version
from istr import istr for s9 in istr.concat(istr.product((0, 1), repeat=9)): as_binary = int(s9, 2) if as_binary % 4.5 == 0: target = int(as_binary / 4.5) s = s9[:] while len(s) > 1: s = [i + j for i, j in zip(s, s[1:])] if s[0] == target: print(f'from {s9} to {target}')LikeLike
NigelR 11:11 am on 1 June 2024 Permalink |
No external dependencies and a recursive approach for the shapes. I started at the high end for the top row and worked down as it might have been faster if I’d stopped once a valid solution was found. As it is, it makes no difference but it confirms a unique solution.
#return bottom row from top row r def blox(r): #are we at the bottom row? if len(r)==1: return r #find the next row down else: return blox(nxt(r)) #return next row down from list of current row nxt = lambda r: [(r[i]+r[i+1]) for i in range(0,len(r)-1)] #top row must be less than 512 and divisible by 9 for top in range (504,0,-9): r1 = [int(y) for y in format(top,'09b')] #have we found a solution? if (bot:=blox(r1)[0])*9/2 == top: print(f"top row was {top}, bottom row was {bot}")LikeLike
Jim Randell 4:51 pm on 1 June 2024 Permalink |
Here is a solution based on a bit of analysis:
We have:
And we can write each of these in terms of the 0,1 values in the top row.
So we can extract the coefficients of these top row values in the equation:
Some of them are positive, and some of them are negative. (And it turns out there are 2 negative values and 7 positive values).
So we assign 0,1 values to the variables in the top row with negative coefficients (there are only 3 interesting cases), and then try to express the resulting value using the 0,1 quantities of the positive values.
We can address this manually, or programatically.
The following program has an internal runtime of 250µs, so it is slightly faster (although more complicated) than just applying the procedure to each of the possible top row values:
Run: [ @replit ]
from enigma import (irange, nCr, subsets, dot, express, nconcat, printf) # we have: 9 * (final value) = 2 * (binary representation) # calculate coefficients in the final value (= pascal_row(8)) pascal_row = lambda n: tuple(nCr(n, r) for r in irange(0, n)) pr8 = pascal_row(8) lhs = tuple(9 * x for x in pr8) # calculate coefficients in the binary representation rhs = tuple(2**n for n in irange(9, 1, step=-1)) # calculate coefficients in <lhs> - <rhs> = 0 cs = tuple(a - b for (a, b) in zip(lhs, rhs)) # collect indices for positive and negative values jps = sorted((j for (j, x) in enumerate(cs) if x > 0), key=cs.__getitem__) jns = list(j for (j, x) in enumerate(cs) if x < 0) # things we could work around, but don't need to assert not (len(jns) > len(jps)) assert len(jps) + len(jns) == len(cs) assert len(set(cs[j] for j in jps)) == len(jps) # the positive and negative values ps = list(cs[j] for j in jps) ns = list(cs[j] for j in jns) # choose 0,1 values for the negative values for vs in subsets((0, 1), size=len(jns), select='M'): # calculate total for the negative values t = -dot(vs, ns) # express the same total using the positive values for qs in express(t, ps, qs=[0, 1]): # construct top row top = [None] * 9 for (j, v) in zip(jns, vs): top[j] = v for (j, v) in zip(jps, qs): top[j] = v # output solution n = nconcat(top, base=2) bot = dot(top, pr8) printf("{top} {n} -> {bot}")Manually:
We are looking to solve:
The coefficients are all different, so we can uniquely identify a 0,1 valued variable with the corresponding coefficient.
This boils down to choosing two subsets such that:
There is a trivial solution where an empty set is chosen on both sides.
Otherwise we have:
The final case corresponds to: a = 1, b = 1, c = 1, d = 0, e = 0, f = 1, g = 0, h = 1, i = 1.
And so the top row is (1, 1, 1, 0, 0, 1, 0, 1, 1) and the bottom row is (102).
LikeLike
Frits 5:42 pm on 2 June 2024 Permalink |
I needed to print the variables to see understand the method.
I had forgotten that “dot” stands for “vector product”.
Thanks for the “key=cs.__getitem__” construct. I didn’t know that.
LikeLike
Jim Randell 10:27 am on 3 June 2024 Permalink |
@Frits:
dicthas theget()function which makes the equivalent look neater for dictionaries:Or I suppose you could use [[
key=(lambda i: seq[i])]] for sequences.LikeLike
Frits 11:19 pm on 2 June 2024 Permalink |
@Jim, is there a reason why express() doesn’t support negative quantities? The code would have been more compact.
LikeLike
Jim Randell 8:02 am on 3 June 2024 Permalink |
@Frits: Allowing negative quantities should be possible, but in general there is no guarantee of termination if non-positive denominations are used in [[
express()]].It feels like solving an integer equation where the variables take on (0, 1) values could have a specialised solver (I think an ILP solver would work). But I used [[
express()]] in this instance to save having to write one.LikeLike
Frits 12:38 pm on 3 June 2024 Permalink |
A minimal modification to Enigma’s express_quantities() is sufficient to make this program work (assuming the denominations are ordered). I don’t see how this subroutine can keep running without terminating.
from enigma import (irange, nCr, dot, nconcat, printf) # express total <t> using denominations <ds>, quantities chosen from <qs> def express_quantities(t, ds, qs, ss=[]): if any(x for x in ss) and t == 0: if not ds: yield ss elif 0 in qs: yield ss + [0] * len(ds) elif ds: d = ds[0] for q in qs: if d * q > t: break for r in express_quantities(t - d * q, ds[1:], qs, ss + [q]): yield r # we have: 9 * (final value) = 2 * (binary representation) # calculate coefficients in the final value (= pascal_row(8)) pascal_row = lambda n: tuple(nCr(n, r) for r in irange(0, n)) pr8 = pascal_row(8) lhs = tuple(9 * x for x in pr8) # calculate coefficients in the binary representation rhs = tuple(2**n for n in irange(9, 1, step=-1)) # calculate coefficients in <lhs> - <rhs> = 0 cs = tuple(a - b for (a, b) in zip(lhs, rhs)) # express the same total using the positive values for top in express_quantities(0, cs, qs=[0, 1]): # construct top row # output solution n = nconcat(top, base=2) bot = dot(top, pr8) printf("{top} {n} -> {bot}")LikeLike
Jim Randell 11:20 am on 4 June 2024 Permalink |
@Frits: But you asked about
express()notexpress_quantities().Think about expressing a value using denominations of (-1, 0, +1) where you can use as many of each as you like.
Of course with finite sets of denominations and quantities there is only a finite number of possible arrangements.
LikeLike
Jim Randell 3:27 pm on 4 June 2024 Permalink |
Or, using a single call to
express():from enigma import (irange, nCr, express, nconcat, dot, printf) # solve the binary equation: sum(n[i] * x[i]) = 0, for x[i] in [0, 1] # return the sequences of binary x[] values def solve(ns): # collect the coefficients (all different absolute values) m = dict() # value -> index ts = set() # set of negative values for (i, n) in enumerate(ns): assert n != 0 # coefficients must be non-zero k = abs(n) if n < 0: ts.add(k) m[k] = i ds = sorted(m.keys()) assert len(ds) == len(ns) # coefficients must all be different # express the sum of the negative values using 0,1 quantities for qs in express(sum(ts), ds, qs=[0, 1]): # return the values in the required order xs = [None] * len(ns) for (d, q) in zip(ds, qs): xs[m[d]] = (1 - q if d in ts else q) yield xs # calculate coefficients for the final value (= pascal_row(8)) pascal_row = lambda n: tuple(nCr(n, r) for r in irange(0, n)) pr8 = pascal_row(8) lhs = tuple(9 * x for x in pr8) # calculate coefficients in the binary representation rhs = tuple(2**n for n in irange(9, 1, step=-1)) # calculate coefficients in <lhs> - <rhs> = 0 ns = tuple(a - b for (a, b) in zip(lhs, rhs)) # solve the 0,1-equation with coefficients <ns> to give the top row for top in solve(ns): # output solution n = nconcat(top, base=2) bot = dot(pr8, top) printf("{top} {n} -> {bot}")LikeLike
Hugo 2:12 pm on 9 June 2024 Permalink |
If the numbers in the top row are a, b, c, d, e, f, g, h, i,
then the value at the bottom has coefficients as given by the appropriate row of Pascal’s triangle: a + 8b + 28c + 56d + 70e + 56f + 28g + 8h + i.
An exhaustive search is still needed, but my program (in Basic) found a solution immediately.
This puzzle opens up the possibility of a whole family of puzzles, with factors other than 4.5. There could also be a different number of digits in the top row.
Where do Jim’s negative values come from? The top row contains only 0s and 1s; each subsequent row is formed by addition, never subtraction.
A further puzzle for me is Frits’ mention of dot for a vector product.
I don’t speak Python, but normally dot is for a scalar product and cross for a vector product.
LikeLike
Hugo 8:48 am on 10 June 2024 Permalink |
I see now what Jim was doing: equating nine times the value of the bottom number and twice the value of the binary number, 256a + 128b + 64c + 32d + 16e + 8f + 4g + 2h + i.
The mental leap was too much for me! I had evaluated them separately.
LikeLike
GeoffR 3:16 pm on 12 June 2024 Permalink |
LikeLike
GeoffR 4:15 pm on 14 June 2024 Permalink |
I tried this teaser with ChatGPT trying to find a solution. Despite several hints, it failed, as we have experienced previously.
I have been experimenting using AI to write poetry in recent months, so I tried a poem for this teaser by feeding the teaser description as a prompt for the poem for ChatGPT. to generate a poem.
It worked well – poem below:
The Hexagon Puzzle – ST 3219
=====================
A Poem by ChatGPT
In Betty’s realm, where numbers dance,
A game of wit and math’s advance,
Hexagons align in rows so neat,
A challenge for young minds to meet.
From nine at the top, they descend,
Each row a puzzle to comprehend,
Zeros and ones adorn the crest,
A binary code, a numeric test.
With eager eyes, her children trace,
The patterns woven in this maze,
Adding the pairs above with care,
Unveiling sums, a secret to share.
And as they reach the final row,
A revelation starts to glow,
The top row’s binary, a key so bright,
Unlocks the bottom’s total, a wondrous sight.
Four and a half times, the answer lies,
A mathematical truth that never dies,
In Betty’s game, where numbers reign,
Hexagons persist, and minds retain.
LikeLike