no subject

sam888sam

题目如下:

有三堆火柴,一堆为3根,一堆为5根,一堆为7根,每次只能在其中的一堆中取走1根,或多根,甚至一堆全部取走,两个人参加比赛,谁取到最后一根火柴为输方.

据说此题有两种解法:
1.谁先取,谁赢.
2.谁先取,谁输.

好象矛盾嘛!答案留给超级聪明的你吧![em11]

[此贴子已经被作者于2003-5-13 20:54:59编辑过]

moneynet

3,5,7 这种情况
后拿的赢

moneynet

参考文章

　有三堆火柴，分别为12根、9根和6根，两人轮流从三堆中取火柴，每次只许从一堆中拿取；取的根数不限（但不可不取）.问如何取才能保证你能取走最后一根火柴而获胜？

　　在讨论问题之前，我们需要先明确一个事实：

　　任何一个自然数，都能够写成下面一列数：

　　1，2，4，8，16，32，…2n-1，…中的若干个数的和.

　　比如，29＝16+8+4+1，15＝8+4+2+1，3＝2+1等.

　　这里，我们先把三堆火柴根数分别写成下面的形式：

　　12＝8＋4 9＝8＋1 6＝4＋2

　　将两个相同的加数配成一对，可以配成两对（8，8）和（4，4），剩下的两个加数1、2无法配对.我们把这种“所有加数不能全部配成对”的称为“非对称型”，把“所有加数都能配成对的称为“对称型”（加数全部为0时也属于对称型）.

　　如果你面对“对称型”，可能发现，不论你在哪一堆中取走多少根火柴，都要使其中的一个数减少，这样一来，至少要拆散原来配好的一对，使它变为“非对称型”.

　　如果你面对“非对称型”，经过试验也可以发现，在某一堆中取走适当根数的火柴，可以将它变为“对称型”.其实，这时你只要找出无法配对的加数中最大的一个，然后在这个加数所对应的那一堆中取出适当根数的火柴，以至于剩下的火柴数分解后，使得所有加数能够全部配成对.如在这个游戏中，由于无法配对的最大加数是2，因此应在数量为6的那一堆中取火柴，使剩下的火柴数为5＝4+1（即取走6-5＝ 1根火柴），这样就使得所有的加数全部配成对了.

　　如果你想获胜，最后的火柴应该由你取走，即你留下了一个各堆火柴根数都是0的“对称型”.可以设想，如果你每次取后都给对方留下“对称型”，而对方取后又不得不给你留下“非对称型”，面对“非对称型”，你总可以设法使它成为“对称型，……如此一直继续下去.因为火柴的根数是有限的，所以经过若干轮后，总有一次出现各堆都是0的情况，这是一个“对称型”，一定是你留下的，那么最后一根火柴当然是被你取走了.

　　因此，当火柴棍是三堆或三堆以上时，获胜的办法为：

　　（1）若开局是“非对称型”，则先取者必胜.策略是：

　　①设法把“非对称型”变为“对称型”留给对方；

　　②每次对方取后，都会把“对称型”变为“非对称型”留给你，你再重复第①步骤，直到最后获胜.

　　（2）若开局是“对称型”，则后取者必胜，策略是：

　　与（1）中的第②步骤相同.

　　下面就以上面的游戏为例，具体实践一番.

　　由于三堆火柴为（12，9，6），开局时是“非对称型”，因此先取者获胜.

　　①从6根一堆的火柴中取走1根（前面已分析过），变成（12，9，5）.

　　②设想对方取成（8，9，5），根据8＝8，9＝8+1，5＝ 4+1，我方应在5根一堆的火柴中取走4根，变为（8，9，1）.

　　③设想对方取成（8，3，1），我方应变为（2，3，1）.

　　④设想对方取成（2，1，1），我方应变为（0，1，1）.

　　⑤对方只能取成（0，0，1），我方取走最后一根，变为（0，0，0）而获胜.

　　如果你掌握了这些游戏获胜的“秘诀”，定能“百战百胜”，做一名“常胜将军”.

sam888sam

有点问题

阿奔

还是没看懂哦，在看下去我会成非对称的

mian1573

简直恐怖！

swlizhong

先拿必胜，最重要是第一次拿任何一堆使其只剩下一根火柴。其后你们自己想想就OK。其实数值不重要。

moneynet

注：我贴的参考文章规则是最后拿到火柴的赢，和原题目的规则最后拿到火柴输刚好相反。不过思路应该是一样的。

ps： to swlizhong：
跟数字组合有关的，详细的解释上面的帖子有。
可以用一个简单的例子反证（按原题，拿到最后一根火柴的输为规则）：
  1，1，1 这种组合，先拿必输。
  1，1，2这种组合，先拿2的一根，变成1，1，1，先拿必胜。

野鹤

没错，虽然很复杂，但我看懂了。
理论知道实际，明白了。

neilli7438

日本有一个数学家，名字叫角谷，这个题目是他出的，他有一个学生叫吉田耕作yoshida，写了本《泛函分析》，很棒的书！

[此贴子已经被作者于2003-5-27 0:23:14编辑过]