将周长为 $24$ 的圆周等分成 $24$ 段，从 $24$ 个分点中选取 $8$ 个点，使得其中任何两点间所夹的弧长都不等于 $3$ 和 $8$．问满足要求的 $8$ 点组的不同取法共有多少种？说明理由．
【难度】
【出处】
2001第16届CMO试题
【标注】
【答案】
略
【解析】
解法一
将 $24$ 个分点依次编号 $1,2, \cdots,24$，并将它们按“坏的关系”排成如下的 $3\times 8$ 数表
$1,4,7,10,13,16,19,22$
$9,12,15,18,21,24,3,6$
$17,20,23,2,5,8,11,14$
易见，表中每行中相邻两数所代表的两个分点间所夹的弧长为 $3$，每列相邻两数所代表的两个分点间所夹的弧长都是 $8$（首尾两数也算作相邻）．这样一来，题中对所取 $8$ 点的要求化为要求所取 $8$ 点的号码在数表中互不相邻．所以每列恰取 $1$ 个数，每行至多 $4$ 个互不相邻的数．从而，$3$ 行数中分别取数的个数只有 $ 4$ 种不同情形 $\{4,4,0\},\{4,3,1\},\{4,2,2\},\{3,3,2\}$．
（1）$\{4,4,0\}$．在 $ 3$ 行中任取一行不取数，有 $3$ 种不同取法．另两行中第一行取 $4$ 个互不相邻的数，有两种不同取法．余下 $4$ 列为另一行所取 $4$ 个数所在的列，唯一确定．由乘法原理知，这种情形共有 $6$ 种不同取法．
（2）$\{4,3,1\}$．在 $3$ 行中取数的个数分别为 $4,3,1$，共有 $3! = 6$ 种不同安排．在一行中取 $4$ 个互不相邻的数，有两种不同取法．在 另一行和余下 $4$ 列中选 $ 1$ 个数，有 $4$ 种不同选法．最后第 $3$ 行从余 下 $3$ 列中各选 $1$ 个数，选法唯一确定．由乘法原理知，这时共有 $6\times 2\times 4=48$ 种不同选法．
（3）$\{4,2,2\}$．从 $3$ 行中选定一行取 $4$ 个不相邻的数，选行有 $3$ 种不同，取数有两种不同，共有 $6$ 种不同取法．余下 $4$ 列互不相邻．第 $2$ 行从 $4$ 列中任取 $2$ 列，共有 $C_{4}^{2}=6$ 种不同取法．由乘法原理知，这种情形共有 $6\times 6=36 $ 种不同取法．
（4）$\{3,3,2\}$．从 $3$ 行数中选定一行取 $2$ 个不相邻的数，选行有 $3$ 种不同，选数 $C_{7}^{2}-1=20$ 种不同（其中减 $1$ 是去掉两个数分别在第 $1$ 列与第 $ 8$ 列的 $1 $ 种）．
选定两数之后，余下 $ 6$ 列被分成两部分，有 $3$ 种不同分段情形：$\{1,5\},\{2,4\}$ 和 $\{3,3\}$．$3$ 种分段的种数分别为 $8,8,4$．容易看出
（i）对于 $\{1,5\}$ 分段，取 $3$ 列互不相邻，有两种不同取法；
（ii）对于 $\{2,4\}$ 分段，取 $3$ 列互不相邻，有 $4$ 种不同取法；
（iii）对于 $\{3,3\}$ 分段，取 $3$ 列互不相邻，有两种不同取法．
所以这种情形的不同取法种数为 $3 \times\{8 \times 2+8 \times 4+4 \times 2\}=168$
综上可知：满足题中要求的不同取法种数为 $6+48+36+168=258$
解法二
同在解法 $1$ 中一样，将 $24$ 个数写成 $3\times 8$ 数表，于是，选取 $8$ 个数时每列恰取 $1$ 个数，这时，从第 $1$ 列取 $1$ 个数，共有 $3 $ 种不同取法．第 $1$ 列取定后，第 $2$ 列所取的数不能与第 $1$ 列所取的数同行，故只有两种不同取法．以后每列都有两种不同取法，共有 $3\times 2^7$ 种不同取法但其中第 $1$ 列所取的数与第 $8$ 列所取的数同行的所有取法都不满足要求．
若记从 $3 \times n$ 数表中每列恰取一个数且任何相邻两列（包括第 $n$ 列与第 $1$ 列）所取的数都不同行的不同取法种数为 $x_n$，则上述的结论恰为 $x_{8}+x_{7}=3 \times 2^{7}$ 类似地可以得到 $x_{n}+x_{n-1}=3 \times 2^{n-1}$ 由此递推，即得
$\begin{aligned} x_{8}= 3 \times 2^{7}-x_{7}= 3 \times 2^{7}-\left(3 \times 2^{6}-x_{6}\right)= 3 \times\left(2^{7}-2^{6}\right)+x_{6}=\cdots= 3 \times\left(2^{7}-2^{6}+2^{5}-2^{4}+2^{3}-2^{2}+2\right)= 3 \times 86=258 \end{aligned}$
即满足题中要求的不同取法种数为 $258$．
将 $24$ 个分点依次编号 $1,2, \cdots,24$，并将它们按“坏的关系”排成如下的 $3\times 8$ 数表
$1,4,7,10,13,16,19,22$
$9,12,15,18,21,24,3,6$
$17,20,23,2,5,8,11,14$
易见，表中每行中相邻两数所代表的两个分点间所夹的弧长为 $3$，每列相邻两数所代表的两个分点间所夹的弧长都是 $8$（首尾两数也算作相邻）．这样一来，题中对所取 $8$ 点的要求化为要求所取 $8$ 点的号码在数表中互不相邻．所以每列恰取 $1$ 个数，每行至多 $4$ 个互不相邻的数．从而，$3$ 行数中分别取数的个数只有 $ 4$ 种不同情形 $\{4,4,0\},\{4,3,1\},\{4,2,2\},\{3,3,2\}$．
（1）$\{4,4,0\}$．在 $ 3$ 行中任取一行不取数，有 $3$ 种不同取法．另两行中第一行取 $4$ 个互不相邻的数，有两种不同取法．余下 $4$ 列为另一行所取 $4$ 个数所在的列，唯一确定．由乘法原理知，这种情形共有 $6$ 种不同取法．
（2）$\{4,3,1\}$．在 $3$ 行中取数的个数分别为 $4,3,1$，共有 $3! = 6$ 种不同安排．在一行中取 $4$ 个互不相邻的数，有两种不同取法．在 另一行和余下 $4$ 列中选 $ 1$ 个数，有 $4$ 种不同选法．最后第 $3$ 行从余 下 $3$ 列中各选 $1$ 个数，选法唯一确定．由乘法原理知，这时共有 $6\times 2\times 4=48$ 种不同选法．
（3）$\{4,2,2\}$．从 $3$ 行中选定一行取 $4$ 个不相邻的数，选行有 $3$ 种不同，取数有两种不同，共有 $6$ 种不同取法．余下 $4$ 列互不相邻．第 $2$ 行从 $4$ 列中任取 $2$ 列，共有 $C_{4}^{2}=6$ 种不同取法．由乘法原理知，这种情形共有 $6\times 6=36 $ 种不同取法．
（4）$\{3,3,2\}$．从 $3$ 行数中选定一行取 $2$ 个不相邻的数，选行有 $3$ 种不同，选数 $C_{7}^{2}-1=20$ 种不同（其中减 $1$ 是去掉两个数分别在第 $1$ 列与第 $ 8$ 列的 $1 $ 种）．
选定两数之后，余下 $ 6$ 列被分成两部分，有 $3$ 种不同分段情形：$\{1,5\},\{2,4\}$ 和 $\{3,3\}$．$3$ 种分段的种数分别为 $8,8,4$．容易看出
（i）对于 $\{1,5\}$ 分段，取 $3$ 列互不相邻，有两种不同取法；
（ii）对于 $\{2,4\}$ 分段，取 $3$ 列互不相邻，有 $4$ 种不同取法；
（iii）对于 $\{3,3\}$ 分段，取 $3$ 列互不相邻，有两种不同取法．
所以这种情形的不同取法种数为 $3 \times\{8 \times 2+8 \times 4+4 \times 2\}=168$
综上可知：满足题中要求的不同取法种数为 $6+48+36+168=258$
解法二
同在解法 $1$ 中一样，将 $24$ 个数写成 $3\times 8$ 数表，于是，选取 $8$ 个数时每列恰取 $1$ 个数，这时，从第 $1$ 列取 $1$ 个数，共有 $3 $ 种不同取法．第 $1$ 列取定后，第 $2$ 列所取的数不能与第 $1$ 列所取的数同行，故只有两种不同取法．以后每列都有两种不同取法，共有 $3\times 2^7$ 种不同取法但其中第 $1$ 列所取的数与第 $8$ 列所取的数同行的所有取法都不满足要求．
若记从 $3 \times n$ 数表中每列恰取一个数且任何相邻两列（包括第 $n$ 列与第 $1$ 列）所取的数都不同行的不同取法种数为 $x_n$，则上述的结论恰为 $x_{8}+x_{7}=3 \times 2^{7}$ 类似地可以得到 $x_{n}+x_{n-1}=3 \times 2^{n-1}$ 由此递推，即得
$\begin{aligned} x_{8}= 3 \times 2^{7}-x_{7}= 3 \times 2^{7}-\left(3 \times 2^{6}-x_{6}\right)= 3 \times\left(2^{7}-2^{6}\right)+x_{6}=\cdots= 3 \times\left(2^{7}-2^{6}+2^{5}-2^{4}+2^{3}-2^{2}+2\right)= 3 \times 86=258 \end{aligned}$
即满足题中要求的不同取法种数为 $258$．
答案
解析
备注
