今日年级:六年级 + 初一
题目来源:Cut-The-Knot(Alexander Bogomolny 数学竞赛题库)
【初一】三角棋盘蚱蜢问题
难度: ⭐⭐⭐(中等,需要染色论证)
题目来源: 100 Grasshoppers on a Triangular Board
知识点: 染色法 · 组合计数 · 鸽巢原理
题目:
一个等边三角形被平行于三边的直线切割成 100 个小三角形格子($10 \times 10$ 三角网格)。相邻(共边)的两个格子互为邻格。最初,每个格子里恰好有一只蚱蜢。
所有蚱蜢同时跳跃——每只蚱蜢跳到其中一个邻格。这样的集体跳跃共进行 9 次。
证明:9 次跳跃结束后,至少有 10 个格子是空的。
解题过程
关键思路:双色染色
第一步:对格子染色
将三角网格按棋盘方式染成红色和棕色,使相邻格子颜色不同。
对于 $n \times n$ 的三角网格(本题 $n = 10$):
- 红色格子数 $= \dfrac{n(n+1)}{2} = \dfrac{10 \times 11}{2} = 55$ 个
- 棕色格子数 $= \dfrac{n(n-1)}{2} = \dfrac{10 \times 9}{2} = 45$ 个
第二步:分析跳跃规律
由于相邻格子颜色不同,每次跳跃时:
- 红色格子上的蚱蜢 → 只能跳到棕色格子
- 棕色格子上的蚱蜢 → 只能跳到红色格子
因此每次跳跃后,所有蚱蜢都换了颜色。
第三步:奇数次跳跃后分析
9 是奇数,所以 9 次跳跃后:
- 原来在红色格子上的 55 只蚱蜢,全部落在棕色格子上
- 棕色格子只有 45 个
由鸽巢原理,55 只蚱蜢占 45 个格子,至少有 10 个红色格子是空的:
\[\text{空格数} \geq 55 - 45 = 10\]结论:9 次(奇数次)跳跃后,至少有 10 个格子是空的。 $\blacksquare$
常见错误
- 忽略奇偶性:未严格利用”9 次为奇数”这一关键条件
- 混淆方向:蚱蜢可以任意选择邻格,而非都朝同一方向跳
知识背景
染色法(Coloring Method)是组合数学中的经典工具。通过将对象染成不同颜色,可以揭示隐藏的不变量或约束。这类方法在竞赛数学中极为常见,也是解决棋盘问题、路径问题的利器。
注意本题中的”9 次”是个障眼法(red herring)——任何奇数次跳跃后,结论都成立。
【六年级】三壶均分水
难度: ⭐⭐(中等,逻辑推理)
题目来源: Three Jugs - Equal Amounts
知识点: 逻辑推理 · 奇偶分析 · 归纳思想
题目:
有三个水壶,共装 $3 \times 2^n$ 品脱水($n$ 为正整数),每壶装整数品脱。
允许的操作:选择装水较多的壶 $A$ 和装水较少的壶 $B$,从 $A$ 向 $B$ 倒水,使 $B$ 中的水翻倍(即向 $B$ 倒入与 $B$ 现有水量相等的水)。
举例($n=2$,总量 12 品脱):初始三壶 $1, 5, 6$ 品脱:
- 从 5 品脱壶向 1 品脱壶倒 1 品脱 $\to (2, 4, 6)$
- 从 6 品脱壶向 2 品脱壶倒 2 品脱 $\to (4, 4, 4)$ ✓ 均分!
问题:除初始分配为 $(a, a, 2a)$ 的特殊情况外,证明总能通过若干次操作将水均分到三壶。
解题过程
目标:使三壶各含 $2^n$ 品脱水。
核心策略:消除奇数,递归化简
第一步:处理奇数情况
若三壶中有奇数品脱的壶,奇数壶必然成对出现(因为总量 $3 \times 2^n$ 是偶数)。
设两壶含奇数量 $a$,第三壶含偶数量 $b = 3 \times 2^n - 2a$。
- 若 $b > a$:从 $b$ 壶向 $a$ 壶倒,得 $(2a, a, b-a)$,奇数消除
- 若 $a > b$:从 $a$ 壶向 $b$ 壶倒,得 $(a, a-b, 2b)$,同样消除奇数
第二步:全为偶数后递归
当三壶都含偶数品脱时,将每壶除以 $2$,规约为 $n-1$ 层的同类问题,由归纳假设可以均分。
特殊情况说明:若初始为 $(a, a, 2a)$,则 $4a = 3 \times 2^n$,此时无论如何操作都无法均分。
常见错误
- 忘记证明不循环:需要论证操作序列必然终止,不会无限循环
- 混淆操作方向:操作是从水多壶向水少壶倒,不能反向
知识背景
这道题体现了 2 的幂在离散数学中的核心地位。每次将偶数壶的水量除以 2,本质上是在做二进制移位操作。类似的”倍增/减半”思想在计算机算法(如快速幂)中也大量使用。
归纳法的思路——”把大问题拆成小问题”——是初中数学和竞赛数学的核心方法之一。
评论