floor_le_ceil_div_iff
lemmaverified
For S > 0, floor(x/S) <= a <= ceil(x/S) iff x < (a+1) S and a S < x + S.
Statement
lemma floor_le_ceil_div_iff (x S a : ℕ) (hS : 0 < S) :
(⌊(x : ℚ) / (S : ℚ)⌋₊ ≤ a ∧ a ≤ ⌈(x : ℚ) / (S : ℚ)⌉₊) ↔ (x < (a + 1) * S ∧ a * S < x + S)- Source
- step towards quota_population_monotone_incompatible_four_states_common_house (common-house-size variant left open by arXiv:2608.02759, Sec. 5; cf. arXiv:2202.11061, Sec. 3.1)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 3
- chore_remaining_set_two_mul_eq_emptyFor every natural number $n$, the set of remaining chores after $2n$ chores have been assigned (out of $2n$ total chores) is empty.
- apx_quota_iffFor positive four-state populations, quota is equivalent to the Boolean natural-number test.
- binary_form_compression_bound_zeroFor every natural number $a$, the compression bound $h_a(0)$ equals 1.
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.
/-- Natural-number form of one state's quota condition: with total population `S > 0`, `⌊x/S⌋ ≤ a ≤ ⌈x/S⌉` iff `x < (a+1) S` and `a S < x + S`. -/lemma floor_le_ceil_div_iff (x S a : ℕ) (hS : 0 < S) : (⌊(x : ℚ) / (S : ℚ)⌋₊ ≤ a ∧ a ≤ ⌈(x : ℚ) / (S : ℚ)⌉₊) ↔ (x < (a + 1) * S ∧ a * S < x + S) := by have hS' : (0 : ℚ) < S := by exact_mod_cast hS have hy : (0 : ℚ) ≤ (x : ℚ) / S := div_nonneg (Nat.cast_nonneg x) hS'.le have h1 : ⌊(x : ℚ) / (S : ℚ)⌋₊ ≤ a ↔ x < (a + 1) * S := by rw [← Nat.lt_succ_iff, Nat.floor_lt hy, div_lt_iff₀ hS'] norm_cast have h2 : a ≤ ⌈(x : ℚ) / (S : ℚ)⌉₊ ↔ a * S < x + S := by cases a with | zero => simp; omega | succ b => rw [Nat.succ_le_iff, Nat.lt_ceil, lt_div_iff₀ hS'] constructor · intro h; have : b * S < x := by exact_mod_cast h rw [Nat.succ_mul]; omega · intro h; rw [Nat.succ_mul] at h exact_mod_cast (show b * S < x by omega) rw [h1, h2]