AFTD Auto-Formalizing Theoretical Domains

op562_not_consistent_eefx_of_ge_three_halves

theoremverifiedformalization

For any number of agents n at least 3 and any error factor rho at least 3/2, no consistent online algorithm can guarantee any positive approximation of EEFX.

Statement

theorem op562_not_consistent_eefx_of_ge_three_halves (n : ℕ) (hn : 3 ≤ n) (ρ : ℝ)
    (hρ : 3 / 2 ≤ ρ) :
    ¬ has_consistent_eefx_algorithm n ρ
Formalizes
arXiv:2610.34625 Section G.6
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 12
  • has_consistent_eefx_algorithmThere exists an online, consistent algorithm alg for n agents and a positive constant α > 0 such that alg guarantees α-EEFX under error…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • is_alpha_eefx_bundleA bundle S of goods is alpha-EEFX for an agent with valuation v if there exists a partition of the remaining goods into n-1 parts such…
  • is_consistent_algorithmAn online algorithm alg for n agents is consistent if for every m : ℕ and all nonnegative valuations v and predictions a_hat with exact…
  • sorted_tupleFor any tuple u : Fin m → ℝ, its sorted tuple is u ∘ Tuple.sort u, which reorders the values of u in nondecreasing order.
  • additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
  • is_online_algorithmFor an allocation algorithm alg taking a number of goods m : ℕ, predicted valuation profiles a_hat : Fin n → Fin m → ℝ, and true valuation…
  • is_alpha_eefx_allocationAn allocation is alpha-EEFX if each agent's bundle is alpha-EEFX for that agent.
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • is_overestimate_predictionPredictions a_hat : Fin n → Fin m → ℝ are overestimates of valuations v : Fin n → Fin m → ℝ with error factor ρ if for every agent i : Fin…
  • guarantees_alpha_eefxAn algorithm alg guarantees alpha-EEFX for n agents under error factor ρ if for every m : ℕ, all nonnegative valuations v and all…
  • bundle_ofUnder an allocation that gives each item x to agent s(x), agent i's bundle is the set of items given to i.

Read back from the Lean

For every natural number $n \ge 3$ and every real number $\rho \ge 3/2$, there does not exist a consistent, online EEFX algorithm for $n$ agents with overestimate parameter $\rho$. Specifically, there does not exist an algorithm alg (which, for each number of goods $m \in \mathbb{N}$, takes a predicted valuation profile $\hat{a} : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$ and an actual valuation profile $v : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$, and assigns each good $t \in \text{Fin } m$ to an agent in $\text{Fin } n$) and a real number $\alpha > 0$ such that all of the following hold: 1. **Online**: For all $m \in \mathbb{N}$, $\hat{a}$, $v, v'$, and $t \in \text{Fin } m$, if $v(i, s) = v'(i, s)$ for all agents $i$ and all goods $s \le t$, then $\text{alg}(m, \hat{a}, v)(t) = \text{alg}(m, \hat{a}, v')(t)$. 2. **Consistent**: For all $m \in \mathbb{N}$ and all non-negative valuation profiles $v$, if $\hat{a}$ is an exact prediction for $v$ (i.e., for every agent $i$, the sorted tuple of $\hat{a}(i)$ equals the sorted tuple of $v(i)$), then the allocation produced by $\text{alg}(m, \hat{a}, v)$ is a 1-EEFX allocation under the additive valuations induced by $v$. 3. **$\alpha$-EEFX robust under $\rho$-overestimation**: For all $m \in \mathbb{N}$ and all non-negative valuation profiles $v$, if $\hat{a}$ is a $\rho$-overestimate prediction for $v$ (i.e., for every agent $i$ and rank $r \in \text{Fin } m$, $\text{sorted\_tuple}(v(i))(r) \le \text{sorted\_tuple}(\hat{a}(i))(r) \le \rho \cdot \text{sorted\_tuple}(v(i))(r)$), then the allocation produced by $\text{alg}(m, \hat{a}, v)$ is an $\alpha$-EEFX allocation under the additive valuations induced by $v$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

For any n ≥ 3 and error factor ρ ≥ 3/2, no consistent online algorithm can guarantee positive approximation α > 0 of EEFX. We construct a predicted profile W with h exponentially decreasing small goods, n - 3 large goods of value 3, and a final good of value 1, and a true profile V identical to W except that the last good is worth (2/3)^(h+1). Consistency forces the algorithm to allocate the last good to an agent with no other goods, and the online property ensures this agent also receives nothing else under V, leaving them with an isolated tiny good that violates α-EEFX.

  1. Sorting a tuple via a permutation preserves order if the composed function is monotone.

    By definition, `sorted_tuple f` is `f` precomposed with the sorting permutation of `f`. Lemma `Tuple.comp_sort_eq_comp_iff_monotone` states that precomposing with a permutation yields the sorted tuple precisely when the composition is monotone.

    lines 11–15

    uses Tuple.comp_sort_eq_comp_iff_monotone

    theorem op562nc_sorted_eq {m : ℕ} (f : Fin m → ℝ) (σ : Equiv.Perm (Fin m))
        (hmono : Monotone (f ∘ σ)) : sorted_tuple f = f ∘ σ := by
      unfold sorted_tuple
      exact ((Tuple.comp_sort_eq_comp_iff_monotone).mpr hmono).symm
    
  2. The sorted values of profile W are (2/3)^(h - r) for r ≤ h and 3 for r > h.

    We construct an explicit bijection `σ` that reverses the small goods and shifts the remaining goods, verify that `op562nc_W ∘ σ` evaluates to the piecewise formula, check that this formula is monotonically non-decreasing, and apply `op562nc_sorted_eq` to identify `sorted_tuple (op562nc_W h n)` with this permutation.

    lines 16–50

    uses op562nc_sorted_eq

    theorem op562nc_sorted_W (h n : ℕ) (hn : 3 ≤ n) :
        ∀ r : Fin (h + n - 2), sorted_tuple (op562nc_W h n) r =
          if r.val ≤ h then (2 / 3 : ℝ) ^ (h - r.val) else 3 := by
      let f : Fin (h + n - 2) → Fin (h + n - 2) := fun r =>
        if hr : r.val < h then ⟨h - 1 - r.val, by omega⟩
        else if r.val = h then ⟨h + n - 3, by omega⟩ else ⟨r.val - 1, by omega⟩
      have hf : Function.Injective f := by
        intro a b hab
        simp only [f] at hab
        apply Fin.ext
        split_ifs at hab <;> simp only [Fin.mk.injEq] at hab <;> omega
      let σ : Equiv.Perm (Fin (h + n - 2)) := Equiv.ofBijective f (Finite.injective_iff_bijective.mp hf)
      have hfv : ∀ r, (σ r).val = if r.val < h then h - 1 - r.val
          else if r.val = h then h + n - 3 else r.val - 1 := by
        intro r
        simp only [σ, Equiv.ofBijective_apply, f]
        split_ifs <;> rfl
      have hval : ∀ r, op562nc_W h n (σ r) = if r.val ≤ h then (2 / 3 : ℝ) ^ (h - r.val) else 3 := by
        intro r
        unfold op562nc_W
        rw [hfv r]
        split_ifs <;> first | omega | rfl | (rw [show h - r.val = 0 by omega, pow_zero]) | (congr 1; omega)
      have hmono : Monotone (op562nc_W h n ∘ σ) := by
        intro a b hab
        simp only [Function.comp, hval]
        have hab' : a.val ≤ b.val := hab
        split_ifs with h1 h2 h2
        · exact pow_le_pow_of_le_one (by norm_num) (by norm_num) (by omega)
        · exact le_trans (pow_le_one₀ (by norm_num) (by norm_num)) (by norm_num)
        · omega
        · exact le_refl _
      intro r
      rw [op562nc_sorted_eq _ σ hmono]
      exact hval r
    
  3. The sorted values of profile V are (2/3)^(h + 1 - r) for r ≤ h and 3 for r > h.

    Similarly, we construct a bijection `σ` mapping the index of the tiny last good to position 0 and reversing the small goods, verify that `op562nc_V ∘ σ` is non-decreasing, and apply `op562nc_sorted_eq` to deduce the sorted values.

    lines 51–86

    uses op562nc_sorted_eq

    theorem op562nc_sorted_V (h n : ℕ) (hn : 3 ≤ n) :
        ∀ r : Fin (h + n - 2), sorted_tuple (op562nc_V h n) r =
          if r.val ≤ h then (2 / 3 : ℝ) ^ (h + 1 - r.val) else 3 := by
      let f : Fin (h + n - 2) → Fin (h + n - 2) := fun r =>
        if r.val = 0 then ⟨h + n - 3, by omega⟩
        else if hr : r.val ≤ h then ⟨h - r.val, by omega⟩ else ⟨r.val - 1, by omega⟩
      have hf : Function.Injective f := by
        intro a b hab
        simp only [f] at hab
        apply Fin.ext
        split_ifs at hab <;> simp only [Fin.mk.injEq] at hab <;> omega
      let σ : Equiv.Perm (Fin (h + n - 2)) := Equiv.ofBijective f (Finite.injective_iff_bijective.mp hf)
      have hfv : ∀ r, (σ r).val = if r.val = 0 then h + n - 3
          else if r.val ≤ h then h - r.val else r.val - 1 := by
        intro r
        simp only [σ, Equiv.ofBijective_apply, f]
        split_ifs <;> rfl
      have hval : ∀ r, op562nc_V h n (σ r) =
          if r.val ≤ h then (2 / 3 : ℝ) ^ (h + 1 - r.val) else 3 := by
        intro r
        unfold op562nc_V
        rw [hfv r]
        split_ifs <;> first | omega | rfl | (congr 1; omega)
      have hmono : Monotone (op562nc_V h n ∘ σ) := by
        intro a b hab
        simp only [Function.comp, hval]
        have hab' : a.val ≤ b.val := hab
        split_ifs with h1 h2 h2
        · exact pow_le_pow_of_le_one (by norm_num) (by norm_num) (by omega)
        · exact le_trans (pow_le_one₀ (by norm_num) (by norm_num)) (by norm_num)
        · omega
        · exact le_refl _
      intro r
      rw [op562nc_sorted_eq _ σ hmono]
      exact hval r
    
  4. Profile W is an overestimate prediction of profile V with error factor ρ ≥ 3/2.

    Comparing sorted tuples componentwise using `op562nc_sorted_W` and `op562nc_sorted_V`: for r ≤ h, the ratio of values is (2/3)^(h - r) / (2/3)^(h + 1 - r) = 3/2 ≤ ρ. For r > h, both profiles equal 3, giving a ratio of 1 ≤ ρ. Thus W is a ρ-overestimate of V.

    lines 87–103

    uses op562nc_sorted_W, op562nc_sorted_V, pow_succ

    theorem op562nc_overestimate (h n : ℕ) (hn : 3 ≤ n) (ρ : ℝ) (hρ : 3 / 2 ≤ ρ) :
        is_overestimate_prediction ρ (fun _ : Fin n => op562nc_V h n)
          (fun _ : Fin n => op562nc_W h n) := by
      intro i r
      simp only
      rw [op562nc_sorted_W h n hn r, op562nc_sorted_V h n hn r]
      split_ifs with hr
      · have he : h + 1 - r.val = (h - r.val) + 1 := by omega
        rw [he, pow_succ]
        have hp : (0 : ℝ) ≤ (2 / 3 : ℝ) ^ (h - r.val) := by positivity
        constructor
        · nlinarith
        · nlinarith
      · constructor
        · exact le_refl _
        · nlinarith
    
  5. By pigeonhole, partitioning goods among n - 1 parts outside a bundle must place two goods from any set of n items into the same part.

    Given n items not in bundle S and an EEFX partition into n - 1 parts Y, mapping each item to the part containing it produces a collision by `Fintype.exists_ne_map_eq_of_card_lt`, yielding two distinct items sharing one part.

    lines 104–127

    uses Fintype.exists_ne_map_eq_of_card_lt

    /-- Pigeonhole for EEFX partitions: `n` distinct goods outside the bundle, two share a part. -/
    theorem op562nc_pigeon {m n : ℕ} (hn : 3 ≤ n) (Y : Fin (n - 1) → Finset (Fin m))
        (S : Finset (Fin m)) (hY : Finset.biUnion Finset.univ Y = Finset.univ \ S)
        (e : Fin n → Fin m) (he : Function.Injective e) (hS : ∀ j, e j ∉ S) :
        ∃ p, ∃ j1 j2, j1 ≠ j2 ∧ e j1 ∈ Y p ∧ e j2 ∈ Y p := by
      classical
      have hcov : ∀ x, x ∉ S → ∃ p, x ∈ Y p := by
        intro x hx
        have : x ∈ Finset.biUnion Finset.univ Y := by
          rw [hY]; simp [hx]
        simpa using this
      let part : Fin m → Fin (n - 1) := fun x =>
        if hx : ∃ p, x ∈ Y p then Classical.choose hx else ⟨0, by omega⟩
      have hpart : ∀ x, x ∉ S → x ∈ Y (part x) := by
        intro x hx
        simp only [part, dif_pos (hcov x hx)]
        exact Classical.choose_spec (hcov x hx)
      obtain ⟨j1, j2, hne, heq⟩ := Fintype.exists_ne_map_eq_of_card_lt (part ∘ e)
        (by simp; omega)
      refine ⟨part (e j1), j1, j2, hne, hpart _ (hS j1), ?_⟩
      have := hpart _ (hS j2)
      simp only [Function.comp] at heq
      rwa [heq]
    
  6. Erasing one item from a part containing two distinct goods leaves a value at least that of the other good.

    Since {b} ⊆ P \ {a}, monotonicity of additive valuations (`op562nc_av_mono`) implies u(b) ≤ additive_valuation u (P \ {a}).

    lines 128–143

    uses op562nc_av_mono

    theorem op562nc_av_mono {m : ℕ} (u : Fin m → ℝ) (hu : ∀ g, 0 ≤ u g) {A B : Finset (Fin m)}
        (hAB : A ⊆ B) : additive_valuation u A ≤ additive_valuation u B :=
      Finset.sum_le_sum_of_subset_of_nonneg hAB (fun _ _ _ => hu _)
    
    /-- Two distinct goods in one part: erasing one leaves at least the other's value. -/
    theorem op562nc_two_in_part {m : ℕ} (u : Fin m → ℝ) (hu : ∀ g, 0 ≤ u g) (P : Finset (Fin m))
        {a b : Fin m} (hab : a ≠ b) (ha : a ∈ P) (hb : b ∈ P) :
        u b ≤ additive_valuation u (P.erase a) := by
      have : ({b} : Finset (Fin m)) ⊆ P.erase a := by
        intro x hx
        rw [Finset.mem_singleton] at hx
        subst hx
        exact Finset.mem_erase.mpr ⟨fun h => hab h.symm, hb⟩
      have := op562nc_av_mono u hu this
      simpa [additive_valuation] using this
    
  7. Profiles V and W assign non-negative values to all goods. automation

    Unfolding the piecewise definitions of V and W, every branch is either a positive power of 2/3 or the constant 3, both of which are positive by `positivity`.

    lines 144–149

    theorem op562nc_V_nonneg (h n : ℕ) : ∀ g, 0 ≤ op562nc_V h n g := by
      intro g; unfold op562nc_V; split_ifs <;> positivity
    
    theorem op562nc_W_nonneg (h n : ℕ) : ∀ g, 0 ≤ op562nc_W h n g := by
      intro g; unfold op562nc_W; split_ifs <;> positivity
    
  8. An agent receiving only the last good does not satisfy α-EEFX under profile V when that good is worth less than α * (2/3)^3.

    There are n goods outside the last good each worth at least (2/3)^3 (the first 3 small goods and n - 3 large goods of value 3). By pigeonhole (`op562nc_pigeon`), two of these share a part, so removing one leaves value at least (2/3)^3. For α-EEFX to hold, the agent's bundle would need to be worth at least α * (2/3)^3, which exceeds the last good's value (2/3)^(h+1), a contradiction.

    lines 150–199

    uses op562nc_pigeon, op562nc_two_in_part, op562nc_av_mono

    /-- The inexact instance: an agent whose bundle is inside the last good is not α-EEFX. -/
    theorem op562nc_fail (h n : ℕ) (hn : 3 ≤ n) (hh : 3 ≤ h) (α : ℝ)
        (hα : (2 / 3 : ℝ) ^ (h + 1) < α * (2 / 3) ^ 3) (S : Finset (Fin (h + n - 2)))
        (hS : ∀ t ∈ S, t.val = h + n - 3) :
        ¬ is_alpha_eefx_bundle (additive_valuation (op562nc_V h n)) n α S := by
      rintro ⟨Y, _hdisj, hY, hefx⟩
      let e : Fin n → Fin (h + n - 2) := fun j =>
        if j.val < 3 then ⟨j.val, by omega⟩ else ⟨h + j.val - 3, by omega⟩
      have he : Function.Injective e := by
        intro a b hab
        simp only [e] at hab
        apply Fin.ext
        split_ifs at hab <;> simp only [Fin.mk.injEq] at hab <;> omega
      have heS : ∀ j, e j ∉ S := by
        intro j hj
        have := hS _ hj
        simp only [e] at this
        split_ifs at this <;> simp only at this <;> omega
      have hev : ∀ j, (2 / 3 : ℝ) ^ 3 ≤ op562nc_V h n (e j) := by
        intro j
        simp only [e, op562nc_V]
        split_ifs with h1 h2 h3 h4 h5 <;> simp only at * <;> try omega
        · exact pow_le_pow_of_le_one (by norm_num) (by norm_num) (by omega)
        · norm_num
      obtain ⟨p, j1, j2, hne, h1, h2⟩ := op562nc_pigeon hn Y S hY e he heS
      have hle := hefx p (e j1) h1
      have hbig := op562nc_two_in_part (op562nc_V h n) (op562nc_V_nonneg h n) (Y p)
        (fun h => hne (he h)) h1 h2
      have hSv : additive_valuation (op562nc_V h n) S ≤ (2 / 3 : ℝ) ^ (h + 1) := by
        have hsub : S ⊆ {(⟨h + n - 3, by omega⟩ : Fin (h + n - 2))} := by
          intro t ht
          rw [Finset.mem_singleton]
          exact Fin.ext (hS t ht)
        have := op562nc_av_mono (op562nc_V h n) (op562nc_V_nonneg h n) hsub
        refine le_trans this (le_of_eq ?_)
        unfold additive_valuation
        rw [Finset.sum_singleton]
        unfold op562nc_V
        show (if h + n - 3 < h then _ else if h + n - 3 < h + n - 3 then (3 : ℝ)
          else (2 / 3 : ℝ) ^ (h + 1)) = (2 / 3) ^ (h + 1)
        rw [if_neg (show ¬ (h + n - 3 < h) by omega), if_neg (show ¬ (h + n - 3 < h + n - 3) by omega)]
      have hα0 : 0 < α := by
        by_contra hc
        push_neg at hc
        have : α * (2 / 3 : ℝ) ^ 3 ≤ 0 := mul_nonpos_of_nonpos_of_nonneg hc (by positivity)
        have : (0 : ℝ) < (2 / 3) ^ (h + 1) := by positivity
        linarith
      have := mul_le_mul_of_nonneg_left (le_trans (hev j2) hbig) hα0.le
      linarith
    
  9. The sum of values of all small goods under profile W is 2 - 2 * (2/3)^h.

    By induction on h using `Finset.sum_range_succ`, the geometric series ∑_{k=0}^{h-1} (2/3)^(k+1) sums to 2 - 2 * (2/3)^h (`op562nc_geom`). Summing over the small goods of profile W evaluates to this sum (`op562nc_T`).

    lines 200–226

    uses Finset.sum_range_succ, op562nc_geom

    theorem op562nc_geom (h : ℕ) :
        ∑ k ∈ Finset.range h, (2 / 3 : ℝ) ^ (k + 1) = 2 - 2 * (2 / 3 : ℝ) ^ h := by
      induction h with
      | zero => simp
      | succ k ih => rw [Finset.sum_range_succ, ih, pow_succ]; ring
    
    theorem op562nc_T (h n : ℕ) (hn : 3 ≤ n) :
        additive_valuation (op562nc_W h n) (Finset.univ.filter (fun t : Fin (h + n - 2) => t.val < h))
          = 2 - 2 * (2 / 3 : ℝ) ^ h := by
      unfold additive_valuation
      rw [Finset.sum_filter]
      have : ∀ t : Fin (h + n - 2), (if t.val < h then op562nc_W h n t else 0) =
          (fun k : ℕ => if k < h then (2 / 3 : ℝ) ^ (k + 1) else 0) t.val := by
        intro t
        simp only [op562nc_W]
        split_ifs <;> rfl
      rw [Finset.sum_congr rfl (fun t _ => this t)]
      rw [Fin.sum_univ_eq_sum_range (fun k : ℕ => if k < h then (2 / 3 : ℝ) ^ (k + 1) else 0)]
      rw [← Finset.sum_filter]
      have hr : (Finset.range (h + n - 2)).filter (fun k => k < h) = Finset.range h := by
        ext k; simp only [Finset.mem_filter, Finset.mem_range]; omega
      rw [hr, op562nc_geom]
    
    theorem op562nc_WQ (h n : ℕ) (g : Fin (h + n - 2)) (hg : g.val < h) :
        op562nc_W h n g = (2 / 3 : ℝ) ^ (g.val + 1) := by
      simp [op562nc_W, hg]
    
  10. In a 1-EEFX allocation for W, an agent holding only small goods worth less than 1 forces all other small goods into a single part.

    If two small goods outside S lay in different parts, or shared a part with a good of value ≥ 1, the EEFX elimination inequality would fail. Hence all remaining small goods must lie in the same part, implying that the total remaining small-goods value minus any single good is at most the agent's bundle value.

    lines 227–329

    uses op562nc_pigeon, op562nc_two_in_part, op562nc_T

    /-- In a 1-EEFX bundle for the exact profile, an agent holding only small goods and worth
    less than 1 must see all other small goods in one part. -/
    theorem op562nc_K (h n : ℕ) (hn : 3 ≤ n) (S : Finset (Fin (h + n - 2)))
        (hbund : is_alpha_eefx_bundle (additive_valuation (op562nc_W h n)) n 1 S)
        (hSQ : ∀ t ∈ S, t.val < h) (hx : additive_valuation (op562nc_W h n) S < 1) :
        ∀ g : Fin (h + n - 2), g.val < h → g ∉ S →
          2 - 2 * (2 / 3 : ℝ) ^ h - additive_valuation (op562nc_W h n) S - op562nc_W h n g
            ≤ additive_valuation (op562nc_W h n) S := by
      classical
      obtain ⟨Y, hdisj, hY, hefx⟩ := hbund
      set av := additive_valuation (op562nc_W h n) with hav
      have hcov : ∀ x, x ∉ S → ∃ p, x ∈ Y p := by
        intro x hx
        have : x ∈ Finset.biUnion Finset.univ Y := by
          rw [hY]; simp [hx]
        simpa using this
      intro g hg hgS
      obtain ⟨p, hp⟩ := hcov g hgS
      have hall : ∀ g' : Fin (h + n - 2), g'.val < h → g' ∉ S → g' ∈ Y p := by
        intro g' hg' hg'S
        by_cases hgg : g' = g
        · rw [hgg]; exact hp
        have hgv : g'.val ≠ g.val := fun h => hgg (Fin.ext h)
        let e : Fin n → Fin (h + n - 2) := fun j =>
          if hj : j.val < n - 3 then ⟨h + j.val, by omega⟩
          else if j.val = n - 3 then ⟨h + n - 3, by omega⟩
          else if j.val = n - 2 then g else g'
        have hev : ∀ j : Fin n, (e j).val = if j.val < n - 3 then h + j.val
            else if j.val = n - 3 then h + n - 3 else if j.val = n - 2 then g.val else g'.val := by
          intro j; simp only [e]; split_ifs <;> rfl
        have he : Function.Injective e := by
          intro a b hab
          have := congrArg Fin.val hab
          rw [hev, hev] at this
          apply Fin.ext
          split_ifs at this <;> omega
        have heS : ∀ j, e j ∉ S := by
          intro j hj
          have hv := hev j
          split_ifs at hv with c1 c2 c3
          · have := hSQ _ hj; omega
          · have := hSQ _ hj; omega
          · have : e j = g := Fin.ext hv
            exact hgS (this ▸ hj)
          · have : e j = g' := Fin.ext hv
            exact hg'S (this ▸ hj)
        obtain ⟨p', j1, j2, hne, h1, h2⟩ := op562nc_pigeon hn Y S hY e he heS
        have hbig : ∀ j, j.val < n - 2 → 1 ≤ op562nc_W h n (e j) := by
          intro j hj
          have hge : h ≤ (e j).val := by rw [hev]; split_ifs <;> omega
          unfold op562nc_W
          rw [if_neg (by omega)]
          split_ifs <;> norm_num
        have hsmall : ∀ ja jb, ja ≠ jb → e ja ∈ Y p' → e jb ∈ Y p' → jb.val < n - 2 → False := by
          intro ja jb hab ha hb hjb
          have h1' := hefx p' (e ja) ha
          have h2' := op562nc_two_in_part (op562nc_W h n) (op562nc_W_nonneg h n) (Y p')
            (fun h => hab (he h)) ha hb
          have := hbig jb hjb
          simp only [one_mul] at h1'
          linarith
        have hj1 : n - 2 ≤ j1.val := by
          by_contra hc; exact hsmall j2 j1 (Ne.symm hne) h2 h1 (by omega)
        have hj2 : n - 2 ≤ j2.val := by
          by_contra hc; exact hsmall j1 j2 hne h1 h2 (by omega)
        have hg_in : g ∈ Y p' ∧ g' ∈ Y p' := by
          have hv : (j1.val = n - 2 ∧ j2.val = n - 1) ∨ (j1.val = n - 1 ∧ j2.val = n - 2) := by
            have := j1.isLt; have := j2.isLt
            have : j1.val ≠ j2.val := fun h => hne (Fin.ext h)
            omega
          rcases hv with ⟨ha, hb⟩ | ⟨ha, hb⟩
          · have e1 : e j1 = g := Fin.ext (by rw [hev]; split_ifs <;> omega)
            have e2 : e j2 = g' := Fin.ext (by rw [hev]; split_ifs <;> omega)
            rw [e1] at h1; rw [e2] at h2; exact ⟨h1, h2⟩
          · have e1 : e j2 = g := Fin.ext (by rw [hev]; split_ifs <;> omega)
            have e2 : e j1 = g' := Fin.ext (by rw [hev]; split_ifs <;> omega)
            rw [e1] at h2; rw [e2] at h1; exact ⟨h2, h1⟩
        have hpp : p = p' := by
          by_contra hc
          have := hdisj p p' hc
          exact Finset.disjoint_left.mp this hp hg_in.1
        rw [hpp]; exact hg_in.2
      set Q := Finset.univ.filter (fun t : Fin (h + n - 2) => t.val < h) with hQ
      have hSsub : S ⊆ Q := by
        intro t ht; simp [hQ, hSQ t ht]
      have hgQ : g ∈ Q \ S := by simp [hQ, hg, hgS]
      have hsub : (Q \ S).erase g ⊆ (Y p).erase g := by
        intro t ht
        rw [Finset.mem_erase] at ht ⊢
        refine ⟨ht.1, ?_⟩
        have ht2 := ht.2
        rw [Finset.mem_sdiff] at ht2
        exact hall t (by simpa [hQ] using ht2.1) ht2.2
      have h1 := op562nc_av_mono (op562nc_W h n) (op562nc_W_nonneg h n) hsub
      have h2 := hefx p g hp
      have h3 : av ((Q \ S).erase g) = av Q - av S - op562nc_W h n g := by
        simp only [hav, additive_valuation]
        rw [Finset.sum_erase_eq_sub hgQ, Finset.sum_sdiff_eq_sub hSsub]
      have hT : av Q = 2 - 2 * (2 / 3 : ℝ) ^ h := by
        rw [hav, hQ]; exact op562nc_T h n hn
      rw [one_mul] at h2
      linarith
    
  11. 3-adic parity distinguishes subsets containing the second smallest good.

    Multiplying the valuation of a set of small goods (excluding the smallest) by 3^(h-1) yields an integer N. Reducing mod 3, every term vanishes except possibly the one corresponding to good h - 2, which equals 2^(h-1) mod 3. Since 2 is non-zero in ZMod 3 (`op562nc_two_ne`), N mod 3 is non-zero precisely when good h - 2 is present.

    lines 330–384

    uses op562nc_WQ, op562nc_two_ne

    /-- Three-adic separation: inside the small goods other than the smallest, the sum of a set
    times `3^(h-1)` is `2^(h-1)` mod 3 when it contains the second smallest good, else 0. -/
    theorem op562nc_three_adic (h n : ℕ) (hh : 2 ≤ h) (X : Finset (Fin (h + n - 2)))
        (hX : ∀ t ∈ X, t.val < h - 1) :
        ∃ N : ℕ, (3 : ℝ) ^ (h - 1) * additive_valuation (op562nc_W h n) X = N ∧
          (N : ZMod 3) = if (∃ t ∈ X, t.val = h - 2) then (2 : ZMod 3) ^ (h - 1) else 0 := by
      classical
      refine ⟨∑ t ∈ X, 2 ^ (t.val + 1) * 3 ^ (h - 2 - t.val), ?_, ?_⟩
      · unfold additive_valuation
        rw [Finset.mul_sum]
        push_cast
        apply Finset.sum_congr rfl
        intro t ht
        have ht' := hX t ht
        rw [op562nc_WQ h n t (by omega)]
        have he : h - 1 = (h - 2 - t.val) + (t.val + 1) := by omega
        rw [he, pow_add, div_pow]
        field_simp
        try ring
      · push_cast
        have hterm : ∀ t ∈ X, ((2 : ZMod 3) ^ (t.val + 1) * (3 : ZMod 3) ^ (h - 2 - t.val)) =
            if t.val = h - 2 then (2 : ZMod 3) ^ (h - 1) else 0 := by
          intro t ht
          have ht' := hX t ht
          split_ifs with heq
          · rw [heq, Nat.sub_self, pow_zero, mul_one]; congr 1; omega
          · have : (3 : ZMod 3) = 0 := by decide
            rw [this, zero_pow (by omega), mul_zero]
        rw [Finset.sum_congr rfl hterm, Finset.sum_ite, Finset.sum_const_zero, add_zero,
          Finset.sum_const]
        by_cases hex : ∃ t ∈ X, t.val = h - 2
        · rw [if_pos hex]
          obtain ⟨t0, ht0, ht0v⟩ := hex
          have hcard : (X.filter (fun t => t.val = h - 2)).card = 1 := by
            rw [Finset.card_eq_one]
            refine ⟨t0, ?_⟩
            ext t
            simp only [Finset.mem_filter, Finset.mem_singleton]
            constructor
            · rintro ⟨_, htv⟩; exact Fin.ext (by omega)
            · rintro rfl; exact ⟨ht0, ht0v⟩
          rw [hcard]; simp
        · rw [if_neg hex]
          have hcard : (X.filter (fun t => t.val = h - 2)) = ∅ := by
            rw [Finset.filter_eq_empty_iff]
            intro t ht htv; exact hex ⟨t, ht, htv⟩
          rw [hcard]; simp
    
    theorem op562nc_two_ne : (2 : ZMod 3) ≠ 0 := by decide
    
    theorem op562nc_two_pow_ne (k : ℕ) : (2 : ZMod 3) ^ k ≠ 0 := by
      haveI : Fact (Nat.Prime 3) := ⟨by norm_num⟩
      exact pow_ne_zero _ op562nc_two_ne
    
    /-- The small-goods lemma for one agent: either worth at least 1, or the 2-part bound. -/
  12. Properties of additive valuations on small goods: additivity on disjoint sets and upper bounds.

    Additive valuation distributes across disjoint unions (`Finset.sum_union`), any subset of small goods is bounded by the total small-goods sum 2 - 2 * (2/3)^h (`op562nc_T`), and single item values lower bound the set valuation (`Finset.single_le_sum`).

    lines 385–407

    uses Finset.sum_union, op562nc_T, Finset.single_le_sum

    def op562nc_Kp (h n : ℕ) (S : Finset (Fin (h + n - 2))) : Prop :=
      (∀ t ∈ S, t.val < h) ∧ (1 ≤ additive_valuation (op562nc_W h n) S ∨
        ∀ g : Fin (h + n - 2), g.val < h → g ∉ S →
          2 - 2 * (2 / 3 : ℝ) ^ h - additive_valuation (op562nc_W h n) S - op562nc_W h n g
            ≤ additive_valuation (op562nc_W h n) S)
    
    theorem op562nc_av_union (h n : ℕ) {A B : Finset (Fin (h + n - 2))} (hAB : Disjoint A B) :
        additive_valuation (op562nc_W h n) (A ∪ B) =
          additive_valuation (op562nc_W h n) A + additive_valuation (op562nc_W h n) B := by
      unfold additive_valuation; exact Finset.sum_union hAB
    
    theorem op562nc_av_le_T (h n : ℕ) (hn : 3 ≤ n) {A : Finset (Fin (h + n - 2))}
        (hA : ∀ t ∈ A, t.val < h) :
        additive_valuation (op562nc_W h n) A ≤ 2 - 2 * (2 / 3 : ℝ) ^ h := by
      rw [← op562nc_T h n hn]
      apply op562nc_av_mono _ (op562nc_W_nonneg h n)
      intro t ht; simp [hA t ht]
    
    theorem op562nc_single_le (h n : ℕ) {A : Finset (Fin (h + n - 2))} {t : Fin (h + n - 2)}
        (ht : t ∈ A) : op562nc_W h n t ≤ additive_valuation (op562nc_W h n) A := by
      unfold additive_valuation
      exact Finset.single_le_sum (f := op562nc_W h n) (fun _ _ => op562nc_W_nonneg h n _) ht
    
  13. No three pairwise disjoint bundles of small goods can all satisfy the EEFX small-goods condition.

    At most one of the three bundles can contain the smallest good d. The other two bundles must each have value at least (2 - 3*(2/3)^h)/2. Summing with the third bundle exceeds the total available small-goods value unless the third bundle contains only d, which then fails the EEFX part inequality. Hence three such bundles cannot exist.

    lines 408–491

    uses op562nc_WQ, op562nc_av_le_T, op562nc_av_union, op562nc_three_aux

    /-- No three disjoint bundles of small goods, two avoiding the smallest good, satisfy the bound. -/
    theorem op562nc_three_aux (h n : ℕ) (hn : 3 ≤ n) (hh : 3 ≤ h)
        (S1 S2 S3 : Finset (Fin (h + n - 2)))
        (h12 : Disjoint S1 S2) (h13 : Disjoint S1 S3) (h23 : Disjoint S2 S3)
        (K1 : op562nc_Kp h n S1) (K2 : op562nc_Kp h n S2) (K3 : op562nc_Kp h n S3)
        (hd1 : ∀ t ∈ S1, t.val ≠ h - 1) (hd2 : ∀ t ∈ S2, t.val ≠ h - 1) : False := by
      classical
      have hδpos : (0 : ℝ) < (2 / 3 : ℝ) ^ h := by positivity
      have hδsmall : (2 / 3 : ℝ) ^ h ≤ 8 / 27 := by
        have : (2 / 3 : ℝ) ^ h ≤ (2 / 3) ^ 3 := pow_le_pow_of_le_one (by norm_num) (by norm_num) hh
        linarith [show ((2 : ℝ) / 3) ^ 3 = 8 / 27 by norm_num]
      let d : Fin (h + n - 2) := ⟨h - 1, by omega⟩
      have hWd : op562nc_W h n d = (2 / 3 : ℝ) ^ h := by
        rw [op562nc_WQ h n d (by show h - 1 < h; omega)]; show (2 / 3 : ℝ) ^ (h - 1 + 1) = (2 / 3) ^ h; congr 1; omega
      have hlow : ∀ S, op562nc_Kp h n S → (∀ t ∈ S, t.val ≠ h - 1) →
          (2 - 2 * (2 / 3 : ℝ) ^ h - (2 / 3 : ℝ) ^ h) / 2 ≤ additive_valuation (op562nc_W h n) S := by
        intro S K hd
        rcases K.2 with h1 | h1
        · linarith
        · have := h1 d (by show h - 1 < h; omega) (fun hm => hd d hm rfl)
          rw [hWd] at this; linarith
      have hx1 := hlow S1 K1 hd1
      have hx2 := hlow S2 K2 hd2
      have hsum : additive_valuation (op562nc_W h n) S1 + additive_valuation (op562nc_W h n) S2
          + additive_valuation (op562nc_W h n) S3 ≤ 2 - 2 * (2 / 3 : ℝ) ^ h := by
        have hu := op562nc_av_le_T h n hn (A := S1 ∪ S2 ∪ S3) (by
          intro t ht
          simp only [Finset.mem_union] at ht
          rcases ht with (ht | ht) | ht
          · exact K1.1 t ht
          · exact K2.1 t ht
          · exact K3.1 t ht)
        rw [op562nc_av_union h n (Finset.disjoint_union_left.mpr ⟨h13, h23⟩),
          op562nc_av_union h n h12] at hu
        linarith
      have hx3 : additive_valuation (op562nc_W h n) S3 ≤ (2 / 3 : ℝ) ^ h := by linarith
      have hS3 : ∀ t ∈ S3, t.val = h - 1 := by
        intro t ht
        by_contra hne
        have htl := K3.1 t ht
        have h1 := op562nc_single_le h n ht
        rw [op562nc_WQ h n t htl] at h1
        have h3 : (2 / 3 : ℝ) ^ (h - 1) ≤ (2 / 3) ^ (t.val + 1) :=
          pow_le_pow_of_le_one (by norm_num) (by norm_num) (by omega)
        have h2 : (2 / 3 : ℝ) ^ h = (2 / 3) ^ (h - 1) * (2 / 3) := by
          rw [← pow_succ]; congr 1; omega
        have h4 : (0 : ℝ) < (2 / 3) ^ (h - 1) := by positivity
        linarith
      rcases K3.2 with h1 | h1
      · linarith
      · let e : Fin (h + n - 2) := ⟨h - 2, by omega⟩
        have h5 := h1 e (by show h - 2 < h; omega) (fun hm => by have := hS3 e hm; change h - 2 = h - 1 at this; omega)
        rw [op562nc_WQ h n e (by show h - 2 < h; omega)] at h5
        have h2 : (2 / 3 : ℝ) ^ h = (2 / 3) ^ (e.val + 1) * (2 / 3) := by
          rw [← pow_succ]; show (2 / 3 : ℝ) ^ h = (2 / 3) ^ (h - 2 + 1 + 1); congr 1; omega
        have h4 : (0 : ℝ) < (2 / 3) ^ (e.val + 1) := by positivity
        linarith
    
    theorem op562nc_three (h n : ℕ) (hn : 3 ≤ n) (hh : 3 ≤ h)
        (S1 S2 S3 : Finset (Fin (h + n - 2)))
        (h12 : Disjoint S1 S2) (h13 : Disjoint S1 S3) (h23 : Disjoint S2 S3)
        (K1 : op562nc_Kp h n S1) (K2 : op562nc_Kp h n S2) (K3 : op562nc_Kp h n S3) : False := by
      -- at most one of the three contains the smallest good
      by_cases c1 : ∀ t ∈ S1, t.val ≠ h - 1
      · by_cases c2 : ∀ t ∈ S2, t.val ≠ h - 1
        · exact op562nc_three_aux h n hn hh S1 S2 S3 h12 h13 h23 K1 K2 K3 c1 c2
        · have c3 : ∀ t ∈ S3, t.val ≠ h - 1 := by
            intro t ht htv
            push_neg at c2
            obtain ⟨t', ht', ht'v⟩ := c2
            have : t = t' := Fin.ext (by omega)
            subst this
            exact Finset.disjoint_left.mp h23 ht' ht
          exact op562nc_three_aux h n hn hh S1 S3 S2 h13 h12 h23.symm K1 K3 K2 c1 c3
      · push_neg at c1
        obtain ⟨t1, ht1, ht1v⟩ := c1
        have hother : ∀ S, Disjoint S1 S → ∀ t ∈ S, t.val ≠ h - 1 := by
          intro S hS t ht htv
          have : t = t1 := Fin.ext (by omega)
          subst this
          exact Finset.disjoint_left.mp hS ht1 ht
        exact op562nc_three_aux h n hn hh S2 S3 S1 h23 h12.symm h13.symm K2 K3 K1
          (hother S2 h12) (hother S3 h13)
    
  14. Two disjoint bundles of small goods satisfying the EEFX condition must cover all small goods.

    If an uncovered small good g0 existed, both bundles would have equal valuation and g0 would have to be the unique smallest good. But then neither bundle contains the smallest good, and by the 3-adic lemma (`op562nc_three_adic`), their integer multiples Nb and Nc must differ mod 3 depending on which bundle contains the second smallest good, contradicting Nb = Nc.

    lines 492–630

    uses op562nc_WQ, op562nc_T, op562nc_av_union, op562nc_three_adic, op562nc_two_pow_ne

    /-- Two disjoint bundles of small goods satisfying the bound cover all small goods. -/
    theorem op562nc_two (h n : ℕ) (hn : 3 ≤ n) (hh : 3 ≤ h)
        (Sb Sc : Finset (Fin (h + n - 2))) (hbc : Disjoint Sb Sc)
        (Kb : op562nc_Kp h n Sb) (Kc : op562nc_Kp h n Sc) :
        ∀ g : Fin (h + n - 2), g.val < h → g ∈ Sb ∨ g ∈ Sc := by
      classical
      set av := additive_valuation (op562nc_W h n) with hav
      set Q := Finset.univ.filter (fun t : Fin (h + n - 2) => t.val < h) with hQ
      have hδpos : (0 : ℝ) < (2 / 3 : ℝ) ^ h := by positivity
      have hWpos : ∀ g, g.val < h → 0 < op562nc_W h n g := by
        intro g hg; rw [op562nc_WQ h n g hg]; positivity
      by_contra hcon
      push_neg at hcon
      obtain ⟨g0, hg0, hg0b, hg0c⟩ := hcon
      set R := Q \ (Sb ∪ Sc) with hR
      have hsubQ : Sb ∪ Sc ⊆ Q := by
        intro t ht
        simp only [Finset.mem_union] at ht
        simp only [hQ, Finset.mem_filter, Finset.mem_univ, true_and]
        rcases ht with ht | ht
        · exact Kb.1 t ht
        · exact Kc.1 t ht
      have hRval : av R = 2 - 2 * (2 / 3 : ℝ) ^ h - av Sb - av Sc := by
        have hT : av Q = 2 - 2 * (2 / 3 : ℝ) ^ h := by rw [hav, hQ]; exact op562nc_T h n hn
        rw [← hT]
        have := op562nc_av_union h n hbc
        rw [← hav] at this
        have h2 : av R = av Q - av (Sb ∪ Sc) := by
          simp only [hR, hav, additive_valuation]
          rw [Finset.sum_sdiff_eq_sub hsubQ]
        rw [h2, this]; ring
      have hmemR : ∀ g, g.val < h → g ∉ Sb → g ∉ Sc → g ∈ R := by
        intro g hg h1 h2
        simp [hR, hQ, hg, h1, h2]
      have hRge : ∀ g, g ∈ R → op562nc_W h n g ≤ av R := fun g hg => op562nc_single_le h n hg
      have hRtwo : ∀ g g', g ∈ R → g' ∈ R → g ≠ g' →
          op562nc_W h n g + op562nc_W h n g' ≤ av R := by
        intro g g' hg hg' hne
        have hsub : ({g, g'} : Finset _) ⊆ R := by
          intro t ht; simp only [Finset.mem_insert, Finset.mem_singleton] at ht
          rcases ht with rfl | rfl <;> assumption
        have := op562nc_av_mono (op562nc_W h n) (op562nc_W_nonneg h n) hsub
        simp only [additive_valuation] at this ⊢
        rwa [Finset.sum_pair hne] at this
      have hg0R := hmemR g0 hg0 hg0b hg0c
      have hW0 := hWpos g0 hg0
      have hbnd : ∀ S, op562nc_Kp h n S → av S < 1 →
          ∀ g, g.val < h → g ∉ S → 2 - 2 * (2 / 3 : ℝ) ^ h - av S - op562nc_W h n g ≤ av S := by
        intro S K hS
        rcases K.2 with h1 | h1
        · linarith
        · exact h1
      have hl := hRge g0 hg0R
      -- both bundles are worth less than 1
      have hb1 : av Sb < 1 := by
        by_contra hc
        push_neg at hc
        have hc1 : av Sc < 1 := by linarith
        have := hbnd Sc Kc hc1 g0 hg0 hg0c
        linarith
      have hc1 : av Sc < 1 := by
        by_contra hc
        push_neg at hc
        have := hbnd Sb Kb hb1 g0 hg0 hg0b
        linarith
      have Bb := hbnd Sb Kb hb1
      have Bc := hbnd Sc Kc hc1
      have e1 := Bb g0 hg0 hg0b
      have e2 := Bc g0 hg0 hg0c
      -- the rest is exactly `g0`, and the two bundles are worth the same
      have hReq : av R = op562nc_W h n g0 := by linarith
      have hxy : av Sb = av Sc := by linarith
      -- every other small good lies in a bundle and is worth at least `g0`
      have hcover : ∀ g, g.val < h → g ≠ g0 → g ∈ Sb ∨ g ∈ Sc := by
        intro g hg hne
        by_contra hc
        push_neg at hc
        have := hRtwo g0 g hg0R (hmemR g hg hc.1 hc.2) (Ne.symm hne)
        have := hWpos g hg
        linarith
      have hge : ∀ g, g.val < h → g ≠ g0 → op562nc_W h n g0 ≤ op562nc_W h n g := by
        intro g hg hne
        rcases hcover g hg hne with hgb | hgc
        · have hgc : g ∉ Sc := fun hm => Finset.disjoint_left.mp hbc hgb hm
          have := Bc g hg hgc; linarith
        · have hgb : g ∉ Sb := fun hm => Finset.disjoint_left.mp hbc hm hgc
          have := Bb g hg hgb; linarith
      -- so `g0` is the smallest good
      have hg0d : g0.val = h - 1 := by
        by_contra hne
        let d : Fin (h + n - 2) := ⟨h - 1, by omega⟩
        have hdv : d.val = h - 1 := rfl
        have h1 := hge d (by rw [hdv]; omega) (fun hm => hne (by rw [← hm]))
        rw [op562nc_WQ h n d (by rw [hdv]; omega), op562nc_WQ h n g0 hg0, hdv] at h1
        have h2 : (2 / 3 : ℝ) ^ (h - 1 + 1) < (2 / 3) ^ (g0.val + 1) :=
          pow_lt_pow_right_of_lt_one₀ (by norm_num) (by norm_num) (by omega)
        linarith
      -- three-adic contradiction on the second smallest good
      have hXb : ∀ t ∈ Sb, t.val < h - 1 := by
        intro t ht
        have := Kb.1 t ht
        have : t ≠ g0 := fun he => hg0b (he ▸ ht)
        have : t.val ≠ g0.val := fun he => this (Fin.ext he)
        omega
      have hXc : ∀ t ∈ Sc, t.val < h - 1 := by
        intro t ht
        have := Kc.1 t ht
        have : t ≠ g0 := fun he => hg0c (he ▸ ht)
        have : t.val ≠ g0.val := fun he => this (Fin.ext he)
        omega
      obtain ⟨Nb, hNb, hNbm⟩ := op562nc_three_adic h n (by omega) Sb hXb
      obtain ⟨Nc, hNc, hNcm⟩ := op562nc_three_adic h n (by omega) Sc hXc
      have hN : Nb = Nc := by
        have : (Nb : ℝ) = Nc := by
          rw [← hNb, ← hNc]; exact congrArg (fun x => (3 : ℝ) ^ (h - 1) * x) hxy
        exact_mod_cast this
      let e : Fin (h + n - 2) := ⟨h - 2, by omega⟩
      have hne : e ≠ g0 := fun he => by
        have := congrArg Fin.val he; change h - 2 = g0.val at this; omega
      have hz := op562nc_two_pow_ne (h - 1)
      rcases hcover e (by show h - 2 < h; omega) hne with heb | hec
      · have hnc : ¬ ∃ t ∈ Sc, t.val = h - 2 := by
          rintro ⟨t, ht, htv⟩
          have : t = e := Fin.ext (by show t.val = h - 2; omega)
          exact Finset.disjoint_left.mp hbc heb (this ▸ ht)
        rw [if_pos ⟨e, heb, rfl⟩] at hNbm
        rw [if_neg hnc] at hNcm
        rw [hN, hNcm] at hNbm
        exact hz hNbm.symm
      · have hnb : ¬ ∃ t ∈ Sb, t.val = h - 2 := by
          rintro ⟨t, ht, htv⟩
          have : t = e := Fin.ext (by show t.val = h - 2; omega)
          exact Finset.disjoint_left.mp hbc (this ▸ ht) hec
        rw [if_pos ⟨e, hec, rfl⟩] at hNcm
        rw [if_neg hnb] at hNbm
        rw [hN] at hNbm
        rw [hNbm] at hNcm
        exact hz hNcm.symm
    
  15. In any 1-EEFX allocation of W, the owner of the last good receives no other good.

    There are n - 3 large goods of value 3, so at least 3 agents receive no large goods. If the owner of the last good also received another good, three agents would hold only small goods satisfying the EEFX condition (`op562nc_K`), which contradicts `op562nc_three`. Furthermore, two such agents cover all small goods (`op562nc_two`), leaving no other goods for the owner of the last good.

    lines 631–704

    uses op562nc_K, op562nc_two, op562nc_bundle_disj, op562nc_three

    theorem op562nc_bundle_disj {m n : ℕ} (σ : Fin m → Fin n) {i j : Fin n} (hij : i ≠ j) :
        Disjoint (bundle_of σ i) (bundle_of σ j) := by
      rw [Finset.disjoint_left]
      intro t ht1 ht2
      simp only [bundle_of, Finset.mem_filter, Finset.mem_univ, true_and] at ht1 ht2
      exact hij (ht1.symm.trans ht2)
    
    /-- Consistency on the exact profile forces the owner of the last good to own nothing else. -/
    theorem op562nc_force (h n : ℕ) (hn : 3 ≤ n) (hh : 3 ≤ h) (σ : Fin (h + n - 2) → Fin n)
        (hσ : is_alpha_eefx_allocation (fun _ => additive_valuation (op562nc_W h n)) 1 σ) :
        ∀ t : Fin (h + n - 2), t.val ≠ h + n - 3 → σ t ≠ σ ⟨h + n - 3, by omega⟩ := by
      classical
      set L : Fin (h + n - 2) := ⟨h + n - 3, by omega⟩ with hL
      have hLv : L.val = h + n - 3 := rfl
      let Jfree : Fin n → Prop := fun i =>
        ∀ j : Fin (h + n - 2), h ≤ j.val → j.val < h + n - 3 → σ j ≠ i
      have hK : ∀ i, Jfree i → σ L ≠ i → op562nc_Kp h n (bundle_of σ i) := by
        intro i hJ hLi
        have hQ : ∀ t ∈ bundle_of σ i, t.val < h := by
          intro t ht
          simp only [bundle_of, Finset.mem_filter, Finset.mem_univ, true_and] at ht
          by_contra hc
          have := t.isLt
          by_cases ht2 : t.val < h + n - 3
          · exact hJ t (by omega) ht2 ht
          · have : t = L := Fin.ext (by rw [hLv]; omega)
            exact hLi (this ▸ ht)
        refine ⟨hQ, ?_⟩
        by_cases h1 : 1 ≤ additive_valuation (op562nc_W h n) (bundle_of σ i)
        · exact Or.inl h1
        · exact Or.inr (op562nc_K h n hn _ (hσ i) hQ (by linarith))
      have hcount : 2 < (Finset.univ.filter Jfree).card := by
        have hA : (Finset.univ.filter (fun i => ¬ Jfree i)) ⊆
            Finset.univ.image (fun j : Fin (n - 3) => σ ⟨h + j.val, by omega⟩) := by
          intro i hi
          simp only [Finset.mem_filter, Finset.mem_univ, true_and, Jfree] at hi
          push_neg at hi
          obtain ⟨j, hj1, hj2, hj3⟩ := hi
          simp only [Finset.mem_image, Finset.mem_univ, true_and]
          refine ⟨⟨j.val - h, by omega⟩, ?_⟩
          rw [← hj3]
          congr 1
          exact Fin.ext (by show h + (j.val - h) = j.val; omega)
        have h1 := Finset.card_le_card hA
        have h2 := Finset.card_image_le (s := (Finset.univ : Finset (Fin (n - 3))))
          (f := fun j : Fin (n - 3) => σ ⟨h + j.val, by omega⟩)
        have h3 := Finset.card_filter_add_card_filter_not
          (s := (Finset.univ : Finset (Fin n))) Jfree
        simp only [Finset.card_univ, Fintype.card_fin] at h2 h3
        omega
      obtain ⟨b1, hb1, b2, hb2, b3, hb3, h12, h13, h23⟩ := Finset.two_lt_card.mp hcount
      simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hb1 hb2 hb3
      have hfin : ∀ a b c, Jfree a → Jfree b → Jfree c → a ≠ b → a ≠ c → b ≠ c → σ L = a →
          ∀ t : Fin (h + n - 2), t.val ≠ h + n - 3 → σ t ≠ a := by
        intro a b c ha hb hc hab hac hbc hLa t ht hta
        have hcov := op562nc_two h n hn hh (bundle_of σ b) (bundle_of σ c)
          (op562nc_bundle_disj σ hbc) (hK b hb (by rw [hLa]; exact hab))
          (hK c hc (by rw [hLa]; exact hac))
        by_cases htl : t.val < h
        · rcases hcov t htl with h1 | h1 <;>
            simp only [bundle_of, Finset.mem_filter, Finset.mem_univ, true_and] at h1
          · exact hab (hta.symm.trans h1)
          · exact hac (hta.symm.trans h1)
        · exact ha t (by omega) (by have := t.isLt; omega) hta
      intro t ht
      by_cases c1 : σ L = b1
      · rw [c1]; exact hfin b1 b2 b3 hb1 hb2 hb3 h12 h13 h23 c1 t ht
      by_cases c2 : σ L = b2
      · rw [c2]; exact hfin b2 b1 b3 hb2 hb1 hb3 (Ne.symm h12) h23 h13 c2 t ht
      by_cases c3 : σ L = b3
      · rw [c3]; exact hfin b3 b1 b2 hb3 hb1 hb2 (Ne.symm h13) (Ne.symm h23) h12 c3 t ht
      exact (op562nc_three h n hn hh _ _ _ (op562nc_bundle_disj σ h12) (op562nc_bundle_disj σ h13)
        (op562nc_bundle_disj σ h23) (hK b1 hb1 c1) (hK b2 hb2 c2) (hK b3 hb3 c3)).elim
    
  16. Assume for contradiction an online algorithm exists, choose h large enough, and set up guarantees on W and V.

    We assume for contradiction that an online algorithm guarantees α-EEFX under error factor ρ ≥ 3/2. We choose h = k + 3 large enough so that (2/3)^(h+1) < α * (2/3)^3. Consistency gives a 1-EEFX allocation on W, and the overestimate guarantee gives an α-EEFX allocation on V with prediction W.

    lines 705–719

    uses exists_pow_lt_of_lt_one, pow_le_pow_of_le_one, lt_of_le_of_lt, op562nc_W_nonneg, op562nc_V_nonneg, op562nc_overestimate

    /-- For n >= 3, no consistent online algorithm guarantees positive EEFX approximation for error factor rho >= 3/2. -/
    theorem op562_not_consistent_eefx_of_ge_three_halves (n : ℕ) (hn : 3 ≤ n) (ρ : ℝ)
        (hρ : 3 / 2 ≤ ρ) :
        ¬ has_consistent_eefx_algorithm n ρ := by
      rintro ⟨alg, α, hα, hon, hcons, hguar⟩
      obtain ⟨k, hk⟩ := exists_pow_lt_of_lt_one (show 0 < α * (2 / 3 : ℝ) ^ 3 by positivity)
        (show (2 / 3 : ℝ) < 1 by norm_num)
      have hh : 3 ≤ k + 3 := by omega
      have hsmall : (2 / 3 : ℝ) ^ (k + 3 + 1) < α * (2 / 3) ^ 3 :=
        lt_of_le_of_lt (pow_le_pow_of_le_one (by norm_num) (by norm_num) (by omega)) hk
      have hσ := hcons (k + 3 + n - 2) (fun _ => op562nc_W (k + 3) n) (fun _ => op562nc_W (k + 3) n)
        (fun _ g => op562nc_W_nonneg (k + 3) n g) (fun _ => rfl)
      have hσ' := hguar (k + 3 + n - 2) (fun _ => op562nc_V (k + 3) n)
        (fun _ => op562nc_W (k + 3) n) (fun _ g => op562nc_V_nonneg (k + 3) n g)
        (op562nc_overestimate (k + 3) n hn ρ hρ)
  17. The online algorithm makes identical allocation decisions on all goods prior to the last good.

    Because the profiles V and W are identical for all goods arriving before the last good, and the online algorithm's decisions depend only on prefixes of the valuation sequence, the allocations of all earlier goods coincide in both runs.

    lines 720–730

      have hsame : ∀ t : Fin (k + 3 + n - 2), t.val ≠ k + 3 + n - 3 →
          alg (k + 3 + n - 2) (fun _ => op562nc_W (k + 3) n) (fun _ => op562nc_V (k + 3) n) t =
          alg (k + 3 + n - 2) (fun _ => op562nc_W (k + 3) n) (fun _ => op562nc_W (k + 3) n) t := by
        intro t ht
        apply hon
        intro s hs i
        show op562nc_V (k + 3) n s = op562nc_W (k + 3) n s
        have hs' : s.val ≤ t.val := hs
        have : s.val < k + 3 + n - 3 := by have := t.isLt; omega
        unfold op562nc_V op562nc_W
        split_ifs <;> first | rfl | omega
  18. The agent holding the last good violates α-EEFX under profile V, completing the contradiction.

    By `op562nc_force`, the agent receiving the last good under W receives no other good. Because decisions on earlier goods coincide, this agent receives no other goods under V either, so their bundle consists solely of the last good. But by `op562nc_fail`, such a bundle cannot satisfy α-EEFX under V, contradicting the algorithm's guarantee.

    lines 731–737

    uses op562nc_force, op562nc_fail

      have hforce := op562nc_force (k + 3) n hn hh _ hσ
      refine op562nc_fail (k + 3) n hn hh α hsmall _ ?_ (hσ' (alg (k + 3 + n - 2)
        (fun _ => op562nc_W (k + 3) n) (fun _ => op562nc_W (k + 3) n) ⟨k + 3 + n - 3, by omega⟩))
      intro t ht
      simp only [bundle_of, Finset.mem_filter, Finset.mem_univ, true_and] at ht
      by_contra hne
      exact hforce t hne (by rw [← hsame t hne]; exact ht)
Tuple.comp_sort_eq_comp_iff_monotone
A permutation of a tuple sorts it in increasing order if and only if the composition is monotone.
op562nc_sorted_eq
If composing a tuple with a permutation σ is monotone, then σ sorts the tuple.
op562nc_sorted_W
The sorted values of profile W: the first h+1 goods are (2/3)^(h - r), and the remaining goods have value 3.
op562nc_sorted_V
The sorted values of profile V: the first h+1 goods are (2/3)^(h + 1 - r), and the remaining goods have value 3.
pow_succ
a^(n + 1) = a^n * a.
Fintype.exists_ne_map_eq_of_card_lt
If a finite domain is strictly larger than the codomain, any function between them maps two distinct elements to the same value.
op562nc_av_mono
Additive valuation with non-negative item values is monotonic under subset inclusion.
op562nc_pigeon
When partitioning goods into n - 1 parts outside a bundle S, any collection of n goods outside S has two items in the same part.
op562nc_two_in_part
If two distinct goods are in a part, removing one leaves a bundle worth at least the value of the other.
Finset.sum_range_succ
The sum over range (n + 1) equals the sum over range n plus the term at n.
op562nc_geom
The sum of powers (2/3)^(k+1) from k = 0 to h - 1 equals 2 - 2 * (2/3)^h.
op562nc_T
The total value under profile W of all small goods (index < h) is 2 - 2 * (2/3)^h.
op562nc_WQ
For any small good g (index < h), its value under W is (2/3)^(g + 1).
op562nc_two_ne
2 is non-zero in the field ZMod 3.
Finset.sum_union
The sum of a function over the union of two disjoint finite sets is the sum of the sums over each set.
Finset.single_le_sum
The value of a single non-negative item in a set is at most the total additive valuation of the set.
op562nc_av_le_T
The additive valuation of any set of small goods under W is at most the total small-goods value 2 - 2 * (2/3)^h.
op562nc_av_union
Additive valuation distributes over the union of disjoint sets.
op562nc_three_aux
Three disjoint bundles of small goods cannot all satisfy the EEFX small-goods condition if two avoid the smallest good.
op562nc_three_adic
Multiplying the value of a subset of small goods (excluding the smallest) by 3^(h-1) yields an integer whose residue mod 3 is non-zero if and only if it contains the second smallest good.
op562nc_two_pow_ne
Powers of 2 are non-zero in ZMod 3.
op562nc_K
In a 1-EEFX bundle of small goods with value < 1 under profile W, all other small goods must be packed into a single part, giving a lower bound on the bundle.
op562nc_two
Any two disjoint bundles of small goods satisfying the EEFX condition must cover all small goods.
op562nc_bundle_disj
Bundles allocated to distinct agents are disjoint.
op562nc_three
There cannot exist three pairwise disjoint bundles of small goods all satisfying the EEFX small-goods condition.
exists_pow_lt_of_lt_one
For any positive real and base r < 1, there exists an exponent k such that r^k is smaller than that real.
pow_le_pow_of_le_one
Powers of a number in [0, 1] decrease as the exponent increases.
lt_of_le_of_lt
Combining a ≤ b and b < c yields a < c.
op562nc_W_nonneg
All goods have non-negative values in profile W.
op562nc_V_nonneg
All goods have non-negative values in profile V.
op562nc_overestimate
Profile W is an overestimate prediction of profile V with error factor ρ ≥ 3/2.
op562nc_force
In any 1-EEFX allocation under profile W, the agent who receives the last good receives nothing else.
op562nc_fail
An agent whose bundle contains only the last good does not satisfy α-EEFX under profile V when the last good's value is less than α * (2/3)^3.

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

Lean’s trace was cut to the first 400 of 952 tactics.

/-- The predicted (and exact) common value profile: `h` goods of values `(2/3)^(t+1)`,then `n - 3` goods of value `3`, then a last good of value `1`. -/noncomputable def op562nc_W (h n : ℕ) : Fin (h + n - 2) → ℝ := fun t =>  if t.val < h then (2 / 3 : ℝ) ^ (t.val + 1) else if t.val < h + n - 3 then 3 else 1/-- The true profile: as `op562nc_W`, but the last good is worth `(2/3)^(h+1)`. -/noncomputable def op562nc_V (h n : ℕ) : Fin (h + n - 2) → ℝ := fun t =>  if t.val < h then (2 / 3 : ℝ) ^ (t.val + 1) else if t.val < h + n - 3 then 3  else (2 / 3 : ℝ) ^ (h + 1)theorem op562nc_sorted_eq {m : ℕ} (f : Fin m → ℝ) (σ : Equiv.Perm (Fin m))    (hmono : Monotone (f ∘ σ)) : sorted_tuple f = f ∘ σ := by  unfold sorted_tuple  exact ((Tuple.comp_sort_eq_comp_iff_monotone).mpr hmono).symmtheorem op562nc_sorted_W (h n : ℕ) (hn : 3 ≤ n) :    ∀ r : Fin (h + n - 2), sorted_tuple (op562nc_W h n) r =      if r.val ≤ h then (2 / 3 : ℝ) ^ (h - r.val) else 3 := by  let f : Fin (h + n - 2) → Fin (h + n - 2) := fun r =>    if hr : r.val < h then ⟨h - 1 - r.val, by omega⟩    else if r.val = h then ⟨h + n - 3, by omega⟩ else ⟨r.val - 1, by omega⟩  have hf : Function.Injective f := by    intro a b hab    simp only [f] at hab    apply Fin.ext    split_ifs at hab <;> simp only [Fin.mk.injEq] at hab <;> omega  let σ : Equiv.Perm (Fin (h + n - 2)) := Equiv.ofBijective f (Finite.injective_iff_bijective.mp hf)  have hfv : ∀ r, (σ r).val = if r.val < h then h - 1 - r.val      else if r.val = h then h + n - 3 else r.val - 1 := by    intro r    simp only [σ, Equiv.ofBijective_apply, f]    split_ifs <;> rfl  have hval : ∀ r, op562nc_W h n (σ r) = if r.val ≤ h then (2 / 3 : ℝ) ^ (h - r.val) else 3 := by    intro r    unfold op562nc_W    rw [hfv r]    split_ifs <;> first | omega | rfl | (rw [show h - r.val = 0 by omega, pow_zero]) | (congr 1; omega)  have hmono : Monotone (op562nc_W h n ∘ σ) := by    intro a b hab    simp only [Function.comp, hval]    have hab' : a.val ≤ b.val := hab    split_ifs with h1 h2 h2    · exact pow_le_pow_of_le_one (by norm_num) (by norm_num) (by omega)    · exact le_trans (pow_le_one₀ (by norm_num) (by norm_num)) (by norm_num)    · omega    · exact le_refl _  intro r  rw [op562nc_sorted_eq _ σ hmono]  exact hval rtheorem op562nc_sorted_V (h n : ℕ) (hn : 3 ≤ n) :    ∀ r : Fin (h + n - 2), sorted_tuple (op562nc_V h n) r =      if r.val ≤ h then (2 / 3 : ℝ) ^ (h + 1 - r.val) else 3 := by  let f : Fin (h + n - 2) → Fin (h + n - 2) := fun r =>    if r.val = 0 then ⟨h + n - 3, by omega⟩    else if hr : r.val ≤ h then ⟨h - r.val, by omega⟩ else ⟨r.val - 1, by omega⟩  have hf : Function.Injective f := by    intro a b hab    simp only [f] at hab    apply Fin.ext    split_ifs at hab <;> simp only [Fin.mk.injEq] at hab <;> omega  let σ : Equiv.Perm (Fin (h + n - 2)) := Equiv.ofBijective f (Finite.injective_iff_bijective.mp hf)  have hfv : ∀ r, (σ r).val = if r.val = 0 then h + n - 3      else if r.val ≤ h then h - r.val else r.val - 1 := by    intro r    simp only [σ, Equiv.ofBijective_apply, f]    split_ifs <;> rfl  have hval : ∀ r, op562nc_V h n (σ r) =      if r.val ≤ h then (2 / 3 : ℝ) ^ (h + 1 - r.val) else 3 := by    intro r    unfold op562nc_V    rw [hfv r]    split_ifs <;> first | omega | rfl | (congr 1; omega)  have hmono : Monotone (op562nc_V h n ∘ σ) := by    intro a b hab    simp only [Function.comp, hval]    have hab' : a.val ≤ b.val := hab    split_ifs with h1 h2 h2    · exact pow_le_pow_of_le_one (by norm_num) (by norm_num) (by omega)    · exact le_trans (pow_le_one₀ (by norm_num) (by norm_num)) (by norm_num)    · omega    · exact le_refl _  intro r  rw [op562nc_sorted_eq _ σ hmono]  exact hval rtheorem op562nc_overestimate (h n : ℕ) (hn : 3 ≤ n) (ρ : ℝ) (hρ : 3 / 2 ≤ ρ) :    is_overestimate_prediction ρ (fun _ : Fin n => op562nc_V h n)      (fun _ : Fin n => op562nc_W h n) := by  intro i r  simp only  rw [op562nc_sorted_W h n hn r, op562nc_sorted_V h n hn r]  split_ifs with hr  · have he : h + 1 - r.val = (h - r.val) + 1 := by omega    rw [he, pow_succ]    have hp : (0 : ℝ) ≤ (2 / 3 : ℝ) ^ (h - r.val) := by positivity    constructor    · nlinarith    · nlinarith  · constructor    · exact le_refl _    · nlinarith/-- Pigeonhole for EEFX partitions: `n` distinct goods outside the bundle, two share a part. -/theorem op562nc_pigeon {m n : ℕ} (hn : 3 ≤ n) (Y : Fin (n - 1) → Finset (Fin m))    (S : Finset (Fin m)) (hY : Finset.biUnion Finset.univ Y = Finset.univ \ S)    (e : Fin n → Fin m) (he : Function.Injective e) (hS : ∀ j, e j ∉ S) :    ∃ p, ∃ j1 j2, j1 ≠ j2 ∧ e j1 ∈ Y p ∧ e j2 ∈ Y p := by  classical  have hcov : ∀ x, x ∉ S → ∃ p, x ∈ Y p := by    intro x hx    have : x ∈ Finset.biUnion Finset.univ Y := by      rw [hY]; simp [hx]    simpa using this  let part : Fin m → Fin (n - 1) := fun x =>    if hx : ∃ p, x ∈ Y p then Classical.choose hx else ⟨0, by omega⟩  have hpart : ∀ x, x ∉ S → x ∈ Y (part x) := by    intro x hx    simp only [part, dif_pos (hcov x hx)]    exact Classical.choose_spec (hcov x hx)  obtain ⟨j1, j2, hne, heq⟩ := Fintype.exists_ne_map_eq_of_card_lt (part ∘ e)    (by simp; omega)  refine ⟨part (e j1), j1, j2, hne, hpart _ (hS j1), ?_⟩  have := hpart _ (hS j2)  simp only [Function.comp] at heq  rwa [heq]theorem op562nc_av_mono {m : ℕ} (u : Fin m → ℝ) (hu : ∀ g, 0 ≤ u g) {A B : Finset (Fin m)}    (hAB : A ⊆ B) : additive_valuation u A ≤ additive_valuation u B :=  Finset.sum_le_sum_of_subset_of_nonneg hAB (fun _ _ _ => hu _)/-- Two distinct goods in one part: erasing one leaves at least the other's value. -/theorem op562nc_two_in_part {m : ℕ} (u : Fin m → ℝ) (hu : ∀ g, 0 ≤ u g) (P : Finset (Fin m))    {a b : Fin m} (hab : a ≠ b) (ha : a ∈ P) (hb : b ∈ P) :    u b ≤ additive_valuation u (P.erase a) := by  have : ({b} : Finset (Fin m)) ⊆ P.erase a := by    intro x hx    rw [Finset.mem_singleton] at hx    subst hx    exact Finset.mem_erase.mpr ⟨fun h => hab h.symm, hb⟩  have := op562nc_av_mono u hu this  simpa [additive_valuation] using thistheorem op562nc_V_nonneg (h n : ℕ) : ∀ g, 0 ≤ op562nc_V h n g := by  intro g; unfold op562nc_V; split_ifs <;> positivitytheorem op562nc_W_nonneg (h n : ℕ) : ∀ g, 0 ≤ op562nc_W h n g := by  intro g; unfold op562nc_W; split_ifs <;> positivity/-- The inexact instance: an agent whose bundle is inside the last good is not α-EEFX. -/theorem op562nc_fail (h n : ℕ) (hn : 3 ≤ n) (hh : 3 ≤ h) (α : ℝ)    (hα : (2 / 3 : ℝ) ^ (h + 1) < α * (2 / 3) ^ 3) (S : Finset (Fin (h + n - 2)))    (hS : ∀ t ∈ S, t.val = h + n - 3) :    ¬ is_alpha_eefx_bundle (additive_valuation (op562nc_V h n)) n α S := by  rintro ⟨Y, _hdisj, hY, hefx⟩  let e : Fin n → Fin (h + n - 2) := fun j =>    if j.val < 3 then ⟨j.val, by omega⟩ else ⟨h + j.val - 3, by omega⟩  have he : Function.Injective e := by    intro a b hab    simp only [e] at hab    apply Fin.ext    split_ifs at hab <;> simp only [Fin.mk.injEq] at hab <;> omega  have heS : ∀ j, e j ∉ S := by    intro j hj    have := hS _ hj    simp only [e] at this    split_ifs at this <;> simp only at this <;> omega  have hev : ∀ j, (2 / 3 : ℝ) ^ 3 ≤ op562nc_V h n (e j) := by    intro j    simp only [e, op562nc_V]    split_ifs with h1 h2 h3 h4 h5 <;> simp only at * <;> try omega    · exact pow_le_pow_of_le_one (by norm_num) (by norm_num) (by omega)    · norm_num  obtain ⟨p, j1, j2, hne, h1, h2⟩ := op562nc_pigeon hn Y S hY e he heS  have hle := hefx p (e j1) h1  have hbig := op562nc_two_in_part (op562nc_V h n) (op562nc_V_nonneg h n) (Y p)    (fun h => hne (he h)) h1 h2  have hSv : additive_valuation (op562nc_V h n) S ≤ (2 / 3 : ℝ) ^ (h + 1) := by    have hsub : S ⊆ {(⟨h + n - 3, by omega⟩ : Fin (h + n - 2))} := by      intro t ht      rw [Finset.mem_singleton]      exact Fin.ext (hS t ht)    have := op562nc_av_mono (op562nc_V h n) (op562nc_V_nonneg h n) hsub    refine le_trans this (le_of_eq ?_)    unfold additive_valuation    rw [Finset.sum_singleton]    unfold op562nc_V    show (if h + n - 3 < h then _ else if h + n - 3 < h + n - 3 then (3 : ℝ)      else (2 / 3 : ℝ) ^ (h + 1)) = (2 / 3) ^ (h + 1)    rw [if_neg (show ¬ (h + n - 3 < h) by omega), if_neg (show ¬ (h + n - 3 < h + n - 3) by omega)]  have hα0 : 0 < α := by    by_contra hc    push_neg at hc    have : α * (2 / 3 : ℝ) ^ 3 ≤ 0 := mul_nonpos_of_nonpos_of_nonneg hc (by positivity)    have : (0 : ℝ) < (2 / 3) ^ (h + 1) := by positivity    linarith  have := mul_le_mul_of_nonneg_left (le_trans (hev j2) hbig) hα0.le  linariththeorem op562nc_geom (h : ℕ) :    ∑ k ∈ Finset.range h, (2 / 3 : ℝ) ^ (k + 1) = 2 - 2 * (2 / 3 : ℝ) ^ h := by  induction h with  | zero => simp  | succ k ih => rw [Finset.sum_range_succ, ih, pow_succ]; ringtheorem op562nc_T (h n : ℕ) (hn : 3 ≤ n) :    additive_valuation (op562nc_W h n) (Finset.univ.filter (fun t : Fin (h + n - 2) => t.val < h))      = 2 - 2 * (2 / 3 : ℝ) ^ h := by  unfold additive_valuation  rw [Finset.sum_filter]  have : ∀ t : Fin (h + n - 2), (if t.val < h then op562nc_W h n t else 0) =      (fun k : ℕ => if k < h then (2 / 3 : ℝ) ^ (k + 1) else 0) t.val := by    intro t    simp only [op562nc_W]    split_ifs <;> rfl  rw [Finset.sum_congr rfl (fun t _ => this t)]  rw [Fin.sum_univ_eq_sum_range (fun k : ℕ => if k < h then (2 / 3 : ℝ) ^ (k + 1) else 0)]  rw [← Finset.sum_filter]  have hr : (Finset.range (h + n - 2)).filter (fun k => k < h) = Finset.range h := by    ext k; simp only [Finset.mem_filter, Finset.mem_range]; omega  rw [hr, op562nc_geom]theorem op562nc_WQ (h n : ℕ) (g : Fin (h + n - 2)) (hg : g.val < h) :    op562nc_W h n g = (2 / 3 : ℝ) ^ (g.val + 1) := by  simp [op562nc_W, hg]/-- In a 1-EEFX bundle for the exact profile, an agent holding only small goods and worthless than 1 must see all other small goods in one part. -/theorem op562nc_K (h n : ℕ) (hn : 3 ≤ n) (S : Finset (Fin (h + n - 2)))    (hbund : is_alpha_eefx_bundle (additive_valuation (op562nc_W h n)) n 1 S)    (hSQ : ∀ t ∈ S, t.val < h) (hx : additive_valuation (op562nc_W h n) S < 1) :    ∀ g : Fin (h + n - 2), g.val < h → g ∉ S →      2 - 2 * (2 / 3 : ℝ) ^ h - additive_valuation (op562nc_W h n) S - op562nc_W h n g        ≤ additive_valuation (op562nc_W h n) S := by  classical  obtain ⟨Y, hdisj, hY, hefx⟩ := hbund  set av := additive_valuation (op562nc_W h n) with hav  have hcov : ∀ x, x ∉ S → ∃ p, x ∈ Y p := by    intro x hx    have : x ∈ Finset.biUnion Finset.univ Y := by      rw [hY]; simp [hx]    simpa using this  intro g hg hgS  obtain ⟨p, hp⟩ := hcov g hgS  have hall : ∀ g' : Fin (h + n - 2), g'.val < h → g' ∉ S → g' ∈ Y p := by    intro g' hg' hg'S    by_cases hgg : g' = g    · rw [hgg]; exact hp    have hgv : g'.val ≠ g.val := fun h => hgg (Fin.ext h)    let e : Fin n → Fin (h + n - 2) := fun j =>      if hj : j.val < n - 3 then ⟨h + j.val, by omega⟩      else if j.val = n - 3 then ⟨h + n - 3, by omega⟩      else if j.val = n - 2 then g else g'    have hev : ∀ j : Fin n, (e j).val = if j.val < n - 3 then h + j.val        else if j.val = n - 3 then h + n - 3 else if j.val = n - 2 then g.val else g'.val := by      intro j; simp only [e]; split_ifs <;> rfl    have he : Function.Injective e := by      intro a b hab      have := congrArg Fin.val hab      rw [hev, hev] at this      apply Fin.ext      split_ifs at this <;> omega    have heS : ∀ j, e j ∉ S := by      intro j hj      have hv := hev j      split_ifs at hv with c1 c2 c3      · have := hSQ _ hj; omega      · have := hSQ _ hj; omega      · have : e j = g := Fin.ext hv        exact hgS (this ▸ hj)      · have : e j = g' := Fin.ext hv        exact hg'S (this ▸ hj)    obtain ⟨p', j1, j2, hne, h1, h2⟩ := op562nc_pigeon hn Y S hY e he heS    have hbig : ∀ j, j.val < n - 2 → 1 ≤ op562nc_W h n (e j) := by      intro j hj      have hge : h ≤ (e j).val := by rw [hev]; split_ifs <;> omega      unfold op562nc_W      rw [if_neg (by omega)]      split_ifs <;> norm_num    have hsmall : ∀ ja jb, ja ≠ jb → e ja ∈ Y p' → e jb ∈ Y p' → jb.val < n - 2 → False := by      intro ja jb hab ha hb hjb      have h1' := hefx p' (e ja) ha      have h2' := op562nc_two_in_part (op562nc_W h n) (op562nc_W_nonneg h n) (Y p')        (fun h => hab (he h)) ha hb      have := hbig jb hjb      simp only [one_mul] at h1'      linarith    have hj1 : n - 2 ≤ j1.val := by      by_contra hc; exact hsmall j2 j1 (Ne.symm hne) h2 h1 (by omega)    have hj2 : n - 2 ≤ j2.val := by      by_contra hc; exact hsmall j1 j2 hne h1 h2 (by omega)    have hg_in : g ∈ Y p' ∧ g' ∈ Y p' := by      have hv : (j1.val = n - 2 ∧ j2.val = n - 1) ∨ (j1.val = n - 1 ∧ j2.val = n - 2) := by        have := j1.isLt; have := j2.isLt        have : j1.val ≠ j2.val := fun h => hne (Fin.ext h)        omega      rcases hv with ⟨ha, hb⟩ | ⟨ha, hb⟩      · have e1 : e j1 = g := Fin.ext (by rw [hev]; split_ifs <;> omega)        have e2 : e j2 = g' := Fin.ext (by rw [hev]; split_ifs <;> omega)        rw [e1] at h1; rw [e2] at h2; exact ⟨h1, h2⟩      · have e1 : e j2 = g := Fin.ext (by rw [hev]; split_ifs <;> omega)        have e2 : e j1 = g' := Fin.ext (by rw [hev]; split_ifs <;> omega)        rw [e1] at h2; rw [e2] at h1; exact ⟨h2, h1⟩    have hpp : p = p' := by      by_contra hc      have := hdisj p p' hc      exact Finset.disjoint_left.mp this hp hg_in.1    rw [hpp]; exact hg_in.2  set Q := Finset.univ.filter (fun t : Fin (h + n - 2) => t.val < h) with hQ  have hSsub : S ⊆ Q := by    intro t ht; simp [hQ, hSQ t ht]  have hgQ : g ∈ Q \ S := by simp [hQ, hg, hgS]  have hsub : (Q \ S).erase g ⊆ (Y p).erase g := by    intro t ht    rw [Finset.mem_erase] at ht ⊢    refine ⟨ht.1, ?_⟩    have ht2 := ht.2    rw [Finset.mem_sdiff] at ht2    exact hall t (by simpa [hQ] using ht2.1) ht2.2  have h1 := op562nc_av_mono (op562nc_W h n) (op562nc_W_nonneg h n) hsub  have h2 := hefx p g hp  have h3 : av ((Q \ S).erase g) = av Q - av S - op562nc_W h n g := by    simp only [hav, additive_valuation]    rw [Finset.sum_erase_eq_sub hgQ, Finset.sum_sdiff_eq_sub hSsub]  have hT : av Q = 2 - 2 * (2 / 3 : ℝ) ^ h := by    rw [hav, hQ]; exact op562nc_T h n hn  rw [one_mul] at h2  linarith/-- Three-adic separation: inside the small goods other than the smallest, the sum of a settimes `3^(h-1)` is `2^(h-1)` mod 3 when it contains the second smallest good, else 0. -/theorem op562nc_three_adic (h n : ℕ) (hh : 2 ≤ h) (X : Finset (Fin (h + n - 2)))    (hX : ∀ t ∈ X, t.val < h - 1) :    ∃ N : ℕ, (3 : ℝ) ^ (h - 1) * additive_valuation (op562nc_W h n) X = N ∧      (N : ZMod 3) = if (∃ t ∈ X, t.val = h - 2) then (2 : ZMod 3) ^ (h - 1) else 0 := by  classical  refine ⟨∑ t ∈ X, 2 ^ (t.val + 1) * 3 ^ (h - 2 - t.val), ?_, ?_⟩  · unfold additive_valuation    rw [Finset.mul_sum]    push_cast    apply Finset.sum_congr rfl    intro t ht    have ht' := hX t ht    rw [op562nc_WQ h n t (by omega)]    have he : h - 1 = (h - 2 - t.val) + (t.val + 1) := by omega    rw [he, pow_add, div_pow]    field_simp    try ring  · push_cast    have hterm : ∀ t ∈ X, ((2 : ZMod 3) ^ (t.val + 1) * (3 : ZMod 3) ^ (h - 2 - t.val)) =        if t.val = h - 2 then (2 : ZMod 3) ^ (h - 1) else 0 := by      intro t ht      have ht' := hX t ht      split_ifs with heq      · rw [heq, Nat.sub_self, pow_zero, mul_one]; congr 1; omega      · have : (3 : ZMod 3) = 0 := by decide        rw [this, zero_pow (by omega), mul_zero]    rw [Finset.sum_congr rfl hterm, Finset.sum_ite, Finset.sum_const_zero, add_zero,      Finset.sum_const]    by_cases hex : ∃ t ∈ X, t.val = h - 2    · rw [if_pos hex]      obtain ⟨t0, ht0, ht0v⟩ := hex      have hcard : (X.filter (fun t => t.val = h - 2)).card = 1 := by        rw [Finset.card_eq_one]        refine ⟨t0, ?_⟩        ext t        simp only [Finset.mem_filter, Finset.mem_singleton]        constructor        · rintro ⟨_, htv⟩; exact Fin.ext (by omega)        · rintro rfl; exact ⟨ht0, ht0v⟩      rw [hcard]; simp    · rw [if_neg hex]      have hcard : (X.filter (fun t => t.val = h - 2)) = ∅ := by        rw [Finset.filter_eq_empty_iff]        intro t ht htv; exact hex ⟨t, ht, htv⟩      rw [hcard]; simptheorem op562nc_two_ne : (2 : ZMod 3) ≠ 0 := by decidetheorem op562nc_two_pow_ne (k : ℕ) : (2 : ZMod 3) ^ k ≠ 0 := by  haveI : Fact (Nat.Prime 3) := ⟨by norm_num⟩  exact pow_ne_zero _ op562nc_two_ne/-- The small-goods lemma for one agent: either worth at least 1, or the 2-part bound. -/def op562nc_Kp (h n : ℕ) (S : Finset (Fin (h + n - 2))) : Prop :=  (∀ t ∈ S, t.val < h) ∧ (1 ≤ additive_valuation (op562nc_W h n) S ∨    ∀ g : Fin (h + n - 2), g.val < h → g ∉ S →      2 - 2 * (2 / 3 : ℝ) ^ h - additive_valuation (op562nc_W h n) S - op562nc_W h n g        ≤ additive_valuation (op562nc_W h n) S)theorem op562nc_av_union (h n : ℕ) {A B : Finset (Fin (h + n - 2))} (hAB : Disjoint A B) :    additive_valuation (op562nc_W h n) (A ∪ B) =      additive_valuation (op562nc_W h n) A + additive_valuation (op562nc_W h n) B := by  unfold additive_valuation; exact Finset.sum_union hABtheorem op562nc_av_le_T (h n : ℕ) (hn : 3 ≤ n) {A : Finset (Fin (h + n - 2))}    (hA : ∀ t ∈ A, t.val < h) :    additive_valuation (op562nc_W h n) A ≤ 2 - 2 * (2 / 3 : ℝ) ^ h := by  rw [← op562nc_T h n hn]  apply op562nc_av_mono _ (op562nc_W_nonneg h n)  intro t ht; simp [hA t ht]theorem op562nc_single_le (h n : ℕ) {A : Finset (Fin (h + n - 2))} {t : Fin (h + n - 2)}    (ht : t ∈ A) : op562nc_W h n t ≤ additive_valuation (op562nc_W h n) A := by  unfold additive_valuation  exact Finset.single_le_sum (f := op562nc_W h n) (fun _ _ => op562nc_W_nonneg h n _) ht/-- No three disjoint bundles of small goods, two avoiding the smallest good, satisfy the bound. -/theorem op562nc_three_aux (h n : ℕ) (hn : 3 ≤ n) (hh : 3 ≤ h)    (S1 S2 S3 : Finset (Fin (h + n - 2)))    (h12 : Disjoint S1 S2) (h13 : Disjoint S1 S3) (h23 : Disjoint S2 S3)    (K1 : op562nc_Kp h n S1) (K2 : op562nc_Kp h n S2) (K3 : op562nc_Kp h n S3)    (hd1 : ∀ t ∈ S1, t.val ≠ h - 1) (hd2 : ∀ t ∈ S2, t.val ≠ h - 1) : False := by  classical  have hδpos : (0 : ℝ) < (2 / 3 : ℝ) ^ h := by positivity  have hδsmall : (2 / 3 : ℝ) ^ h ≤ 8 / 27 := by    have : (2 / 3 : ℝ) ^ h ≤ (2 / 3) ^ 3 := pow_le_pow_of_le_one (by norm_num) (by norm_num) hh    linarith [show ((2 : ℝ) / 3) ^ 3 = 8 / 27 by norm_num]  let d : Fin (h + n - 2) := ⟨h - 1, by omega⟩  have hWd : op562nc_W h n d = (2 / 3 : ℝ) ^ h := by    rw [op562nc_WQ h n d (by show h - 1 < h; omega)]; show (2 / 3 : ℝ) ^ (h - 1 + 1) = (2 / 3) ^ h; congr 1; omega  have hlow : ∀ S, op562nc_Kp h n S → (∀ t ∈ S, t.val ≠ h - 1) →      (2 - 2 * (2 / 3 : ℝ) ^ h - (2 / 3 : ℝ) ^ h) / 2 ≤ additive_valuation (op562nc_W h n) S := by    intro S K hd    rcases K.2 with h1 | h1    · linarith    · have := h1 d (by show h - 1 < h; omega) (fun hm => hd d hm rfl)      rw [hWd] at this; linarith  have hx1 := hlow S1 K1 hd1  have hx2 := hlow S2 K2 hd2  have hsum : additive_valuation (op562nc_W h n) S1 + additive_valuation (op562nc_W h n) S2      + additive_valuation (op562nc_W h n) S3 ≤ 2 - 2 * (2 / 3 : ℝ) ^ h := by    have hu := op562nc_av_le_T h n hn (A := S1 ∪ S2 ∪ S3) (by      intro t ht      simp only [Finset.mem_union] at ht      rcases ht with (ht | ht) | ht      · exact K1.1 t ht      · exact K2.1 t ht      · exact K3.1 t ht)    rw [op562nc_av_union h n (Finset.disjoint_union_left.mpr ⟨h13, h23⟩),      op562nc_av_union h n h12] at hu    linarith  have hx3 : additive_valuation (op562nc_W h n) S3 ≤ (2 / 3 : ℝ) ^ h := by linarith  have hS3 : ∀ t ∈ S3, t.val = h - 1 := by    intro t ht    by_contra hne    have htl := K3.1 t ht    have h1 := op562nc_single_le h n ht    rw [op562nc_WQ h n t htl] at h1    have h3 : (2 / 3 : ℝ) ^ (h - 1) ≤ (2 / 3) ^ (t.val + 1) :=      pow_le_pow_of_le_one (by norm_num) (by norm_num) (by omega)    have h2 : (2 / 3 : ℝ) ^ h = (2 / 3) ^ (h - 1) * (2 / 3) := by      rw [← pow_succ]; congr 1; omega    have h4 : (0 : ℝ) < (2 / 3) ^ (h - 1) := by positivity    linarith  rcases K3.2 with h1 | h1  · linarith  · let e : Fin (h + n - 2) := ⟨h - 2, by omega⟩    have h5 := h1 e (by show h - 2 < h; omega) (fun hm => by have := hS3 e hm; change h - 2 = h - 1 at this; omega)    rw [op562nc_WQ h n e (by show h - 2 < h; omega)] at h5    have h2 : (2 / 3 : ℝ) ^ h = (2 / 3) ^ (e.val + 1) * (2 / 3) := by      rw [← pow_succ]; show (2 / 3 : ℝ) ^ h = (2 / 3) ^ (h - 2 + 1 + 1); congr 1; omega    have h4 : (0 : ℝ) < (2 / 3) ^ (e.val + 1) := by positivity    linariththeorem op562nc_three (h n : ℕ) (hn : 3 ≤ n) (hh : 3 ≤ h)    (S1 S2 S3 : Finset (Fin (h + n - 2)))    (h12 : Disjoint S1 S2) (h13 : Disjoint S1 S3) (h23 : Disjoint S2 S3)    (K1 : op562nc_Kp h n S1) (K2 : op562nc_Kp h n S2) (K3 : op562nc_Kp h n S3) : False := by  -- at most one of the three contains the smallest good  by_cases c1 : ∀ t ∈ S1, t.val ≠ h - 1  · by_cases c2 : ∀ t ∈ S2, t.val ≠ h - 1    · exact op562nc_three_aux h n hn hh S1 S2 S3 h12 h13 h23 K1 K2 K3 c1 c2    · have c3 : ∀ t ∈ S3, t.val ≠ h - 1 := by        intro t ht htv        push_neg at c2        obtain ⟨t', ht', ht'v⟩ := c2        have : t = t' := Fin.ext (by omega)        subst this        exact Finset.disjoint_left.mp h23 ht' ht      exact op562nc_three_aux h n hn hh S1 S3 S2 h13 h12 h23.symm K1 K3 K2 c1 c3  · push_neg at c1    obtain ⟨t1, ht1, ht1v⟩ := c1    have hother : ∀ S, Disjoint S1 S → ∀ t ∈ S, t.val ≠ h - 1 := by      intro S hS t ht htv      have : t = t1 := Fin.ext (by omega)      subst this      exact Finset.disjoint_left.mp hS ht1 ht    exact op562nc_three_aux h n hn hh S2 S3 S1 h23 h12.symm h13.symm K2 K3 K1      (hother S2 h12) (hother S3 h13)/-- Two disjoint bundles of small goods satisfying the bound cover all small goods. -/theorem op562nc_two (h n : ℕ) (hn : 3 ≤ n) (hh : 3 ≤ h)    (Sb Sc : Finset (Fin (h + n - 2))) (hbc : Disjoint Sb Sc)    (Kb : op562nc_Kp h n Sb) (Kc : op562nc_Kp h n Sc) :    ∀ g : Fin (h + n - 2), g.val < h → g ∈ Sb ∨ g ∈ Sc := by  classical  set av := additive_valuation (op562nc_W h n) with hav  set Q := Finset.univ.filter (fun t : Fin (h + n - 2) => t.val < h) with hQ  have hδpos : (0 : ℝ) < (2 / 3 : ℝ) ^ h := by positivity  have hWpos : ∀ g, g.val < h → 0 < op562nc_W h n g := by    intro g hg; rw [op562nc_WQ h n g hg]; positivity  by_contra hcon  push_neg at hcon  obtain ⟨g0, hg0, hg0b, hg0c⟩ := hcon  set R := Q \ (Sb ∪ Sc) with hR  have hsubQ : Sb ∪ Sc ⊆ Q := by    intro t ht    simp only [Finset.mem_union] at ht    simp only [hQ, Finset.mem_filter, Finset.mem_univ, true_and]    rcases ht with ht | ht    · exact Kb.1 t ht    · exact Kc.1 t ht  have hRval : av R = 2 - 2 * (2 / 3 : ℝ) ^ h - av Sb - av Sc := by    have hT : av Q = 2 - 2 * (2 / 3 : ℝ) ^ h := by rw [hav, hQ]; exact op562nc_T h n hn    rw [← hT]    have := op562nc_av_union h n hbc    rw [← hav] at this    have h2 : av R = av Q - av (Sb ∪ Sc) := by      simp only [hR, hav, additive_valuation]      rw [Finset.sum_sdiff_eq_sub hsubQ]    rw [h2, this]; ring  have hmemR : ∀ g, g.val < h → g ∉ Sb → g ∉ Sc → g ∈ R := by    intro g hg h1 h2    simp [hR, hQ, hg, h1, h2]  have hRge : ∀ g, g ∈ R → op562nc_W h n g ≤ av R := fun g hg => op562nc_single_le h n hg  have hRtwo : ∀ g g', g ∈ R → g' ∈ R → g ≠ g' →      op562nc_W h n g + op562nc_W h n g' ≤ av R := by    intro g g' hg hg' hne    have hsub : ({g, g'} : Finset _) ⊆ R := by      intro t ht; simp only [Finset.mem_insert, Finset.mem_singleton] at ht      rcases ht with rfl | rfl <;> assumption    have := op562nc_av_mono (op562nc_W h n) (op562nc_W_nonneg h n) hsub    simp only [additive_valuation] at this ⊢    rwa [Finset.sum_pair hne] at this  have hg0R := hmemR g0 hg0 hg0b hg0c  have hW0 := hWpos g0 hg0  have hbnd : ∀ S, op562nc_Kp h n S → av S < 1 →      ∀ g, g.val < h → g ∉ S → 2 - 2 * (2 / 3 : ℝ) ^ h - av S - op562nc_W h n g ≤ av S := by    intro S K hS    rcases K.2 with h1 | h1    · linarith    · exact h1  have hl := hRge g0 hg0R  -- both bundles are worth less than 1  have hb1 : av Sb < 1 := by    by_contra hc    push_neg at hc    have hc1 : av Sc < 1 := by linarith    have := hbnd Sc Kc hc1 g0 hg0 hg0c    linarith  have hc1 : av Sc < 1 := by    by_contra hc    push_neg at hc    have := hbnd Sb Kb hb1 g0 hg0 hg0b    linarith  have Bb := hbnd Sb Kb hb1  have Bc := hbnd Sc Kc hc1  have e1 := Bb g0 hg0 hg0b  have e2 := Bc g0 hg0 hg0c  -- the rest is exactly `g0`, and the two bundles are worth the same  have hReq : av R = op562nc_W h n g0 := by linarith  have hxy : av Sb = av Sc := by linarith  -- every other small good lies in a bundle and is worth at least `g0`  have hcover : ∀ g, g.val < h → g ≠ g0 → g ∈ Sb ∨ g ∈ Sc := by    intro g hg hne    by_contra hc    push_neg at hc    have := hRtwo g0 g hg0R (hmemR g hg hc.1 hc.2) (Ne.symm hne)    have := hWpos g hg    linarith  have hge : ∀ g, g.val < h → g ≠ g0 → op562nc_W h n g0 ≤ op562nc_W h n g := by    intro g hg hne    rcases hcover g hg hne with hgb | hgc    · have hgc : g ∉ Sc := fun hm => Finset.disjoint_left.mp hbc hgb hm      have := Bc g hg hgc; linarith    · have hgb : g ∉ Sb := fun hm => Finset.disjoint_left.mp hbc hm hgc      have := Bb g hg hgb; linarith  -- so `g0` is the smallest good  have hg0d : g0.val = h - 1 := by    by_contra hne    let d : Fin (h + n - 2) := ⟨h - 1, by omega⟩    have hdv : d.val = h - 1 := rfl    have h1 := hge d (by rw [hdv]; omega) (fun hm => hne (by rw [← hm]))    rw [op562nc_WQ h n d (by rw [hdv]; omega), op562nc_WQ h n g0 hg0, hdv] at h1    have h2 : (2 / 3 : ℝ) ^ (h - 1 + 1) < (2 / 3) ^ (g0.val + 1) :=      pow_lt_pow_right_of_lt_one₀ (by norm_num) (by norm_num) (by omega)    linarith  -- three-adic contradiction on the second smallest good  have hXb : ∀ t ∈ Sb, t.val < h - 1 := by    intro t ht    have := Kb.1 t ht    have : t ≠ g0 := fun he => hg0b (he ▸ ht)    have : t.val ≠ g0.val := fun he => this (Fin.ext he)    omega  have hXc : ∀ t ∈ Sc, t.val < h - 1 := by    intro t ht    have := Kc.1 t ht    have : t ≠ g0 := fun he => hg0c (he ▸ ht)    have : t.val ≠ g0.val := fun he => this (Fin.ext he)    omega  obtain ⟨Nb, hNb, hNbm⟩ := op562nc_three_adic h n (by omega) Sb hXb  obtain ⟨Nc, hNc, hNcm⟩ := op562nc_three_adic h n (by omega) Sc hXc  have hN : Nb = Nc := by    have : (Nb : ℝ) = Nc := by      rw [← hNb, ← hNc]; exact congrArg (fun x => (3 : ℝ) ^ (h - 1) * x) hxy    exact_mod_cast this  let e : Fin (h + n - 2) := ⟨h - 2, by omega⟩  have hne : e ≠ g0 := fun he => by    have := congrArg Fin.val he; change h - 2 = g0.val at this; omega  have hz := op562nc_two_pow_ne (h - 1)  rcases hcover e (by show h - 2 < h; omega) hne with heb | hec  · have hnc : ¬ ∃ t ∈ Sc, t.val = h - 2 := by      rintro ⟨t, ht, htv⟩      have : t = e := Fin.ext (by show t.val = h - 2; omega)      exact Finset.disjoint_left.mp hbc heb (this ▸ ht)    rw [if_pos ⟨e, heb, rfl⟩] at hNbm    rw [if_neg hnc] at hNcm    rw [hN, hNcm] at hNbm    exact hz hNbm.symm  · have hnb : ¬ ∃ t ∈ Sb, t.val = h - 2 := by      rintro ⟨t, ht, htv⟩      have : t = e := Fin.ext (by show t.val = h - 2; omega)      exact Finset.disjoint_left.mp hbc (this ▸ ht) hec    rw [if_pos ⟨e, hec, rfl⟩] at hNcm    rw [if_neg hnb] at hNbm    rw [hN] at hNbm    rw [hNbm] at hNcm    exact hz hNcm.symmtheorem op562nc_bundle_disj {m n : ℕ} (σ : Fin m → Fin n) {i j : Fin n} (hij : i ≠ j) :    Disjoint (bundle_of σ i) (bundle_of σ j) := by  rw [Finset.disjoint_left]  intro t ht1 ht2  simp only [bundle_of, Finset.mem_filter, Finset.mem_univ, true_and] at ht1 ht2  exact hij (ht1.symm.trans ht2)/-- Consistency on the exact profile forces the owner of the last good to own nothing else. -/theorem op562nc_force (h n : ℕ) (hn : 3 ≤ n) (hh : 3 ≤ h) (σ : Fin (h + n - 2) → Fin n)    (hσ : is_alpha_eefx_allocation (fun _ => additive_valuation (op562nc_W h n)) 1 σ) :    ∀ t : Fin (h + n - 2), t.val ≠ h + n - 3 → σ t ≠ σ ⟨h + n - 3, by omega⟩ := by  classical  set L : Fin (h + n - 2) := ⟨h + n - 3, by omega⟩ with hL  have hLv : L.val = h + n - 3 := rfl  let Jfree : Fin n → Prop := fun i =>    ∀ j : Fin (h + n - 2), h ≤ j.val → j.val < h + n - 3 → σ j ≠ i  have hK : ∀ i, Jfree i → σ L ≠ i → op562nc_Kp h n (bundle_of σ i) := by    intro i hJ hLi    have hQ : ∀ t ∈ bundle_of σ i, t.val < h := by      intro t ht      simp only [bundle_of, Finset.mem_filter, Finset.mem_univ, true_and] at ht      by_contra hc      have := t.isLt      by_cases ht2 : t.val < h + n - 3      · exact hJ t (by omega) ht2 ht      · have : t = L := Fin.ext (by rw [hLv]; omega)        exact hLi (this ▸ ht)    refine ⟨hQ, ?_⟩    by_cases h1 : 1 ≤ additive_valuation (op562nc_W h n) (bundle_of σ i)    · exact Or.inl h1    · exact Or.inr (op562nc_K h n hn _ (hσ i) hQ (by linarith))  have hcount : 2 < (Finset.univ.filter Jfree).card := by    have hA : (Finset.univ.filter (fun i => ¬ Jfree i)) ⊆        Finset.univ.image (fun j : Fin (n - 3) => σ ⟨h + j.val, by omega⟩) := by      intro i hi      simp only [Finset.mem_filter, Finset.mem_univ, true_and, Jfree] at hi      push_neg at hi      obtain ⟨j, hj1, hj2, hj3⟩ := hi      simp only [Finset.mem_image, Finset.mem_univ, true_and]      refine ⟨⟨j.val - h, by omega⟩, ?_⟩      rw [← hj3]      congr 1      exact Fin.ext (by show h + (j.val - h) = j.val; omega)    have h1 := Finset.card_le_card hA    have h2 := Finset.card_image_le (s := (Finset.univ : Finset (Fin (n - 3))))      (f := fun j : Fin (n - 3) => σ ⟨h + j.val, by omega⟩)    have h3 := Finset.card_filter_add_card_filter_not      (s := (Finset.univ : Finset (Fin n))) Jfree    simp only [Finset.card_univ, Fintype.card_fin] at h2 h3    omega  obtain ⟨b1, hb1, b2, hb2, b3, hb3, h12, h13, h23⟩ := Finset.two_lt_card.mp hcount  simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hb1 hb2 hb3  have hfin : ∀ a b c, Jfree a → Jfree b → Jfree c → a ≠ b → a ≠ c → b ≠ c → σ L = a →      ∀ t : Fin (h + n - 2), t.val ≠ h + n - 3 → σ t ≠ a := by    intro a b c ha hb hc hab hac hbc hLa t ht hta    have hcov := op562nc_two h n hn hh (bundle_of σ b) (bundle_of σ c)      (op562nc_bundle_disj σ hbc) (hK b hb (by rw [hLa]; exact hab))      (hK c hc (by rw [hLa]; exact hac))    by_cases htl : t.val < h    · rcases hcov t htl with h1 | h1 <;>        simp only [bundle_of, Finset.mem_filter, Finset.mem_univ, true_and] at h1      · exact hab (hta.symm.trans h1)      · exact hac (hta.symm.trans h1)    · exact ha t (by omega) (by have := t.isLt; omega) hta  intro t ht  by_cases c1 : σ L = b1  · rw [c1]; exact hfin b1 b2 b3 hb1 hb2 hb3 h12 h13 h23 c1 t ht  by_cases c2 : σ L = b2  · rw [c2]; exact hfin b2 b1 b3 hb2 hb1 hb3 (Ne.symm h12) h23 h13 c2 t ht  by_cases c3 : σ L = b3  · rw [c3]; exact hfin b3 b1 b2 hb3 hb1 hb2 (Ne.symm h13) (Ne.symm h23) h12 c3 t ht  exact (op562nc_three h n hn hh _ _ _ (op562nc_bundle_disj σ h12) (op562nc_bundle_disj σ h13)    (op562nc_bundle_disj σ h23) (hK b1 hb1 c1) (hK b2 hb2 c2) (hK b3 hb3 c3)).elim/-- For n >= 3, no consistent online algorithm guarantees positive EEFX approximation for error factor rho >= 3/2. -/theorem op562_not_consistent_eefx_of_ge_three_halves (n : ℕ) (hn : 3 ≤ n) (ρ : ℝ)    (hρ : 3 / 2 ≤ ρ) :    ¬ has_consistent_eefx_algorithm n ρ := by  rintro ⟨alg, α, hα, hon, hcons, hguar⟩  obtain ⟨k, hk⟩ := exists_pow_lt_of_lt_one (show 0 < α * (2 / 3 : ℝ) ^ 3 by positivity)    (show (2 / 3 : ℝ) < 1 by norm_num)  have hh : 3 ≤ k + 3 := by omega  have hsmall : (2 / 3 : ℝ) ^ (k + 3 + 1) < α * (2 / 3) ^ 3 :=    lt_of_le_of_lt (pow_le_pow_of_le_one (by norm_num) (by norm_num) (by omega)) hk  have hσ := hcons (k + 3 + n - 2) (fun _ => op562nc_W (k + 3) n) (fun _ => op562nc_W (k + 3) n)    (fun _ g => op562nc_W_nonneg (k + 3) n g) (fun _ => rfl)  have hσ' := hguar (k + 3 + n - 2) (fun _ => op562nc_V (k + 3) n)    (fun _ => op562nc_W (k + 3) n) (fun _ g => op562nc_V_nonneg (k + 3) n g)    (op562nc_overestimate (k + 3) n hn ρ hρ)  have hsame : ∀ t : Fin (k + 3 + n - 2), t.val ≠ k + 3 + n - 3 →      alg (k + 3 + n - 2) (fun _ => op562nc_W (k + 3) n) (fun _ => op562nc_V (k + 3) n) t =      alg (k + 3 + n - 2) (fun _ => op562nc_W (k + 3) n) (fun _ => op562nc_W (k + 3) n) t := by    intro t ht    apply hon    intro s hs i    show op562nc_V (k + 3) n s = op562nc_W (k + 3) n s    have hs' : s.val ≤ t.val := hs    have : s.val < k + 3 + n - 3 := by have := t.isLt; omega    unfold op562nc_V op562nc_W    split_ifs <;> first | rfl | omega  have hforce := op562nc_force (k + 3) n hn hh _ hσ  refine op562nc_fail (k + 3) n hn hh α hsmall _ ?_ (hσ' (alg (k + 3 + n - 2)    (fun _ => op562nc_W (k + 3) n) (fun _ => op562nc_W (k + 3) n) ⟨k + 3 + n - 3, by omega⟩))  intro t ht  simp only [bundle_of, Finset.mem_filter, Finset.mem_univ, true_and] at ht  by_contra hne  exact hforce t hne (by rw [← hsame t hne]; exact ht)
See it in the graphDiscuss this resultChallenge it