砍树游戏答案（图）

constant · 发表于 2006-4-3 23:33:40

在纸上随便画几棵树（例如下图），两人轮流砍。每次可以在任何一个节点处砍掉一枝。可以砍掉整个一棵树。如果一个节点有几个树枝，只能砍掉一枝。最后无树可砍的人负。

就下图而言，先砍能不能获胜？

答案: 如果没有分叉，即每个节点只有一枝，这就变成了拿石子游戏（NIM）。有分叉的道理也差不多：左边的树有两枝，中间的树上面两枝可以抵消，中间两枝可以抵消，所以相当于一枝。我们知道在NIM里面（1，2，3）是负状态，所以先砍的人可以把第三棵树左边的小枝砍掉，剩3枝。

可以证明这个砍法是唯一的。

大头羊 · 发表于 2006-4-4 04:11:51

明白了，不是（2 3 1 ）是（2 1 1）。

凡是对称的，可以看做“两组一样”，是可对称消除的。

这样的话，这个题还可以无限添加对称的树枝，但是本质不变。

好题

大头羊 · 发表于 2006-4-4 01:30:54

(1)如果对手第二轮把中间最高端的左枝砍去，我只能砍最高端的右枝，否则都是输，对吗？

如果(1)对，那么如果第三轮对手把第三棵树砍成只剩一枝，那么不就等于把（2 3 1）留给我了吗？那我砍哪个不都是输吗？

		自动登录	找回密码
密码			立即注册

动态微博