例 1 g5-c07-p02
题:在所有三位数中,各位数字之和等于 $12$ 的有多少个?
按规律解:按百位数字分类枚举。百位是 $1$ 时,十位加个位要等于 $11$,十位可取 $2\sim 9$(个位相应取 $9\sim 2$),共 $8$ 个;百位是 $2$ 时,后两位和为 $10$,十位取 $1\sim 9$ 共 $9$ 个;百位是 $3$ 时后两位和为 $9$,十位取 $0\sim 9$ 共 $10$ 个;之后百位每增大 $1$,后两位的和就减小 $1$,个数依次是 $9$、$8$、$7$、$6$、$5$、$4$。全部相加:$8+9+10+9+8+7+6+5+4=66$ 个。
为什么对:为什么按百位分类就不会重也不会漏?因为每个三位数的百位是唯一确定的,它必然恰好落进“百位是几”的某一类里,不会同时属于两类(不重),九类合起来又正好是全部三位数(不漏)。每一类里再让十位从小到大走一遍,个位被和锁死,所以类内也滴水不漏。
例 2 g5-c07-p08
题:把黑桃 A~$10$ 与红心 A~$10$ 配成 $10$ 对(A 当作 $1$),两张牌上数的乘积除以 $10$ 余 $1$,能配出几对?
按规律解:乘积除以 $10$ 余 $1$,意思就是乘积的末位(个位)是 $1$。先缩范围:只要有一个因数是偶数,乘积末位就是偶数,绝不可能是 $1$,所以两个数都得是奇数,候选只剩 $1,3,5,7,9$。再看这些奇数两两相乘的末位:$1\times 1=1$(末位 $1$,行)、$3\times 7=21$(末位 $1$,行)、$7\times 3=21$(行)、$9\times 9=81$(行),而带 $5$ 的相乘末位都是 $5$。所以符合的有 $4$ 对。
为什么对:为什么只看末位就够了?因为两个数乘积的末位,只由这两个数各自的末位决定,跟更高位无关。先用“偶数出局”这一刀把范围从 $10$ 个数砍到 $5$ 个奇数,剩下要试的组合就很少,挨个乘一下末位即可,既快又不会漏。
例 3 g5-c07-p19
题:把 $2\sim 9$ 这 $8$ 个数分成 $4$ 对,使每对的和都是质数,共有几种分法?
按规律解:先缩范围:两个数的和如果是大于 $2$ 的质数,必是奇数,而奇数只能由“一奇加一偶”得到,所以每一对都必须一奇一偶。再从最小的数 $2$ 入手分类:能和 $2$ 配成质数的有 $3,5,9$(和为 $5,7,11$)。(a) $2$ 配 $3$:剩下最小是 $4$,$4$ 能配 $7$ 或 $9$,每种再往下定都唯一,得 $2$ 种;(b) $2$ 配 $5$:剩下最小是 $3$,$3$ 配 $4$ 或 $8$,得 $2$ 种;(c) $2$ 配 $9$:剩下最小是 $3$,$3$ 配 $4$ 或 $8$,得 $2$ 种。合计 $2+2+2=6$ 种。
为什么对:为什么总从“当前最小的数”开始定?因为最小的数选择最少、最好控制,先把它钉死,剩下的局面立刻变小。这样一层层往下,每一步都只剩很少几种走法,分支清清楚楚,既不会把同一种分法从不同顺序数两遍,也不会漏掉任何一支。
例 4 g5-c07-p21
题:满足 $\dfrac{1}{a}+\dfrac{1}{b}+\dfrac{1}{c}=\dfrac{3}{4}$ 的整数 $a,b,c$ 能组成多少个不同的有序数组 $(a,b,c)$?
按规律解:先用缩放卡范围:不妨设 $a\le b\le c$,那么 $\dfrac{1}{a}$ 是三个分数里最大的,三个加起来是 $\dfrac34$,所以 $\dfrac{3}{a}\ge\dfrac34$,得 $a\le 4$。逐一枚举 $a$:$a=4$ 时 $b=c=4$;$a=3$ 时解出 $(3,4,6)$ 和 $(3,3,12)$;$a=2$ 时解出 $(2,8,8)$、$(2,6,12)$、$(2,5,20)$。这些是“从小到大”的无序解,最后还原成有序数组:三个都不同(如 $2,6,12$)有 $6$ 种排法,恰有两个相同(如 $4,4,4$ 之外的 $3,3,12$、$2,8,8$)有 $3$ 种排法,三个全同($4,4,4$)有 $1$ 种。合计 $1+3+3+3+6+6=25$ 个。
为什么对:为什么先假设 $a\le b\le c$ 再放缩?因为不加约束直接枚举三个变量会乱成一团、还会重复。设了大小顺序后,最大的分数 $\dfrac1a$ 至少要扛起平均的份额,立刻把 $a$ 锁在 $4$ 以内,枚举量瞬间变小;先求出“无序的骨架解”,最后再按相同数字的个数补回排列数,就能不重不漏地数清所有有序数组。