import Mathlib open Finset lemma fs_map_aux : ∀ (x : Stream' ℕ) (m : ℕ), m ∈ Hindman.FS x → ∀ a : Stream' ℕ+, x = a.map (fun p : ℕ+ => (p : ℕ)) → ∃ p ∈ Hindman.FS a, (p : ℕ) = m := by intro x m h induction h with | head' x => rintro a rfl exact ⟨a.head, Hindman.FS.head _, by simp⟩ | tail' x m _ ih => rintro a rfl obtain ⟨p, hp, hpe⟩ := ih a.tail (by rw [Stream'.tail_map]) exact ⟨p, Hindman.FS.tail _ _ hp, hpe⟩ | cons' x m _ ih => rintro a rfl obtain ⟨p, hp, hpe⟩ := ih a.tail (by rw [Stream'.tail_map]) exact ⟨a.head + p, Hindman.FS.cons _ _ hp, by simp [hpe]⟩ theorem erdos_task : open Finset in ∀ c : ℕ → Fin 2, ∃ a : ℕ → ℕ, StrictMono a ∧ 0 < a 0 ∧ ∃ col : Fin 2, ∀ T : Finset ℕ, T.Nonempty → c (∑ i ∈ T, a i) = col := by intro c obtain ⟨S, hS, b, hb⟩ := Hindman.exists_FS_of_finite_cover (M := ℕ+) (Set.range (fun j : Fin 2 => {m : ℕ+ | c m = j})) (Set.finite_range _) (by intro m _; exact Set.mem_sUnion.2 ⟨_, ⟨c m, rfl⟩, rfl⟩) obtain ⟨col, rfl⟩ := hS set B : ℕ → ℕ := fun i => (b.get i : ℕ) with hBdef have hBpos : ∀ i, 0 < B i := fun i => (b.get i).pos have hFS : ∀ F : Finset ℕ, F.Nonempty → c (∑ i ∈ F, B i) = col := by intro F hF have h1 := Hindman.FS.finsetSum (b.map (fun x : ℕ+ => (x:ℕ))) F hF obtain ⟨p, hp, hpeq⟩ := fs_map_aux _ _ h1 b rfl have := hb hp simp only [Set.mem_ofPred_eq] at this rw [← this, hpeq] simp [hBdef, Stream'.get_map] let s : ℕ → ℕ := fun k => Nat.rec 0 (fun k sk => sk + 1 + ∑ i ∈ range sk, B i) k have hs : ∀ k, s (k+1) = s k + 1 + ∑ i ∈ range (s k), B i := fun k => rfl have hs0 : s 0 = 0 := rfl have smono : StrictMono s := strictMono_nat_of_lt_succ (fun k => by rw [hs]; omega) refine ⟨fun k => ∑ i ∈ Ico (s k) (s (k+1)), B i, ?_, ?_, col, ?_⟩ · refine strictMono_nat_of_lt_succ (fun k => ?_) have h1 : ∑ i ∈ Ico (s k) (s (k+1)), B i ≤ ∑ i ∈ range (s (k+1)), B i := by apply sum_le_sum_of_subset rw [range_eq_Ico] exact Ico_subset_Ico (Nat.zero_le _) le_rfl have h2 : ∑ i ∈ Ico (s (k+1)) (s (k+1+1)), 1 ≤ ∑ i ∈ Ico (s (k+1)) (s (k+1+1)), B i := sum_le_sum (fun i _ => hBpos i) simp only [sum_const, Nat.card_Ico, smul_eq_mul, mul_one] at h2 have h3 := hs (k+1) show ∑ i ∈ Ico (s k) (s (k+1)), B i < ∑ i ∈ Ico (s (k+1)) (s (k+1+1)), B i omega · show 0 < ∑ i ∈ Ico (s 0) (s (0+1)), B i rw [hs 0, hs0] simpa using hBpos 0 · intro T hT rw [← sum_biUnion] · apply hFS exact hT.biUnion (fun k _ => nonempty_Ico.2 (smono (lt_add_one k))) · intro k _ l _ hkl simp only [Function.onFun] rcases lt_or_gt_of_ne hkl with h | h · rw [Finset.disjoint_left] intro i hi hi' rw [mem_Ico] at hi hi' have := smono.monotone (show k + 1 ≤ l by omega) omega · rw [Finset.disjoint_left] intro i hi hi' rw [mem_Ico] at hi hi' have := smono.monotone (show l + 1 ≤ k by omega) omega