取硬币游戏

取硬币游戏一

参加游戏的两个对手A和B，在他们面前的桌上有几堆分开的硬币，每堆硬币的数目是任意的。双方轮流从任意一堆（只许一堆）拿走一枚或几枚硬币（也可把整堆取走），直到把硬币完全取完为止，谁最后一个取完，谁就算胜利（或规定为失败）。

解题过程及结论

1. 仅1堆：先拿者必胜，策略：全部拿完

2. 仅2堆：设为（k1,k2）

2.1 当k1=k2时，先拿者必败 策略：A在其中1堆中拿多少，B在另1堆中就拿多少，直到拿完为止。 2.2 当k1≠k2时，先拿者必胜 策略：A在数量多的1堆中拿走abs（k1－k2）个，则变为局面2.1，B必败。

3. 仅3堆：设为（k1,k2,k3）

3.1 当k1=k2=k3或其中任何2堆数量相等时，先拿者必胜 策略：A一次全部拿走硬币数量不同的1堆的所有硬币，则变为局面2.1，B必败。 3.2 当k1≠k2≠k3时，分析如下 3.2.1 先用简单的例子，当（1，2，k）时 1）当k=3时，先拿者必败，分析如下 A来取后只可能出现如下局面： （1）（2，3）如局面2.2 A必败（2）（1，3）如局面2.2 A必败（3）（1，1，3）如局面3.1 A必败（4）（1，2）如局面2.2 A必败（5）（1，2，1）如局面3.1 A必败（6）（1，2，2）如局面3.1 A必败 因此，当（1，2，3）时，先拿者必败 2）当k≠3时，先拿者必胜 策略：A在第3堆中取走（k－3）枚硬币，则变为3.2.1的1）局面，A必胜 3）同理，可分析（1，3，k）的局面 当k=2时，先拿者必败 当k≠2时，先拿者必胜 4）同理，还可分析（2，3，k）的局面 当k=1时，先拿者必败 当k≠1时，先拿者必胜 3.2.2 认真分析3.2.1可得出结论 1）当且仅当(k1)^(k2)^(k3)=0时（其中“^”为位异或运算符），先拿者必败 也可表述为当(k1)^(k2)=k3时，先拿者必败 2）(k1)^(k2)^(k3) ≠0时，先拿者必胜 策略： （1）分别计算(k1)^(k2)、(k1)^(k3)、(k3)^(k2)的值，设其分别为m1、m2、m3，再分别比较k3与m1、k2与m2、k1与m3的大小，其中必有一个M值小，先从其对应k值的堆中取走（k－m）枚硬币。 （2）重复第（1）步并利用1、2的结论即可。

举例说明：（3，4，7）因3^4^7=0，因此，先拿者必败若A从第1堆取走1枚硬币，则变为（2，4，7）此时，B如何应对呢？ 2^4=6，2^7=5，4^7=3，因此从第3堆中取走7-6=1枚硬币，变为（2，4，6），因2^4^6=0，因此此局面仍然对A不利，同理，下一步无论A怎样取，B可用同样的策略形成对A不利的局面，A必败。

4. 当n堆且各堆硬币数量相同时：设为（k,k,k，…k）时 4.1 当n为奇数时，先拿者必胜 策略：A先一次取走其中1堆中的所有硬币，B在其中另1堆中拿多少，A就在其对应数量（与B取硬币前数量）的另1堆中取多少，直到取完为止。 4.2 当n为偶数时，先拿者必败 策略：A在其中1堆中拿多少，B就在其对应数量（与A取硬币前数量）的另1堆中取多少，直到拿完为止。

5. 当n堆且各堆硬币数量均不相同时：设为（k1,k2,k3，…kn）且k1≠k2≠k3…≠kn时 5.1 当（k1）^(k2)^…(kn）≠0时，先拿者必胜 5.1 当（k1）^(k2)^…(kn）=0时，先拿者必败 5.3 其策略可参照3.2.2

6. 当n堆且各堆硬币数量既有相同又有不相同时：设为（k1,k2,k3，…kn）时 1）先将堆按数量分类，将数量相同的归为一类，假设k1数量的有p1堆，且p1>1 K2数量的有p2堆，且p2>1 …….Km数量的有pm堆，且pm>1 其余（q-m）堆的数量均不同 则p1+p2+…+pm+（q-m）=n 2）再将p1到pm堆按奇偶分类。 3）综合运用4、5的策略即可。

该页面最新编辑时间为 2023年12月26日