import Mathlib lemma key_compl {m : ℕ} (A X : Finset (Fin m)) : (Aᶜ ∩ X).card + (A ∩ X).card = X.card := by have h := Finset.card_inter_add_card_sdiff X A have e1 : Aᶜ ∩ X = X \ A := by ext x; simp; tauto rw [e1, Finset.inter_comm]; omega theorem erdos_task : ∀ (n : ℕ), ∃ F : Finset (Finset (Fin (4 * n))), (∀ A ∈ F, A.card = 2 * n) ∧ (∀ A ∈ F, ∀ B ∈ F, 2 ≤ (A ∩ B).card) ∧ F.card = ((4 * n).choose (2 * n) - (2 * n).choose n ^ 2) / 2 := by intro n classical let X : Finset (Fin (4*n)) := Finset.univ.filter (fun i => i.val < 2*n) have hX : X.card = 2*n := by have := Fin.card_filter_val_lt (n := 4*n) (m := 2*n) simp only [X] rw [this]; omega have hXc : Xᶜ.card = 2*n := by rw [Finset.card_compl, hX, Fintype.card_fin]; omega let S : Finset (Finset (Fin (4*n))) := Finset.univ.powersetCard (2*n) have hS : S.card = (4*n).choose (2*n) := by simp [S, Finset.card_powersetCard] refine ⟨S.filter (fun A => n+1 ≤ (A ∩ X).card), ?_, ?_, ?_⟩ · intro A hA simp only [S, Finset.mem_filter, Finset.mem_powersetCard] at hA exact hA.1.2 · intro A hA B hB simp only [S, Finset.mem_filter, Finset.mem_powersetCard] at hA hB have h1 := Finset.card_union_add_card_inter (A ∩ X) (B ∩ X) have h2 : ((A ∩ X) ∪ (B ∩ X)).card ≤ X.card := Finset.card_le_card (by intro x; simp; tauto) have h3 : ((A ∩ X) ∩ (B ∩ X)).card ≤ (A ∩ B).card := Finset.card_le_card (by intro x; simp; tauto) omega · have e1 := Finset.card_filter_add_card_filter_not (s := S) (fun A => n+1 ≤ (A ∩ X).card) have e2 := Finset.card_filter_add_card_filter_not (s := S.filter (fun A => ¬ n+1 ≤ (A ∩ X).card)) (fun A => (A ∩ X).card = n) rw [Finset.filter_filter, Finset.filter_filter] at e2 have hFG : (S.filter (fun A => n+1 ≤ (A ∩ X).card)).card = (S.filter (fun A => ¬ n+1 ≤ (A ∩ X).card ∧ ¬ (A ∩ X).card = n)).card := by apply Finset.card_nbij' (fun A => Aᶜ) (fun A => Aᶜ) · intro A hA simp only [S, Finset.coe_filter, Finset.mem_powersetCard, Set.mem_setOf_eq] at hA ⊢ have := key_compl A X have hc : Aᶜ.card = 2 * n := by rw [Finset.card_compl, hA.1.2, Fintype.card_fin]; omega refine ⟨⟨Finset.subset_univ _, hc⟩, by omega, by omega⟩ · intro A hA simp only [S, Finset.coe_filter, Finset.mem_powersetCard, Set.mem_setOf_eq] at hA ⊢ have := key_compl A X have hc : Aᶜ.card = 2 * n := by rw [Finset.card_compl, hA.1.2, Fintype.card_fin]; omega refine ⟨⟨Finset.subset_univ _, hc⟩, by omega⟩ · intro A _; simp · intro A _; simp have hM : (S.filter (fun A => ¬ n+1 ≤ (A ∩ X).card ∧ (A ∩ X).card = n)).card = (2*n).choose n ^ 2 := by have : (2*n).choose n ^ 2 = ((X.powersetCard n) ×ˢ (Xᶜ.powersetCard n)).card := by rw [Finset.card_product, Finset.card_powersetCard, Finset.card_powersetCard, hX, hXc, sq] rw [this] apply Finset.card_nbij' (fun A => (A ∩ X, A ∩ Xᶜ)) (fun p => p.1 ∪ p.2) · intro A hA simp only [S, Finset.coe_filter, Finset.mem_powersetCard, Set.mem_setOf_eq, Finset.coe_product, Set.mem_prod, Finset.mem_coe] at hA ⊢ have h := Finset.card_inter_add_card_sdiff A X rw [Finset.sdiff_eq_inter_compl] at h refine ⟨⟨Finset.inter_subset_right, hA.2.2⟩, ⟨Finset.inter_subset_right, by omega⟩⟩ · intro p hp simp only [S, Finset.coe_filter, Finset.mem_powersetCard, Set.mem_setOf_eq, Finset.coe_product, Set.mem_prod, Finset.mem_coe] at hp ⊢ obtain ⟨⟨h1, h2⟩, h3, h4⟩ := hp have hd : Disjoint p.1 p.2 := Finset.disjoint_of_subset_left h1 (Finset.disjoint_of_subset_right h3 disjoint_compl_right) have e : (p.1 ∪ p.2) ∩ X = p.1 := by ext x have := @h1 x have := @h3 x simp at * tauto rw [e, Finset.card_union_of_disjoint hd] refine ⟨⟨Finset.subset_univ _, by omega⟩, by omega, h2⟩ · intro A _ simp only ext x; simp; tauto · intro p hp simp only [S, Finset.coe_filter, Finset.mem_powersetCard, Set.mem_setOf_eq, Finset.coe_product, Set.mem_prod, Finset.mem_coe] at hp obtain ⟨⟨h1, h2⟩, h3, h4⟩ := hp ext x · have := @h1 x have := @h3 x simp at * tauto · have := @h1 x have := @h3 x simp at * tauto omega