Compfiles/Imo2026P1.lean

GitHub source file

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
  1. abbrev Imo2026P1.Board A board is a finite multiset of natural numbers line 49 source

    Source documentation

    A board is a finite multiset of natural numbers. The full board discipline (entries ≥ 1, cardinality 2026) is captured by the predicate IsInitial.

    no axioms what this means

    Proof uses: Multiset, Nat

    abbrev Board := Multiset ℕ
  2. def Imo2026P1.IsInitial An initial board: exactly 2026 entries, each strictly greater than 1 line 52 source

    Source documentation

    An initial board: exactly 2026 entries, each strictly greater than 1.

    standard axioms: propext what this means

    Statement uses: Imo2026P1.Board

    Proof uses: And, Eq, Nat, Multiset.card, OfNat.ofNat, Membership.mem, LT.lt

    3 instances, coercions and auxiliary constants left out.

    def IsInitial (B : Board) : Prop :=
    …

    Mentions: Imo2026P1.Board

  3. def Imo2026P1.Move Documented declaration: Move line 60 source

    Source 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 insert gcd(m, n) and lcm(m, n) / gcd(m, n). Using m ::ₘ n ::ₘ s for 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.lcm

    4 instances, coercions and auxiliary constants left out.

    def Move (B B' : Board) : Prop :=
    …

    Mentions: Imo2026P1.Board

  4. def Imo2026P1.IsTerminal A board is terminal when at most one entry is > 1, so no move is possible line 66 source

    Source 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.ofNat

    4 instances, coercions and auxiliary constants left out.

    def IsTerminal (B : Board) : Prop :=
    …

    Mentions: Imo2026P1.Board

  5. def Imo2026P1.HasUniqueLarge A board has a unique large entry when exactly one entry is > 1 line 70 source

    Source 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.ofNat

    3 instances, coercions and auxiliary constants left out.

    def HasUniqueLarge (B : Board) : Prop :=
    …

    Mentions: Imo2026P1.Board

  6. def Imo2026P1.Reachable Reachable B B' : B' can be obtained from B by a finite sequence of moves (the reflexive–transitive closure of Move) line 76 source

    Source documentation

    Reachable B B' : B' can be obtained from B by a finite sequence of moves (the reflexive–transitive closure of Move). A finite play from B to a terminal board B' is precisely a witness of Reachable B B' with IsTerminal B'.

    standard axioms: Quot.sound what this means

    Statement uses: Imo2026P1.Board

    Proof uses: Relation.ReflTransGen, Imo2026P1.Move

    def Reachable (B B' : Board) : Prop := Relation.ReflTransGen Move B B'
    …

    Mentions: Imo2026P1.Board, Imo2026P1.Move

  7. def Imo2026P1.gExp The exponent g_p for a prime p and board B: the gcd of the p-adic valuations of the entries of B line 84 source

    Source documentation

    The exponent g_p for a prime p and board B: the gcd of the p-adic valuations of the entries of B. Since gcd(a, 0) = a, valuations equal to 0 (entries not divisible by p) do not affect this gcd, so gExp p B is the gcd of the positive p-adic valuations occurring in B.

    standard axioms: Classical.choice, Quot.sound, propext what this means

    Statement uses: Nat, Imo2026P1.Board

    Proof uses: Multiset.gcd, Multiset.map, padicValNat

    3 instances, coercions and auxiliary constants left out.

    noncomputable def gExp (p : ℕ) (B : Board) : ℕ :=
    …

    Mentions: Imo2026P1.Board

  8. def Imo2026P1.Mval The claimed invariant terminal value M = ∏_{p ∣ ∏ B} p ^ gExp p B, the product over all primes dividing some entry of B of p raised to the gcd of the p-adic valuations line 90 source

    Source documentation

    The claimed invariant terminal value M = ∏_{p ∣ ∏ B} p ^ gExp p B, the product over all primes dividing some entry of B of p raised to the gcd of the p-adic valuations.

    standard axioms: Classical.choice, Quot.sound, propext what this means

    Statement uses: Imo2026P1.Board, Nat

    Proof uses: Finset.prod, Nat.primeFactors, Multiset.prod, HPow.hPow, Imo2026P1.gExp

    5 instances, coercions and auxiliary constants left out.

    noncomputable def Mval (B : Board) : ℕ :=
    …

    Mentions: Imo2026P1.Board

  9. lemma Imo2026P1.move_ge_one Moves preserve the property that all entries are ≥ 1 line 115 source

    Source 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.ofNat

    Proof 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.symm and 11 more

    30 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

  10. lemma Imo2026P1.ge_one_reachable Reachable boards have all entries ≥ 1, provided the start board does line 142 source

    Source 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.Reachable

    Proof uses: Relation.ReflTransGen.rec, Imo2026P1.Move, Relation.ReflTransGen, Imo2026P1.move_ge_one

    6 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

  11. lemma Imo2026P1.large_count_pos_of_move A move always produces at least one entry > 1 line 149 source

    Source 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.lt

    Proof 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.intro and 14 more

    23 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

  12. lemma Imo2026P1.large_count_pos_of_reachable Reachable boards have at least one entry > 1, provided the start board does line 177 source

    Source 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.Reachable

    Proof uses: Relation.ReflTransGen.rec, Imo2026P1.Move, Relation.ReflTransGen, Imo2026P1.large_count_pos_of_move

    8 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

  13. lemma Imo2026P1.gcd_min_sub_max gcd(min a b, max a b - min a b) = gcd(a, b) line 185 source

    Source 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.max

    Proof 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_left

    15 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
    …
  14. lemma Imo2026P1.gExp_move For a prime p, the quantity gExp p is preserved by a move line 191 source

    Source documentation

    For a prime p, the quantity gExp p is 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.lcm

    Proof 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_left and 29 more

    48 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

  15. lemma Imo2026P1.Mval_move Mval is invariant under a move, for boards whose remaining entries are ≥ 1 line 233 source

    Source documentation

    Mval is 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.lcm

    Proof 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_assoc and 18 more

    63 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

  16. lemma Imo2026P1.Mval_reachable Mval is invariant along any finite play line 266 source

    Source documentation

    Mval is 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.Mval

    Proof 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_move

    11 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

  17. lemma Imo2026P1.Mval_terminal On a terminal board with entries ≥ 1, Mval equals the unique large entry line 281 source

    Source documentation

    On a terminal board with entries ≥ 1, Mval equals 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.Mval

    Proof 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, Not and 43 more

    51 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

  18. lemma Imo2026P1.unique_large_of_reachable_terminal Any terminal board reachable from an initial board B₀ has exactly one entry > 1 line 324 source

    Source 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_antisymm

    7 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

  19. lemma Imo2026P1.large_mem_eq_Mval Any entry > 1 of a terminal board reachable from an initial board B₀ equals Mval B₀ line 336 source

    Source documentation

    Any entry > 1 of a terminal board reachable from an initial board B₀ equals Mval 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.Mval

    Proof 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, congrArg

    8 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

  20. problem Imo2026P1.imo2026_p1a_termination Statement (a), part 1 — termination line 350 source

    Source documentation

    Statement (a), part 1 — termination. There is no infinite play starting from an initial board B₀: no infinite sequence of boards can start at B₀ and have every consecutive pair related by a Move.

    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.hAdd

    Proof 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, Ne and 55 more

    67 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

  21. problem Imo2026P1.imo2026_p1a_unique_large Statement (a), part 2 — unique large entry line 451 source

    Source 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

  22. problem Imo2026P1.imo2026_p1b_invariance Statement (b) — invariance of M line 459 source

    Source documentation

    Statement (b) — invariance of M. Any two terminal boards reachable from the same initial board B₀ have the same set of entries > 1; since (by (a)) each has exactly one such entry, this says the terminal value M is 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.mem

    Proof 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.refl and 13 more

    14 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