Teaser 3222: Squarism
From The Sunday Times, 23rd June 2024 [link] [link]
There are 84 marbles, numbered sequentially from 1, in a bag. Oliver (going first) and Pam take turns, each removing two marbles from the bag. The player finds the “most square” integer factorisation of each number. The difference between the two factors for each number is then added to the player’s score (e.g. removing marbles 1 and 84 scores 5 points since 1 = 1 × 1 and 84 = 7 × 12), and the game ends when all marbles are removed.
After each of the first four turns (two each), both players’ expected final score was a whole number. For example, if there were 90 points remaining, with 4 turns left for Oliver and 5 for Pam, Oliver would expect to score another 40 points. In addition, each player’s score for their second turn was the same as their first. Also, Pamela scored the lowest possible game total.
What was Oliver’s expected final score after Pamela’s second turn?
[teaser3222]
Frits and 
S2T2 
Jim Randell 5:27 pm on 21 June 2024 Permalink |
This Python program looks for possible repeated scores for O and P that could happen in the first 4 turns, that give the required whole number expectations, to give candidate solutions.
Once candidates are found (there are only two) it then attempts to choose marble values for the turns that give the required score, and any non-viable candidates (one of them) are eliminated.
It runs in 71ms. (Internal runtime is 656µs).
from enigma import (irange, isqrt, div, ediv, group, subsets, disjoint_cproduct, disjoint_union, printf) # calculate the score for a marble def score(n): for a in irange(isqrt(n), 1, step=-1): b = div(n, a) if b is not None: return abs(a - b) # group the marbles by score g = group(irange(1, 84), by=score) # calculate total number of points tot = sum(k * len(vs) for (k, vs) in g.items()) # find possible scores available to O and P (keysO, keysP) = (list(), list()) t = 0 for k in sorted(g.keys()): n = len(g[k]) t += n if not (t < 42): keysO.append(k) if not (t > n + 42): keysP.append(k) # construct example scores for O and P def choose(OPs, i=0, ss=list(), used=set()): # are we done? if not OPs: yield ss else: # choose values for the next score s = OPs[0] for vs in subsets([keysO, keysP][i], size=2, select='R'): if not (sum(vs) == s): continue # choose marbles for xs in disjoint_cproduct(g[v] for v in vs): used_ = disjoint_union([used, xs]) if used_ is not None: yield from choose(OPs[1:], 1 - i, ss + [xs], used_) # possible scores for O and P scoresO = set(sum(ks) for ks in subsets(keysO, size=2, select='R')) scoresP = set(sum(ks) for ks in subsets(keysP, size=2, select='R')) # check expected remaining points def check_exp(r, *fs): try: return list(ediv(r * a, b) for (a, b) in fs) except ValueError: return None # consider scores for O's first 2 turns for sO in scoresO: # expected remaining points after turn 1 (41 remaining turns) if not check_exp(tot - sO, (20, 41), (21, 41)): continue # consider scores for P's first 2 turns for sP in scoresP: # expected remaining points after turn 2 (40 remaining turns) if not check_exp(tot - (sO + sP), (20, 40)): continue # expected remaining points after turn 3 (39 remaining turns) if not check_exp(tot - (sO + sP + sO), (19, 39), (20, 39)): continue # expected remaining points after turn 4 (38 remaining turns) es = check_exp(tot - (sO + sP + sO + sP), (19, 38)) if not es: continue # check scores can be made twice if not any(choose([sO, sP] * 2)): continue # output solution candidate printf("expected total scores: O={tO} P={tP} [sO={sO} sP={sP}]", tO=sO + sO + es[0], tP=sP + sP + es[0])Solution: Oliver’s expected final score after Pam takes her second turn is 685.
There are only two candidate turn scores that give the required whole number expectations:
and:
However a score of 134 can only be made by choosing marbles 53 (score = 52) and 83 (score = 82), so this cannot be repeated in the third turn. Hence the second candidate solution is eliminated.
But there are many ways to make the scores for the first candidate solution, for example:
In fact, when the game ends, P has scored the lowest possible total, which is 92 points, and so O has scored the remaining 1190 points.
LikeLike
Jim Randell 12:59 pm on 22 June 2024 Permalink |
We can simplify this approach by just keeping a multiset (or bag(!)) of the possible scores, and then we don’t need to worry about the actual marbles chosen at all.
Run: [ @replit ]
from enigma import (irange, isqrt, div, ediv, group, multiset, first, subsets, cproduct, call, printf) # calculate the score for a marble def score(n): for a in irange(isqrt(n), 1, step=-1): b = div(n, a) if b is not None: return abs(a - b) # make a multiset of scores scores = multiset.from_seq(score(x) for x in irange(1, 84)) # calculate total number of points tot = scores.sum() # scores for P and O (P has the lowest 42) scoresP = multiset.from_seq(first(scores.sorted(), 42)) scoresO = scores.difference(scoresP) # possible total scores for O and P in a turn turnsO = group(scoresO.subsets(size=2), by=sum) turnsP = group(scoresP.subsets(size=2), by=sum) # check expected remaining points def check_exp(r, *fs): try: return list(ediv(r * a, b) for (a, b) in fs) except ValueError: return None # check scores can be made twice def check_scores(sO, sP): for (ssO, ssP) in cproduct(subsets(xs, size=2, select='R') for xs in [turnsO[sO], turnsP[sP]]): if call(multiset.from_dict, ssO + ssP).issubset(scores): return True # consider scores for O's first 2 turns for sO in turnsO: # expected remaining points after turn 1 (41 remaining turns) if not check_exp(tot - sO, (20, 41), (21, 41)): continue # consider scores for P's first 2 turns for sP in turnsP: # expected remaining points after turn 2 (40 remaining turns) if not check_exp(tot - (sO + sP), (20, 40)): continue # expected remaining points after turn 3 (39 remaining turns) if not check_exp(tot - (sO + sP + sO), (19, 39), (20, 39)): continue # expected remaining points after turn 4 (38 remaining turns) es = check_exp(tot - (sO + sP + sO + sP), (19, 38)) if not es: continue # check the turn scores can be made twice if not check_scores(sO, sP): continue # output solution candidate printf("expected total scores: O={tO} P={tP} [sO={sO} sP={sP}]", tO=sO + sO + es[0], tP=sP + sP + es[0])LikeLike
Frits 11:35 am on 23 June 2024 Permalink |
Just for fun:
g = {i: set() for i in range(84)} for a in range(1, 85): for b in range(a, 0, -1): if a * b > 84 or any(a * b in g[i] for i in range(a - b)): continue g[a - b].add(a * b) g = {k: vs for k, vs in g.items() if vs} # remove empty items@Jim, you don’t use the “ss” list so you could just yield True “if not OPs”.
LikeLike
Frits 8:40 pm on 21 June 2024 Permalink |
There must be a smarter way of getting this solution.
The program runs in 350ms (PyPy).
from enigma import divisor_pairs from itertools import combinations # determine differences for "most square" integer factorisation seq = [sorted(b - a for a, b in divisor_pairs(i))[0] for i in range(1, 85)] # total of all scores T = sum(seq) P, O = [], [] # determine the lowest scores for Pam for i, s, in enumerate(sorted(seq), 1): if i <= 42: P.append(s) else: O.append(s) sols = set() # first turn for Oliver for o12 in combinations(O, 2): # 20/41 * remaining is a whole number if (T - (sum_o12 := o12[0] + o12[1])) % 41: continue # first turn for Pam for p12 in combinations(P, 2): # 20/40 * remaining is a whole number if (T - (sum_p12 := p12[0] + p12[1]) - sum_o12) % 2: continue O_ = O.copy() for o in o12: O_.remove(o) # second turn for Oliver for o34 in combinations(O_, 2): # 19/39 * remaining is a whole number if (T - (sum_o34 := o34[0] + o34[1]) - sum_o12 - sum_p12) % 39: continue # score for their second turn was the same as their first if sum_o34 != sum_o12: continue P_ = P.copy() for p in p12: P_.remove(p) for p34 in combinations(P_, 2): remaining = (T - (sum_p34 := p34[0] + p34[1]) - sum_o12 - sum_p12 - sum_o34) # 19/38 * remaining is a whole number # score for their second turn was the same as their first if remaining % 2 or sum_p34 != sum_p12: continue # Oliver's expected final score after Pamela’s second turn sols.add(str(sum_o12 + sum_o34 + remaining // 2)) print("answer:", ' or '.join(sols))LikeLike
Frits 2:16 pm on 22 June 2024 Permalink |
An easy performance improvement is to use keep2() in the combinations() lines.
# keep only a maximum of 2 occurences of a sequence item keep2 = lambda seq: [b for a in [[x] * min(2, seq.count(x)) for x in sorted(set(seq))] for b in a]LikeLike
Frits 7:19 am on 24 June 2024 Permalink |
from itertools import combinations seq = [] for n in range(1, 85): # find the two factors nearest to a square for a in range(int(n**.5), 0, -1): b, r = divmod(n, a) if r: continue seq.append(b - a) break seq.sort() T = sum(seq) # total of all scores assert T % 2 == 0 # whole number expected score after 4th turn P, O = seq[:42], seq[42:] # points for Pam and Oliver # sum of points of 2 marbles for Oliver that guarantees divisibility by 41 o_sums = [sm for i in range(5) if sum(O[:2]) <= (sm := (T % 41) + 41 * i) <= sum(O[-2:])] # indices of 2 marbles for Oliver that guarantees divisibility by 41 o_pairs = {sm: [(i1, i1 + i2 + 1) for i1, m1 in enumerate(O[:-1]) for i2, m2 in enumerate(O[i1 + 1:]) if m1 + m2 == sm] for sm in o_sums} # reduce items if possible o_pairs = {k: vs for k, vs in o_pairs.items() if len(vs) > 1} o_sums = [sm for sm in o_sums if sm in o_pairs] # valid Oliver/Pam points that also guarantees divisibility by 39 # after the third turn and divisibility by 2 after the second turn op_pts = [(o_pts, p_pts) for o_pts in o_sums if (T - o_pts - (p_pts := (T - 2 * o_pts) % 39)) % 2 == 0] sols = set() # can solutions be formed by picking 4 different marbles per person for o, p in op_pts: # pick 4 marbles for Oliver if not any(len(set(a + b)) == 4 for a, b in combinations(o_pairs[o], 2)): continue # indices of 2 marbles for Pam p_pairs = [(i1, i1 + i2 + 1) for i1, m1 in enumerate(P[:-1]) for i2, m2 in enumerate(P[i1 + 1:]) if m1 + m2 == p] # pick 4 marbles for Pam if not any(len(set(a + b)) == 4 for a, b in combinations(p_pairs, 2)): continue # store Oliver's expected final score after Pamela's second turn sols.add(str(T // 2 + o - p)) print("answer:", ' or '.join(sols))LikeLike