trick problems

收集各类 trick problems，积少成多，锻炼思维，防止老年痴呆。

虽然这些问题各种奇奇怪怪，但是也是有些门道可循的，转换为数学问题、反证法、逆向思维、找到里头可以 trick 的点。

有时候，虽然解不出答案，但是能把思考过程说出来也是很好的。

2 刀分 7 天工资

Q:老板有一块金子，恰好是程序员 Zing 一周的工资，每天工资一样。老板需要每天向 Zing 支付工资，不得多付，不得拖欠，仅允许对金子切 2 刀。问解决方案。

A：把金子分为 1/7,2/7,4/7。第一天支付 1/7，第二天拿 2/7 换 1/7，第三天再给 1/7，第四天拿 4/7 换 1/7 和 2/7...

海盗分赃问题

Q:5 个海盗抢到 100 个金币，每个一样大。5 人按照顺序提出分配方案，然后所有人表决，半数以上人同意时采用该分配方案，否则将提方案的人丢进大海喂鲨鱼。
前提：海盗的决策都是聪明的，海盗都是贪婪而且残忍的。

A： 从后往前考虑

• 若前 3 个都被扔到海里，只剩下 4 和 5，4 不可能获得一半以上的票数，那么 4 只有死路一条，因此无论 3 什么提案都要同意。
• 那么对于 3 来说，干掉 1 和 2 之后，只剩下 3 人，有了自己和 4 那一票，无论自己什么提案都可以通过，因此提出 100，0，0
• 对于 2 来说，若要使自己的提案通过，还需要拉拢 2 票。因此需要给出的 offer 比 3 的提案更好，因此只能拉拢 4 和 5 两人，98，0，1，1
• 对于 1 来说，也需要拉拢 2 票，所有最优的提案是 97，0，1，2，0 或 97，0，1，0，2

百人开灯

Q：房间里头有 100 个灯对应 100 个开关，按顺序从 1 到 100 编号，初始全部灯均关闭。门外有 100 个人，按顺序 1 到 100 编号，每个人依次进入，且必须开或关 那些灯的编号可以整除自己编号的开关。问所有人经过后，房间里有哪些灯是亮的。

A：这道题其实是问每个数的因数个数是奇数还是偶数。任意数 n 的因数都是成对出现的，1 和 n，a 和 n/a 等等，但是这其中有一个特殊情况，若 a=n/a 那么因数的个数就变成奇数了。所以房间里 1，4，9，25，36，49，64，81（n^2<=100）是亮的。

5L 和 3L 杯子量 4L 水

Q：只有 5L 和 3L 的无刻度杯子各一个，水无限，要求量出 4L 水

A：思路是 4=3+1，4=5-1

• 4=3+1：3L 杯子装满，倒到 5L 杯子中，3L 杯子再装满，倒到 5L 杯子直到 5L 杯子满，此时 3L 杯子中剩下 1L 水。把 5L 杯子里的水倒掉，3L 杯子中的 1L 倒入 5L 杯子中，3L 杯子再装满，倒到 5L 杯子中。
• 4=5-1：5L 杯子装满，倒到 3L 杯子中直到 3L 杯子满，此时 5L 杯子中剩下 2L，3L 杯子中的水倒掉，把 5L 杯子中的 2L 水倒到 3L 杯子中，5L 杯子水装满，然后往 3L 杯子倒水直到 3L 杯子满。

烧绳子

Q：两根燃烧速度不均匀的绳子，但是烧完均 60 分钟，要求计时 30 分钟和 45 分钟。

A：30 分钟：一根绳子两头同时点着，烧尽即为 30 分钟。45 分钟，第一个绳子两头同时点着，同时第二根绳子点着一头，当第一根绳子烧尽的时候把第二根绳子另一头也点上，第二根绳子烧尽即为 45 分钟。

兔子试毒药

Q：有 1000 瓶药水，其中只有 1 瓶是毒药，兔子喝毒药 1 天后才会死，问最少用几只兔子能找到那瓶毒药？

A：2^9<1000<2^10，因此最少 10 只兔子可以试出毒药。解决方法是，将 10 只兔子进行编号 10 到 1 表示 2 进制从高位到低位，将 1000 瓶药水进行编号 1 到 1000。将药水编号转化为 2 进制，哪些位置上为 1，喂给对应的兔子，如 7 号药水 2 进制是 0000000111 ,喂给 1、2、3 号兔子。1 天后，观察哪些兔子死了，将死亡兔子位置设为 1，转换为 10 进制则是对应的毒药。若只有 1、2、3 号兔子死亡，则 0000000111=7 号药水有毒。

拿球问题

Q：现在有 100 各球，甲乙两人轮流拿球，每人每次只能拿 1-5 个球，拿到最后一个球为胜者。若甲先拿球，有办法保证甲一定获胜吗？如果有甲应该如何拿。

A：从后往前推，若甲拿到第 94 个球，则无论已如何拿，甲总能拿到第 100 个球。为了保证拿到第 94 个球，甲必须保证拿到第 88 个球。以此类推，甲必须拿到第(100-n*6)个球。因此为了获胜，甲第一次需要拿 4 个球，之后每次根据乙拿 x 个，甲再拿(6-x)即可。

青蛙跳楼梯

Q:有 100 阶楼梯，小青蛙一次能跳 1 阶、2 阶或 3 阶。求问小青蛙恰好跳到第 100 阶，有多少种跳法？

A：这道题用动态规划解决，定义 d[i]=n 为跳到第 i 阶有 n 种方法。则有：对于 i=100,小青蛙可以先跳到 99 阶，再跳 1 阶到 100；也可以跳到 98 阶，再跳 2 阶到 100（不能跳 1+1，因为会和 99 重复）；也可以跳到 97 阶，再跳 3 阶到 100。d[i]=d[i-1]+d[i-2]+d[i-3]

Q:现在小青蛙长成大青蛙了，大青蛙可以一次跳 1、2、3、...、n 阶楼梯，求问大青蛙有多少种方法跳 n 阶。

A：对于这道题再用动态规划就把问题复杂化了。转化一种思路。总共 n 阶楼梯，第 n 阶肯定要到达，那么剩下的 n-1 阶，每一阶大青蛙可能落到也可能跳过（0 或 1），可以当作一个 n-1 位的 2 进制数，因此很直接的有 2^(n-1)种可能。

天堂与地狱

Q：你来到一个天堂和地狱的岔路口，但是不知道哪边是通往天堂哪边通往低于。岔路口有两个人，都直到路往何方，但是其中一个只有说实话，一个只会说假话，你并不认识他们，你可以向两人问相同的问题，若要去天堂，该如何问？

A：你可以这么问“若我问另外一个人地狱怎么走，他会指哪条路？”。无论问哪个人，都会指向同一条路，且这条路就是通向天堂的路。True and False = False and True = False

硬币问题

Q：有 25 个硬币，其中 10 个正面朝上，你被蒙住眼睛，也无法通过手摸出正反面。要求你将硬币分为两堆。使两堆硬币正面朝上的个数一样。

A:将硬币分成两堆分别为 15 和 10。15 个硬币中正面朝上有 a 个，10 个硬币中正面朝上有 b 个，背面朝上有 c 个。则有 a+b=b+c=10。即 a=c，15 个中正面朝上的硬币个数=10 个中背面朝上的硬币个数，因此只需要把 10 个那堆的硬币全部翻转一遍即可。