每日科技文摘Daily Tech Digest

每日科技文摘Daily Tech Digest

发布于 2026-10-15Published 2026-10-15

今日深读Today's Deep Read

今日深读:LLM 把技术扩散的漏斗倒了过来(2025 年 4 月)Today's Deep Read: LLMs Flip the Technology Diffusion Funnel (April 2025)

先说一个几乎没人注意到的历史规律:从电力、密码学、计算机、飞机,到互联网和 GPS,所有变革性技术走的都是同一条「自上而下」的扩散路径——先在政府和军方手里,再到企业,最后才轮到普通人。原因不神秘:新技术早期又贵、又笨重、又需要专门技能,天然只有大机构用得起。Karpathy 这篇文章的出发点,是他意识到 LLM 把这条规律整个倒了过来:ChatGPT 成了史上增长最快的消费级应用,约四亿周活跃用户拿它写作、编程、翻译、辅导功课、做深度调研;反倒是企业和政府的采纳,「明显更迟缓、更平淡」。个体第一次在革命性技术上跑赢了组织。Start with a historical pattern almost nobody notices: electricity, cryptography, computers, flight, the internet, GPS — every transformative technology diffused in the same top-down order. First government and military, then corporations, and only much later individuals. The reason is not mysterious: early versions of powerful technologies are expensive, bulky, and expertise-gated, so naturally only large institutions could operate them. Karpathy's essay begins with his realization that LLMs have flipped this pattern: ChatGPT became the fastest-growing consumer application in history, with some 400 million weekly users writing, coding, translating, tutoring, summarizing, doing deep research — while adoption in corporations and governments has been, in his words, 'more muted and lagging.' For the first time, individuals got a transformative technology before organizations did.

为什么会这样?他的第一个解释切在能力画像上。LLM 提供的是一种奇怪组合:「准专家级 × 极宽覆盖」——什么都能到及格线以上,但哪行都算不上顶尖,而且会犯错。对组织来说,这不够看,因为组织的超能力恰恰是把各领域的真专家集中到一起,LLM 只能在专家已经会做的事情上「好一点点」。但对个体完全不同:一个人通常最多在一两件事上是专家,「样样及格的准专家」对他来说不是补充,而是第一次把做不到的事变成做得到的事——程序员可以开始处理法律文档,研究员可以自己拉数据分析,任何人都能给自己做一个小应用、生成一套营销素材,全程不必雇人、不必求人是这个解释的精髓:LLM 的「浅」对专家是缺陷,对普通人却是史无前例的宽度。Why? His first explanation is about the capability profile. LLMs offer a strange combination: quasi-expert performance across a very wide range of domains — above passing grade nearly everywhere, top-tier nowhere, and fallible. That profile barely impresses organizations, because an organization's superpower is precisely concentrating genuine experts; an LLM only makes the things experts already do 'a bit better.' For individuals the story is reversed: a person is usually an expert in at most one or two things, so broad-but-adequate capability does not supplement them — it unlocks things they could never do before: the programmer drafts their own legal-document analysis, the researcher runs their own data analysis, anyone builds their own app or marketing assets without hiring or asking anyone. This is the heart of the argument: for experts, LLM shallowness is a flaw; for everyone else it is unprecedented breadth.

第二个解释:组织面对的本来就是困难模式。集成、遗留系统、品牌规范、安全协议、隐私合规、国际化、法律风险——变量成倍增加,容错率压到极低。「你没法把这一切塞进一个上下文窗口」;个人 vibe coding 搞砸了只是丑一点,企业在一次严重幻觉面前可能丢掉整个项目、丢一份工作。第三个解释最朴素也最硬:大组织的惯性——文化、先例、地盘之争、沟通开销、分布式员工的再培训、老式官僚流程。所有这些逆风,都专门针对「灵活但浅、会出错」的新工具。His second explanation: organizations play the game on hard mode. Integrations, legacy systems, brand style guides, security protocols, privacy, internationalization, legal risk — the variables multiply and the margin for error collapses. 'You can't put all of that in a context window.' An individual's vibe-coded toy failing looks silly; one disastrous hallucination inside a company can cost someone their job. The third explanation is the oldest: institutional inertia — culture, historical precedents, turf wars that escalate during rapid change, communication overhead, retraining a distributed workforce, plain bureaucracy. Every one of these headwinds hits exactly the tool that is versatile but shallow and fallible.

把三层叠起来,就得到一个能同时解释两种流行论调的框架:「LLM 对企业没用」和「LLM 改变了普通人的生活」都是真的,而且不矛盾——它们本来就是同一个非对称性的两面。企业采纳慢不是工具不行,而是工具画像与企业问题的形状错配;个体上手快也不是错觉,而是个体问题的形状恰好匹配「广而浅」。Karpathy 补了一句前瞻:未来的利益分配取决于能力动态范围和资本投入的函数——模型继续变强,「深」的部分迟早会追上来,那时组织的采纳才会真正起飞。Stack the three layers and you get a framework that explains two popular claims at once: 'LLMs are useless for business' and 'LLMs are changing ordinary people's lives' are both true, and they don't contradict — they are two faces of one asymmetry. Enterprise adoption is slow not because the tool is weak but because the tool's profile mismatches the shape of organizational problems; individual uptake is fast not because of hype but because individual problems match 'broad and adequate.' Karpathy adds a forward look: how the benefits keep distributing depends on the dynamic range of model capability versus capital expenditure — as models deepen, the corporate half of the diffusion should eventually catch up.

对我们最实用的带走是一条路标:今天,如果想知道一项新技术到底能给「人」做什么,别看企业公告,看普通人在用它做什么——那里是价值最先兑现的地方;也别用「还没进企业采购清单」来给一个消费级工具定罪。反过来,如果你在组织里推动 AI,最大的杠杆不是买更强的模型,而是把「塞不进上下文窗口的复杂度」一层层显式化:规范、测试、边界。这两件事合起来,就是漏斗倒转时代的生存姿势。The most practical takeaway is a signpost. To learn what a new technology can really do for humans, don't read enterprise announcements — watch what ordinary people do with it; that's where value lands first. And never convict a consumer-grade tool by its absence from a procurement checklist. Conversely, if you drive AI inside an organization, the biggest lever is not a stronger model but making the un-context-window-able complexity explicit: specs, tests, boundaries. Together, that is how you live in the era of the flipped funnel.

AI 思考AI Thoughts

数学之美The Beauty of Math

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

每日 Lean 谜题(★4):USAMO 2024 第四题——什么样的 (m, n) 项链能「怎么剪都数得清」Daily Lean Puzzle (★4): USAMO 2024 Problem 4 — Which (m, n) Necklaces Stay Countable Under Every Cut

设 $m, n$ 为正整数。一条环形项链上有 $m \cdot n$ 颗珠子,每颗染成红色或蓝色。如果无论从哪里下剪、把圆环分成 $m$ 段各含 $n$ 颗连续珠子的链条时,这 $m$ 段里的红珠数都两两不同,就称这种染色是好的。求所有存在「好染色」的 $(m, n)$。Let $m$ and $n$ be positive integers. A circular necklace has $m \cdot n$ beads, each colored red or blue. Call a coloring good if, no matter where you cut the circle into $m$ blocks of $n$ consecutive beads, the numbers of red beads in the $m$ blocks are pairwise distinct. Determine all pairs $(m, n)$ that admit a good coloring.

已验证的 Lean 定理断言:好染色存在的充要条件是 $m \le n + 1$,即 $(\exists c,\ \mathrm{AllCutsDistinct}\ c) \leftrightarrow (m \le n + 1)$。The verified Lean theorem asserts that a good coloring exists exactly when $m \le n + 1$: $(\exists c,\ \mathrm{AllCutsDistinct}\ c) \leftrightarrow (m \le n + 1)$.

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.BigOperators.Intervals
import Mathlib.Algebra.Order.Ring.Star
import Mathlib.Data.ZMod.Basic
import Mathlib.Tactic.Ring

/-!
# USA Mathematical Olympiad 2024, Problem 4

Let m and n be positive integers. A circular necklace contains mn beads, each
either red or blue. It turned out that no matter how the necklace was cut into
m blocks of n consecutive beads, each block had a distinct number of red beads.
Determine, with proof, all possible values of the ordered pair (m, n).
-/

namespace Usa2024P4

abbrev Necklace (m n : ℕ) := ZMod (m * n) → Bool

def blockCount {m n : ℕ} (c : Necklace m n) (s : ZMod (m * n)) (i : ℕ) : ℕ :=
  ∑ j ∈ Finset.range n, if c (s + ((i * n + j : ℕ) : ZMod (m * n))) then 1 else 0

def AllCutsDistinct {m n : ℕ} (c : Necklace m n) : Prop :=
  ∀ s : ZMod (m * n), Function.Injective (fun i : Fin m ↦ blockCount c s i.val)

abbrev solution : ℕ → ℕ → Prop := sorry

theorem usa2024_p4 (m n : ℕ) (hm : 0 < m) (hn : 0 < n) :
    (∃ c : Necklace m n, AllCutsDistinct c) ↔ solution m n := by
  sorry
end Usa2024P4

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

提示Hint

「不可能」那半边几乎免费:每段至多 $n$ 颗红珠,$m$ 个两两不同的数只能住进 $\{0, 1, \dots, n\}$。难的是构造:把 $m \cdot n$ 颗珠子摊成 $m$ 行、每行 $n$ 颗,找一条「逐行缩短的阶梯」染色规则,再对任意起点 $s < n$ 一段段数一遍。The impossibility half is nearly free: each block holds at most $n$ red beads, so $m$ pairwise-distinct counts must live in $\{0, 1, \dots, n\}$. The hard half is the construction: unroll the $m \cdot n$ beads into $m$ rows of $n$, find a 'staircase' coloring rule that shrinks one row at a time, then count the blocks for every cut offset $s < n$.

答案与讲解Solution & walkthrough
  1. 先把「怎么剪都算」形式化:珠子编号用 `ZMod (m * n) → Bool`——环形的「减了模就绕回来」免费得到。`blockCount c s i` 是对 `Finset.range n` 的示性函数求和,即起点在 $s + i \cdot n$ 的那一段的红珠数;`AllCutsDistinct c` 定义为 $\forall s$,函数 $i \mapsto \mathrm{blockCount}\ c\ s\ i$ 单射——「两两不同」在 Lean 里就是函数单射。First formalize 'every cut counts differently': index beads as `ZMod (m * n) → Bool` — the circle's wrap-around comes free from modular arithmetic. `blockCount c s i` sums the indicator over `Finset.range n`, the red count in the block starting at $s + i \cdot n$; `AllCutsDistinct c` means: for all $s$, the function $i \mapsto \mathrm{blockCount}\ c\ s\ i$ is injective — 'pairwise distinct' becomes function injectivity.
  2. 必要性(数学:抽屉原理;Lean:`Finset.card_image_of_injective` + `card_le_card`):每段 $n$ 颗珠子,红珠数 $\le n$,所以 $m$ 个互不相同的值落在 $\{0, 1, \dots, n\}$ 里——$m \le n + 1$。Lean 里把 `Fin m` 沿 `blockCount` 取像,单射让像的大小仍是 $m$,包含进 `Finset.range (n+1)` 后数元素就完事。Necessity (math: pigeonhole; Lean: `Finset.card_image_of_injective` + `card_le_card`): each block has $n$ beads so its red count is at most $n$; $m$ distinct values must live inside $\{0, 1, \dots, n\}$, giving $m \le n + 1$. In Lean, image `Fin m` under `blockCount`, use injectivity to keep cardinality $m$, note the image sits inside `Finset.range (n+1)`, and count.
  3. 充分性(数学:构造;Lean:`rowRed` / `constr`):给珠子 $p$ 写成 $p = q \cdot n + j$($j < n$),$q$ 是行、$j$ 是列;染红当且仅当 $n + 1 - m \le j < n - q$——一张逐行缩短一格的阶梯形。Lean 用 `p % n` 和 `p / n` 取坐标,`decide` 判定染红。Sufficiency (math: construction; Lean: `rowRed` / `constr`): write bead $p$ as $p = q \cdot n + j$ with $j < n$ — row $q$, column $j$ — and color it red exactly when $n + 1 - m \le j < n - q$: a staircase that shortens by one cell per row. Lean extracts the coordinates with `p % n` and `p / n` and decides with `decide`.
  4. 数数(数学:分情况 + 区间重排;Lean:`sum_rowRed` 与 `sum_rowRed_last`):对起点偏移 $s' < n$,第 $t$ 段红珠数在 $s' + t < n$ 时是 $m - 1 - t$,否则是 $m - 2 - t$——相邻两段错开 1,保证互不相同;而绕回尾部的那一段恰有 $s' - (n + 1 - m)$ 颗。Lean 先用 `Finset.sum_range_add` 把「跨过行尾」的和拆成前后两段,再用 `Ico` 区间等式改写集合、`Nat.card_Ico` 数区间长度,`lia` 收尾。Counting (math: cases + interval rearrangement; Lean: `sum_rowRed`, `sum_rowRed_last`): for a cut offset $s' < n$, block $t$ holds $m - 1 - t$ red beads when $s' + t < n$ and $m - 2 - t$ otherwise — adjacent blocks differ by 1, so all $m$ counts are distinct; the wrap-around last block holds exactly $s' - (n + 1 - m)$. Lean splits sums that straddle a row end with `Finset.sum_range_add`, rewrites the filtered index sets as `Ico` intervals, and finishes with `Nat.card_Ico` plus `lia`.
  5. 合成:把两个方向装进 `constructor` 分出的两个目标,最后 `#print axioms` 只剩 Lean 标准公理。整个证明里真正「难」的只有阶梯构造那一步;形式化最狠的贡献是逼你在动笔前决定「两两不同」到底是哪个函数的单射——这一步棋,往往就是解题的一半。Assembly: pack the two directions into the two goals from `constructor`; `#print axioms` then shows only Lean's standard axioms. Across the whole proof only the staircase construction is genuinely inventive — formalization's cruelest, best contribution is forcing you to decide, before writing anything, which function's injectivity 'pairwise distinct' is. That decision often solves half the problem.
/-
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.BigOperators.Intervals
import Mathlib.Algebra.Order.Ring.Star
import Mathlib.Data.ZMod.Basic
import Mathlib.Tactic.Ring

/-!
# USA Mathematical Olympiad 2024, Problem 4

Let m and n be positive integers. A circular necklace contains mn beads, each
either red or blue. It turned out that no matter how the necklace was cut into
m blocks of n consecutive beads, each block had a distinct number of red beads.
Determine, with proof, all possible values of the ordered pair (m, n).
-/

namespace Usa2024P4

/-- A circular necklace with `m * n` beads, each red (`true`) or blue (`false`).
The beads are indexed by their position on the circle, i.e. by `ZMod (m * n)`. -/
abbrev Necklace (m n : ℕ) := ZMod (m * n) → Bool

/-- The number of red beads in the block of `n` consecutive beads starting at
position `s + i * n` (positions are taken modulo `m * n`). -/
def blockCount {m n : ℕ} (c : Necklace m n) (s : ZMod (m * n)) (i : ℕ) : ℕ :=
  ∑ j ∈ Finset.range n, if c (s + ((i * n + j : ℕ) : ZMod (m * n))) then 1 else 0

/-- The property from the problem statement: no matter how the necklace is cut
into `m` blocks of `n` consecutive beads (the cut is determined by the starting
position `s` of the first block), the numbers of red beads in the `m` blocks
are pairwise distinct. -/
def AllCutsDistinct {m n : ℕ} (c : Necklace m n) : Prop :=
  ∀ s : ZMod (m * n), Function.Injective (fun i : Fin m ↦ blockCount c s i.val)

/-- Each block contains `n` beads, so its red bead count is at most `n`. -/
lemma blockCount_le {m n : ℕ} (c : Necklace m n) (s : ZMod (m * n)) (i : ℕ) :
    blockCount c s i ≤ n := by
  unfold blockCount
  calc (∑ j ∈ Finset.range n, if c (s + ((i * n + j : ℕ) : ZMod (m * n))) then 1 else 0)
      ≤ ∑ j ∈ Finset.range n, 1 := by
        apply Finset.sum_le_sum
        intro j _
        split <;> simp
    _ = n := by simp

/-- Necessity: the `m` distinct block counts all lie in `{0, 1, ..., n}`,
which has only `n + 1` elements. -/
lemma le_of_allCutsDistinct {m n : ℕ} {c : Necklace m n} (hc : AllCutsDistinct c) :
    m ≤ n + 1 := by
  have hinj := hc 0
  have hsub : Finset.univ.image (fun i : Fin m ↦ blockCount c 0 i.val) ⊆
      Finset.range (n + 1) := by
    intro x hx
    rw [Finset.mem_image] at hx
    obtain ⟨i, -, rfl⟩ := hx
    rw [Finset.mem_range]
    exact Nat.lt_succ_of_le (blockCount_le c 0 i.val)
  have hcard := Finset.card_le_card hsub
  rw [Finset.card_image_of_injective _ hinj, Finset.card_univ, Fintype.card_fin,
    Finset.card_range] at hcard
  exact hcard

/-- The red indicator of the unfolded construction: writing `p = q * n + j`
with `j < n` (so `q` is the row and `j` the column of bead `p`), the bead is
red iff `n + 1 - m ≤ j < n - q`. -/
def rowRed (m n : ℕ) (p : ℕ) : ℕ :=
  if n + 1 - m ≤ p % n ∧ p % n + p / n < n then 1 else 0

/-- Evaluating `rowRed` on the bead `t * n + a` in row `t`, column `a`. -/
lemma rowRed_eq {m n : ℕ} (hn : 0 < n) (t a : ℕ) (ha : a < n) :
    rowRed m n (t * n + a) = if n + 1 - m ≤ a ∧ a + t < n then 1 else 0 := by
  unfold rowRed
  have h1 : (t * n + a) % n = a := Nat.mul_add_mod_of_lt ha
  have h2 : (t * n + a) / n = t := by
    rw [show t * n + a = a + n * t by ring, Nat.add_mul_div_left _ _ hn,
      Nat.div_eq_of_lt ha, Nat.zero_add]
  rw [h1, h2]

/-- Evaluating `rowRed` on a bead in row `0`. -/
lemma rowRed_self {m n j : ℕ} (hj : j < n) :
    rowRed m n j = if n + 1 - m ≤ j then 1 else 0 := by
  unfold rowRed
  rw [Nat.mod_eq_of_lt hj, Nat.div_eq_of_lt hj]
  simp only [Nat.add_zero, hj, and_true]

/-- The necklace constructed for the `m ≤ n + 1` direction: writing
`p = q * n + j` with `j < n`, bead `p` is red iff `n + 1 - m ≤ j < n - q`. -/
def constr (m n : ℕ) : Necklace m n :=
  fun p ↦ decide (n + 1 - m ≤ p.val % n ∧ p.val % n + p.val / n < n)

/-- Bridging lemma: the block count of the constructed necklace can be computed
with natural number arithmetic; the modulo `m * n` on the indices keeps track
of the wrap-around of the circle. -/
lemma blockCount_constr_eq {m n : ℕ} (s' t : ℕ) :
    blockCount (constr m n) ((s' : ℕ) : ZMod (m * n)) t =
      ∑ j ∈ Finset.range n, rowRed m n ((s' + t * n + j) % (m * n)) := by
  unfold blockCount
  apply Finset.sum_congr rfl
  intro j _
  rw [show ((s' : ℕ) : ZMod (m * n)) + ((t * n + j : ℕ) : ZMod (m * n)) =
      ((s' + t * n + j : ℕ) : ZMod (m * n)) by push_cast; ring]
  simp only [constr, rowRed, ZMod.val_natCast, decide_eq_true_eq]

/-- The key counting lemma: for a cut starting at `s' < n`, the number of red
beads in block `t` (interpreted without wrap-around) is
`m - 1 - t` if `s' + t < n` and `m - 2 - t` otherwise. -/
lemma sum_rowRed {m n : ℕ} (hn : 0 < n) (hmn : m ≤ n + 1) {s' t : ℕ}
    (hs : s' < n) :
    (∑ j ∈ Finset.range n, rowRed m n (s' + t * n + j)) =
      if s' + t < n then m - 1 - t else m - 2 - t := by
  have e := Finset.sum_range_add (fun j ↦ rowRed m n (s' + t * n + j)) (n - s') s'
  rw [Nat.sub_add_cancel (Nat.le_of_lt hs)] at e
  rw [e]
  -- the first `n - s'` beads lie in row `t`, columns `s'` to `n - 1`
  have h1 : (∑ j ∈ Finset.range (n - s'), rowRed m n (s' + t * n + j)) =
      n - t - max s' (n + 1 - m) := by
    have step : (∑ j ∈ Finset.range (n - s'), rowRed m n (s' + t * n + j)) =
        ∑ j ∈ Finset.range (n - s'),
          (if n + 1 - m ≤ s' + j ∧ s' + j + t < n then 1 else 0) := by
      apply Finset.sum_congr rfl
      intro j hj
      rw [Finset.mem_range] at hj
      rw [show s' + t * n + j = t * n + (s' + j) by ring,
        rowRed_eq hn t (s' + j) (by lia)]
    rw [step]
    have hico := Finset.sum_Ico_eq_sum_range
      (f := fun u ↦ if n + 1 - m ≤ u ∧ u + t < n then 1 else 0) s' n
    rw [← hico, ← Finset.card_filter]
    have hfilter : (Finset.Ico s' n).filter (fun u ↦ n + 1 - m ≤ u ∧ u + t < n) =
        Finset.Ico (max s' (n + 1 - m)) (n - t) := by
      ext u
      simp only [Finset.mem_filter, Finset.mem_Ico]
      lia
    rw [hfilter, Nat.card_Ico]
  -- the last `s'` beads lie in row `t + 1`, columns `0` to `s' - 1`
  have h2 : (∑ j ∈ Finset.range s', rowRed m n (s' + t * n + (n - s' + j))) =
      min s' (n - t - 1) - (n + 1 - m) := by
    have step : (∑ j ∈ Finset.range s', rowRed m n (s' + t * n + (n - s' + j))) =
        ∑ j ∈ Finset.range s',
          (if n + 1 - m ≤ j ∧ j + (t + 1) < n then 1 else 0) := by
      apply Finset.sum_congr rfl
      intro j hj
      rw [Finset.mem_range] at hj
      rw [show s' + t * n + (n - s' + j) = (t + 1) * n + j by
        rw [add_mul, one_mul]; lia, rowRed_eq hn (t + 1) j (by lia)]
    rw [step, ← Finset.card_filter]
    have hfilter : (Finset.range s').filter (fun j ↦ n + 1 - m ≤ j ∧ j + (t + 1) < n) =
        Finset.Ico (n + 1 - m) (min s' (n - t - 1)) := by
      ext u
      simp only [Finset.mem_filter, Finset.mem_range, Finset.mem_Ico]
      lia
    rw [hfilter, Nat.card_Ico]
  rw [h1, h2]
  split_ifs with h <;> lia

/-- The last block (which wraps around the end of the necklace) contains
exactly `s' - (n + 1 - m)` red beads: its first `n - s'` beads lie in row
`m - 1` (which is entirely blue) and its last `s'` beads lie in row `0`. -/
lemma sum_rowRed_last {m n : ℕ} (hm : 0 < m) (hn : 0 < n) (hmn : m ≤ n + 1) {s' : ℕ}
    (hs : s' < n) :
    (∑ j ∈ Finset.range n, rowRed m n ((s' + (m - 1) * n + j) % (m * n))) =
      s' - (n + 1 - m) := by
  have hmn' : (m - 1) * n + n = m * n := by
    obtain ⟨k, rfl⟩ : ∃ k, m = k + 1 := ⟨m - 1, by lia⟩
    rw [Nat.add_sub_cancel, Nat.succ_mul]
  have e := Finset.sum_range_add
    (fun j ↦ rowRed m n ((s' + (m - 1) * n + j) % (m * n))) (n - s') s'
  rw [Nat.sub_add_cancel (Nat.le_of_lt hs)] at e
  rw [e]
  -- the first `n - s'` beads lie in row `m - 1`, which has no red beads
  have h1 : (∑ j ∈ Finset.range (n - s'),
      rowRed m n ((s' + (m - 1) * n + j) % (m * n))) = 0 := by
    apply Finset.sum_eq_zero
    intro j hj
    rw [Finset.mem_range] at hj
    have hlt : s' + (m - 1) * n + j < m * n := by
      have hsj : s' + j < n := by lia
      have h' := add_lt_add_left hsj ((m - 1) * n)
      lia
    rw [Nat.mod_eq_of_lt hlt, show s' + (m - 1) * n + j = (m - 1) * n + (s' + j) by ring,
      rowRed_eq hn (m - 1) (s' + j) (by lia), ite_eq_right (by lia)]
  -- the last `s'` beads wrap around into row `0`, columns `0` to `s' - 1`
  have h2 : (∑ j ∈ Finset.range s',
      rowRed m n ((s' + (m - 1) * n + (n - s' + j)) % (m * n))) = s' - (n + 1 - m) := by
    have step : ∀ j ∈ Finset.range s',
        rowRed m n ((s' + (m - 1) * n + (n - s' + j)) % (m * n)) =
          if n + 1 - m ≤ j then 1 else 0 := by
      intro j hj
      rw [Finset.mem_range] at hj
      have e1 : s' + (m - 1) * n + (n - s' + j) = m * n + j := by
        have hle : s' ≤ n := Nat.le_of_lt hs
        calc s' + (m - 1) * n + (n - s' + j) = (m - 1) * n + n + j := by lia
          _ = m * n + j := by rw [hmn']
      rw [e1, Nat.add_comm (m * n) j, Nat.add_mod_right,
        Nat.mod_eq_of_lt (by
          have hle : n ≤ m * n := Nat.le_mul_of_pos_left n hm
          lia),
        rowRed_self (by lia : j < n)]
    rw [Finset.sum_congr rfl step, ← Finset.card_filter]
    have hfilter : (Finset.range s').filter (fun j ↦ n + 1 - m ≤ j) =
        Finset.Ico (n + 1 - m) s' := by
      ext u
      simp only [Finset.mem_filter, Finset.mem_range, Finset.mem_Ico]
      lia
    rw [hfilter, Nat.card_Ico]
  rw [h1, h2, Nat.zero_add]

/-- The complete formula for the block counts of the constructed necklace
when the cut starts at `s' < n`. -/
lemma blockCount_constr {m n : ℕ} (hm : 0 < m) (hn : 0 < n) (hmn : m ≤ n + 1) {s' t : ℕ}
    (hs : s' < n) (ht : t < m) :
    blockCount (constr m n) ((s' : ℕ) : ZMod (m * n)) t =
      if t = m - 1 then s' - (n + 1 - m)
      else if s' + t < n then m - 1 - t else m - 2 - t := by
  rw [blockCount_constr_eq s' t]
  by_cases hlast : t = m - 1
  · subst hlast
    rw [ite_eq_left rfl]
    exact sum_rowRed_last hm hn hmn hs
  · rw [ite_eq_right hlast]
    have hlt : ∀ j ∈ Finset.range n, s' + t * n + j < m * n := by
      intro j hj
      rw [Finset.mem_range] at hj
      have hle : (t + 2) * n ≤ m * n := by
        have h : t + 2 ≤ m := by lia
        exact mul_le_mul_of_nonneg_right h (Nat.zero_le n)
      calc s' + t * n + j < t * n + 2 * n := by lia
        _ = (t + 2) * n := by rw [add_mul]
        _ ≤ m * n := hle
    have step : (∑ j ∈ Finset.range n, rowRed m n ((s' + t * n + j) % (m * n))) =
        ∑ j ∈ Finset.range n, rowRed m n (s' + t * n + j) := by
      apply Finset.sum_congr rfl
      intro j hj
      rw [Nat.mod_eq_of_lt (hlt j hj)]
    rw [step]
    exact sum_rowRed hn hmn hs

/-- The block count is periodic in the block index with period `m`. -/
lemma blockCount_add_period {m n : ℕ} (c : Necklace m n) (s : ZMod (m * n)) (i : ℕ) :
    blockCount c s (i + m) = blockCount c s i := by
  unfold blockCount
  apply Finset.sum_congr rfl
  intro j _
  have e : (((i + m) * n + j : ℕ) : ZMod (m * n)) = ((i * n + j : ℕ) : ZMod (m * n)) := by
    have h : (i + m) * n + j = i * n + j + m * n := by ring
    rw [h, Nat.cast_add, ZMod.natCast_self, add_zero]
  rw [e]

/-- Iterated version of `blockCount_add_period`. -/
lemma blockCount_add_mul {m n : ℕ} (c : Necklace m n) (s : ZMod (m * n)) (i q : ℕ) :
    blockCount c s (i + m * q) = blockCount c s i := by
  induction q with
  | zero => simp
  | succ q ih =>
    have h : i + m * (q + 1) = (i + m * q) + m := by ring
    rw [h, blockCount_add_period c s (i + m * q), ih]

/-- The block count only depends on the block index modulo `m`. -/
lemma blockCount_mod {m n : ℕ} (c : Necklace m n) (s : ZMod (m * n)) (x : ℕ) :
    blockCount c s x = blockCount c s (x % m) := by
  conv_lhs => rw [← Nat.mod_add_div x m]
  exact blockCount_add_mul c s (x % m) (x / m)

/-- Shifting the starting position of the cut by `n` beads shifts the blocks
by one. This reduces a general cut `s` to a cut starting at `s.val % n < n`. -/
lemma blockCount_shift {m n : ℕ} [NeZero (m * n)] (c : Necklace m n)
    (s : ZMod (m * n)) (i : ℕ) :
    blockCount c s i =
      blockCount c ((s.val % n : ℕ) : ZMod (m * n)) (s.val / n + i) := by
  unfold blockCount
  apply Finset.sum_congr rfl
  intro j _
  have e : s + ((i * n + j : ℕ) : ZMod (m * n)) =
      ((s.val % n : ℕ) : ZMod (m * n)) + (((s.val / n + i) * n + j : ℕ) : ZMod (m * n)) := by
    conv_lhs => rw [← ZMod.natCast_zmod_val s, ← Nat.cast_add]
    rw [← Nat.cast_add]
    congr 1
    conv_lhs => rw [← Nat.mod_add_div s.val n]
    ring
  rw [e]

/-- The constructed necklace satisfies the property of the problem. -/
lemma allCutsDistinct_constr {m n : ℕ} (hm : 0 < m) (hn : 0 < n) (hmn : m ≤ n + 1) :
    AllCutsDistinct (constr m n) := by
  have : NeZero (m * n) := ⟨(Nat.mul_pos hm hn).ne'⟩
  intro s i₁ i₂ hij
  have hij' : blockCount (constr m n) s i₁.val =
      blockCount (constr m n) s i₂.val := hij
  rw [blockCount_shift _ s i₁.val, blockCount_shift _ s i₂.val,
    blockCount_mod _ _ (s.val / n + i₁.val),
    blockCount_mod _ _ (s.val / n + i₂.val)] at hij'
  have hs' : s.val % n < n := Nat.mod_lt s.val hn
  have hr1 : (s.val / n + i₁.val) % m < m := Nat.mod_lt _ hm
  have hr2 : (s.val / n + i₂.val) % m < m := Nat.mod_lt _ hm
  rw [blockCount_constr hm hn hmn hs' hr1, blockCount_constr hm hn hmn hs' hr2] at hij'
  -- the explicit formula now forces the two shifted block indices to coincide
  have hval : (s.val / n + i₁.val) % m = (s.val / n + i₂.val) % m := by
    split_ifs at hij' <;> omega
  have hz : ((s.val / n + i₁.val : ℕ) : ZMod m) = ((s.val / n + i₂.val : ℕ) : ZMod m) :=
    (ZMod.natCast_eq_natCast_iff _ _ _).mpr hval
  push_cast at hz
  have h3 : (i₁.val : ZMod m) = (i₂.val : ZMod m) := add_left_cancel hz
  have h4 : i₁.val ≡ i₂.val [MOD m] := (ZMod.natCast_eq_natCast_iff _ _ _).mp h3
  have h5 : i₁.val % m = i₂.val % m := h4
  rw [Nat.mod_eq_of_lt i₁.isLt, Nat.mod_eq_of_lt i₂.isLt] at h5
  exact Fin.ext h5

/-- The answer: the required necklaces exist exactly for the pairs `(m, n)`
with `m ≤ n + 1`. -/
abbrev solution : ℕ → ℕ → Prop := fun m n ↦ m ≤ n + 1

theorem usa2024_p4 (m n : ℕ) (hm : 0 < m) (hn : 0 < n) :
    (∃ c : Necklace m n, AllCutsDistinct c) ↔ solution m n := by
  constructor
  · rintro ⟨c, hc⟩
    exact le_of_allCutsDistinct hc
  · intro h
    exact ⟨constr m n, allCutsDistinct_constr hm hn h⟩

end Usa2024P4

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

人的思考A human's take

Compfiles: USA Mathematical Olympiad 2024, Problem 4(Lean 形式化仓库中的原题陈述与证明) — Compfiles 社区(David Renshaw 维护;题面为人类撰写的竞赛原文,Apache-2.0)

这个 Lean 文件的头部注释用人话保留了竞赛原题——「 Determine, with proof, all possible values of the ordered pair (m, n)」——而形式化者的思路全藏在定义顺序里:先决定把「项链」认作 `ZMod (m * n) → Bool`(环 = 取模算术,不引入任何「圆」的对象),再决定把「数红珠」认作示性函数在 `Finset.range n` 上的求和,最后把最含糊的那句「任意剪法都两两不同」翻译成 ∀ s 加一个函数的单射性。这个 Lean 文件的头部注释用人话保留了竞赛原题——「 Determine, with proof, all possible values of the ordered pair (m, n)」——而形式化者的思路全藏在定义顺序里:先决定把「项链」认作 `ZMod (m * n) → Bool`(环 = 取模算术,不引入任何「圆」的对象),再决定把「数红珠」认作示性函数在 `Finset.range n` 上的求和,最后把最含糊的那句「任意剪法都两两不同」翻译成 ∀ s 加一个函数的单射性。

读这个文件的收获是看人怎么「翻译竞赛话术」:证明尚未开始,三个定义已经把答案的形状逼出来了——单射 + 值在 $\{0..n\}$ 里,几乎就是必要性证明本身;而「$p / n$ 当行号、$p \% n$ 当列号」这一行,就是阶梯构造的全部入口。Compfiles 的惯例(题面、许可、形式化说明同文件存放)也让这类「怎么想的」可以被人核对。读这个文件的收获是看人怎么「翻译竞赛话术」:证明尚未开始,三个定义已经把答案的形状逼出来了——单射 + 值在 $\{0..n\}$ 里,几乎就是必要性证明本身;而「$p / n$ 当行号、$p \% n$ 当列号」这一行,就是阶梯构造的全部入口。Compfiles 的惯例(题面、许可、形式化说明同文件存放)也让这类「怎么想的」可以被人核对。

AI 随想An AI's reflection

以下由 AI 撰写。Written by AI.

这道题最迷人的地方是答案的谦逊:$m \le n + 1$,一行抽屉原理几乎就是下界的全部。真正的门槛在另一半——你得「画」出来:把珠子摊成 $m$ 行 $n$ 列,每往下一行就把阶梯缩短一格,于是相邻两段恒差一颗红珠,怎么剪都错不开。这个阶梯不是算出来的,是看出来的;而 Lean 的形式化恰好记录了这件事的两半:`rowRed` 那一行「除法取行、模数取列」是看,后面的求和引理是算。对做题的人来说,这也是竞赛与形式化共同的教训:难的部分往往不是证明一个不等式,而是决定让哪句模糊的中文先变成哪个精确的函数——「两两不同」翻译成单射的那一刻,必要性已经写完了。今天深读里 Karpathy 说 LLM 是「准专家 × 广覆盖」;这道谜题是它的反面教材:机器可以验算每一段求和,但「摊成表格画个阶梯」这一步,目前仍然是一个人的眼睛先看见、编译器随后同意。答案折叠在提示里,但看见阶梯的那一眼,折叠在 $m \le n + 1$ 里,谁也没法替你省。What makes this problem lovely is the humility of its answer: $m \le n + 1$ — one line of pigeonhole is nearly the whole lower bound. The real threshold is the other half, where you must draw: unroll the beads into $m$ rows of $n$, shorten the staircase by one cell each row down, and then neighboring blocks always differ by exactly one red bead — no cut can make two counts collide. The staircase is not computed, it is seen; and the Lean formalization records precisely the two halves of that seeing: `rowRed`'s single line — divide for the row, mod for the column — is the eye, the summation lemmas afterward are the arithmetic. The shared lesson for contest solvers and formalizers alike: the hard part is rarely proving an inequality, it is deciding which vague clause of the problem becomes which exact function first — the moment 'pairwise distinct' becomes injectivity, the necessity proof has practically written itself. In today's lead, Karpathy describes LLMs as quasi-expert yet broad; this puzzle is the inverse exhibit: a machine can verify every block-sum, but the staircase must currently be seen by a human's eye before a compiler agrees. The answer hides in the hint, but the glance that sees it hides inside $m \le n + 1$, and nobody can skip it for you.

✓ 已通过 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-rc4 · Mathlib feefa32

程序员随想Programmer Musings

哲学与生活Philosophy & Life

工具角Tools Corner