deadline_schedule_exists_iff_sorted_deadline_ge
Boxes i₁, …, i_k with nondecreasing integer deadlines d_{i₁} ≤ … ≤ d_{i_k} can be opened one per round (rounds 1, 2, …), each box i in a round t ≤ d_i, if and only if d_{i_j} ≥ j for every j. (Here box j is indexed from 0, so the condition reads j + 1 ≤ d j.)
Statement
theorem deadline_schedule_exists_iff_sorted_deadline_ge (k : ℕ) (d : Fin k → ℕ)
(hd : Monotone d) :
(∃ σ : Fin k → ℕ, Function.Injective σ ∧ ∀ j, 1 ≤ σ j ∧ σ j ≤ d j) ↔
∀ j : Fin k, j.val + 1 ≤ d j- Formalizes
- arXiv:2610.13775 (A 1/2-Approximation for Pandora's Problem with Deadlines), Lemma 2, first part (the feasibility characterization; the O(n²) dynamic program of the second part is not stated).
- Verified
- 13 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- LinearOrder.toTotalPreorderEvery
The proof, explained
The theorem establishes that boxes with nondecreasing deadlines can be opened one per round within their deadlines if and only if each box j satisfies j + 1 ≤ d(j). For the forward direction, an injective schedule maps the first j + 1 boxes into the rounds {1, …, d(j)}, so the pigeonhole principle forces j + 1 ≤ d(j). For the backward direction, assigning box j to round j + 1 provides an explicit injective schedule meeting all deadlines.
To prove the equivalence, we first consider the forward direction: assuming a valid schedule exists, we fix an arbitrary box index j.
We split the equivalence into both directions. For the forward direction (⇒), we assume there exists an injective schedule σ : Fin k → ℕ opening each box x in a round between 1 and d(x), and take an arbitrary box index j : Fin k.
constructor · rintro ⟨σ, h_inj, h_bound⟩ jThe schedule σ maps the first j + 1 boxes {x : Fin k | x ≤ j} into the round interval {1, …, d(j)}.
For any box x ≤ j, its round σ(x) is at least 1, and by monotonicity of deadlines, σ(x) ≤ d(x) ≤ d(j). Rewriting membership conditions using Finset.mem_coe, Finset.mem_Iic, and Finset.mem_Icc shows that σ maps Finset.Iic j into Finset.Icc 1 (d j).
uses
Finset.mem_coe,Finset.mem_Iic,Finset.mem_Icchave h_maps : Set.MapsTo σ (Finset.Iic j : Set (Fin k)) (Finset.Icc 1 (d j) : Set ℕ) := by intro x hx rw [Finset.mem_coe, Finset.mem_Iic] at hx rw [Finset.mem_coe, Finset.mem_Icc] exact ⟨(h_bound x).1, (h_bound x).2.trans (hd hx)⟩
By the pigeonhole principle on cardinalities, j + 1 ≤ d(j).
Because σ is injective on Finset.Iic j, Finset.card_le_card_of_injOn implies that the cardinality of Finset.Iic j is at most that of Finset.Icc 1 (d j). Evaluating the cardinalities with Fin.card_Iic and Nat.card_Icc gives j + 1 ≤ d(j) + 1 - 1, from which linear arithmetic (omega) yields j + 1 ≤ d(j).
uses
Finset.card_le_card_of_injOn,Fin.card_Iic,Nat.card_Icchave h_card := Finset.card_le_card_of_injOn σ h_maps h_inj.injOn rw [Fin.card_Iic, Nat.card_Icc] at h_card omega
For the backward direction, we propose the candidate schedule σ(j) = j + 1.
Assuming j + 1 ≤ d(j) for all j, we schedule box j in round j + 1. This reduces the backward direction to verifying that this assignment is injective and satisfies the deadline bounds.
· intro h use fun j => j.val + 1 refine ⟨?_, ?_⟩
The schedule σ(j) = j + 1 is injective.
If a + 1 = b + 1, linear integer arithmetic (omega) simplifies this to a = b in ℕ, and Fin.ext concludes that the Fin k indices a and b are equal.
uses
Fin.ext· intro a b hab apply Fin.ext dsimp at hab omega
The schedule σ(j) = j + 1 satisfies 1 ≤ σ(j) ≤ d(j) for every box j.
For any j, the lower bound 1 ≤ j + 1 holds by Nat.le_add_left, and the upper bound j + 1 ≤ d(j) holds directly by the hypothesis h.
uses
Nat.le_add_left· intro j exact ⟨Nat.le_add_left 1 j.val, h j⟩
Fin.ext- Two elements of Fin n are equal if their underlying natural values are equal.
Fin.card_Iic- The closed lower interval Finset.Iic b in Fin n contains b + 1 elements.
Finset.mem_coe- An element belongs to the set coercion of a finite set if and only if it belongs to the finite set.
Finset.mem_Icc- An element x belongs to the closed interval Finset.Icc a b if and only if a ≤ x and x ≤ b.
Finset.mem_Iic- An element x belongs to the lower interval Finset.Iic a if and only if x ≤ a.
Finset.card_le_card_of_injOn- If a function maps a finite set s into a finite set t and is injective on s, then the cardinality of s is at most that of t.
Nat.card_Icc- For natural numbers a and b, the number of elements in the closed interval Finset.Icc a b is b + 1 - a.
Nat.le_add_left- For any natural numbers n and m, n ≤ m + n.
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 deadline_schedule_exists_iff_sorted_deadline_ge (k : ℕ) (d : Fin k → ℕ) (hd : Monotone d) : (∃ σ : Fin k → ℕ, Function.Injective σ ∧ ∀ j, 1 ≤ σ j ∧ σ j ≤ d j) ↔ ∀ j : Fin k, j.val + 1 ≤ d j := by constructor · rintro ⟨σ, h_inj, h_bound⟩ j have h_maps : Set.MapsTo σ (Finset.Iic j : Set (Fin k)) (Finset.Icc 1 (d j) : Set ℕ) := by intro x hx rw [Finset.mem_coe, Finset.mem_Iic] at hx rw [Finset.mem_coe, Finset.mem_Icc] exact ⟨(h_bound x).1, (h_bound x).2.trans (hd hx)⟩ have h_card := Finset.card_le_card_of_injOn σ h_maps h_inj.injOn rw [Fin.card_Iic, Nat.card_Icc] at h_card omega · intro h use fun j => j.val + 1 refine ⟨?_, ?_⟩ · intro a b hab apply Fin.ext dsimp at hab omega · intro j exact ⟨Nat.le_add_left 1 j.val, h j⟩