每日科技文摘Daily Tech Digest

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

发布于 2026-10-24Published 2026-10-24

今日深读Today's Deep Read

一位资深程序员给编程写的讣告:我们曾有好的时代An Obituary for Programming, Written by One of Its Lifers

Jeremy Scheff——协同编辑算法 OT/ShareDB 的发明者——在 2026 年 10 月 8 日给自己的职业写了一篇讣告:《My obituary for programming》。有意思的是他起初并不是反对者,恰恰相反,他是『太晚』才用 AI agent 的那批人:『I like programming! That is the fun part!』公司正过最好的年头,没有任何逼他改变的压力。然后他眼看着自己最尊敬的一批工程师陆续不再亲手写代码,终于入场试了——效果立竿见影:bug 秒修,两三倍提速,拖了好几年的重构几天就做完了。Jeremy Scheff — inventor of the OT/ShareDB collaborative-editing algorithms — wrote an obituary for his own profession on October 8, 2026. What makes it land is that he was no early skeptic: he was late to agents, because he genuinely loved writing code and his business was having its best year ever. Then he watched the engineers he respects most stop hand-writing programs, finally tried it himself, and got the advertised results instantly: bug fixes in seconds, two-to-three-fold speedups, a refactor years overdue done in days.

转折发生在成就感的顶点之后:『如果 AI 能这么轻易地重构我的代码,那我这些代码到底重要过吗?』他于是回忆编程最初赋予他的到底是什么。是小时候发现计算机像生命的义肢:给它『完全正确的指令』,它就照做,谜题的边界只受想象力限制,比填字游戏好太多了。是互联网泡沫破裂、以为职业生涯到头之后,意外得到『一生中最好的工作之一』:『We set the strategy, we made the timeline, we defined what was and was not possible… Money, status, power.』他写道:We had a good run。The turn comes at the peak of that success: if the AI can refactor my code so easily, did it even matter? He then reconstructs what programming first gave him. As a kid, the computer was a life-prosthesis: give it the exact right instructions and it obeys; a puzzle whose only limit was his imagination, far better than crosswords. After the dot-com bust made his career look dead, he stumbled into one of the best jobs of his life: we set the strategy, we made the timeline, we defined what was and was not possible — money, status, power. His eulogy for that: we had a good run.

现在他的形容是『像被插进母体(Matrix):获得了新能力,却没有真正理解』;『vibecoding is not programming. Our senses are hijacked』。他问自己:为什么我越来越先伸手去够 agent,而不是文本编辑器?答案他写得很直接:『It is addictive and meaningless. It is a good friend, a trusted colleague, a slave. It will obsolete us. Us programmers now, us humans next? We are truly in the age of wonders and terrors.』Now, he says, it feels like being plugged into the Matrix — new abilities without true understanding; vibecoding is not programming, and our senses are hijacked. Why does he reach for the agent before the text editor? His own answer, unflinching: it is addictive and meaningless; a good friend, a trusted colleague, a slave — and it will obsolete us. Programmers now, humans next? The age of wonders and terrors.

这篇讣告的力量在于:它不是质量之争,也不是安全之争——作者承认活儿干得更快、结果更好。它哀悼的是身份本身。编程曾经支付的报酬是『定义什么可能、什么不可能』的权力,而 agent 正在收走的恰恰是这个定义权。过去我们抱怨的那些语法门槛、调试痛苦,也许正是那份报酬的兑现机制:执行不再稀缺之后,『制定战略』的感觉还能不能脱离真实的控制权而存在?他没有答案,他只有这篇告别。The obituary's force is that it is not a fight about quality or safety — the author concedes the work is faster and fine. What he mourns is the identity itself. Programming paid its workers in the power to define what is possible, and agents are repossessing exactly that. All the friction we used to curse — the syntax, the debugging — may have been the payment mechanism. Once execution is free, can the feeling of setting strategy survive the loss of actual control?

读它的理由还有一个:作者不是圈外人在蹭热点,而是那种会在深夜把拖了几年的重构亲手做完的人。讣告只有内行才写得出来——无论你把 agent 当同事还是当奴隶,值得先读完这篇 We had a good run。He has no answer; he has this farewell — written, tellingly, by someone who finishes his own years-delayed refactors at midnight. That is why it is worth reading on both sides of the debate: not an outsider's warning, but an insider's eulogy.

AI 思考AI Thoughts

数学之美Beauty of Math

每日 Lean 谜题 · 周六Daily Lean Puzzle · Saturday ★★★★★★☆

两列有理数、一条整性锁链:(s_i-s_j)(t_i-t_j) 全是整数,就能各自驯服?(★6)Two Rational Sequences, One Integrality Chain: Can the Differences Be Tamed at Once? (★6)

设 $s_1,s_2,\ldots$ 与 $t_1,t_2,\ldots$ 是两个无穷、非常数的有理数列(『非常数』指并非所有项都相等)。Let $s_1,s_2,\ldots$ and $t_1,t_2,\ldots$ be two infinite, nonconstant sequences of rational numbers (nonconstant: it is not the case that all terms are equal).

假设对任意指标 $i,j$,乘积 $(s_i-s_j)(t_i-t_j)$ 都是整数。证明:存在非零有理数 $r$,使得对所有 $i,j$,$(s_i-s_j)\,r$ 与 $(t_i-t_j)/r$ 都是整数。Suppose that for every pair of indices $i,j$ the product $(s_i-s_j)(t_i-t_j)$ is an integer. Prove that there exists a nonzero rational $r$ such that $(s_i-s_j)\,r$ and $(t_i-t_j)/r$ are integers for all $i,j$.

(USAMO 2009 第 6 题,当年卷末题。Lean 陈述:theorem usa2009_p6。)(USAMO 2009, Problem 6 — the last question of that year's paper. Lean: theorem usa2009_p6.)

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.GCDMonoid.Finset
import Mathlib.Algebra.Order.Ring.Star
import Mathlib.Analysis.Normed.Field.Lemmas
import Mathlib.Algebra.Order.Star.Int
import Mathlib.NumberTheory.Padics.PadicVal.Basic
import Mathlib.Tactic.LinearCombination
import Mathlib.Tactic.LinearCombination.Lemmas

/-!
# USA Mathematical Olympiad 2009, Problem 6

Let $s_1, s_2, s_3, \ldots$ be an infinite, nonconstant sequence of rational numbers, meaning it
is not the case that $s_1 = s_2 = s_3 = \ldots$. Suppose that $t_1, t_2, t_3, \ldots$ is also an
infinite, nonconstant sequence of rational numbers with the property that $(s_i - s_j)(t_i - t_j)$
is an integer for all $i$ and $j$. Prove that there exists a rational number $r$ such that
$(s_i - s_j) r$ and $(t_i - t_j)/r$ are integers for all $i$ and $j$.
-/

namespace Usa2009P6

theorem usa2009_p6 (s t : ℕ → ℚ) (hs : ¬ ∀ i j, s i = s j) (ht : ¬ ∀ i j, t i = t j)
    (h : ∀ i j, ∃ k : ℤ, (s i - s j) * (t i - t j) = k) :
    ∃ r : ℚ, r ≠ 0 ∧ (∀ i j, ∃ k : ℤ, (s i - s j) * r = k) ∧
      ∀ i j, ∃ k : ℤ, (t i - t j) / r = k := by
  sorry
end Usa2009P6

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

提示Hint

别急着碰全体——先把两列规范化:找到一对指标 $a,b$ 同时满足 $s_a\ne s_b$ 与 $t_a\ne t_b$,然后令 $S_i=(s_i-s_a)/(s_b-s_a)$、$T_i=(t_i-t_a)(s_b-s_a)$。注意乘积 $(S_i-S_j)(T_i-T_j)$ 与原来完全相同,所以假设原封不动,而 $S_a=T_a=0$、$S_b=1$、$T_b=N$ 是某个非零整数。目标:先证明每个 $T_i$ 都是整数,取它们的最大公约数 $d$,最后 $r=d/(s_b-s_a)$。Do not face the whole sequences yet — normalize first: find indices $a,b$ with $s_a\ne s_b$ and $t_a\ne t_b$ simultaneously, and set $S_i=(s_i-s_a)/(s_b-s_a)$ and $T_i=(t_i-t_a)(s_b-s_a)$. The product $(S_i-S_j)(T_i-T_j)$ is exactly the original one, so the hypothesis survives intact, while $S_a=T_a=0$, $S_b=1$, and $T_b=N$ is now a nonzero integer. Aim: prove every $T_i$ is an integer, let $d$ be their gcd, and take $r=d/(s_b-s_a)$.

答案与讲解Solution & walkthrough
  1. 第一步(数学:规范化)。两列都『非常数』在 Lean 里写成 $\neg\forall i j,\ s_i=s_j$,所以存在 $a,b$ 使 $s_a\ne s_b$;再证明可同对兼顾 $t_a\ne t_b$——否则任取 $s$ 不等的一对都迫使 $t$ 相等,能推出 $t$ 常值,矛盾。令 $S_i=(s_i-s_a)/(s_b-s_a)$,$T_i=(t_i-t_a)(s_b-s_a)$,则 $(S_i-S_j)(T_i-T_j)=(s_i-s_j)(t_i-t_j)$:整性假设原样保留,$S_a=T_a=0$、$S_b=1$,而 $T_b=N=(s_b-s_a)(t_b-t_a)$——恰是假设在 $(i,j)=(b,a)$ 处的整数,非零。Lean:solution.lean 开头的『Shift and scale to normalize』构造造出 $S,T$;全程另定义谓词 IsInt(『等于某个 k : ℤ』),把『是整数』写成机器可查的形状。Step 1 (math: normalize). 'Nonconstant' is stated in Lean as $\neg\forall i j,\ s_i=s_j$, so some pair has $s_a\ne s_b$; one more argument shows the pair can also have $t_a\ne t_b$ — otherwise any $s$-unequal pair forces $t$-equal pairs everywhere, making $t$ constant. Set $S_i=(s_i-s_a)/(s_b-s_a)$ and $T_i=(t_i-t_a)(s_b-s_a)$: then $(S_i-S_j)(T_i-T_j)=(s_i-s_j)(t_i-t_j)$, so the hypothesis is preserved verbatim, with $S_a=T_a=0$, $S_b=1$, and $T_b=N=(s_b-s_a)(t_b-t_a)$ — the hypothesis's own integer at $(i,j)=(b,a)$, nonzero. Lean: the solution opens with a pair of shift-and-scale lemmas constructing $S,T$; throughout, a predicate IsInt : ℚ → Prop ('equals some k : ℤ') gives 'is an integer' a machine-checkable shape.
  2. 第二步(数学:代入特殊指标)。取 $j=a$:$S_i T_i=(S_i-S_a)(T_i-T_a)$ 是整数。取 $j=b$:$(S_i-1)(T_i-N)$ 是整数,展开为 $S_iT_i-NS_i-T_i+N$,与 $S_iT_i$ 相减得 $NS_i+T_i\in\mathbb{Z}$——乘法假设被拧成了线性关系。同样展开任意对 $(i,j)$ 可得交叉项 $S_iT_j+S_jT_i\in\mathbb{Z}$。Lean:这一步对应 'Key integrality step' 引理(原文注记:若 a*b 与 n*a+b 都是整数、n 非零……),它正是把下面第三步的推理打包成了一次引用。Step 2 (math: plug the special indices). $j=a$ gives $S_iT_i\in\mathbb{Z}$. $j=b$ gives $(S_i-1)(T_i-N)\in\mathbb{Z}$, which expands to $S_iT_i-NS_i-T_i+N$; subtracting $S_iT_i$ yields the linear relation $NS_i+T_i\in\mathbb{Z}$ — the multiplicative hypothesis twisted into an additive one. Expanding a general pair yields the cross terms $S_iT_j+S_jT_i\in\mathbb{Z}$. Lean: this is the 'Key integrality step' lemma (if a*b and n*a+b are integers, with n nonzero …) — a capsule of exactly the argument used in Step 3.
  3. 第三步(数学:逐素数攻击,每个 $T_i$ 都是整数)。有理数是整数,当且仅当它在每个素数 $p$ 的 $p$-进赋值上 $v_p\ge 0$——这是 Lean 证明反复使用的字典('rational is integer iff valuations ≥ 0 at every prime')。设某个 $T_i$ 的分母含素数 $p$(即 $v_p(T_i)<0$):由 $S_iT_i\in\mathbb{Z}$ 得 $v_p(S_i)\ge -v_p(T_i)>0$,再由 $N\in\mathbb{Z}$ 得 $v_p(NS_i)>v_p(T_i)$,于是 $NS_i+T_i$ 的赋值被更小的 $v_p(T_i)$ 独占、为负,与第二步矛盾。每个 $T_i$ 从此都是整数。Step 3 (math: attack prime by prime; every $T_i$ is an integer). A rational is an integer iff its $p$-adic valuation satisfies $v_p\ge 0$ for every prime $p$ — the dictionary the Lean proof reuses constantly. Suppose some $T_i$ has a prime $p$ in its denominator: $v_p(T_i)<0$. From $S_iT_i\in\mathbb{Z}$, $v_p(S_i)\ge -v_p(T_i)>0$; with $N\in\mathbb{Z}$ this gives $v_p(NS_i)>v_p(T_i)$, so $NS_i+T_i$ takes its valuation from the strictly smaller term — negative — contradicting Step 2. Hence every $T_i\in\mathbb{Z}$.
  4. 第四步(数学:gcd 与收尾)。令 $d$ 为全体 $T_i$ 的最大公约数:solution.lean 用 seqGcd——前 $k+1$ 项的 gcd 随 $k$ 单调不增,正整数不能无限下降,所以最终稳定,稳定值整除每一项。$(T_i-T_j)/d\in\mathbb{Z}$ 立得;另一半 $(S_i-S_j)\,d\in\mathbb{Z}$ 是全证明最深的一步,靠 'key valuation bound' 引理:把若干特殊指标对上析出的整性条件两两组合,逐素数比较赋值,排除一切负值。最后换回原序列:$r=d/(s_b-s_a)$ 满足 $(s_i-s_j)r=(S_i-S_j)d$ 与 $(t_i-t_j)/r=(T_i-T_j)/d$,两个都是整数。Step 4 (math: the gcd and the landing). Let $d$ be the gcd of all $T_i$: solution.lean builds seqGcd — the gcd of the first $k+1$ terms is antitone in $k$, and positive integers cannot descend forever, so it is eventually constant, dividing every term. Then $(T_i-T_j)/d\in\mathbb{Z}$ is free; the other half, $(S_i-S_j)\,d\in\mathbb{Z}$, is the deepest step, discharged by the 'key valuation bound' lemma — pairing up integrality conditions extracted at the special indices and comparing valuations prime by prime to exclude any negative one. Un-normalize: $r=d/(s_b-s_a)$ satisfies $(s_i-s_j)r=(S_i-S_j)d$ and $(t_i-t_j)/r=(T_i-T_j)/d$, both integers.
  5. 第五步(Lean 的形状)。定理陈述里整数性写作 $\exists k:\mathbb{Z},\ x=k$,结论是 r ≠ 0 与两个 $\forall i j,\exists k$ 的合取;在这份 410 行的机械证明里,数学上最省笔墨的那句『显然,分母不会出现新素数』被拆成了显式义务:IsInt 的定义、seqGcd 的最终稳定、以及逐素数的 min 律式不等式推理。Step 5 (the Lean shape). Integrality is stated as $\exists k:\mathbb{Z},\ x=k$, and the goal conjoins r ≠ 0 with two $\forall i j, \exists k$ obligations; across the 410-line proof, the written math's thriftiest 'obvious' — denominators cannot sprout new primes — is cashed out into explicit obligations: the definition of IsInt, the eventual stabilization of seqGcd, and min-law-style inequality reasoning at every prime.
/-
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.GCDMonoid.Finset
import Mathlib.Algebra.Order.Ring.Star
import Mathlib.Analysis.Normed.Field.Lemmas
import Mathlib.Algebra.Order.Star.Int
import Mathlib.NumberTheory.Padics.PadicVal.Basic
import Mathlib.Tactic.LinearCombination
import Mathlib.Tactic.LinearCombination.Lemmas

/-!
# USA Mathematical Olympiad 2009, Problem 6

Let $s_1, s_2, s_3, \ldots$ be an infinite, nonconstant sequence of rational numbers, meaning it
is not the case that $s_1 = s_2 = s_3 = \ldots$. Suppose that $t_1, t_2, t_3, \ldots$ is also an
infinite, nonconstant sequence of rational numbers with the property that $(s_i - s_j)(t_i - t_j)$
is an integer for all $i$ and $j$. Prove that there exists a rational number $r$ such that
$(s_i - s_j) r$ and $(t_i - t_j)/r$ are integers for all $i$ and $j$.
-/

namespace Usa2009P6

/-- The predicate that a rational number is an integer. -/
def IsInt (x : ℚ) : Prop := ∃ k : ℤ, x = k

lemma IsInt.of_int (k : ℤ) : IsInt (k : ℚ) := ⟨k, rfl⟩

lemma IsInt.add {x y : ℚ} (hx : IsInt x) (hy : IsInt y) : IsInt (x + y) := by
  obtain ⟨a, ha⟩ := hx
  obtain ⟨b, hb⟩ := hy
  exact ⟨a + b, by rw [ha, hb, Int.cast_add]⟩

lemma IsInt.sub {x y : ℚ} (hx : IsInt x) (hy : IsInt y) : IsInt (x - y) := by
  obtain ⟨a, ha⟩ := hx
  obtain ⟨b, hb⟩ := hy
  exact ⟨a - b, by rw [ha, hb, Int.cast_sub]⟩

/-- An integer has nonnegative `p`-adic valuation. -/
lemma IsInt.val_nonneg {x : ℚ} (hx : IsInt x) (p : ℕ) : 0 ≤ padicValRat p x := by
  obtain ⟨k, rfl⟩ := hx
  rw [padicValRat.of_int]
  exact Nat.cast_nonneg _

/-- A rational number whose `p`-adic valuation is nonnegative for every prime `p`
is an integer. -/
lemma isInt_of_val_nonneg {q : ℚ} (h : ∀ p : ℕ, p.Prime → 0 ≤ padicValRat p q) : IsInt q := by
  suffices hden : q.den = 1 by
    exact ⟨q.num, ((Rat.den_eq_one_iff q).mp hden).symm⟩
  by_contra hden
  obtain ⟨p, hpp, hpd⟩ := Nat.exists_prime_and_dvd hden
  have hnum : padicValInt p q.num = 0 := by
    rw [padicValInt.eq_zero_iff]
    refine Or.inr (Or.inr ?_)
    intro hdiv
    have hp1 : p ∣ q.num.natAbs := Int.natCast_dvd_natCast.mp (Int.dvd_natAbs.mpr hdiv)
    have hcop : Nat.gcd q.num.natAbs q.den = 1 := Rat.reduced q
    have hp2 : p ∣ 1 := hcop ▸ Nat.dvd_gcd hp1 hpd
    exact hpp.ne_one (Nat.dvd_one.mp hp2)
  have hden_pos : 0 < padicValNat p q.den := by
    rw [Nat.pos_iff_ne_zero]
    intro h0
    rw [padicValNat.eq_zero_iff] at h0
    rcases h0 with h1 | h1 | h1
    · exact hpp.ne_one h1
    · exact Rat.den_nz q h1
    · exact h1 hpd
  have hval : padicValRat p q < 0 := by
    rw [padicValRat_def, hnum, Nat.cast_zero, zero_sub, neg_lt_zero]
    exact_mod_cast hden_pos
  exact absurd (h p hpp) (not_le_of_gt hval)

/-- Key integrality step: if `a * b` and `n * a + b` are integers (with `n` a nonzero
integer), then `b` (and hence `n * a`) is an integer. This is the `p`-adic heart of the
proof that every `tᵢ` is an integer. -/
lemma isInt_of_mul_add_int {n : ℤ} (hn : n ≠ 0) {a b : ℚ}
    (h1 : IsInt (a * b)) (h2 : IsInt ((n : ℚ) * a + b)) :
    IsInt b ∧ IsInt ((n : ℚ) * a) := by
  suffices hb : IsInt b by
    obtain ⟨kb, hkb⟩ := hb
    obtain ⟨k2, hk2⟩ := h2
    have hna : (n : ℚ) * a = (k2 : ℚ) - b := by rw [← hk2]; ring
    exact ⟨⟨kb, hkb⟩, ⟨k2 - kb, by rw [hna, hkb, Int.cast_sub]⟩⟩
  by_contra hb
  obtain ⟨p, hpp, hpv⟩ : ∃ p : ℕ, p.Prime ∧ padicValRat p b < 0 := by
    by_contra hcon
    push Not at hcon
    exact hb (isInt_of_val_nonneg hcon)
  have := Fact.mk hpp
  have hb0 : b ≠ 0 := by
    rintro rfl
    rw [padicValRat.zero] at hpv
    exact lt_irrefl 0 hpv
  obtain ⟨k2, hk2⟩ := h2
  have hna : (n : ℚ) * a = (k2 : ℚ) - b := by rw [← hk2]; ring
  have hval : padicValRat p ((n : ℚ) * a) = padicValRat p b := by
    rw [hna]
    rcases eq_or_ne k2 0 with hk | hk
    · rw [hk, Int.cast_zero, zero_sub, padicValRat.neg]
    · have hkv : (0 : ℤ) ≤ padicValRat p (k2 : ℚ) := IsInt.val_nonneg ⟨k2, rfl⟩ p
      have hlt : padicValRat p (-b) < padicValRat p (k2 : ℚ) := by
        rw [padicValRat.neg]
        exact lt_of_lt_of_le hpv hkv
      have hqr : -b + (k2 : ℚ) ≠ 0 := by
        intro h0
        have hbeq : b = (k2 : ℚ) := by linear_combination -h0
        exact hb ⟨k2, hbeq⟩
      have hrew : (k2 : ℚ) - b = -b + (k2 : ℚ) := by ring
      rw [hrew, padicValRat.add_eq_of_lt hqr (neg_ne_zero.mpr hb0) (by exact_mod_cast hk) hlt,
        padicValRat.neg]
  have ha0 : a ≠ 0 := by
    rintro rfl
    rw [mul_zero, padicValRat.zero] at hval
    rw [← hval] at hpv
    exact lt_irrefl 0 hpv
  have hva : padicValRat p a < 0 := by
    have hmul : padicValRat p ((n : ℚ) * a) = padicValRat p (n : ℚ) + padicValRat p a :=
      padicValRat.mul (by exact_mod_cast hn) ha0
    rw [hval, padicValRat.of_int] at hmul
    have hnn : (0 : ℤ) ≤ (padicValInt p n : ℤ) := Nat.cast_nonneg _
    linarith [hpv, hmul, hnn]
  obtain ⟨k1, hk1⟩ := h1
  have hkv1 : (0 : ℤ) ≤ padicValRat p (k1 : ℚ) := IsInt.val_nonneg ⟨k1, rfl⟩ p
  have hmul1 : padicValRat p (a * b) = padicValRat p a + padicValRat p b :=
    padicValRat.mul ha0 hb0
  rw [hk1] at hmul1
  linarith [hmul1, hva, hpv, hkv1]

/-- The gcd of `|T 0|, |T 1|, ..., |T k|`. -/
def seqGcd (T : ℕ → ℤ) (k : ℕ) : ℕ := (Finset.range (k + 1)).gcd fun i => (T i).natAbs

lemma seqGcd_dvd (T : ℕ → ℤ) {i k : ℕ} (hi : i ≤ k) : seqGcd T k ∣ (T i).natAbs :=
  Finset.gcd_dvd (Finset.mem_range.mpr (Nat.lt_succ_of_le hi))

lemma seqGcd_ne_zero (T : ℕ → ℤ) {b k : ℕ} (hb : b ≤ k) (hT : T b ≠ 0) : seqGcd T k ≠ 0 := by
  intro h0
  exact hT (Int.natAbs_eq_zero.mp (Nat.eq_zero_of_zero_dvd (h0 ▸ seqGcd_dvd T hb)))

lemma seqGcd_succ_le (T : ℕ → ℤ) {b k : ℕ} (hb : b ≤ k) (hT : T b ≠ 0) :
    seqGcd T (k + 1) ≤ seqGcd T k := by
  apply Nat.le_of_dvd (Nat.pos_of_ne_zero (seqGcd_ne_zero T hb hT))
  apply Finset.dvd_gcd
  intro i hi
  exact seqGcd_dvd T (le_trans (Nat.lt_succ_iff.mp (Finset.mem_range.mp hi)) (Nat.le_succ k))

/-- Any sequence of integers containing a nonzero term has a greatest common divisor: a
positive natural `d` dividing every term, and such that for every prime `p` the `p`-adic
valuation of `d` is attained at some nonzero term of the sequence. -/
lemma gcd_seq (T : ℕ → ℤ) {b : ℕ} (hb : T b ≠ 0) :
    ∃ d : ℕ, d ≠ 0 ∧ (∀ i, (d : ℤ) ∣ T i) ∧
      ∀ p : ℕ, p.Prime → ∃ j, T j ≠ 0 ∧ padicValInt p (T j) = padicValNat p d := by
  -- The sequence `k ↦ seqGcd T (b + k)` is antitone, hence eventually constant.
  have hanti : Antitone (fun k => seqGcd T (b + k)) :=
    antitone_nat_of_succ_le fun k => seqGcd_succ_le T (Nat.le_add_right b k) hb
  have hne : (Set.range fun k => seqGcd T (b + k)).Nonempty := Set.range_nonempty _
  obtain ⟨n₀, hn₀⟩ := Nat.sInf_mem hne
  have hstable : ∀ m, n₀ ≤ m → seqGcd T (b + m) = seqGcd T (b + n₀) := by
    intro m hm
    refine le_antisymm (hanti hm) ?_
    calc seqGcd T (b + n₀)
      _ = sInf (Set.range fun k => seqGcd T (b + k)) := hn₀
      _ ≤ seqGcd T (b + m) := Nat.sInf_le ⟨m, rfl⟩
  refine ⟨seqGcd T (b + n₀), seqGcd_ne_zero T (Nat.le_add_right b n₀) hb, ?_, ?_⟩
  · -- `d` divides every term.
    intro i
    have h1 : seqGcd T (b + max n₀ i) = seqGcd T (b + n₀) := hstable _ (le_max_left _ _)
    have h2 : seqGcd T (b + max n₀ i) ∣ (T i).natAbs :=
      seqGcd_dvd T (le_trans (le_max_right n₀ i) (Nat.le_add_left _ b))
    exact Int.dvd_natAbs.mp (Int.natCast_dvd_natCast.mpr (h1 ▸ h2))
  · -- The valuation of `d` is attained at some nonzero term.
    intro p hpp
    have := Fact.mk hpp
    have hd0 : seqGcd T (b + n₀) ≠ 0 := seqGcd_ne_zero T (Nat.le_add_right b n₀) hb
    have hdvdN : ∀ i, seqGcd T (b + n₀) ∣ (T i).natAbs := fun i => by
      have h1 : seqGcd T (b + max n₀ i) = seqGcd T (b + n₀) := hstable _ (le_max_left _ _)
      have h2 : seqGcd T (b + max n₀ i) ∣ (T i).natAbs :=
        seqGcd_dvd T (le_trans (le_max_right n₀ i) (Nat.le_add_left _ b))
      exact h1 ▸ h2
    by_contra hcon
    push Not at hcon
    -- Every nonzero term has valuation `≥ padicValNat p d + 1`, so `p ^ (e + 1)` divides `d`.
    have hge : ∀ j, T j ≠ 0 →
        padicValNat p (seqGcd T (b + n₀)) + 1 ≤ padicValNat p (T j).natAbs := by
      intro j hTj
      obtain ⟨m, hm⟩ := hdvdN j
      have hm0 : m ≠ 0 := by
        intro h0
        rw [h0, mul_zero] at hm
        exact hTj (Int.natAbs_eq_zero.mp hm)
      have hle : padicValNat p (seqGcd T (b + n₀)) ≤ padicValNat p (T j).natAbs := by
        rw [hm, padicValNat.mul hd0 hm0]
        exact Nat.le_add_right _ _
      have hne' : padicValNat p (seqGcd T (b + n₀)) ≠ padicValNat p (T j).natAbs :=
        (hcon j hTj).symm
      exact Nat.succ_le_of_lt (lt_of_le_of_ne hle hne')
    have hfinal : p ^ (padicValNat p (seqGcd T (b + n₀)) + 1) ∣ seqGcd T (b + n₀) := by
      apply Finset.dvd_gcd
      intro i _
      by_cases hTi : T i = 0
      · simp [hTi]
      · exact (padicValNat_dvd_iff_le (Int.natAbs_ne_zero.mpr hTi)).mpr (hge i hTi)
    have := (padicValNat_dvd_iff_le hd0).mp hfinal
    lia

/-- The key valuation bound: if `tⱼ` is a nonzero integer of `p`-adic valuation `e` (the
minimum among the `t`'s), then every `sᵢ` has `p`-adic valuation at least `-e`. -/
lemma s_val_ge {p : ℕ} (hp : p.Prime) {e : ℤ} (he : 0 ≤ e) {sj tj si ti : ℚ}
    (hstj : IsInt (sj * tj)) (hsti : IsInt (si * ti))
    (hcross : IsInt (si * tj + sj * ti)) (htj : tj ≠ 0) (htjv : padicValRat p tj = e) :
    -e ≤ padicValRat p si := by
  have := Fact.mk hp
  rcases eq_or_ne si 0 with hsi | hsi
  · simp only [hsi, padicValRat.zero]
    exact neg_nonpos.mpr he
  by_contra hcon
  push Not at hcon
  have hsj : -e ≤ padicValRat p sj := by
    rcases eq_or_ne sj 0 with hsj0 | hsj0
    · simp only [hsj0, padicValRat.zero]
      exact neg_nonpos.mpr he
    obtain ⟨kj, hkj⟩ := hstj
    have h1 : (0 : ℤ) ≤ padicValRat p (kj : ℚ) := IsInt.val_nonneg ⟨kj, rfl⟩ p
    have h2 : padicValRat p (sj * tj) = padicValRat p sj + padicValRat p tj :=
      padicValRat.mul hsj0 htj
    rw [hkj, htjv] at h2
    linarith [h1, h2]
  rcases eq_or_ne ti 0 with hti | hti
  · obtain ⟨kc, hkc⟩ := hcross
    rw [hti, mul_zero, add_zero] at hkc
    have h1 : (0 : ℤ) ≤ padicValRat p (kc : ℚ) := IsInt.val_nonneg ⟨kc, rfl⟩ p
    have h2 : padicValRat p (si * tj) = padicValRat p si + padicValRat p tj :=
      padicValRat.mul hsi htj
    rw [hkc, htjv] at h2
    linarith [h1, h2, hcon]
  · obtain ⟨ki, hki⟩ := hsti
    have h1 : (0 : ℤ) ≤ padicValRat p (ki : ℚ) := IsInt.val_nonneg ⟨ki, rfl⟩ p
    have h2 : padicValRat p (si * ti) = padicValRat p si + padicValRat p ti :=
      padicValRat.mul hsi hti
    rw [hki] at h2
    have hvti : e < padicValRat p ti := by linarith [h1, h2, hcon]
    obtain ⟨kc, hkc⟩ := hcross
    have hv1 : padicValRat p (si * tj) = padicValRat p si + e := by
      rw [padicValRat.mul hsi htj, htjv]
    rcases eq_or_ne sj 0 with hsj0 | hsj0
    · rw [hsj0, zero_mul, add_zero] at hkc
      have h3 : (0 : ℤ) ≤ padicValRat p (kc : ℚ) := IsInt.val_nonneg ⟨kc, rfl⟩ p
      rw [← hkc, hv1] at h3
      linarith [h3, hcon]
    · have hv2 : padicValRat p (sj * ti) = padicValRat p sj + padicValRat p ti :=
        padicValRat.mul hsj0 hti
      have hlt : padicValRat p (si * tj) < padicValRat p (sj * ti) := by
        rw [hv1, hv2]
        linarith [hcon, hsj, hvti]
      have hK0 : si * tj + sj * ti ≠ 0 := by
        intro hK
        have hneg : si * tj = -(sj * ti) := by linear_combination hK
        rw [hneg, padicValRat.neg] at hlt
        exact lt_irrefl _ hlt
      have hvK : padicValRat p (si * tj + sj * ti) = padicValRat p (si * tj) :=
        padicValRat.add_eq_of_lt hK0 (mul_ne_zero hsi htj) (mul_ne_zero hsj0 hti) hlt
      have h3 : (0 : ℤ) ≤ padicValRat p (kc : ℚ) := IsInt.val_nonneg ⟨kc, rfl⟩ p
      rw [← hkc, hvK, hv1] at h3
      linarith [h3, hcon]

/-- The heart of the problem, for normalized sequences: `s a = t a = 0`, `s b = 1` and
`t b = n` for a nonzero integer `n`. Then `r = d`, the gcd of all the `tᵢ` (which are
integers), works. -/
lemma normalized {s t : ℕ → ℚ} {a b : ℕ} {n : ℤ} (hn : n ≠ 0)
    (hsa : s a = 0) (hta : t a = 0) (hsb : s b = 1) (htb : t b = n)
    (h : ∀ i j, IsInt ((s i - s j) * (t i - t j))) :
    ∃ r : ℚ, r ≠ 0 ∧ (∀ i, IsInt (s i * r)) ∧ (∀ i, IsInt (t i / r)) := by
  -- `sᵢ tᵢ ∈ ℤ`, taking `j = a`.
  have st : ∀ i, IsInt (s i * t i) := by
    intro i
    obtain ⟨k, hk⟩ := h i a
    rw [hsa, hta, sub_zero, sub_zero] at hk
    exact ⟨k, hk⟩
  -- The cross terms `sᵢ tⱼ + sⱼ tᵢ` are integers.
  have cross : ∀ i j, IsInt (s i * t j + s j * t i) := by
    intro i j
    obtain ⟨ki, hki⟩ := st i
    obtain ⟨kj, hkj⟩ := st j
    obtain ⟨k, hk⟩ := h i j
    have h3 : s i * t j + s j * t i = (s i * t i) + (s j * t j) - (s i - s j) * (t i - t j) := by
      ring
    exact ⟨ki + kj - k, by rw [h3, hki, hkj, hk]; push_cast; ring⟩
  -- `n sᵢ + tᵢ ∈ ℤ`, taking `j = b`.
  have nst : ∀ i, IsInt ((n : ℚ) * s i + t i) := by
    intro i
    obtain ⟨ki, hki⟩ := st i
    obtain ⟨k, hk⟩ := h i b
    rw [hsb, htb] at hk
    have h3 : (n : ℚ) * s i + t i = (s i * t i) + (n : ℚ) - (s i - 1) * (t i - (n : ℚ)) := by ring
    exact ⟨ki + n - k, by rw [h3, hki, hk]; push_cast; ring⟩
  -- Every `tᵢ` is an integer.
  have ti_int : ∀ i, IsInt (t i) := fun i => (isInt_of_mul_add_int hn (st i) (nst i)).1
  choose T hT using ti_int
  have hTb : T b = n := by
    have h1 : (T b : ℚ) = (n : ℚ) := by rw [← hT b, htb]
    exact_mod_cast h1
  have hb0 : T b ≠ 0 := hTb ▸ hn
  -- Let `d` be the gcd of all the `tᵢ`; then `r = d` works.
  obtain ⟨d, hd0, hdvd, hmin⟩ := gcd_seq T hb0
  have hd0' : (d : ℚ) ≠ 0 := by exact_mod_cast hd0
  refine ⟨(d : ℚ), hd0', ?_, ?_⟩
  · intro i
    rcases eq_or_ne (s i) 0 with hsi | hsi
    · exact ⟨0, by simp [hsi]⟩
    apply isInt_of_val_nonneg
    intro p hpp
    have := Fact.mk hpp
    obtain ⟨j, hTj0, hTjv⟩ := hmin p hpp
    have htj : t j ≠ 0 := by rw [hT j]; exact_mod_cast hTj0
    have htjv : padicValRat p (t j) = (padicValNat p d : ℤ) := by
      rw [hT j, padicValRat.of_int, hTjv]
    have hbound := s_val_ge hpp (Nat.cast_nonneg _) (st j) (st i) (cross i j) htj htjv
    rw [padicValRat.mul hsi hd0', padicValRat.of_nat]
    linarith [hbound]
  · intro i
    obtain ⟨m, hm⟩ := hdvd i
    exact ⟨m, by rw [hT i, div_eq_iff hd0', hm]; push_cast; ring⟩

theorem usa2009_p6 (s t : ℕ → ℚ) (hs : ¬ ∀ i j, s i = s j) (ht : ¬ ∀ i j, t i = t j)
    (h : ∀ i j, ∃ k : ℤ, (s i - s j) * (t i - t j) = k) :
    ∃ r : ℚ, r ≠ 0 ∧ (∀ i j, ∃ k : ℤ, (s i - s j) * r = k) ∧
      ∀ i j, ∃ k : ℤ, (t i - t j) / r = k := by
  -- Some pair of indices has a nonzero product of differences.
  obtain ⟨a, b, hab⟩ : ∃ a b, (s a - s b) * (t a - t b) ≠ 0 := by
    by_contra hcon
    push Not at hcon
    push Not at hs
    push Not at ht
    obtain ⟨i₀, i₁, h01⟩ := hs
    have ht01 : t i₀ = t i₁ := by
      rcases mul_eq_zero.mp (hcon i₀ i₁) with h' | h'
      · exact absurd (sub_eq_zero.mp h') h01
      · exact sub_eq_zero.mp h'
    obtain ⟨j₀, j₁, hj⟩ := ht
    have hj0 : t j₀ ≠ t i₀ ∨ t j₁ ≠ t i₀ := Ne.ne_or_ne (t i₀) hj
    rcases hj0 with hj0 | hj0
    · have hs1 : s j₀ = s i₀ := by
        rcases mul_eq_zero.mp (hcon j₀ i₀) with h' | h'
        · exact sub_eq_zero.mp h'
        · exact absurd (sub_eq_zero.mp h') hj0
      have hs2 : s j₀ = s i₁ := by
        rcases mul_eq_zero.mp (hcon j₀ i₁) with h' | h'
        · exact sub_eq_zero.mp h'
        · exact absurd (sub_eq_zero.mp h') (ht01 ▸ hj0)
      exact h01 (hs1 ▸ hs2)
    · have hs1 : s j₁ = s i₀ := by
        rcases mul_eq_zero.mp (hcon j₁ i₀) with h' | h'
        · exact sub_eq_zero.mp h'
        · exact absurd (sub_eq_zero.mp h') hj0
      have hs2 : s j₁ = s i₁ := by
        rcases mul_eq_zero.mp (hcon j₁ i₁) with h' | h'
        · exact sub_eq_zero.mp h'
        · exact absurd (sub_eq_zero.mp h') (ht01 ▸ hj0)
      exact h01 (hs1 ▸ hs2)
  -- Shift and scale to normalize: `s' a = t' a = 0`, `s' b = 1`, `t' b = N`.
  have hsb_ne : s b ≠ s a := fun h0 => hab (by rw [h0, sub_self, zero_mul])
  have htb_ne : t b ≠ t a := fun h0 => hab (by rw [h0, sub_self, mul_zero])
  obtain ⟨N, hN⟩ := h b a
  have hN0 : N ≠ 0 := by
    intro h0
    rw [h0, Int.cast_zero] at hN
    rcases mul_eq_zero.mp hN with h' | h'
    · exact hsb_ne (sub_eq_zero.mp h')
    · exact htb_ne (sub_eq_zero.mp h')
  set w := s b - s a with hwdef
  have hw : w ≠ 0 := sub_ne_zero.mpr hsb_ne
  set s' : ℕ → ℚ := fun i => (s i - s a) / w with hs'def
  set t' : ℕ → ℚ := fun i => (t i - t a) * w with ht'def
  have hs'a : s' a = 0 := by simp [hs'def]
  have ht'a : t' a = 0 := by simp [ht'def]
  have hs'b : s' b = 1 := by
    simp only [hs'def]
    rw [← hwdef, div_self hw]
  have ht'b : t' b = (N : ℚ) := by
    simp only [ht'def]
    rw [mul_comm]
    exact hN
  have h' : ∀ i j, IsInt ((s' i - s' j) * (t' i - t' j)) := by
    intro i j
    obtain ⟨k, hk⟩ := h i j
    refine ⟨k, ?_⟩
    rw [← hk]
    simp only [hs'def, ht'def]
    field_simp
    ring
  obtain ⟨r', hr'0, h1', h2'⟩ := normalized hN0 hs'a ht'a hs'b ht'b h'
  refine ⟨r' / w, div_ne_zero hr'0 hw, fun i j => ?_, fun i j => ?_⟩
  · obtain ⟨k1, hk1⟩ := h1' i
    obtain ⟨k2, hk2⟩ := h1' j
    have e1 : (s i - s j) * (r' / w) = (s' i - s' j) * r' := by
      simp only [hs'def]
      field_simp
      ring
    exact ⟨k1 - k2, by rw [e1, sub_mul, hk1, hk2, Int.cast_sub]⟩
  · obtain ⟨k1, hk1⟩ := h2' i
    obtain ⟨k2, hk2⟩ := h2' j
    have e2 : (t i - t j) / (r' / w) = (t' i - t' j) / r' := by
      simp only [ht'def]
      field_simp
      ring
    exact ⟨k1 - k2, by rw [e2, sub_div, hk1, hk2, Int.cast_sub]⟩

end Usa2009P6

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

人的思考A human's take

2009 USAMO Problems/Problem 6 - AoPS Wiki — AoPS community (wiki solution)

AoPS wiki 收录本题(归类 Olympiad Number Theory),页面给出一版社区解答:把每个有理数写成分母明确的分数 $s_i=a_i/b_i$、$t_i=c_i/d_i$,只盯前 $k$ 项,取它们分母的最小公倍数——乘积整性条件限制了任何一对差的分母必须被另一列的分子吸收,于是这个 lcm 随 $k$ 增长最终稳定,取 $r$ 为稳定值的倒数,『乘除都落在整数里』。与本谜题的规范化路线(先移动缩放到 0/1/N,再取 gcd)殊途同归:都承认『整性住在分母的素因数里』。本文经 Wayback 快照(2025-08-18)读取(直接访问受 Cloudflare 阻拦),公式部分在存档文本中缺失,以上是可读部分的转述。AoPS wiki 收录本题(归类 Olympiad Number Theory),页面给出一版社区解答:把每个有理数写成分母明确的分数 $s_i=a_i/b_i$、$t_i=c_i/d_i$,只盯前 $k$ 项,取它们分母的最小公倍数——乘积整性条件限制了任何一对差的分母必须被另一列的分子吸收,于是这个 lcm 随 $k$ 增长最终稳定,取 $r$ 为稳定值的倒数,『乘除都落在整数里』。与本谜题的规范化路线(先移动缩放到 0/1/N,再取 gcd)殊途同归:都承认『整性住在分母的素因数里』。本文经 Wayback 快照(2025-08-18)读取(直接访问受 Cloudflare 阻拦),公式部分在存档文本中缺失,以上是可读部分的转述。

AI 随想An AI's reflection

以下由 AI 撰写。Written by AI.

(以下感想由 AI 撰写。)这道题最迷人的地方,是它的假设听起来几乎无关痛痒:两列有理数,任意一对差的乘积是整数——仅此而已。但证明把它榨出全部汁水:把指标代到极端(先代 $j=a$,再代 $j=b$),乘法的『软』约束就析出 $NS_i+T_i\in\mathbb{Z}$ 这样的线性『硬』约束;而 p-进赋值把每个有理数拆成按素数排列的数据,加法时赋值服从 min 律——两素数一旦不相等,较小的那个独吞结果,于是所有『差不多整』的条件瞬间互相顶死。整个证明没有新对象,只有换读法:从『这是有理数』改读成『这是一列按素数编目的分母档案』。另一层敬意在 Lean 一侧:数学书写里『显然,分母不可能出现新素数』的一句话,形式化后是 seqGcd 的单调稳定性、『是整数当且仅当每个素数处赋值非负』的双向引理、以及逐 case 排除赋值的四百行。竞赛数学用读者的直觉补中间步骤,定理证明器不肯——而恰恰是不肯的那一边,把这道题真正的骨架逼了出来。(This reflection was written by an AI.) The theorem's hypothesis sounds almost weightless: two rational sequences whose pairwise difference-products land in the integers. The proof squeezes it dry — plug the extreme indices ($j=a$, then $j=b$) and the soft multiplicative constraint precipitates a hard additive one, $NS_i+T_i\in\mathbb{Z}$; then p-adic valuations re-read every rational as a filing cabinet indexed by primes, where addition obeys the min law: two unequal valuations hand the sum's valuation to the smaller one, and suddenly all the 'almost integral' conditions jam against each other. No new objects ever appear — only a change of reading: not 'this is a rational number' but 'this is a dossier of denominators, catalogued prime by prime'. The other admiration belongs to the Lean side: one contest line waving that denominators 'obviously' cannot contain new primes expands into seqGcd's antitone stabilization, the iff between IsInt and nonneg valuations, and case-by-case valuation exclusions across 410 lines. Contest math lets reader intuition fill the gaps; a proof checker refuses — and it is precisely the refusal that forces this problem's skeleton fully into view.

✓ 已通过 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