珍珠湾ART

标题: 请继续考虑“也拿石头子儿来玩”。至今在此坛还没人给出正确解法。 [打印本页]

作者: Ein 时间: 2006-6-25 13:12
标题: 请继续考虑“也拿石头子儿来玩”。至今在此坛还没人给出正确解法。

原题在半个月前贴出，康大帝指出了正确思路，但解法有误。此题不同于其他大多数“拿石头子儿”游戏，其解法有严密的数学证明。有谁能攻克此题？盼诸位牛人出手。也请康大帝加油。现将原题再述于下：www.ddhw.com

www.ddhw.com

一堆石头子儿（譬如说，好几十或上百个），随意地分成几堆。两人交替地从中拿，直至拿光。规则是：每次任选一堆, 从中拿至少一个至多一整堆，不能不拿，也不能跨堆拿。约定：拿最后一次者为输。请问如何才能尽量不输？为了显得更“公平”些，不妨让一人分堆，另一人先拿。进一步，如果把约定改为：拿最后一次者为赢，又如何玩法？

作者: 东北逍遥客 时间: 2006-6-26 05:00
标题: 回复：请继续考虑“也拿石头子儿来玩”。至今在此坛还没人给出正确解法。

这道题很简单啊！怎么还需要重贴？

我是学电脑的，我们的二进制算术比十进制算得还遛，能保持剩余堆异或值为0者胜。记着在最后时刻给对手留一个哟。

作者: Jenny 时间: 2006-6-26 06:37
标题: 回复：回复：回复：请玩一盘

>>>>你在楼下那个贴里问我“知道音音是谁吗”？

你还没有告诉我你是谁~~

作者: Jenny 时间: 2006-6-26 07:40
标题: 回复：回复：回复：回复：回复：请玩一盘

太好了！等你注册了我就能给你送花飞KISS了~~hehe~~

作者: 东北逍遥客 时间: 2006-6-26 08:47
标题: 回复：回复：回复：请玩一盘

回来一看，吓我一跳，怎么这么多回复。不说别的，解一下你的例子。

219 = 11011011B

117 = 01110101B

221 = 11011101B

11011011B^01110101B^11011101B = 01110011B

因为01110011B不等于0，所以我选择先拿。

*** 从117里取出111个使其等于6（00000110B） ***

促使11011011B^00000110B^11011101B = 0

用二进制只是方便调整而已。

后续的我就不用再说啥了吧？

作者: Ein 时间: 2006-6-26 10:20
标题: 回复东北逍遥客

网友们也许要问，你是如何确定对策“从第二堆中拿掉111个剩6个”的。另外，对方再拿一次后，是否一定会给你留下机会？所以，你必须

（1）证明：任何“负态”（异或值为0）经拿一次后一定成为“胜态”（异或值不为0）；

（2）证明：对任何给定的“胜态”，一定存在至少一种（可能是1，或3，...，最多可为不超过n的最大奇数）拿法，使其恢复成“负态”。进而，给出找到这种（些）拿法的算法（Algorithm）。

“用二进制只是方便调整而已”的说法是不全面的，也可看出，你给的解的这一步虽正确，但它是“调整”出来的，也就是“凑”出来的。如果数字再大些，凑起来就费劲了。许多人只知其然而不知其所以然（或者，没有想到要知其所以然）。建议你加油，完成上述两条，上升到理论层次。这也就回答了你为何还要重贴的问题。

此游戏曾在441B电子计算机上用机器语言实现，仅用了十几条指令，当时拿来供xx们与机器对玩。你是学电脑的，也许知道中国441B机的背景（也可能知道441C）。

作者: 东北逍遥客 时间: 2006-6-26 12:51
标题: 回复：回复东北逍遥客

抱歉，知道自己知识贫乏，不知道441什么的，听起来怎么那么像东北咆么呢
你说的那两个证明在我看来是只能是自明的，因为我一想它就该是那样的，不会证明，可以算作是第六、第七公设。哪位大侠分析完了第五公设还有余劲儿没使完，可以攻一攻。
我还是找一个软柿子捏一下，你要是不提这辈子可能都想不起来了电脑里竟是这种东西在工作，好容易搞到20条指令之内，十几条指令总不会还包括输入输出吧？
要调试可是太难为我了，哪位大侠如果发现有问题请告知，错了不许笑话啊！

（明天早晨来看看）www.ddhw.com

    mov si, DATA_OFFSET
    mov cx, ITEM_NUM
    xor ah, ah
loop1:
    xor ah, [si]
    inc si
    loop loop1
    or ah, ah
    jz not_found

    mov si, DATA_OFFSET
    mov cx, ITEM_NUM
loop2:
    mov al, ah
    xor al, [si]
    cmp al, [si]
    jle found
    inc si
    loop loop2www.ddhw.com

not_found:
    ; 没法取了，认输
    ...
found:
    mov dl, [si]
    sub dl, al
    ; si是要取那堆数的地址
    ; dl 是这次要取的数目
    ...

作者: Ein 时间: 2006-6-26 17:37
标题: 回复：回复：回复东北逍遥客

我相信你能玩赢。你不是数学家，能“自明”已当不易，倘能“给出”则更佳。441机（B或C型）不是美国货，你又不是电脑史专家，难怪你不知道。当国人在用441时，你我还不知“电脑”这个词呢。

作者: 小算盘 时间: 2006-6-27 11:41
标题: 回复：请继续考虑“也拿石头子儿来玩”。至今在此坛还没人给出正确解法。

什么烂题目，先拿必胜！

先拿者每堆都拿到剩下一颗石头，后拿者只能干瞪眼！

作者: Ein 时间: 2006-6-27 11:57
标题: 回复：回复：请继续考虑“也拿石头子儿来玩”。至今在此坛还没人给出正确解法。

小算盘，请再看一遍题目。然后想一想，...

作者: 小算盘 时间: 2006-6-27 13:37
标题: 回复：回复：回复：请继续考虑“也拿石头子儿来玩”。至今在此坛还没人给出正确解法。

有问题吗？

先拿者任选一堆（n颗），从拿走n-1颗，后拿者只能拿这堆的剩下一颗，类推下去。。。最后一堆的最后一颗是谁拿？

作者: Ein 时间: 2006-6-27 16:12
标题: 回复：回复：回复：回复：请继续考虑“也拿石头子儿来玩”。至今在此坛还没人给出正确解法。

后者可任选一堆，不一定是你拿的那堆，再从中取若干。例如，3，3，3。你选一堆拿走2个，我就从另一堆中拿走一个，形成1，2，3。你就输定了。

作者: 新用户 时间: 2006-6-28 21:42
标题: Ein好样儿，喜欢你的态度，，，，

Ein好样儿，喜欢你的态度，，，，

作者: husonghu 时间: 2006-6-29 00:16
标题: Ein，音音，很了不起[@};-][@};-][@};-][@};-]

Ein，音音，很了不起

作者: try 时间: 2006-6-29 11:59
标题: TRY!?

不知道解这道题需要的最高数学程度是什么？

先试一下：

约定最后一次拿者胜。

石子数：1 先拿者：败

石子数：2 先拿者：胜

石子数：3 先拿者：败

石子数：4 先拿者：败

猜想：分的方法与石子数有关。

作者: Ein 时间: 2006-6-29 20:29
标题: 回复：TRY!?

我没有看懂你的石子数1，2，3，4。

此题仅要求知道二进制数及逻辑运算。当然，还需懂得如何来证明一个命题。如果学过“离散数学”那就完全有能力来彻底解决这个问题了。

作者: Ein 时间: 2006-6-30 05:11
标题: 谢谢诸位鼓励！

谢谢诸位鼓励！

作者: Hobson 时间: 2006-7-19 00:24
标题: 回复：请继续考虑“也拿石头子儿来玩”。至今在此坛还没人给出正确解法。

这个题已被解决，详情请见这个英文网页：

http://en.wikipedia.org/wiki/Nim

Nim is a two-player mathematical game of strategy in which players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap.www.ddhw.com

Nim has been mathematically solved for any number of initial heaps and objects; that is, there is an easily-calculated way to determine which player will win and what winning moves are open to that player. In a game that starts with heaps of 3, 4, and 5, the first player will win with optimal play, whether the misère or normal play convention is followed.

这个游戏是叫Nim.

作者: 也拿石头子儿来玩 时间: 2006-8-1 10:32
标题: 回复：请继续考虑“也拿石头子儿来玩”。至今在此坛还没人给出正确解法。

1,1 2,2 3, 3 n,n ......1,1,1 1,2,3 1,4 ,5 1,5,6 .......

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