AFTD Auto-Formalizing Theoretical Domains

critical_three_seven_allocation_tables_structure

theoremverified

Each of the seven displayed three-round allocation tables assigns every chore once to each agent across rounds, gives the diagonal agent three chores and each other agent two, and assigns at most one of the first four chores to the diagonal agent in round zero.

Statement

theorem critical_three_seven_allocation_tables_structure :
    let T : Fin 7 → Fin 3 → Fin 7 → Fin 3 := ![
      ![![0, 2, 1, 1, 2, 0, 0], ![1, 1, 0, 0, 1, 2, 2], ![2, 0, 2, 2, 0, 1, 1]],
      ![![0, 2, 1, 1, 2, 0, 0], ![1, 0, 0, 2, 1, 1, 2], ![2, 1, 2, 0, 0, 2, 1]],
      ![![2, 1, 2, 0, 1, 0, 0], ![1, 0, 1, 2, 0, 1, 2], ![0, 2, 0, 1, 2, 2, 1]],
      ![![1, 0, 2, 1, 0, 0, 2], ![2, 1, 0, 2, 1, 1, 0], ![0, 2, 1, 0, 2, 2, 1]],
      ![![1, 2, 2, 1, 0, 0, 0], ![0, 1, 1, 0, 2, 1, 2], ![2, 0, 0, 2, 1, 2, 1]],
      ![![0, 1, 2, 2, 0, 1, 0], ![1, 0, 1, 0, 1, 2, 2], ![2, 2, 0, 1, 2, 0, 1]],
      ![![0, 2, 2, 1, 1, 0, 0], ![1, 0, 1, 2, 0, 2, 1], ![2, 1, 0, 0, 2, 1, 2]]
    ]
    (∀ (j : Fin 7) (g : Fin 7) (i : Fin 3),
      (Finset.univ.filter fun t : Fin 3 => T j t g = i).card = 1) ∧
    (∀ (j : Fin 7) (t i : Fin 3),
      (Finset.univ.filter fun g : Fin 7 => T j t g = i).card = if i = t then 3 else 2) ∧
    (∀ j : Fin 7, (Finset.univ.filter fun g : Fin 7 => g.val < 4 ∧ T j 0 g = 0).card ≤ 1)
Source
Explicit finite allocation certificate for OP-1112, experiment 26817.
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The theorem verifies three structural properties for seven concrete chore-allocation tables with three agents, three rounds, and seven chores: every chore is given to every agent exactly once, the diagonal agent receives three chores and other agents two in each round, and agent 0 receives at most one of the first four chores in round 0. Because the tables are explicit and all conditions involve finite domains, the proposition is decidable. The proof is completed in a single step by exhaustive computation via `decide`.

  1. All seven allocation tables satisfy the three structural conditions: each chore is assigned to each agent exactly once across the three rounds, in each round the diagonal agent receives three chores while the other two agents receive two, and agent 0 receives at most one of the first four chores in round 0. automation

    The tables are given as explicit matrices of values in $\text{Fin } 3$, and all quantifiers in the theorem statement range over the finite index sets $\text{Fin } 7$ and $\text{Fin } 3$. Consequently, the entire assertion is a closed, decidable proposition. The `decide` tactic evaluates this finite check by direct computation and confirms that all three conditions hold for all seven tables.

    line 19

      decide

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

set_option maxRecDepth 100000set_option maxHeartbeats 10000000theorem critical_three_seven_allocation_tables_structure :    let T : Fin 7 → Fin 3 → Fin 7 → Fin 3 := ![      ![![0, 2, 1, 1, 2, 0, 0], ![1, 1, 0, 0, 1, 2, 2], ![2, 0, 2, 2, 0, 1, 1]],      ![![0, 2, 1, 1, 2, 0, 0], ![1, 0, 0, 2, 1, 1, 2], ![2, 1, 2, 0, 0, 2, 1]],      ![![2, 1, 2, 0, 1, 0, 0], ![1, 0, 1, 2, 0, 1, 2], ![0, 2, 0, 1, 2, 2, 1]],      ![![1, 0, 2, 1, 0, 0, 2], ![2, 1, 0, 2, 1, 1, 0], ![0, 2, 1, 0, 2, 2, 1]],      ![![1, 2, 2, 1, 0, 0, 0], ![0, 1, 1, 0, 2, 1, 2], ![2, 0, 0, 2, 1, 2, 1]],      ![![0, 1, 2, 2, 0, 1, 0], ![1, 0, 1, 0, 1, 2, 2], ![2, 2, 0, 1, 2, 0, 1]],      ![![0, 2, 2, 1, 1, 0, 0], ![1, 0, 1, 2, 0, 2, 1], ![2, 1, 0, 0, 2, 1, 2]]    ]    (∀ (j : Fin 7) (g : Fin 7) (i : Fin 3),      (Finset.univ.filter fun t : Fin 3 => T j t g = i).card = 1) ∧    (∀ (j : Fin 7) (t i : Fin 3),      (Finset.univ.filter fun g : Fin 7 => T j t g = i).card = if i = t then 3 else 2) ∧    (∀ j : Fin 7, (Finset.univ.filter fun g : Fin 7 => g.val < 4 ∧ T j 0 g = 0).card ≤ 1) := by  decide
See it in the graphDiscuss this resultChallenge it