周二被问到的两个问题 2014-03-03

本文从WordPress迁移而来, 查看全部WordPress迁移文章

差点忘记了……

  1. 设电梯长度为L1,平路长度为L2,绑鞋带时间为S,人速度为v,电梯速度为u。分两种情况讨论,S <= L1/u,即人若在电梯上绑鞋带,绑完后还没离开电梯;S >= L1/u , 即人若在电梯上绑鞋带,绑完之前电梯已经运行完了。两种情况计算的结果都是在电梯上绑鞋带会更快啊(这其实很显然吧…),但那天被问到的时候,想多了,没坚定啊。被问到你会怎么做的时候,我说,用数学去证明啊,然后随便出了个数据,发现自己是对的,然后无奈地说那我用大量地随机数据去验证……(后来想想有点搞笑啊…..)
  2. 这题, 有点意思(没研究过博弈,搞过博弈的大牛应该一眼看出答案了吧….)。甲乙轮流取银币,甲先取,每人每次能取1~4个银币;只有1个金币,必须最后取,且银币和金币不能同时取,取到金币的人胜利。现有20个银币,谁能赢。
    答案是先手胜

    1. 银币数为4,先手取3个,剩下1个,后手必取,然后先手就胜了……
    2. 银币数为8,先手取2个,剩下6个,无论后手怎么取,都去不到第7个,所以第7个还是被先手取了,剩下1个,后手又败了…..
    3. 银币数为12,先手取1个,剩下11个,无论后手怎么取,先手再取的话,都能使得银币数剩下6个,回到了 2 这个情况,所以后手必败,先手必胜
    4. 银币数为16,无论先手怎么取,到后手取的话,都可以让银币数剩下11个,那么就回到了 3 , 只不过这次面对的人是先手,所以先手必败,后手必胜
    5. 银币数为20,先手马上拿掉4个,剩下16个,这时候面对这状态的人是后手,这是个必败态,所以后手必败,先手必胜

      所以这题的答案是,先手一开始拿4个,然后就进入必胜的节奏了……..

      这时候我们已经可以得到一个很重要的结论了,就是先手要想胜利的话,必须按照上面说的规则去取,很容易想到,如果先手不按上面的规则去取,他就是必败的,所以先手是必胜的且取法唯一(银币数为16的时候先手是必败的)

      不妨再推导下去

    6. 银币数为24,先手取3个,剩下21个;到后手取,但是后手无论怎么取,到先手取的时候,先手都可以令到银币剩下16个,所以后手要面对剩下16个银币的状态,这是个必败态,所以这局先手必胜

      然后就没必要推导下去了,可以看出这是个循环,总结这个规律就是

    7. 当每次取的银币数为1~k,而总银币数为m*k的时候,先手是有办法保证自己必胜的(且办法唯一)

    8. 当m = 1,2,3,4,5,6…………..,先手第一次取的银币数应该为 (k-1),(k-2)(k-3)……1,0,k,(k-1),(k-2),(k-3)………………
      这是个循环,循环节为 (k-1),(k-2)(k-3)……1,0,k ,注意0,先手必须取0个才能必胜,否则必败,但并不允许取0个,所以矛盾,那盘,先手是必败的!

(今天去了1个小时图书馆….写个证明就没了…..准备看书…..同学考公务员发个考题过来问…..又是数学的……..一个小时又没了……人生)