珍珠湾ART

标题: 砍树游戏答案（图） [打印本页]

作者: constant 时间: 2006-4-3 23:33
标题: 砍树游戏答案（图）

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

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

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

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

作者: 大头羊 时间: 2006-4-4 01:30
标题: 回复：砍树游戏答案（图）

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

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

作者: 大头羊 时间: 2006-4-4 04:11
标题: 回复：回复：砍树游戏答案（图）

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

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

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

好题

欢迎光临珍珠湾ART (http://69.48.205.96:9997/)