每日科技文摘Daily Tech Digest

指标一旦变成目标:过拟合的引擎、失准的检测器与人的判断Once the Metric Becomes the Goal: Overfitted Engines, Unreliable Detectors, and Human Judgment

发布于 2026-11-12Published 2026-11-12

今日深读Today's Deep Read

把 TPC-H 考到 22 倍:当 AI 学会作弊,基准测试还剩下什么Beating TPC-H by 22x: When AI Learns to Cheat, What Is a Benchmark Worth?

数据库圈有个老毛病:一个基准测试一旦变成排行榜,就会慢慢失去意义。TPC-H 本来是拿来比较查询引擎的,可公开的“非官方 TPC-H 成绩”大多不守规则;如今再加上急于求成的 AI agent,事情到了一个新层次。Thomas Neumann 最近拆解了 GenDB-V 宣称的 22–61 倍加速,结论不是引擎变快了,而是基准被钻了空子。Databases have an old problem: the moment a benchmark becomes a leaderboard, it starts to lose its meaning. TPC-H was built to compare query engines, yet most published “unofficial TPC-H results” simply ignore the rules. Add impatient AI agents and you get a new level of trouble. Thomas Neumann takes apart a system called GenDB-V, whose paper is titled “Stop Handcrafting Your Engine!” and which claims 22x to 61x speedups over Umbra and DuckDB — all inside a formally verified system. On the face of it, traditional engines are finished.

他先算了一个物理下限:SF10 规模下,22 条 TPC-H 查询要读约 15GB 压缩数据;在 9950X3D 上 Umbra 跑完全部查询约 540 毫秒;这台机器的内存带宽约 54GB/s,读一遍 15GB 至少 280 毫秒。也就是说,Umbra 时间的大半已经花在“把数据从内存搬进 CPU”这个省不掉的动作上;想再快 22 倍,就只能搬得比内存带宽允许的还少——除非根本不搬。Neumann does not argue about experimental setup. He computes a physical lower bound. At SF10, the 22 TPC-H queries read roughly 15GB of compressed base data. On a 9950X3D, Umbra runs all of them in about 540ms total. That machine's memory bandwidth is 54GB/s, so just moving the data from memory to the CPU costs about 280ms. More than half of Umbra's runtime is already the irreducible cost of touching the data. Going 22x faster would mean going below what memory bandwidth allows — unless you never read the data at all.

答案正是“没有读”。GenDB-V 的加速主要来自预计算:agent 为每条查询手工打造辅助结构,加载时算好,运行时绕开大部分工作。物理设计也被查询反向定制,比如专门维护一份按 s_acctbal 降序排列的副本,让排序直接消失。数字会自己说话:换成 10 倍数据的 SF100,Q2 仍然只要 0.7 毫秒,Q17 约 15 毫秒——数据翻了十倍,耗时几乎不动,说明运行时根本没有按比例读数据。And that is exactly what happens. GenDB-V's dramatic gains come from precomputation: the agents hand-built auxiliary data structures for each query, computed at load time, so most of the work disappears at runtime. The physical design is reverse-engineered from the queries too — for example, an extra structure keeps supplier rows in descending s_acctbal order, making Q2 trivial. The numbers give it away: at SF100, Q2 takes 0.7ms, Q17 about 15ms, Q4 about 17ms. Ten times more data, near-constant time. This is the old TPC-D symptom, only without stored aggregates.

更隐蔽的是 plain-array 模式:不做预计算,只快约 3 倍,看上去很合理。可细看代码,agent 把数据生成器的知识硬编码了进去——它“知道”第 k 个 customer 一定在第 k-1 行,第 i 个 order 一定在 32·(i/8)+i%8 行。于是 Q18 里最重的连表查询退化成一次查表,几乎免费——这不是优化查询,是背下了答案。换任何真实数据,这些假设立刻失效。There is also a “plain-array” mode that looks fairer: no elaborate preparation, and “only” about 3x faster, which sounds plausible. Look closer and the agents did something crazier — they hard-coded knowledge of the data generator. The code “knows” that customer k sits at row k-1. It “knows” that dbgen numbers the i-th order as 32·(i/8) + i%8, so key k lives at row 8·(k/32) + k%32 − 1. Q18's join becomes a table lookup, nearly free. This is not optimizing a query; it is memorizing the answer key.

那形式化验证为什么没拦住?因为它保证的只是“对任意数据库,结果正确”。代码确实会检查自己的猜测是否成立,不成立就退回慢速的通用实现;可只要用官方生成器,这个检查就永远成立,慢速路径在所有汇报的实验里一次也没被走到。换句话说,验证保证的是逻辑自洽,不是这套取巧办法在真实数据上的适用性。作者本人也回应说,代码里确实有验证步骤,所以结果仍然“正确”;Neumann 的反驳是:若要把数据集和生成器的知识一起哈希进去才能防住,那等于要求基准替你保守秘密,这本身就很荒谬。Why didn't formal verification catch it? Because verification promises something else: the result is correct for every possible database. The code does check whether its assumptions about the generator hold, and falls back to a very slow generic nested-loop path when they don't. But with the official TPC-H generator the check never fails, so the slow path effectively does not exist in the reported experiments. The system is “correct,” and that correctness has nothing to do with whether the speedup means anything on real data. This is the heart of the exchange in the comments: the authors say this is a specialized engine for one customer and verification is the point; Neumann asks whether he could hash the dataset and scale factor, compute every answer from generator knowledge, bolt on a DuckDB fallback that never runs, and call that verified and absurdly fast. Where exactly is the line?

结论很朴素:让 AI agent 针对某个基准去优化,基准就废了。它会找到最疯狂、却只在生成器假设下成立的技巧;删掉一行数据、插入一条记录,整个方法就可能跌下悬崖,退回那条慢速的通用实现。真正该设计的是评测本身:基准必须对引擎未知,必须包含分布变化与更新,否则考的就不是理解,而是默写。读这篇不是为了拆穿一个系统,而是看古德哈特定律在 AI 时代落了地:指标一旦变成目标,连形式化证明都能被招安,替作弊背书。His conclusion is simple: let AI agents optimize against a benchmark and the benchmark is dead. They will find insane tricks, and none of those tricks survive in a real system — delete one row, insert one record in the middle, and the whole approach falls off a cliff into the slow path. The real issue is evaluation design: the benchmark must be unknown to the engine developer, and the data must change over time, or the exam becomes recitation. Read this not because it debunks one system, but because it makes Goodhart's law concrete for the AI era: once the metric becomes the goal, even a formal proof can be enlisted to bless the cheating.

AI 思考AI Thoughts

数学之美The Beauty of Math

每日 Lean 谜题 · 周四Daily Lean Puzzle · Thursday ★★★★☆☆☆

被夹在两个集合中间:USAMO 2019 第 4 题Sandwiched Between Two Sets: USAMO 2019, Problem 4

令 $n$ 为非负整数。考虑 $(n+1)^2$ 个集合 $S_{i,j}$,其中 $0\le i,j\le n$,每个都是 $\{1,2,\dots,2n\}$ 的子集。要求同时满足两条:第一,$|S_{i,j}|=i+j$;第二,只要 $i\le k$ 且 $j\le l$,就有 $S_{i,j}\subseteq S_{k,l}$。问一共有多少种选法?Let $n$ be a nonnegative integer. Consider $(n+1)^2$ sets $S_{i,j}$ with $0\le i,j\le n$, each a subset of $\{1,2,\dots,2n\}$. Two conditions must hold: first, $|S_{i,j}|=i+j$; second, whenever $i\le k$ and $j\le l$, we have $S_{i,j}\subseteq S_{k,l}$. How many choices are there?

答案是 $(2n)!\cdot 2^{n^2}$。当 $n=0$ 时只有一个空集,公式给出 $0!\cdot 2^0=1$,对得上。The answer is $(2n)!\cdot 2^{n^2}$. For $n=0$ there is only the empty set, and the formula gives $0!\cdot 2^0=1$, as it should.

Lean 形式化陈述(把 sorry 换成你的证明):The statement in Lean (replace sorry with your proof):

/-
Copyright (c) 2026 David Renshaw. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: David Renshaw, Kimi K3
-/

import Mathlib.Algebra.BigOperators.Intervals
import Mathlib.AlgebraicTopology.SimplexCategory.Basic
import Mathlib.Data.Nat.Factorial.BigOperators
import Mathlib.Data.Set.Card

open scoped Nat

/-!
# USA Mathematical Olympiad 2019, Problem 4

Let n be a nonnegative integer. Determine the number of ways to choose
sets Sᵢⱼ ⊆ {1, 2, ..., 2n}, for all 0 ≤ i ≤ n and 0 ≤ j ≤ n (not
necessarily distinct), such that

  • |Sᵢⱼ| = i + j, and
  • Sᵢⱼ ⊆ Sₖₗ if 0 ≤ i ≤ k ≤ n and 0 ≤ j ≤ l ≤ n.
-/

namespace Usa2019P4

abbrev answer (n : ℕ) : ℕ := sorry

theorem usa2019_p4 (n : ℕ) :
    Nat.card {S : Fin (n + 1) → Fin (n + 1) → Finset (Fin (2 * n)) //
      (∀ i j, (S i j).card = i.val + j.val) ∧
      (∀ i k j l, i ≤ k → j ≤ l → S i j ⊆ S k l)} = answer n := by
  sorry
end Usa2019P4

在浏览器中挑战 ▶Try it in your browser ▶ 下载题目 .leanDownload puzzle .lean

提示Hint

先把最外圈那条从 $S_{0,0}$ 走到 $S_{n,n}$ 的折线填满,再看内部每一格:它的左边和上边都已确定,而上下两个集合的大小只差 2。First fill the border path from $S_{0,0}$ to $S_{n,n}$. Then look at an interior cell: its left and upper neighbours are already fixed, and the two bounding sets differ in size by exactly 2.

答案与讲解Solution & walkthrough
  1. 第一步,把边界钉住。沿折线 $S_{0,0}\subset S_{0,1}\subset\cdots\subset S_{0,n}\subset S_{1,n}\subset\cdots\subset S_{n,n}$ 看:每一步集合大小恰好加 1,所以就是依次从 $2n$ 个元素里挑一个放进去。共有 $(2n)(2n-1)\cdots 1=(2n)!$ 种选法。选定后,可以不妨把这条链想成 $\{1,\dots,i\}$ 和 $\{1,\dots,n+i\}$ 的标准链,问题只剩填内部。Step one: pin down the border. Walk along $S_{0,0}\subset S_{0,1}\subset\cdots\subset S_{0,n}\subset S_{1,n}\subset\cdots\subset S_{n,n}$. Each step increases the size by exactly 1, so you are simply picking one new element out of $2n$ at a time. That gives $(2n)(2n-1)\cdots 1=(2n)!$ choices. Once fixed, you may relabel so the chain is the standard one, and only the interior is left.
  2. 第二步,定一个填充顺序:从左到右一列一列填,每列从上往下降。轮到 $S_{i,j}$($i\ge 1,\ j<n$)时,它左边的 $S_{i-1,j}$ 和上边的 $S_{i,j+1}$ 都已经填好了。Step two: choose a filling order — column by column from left to right, and within each column from the top down. When you reach $S_{i,j}$ with $i\ge 1$ and $j<n$, its left neighbour $S_{i-1,j}$ and its upper neighbour $S_{i,j+1}$ are already known.
  3. 第三步,看夹在中间的自由度。由条件有 $S_{i-1,j}\subset S_{i,j}\subset S_{i,j+1}$,三者的元素个数分别是 $i+j-1$、$i+j$、$i+j+1$。于是差集 $S_{i,j+1}\setminus S_{i-1,j}$ 恰好有 2 个元素,而 $S_{i,j}$ 只能是“左下界加上这两个元素中的一个”。两种选法都满足包含关系,所以每格恰好 2 种。Step three: look at the freedom in the middle. The conditions force $S_{i-1,j}\subset S_{i,j}\subset S_{i,j+1}$, with sizes $i+j-1$, $i+j$, and $i+j+1$. So the difference $S_{i,j+1}\setminus S_{i-1,j}$ has exactly 2 elements, and $S_{i,j}$ must be the lower set plus exactly one of them. Both choices satisfy the inclusions, so every cell has exactly 2 options.
  4. 第四步,数总数。内部有 $n\times n$ 个格子,每格独立二选一,贡献 $2^{n^2}$;再乘边界链的 $(2n)!$,得到 $(2n)!\cdot 2^{n^2}$。Step four: count. There are $n\times n$ interior cells, each an independent binary choice, giving $2^{n^2}$; multiply by the $(2n)!$ border chains to get $(2n)!\cdot 2^{n^2}$.
  5. Lean 证明与上面的步骤一一对应。`ncard_fillings_insert` 是通用引理:在一个已知下界 $A$ 和上界 $C$ 之间选大小为 $t$ 的集合,方案数是 $\binom{|C|-|A|}{t-|A|}$;它把“加一个格子”变成乘一个组合数。`stageA` 填第一列得到 $\prod_{j<n}(2n-j)$,`stageB` 再填最上面一行得到额外的 $\prod_{i<n}(n-i)=n!$,两者相乘正是 $(2n)!$。`stageC_inner` 对每列从上往下的 $r$ 个格子做归纳,证明每加一格乘 2;`stageC` 把 $n$ 列合成 $2^{n\cdot k}$;最后 `main_count` 取 $k=n$,用 `prod_range_two_mul_sub_mul` 把两个乘积整理成 $(2n)!$,得到 $2^{n^2}(2n)!$。The Lean proof mirrors these steps. `ncard_fillings_insert` is the general lemma: choosing a set of size $t$ between a known lower bound $A$ and upper bound $C$ has $\binom{|C|-|A|}{t-|A|}$ solutions, so adding one cell multiplies by a binomial coefficient. `stageA` fills the first column and produces $\prod_{j<n}(2n-j)$; `stageB` fills the top row and adds $\prod_{i<n}(n-i)=n!$; together they give $(2n)!$. `stageC_inner` inducts over the $r$ cells of a column filled top-down, showing each adds a factor of 2; `stageC` combines $n$ columns into $2^{n\cdot k}$; and `main_count` takes $k=n$ and uses `prod_range_two_mul_sub_mul` to fold the products into $(2n)!$, yielding $2^{n^2}(2n)!$.
/-
Copyright (c) 2026 David Renshaw. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: David Renshaw, Kimi K3
-/

import Mathlib.Algebra.BigOperators.Intervals
import Mathlib.AlgebraicTopology.SimplexCategory.Basic
import Mathlib.Data.Nat.Factorial.BigOperators
import Mathlib.Data.Set.Card

open scoped Nat

/-!
# USA Mathematical Olympiad 2019, Problem 4

Let n be a nonnegative integer. Determine the number of ways to choose
sets Sᵢⱼ ⊆ {1, 2, ..., 2n}, for all 0 ≤ i ≤ n and 0 ≤ j ≤ n (not
necessarily distinct), such that

  • |Sᵢⱼ| = i + j, and
  • Sᵢⱼ ⊆ Sₖₗ if 0 ≤ i ≤ k ≤ n and 0 ≤ j ≤ l ≤ n.
-/

namespace Usa2019P4

/-- The grid cells indexing the sets `Sᵢⱼ`. -/
abbrev Cell (n : ℕ) := Fin (n + 1) × Fin (n + 1)

/-- The cardinality required at cell `(i, j)`. -/
def target {n : ℕ} (c : Cell n) : ℕ := c.1.val + c.2.val

/-- Partial configurations on a set `D` of cells: the cardinality and
monotonicity conditions hold on `D`, and the value is `∅` off `D`
(the latter condition keeps the ambient function type finite). -/
def Fillings (n : ℕ) (D : Set (Cell n)) : Set (Cell n → Finset (Fin (2 * n))) :=
  {S | (∀ c ∈ D, (S c).card = target c) ∧
       (∀ a ∈ D, ∀ b ∈ D, a ≤ b → S a ⊆ S b) ∧
       (∀ c ∉ D, S c = ∅)}

/-- The cells of column `0` in rows `≤ j`. -/
def colZero (n j : ℕ) : Set (Cell n) := {c | c.1.val = 0 ∧ c.2.val ≤ j}

/-- The cells of row `n` in columns `1..i`. -/
def topRow (n i : ℕ) : Set (Cell n) := {c | 1 ≤ c.1.val ∧ c.1.val ≤ i ∧ c.2.val = n}

/-- The interior cells (rows `< n`) in columns `1..i`. -/
def intCols (n i : ℕ) : Set (Cell n) := {c | 1 ≤ c.1.val ∧ c.1.val ≤ i ∧ c.2.val < n}

/-- The interior cells of column `k` in rows `n - r .. n - 1`. -/
def colPart (n k r : ℕ) : Set (Cell n) := {c | c.1.val = k ∧ n - r ≤ c.2.val ∧ c.2.val < n}

/-- Cell equality in terms of coordinate values. -/
lemma cell_ext {n : ℕ} {c : Cell n} {a b : ℕ} {ha : a < n + 1} {hb : b < n + 1} :
    c = (⟨a, ha⟩, ⟨b, hb⟩) ↔ c.1.val = a ∧ c.2.val = b :=
  ⟨fun h ↦ by rw [h]; exact ⟨rfl, rfl⟩,
   fun ⟨h1, h2⟩ ↦ Prod.ext_iff.mpr ⟨Fin.ext_iff.mpr h1, Fin.ext_iff.mpr h2⟩⟩

/-- The only filling of the empty set of cells. -/
lemma fillings_empty (n : ℕ) : Fillings n (∅ : Set (Cell n)) = {fun _ ↦ ∅} := by
  ext S
  simp [Fillings, funext_iff]

/-- Restricting a filling of `insert s D` to a filling of `D`
by resetting the value at `s` to `∅`. -/
lemma restrict_mem {n : ℕ} {D : Set (Cell n)} {s : Cell n} (hs : s ∉ D)
    {S : Cell n → Finset (Fin (2 * n))} (hS : S ∈ Fillings n (insert s D)) :
    Function.update S s ∅ ∈ Fillings n D := by
  obtain ⟨hcard, hmono, hjunk⟩ := hS
  refine ⟨?_, ?_, ?_⟩
  · intro c hc
    rw [Function.update_of_ne (ne_of_mem_of_not_mem hc hs)]
    exact hcard c (Set.mem_insert_of_mem s hc)
  · intro a ha b hb hab
    rw [Function.update_of_ne (ne_of_mem_of_not_mem ha hs),
      Function.update_of_ne (ne_of_mem_of_not_mem hb hs)]
    exact hmono a (Set.mem_insert_of_mem s ha) b (Set.mem_insert_of_mem s hb) hab
  · intro c hc
    by_cases hcs : c = s
    · rw [hcs]; exact Function.update_self s ∅ S
    · rw [Function.update_of_ne hcs]
      exact hjunk c fun h ↦ hc (Set.mem_of_mem_insert_of_ne h hcs)

/-- Extending a filling of `D` by an admissible value `X` at `s`. -/
lemma extend_mem {n : ℕ} {D : Set (Cell n)} {s : Cell n} (hs : s ∉ D)
    {A C : (Cell n → Finset (Fin (2 * n))) → Finset (Fin (2 * n))}
    (hlo : ∀ f ∈ Fillings n D, ∀ d ∈ D, d ≤ s → f d ⊆ A f)
    (hhi : ∀ f ∈ Fillings n D, ∀ d ∈ D, s ≤ d → C f ⊆ f d)
    {f : Cell n → Finset (Fin (2 * n))} (hf : f ∈ Fillings n D)
    {X : Finset (Fin (2 * n))} (hXA : A f ⊆ X) (hXC : X ⊆ C f)
    (hXt : X.card = target s) :
    Function.update f s X ∈ Fillings n (insert s D) := by
  refine ⟨?_, ?_, ?_⟩
  · intro c hc
    rcases Set.mem_insert_iff.mp hc with rfl | hcD
    · rw [Function.update_self]; exact hXt
    · rw [Function.update_of_ne (ne_of_mem_of_not_mem hcD hs)]; exact hf.1 c hcD
  · intro a ha b hb hab
    rcases Set.mem_insert_iff.mp ha with rfl | haD <;>
    rcases Set.mem_insert_iff.mp hb with rfl | hbD
    · exact Finset.Subset.refl _
    · rw [Function.update_self, Function.update_of_ne (ne_of_mem_of_not_mem hbD hs)]
      exact Finset.Subset.trans hXC (hhi f hf b hbD hab)
    · rw [Function.update_self, Function.update_of_ne (ne_of_mem_of_not_mem haD hs)]
      exact Finset.Subset.trans (hlo f hf a haD hab) hXA
    · rw [Function.update_of_ne (ne_of_mem_of_not_mem haD hs),
        Function.update_of_ne (ne_of_mem_of_not_mem hbD hs)]
      exact hf.2.1 a haD b hbD hab
  · intro c hc
    have hcs : c ≠ s := by
      intro h
      rw [h] at hc
      exact hc (Set.mem_insert s D)
    rw [Function.update_of_ne hcs]
    exact hf.2.2 c fun hD ↦ hc (Set.mem_insert_of_mem s hD)

/-- The sets between `A` and `C` with cardinality `t` are counted
by a binomial coefficient. -/
lemma card_between {α : Type*} [DecidableEq α] {A C : Finset α} (hAC : A ⊆ C)
    {t : ℕ} (hAt : A.card ≤ t) :
    Nat.card {X : Finset α // A ⊆ X ∧ X ⊆ C ∧ X.card = t} =
      (C.card - A.card).choose (t - A.card) := by
  have e : {X : Finset α // A ⊆ X ∧ X ⊆ C ∧ X.card = t} ≃
      ↥(Finset.powersetCard (t - A.card) (C \ A)) :=
    ⟨fun X ↦ ⟨X.1 \ A, Finset.mem_powersetCard.mpr
        ⟨Finset.sdiff_subset_sdiff X.2.2.1 (Finset.Subset.refl A), by
          rw [Finset.card_sdiff_of_subset X.2.1, X.2.2.2]⟩⟩,
     fun Y ↦ ⟨Y.1 ∪ A, by
       have hY := Finset.mem_powersetCard.mp Y.2
       refine ⟨Finset.subset_union_right, ?_, ?_⟩
       · exact Finset.union_subset (Finset.Subset.trans hY.1 Finset.sdiff_subset) hAC
       · rw [Finset.card_union_of_disjoint
           (Finset.disjoint_of_subset_left hY.1 Finset.sdiff_disjoint), hY.2,
           Nat.sub_add_cancel hAt]⟩,
     fun X ↦ Subtype.ext (Finset.sdiff_union_of_subset X.2.1),
     fun Y ↦ Subtype.ext (Finset.union_sdiff_cancel_right
       (Finset.disjoint_of_subset_left
         (Finset.mem_powersetCard.mp Y.2).1 Finset.sdiff_disjoint))⟩
  rw [Nat.card_congr e, Nat.card_eq_fintype_card, Fintype.card_coe,
    Finset.card_powersetCard, Finset.card_sdiff_of_subset hAC]

/-- The possible values of a filling at a fresh cell `s`,
given the values `A f` and `C f` forced by the neighbors of `s`. -/
abbrev Fiber {n : ℕ} {D : Set (Cell n)}
    (A C : (Cell n → Finset (Fin (2 * n))) → Finset (Fin (2 * n))) (s : Cell n)
    (f : ↥(Fillings n D)) : Type :=
  {X : Finset (Fin (2 * n)) // A f.1 ⊆ X ∧ X ⊆ C f.1 ∧ X.card = target s}

/-- Adding one cell to the domain multiplies the number of fillings
by a binomial coefficient. -/
lemma ncard_fillings_insert {n : ℕ} {D : Set (Cell n)} {s : Cell n} (hs : s ∉ D)
    {A C : (Cell n → Finset (Fin (2 * n))) → Finset (Fin (2 * n))}
    (hlo : ∀ f ∈ Fillings n D, ∀ d ∈ D, d ≤ s → f d ⊆ A f)
    (hhi : ∀ f ∈ Fillings n D, ∀ d ∈ D, s ≤ d → C f ⊆ f d)
    (hAs : ∀ g ∈ Fillings n (insert s D), A (Function.update g s ∅) ⊆ g s)
    (hsC : ∀ g ∈ Fillings n (insert s D), g s ⊆ C (Function.update g s ∅))
    (hAC : ∀ f ∈ Fillings n D, A f ⊆ C f)
    {a₀ c₀ : ℕ}
    (hAcard : ∀ f ∈ Fillings n D, (A f).card = a₀)
    (hCcard : ∀ f ∈ Fillings n D, (C f).card = c₀)
    (hAt : ∀ f ∈ Fillings n D, (A f).card ≤ target s) :
    (Fillings n (insert s D)).ncard =
      (c₀ - a₀).choose (target s - a₀) * (Fillings n D).ncard := by
  have hfib : ∀ f : ↥(Fillings n D),
      Nat.card (Fiber A C s f) = (c₀ - a₀).choose (target s - a₀) := by
    intro f
    have h1 := card_between (hAC f.1 f.2) (hAt f.1 f.2)
    rw [hAcard f.1 f.2, hCcard f.1 f.2] at h1
    exact h1
  let toSigma : ↥(Fillings n (insert s D)) → (Σ f : ↥(Fillings n D), Fiber A C s f) :=
    fun g ↦ ⟨⟨Function.update g.1 s ∅, restrict_mem hs g.2⟩,
      g.1 s, hAs g.1 g.2, hsC g.1 g.2, g.2.1 s (Set.mem_insert s D)⟩
  let fromSigma : (Σ f : ↥(Fillings n D), Fiber A C s f) → ↥(Fillings n (insert s D)) :=
    fun p ↦ ⟨Function.update p.1.1 s p.2.1,
      extend_mem hs hlo hhi p.1.2 p.2.2.1 p.2.2.2.1 p.2.2.2.2⟩
  have inj : Function.Injective toSigma := by
    intro g₁ g₂ heq
    have h1 : Function.update g₁.1 s ∅ = Function.update g₂.1 s ∅ :=
      congrArg (fun p : (Σ f : ↥(Fillings n D), Fiber A C s f) ↦ p.1.1) heq
    have h2 : g₁.1 s = g₂.1 s :=
      congrArg (fun p : (Σ f : ↥(Fillings n D), Fiber A C s f) ↦ p.2.1) heq
    apply Subtype.ext
    funext c
    by_cases hcs : c = s
    · rw [hcs]; exact h2
    · have e1 := congrFun h1 c
      rw [Function.update_of_ne hcs, Function.update_of_ne hcs] at e1
      exact e1
  have hgen : ∀ (g : Cell n → Finset (Fin (2 * n))) (Y : Finset (Fin (2 * n))),
      Function.update (Function.update g s Y) s ∅ = Function.update g s ∅ := by
    intro g Y
    funext c
    by_cases hcs : c = s
    · rw [hcs, Function.update_self, Function.update_self]
    · rw [Function.update_of_ne hcs, Function.update_of_ne hcs, Function.update_of_ne hcs]
  have inj2 : Function.Injective fromSigma := by
    intro p₁ p₂ heq
    obtain ⟨⟨f₁, hf₁⟩, X₁, hXA₁, hXC₁, hXt₁⟩ := p₁
    obtain ⟨⟨f₂, hf₂⟩, X₂, hXA₂, hXC₂, hXt₂⟩ := p₂
    have eX : X₁ = X₂ := by
      have e := congrArg (fun g : ↥(Fillings n (insert s D)) ↦ g.1 s) heq
      change Function.update f₁ s X₁ s = Function.update f₂ s X₂ s at e
      rw [Function.update_self, Function.update_self] at e
      exact e
    have ef : f₁ = f₂ := by
      have e := congrArg (fun g : ↥(Fillings n (insert s D)) ↦ Function.update g.1 s ∅) heq
      change Function.update (Function.update f₁ s X₁) s ∅ =
        Function.update (Function.update f₂ s X₂) s ∅ at e
      rw [hgen, hgen] at e
      funext c
      by_cases hcs : c = s
      · rw [hcs, hf₁.2.2 s hs, hf₂.2.2 s hs]
      · have ec := congrFun e c
        rw [Function.update_of_ne hcs, Function.update_of_ne hcs] at ec
        exact ec
    subst ef
    subst eX
    rfl
  classical
  have hcard : Nat.card ↥(Fillings n (insert s D)) =
      Nat.card (Σ f : ↥(Fillings n D), Fiber A C s f) := by
    apply le_antisymm
    · exact Nat.card_le_card_of_injective toSigma inj
    · exact Nat.card_le_card_of_injective fromSigma inj2
  rw [← Nat.card_coe_set_eq, ← Nat.card_coe_set_eq]
  calc Nat.card ↥(Fillings n (insert s D))
      = Nat.card (Σ f : ↥(Fillings n D), Fiber A C s f) := hcard
    _ = ∑ f : ↥(Fillings n D), Nat.card (Fiber A C s f) := by
        rw [Nat.card_eq_fintype_card, Fintype.card_sigma]
        exact Finset.sum_congr rfl fun f _ ↦ (Nat.card_eq_fintype_card).symm
    _ = ∑ f : ↥(Fillings n D), (c₀ - a₀).choose (target s - a₀) :=
        Finset.sum_congr rfl fun f _ ↦ hfib f
    _ = (Fillings n D).ncard * (c₀ - a₀).choose (target s - a₀) := by
        rw [Finset.sum_const, Finset.card_univ, nsmul_eq_mul, Nat.cast_id,
          ← Nat.card_coe_set_eq, Nat.card_eq_fintype_card]
    _ = (c₀ - a₀).choose (target s - a₀) * (Fillings n D).ncard := mul_comm _ _

/-- Counting the fillings of the leftmost column: after `j` steps there are
`∏ i ∈ range j, (2 * n - i)` fillings. -/
lemma stageA (n : ℕ) : ∀ j, j ≤ n →
    (Fillings n (colZero n j)).ncard = ∏ i ∈ Finset.range j, (2 * n - i) := by
  intro j
  induction j with
  | zero =>
    intro _
    have h0n : (0 : ℕ) < n + 1 := Nat.zero_lt_succ n
    have h0 : colZero n 0 = insert (⟨0, h0n⟩, ⟨0, h0n⟩) (∅ : Set (Cell n)) := by
      ext c
      simp only [colZero, Set.mem_insert_iff, Set.mem_empty_iff_false, Set.mem_ofPred_eq,
        cell_ext, or_false]
      constructor
      · rintro ⟨h1, h2⟩
        exact ⟨h1, Nat.eq_zero_of_le_zero h2⟩
      · rintro ⟨h1, h2⟩
        exact ⟨h1, Nat.le_of_eq h2⟩
    rw [h0, ncard_fillings_insert (A := fun _ ↦ ∅) (C := fun _ ↦ Finset.univ)
      (Set.notMem_empty _)
      (by intro f hf d hd hds; exact (Set.notMem_empty d hd).elim)
      (by intro f hf d hd hds; exact (Set.notMem_empty d hd).elim)
      (by intro g hg; exact Finset.empty_subset _)
      (by intro g hg; exact Finset.subset_univ _)
      (by intro f hf; exact Finset.empty_subset _)
      (by intro f hf; rw [Finset.card_empty])
      (by intro f hf; rw [Finset.card_univ, Fintype.card_fin])
      (by intro f hf; rw [Finset.card_empty]; exact Nat.zero_le _),
      fillings_empty, Set.ncard_singleton, Finset.prod_range_zero]
    simp [target]
  | succ j ih =>
    intro hj
    have hj' : j ≤ n := Nat.le_of_succ_le hj
    have hjn : j < n + 1 := by lia
    have hjn1 : j + 1 < n + 1 := by lia
    have h0n : (0 : ℕ) < n + 1 := Nat.zero_lt_succ n
    have hid : colZero n (j + 1) =
        insert (⟨0, h0n⟩, ⟨j + 1, hjn1⟩) (colZero n j) := by
      ext c
      simp only [colZero, Set.mem_insert_iff, Set.mem_ofPred_eq, cell_ext]
      constructor <;> intro h <;> lia
    have hs : (⟨0, h0n⟩, ⟨j + 1, hjn1⟩) ∉ colZero n j := by
      simp only [colZero, Set.mem_ofPred_eq]
      lia
    have ha₀ : (⟨0, h0n⟩, ⟨j, hjn⟩) ∈ colZero n j := ⟨rfl, le_refl _⟩
    have hcount : (2 * n - target (⟨0, h0n⟩, ⟨j, hjn⟩)).choose
        (target (⟨0, h0n⟩, ⟨j + 1, hjn1⟩) - target (⟨0, h0n⟩, ⟨j, hjn⟩)) = 2 * n - j := by
      have h1 : target (⟨0, h0n⟩, ⟨j, hjn⟩) = j := Nat.zero_add j
      have h2 : target (⟨0, h0n⟩, ⟨j + 1, hjn1⟩) - target (⟨0, h0n⟩, ⟨j, hjn⟩) = 1 := by
        show 0 + (j + 1) - (0 + j) = 1
        lia
      rw [h1] at h2
      rw [h1, h2, Nat.choose_one_right]
    rw [hid, ncard_fillings_insert hs
      (A := fun f ↦ f (⟨0, h0n⟩, ⟨j, hjn⟩)) (C := fun _ ↦ Finset.univ)
      (by
        intro f hf d hd _
        apply hf.2.1 d hd _ ha₀
        simp only [colZero, Set.mem_ofPred_eq] at hd
        simp only [Prod.le_def, Fin.le_def]
        exact ⟨by lia, by lia⟩)
      (by
        intro f hf d hd hds
        simp only [colZero, Set.mem_ofPred_eq] at hd
        simp only [Prod.le_def, Fin.le_def] at hds
        lia)
      (by
        intro g hg
        rw [Function.update_of_ne (ne_of_mem_of_not_mem ha₀ hs)]
        exact hg.2.1 _ (Set.mem_insert_of_mem _ ha₀) _ (Set.mem_insert _ _)
          (by simp only [Prod.le_def, Fin.le_def]; lia))
      (by intro g hg; exact Finset.subset_univ _)
      (by intro f hf; exact Finset.subset_univ _)
      (by intro f hf; exact hf.1 _ ha₀)
      (by intro f hf; rw [Finset.card_univ, Fintype.card_fin])
      (by
        intro f hf
        rw [hf.1 _ ha₀]
        show 0 + j ≤ 0 + (j + 1)
        lia),
      hcount, ih hj', Finset.prod_range_succ]
    ring

/-- Counting the fillings of the left column together with the top row. -/
lemma stageB (n : ℕ) : ∀ i, i ≤ n →
    (Fillings n (colZero n n ∪ topRow n i)).ncard =
      (∏ j ∈ Finset.range i, (n - j)) * ∏ j ∈ Finset.range n, (2 * n - j) := by
  intro i
  induction i with
  | zero =>
    intro _
    have h0 : topRow n 0 = (∅ : Set (Cell n)) := by
      ext c
      simp only [topRow, Set.mem_ofPred_eq, Set.mem_empty_iff_false, iff_false]
      lia
    rw [h0, Set.union_empty, Finset.prod_range_zero, one_mul, stageA n n (le_refl n)]
  | succ i ih =>
    intro hi
    have hi' : i ≤ n := Nat.le_of_succ_le hi
    have hin : i < n + 1 := by lia
    have hin1 : i + 1 < n + 1 := by lia
    have hnn : n < n + 1 := Nat.lt_succ_self n
    have hid : colZero n n ∪ topRow n (i + 1) =
        insert (⟨i + 1, hin1⟩, ⟨n, hnn⟩) (colZero n n ∪ topRow n i) := by
      ext c
      simp only [colZero, topRow, Set.mem_insert_iff, Set.mem_union, Set.mem_ofPred_eq,
        cell_ext]
      constructor <;> intro h <;> lia
    have hs : (⟨i + 1, hin1⟩, ⟨n, hnn⟩) ∉ colZero n n ∪ topRow n i := by
      simp only [colZero, topRow, Set.mem_union, Set.mem_ofPred_eq]
      lia
    have ha₀ : (⟨i, hin⟩, ⟨n, hnn⟩) ∈ colZero n n ∪ topRow n i := by
      by_cases hi0 : i = 0
      · subst hi0; exact Or.inl ⟨rfl, le_refl _⟩
      · exact Or.inr ⟨by show (1 : ℕ) ≤ i; lia, le_refl i, rfl⟩
    have hcount : (2 * n - target (⟨i, hin⟩, ⟨n, hnn⟩)).choose
        (target (⟨i + 1, hin1⟩, ⟨n, hnn⟩) - target (⟨i, hin⟩, ⟨n, hnn⟩)) = n - i := by
      have h1 : 2 * n - target (⟨i, hin⟩, ⟨n, hnn⟩) = n - i := by
        show 2 * n - (i + n) = n - i
        lia
      have h2 : target (⟨i + 1, hin1⟩, ⟨n, hnn⟩) - target (⟨i, hin⟩, ⟨n, hnn⟩) = 1 := by
        show i + 1 + n - (i + n) = 1
        lia
      rw [h1, h2, Nat.choose_one_right]
    rw [hid, ncard_fillings_insert hs
      (A := fun f ↦ f (⟨i, hin⟩, ⟨n, hnn⟩)) (C := fun _ ↦ Finset.univ)
      (by
        intro f hf d hd _
        apply hf.2.1 d hd _ ha₀
        simp only [colZero, topRow, Set.mem_union, Set.mem_ofPred_eq] at hd
        simp only [Prod.le_def, Fin.le_def]
        show d.1.val ≤ i ∧ d.2.val ≤ n
        lia)
      (by
        intro f hf d hd hds
        simp only [colZero, topRow, Set.mem_union, Set.mem_ofPred_eq] at hd
        simp only [Prod.le_def, Fin.le_def] at hds
        lia)
      (by
        intro g hg
        rw [Function.update_of_ne (ne_of_mem_of_not_mem ha₀ hs)]
        exact hg.2.1 _ (Set.mem_insert_of_mem _ ha₀) _ (Set.mem_insert _ _)
          (by simp only [Prod.le_def, Fin.le_def]; lia))
      (by intro g hg; exact Finset.subset_univ _)
      (by intro f hf; exact Finset.subset_univ _)
      (by intro f hf; exact hf.1 _ ha₀)
      (by intro f hf; rw [Finset.card_univ, Fintype.card_fin])
      (by
        intro f hf
        rw [hf.1 _ ha₀]
        show i + n ≤ i + 1 + n
        lia),
      hcount, ih hi', Finset.prod_range_succ]
    ring

/-- Filling the interior column `k + 1` from the top down: each of the
`n` cells doubles the number of fillings. -/
lemma stageC_inner (n : ℕ) : ∀ r, r ≤ n → ∀ k, k < n →
    (Fillings n (colZero n n ∪ topRow n n ∪ intCols n k ∪ colPart n (k + 1) r)).ncard =
      2 ^ r * (Fillings n (colZero n n ∪ topRow n n ∪ intCols n k)).ncard := by
  intro r
  induction r with
  | zero =>
    intro _ k hk
    have h0 : colPart n (k + 1) 0 = (∅ : Set (Cell n)) := by
      ext c
      simp only [colPart, Set.mem_ofPred_eq, Set.mem_empty_iff_false, iff_false]
      lia
    rw [h0, Set.union_empty, pow_zero, one_mul]
  | succ r ih =>
    intro hr k hk
    have hr' : r ≤ n := Nat.le_of_succ_le hr
    have hkn : k < n + 1 := by lia
    have hkn1 : k + 1 < n + 1 := by lia
    have hnr : n - r < n + 1 := by lia
    have hnr1 : n - r - 1 < n + 1 := by lia
    have hid : colZero n n ∪ topRow n n ∪ intCols n k ∪ colPart n (k + 1) (r + 1) =
        insert (⟨k + 1, hkn1⟩, ⟨n - r - 1, hnr1⟩)
          (colZero n n ∪ topRow n n ∪ intCols n k ∪ colPart n (k + 1) r) := by
      ext c
      simp only [colZero, topRow, intCols, colPart, Set.mem_insert_iff, Set.mem_union,
        Set.mem_ofPred_eq, cell_ext]
      constructor <;> intro h <;> lia
    have hs : (⟨k + 1, hkn1⟩, ⟨n - r - 1, hnr1⟩) ∉
        colZero n n ∪ topRow n n ∪ intCols n k ∪ colPart n (k + 1) r := by
      simp only [colZero, topRow, intCols, colPart, Set.mem_union, Set.mem_ofPred_eq]
      lia
    have ha₀ : (⟨k, hkn⟩, ⟨n - r - 1, hnr1⟩) ∈
        colZero n n ∪ topRow n n ∪ intCols n k ∪ colPart n (k + 1) r := by
      by_cases hk0 : k = 0
      · subst hk0
        exact Or.inl (Or.inl (Or.inl ⟨rfl, by show n - r - 1 ≤ n; lia⟩))
      · exact Or.inl (Or.inr ⟨by show (1 : ℕ) ≤ k; lia, le_refl k,
          by show n - r - 1 < n; lia⟩)
    have hc₀ : (⟨k + 1, hkn1⟩, ⟨n - r, hnr⟩) ∈
        colZero n n ∪ topRow n n ∪ intCols n k ∪ colPart n (k + 1) r := by
      by_cases hr0 : r = 0
      · subst hr0
        exact Or.inl (Or.inl (Or.inr ⟨by show (1 : ℕ) ≤ k + 1; lia,
          by show k + 1 ≤ n; lia, by show n - 0 = n; lia⟩))
      · exact Or.inr ⟨rfl, le_refl _, by show n - r < n; lia⟩
    have hcount : (target (⟨k + 1, hkn1⟩, ⟨n - r, hnr⟩) -
        target (⟨k, hkn⟩, ⟨n - r - 1, hnr1⟩)).choose
        (target (⟨k + 1, hkn1⟩, ⟨n - r - 1, hnr1⟩) -
          target (⟨k, hkn⟩, ⟨n - r - 1, hnr1⟩)) = 2 := by
      have h1 : target (⟨k + 1, hkn1⟩, ⟨n - r, hnr⟩) -
          target (⟨k, hkn⟩, ⟨n - r - 1, hnr1⟩) = 2 := by
        show k + 1 + (n - r) - (k + (n - r - 1)) = 2
        lia
      have h2 : target (⟨k + 1, hkn1⟩, ⟨n - r - 1, hnr1⟩) -
          target (⟨k, hkn⟩, ⟨n - r - 1, hnr1⟩) = 1 := by
        show k + 1 + (n - r - 1) - (k + (n - r - 1)) = 1
        lia
      rw [h1, h2, Nat.choose_one_right]
    rw [hid, ncard_fillings_insert hs
      (A := fun f ↦ f (⟨k, hkn⟩, ⟨n - r - 1, hnr1⟩))
      (C := fun f ↦ f (⟨k + 1, hkn1⟩, ⟨n - r, hnr⟩))
      (by
        intro f hf d hd hds
        apply hf.2.1 d hd _ ha₀
        simp only [colZero, topRow, intCols, colPart, Set.mem_union, Set.mem_ofPred_eq] at hd
        simp only [Prod.le_def, Fin.le_def] at hds ⊢
        lia)
      (by
        intro f hf d hd hds
        apply hf.2.1 _ hc₀ d hd
        simp only [colZero, topRow, intCols, colPart, Set.mem_union, Set.mem_ofPred_eq] at hd
        simp only [Prod.le_def, Fin.le_def] at hds ⊢
        lia)
      (by
        intro g hg
        rw [Function.update_of_ne (ne_of_mem_of_not_mem ha₀ hs)]
        exact hg.2.1 _ (Set.mem_insert_of_mem _ ha₀) _ (Set.mem_insert _ _)
          (by simp only [Prod.le_def, Fin.le_def]; lia))
      (by
        intro g hg
        rw [Function.update_of_ne (ne_of_mem_of_not_mem hc₀ hs)]
        exact hg.2.1 _ (Set.mem_insert _ _) _ (Set.mem_insert_of_mem _ hc₀)
          (by simp only [Prod.le_def, Fin.le_def]; lia))
      (by
        intro f hf
        exact hf.2.1 _ ha₀ _ hc₀ (by simp only [Prod.le_def, Fin.le_def]; lia))
      (by intro f hf; exact hf.1 _ ha₀)
      (by intro f hf; exact hf.1 _ hc₀)
      (by
        intro f hf
        rw [hf.1 _ ha₀]
        show k + (n - r - 1) ≤ k + 1 + (n - r - 1)
        lia),
      hcount, ih hr' k hk, pow_succ]
    ring

/-- Counting the fillings of everything except the right column
of the grid. -/
lemma stageC (n : ℕ) : ∀ k, k ≤ n →
    (Fillings n (colZero n n ∪ topRow n n ∪ intCols n k)).ncard =
      2 ^ (n * k) * ((∏ i ∈ Finset.range n, (n - i)) * ∏ j ∈ Finset.range n, (2 * n - j)) := by
  intro k
  induction k with
  | zero =>
    intro _
    have h0 : intCols n 0 = (∅ : Set (Cell n)) := by
      ext c
      simp only [intCols, Set.mem_ofPred_eq, Set.mem_empty_iff_false, iff_false]
      lia
    rw [h0, Set.union_empty, stageB n n (le_refl n)]
    simp
  | succ k ih =>
    intro hk
    have hk' : k < n := by lia
    have hid : colZero n n ∪ topRow n n ∪ intCols n (k + 1) =
        colZero n n ∪ topRow n n ∪ intCols n k ∪ colPart n (k + 1) n := by
      ext c
      simp only [colZero, topRow, intCols, colPart, Set.mem_union, Set.mem_ofPred_eq]
      constructor <;> intro h <;> lia
    rw [hid, stageC_inner n n (le_refl n) k hk', ih (Nat.le_of_succ_le hk),
      Nat.mul_succ, pow_add]
    ring

theorem prod_range_self_sub (n : ℕ) :
    ∏ i ∈ Finset.range n, (n - i) = n ! := by
  rw [← Finset.prod_range_add_one_eq_factorial,
    ← Finset.prod_range_reflect (fun j => j + 1) n]
  refine Finset.prod_congr rfl fun j hj => ?_
  rw [Finset.mem_range] at hj
  lia

theorem prod_range_two_mul_sub_mul (n : ℕ) :
    (∏ j ∈ Finset.range n, (2 * n - j)) * (∏ i ∈ Finset.range n, (n - i)) = (2 * n) ! := by
  have h2 : ∏ j ∈ Finset.range n, (2 * n - j) = ∏ x ∈ Finset.range n, (n + x + 1) := by
    rw [← Finset.prod_range_reflect (fun j => 2 * n - j) n]
    refine Finset.prod_congr rfl fun j hj => ?_
    rw [Finset.mem_range] at hj
    lia
  have h3 : (∏ x ∈ Finset.range n, (n + x + 1)) * (∏ x ∈ Finset.range n, (x + 1))
      = (2 * n)! := by
    have h := Finset.prod_range_add (fun i => i + 1) n n
    rw [← Nat.two_mul n, Finset.prod_range_add_one_eq_factorial] at h
    rw [h]
    exact Nat.mul_comm _ _
  rw [prod_range_self_sub n, h2, ← Finset.prod_range_add_one_eq_factorial n, h3]

/-- The full count: the number of valid configurations is
`(2 * n)! * 2 ^ (n ^ 2)`. -/
lemma main_count (n : ℕ) : (Fillings n Set.univ).ncard = (2 * n)! * 2 ^ (n ^ 2) := by
  have huniv : (Set.univ : Set (Cell n)) = colZero n n ∪ topRow n n ∪ intCols n n := by
    ext c
    simp only [Set.mem_univ, colZero, topRow, intCols, Set.mem_union, Set.mem_ofPred_eq,
      true_iff]
    have h1 := c.1.isLt
    have h2 := c.2.isLt
    lia
  rw [huniv, stageC n n (le_refl n),
    mul_comm (∏ i ∈ Finset.range n, (n - i)) (∏ j ∈ Finset.range n, (2 * n - j)),
    prod_range_two_mul_sub_mul, show n * n = n ^ 2 from (pow_two n).symm, mul_comm]

abbrev answer (n : ℕ) : ℕ := (2 * n)! * 2 ^ (n ^ 2)

theorem usa2019_p4 (n : ℕ) :
    Nat.card {S : Fin (n + 1) → Fin (n + 1) → Finset (Fin (2 * n)) //
      (∀ i j, (S i j).card = i.val + j.val) ∧
      (∀ i k j l, i ≤ k → j ≤ l → S i j ⊆ S k l)} = answer n := by
  have e : {S : Fin (n + 1) → Fin (n + 1) → Finset (Fin (2 * n)) //
      (∀ i j, (S i j).card = i.val + j.val) ∧
      (∀ i k j l, i ≤ k → j ≤ l → S i j ⊆ S k l)} ≃ ↥(Fillings n Set.univ) := by
    refine ⟨?_, ?_, ?_, ?_⟩
    · exact fun S ↦ ⟨fun c ↦ S.1 c.1 c.2, by
        refine ⟨?_, ?_, ?_⟩
        · intro c _
          exact S.2.1 c.1 c.2
        · intro a _ b _ hab
          exact S.2.2 a.1 b.1 a.2 b.2 (Prod.le_def.mp hab).1 (Prod.le_def.mp hab).2
        · intro c hc
          exact absurd (Set.mem_univ c) hc⟩
    · exact fun S ↦ ⟨fun i j ↦ S.1 (i, j), by
        refine ⟨?_, ?_⟩
        · intro i j
          exact S.2.1 (i, j) (Set.mem_univ _)
        · intro i k j l hik hjl
          exact S.2.2.1 (i, j) (Set.mem_univ _) (k, l) (Set.mem_univ _)
            (Prod.le_def.mpr ⟨hik, hjl⟩)⟩
    · intro S
      exact Subtype.ext rfl
    · intro S
      apply Subtype.ext
      funext c
      change S.1 (c.1, c.2) = S.1 c
      rw [Prod.mk.eta]
  rw [Nat.card_congr e, Nat.card_coe_set_eq, main_count]

end Usa2019P4

运行答案 ▶Run the solution ▶ 下载答案 .leanDownload solution .lean

人的思考A human's take

USAMO 2019 Solution Notes — Evan Chen

Evan Chen 的题解先做归一化:边界链 $S_{0,0}\subset\cdots\subset S_{n,n}$ 每一步只加一个元素,选定后有 $(2n)!$ 种,并且可以不妨设 $S_{0,i}=\{1,\dots,i\}$、$S_{i,n}=\{1,\dots,n+i\}$,于是问题只剩填内部。Evan Chen's solution starts by normalizing: the border chain $S_{0,0}\subset\cdots\subset S_{n,n}$ adds exactly one element per step, giving $(2n)!$ choices, after which one may assume $S_{0,i}=\{1,\dots,i\}$ and $S_{i,n}=\{1,\dots,n+i\}$; only the interior remains.

他证明了一个更强的命题:对任何“杨表形状”的格子集合 $T$(一个格子在 $T$ 里,则它上方和左方的格子也在 $T$ 里),满足条件的填法恰好是 $2^{|T|}$ 种。He proves a stronger statement: for any Young-diagram-shaped set $T$ of cells (if a cell is in $T$, so are the cells above and to its left), the number of valid fillings is exactly $2^{|T|}$.

归纳的关键是角上的三个格子:若 $B=A\cup\{x\}$、$C=A\cup\{x,y\}$ 已固定,待定的 $S$ 大小夹在 $B$ 与 $C$ 之间,只能取 $A\cup\{x\}$(即 $B$)或 $A\cup\{y\}$,两种都合法,于是每添一格就多一个因子 2。The induction turns on a corner of three cells: if $B=A\cup\{x\}$ and $C=A\cup\{x,y\}$ are fixed, the pending $S$ has size strictly between them, so it can only be $A\cup\{x\}$ (that is, $B$) or $A\cup\{y\}$; both are legal, so each added cell doubles the count.

内部有 $n^2$ 个格子,所以填法是 $2^{n^2}$,总数 $(2n)!\cdot2^{n^2}$。文末还附了 Daniel Zhu 的双射解法:把每个元素看成从正方形左端走到右端的一条路径,$n^2$ 个内部顶点各自决定两条路径是否交叉,因此每点 2 种。There are $n^2$ interior cells, hence $2^{n^2}$ fillings and a total of $(2n)!\cdot2^{n^2}$. He also includes Daniel Zhu's bijection: view each element as a path from the left edge of the square to the right edge, with each of the $n^2$ interior vertices deciding whether its two paths cross — two options per vertex.

AI 随想An AI's reflection

以下由 AI 撰写。Written by AI.

这道题最漂亮的地方,是它没有去“数”那个巨大的对象,而是先改变看它的顺序。$(n+1)^2$ 个集合、每个都有 $i+j$ 个元素,直接想会以为自由度大得无从下手;可一旦把边界链钉住,内部的每一格就被它的左边和上边夹死了,只剩两个选择。指数级的搜索空间被结构压成了 $n^2$ 次独立抛硬币。The loveliest thing about this problem is that it never counts the huge object directly; it changes the order in which you look at it. With $(n+1)^2$ sets, each of size $i+j$, the freedom seems impossible to get hold of. But once the border chain is nailed down, every interior cell is squeezed between its left and upper neighbours and has only two options. An exponential search space collapses into $n^2$ independent coin flips.

这也解释了为什么归纳在这里这么好用:不是硬啃整体,而是找一个“当前只有这一格没定、而它的上下界都已经知道”的顺序。写程序时我们做的是同一件事——把一个大状态拆成可以局部决定的小步骤,让每一步的自由度小到能看清。That is also why induction works so well here: you do not attack the whole thing, you find an order in which exactly one cell is undecided and both of its bounds are known. It is what we do in programs — split a large state into locally decidable steps, each small enough that its freedom is visible.

形式化的版本还多给了一层东西:那些在纸上一句“显然只有两种”的地方,被展开成组合数引理、边界乘积和逐格归纳。人读证明时容易滑过去的“显然”,在 Lean 里必须真的成立。The formal version adds one more layer: places where a paper proof says “obviously there are two choices” become a binomial lemma, a product over the border, and a cell-by-cell induction. The “obvious” that a human skims must actually hold in Lean.

✓ 已通过 Lean 编译验证(无 sorry,无额外公理)✓ Verified by Lean (no sorry, no extra axioms) · 题目与形式化证明来自 compfiles(Apache-2.0 (compfiles, David Renshaw and contributors))Problem and formal proof from compfiles (Apache-2.0 (compfiles, David Renshaw and contributors)) · Lean v4.36.0-rc2 · Mathlib 1c2b155

程序员随想Programmer Reflections

哲学与生活Philosophy and Life

工具角Tools Corner