AFTD Auto-Formalizing Theoretical Domains

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

Lean source view module on GitHub

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