Compfiles/Imo2026P1.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
22 declarations, 0 contain sorry, 0 declared as axioms
International Mathematical Olympiad 2026, Problem 1
There are 2026 integers greater than 1 written on a blackboard, not necessarily different. In a move, Confucius chooses two integers m > 1 and n > 1 from different places on the blackboard and replaces these two integers with gcd(m, n) and lcm(m, n) / gcd(m, n). He continues to make moves while it is possible to do so.
(a) Prove that, regardless of the choices of Confucius, after finitely many moves, exactly one integer M on the blackboard is greater than 1.
(b) Prove that the value of M does not depend on the choices of Confucius.
(Note that gcd(x, y) denotes the greatest common divisor of positive integers x and y, and lcm(x, y) denotes the least common multiple of x and y.)
Statement formalization adapted from AxiomMath/IMO2026; proof adapted from Humanfia's Kimi-K3 solutions (https://github.com/humanfia/imo2026).
Imports (6)
Imported by 1 file
- abbrev
Imo2026P1.BoardA board is a finite multiset of natural numbers line 49 sourceSource documentation
A board is a finite multiset of natural numbers. The full board discipline (entries
≥ 1, cardinality2026) is captured by the predicateIsInitial.no axioms what this means
Proof uses:
Multiset,Natabbrev Board := Multiset ℕ
- def
Imo2026P1.IsInitialAn initial board: exactly2026entries, each strictly greater than1line 52 sourceSource documentation
An initial board: exactly
2026entries, each strictly greater than1.standard axioms: propext what this means
Statement uses: Imo2026P1.Board
Proof uses:
And,Eq,Nat,Multiset.card,OfNat.ofNat,Membership.mem,LT.lt3 instances, coercions and auxiliary constants left out.
def IsInitial (B : Board) : Prop := …
Mentions: Imo2026P1.Board
- def
Imo2026P1.MoveDocumented declaration: Move line 60 sourceSource documentation
A single move: pick two entries
m, n(from two distinct positions, modelled as two separate elements of the multiset) both> 1, remove them and insertgcd(m, n)andlcm(m, n) / gcd(m, n). Usingm ::ₘ n ::ₘ sfor the source board automatically encodes that the two chosen positions are distinct (they are two separate multiset elements, whose values may coincide).standard axioms: Quot.sound what this means
Statement uses: Imo2026P1.Board
Proof uses:
Exists,Nat,And,LT.lt,OfNat.ofNat,Eq,Multiset.cons,Nat.gcd,HDiv.hDiv,Nat.lcm4 instances, coercions and auxiliary constants left out.
def Move (B B' : Board) : Prop := …
Mentions: Imo2026P1.Board
- def
Imo2026P1.IsTerminalA board is terminal when at most one entry is> 1, so no move is possible line 66 sourceSource documentation
A board is terminal when at most one entry is
> 1, so no move is possible.standard axioms: Quot.sound, propext what this means
Statement uses: Imo2026P1.Board
Proof uses:
LE.le,Nat,Multiset.card,Multiset.filter,LT.lt,OfNat.ofNat4 instances, coercions and auxiliary constants left out.
def IsTerminal (B : Board) : Prop := …
Mentions: Imo2026P1.Board
- def
Imo2026P1.HasUniqueLargeA board has a unique large entry when exactly one entry is> 1line 70 sourceSource documentation
A board has a unique large entry when exactly one entry is
> 1.standard axioms: Quot.sound, propext what this means
Statement uses: Imo2026P1.Board
Proof uses:
Eq,Nat,Multiset.card,Multiset.filter,LT.lt,OfNat.ofNat3 instances, coercions and auxiliary constants left out.
def HasUniqueLarge (B : Board) : Prop := …
Mentions: Imo2026P1.Board
- def
Imo2026P1.ReachableReachable B B':B'can be obtained fromBby a finite sequence of moves (the reflexive–transitive closure ofMove) line 76 sourceSource documentation
Reachable B B':B'can be obtained fromBby a finite sequence of moves (the reflexive–transitive closure ofMove). A finite play fromBto a terminal boardB'is precisely a witness ofReachable B B'withIsTerminal B'.standard axioms: Quot.sound what this means
Statement uses: Imo2026P1.Board
Proof uses:
Relation.ReflTransGen, Imo2026P1.Movedef Reachable (B B' : Board) : Prop := Relation.ReflTransGen Move B B' …
Mentions: Imo2026P1.Board, Imo2026P1.Move
- def
Imo2026P1.gExpThe exponentg_pfor a primepand boardB: thegcdof thep-adic valuations of the entries ofBline 84 sourceSource documentation
The exponent
g_pfor a primepand boardB: thegcdof thep-adic valuations of the entries ofB. Sincegcd(a, 0) = a, valuations equal to0(entries not divisible byp) do not affect this gcd, sogExp p Bis the gcd of the positivep-adic valuations occurring inB.standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Nat, Imo2026P1.BoardProof uses:
Multiset.gcd,Multiset.map,padicValNat3 instances, coercions and auxiliary constants left out.
noncomputable def gExp (p : ℕ) (B : Board) : ℕ := …
Mentions: Imo2026P1.Board
- def
Imo2026P1.MvalThe claimed invariant terminal valueM = ∏_{p ∣ ∏ B} p ^ gExp p B, the product over all primes dividing some entry ofBofpraised to the gcd of thep-adic valuations line 90 sourceSource documentation
The claimed invariant terminal value
M = ∏_{p ∣ ∏ B} p ^ gExp p B, the product over all primes dividing some entry ofBofpraised to the gcd of thep-adic valuations.standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: Imo2026P1.Board,
NatProof uses:
Finset.prod,Nat.primeFactors,Multiset.prod,HPow.hPow, Imo2026P1.gExp5 instances, coercions and auxiliary constants left out.
noncomputable def Mval (B : Board) : ℕ := …
Mentions: Imo2026P1.Board
- lemma
Imo2026P1.move_ge_oneMoves preserve the property that all entries are≥ 1line 115 sourceSource documentation
Moves preserve the property that all entries are
≥ 1.standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: Imo2026P1.Board, Imo2026P1.Move,
Nat,Membership.mem,LE.le,OfNat.ofNatProof uses:
Exists,And,LT.lt,Eq,Multiset.cons,Nat.gcd,HDiv.hDiv,Nat.lcm,Ne,Multiset,Or,Eq.mp,congrArg,propext,Multiset.mem_cons,Iff.mpr,Nat.one_le_iff_ne_zero,And.left,Nat.gcd_eq_zero_iff,Eq.symmand 11 more30 instances, coercions and auxiliary constants left out.
Tactic trace: 26 steps
Open to load the checked before-and-after goal states.
lemma move_ge_one {B B' : Board} (hmove : Move B B') (hB : ∀ a ∈ B, 1 ≤ a) : ∀ a ∈ B', 1 ≤ a := by …Mentions: Imo2026P1.Board, Imo2026P1.Move
- lemma
Imo2026P1.ge_one_reachableReachable boards have all entries≥ 1, provided the start board does line 142 sourceSource documentation
Reachable boards have all entries
≥ 1, provided the start board does.standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: Imo2026P1.Board,
Nat,Membership.mem,LE.le,OfNat.ofNat, Imo2026P1.ReachableProof uses:
Relation.ReflTransGen.rec, Imo2026P1.Move,Relation.ReflTransGen, Imo2026P1.move_ge_one6 instances, coercions and auxiliary constants left out.
Tactic trace: 3 steps
Open to load the checked before-and-after goal states.
lemma ge_one_reachable {B₀ B : Board} (hge : ∀ a ∈ B₀, 1 ≤ a) (hreach : Reachable B₀ B) : ∀ a ∈ B, 1 ≤ a := by …Mentions: Imo2026P1.Board, Imo2026P1.Reachable
- lemma
Imo2026P1.large_count_pos_of_moveA move always produces at least one entry> 1line 149 sourceSource documentation
A move always produces at least one entry
> 1.standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: Imo2026P1.Board, Imo2026P1.Move,
LE.le,Nat,OfNat.ofNat,Multiset.card,Multiset.filter,LT.ltProof uses:
Exists,And,Eq,Multiset.cons,Nat.gcd,HDiv.hDiv,Nat.lcm,Ne,Membership.mem,Multiset,Multiset.notMem_zero,Eq.mp,congrArg,Iff.mpr,Nat.one_le_iff_ne_zero,Iff.mp,Multiset.card_eq_zero,dite,Multiset.mem_filter,And.introand 14 more23 instances, coercions and auxiliary constants left out.
Tactic trace: 24 steps
Open to load the checked before-and-after goal states.
lemma large_count_pos_of_move {B B' : Board} (hmove : Move B B') : 1 ≤ (B'.filter fun a => 1 < a).card := by …Mentions: Imo2026P1.Board, Imo2026P1.Move
- lemma
Imo2026P1.large_count_pos_of_reachableReachable boards have at least one entry> 1, provided the start board does line 177 sourceSource documentation
Reachable boards have at least one entry
> 1, provided the start board does.standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: Imo2026P1.Board,
LE.le,Nat,OfNat.ofNat,Multiset.card,Multiset.filter,LT.lt, Imo2026P1.ReachableProof uses:
Relation.ReflTransGen.rec, Imo2026P1.Move,Relation.ReflTransGen, Imo2026P1.large_count_pos_of_move8 instances, coercions and auxiliary constants left out.
Tactic trace: 3 steps
Open to load the checked before-and-after goal states.
lemma large_count_pos_of_reachable {B₀ B : Board} (h : 1 ≤ (B₀.filter fun a => 1 < a).card) (hreach : Reachable B₀ B) : 1 ≤ (B.filter fun a => 1 < a).card := by …Mentions: Imo2026P1.Board, h, Imo2026P1.Reachable
- lemma
Imo2026P1.gcd_min_sub_maxgcd(min a b, max a b - min a b) = gcd(a, b)line 185 sourceSource documentation
gcd(min a b, max a b - min a b) = gcd(a, b).standard axioms: Quot.sound, propext what this means
Statement uses:
Nat,Eq,Nat.gcd,Min.min,HSub.hSub,Max.maxProof uses:
LE.le,Or,le_total,Eq.mpr,id,congrArg,min_eq_left,max_eq_right,Nat.gcd_comm,Nat.gcd_sub_self_left,Eq.refl,min_eq_right,max_eq_left15 instances, coercions and auxiliary constants left out.
Tactic trace: 5 steps
Open to load the checked before-and-after goal states.
lemma gcd_min_sub_max (a b : ℕ) : Nat.gcd (min a b) (max a b - min a b) = Nat.gcd a b := by …
- lemma
Imo2026P1.gExp_moveFor a primep, the quantitygExp pis preserved by a move line 191 sourceSource documentation
For a prime
p, the quantitygExp pis preserved by a move.standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Nat,LT.lt,OfNat.ofNat, Imo2026P1.Board,Nat.Prime,Eq, Imo2026P1.gExp,Multiset.cons,Nat.gcd,HDiv.hDiv,Nat.lcmProof uses:
Fact,Fact.mk,Ne,And.left,Eq.mp,And,congrArg,propext,Nat.gcd_eq_zero_iff,HMul.hMul,Nat.gcd_mul_lcm,mul_ne_zero,Eq.symm,MulZeroClass.mul_zero,LE.le,Nat.le_of_dvd,Nat.pos_of_ne_zero,Dvd.dvd.trans,Nat.gcd_dvd_left,Nat.dvd_lcm_leftand 29 more48 instances, coercions and auxiliary constants left out.
Tactic trace: 29 steps
Open to load the checked before-and-after goal states.
lemma gExp_move {m n : ℕ} (hm : 1 < m) (hn : 1 < n) (s : Board) {p : ℕ} (hp : p.Prime) : gExp p (Nat.gcd m n ::ₘ (Nat.lcm m n / Nat.gcd m n) ::ₘ s) = gExp p (m ::ₘ n ::ₘ s) := by …Mentions: Imo2026P1.Board, Imo2026P1.gExp
- lemma
Imo2026P1.Mval_moveMvalis invariant under a move, for boards whose remaining entries are≥ 1line 233 sourceSource documentation
Mvalis invariant under a move, for boards whose remaining entries are≥ 1.standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses:
Nat,LT.lt,OfNat.ofNat, Imo2026P1.Board,Membership.mem,LE.le,Eq, Imo2026P1.Mval,Multiset.cons,Nat.gcd,HDiv.hDiv,Nat.lcmProof uses:
Ne,Multiset.prod,Eq.mp,Multiset,congrArg,propext,Multiset.prod_eq_zero_iff,HMul.hMul,Nat.gcd_mul_lcm,mul_ne_zero,Eq.symm,MulZeroClass.mul_zero,Nat.mul_div_cancel',Dvd.dvd.trans,Nat.gcd_dvd_left,Nat.dvd_lcm_left,Eq.mpr,id,Multiset.prod_cons,mul_assocand 18 more63 instances, coercions and auxiliary constants left out.
Tactic trace: 28 steps
Open to load the checked before-and-after goal states.
lemma Mval_move {m n : ℕ} (hm : 1 < m) (hn : 1 < n) (s : Board) (hs : ∀ a ∈ s, 1 ≤ a) : Mval (Nat.gcd m n ::ₘ (Nat.lcm m n / Nat.gcd m n) ::ₘ s) = Mval (m ::ₘ n ::ₘ s) := by …Mentions: Imo2026P1.Board, Imo2026P1.Mval
- lemma
Imo2026P1.Mval_reachableMvalis invariant along any finite play line 266 sourceSource documentation
Mvalis invariant along any finite play.standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: Imo2026P1.Board,
Nat,Membership.mem,LE.le,OfNat.ofNat, Imo2026P1.Reachable,Eq, Imo2026P1.MvalProof uses:
Relation.ReflTransGen.rec, Imo2026P1.Move,Eq.refl,Relation.ReflTransGen,Exists,And,LT.lt,Multiset.cons,Nat.gcd,HDiv.hDiv,Nat.lcm, Imo2026P1.ge_one_reachable,Eq.rec,Multiset,Multiset.mem_cons_of_mem,Eq.symm,Eq.mpr,id,congrArg, Imo2026P1.Mval_move11 instances, coercions and auxiliary constants left out.
Tactic trace: 9 steps
Open to load the checked before-and-after goal states.
lemma Mval_reachable {B₀ B : Board} (hge : ∀ a ∈ B₀, 1 ≤ a) (hreach : Reachable B₀ B) : Mval B = Mval B₀ := by …Mentions: Imo2026P1.Board, Imo2026P1.Reachable, Imo2026P1.Mval
- lemma
Imo2026P1.Mval_terminalOn a terminal board with entries≥ 1,Mvalequals the unique large entry line 281 sourceSource documentation
On a terminal board with entries
≥ 1,Mvalequals the unique large entry.standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: Imo2026P1.Board,
Nat,Membership.mem,LE.le,OfNat.ofNat, Imo2026P1.HasUniqueLarge,LT.lt,Eq, Imo2026P1.MvalProof uses:
Multiset,Multiset.filter,Singleton.singleton,Iff.mpr,And,Multiset.mem_filter,And.intro,Exists,Iff.mp,Multiset.card,Multiset.card_eq_one,Eq.symm,Multiset.mem_singleton,Eq.mp,congrArg,Eq.mpr,id,Eq.refl,HAdd.hAdd,Notand 43 more51 instances, coercions and auxiliary constants left out.
Tactic trace: 36 steps
Open to load the checked before-and-after goal states.
lemma Mval_terminal {B' : Board} (hge : ∀ a ∈ B', 1 ≤ a) (huniq : HasUniqueLarge B') {M : ℕ} (hM : 1 < M) (hMem : M ∈ B') : Mval B' = M := by …Mentions: Imo2026P1.Board, Imo2026P1.HasUniqueLarge, Imo2026P1.Mval
- lemma
Imo2026P1.unique_large_of_reachable_terminalAny terminal board reachable from an initial boardB₀has exactly one entry> 1line 324 sourceSource documentation
Any terminal board reachable from an initial board
B₀has exactly one entry> 1.standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: Imo2026P1.Board, Imo2026P1.IsInitial, Imo2026P1.Reachable, Imo2026P1.IsTerminal, Imo2026P1.HasUniqueLarge
Proof uses:
Eq,Multiset,Nat,Multiset.filter,LT.lt,OfNat.ofNat,Iff.mpr,Membership.mem,Multiset.filter_eq_self,And.right,Multiset.card,LE.le,Eq.mpr,id,congrArg,And.left,Eq.refl, Imo2026P1.large_count_pos_of_reachable,le_antisymm7 instances, coercions and auxiliary constants left out.
Tactic trace: 7 steps
Open to load the checked before-and-after goal states.
lemma unique_large_of_reachable_terminal (B₀ : Board) (hB₀ : IsInitial B₀) (B' : Board) (hreach : Reachable B₀ B') (hterm : IsTerminal B') : HasUniqueLarge B' := by …Mentions: Imo2026P1.Board, Imo2026P1.IsInitial, Imo2026P1.Reachable, Imo2026P1.IsTerminal, Imo2026P1.HasUniqueLarge
- lemma
Imo2026P1.large_mem_eq_MvalAny entry> 1of a terminal board reachable from an initial boardB₀equalsMval B₀line 336 sourceSource documentation
Any entry
> 1of a terminal board reachable from an initial boardB₀equalsMval B₀.standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: Imo2026P1.Board, Imo2026P1.IsInitial, Imo2026P1.Reachable, Imo2026P1.IsTerminal,
Nat,LT.lt,OfNat.ofNat,Membership.mem,Eq, Imo2026P1.MvalProof uses:
LE.le, Imo2026P1.ge_one_reachable,LT.lt.le,And.right,Multiset.card, Imo2026P1.HasUniqueLarge, Imo2026P1.unique_large_of_reachable_terminal, Imo2026P1.Mval_terminal, Imo2026P1.Mval_reachable,Eq.symm,Eq.mp,congrArg8 instances, coercions and auxiliary constants left out.
Tactic trace: 6 steps
Open to load the checked before-and-after goal states.
lemma large_mem_eq_Mval {B₀ B' : Board} (hB₀ : IsInitial B₀) (hreach : Reachable B₀ B') (hterm : IsTerminal B') {M : ℕ} (hM : 1 < M) (hMem : M ∈ B') : M = Mval B₀ := by …Mentions: Imo2026P1.Board, Imo2026P1.IsInitial, Imo2026P1.Reachable, Imo2026P1.IsTerminal, Imo2026P1.Mval
- problem
Imo2026P1.imo2026_p1a_terminationStatement (a), part 1 — termination line 350 sourceSource documentation
Statement (a), part 1 — termination. There is no infinite play starting from an initial board
B₀: no infinite sequence of boards can start atB₀and have every consecutive pair related by aMove.standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: Imo2026P1.Board, Imo2026P1.IsInitial,
Not,Exists,Nat,And,Eq,OfNat.ofNat, Imo2026P1.Move,HAdd.hAddProof uses:
Membership.mem,LE.le,LT.lt,Multiset.prod,Nat.pos_of_ne_zero,Iff.mp,Multiset,Multiset.prod_eq_zero_iff,Lex,Prod,Equiv,toLex,Prod.mk,Multiset.card,Multiset.filter,Multiset.cons,Nat.gcd,HDiv.hDiv,Nat.lcm,Neand 55 more67 instances, coercions and auxiliary constants left out.
Tactic trace: 75 steps
Open to load the checked before-and-after goal states.
problem imo2026_p1a_termination (B₀ : Board) (hB₀ : IsInitial B₀) : ¬ ∃ f : ℕ → Board, f 0 = B₀ ∧ ∀ k, Move (f k) (f (k + 1)) := by …Mentions: Imo2026P1.Board, Imo2026P1.IsInitial, f, Imo2026P1.Move
- problem
Imo2026P1.imo2026_p1a_unique_largeStatement (a), part 2 — unique large entry line 451 sourceSource documentation
Statement (a), part 2 — unique large entry. Any terminal board reachable from an initial board
B₀has exactly one entry> 1.standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: Imo2026P1.Board, Imo2026P1.IsInitial, Imo2026P1.Reachable, Imo2026P1.IsTerminal, Imo2026P1.HasUniqueLarge
Proof uses: Imo2026P1.unique_large_of_reachable_terminal
problem imo2026_p1a_unique_large (B₀ : Board) (hB₀ : IsInitial B₀) (B' : Board) (hreach : Reachable B₀ B') (hterm : IsTerminal B') : HasUniqueLarge B' := …Mentions: Imo2026P1.Board, Imo2026P1.IsInitial, Imo2026P1.Reachable, Imo2026P1.IsTerminal, Imo2026P1.HasUniqueLarge
- problem
Imo2026P1.imo2026_p1b_invarianceStatement (b) — invariance ofMline 459 sourceSource documentation
Statement (b) — invariance of
M. Any two terminal boards reachable from the same initial boardB₀have the same set of entries> 1; since (by (a)) each has exactly one such entry, this says the terminal valueMis the same for both.standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: Imo2026P1.Board, Imo2026P1.IsInitial, Imo2026P1.Reachable, Imo2026P1.IsTerminal,
Nat,Iff,And,LT.lt,OfNat.ofNat,Membership.memProof uses:
Exists, Imo2026P1.HasUniqueLarge, Imo2026P1.unique_large_of_reachable_terminal,Eq,Multiset.card,Multiset.filter,Ne,Multiset,absurd,False,Eq.mp,congrArg,Multiset.card_zero,of_decide_eq_true,Not,id,Bool,Decidable.decide,Bool.true,Eq.refland 13 more14 instances, coercions and auxiliary constants left out.
Tactic trace: 25 steps
Open to load the checked before-and-after goal states.
problem imo2026_p1b_invariance (B₀ : Board) (hB₀ : IsInitial B₀) (B₁ B₂ : Board) (h₁ : Reachable B₀ B₁) (h₂ : Reachable B₀ B₂) (t₁ : IsTerminal B₁) (t₂ : IsTerminal B₂) : ∀ M, (1 < M ∧ M ∈ B₁) ↔ (1 < M ∧ M ∈ B₂) := by …Mentions: Imo2026P1.Board, Imo2026P1.IsInitial, Imo2026P1.Reachable, Imo2026P1.IsTerminal