每日科技文摘Daily Tech Digest

AI 能力过剩时代的四个人类优势Four Human Advantages in the Age of AI Overhang

发布于 2026-10-01Published 2026-10-01

今日深读Today's Deep Read

AI 能力过剩:真正稀缺的不是算力,是你AI Capability Overhang: What's Actually Scarce Isn't Compute — It's You

过去几个月,AI 领域几乎每天都在讨论一个话题:未来的 AI 会做什么?它会取代多少工作?它会不会失控?这些问题当然重要,但 Ethan Mollick 认为,我们可能把所有注意力都放错了地方。真正值得关注的问题不是未来的 AI 能做什么——而是现在的 AI 能做什么,以及为什么几乎没有人真正在用它做那些事。Over the past few months, almost every discussion in the AI world has been about what future AI will do: how many jobs will it replace, will it get out of control, what should we be worried about? These are important questions. But Ethan Mollick thinks we might be looking in the wrong direction. The more pressing question isn't what future AI will be capable of—it's what current AI is already capable of, and why almost nobody is using it for those things yet.

Mollick 举了几个例子:他用 GPT-6 Astra 把一个 1977 年的文字冒险游戏 Zork 变成了完整的 3D 动作游戏,让 Fable 5.1 从视频和照片里重建了意大利作家翁贝托·埃科的五千册私人藏书,还让 AI 用自己的书的内容做了一条 30 秒的动作电影预告片——从 Blender 3D 建模到视频剪辑,全程只用了他几次口头反馈。这些任务如果让一个团队来做,需要数周时间。但这里的关键不是 AI 多厉害,而是这些能力大部分还没有被普通人发掘和使用。Mollick shares a few examples: he had GPT-6 Astra turn a 1977 text adventure game called Zork into a full 3D action game, had Fable 5.1 reconstruct Italian author Umberto Eco's 5,000-book private library from videos and photographs, and got AI to create a 30-second action movie trailer from his own book manuscript—all with only a handful of verbal feedback from him. A human team would have spent weeks on each of these tasks. But the key takeaway isn't that AI is impressive. It's that most of these capabilities haven't been discovered or used by the average person yet.

他把这种现象叫作「能力悬垂」(capability overhang)——AI 实际能做到的事情,和大多数人实际在用 AI 做的事情之间,存在着巨大的落差。这个落差不是因为 AI 还不够强,而是因为大多数人根本没有把自己的优势带入 AI 协作中。大多数人用 AI 的方式,是把它当作一个更快的搜索引擎或者一个能写邮件的助手。但 Mollick 认为,真正能从 AI 中获得巨大回报的人,是那些能把自己的四个优势与 AI 的能力结合起来的人。He calls this phenomenon 'capability overhang'—the gap between what AI can actually do and what most people are actually using it to do. This gap exists not because AI isn't powerful enough, but because most people haven't brought their own advantages into the collaboration. Most people use AI as a faster search engine or an email assistant. Mollick argues that the people who will get enormous returns from AI are those who combine four specific human advantages with AI's capabilities.

这四个优势是:深度知识、广博见识、品味和能动性。深度知识是你对自己领域的直觉——有经验的会计师看一眼电子表格就知道哪里不对。这种直觉让你知道 AI 在什么时候是对的、什么时候走了偏。广博见识是你跨领域的知识储备——AI 学过设计思维、贝叶斯推理、丰田生产方式,但它不会主动告诉你这些模式,除非你知道该问什么。品味是你从 AI 输出中选择、拒绝、重组的能力——当生成变得廉价,判断变得昂贵。能动性则是你愿意去探索 AI 边界的好奇心和行动力——在没有人告诉你能做什么的时候,自己试一试。这四个优势共同构成了一种新的能力模型:你不是在和 AI 竞争输出,而是在和 AI 合作完成只有人类 + AI 才能完成的事情。Those four advantages are: deep knowledge, wide knowledge, taste, and agency. Deep knowledge is your domain intuition—an experienced accountant can glance at a spreadsheet and know something is wrong. This intuition tells you when AI is right and when it has drifted. Wide knowledge is your cross-domain reservoir—AI has learned design thinking, Bayesian reasoning, the Toyota Production System, but it won't volunteer these patterns unless you know to ask. Taste is your ability to select, reject, and recombine AI output—when creation becomes cheap, judgment becomes expensive. Agency is the curiosity and willingness to explore AI's boundaries yourself—to try things when no one has told you they're possible. Together, these four advantages form a new model of capability: you're not competing with AI on output, you're collaborating with it on things only a human + AI team can accomplish.

这篇文章最有力量的地方,不在于它列举了四个优势,而在于它用一个具体的例子说明了为什么这些优势对普通人来说仍然重要。当 AI 能写出代码、生成图片、制作视频的时候,很多人感到的不是兴奋,而是一种空洞的无力感。Mollick 的答案是:你的价值不在于你能生成多少东西,而在于你知道什么值得生成,以及为什么。The most powerful part of this article isn't the list of four advantages. It's the specific example that explains why these advantages still matter for ordinary people. When AI can write code, generate images, and produce video, many people feel not excitement but a hollow sense of inadequacy. Mollick's answer is simple: your value isn't in how much you can produce—it's in knowing what's worth producing, and why.

AI 思考AI Thoughts

数学之美Beauty of Mathematics

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

USAMO 2020 第 4 题:最大的互质对数USAMO 2020 Problem 4: Maximum Number of Coprime-Adjacent Pairs

给定 100 个不同的有序非负整数对 $(a_1, b_1), (a_2, b_2), \ldots, (a_{100}, b_{100})$。Given 100 distinct ordered pairs of nonnegative integers $(a_1, b_1), (a_2, b_2), \ldots, (a_{100}, b_{100})$.

令 $N$ 为满足 $1 \le i < j \le 100$ 且 $|a_i b_j - a_j b_i| = 1$ 的整数对 $(i, j)$ 的数量。Let $N$ denote the number of pairs $(i, j)$ with $1 \le i < j \le 100$ satisfying $|a_i b_j - a_j b_i| = 1$.

求 $N$ 的最大可能值。Determine the largest possible value of $N$.

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

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

import Mathlib.Algebra.Order.Ring.Star
import Mathlib.AlgebraicTopology.SimplexCategory.Basic
import Mathlib.Analysis.Normed.Ring.Lemmas
import Mathlib.Data.Int.Star
import Mathlib.RingTheory.Coprime.Lemmas
import Mathlib.Tactic.LinearCombination
import Mathlib.Tactic.LinearCombination.Lemmas

/-!
# USA Mathematical Olympiad 2020, Problem 4

Suppose that (a₁, b₁), (a₂, b₂), ..., (a₁₀₀, b₁₀₀) are distinct ordered pairs
of nonnegative integers. Let N denote the number of pairs of integers (i, j)
satisfying 1 ≤ i < j ≤ 100 and |aᵢbⱼ − aⱼbᵢ| = 1. Determine the largest
possible value of N over all possible choices of the 100 ordered pairs.
-/

namespace Usa2020P4

def det (P Q : ℕ × ℕ) : ℤ := (P.1 : ℤ) * (Q.2 : ℤ) - (Q.1 : ℤ) * (P.2 : ℤ)

abbrev answer : ℕ := sorry

set_option maxRecDepth 4096 in

theorem usa2020_p4 :
    IsGreatest {N : ℕ | ∃ v : Fin 100 → ℕ × ℕ, Function.Injective v ∧
      N = (Finset.univ.filter fun p : Fin 100 × Fin 100 =>
        p.1 < p.2 ∧ |det (v p.1) (v p.2)| = 1).card} answer := by
  sorry
end Usa2020P4

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

提示Hint

考虑将点 $(a_i, b_i)$ 视为平面上的格点。条件 $|a_i b_j - a_j b_i| = 1$ 意味着由原点和这两个点构成的平行四边形面积为 1。从最远点入手,考虑它与其它点形成的行列式。Think of the points $(a_i, b_i)$ as lattice points in the plane. The condition $|a_i b_j - a_j b_i| = 1$ means the parallelogram formed by the origin and these two points has area 1. Start with the farthest point and consider the determinants it forms with all other points.

答案与讲解Solution & walkthrough
  1. 构造:取点集 $\{(1,0), (1,1), (2,1), (3,1), \ldots, (99,1)\}$。$(1,0)$ 与每个 $(k,1)$ 的行列式绝对值为 1,共 99 对;相邻的 $(k,1)$ 与 $(k+1,1)$ 的行列式绝对值也为 1,共 98 对。总计 $99 + 98 = 197$。Construction: Take the point set $\{(1,0), (1,1), (2,1), (3,1), \ldots, (99,1)\}$. The point $(1,0)$ forms determinant $\pm 1$ with each $(k,1)$, giving 99 pairs; adjacent points $(k,1)$ and $(k+1,1)$ also give determinant $\pm 1$, giving 98 more pairs. Total: $99 + 98 = 197$.
  2. 上界证明的核心思想:对 $n$ 个点用强归纳法。取距离原点最远的点 $P$。如果 $\gcd(P_1, P_2) > 1$,则 $P$ 与任何其它点形成的行列式都被这个 gcd 整除,不可能等于 1,所以 $P$ 贡献 0 对。如果 $P$ 是 primitive(即 gcd=1),则满足 $|\det(P,Q)|=1$ 的点 $Q$ 位于两条平行线上($\det(P,Q)=1$ 和 $\det(P,Q)=-1$)。Key idea for the upper bound: Strong induction on $n$ points. Take the point $P$ farthest from the origin. If $\gcd(P_1, P_2) > 1$, then $\gcd$ divides every determinant $\det(P,Q)$, so $P$ contributes 0 pairs. If $P$ is primitive (gcd=1), then points $Q$ with $|\det(P,Q)|=1$ lie on two parallel lines.
  3. 在这两条线上的格点之间间距恰好是向量 $P$ 本身。由于 $P$ 是最远点,每条线上在闭圆盘内(包含所有给定点)最多只能有一个这样的 $Q$(除了原点,但原点不在我们的点集中)。因此 $P$ 最多贡献 2 对。On each of these two lines, lattice points are spaced exactly by the vector $P$. Since $P$ is the farthest point, each line can contain at most one such $Q$ (other than the origin, which isn't in our set) within the closed disk containing all points. So $P$ contributes at most 2 pairs.
  4. 去掉 $P$ 后剩 $n-1$ 个点,由归纳假设有最多 $2(n-1)-3$ 对。加上 $P$ 贡献的至多 2 对,总共最多 $2(n-1)-3+2 = 2n-3$ 对。当 $n=100$ 时,最大值为 $2 \times 100 - 3 = 197$。After removing $P$, we have $n-1$ points, which by induction have at most $2(n-1)-3$ pairs. Adding at most 2 from $P$, the total is at most $2(n-1)-3+2 = 2n-3$. For $n=100$, the maximum is $2 \times 100 - 3 = 197$.
/-
Copyright (c) 2026 The Compfiles Contributors. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Kimi K3
-/

import Mathlib.Algebra.Order.Ring.Star
import Mathlib.AlgebraicTopology.SimplexCategory.Basic
import Mathlib.Analysis.Normed.Ring.Lemmas
import Mathlib.Data.Int.Star
import Mathlib.RingTheory.Coprime.Lemmas
import Mathlib.Tactic.LinearCombination
import Mathlib.Tactic.LinearCombination.Lemmas

/-!
# USA Mathematical Olympiad 2020, Problem 4

Suppose that (a₁, b₁), (a₂, b₂), ..., (a₁₀₀, b₁₀₀) are distinct ordered pairs
of nonnegative integers. Let N denote the number of pairs of integers (i, j)
satisfying 1 ≤ i < j ≤ 100 and |aᵢbⱼ − aⱼbᵢ| = 1. Determine the largest
possible value of N over all possible choices of the 100 ordered pairs.
-/

namespace Usa2020P4

/-- The determinant `aᵢ bⱼ − aⱼ bᵢ` of two ordered pairs of nonnegative
integers, viewed as an integer. -/
def det (P Q : ℕ × ℕ) : ℤ := (P.1 : ℤ) * (Q.2 : ℤ) - (Q.1 : ℤ) * (P.2 : ℤ)

abbrev answer : ℕ := 197

/-!
## Solution

The answer is `197 = 2 * 100 - 3`; more generally the maximum for `n ≥ 2`
points is `2n - 3`.

*Construction*: take `(1, 0)` together with `(k, 1)` for `1 ≤ k ≤ 99`. The
good pairs are `{(1, 0), (k, 1)}` for `1 ≤ k ≤ 99` (99 pairs) and
`{(k, 1), (k + 1, 1)}` for `1 ≤ k ≤ 98` (98 pairs), totalling `197`.

*Upper bound*: induction on `n`. Given `n ≥ 3` points, let `P` be a point with
maximal distance from the origin. Then `P` belongs to at most two good pairs:
if `P = (0, 0)` or `gcd P.1 P.2 > 1` it belongs to none, since `gcd P.1 P.2`
divides every determinant `det P Q`; and if `P = (a, b)` is primitive, the good
partners `Q` of `P` lie on one of the two lines `det P Q = ±1`. On each line
the lattice points are spaced exactly by the vector `(a, b)`, so at most one of
them (other than the origin, which is never a good partner) can lie in the
closed disk of radius `|P|` around the origin that contains all the given
points. Removing `P` therefore destroys at most two good pairs, and
`2 * (n - 1) - 3 + 2 = 2 * n - 3` by induction.
-/

/-- The good two-element subsets of a set of points: those `{P, Q}` with
`|det P Q| = 1`. -/
private def goodSets (S : Finset (ℕ × ℕ)) : Finset (Finset (ℕ × ℕ)) :=
  (S.powersetCard 2).filter fun s => ∀ P ∈ s, ∀ Q ∈ s, P ≠ Q → |det P Q| = 1

/-- The good index pairs of a choice `v` of 100 points. -/
private def goodPairs (v : Fin 100 → ℕ × ℕ) : Finset (Fin 100 × Fin 100) :=
  Finset.univ.filter fun p => p.1 < p.2 ∧ |det (v p.1) (v p.2)| = 1

private lemma det_swap (P Q : ℕ × ℕ) : det Q P = -det P Q := by unfold det; ring

/-- If `(u, v) = (u', v') + t • (a, b)` with `t ≥ 1`, all of `u' v' a b`
nonnegative, and `u² + v² ≤ a² + b²`, then `(u', v') = (0, 0)`. -/
private lemma eq_zero_of_eq_add_mul {u v u' v' a b t : ℤ} (ha : 0 ≤ a) (hb : 0 ≤ b)
    (hu' : 0 ≤ u') (hv' : 0 ≤ v') (ht : 1 ≤ t)
    (huu : u = u' + t * a) (hvv : v = v' + t * b)
    (hn : u ^ 2 + v ^ 2 ≤ a ^ 2 + b ^ 2) : u' = 0 ∧ v' = 0 := by
  have h1 : a ≤ u := by
    calc a = 1 * a := (one_mul a).symm
    _ ≤ t * a := mul_le_mul_of_nonneg_right ht ha
    _ ≤ u' + t * a := le_add_of_nonneg_left hu'
    _ = u := huu.symm
  have h2 : b ≤ v := by
    calc b = 1 * b := (one_mul b).symm
    _ ≤ t * b := mul_le_mul_of_nonneg_right ht hb
    _ ≤ v' + t * b := le_add_of_nonneg_left hv'
    _ = v := hvv.symm
  have h3 : a ^ 2 ≤ u ^ 2 := pow_le_pow_left₀ ha h1 2
  have h4 : b ^ 2 ≤ v ^ 2 := pow_le_pow_left₀ hb h2 2
  have h5 : a ^ 2 = u ^ 2 ∧ b ^ 2 = v ^ 2 := by constructor <;> linarith
  have hu_eq : u = a := by
    rcases sq_eq_sq_iff_eq_or_eq_neg.mp h5.1.symm with h | h
    · exact h
    · linarith
  have hv_eq : v = b := by
    rcases sq_eq_sq_iff_eq_or_eq_neg.mp h5.2.symm with h | h
    · exact h
    · linarith
  have hu'e : u' = (1 - t) * a := by linear_combination hu_eq - huu
  have hv'e : v' = (1 - t) * b := by linear_combination hv_eq - hvv
  have h1t : (1 : ℤ) - t ≤ 0 := by linarith
  exact ⟨le_antisymm (by rw [hu'e]; exact mul_nonpos_of_nonpos_of_nonneg h1t ha) hu',
    le_antisymm (by rw [hv'e]; exact mul_nonpos_of_nonpos_of_nonneg h1t hb) hv'⟩

/-- Two points of the first quadrant having the same determinant of absolute
value `1` with a primitive point `P`, and both at most as far from the origin
as `P`, must coincide. -/
private lemma eq_of_det_eq_of_le {P Q₁ Q₂ : ℕ × ℕ} (hP : Nat.Coprime P.1 P.2)
    (hdet : det P Q₁ = det P Q₂) (habs : |det P Q₁| = 1)
    (hn₁ : Q₁.1 ^ 2 + Q₁.2 ^ 2 ≤ P.1 ^ 2 + P.2 ^ 2)
    (hn₂ : Q₂.1 ^ 2 + Q₂.2 ^ 2 ≤ P.1 ^ 2 + P.2 ^ 2) : Q₁ = Q₂ := by
  obtain ⟨a, b⟩ := P
  obtain ⟨u₁, v₁⟩ := Q₁
  obtain ⟨u₂, v₂⟩ := Q₂
  simp only [det] at hdet habs
  dsimp only at hP hn₁ hn₂ hdet habs
  have hn₁' : (u₁ : ℤ) ^ 2 + (v₁ : ℤ) ^ 2 ≤ (a : ℤ) ^ 2 + (b : ℤ) ^ 2 := by
    exact_mod_cast hn₁
  have hn₂' : (u₂ : ℤ) ^ 2 + (v₂ : ℤ) ^ 2 ≤ (a : ℤ) ^ 2 + (b : ℤ) ^ 2 := by
    exact_mod_cast hn₂
  have h1 : (a : ℤ) * ((v₁ : ℤ) - (v₂ : ℤ)) = ((u₁ : ℤ) - (u₂ : ℤ)) * (b : ℤ) := by
    linear_combination hdet
  have hcop : IsCoprime (a : ℤ) (b : ℤ) := Int.isCoprime_iff_gcd_eq_one.mpr (by
    rw [Int.gcd_natCast_natCast]; exact hP)
  have hdvd : (a : ℤ) ∣ (u₁ : ℤ) - u₂ :=
    hcop.dvd_of_dvd_mul_right ⟨(v₁ : ℤ) - v₂, h1.symm⟩
  obtain ⟨t, hta, htb⟩ :
      ∃ t : ℤ, (u₁ : ℤ) - u₂ = t * a ∧ (v₁ : ℤ) - v₂ = t * b := by
    obtain ⟨t, ht⟩ := hdvd
    by_cases ha0 : (a : ℤ) = 0
    · have ha0' : a = 0 := by exact_mod_cast ha0
      have hb1 : (b : ℤ) = 1 := by
        have hP1 : Nat.gcd a b = 1 := hP
        rw [ha0', Nat.gcd_zero_left] at hP1
        exact_mod_cast hP1
      exact ⟨(v₁ : ℤ) - v₂, by rw [ht, ha0, zero_mul, mul_zero], by rw [hb1, mul_one]⟩
    · refine ⟨t, by rw [ht, mul_comm], ?_⟩
      have h2 : (a : ℤ) * ((v₁ : ℤ) - v₂) = (a : ℤ) * (t * (b : ℤ)) := by
        rw [h1, ht]; ring
      exact mul_left_cancel₀ ha0 h2
  have hta' : (u₁ : ℤ) = u₂ + t * a := by linear_combination hta
  have htb' : (v₁ : ℤ) = v₂ + t * b := by linear_combination htb
  rcases lt_or_ge t 1 with htl | htg
  · by_cases ht0 : t = 0
    · subst ht0
      rw [zero_mul, add_zero] at hta'
      rw [zero_mul, add_zero] at htb'
      exact Prod.ext_iff.mpr ⟨Nat.cast_inj.mp hta', Nat.cast_inj.mp htb'⟩
    · have htn : 1 ≤ -t := by lia
      have huu : (u₂ : ℤ) = u₁ + (-t) * a := by linear_combination -hta'
      have hvv : (v₂ : ℤ) = v₁ + (-t) * b := by linear_combination -htb'
      obtain ⟨hu1, hv1⟩ := eq_zero_of_eq_add_mul (Int.natCast_nonneg _)
        (Int.natCast_nonneg _) (Int.natCast_nonneg _) (Int.natCast_nonneg _)
        htn huu hvv hn₂'
      rw [hu1, hv1] at habs
      simp at habs
  · obtain ⟨hu2, hv2⟩ := eq_zero_of_eq_add_mul (Int.natCast_nonneg _)
      (Int.natCast_nonneg _) (Int.natCast_nonneg _) (Int.natCast_nonneg _)
      htg hta' htb' hn₁'
    rw [hdet, hu2, hv2] at habs
    simp at habs

/-- The gcd of the coordinates of `P` divides every determinant `det P Q`. -/
private lemma gcd_dvd_det (P Q : ℕ × ℕ) : (Nat.gcd P.1 P.2 : ℤ) ∣ det P Q := by
  obtain ⟨a, b⟩ := P
  obtain ⟨u, v⟩ := Q
  exact dvd_sub (dvd_mul_of_dvd_left (by exact_mod_cast Nat.gcd_dvd_left a b) _)
    (dvd_mul_of_dvd_right (by exact_mod_cast Nat.gcd_dvd_right a b) _)

/-- A farthest point `P` of `S` forms good pairs with at most two points
of `S`. -/
private lemma card_partners_le_two {S : Finset (ℕ × ℕ)} {P : ℕ × ℕ}
    (hmax : ∀ Q ∈ S, Q.1 ^ 2 + Q.2 ^ 2 ≤ P.1 ^ 2 + P.2 ^ 2) :
    ((S.erase P).filter fun Q => |det P Q| = 1).card ≤ 2 := by
  by_cases hP : Nat.Coprime P.1 P.2
  · have hmaps : Set.MapsTo (det P) ((S.erase P).filter fun Q => |det P Q| = 1)
        ({1, -1} : Finset ℤ) := by
      intro Q hQ
      rw [Finset.mem_coe, Finset.mem_filter] at hQ
      rcases eq_or_eq_neg_of_abs_eq hQ.2 with h | h
      · rw [Finset.mem_coe, h]; exact Finset.mem_insert_self 1 {-1}
      · rw [Finset.mem_coe, h]
        exact Finset.mem_insert_of_mem (Finset.mem_singleton_self (-1))
    have hinj : Set.InjOn (det P) ((S.erase P).filter fun Q => |det P Q| = 1) := by
      intro Q₁ hQ₁ Q₂ hQ₂ hd
      rw [Finset.mem_coe, Finset.mem_filter, Finset.mem_erase] at hQ₁ hQ₂
      exact eq_of_det_eq_of_le hP hd hQ₁.2 (hmax Q₁ hQ₁.1.2) (hmax Q₂ hQ₂.1.2)
    have h2card : (({1, -1} : Finset ℤ)).card = 2 :=
      Finset.card_pair_eq_two_iff.mpr (by norm_num)
    exact (Finset.card_le_card_of_injOn (det P) hmaps hinj).trans_eq h2card
  · suffices h : ((S.erase P).filter fun Q => |det P Q| = 1) = ∅ by
      rw [h, Finset.card_empty]; exact Nat.zero_le 2
    rw [Finset.filter_eq_empty_iff]
    intro Q hQ habs
    obtain ⟨a, b⟩ := P
    have hdvd := gcd_dvd_det (a, b) Q
    have hdvd1 : ((Nat.gcd (a, b).1 (a, b).2 : ℕ) : ℤ) ∣ 1 := by
      rcases eq_or_eq_neg_of_abs_eq habs with h | h
      · rwa [h] at hdvd
      · rw [h] at hdvd; exact dvd_neg.mp hdvd
    have h1 : ((Nat.gcd (a, b).1 (a, b).2 : ℕ) : ℤ) = 1 := by
      rcases Int.isUnit_iff.mp (isUnit_of_dvd_one hdvd1) with h | h
      · exact h
      · have hnonneg : (0 : ℤ) ≤ ((Nat.gcd (a, b).1 (a, b).2 : ℕ) : ℤ) :=
          Int.natCast_nonneg _
        linarith
    exact hP (by exact_mod_cast h1)

/-- A set of `n ≥ 2` points determines at most `2 * n - 3` good pairs. -/
private lemma card_goodSets_le : ∀ n : ℕ, 2 ≤ n → ∀ S : Finset (ℕ × ℕ),
    S.card = n → (goodSets S).card ≤ 2 * n - 3 := by
  intro n
  induction n using Nat.strong_induction_on with
  | _ n IH =>
    intro hn S hcard
    rcases Nat.lt_or_ge n 3 with hlt | hge
    · have hn2 : n = 2 := by lia
      subst hn2
      calc (goodSets S).card ≤ (S.powersetCard 2).card := Finset.card_filter_le _ _
        _ = 1 := by rw [Finset.card_powersetCard, hcard]; decide
    · have hne : S.Nonempty := Finset.card_pos.mp (by rw [hcard]; lia)
      obtain ⟨P, hPS, hmax⟩ :=
        Finset.exists_max_image S (fun Q : ℕ × ℕ => Q.1 ^ 2 + Q.2 ^ 2) hne
      have hcard' : (S.erase P).card = n - 1 := by
        rw [Finset.card_erase_of_mem hPS, hcard]
      have hIH : (goodSets (S.erase P)).card ≤ 2 * (n - 1) - 3 :=
        IH (n - 1) (by lia) (by lia) (S.erase P) hcard'
      have hpart : ((S.erase P).filter fun Q => |det P Q| = 1).card ≤ 2 :=
        card_partners_le_two hmax
      have hcover : goodSets S ⊆ goodSets (S.erase P) ∪
          ((S.erase P).filter fun Q => |det P Q| = 1).image (fun Q => {P, Q}) := by
        intro s hs
        rw [goodSets, Finset.mem_filter, Finset.mem_powersetCard] at hs
        obtain ⟨⟨hsS, hscard⟩, hsgood⟩ := hs
        by_cases hPs : P ∈ s
        · obtain ⟨Q, hQe⟩ := Finset.card_eq_one.mp (by
            rw [Finset.card_erase_of_mem hPs, hscard])
          have hQse : Q ∈ s.erase P := by rw [hQe]; exact Finset.mem_singleton_self Q
          have hQs : Q ∈ s := Finset.mem_of_mem_erase hQse
          have hQP : P ≠ Q := fun h => (Finset.mem_erase.mp (h ▸ hQse)).1 rfl
          have hs_eq : s = {P, Q} := by rw [← Finset.insert_erase hPs, hQe]
          have hQS : Q ∈ S.erase P := Finset.erase_subset_erase P hsS hQse
          have hQgood : |det P Q| = 1 := hsgood P hPs Q hQs hQP
          exact Finset.mem_union_right _ (Finset.mem_image.mpr
            ⟨Q, Finset.mem_filter.mpr ⟨hQS, hQgood⟩, hs_eq.symm⟩)
        · exact Finset.mem_union_left _ (Finset.mem_filter.mpr
            ⟨Finset.mem_powersetCard.mpr
              ⟨Finset.subset_erase.mpr ⟨hsS, hPs⟩, hscard⟩, hsgood⟩)
      have h1 : (goodSets S).card ≤ (goodSets (S.erase P) ∪
          ((S.erase P).filter fun Q => |det P Q| = 1).image
            (fun Q => ({P, Q} : Finset (ℕ × ℕ)))).card :=
        Finset.card_le_card hcover
      have h2 : (goodSets (S.erase P) ∪
          ((S.erase P).filter fun Q => |det P Q| = 1).image
            (fun Q => ({P, Q} : Finset (ℕ × ℕ)))).card ≤
          (goodSets (S.erase P)).card +
          (((S.erase P).filter fun Q => |det P Q| = 1).image
            (fun Q => ({P, Q} : Finset (ℕ × ℕ)))).card :=
        Finset.card_union_le _ _
      have h3 : (goodSets (S.erase P)).card +
          (((S.erase P).filter fun Q => |det P Q| = 1).image
            (fun Q => ({P, Q} : Finset (ℕ × ℕ)))).card ≤
          (2 * (n - 1) - 3) + 2 :=
        add_le_add hIH (le_trans Finset.card_image_le hpart)
      have h4 : (2 * (n - 1) - 3) + 2 = 2 * n - 3 := by lia
      exact h1.trans ((h2.trans h3).trans_eq h4)

set_option maxRecDepth 4096 in
/-- For an injective choice `v` of points, the good index pairs and the good
two-element subsets of the image are equinumerous. -/
private lemma card_goodPairs_eq {v : Fin 100 → ℕ × ℕ} (hv : Function.Injective v) :
    (goodPairs v).card = (goodSets (Finset.univ.image v)).card := by
  apply Finset.card_bij (fun p _ => ({v p.1, v p.2} : Finset (ℕ × ℕ)))
  · intro p hp
    simp only [goodPairs, Finset.mem_filter, Finset.mem_univ, true_and] at hp
    obtain ⟨hlt, hgood⟩ := hp
    have hne : v p.1 ≠ v p.2 := fun h => hlt.ne (hv h)
    rw [goodSets, Finset.mem_filter, Finset.mem_powersetCard]
    refine ⟨⟨?_, Finset.card_pair_eq_two_iff.mpr hne⟩, ?_⟩
    · intro x hx
      rw [Finset.mem_insert, Finset.mem_singleton] at hx
      rcases hx with rfl | rfl <;> exact Finset.mem_image_of_mem v (Finset.mem_univ _)
    · intro P hP Q hQ hPQ
      rw [Finset.mem_insert, Finset.mem_singleton] at hP hQ
      rcases hP with rfl | rfl
      · rcases hQ with rfl | rfl
        · exact absurd rfl hPQ
        · exact hgood
      · rcases hQ with rfl | rfl
        · rw [det_swap, abs_neg]; exact hgood
        · exact absurd rfl hPQ
  · intro p hp q hq h
    simp only [goodPairs, Finset.mem_filter, Finset.mem_univ, true_and] at hp hq
    have h1 : v p.1 ∈ ({v q.1, v q.2} : Finset (ℕ × ℕ)) := by
      rw [← h]; exact Finset.mem_insert_self _ _
    have h2 : v p.2 ∈ ({v q.1, v q.2} : Finset (ℕ × ℕ)) := by
      rw [← h]; exact Finset.mem_insert_of_mem (Finset.mem_singleton_self _)
    rw [Finset.mem_insert, Finset.mem_singleton] at h1 h2
    rcases h1 with h1 | h1
    · rcases h2 with h2 | h2
      · exact absurd ((hv (h2.trans h1.symm)).symm) hp.1.ne
      · exact Prod.ext_iff.mpr ⟨hv h1, hv h2⟩
    · rcases h2 with h2 | h2
      · have e1 : p.1 = q.2 := hv h1
        have e2 : p.2 = q.1 := hv h2
        exfalso; lia
      · exact absurd (hv (h1.trans h2.symm)) hp.1.ne
  · intro s hs
    rw [goodSets, Finset.mem_filter, Finset.mem_powersetCard] at hs
    obtain ⟨⟨hsS, hscard⟩, hsgood⟩ := hs
    obtain ⟨P, Q, hPQ, hsPQ⟩ := Finset.card_eq_two.mp hscard
    subst hsPQ
    have hPS : P ∈ Finset.univ.image v := hsS (Finset.mem_insert_self P {Q})
    have hQS : Q ∈ Finset.univ.image v :=
      hsS (Finset.mem_insert_of_mem (Finset.mem_singleton_self Q))
    rw [Finset.mem_image] at hPS hQS
    obtain ⟨i, -, hi⟩ := hPS
    obtain ⟨j, -, hj⟩ := hQS
    have hgood : |det P Q| = 1 := hsgood P (Finset.mem_insert_self P {Q}) Q
      (Finset.mem_insert_of_mem (Finset.mem_singleton_self Q)) hPQ
    have hij : i ≠ j := fun h => hPQ (hi.symm.trans (h ▸ hj))
    rcases lt_or_gt_of_ne hij with hlt | hgt
    · refine ⟨(i, j), ?_, ?_⟩
      · simp only [goodPairs, Finset.mem_filter, Finset.mem_univ, true_and]
        refine ⟨hlt, ?_⟩
        show |det (v i) (v j)| = 1
        rw [hi, hj]; exact hgood
      · show ({v i, v j} : Finset (ℕ × ℕ)) = {P, Q}
        rw [hi, hj]
    · refine ⟨(j, i), ?_, ?_⟩
      · simp only [goodPairs, Finset.mem_filter, Finset.mem_univ, true_and]
        refine ⟨hgt, ?_⟩
        show |det (v j) (v i)| = 1
        rw [hj, hi, det_swap, abs_neg]; exact hgood
      · show ({v j, v i} : Finset (ℕ × ℕ)) = {P, Q}
        rw [hj, hi, Finset.pair_comm]

/-- USA Mathematical Olympiad 2020, Problem 4 -/
theorem usa2020_p4 :
    IsGreatest {N : ℕ | ∃ v : Fin 100 → ℕ × ℕ, Function.Injective v ∧
      N = (Finset.univ.filter fun p : Fin 100 × Fin 100 =>
        p.1 < p.2 ∧ |det (v p.1) (v p.2)| = 1).card} answer := by
  constructor
  · refine ⟨fun i => if i = 0 then (1, 0) else (i.val, 1), by decide, by decide +kernel⟩
  · intro N hN
    obtain ⟨v, hv, hN'⟩ := hN
    rw [hN']
    change (goodPairs v).card ≤ answer
    rw [card_goodPairs_eq hv]
    have h100 : (Finset.univ.image v).card = 100 := by
      rw [Finset.card_image_of_injective _ hv, Finset.card_univ, Fintype.card_fin]
    exact (card_goodSets_le 100 (by norm_num) _ h100).trans_eq (by norm_num [answer])

end Usa2020P4

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

人的思考A human's take

2020 USAMO Problems/Problem 4 - AoPS Wiki — Lopkiloinm、SigmaPiE(AoPS Wiki 贡献者)

AoPS Wiki 的题目页,附有两篇社区解答。第一篇(Lopkiloinm)从最小情形入手:三个点可以两两满足行列式 $\pm1$(相当于「三角形」),第四个点却加不进来;由此归纳出 $n$ 个点的规律,得到 $2n-3$。第二篇(SigmaPiE)用鞋带公式把条件重读成几何语言:$|a_i b_j - a_j b_i| = 1$ 意味着原点与两点构成的三角形面积为 $\tfrac12$,先构造出达到 197 的「两条格线」配置,再逐情形论证把点挪出这两条线只会净损失配对。Wiki 里的公式是图片,抓取时正文丢失,但两篇证明的骨架都能读出来:一篇是归纳加极端元,一篇是面积加格线计数——与本页折叠的讲解思路一致。The AoPS Wiki page for the problem, hosting two community solutions. The first (Lopkiloinm) starts from the smallest cases: three points can have all pairwise determinants equal to $\pm1$, but no fourth point can join them; the pattern for $n$ points then yields $2n-3$. The second (SigmaPiE) re-reads the condition geometrically via the shoelace formula: $|a_i b_j - a_j b_i| = 1$ means the triangle formed with the origin has area $\tfrac12$. It builds the two-lattice-line construction reaching 197, then argues case by case that moving points off those lines only loses pairs. The wiki renders formulas as images that drop out in text extraction, but both proof skeletons are legible: one induction plus an extremal argument, the other area and lattice-line counting—matching the walkthrough folded below.

AI 随想An AI's reflection

以下由 AI 撰写。Written by AI.

这道题最迷人的地方,在于它把一个看似组合计数的问题,转化为一个几何直觉问题。条件 $|a_i b_j - a_j b_i| = 1$ 看起来只是一个代数式子,但它的几何意义是:由原点和这两个点张成的平行四边形面积恰好为 1。这意味着这两个点构成的向量是「互质」的——它们之间没有更粗的格点。The most captivating aspect of this problem is how it transforms what appears to be a combinatorial counting problem into a question of geometric intuition. The condition $|a_i b_j - a_j b_i| = 1$ looks like a mere algebraic expression, but its geometric meaning is precise: the parallelogram spanned by the origin and these two points has area exactly 1. This means the two vectors are 'coprime'—no coarser lattice point lies between them.

证明的上界部分用了一个经典的极值论证:取最远的点。这个策略在组合数学中非常常见——当你需要证明某个量有上界时,找一个极端元素,看看它最多能贡献什么。在这里,最远点 $P$ 的几何性质非常强:所有其他点都在以原点为圆心、$|P|$ 为半径的圆盘内。而满足行列式条件的那些点,恰好落在两条相距固定的平行线上。圆盘与直线的交点最多两个,但其中一个必须是原点(被排除),所以每条线最多一个。这个几何约束把代数问题变成了简单的计数问题。The upper bound proof uses a classic extremal argument: take the farthest point. This strategy is ubiquitous in combinatorics—when proving an upper bound, find an extreme element and determine its maximum possible contribution. Here, the farthest point $P$ has strong geometric properties: all other points lie within a disk centered at the origin with radius $|P|$. The points satisfying the determinant condition lie exactly on two parallel lines at fixed distance. A disk intersects a line in at most two points, but one must be the origin (excluded), so each line contributes at most one valid point. This geometric constraint reduces an algebraic problem to simple counting.

构造部分同样优雅:选一条直线上的 99 个点,再加一个不在该直线上的点。这样每条直线上的相邻点对贡献 98 对,那个额外的点与所有 99 个点各贡献 1 对,总共 197 对。这个构造之所以有效,是因为它同时利用了两种不同的「互质关系」——共线点之间的相邻关系,和非共线点与原点之间的面积关系。The construction is equally elegant: pick 99 collinear points on one line, plus one point not on that line. Adjacent pairs on the line contribute 98, and the extra point pairs with all 99 line points for 99 more, totaling 197. This works because it simultaneously exploits two different kinds of 'coprimality'—adjacency along a line, and area-1 relationships with the origin.

这道题提醒我们:好的竞赛题往往有一个「几何灵魂」藏在代数外壳下面。找到那个灵魂,证明就自然浮现了。This problem reminds us that good competition problems often hide a geometric soul beneath an algebraic shell. Find that soul, and the proof emerges naturally.

✓ 已通过 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.35.0-rc3 · Mathlib 3f6737d

程序员随想Programmer Reflections

哲学与生活Philosophy & Life

工具角Tools Corner