Compfiles/Usa2026P2.lean
Explanation legend Lean4 Domain Explanation Language (L4DEL)
L4DEL explanations are a separate layer. They do not change the Lean source. Intuition is explanatory prose; numbered items are a reading path; sources link the wording back to evidence.
- L4DEL
- Lean4 Domain Explanation Language
Credit: The upstream authors and contributors retain credit for the project and mathematics. lean4-explainer only renders their pinned source and adds the separately disclosed explanation layer.
Project sources: Pinned compfiles documentation, Pinned compfiles corpus index
27 declarations, 0 contain sorry, 0 declared as axioms
USA Mathematical Olympiad 2026, Problem 2
Annie is playing a game where she starts with a row of positive integers, written on a blackboard, each of which is a power of 2. On each turn, she can erase two adjacent numbers and replace them with a power of 2 that is greater than either of the erased numbers. This shortens the row of numbers, and she continues to take turns until only one number remains. Annie wins the game if the final remaining number is less than 4 times the sum of the original numbers. Is it always possible for Annie to win, regardless of the starting row of numbers?
Imports (5)
Imported by 1 file
- def
Usa2026P2.IsPow2A positive integer which is a power of two (in particular1 = 2 ^ 0counts) line 34 sourceSource documentation
A positive integer which is a power of two (in particular
1 = 2 ^ 0counts).standard axioms: propext what this means
Statement uses:
NatProof uses:
Exists,Eq,HPow.hPow,OfNat.ofNat5 instances, coercions and auxiliary constants left out.
def IsPow2 (x : ℕ) : Prop := ∃ k, x = 2 ^ k
- inductive
Usa2026P2.MoveOne legal turn of the game: the two adjacent entriesxandyare erased and replaced by a power of twozwhich is strictly larger than both of them line 38 sourceSource documentation
One legal turn of the game: the two adjacent entries
xandyare erased and replaced by a power of twozwhich is strictly larger than both of them.standard axioms: propext what this means
Statement uses:
List,Natinductive Move : List ℕ → List ℕ → Prop | mk (l r : List ℕ) (x y z : ℕ) (hz : IsPow2 z) (hx : x < z) (hy : y < z) : Move (l ++ x :: y :: r) (l ++ z :: r) snip begin /-! ### Proof sketch (following Evan Chen's USAMO 2026 solution notes, <https://web.evanchen.cc/exams/USAMO-2026-notes.pdf>)Mentions: Usa2026P2.IsPow2, solution
- def
Usa2026P2.innerSumForl = [b₁, ..., bₘ],innerSum lis `4 * b₁ + 4 * b₂ + line 70 sourceSource documentation
For
l = [b₁, ..., bₘ],innerSum lis4 * b₁ + 4 * b₂ + ... + 4 * b_{m-1} + 2 * bₘ(and0for the empty list): the "tail" ofSafter the first entry.no axioms what this means
Statement uses:
List,Nat2 instances, coercions and auxiliary constants left out.
def innerSum : List ℕ → ℕ | [] => 0 | [x] => 2 * x | x :: y :: rest => 4 * x + innerSum (y :: rest) /-- The target bound for a row `a = [a₁, ..., aₙ]`: `a₁` if `n = 1`, and `2 * a₁ + 4 * a₂ + ... + 4 * a_{n-1} + 2 * aₙ` if `n ≥ 2` (and `0` if `n = 0`). -/ - def
Usa2026P2.SThe target bound for a rowa = [a₁, ..., aₙ]:a₁ifn = 1, and `2 * a₁ + 4 * a₂ + line 77 sourceSource documentation
The target bound for a row
a = [a₁, ..., aₙ]:a₁ifn = 1, and2 * a₁ + 4 * a₂ + ... + 4 * a_{n-1} + 2 * aₙifn ≥ 2(and0ifn = 0).no axioms what this means
Statement uses:
List,NatProof uses:
Usa2026P2.innerSum.match_1,Unit,OfNat.ofNat,HAdd.hAdd,HMul.hMul, Usa2026P2.innerSum,List.cons5 instances, coercions and auxiliary constants left out.
def S : List ℕ → ℕ | [] => 0 | [x] => x | x :: y :: rest => 2 * x + innerSum (y :: rest)
Mentions: Usa2026P2.innerSum
- theorem
Usa2026P2.innerSum_nilline 82 sourceno axioms what this means
Statement uses:
Eq,Nat, Usa2026P2.innerSum,List.nil,OfNat.ofNatProof uses:
rfl1 instances, coercions and auxiliary constants left out.
- theorem
Usa2026P2.innerSum_singletonline 83 sourceno axioms what this means
Statement uses:
Nat,Eq, Usa2026P2.innerSum,List.cons,List.nil,HMul.hMul,OfNat.ofNatProof uses:
rfl3 instances, coercions and auxiliary constants left out.
- theorem
Usa2026P2.innerSum_cons_consline 84 sourceno axioms what this means
Statement uses:
Nat,List,Eq, Usa2026P2.innerSum,List.cons,HAdd.hAdd,HMul.hMul,OfNat.ofNatProof uses:
rfl5 instances, coercions and auxiliary constants left out.
- theorem
Usa2026P2.S_nilline 87 sourceno axioms what this means
Statement uses:
Eq,Nat, Usa2026P2.S,List.nil,OfNat.ofNatProof uses:
rfl1 instances, coercions and auxiliary constants left out.
- theorem
Usa2026P2.S_singletonline 88 sourceno axioms what this means
Statement uses:
Nat,Eq, Usa2026P2.S,List.cons,List.nilProof uses:
rfl - theorem
Usa2026P2.S_cons_consline 89 sourceno axioms what this means
Statement uses:
Nat,List,Eq, Usa2026P2.S,List.cons,HAdd.hAdd,HMul.hMul,OfNat.ofNat, Usa2026P2.innerSumProof uses:
rfl5 instances, coercions and auxiliary constants left out.
- theorem
Usa2026P2.innerSum_le_four_mul_sumline 92 sourcestandard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
List,Nat,LE.le, Usa2026P2.innerSum,HMul.hMul,OfNat.ofNat,List.sum16 instances, coercions and auxiliary constants left out.
Tactic trace: 6 steps
Open to load the checked before-and-after goal states.
- theorem
Usa2026P2.S_lt_four_mul_sumThe boundS ais always less than four times the sum of the row line 101 sourceSource documentation
The bound
S ais always less than four times the sum of the row.standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
List,Nat,Ne,List.nil,Membership.mem,LT.lt,OfNat.ofNat, Usa2026P2.S,HMul.hMul,List.sumProof uses:
False.elim,rfl,List.cons,List.mem_singleton_self,Eq.mpr,id,Eq,congrArg,List.sum_singleton,HAdd.hAdd,List.mem_cons_self,LE.le, Usa2026P2.innerSum, Usa2026P2.innerSum_le_four_mul_sum23 instances, coercions and auxiliary constants left out.
Tactic trace: 7 steps
Open to load the checked before-and-after goal states.
theorem S_lt_four_mul_sum : ∀ (a : List ℕ), a ≠ [] → (∀ x ∈ a, 0 < x) → S a < 4 * a.sum | [], h, _ => (h rfl).elim | [x], _, h => by have hx : 0 < x := h x (List.mem_singleton_self x) …Mentions: Usa2026P2.S, h
- theorem
Usa2026P2.two_mul_last_le_innerSumThe last entry of a nonempty row, doubled, is at mostinnerSumof the row line 114 sourceSource documentation
The last entry of a nonempty row, doubled, is at most
innerSumof the row.standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
List,Nat,LE.le,HMul.hMul,OfNat.ofNat, Usa2026P2.innerSum,HAppend.hAppend,List.cons,List.nil14 instances, coercions and auxiliary constants left out.
Tactic trace: 5 steps
Open to load the checked before-and-after goal states.
theorem two_mul_last_le_innerSum : ∀ (q : List ℕ) (y : ℕ), 2 * y ≤ innerSum (q ++ [y]) | [], y => le_refl _ | [x], y => by simp only [List.singleton_append, innerSum_cons_cons, innerSum_singleton] lia | x :: z :: q', y => by have ih := two_mul_last_le_innerSum (z :: q') y …Mentions: Usa2026P2.innerSum, Usa2026P2.innerSum_cons_cons, Usa2026P2.innerSum_singleton
- theorem
Usa2026P2.two_mul_getLast_le_SThe last entry of a row with at least two entries, doubled, is at mostSof the row line 127 sourceSource documentation
The last entry of a row with at least two entries, doubled, is at most
Sof the row.standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
List,Nat,LE.le,OfNat.ofNat,List.length,Ne,List.nil,HMul.hMul,List.getLast, Usa2026P2.SProof uses:
Exists,Eq,List.cons,List.exists_cons_of_ne_nil,False,False.elim,Eq.mp,Eq.trans,congrArg,zero_add,Eq.symm,Eq.mpr,HAdd.hAdd, Usa2026P2.innerSum,id, Usa2026P2.S_cons_cons,List.cons_ne_nil,rfl,HAppend.hAppend,List.dropLastand 2 more28 instances, coercions and auxiliary constants left out.
Tactic trace: 11 steps
Open to load the checked before-and-after goal states.
theorem two_mul_getLast_le_S (a : List ℕ) (ha : 2 ≤ a.length) (h : a ≠ []) : 2 * a.getLast h ≤ S a := by …Mentions: h, Usa2026P2.S
- theorem
Usa2026P2.innerSum_consExpandinginnerSumat the head of a nonempty tail: the head entry is counted with coefficient4ininnerSumbut with coefficient2inSline 143 sourceSource documentation
Expanding
innerSumat the head of a nonempty tail: the head entry is counted with coefficient4ininnerSumbut with coefficient2inS.standard axioms: propext what this means
Statement uses:
Nat,List,Ne,List.nil,Eq, Usa2026P2.innerSum,List.cons,HAdd.hAdd, Usa2026P2.S,HMul.hMul,OfNat.ofNatProof uses:
Exists,List.exists_cons_of_ne_nil,id,Mathlib.Tactic.Ring.of_eq,HPow.hPow,Nat.rawCast,Mathlib.Tactic.Ring.Common.add_congr,Mathlib.Tactic.Ring.Common.mul_congr,Mathlib.Tactic.Ring.cast_pos,Mathlib.Meta.NormNum.isNat_ofNat,Eq.refl,Mathlib.Tactic.Ring.Common.atom_pf,rfl,Eq.mpr,congrArg,Eq.symm,Mathlib.Tactic.Ring.Common.add_mul,Mathlib.Tactic.Ring.Common.mul_add,Mathlib.Tactic.Ring.Common.mul_pf_right,Mathlib.Meta.NormNum.IsNat.to_raw_eqand 10 more28 instances, coercions and auxiliary constants left out.
Tactic trace: 3 steps
Open to load the checked before-and-after goal states.
theorem innerSum_cons (y : ℕ) (m : List ℕ) (hm : m ≠ []) : innerSum (y :: m) = S (y :: m) + 2 * y := by …Mentions: Usa2026P2.innerSum, Usa2026P2.S
- theorem
Usa2026P2.S_cons_cons_appendExpandingSat the two leftmost entries of a row line 150 sourceSource documentation
Expanding
Sat the two leftmost entries of a row.standard axioms: propext what this means
Statement uses:
Nat,List,Ne,HAppend.hAppend,List.nil,Eq, Usa2026P2.S,List.cons,HAdd.hAdd,HMul.hMul,OfNat.ofNatProof uses:
Eq.mpr,id,congrArg,rfl, Usa2026P2.innerSum, Usa2026P2.S_cons_cons, Usa2026P2.innerSum_cons,Eq.refl14 instances, coercions and auxiliary constants left out.
Tactic trace: 1 steps
Open to load the checked before-and-after goal states.
theorem S_cons_cons_append (p₁ p₂ : ℕ) (p'' l : List ℕ) (h : p'' ++ l ≠ []) : S ((p₁ :: p₂ :: p'') ++ l) = 2 * p₁ + (S ((p₂ :: p'') ++ l) + 2 * p₂) := by …Mentions: h, Usa2026P2.S
- theorem
Usa2026P2.S_appendDocumented declaration: S_append line 158 sourceSource documentation
The overlap identity: if a row is decomposed as
p ++ x :: qwith bothpandqnonempty (soxis a middle entry, counted with coefficient4), then itsS-value is the sum of theS-values of the overlapping partsp ++ [x]andx :: q.standard axioms: propext what this means
Statement uses:
List,Nat,Ne,List.nil,Eq, Usa2026P2.S,HAppend.hAppend,List.cons,HAdd.hAdd10 instances, coercions and auxiliary constants left out.
Tactic trace: 10 steps
Open to load the checked before-and-after goal states.
theorem S_append : ∀ (p q : List ℕ) (x : ℕ), p ≠ [] → q ≠ [] → S (p ++ x :: q) = S (p ++ [x]) + S (x :: q) | [], _, _, h, _ => (h rfl).elim | [p₁], q, x, _, hq => by obtain ⟨q₁, q', rfl⟩ := List.exists_cons_of_ne_nil hq …Mentions: Usa2026P2.S, h
- theorem
Usa2026P2.exists_splitThe key combinatorial step: any row with at least two entries can be cut into a nonempty prefix and a nonempty suffix whoseS-values are both at mostS a / 2line 174 sourceSource documentation
The key combinatorial step: any row with at least two entries can be cut into a nonempty prefix and a nonempty suffix whose
S-values are both at mostS a / 2.standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
List,Nat,LE.le,OfNat.ofNat,List.length,Exists,And,LT.lt,HMul.hMul, Usa2026P2.S,List.take,List.dropProof uses:
Ne,List.nil,Eq,False,False.elim,Eq.mp,Eq.trans,Eq.symm,List.cons,List.exists_cons_of_ne_nil,congrArg,zero_add,rfl,Eq.mpr,id, Usa2026P2.S_singleton,HAdd.hAdd, Usa2026P2.innerSum, Usa2026P2.S_cons_cons,Nat.le_add_rightand 27 more52 instances, coercions and auxiliary constants left out.
Tactic trace: 41 steps
Open to load the checked before-and-after goal states.
theorem exists_split (a : List ℕ) (ha : 2 ≤ a.length) : ∃ k, 1 ≤ k ∧ k < a.length ∧ 2 * S (a.take k) ≤ S a ∧ 2 * S (a.drop k) ≤ S a := by …Mentions: Usa2026P2.S
- inductive
Usa2026P2.ReducesReduces a mmeans that the rowacan be reduced to the single numbermby a sequence of legal moves line 226 sourceSource documentation
Reduces a mmeans that the rowacan be reduced to the single numbermby a sequence of legal moves. A derivation is a full binary tree whose leaves are the entries ofaand whose internal nodes are powers of two larger than their children; conversely any play of the game produces such a tree (the last move combines the reductions of two complementary blocks), soReduces a mholds exactly when Annie can achieve the final numberm.standard axioms: propext what this means
Statement uses:
List,Natinductive Reduces : List ℕ → ℕ → Prop | base (x : ℕ) : Reduces [x] x | append (u v : List ℕ) (x y z : ℕ) (hu : Reduces u x) (hv : Reduces v y) (hz : IsPow2 z) (hx : x < z) (hy : y < z) : Reduces (u ++ v) z /-- A number reachable from a row of powers of two is again a power of two. -/Mentions: base, Usa2026P2.IsPow2
- theorem
Usa2026P2.reduces_isPow2A number reachable from a row of powers of two is again a power of two line 232 sourceSource documentation
A number reachable from a row of powers of two is again a power of two.
standard axioms: propext what this means
Statement uses:
List,Nat, Usa2026P2.Reduces,Membership.mem, Usa2026P2.IsPow2Proof uses:
Usa2026P2.Reduces.rec,List.cons,List.nil,List.mem_singleton_self,LT.lt,HAppend.hAppend5 instances, coercions and auxiliary constants left out.
Tactic trace: 3 steps
Open to load the checked before-and-after goal states.
theorem reduces_isPow2 {l : List ℕ} {m : ℕ} (h : Reduces l m) (hp : ∀ x ∈ l, IsPow2 x) : IsPow2 m := by …Mentions: h, Usa2026P2.Reduces, Usa2026P2.IsPow2
- theorem
Usa2026P2.exists_reduces_leThe main induction: every nonempty row of powers of two can be reduced to a single number which is at mostSof the row line 240 sourceSource documentation
The main induction: every nonempty row of powers of two can be reduced to a single number which is at most
Sof the row.standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Nat,List,Eq,List.length,Ne,List.nil,Membership.mem, Usa2026P2.IsPow2,Exists,And, Usa2026P2.Reduces,LE.le, Usa2026P2.SProof uses:
Nat.strong_induction_on,LT.lt,False.elim,rfl,List.cons,Exists.intro,And.intro,Usa2026P2.Reduces.base,le_of_eq,Eq.symm, Usa2026P2.S_singleton,OfNat.ofNat,of_eq_true,HAdd.hAdd,Eq.trans,True,Function.swap,HMul.hMul,List.take,List.dropand 60 more97 instances, coercions and auxiliary constants left out.
Tactic trace: 68 steps
Open to load the checked before-and-after goal states.
theorem exists_reduces_le : ∀ n : ℕ, ∀ a : List ℕ, a.length = n → a ≠ [] → (∀ x ∈ a, IsPow2 x) → ∃ m, Reduces a m ∧ m ≤ S a := by …Mentions: Usa2026P2.IsPow2, Usa2026P2.Reduces, Usa2026P2.S
- theorem
Usa2026P2.Move.append_rightMoves can also be performed with an additional row appended on the right line 293 sourceSource documentation
Moves can also be performed with an additional row appended on the right.
standard axioms: propext what this means
Statement uses:
List,Nat, Usa2026P2.Move,HAppend.hAppendProof uses:
Eq,HEq, Usa2026P2.IsPow2,LT.lt,List.cons,Usa2026P2.Move.mk,Eq.mpr,id,congrArg,of_eq_true,Eq.trans,True,congrFun',List.append_assoc,eq_self,Eq.symm,Eq.refl,HEq.refl7 instances, coercions and auxiliary constants left out.
Tactic trace: 5 steps
Open to load the checked before-and-after goal states.
theorem Move.append_right {a b : List ℕ} (h : Move a b) (r : List ℕ) : Move (a ++ r) (b ++ r) := by …Mentions: h, Usa2026P2.Move
- theorem
Usa2026P2.Move.append_leftMoves can also be performed with an additional row appended on the left line 301 sourceSource documentation
Moves can also be performed with an additional row appended on the left.
standard axioms: propext what this means
Statement uses:
List,Nat, Usa2026P2.Move,HAppend.hAppendProof uses:
Eq,HEq, Usa2026P2.IsPow2,LT.lt,List.cons,Usa2026P2.Move.mk,Eq.mpr,id,congrArg,of_eq_true,Eq.trans,True,List.append_assoc,eq_self,Eq.symm,Eq.refl,HEq.refl7 instances, coercions and auxiliary constants left out.
Tactic trace: 5 steps
Open to load the checked before-and-after goal states.
theorem Move.append_left (l : List ℕ) {a b : List ℕ} (h : Move a b) : Move (l ++ a) (l ++ b) := by …Mentions: h, Usa2026P2.Move
- theorem
Usa2026P2.reflTransGen_mapPushing a chain of moves through a context map line 309 sourceSource documentation
Pushing a chain of moves through a context map.
standard axioms: propext what this means
Statement uses:
List,Nat, Usa2026P2.Move,Relation.ReflTransGenProof uses:
Relation.ReflTransGen.rec,Relation.ReflTransGen.refl,Relation.ReflTransGen.trans,Relation.ReflTransGen.singleTactic trace: 3 steps
Open to load the checked before-and-after goal states.
theorem reflTransGen_map (f : List ℕ → List ℕ) (hf : ∀ {s t : List ℕ}, Move s t → Move (f s) (f t)) {a b : List ℕ} (h : Relation.ReflTransGen Move a b) : Relation.ReflTransGen Move (f a) (f b) := by …Mentions: f, Usa2026P2.Move, h
- theorem
Usa2026P2.reduces_movesAReducesderivation yields an actual sequence of legal moves: reduce the left block, then the right block, then combine the two remaining adjacent numbers line 318 sourceSource documentation
A
Reducesderivation yields an actual sequence of legal moves: reduce the left block, then the right block, then combine the two remaining adjacent numbers.standard axioms: propext what this means
Statement uses:
List,Nat, Usa2026P2.Reduces,Relation.ReflTransGen, Usa2026P2.Move,List.cons,List.nilProof uses:
Usa2026P2.Reduces.rec,Relation.ReflTransGen.refl, Usa2026P2.IsPow2,LT.lt,HAppend.hAppend, Usa2026P2.reflTransGen_map, Usa2026P2.Move.append_right, Usa2026P2.Move.append_left,Relation.ReflTransGen.single,Usa2026P2.Move.mk,Relation.ReflTransGen.trans3 instances, coercions and auxiliary constants left out.
Tactic trace: 6 steps
Open to load the checked before-and-after goal states.
theorem reduces_moves {a : List ℕ} {m : ℕ} (h : Reduces a m) : Relation.ReflTransGen Move a [m] := by …Mentions: h, Usa2026P2.Reduces, Usa2026P2.Move
- theorem
Usa2026P2.IsPow2.posPowers of two are positive line 332 sourceSource documentation
Powers of two are positive.
standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Nat, Usa2026P2.IsPow2,LT.lt,OfNat.ofNatProof uses:
Eq,HPow.hPow,pow_pos,Mathlib.Meta.Positivity.pos_of_isNat,Mathlib.Meta.NormNum.isNat_ofNat,Eq.refl,Bool,Nat.ble,Eq.symm19 instances, coercions and auxiliary constants left out.
Tactic trace: 2 steps
Open to load the checked before-and-after goal states.
theorem IsPow2.pos {x : ℕ} (h : IsPow2 x) : 0 < x := by …Mentions: h, Usa2026P2.IsPow2
- problem
Usa2026P2.usa2026_p2The answer is yes: from any starting row of powers of two, Annie can always reach a single number which is less than four times the sum of the starting row line 340 sourceSource documentation
The answer is yes: from any starting row of powers of two, Annie can always reach a single number which is less than four times the sum of the starting row.
standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
List,Nat,Ne,List.nil,Membership.mem, Usa2026P2.IsPow2,Exists,And,Relation.ReflTransGen, Usa2026P2.Move,List.cons,LT.lt,HMul.hMul,OfNat.ofNat,List.sumProof uses: Usa2026P2.Reduces,
LE.le, Usa2026P2.S, Usa2026P2.exists_reduces_le,List.length,rfl, Usa2026P2.IsPow2.pos,Exists.intro,And.intro, Usa2026P2.reduces_moves,lt_of_le_of_lt, Usa2026P2.S_lt_four_mul_sum20 instances, coercions and auxiliary constants left out.
Tactic trace: 3 steps
Open to load the checked before-and-after goal states.
problem usa2026_p2 (a : List ℕ) (ha : a ≠ []) (hp : ∀ x ∈ a, IsPow2 x) : ∃ m, Relation.ReflTransGen Move a [m] ∧ m < 4 * a.sum := by …Mentions: Usa2026P2.IsPow2, Usa2026P2.Move