第一题【五年级】:信封与信的错放问题
难度等级:华罗庚金杯 预选赛
题目
小明写了 $5$ 封信,分别对应 $5$ 个不同的信封。他把信随机塞进信封(每个信封恰好塞一封),结果没有一封信塞对了信封。
(1) 这样的塞法共有多少种?
(2) 若规定第 $1$ 封信不能放在第 $1$ 个信封,第 $2$ 封信不能放在第 $2$ 个信封(其余无限制),共有多少种塞法?
(3) 进阶:若恰好有 $2$ 封信塞对了信封,其余 $3$ 封均未塞对,共有多少种塞法?
解题过程
第 (1) 题:全错位排列
设 $5$ 封信的全错位排列数为 $D_5$。
利用容斥原理推导:设 $A_i$ 为第 $i$ 封信放对信封的排列集合,则
\[D_5 = 5! - \lvert A_1 \cup A_2 \cup A_3 \cup A_4 \cup A_5 \rvert\]由容斥原理:
\[\lvert A_1 \cup \cdots \cup A_5 \rvert = \binom{5}{1}4! - \binom{5}{2}3! + \binom{5}{3}2! - \binom{5}{4}1! + \binom{5}{5}0!\] \[= 5 \cdot 24 - 10 \cdot 6 + 10 \cdot 2 - 5 \cdot 1 + 1 \cdot 1 = 120 - 60 + 20 - 5 + 1 = 76\]因此
\[D_5 = 120 - 76 = \boxed{44}\]验证递推公式:$D_n = (n-1)(D_{n-1} + D_{n-2})$
\[D_1=0,\; D_2=1,\; D_3=2,\; D_4=9,\; D_5=44 \checkmark\]第 (2) 题:部分限制排列
此时只限制第 $1$、$2$ 封信的位置,其余 $3$ 封无限制,求满足”第1封不在位1,第2封不在位2”的排列总数。
设 $A_1$:第1封在位1,$A_2$:第2封在位2,利用容斥原理:
\[N = 5! - \lvert A_1 \rvert - \lvert A_2 \rvert + \lvert A_1 \cap A_2 \rvert\] \[= 120 - 4! - 4! + 3! = 120 - 24 - 24 + 6 = \boxed{78}\]第 (3) 题:恰好 $2$ 封信塞对
关键构造:先从 $5$ 封信中选 $2$ 封塞对,再让剩余 $3$ 封全部错位。
\[N = \binom{5}{2} \cdot D_3 = 10 \times 2 = \boxed{20}\]其中 $D_3 = 2$(3元素全错排只有 $(2,3,1)$ 和 $(3,1,2)$ 两种)。
竞赛思维总结:错位排列问题的核心是”容斥原理 + 递推”,第(3)问的分步计数乘法原理是竞赛中常见的将”混合条件”转化为”选择 + 全错排”的典型技巧。
知识背景
错位排列(Derangement)是组合数学的经典模型,由欧拉(Euler)在18世纪提出。$n$ 元素的全错位排列数 $D_n$ 满足:
\[D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}\]当 $n$ 较大时,$D_n \approx \dfrac{n!}{e}$($e \approx 2.718$),即随机排列恰好全部错位的概率约为 $\dfrac{1}{e} \approx 36.8\%$。这一结论来自泰勒展开,是分析组合学与概率论的交叉点,在华罗庚金杯和全国联赛中频繁以变形题出现。
第二题【初一】:格点多边形的面积——Pick 定理
难度等级:全国初中数学联赛 初赛
题目
在平面直角坐标系中,坐标均为整数的点称为格点。以 $A(1,1)$、$B(5,1)$、$C(2,4)$ 为顶点的三角形称为格点三角形。
(1) 不用坐标公式,仅通过数格点的方法,验证三角形 $ABC$ 的面积。
(2) 已知 Pick 定理:格点多边形面积 $S = I + \dfrac{B}{2} - 1$,其中 $I$ 为内部格点数,$B$ 为边界格点数。用 Pick 定理求 $\triangle ABC$ 的面积,并与 (1) 结果验证一致。
(3) 若在坐标平面中有一个格点凸四边形,其内部恰好有 $5$ 个格点,边界恰好有 $8$ 个格点,求该四边形的面积。
(4) 挑战:是否存在一个格点三角形,其面积等于 $\dfrac{3}{2}$,且内部没有格点?若存在,构造一个例子;若不存在,说明理由。
解题过程
第 (1) 题:割补法求面积
将 $\triangle ABC$($A(1,1)$,$B(5,1)$,$C(2,4)$)嵌入矩形 $[1,5]\times[1,4]$,面积为 $4 \times 3 = 12$。
减去三个直角三角形:
- $\triangle ABP$($P=(5,1)$ 已在 $B$,取辅助点):底边 $AB = 4$,高 = $0$,此边水平;
- 用外接矩形割补:
三个角三角形:
\[S_1 = \tfrac{1}{2} \cdot 1 \cdot 3 = \tfrac{3}{2} \quad (A\text{ 到 }C\text{ 竖直方向,底1高3})\] \[S_2 = \tfrac{1}{2} \cdot 3 \cdot 3 = \tfrac{9}{2} \quad (B\text{ 到 }C)\] \[S_3 = \tfrac{1}{2} \cdot 4 \cdot 0 \quad \text{(}AB\text{ 水平,不贡献)}\]重新用坐标面积公式(验证用):
\[S = \tfrac{1}{2}\lvert (x_A(y_B - y_C) + x_B(y_C - y_A) + x_C(y_A - y_B)) \rvert\] \[= \tfrac{1}{2}\lvert 1(1-4) + 5(4-1) + 2(1-1) \rvert = \tfrac{1}{2}\lvert -3 + 15 + 0 \rvert = \tfrac{12}{2} = \boxed{6}\]第 (2) 题:Pick 定理验证
统计 $\triangle ABC$ 的格点:
边界格点 $B$:
- 边 $AB$:从 $(1,1)$ 到 $(5,1)$,水平,格点数 $= \gcd(4,0) = 4$,含两端点共 $5$ 个,边上格点(不含端点)$= 3$ 个
- 边 $BC$:从 $(5,1)$ 到 $(2,4)$,$\Delta x = 3, \Delta y = 3$,$\gcd(3,3)=3$,边上格点(不含端点)$= 2$ 个
- 边 $CA$:从 $(2,4)$ 到 $(1,1)$,$\Delta x = 1, \Delta y = 3$,$\gcd(1,3)=1$,边上格点(不含端点)$= 0$ 个
内部格点 $I$:逐行检查 $y=2,3$:
- $y=2$:$x \in {2, 3, 4}$ 在三角形内,$I$ 贡献 $2$($x=2,3$,$x=4$ 在 $BC$ 线上需验证)。精确检查边 $BC$:过 $(5,1)(2,4)$,方程 $x = 5 - t, y = 1 + t$,当 $y=2$ 时 $t=1, x=4$——即 $(4,2)$ 在边 $BC$ 上(边界点)。故内部点为 $(2,2),(3,2)$,贡献 $2$。
- $y=3$:边 $BC$ 在 $y=3$ 时 $x=3$,边 $CA$ 在 $y=3$ 时:过 $(2,4)(1,1)$,斜率 $3$,$x = 2 - \tfrac{1}{3}(4-3) = \tfrac{5}{3}$,故内部整数 $x$ 需 $\tfrac{5}{3} < x < 3$,即 $x=2$,贡献 $1$。
Pick 定理:
\[S = I + \tfrac{B}{2} - 1 = 3 + \tfrac{8}{2} - 1 = 3 + 4 - 1 = \boxed{6} \checkmark\]第 (3) 题:凸四边形面积
已知 $I = 5$,$B = 8$,由 Pick 定理直接得:
\[S = 5 + \tfrac{8}{2} - 1 = 5 + 4 - 1 = \boxed{8}\]第 (4) 题:面积为 $\tfrac{3}{2}$,无内部格点
由 Pick 定理,若 $I = 0$,则 $S = \tfrac{B}{2} - 1$,要使 $S = \tfrac{3}{2}$:
\[\tfrac{B}{2} - 1 = \tfrac{3}{2} \implies B = 5\]即需要找一个格点三角形,边界恰好有 $5$ 个格点(含三顶点),内部无格点。
构造:取 $A(0,0)$,$B(3,0)$,$C(0,1)$。
- 边 $AB$:$\gcd(3,0)=3$,边界点(不含端)$= 2$ 个:$(1,0),(2,0)$
- 边 $BC$:$\gcd(3,1)=1$,边界点(不含端)$= 0$ 个
- 边 $CA$:$\gcd(0,1)=1$,边界点(不含端)$= 0$ 个
验证内部无格点:三角形区域为 $x \geq 0, y \geq 0, x + 3y \leq 3$。唯一可能内部整数点 $(1,0),(2,0)$ 均在边上,故 $I = 0$。
\[S = \tfrac{1}{2} \cdot 3 \cdot 1 = \tfrac{3}{2} \checkmark\]答:存在,例如以 $(0,0),(3,0),(0,1)$ 为顶点的格点三角形满足条件。
知识背景
Pick 定理由奥地利数学家 Georg Pick 于 1899 年发现。该定理将几何量(面积)与数论量(格点计数)完美连接,是竞赛几何与组合数论的经典桥梁。其证明思路是:先对三角形证明(利用仿射变换化为标准三角形),再通过三角剖分推广到任意多边形。Pick 定理在全国初中联赛和 IMO 预选题中均有出现,特别是”构造特定格点图形”类问题,往往结合整除性和不等式综合考查。
评论