prescribed_four_agent_triple_completion_obstruction
There is no four-round assignment of nine chores to four agents in which each chore visits each agent once, round i gives agent i three chores and every other agent two chores, and chores 0, 1 and 2 go to agent 0 in round 0, agent 1 in round 1, and an agent other than 2 in round 2.
Statement
theorem prescribed_four_agent_triple_completion_obstruction : ¬ ∃ F : Fin 4 → Fin 9 → Fin 4, (∀ g, Function.Bijective (fun t => F t g)) ∧ (∀ t i, (Finset.univ.filter fun g => F t g = i).card = if i = t then 3 else 2) ∧ ∀ g ∈ ({0,1,2} : Finset (Fin 9)), F 0 g = 0 ∧ F 1 g = 1 ∧ F 2 g ≠ 2
- Source
- An explicit obstruction to a proposed allocation-completion criterion, experiment 26849.
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The proof proceeds by contradiction. Assuming such a chore assignment exists, each of the three chores 0, 1, and 2 must visit agent 0 in round 0 and agent 1 in round 1. Because each chore visits every agent at most once across the four rounds and none of these three chores visits agent 2 in round 2, all three chores must be assigned to agent 3 in round 2. However, in round 2, agent 3 is allotted only two chores, which implies that a set of three distinct chores is contained in a set of size two. Comparing cardinalities yields $3 \le 2$, a contradiction.
Assume for contradiction that a valid chore assignment exists.
We assume the existence of an assignment $F : \text{Fin } 4 \to \text{Fin } 9 \to \text{Fin } 4$ satisfying the three conditions: chore bijectivity across the four rounds ($hbij$), the prescribed round-by-round workload for each agent ($hsize$), and the initial placements for chores 0, 1, and 2 ($hfixed$).
classical rintro ⟨F, hbij, hsize, hfixed⟩
For each of the chores 0, 1, and 2, the agent visited in round 2 must be agent 3.
Let $g \in \{0, 1, 2\}$. By hypothesis, chore $g$ is assigned to agent 0 in round 0, agent 1 in round 1, and not agent 2 in round 2. Because each chore visits each agent exactly once across the four rounds, the schedule $t \mapsto F(t, g)$ is injective. Therefore, having $F(2, g) = 0$ would force round 2 to be round 0, a contradiction; hence $F(2, g) \ne 0$. Similarly, $F(2, g) = 1$ would force round 2 to be round 1, so $F(2, g) \ne 1$. Since agents 0, 1, and 2 are ruled out, exhaustively checking all four agents leaves agent 3 as the only possibility.
have hmust (g : Fin 9) (hg : g ∈ ({0,1,2} : Finset (Fin 9))) : F 2 g = 3 := by obtain ⟨ha, hb, hc⟩ := hfixed g hg have hzero : F 2 g ≠ 0 := by intro he have heq : (2 : Fin 4) = 0 := (hbij g).1 (he.trans ha.symm) exact (by decide : (2 : Fin 4) ≠ 0) heq have hone : F 2 g ≠ 1 := by intro he have heq : (2 : Fin 4) = 1 := (hbij g).1 (he.trans hb.symm) exact (by decide : (2 : Fin 4) ≠ 1) heq generalize he : F 2 g = x fin_cases x <;> simp_all
The set of chores $\{0, 1, 2\}$ is a subset of the chores assigned to agent 3 in round 2.
To show that $\{0, 1, 2\} \subseteq \{g \mid F(2, g) = 3\}$, consider any $g \in \{0, 1, 2\}$. By `Finset.mem_filter`, `Finset.mem_univ`, and `true_and`, belonging to this filtered finset is equivalent to satisfying $F(2, g) = 3$, which was established in the preceding step.
uses
Finset.mem_filter,Finset.mem_univ,true_andhave hsubset : ({0,1,2} : Finset (Fin 9)) ⊆ Finset.univ.filter (fun g => F 2 g = 3) := by intro g hg simp only [Finset.mem_filter, Finset.mem_univ, true_and] exact hmust g hg
Comparing the cardinalities of the two sets yields a contradiction.
By `Finset.card_le_card`, the inclusion $\{0, 1, 2\} \subseteq \{g \mid F(2, g) = 3\}$ implies $|\{0, 1, 2\}| \le |\{g \mid F(2, g) = 3\}|$. The set $\{0, 1, 2\}$ has cardinality 3. On the other hand, the workload specification in $hsize$ for round 2 and agent 3 dictates that agent 3 receives only 2 chores (since $3 \ne 2$). Substituting these two values gives $3 \le 2$, which is impossible and completes the proof by contradiction.
uses
Finset.card_le_cardhave hcard := Finset.card_le_card hsubset have hthree : ({0,1,2} : Finset (Fin 9)).card = 3 := by decide have htwo : (Finset.univ.filter fun g : Fin 9 => F 2 g = 3).card = 2 := by simpa using hsize 2 3 rw [hthree, htwo] at hcard exact (by decide : ¬ 3 ≤ 2) hcard
Finset.mem_filter- An element belongs to the filtered finset `Finset.filter p s` if and only if it belongs to `s` and satisfies the predicate `p`.
Finset.mem_univ- Every element of a finite type belongs to the universal finset `Finset.univ`.
true_and- The conjunction `True ∧ p` is logically equivalent to `p`.
Finset.card_le_card- If a finite set `s` is a subset of `t`, then the cardinality of `s` is at most the cardinality of `t` (`|s| ≤ |t|`).
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.
theorem prescribed_four_agent_triple_completion_obstruction : ¬ ∃ F : Fin 4 → Fin 9 → Fin 4, (∀ g, Function.Bijective (fun t => F t g)) ∧ (∀ t i, (Finset.univ.filter fun g => F t g = i).card = if i = t then 3 else 2) ∧ ∀ g ∈ ({0,1,2} : Finset (Fin 9)), F 0 g = 0 ∧ F 1 g = 1 ∧ F 2 g ≠ 2 := by classical rintro ⟨F, hbij, hsize, hfixed⟩ have hmust (g : Fin 9) (hg : g ∈ ({0,1,2} : Finset (Fin 9))) : F 2 g = 3 := by obtain ⟨ha, hb, hc⟩ := hfixed g hg have hzero : F 2 g ≠ 0 := by intro he have heq : (2 : Fin 4) = 0 := (hbij g).1 (he.trans ha.symm) exact (by decide : (2 : Fin 4) ≠ 0) heq have hone : F 2 g ≠ 1 := by intro he have heq : (2 : Fin 4) = 1 := (hbij g).1 (he.trans hb.symm) exact (by decide : (2 : Fin 4) ≠ 1) heq generalize he : F 2 g = x fin_cases x <;> simp_all have hsubset : ({0,1,2} : Finset (Fin 9)) ⊆ Finset.univ.filter (fun g => F 2 g = 3) := by intro g hg simp only [Finset.mem_filter, Finset.mem_univ, true_and] exact hmust g hg have hcard := Finset.card_le_card hsubset have hthree : ({0,1,2} : Finset (Fin 9)).card = 3 := by decide have htwo : (Finset.univ.filter fun g : Fin 9 => F 2 g = 3).card = 2 := by simpa using hsize 2 3 rw [hthree, htwo] at hcard exact (by decide : ¬ 3 ≤ 2) hcard