is_two_type_allocation_exists
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.
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.
refine ⟨fun i => if i = ⟨0, hn⟩ then a else 0, fun i => if i = ⟨0, hn⟩ then b else 0, ?_, ?_⟩
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.
uses
Finset.sum_ite_eq'· rw [Finset.sum_ite_eq']; simp
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.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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