每日科技文摘Daily Tech Digest

今日深读:AI 时代,数学家该做什么?Today's Deep Read: What Should Mathematicians Do in the Age of AI?

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

AI 思考AI Thoughts

数学之美The Beauty of Mathematics

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

IMO 1983 第 5 题:1983 个无三项等差的数IMO 1983 Problem 5: 1983 Integers with No Three in Arithmetic Progression

从 $1$ 到 $10^5$ 中,能否选出 $1983$ 个不同的正整数,使得其中任意三个数不构成等差数列?From the integers $1$ to $10^5$, can we choose $1983$ distinct positive integers such that no three form an arithmetic progression?

换句话说:是否存在一个集合 $S$,满足 $|S| = 1983$,$S$ 中每个元素 $\le 10^5$,且对任意 $x < y < z$ 属于 $S$,都有 $x + z \ne 2y$?In other words: does there exist a set $S$ with $|S| = 1983$, every element $\le 10^5$, and for any $x < y < z$ in $S$, $x + z \ne 2y$?

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

/-
Copyright (c) 2024 The Compfiles Contributors. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: InternLM-MATH LEAN Formalizer v0.1, Benpigchu
-/

import Mathlib.Data.List.GetD
import Mathlib.Tactic

/-!
# International Mathematical Olympiad 1983, Problem 5

Is it possible to choose $1983$ distinct positive integers,
all less than or equal to $10^5$,
no three of which are consecutive terms of an arithmetic progression?
Justify your answer.
-/

namespace Imo1983P5

theorem imo1983_p5 :
  ∃ S : Finset ℕ+, S.card = 1983 ∧
  (∀ x ∈ S, x ≤ 10^5) ∧
  ∀ x ∈ S, ∀ y ∈ S, ∀ z ∈ S, x < y ∧ y < z → x + z ≠ 2 * y := by
  sorry
end Imo1983P5

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

提示Hint

考虑把十进制数转换成三进制表示——如果一个数的三进制表示只包含 0 和 1,它会有什么性质?Consider converting numbers to their ternary (base-3) representation—if a number's ternary representation contains only digits 0 and 1, what property does it have?

答案与讲解Solution & walkthrough
  1. 第一步:为什么是三进制——等差数列的条件 $x + z = 2y$ 可以重新表述为:$y - x = z - y$,即 $y$ 是 $x$ 和 $z$ 的中点。如果我们构造一个集合,使得任意两个元素的和在三进制下'不会进位',那么 $x + z = 2y$ 就不可能发生。Step 1: Why ternary?—The arithmetic progression condition $x + z = 2y$ can be restated as: $y - x = z - y$, meaning $y$ is the midpoint of $x$ and $z$. If we construct a set where the sum of any two elements 'never carries' in ternary, then $x + z = 2y$ cannot occur.
  2. 第二步:核心构造——把 $0$ 到 $2^n - 1$ 的每个数,用二进制写出,然后把二进制 digits 当作三进制 digits 来解释。例如 $n=3$ 时,二进制 5 是 101,当作三进制就是 $1\cdot9 + 0\cdot3 + 1\cdot1 = 10$。这个映射产生了一个 $2^n$ 个元素的集合,其中任意两个数在三进制下相加不会进位(因为 digits 只有 0 和 1)。Step 2: The core construction—Take each number from $0$ to $2^n - 1$, write it in binary, then interpret those binary digits as ternary digits. For example, for $n=3$, binary 5 is 101, interpreted as ternary it becomes $1\cdot9 + 0\cdot3 + 1\cdot1 = 10$. This mapping produces a set of $2^n$ elements where no two numbers carry when added in ternary (since digits are only 0 and 1).
  3. 第三步:为什么没有等差数列——假设 $x, y, z$ 构成等差数列,即 $x + z = 2y$。在三进制下,$x + z$ 的每个 digit 是 $x$ 和 $z$ 对应 digit 的和(0+0=0, 0+1=1, 1+0=1, 1+1=2),而 $2y$ 的每个 digit 是 $y$ 对应 digit 的两倍(0→0, 1→2)。要让两边相等,$x$ 和 $z$ 的每个 digit 必须相同,即 $x = z$,但这与 $x < z$ 矛盾。Step 3: Why no arithmetic progression—Suppose $x, y, z$ form an AP, i.e., $x + z = 2y$. In ternary, each digit of $x + z$ is the sum of corresponding digits of $x$ and $z$ (0+0=0, 0+1=1, 1+0=1, 1+1=2), while each digit of $2y$ is twice the corresponding digit of $y$ (0→0, 1→2). For equality, $x$ and $z$ must have identical digits at every position, meaning $x = z$, contradicting $x < z$.
  4. 第四步:验证大小——取 $n = 11$,构造出的集合有 $2^{11} - 1 = 2047$ 个元素,最大元素是 $\sum_{i=0}^{10} 3^i = \frac{3^{11}-1}{2} = 88573 < 10^5$。从这个集合中任选 1983 个元素即可。Step 4: Verify the size—Take $n = 11$. The constructed set has $2^{11} - 1 = 2047$ elements, and the maximum element is $\sum_{i=0}^{10} 3^i = \frac{3^{11}-1}{2} = 88573 < 10^5$. Select any 1983 elements from this set.
/-
Copyright (c) 2024 The Compfiles Contributors. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: InternLM-MATH LEAN Formalizer v0.1, Benpigchu
-/

import Mathlib.Data.List.GetD
import Mathlib.Tactic

/-!
# International Mathematical Olympiad 1983, Problem 5

Is it possible to choose $1983$ distinct positive integers,
all less than or equal to $10^5$,
no three of which are consecutive terms of an arithmetic progression?
Justify your answer.
-/

namespace Imo1983P5

lemma Nat.ofDigits_eq (b : ℕ) (L : List ℕ)
    : Nat.ofDigits b L = ∑ i ∈ Finset.range L.length, (L.getI i) * b ^ i := by
  induction L with
  | nil => simp
  | cons d L' h =>
    simp only [Nat.ofDigits_cons, List.length_cons, Finset.sum_range_succ',
               List.getI_cons_zero, pow_zero, mul_one, List.getI_cons_succ]
    rw [h, add_comm, mul_comm, Finset.sum_mul]
    congr 1
    apply Finset.sum_congr rfl fun i _ ↦ by ring

lemma Nat.getI_digits_lt (n i : ℕ) {b : ℕ} (h : 2 ≤ b) : (b.digits n).getI i < b := by
  simp only [← List.getD_default_eq_getI, Nat.default_eq_zero, Nat.getD_digits n i h]
  exact Nat.mod_lt _ (by lia)

lemma Nat.getI_digits_add (m n : ℕ) {b : ℕ} (hb : 2 ≤ b)
  (h : ∀ i : ℕ, (b.digits m).getI i + (b.digits n).getI i < b)
  : ∀ i : ℕ, (b.digits m).getI i  + (b.digits n).getI i = (b.digits (m + n)).getI i := by
  induction' m using Nat.strong_induction_on with m h' generalizing n
  by_cases! h'' : m = 0 ∨ n = 0
  · rcases h'' with rfl | rfl <;> simp [Nat.digits_zero, List.getI_nil]
  · rw [Nat.ne_zero_iff_zero_lt, Nat.ne_zero_iff_zero_lt] at h''
    rw [Nat.digits_of_two_le_of_pos hb h''.left] at h ⊢
    rw [Nat.digits_of_two_le_of_pos hb h''.right] at h ⊢
    have hmn : 0 < m + n := add_pos h''.left h''.right
    rw [Nat.digits_of_two_le_of_pos hb hmn]
    have h0 := h 0
    rw [List.getI_cons_zero, List.getI_cons_zero] at h0
    intro i
    by_cases! hi : i = 0
    · rw [hi, List.getI_cons_zero, List.getI_cons_zero, List.getI_cons_zero]
      exact (Nat.add_mod_of_add_mod_lt h0).symm
    · rcases Nat.exists_eq_succ_of_ne_zero hi with ⟨i', hi'⟩
      rw [hi', List.getI_cons_succ, List.getI_cons_succ, List.getI_cons_succ]
      have hm' : m / b < m := Nat.div_lt_self h''.left (by lia)
      have h'mn : ∀ (i : ℕ), (b.digits (m / b)).getI i + (b.digits (n / b)).getI i < b := by
        intro i
        rw [← List.getI_cons_succ (m / b)]
        nth_rw 2 [← List.getI_cons_succ (n / b)]
        exact h (i + 1)
      have h'm'n' := h' (m / b) hm' (n / b) h'mn
      rw [h'm'n' i']
      congr
      exact (Nat.add_div_eq_of_add_mod_lt h0).symm

lemma Nat.eq_iff_getI_digits_eq (m n b: ℕ)
  : m = n ↔ (∀ i : ℕ, (b.digits m).getI i  = (b.digits n).getI i) := by
  constructor
  · intro hmn i
    rw [hmn]
  · intro h
    rw [← Nat.ofDigits_digits b m, ← Nat.ofDigits_digits b n]
    rw [Nat.ofDigits_eq, Nat.ofDigits_eq]
    rw [← Finset.sdiff_union_inter (Finset.range (b.digits m).length) (Finset.range (b.digits n).length)]
    nth_rw 3 [← Finset.sdiff_union_inter (Finset.range (b.digits n).length) (Finset.range (b.digits m).length)]
    rw [Finset.sum_union (Finset.disjoint_sdiff_inter _ _)]
    rw [Finset.sum_union (Finset.disjoint_sdiff_inter _ _)]
    have h₁ : ∀ i ∈ Finset.range (b.digits m).length \ Finset.range (b.digits n).length,
      (b.digits m).getI i * b ^ i = 0 := by
      intro i hi
      rw [h i]
      apply mul_eq_zero_of_left
      rw [← Nat.default_eq_zero]
      apply List.getI_eq_default
      rw [Finset.mem_sdiff, Finset.mem_range, Finset.mem_range, not_lt] at hi
      exact hi.right
    have h₂ : ∀ i ∈ Finset.range (b.digits n).length \ Finset.range (b.digits m).length,
      (b.digits n).getI i * b ^ i = 0 := by
      intro i hi
      rw [← h i]
      apply mul_eq_zero_of_left
      rw [← Nat.default_eq_zero]
      apply List.getI_eq_default
      rw [Finset.mem_sdiff, Finset.mem_range, Finset.mem_range, not_lt] at hi
      exact hi.right
    rw [Finset.sum_eq_zero h₁, Finset.sum_eq_zero h₂, zero_add, zero_add]
    apply Finset.sum_congr (Finset.inter_comm _ _)
    intro i hi
    rw [h i]

def base_two_to_base_three (n : ℕ) := Nat.ofDigits 3 (Nat.digits 2 n)

lemma digits_base_two_to_base_three (n : ℕ)
    : Nat.digits 2 n = Nat.digits 3 (base_two_to_base_three n) := by
  symm; rw [base_two_to_base_three]; apply Nat.digits_ofDigits
  · norm_num
  · exact fun l hl => lt_trans (Nat.digits_lt_base (by norm_num) hl) (by norm_num)
  · exact fun h => Nat.getLast_digit_ne_zero 2 (Nat.digits_ne_nil_iff_ne_zero.mp h)

lemma base_two_to_base_three_inj : Function.Injective base_two_to_base_three := fun m n hmn =>
  Nat.digits_inj_iff.mp (by rw [digits_base_two_to_base_three, digits_base_two_to_base_three, hmn])

lemma base_two_to_base_three_zero : base_two_to_base_three 0 = 0 := rfl

lemma base_two_to_base_three_pos {m : ℕ} (hm : 0 < m) : 0 < base_two_to_base_three m :=
  Nat.pos_of_ne_zero (base_two_to_base_three_zero ▸ base_two_to_base_three_inj.ne hm.ne')

def zero_or_one_in_base_three (n : ℕ) :=
  ∀ i : ℕ, (Nat.digits 3 n).getI i = 0 ∨ (Nat.digits 3 n).getI i = 1

lemma zero_or_one_in_base_three_of_eq_base_two_to_base_three
  {m n : ℕ} (hmn : base_two_to_base_three n = m)
  : zero_or_one_in_base_three m := by
  rw [← hmn, zero_or_one_in_base_three]
  intro i
  rw [← Nat.le_one_iff_eq_zero_or_eq_one, ← digits_base_two_to_base_three]
  rw [← Nat.lt_succ_iff]
  apply Nat.getI_digits_lt
  rfl

lemma eq_iff_of_zero_or_one_in_base {m n : ℕ} (hm : zero_or_one_in_base_three m) (hn : zero_or_one_in_base_three n)
  : (∀ i : ℕ, (Nat.digits 3 (m + n)).getI i = 0 ∨ (Nat.digits 3 (m + n)).getI i = 2)
    ↔ m = n := by
    rw [zero_or_one_in_base_three] at hm hn
    rw [Nat.eq_iff_getI_digits_eq m n 3]
    have h : ∀ i : ℕ, (Nat.digits 3 m).getI i + (Nat.digits 3 n).getI i < 3 := fun i ↦ by
      have := hm i; have := hn i; lia
    apply Nat.getI_digits_add _ _ (by norm_num) at h
    constructor <;> intro h' i
    · have := hm i; have := hn i; have := h i; have := h' i; lia
    · have := hn i; have := h i; have := h' i; lia

theorem generalized (n : ℕ+) :
  ∃ S : Finset ℕ+, S.card = 2 ^ n.val - 1 ∧
  (∀ x ∈ S, x.val ≤ (3 ^ n.val - 1) / 2) ∧
  ∀ x ∈ S, ∀ y ∈ S, ∀ z ∈ S, x < y ∧ y < z → x + z ≠ 2 * y := by
  -- typecast the finset into ℕ+
  use Finset.map ⟨(⟨base_two_to_base_three ·.val, base_two_to_base_three_pos (by grind)⟩),
    fun _ _ h => by
      exact Subtype.ext
        (base_two_to_base_three_inj (congrArg PNat.val h))⟩ (Finset.range (2 ^ n.val) \ Finset.range 1).attach
  and_intros
  · rw [Finset.card_map, Finset.card_attach, Finset.card_sdiff]
    rw [Finset.range_inter_range, Finset.card_range, Finset.card_range]
    congr 1
    exact min_eq_left (Nat.one_le_pow _ _ (by norm_num))
  · intro x hx
    rw [Finset.mem_map] at hx
    simp_rw [Finset.mem_attach, true_and, DFunLike.coe] at hx
    rcases hx with ⟨⟨m, hm⟩, rfl⟩
    rw [PNat.mk_coe, base_two_to_base_three, Nat.ofDigits_eq]
    have h' : ∀ i ∈ Finset.range (Nat.digits 2 m).length, (Nat.digits 2 m).getI i * 3 ^ i ≤ 3 ^ i := by
      intro i _; nth_rw 2 [← one_mul (3 ^ i)]
      exact Nat.mul_le_mul_right _ (Nat.lt_succ_iff.mp (Nat.getI_digits_lt (b := 2) m i le_rfl))
    apply le_trans (Finset.sum_le_sum h')
    rw [Nat.le_div_iff_mul_le (by norm_num)]
    zify
    nth_rw 2 [(by norm_num : (2 : ℤ) = 3 - 1)]
    rw [geom_sum_mul, Nat.cast_sub (Nat.one_le_pow _ 3 (by norm_num)), Nat.cast_one]
    rw [sub_le_sub_iff_right]
    push_cast
    rw [pow_le_pow_iff_right₀ (by norm_num), Nat.digits_length_le_iff (by norm_num)]
    rw [Finset.mem_sdiff, Finset.mem_range] at hm
    exact hm.left
  · rintro x hx y hy z hz h'
    contrapose! h'
    simp_rw [Finset.mem_map, ← PNat.coe_inj, DFunLike.coe, PNat.mk_coe] at hx hy hz
    rcases hx with ⟨x', -, hx'x⟩
    rcases hy with ⟨y', -, hy'y⟩
    rcases hz with ⟨z', -, hz'z⟩
    rw [← PNat.coe_lt_coe, ← PNat.coe_le_coe, PNat.val]
    apply zero_or_one_in_base_three_of_eq_base_two_to_base_three at hx'x
    apply zero_or_one_in_base_three_of_eq_base_two_to_base_three at hy'y
    apply zero_or_one_in_base_three_of_eq_base_two_to_base_three at hz'z
    suffices h : (x : ℕ) = z by rw [PNat.coe_inj.mp h]; apply le_of_lt
    rw [← eq_iff_of_zero_or_one_in_base hx'x hz'z]
    norm_cast; rw [h']; push_cast; rw [two_mul]
    rw [eq_iff_of_zero_or_one_in_base hy'y hy'y]

theorem imo1983_p5 :
  ∃ S : Finset ℕ+, S.card = 1983 ∧
  (∀ x ∈ S, x ≤ 10^5) ∧
  ∀ x ∈ S, ∀ y ∈ S, ∀ z ∈ S, x < y ∧ y < z → x + z ≠ 2 * y := by
  rcases generalized 11 with ⟨S', hS'₁, hS'₂, hS'₃⟩
  have h : 1983 ≤ S'.card := by rw [hS'₁]; norm_num
  rcases Finset.exists_subset_card_eq h with ⟨S, hS₁, hS₂⟩
  use S
  and_intros
  · exact hS₂
  · exact fun x hx ↦ by rw [← PNat.coe_le_coe]; exact le_trans (hS'₂ x (hS₁ hx)) (by norm_num)
  · exact fun x hx y hy z hz ↦ hS'₃ x (hS₁ hx) y (hS₁ hy) z (hS₁ hz)

end Imo1983P5

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

人的思考A human's take

IMO 1983 Problem 5 — Compfiles formalization — David Renshaw and contributors

这道题的标准解法是使用'三进制不含数字 2'的构造。核心思路是:如果一个数的三进制表示只含 0 和 1,那么任意两个这样的数相加不会进位,从而 $x + z = 2y$ 在三进制下不可能成立(因为左边 digits 是 0/1/2,右边 digits 是 0/2,要相等必须 $x=z$)。The standard solution uses the construction of numbers whose ternary representation contains only digits 0 and 1. The core idea: if a number's ternary representation contains only 0s and 1s, then adding any two such numbers never carries, making $x + z = 2y$ impossible in ternary (since left side digits are 0/1/2, right side digits are 0/2; equality requires $x=z$).

取 $n=11$,构造出的集合有 $2^{11}-1 = 2047$ 个元素,最大元素 $88573 < 10^5$,从中任选 1983 个即可满足要求。Taking $n=11$, the constructed set has $2^{11}-1 = 2047$ elements, with maximum element $88573 < 10^5$. Selecting any 1983 elements from this set satisfies the requirement.

AI 随想An AI's reflection

以下由 AI 撰写。Written by AI.

这道 IMO 1983 的第 5 题,看似是一个纯粹的构造问题,但它的核心技巧——用进位来排除某种等式——是一个非常有普遍性的思路。在组合数学中,'进位'经常是障碍:两个数相加时进位会破坏我们想要的性质。如果能构造一个集合,使得集合内任意两数相加'永远不进位',那么很多等式就不可能成立。This IMO 1983 Problem 5,看似 a pure construction problem, has a core technique—using carries to exclude certain equations—that is very general. In combinatorics, 'carries' are often the obstacle: when two numbers add, carries破坏 properties we want. If we can construct a set where any two elements 'never carry' when added, many equations become impossible.

三进制下的'只含 0 和 1'的数,正是这样一个集合。它的精妙之处在于:不是通过'限制元素的数量'来避免等差数列,而是通过'限制元素的表示方式'来从结构上排除可能性。这是一种更深层的数学思维——不是'有多少',而是'长什么样'。The set of numbers containing only 0s and 1s in ternary is exactly such a set. Its elegance lies in: not avoiding APs by 'limiting the number of elements,' but by 'limiting the representation' to structurally exclude possibilities. This is deeper mathematical thinking—not 'how many,' but 'what does it look like.'

Lean 形式化的价值在于,它迫使这个构造的每一步都精确到 digit 级别。手工证明中我们可以说'显然不会进位',但 Lean 要求你证明 $x + z$ 的每个 digit 确实不等于 $2y$ 的对应 digit。这种精确性不是为了炫技,而是为了确保'直觉'没有遗漏任何边界情况。The value of Lean formalization is that it forces every step of this construction to be precise to the digit level. In a handwritten proof we can say 'obviously no carry,' but Lean requires you to prove that each digit of $x + z$ indeed doesn't equal the corresponding digit of $2y$. This precision isn't showing off—it's ensuring 'intuition' hasn't missed any edge case.

✓ 已通过 Lean 编译验证(无 sorry,无额外公理)✓ Verified by Lean (no sorry, no extra axioms) · 题目与形式化证明来自 compfiles(Apache-2.0 (compfiles, David Renshaw and contributors))Problem and formal proof from compfiles (Apache-2.0 (compfiles, David Renshaw and contributors)) · Lean v4.35.0-rc3 · Mathlib dd56d02

程序员随想Programmer Reflections

哲学与生活Philosophy and Life

工具角Tools Corner