`Compfiles/Usa1988P3.lean`

Explanation legend Lean4 Domain Explanation Language (L4DEL)

L4DEL explanations are a separate layer. They do not change the Lean source. Intuition is explanatory prose; numbered items are a reading path; sources link the wording back to evidence.

L4DEL: Lean4 Domain Explanation Language

Annotation provenance. This overlay contains 8 curated AI-written annotations and 3305 mechanical source-derived annotations. They have not been human-reviewed as explanations; treat them as unverified and not mathematical authority. Retained generation history: The 71 original curated annotations were produced in a Claude Sonnet 5.5 session at medium effort; Claude Opus 5.5 is recorded in that session as the advisor model, not the direct author. The bulk source-derived expansion was generated mechanically from pinned source comments by tooling developed in a GPT-5.6 Sol session at ultra reasoning; GPT-5.6 Sol did not originate the quoted source prose. On 2026-10-17 the mechanically generated source-comment annotations of the Formal Conjectures, Carleson, FLT, PFR, CompFiles, Mathematics in Lean and Theorem Proving in Lean overlays were regenerated by the same generator after three corrections made in a Claude Sonnet 5.5 session: titles no longer cut a sentence inside mathematics or end on a dangling word, workflow markers are removed from the quoted prose, and declaration names follow the scanner's namespace resolution. The boilerplate step line was dropped, and comments that were only a row of dashes no longer yield annotations. No new prose was written and no human review is claimed.

Credit: The upstream authors and contributors retain credit for the project and mathematics. lean4-explainer only renders their pinned source and adds the separately disclosed explanation layer.

Project sources: Pinned compfiles documentation, Pinned compfiles corpus index

2 declarations, 0 contain sorry, 0 declared as axioms

USA Mathematical Olympiad 1988, Problem 3

Let X be the set {1, 2, ... , 20} and let P be the set of all 9-element subsets of X. Show that for any map f : P → X we can find a 10-element subset Y of X, such that f(Y - {k}) ≠ k for any k in Y.

Imports (4)

Imported by 1 file

Compfiles.lean

lemma Usa1988P3.card_bad_pairs_le Documented declaration: card_bad_pairs_le line 39 source
Source documentation
For any finite set X, the number of pairs (Y, k) where Y is a 10-element subset of X, k ∈ Y, and f (Y.erase k) = k is at most the number of 9-element subsets of X: the map (Y, k) ↦ Y.erase k is injective on such pairs, because k = f (Y.erase k) is determined by the image, and then Y = insert k (Y.erase k) is determined as well.

standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: Finset, Nat, LE.le, Finset.card, Sigma, Finset.sigma, Finset.powersetCard, OfNat.ofNat, Finset.filter, Eq, Finset.erase
Proof uses: Finset.card_le_card_of_injOn, Sigma.fst, Sigma.snd, Membership.mem, Set, Sigma.mk, And, Eq.mp, Eq.trans, congr, congrArg, congrFun', Finset.filter_congr, Iff.of_eq, Eq.refl, id, Eq.mpr, propext, Finset.mem_powersetCard, And.intro and 11 more
21 instances, coercions and auxiliary constants left out.

Tactic trace: 21 steps
Open to load the checked before-and-after goal states.
```
lemma card_bad_pairs_le (X : Finset ℕ) (f : Finset ℕ → ℕ) :
    ((X.powersetCard 10).sigma
        (fun Y ↦ Y.filter (fun k ↦ f (Y.erase k) = k))).card
      ≤ (X.powersetCard 9).card := by
…
```
Mentions: f
problem Usa1988P3.usa1988_p3 line 64 source
standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: Finset, Nat, Exists, And, LE.le, Finset.Icc, OfNat.ofNat, Eq, Finset.card, Membership.mem, Ne, Finset.erase
Proof uses: Decidable.byContradiction, Not, Finset.powersetCard, Finset.filter, Eq.mp, Eq.trans, binderNameHint, forall_congr, Mathlib.Tactic.Push.not_and_eq, implies_congr, Eq.refl, Mathlib.Tactic.Push.not_forall_eq, congrArg, funext, And.left, propext, Finset.mem_powersetCard, And.right, Iff.mpr, LT.lt and 27 more
37 instances, coercions and auxiliary constants left out.

Tactic trace: 18 steps
Open to load the checked before-and-after goal states.