AFTD Auto-Formalizing Theoretical Domains

prescribed_four_agent_triple_completion_obstruction

theoremverified

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.

  1. 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$).

    lines 6–7

      classical
      rintro ⟨F, hbij, hsize, hfixed⟩
  2. 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.

    lines 8–19

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

    lines 20–23

    uses Finset.mem_filter, Finset.mem_univ, true_and

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

    lines 24–29

    uses Finset.card_le_card

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

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
See it in the graphDiscuss this resultChallenge it