AFTD Auto-Formalizing Theoretical Domains

is_two_type_allocation_exists

theoremverified

For any positive number of agents n and any item counts a and b, there exists a complete count allocation of the two types of goods.

Statement

theorem is_two_type_allocation_exists (n a b : ℕ) (hn : 0 < n) :
    ∃ x y : Fin n → ℕ, (∑ i, x i = a) ∧ (∑ i, y i = b)
Source
arXiv:2610.19099
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

Read back from the Lean

For all natural numbers $n$, $a$, and $b$, if $0 < n$, then there exist functions $x, y : \mathrm{Fin}(n) \to \mathbb{N}$ such that $\sum_{i : \mathrm{Fin}(n)} x(i) = a$ and $\sum_{i : \mathrm{Fin}(n)} y(i) = b$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

To prove that an allocation exists, we construct an explicit one: because n > 0, there is a first agent (index 0), to whom we assign all a units of the first good and all b units of the second good, giving 0 to all other agents. The sum over all agents for each good collapses to the single non-zero term for agent 0, verifying the required totals.

  1. Define an allocation giving all items of both goods to agent 0 and nothing to the others.

    Since n > 0, the set of agents Fin n is non-empty, containing the index 0 (as ⟨0, hn⟩). We provide explicit candidate allocation functions x and y: agent 0 receives a units of the first good and b units of the second good, while every other agent receives 0. This reduces the existential goal to verifying the two sum conditions: ∑ i, x i = a and ∑ i, y i = b.

    lines 4–5

      refine ⟨fun i => if i = ⟨0, hn⟩ then a else 0,
              fun i => if i = ⟨0, hn⟩ then b else 0, ?_, ?_⟩
  2. The sum of the first good's allocations across all agents equals a.

    Applying Finset.sum_ite_eq' collapses the sum over all agents to the single term for agent 0, producing the goal (if ⟨0, hn⟩ ∈ Finset.univ then a else 0) = a. Since agent 0 belongs to the universe of all agents Finset.univ, the condition is true and simplification closes the goal.

    line 6

    uses Finset.sum_ite_eq'

      · rw [Finset.sum_ite_eq']; simp
  3. The sum of the second good's allocations across all agents equals b.

    By the identical reasoning, Finset.sum_ite_eq' collapses the sum of y over all agents to the single term at agent 0, and simplification reduces the resulting conditional expression to b = b.

    line 7

    uses Finset.sum_ite_eq'

      · rw [Finset.sum_ite_eq']; simp
Finset.sum_ite_eq'
The sum over a finite set s of a function that equals b(x) when x = a and 0 otherwise collapses to b(a) if a ∈ s, and 0 otherwise.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- A complete count allocation of two types of goods always exists when n > 0. -/theorem is_two_type_allocation_exists (n a b : ℕ) (hn : 0 < n) :    ∃ x y : Fin n → ℕ, (∑ i, x i = a) ∧ (∑ i, y i = b) := by  refine ⟨fun i => if i = ⟨0, hn⟩ then a else 0,          fun i => if i = ⟨0, hn⟩ then b else 0, ?_, ?_⟩  · rw [Finset.sum_ite_eq']; simp  · rw [Finset.sum_ite_eq']; simp
See it in the graphDiscuss this resultChallenge it