planar_necklace_three_agents_two_cuts_empty
The empty point set in the plane can be trivially fairly divided among 3 agents with at most 2 straight-line cuts (0 cuts suffice).
Statement
theorem planar_necklace_three_agents_two_cuts_empty (P : Finset (ℝ × ℝ)) (c : (ℝ × ℝ) → Fin 2) (hP : P = ∅) : ∃ (L : Finset StraightLine) (α : (ℝ × ℝ) → Fin 3), L.card ≤ 2 ∧ is_straight_line_cut_consistent P L α ∧ ∀ i : Fin 3, (P.filter (fun p => α p = i ∧ c p = 0)).card = (P.filter (fun p => c p = 0)).card / 3 ∧ (P.filter (fun p => α p = i ∧ c p = 1)).card = (P.filter (fun p => c p = 1)).card / 3
- Source
- step towards planar_necklace_three_agents_two_cuts
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- StraightLineA straight line in the plane ℝ², given by an affine functional with nonzero linear part.
- is_straight_line_cut_consistentGiven a finite set P of points in ℝ × ℝ, a finite set L of straight lines (StraightLine), a natural number k, and an allocation function α…
The proof, explained
For the empty point set P = ∅, we choose zero cut lines (L = ∅) and assign all points to the first agent. The cut count satisfies 0 ≤ 2, and the fair division condition holds trivially because each agent receives 0 points of each color, matching 0 / 3 = 0. The cut consistency requirement holds vacuously since there are no points and no cuts.
Choosing no cuts (L = ∅) and assigning all points to agent 0 satisfies the cut bound and fair division on the empty point set, leaving only cut consistency to be verified.
Substitute P = ∅ using the hypothesis hP. We then choose the empty set of cuts L = ∅ and the constant assignment α(p) = 0 for all points p. The cut bound |L| ≤ 2 reduces to 0 ≤ 2, which holds trivially. For each agent i ∈ Fin 3 and each color c ∈ {0, 1}, the filtered point set from P = ∅ is empty, so its cardinality is 0. Since 0 = 0 / 3, every agent trivially receives an equal share (0 points) of each color.
subst hP refine ⟨∅, fun _ => 0, by simp, ?_, by simp⟩
The cut consistency condition holds vacuously for L = ∅ and P = ∅.
Unfolding the definition of is_straight_line_cut_consistent, we need to provide a sign function s : StraightLine → ℝ × ℝ → Bool respecting line orientations on P and guaranteeing that points with identical signs across all cuts in L have the same assignment in α. Choosing the constant dummy function s(ℓ, p) = false, both required conditions quantify universally over points in P = ∅ and lines in L = ∅, and therefore hold vacuously.
uses
is_straight_line_cut_consistentunfold is_straight_line_cut_consistent refine ⟨fun _ _ => false, by simp, by simp⟩
is_straight_line_cut_consistent- An assignment of points to agents is consistent with a set of straight-line cuts if there exists a sign function (indicating which side of each line each point lies on) such that points receiving the same signs for all cuts are assigned to the same agent.
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.
/-- The empty point set in the plane can be trivially fairly divided among 3 agents with at most 2 straight lines. -/theorem planar_necklace_three_agents_two_cuts_empty (P : Finset (ℝ × ℝ)) (c : (ℝ × ℝ) → Fin 2) (hP : P = ∅) : ∃ (L : Finset StraightLine) (α : (ℝ × ℝ) → Fin 3), L.card ≤ 2 ∧ is_straight_line_cut_consistent P L α ∧ ∀ i : Fin 3, (P.filter (fun p => α p = i ∧ c p = 0)).card = (P.filter (fun p => c p = 0)).card / 3 ∧ (P.filter (fun p => α p = i ∧ c p = 1)).card = (P.filter (fun p => c p = 1)).card / 3 := by subst hP refine ⟨∅, fun _ => 0, by simp, ?_, by simp⟩ unfold is_straight_line_cut_consistent refine ⟨fun _ _ => false, by simp, by simp⟩