我要招人

去企业版

首页 > 试题广场 >

拿火柴问题

[单选题]

有3堆火柴，分别有4,5,7根，两个人依次取火柴，每次只能取同一堆的火柴，最少拿一根，最多拿着堆内所有火柴，取走最后一根火柴，让对方无火柴可以取者为胜。请问现在谁会获胜?()

```
后手
```
```
先手
```
```
不确定
```

查看答案及解析

推荐

SunburstRun

答案是B

如果只剩下一堆火柴，那么只要有点智商就会直接全部拿走，让对方输掉，所以关键就看倒数第二堆，要想赢，那么就必须让对方那第二堆的最后一个根，如何做到呢，就是先手拿完一堆火柴只剩下一根，让对面拿这堆的最后一根，第二堆也是一样，一堆火柴只剩下一根，让对面拿这堆的最后一根，第三堆你直接拿走

编辑于 2015-09-30 11:09:40 回复(10)

姜海宽

应该是先手B 解析如下：

先手先拿掉第3堆的6根，这时候变成了4，5，1三堆

此时如果对方（后手）拿掉了1，那么就剩下4，5两堆我就拿5里面的1根，保证剩下两堆的数量相等，这样不论对方如何再拿，我都可以从另外一堆拿掉相应的根数，始终保持两堆相等，直到出现两堆都是1根的情况，这时就赢了。

如果对方（后手）拿4或5堆全部，我就把剩下的拿掉剩1根，又出现了两堆都是1的情况。

如果对方（后手）拿掉4或5堆的一部分：如果4里拿1，我在5里拿2，变成1，2，3 对方如何再拿我都能保证最后手；如果5里拿1，我就拿1堆里的那一根，变成4，4，保证后手；如果5里拿2，我就4里拿2，变成1，2，3，保证最后手。

关于1，2，3的情况下，我就能保证最后手应该是很容易推导出来的，大家不妨自己列一下，也就几种情况而已。

觉得满意记得点赞哦：）

发表于 2015-10-04 17:34:15 回复(6)

sharpdeep

先手只要前面两堆都只剩下一根，最后一堆全部拿走就100%赢

发表于 2015-09-30 23:47:45 回复(1)

pngfi

从网上搬过来的解释，该题中因为

4 ---100

5 ---101

7 ---111

最左边3个1明显处于非平衡态，所以先手赢。

nim取子问题：

如果游戏开始时只有一堆硬币，游戏人I则通过取走所有的硬币而获胜。现在设有2堆硬币，且硬币数量分别为N ₁ 和N ₂ 。游戏人取得胜利并不在于N1和N2的值具体是多少，而是取决于它们是否相等。设N ₁ ！=N ₂ ，游戏人I从大堆中取走的硬币使得两堆硬币数量相等，于是，游戏人I以后每次取子的数量与游戏人II相等而最终获胜。但是如果N ₁ = N ₂ ，则：游戏人II只要按着游戏人I取子的数量在另一堆中取相等数量的硬币，最终获胜者将会是游戏人II。这样，两堆的取子获胜策略就已经找到了。

现在我们如何从两堆的取子策略扩展到任意堆数中呢？

首先来回忆一下，每个正整数都有对应的一个二进制数，例如：57₍₁₀₎à 111001₍₂₎ ，即：57₍₁₀₎=2⁵+2⁴+2³+2⁰。于是，我们可以认为每一堆硬币数由2的幂数的子堆组成。这样，含有57枚硬币大堆就能看成是分别由数量为2⁵、2⁴、2³、2⁰的各个子堆组成。

现在考虑各大堆大小分别为N₁，N₂，……N_k的一般的Nim取子游戏。将每一个数N_i表示为其二进制数（数的位数相等，不等时在前面补0）：

N₁= a_s…a₁a₀

N₂= b_s…b₁b₀

……

N_k= m_s…m₁m₀

如果每一种大小的子堆的个数都是偶数，我们就称Nim取子游戏是平衡的，而对应位相加是偶数的称为平衡位，否则称为非平衡位。因此，Nim取子游戏是平衡的，当且仅当：

a_s+ b_s + … + m_s 是偶数

……

a₁+ b₁+ … + m₁是偶数

a₀+ b₀ + … + m₀是偶数

于是，我们就能得出获胜策略：

游戏人I能够在非平衡取子游戏中取胜，而游戏人II能够在平衡的取子游戏中取胜。

我们以一个两堆硬币的Nim取子游戏作为试验。设游戏开始时游戏处于非平衡状态。这样，游戏人I就能通过一种取子方式使得他取子后留给游戏人II的是一个平衡状态下的游戏，接着无论游戏人II 如何取子，再留给游戏人I的一定是一个非平衡状态游戏，如此反复进行，当游戏人II在最后一次平衡状态下取子后，游戏人I便能一次性取走所有的硬币而获胜。而如果游戏开始时游戏牌平衡状态，那根据上述方式取子，最终游戏人II能获胜。

发表于 2016-09-06 14:26:21 回复(1)

919323

因为4^5^7 != 0，所以先手有必胜的策略.

发表于 2015-10-03 19:51:53 回复(0)

wcz2023

打一顿就赢了

发表于 2015-10-04 12:16:04 回复(0)

沙秋

先手赢。

可以倒着来思考。

1)对于最后一堆，第一次取的人肯定一次性拿完啦，不然对方就拿完了，那么谁取倒数第二堆的最后一根谁就输。

2) 倒数第二堆第一次取的人肯定不希望自己取最后一根，那么他就必然取走总数 - 1 根，由此可得第一次取倒数第二堆的人能赢。

3) 由上一条可得取第一堆最后一根的人就要输，因此第一次取第一堆的人肯定取走总数-1根，因此可得先手赢。

假设 A,B两人来取，A是先手，取的堆一次为 4,5,7 对应的三堆（顺序无所谓）取法应该会变成这样：

第一堆：A - 3 ，B - 1

第二堆：A - 4 , B - 1,

第三堆： A - 7

最终B无火柴可取。

发表于 2015-10-05 10:23:17 回复(0)

亲切年

如果是可以取不同堆的火柴的话，这题的答案是C么？？？

发表于 2015-10-01 21:06:06 回复(0)

zt_xcyk

前两堆给后手留一根第三堆全拿后手就输了

发表于 2015-09-30 20:51:03 回复(0)

大漠孤狼

先手赢，前两次分别拿了剩一根，后手只能拿那一根，最后一堆一次拿走

发表于 2015-09-30 16:10:10 回复(0)

Vigilr

有点博弈论的感觉

发表于 2021-04-10 17:23:36 回复(0)

abner112

总结别人答案。技巧是所有堆异或为0先手输，其他先手赢。4^5^7 != 0。因此先手胜利。异或是所有二进制位都是偶数个1时是0，其他情况都不是0。三个数的二进制分别是100，101，111。如果要改第一个使得运算为0，只能改为010，既2，4-2=2，先手取第一个数2。如果要改第二个使得运算为0，只能改为011，既3，5-3=2，先手取第二个数2。如果要改第三个使得运算为0，只能改为001，既1，7-1=6，先手取第三个数6。

发表于 2019-12-20 10:29:43 回复(0)