Teaser 2795: No mean feat
From The Sunday Times, 17th April 2016 [link] [link]
I bought a run of consecutively-numbered raffle tickets, some of which were red and the rest were blue. Amongst my numbers no red number was the average of two other reds, and no blue number was the average of two other blues. I actually won the raffle. My two-figure winning red number was in fact the geometric mean of two other red numbers of mine. [The geometric mean of M and N is the square root of (M×N)].
What were my blue numbers?
[teaser2795]
GeoffR and 
Jim Olson are discussing. 
Tony Brooke-Taylor, 
Frits, and 
John Crabtree are discussing. 
Brian Gladman, 
Hugh Casement, 
S2T2 
Jim Randell 9:23 am on 17 June 2021 Permalink |
The winning ticket w is the geometric mean of two of the other tickets, say a and b:
So, the range of tickets must include the interval [a, …, b]. And if this interval can be successfully coloured (with a, w, b red) then we have a solution.
This Python program runs in 530ms.
Run: [ @replit ]
from enigma import (irange, divisors_pairs, empty, peek, filter2, mod, subsets, diff, printf) # check no number in <ns> is the mean of two other numbers in <ns> def check(ns): for ps in filter2(mod(2), ns): if any((x + y) // 2 in ns for (x, y) in subsets(ps, 2)): return False return True # colour tickets in <ts> to give reds <rs> and blues <bs> def colour(ts, rs, bs): if not ts: yield (rs, bs) else: (t, ts_) = (ts[0], ts[1:]) # try red rs_ = rs.union([t]) if check(rs_): yield from colour(ts_, rs_, bs) # try blue bs_ = bs.union([t]) if check(bs_): yield from colour(ts_, rs, bs_) # consider possible 2-digit winning tickets for w in irange(10, 99): # consider possible other ticket whose geometric mean is w for (a, b) in divisors_pairs(w, 2): if not (a < b): break # can we colour the tickets? rs = {a, w, b} if not check(rs): continue ts = diff(irange(a, b), rs) try: (reds, blues) = peek(colour(ts, rs, empty)) except ValueError: continue printf("red = {reds}, blue = {blues} [w={w}; a={a} b={b}]", reds=sorted(reds), blues=sorted(blues))Solution: The blue tickets were numbered: 10, 11, 14, 15.
And the red tickets were: 9, 12, 13, 16.
i.e. the sequence is: (R9, B10, B11, R12, R13, B14, B15, R16).
The winning ticket is 12, which is the geometric mean of 9 and 16.
And we can check that the sequence cannot be extended (with 8 or 17):
For a faster execution time we can note that if we have a sequence of numbers such that no number is the mean of any other two.
Then the sequence:
also has this property.
So if we find a pattern of red/blue colourings of consecutive numbers, we can also form another valid pattern by adding a constant to each of the numbers (or by swapping the colours).
The following program finds all possible patterns (of length 4 or more):
from enigma import printf # generate colourings, with at least k elements def patterns(s, n, choice=(0, 1)): j = len(s) if not (j < n): yield s for x in choice: for (i, y) in enumerate(s): if y == x: (d, r) = divmod(i + j, 2) if r == 0 and s[d] == x: break else: yield from patterns(s + [x], n, choice) # output patterns for ps in patterns([0], 4): printf("{ps}")And we could modify the original program to check that the sequence of tickets matches one of these patterns, although we can cut the run time of the program down to 51ms by simply rejecting sequences that are longer than the maximum pattern length (which is 8).
Replacing line 26 with the following does the trick:
There are 3 viable patterns of length 8, which we can identify with the following sequences:
Giving a total of 6 possible red/blue colourings.
The solution sequence (R9, B10, B11, R12, R13, B14, B15, R16) matches the last of these patterns.
LikeLike
Jim Randell 9:26 am on 17 June 2021 Permalink |
The following approach is based on an observation by Brian Gladman [link].
Suppose the winning number (at index w in the sequence), is between the numbers at indices a and b that are the components of the geometric mean.
Then the sequence is:
So, given the values of the indices within the sequence a, w, b we can calculate the starting value of the sequence.
The following Python program generates possible patterns, and then looks for indices that produce a viable value for n. The values of the blue tickets can then be determined.
It runs in 48ms (but the internal runtime is only 243µs compared to 1.26ms for my previous program (with modification)).
from enigma import (irange, subsets, div, group, printf) # generate colourings, with at least k elements def patterns(s, n, choice=(0, 1)): j = len(s) if not (j < n): yield s for x in choice: for (i, y) in enumerate(s): if y == x: (d, r) = divmod(i + j, 2) if r == 0 and s[d] == x: break else: yield from patterns(s + [x], n, choice) # collect patterns by length pats = group(patterns([0], 4), by=len) m = max(pats.keys()) # consider values for a, w, b for (a, w, b) in subsets(irange(0, m - 1), size=3): # calculate n n = div(w * w - a * b, a + b - 2 * w) if n is None or n + w < 10 or n + w > 99: continue # look for patterns with length at least b + 1 for (k, vs) in pats.items(): if not (k > b): continue for ps in vs: # look for patterns where a, w, b are red red = ps[a] if not (red == ps[w] == ps[b]): continue # output solution blues = sorted(n + j for (j, x) in enumerate(ps) if x != red) printf("blues = {blues} [ps={ps} n={n} red={red} w={w}]")It turns out there is only one possible value for (a, w, b) = (0, 3, 7), which gives n = 9.
So the sequence is maximal, and of the three candidates only (0, 1, 1, 0, 0, 1, 1, 0) has elements 0, 3, 7 the same. They are all 0, so the 1’s indicate the blue tickets.
LikeLike