2011-江苏卷-23 解-同余分类计数

本题导读

本题考查排列与组合计数，以及同余与整除。

📌【题干】

Question

（2011年江苏卷） 设整数 $n⩾4$，$P(a,b)$ 是平面直角坐标系 $xOy$ 中的点，其中 $a$，$b\in \{1,2,3,\cdots ,n\}$，$a>b$.

(1) 记 $A_n$ 为满足 $a-b=3$ 的点 $P$ 的个数，求 $A_n$；

(2) 记 $B_n$ 为满足 $\frac{1}{3}(a-b)$ 是整数的点 $P$ 的个数，求 $B_n$.

🔍【思路分析】

破题导航

1. 步骤1：(1) 由 $a=b+3$ 直接定 $b$ 的范围
2. 步骤2：(2) 令 $a-b=3k$
3. 步骤3：对 $k$ 求和后按 $n$ 模 $3$ 的余数分类

✅【答案】

点击查看答案

(1) $A_n=n-3$

(2) $B_n=\{\begin{array}{ll}\frac{n(n-3)}{6},& 3\mid n,\\ \frac{(n-1)(n-2)}{6},& 3\nmid n.\end{array}$

✍【详细解析】

Abstract

（1）当 $a-b=3$ 时，$b=a-3$。由 $1⩽b⩽n$ 及 $1⩽a⩽n$，得 $1⩽b⩽n-3$。

每个符合条件的 $b$ 唯一对应点 $P(b+3,b)$，故 $A_n=n-3$。

（2）因为 $a>b$，$\frac{1}{3}(a-b)$ 为整数当且仅当存在正整数 $k$，使 $a-b=3k$。

对固定的 $k$，$b=a-3k$，且 $1⩽b⩽n-3k$，所以满足条件的点有 $n-3k$ 个。

令 $m=\lfloor \frac{n-1}{3}\rfloor$，则 $1⩽k⩽m$，从而

$B_n=\sum _{k=1}^m(n-3k)=mn-\frac{3m(m+1)}{2}$。

① 若 $3\mid n$，记 $n=3q$，则 $m=q-1$，代入得

$B_n=\frac{n(n-3)}{6}$。

② 若 $3\nmid n$，则 $n=3q+1$ 或 $n=3q+2$，两种情形代入上式均得

$B_n=\frac{(n-1)(n-2)}{6}$。

综上，$B_n=\{\begin{array}{ll}\frac{n(n-3)}{6},& 3\mid n,\\ \frac{(n-1)(n-2)}{6},& 3\nmid n.\end{array}$

💡【考点归纳与避坑指南】

Danger

核心考点：整除与同余；组合计数模型；带余除法下的分类求和

核心方法：令差为 $3k$ 按步长分类，每个 $k$ 的点数为 $n-3k$，再用等差求和与带余除法收口

避坑指南：必须对 $n$ 模 $3$ 的余数分类，只按某一种特殊情形计算会漏解；$m=\lfloor \frac{n-1}{3}\rfloor$ 的上界来源是 $b⩾1$，写成 $\lfloor \frac{n}{3}\rfloor$ 会在 $n=3q$ 时多算一类。

📖【试题探源与推广】

Tip

试题探源：同余计数与分类求和题，与 2012 年江苏卷第 23 题、2013 年江苏卷第 23 题同族。

结论推广：对任意正整数 $p$，满足 $a\equiv b(\mathrm{mod}p)$（$1⩽b<a⩽n$）的点数为 $\sum _{i=0}^{p-1}\left(\genfrac{}{}{0ex}{}{n_i}{2}\right)$（$n_i$ 为各剩余类的元素个数），与本解法的求和式一致。

方法推广：计数题先找”差为定值的步长结构”，把个数写成关于步长的等差式求和，最后按除数余数分类化简并核对首例（如 $n=4$ 时 $B_4=1$）。

🔗【关联脉络】

Multi column

知识锚点 (Nodes)

• 22.01 计数原理、排列与组合

类题演练 (Links)

• 2012-江苏卷-23 解-集合计数与归纳推理