AFTD Auto-Formalizing Theoretical Domains

planar_necklace_three_agents_two_cuts_empty

theoremverified

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.

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

    lines 11–12

      subst hP
      refine ⟨∅, fun _ => 0, by simp, ?_, by simp⟩
  2. 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.

    lines 13–14

    uses is_straight_line_cut_consistent

      unfold 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

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