黑白棋取法问题
桌子上现有 3 枚黑棋子和 3 枚白棋子, 小洁要分若干次把它们取走. 她每次可以取一种颜色的若干枚棋子, 或者取两种颜色的相同个数的棋子.
那么她有多少种不同的方法将这些棋子取完. （相同颜色的棋子不作区分）
[Hint] 可以先考虑 2 枚黑棋子和 2 枚白棋子的情况, 此时有 22 种取法.
对于 $m$ 枚黑棋子和 $m$ 枚白棋子, 记取法数是 $f(m)$.
尝试证明 $f(4)=1712$. 并思考能否用计算机计算这个问题.
Answer
问题及解答
1
一般的方法是采用组合计数. 这里我们改用方程求解的办法. 当然本质上还是组合. 这个方法有很大的复杂性.
先考虑 2 枚黑棋子和 2 枚白棋子的情况. 记黑棋为 +1, 白棋为 -1. 这样记是为了计算的方便.
记号: x=[-1,1] 表示一次取白棋一个, 黑棋一个, 此时所取的数量是其中数的绝对值之和, |x|=|[-1,1]|=1+1=2.
(1) 分四次取完
考虑方程
\[
\begin{cases}
x+y+z+w=0,\\
|x|+|y|+|z|+|w|=4,\\
x,y,z,w=\pm 1.
\end{cases}
\]
此方程中 $x,y,z,w$ 中 +1 和 -1 的个数必定相等. 因此有 $C_4^2=6$ 个解.
(2) 分三次取完
\[
\begin{cases}
x+y+z=0,\\
|x|+|y|+|z|=4,\\
x,y,z=0, \pm 1, \pm 2.
\end{cases}
\]
(2.a) 设 $x,y,z\neq 0$. 则至少有一个是 2 或 -2. 比如 $(1,1,-2)$, $(-1,-1,2)$. 根据 2 或 -2 的位置, 分别有 3 个解, 故有 6 个解.
(2.b) 设 $x,y,z$ 中有一个是 0. 由于要分三次取完, 因此, 这个 0 意味着只能是 [+1,-1] (即一个黑棋一个白棋一起拿, 我们用[] 表示一次取的). 不妨设 $z=0$, 于是方程退化为
\[
\begin{cases}
x+y=0,\\
|x|+|y|=2,\\
x,y=\pm 1.
\end{cases}
\]
此方程中 1,-1 的个数必定相等, 所以有 2 个解. 加上也可以是 $x=0$ 或 $y=0$, 并且 [+1], [-1], [+1,-1] 彼此不同, 故有 6 个解.
(3) 分两次取完
\[
\begin{cases}
x+y=0,\\
|x|+|y|=4,\\
x,y,z=0, \pm 2.
\end{cases}
\]
注意此时 $x,y$ 不可能取 $\pm 1$. 因此, 显然只有 [2,-2], [-2,2], [0,0] 三个解.
(4) 分一次取完
\[
\begin{cases}
x=0,\\
|x|=4,\\
\end{cases}
\]
显然只有一个解 [2,-2]
因此, 我们汇总如下
按取的次数取完 取法
| 拿i次取完 | 取法个数 |
| 4 | 6 |
| 3 | 12 |
| 2 | 3 |
| 1 | 1 |
| 总计 | 22 |
2
对于 3 枚黑棋子和 3 枚白棋子的情况, 按分 $k$ 次取完进行讨论. 这里 $k=6,5,4,3,2,1$.
(1) 分六次取完
考虑方程
\[
\begin{cases}
x_1+x_2+x_3+x_4+x_5+x_6=0,\\
\sum_{i=1}^{6}|x_i|=6,\\
x_i=\pm 1.
\end{cases}
\]
这里必定有三个 +1, 三个 -1. 位置不同, 所表示的解可能就不同. 只要在这六个未知量中选择三个命之为 +1, 则剩下的只能是 -1. 反之, 若将选中的三个未知量定为 -1, 则剩余三个一定是 +1. 因此共有 $C_6^3=20$ 个解.
(当然, 这20个解可以详细写出来)
(2) 分五次取完
考虑方程
\[
\begin{cases}
x_1+x_2+x_3+x_4+x_5=0,\\
\sum_{i=1}^{5}|x_i|=6,\\
x_i=0, \pm 1, \pm 2.
\end{cases}
\]
此时任意 $x_i\neq\pm 3$, 因为需要分五次拿完.
分两种情况
(2.a) 存在某个 $x_j=0$. 不妨设 $x_5=0$, 也即 $x_5=[1,-1]$ (注意不可能 $x_5=[2,-2]$).
于是方程化为
\[
\begin{cases}
x_1+x_2+x_3+x_4=0,\\
\sum_{i=1}^{4}|x_i|=4,\\
x_i=\pm 1.
\end{cases}
\]
注意到 $x_i\neq 0$, 因为如果有某个 $x_j=0=[1,-1]$, 则不可能达到四次取完.
这个方程已经在上面（黑棋2个白棋2个）情况中计算, 共有 6 个解. 注意到 $x_5=[1,-1]$ 与 $x_i,i=1,2,3,4$ 都不同, 因此(2.a)总共有 $5\times 6=30$ 个解.
(2.b) 任何 $x_i\neq 0$. 则必存在某个 $x_j=\pm 2$. 不放假设 $x_5=2$, 则方程变为
\[
\begin{cases}
x_1+x_2+x_3+x_4=-2,\\
\sum_{i=1}^{4}|x_i|=4,\\
x_i=\pm 1.
\end{cases}
\]
显然这里 $x_i$ 不可能为 $\pm 2$. 此方程的解形如 ([-1],[-1],[-1],[+1]), 故有 4 个解. 类似的, 如果 $x_5=-2$, 则方程的解形如 ([+1],[+1],[+1],[-1]), 也有相应的 4 个解. 加上 $x_5=\pm$ 不同于这里的 $\pm 1$.
因此 (2) 共有 $(4+4)\times 5=40$ 个解.
(3) 分四次取完
考虑方程
\[
\begin{cases}
x_1+x_2+x_3+x_4=0,\\
\sum_{i=1}^{4}|x_i|=6,\\
x_i=0, \pm 1, \pm 2, \pm 3.
\end{cases}
\]
(3.a) 若存在某个 $x_j=0$, 不放设 $x_4=0$, 即 $x_4=[1,-1]$(不可能是 $[2,-2]$), 则方程化为
\[
\begin{cases}
x_1+x_2+x_3=0,\\
\sum_{i=1}^{4}|x_i|=4,\\
x_i=0, \pm 1, \pm 2.
\end{cases}
\]
此方程在 $m=2$(黑棋白棋个数均为 2) 时已经计算, 共 12 个解.
但要结合这里的情况, 不能直接得出 (3.a) 有 $12\times 4=48$ 个解.
事实上, $m=2$ 时, 此方程的解形如 ([-1], [-1], [1,1]) 或 ([1],[1],[-1,-1]) 的排列, 其中的元素与 [1,-1] 不同, 因此有 $6\times 4=24$ 个解.
另一方面还有形如 ([1,-1],[1],[-1]) 的解, 其中有个元素与这里的 $x_4=[1,-1]$ 相同, 因此相应的有 $6\times 2=12$ 个解.
总之 (3.a) 有 $24+12=36$ 个解.
-------------------------------------
(3.b) 任意 $x_i\neq 0$. 则方程变为
\[
\begin{cases}
x_1+x_2+x_3+x_4=0,\\
\sum_{i=1}^{4}|x_i|=6,\\
x_i=\pm 1, \pm 2, \pm 3.
\end{cases}
\]
含有 $\pm 3$ 的解形如 $([1],[1],[1],[-3])$ 或 $([-1],[-1],[-1],[3])$. 小计 $4+4=8$ 个解.
不含有 $3$ 的方程形如
\[
\begin{cases}
x_1+x_2+x_3+x_4=0,\\
\sum_{i=1}^{4}|x_i|=6,\\
x_i=\pm 1, \pm 2.
\end{cases}
\]
于是, 此方程中必有 +2, 和 -2. 于是解形如 ([1],[-1],[1,1],[-1,-1]) , 元素各不相同, 故有 $P_4=4\times 3\times 2\times 1=24$ 个解. 于是 (3.b) 共有 $8+24=32$ 个解.
(3) 共计有 $36+32=68$ 个解.
(4) 分三次取完
考虑方程
\[
\begin{cases}
x_1+x_2+x_3=0,\\
\sum_{i=1}^{3}|x_i|=6,\\
x_i=0, \pm 1, \pm 2, \pm 3.
\end{cases}
\]
(4.a) 若存在某个 $x_j=0$, 不妨设 $x_3=0=[1,-1]$ 或 $[2,-2]$. 则
\[
\begin{cases}
x_1+x_2=0,\\
\sum_{i=1}^{2}|x_i|=4 or 2,\\
x_i=0, \pm 1, \pm 2.
\end{cases}
\]
如果 $\sum_{i=1}^{2}|x_i|=4$, 则推出 $(0,0)$, $(2,-2)$, $(-2,2)$. 对应到 $(x_1,x_2,x_3)$ 为
$(0,0,0)$ 一个解; $(2,-2,[1,-1])$ 6 个解; $([2,-2],[1],[-1])$ 6 个解.
小计 (4.a) 有 $13$ 个解.
---------------------------
(4.b) 任意 $x_i\neq 0$. 方程变为
\[
\begin{cases}
x_1+x_2+x_3=0,\\
\sum_{i=1}^{3}|x_i|=6,\\
x_i=\pm 1, \pm 2, \pm 3.
\end{cases}
\]
显然 $|x_i|$ 中不可能出现两个 1, 或两个 2, 或两个 3. 因此只可能是 $([1],[2], [-3])$ 或 $([-1],[-2],[3])$. 于是有 $6\times 2=12$ 个解.
因此, (4) 有 $13+12=25$ 个解.
(5) 分两次取完
考虑方程
\[
\begin{cases}
x_1+x_2=0,\\
\sum_{i=1}^{2}|x_i|=6,\\
x_i=0, \pm 3.
\end{cases}
\]
(5.a) 若某个 $x_j=0$, 不放假设 $x_2=0=[1,-1]$ 或 $[2,-2]$. 于是方程化为 $x_1=0$. 于是解为
$([1,-1],[2,-2])$, $([2,-2],[1,-1])$. 共两个解.
(5.b) 若任意 $x_i\neq 0$. 则方程化为
\[
\begin{cases}
x_1+x_2=0,\\
\sum_{i=1}^{2}|x_i|=6,\\
x_i=\pm 3.
\end{cases}
\]
于是方程有两个解 $(3,-3)$ 和 $(-3,3)$.
(5) 共有 4 个解.
(6) 分一次取完.
方程为 $x_1=0$. 显然解只有一个. 为 $([1,1,1,-1,-1,-1])$.
综上所述, 我们得到总的取法数是 188 种.
按取的次数取完 取法
| 拿i次取完 | 取法个数 |
| 6 | 20 |
| 5 | 70 |
| 4 | 68 |
| 3 | 25 |
| 2 | 4 |
| 1 | 1 |
| 总计 | 188 |