Teaser 3036: That old chestnut
From The Sunday Times, 29th November 2020 [link]
Clearing out an old drawer I found a wrinkled conker. It was my magnificent old 6709-er, a title earned by being the only survivor of a competition that I had had with friends. The competition had started with five conkers, veterans of many campaigns; each had begun at a different value between 1300 and 1400.
We used the rule that if an m-er beat an n-er in an encounter (by destroying it, of course!) the m-er would become an m+n+1-er; in effect, at any time the value of a conker was the number of destroyed conkers in all confrontations in its “ancestry”.
I recall that at the beginning of, and throughout, the competition, the value of every surviving conker was a prime number.
What were the values of the five conkers at the start?
[teaser3036]
Frits are discussing. 
S2T2 
Jim Randell 2:10 pm on 27 November 2020 Permalink |
There are 5 conkers (with values, say A, B, C, D, E), and there are 4 matches where one conker is destroyed in each match. The ultimate winner ending up with a value of (A + B + C + D + E + 4), and we know this value is 6079.
This Python 3 program runs in 49ms.
from enigma import Primes, subsets, printf # target for the champion T = 6709 # for checking primes primes = Primes(T) # play values against each other until there is an ultimate winner def solve(vs, ss=[]): # are we done? if len(vs) == 1: yield ss # choose 2 conkers to play for ((i, m), (j, n)) in subsets(enumerate(vs), size=2): v = m + n + 1 if v in primes: yield from solve(vs[:i] + vs[i + 1:j] + vs[j + 1:] + [v], ss + [(m, n)]) # choose 5 initial primes values between 1300 and 1400 for vs in subsets(primes.irange(1300, 1400), size=5): if sum(vs) + 4 != T: continue # check for a possible sequence of matches for ss in solve(list(vs)): # output solution printf("{vs} -> {ss}") break # we only need one possibilitySolution: The values of the five starting conkers were: 1301, 1303, 1361, 1367, 1373.
The conkers are:
And one possible sequence of matches is:
An alternative sequence is:
Note that by selecting pairs of conkers for battle by index (rather than value) we ensure that the program works even if more than one conker has the same value. It turns out that in the solution sequence all the conkers do have different values, so it is possible to get the correct answer with a less rigorous program.
LikeLike
Jim Randell 12:49 pm on 14 December 2020 Permalink |
Here’s a solution using [[
multiset()]] from the enigma.py library, which is a bit neater than using indices (and also more efficient).This Python 3 program runs in 44ms.
from enigma import Primes, subsets, multiset, ordered, printf # target for the champion T = 6709 # for checking primes primes = Primes(T) # play values against each other until there is an ultimate winner def solve(vs, ss=[]): # are we done? if len(vs) == 1: yield ss # choose 2 conkers to play for (m, n) in subsets(vs, size=2, select="mC"): v = m + n + 1 if v in primes: yield from solve(vs.difference((m, n)).add(v), ss + [ordered(m, n)]) # choose 5 initial primes values between 1300 and 1400 for vs in subsets(primes.irange(1300, 1400), size=5): if sum(vs) + 4 != T: continue # check for a possible sequence of matches for ss in solve(multiset(vs)): # output solution printf("{vs} -> {ss}") break # we only need one possibilityLikeLike
Frits 5:58 pm on 28 November 2020 Permalink |
2 encounters are enough to filter out a unique solution (we have been told there is a solution).
Coding more encounters would have resulted in an even more messy code.
from enigma import SubstitutedExpression, is_prime # the alphametic puzzle p = SubstitutedExpression( [ # 5 increasing prime numbers between 1300 and 1400 "is_prime(1300 + AB)", "CD > AB", "is_prime(1300 + CD)", "EF > CD", "is_prime(1300 + EF)", "GH > EF", "is_prime(1300 + GH)", "IJ > GH", "is_prime(1300 + IJ)", # winner has value of (A + B + C + D + E + 4), has to be 6709. "AB + CD + EF + GH + IJ == 205", # 1st encounter "is_prime(2601 + V*AB + W*CD + X*EF + Y*GH + Z*IJ)", # 1st encounter : pick 2 "V + W + X + Y + Z == 2", # 2nd encounter "is_prime(1301 + \ (1 - P)*1300 + P*(2601 + V*AB + W*CD + X*EF + Y*GH + Z*IJ) + \ Q*(1-V)*AB + R*(1-W)*CD + S*(1-X)*EF + T*(1-Y)*GH + U*(1-Z)*IJ)", # 2nd encounter: pick exactly 2 "P + Q*(1-V) + R*(1-W) + S*(1-X) + T*(1-Y) + U*(1-Z) == 2", # limit number of same solutions "Q * V == 0", # force Q to be 0 if V equals 1 "R * W == 0", # force R to be 0 if W equals 1 "S * X == 0", # force S to be 0 if X equals 1 "T * Y == 0", # force T to be 0 if Y equals 1 "U * Z == 0", # force U to be 0 if Z equals 1 ], answer="AB, CD, EF, GH, IJ, 2601 + V*AB + W*CD + X*EF + Y*GH + Z*IJ, \ 1301 + (1 - P)*1300 + P*(2601 + V*AB + W*CD + X*EF + Y*GH + Z*IJ) + \ Q*(1-V)*AB + R*(1-W)*CD + S*(1-X)*EF + T*(1-Y)*GH + U*(1-Z)*IJ, \ P,Q,R,S,T,U,V,W,X,Y,Z", d2i={k:"PQRSTUVWXYZ" for (k) in range(2,10)}, distinct="", verbose=0) # Print answers prev = "" print(" I II III IV V e1 e2 " "P, Q, R, S, T, U, V, W, X, Y, Z]") for (_, ans) in p.solve(): if ans[:5] != prev: print([x if i > 4 else x + 1300 for (i, x) in enumerate(ans)]) prev = ans[:5]LikeLike