exists_bin_packing_of_total_capacity_ge
If b bins have capacities C_j and current loads L_j ≤ C_j with Σ L_j + (m + b)η ≤ Σ C_j (η > 0), then m items of size η can be added to the bins without exceeding any capacity.
Statement
theorem exists_bin_packing_of_total_capacity_ge {b m : ℕ} (C L : Fin b → ℝ) (η : ℝ) (hη : 0 < η) (hL : ∀ j, L j ≤ C j) (h : ∑ j, L j + (m + b) * η ≤ ∑ j, C j) : ∃ f : Fin m → Fin b, ∀ j, L j + (Finset.univ.filter (fun i => f i = j)).card * η ≤ C j
- Formalizes
- arXiv:2610.15520 (Improving the bounds on approximating weighted maximin shares of chores), Lemma 5.4.
- Verified
- 14 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The theorem is proved by induction on the number of items m, universally quantified over the load vector L. In the inductive step from m to m + 1, assuming b > 0 (as b = 0 contradicts the capacity inequality), an averaging argument proves that at least one bin j₀ has room for an item of size η, because otherwise all bins would strictly exceed their capacity. Placing one item into bin j₀ increases the total load by η, which exactly matches the reduction of the remaining slack term from (m + 1 + b)η to (m + b)η. Applying the induction hypothesis to the updated loads packs the remaining m items, and prepending j₀ yields a valid packing of all m + 1 items.
The base case m = 0 holds: with zero items to place, the empty assignment leaves the loads L_j ≤ C_j unchanged.
We universally quantify over the initial loads L and induct on the number of items m. When m = 0, no items need to be assigned, so we choose the empty assignment function (from Fin 0). Since the preimage of any bin j under this function is empty, the item count in each bin is 0, and the capacity check reduces directly to the initial hypothesis L_j ≤ C_j.
uses
Finset.filter_eq_empty_iff,Finset.card_empty,Nat.cast_zero,MulZeroClass.zero_mul,add_zerorevert L induction m with | zero => intro L hL h refine ⟨fun i => i.elim0, ?_⟩ intro j have : (Finset.univ.filter (fun (i : Fin 0) => (fun _ => i.elim0) i = j)) = ∅ := by rw [Finset.filter_eq_empty_iff] intro i exact i.elim0 rw [this, Finset.card_empty, Nat.cast_zero, MulZeroClass.zero_mul, add_zero] exact hL j
For the inductive step m + 1, we may assume b > 0, since b = 0 contradicts the total capacity condition.
We assume the inductive hypothesis for m and introduce the loads L for m + 1 items. If there are no bins (b = 0), all sums over bins are empty and vanish, reducing the hypothesis to (m + 1)η ≤ 0. But m + 1 ≥ 1 and η > 0 imply (m + 1)η > 0, yielding a contradiction. Hence b > 0.
uses
Nat.eq_zero_or_pos,Finset.univ_eq_empty,Finset.sum_empty,zero_add| succ m ih => intro L hL h rcases Nat.eq_zero_or_pos b with rfl | hb · simp only [Finset.univ_eq_empty, Finset.sum_empty, zero_add] at h have hpos : 0 < ((m + 1 : ℝ) * η) := by positivity push_cast at h linarithThere exists at least one bin j₀ that can accommodate an item of size η, that is, L_{j₀} + η ≤ C_{j₀}.
Suppose, for contradiction, that every bin satisfies C_j < L_j + η. Because b > 0, the set of bins is nonempty. Summing these strict inequalities across all b bins gives ∑ C_j < ∑ L_j + bη. However, the total capacity hypothesis guarantees ∑ L_j + (m + 1 + b)η ≤ ∑ C_j. Since (m + 1)η > 0, this implies ∑ L_j + bη < ∑ C_j ≤ ∑ C_j - (m + 1)η, a contradiction. We obtain a bin j₀ satisfying L_{j₀} + η ≤ C_{j₀}.
uses
Finset.univ_nonempty_iff.mpr,Fin.pos_iff_nonempty.mp,Finset.sum_lt_sum_of_nonempty,Finset.sum_add_distrib,Finset.sum_const,Finset.card_univ,Fintype.card_fin,nsmul_eq_mul,Nat.cast_nonneg· have hex : ∃ j₀ : Fin b, L j₀ + η ≤ C j₀ := by by_contra! h_all have h_ne : (Finset.univ : Finset (Fin b)).Nonempty := Finset.univ_nonempty_iff.mpr (Fin.pos_iff_nonempty.mp hb) have h1 : ∑ j, C j < ∑ j, (L j + η) := Finset.sum_lt_sum_of_nonempty h_ne (fun j _ => h_all j) rw [Finset.sum_add_distrib, Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul] at h1 have hm : 0 ≤ (m : ℝ) := Nat.cast_nonneg m have h_exp : (↑(m + 1) + ↑b : ℝ) * η = (m : ℝ) * η + η + (b : ℝ) * η := by push_cast ring nlinarith rcases hex with ⟨j₀, hj₀⟩
Updating the load of bin j₀ by η yields loads L' that respect every bin capacity (L'_j ≤ C_j for all j).
We define the new load function L' by increasing bin j₀'s load to L_{j₀} + η and keeping all other bin loads unchanged. For j = j₀, L'_{j₀} = L_{j₀} + η ≤ C_{j₀} by the choice of j₀. For j ≠ j₀, L'_j = L_j ≤ C_j by the initial load hypothesis.
uses
Function.update_self,Function.update_of_neset L' := Function.update L j₀ (L j₀ + η) with hL'_def have hL' : ∀ j, L' j ≤ C j := by intro j by_cases hj : j = j₀ · subst hj rw [hL'_def, Function.update_self] exact hj₀ · rw [hL'_def, Function.update_of_ne hj] exact hL j
The updated loads L' satisfy the total capacity condition for the remaining m items: ∑ L'_j + (m + b)η ≤ ∑ C_j.
Because L' differs from L only at j₀ where its load increases by η, the total load increases by exactly η: ∑ L'_j = ∑ L_j + η. Rewriting (m + 1 + b)η as (m + b)η + η, the original inequality ∑ L_j + (m + 1 + b)η ≤ ∑ C_j rearranges via linear arithmetic to ∑ L'_j + (m + b)η ≤ ∑ C_j.
uses
Finset.mem_univ,Finset.sum_update_of_mem,Finset.sdiff_singleton_eq_erase,Finset.add_sum_erasehave h_sum' : ∑ j, L' j + ((m : ℝ) + (b : ℝ)) * η ≤ ∑ j, C j := by have hi : j₀ ∈ (Finset.univ : Finset (Fin b)) := Finset.mem_univ j₀ have h1 := Finset.sum_update_of_mem hi L (L j₀ + η) rw [Finset.sdiff_singleton_eq_erase] at h1 have h2 := Finset.add_sum_erase Finset.univ L hi have h_sum : ∑ j, L' j = (∑ j, L j) + η := by rw [hL'_def, h1] linarith have : (↑(m + 1) + ↑b : ℝ) * η = (↑m + ↑b) * η + η := by push_cast ring linarith
By the induction hypothesis, there is a packing f' for the remaining m items, and assigning the first item to j₀ decomposes each bin's count into the first item plus the rest.
Applying the induction hypothesis to the loads L' and remaining m items gives a valid packing f' : Fin m → Fin b. We define an assignment for all m + 1 items by mapping the first item (index 0) to j₀ and the remaining m items according to f'. Using the counting lemma Fin.card_filter_univ_succ, the total number of items assigned to bin j is |(f')⁻¹(j)| + 1 if j = j₀, and |(f')⁻¹(j)| if j ≠ j₀.
uses
Fin.card_filter_univ_succ,Fin.cons_zero,Fin.cons_succrcases ih L' hL' h_sum' with ⟨f', hf'⟩ refine ⟨Fin.cons (α := fun _ => Fin b) j₀ f', ?_⟩ intro j have h_card := @Fin.card_filter_univ_succ m (fun (i : Fin (m + 1)) => (Fin.cons (α := fun _ => Fin b) j₀ f') i = j) _ simp only [Fin.cons_zero, Fin.cons_succ] at h_card have h_ih_j := hf' j
Every bin j respects its capacity under the extended packing: L_j + |f⁻¹(j)|η ≤ C_j.
We split into cases on whether j = j₀: if j = j₀, the bin receives the first item, so its load is L_{j₀} + (|(f')⁻¹(j₀)| + 1)η = (L_{j₀} + η) + |(f')⁻¹(j₀)|η = L'_{j₀} + |(f')⁻¹(j₀)|η ≤ C_{j₀}, which holds by the induction hypothesis on f'. If j ≠ j₀, the bin receives no additional item, so its load is L_j + |(f')⁻¹(j)|η = L'_j + |(f')⁻¹(j)|η ≤ C_j, which also holds by the induction hypothesis on f'.
uses
Function.update_self,if_pos,Function.update_of_ne,Ne.symm,if_negby_cases hj : j₀ = j · subst hj rw [hL'_def, Function.update_self] at h_ih_j rw [h_card, if_pos rfl] push_cast linarith · rw [hL'_def, Function.update_of_ne (Ne.symm hj)] at h_ih_j rw [h_card, if_neg hj] exact h_ih_j
add_zero- Adding zero to an element leaves it unchanged (a + 0 = a).
Fin.cons_zero- Evaluating the tuple extension `Fin.cons x p` at index 0 yields the head element x.
Fin.cons_succ- Evaluating the tuple extension `Fin.cons x p` at a successor index i.succ yields p(i).
Fin.card_filter_univ_succ- The count of elements in Fin (n + 1) satisfying predicate p is the count on Fin n (via successor) plus 1 if 0 satisfies p, and 0 otherwise.
Fin.pos_iff_nonempty.mp- If n > 0, then the type Fin n is nonempty.
Finset.add_sum_erase- Adding f(a) to the sum of f over a finset s with a erased yields the full sum over s.
Finset.card_empty- The cardinality of the empty finset is 0.
Finset.card_univ- The cardinality of the universal finset on a finite type equals the cardinality of the type.
Finset.filter_eq_empty_iff- A filtered finset is empty if and only if no element in the finset satisfies the filtering predicate.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
Finset.sdiff_singleton_eq_erase- Removing a singleton {a} from a finset by set difference is equivalent to erasing a.
Finset.sum_add_distrib- The sum of a pointwise sum of functions over a finset equals the sum of the individual sums.
Finset.sum_const- Summing a constant over a finset equals the cardinality of the finset multiplied by the constant.
Finset.sum_empty- The sum of any function over the empty finset is 0.
Finset.sum_lt_sum_of_nonempty- If a finset is nonempty and f(i) < g(i) for all elements i in the finset, then the sum of f is strictly less than the sum of g.
Finset.sum_update_of_mem- The sum over a finset s of a function updated at i ∈ s with value b equals b plus the sum of the original function over s with i removed.
Finset.univ_eq_empty- The universal finset of an empty type is the empty finset.
Finset.univ_nonempty_iff.mpr- If a finite type is nonempty, then its universal finset is nonempty.
Fintype.card_fin- The cardinality of Fin n is n.
Function.update_self- An updated function f[a ↦ v] evaluated at a equals v.
Function.update_of_ne- An updated function f[a' ↦ v] evaluated at an input a ≠ a' equals the original value f(a).
if_neg- If condition c is false, then `if c then t else e` reduces to e.
if_pos- If condition c is true, then `if c then t else e` reduces to t.
MulZeroClass.zero_mul- Zero multiplied by any element is zero (0 * a = 0).
Nat.cast_zero- The coercion of the natural number 0 into an additive monoid with one is 0.
Nat.cast_nonneg- The coercion of any natural number into an ordered semiring is non-negative (0 ≤ n).
Nat.eq_zero_or_pos- Every natural number is either equal to 0 or strictly positive.
Ne.symm- Inequality is symmetric: if a ≠ b, then b ≠ a.
nsmul_eq_mul- Scalar multiplication by a natural number n • a is equal to the ring product (n : R) * a.
zero_add- Adding zero on the left leaves an element unchanged (0 + a = a).
- The case b = 0 is handled as a separate degenerate case: with no bins, the capacity inequality forces (m + 1)η ≤ 0, which contradicts m + 1 ≥ 1 and η > 0.
- The lemma Fin.card_filter_univ_succ is a formal bookkeeping lemma for counting preimages in Fin (m + 1): it proves that prepending j₀ to f' increases the count of items in bin j by 1 if j = j₀ and leaves it unchanged otherwise.
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.
theorem exists_bin_packing_of_total_capacity_ge {b m : ℕ} (C L : Fin b → ℝ) (η : ℝ) (hη : 0 < η) (hL : ∀ j, L j ≤ C j) (h : ∑ j, L j + (m + b) * η ≤ ∑ j, C j) : ∃ f : Fin m → Fin b, ∀ j, L j + (Finset.univ.filter (fun i => f i = j)).card * η ≤ C j := by revert L induction m with | zero => intro L hL h refine ⟨fun i => i.elim0, ?_⟩ intro j have : (Finset.univ.filter (fun (i : Fin 0) => (fun _ => i.elim0) i = j)) = ∅ := by rw [Finset.filter_eq_empty_iff] intro i exact i.elim0 rw [this, Finset.card_empty, Nat.cast_zero, MulZeroClass.zero_mul, add_zero] exact hL j | succ m ih => intro L hL h rcases Nat.eq_zero_or_pos b with rfl | hb · simp only [Finset.univ_eq_empty, Finset.sum_empty, zero_add] at h have hpos : 0 < ((m + 1 : ℝ) * η) := by positivity push_cast at h linarith · have hex : ∃ j₀ : Fin b, L j₀ + η ≤ C j₀ := by by_contra! h_all have h_ne : (Finset.univ : Finset (Fin b)).Nonempty := Finset.univ_nonempty_iff.mpr (Fin.pos_iff_nonempty.mp hb) have h1 : ∑ j, C j < ∑ j, (L j + η) := Finset.sum_lt_sum_of_nonempty h_ne (fun j _ => h_all j) rw [Finset.sum_add_distrib, Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul] at h1 have hm : 0 ≤ (m : ℝ) := Nat.cast_nonneg m have h_exp : (↑(m + 1) + ↑b : ℝ) * η = (m : ℝ) * η + η + (b : ℝ) * η := by push_cast ring nlinarith rcases hex with ⟨j₀, hj₀⟩ set L' := Function.update L j₀ (L j₀ + η) with hL'_def have hL' : ∀ j, L' j ≤ C j := by intro j by_cases hj : j = j₀ · subst hj rw [hL'_def, Function.update_self] exact hj₀ · rw [hL'_def, Function.update_of_ne hj] exact hL j have h_sum' : ∑ j, L' j + ((m : ℝ) + (b : ℝ)) * η ≤ ∑ j, C j := by have hi : j₀ ∈ (Finset.univ : Finset (Fin b)) := Finset.mem_univ j₀ have h1 := Finset.sum_update_of_mem hi L (L j₀ + η) rw [Finset.sdiff_singleton_eq_erase] at h1 have h2 := Finset.add_sum_erase Finset.univ L hi have h_sum : ∑ j, L' j = (∑ j, L j) + η := by rw [hL'_def, h1] linarith have : (↑(m + 1) + ↑b : ℝ) * η = (↑m + ↑b) * η + η := by push_cast ring linarith rcases ih L' hL' h_sum' with ⟨f', hf'⟩ refine ⟨Fin.cons (α := fun _ => Fin b) j₀ f', ?_⟩ intro j have h_card := @Fin.card_filter_univ_succ m (fun (i : Fin (m + 1)) => (Fin.cons (α := fun _ => Fin b) j₀ f') i = j) _ simp only [Fin.cons_zero, Fin.cons_succ] at h_card have h_ih_j := hf' j by_cases hj : j₀ = j · subst hj rw [hL'_def, Function.update_self] at h_ih_j rw [h_card, if_pos rfl] push_cast linarith · rw [hL'_def, Function.update_of_ne (Ne.symm hj)] at h_ih_j rw [h_card, if_neg hj] exact h_ih_j