planar_necklace_two_parallel_cuts_six_points
Let P be a finite set of 6 points in ℝ × ℝ with a coloring c : (ℝ × ℝ) → Fin 2 having exactly 3 red points (color 0) in P and 3 blue points (color 1) in P. Then there exist a non-zero linear map φ : (ℝ × ℝ) →ₗ[ℝ] ℝ, thresholds t₁, t₂ ∈ ℝ, and an assignment function α : (ℝ × ℝ) → Fin 3 such that is_parallel_two_cut_consistent P φ t₁ t₂ α holds, and for each region i : Fin 3, exactly 1 red point (color 0) and 1 blue point (color 1) of P are assigned to region i by α.
Statement
theorem planar_necklace_two_parallel_cuts_six_points (P : Finset (ℝ × ℝ)) (c : (ℝ × ℝ) → Fin 2) (hP_card : P.card = 6) (h_red : (P.filter (fun p => c p = 0)).card = 3) (h_blue : (P.filter (fun p => c p = 1)).card = 3) : ∃ (φ : (ℝ × ℝ) →ₗ[ℝ] ℝ) (t₁ t₂ : ℝ) (α : (ℝ × ℝ) → Fin 3), φ ≠ 0 ∧ is_parallel_two_cut_consistent P φ t₁ t₂ α ∧ ∀ i : Fin 3, (P.filter (fun p => α p = i ∧ c p = 0)).card = 1 ∧ (P.filter (fun p => α p = i ∧ c p = 1)).card = 1
- Formalizes
- arXiv:2610.27956 Theorem 10
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- is_parallel_two_cut_consistentGiven a finite set of points P in ℝ × ℝ, an ℝ-linear map φ : (ℝ × ℝ) →ₗ[ℝ] ℝ, two thresholds t₁, t₂ ∈ ℝ, and an assignment function α : (ℝ…
- three_subset_sum_ten_or_eleven_pair_balancedLet s be a 3-element subset of Fin 6. If the sum over x in s of (x.val + 1) is 10 or 11, then s contains exactly one element from {0, 1},…
- FThe prime field $\mathrm{GF}(p)$, realized as $\mathbb{Z}/p\mathbb{Z}$ via
ZMod.
- Used by 1
- planar_necklace_two_cuts_six_pointsFor any finite set P of 6 points in the plane ℝ × ℝ colored with two colors c : (ℝ × ℝ) → Fin 2 such that exactly 3 points are colored 0…
Read back from the Lean
Given a finite set of points $P \subseteq \mathbb{R}^2$ and a 2-coloring $c : \mathbb{R}^2 \to \{0, 1\}$ such that: 1. $P$ has cardinality 6 ($|P| = 6$), 2. exactly 3 points of $P$ have color 0 ($|\{p \in P \mid c(p) = 0\}| = 3$), and 3. exactly 3 points of $P$ have color 1 ($|\{p \in P \mid c(p) = 1\}| = 3$), there exist a non-zero $\mathbb{R}$-linear map $\varphi : \mathbb{R}^2 \to \mathbb{R}$ ($\varphi \neq 0$), two real numbers $t_1, t_2 \in \mathbb{R}$, and an assignment function $\alpha : \mathbb{R}^2 \to \{0, 1, 2\}$ such that: 1. $t_1 \le t_2$, 2. for all $p \in P$: - if $\alpha(p) = 0$, then $\varphi(p) \le t_1$, - if $\alpha(p) = 1$, then $t_1 \le \varphi(p) \le t_2$, - if $\alpha(p) = 2$, then $t_2 \le \varphi(p)$, and 3. for each $i \in \{0, 1, 2\}$, the subset of $P$ assigned label $i$ contains exactly one point of color 0 and exactly one point of color 1, i.e., $|\{p \in P \mid \alpha(p) = i \wedge c(p) = 0\}| = 1$ and $|\{p \in P \mid \alpha(p) = i \wedge c(p) = 1\}| = 1$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To fairly allocate 3 red and 3 blue points in the plane into 3 regions using two parallel cuts, the proof projects the points along a direction u. The median projection of the 3 red points and the median projection of the 3 blue points define an odd continuous difference function on the circle. By the intermediate value theorem, there exists a direction u where these two medians coincide at a common value s. Setting both cut thresholds to s and assigning the low, middle, and high points of each color to regions 0, 1, and 2 yields a consistent parallel cut with exactly 1 red and 1 blue point in each region.
med3 is an odd function
Using the properties min(-a, -b) = -max(a, b) and max(-a, -b) = -min(a, b), negating all arguments negates the median.
unfold planar_necklace_two_parallel_cuts_six_points_med3 rw [min_neg_neg, min_neg_neg, max_neg_neg, max_neg_neg]; ring
med3 evaluates to the middle element in all six permutations
By definition of min and max, for each sorted ordering of x, y, z, the minimum and maximum cancel two elements, leaving the middle one.
unfold planar_necklace_two_parallel_cuts_six_points_med3 rw [min_eq_left hxy, min_eq_left (hxy.trans hyz), max_eq_right hxy, max_eq_right hyz]; ring lemma planar_necklace_two_parallel_cuts_six_points_med3_xzy {x y z : ℝ} (hxz : x ≤ z) (hzy : z ≤ y) : planar_necklace_two_parallel_cuts_six_points_med3 x y z = z := by unfold planar_necklace_two_parallel_cuts_six_points_med3 rw [min_eq_left (hxz.trans hzy), min_eq_left hxz, max_eq_right (hxz.trans hzy), max_eq_left hzy]; ring lemma planar_necklace_two_parallel_cuts_six_points_med3_yxz {x y z : ℝ} (hyx : y ≤ x) (hxz : x ≤ z) : planar_necklace_two_parallel_cuts_six_points_med3 x y z = x := by unfold planar_necklace_two_parallel_cuts_six_points_med3 rw [min_eq_right hyx, min_eq_left (hyx.trans hxz), max_eq_left hyx, max_eq_right hxz]; ring lemma planar_necklace_two_parallel_cuts_six_points_med3_yzx {x y z : ℝ} (hyz : y ≤ z) (hzx : z ≤ x) : planar_necklace_two_parallel_cuts_six_points_med3 x y z = z := by unfold planar_necklace_two_parallel_cuts_six_points_med3 rw [min_eq_right (hyz.trans hzx), min_eq_left hyz, max_eq_left (hyz.trans hzx), max_eq_left hzx]; ring lemma planar_necklace_two_parallel_cuts_six_points_med3_zxy {x y z : ℝ} (hzx : z ≤ x) (hxy : x ≤ y) : planar_necklace_two_parallel_cuts_six_points_med3 x y z = x := by unfold planar_necklace_two_parallel_cuts_six_points_med3 rw [min_eq_left hxy, min_eq_right hzx, max_eq_right hxy, max_eq_left (hzx.trans hxy)]; ring lemma planar_necklace_two_parallel_cuts_six_points_med3_zyx {x y z : ℝ} (hzy : z ≤ y) (hyx : y ≤ x) : planar_necklace_two_parallel_cuts_six_points_med3 x y z = y := by unfold planar_necklace_two_parallel_cuts_six_points_med3 rw [min_eq_right hyx, min_eq_right hzy, max_eq_left hyx, max_eq_left (hzy.trans hyx)]; ring
med3 is always one of the three inputs
By totality of the order on real numbers, x, y, z satisfy one of the permutations, hence med3 equals x, y, or z.
rcases le_total x y with hxy | hyx · rcases le_total y z with hyz | hzy · exact Or.inr (Or.inl (planar_necklace_two_parallel_cuts_six_points_med3_xyz hxy hyz)) · rcases le_total x z with hxz | hzx · exact Or.inr (Or.inr (planar_necklace_two_parallel_cuts_six_points_med3_xzy hxz hzy)) · exact Or.inl (planar_necklace_two_parallel_cuts_six_points_med3_zxy hzx hxy) · rcases le_total z x with hzx | hxz · rcases le_total y z with hyz | hzy · exact Or.inr (Or.inr (planar_necklace_two_parallel_cuts_six_points_med3_yzx hyz hzx)) · exact Or.inr (Or.inl (planar_necklace_two_parallel_cuts_six_points_med3_zyx hzy hyx)) · exact Or.inl (planar_necklace_two_parallel_cuts_six_points_med3_yxz hyx hxz)
if med3 is x, then x lies between y and z
Evaluating med3 across all permutations, equality to x implies either y ≤ x ≤ z or z ≤ x ≤ y.
rcases le_total x y with hxy | hyx · rcases le_total y z with hyz | hzy · rw [planar_necklace_two_parallel_cuts_six_points_med3_xyz hxy hyz] at h exact Or.inl ⟨by linarith, by linarith⟩ · rcases le_total x z with hxz | hzx · rw [planar_necklace_two_parallel_cuts_six_points_med3_xzy hxz hzy] at h exact Or.inr ⟨by linarith, by linarith⟩ · exact Or.inr ⟨hzx, hxy⟩ · rcases le_total z x with hzx | hxz · rcases le_total y z with hyz | hzy · rw [planar_necklace_two_parallel_cuts_six_points_med3_yzx hyz hzx] at h exact Or.inl ⟨by linarith, by linarith⟩ · rw [planar_necklace_two_parallel_cuts_six_points_med3_zyx hzy hyx] at h exact Or.inr ⟨hzx, by linarith⟩ · rw [planar_necklace_two_parallel_cuts_six_points_med3_yxz hyx hxz] at h exact Or.inl ⟨hyx, hxz⟩
med3 is invariant under transposing the first two arguments and under reversing all three
Symmetry and associativity of min and max imply med3(x, y, z) = med3(y, x, z) and med3(x, y, z) = med3(z, y, x).
unfold planar_necklace_two_parallel_cuts_six_points_med3 rw [min_comm x y, max_comm x y]; ring lemma planar_necklace_two_parallel_cuts_six_points_med3_rev (x y z : ℝ) : planar_necklace_two_parallel_cuts_six_points_med3 x y z = planar_necklace_two_parallel_cuts_six_points_med3 z y x := by unfold planar_necklace_two_parallel_cuts_six_points_med3 have h1 : min (min x y) z = min (min z y) x := by rw [min_assoc, min_comm x (min y z), min_comm y z] have h2 : max (max x y) z = max (max z y) x := by rw [max_assoc, max_comm x (max y z), max_comm y z] rw [h1,h2]; ring
if med3 is y or z, it lies between the other two inputs
Applying the symmetry of med3 reduces this to the case where med3 equals the first argument.
have h' : planar_necklace_two_parallel_cuts_six_points_med3 y x z = y := by rw [← planar_necklace_two_parallel_cuts_six_points_med3_comm12]; exact h exact planar_necklace_two_parallel_cuts_six_points_med3_eq_left h' lemma planar_necklace_two_parallel_cuts_six_points_med3_eq_right {x y z : ℝ} (h : planar_necklace_two_parallel_cuts_six_points_med3 x y z = z) : (x ≤ z ∧ z ≤ y) ∨ (y ≤ z ∧ z ≤ x) := by have h' : planar_necklace_two_parallel_cuts_six_points_med3 z y x = z := by rw [← planar_necklace_two_parallel_cuts_six_points_med3_rev]; exact h rcases planar_necklace_two_parallel_cuts_six_points_med3_eq_left h' with ⟨a,b⟩ | ⟨a,b⟩ · exact Or.inr ⟨a,b⟩ · exact Or.inl ⟨a,b⟩
three distinct points can be sorted as low, mid, hi relative to their median
Using the median properties, one point evaluates to the median, while the other two lie on opposite sides of it.
rcases planar_necklace_two_parallel_cuts_six_points_med3_mem (f p0) (f p1) (f p2) with h | h | h · rcases planar_necklace_two_parallel_cuts_six_points_med3_eq_left h with ⟨hle,hge⟩ | ⟨hle,hge⟩ · exact ⟨p1,p0,p2, h01.symm, h12, h02, by ext x; simp [Finset.mem_insert, Finset.mem_singleton, or_comm, or_left_comm, or_assoc], le_trans hle (le_of_eq h.symm), h.symm, le_trans (le_of_eq h) hge⟩ · exact ⟨p2,p0,p1, h02.symm, h12.symm, h01, by ext x; simp [Finset.mem_insert, Finset.mem_singleton, or_comm, or_left_comm, or_assoc], le_trans hle (le_of_eq h.symm), h.symm, le_trans (le_of_eq h) hge⟩ · rcases planar_necklace_two_parallel_cuts_six_points_med3_eq_mid h with ⟨hle,hge⟩ | ⟨hle,hge⟩ · exact ⟨p0,p1,p2, h01, h02, h12, by ext x; simp [Finset.mem_insert, Finset.mem_singleton, or_comm, or_left_comm, or_assoc], le_trans hle (le_of_eq h.symm), h.symm, le_trans (le_of_eq h) hge⟩ · exact ⟨p2,p1,p0, h12.symm, h02.symm, h01.symm, by ext x; simp [Finset.mem_insert, Finset.mem_singleton, or_comm, or_left_comm, or_assoc], le_trans hle (le_of_eq h.symm), h.symm, le_trans (le_of_eq h) hge⟩ · rcases planar_necklace_two_parallel_cuts_six_points_med3_eq_right h with ⟨hle,hge⟩ | ⟨hle,hge⟩ · exact ⟨p0,p2,p1, h02, h01, h12.symm, by ext x; simp [Finset.mem_insert, Finset.mem_singleton, or_comm, or_left_comm, or_assoc], le_trans hle (le_of_eq h.symm), h.symm, le_trans (le_of_eq h) hge⟩ · exact ⟨p1,p2,p0, h12, h01.symm, h02.symm, by ext x; simp [Finset.mem_insert, Finset.mem_singleton, or_comm, or_left_comm, or_assoc], le_trans hle (le_of_eq h.symm), h.symm, le_trans (le_of_eq h) hge⟩
projection onto u is linear, continuous, and odd
The dot product projection is linear and continuous, making the projected median an odd and continuous function of u.
simp [planar_necklace_two_parallel_cuts_six_points_proj]; ring lemma planar_necklace_two_parallel_cuts_six_points_continuous_medproj (a b c : ℝ × ℝ) : Continuous (fun u : ℝ × ℝ => planar_necklace_two_parallel_cuts_six_points_med3 (planar_necklace_two_parallel_cuts_six_points_proj u a) (planar_necklace_two_parallel_cuts_six_points_proj u b) (planar_necklace_two_parallel_cuts_six_points_proj u c)) := by unfold planar_necklace_two_parallel_cuts_six_points_med3 planar_necklace_two_parallel_cuts_six_points_proj continuity lemma planar_necklace_two_parallel_cuts_six_points_medproj_neg (u : ℝ × ℝ) (a b c : ℝ × ℝ) : planar_necklace_two_parallel_cuts_six_points_med3 (planar_necklace_two_parallel_cuts_six_points_proj (-u) a) (planar_necklace_two_parallel_cuts_six_points_proj (-u) b) (planar_necklace_two_parallel_cuts_six_points_proj (-u) c) = - planar_necklace_two_parallel_cuts_six_points_med3 (planar_necklace_two_parallel_cuts_six_points_proj u a) (planar_necklace_two_parallel_cuts_six_points_proj u b) (planar_necklace_two_parallel_cuts_six_points_proj u c) := by simp only [planar_necklace_two_parallel_cuts_six_points_proj_neg] exact planar_necklace_two_parallel_cuts_six_points_med3_neg _ _ _
there exists a non-zero direction u where red and blue median projections coincide
The difference of red and blue projected medians on the unit circle is an odd continuous function G(θ), so G(π) = -G(0). By the intermediate value theorem, G has a zero, giving the required direction vector u ≠ 0.
let F : ℝ × ℝ → ℝ := fun u => planar_necklace_two_parallel_cuts_six_points_med3 (planar_necklace_two_parallel_cuts_six_points_proj u a0) (planar_necklace_two_parallel_cuts_six_points_proj u a1) (planar_necklace_two_parallel_cuts_six_points_proj u a2) - planar_necklace_two_parallel_cuts_six_points_med3 (planar_necklace_two_parallel_cuts_six_points_proj u b0) (planar_necklace_two_parallel_cuts_six_points_proj u b1) (planar_necklace_two_parallel_cuts_six_points_proj u b2) have hFcont : Continuous F := (planar_necklace_two_parallel_cuts_six_points_continuous_medproj a0 a1 a2).sub (planar_necklace_two_parallel_cuts_six_points_continuous_medproj b0 b1 b2) have hFneg : ∀ u, F (-u) = - F u := by intro u simp only [F, planar_necklace_two_parallel_cuts_six_points_medproj_neg]; ring let G : ℝ → ℝ := fun θ => F (planar_necklace_two_parallel_cuts_six_points_circ θ) have hGcont : Continuous G := hFcont.comp (by unfold planar_necklace_two_parallel_cuts_six_points_circ; continuity) have hGpi : G Real.pi = - G 0 := by have hc : planar_necklace_two_parallel_cuts_six_points_circ Real.pi = - planar_necklace_two_parallel_cuts_six_points_circ 0 := by simp [planar_necklace_two_parallel_cuts_six_points_circ, Real.cos_pi, Real.sin_pi] show F (planar_necklace_two_parallel_cuts_six_points_circ Real.pi) = - F (planar_necklace_two_parallel_cuts_six_points_circ 0) rw [hc, hFneg] have hzero : ∃ θ : ℝ, G θ = 0 := by rcases le_total (G 0) 0 with hle | hge · have hmem : (0:ℝ) ∈ Set.Icc (G 0) (G Real.pi) := by rw [Set.mem_Icc]; constructor <;> linarith obtain ⟨θ, hθ, hθeq⟩ := intermediate_value_Icc (le_of_lt Real.pi_pos) hGcont.continuousOn hmem exact ⟨θ, hθeq⟩ · have hmem : (0:ℝ) ∈ Set.Icc (G Real.pi) (G 0) := by rw [Set.mem_Icc]; constructor <;> linarith obtain ⟨θ, hθ, hθeq⟩ := intermediate_value_Icc' (le_of_lt Real.pi_pos) hGcont.continuousOn hmem exact ⟨θ, hθeq⟩ obtain ⟨θ, hθ⟩ := hzero refine ⟨planar_necklace_two_parallel_cuts_six_points_circ θ, ?_, ?_⟩ · intro h have hcos : Real.cos θ = 0 := by simpa [planar_necklace_two_parallel_cuts_six_points_circ] using congrArg Prod.fst h have hsin : Real.sin θ = 0 := by simpa [planar_necklace_two_parallel_cuts_six_points_circ] using congrArg Prod.snd h have h1 : Real.cos θ ^ 2 + Real.sin θ ^ 2 = 1 := Real.cos_sq_add_sin_sq θ rw [hcos, hsin] at h1; norm_num at h1 · simp only [G, F] at hθ; linarith
filtering a three-element set by distinct region indices yields singletons
Each region index 0, 1, 2 is assigned to exactly one of the three points, so filtering by any index isolates that point.
ext p; simp only [Finset.mem_filter, Finset.mem_insert, Finset.mem_singleton] constructor · rintro ⟨rfl | rfl | rfl, hp⟩ · rfl · rw [hb] at hp; exact absurd hp (by decide) · rw [hc] at hp; exact absurd hp (by decide) · rintro rfl; exact ⟨Or.inl rfl, ha⟩ lemma planar_necklace_two_parallel_cuts_six_points_filter_three_one {α : Type} [DecidableEq α] (a b c : α) (f : α → Fin 3) (ha : f a = 0) (hb : f b = 1) (hc : f c = 2) : ({a,b,c} : Finset α).filter (fun p => f p = 1) = {b} := by ext p; simp only [Finset.mem_filter, Finset.mem_insert, Finset.mem_singleton] constructor · rintro ⟨rfl | rfl | rfl, hp⟩ · rw [ha] at hp; exact absurd hp (by decide) · rfl · rw [hc] at hp; exact absurd hp (by decide) · rintro rfl; exact ⟨Or.inr (Or.inl rfl), hb⟩ lemma planar_necklace_two_parallel_cuts_six_points_filter_three_two {α : Type} [DecidableEq α] (a b c : α) (f : α → Fin 3) (ha : f a = 0) (hb : f b = 1) (hc : f c = 2) : ({a,b,c} : Finset α).filter (fun p => f p = 2) = {c} := by ext p; simp only [Finset.mem_filter, Finset.mem_insert, Finset.mem_singleton] constructor · rintro ⟨rfl | rfl | rfl, hp⟩ · rw [ha] at hp; exact absurd hp (by decide) · rw [hb] at hp; exact absurd hp (by decide) · rfl · rintro rfl; exact ⟨Or.inr (Or.inr rfl), hc⟩
extract the three red points and three blue points
From the cardinality assumptions, there are three distinct red points and three distinct blue points in P.
classical rw [Finset.card_eq_three] at h_red obtain ⟨r0, r1, r2, hr01, hr02, hr12, hR⟩ := h_red rw [Finset.card_eq_three] at h_blue obtain ⟨b0, b1, b2, hb01, hb02, hb12, hB⟩ := h_blue have hr0R : r0 ∈ P.filter (fun p => c p = 0) := by rw [hR]; simp have hr1R : r1 ∈ P.filter (fun p => c p = 0) := by rw [hR]; simp have hr2R : r2 ∈ P.filter (fun p => c p = 0) := by rw [hR]; simp have hb0B : b0 ∈ P.filter (fun p => c p = 1) := by rw [hB]; simp have hb1B : b1 ∈ P.filter (fun p => c p = 1) := by rw [hB]; simp have hb2B : b2 ∈ P.filter (fun p => c p = 1) := by rw [hB]; simp have hcr0 : c r0 = 0 := (Finset.mem_filter.mp hr0R).2 have hcr1 : c r1 = 0 := (Finset.mem_filter.mp hr1R).2 have hcr2 : c r2 = 0 := (Finset.mem_filter.mp hr2R).2 have hcb0 : c b0 = 1 := (Finset.mem_filter.mp hb0B).2 have hcb1 : c b1 = 1 := (Finset.mem_filter.mp hb1B).2 have hcb2 : c b2 = 1 := (Finset.mem_filter.mp hb2B).2
find a direction u and common median threshold s
Apply the antipodal median theorem to obtain u ≠ 0 and define φ as the projection onto u, setting s to be the common median.
obtain ⟨u, hu_ne, hu_eq⟩ := planar_necklace_two_parallel_cuts_six_points_exists_median_eq r0 r1 r2 b0 b1 b2 let φ : (ℝ × ℝ) →ₗ[ℝ] ℝ := { toFun := fun p => planar_necklace_two_parallel_cuts_six_points_proj u p map_add' := by intro a b; simp [planar_necklace_two_parallel_cuts_six_points_proj]; ring map_smul' := by intro a b; simp [planar_necklace_two_parallel_cuts_six_points_proj]; ring } have hφ : ∀ p, φ p = planar_necklace_two_parallel_cuts_six_points_proj u p := fun p => rfl have hs_eq : planar_necklace_two_parallel_cuts_six_points_med3 (φ r0) (φ r1) (φ r2) = planar_necklace_two_parallel_cuts_six_points_med3 (φ b0) (φ b1) (φ b2) := by simpa [hφ] using hu_eq let s : ℝ := planar_necklace_two_parallel_cuts_six_points_med3 (φ r0) (φ r1) (φ r2)
order the red points and blue points with respect to s
Sort the three red points into rlo, rmid, rhi and the blue points into blo, bmid, bhi, with the middle points projecting to s.
obtain ⟨rlo, rmid, rhi, hrlo_mid, hrlo_hi, hrmid_hi, hrset, hrle, hrmeq, hrge⟩ := planar_necklace_two_parallel_cuts_six_points_ordered_triple (fun p : ℝ × ℝ => φ p) hr01 hr02 hr12 obtain ⟨blo, bmid, bhi, hblo_mid, hblo_hi, hbmid_hi, hbset, hble, hbmeq, hbge⟩ := planar_necklace_two_parallel_cuts_six_points_ordered_triple (fun p : ℝ × ℝ => φ p) hb01 hb02 hb12 have hrmeq' : φ rmid = s := hrmeq have hs_eq' : s = planar_necklace_two_parallel_cuts_six_points_med3 (φ b0) (φ b1) (φ b2) := hs_eq have hbmeq' : φ bmid = s := by show φ bmid = planar_necklace_two_parallel_cuts_six_points_med3 (φ r0) (φ r1) (φ r2) rw [hbmeq, hs_eq] have hble' : φ blo ≤ s := by rw [hs_eq']; exact hble have hbge' : s ≤ φ bhi := by rw [hs_eq']; exact hbge have hrloR : rlo ∈ P.filter (fun p => c p = 0) := by have h1 : rlo ∈ ({rlo,rmid,rhi} : Finset (ℝ × ℝ)) := by simp rw [hrset] at h1 rwa [← hR] at h1 have hrmidR : rmid ∈ P.filter (fun p => c p = 0) := by have h1 : rmid ∈ ({rlo,rmid,rhi} : Finset (ℝ × ℝ)) := by simp rw [hrset] at h1 rwa [← hR] at h1 have hrhiR : rhi ∈ P.filter (fun p => c p = 0) := by have h1 : rhi ∈ ({rlo,rmid,rhi} : Finset (ℝ × ℝ)) := by simp rw [hrset] at h1 rwa [← hR] at h1 have hbloB : blo ∈ P.filter (fun p => c p = 1) := by have h1 : blo ∈ ({blo,bmid,bhi} : Finset (ℝ × ℝ)) := by simp rw [hbset] at h1 rwa [← hB] at h1 have hbmidB : bmid ∈ P.filter (fun p => c p = 1) := by have h1 : bmid ∈ ({blo,bmid,bhi} : Finset (ℝ × ℝ)) := by simp rw [hbset] at h1 rwa [← hB] at h1 have hbhiB : bhi ∈ P.filter (fun p => c p = 1) := by have h1 : bhi ∈ ({blo,bmid,bhi} : Finset (ℝ × ℝ)) := by simp rw [hbset] at h1 rwa [← hB] at h1 have hcrlo : c rlo = 0 := (Finset.mem_filter.mp hrloR).2 have hcrmid : c rmid = 0 := (Finset.mem_filter.mp hrmidR).2 have hcrhi : c rhi = 0 := (Finset.mem_filter.mp hrhiR).2 have hcblo : c blo = 1 := (Finset.mem_filter.mp hbloB).2 have hcbmid : c bmid = 1 := (Finset.mem_filter.mp hbmidB).2 have hcbhi : c bhi = 1 := (Finset.mem_filter.mp hbhiB).2 have hne_rb : ∀ (r b : ℝ × ℝ), c r = 0 → c b = 1 → r ≠ b := by intro r b hcr hcb h rw [h] at hcr rw [hcb] at hcr exact absurd hcr (by decide)
define the assignment α and verify point coverage
Assign low points to 0, middle points to 1, and high points to 2, and observe that these six points constitute all of P.
let α : (ℝ × ℝ) → Fin 3 := fun p => if p = rlo then 0 else if p = rmid then 1 else if p = rhi then 2 else if p = blo then 0 else if p = bmid then 1 else if p = bhi then 2 else 0 have hαrlo : α rlo = 0 := by simp [α] have hαrmid : α rmid = 1 := by simp [α, Ne.symm hrlo_mid] have hαrhi : α rhi = 2 := by simp [α, Ne.symm hrlo_hi, Ne.symm hrmid_hi] have hαblo : α blo = 0 := by simp [α, Ne.symm (hne_rb rlo blo hcrlo hcblo), Ne.symm (hne_rb rmid blo hcrmid hcblo), Ne.symm (hne_rb rhi blo hcrhi hcblo)] have hαbmid : α bmid = 1 := by simp [α, Ne.symm (hne_rb rlo bmid hcrlo hcbmid), Ne.symm (hne_rb rmid bmid hcrmid hcbmid), Ne.symm (hne_rb rhi bmid hcrhi hcbmid), Ne.symm hblo_mid] have hαbhi : α bhi = 2 := by simp [α, Ne.symm (hne_rb rlo bhi hcrlo hcbhi), Ne.symm (hne_rb rmid bhi hcrmid hcbhi), Ne.symm (hne_rb rhi bhi hcrhi hcbhi), Ne.symm hblo_hi, Ne.symm hbmid_hi] have hR' : P.filter (fun p => c p = 0) = ({rlo,rmid,rhi} : Finset (ℝ × ℝ)) := by rw [hR]; exact hrset.symm have hB' : P.filter (fun p => c p = 1) = ({blo,bmid,bhi} : Finset (ℝ × ℝ)) := by rw [hB]; exact hbset.symm have hcov : ∀ p ∈ P, p = rlo ∨ p = rmid ∨ p = rhi ∨ p = blo ∨ p = bmid ∨ p = bhi := by intro p hp have hc2 : ∀ q : Fin 2, q = 0 ∨ q = 1 := by decide rcases hc2 (c p) with hc | hc · have hmem : p ∈ ({rlo,rmid,rhi} : Finset (ℝ × ℝ)) := by rw [← hR']; exact Finset.mem_filter.mpr ⟨hp, hc⟩ simp only [Finset.mem_insert, Finset.mem_singleton] at hmem tauto · have hmem : p ∈ ({blo,bmid,bhi} : Finset (ℝ × ℝ)) := by rw [← hB']; exact Finset.mem_filter.mpr ⟨hp, hc⟩ simp only [Finset.mem_insert, Finset.mem_singleton] at hmem tauto
verify consistency of α with two cuts at threshold s
By construction, region 0 points have projection ≤ s, region 1 points have projection = s, and region 2 points have projection ≥ s.
have hcons : ∀ p ∈ P, (α p = 0 → φ p ≤ s) ∧ (α p = 1 → s ≤ φ p ∧ φ p ≤ s) ∧ (α p = 2 → s ≤ φ p) := by intro p hp rcases hcov p hp with h | h | h | h | h | h · rw [h, hαrlo] exact ⟨fun _ => hrle, fun hh => absurd hh (by decide), fun hh => absurd hh (by decide)⟩ · rw [h, hαrmid] exact ⟨fun hh => absurd hh (by decide), fun _ => ⟨le_of_eq hrmeq'.symm, le_of_eq hrmeq'⟩, fun hh => absurd hh (by decide)⟩ · rw [h, hαrhi] exact ⟨fun hh => absurd hh (by decide), fun hh => absurd hh (by decide), fun _ => hrge⟩ · rw [h, hαblo] exact ⟨fun _ => hble', fun hh => absurd hh (by decide), fun hh => absurd hh (by decide)⟩ · rw [h, hαbmid] exact ⟨fun hh => absurd hh (by decide), fun _ => ⟨le_of_eq hbmeq'.symm, le_of_eq hbmeq'⟩, fun hh => absurd hh (by decide)⟩ · rw [h, hαbhi] exact ⟨fun hh => absurd hh (by decide), fun hh => absurd hh (by decide), fun _ => hbge'⟩
each region contains exactly one red point and one blue point
Filtering the red and blue sets by the region indices confirms that each region gets exactly one red and one blue point.
have hfilterR : ∀ i : Fin 3, P.filter (fun p => α p = i ∧ c p = 0) = (P.filter (fun p => c p = 0)).filter (fun p => α p = i) := by intro i; ext p; simp only [Finset.mem_filter]; tauto have hfilterB : ∀ i : Fin 3, P.filter (fun p => α p = i ∧ c p = 1) = (P.filter (fun p => c p = 1)).filter (fun p => α p = i) := by intro i; ext p; simp only [Finset.mem_filter]; tauto have hRf0 : (P.filter (fun p => c p = 0)).filter (fun p => α p = 0) = {rlo} := by rw [hR'] exact planar_necklace_two_parallel_cuts_six_points_filter_three_zero rlo rmid rhi α hαrlo hαrmid hαrhi have hRf1 : (P.filter (fun p => c p = 0)).filter (fun p => α p = 1) = {rmid} := by rw [hR'] exact planar_necklace_two_parallel_cuts_six_points_filter_three_one rlo rmid rhi α hαrlo hαrmid hαrhi have hRf2 : (P.filter (fun p => c p = 0)).filter (fun p => α p = 2) = {rhi} := by rw [hR'] exact planar_necklace_two_parallel_cuts_six_points_filter_three_two rlo rmid rhi α hαrlo hαrmid hαrhi have hBf0 : (P.filter (fun p => c p = 1)).filter (fun p => α p = 0) = {blo} := by rw [hB'] exact planar_necklace_two_parallel_cuts_six_points_filter_three_zero blo bmid bhi α hαblo hαbmid hαbhi have hBf1 : (P.filter (fun p => c p = 1)).filter (fun p => α p = 1) = {bmid} := by rw [hB'] exact planar_necklace_two_parallel_cuts_six_points_filter_three_one blo bmid bhi α hαblo hαbmid hαbhi have hBf2 : (P.filter (fun p => c p = 1)).filter (fun p => α p = 2) = {bhi} := by rw [hB'] exact planar_necklace_two_parallel_cuts_six_points_filter_three_two blo bmid bhi α hαblo hαbmid hαbhi
the linear functional φ is non-zero
Since u ≠ 0, φ(u) is the sum of squares of its components, which is strictly positive.
have hφne : φ ≠ 0 := by intro h0 have hu : φ u = 0 := by rw [h0]; simp have hp : 0 < φ u := by rw [hφ] have hsq : planar_necklace_two_parallel_cuts_six_points_proj u u = u.1 ^ 2 + u.2 ^ 2 := by unfold planar_necklace_two_parallel_cuts_six_points_proj; ring rw [hsq] rcases eq_or_ne u.1 0 with h1 | h1 · rcases eq_or_ne u.2 0 with h2 | h2 · exact absurd (Prod.ext h1 h2) hu_ne · nlinarith [sq_pos_of_ne_zero h2] · nlinarith [sq_pos_of_ne_zero h1] linarith
conclude the theorem
Provide φ, s, s, and α as witnesses satisfying non-zeroness, consistency, and the equal allocation of 1 red and 1 blue point to each region.
refine ⟨φ, s, s, α, hφne, ?_, ?_⟩ · exact ⟨le_refl s, hcons⟩ · intro i refine ⟨?_, ?_⟩ · fin_cases i · show (P.filter (fun p => α p = (0:Fin 3) ∧ c p = 0)).card = 1 rw [hfilterR 0, hRf0]; simp · show (P.filter (fun p => α p = (1:Fin 3) ∧ c p = 0)).card = 1 rw [hfilterR 1, hRf1]; simp · show (P.filter (fun p => α p = (2:Fin 3) ∧ c p = 0)).card = 1 rw [hfilterR 2, hRf2]; simp · fin_cases i · show (P.filter (fun p => α p = (0:Fin 3) ∧ c p = 1)).card = 1 rw [hfilterB 0, hBf0]; simp · show (P.filter (fun p => α p = (1:Fin 3) ∧ c p = 1)).card = 1 rw [hfilterB 1, hBf1]; simp · show (P.filter (fun p => α p = (2:Fin 3) ∧ c p = 1)).card = 1 rw [hfilterB 2, hBf2]; simp
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.
Lean’s trace was cut to the first 400 of 411 tactics.
noncomputable def planar_necklace_two_parallel_cuts_six_points_med3 (x y z : ℝ) : ℝ := x + y + z - min (min x y) z - max (max x y) zlemma planar_necklace_two_parallel_cuts_six_points_med3_neg (x y z : ℝ) : planar_necklace_two_parallel_cuts_six_points_med3 (-x) (-y) (-z) = - planar_necklace_two_parallel_cuts_six_points_med3 x y z := by unfold planar_necklace_two_parallel_cuts_six_points_med3 rw [min_neg_neg, min_neg_neg, max_neg_neg, max_neg_neg]; ringlemma planar_necklace_two_parallel_cuts_six_points_med3_xyz {x y z : ℝ} (hxy : x ≤ y) (hyz : y ≤ z) : planar_necklace_two_parallel_cuts_six_points_med3 x y z = y := by unfold planar_necklace_two_parallel_cuts_six_points_med3 rw [min_eq_left hxy, min_eq_left (hxy.trans hyz), max_eq_right hxy, max_eq_right hyz]; ringlemma planar_necklace_two_parallel_cuts_six_points_med3_xzy {x y z : ℝ} (hxz : x ≤ z) (hzy : z ≤ y) : planar_necklace_two_parallel_cuts_six_points_med3 x y z = z := by unfold planar_necklace_two_parallel_cuts_six_points_med3 rw [min_eq_left (hxz.trans hzy), min_eq_left hxz, max_eq_right (hxz.trans hzy), max_eq_left hzy]; ringlemma planar_necklace_two_parallel_cuts_six_points_med3_yxz {x y z : ℝ} (hyx : y ≤ x) (hxz : x ≤ z) : planar_necklace_two_parallel_cuts_six_points_med3 x y z = x := by unfold planar_necklace_two_parallel_cuts_six_points_med3 rw [min_eq_right hyx, min_eq_left (hyx.trans hxz), max_eq_left hyx, max_eq_right hxz]; ringlemma planar_necklace_two_parallel_cuts_six_points_med3_yzx {x y z : ℝ} (hyz : y ≤ z) (hzx : z ≤ x) : planar_necklace_two_parallel_cuts_six_points_med3 x y z = z := by unfold planar_necklace_two_parallel_cuts_six_points_med3 rw [min_eq_right (hyz.trans hzx), min_eq_left hyz, max_eq_left (hyz.trans hzx), max_eq_left hzx]; ringlemma planar_necklace_two_parallel_cuts_six_points_med3_zxy {x y z : ℝ} (hzx : z ≤ x) (hxy : x ≤ y) : planar_necklace_two_parallel_cuts_six_points_med3 x y z = x := by unfold planar_necklace_two_parallel_cuts_six_points_med3 rw [min_eq_left hxy, min_eq_right hzx, max_eq_right hxy, max_eq_left (hzx.trans hxy)]; ringlemma planar_necklace_two_parallel_cuts_six_points_med3_zyx {x y z : ℝ} (hzy : z ≤ y) (hyx : y ≤ x) : planar_necklace_two_parallel_cuts_six_points_med3 x y z = y := by unfold planar_necklace_two_parallel_cuts_six_points_med3 rw [min_eq_right hyx, min_eq_right hzy, max_eq_left hyx, max_eq_left (hzy.trans hyx)]; ringlemma planar_necklace_two_parallel_cuts_six_points_med3_mem (x y z : ℝ) : planar_necklace_two_parallel_cuts_six_points_med3 x y z = x ∨ planar_necklace_two_parallel_cuts_six_points_med3 x y z = y ∨ planar_necklace_two_parallel_cuts_six_points_med3 x y z = z := by rcases le_total x y with hxy | hyx · rcases le_total y z with hyz | hzy · exact Or.inr (Or.inl (planar_necklace_two_parallel_cuts_six_points_med3_xyz hxy hyz)) · rcases le_total x z with hxz | hzx · exact Or.inr (Or.inr (planar_necklace_two_parallel_cuts_six_points_med3_xzy hxz hzy)) · exact Or.inl (planar_necklace_two_parallel_cuts_six_points_med3_zxy hzx hxy) · rcases le_total z x with hzx | hxz · rcases le_total y z with hyz | hzy · exact Or.inr (Or.inr (planar_necklace_two_parallel_cuts_six_points_med3_yzx hyz hzx)) · exact Or.inr (Or.inl (planar_necklace_two_parallel_cuts_six_points_med3_zyx hzy hyx)) · exact Or.inl (planar_necklace_two_parallel_cuts_six_points_med3_yxz hyx hxz)lemma planar_necklace_two_parallel_cuts_six_points_med3_eq_left {x y z : ℝ} (h : planar_necklace_two_parallel_cuts_six_points_med3 x y z = x) : (y ≤ x ∧ x ≤ z) ∨ (z ≤ x ∧ x ≤ y) := by rcases le_total x y with hxy | hyx · rcases le_total y z with hyz | hzy · rw [planar_necklace_two_parallel_cuts_six_points_med3_xyz hxy hyz] at h exact Or.inl ⟨by linarith, by linarith⟩ · rcases le_total x z with hxz | hzx · rw [planar_necklace_two_parallel_cuts_six_points_med3_xzy hxz hzy] at h exact Or.inr ⟨by linarith, by linarith⟩ · exact Or.inr ⟨hzx, hxy⟩ · rcases le_total z x with hzx | hxz · rcases le_total y z with hyz | hzy · rw [planar_necklace_two_parallel_cuts_six_points_med3_yzx hyz hzx] at h exact Or.inl ⟨by linarith, by linarith⟩ · rw [planar_necklace_two_parallel_cuts_six_points_med3_zyx hzy hyx] at h exact Or.inr ⟨hzx, by linarith⟩ · rw [planar_necklace_two_parallel_cuts_six_points_med3_yxz hyx hxz] at h exact Or.inl ⟨hyx, hxz⟩lemma planar_necklace_two_parallel_cuts_six_points_med3_comm12 (x y z : ℝ) : planar_necklace_two_parallel_cuts_six_points_med3 x y z = planar_necklace_two_parallel_cuts_six_points_med3 y x z := by unfold planar_necklace_two_parallel_cuts_six_points_med3 rw [min_comm x y, max_comm x y]; ringlemma planar_necklace_two_parallel_cuts_six_points_med3_rev (x y z : ℝ) : planar_necklace_two_parallel_cuts_six_points_med3 x y z = planar_necklace_two_parallel_cuts_six_points_med3 z y x := by unfold planar_necklace_two_parallel_cuts_six_points_med3 have h1 : min (min x y) z = min (min z y) x := by rw [min_assoc, min_comm x (min y z), min_comm y z] have h2 : max (max x y) z = max (max z y) x := by rw [max_assoc, max_comm x (max y z), max_comm y z] rw [h1,h2]; ringlemma planar_necklace_two_parallel_cuts_six_points_med3_eq_mid {x y z : ℝ} (h : planar_necklace_two_parallel_cuts_six_points_med3 x y z = y) : (x ≤ y ∧ y ≤ z) ∨ (z ≤ y ∧ y ≤ x) := by have h' : planar_necklace_two_parallel_cuts_six_points_med3 y x z = y := by rw [← planar_necklace_two_parallel_cuts_six_points_med3_comm12]; exact h exact planar_necklace_two_parallel_cuts_six_points_med3_eq_left h'lemma planar_necklace_two_parallel_cuts_six_points_med3_eq_right {x y z : ℝ} (h : planar_necklace_two_parallel_cuts_six_points_med3 x y z = z) : (x ≤ z ∧ z ≤ y) ∨ (y ≤ z ∧ z ≤ x) := by have h' : planar_necklace_two_parallel_cuts_six_points_med3 z y x = z := by rw [← planar_necklace_two_parallel_cuts_six_points_med3_rev]; exact h rcases planar_necklace_two_parallel_cuts_six_points_med3_eq_left h' with ⟨a,b⟩ | ⟨a,b⟩ · exact Or.inr ⟨a,b⟩ · exact Or.inl ⟨a,b⟩lemma planar_necklace_two_parallel_cuts_six_points_ordered_triple {α : Type} [DecidableEq α] (f : α → ℝ) {p0 p1 p2 : α} (h01 : p0 ≠ p1) (h02 : p0 ≠ p2) (h12 : p1 ≠ p2) : ∃ a b c : α, a ≠ b ∧ a ≠ c ∧ b ≠ c ∧ ({a,b,c} : Finset α) = {p0,p1,p2} ∧ f a ≤ planar_necklace_two_parallel_cuts_six_points_med3 (f p0) (f p1) (f p2) ∧ f b = planar_necklace_two_parallel_cuts_six_points_med3 (f p0) (f p1) (f p2) ∧ planar_necklace_two_parallel_cuts_six_points_med3 (f p0) (f p1) (f p2) ≤ f c := by rcases planar_necklace_two_parallel_cuts_six_points_med3_mem (f p0) (f p1) (f p2) with h | h | h · rcases planar_necklace_two_parallel_cuts_six_points_med3_eq_left h with ⟨hle,hge⟩ | ⟨hle,hge⟩ · exact ⟨p1,p0,p2, h01.symm, h12, h02, by ext x; simp [Finset.mem_insert, Finset.mem_singleton, or_comm, or_left_comm, or_assoc], le_trans hle (le_of_eq h.symm), h.symm, le_trans (le_of_eq h) hge⟩ · exact ⟨p2,p0,p1, h02.symm, h12.symm, h01, by ext x; simp [Finset.mem_insert, Finset.mem_singleton, or_comm, or_left_comm, or_assoc], le_trans hle (le_of_eq h.symm), h.symm, le_trans (le_of_eq h) hge⟩ · rcases planar_necklace_two_parallel_cuts_six_points_med3_eq_mid h with ⟨hle,hge⟩ | ⟨hle,hge⟩ · exact ⟨p0,p1,p2, h01, h02, h12, by ext x; simp [Finset.mem_insert, Finset.mem_singleton, or_comm, or_left_comm, or_assoc], le_trans hle (le_of_eq h.symm), h.symm, le_trans (le_of_eq h) hge⟩ · exact ⟨p2,p1,p0, h12.symm, h02.symm, h01.symm, by ext x; simp [Finset.mem_insert, Finset.mem_singleton, or_comm, or_left_comm, or_assoc], le_trans hle (le_of_eq h.symm), h.symm, le_trans (le_of_eq h) hge⟩ · rcases planar_necklace_two_parallel_cuts_six_points_med3_eq_right h with ⟨hle,hge⟩ | ⟨hle,hge⟩ · exact ⟨p0,p2,p1, h02, h01, h12.symm, by ext x; simp [Finset.mem_insert, Finset.mem_singleton, or_comm, or_left_comm, or_assoc], le_trans hle (le_of_eq h.symm), h.symm, le_trans (le_of_eq h) hge⟩ · exact ⟨p1,p2,p0, h12, h01.symm, h02.symm, by ext x; simp [Finset.mem_insert, Finset.mem_singleton, or_comm, or_left_comm, or_assoc], le_trans hle (le_of_eq h.symm), h.symm, le_trans (le_of_eq h) hge⟩noncomputable def planar_necklace_two_parallel_cuts_six_points_proj (u p : ℝ × ℝ) : ℝ := p.1 * u.1 + p.2 * u.2lemma planar_necklace_two_parallel_cuts_six_points_proj_neg (u p : ℝ × ℝ) : planar_necklace_two_parallel_cuts_six_points_proj (-u) p = - planar_necklace_two_parallel_cuts_six_points_proj u p := by simp [planar_necklace_two_parallel_cuts_six_points_proj]; ringlemma planar_necklace_two_parallel_cuts_six_points_continuous_medproj (a b c : ℝ × ℝ) : Continuous (fun u : ℝ × ℝ => planar_necklace_two_parallel_cuts_six_points_med3 (planar_necklace_two_parallel_cuts_six_points_proj u a) (planar_necklace_two_parallel_cuts_six_points_proj u b) (planar_necklace_two_parallel_cuts_six_points_proj u c)) := by unfold planar_necklace_two_parallel_cuts_six_points_med3 planar_necklace_two_parallel_cuts_six_points_proj continuitylemma planar_necklace_two_parallel_cuts_six_points_medproj_neg (u : ℝ × ℝ) (a b c : ℝ × ℝ) : planar_necklace_two_parallel_cuts_six_points_med3 (planar_necklace_two_parallel_cuts_six_points_proj (-u) a) (planar_necklace_two_parallel_cuts_six_points_proj (-u) b) (planar_necklace_two_parallel_cuts_six_points_proj (-u) c) = - planar_necklace_two_parallel_cuts_six_points_med3 (planar_necklace_two_parallel_cuts_six_points_proj u a) (planar_necklace_two_parallel_cuts_six_points_proj u b) (planar_necklace_two_parallel_cuts_six_points_proj u c) := by simp only [planar_necklace_two_parallel_cuts_six_points_proj_neg] exact planar_necklace_two_parallel_cuts_six_points_med3_neg _ _ _noncomputable def planar_necklace_two_parallel_cuts_six_points_circ (θ : ℝ) : ℝ × ℝ := (Real.cos θ, Real.sin θ)lemma planar_necklace_two_parallel_cuts_six_points_exists_median_eq (a0 a1 a2 b0 b1 b2 : ℝ × ℝ) : ∃ u : ℝ × ℝ, u ≠ 0 ∧ planar_necklace_two_parallel_cuts_six_points_med3 (planar_necklace_two_parallel_cuts_six_points_proj u a0) (planar_necklace_two_parallel_cuts_six_points_proj u a1) (planar_necklace_two_parallel_cuts_six_points_proj u a2) = planar_necklace_two_parallel_cuts_six_points_med3 (planar_necklace_two_parallel_cuts_six_points_proj u b0) (planar_necklace_two_parallel_cuts_six_points_proj u b1) (planar_necklace_two_parallel_cuts_six_points_proj u b2) := by let F : ℝ × ℝ → ℝ := fun u => planar_necklace_two_parallel_cuts_six_points_med3 (planar_necklace_two_parallel_cuts_six_points_proj u a0) (planar_necklace_two_parallel_cuts_six_points_proj u a1) (planar_necklace_two_parallel_cuts_six_points_proj u a2) - planar_necklace_two_parallel_cuts_six_points_med3 (planar_necklace_two_parallel_cuts_six_points_proj u b0) (planar_necklace_two_parallel_cuts_six_points_proj u b1) (planar_necklace_two_parallel_cuts_six_points_proj u b2) have hFcont : Continuous F := (planar_necklace_two_parallel_cuts_six_points_continuous_medproj a0 a1 a2).sub (planar_necklace_two_parallel_cuts_six_points_continuous_medproj b0 b1 b2) have hFneg : ∀ u, F (-u) = - F u := by intro u simp only [F, planar_necklace_two_parallel_cuts_six_points_medproj_neg]; ring let G : ℝ → ℝ := fun θ => F (planar_necklace_two_parallel_cuts_six_points_circ θ) have hGcont : Continuous G := hFcont.comp (by unfold planar_necklace_two_parallel_cuts_six_points_circ; continuity) have hGpi : G Real.pi = - G 0 := by have hc : planar_necklace_two_parallel_cuts_six_points_circ Real.pi = - planar_necklace_two_parallel_cuts_six_points_circ 0 := by simp [planar_necklace_two_parallel_cuts_six_points_circ, Real.cos_pi, Real.sin_pi] show F (planar_necklace_two_parallel_cuts_six_points_circ Real.pi) = - F (planar_necklace_two_parallel_cuts_six_points_circ 0) rw [hc, hFneg] have hzero : ∃ θ : ℝ, G θ = 0 := by rcases le_total (G 0) 0 with hle | hge · have hmem : (0:ℝ) ∈ Set.Icc (G 0) (G Real.pi) := by rw [Set.mem_Icc]; constructor <;> linarith obtain ⟨θ, hθ, hθeq⟩ := intermediate_value_Icc (le_of_lt Real.pi_pos) hGcont.continuousOn hmem exact ⟨θ, hθeq⟩ · have hmem : (0:ℝ) ∈ Set.Icc (G Real.pi) (G 0) := by rw [Set.mem_Icc]; constructor <;> linarith obtain ⟨θ, hθ, hθeq⟩ := intermediate_value_Icc' (le_of_lt Real.pi_pos) hGcont.continuousOn hmem exact ⟨θ, hθeq⟩ obtain ⟨θ, hθ⟩ := hzero refine ⟨planar_necklace_two_parallel_cuts_six_points_circ θ, ?_, ?_⟩ · intro h have hcos : Real.cos θ = 0 := by simpa [planar_necklace_two_parallel_cuts_six_points_circ] using congrArg Prod.fst h have hsin : Real.sin θ = 0 := by simpa [planar_necklace_two_parallel_cuts_six_points_circ] using congrArg Prod.snd h have h1 : Real.cos θ ^ 2 + Real.sin θ ^ 2 = 1 := Real.cos_sq_add_sin_sq θ rw [hcos, hsin] at h1; norm_num at h1 · simp only [G, F] at hθ; linarithlemma planar_necklace_two_parallel_cuts_six_points_filter_three_zero {α : Type} [DecidableEq α] (a b c : α) (f : α → Fin 3) (ha : f a = 0) (hb : f b = 1) (hc : f c = 2) : ({a,b,c} : Finset α).filter (fun p => f p = 0) = {a} := by ext p; simp only [Finset.mem_filter, Finset.mem_insert, Finset.mem_singleton] constructor · rintro ⟨rfl | rfl | rfl, hp⟩ · rfl · rw [hb] at hp; exact absurd hp (by decide) · rw [hc] at hp; exact absurd hp (by decide) · rintro rfl; exact ⟨Or.inl rfl, ha⟩lemma planar_necklace_two_parallel_cuts_six_points_filter_three_one {α : Type} [DecidableEq α] (a b c : α) (f : α → Fin 3) (ha : f a = 0) (hb : f b = 1) (hc : f c = 2) : ({a,b,c} : Finset α).filter (fun p => f p = 1) = {b} := by ext p; simp only [Finset.mem_filter, Finset.mem_insert, Finset.mem_singleton] constructor · rintro ⟨rfl | rfl | rfl, hp⟩ · rw [ha] at hp; exact absurd hp (by decide) · rfl · rw [hc] at hp; exact absurd hp (by decide) · rintro rfl; exact ⟨Or.inr (Or.inl rfl), hb⟩lemma planar_necklace_two_parallel_cuts_six_points_filter_three_two {α : Type} [DecidableEq α] (a b c : α) (f : α → Fin 3) (ha : f a = 0) (hb : f b = 1) (hc : f c = 2) : ({a,b,c} : Finset α).filter (fun p => f p = 2) = {c} := by ext p; simp only [Finset.mem_filter, Finset.mem_insert, Finset.mem_singleton] constructor · rintro ⟨rfl | rfl | rfl, hp⟩ · rw [ha] at hp; exact absurd hp (by decide) · rw [hb] at hp; exact absurd hp (by decide) · rfl · rintro rfl; exact ⟨Or.inr (Or.inr rfl), hc⟩/-- For any 6 points in the plane with 3 red and 3 blue, there exist two parallel cuts fairly allocating 1 red and 1 blue point to each of three regions. -/theorem planar_necklace_two_parallel_cuts_six_points (P : Finset (ℝ × ℝ)) (c : (ℝ × ℝ) → Fin 2) (hP_card : P.card = 6) (h_red : (P.filter (fun p => c p = 0)).card = 3) (h_blue : (P.filter (fun p => c p = 1)).card = 3) : ∃ (φ : (ℝ × ℝ) →ₗ[ℝ] ℝ) (t₁ t₂ : ℝ) (α : (ℝ × ℝ) → Fin 3), φ ≠ 0 ∧ is_parallel_two_cut_consistent P φ t₁ t₂ α ∧ ∀ i : Fin 3, (P.filter (fun p => α p = i ∧ c p = 0)).card = 1 ∧ (P.filter (fun p => α p = i ∧ c p = 1)).card = 1 := by classical rw [Finset.card_eq_three] at h_red obtain ⟨r0, r1, r2, hr01, hr02, hr12, hR⟩ := h_red rw [Finset.card_eq_three] at h_blue obtain ⟨b0, b1, b2, hb01, hb02, hb12, hB⟩ := h_blue have hr0R : r0 ∈ P.filter (fun p => c p = 0) := by rw [hR]; simp have hr1R : r1 ∈ P.filter (fun p => c p = 0) := by rw [hR]; simp have hr2R : r2 ∈ P.filter (fun p => c p = 0) := by rw [hR]; simp have hb0B : b0 ∈ P.filter (fun p => c p = 1) := by rw [hB]; simp have hb1B : b1 ∈ P.filter (fun p => c p = 1) := by rw [hB]; simp have hb2B : b2 ∈ P.filter (fun p => c p = 1) := by rw [hB]; simp have hcr0 : c r0 = 0 := (Finset.mem_filter.mp hr0R).2 have hcr1 : c r1 = 0 := (Finset.mem_filter.mp hr1R).2 have hcr2 : c r2 = 0 := (Finset.mem_filter.mp hr2R).2 have hcb0 : c b0 = 1 := (Finset.mem_filter.mp hb0B).2 have hcb1 : c b1 = 1 := (Finset.mem_filter.mp hb1B).2 have hcb2 : c b2 = 1 := (Finset.mem_filter.mp hb2B).2 obtain ⟨u, hu_ne, hu_eq⟩ := planar_necklace_two_parallel_cuts_six_points_exists_median_eq r0 r1 r2 b0 b1 b2 let φ : (ℝ × ℝ) →ₗ[ℝ] ℝ := { toFun := fun p => planar_necklace_two_parallel_cuts_six_points_proj u p map_add' := by intro a b; simp [planar_necklace_two_parallel_cuts_six_points_proj]; ring map_smul' := by intro a b; simp [planar_necklace_two_parallel_cuts_six_points_proj]; ring } have hφ : ∀ p, φ p = planar_necklace_two_parallel_cuts_six_points_proj u p := fun p => rfl have hs_eq : planar_necklace_two_parallel_cuts_six_points_med3 (φ r0) (φ r1) (φ r2) = planar_necklace_two_parallel_cuts_six_points_med3 (φ b0) (φ b1) (φ b2) := by simpa [hφ] using hu_eq let s : ℝ := planar_necklace_two_parallel_cuts_six_points_med3 (φ r0) (φ r1) (φ r2) obtain ⟨rlo, rmid, rhi, hrlo_mid, hrlo_hi, hrmid_hi, hrset, hrle, hrmeq, hrge⟩ := planar_necklace_two_parallel_cuts_six_points_ordered_triple (fun p : ℝ × ℝ => φ p) hr01 hr02 hr12 obtain ⟨blo, bmid, bhi, hblo_mid, hblo_hi, hbmid_hi, hbset, hble, hbmeq, hbge⟩ := planar_necklace_two_parallel_cuts_six_points_ordered_triple (fun p : ℝ × ℝ => φ p) hb01 hb02 hb12 have hrmeq' : φ rmid = s := hrmeq have hs_eq' : s = planar_necklace_two_parallel_cuts_six_points_med3 (φ b0) (φ b1) (φ b2) := hs_eq have hbmeq' : φ bmid = s := by show φ bmid = planar_necklace_two_parallel_cuts_six_points_med3 (φ r0) (φ r1) (φ r2) rw [hbmeq, hs_eq] have hble' : φ blo ≤ s := by rw [hs_eq']; exact hble have hbge' : s ≤ φ bhi := by rw [hs_eq']; exact hbge have hrloR : rlo ∈ P.filter (fun p => c p = 0) := by have h1 : rlo ∈ ({rlo,rmid,rhi} : Finset (ℝ × ℝ)) := by simp rw [hrset] at h1 rwa [← hR] at h1 have hrmidR : rmid ∈ P.filter (fun p => c p = 0) := by have h1 : rmid ∈ ({rlo,rmid,rhi} : Finset (ℝ × ℝ)) := by simp rw [hrset] at h1 rwa [← hR] at h1 have hrhiR : rhi ∈ P.filter (fun p => c p = 0) := by have h1 : rhi ∈ ({rlo,rmid,rhi} : Finset (ℝ × ℝ)) := by simp rw [hrset] at h1 rwa [← hR] at h1 have hbloB : blo ∈ P.filter (fun p => c p = 1) := by have h1 : blo ∈ ({blo,bmid,bhi} : Finset (ℝ × ℝ)) := by simp rw [hbset] at h1 rwa [← hB] at h1 have hbmidB : bmid ∈ P.filter (fun p => c p = 1) := by have h1 : bmid ∈ ({blo,bmid,bhi} : Finset (ℝ × ℝ)) := by simp rw [hbset] at h1 rwa [← hB] at h1 have hbhiB : bhi ∈ P.filter (fun p => c p = 1) := by have h1 : bhi ∈ ({blo,bmid,bhi} : Finset (ℝ × ℝ)) := by simp rw [hbset] at h1 rwa [← hB] at h1 have hcrlo : c rlo = 0 := (Finset.mem_filter.mp hrloR).2 have hcrmid : c rmid = 0 := (Finset.mem_filter.mp hrmidR).2 have hcrhi : c rhi = 0 := (Finset.mem_filter.mp hrhiR).2 have hcblo : c blo = 1 := (Finset.mem_filter.mp hbloB).2 have hcbmid : c bmid = 1 := (Finset.mem_filter.mp hbmidB).2 have hcbhi : c bhi = 1 := (Finset.mem_filter.mp hbhiB).2 have hne_rb : ∀ (r b : ℝ × ℝ), c r = 0 → c b = 1 → r ≠ b := by intro r b hcr hcb h rw [h] at hcr rw [hcb] at hcr exact absurd hcr (by decide) let α : (ℝ × ℝ) → Fin 3 := fun p => if p = rlo then 0 else if p = rmid then 1 else if p = rhi then 2 else if p = blo then 0 else if p = bmid then 1 else if p = bhi then 2 else 0 have hαrlo : α rlo = 0 := by simp [α] have hαrmid : α rmid = 1 := by simp [α, Ne.symm hrlo_mid] have hαrhi : α rhi = 2 := by simp [α, Ne.symm hrlo_hi, Ne.symm hrmid_hi] have hαblo : α blo = 0 := by simp [α, Ne.symm (hne_rb rlo blo hcrlo hcblo), Ne.symm (hne_rb rmid blo hcrmid hcblo), Ne.symm (hne_rb rhi blo hcrhi hcblo)] have hαbmid : α bmid = 1 := by simp [α, Ne.symm (hne_rb rlo bmid hcrlo hcbmid), Ne.symm (hne_rb rmid bmid hcrmid hcbmid), Ne.symm (hne_rb rhi bmid hcrhi hcbmid), Ne.symm hblo_mid] have hαbhi : α bhi = 2 := by simp [α, Ne.symm (hne_rb rlo bhi hcrlo hcbhi), Ne.symm (hne_rb rmid bhi hcrmid hcbhi), Ne.symm (hne_rb rhi bhi hcrhi hcbhi), Ne.symm hblo_hi, Ne.symm hbmid_hi] have hR' : P.filter (fun p => c p = 0) = ({rlo,rmid,rhi} : Finset (ℝ × ℝ)) := by rw [hR]; exact hrset.symm have hB' : P.filter (fun p => c p = 1) = ({blo,bmid,bhi} : Finset (ℝ × ℝ)) := by rw [hB]; exact hbset.symm have hcov : ∀ p ∈ P, p = rlo ∨ p = rmid ∨ p = rhi ∨ p = blo ∨ p = bmid ∨ p = bhi := by intro p hp have hc2 : ∀ q : Fin 2, q = 0 ∨ q = 1 := by decide rcases hc2 (c p) with hc | hc · have hmem : p ∈ ({rlo,rmid,rhi} : Finset (ℝ × ℝ)) := by rw [← hR']; exact Finset.mem_filter.mpr ⟨hp, hc⟩ simp only [Finset.mem_insert, Finset.mem_singleton] at hmem tauto · have hmem : p ∈ ({blo,bmid,bhi} : Finset (ℝ × ℝ)) := by rw [← hB']; exact Finset.mem_filter.mpr ⟨hp, hc⟩ simp only [Finset.mem_insert, Finset.mem_singleton] at hmem tauto have hcons : ∀ p ∈ P, (α p = 0 → φ p ≤ s) ∧ (α p = 1 → s ≤ φ p ∧ φ p ≤ s) ∧ (α p = 2 → s ≤ φ p) := by intro p hp rcases hcov p hp with h | h | h | h | h | h · rw [h, hαrlo] exact ⟨fun _ => hrle, fun hh => absurd hh (by decide), fun hh => absurd hh (by decide)⟩ · rw [h, hαrmid] exact ⟨fun hh => absurd hh (by decide), fun _ => ⟨le_of_eq hrmeq'.symm, le_of_eq hrmeq'⟩, fun hh => absurd hh (by decide)⟩ · rw [h, hαrhi] exact ⟨fun hh => absurd hh (by decide), fun hh => absurd hh (by decide), fun _ => hrge⟩ · rw [h, hαblo] exact ⟨fun _ => hble', fun hh => absurd hh (by decide), fun hh => absurd hh (by decide)⟩ · rw [h, hαbmid] exact ⟨fun hh => absurd hh (by decide), fun _ => ⟨le_of_eq hbmeq'.symm, le_of_eq hbmeq'⟩, fun hh => absurd hh (by decide)⟩ · rw [h, hαbhi] exact ⟨fun hh => absurd hh (by decide), fun hh => absurd hh (by decide), fun _ => hbge'⟩ have hfilterR : ∀ i : Fin 3, P.filter (fun p => α p = i ∧ c p = 0) = (P.filter (fun p => c p = 0)).filter (fun p => α p = i) := by intro i; ext p; simp only [Finset.mem_filter]; tauto have hfilterB : ∀ i : Fin 3, P.filter (fun p => α p = i ∧ c p = 1) = (P.filter (fun p => c p = 1)).filter (fun p => α p = i) := by intro i; ext p; simp only [Finset.mem_filter]; tauto have hRf0 : (P.filter (fun p => c p = 0)).filter (fun p => α p = 0) = {rlo} := by rw [hR'] exact planar_necklace_two_parallel_cuts_six_points_filter_three_zero rlo rmid rhi α hαrlo hαrmid hαrhi have hRf1 : (P.filter (fun p => c p = 0)).filter (fun p => α p = 1) = {rmid} := by rw [hR'] exact planar_necklace_two_parallel_cuts_six_points_filter_three_one rlo rmid rhi α hαrlo hαrmid hαrhi have hRf2 : (P.filter (fun p => c p = 0)).filter (fun p => α p = 2) = {rhi} := by rw [hR'] exact planar_necklace_two_parallel_cuts_six_points_filter_three_two rlo rmid rhi α hαrlo hαrmid hαrhi have hBf0 : (P.filter (fun p => c p = 1)).filter (fun p => α p = 0) = {blo} := by rw [hB'] exact planar_necklace_two_parallel_cuts_six_points_filter_three_zero blo bmid bhi α hαblo hαbmid hαbhi have hBf1 : (P.filter (fun p => c p = 1)).filter (fun p => α p = 1) = {bmid} := by rw [hB'] exact planar_necklace_two_parallel_cuts_six_points_filter_three_one blo bmid bhi α hαblo hαbmid hαbhi have hBf2 : (P.filter (fun p => c p = 1)).filter (fun p => α p = 2) = {bhi} := by rw [hB'] exact planar_necklace_two_parallel_cuts_six_points_filter_three_two blo bmid bhi α hαblo hαbmid hαbhi have hφne : φ ≠ 0 := by intro h0 have hu : φ u = 0 := by rw [h0]; simp have hp : 0 < φ u := by rw [hφ] have hsq : planar_necklace_two_parallel_cuts_six_points_proj u u = u.1 ^ 2 + u.2 ^ 2 := by unfold planar_necklace_two_parallel_cuts_six_points_proj; ring rw [hsq] rcases eq_or_ne u.1 0 with h1 | h1 · rcases eq_or_ne u.2 0 with h2 | h2 · exact absurd (Prod.ext h1 h2) hu_ne · nlinarith [sq_pos_of_ne_zero h2] · nlinarith [sq_pos_of_ne_zero h1] linarith refine ⟨φ, s, s, α, hφne, ?_, ?_⟩ · exact ⟨le_refl s, hcons⟩ · intro i refine ⟨?_, ?_⟩ · fin_cases i · show (P.filter (fun p => α p = (0:Fin 3) ∧ c p = 0)).card = 1 rw [hfilterR 0, hRf0]; simp · show (P.filter (fun p => α p = (1:Fin 3) ∧ c p = 0)).card = 1 rw [hfilterR 1, hRf1]; simp · show (P.filter (fun p => α p = (2:Fin 3) ∧ c p = 0)).card = 1 rw [hfilterR 2, hRf2]; simp · fin_cases i · show (P.filter (fun p => α p = (0:Fin 3) ∧ c p = 1)).card = 1 rw [hfilterB 0, hBf0]; simp · show (P.filter (fun p => α p = (1:Fin 3) ∧ c p = 1)).card = 1 rw [hfilterB 1, hBf1]; simp · show (P.filter (fun p => α p = (2:Fin 3) ∧ c p = 1)).card = 1 rw [hfilterB 2, hBf2]; simp