straight_line_bisection_of_cut_zero
If every point lies on a given straight line and each of two colors has even size, that one line admits a consistent allocation bisecting both colors. This handles the collinear case using the permitted boundary signs.
Statement
theorem straight_line_bisection_of_cut_zero (P : Finset (ℝ × ℝ)) (c : (ℝ × ℝ) → Fin 2) (ℓ : StraightLine) (heven : ∀ j, 2 ∣ (P.filter fun p => c p = j).card) (hzero : ∀ p ∈ P, ℓ.cut p = 0) : ∃ α : (ℝ × ℝ) → Fin 2, is_straight_line_cut_consistent P {ℓ} α ∧ ∀ i j : Fin 2, (P.filter fun p => α p = i ∧ c p = j).card = (P.filter fun p => c p = j).card / 2
- Source
- Boundary-assignment helper for planar_necklace_three_agents_three_cuts; arXiv:2610.27956 Proposition 9 and its bisection step. The definition permits arbitrary signs on zero cuts.
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- straight_line_bisection_of_side_card_boundsA straight line whose strictly positive and strictly negative sides each contain at most half of each color admits a consistent two-agent…
- 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
The proof reduces the claim to straight_line_bisection_of_side_card_bounds, which guarantees a consistent bisecting allocation whenever each open half-plane bounded by the line contains at most half of the points of each color. Since every point of the set lies directly on the line ℓ, both the strictly positive and strictly negative half-planes contain no points at all. Their cardinalities are zero, which trivially satisfies the required upper bounds.
It suffices to show that each color class has at most half its points in the positive half-plane (0 < ℓ.cut p) and at most half in the negative half-plane (ℓ.cut p < 0).
By invoking the existing result straight_line_bisection_of_side_card_bounds with the even-cardinality hypothesis heven, the problem of finding a bisecting cut-consistent allocation reduces to verifying that both open half-planes contain at most half of the points of each color.
uses
straight_line_bisection_of_side_card_boundsapply straight_line_bisection_of_side_card_bounds P c ℓ hevenFor each color j, the number of points of color j in the positive half-plane 0 < ℓ.cut p is at most half the total number of points of that color.
Let j be a color. Since every point p in P lies on ℓ by assumption (ℓ.cut p = 0), any point in the filtered set would satisfy 0 < 0, which is impossible by irreflexivity of strict inequality (lt_irrefl). Thus, by filter_eq_empty_iff.mpr and mem_filter.mp, the set of points of color j in the positive half-plane is empty. Its cardinality is 0 by card_empty, which is at most half of the total size by Nat.zero_le.
uses
filter_eq_empty_iff.mpr,mem_filter.mp,lt_irrefl,card_empty,Nat.zero_le· intro j have hempty : ((P.filter fun p => c p = j).filter fun p => 0 < ℓ.cut p) = ∅ := by apply filter_eq_empty_iff.mpr intro p hp rw [hzero p (mem_filter.mp hp).1] exact lt_irrefl _ rw [hempty, card_empty] exact Nat.zero_le _
For each color j, the number of points of color j in the negative half-plane ℓ.cut p < 0 is at most half the total number of points of that color.
Let j be a color. Symmetrically, any point in the negative half-plane would satisfy ℓ.cut p < 0, which contradicts ℓ.cut p = 0 via lt_irrefl. Therefore, by filter_eq_empty_iff.mpr and mem_filter.mp, the set of points of color j in the negative half-plane is empty. Its cardinality is 0 by card_empty, which is at most half the color size by Nat.zero_le.
uses
filter_eq_empty_iff.mpr,mem_filter.mp,lt_irrefl,card_empty,Nat.zero_le· intro j have hempty : ((P.filter fun p => c p = j).filter fun p => ℓ.cut p < 0) = ∅ := by apply filter_eq_empty_iff.mpr intro p hp rw [hzero p (mem_filter.mp hp).1] exact lt_irrefl _ rw [hempty, card_empty] exact Nat.zero_le _
straight_line_bisection_of_side_card_bounds- If each open half-plane bounded by a line contains at most half of the points of each even-sized color class, then there exists a cut-consistent allocation that bisects both color classes.
filter_eq_empty_iff.mpr- If no element of a finite set satisfies a predicate, then the filtered set is empty.
mem_filter.mp- An element belongs to a filtered set only if it belongs to the original set and satisfies the predicate.
lt_irrefl- Strict inequality is irreflexive: no element is strictly less than itself.
card_empty- The cardinality of the empty finite set is zero.
Nat.zero_le- Zero is less than or equal to every natural number.
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.
open Finsettheorem straight_line_bisection_of_cut_zero (P : Finset (ℝ × ℝ)) (c : (ℝ × ℝ) → Fin 2) (ℓ : StraightLine) (heven : ∀ j, 2 ∣ (P.filter fun p => c p = j).card) (hzero : ∀ p ∈ P, ℓ.cut p = 0) : ∃ α : (ℝ × ℝ) → Fin 2, is_straight_line_cut_consistent P {ℓ} α ∧ ∀ i j : Fin 2, (P.filter fun p => α p = i ∧ c p = j).card = (P.filter fun p => c p = j).card / 2 := by apply straight_line_bisection_of_side_card_bounds P c ℓ heven · intro j have hempty : ((P.filter fun p => c p = j).filter fun p => 0 < ℓ.cut p) = ∅ := by apply filter_eq_empty_iff.mpr intro p hp rw [hzero p (mem_filter.mp hp).1] exact lt_irrefl _ rw [hempty, card_empty] exact Nat.zero_le _ · intro j have hempty : ((P.filter fun p => c p = j).filter fun p => ℓ.cut p < 0) = ∅ := by apply filter_eq_empty_iff.mpr intro p hp rw [hzero p (mem_filter.mp hp).1] exact lt_irrefl _ rw [hempty, card_empty] exact Nat.zero_le _