propm_cut_choose
lemmaverified
Cut and choose on one set of items: the cutter keeps K, the chooser gets the rest; the chooser gets at least half, and the cutter misses half by at most half of any item given to the chooser.
Statement
lemma propm_cut_choose {m : ℕ} (T : Finset (Fin m)) (vc vh : Fin m → ℝ) (hvc : ∀ x, 0 ≤ vc x) :
∃ K ⊆ T, (∀ g ∈ T \ K, ∑ x ∈ T, vc x ≤ 2 * ∑ x ∈ K, vc x + vc g) ∧
∑ x ∈ T, vh x ≤ 2 * ∑ x ∈ T \ K, vh x- Source
- step towards propm_orientation_of_out_degree_two (PROPm orientations, arXiv:2602.18098 v2, Sec. 6)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- propm_efx_splitFor one nonnegative additive valuation, every finite set of items has an EFX split: each side minus any one of its items is worth at most…
- Used by 1
- propm_orientation_of_out_degree_twoIf the simple graph underlying a loopless multigraph has an orientation with every out-degree at most two, then for nonnegative additive…
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.
/-- Cut and choose on one parallel class `T`: the cutter (valuation `vc ≥ 0`) keeps `K`, the chooser (valuation `vh`) gets `T \ K`. The chooser gets at least half of `T`, and the cutter misses half of `T` by at most half of any item given to the chooser. -/lemma propm_cut_choose {m : ℕ} (T : Finset (Fin m)) (vc vh : Fin m → ℝ) (hvc : ∀ x, 0 ≤ vc x) : ∃ K ⊆ T, (∀ g ∈ T \ K, ∑ x ∈ T, vc x ≤ 2 * ∑ x ∈ K, vc x + vc g) ∧ ∑ x ∈ T, vh x ≤ 2 * ∑ x ∈ T \ K, vh x := by classical obtain ⟨X, hXT, h1, h2⟩ := propm_efx_split T vc hvc have hX : ∀ w : Fin m → ℝ, ∑ x ∈ T \ X, w x = ∑ x ∈ T, w x - ∑ x ∈ X, w x := fun w => by rw [← Finset.sum_sdiff hXT]; ring by_cases hc : 2 * ∑ x ∈ X, vh x ≤ ∑ x ∈ T, vh x · exact ⟨X, hXT, fun g hg => by linarith [h2 g hg], by rw [hX]; linarith⟩ · refine ⟨T \ X, Finset.sdiff_subset, fun g hg => ?_, ?_⟩ · rw [Finset.sdiff_sdiff_eq_self hXT] at hg rw [hX]; linarith [h1 g hg] · rw [Finset.sdiff_sdiff_eq_self hXT]; linarith