[深海活动]★★★逻辑思维类问题连连看★★★

zcy123456

先取者输，我们通过分析可以知道当轮到B取硬币时只要剩下2、3、5时A就必输，而这可以通过适当的方法达到。
1、若A一开始取4，B取2，那么下一轮A只能取1或2，则刚好给B剩下2或3，B胜。
2、若A一开始取2，B取4，接下来取法和情况1相同。
3、若A一开始取1，B取2，此时还剩7.之后（a）若A取1，B取2，还剩4枚，情况同第一种，B胜。
                   （b）若A取2，B取1，情况同上，B胜。
                   （b）若A取4，B取2，此时最后一枚只能A取，B胜。
所以B必胜A必输

speary

反正结果是B胜A输，推导是否令人信服就由楼主判定了。

neotsu

1994的推理还是蛮对的。

speary

过了36小时，就给出答案吧，具体谁对楼主评吧

根据（2）和（3）：
（a）当这堆硬币中只有一枚硬币要取的时候，显然取者必输。
（b）当这堆硬币中有两枚硬币要取的时候，取者可以只取走一枚硬币而获胜，因为这样就使对方陷入了只有一枚硬币要取的必败境地。
（c）当这堆硬币中有三枚硬币要取的时候，取者可以取走两枚硬币从而获胜，因为这样就可以使对方陷入同（b）一样的必败境地。如果他只取走一枚硬币，对方就取走最后一枚硬币而获胜。
（d）当这堆硬币中有四枚硬币要取的时候，取者必输。如果他取走一枚，就把有三枚硬币要取的必胜机会留给了对方。如果他取走两枚，就把有两枚硬币要取的必胜机会留给了对方。如果他取走四美硬币，显然他马上就输了。他不可能获胜，因为他不可能留下一定枚数的硬币从而使对方陷于必败的境地。
（e）当这堆硬币中有五枚硬币要取的时候，如果取者能够留下一定枚数的硬币从而使对方陷于必败的境地，那他就赢了。因此，如果他能留下一枚或者四枚硬币让对方取，那他就赢了。于是他取走四枚硬币，留下一枚或者取走一枚硬币，留下四枚。
按照这样的推理，我们可以发现，当有一枚、四枚、七枚或者十枚硬币要取的时候，取者注定要输；当有两枚、三枚、五枚、六枚、八枚或九枚硬币要取的时候，取者稳操胜券。
下列两表总结了这两种情况分别是怎样注定导致失败和怎样稳步走向胜利的。

注定要输的局面	如果一方取走	他留给对方的必胜机会
4	1 2 4	3 2 0
7	1 2 4	6 5 3
10	1 2 4	9 8 6

稳操胜券的局面	如果一方取走	他使对方陷入的必败境地
2	1	1
3	2	1
5	1 4	4 1
6	2	4
8	1 4	7 4
9	2	7

由于开局10枚，A开局，故B必赢

neotsu

spready 的推算还是太复杂了，1994的推算还是很精简的

三的倍数是亮点，4可以视为4 mod 3 = 1, 即，只存在1,2,1( = 4mod3)的情况，所以三枚为2者和的普通硬币游戏规律被拓展为三或六为二者和的游戏规律，可以等同于三的规律。

因此可以不必通过穷举排查即可得到结果。


顺便提一下n+1两者和硬币的规律

一人最多可连续拿到n枚，则保证拿不到最后一枚需要剩下的硬币为（n+1）+1 枚，同理，上一轮的保证数字为 2（n+1）+1枚， 可以反推到m(n+1)+1的关键数字。

camio

真是八仙过海，各显神通啊！

对于解题太简略，跳跃性太强的，恕我太愚笨，看不懂，请各位见谅！

请zcy123456

出第17题

neotsu

第十六题如果拓展到200枚硬币，1994的方法仍然有解，而speary就困难了

如果改成 每人可以拿1，2，3，4，5，7枚硬币，也是同样的局面。。。。

zcy123456

我来出题了，好像有点来晚了
[size=3]17题：现有一排n只正立的酒杯，规定每次只许翻动其中任意n-1只酒杯（即原来正的变倒的，倒的变正的），问：
能否经过若干次翻动，把所有酒杯都倒过来？若有，给出一种具体的翻动方法
（注：该题要对n进行讨论分析，可能会有点麻烦。还有讨论时候还要有一定的猜想，然后再证明）

指舞如歌

当n为偶数时，显然是可行的。具体操作程序如下：
1、第1只酒杯不动，其他酒杯翻转；
2、第2只酒杯不动，其他酒杯翻转；
……………………
n、第n只酒杯不动，其他酒杯翻转。
经过以上n次操作以后，每只酒杯翻转n-1次，而n-1是奇数，因此，所有酒杯已经倒过来了。

当n为奇数时，是不可行的。用反证法很容易证明：
假定经过若干次翻动使得所有酒杯都已翻转，则每只酒杯被翻动了奇数次。而酒杯的总数是奇数，所有总翻动次数是奇数。但是，每一次翻动都要翻动n-1只酒杯，即翻动次数必为偶数次，于是，总翻动次数是偶数。矛盾。

gaokaobsd

引用第168楼指舞如歌于2009-08-02 17:48发表的 :
当n为偶数时，显然是可行的。具体操作程序如下：
1、第1只酒杯不动，其他酒杯翻转；
2、第2只酒杯不动，其他酒杯翻转；
……………………
n、第n只酒杯不动，其他酒杯翻转。
.......

有道理

zcy123456

果然有才，楼上的应该做过这个题吧

指舞如歌

第18题：在中国象棋棋盘上，一只马从右下角出发，到达棋盘上的哪一个点所需的步数最多？对于m*n尺寸的棋盘，给出一般性的结论。

23:59

瓦力的题有难度

camio

一般性的结论指的是？

象棋棋盘不是固定行数和列数的么？

speary

一般性就是随便m*n的方格啦，跟象棋棋盘没关系的；其实这题跟象棋棋盘没啥关系，只是要用到马跳日而已，我理解。

指舞如歌

引用第174楼speary于2009-08-04 10:14发表的 :
一般性就是随便m*n的方格啦，跟象棋棋盘没关系的；其实这题跟象棋棋盘没啥关系，只是要用到马跳日而已，我理解。

speary兄的理解没错。

为简单起见，可以仅仅讨论m小于2n并且n小于2m的情况。

speary

超时啦，楼主按照规则该给答案并出新题了吧

指舞如歌

参考答案：

在标准棋盘（9*10）上，最远点是左上角，至少需要7步。理由如下：
1、显然，7步可以到达。
2、小于7步的走法不存在。反证法：起点距终点的纵坐标与横坐标之和为17，每走一步，这个值顶多缩小3。显然，5步的走法不存在。假定存在6步的解法，则必然3步上上左，三步左左上，但是此时无法达到左上角。

在m*n的棋盘上（m和n都大于3），首先考虑m小于2n并且n小于2m的情况。
如果m+n可以被3整除，则最远点是与左上角相邻的两个点；
如果m+n不能被3整除，则最远点是左上角。

当m大于或等于2n时，最远点位于远离起点的边上。
如果m除以4的余数为3或2，则最远点是在远离起点的边上、纵坐标分别为0、2、4……的点。
如果m除以4的余数为1，则最远点是在远离起点的边上、纵坐标分别为1、3、5……的点。
如果m除以4的余数为1，则最远点是在远离起点的边上、纵坐标分别为1、3、5……的点。
如果m被4整除，则最远点是在远离起点的边上、纵坐标分别为1、3、5……的点，以及在与远离起点的边相邻的纵线上、纵坐标分别为0、2、4……的点。

n大于或等于2m的情况类似。

可以用递归方法证明。

指舞如歌

重新出题：
第19题：有一只天平，n个小球，其中有一只小球与其他球不同，但不知是更轻还是更重。众所周知，当n为12时，称三次可以标定这个独特的小球并确定轻重。

问题：如果允许称四次，则最多可以允许n是多少？



一个相关的问题，也很有趣：有13只小球，其中有一只小球与其他球不同，但不知是更轻还是更重。另外，还有一只标准球（第14只球），标准球的重量与13只球中的12只相同。称三次是否可以标定这个独特的小球并确定轻重？
此题仅供参考，不属于活动内容。

neotsu

恰好知道。40个

但不是我推导出来的，惭愧

http://faq.csdn.net/read/179539.html

称球问题一般会有以下3种变形：
1、n个球，其中有一个坏的，知道是轻还是重，用天平称出坏球来。
2、n个球，其中有一个坏的，不知是轻还是重，用天平称出坏球来。
3、n个球，其中有一个坏的，不知是轻还是重，用天平称出坏球来，并告知坏球是轻还是重。

对于上面3种情况，称量n次，最多可以在几个球中找出坏球来？

答案：分别为：3^n, (3^n - 1)/2, (3^n - 3)/2.

称法体现在下面的证明中：

一、
  
  天平称重，有两个托盘比较轻重，加上托盘外面，也就是每次称重有3个结果，就是ln3/ln2比特信息。n个球要知道其中一个不同的球，如果知道那个不同重量的球是轻还是重，找出来的话那就是n个结果中的一种，就是有ln(n)/ln2比特信息，

  假设我们要称k次，根据信息理论：
   k*ln3/ln2>=ln(n)/ln2,   解得k>=ln(n)/ln3
  

  这是得到下限，可以很轻易证明满足条件的最小正整数k就是所求。比如称3次知道轻重可以从3^3=27个球中找出不同的球出来。

  具体称法就是：每次再待定的n个球中取[(n+2)/3]个球，放在天平左边；[(n+2)/3]个球放在天平右边。
（注：[ x ]表示不大于x的最大整数。）


二、

BBS水木清华站∶精华区
发信人: idle (回归线), 信区: GreatTurn
标 题: 称小球问题终结----m次称出(3^m-1)/2个球的解法
发信站: BBS 水木清华站 (Sat Jul 25 09:10:51 1998)

对于N(m)=(3^m-1)/2个小球，现在我们来寻求m次的解法。
首先，对于m=2的情况，相当于四个小球来称两次的情况，这个已经讨论过多次了，也很简单，在此略去
其次，若m<=k-1时，假定对于N(k-1)=(3^(k-1)-1)/2个球的情况我们都有解法。
  现在来考虑m=k的情况。
  第一次称取[3^(k-1)-1]个球放在天平天平两端，则：  
   如果平衡，获得[3^(k-1)-1]个标准球，坏球在剩下的[3^(k-1)+1]/2个中。由于
     [3^(k-1)-1]>=[3^(k-1)+1]/2，（k>=2),即已知的标准球数不小于未知球数;
     所以在以后的测量中就相当于任意给定标准球的情况，由前面的引理二可知
     对于[3^(k-1)+1]/2的情况(k-1)次可解。
   如果不平衡，大的那方记做A,小的那方记作B。标准球记做C.
   则现在我们有[3^(k-1)-1]/2个A球和B球，有[3^(k-1)+1]/2个C球。
     第二次用3^(k-2)个A球加[3^(k-2)-1]/2个B球放左边;
         3^(k-2)个C球加[3^(k-2)-1]/2个A球放右边。
      如果左边大于右边，则说明是在左边的3^(k-2)个A球中质量大的为坏球；
      如果左边等于右边，则说明是在第二次称时没用的3^(k-2)个B球中质量轻
          的为坏球。以上两种情况都可以再用三分法(k-2)次解决，加上前两
         次共k次解决。
      如果左边小于右边，则坏球在左边的[3^(k-2)-1]/2个B球中或在右边的同样
       数目的A球中。此时的情况和第二次开始时类似（只不过是k-1变成k-2).
       用相同的办法一直往下追溯到一个A球和一个B球一次区分的情况，这时
       只需拿A球和标准球比较以下就行了。
       因此在这种情况下也是可以最终用k次解决的。

由以上两步加上数学归纳法知，对于N(m)=(3^m-1)/2的情况，称m次是可以称出来的。

由这个解法加上前面所给出的上界Nmax(m)<=(3^m-1)/2，知称m次能解决的最大的小球数
Nmax(m)=(3^m-1)/2。
有兴趣的人可以验证一下m=3,N=13的情况----该情况已经被反复拿出来讨论过了。


三、

发信人: Nature (成长的烦恼), 信区: Mathematics
标 题: [转载] 关于称球问题的我的解答
发信站: 南京大学小百合站 (Wed Nov 8 17:47:05 2000), 站内信件

【 以下文字转载自 Algorithm 讨论区 】
【 原文由 grass 所发表 】

我们来分析第一次称的三堆球：
(一)若不平衡，我们得到的信息是：
1． 坏球在天边上的两堆里；
2． 有一堆的球重，一堆轻。

大家往往会忽视第二条信息，实际上这条信息是非常重要的。
若我们知道一些球的轻重关系，我们可以用比不知道这个关系称的次数更少就得出结论。如：若告诉你坏球轻，那么27个球只要三次就够了。

所以我们要研究一下，若我们知道一些球的轻重关系，n次最多可以称出多少个球。我们用函数h(n)表示。

（二）若平衡，则得到的信息是：
1． 坏球在剩下的一堆中；
2． 有若干个好球可以给我们利用。
第二条信息又是大家容易忽视的。就如12个球，称第一次若平衡，我们就可以用天平上
的球作为标准球。有标准球，两次可以称称出4个球（见第一试题解答部分的2—5）；若
没有的话，就只能称出3个球。

所以我们还要研究一下，若我们有一个标准球，n次最多可以称出多少个球。我们
用函数g(n)表示。

定义一：若一个球，若知道它不可能偏重（或知道不可能偏轻），则我们称此球为半确定重球（或半确定轻球）；半确定重球和半确定轻球统称为半确定球。
第一题中，通过第一次称重后，若不平衡，则1,2,3,4,5,6,7,8号球都成为半确定球，
若1，2，3，4〈5，6，7，8，则1,2,3,4为半确定轻球，5,6,7,8为半确定重球。

定义二：若一个球，若知道它是好球，则我们称此球为确定好球；若知道是坏球，确定坏球。确定好球和确定好球统称为确定球。
第一题中，通过第一次称重后，若平衡，则1,2,3,4,5,6,7,8号球都成为确定球好球。

定义三：若一个球，既不是确定球，也不是半确定球若，则我们称此球为不确定球。
第一题中，通过第一次称重后，则9，10，11，12号球都成为不确定球。
一次未称之前，所有球都是不确定球。

引理一、对于放上过天平的球，都是半确定球或是确定球
这是个显然成立的命题。

定义四：若所有球都是半确定球，那么n次可称出的球的最大个数我们用 h(n)表示。

引理二：h(n)=3^n。

证明：
用归纳法来证：
⑴对于n=1,先证3个球是可称的，再证4个是不可称的。
① 3个球可称，
若全为半确定重球，任意挑两个，若不平衡，重的就是坏重球；否则，剩下的那个就是坏重球；
全为半确定轻球同理；
若两个半确定重球，一个半确定轻球，则称两个两半确定重球，若不平衡，重的就是确定重球；否则，剩下的那个就是确定轻球；
若一个半确定重球，两个半确定轻球同理。
所以，3个求可称。

②四个球不可称
若是4个球，天平称一次，只能提供三条信息，由抽屉原理，必然有两个球的信息是相同的。故一次无法保证能判断出来。
故，n=1是h(n)=3^n是成立的。
⑵设n = k时命题成立，对于n=k+1
①先证t=3^(k+1)个球是可判断的：
  设t中有a个半确定重球，b个半确定轻球,t =a + b ;
  由对称性，不妨设a>b (a + b是奇数，所以不可能相等)

  按如下方法分为三堆：
若a>=2*(3^k),则天平两边各放3^k个半确定重球。若不平衡，坏球在重的那堆中；平衡的话，坏球在剩下的那堆中。这时剩3^k个球，k次可判断出来，共k+1次，成立。

若a<2*(3^k), 则天平两边各放[a/2]个半确定重球,3^k-[a/2]个半确定轻球。若不平衡，坏球在重的那堆中的半确定重球或轻的那堆半确定轻球中；平衡的话，坏球在剩下的那堆中。这时剩3^k个球，k次可判断出来，共k+1次，成立。
  a < b 同理可证。
所以3^(k+1)个球是可判断的。

②若3^(k+1)+1个球，称一次，只能提供三条信息，由抽屉原理，必然有3^k+1个球的信息是相同的，这3^k+1个球无法用k次称出。故k+1次无法保证能判断出来。
故，n=k+1也成立。
由归纳法，h(n)=3^n对一切自然数都成立。

再回到原题，来求f(n).
对于第一次处理后，若不平衡，天平两边的球都将成为半确定球。设两边球个数各为a个，另外一堆个数为b个。易知，a与b相互独立。为使得f(n)=2a+b最大，即要分别求出a , b的最大值。
由引理二，这2a个半确定球要在n-1次判断出，当且仅当
2a <= h (n-1)=3^(n-1).
但等号无法取到，因为3^(n-1)为奇数,所以2a<=3(n-1)-1,
max(a)=(3^(n-1)-1)/2