每日科技文摘Daily Tech Digest

每日思考文摘 · 2026-10-22Daily Thought Digest · 2026-10-22

发布于 2026-10-22Published 2026-10-22

今日深读Today's Deep Read

只有 1 字节熵的 CA 私钥:eMudhra 的 8 张中间证书,让全世界裸奔了 17 个月Eight Bits of Trust: How Eight CA Private Keys of One Byte Stood Between the World and Forged Certificates for 17 Months

Scott Helme 在 eMudhra 事件里做了一件很克制但很关键的事:他没有去讲『CA 私钥被偷了所以出事』这种熟悉的故事,而是把整起事故的『how』一层层剥开——8 张中间证书的私钥,不是被偷的,是从第一天起就是公开的:每张密钥的有效熵只有 1 个字节(d 等于 4、56、115 之类的小数字),任何看过证书的人,在自己笔记本上花不到 1 秒就能复原。这不是『供应链被黑』,这是『供应链在出厂时就没有锁』。Scott Helme did something restrained but crucial in the eMudhra incident write-up: instead of the familiar 'CA key was stolen, incident happened' story, he peeled the 'how' layer by layer. Eight intermediate CA private keys were not stolen — they were public from day one, because each one held only one byte of actual entropy (d = 4, 56, 115, …). Anyone who ever saw one of those certificates could recover the key in under a second on a laptop. This is not 'the supply chain got hacked.' This is 'the supply chain shipped without locks.'

他把这件事拆成三步。第一步是数学事实:P-384 椭圆曲线的私钥本应是一个 384 位的随机数($2^{384}$ 种可能,搜不过来),而 eMudhra 的 8 张密钥里,每个都是 47 个零字节加一个有内容的字节——最多 255 步就能穷举。这里值得停一秒,把『穷举』到底意味着什么说死:椭圆曲线签名里,公钥是私钥与一个固定基点的乘积($Q = dG$),验签只需要公钥;所以一旦有人把 d 试出来,他拿到的不是一个『理论上的漏洞』,而是一份和 eMudhra 完全一样的签名能力——可以给任何自己挑的域名签发证书,可以给任何软件签名。攻击成本不需要数学突破,只需要一段几十行的脚本加一次循环。第二步是时间事实:这些密钥从 2025 年 4 月起就写在公开证书里,到 2026 年 10 月被披露,中间 17 个月,任何一个看过证书的人都能复原——没有人『偷』,是因为根本不需要偷。第三步是范围事实:Chrome/Firefox/Safari 因为有 Certificate Transparency 强制校验兜住了,但 curl、CI 流水线、IoT 设备、Windows 代码签名这些默认 TLS 客户端既不查 CRL 也不查 CT,对它们来说『吊销』是一个没有效果的操作——吊销信息写在 CRL/OCSP 应答和 CT 日志里,靠客户端主动去查才生效;客户端不查,一张已被吊销的证书和一张正常证书在 TLS 握手里就无法区分。17 个月窗口里任何一次误用都无法被追溯,而受影响设备的证书有效期到 2039 年 7 月。He breaks it into three facts. The math: a P-384 elliptic-curve private key should be a 384-bit random number ($2^{384}$ possibilities — nobody can search that); eMudhra's keys were 47 zero bytes plus one content byte, so a search of at most 255 steps recovers every one. Pause for a second on what 'brute force' actually buys you: in elliptic-curve signatures the public key is the private key times a fixed base point ($Q = dG$), and verification only needs the public key — so whoever recovers d does not get 'a theoretical hole,' they get signing capability identical to eMudhra's own: certificates for any domain they choose, signatures on any software. No mathematical breakthrough is required — a few dozen lines of script and a loop. The time: the keys sat inside public certificates from April 2025 until the October 2026 disclosure — seventeen months in which anyone looking at the certificate could have recovered the key, and nobody 'stole' anything, because no theft was needed. The blast radius: Chrome, Firefox and Safari are protected by enforced Certificate Transparency, but default TLS clients — curl, CI pipelines, IoT devices, Windows code-signing — check neither CRL nor CT, so 'revocation' is a no-op for them — revocation only works because clients agree to look it up in CRL/OCSP responses and CT logs; if the client never asks, a revoked certificate and a valid one are indistinguishable during the TLS handshake. Anything abused in that 17-month window is unrecoverable, and affected device certificates stay valid until July 2039.

Helme 自己在机器上验证:一个伪造的 api.stripe.com 证书,在 curl/Python/Node 的默认设置下都通过了校验(『SSL certificate verify ok』)。这不是假设,是他跑出来的结果。他给出的应对也很具体:能更新的(操作系统 ca-certificates、certifi、Node、Homebrew、容器基镜像)立即更新;不能更新的(路由、打印、电视、家电的冻结固件)在证书 2039 年过期之前,永远信任着这批密钥。Helme verified this on his own machines: a forged api.stripe.com certificate passed validation in curl, Python and Node under default settings ('SSL certificate verify ok'). That is not a hypothetical, it is a measured result. His concrete response: update everything that ships a CA bundle (OS ca-certificates, certifi, Node, Homebrew, container base images); for what cannot be updated (routers, printers, TVs, appliances with frozen firmware), the trust window runs until the 2039 expiry.

真正值得带走的不是『记得打补丁』,而是一个更底层的原则:**信任一个体系时,最小熵决定安全边界,而不是流程**。这套体系里最弱的 1 字节,就替代了所有其他的 383 字节。这和 SRE 里『木桶最短的那块板』、加密里『Kerckhoffs 原理假设攻击者知道你的一切』是一脉相承的:当你说『我们安全』,要问的不是流程上我们做了哪些事,而是整个链条里最容易被绕过的那一处,熵是多少。反过来用,这是一份可执行的检查清单:审计一个系统时,别数自己上了多少层防护,去找最薄的那一层——随机数用的是哪个函数?密钥是不是生成流程里的默认值甚至写死的?哪一步的熵,已经小于攻击者的预算?The deeper takeaway is not 'remember to patch.' It is a principle: **in a trust system, the minimum entropy in the chain defines the security boundary, not the process**. The single weakest byte in the system replaced all the other 383 bytes. This is the same family of insight as 'the shortest stave of the bucket' in SRE and Kerckhoffs's principle in cryptography: when you say 'we are secure', ask not what processes you followed, but where the one point is where the chain's entropy drops, and how little it is. Flipped around, that is an executable checklist: when auditing a system, don't count the layers of defense — find the thinnest one. Which function generated the randomness? Is a key set to some default (or hard-coded) value in the provisioning flow? Which step's entropy is now smaller than an attacker's budget?

AI 思考AI Thoughts

数学之美Mathematics & Its Beauty

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

「总和够大、平方和也够大,必有一个 ≥ 2」(★4)'The Sum Is Big, the Squares Are Big Too, So Some Term Must Be ≥ 2' (★4)

设 $a_1, a_2, \dots, a_n$ 是一组 $n>3$ 的实数,满足:Let $a_1, a_2, \dots, a_n$ be $n>3$ real numbers such that

$$a_1 + a_2 + \cdots + a_n \ge n$$$$a_1 + a_2 + \cdots + a_n \ge n$$

且and

$$a_1^2 + a_2^2 + \cdots + a_n^2 \ge n^2.$$$$a_1^2 + a_2^2 + \cdots + a_n^2 \ge n^2.$$

证明:$\max(a_1, a_2, \dots, a_n) \ge 2$。Prove that $\max(a_1, a_2, \dots, a_n) \ge 2$.

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.Archimedean.Real.Basic
import Mathlib.Algebra.Order.BigOperators.Ring.Finset
import Mathlib.Algebra.Order.Ring.Star

/-!
# USA Mathematical Olympiad 1999, Problem 4

Let a₁, a₂, ..., aₙ be a sequence of n > 3 real numbers such that

  a₁ + a₂ + ⋯ + aₙ ≥ n

and

  a₁² + a₂² + ⋯ + aₙ² ≥ n².

Prove that max(a₁, a₂, ..., aₙ) ≥ 2.
-/

namespace Usa1999P4

theorem usa1999_p4 (n : ℕ) (hn : 3 < n) (a : Fin n → ℝ)
    (hsum : (n : ℝ) ≤ ∑ i, a i) (hsq : (n : ℝ) ^ 2 ≤ ∑ i, (a i) ^ 2) :
    ∃ i, 2 ≤ a i := by
  sorry
end Usa1999P4

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

提示Hint

先做反证:假设所有 $a_i < 2$。把序列分成非负项($P$)和负项($N$)。有一个『平滑化』(smoothing)技巧:如果 $N$ 里有两个负数,把它们合并成一个负数加一个 0——总和不变,但平方和变大——所以最坏情况一定有『恰好一个』负项。把这个负项单独拎出来,剩下的就只是个一元不等式。Try contradiction: suppose all $a_i < 2$. Split the sequence into non-negative terms ($P$) and negative terms ($N$). There is a 'smoothing' trick: if $N$ contains two negatives, merge them into one negative plus a zero — the total sum is unchanged, but the sum of squares increases — so the worst case has exactly one negative term. Pull that one out and the rest is just a one-variable inequality.

答案与讲解Solution & walkthrough
  1. 第一步:做反证,假设所有 $a_i < 2$。Lean 里是 `by_contra! hlt2`,展开后得到一个假设 `hlt2 : ∀ i, a i < 2`(对每个 $i$ 都严格小于 2)。这个 `!` 后缀把目标取反并展开成具体形式,对应数学上『假设目标不成立』。Step 1: work by contradiction, assuming all $a_i < 2$. In Lean this is `by_contra! hlt2`, which unfolds into the hypothesis `hlt2 : ∀ i, a i < 2` (strictly less than 2 for every $i$). The `!` suffix negates the goal and expands it into this concrete form — the math step 'suppose the goal fails.'
  2. 第二步:把 $n$ 个索引分成两组——$P = \{i : 0 \le a_i\}$(非负项)和 $N = \{i : a_i < 0\}$(负项)。Lean 里用 `Finset.univ.filter` 做这件事(`set P := Finset.univ.filter fun i ↦ 0 ≤ a i`),然后有一个 `hpart` 引理:任何序列的总和等于 $P$ 上总和加 $N$ 上总和,这是『分拆求和』的标准操作。Step 2: split the $n$ indices into two sets — $P = \{i : 0 \le a_i\}$ (non-negative terms) and $N = \{i : a_i < 0\}$ (negative terms). In Lean, `Finset.univ.filter` does this (`set P := Finset.univ.filter fun i ↦ 0 ≤ a i`), and a helper lemma `hpart` says that any sum over all indices equals the $P$-part plus the $N$-part — the standard 'sum over a partition' move.
  3. 第三步:分两个情形。情形 A:$N = \emptyset$(所有项非负)。此时每个 $a_i^2 < 4$,所以 $\sum a_i^2 < 4n$;而 $n>3$ 即 $n \ge 4$,意味着 $4n \le n^2$($n=4$ 时取等号),于是 $n^2 \le \sum a_i^2 < 4n \le n^2$,矛盾。Lean 里这是第一个 `by_cases hNe : N = ∅` 分支,`nlinarith` 负责那个二次不等式判断。Step 3: two cases. Case A: $N = \emptyset$ (all terms non-negative). Then each $a_i^2 < 4$, so $\sum a_i^2 < 4n$; and $n>3$ — i.e. $n \ge 4$ — gives $4n \le n^2$ (equality at $n=4$), so $n^2 \le \sum a_i^2 < 4n \le n^2$ — contradiction. In Lean this is the first `by_cases hNe : N = ∅` branch, with `nlinarith` handling the quadratic-inequality check.
  4. 第四步:情形 B:$N$ 非空。令 $S = \sum_{i \in P} a_i$(非负项之和),$M = -\sum_{i \in N} a_i$(负项之和的相反数,$M>0$)。Lean 的 `set S := ...` 和 `set M := ...` 对应这个重命名。从总和一个 $S - M \ge n$;从平方和,非负部分每项 $a_i^2 \le 2a_i$(当 $0 \le a_i < 2$ 时 $a_i^2 < 2a_i$),所以 $\sum_P a_i^2 \le 2S$;负项部分 $\sum_N a_i^2 \le M^2$(把所有负项合成 $-M$ 之后平方就是 $M^2$,这是『平滑化』的 Lean 版——`sum_sq_le_sq_sum_of_nonpos` 引理)。Step 4: Case B: $N$ is non-empty. Let $S = \sum_{i \in P} a_i$ and $M = -\sum_{i \in N} a_i$ (with $M>0$). The Lean `set S := ...` and `set M := ...` lines correspond to these renamings. From the sum hypothesis: $S - M \ge n$. From the squares hypothesis: for non-negative terms, $a_i^2 \le 2a_i$ when $0 \le a_i < 2$ (since $a_i^2 < 2a_i$ strictly), so $\sum_P a_i^2 \le 2S$; for negative terms, $\sum_N a_i^2 \le M^2$ (merging all negatives into one $-M$ and squaring gives $M^2$ — this is the Lean version of 'smoothing', via the helper lemma `sum_sq_le_sq_sum_of_nonpos`).
  5. 第五步:把界串起来:由 $\sum_P a_i^2 \le 2S$ 和 $\sum_N a_i^2 \le M^2$ 得 $n^2 \le 2S + M^2$;又 $M \le S - n$,所以 $n^2 \le 2S + (S-n)^2$。移项,并用 Lean 证明里那条 `ring` 恒等式 $2S + (S-n)^2 - n^2 = S\,(S + 2 - 2n)$,得到 $0 \le S\,(S - 2(n-1))$。因为 $S > 0$($S \ge n + M > n > 0$),只能 $S \ge 2(n-1)$。另一边:$P$ 非空且每项严格小于 2,所以 $S < 2\cdot\#P$;而 $N$ 非空给出 $\#P \le n-1$,于是 $S < 2(n-1)$。两头一夹,矛盾。Lean 的最后几行(`hSge`、`hSlt`、`hcard`、`hfin`)对应的正是这条链。Step 5: chain the bounds: $\sum_P a_i^2 \le 2S$ and $\sum_N a_i^2 \le M^2$ give $n^2 \le 2S + M^2$; with $M \le S - n$ this becomes $n^2 \le 2S + (S-n)^2$. Rearranging via the ring identity the Lean proof uses, $2S + (S-n)^2 - n^2 = S(S + 2 - 2n)$, we get $0 \le S(S - 2(n-1))$. Since $S > 0$ (indeed $S \ge n + M > n$), this forces $S \ge 2(n-1)$. On the other hand, $P$ is non-empty and every term in it is strictly below 2, so $S < 2\cdot\#P$; and since $N$ is non-empty, $\#P \le n-1$, hence $S < 2(n-1)$. The two bounds squeeze each other — the last four Lean lines (`hSge`, `hSlt`, `hcard`, `hfin`) walk exactly this chain.
  6. 整条证明的核心是:平方和对『不均匀』很敏感——把所有项都压在 $<2$ 之下,平方和的上界被『均匀分布时最大』($M$ 集中在一个变量上时 $M^2$ 最大),而均匀分布恰恰意味着 $S$ 很大,$S$ 很大又意味着总和超出 $n$,矛盾。这是竞赛数学里典型的『集中 vs 均匀』权衡,Lean 的 `nlinarith` 把每个局部不等式都自动处理,人负责的是判断『哪些局部步骤该连起来』。The heart of the proof: the sum of squares is sensitive to 'unevenness.' Squeezing every term below 2 puts the worst-case square-sum where $M$ is concentrated in one variable ($M^2$ is largest when $M$ is concentrated), which is exactly the case where $S$ gets large, and a large $S$ means the total sum exceeds $n$ — contradiction. This is the classic 'concentration vs. uniformity' trade-off from olympiad mathematics; Lean's `nlinarith` handles each local inequality automatically, and the human's job is deciding which local steps to chain together.
/-
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.Archimedean.Real.Basic
import Mathlib.Algebra.Order.BigOperators.Ring.Finset
import Mathlib.Algebra.Order.Ring.Star

/-!
# USA Mathematical Olympiad 1999, Problem 4

Let a₁, a₂, ..., aₙ be a sequence of n > 3 real numbers such that

  a₁ + a₂ + ⋯ + aₙ ≥ n

and

  a₁² + a₂² + ⋯ + aₙ² ≥ n².

Prove that max(a₁, a₂, ..., aₙ) ≥ 2.
-/

namespace Usa1999P4

/-!
We follow the proof from Evan Chen's
[USAMO 1999 Solution Notes](https://web.evanchen.cc/exams/USAMO-1999-notes.pdf),
reformulated so that no iterative "smoothing" is needed.

Assume `aᵢ < 2` for all `i`. If every `aᵢ` is nonnegative, then
`∑ aᵢ² < 4n ≤ n²`, a contradiction. Otherwise, writing `S` for the sum of the
nonnegative entries and `-M` for the sum of the negative entries, one checks
`∑ aᵢ² ≤ 2S + M²` and `M ≤ S - n`, hence `n² ≤ 2S + (S - n)²`, which forces
`S ≥ 2n - 2`. But `S < 2·#P ≤ 2(n - 1)`, contradiction.
-/

/-- If every value of `f` on `s` is nonpositive, then the sum of the squares is
at most the square of the sum: the cross terms are nonnegative. -/
theorem sum_sq_le_sq_sum_of_nonpos {ι : Type*} (s : Finset ι) (f : ι → ℝ)
    (hf : ∀ i ∈ s, f i ≤ 0) :
    ∑ i ∈ s, f i ^ 2 ≤ (∑ i ∈ s, f i) ^ 2 := by
  have h1 : ∑ i ∈ s, f i ^ 2 = ∑ i ∈ s, (-f i) ^ 2 :=
    Finset.sum_congr rfl fun i _ ↦ by rw [neg_sq]
  have h2 : (∑ i ∈ s, f i) ^ 2 = (∑ i ∈ s, -f i) ^ 2 := by
    rw [Finset.sum_neg_distrib, neg_sq]
  rw [h1, h2]
  exact Finset.sum_sq_le_sq_sum_of_nonneg fun i hi ↦ neg_nonneg.mpr (hf i hi)

theorem usa1999_p4 (n : ℕ) (hn : 3 < n) (a : Fin n → ℝ)
    (hsum : (n : ℝ) ≤ ∑ i, a i) (hsq : (n : ℝ) ^ 2 ≤ ∑ i, (a i) ^ 2) :
    ∃ i, 2 ≤ a i := by
  by_contra! hlt2
  -- `P` = indices of the nonnegative entries, `N` = indices of the negative ones.
  set P := Finset.univ.filter fun i ↦ 0 ≤ a i with hP
  set N := Finset.univ.filter fun i ↦ ¬ 0 ≤ a i with hN
  have hpart : ∀ f : Fin n → ℝ, ∑ i, f i = ∑ i ∈ P, f i + ∑ i ∈ N, f i :=
    fun f ↦ (Finset.sum_filter_add_sum_filter_not Finset.univ _ f).symm
  by_cases hNe : N = ∅
  · -- Every entry is nonnegative, so `aᵢ² < 4` for all `i` and `∑ aᵢ² < 4n ≤ n²`.
    have hnonneg : ∀ i, 0 ≤ a i := by
      intro i
      by_contra hi
      have him : i ∈ N := Finset.mem_filter.mpr ⟨Finset.mem_univ i, hi⟩
      rw [hNe] at him
      exact Finset.notMem_empty i him
    have hsum4 : ∑ i, (a i) ^ 2 < 4 * n := by
      have hlt : ∑ i, (a i) ^ 2 < ∑ _i : Fin n, (4 : ℝ) := by
        apply Finset.sum_lt_sum_of_nonempty
        · have : Nonempty (Fin n) := ⟨⟨0, by lia⟩⟩
          exact Finset.univ_nonempty
        · intro i _
          have h1 := hnonneg i
          have h2 := hlt2 i
          nlinarith [mul_nonneg h1 (sub_nonneg_of_le h2.le : (0 : ℝ) ≤ 2 - a i)]
      rw [Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul] at hlt
      linarith [hlt]
    have hn4 : (4 : ℝ) * n ≤ (n : ℝ) ^ 2 := by
      have h1 : (4 : ℝ) ≤ n := by exact_mod_cast hn
      have h2 : (0 : ℝ) ≤ n := by positivity
      calc (4 : ℝ) * n ≤ n * n := mul_le_mul_of_nonneg_right h1 h2
        _ = (n : ℝ) ^ 2 := by ring
    linarith
  · -- Some entry is negative.
    have hNne : N.Nonempty := Finset.nonempty_iff_ne_empty.mpr hNe
    set S := ∑ i ∈ P, a i with hSdef
    set M := -∑ i ∈ N, a i with hMdef
    have hMpos : 0 < M := by
      have hneg : ∑ i ∈ N, a i < 0 := by
        have hlt : ∑ i ∈ N, a i < ∑ _i ∈ N, (0 : ℝ) :=
          Finset.sum_lt_sum_of_nonempty hNne fun i hi ↦
            not_le.mp (Finset.mem_filter.mp hi).2
        rwa [Finset.sum_const_zero] at hlt
      rw [hMdef]
      exact neg_pos.mpr hneg
    have hSM : (n : ℝ) ≤ S - M := by
      have hp := hpart a
      rw [hSdef, hMdef]
      linarith [hsum, hp]
    have hSpos : 0 < S := by
      have hnpos : (0 : ℝ) < n := by exact_mod_cast (show 0 < n by lia)
      linarith [hSM, hMpos, hnpos]
    -- Bound the two parts of `∑ aᵢ²`: on `P` use `aᵢ² ≤ 2aᵢ`, on `N` the
    -- cross terms of `M²` are nonnegative.
    have hPsq : ∑ i ∈ P, (a i) ^ 2 ≤ 2 * S := by
      rw [hSdef, Finset.mul_sum]
      refine Finset.sum_le_sum fun i hi ↦ ?_
      have h1 : 0 ≤ a i := (Finset.mem_filter.mp hi).2
      have h2 : a i < 2 := hlt2 i
      nlinarith [mul_nonneg h1 (sub_nonneg_of_le h2.le : (0 : ℝ) ≤ 2 - a i)]
    have hNsq : ∑ i ∈ N, (a i) ^ 2 ≤ M ^ 2 := by
      rw [hMdef, neg_sq]
      exact sum_sq_le_sq_sum_of_nonpos N a fun i hi ↦
        le_of_lt (not_le.mp (Finset.mem_filter.mp hi).2)
    -- Combine: `n² ≤ 2S + (S - n)²`, hence `S ≥ 2n - 2`.
    have hMle : M ≤ S - n := by linarith [hSM]
    have hMsq : M ^ 2 ≤ (S - n) ^ 2 := pow_le_pow_left₀ hMpos.le hMle 2
    have hcomb : (n : ℝ) ^ 2 ≤ 2 * S + (S - n) ^ 2 :=
      calc (n : ℝ) ^ 2 ≤ ∑ i, (a i) ^ 2 := hsq
        _ = ∑ i ∈ P, (a i) ^ 2 + ∑ i ∈ N, (a i) ^ 2 := hpart _
        _ ≤ 2 * S + M ^ 2 := add_le_add hPsq hNsq
        _ ≤ 2 * S + (S - n) ^ 2 := by linarith [hMsq]
    have hSge : 2 * n - 2 ≤ S := by
      have hstep : 0 ≤ S * (S + 2 - 2 * n) := by
        have h2 : S * (S + 2 - 2 * n) = 2 * S + (S - n) ^ 2 - n ^ 2 := by ring
        rw [h2]
        linarith [hcomb]
      have hX : 0 ≤ S + 2 - 2 * n := nonneg_of_mul_nonneg_right hstep hSpos
      linarith
    -- But `S < 2·#P ≤ 2(n - 1)`, contradiction.
    have hPne : P.Nonempty := by
      by_contra hcon
      rw [Finset.not_nonempty_iff_eq_empty] at hcon
      have hS0 : S = 0 := by rw [hSdef, hcon, Finset.sum_empty]
      linarith [hSpos, hS0]
    have hSlt : S < 2 * P.card := by
      obtain ⟨j, hj⟩ := hPne
      have hlt : ∑ i ∈ P, a i < ∑ _i ∈ P, (2 : ℝ) :=
        Finset.sum_lt_sum (fun i _ ↦ le_of_lt (hlt2 i)) ⟨j, hj, hlt2 j⟩
      rw [Finset.sum_const, nsmul_eq_mul] at hlt
      rw [hSdef]
      linarith [hlt]
    have hcard : (P.card : ℝ) + 1 ≤ n := by
      have h1 : P.card + N.card = n := by
        have h2 := Finset.card_filter_add_card_filter_not (s := Finset.univ)
          (p := fun i ↦ 0 ≤ a i)
        rwa [Finset.card_univ, Fintype.card_fin] at h2
      have h2 : 1 ≤ N.card := Finset.card_pos.mpr hNne
      have h3 : P.card + 1 ≤ n := by lia
      exact_mod_cast h3
    have hfin : 2 * (P.card : ℝ) ≤ 2 * n - 2 := by linarith [hcard]
    linarith [hSge, hSlt, hfin]

end Usa1999P4

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

人的思考A human's take

Evan Chen — USAMO 1999 Solution Notes(Problem 4) — Evan Chen(陳誼廷)

Evan Chen 的解法比 Lean 形式化里的还简洁一步:他直接用『smoothing』(平滑化)说——如果 $N$ 里有两个负数 $-x$ 和 $-y$($x,y>0$),把它们换成 $-(x+y)$ 和 $0$:总和不变,但平方和增大($(-x)^2+(-y)^2 < (-(x+y))^2$)。所以『最坏情况』(平方和最大的情况)一定恰好只有一个负项,可以假设 $a_n = -M$。Evan Chen's solution is one step more direct than the Lean formalization: he invokes 'smoothing' outright — if $N$ contains two negatives $-x$ and $-y$ ($x,y>0$), replace them with $-(x+y)$ and $0$: the total sum is unchanged, but the sum of squares increases ($(-x)^2+(-y)^2 < (-(x+y))^2$). So the 'worst case' (largest square-sum) has exactly one negative term, and one may assume $a_n = -M$.

接着 Chen 说把非负项都『平滑』到 2:得到两个不等式 $2(n-1) - M > n$ 和 $4(n-1) + M^2 > n^2$。前者给出 $M < n-2$(注意方向:这是严格不等式,$2(n-1) - M > n$ 推出 $M < 2n-2-n = n-2$);后者 $M^2 > n^2 - 4(n-1) = n^2 - 4n + 4 = (n-2)^2$ 推出 $M > n-2$。两行合起来 $M < n-2$ 和 $M > n-2$,矛盾。Chen then 'smooths' all the non-negative terms up to 2, yielding two inequalities: $2(n-1) - M > n$ and $4(n-1) + M^2 > n^2$. The first gives $M < n-2$; the second, $M^2 > n^2 - 4(n-1) = (n-2)^2$, gives $M > n-2$. Together, $M < n-2$ and $M > n-2$ — contradiction.

Chen 还给出了原题的等号情形:$n-1$ 个 $a_i$ 等于 2、最后一个等于 $-(n-2)$——此时总和恰好是 $n$、平方和恰好是 $n^2$、最大项恰好是 2。这说明结论里的『2』是紧的:常数一步都不能再往上调,这正是它作为竞赛题的漂亮之处。Chen also gives the equality case of the original problem: $n-1$ of the $a_i$ equal 2 and the last equals $-(n-2)$ — then the sum is exactly $n$, the square-sum exactly $n^2$, and the maximum exactly 2. So the constant 2 in the conclusion is tight: it cannot be pushed even slightly higher, which is what makes this such an elegant olympiad problem.

AI 随想An AI's reflection

以下由 AI 撰写。Written by AI.

这道题(USAMO 1999 P4)表面上是一道『证明某个变量 ≥ 某常数』的不等式,但真正的洞见藏在那个『平滑化』操作里:把两个负数合并成一个负数加一个 0,总和不变、平方和增大——这意味着『让平方和最坏』这件事,会把配置推向一个『尽可能集中』的形状。这是很多竞赛不等式题共享的底层直觉:当约束是『总和固定、求平方和最大』这类形式时,最坏情况总在『尽可能不均匀』的那端,而不是『均匀分布』那一端。USAMO 1999 P4 looks, on the surface, like a standard 'prove some variable is at least a constant' inequality. The real insight hides in that 'smoothing' move: merge two negatives into one negative plus a zero — total unchanged, sum of squares increased. This says that 'making the square-sum worst' pushes the configuration toward a 'maximally concentrated' shape. This is a low-level intuition shared by many olympiad inequality problems: when the constraint is 'sum fixed, maximize the sum of squares' (or its variants), the worst case sits at the 'as uneven as possible' end, not the 'evenly spread out' end.

把这条直觉套到 AI/数学工具上:这题之所以值得在 Lean 里做一遍(而不是纸面上已经解出),是因为 Lean 强迫你把这个『平滑化』拆成一个明确的引理(`sum_sq_le_sq_sum_of_nonpos`),而不是一句『这是显然的』滑过去。竞赛数学里『显然』两个字是危险词——它通常意味着『这里藏着一行没写的引理』。形式化之后,那个『显然』变成了引理名,可以单独复用(比如套到任何『非负项上求平方和上界』的场合)。Applying that intuition to AI/math tooling: this problem is worth doing in Lean (rather than having it already solved on paper) because Lean forces you to break the 'smoothing' into an explicit lemma (`sum_sq_le_sq_sum_of_nonpos`), instead of sliding past it with 'this is obvious.' In olympiad math, the word 'obvious' is a danger word — it usually means 'there is a lemma hiding that was not written down.' After formalization, that 'obvious' becomes a named lemma, reusable in any situation of the form 'bound the sum of squares over non-negative terms.'

还有一个容易忽略的点:$n>3$ 这个下界卡在哪里。卡在情形 A:所有项非负时,证明用的是 $\sum a_i^2 < 4n$,而要把 $4n$ 压进 $n^2$ 之内需要 $n \ge 4$。$n=3$ 时这一步崩了,而且确实有反例:$a_1 = a_2 = a_3 = \sqrt{3}$——总和 $3\sqrt{3} \approx 5.2 \ge 3$,平方和恰好 $9 = n^2$,最大项 $\sqrt{3} < 2$。$n=2$ 同样失败:$a_1 = a_2 = 1.9$,总和 $3.8 \ge 2$,平方和 $7.22 \ge 4$,最大项仍然小于 2。『为什么恰好是 $n>3$』这个问题,是对你理解深度的反查:能亲手构造出 $n=3$ 的反例,才说明你真知道那个不等式在证明里顶用的是哪一下。One easily-missed point: where the bound $n>3$ bites. It bites in Case A: when all terms are non-negative, the proof uses $\sum a_i^2 < 4n$, and pushing $4n$ below $n^2$ requires $n \ge 4$. At $n=3$ that step collapses — and there really is a counterexample: $a_1 = a_2 = a_3 = \sqrt{3}$, with sum $3\sqrt{3} \approx 5.2 \ge 3$, squares exactly $9 = n^2$, and maximum $\sqrt{3} < 2$. $n=2$ fails too: $a_1 = a_2 = 1.9$ gives sum $3.8 \ge 2$, squares $7.22 \ge 4$, maximum still below 2. Asking 'why exactly $n>3$?' is a reverse-check on your understanding: constructing the $n=3$ counterexample with your own hands means you know precisely which move the inequality is load-bearing for.

✓ 已通过 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 · Mathlib 56a0058

程序员随想A Programmer's Reflections

哲学与生活Philosophy & Life

工具角Tools Corner