critical_three_canonical_diagonal_coverage
For each pair of listed four-bit masks with sorted two-bit signatures in each of the designated chore groups, one of seven explicitly listed pairs of diagonal triples contains at most one high chore per agent.
Statement
theorem critical_three_canonical_diagonal_coverage : let bit : ℕ → ℕ → ℕ := fun x j => x / 2^j % 2 let pop : ℕ → ℕ := fun x => bit x 0 + bit x 1 + bit x 2 + bit x 3 + bit x 4 + bit x 5 + bit x 6 let masks : Fin 35 → ℕ := ![15, 23, 27, 29, 30, 39, 43, 45, 46, 51, 53, 54, 57, 58, 60, 71, 75, 77, 78, 83, 85, 86, 89, 90, 92, 99, 101, 102, 105, 106, 108, 113, 114, 116, 120] let sig : ℕ → ℕ → ℕ → ℕ := fun a b j => bit a j + 2 * bit b j let one : ℕ → ℕ → ℕ → ℕ → Prop := fun a x y z => bit a x + bit a y + bit a z ≤ 1 ∀ a b : Fin 35, (pop (masks a) = 4 ∧ pop (masks b) = 4 ∧ sig (masks a) (masks b) 0 ≤ sig (masks a) (masks b) 1 ∧ sig (masks a) (masks b) 1 ≤ sig (masks a) (masks b) 2 ∧ sig (masks a) (masks b) 2 ≤ sig (masks a) (masks b) 3 ∧ sig (masks a) (masks b) 4 ≤ sig (masks a) (masks b) 5 ∧ sig (masks a) (masks b) 5 ≤ sig (masks a) (masks b) 6) → ((one (masks a) 0 1 4 ∧ one (masks b) 0 2 3) ∨ (one (masks a) 0 4 5 ∧ one (masks b) 0 2 5) ∨ (one (masks a) 0 2 5 ∧ one (masks b) 1 4 5) ∨ (one (masks a) 1 4 5 ∧ one (masks b) 1 4 5) ∨ (one (masks a) 1 2 5 ∧ one (masks b) 0 3 5) ∨ (one (masks a) 0 2 4 ∧ one (masks b) 0 1 4) ∨ (one (masks a) 0 2 6 ∧ one (masks b) 0 4 6))
- Source
- Explicit finite certificate for OP-1112, experiment 26817.
- Verified
- 14 Nov 2026
- Axioms
propext- Used by 1
- three_agent_critical_equal_weight_allocation_familyFor three agents and seven chores, suppose each agent designates four chores high. There exist three allocations such that every chore…
The proof, explained
The theorem asserts that among all pairs of 4-element subsets of a 7-element chore set (encoded as 7-bit integers of Hamming weight 4) whose joint chore signatures are sorted within groups {0, 1, 2, 3} and {4, 5, 6}, at least one of seven specified pairs of chore triples allocates at most one chore to each agent. The proof proceeds by finite exhaustive verification: after unfolding the definitions of bits, weights, signatures, and triple occupancy, Lean's `decide` tactic checks all 35 × 35 = 1,225 mask pairs by direct computation.
Every pair of masks satisfying the sorted signature and weight conditions satisfies at least one of the seven diagonal triple coverage conditions. automation
The local definitions (`bit`, `pop`, `masks`, `sig`, and `one`) are unfolded into the goal by `dsimp only`. Because the universal quantification ranges over the finite type `Fin 35 × Fin 35` (a total of 35 × 35 = 1,225 pairs) and each condition is an arithmetic check on small natural numbers, the entire proposition is decidable. The `decide` tactic verifies the claim by exhaustive kernel evaluation over all 1,225 pairs.
dsimp only decide
- The proof is entirely computational: the `decide` tactic exhaustively checks all 1,225 pairs in the finite search space without providing a human-readable combinatorial explanation for why this specific list of seven triples suffices.
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.
set_option maxRecDepth 100000set_option maxHeartbeats 10000000theorem critical_three_canonical_diagonal_coverage : let bit : ℕ → ℕ → ℕ := fun x j => x / 2^j % 2 let pop : ℕ → ℕ := fun x => bit x 0 + bit x 1 + bit x 2 + bit x 3 + bit x 4 + bit x 5 + bit x 6 let masks : Fin 35 → ℕ := ![15, 23, 27, 29, 30, 39, 43, 45, 46, 51, 53, 54, 57, 58, 60, 71, 75, 77, 78, 83, 85, 86, 89, 90, 92, 99, 101, 102, 105, 106, 108, 113, 114, 116, 120] let sig : ℕ → ℕ → ℕ → ℕ := fun a b j => bit a j + 2 * bit b j let one : ℕ → ℕ → ℕ → ℕ → Prop := fun a x y z => bit a x + bit a y + bit a z ≤ 1 ∀ a b : Fin 35, (pop (masks a) = 4 ∧ pop (masks b) = 4 ∧ sig (masks a) (masks b) 0 ≤ sig (masks a) (masks b) 1 ∧ sig (masks a) (masks b) 1 ≤ sig (masks a) (masks b) 2 ∧ sig (masks a) (masks b) 2 ≤ sig (masks a) (masks b) 3 ∧ sig (masks a) (masks b) 4 ≤ sig (masks a) (masks b) 5 ∧ sig (masks a) (masks b) 5 ≤ sig (masks a) (masks b) 6) → ((one (masks a) 0 1 4 ∧ one (masks b) 0 2 3) ∨ (one (masks a) 0 4 5 ∧ one (masks b) 0 2 5) ∨ (one (masks a) 0 2 5 ∧ one (masks b) 1 4 5) ∨ (one (masks a) 1 4 5 ∧ one (masks b) 1 4 5) ∨ (one (masks a) 1 2 5 ∧ one (masks b) 0 3 5) ∨ (one (masks a) 0 2 4 ∧ one (masks b) 0 1 4) ∨ (one (masks a) 0 2 6 ∧ one (masks b) 0 4 6)) := by dsimp only decide