|
冯跃峰 本文提出如下一个有趣的 三色棋搏弈问题：桌面上有三种不同颜色的棋子，各种颜色的棋子分别有t、m、n只，其中t、m、n是给定的不全为零的自然数，满足t≤m≤n，两个人轮流在桌面上取棋子，规定每次只能取一种颜色的棋子，且至少取出一只棋子，取得的棋子不再放回，规定取得最后一只棋子者为输，问谁有必胜策略? 本问题有相当的难度，我们得到了它的一种解法，但其过程很繁，期盼读者能找到它的一个简单解法。 用（t，m，n）表示三种颜色的棋子分别有t、m、n只的状态，称先走者有必胜策略的状态为胜局，后走者有必胜策略的状态为负局。 先解决t≤1的特殊情形，有如下的结论： 定理1：对于三色棋搏弈问题（t，m，n）（t≤m≤n），当t≤1时，状态（t，m，n）（t≤m≤n，t≤1）中只有（0，0，1）、（0，n，n）（n>1）、（1，1，1）和（1，2k，2k+1）（k∈N）是负局，其余都是胜局。 证明：分两种情况讨论。 （1）当t=0时，状态（t，m，n）（t≤m≤n，t≤1）=（0，m，n）（m≤n）。 若m=0、1，则（0，0，1）显然是负局。 （0，0，n）（n>1）是胜局，因为将n变成1便得到上述负局。 （0，1，n）（n≥1）是胜局，因为将n变成0便得到上述负局。 若m>1，可以证明A=（0，n，n）（n>1）是负局。 实际上，不妨设甲将A中一个n变成a（a<n），得到状态B=（0，a，n）（n>1）。 当a=0时，B=（0，0，n）（n>1）是胜局； 当a=1时，B=（0，1，n）（n>1）是胜局； 而a>1时，乙可对B=（0，a，n）（n>1）操作，使n变成a（a<n），得到状态C=（0，a，a）（a>1），C与A=（0，n，n）（n>1）是同类型状态，如此下去，乙胜，所以A=（0，n，n）（n>1）是负局。 此外，（0，m，n）（1<m<n）是胜局，因为操作可将n变成m，得到的状态B=（0，m，m）（m>1）是负局。 综上所述，当t=0时，只有（0，0，1）、（0，n，n）（n>1）是负局，其余都是胜局。 （2）当t=1时，初始状态为（1，m，n）（1≤m≤n）。 若m=1，则显然（1，1，1）是负局，因为它操作后只能得到胜局（0，1，1）。 （1，1，n）（n>1）是胜局，因为将n变成1得到负局。 若m>1，则（1，n，n）（n>1）是胜局，因为将1变成0得到负局。 此外，考察状态（1，m，n）（1<m<n），我们证明如下的 引理：对一切正整数k，有（1，2k，2k+1）为负局，而（1，2k，n）（n>2k+1）、（1，m，n）（1<m<n，1<m<2k，且m为偶数时，n-m≥2）都是胜局。 对k归纳，当k=1时，（1，2k，2k+1）=（1，2，3），操作一次只能得到（0，2，3），（1，1，3），（1，0，3），（1，2，2），（1，2，1），（1，2，0），其中除（1，2，2）外都是已证的胜局，而（1，2，2）可操作到负局（0，2，2），所以（1，2，2）也是胜局，所以（1，2，3）是负局。 对于状态（1，2，n）（n>3），将n变成3，得到负局（1，2，3），所以（1，2，n）（n>3）是胜局。 对于状态（1，m，n）（1<m<n，1<m<2），只能是（1，1，n）（n>1），将n变成1，得到负局（1，1，1），所以（1，1，n）（n>1）是胜局。 所以k=1时结论成立。 设结论对小于k的正整数成立，考虑k的情形。 对于状态（1，2k，2k+1），如果操作T（1，2k，2k+1）将1变成0，则得到胜局（0，2k，2k+1）； 如果操作T（1，2k，2k+1）将2k变成a（a<2k），得到状态（1，a，2k+1）。 当a=2k-1时，（1，a，2k+1）=（1，2k-1，2k+1），可操作一次，使之变成（1，2k-1，2k-2），由归纳假设，（1，2k-1，2k-2）是负局，所以（1，a，2k+1）是胜局； 当a=2k-2时，（1，a，2k+1）=（1，2k-2，2k+1），可操作一次，使之变成（1，2k-2，2k-1），由归纳假设，（1，2k-2，2k-1）是负局，所以（1，a，2k+1）是胜局； 当a<2k-2时，因为1< a<2k-2，由归纳假设，（1，a，2k+1）是胜局； 如果操作T（1，2k，2k+1）将2k+1变成b（b<2k+1），得到状态（1，2k，b）。 当b=2k时，（1，2k，b）=（1，2k，2k），可操作一次，使之变成负局（0，2k，2k），所以（1，2k，b）是胜局； 当b=2k-1时，（1，2k，b）=（1，2k，2k-1），可操作一次，使之变成（1，2k-2，2k-1），由归纳假设，（1，2k-2，2k-1）是负局，所以（1，2k，b）是胜局； 当b=2k-2时，（1，2k，b）=（1，2k，2k-2），可操作一次，使之变成（1，2k-2，2k-1），由归纳假设，（1，2k-2，2k-1）是负局，所以（1，2k，b）是胜局； 当b<2k-2时，因为1< b<2k-2，由归纳假设，（1，2k，b）=（1，b，2k）是胜局；由此可见，T（1，2k，2k+1）恒为胜局，所以（1，2k，2k+1）是负局。 对于状态（1，m，n）（1<m<n，1<m<2k，且m为偶数时，n-m≥2），因为m≤2k-1，不妨设2t-3<m≤2t-1，其中t≤k。 如果m=2t-2，则（1，m，n）=（1，2t-2，n），因为m为偶数，有n-m≥2，即n≥m+2=2t，于是，可操作一次，将（1，2t-2，n）变成（1，2t-2，2t-1），由于2t-2=2（t-1），而t-1<t≤k，由归纳假设，（1，2t-2，2t-1）是负局，所以（1，m，n）是胜局； 如果m=2t-1，则（1，m，n）=（1，2t-1，n），因为n-m≥1，即n≥m+1=2t，于是，可操作一次，将（1，2t-1，n）变成负局（1，2t-2，2t-1），所以（1，m，n）是胜局。 所以结论对k成立，引理获证。 由k的任意性，当t=1时，状态（1，m，n）（1≤m≤n）中只有（1，1，1）和（1，2k，2k+1）（k∈N+）是负局，其余都是胜局。 综合（1）（2），定理1获证。  由定理2可知，对一般的三色棋搏弈问题（t，m，n）（t≤m≤n），我们只需解决t=2、3的两种情形。 情形1：当t=2时，易知（2，2，n）是胜局，因为它可操作一次变成负局（0，2，2）。 （2，n，n）是胜局，因为它可操作一次变成负局（0，n，n）。 下面只需讨论2=t<m<n的情形。 （2，2k，2k+1）是胜局，因为它可操作一次变成负局（1，2k，2k+1）。 （2，3，n）是胜局，因为它可操作一次变成负局（1，2，3）。 （2，4，5）是胜局，它是（2，2k，2k+1）型。 （2，4，6）是负局，因为由穷举可知，它无论怎样操作一次都变成胜局。 （2，4，n）（n>6）是胜局，因为它可操作一次变成负局（2，4，6）。 （2，5，6）是胜局，因为它可操作一次变成负局（2，4，6）。 （2，5，7）是负局，因为穷举可知，它无论怎样操作一次都变成胜局。 （2，5，n）（n>7）是胜局，因为它可操作一次变成负局（2，5，7）。 （2，6，n）是胜局，因为它可操作一次变成负局（2，4，6）。 （2，7，n）是胜局，因为它可操作一次变成负局（2，5，7）。 （2，8，9）是胜局，它是（2，2k，2k+1）型。 （2，8，10）是负局，因为穷举可知，它无论怎样操作一次都变成胜局。 （2，8，n）（n>10）是胜局，因为它可操作一次变成负局（2，8，10）。 由此可猜想，对于状态（2，m，n）（2≤m≤n），所有负局为（2，4k，4k+2）及（2，4k+1，4k+3）（k∈N+）型。 为证明此猜想，我们先证明如下的 定理3：对于状态（2，m，n）（2≤m≤n），只有（2，4k，4k+2）及（2，4k+1，4k+3）（k∈N+）是负局，而（2，4k，m）（k∈N+，m≥4k，m≠4k+2）及（2，4k+1，n）（k∈N+，n≥4k+1，n≠4k+3）是胜局，且（2，4k+2，m）（k、m∈N+，m≥4k+2）及（2，4k+3，n）（k、n∈N+，n≥4k+3）是胜局。 证明：对k归纳，当k=1时，（2，4，6）、（2，5，7）是负局，因为由穷举可知，它无论怎样操作一次都变成胜局。 对于（2，4k，m）（k∈N+，m≥4k，m≠4k+2），（2，4k，m）=（2，4，m）（m≥4，m≠6）。 当m=4时，（2，4，m）=（2，4，4）是胜局，因为它可操作一次变成负局（0，4，4）。当m=5时，（2，4，m）=（2，4，5）是胜局，因为它可操作一次变成负局（1，4，5）。 当m≥7时，（2，4，m）是胜局，因为它可操作一次变成负局（2，4，6）。 对于（2，4k+1，n）（k∈N+，n≥4k+1，n≠4k+3），（2，4k+1，n）=（2，5，n）（n≥5，n≠7）。 当n=5时，（2，5，n）=（2，5，5）是胜局，因为它可操作一次变成负局（0，5，5）。 当n=6时，（2，5，n）=（2，5，6）是胜局，因为它可操作一次变成负局（2，4，6）。 当n≥8时，（2，5，n）是胜局，因为它可操作一次变成负局（2，5，7）。 对于（2，4k+2，m）（k、m∈N+，m≥4k+2），（2，4k+2，m）=（2，6，m）（m≥6）是胜局，因为它可操作一次变成负局（2，4，6）。 对于（2，4k+3，n）（k、n∈N+，n≥4k+3），（2，4k+3，n）=（2，7，n）（n≥7）是胜局，因为它可操作一次变成负局（2，5，7）。 所以，k=1时结论成立。 设结论对小于k的正整数成立，考察k的情形。 对于状态A=（2，4k，4k+2）（k∈N+），设对A进行的操作为T。 如果T将A中的2变成a（a=0、1），得到状态T（A）=（a，4k，4k+2），由t=0、1的情形，T（A）是胜局。 如果T将A中的4k变成b（0≤b<4k），得到状态T（A）=（2，b，4k+2）。 若b=4r（r<k），则T（A）=（2，4r，4k+2）是胜局，因为它可操作一次变成（2，4r，4r+2），由归纳假设，这是负局。 若b=4r+1（r<k），则T（A）=（2，4r+1，4k+2）是胜局，因为它可操作一次变成（2，4r+1，4r+3），由归纳假设，这是负局。 若b=4r+2（r<k），则T（A）=（2，4r+2，4k+2）是胜局，因为它可操作一次变成（2，4r，4r+2），由归纳假设，这是负局。 若b=4r+3（r<k），则T（A）=（2，4r+3，4k+2）是胜局，因为它可操作一次变成（2，4r+1，4r+3），由归纳假设，这是负局。 如果T将A中的4k+2变成c（0≤c<4k+2），得到状态T（A）=（2，4k，c）。 若c=4r（r≤k），则T（A）=（2，4k，4r）。 若r=k，则T（A）=（2，4k，4k）是胜局，因为它可操作一次变成（0，4k，4k），这是负局。 若r<k，则T（A）=（2，4k，4r））是胜局，因为它可操作一次变成（2，4r，4r+2），由归纳假设，这是负局。 若c=4r+1（r≤k），则T（A）=（2，4k，4r+1）。 若r=k，则T（A）=（2，4k，4k+1）是胜局，因为它可操作一次变成（1，4k，4k+1），这是负局。 若r<k，则T（A）=（2，4k，4r+1）是胜局，因为它可操作一次变成（2，4r+1，4r+3），由归纳假设，这是负局。 若c=4r+2（r<k），则T（A）=（2，4k，4r+2）是胜局，因为它可操作一次变成（2，4r，4r+2），由归纳假设，这是负局。 若c=4r+3（r<k），则T（A）=（2，4k，4r+3）是胜局，因为它可操作一次变成（2，4r+1，4r+3），由归纳假设，这是负局。 所以A=（2，4k，4k+2）是负局……（*） 对于状态B=（2，4k+1，4k+3）（k∈N+），设对B进行的操作为T。 如果T将B中的2变成x（x=0、1），得到状态T（B）=（x，4k+1，4k+3），由t=0、1的情形，T（B）是胜局。 如果T将B中的4k+1变成y（0≤y<4k+1），得到状态T（B）=（2，y，4k+3）。 若y=4r（r≤k），则T（B）=（2，4r，4k+3）。 若r=k，则T（B）=（2，4k，4k+3）是胜局，因为它可操作一次变成（2，4k，4k+2），由（*），这是负局。 若r<k，则T（B）=（2，4r，4k+3）是胜局，因为它可操作一次变成（2，4r，4r+2），由归纳假设，这是负局。 若y=4r+1（r<k），则T（B）=（2，4r+1，4k+3）是胜局，因为它可操作一次变成（2，4r+1，4r+3），由归纳假设，这是负局。 若b=4r+2（r<k），则T（B）=（2，4r+2，4k+3）是胜局，因为它可操作一次变成（2，4r，4r+2），由归纳假设，这是负局。 若b=4r+3（r<k），则T（B）=（2，4r+3，4k+3）是胜局，因为它可操作一次变成（2，4r+1，4r+3），由归纳假设，这是负局。 如果T将B中的4k+3变成z（0≤z<4k+3），得到状态T（B）=（2，4k+1，z）。 若z=4r（r≤k），则T（B）=（2，4k+1，4r）。 若r=k，则T（B）=（2，4k+1，4k）是胜局，因为它可操作一次变成（0，4k+1，4k），这是负局。 若r<k，则T（B）=（2，4k+1，4r）是胜局，因为它可操作一次变成（2，4r，4r+2），由归纳假设，这是负局。 若z=4r+1（r≤k），则T（B）=（2，4k+1，4r+1）。 若r=k，则T（B）=（2，4k+1，4k+1））是胜局，因为它可操作一次变成（0，4k+1，4k+1），这是负局。 若r<k，则T（B）=（2，4k+1，4r+1））是胜局，因为它可操作一次变成（2，4r+1，4r+3），由归纳假设，这是负局。 若z=4r+2（r≤k），则T（B）=（2，4k+1，4r+2）。 若r=k，则T（B）=（2，4k+1，4k+2）是胜局，因为它可操作一次变成（2，4k，4k+2），由（*），这是负局。 若r<k，则T（B）=（2，4k+1，4r+2）是胜局，因为它可操作一次变成（2，4r，4r+2），由归纳假设，这是负局。 若z=4r+3（r<k），则T（B）=（2，4k+1，4r+3）是胜局，因为它可操作一次变成（2，4r+1，4r+3），由归纳假设，这是负局。 所以B=（2，4k+1，4k+3）是负局……（**） 对于状态C=（2，4k，m）（k∈N+，m≥4k，m≠4k+2），如果m=4k，则C=（2，4k，4k）（k∈N+）是胜局，因为它可操作一次变成（0，4k，4k），这是负局。 如果m=4k+1，则C=（2，4k，4k+1）（k∈N+）是胜局，因为它可操作一次变成（1，4k，4k+1），这是负局。 如果m≥4k+3，则C=（2，4k，m）（k∈N+）是胜局，因为它可操作一次变成（2，4k，4k+2），由（*），这是负局。 对于状态D=（2，4k+1，n）（k∈N+，n≥4k+1，n≠4k+3），如果n=4k+1，则D=（2，4k+1，4k+1）（k∈N+）是胜局，因为它可操作一次变成（0，4k+1，4k+1），这是负局。 如果n=4k+2，则D=（2，4k+1，4k+2）（k∈N+）是胜局，因为它可操作一次变成（2，4k，4k+2），由（*），这是负局。 如果n≥4k+4，则D=（2，4k+1，n）（k∈N+）是胜局，因为它可操作一次变成（2，4k+1，4k+3），由（**），这是负局。 最后，对于状态（2，4k+2，m）（k、n∈N+，m≥4k+2）及（2，4k+3，n）（k、n∈N+，n≥4k+3），它们都是胜局，因为它们可操作一次分别变成负局（0，4k，4k+2）、（2，4k+1，4k+3）。 所以结论成立，由归纳原理，定理3获证。 利用以上定理，可解决t为偶数的所有情形。 实际上，当t为偶数时，若t=0、2，则结论如定理1和3所述。 若t≥4，则令t=2r+2（t∈N+），则（t，m，n）=（2r+2，m，n）（4≤2r+2≤m≤n）。 由定理2，（2r+2，m，n）~（2，m-2r，n-2r）（2≤m-2r≤n-2r）， 由定理3，当t=2时只有（2，4k，4k+2）及（2，4k+1，4k+3）（k∈N+）是负局，所以（2r+2，m，n）只有m-2r=4k，n-2r=4k+2，及m-2r=4k+1，n-2r=4k+3（k∈N+）时为负局，此时，t=2r+2，m=2r+4k，n=2r+4k+2，或t=2r+2，m=2r+4k+1，n=2r+4k+3（k∈N+）。 由此可见，当t为偶数时，状态（t，m，n）（t≤m≤n）中只有（0，0，1）、（0，n，n）（n>1）、（2r，2r+4k-2， 2r+4k）、（2r，2r+4k-1， 2r+4k+1）（r、k∈N+）是负局，其余都是胜局。 情形2：当t=3时，易知（3，3，n）是胜局，因为它可操作一次变成负局（0，3，3）。 （3，n，n）是胜局，因为它可操作一次变成负局（0，n，n）。 下面只需讨论3=t<m<n的情形。 （3，2k，2k+1）是胜局，因为它可操作一次变成负局（1，2k，2k+1）。 （3，4，5）是胜局，因为它可操作一次变成负局（1，4，5）。 （3，4，6）是胜局，因为它可操作一次变成负局（2，4，6）。 （3，4，7）是负局，因为由穷举可知，它无论怎样操作一次都变成胜局。 （3，4，n）（n>7）是胜局，因为它可操作一次变成负局（3，4，7）。 （3，5，6）是负局，因为由穷举可知，它无论怎样操作一次都变成胜局。 （3，5，n）（n>5）是胜局，因为它可操作一次变成负局（3，5，6）。 （3，6，n）是胜局，因为它可操作一次变成负局（3，5，6）。 （3，7，n）是胜局，因为它可操作一次变成负局（3，4，7）。 （3，8，9）是胜局，因为它可操作一次变成负局（1，8，9）。 （3，8，10）是胜局，因为它可操作一次变成负局（2，8，10）。 （3，8，11）是负局，因为由穷举可知，它无论怎样操作一次都变成胜局。 （3，9，10）是负局，因为由穷举可知，它无论怎样操作一次都变成胜局。 由此可猜想（已出现周期），所有负局为（3，4k，4k+3）及（3，4k+1，4k+2）（k∈N+）型。 我们可仿照定理3的证明，得到如下的 定理4：对于状态（3，m，n）（3≤m≤n），只有（3，4k，4k+3）及（3，4k+1，4k+2）（k∈N+）是负局，而（3，4k，m）（k∈N+，m≥4k，m≠4k+3）及（3，4k+1，n）（k∈N+，n≥4k+3）是胜局，且（2，4k+2，m）（k、m∈N+，m≥4k+2）及（2，4k+3，n）（k、n∈N+，n≥4k+3）是胜局。 利用定理2和4，可解决t为奇数的所有情形。 实际上，当t为奇数时，若t=1、3，则结论如定理1和4所述。 若t≥5，则令t=2r+3（t∈N+），则（t，m，n）=（2r+3，m，n）（5≤2r+3≤m≤n）。 由定理2，（2r+3，m，n）~（3，m-2r，n-2r）（3≤m-2r≤n-2r）， 由定理4，当t=3时只有（3，4k，4k+3）及（3，4k+1，4k+2）（k∈N+）是负局，所以（2r+3，m，n）只有m-2r=4k，n-2r=4k+3，及m-2r=4k+1，n-2r=4k+2（k∈N+）时为负局，此时，t=2r+3，m=2r+4k，n=2r+4k+3，或t=2r+3，m=2r+4k+1，n=2r+4k+2（r∈N，k∈N+）。 由此可见，当t为奇数时，状态（t，m，n）（t≤m≤n）中只有（1，1，1）和（1，2k，2k+1）（k∈N+）、（2r+1，2r+4k-2， 2r+4k+1）、（2r+1，2r+4k-1， 2r+4k）（r、k∈N+）是负局，其余都是胜局。 综上所述，三色棋搏弈问题（t，m，n）（t≤m≤n）的解为：所有负局是（0，0，1）、（0，n，n）（n>1）、（1，1，1）、（1，2k，2k+1）（k∈N）、（2r，2r+4k-2， 2r+4k）、（2r，2r+4k-1， 2r+4k+1）（r、k∈N+）、（2r+1，2r+4k-2， 2r+4k+1）及（2r+1，2r+4k-1， 2r+4k）（r、k∈N+），其余都是胜局。 |
|
|
