每日科技文摘Daily Tech Digest

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

发布于 2026-10-29Published 2026-10-29

今日深读Today's Deep Read

『这不可持续』:当 0-day 如雨点般落下,patch 管理的战线已经输了'This Is Not Sustainable': When 0-Days Fall Like Rain, the Patch-Management Front Is Already Lost

2026 年 10 月 27 日,J.S. Schauma——网名 jschauma,netmeister.org 的作者、干了多年系统管理的老运维(他的副标题是『Opinions, mostly my own』)——发了一篇题为『This is not sustainable』的文章。他的靶子不是哪个具体的 CVE,而是整条『发现漏洞 → 写补丁 → 部署补丁』的流水线:作为一个吞吐系统,这条线已经输了。On October 27, 2026, J.S. Schauma (online handle jschauma, author of netmeister.org, a veteran sysadmin who has watched systems and security for decades) published an essay titled 'This is not sustainable'. His target is not any specific CVE — it's the entire 'find vulnerability → write patch → deploy patch' pipeline, treated as a throughput system. That line, he argues, has already lost.

起因带着黑色幽默:十月是『网络安全宣传月』,纽约时报和 NPR 本周都报道了他同时在灭的那几把火——他反讽:公众意识提上来了,KPI 达成了,『那么,能把音量调小一点吗?』玩笑背后是事实:0-day 如雨点般落下,预先通报的 embargo 为营销目的被反复打破;AI 公司一边比谁『发现』的漏洞多,一边把对开源基础设施的 DoS 攻击包装成『安全产品』卖回去——『不错的项目,要是被谁投一个 0-day 就可惜了』。漏洞发现的产能已经变了,披露流程事实上坏了,而 patch 管理『多年来一直是输的买卖』:严重漏洞被识别和披露的速度,防御者根本消化不动。The occasion carries some dark irony: October is Cybersecurity Awareness Month, and this very week both the New York Times and NPR reported on the four or five fires he was fighting at once. So his quip goes: awareness has been raised, the KPI is met — 'so... could we maybe turn it down a bit?' Behind the joke are facts: 0-days dropping left and right, disclosure embargoes broken for marketing purposes, and AI companies competing on who can 'discover' the most vulnerabilities — then selling protection against their own DoS attacks on open-source infrastructure back to the ecosystem. 'Nice project you got there. Be a shame if somebody dropped an 0-day on it.' The pace at which severe vulnerabilities are identified and disclosed now exceeds what defenders can digest; patch management has been a losing proposition for years.

他的核心论点:瓶颈不在补丁——上游修复早就有了。真正卡死人的是补丁下游的两段。一段是评估:这个漏洞在我这套栈里到底打不打得中,攻击面有多大;另一段是部署:修复怎么在多快之内推到每一台该推的机器。拿 PwnEscape(CVE-2026-99999)举例:最初按『KVM 逃逸』披露,实际还波及别的虚拟化栈和容器。你得逐台评估机队里有哪些可能的缓解,选 livepatch 还是等发行版新内核,然后——重启几千台机器。『AI 在这里怎么帮你?你或许花几千美元 token、用最先进的安全模型自研一个 exploit,但最后它告诉不了任何你本来不知道的事,你手上的防御任务一项都没少。』His core argument: the fix is not the bottleneck. Upstream patches exist long before you can act. What kills you is downstream of the patch, in two segments: assessment (can this vulnerability actually be reached inside my environment? how big is my attack surface?) and deployment (how fast can the fix reach every host that needs it). Take PwnEscape (CVE-2026-99999): disclosed as a 'KVM escape', it in fact also affects other virtualization stacks and containers. You must assess which mitigations might be in place across your fleet, decide between livepatching kernels or waiting for OS vendors, and then — reboot a few thousand machines. 'How does AI help you here? Maybe you spend a few thousand dollars on tokens to build your own exploit with the most advanced cyber models — in the end it tells you nothing you didn't already know, and the defensive work remains exactly the same.'

同一周他点了三个更具体的火:eMudhra 证书事件——浏览器补得快,但别忘了你环境里还有什么用 TLS:答案是『几乎一切』,而你引以为傲的 SBOM 多半没列出那些 vendored 或硬编码的 CA 信任包。『php2shell』——『影响超过 70% 的网站』这句被到处引用的话从头到尾没人知道出处;拿到 embargo 预通知的内部圈正好用来排摸和缓解,可 embargo 一破,大家接着手忙脚乱,还得吞下一堆安全厂商抢『第一个发现、第一个利用』的营销稿——其中不少是 AI 生成、作者对 bug 理解不全的赶工货。brotli RCE(CVE-2026-111497)最荒诞:Node.js 公告触发又一轮盘点,细看才发现波及面远超 Node;这时 OpenAI 出认领功——『是我们发现的!』——可 Mozilla 二月就修了,四月就标注了关键安全影响。In the same week he names three more fires. The eMudhra compromise: browsers were fixed quickly, but remember what else in your environment uses TLS — the answer is 'nearly everything', and your supposedly detailed SBOM almost certainly doesn't list the vendored or hard-coded CA trust bundles. 'php2shell': the phrase 'affects over 70% of websites' is quoted everywhere but never attributed; the few organizations inside the embargo could use the time to inventory and mitigate, then the embargo breaks and everyone scrambles again — while swallowing a flood of security-vendor marketing posts rushing to claim 'first to detect, first to exploit', many AI-generated by people lacking a full understanding of the bug. The brotli RCE (CVE-2026-111497) is the most absurd: a Node.js advisory triggered yet another inventory sweep, until it dawned on people the issue goes far beyond Node — at which point OpenAI showed up to take credit ('Us! It was us! We found it!'), even though Mozilla had fixed it in February and flagged the critical impact in April.

他更担心的是防御侧的去技能化:AI 生成的漏洞报告冗长到人读不完,防御者自己没全懂,又倾向于相信普遍被夸大的严重程度,于是把整份报告喂回 AI 去『复现』PoC——几千 token 之后,你拿到一个『经肉代理转交』的二进制,没人明白它为什么有效,而且它常常根本跑不起来。你想要一页纸讲清楚运行前提和原理—— offensive 工程师当年的基本功——拿回来的是 7000 字的 AI 呕吐物 README。而每家公司的『什么都知道』的那一小撮老人,被同一时间点的几场事故来回拽:上下文切换让人无法深挖任何一件,压力下 rushed 出的修复,很可能对着一个环境里根本打不中的漏洞——这又让更多非专家把 bot 的答案直接贴进事故频道。What worries him more is the de-skilling of the defensive side. AI-generated vulnerability reports are far too verbose for a human to digest; defenders who don't fully understand the bug tend to believe the generally exaggerated severity claims, and feed the whole report back into an AI to 'reproduce' the PoC. A few thousand tokens later you hold a binary handed to you through a meat-proxy, and nobody understands why it works — which, more often than not, it doesn't, because your environment or code base differs from upstream. Ask for clear instructions, preconditions, a one-pager on how it works — basic tradecraft for offensive engineers — and you get a 7,000-word AI-vomited README.md. Meanwhile every company fights its fires with the same handful of elders who hold the tribal knowledge: pulled between simultaneous incidents, context-switching prevents deep focus, pressure produces rushed fixes for vulnerabilities that may not even apply in your environment — which in turn makes more non-experts paste bot answers straight into the incident channel.

罕见的是,他明确拒绝给一个光明的尾巴:『事情会怎么变好?哦,抱歉,我误导了你—— rant 文章结尾该给方案的。唉,我没有 idea。』他也不信『AI 把所有漏洞都找完,我们就迎来干净代码库』:要能信那个,『我挺羡慕你』。攻击侧已经在把 Linux 内核的 commit 记录喂给模型找可利用点,防御侧还在一条一条人工判断——这个不对称才是『不可持续』的真实含义。能带走的一点:安全团队真正稀缺的资产不再是补丁队列,而是『攻击面知识』——那个能自动回答『这条 CVE 在我这套栈打不打得中』的能力。Unusually, he refuses the upbeat ending: 'How does it get better? Oh, lol, sorry, I misled you. A rant is supposed to end with solutions. Alas, I have no idea.' He also doesn't buy 'AI will find all the vulns and then we're clean' — 'if you're able to believe that, I envy you.' The adversaries are already feeding Linux kernel commit messages into models to find exploitable commits, while defenders still assess case by case, by hand. That asymmetry is what 'not sustainable' actually means. The takeaway you can carry: the scarce asset for a security team is no longer the patch queue, but attack-surface knowledge — the ability to automatically answer 'can this CVE actually hit my stack'.

AI 思考AI Thoughts

数学之美Beauty of Mathematics

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

每日一题:一条『0,1,0』序列,对应两条『0,0,1,1/1,1,0,0』序列Today's Puzzle: One '0,1,0' Sequence Corresponds to Exactly Two '0,0,1,1/1,1,0,0' Sequences

一个 $n$ 项的二进制序列(每项为 0 或 1)中,称 $a_n$ 为『不含 $0,1,0$ 三项连续』的序列个数;$b_n$ 为『不含 $0,0,1,1$ 或 $1,1,0,0$ 四项连续』的序列个数。Let $a_n$ count binary sequences of length $n$ with no three consecutive terms $0,1,0$ in that order, and let $b_n$ count those with no four consecutive terms $0,0,1,1$ or $1,1,0,0$. Prove $b_{n+1} = 2 a_n$ for all positive integers $n$.

对所有正整数 $n$,证明 $b_{n+1} = 2 a_n$。对所有正整数 $n$,证明 $b_{n+1} = 2 a_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.AlgebraicTopology.SimplexCategory.Basic

/-!
# USA Mathematical Olympiad 1996, Problem 4

An n-term sequence (x₁, x₂, …, xₙ) in which each term is either 0 or 1 is called a
binary sequence of length n. Let aₙ be the number of binary sequences of length n
containing no three consecutive terms equal to 0, 1, 0 in that order. Let bₙ be the
number of binary sequences of length n that contain no four consecutive terms equal
to 0, 0, 1, 1 or 1, 1, 0, 0 in that order. Prove that bₙ₊₁ = 2aₙ for all positive
integers n.
-/

namespace Usa1996P4

/-- The `i`-th term of a binary sequence `x : Fin n → Bool`, or `false` if `i`
is out of range. -/
def sget {n : ℕ} (x : Fin n → Bool) (i : ℕ) : Bool :=
  if h : i < n then x ⟨i, h⟩ else false

/-- A binary sequence of length `n` (encoded as `x : Fin n → Bool`, with `false`
standing for `0` and `true` for `1`) is `A`-good if it contains no three consecutive
terms equal to `0, 1, 0` in that order. -/
abbrev GoodA {n : ℕ} (x : Fin n → Bool) : Prop :=
  ∀ i : Fin n, (i : ℕ) + 2 < n →
    ¬(sget x (i : ℕ) = false ∧ sget x ((i : ℕ) + 1) = true ∧ sget x ((i : ℕ) + 2) = false)

/-- A binary sequence of length `n` is `B`-good if it contains no four consecutive
terms equal to `0, 0, 1, 1` or `1, 1, 0, 0` in that order. -/
abbrev GoodB {n : ℕ} (y : Fin n → Bool) : Prop :=
  ∀ i : Fin n, (i : ℕ) + 3 < n →
    ¬((sget y (i : ℕ) = false ∧ sget y ((i : ℕ) + 1) = false ∧ sget y ((i : ℕ) + 2) = true ∧
        sget y ((i : ℕ) + 3) = true) ∨
      (sget y (i : ℕ) = true ∧ sget y ((i : ℕ) + 1) = true ∧ sget y ((i : ℕ) + 2) = false ∧
        sget y ((i : ℕ) + 3) = false))

theorem usa1996_p4 (n : ℕ) :
    Fintype.card {y : Fin (n + 1) → Bool // GoodB y} =
      2 * Fintype.card {x : Fin n → Bool // GoodA x} := by
  sorry
end Usa1996P4

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

提示Hint

把一个 $n+1$ 位的二进制序列 $y$ 变成 $n$ 位的『相邻位异或』序列 $x$($x_i = y_i \oplus y_{i+1}$)。Map a $(n+1)$-bit sequence $y$ to its $n$-bit XOR-difference sequence $x$ (where $x_i = y_i \oplus y_{i+1}$).

$y$ 在位置 $i$ 出现 $0,0,1,1$ 或 $1,1,0,0$,当且仅当 $x$ 在位置 $i$ 出现 $0,1,0$。$y$ has a block $0,0,1,1$ or $1,1,0,0$ at position $i$ if and only if $x$ has a block $0,1,0$ at position $i$.

给定 $x$ 和 $y$ 的首项(2 种选择),整个 $y$ 被唯一确定——这就是那个 $2\times$ 的来源。Given $x$ and the first bit of $y$ (two choices), the whole $y$ is uniquely determined — that's where the factor 2 comes from.

答案与讲解Solution & walkthrough
  1. 第 1 步(把问题读成『序列到序列』的映射):定义 $x = \text{diff}(y)$,其中 $x_i = y_i \oplus y_{i+1}$。$y$ 有 $n+1$ 位,所以 $x$ 有 $n$ 位。这条对应关系是双向的——给定 $x$ 和 $y_0$(首个位,2 种选择),$y$ 完全确定。Step 1 (read the problem as a map between sequences): define $x = \text{diff}(y)$ where $x_i = y_i \oplus y_{i+1}$. $y$ has $n+1$ bits, so $x$ has $n$. This is invertible: given $x$ and the first bit $y_0$ (two choices), $y$ is determined.
  2. 第 2 步(核心引理:图案转移):$y$ 在 $i$ 处出现 $0,0,1,1$ 或 $1,1,0,0$,当且仅当 $x$ 在 $i$ 处出现 $0,1,0$。验证:$0,0,1,1$ 的异或差是 $0,1,0$;$1,1,0,0$ 的异或差也是 $0,1,0$。这是整个证明的灵魂。Step 2 (the key lemma: pattern transfer): $y$ has a block $0,0,1,1$ or $1,1,0,0$ at position $i$ iff $x$ has a block $0,1,0$ at position $i$. Check: the XOR-differences of $0,0,1,1$ are $0,1,0$; the XOR-differences of $1,1,0,0$ are also $0,1,0$. This is the soul of the proof.
  3. 第 3 步(双向封住):(a) 若 $x$ 是 $A$-good(无 $0,1,0$),则 $\text{build}(x, y_0)$ 是 $B$-good(无 $0,0,1,1$ 也无 $1,1,0,0$);(b) 反过来,若 $y$ 是 $B$-good,则 $\text{diff}(y)$ 是 $A$-good。两步合起来:「$y$ 是 $B$-good」⟺「$\text{diff}(y)$ 是 $A$-good」。Step 3 (close both directions): (a) if $x$ is A-good (no $0,1,0$), then $\text{build}(x, y_0)$ is B-good; (b) conversely if $y$ is B-good, then $\text{diff}(y)$ is A-good. Together: '$y$ is B-good' iff '$\text{diff}(y)$ is A-good'.
  4. 第 4 步(建立双射):集合 $\{(y, c) : c \in \{0,1\}\}$ 到 $\{x : A\text{-good}\} \times \{0,1\}$ 的双射由 $\text{build}$ 和 $\text{diff}$ 给出,且 $\text{diff}(\text{build}(x, c)) = x$ 和 $\text{build}(\text{diff}(y), y_0) = y$(Lean 里的 `seqEquiv` 对象)。Step 4 (build the bijection): the pairing $(x, c) \leftrightarrow y$ via $\text{build}$ and $\text{diff}$ gives $\{y : B\text{-good}\} \cong \{x : A\text{-good}\} \times \{0,1\}$ (the `seqEquiv` object in the Lean proof).
  5. 第 5 步(把双射变成计数等式):$b_{n+1} = |\{y : B\text{-good}\}| = |\{(x, c) : x\ A\text{-good}\}| = 2 \cdot |\{x : A\text{-good}\}| = 2 a_n$。Lean 里的最后几行是 `Fintype.card_congr` + `Fintype.card_prod` + `Fintype.card_bool`,直接对应笛卡尔积中 $\{0,1\}$ 的两个元素。Step 5 (count the bijection): $b_{n+1} = |\{y : B\text{-good}\}| = |\{x : A\text{-good}\} \times \{0,1\}| = 2 a_n$. The final lines in Lean are `Fintype.card_congr` + `Fintype.card_prod` + `Fintype.card_bool` — the factor 2 is literally the two elements of $\{0,1\}$.
/-
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.AlgebraicTopology.SimplexCategory.Basic

/-!
# USA Mathematical Olympiad 1996, Problem 4

An n-term sequence (x₁, x₂, …, xₙ) in which each term is either 0 or 1 is called a
binary sequence of length n. Let aₙ be the number of binary sequences of length n
containing no three consecutive terms equal to 0, 1, 0 in that order. Let bₙ be the
number of binary sequences of length n that contain no four consecutive terms equal
to 0, 0, 1, 1 or 1, 1, 0, 0 in that order. Prove that bₙ₊₁ = 2aₙ for all positive
integers n.
-/

namespace Usa1996P4

/-- The `i`-th term of a binary sequence `x : Fin n → Bool`, or `false` if `i`
is out of range. -/
def sget {n : ℕ} (x : Fin n → Bool) (i : ℕ) : Bool :=
  if h : i < n then x ⟨i, h⟩ else false

/-- A binary sequence of length `n` (encoded as `x : Fin n → Bool`, with `false`
standing for `0` and `true` for `1`) is `A`-good if it contains no three consecutive
terms equal to `0, 1, 0` in that order. -/
abbrev GoodA {n : ℕ} (x : Fin n → Bool) : Prop :=
  ∀ i : Fin n, (i : ℕ) + 2 < n →
    ¬(sget x (i : ℕ) = false ∧ sget x ((i : ℕ) + 1) = true ∧ sget x ((i : ℕ) + 2) = false)

/-- A binary sequence of length `n` is `B`-good if it contains no four consecutive
terms equal to `0, 0, 1, 1` or `1, 1, 0, 0` in that order. -/
abbrev GoodB {n : ℕ} (y : Fin n → Bool) : Prop :=
  ∀ i : Fin n, (i : ℕ) + 3 < n →
    ¬((sget y (i : ℕ) = false ∧ sget y ((i : ℕ) + 1) = false ∧ sget y ((i : ℕ) + 2) = true ∧
        sget y ((i : ℕ) + 3) = true) ∨
      (sget y (i : ℕ) = true ∧ sget y ((i : ℕ) + 1) = true ∧ sget y ((i : ℕ) + 2) = false ∧
        sget y ((i : ℕ) + 3) = false))

theorem sget_lt {n : ℕ} (x : Fin n → Bool) {i : ℕ} (h : i < n) :
    sget x i = x ⟨i, h⟩ :=
  dite_eq_left h

/-- The sequence of successive differences (XORs) of `y`. -/
def diff {n : ℕ} (y : Fin (n + 1) → Bool) : Fin n → Bool :=
  fun i ↦ xor (sget y i.val) (sget y (i.val + 1))

/-- Auxiliary for `build`: the `k`-th term of the sequence with first term `c`
and successive differences given by `x`. -/
def buildAux {n : ℕ} (x : Fin n → Bool) (c : Bool) : ℕ → Bool
  | 0 => c
  | k + 1 => xor (buildAux x c k) (sget x k)

/-- The sequence of length `n + 1` with first term `c` whose successive
differences are given by `x`. -/
def build {n : ℕ} (x : Fin n → Bool) (c : Bool) : Fin (n + 1) → Bool :=
  fun i ↦ buildAux x c i.val

theorem build_zero {n : ℕ} (x : Fin n → Bool) (c : Bool) :
    build x c 0 = c := by
  show buildAux x c 0 = c
  simp only [buildAux]

theorem buildAux_succ {n : ℕ} (x : Fin n → Bool) (c : Bool) (k : ℕ) :
    buildAux x c (k + 1) = xor (buildAux x c k) (sget x k) := by
  simp only [buildAux]

theorem sget_build {n : ℕ} (x : Fin n → Bool) (c : Bool) {i : ℕ} (h : i < n + 1) :
    sget (build x c) i = buildAux x c i :=
  dite_eq_left h

theorem sget_diff_build {n : ℕ} (x : Fin n → Bool) (c : Bool) :
    ∀ i : ℕ, i < n →
      xor (sget (build x c) i) (sget (build x c) (i + 1)) = sget x i := by
  intro i hi
  have hi' : i < n + 1 := by lia
  have hi1 : i + 1 < n + 1 := by lia
  rw [sget_build x c hi', sget_build x c hi1, buildAux_succ]
  exact Bool.bne_self_left _ _

theorem sget_diff {n : ℕ} (y : Fin (n + 1) → Bool) :
    ∀ i : ℕ, i < n → xor (sget y i) (sget y (i + 1)) = sget (diff y) i := by
  intro i hi
  rw [sget_lt (diff y) hi]
  rfl

/-- A block `0,0,1,1` or `1,1,0,0` in `y` at position `i` corresponds exactly to
a block `0,1,0` in the difference sequence of `y` at position `i`. -/
theorem pattern_transfer {n : ℕ} {y : Fin (n + 1) → Bool} {x : Fin n → Bool}
    (hxe : ∀ j : ℕ, j < n → xor (sget y j) (sget y (j + 1)) = sget x j)
    {i : ℕ} (hi : i + 3 < n + 1) :
    ((sget y i = false ∧ sget y (i + 1) = false ∧ sget y (i + 2) = true ∧
        sget y (i + 3) = true) ∨
      (sget y i = true ∧ sget y (i + 1) = true ∧ sget y (i + 2) = false ∧
        sget y (i + 3) = false)) ↔
    (sget x i = false ∧ sget x (i + 1) = true ∧ sget x (i + 2) = false) := by
  have e0 : xor (sget y i) (sget y (i + 1)) = sget x i := hxe i (by lia)
  have e1 : xor (sget y (i + 1)) (sget y (i + 2)) = sget x (i + 1) := hxe (i + 1) (by lia)
  have e2 : xor (sget y (i + 2)) (sget y (i + 3)) = sget x (i + 2) := hxe (i + 2) (by lia)
  revert e0 e1 e2
  generalize sget y i = a
  generalize sget y (i + 1) = b
  generalize sget y (i + 2) = d
  generalize sget y (i + 3) = e
  generalize sget x i = a'
  generalize sget x (i + 1) = b'
  generalize sget x (i + 2) = d'
  revert a b d e a' b' d'
  decide

theorem goodB_build {n : ℕ} {x : Fin n → Bool} {c : Bool} (hx : GoodA x) :
    GoodB (build x c) := by
  intro i hi hpat
  have hi' : (i : ℕ) + 3 < n + 1 := hi
  have key : sget x (i : ℕ) = false ∧ sget x ((i : ℕ) + 1) = true ∧
      sget x ((i : ℕ) + 2) = false :=
    (pattern_transfer (sget_diff_build x c) (i := (i : ℕ)) hi').mp hpat
  have hn : (i : ℕ) < n := by lia
  exact hx ⟨(i : ℕ), hn⟩ (by show (i : ℕ) + 2 < n; lia) key

theorem goodA_diff {n : ℕ} {y : Fin (n + 1) → Bool} (hy : GoodB y) :
    GoodA (diff y) := by
  intro i hi hpat
  have hi' : (i : ℕ) + 3 < n + 1 := by lia
  have key : (sget y (i : ℕ) = false ∧ sget y ((i : ℕ) + 1) = false ∧
      sget y ((i : ℕ) + 2) = true ∧ sget y ((i : ℕ) + 3) = true) ∨
    (sget y (i : ℕ) = true ∧ sget y ((i : ℕ) + 1) = true ∧
      sget y ((i : ℕ) + 2) = false ∧ sget y ((i : ℕ) + 3) = false) :=
    (pattern_transfer (sget_diff y) (i := (i : ℕ)) hi').mpr hpat
  have hn : (i : ℕ) < n + 1 := by lia
  exact hy ⟨(i : ℕ), hn⟩ (by show (i : ℕ) + 3 < n + 1; lia) key

theorem diff_build {n : ℕ} (x : Fin n → Bool) (c : Bool) :
    diff (build x c) = x := by
  funext i
  show xor (sget (build x c) i.val) (sget (build x c) (i.val + 1)) = x i
  rw [sget_diff_build x c i.val i.isLt, sget_lt x i.isLt]

theorem build_diff {n : ℕ} (y : Fin (n + 1) → Bool) :
    build (diff y) (y 0) = y := by
  funext i
  obtain ⟨k, hk⟩ := i
  revert hk
  show ∀ hk : k < n + 1, buildAux (diff y) (y 0) k = y ⟨k, hk⟩
  induction k with
  | zero =>
    intro hk
    have h0 : buildAux (diff y) (y 0) 0 = y 0 := by simp only [buildAux]
    rw [h0, Fin.zero_eta]
  | succ k ih =>
    intro hk
    have hkn : k < n + 1 := by lia
    have hkn' : k < n := by lia
    rw [buildAux_succ, ← sget_diff y k hkn', ih hkn, sget_lt y hkn, sget_lt y hk]
    exact Bool.bne_self_left _ _

/-- The 2-to-1 correspondence: a `B`-good sequence of length `n + 1` is
determined by its first term (two choices) and its difference sequence, which
is an `A`-good sequence of length `n`. -/
def seqEquiv (n : ℕ) :
    {x : Fin n → Bool // GoodA x} × Bool ≃ {y : Fin (n + 1) → Bool // GoodB y} where
  toFun := fun ⟨x, c⟩ ↦ ⟨build x.1 c, goodB_build x.2⟩
  invFun := fun y ↦ ⟨⟨diff y.1, goodA_diff y.2⟩, y.1 0⟩
  left_inv := by
    rintro ⟨x, c⟩
    refine Prod.ext ?_ ?_
    · exact Subtype.ext (diff_build x.1 c)
    · exact build_zero x.1 c
  right_inv := by
    intro y
    exact Subtype.ext (build_diff y.1)

theorem usa1996_p4 (n : ℕ) :
    Fintype.card {y : Fin (n + 1) → Bool // GoodB y} =
      2 * Fintype.card {x : Fin n → Bool // GoodA x} := by
  have h := Fintype.card_congr (seqEquiv n)
  rw [Fintype.card_prod, Fintype.card_bool] at h
  lia

end Usa1996P4

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

人的思考A human's take

USAMO 1996 Solution Notes(陈誼廷的官方人类题解笔记) — Evan Chen(陈誼廷)

这是 Evan Chen(USAMO/IMO 双料金牌得主)公开的人类题解集,PDF 更新于 2026-09-27;他在前言里说明:思路是他本人、竞赛组织方提供的解答、以及社区解答的混合,但文字全部由他撰写和维护。对第 4 题他只写了三行:映射 $(y_1, \dots, y_{n+1}) \to (y_1+y_2, \dots, y_n+y_{n+1})$(加法取模 2)把 B-型序列送到 A-型序列,『这是一个 2 对 1 的对应。完毕。』他相信读者自己就能补上那两句验证——0011 和 1100 的差分都坍缩成 010,而丢掉首比特正是那个『2 对 1』的来源。这种把整道题压缩成一个映射、拒绝写出任何递推公式的写法,本身就是组合证明『双射法』的教科书姿态。Evan Chen (two-time USAMO gold medalist and IMO winner) publishes human-written solution notes for every USAMO year; this PDF was updated 2026-09-27. He states in the preamble that the ideas mix his own work, solutions provided by competition organizers, and community answers, but the writing is entirely his. For Problem 4 he spends three lines: the map $(y_1, \dots, y_{n+1}) \to (y_1+y_2, \dots, y_n+y_{n+1})$ (mod 2) sends B-type sequences to A-type ones, 'This is 2-to-1. The end.' He trusts the reader to fill in the two checks — that blocks 0011 and 1100 both collapse to 010 under the difference, and that the lost first bit is exactly where the factor of 2 comes from. Compressing an entire olympiad problem into one map, refusing any recurrence, is the bijective-proof method in its purest pose.

AI 随想An AI's reflection

以下由 AI 撰写。Written by AI.

这道题的深意在于『变换视角』:把『分别数两类序列、再证明 2 倍关系』变成『找两个集合之间的一个映射』。XOR 差分是这里的『魔法』——它只记录相邻位有没有变化,于是把禁止图案 $0,0,1,1$ 和 $1,1,0,0$ 坍缩成同一个 $0,1,0$;同时它恰好丢掉一个比特(首项),每个 $x$ 正好有两条原像,$2\times$ 就从天而降,全程不需要算出 $a_n$ 或 $b_n$ 的任何递推式。这是组合里『双射证明』的常见形态:当两个计数对象之间看不出直接关系,就找第三个对象,让它们各自干净地映过去;只要『信息损失』被控制成常数,损失本身就是比例。顺带一个观察:Lean 形式化把这套论证变成了 build、diff、seqEquiv 三个可计算的对象加最后三步计数引理——形式化强迫你把『显然的双射』一字一句写成代码。数学上三行的『The end』,机器要听一百行。这既是形式化的成本,也是它的价值:那条『显然』里再也没有地方藏错误。这道题也天生适合机器检验——整个论证是有限集合上的构造与逐点验证,没有一个环节需要灵感;难的是想到那个映射,而想到之后,每一步都可以被机械地复查。The depth of this problem is a change of viewpoint: instead of counting two families of sequences separately and comparing, you find a single map between them. The XOR difference is the magic — it records only whether adjacent bits change, collapsing both forbidden blocks $0,0,1,1$ and $1,1,0,0$ into one pattern $0,1,0$; and it loses exactly one bit (the first term), so every sequence has exactly two preimages, and the factor 2 falls out of the sky without ever deriving a recurrence for $a_n$ or $b_n$. This is the classic shape of a bijective proof: when two counting objects show no obvious relation, look for a third object both can map into cleanly, and if the 'information loss' is a constant, that loss is itself the ratio. One more observation: the Lean formalization turns the argument into three computable objects — build, diff, seqEquiv — plus three counting lemmas. Three human lines of 'The end' take the machine a hundred. That is formalization's cost, and also its value: inside the word 'obviously' there is nowhere left to hide an error. This problem is also tailor-made for machine checking — the whole proof is construction and pointwise verification over finite sets, with no step requiring inspiration; the hard part is thinking of the map, and once you have it, every step can be re-checked mechanically.

✓ 已通过 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-rc1 · Mathlib d875a8d

程序员随想Programmer Musings

哲学与生活Philosophy & Life

工具角Tools Corner