1.1 毒药问题
问题：有1000个一模一样的瓶子，其中有999瓶是普通的水，有1瓶是毒药。任何喝下毒药的生命都会在一星期之后死亡。现在你只有10只小白鼠和1个星期的时间，如何检验出哪个瓶子有毒药？
首先一共有1000瓶，2的10次方是1024，刚好大于1000， 也就是说，1000瓶药品可以使用10位二进制数就可以表示。
从第一个开始：
第一瓶 ： 00 0000 0001
第二瓶 ： 00 0000 0010
第三瓶 ： 00 0000 0011
……
第999瓶： 11 1111 0010
第1000瓶：11 1111 0011
需要十只老鼠，如果按顺序编号，ABCDEFGHIJ分别代表从低位到高位每一个位。 每只老鼠对应一个二进制位，如果该位上的数字为1，则给老鼠喝瓶里的药。 观察，若死亡的老鼠编号为：ACFGJ，一共死去五只老鼠，则对应的编号为 10 0110 0101， 则有毒的药品为该编号的药品，转为十进制数为：613号
1.2 分金块问题
问题：工人为老板打工，工作七天可以获得一块金子，工人每天可以分得一点金子，老板必须每天发金子，不能多给，也不能少给，把这个金子切两刀，就可以每天给工人发工资，请问怎么切？
切两刀将金子分成三份，1/7、2/7、4/7；
工作第一天 把1/7分给工人；
工作第二天 把2/7分给工人，并要回1/7那块金子，工人有2/7的金子；
工作第三天 把1/7给工人，工人有3/7金子；
工作第四天 把前两块金子要回，给工人4/7的金子 工人有4/7的金子；
工作第五天 把1/7分给工人 工人有5/7的金子；
工作第六天 把2/7分给工人，并要回1/7那块金子，工人有6/7的金子；
工作第七天 把1/7给工人，工人有完整的金子；
扩展：如何给工人发15天的工资？把金块分成1/15、2/15、4/15、8/15
2. 先手必胜问题
2.1 抢 30的必胜策略
问题：抢 30 是双人游戏，游戏规则是：第一个人喊“ 1 ”或“ 2 ”，第二个人要接着往下喊一个或两个数，然后再轮到第一个人。两人轮流进行下去，最后喊 30 的人获胜，问喊数字的最佳策略。
尽量喊3的倍数。
解析： 倒着看，喊 27 的人必胜。假设 A 喊了 27，B只能喊 28 或 29 ， 下个回合，A 一定可以喊30。以此类推，喊24的人必胜，即喊 3 的倍数者必胜
若双方争抢3的倍数（假设每次都是最优解），谁先喊，谁一定输
2.2 100本书，每次能够拿1~5本，怎么拿能保证最后一次是你拿？
如果最后一次是我拿，那么上回合最少剩下6本；
只要保持每个回合结束后都剩下6的倍数，且在这个回合中我拿的书和对方拿的书加起来为6本；第一次我必须先手拿4本(100 % 6 = 4)，这不算在第一回合内
2.3 轮流拿石子
问题1：一共有N颗石子，每次最多取M颗最少取1颗，A，B轮流取，谁最后会获胜？（假设他们每次都取最优解）
简单的巴什博奕
假如A先取，N<M，A获胜
N>M，若N能被（M + 1）整除时，A失败
若N不能被（M + 1）整除时，A获胜
解析：以A先手为例，N<M时A一次拿完（不可能给B留机会，前提就是每次取最优），不会给B留机会；
N>M时，A要想赢，必须要在自己倒数第二次取完的时候还剩下（M + 1）颗石子，这样不论B取几颗，A都获胜！因此要控制最后一轮的石子数量，分两种情况分析：
- N不能被（M + 1）整除，A先拿走n颗石子（使得剩下的石子数量是（M + 1）的整数倍），那么下一次B拿走k颗石子时，A就拿走（M + 1）- k颗石子。这样不论B怎么拿A总能控制剩下的石子数量是（M + 1）的整数倍，那么最后一轮一定剩下（M + 1）颗
- N能被（M + 1）整除，无论A怎么拿，B可以控制剩下石子数量（M + 1）的整数倍，在最后一轮之前B拿完后还剩（M + 1）颗，A拿多少颗都是输
问题2：有若干堆石子，每堆石子的数量是有限的，二个人依次从这些石子堆中拿取任意的石子，至少一个（不能不取），最后一个拿光石子的人胜利。
较复杂的尼姆博弈
3. 推理题
3.1 掰巧克力问题
问题：一块N * M大小的巧克力，每次掰一块的一行或一列，全部掰成 1 * 1 大小的巧克力需要掰多少次？
N * M - 1次；
不管怎么掰，每次只能把一个大块掰成两个小块，即每次掰只能增加1块巧克力； 那么将1块巧克力掰成N * M块小巧克力就需要掰N * M - 1次
3.2 辩论赛问题
问题：1000个人参加辩论赛，1对1进行辩论，淘汰输掉的一方，问需要安排多少场比赛才能角出冠军？
每场辩论赛只能淘汰一个人，要淘汰999个人则需要安排999场比赛
3.3 在24小时里面时针分针秒针可以重合几次
24小时中时针走2圈，而分针走24圈，时针和分针重合24-2=22次， 但秒针与二者重合只有0和12时两次
4. 概率问题
4.1 一个圆上随机画两条弦，求相交的概率？
四个点确定两条线，在一个圆上取四个点； 四个点画两条线有三种情况，其中只有一种情况是相交的，故相交概率为 三分之一
4.2 火枪手决斗，谁活下来的概率大？
问题：彼此痛恨的甲、乙、丙三个枪手准备决斗。甲枪法最好，十发八中；乙枪法次之，十发六中；丙枪法最差，十发四中。如果三人同时开枪，并且每人每轮只发一枪；那么枪战后，谁活下来的机会大一些？
参考回答： 一般人认为甲的枪法好，活下来的可能性大一些。但合乎推理的结论是，枪法最糟糕的丙活下来的几率最大；
那么我们先来分析一下各个枪手的策略：
如同田忌赛马一般，枪手甲一定要对枪手乙先。因为乙对甲的威胁要比丙对甲的威胁更大，甲应该首先干掉乙，这是甲的最佳策略。
同样的道理，枪手乙的最佳策略是第一枪瞄准甲。乙一旦将甲干掉，乙和丙进行对决，乙胜算的概率自然大很多。
枪手丙的最佳策略也是先对甲。乙的枪法毕竟比甲差一些，丙先把甲干掉再与乙进行对决，丙的存活概率还是要高一些。
我们根据分析来计算一下三个枪手在上述情况下的存活几率：
第一轮：甲射乙，乙射甲，丙射甲。
甲的活率为24%（40% X 60%）
乙的活率为20%(100% - 80%)
丙的活率为100%（无人射丙）
由于丙100％存活率，因此根据上轮甲乙存活的情况来计算三人第二轮的存活几率：
情况1：甲活乙死（24% X 80% = 19.2%） 甲射丙，丙射甲：甲的活率为60%，丙的活率为20%。
情况2：乙活甲死（20% X 76% = 15.2%） 乙射丙，丙射乙：乙的活率为60%，丙的活率为40%。
情况3：甲乙同活（24% X 20% = 4.8%） 重复第一轮。
情况4：甲乙同死（76% X 80% = 60.8%） 枪战结束。
据此来计算三人活率：
甲的活率为(19.2% X 60%) + (4.8% X 24%) = 12.672%
乙的活率为(15.2% X 60%) + (4.8% X 20%) = 10.08%
丙的活率为(19.2% X 20%) + (15.2% X 40%) + (4.8% X 100%) + (60.8% X 100%) = 75.52%
通过对两轮枪战的详细概率计算，我们发现枪法最差的丙存活的几率最大，枪法较好的甲和乙的存活几率却远低于丙的存活几率
4.3 100个奴隶猜帽子颜色
问题：一百个奴隶站成一纵列，每人头上随机带上黑色或白色的帽子，各人不知道自己帽子的颜色，但是能看见自己前面所有人帽子的颜色． 然后从最后一个奴隶开始，每人只能用同一种声调和音量说一个字：”黑”或”白”， 如果说中了自己帽子的颜色，就存活，说错了就拉出去斩了，说的参考回答所有奴隶都能听见。 是否说对，其他奴隶不知道。 在这之前，所有奴隶可以聚在一起商量策略，问如果奴隶都足够聪明而且反应足够快，100个人最大存活率是多少？
1、最后一个人如果看到奇数顶黑帽子报“黑”否则报“白”，他可能死
2、其他人记住这个值（实际是黑帽奇偶数），在此之后当再听到黑时，黑帽数量减一
3、从倒数第二人开始，就有两个信息：记住的值与看到的值，相同报“白”，不同报“黑” 99人能100%存活，1人50%能活
另外，此题还有变种：每个奴隶只能看见前面一个人帽子颜色又能最多存活多少人？ 参考回答：增加限制条件后，上面的方法就失效了， 此时只能约定偶数位奴隶说他前一个人的帽子颜色， 奇数奴隶获取信息100%存活，偶数奴隶50%几率存活
5. 水桶问题
5.1 水资源无限，5L和3L水桶各一个，怎样取4L的水？
初始时0，3（5L，3L）
交换3，0
注满3，3
倒入5，1
清空0，1
交换1，0
注满1，3
5.2 水资源无限，5L和6L水桶各一个，怎样取3L的水？
初始时5，0（5L，6L）
交换0，5
注满5，5
倒入4，6
清空4，0
交换0，4
注满5，4
导入3，6
5.3 一个装了10L水的桶，一个7L的空桶，一个3L的空桶，怎样变成2个5L？
（水有限，多解，思路a+b>c，且a<c b<c，用a+b-c）
初始时10，0，0
注满3，7，0
注满3，4，3
清空6，4，0
倒入6，1，3
清空9，1，0
交换9，0，1
注满2，7，1
注满2，5，3
合并5，5，0
6. 计时问题
6.1 有一个能计时6分钟的小沙漏和一个能计时8分钟的大沙漏，如何计时10分钟？
两个沙漏同时倒置开始计时，等小沙漏漏完，大沙漏还剩2分钟，这时倒置小沙漏继续计时；
大沙漏漏完小沙漏还剩4分钟，再把大沙漏倒置继续计时；
小沙漏漏完大沙漏还剩4分钟，这时准备工作已经完毕；
等待大沙漏漏完（4分钟）+ 小沙漏（6分钟） = 10分钟
6.2 烧一根绳子需要一个小时，现有若干条相同的绳子，问如何计时15分钟？
点燃绳子A的一头，同时点燃绳子B的两头； 绳子B烧完的时候绳子A还剩一半，此时点燃绳子A的另一头开始计时；15分钟绳子A烧完
6.3 蜡烛燃烧问题：两根蜡烛，燃烧完都需要1小时，怎么确定15分钟是多久？
点燃第一根的一端，第二根的两端
第二根烧完代表半小时后，点燃第一根另一端，烧完代表15分钟
7. 赛马问题
7.1 64匹马8条跑道找最快的4匹马，需要跑几次？
11
第一步：全部马分为8组，每组8匹，每组各跑一次，然后淘汰掉每组的后四名（需要比赛8场）
| A1 |
B1 |
C1 |
D1 |
E1 |
F1 |
G1 |
H1 |
| A2 |
B2 |
C2 |
D2 |
E2 |
F2 |
G2 |
H2 |
| A3 |
B3 |
C3 |
D3 |
E3 |
F3 |
G3 |
H3 |
| A4 |
B4 |
C4 |
D4 |
E4 |
F4 |
G4 |
H4 |
| A5 |
B5 |
C5 |
D5 |
E5 |
F5 |
G5 |
H5 |
| A6 |
B6 |
C6 |
D6 |
E6 |
F6 |
G6 |
H6 |
| A7 |
B7 |
C7 |
D7 |
E7 |
F7 |
G7 |
H7 |
| A8 |
B8 |
C8 |
D8 |
E8 |
F8 |
G8 |
H8 |
第二步：取每组第一名进行一次比赛，然后淘汰最后四名所在组的所有马，如下图（需要比赛1场）这个时候总冠军已经诞生，它就是A1，蓝域（它不需要比赛了）
| A1 |
B1 |
C1 |
D1 |
E1 |
F1 |
G1 |
H1 |
| A2 |
B2 |
C2 |
D2 |
E2 |
F2 |
G2 |
H2 |
| A3 |
B3 |
C3 |
D3 |
E3 |
F3 |
G3 |
H3 |
| A4 |
B4 |
C4 |
D4 |
E4 |
F4 |
G4 |
H4 |
| A5 |
B5 |
C5 |
D5 |
E5 |
F5 |
G5 |
H5 |
| A6 |
B6 |
C6 |
D6 |
E6 |
F6 |
G6 |
H6 |
| A7 |
B7 |
C7 |
D7 |
E7 |
F7 |
G7 |
H7 |
| A8 |
B8 |
C8 |
D8 |
E8 |
F8 |
G8 |
H8 |
而其他可能跑得最快的三匹马只可能是下图中的黄域了（A2,A3,A4,B1,B2,B3,C1,C2,D1，共9匹马）
| A1 |
B1 |
C1 |
D1 |
E1 |
F1 |
G1 |
H1 |
| A2 |
B2 |
C2 |
D2 |
E2 |
F2 |
G2 |
H2 |
| A3 |
B3 |
C3 |
D3 |
E3 |
F3 |
G3 |
H3 |
| A4 |
B4 |
C4 |
D4 |
E4 |
F4 |
G4 |
H4 |
| A5 |
B5 |
C5 |
D5 |
E5 |
F5 |
G5 |
H5 |
| A6 |
B6 |
C6 |
D6 |
E6 |
F6 |
G6 |
H6 |
| A7 |
B7 |
C7 |
D7 |
E7 |
F7 |
G7 |
H7 |
| A8 |
B8 |
C8 |
D8 |
E8 |
F8 |
G8 |
H8 |
第三步：只要从上面的9匹马中找出跑得最快的三匹马就可以了，但是现在只要8个跑道，怎么办？那就随机选出8匹马进行一次比赛吧（需要比赛一场）
第四步：上面比赛完，选出了前三名，但是9匹马中还有一匹马没跑呢，它可能是一个潜力股啊，那就和前三名比一比吧，这四匹马比一场，选出前三名。最后加上总冠军，跑得最快的四匹马诞生了！！！（需要一场比赛）
最后，一共需要比赛的场次：8 + 1 + 1 + 1 = 11 场
8. 过河/过桥问题
8.1 三人三鬼过桥（狼羊过河）
问题：有三个人跟三个鬼要过河,河上没桥只有条小船,然后船一次只能渡一个人和一个鬼,或者两个鬼或者两个人,无论在哪边岸上,只有是人比鬼少的情况下(如两鬼一人,三鬼两人,三鬼一人)人会被鬼吃,然而船又一定需要人或鬼操作才能航行(要有人或鬼划船),问,如何安全的把三人三鬼渡过河对岸?
先两鬼过去。在一鬼回来。对面有一鬼。这边有三人两鬼
再两鬼过去。在一鬼回来。对面有两鬼。这边有三人一鬼
再两人过去。一人一鬼回来。对面一人一鬼。这边两人两鬼
最后两人过去。一鬼回来。对面三人。这边三鬼
剩下的就三个鬼二个过去一个回来在接另外个就OK了
8.2 限时过桥问题
问题：在一个夜晚，同时有4人需要过一桥，一次最多只能通过两个人，且只有一只手电筒，而且每人的速度不同。A，B，C，D需要时间分别为：1，2，5，10分钟。问：在17分钟内这四个人怎么过桥？
总共是17分钟
第一步：A、B过花时间2分钟
第二步：B回花时间2分钟
第三步：C、D过花时间10分钟
第四步：A回花时间1分钟
第五步：A、B再过花时间2分钟
9. 最优解问题
9.1 猴子搬香蕉
问题：一个小猴子边上有100根香蕉，它要走过50米才能到家，每次它最多搬50根香蕉，（多了就被压死了），它每走1米就要吃掉一根，请问它最多能把多少根香蕉搬到家里。
（提示：他可以把香蕉放下往返的走，但是必须保证它每走一米都能有香蕉吃。也可以走到n米时，放下一些香蕉，拿着n根香蕉走回去重新搬50根。）
此题迷惑点在于：走一米吃一根香蕉，一共走50米，那不是把50根香蕉吃完了吗？如果要回去搬另外50根香蕉，则往回走的时候也要吃香蕉，这样每走一米需要吃掉三根香蕉，走50米岂不是需要150根香蕉？
本题关键点在于：猴子搬箱子的过程其实分为两个阶段，第一阶段：来回搬，当香蕉数目大于50根时，猴子每搬一米需要吃掉三根香蕉。第二阶段：香蕉数<=50，直接搬回去。每走一米吃掉1根
我们分析第一阶段：假如把100根香蕉分为两箱。一箱50根
第一步，把A箱搬一米，吃一根
第二步，往回走一米，吃一根
第三步，把B箱搬一米，吃一根
这样，把所有香蕉搬走一米需要吃掉三根香蕉
这样走到第几米的时候，香蕉数刚好小于50呢？ 100-3n<50 && 100-3(n-1)>50
走到16米的时候，吃掉48根香蕉，剩52根香蕉。这步很有意思，它可以直接搬50往前走，也可以再来回搬一次，但结果都是一样的。到17米的时候，猴子还有49根香蕉。这时猴子就轻松啦。直接背着走就行
第二阶段：走一米吃一根
把剩下的50-17=33米走完。还剩49-33=16根香蕉
9.2 高楼扔鸡蛋
问题：有2个鸡蛋，从100层楼上往下扔，以此来测试鸡蛋的硬度。比如鸡蛋在第9层没有摔碎，在第10层摔碎了，那么鸡蛋不会摔碎的临界点就是9层。如何用最少的尝试次数，测试出鸡蛋不会摔碎的临界点？
1 暴力法
举个栗子，最笨的测试方法，是什么样的呢？把其中一个鸡蛋，从第1层开始往下扔。如果在第1层没碎，换到第2层扔；如果在第2层没碎，换到第3层扔…如果第59层没碎，换到第60层扔；如果第60层碎了，说明不会摔碎的临界点是第59层
在最坏情况下，这个方法需要扔100次
2 二分法
采用类似于 二分查找 的方法，把鸡蛋从一半楼层（50层）往下扔
如果第一枚鸡蛋，在50层碎了，第二枚鸡蛋，就从第1层开始扔，一层一层增长，一直扔到第49层
如果第一枚鸡蛋在50层没碎了，则继续使用二分法，在剩余楼层的一半（75层）往下扔…
这个方法在最坏情况下，需要尝试50次
3 均匀法
如何让第一枚鸡蛋和第二枚鸡蛋的尝试次数，尽可能均衡呢？
很简单，做一个平方根运算，100的平方根是10
因此，我们尝试每10层扔一次：第1次从10层扔，第2次从20层扔，第3次从30层…一直扔到100层
这样的最好情况是在第10层碎掉，尝试次数为 1 + 9 = 10次
最坏的情况是在第100层碎掉，尝试次数为 10 + 9 = 19次
不过，这里有一个小小的优化点，我们可以从15层开始扔，接下来从25层、35层扔…一直到95层
这样最坏情况是在第95层碎掉，尝试次数为 9 + 9 = 18次
4 最优解法
最优解法是反向思考的经典：如果最优解法在最坏情况下需要扔X次，那第一次在第几层扔最好呢？
答案是：从X层扔
假设最优的尝试次数的x次，为什么第一次扔就要选择第x层呢？
假设第一次扔在第x+1层：如果第一个鸡蛋碎了，那么第二个鸡蛋只能从第1层开始一层一层扔，一直扔到第x层。这样一来，我们总共尝试了x+1次，和假设尝试x次相悖。由此可见，第一次扔的楼层必须小于x+1层
假设第一次扔在第x-1层：如果第一个鸡蛋碎了，那么第二个鸡蛋只能从第1层开始一层一层扔，一直扔到第x-2层。这样一来，我们总共尝试了x-2+1 = x-1次，虽然没有超出假设次数，但似乎有些过于保守
假设第一次扔在第x层：如果第一个鸡蛋碎了，那么第二个鸡蛋只能从第1层开始一层一层扔，一直扔到第x-1层。这样一来，我们总共尝试了x-1+1 = x次，刚刚好没有超出假设次数
因此，要想尽量楼层跨度大一些，又要保证不超过假设的尝试次数x，那么第一次扔鸡蛋的最优选择就是第x层。那么算最坏情况，第二次你只剩下x-1次机会，按照上面的说法，你第二次尝试的位置必然是X+（X-1）；以此类推我们可得：
x + (x-1) + (x-2) + … + 1 = 100
这个方程式不难理解：
左边的多项式是各次扔鸡蛋的楼层跨度之和。由于假设尝试x次，所以这个多项式共有x项。右边是总的楼层数100
x + (x-1) + (x-2) + … + 1 = 100 转化为 (x+1)*x/2 = 100
最终x向上取整，得到 x = 14
因此，最优解在最坏情况的尝试次数是14次，第一次扔鸡蛋的楼层也是14层。
最后，让我们把第一个鸡蛋没碎的情况下，所尝试的楼层数完整列举出来：
14，27， 39， 50， 60， 69， 77， 84， 90， 95， 99， 100
举个栗子验证下：
假如鸡蛋不会碎的临界点是65层， 那么第一个鸡蛋扔出的楼层是14，27，50，60，69。这时候啪的一声碎了。 第二个鸡蛋继续，从61层开始，61，62，63，64，65，66，啪的一声碎了。 因此得到不会碎的临界点65层，总尝试次数是 6 + 6 = 12 < 14
9.3 利用空瓶换饮料，最多喝几瓶
问题：1000瓶饮料，3个空瓶子能够换1瓶饮料，问最多能喝几瓶？
第一种思路:
拿走3瓶，换回1瓶，相当于减少2瓶。但是最后剩下4瓶的时候例外，这时只能换1瓶。所以我们计算1000减2能减多少次，直到剩下4.
（1000-4=996，996/2=498）所以1000减2能减498次直到剩下4瓶，最后剩下的4瓶还可以换一瓶，所以总共是1000+498+1=1499瓶。
第二种思路:dp
初始情况，3个瓶子时将发生一次交换，因此视为特殊情况
之后每增加两个瓶子又可以再换一瓶
即dp[i] = dp[i - 2] + (i - (i - 2)) + 1
由dp[i - 2]可求得dp[i]
(i - (i - 2))，即为当前增加的2瓶饮料（写成这样便于理解）
1即为增加了2个空瓶，之后又可以换一瓶饮料
简化为dp[i] = dp[i - 2] + 2 + 1
10. 数字问题
10.1 11223344问题
问题：有8个数，11223344，将其排列，要求结果满足：两个1之间有一个数，两个2之间有两个数，两个3之间有三个数，两个4之间有四个数。问这个结果是多少？
41312432 或 23421314
位数有限，所以先排最大的4，再排3再排2
10.2 给定随机函数，生成别的随机数
问题：给定生成1到5的随机数Rand5()，如何得到生成1到7的随机数函数Rand7()？
思路 ：由大的生成小的容易，比如由Rand7()生成Rand5()，所以我们先构造一个大于7的随机数生成函数。 记住下面这个式子：
RandNN= N( RandN()-1 ) + RandN() ;// 生成1到N^2之间的随机数
可以看作是在数轴上撒豆子。N是跨度/步长，是RandN()生成的数的范围长度，
RandN()-1的目的是生成0到N-1的数，是跳数。后面+RandN()的目的是填满中间的空隙
比如 Rand25= 5( Rand5()-1 ) + Rand5() 可以生成1到25之间的随机数。我们可以只要1到21（3*7）之间的数字，所以可以这么写
int rand7(){
int x=INT_MAX;
while(x>21){
x=5*(rand5()-1)+rand5();
}
return x%7+1;
}
11. 重量问题
11.1 乒乓球重量问题：8个乒乓球，其中一个重，有一个秤，问至少几次能够找出重的那个乒乓球
2次，分成3堆，3，3，2。
①称3和3，如果一样重，代表重的在2
②称2个那一堆的
或
①称3和3，不一样重，重的在3里面重的那堆
②3个里面随便取2个，一样重，第三个重，不一样重，重的那个就是
11.2 盐重量问题：有7克、2克砝码各一个，天平一只，如何只用这些物品五次内将140克的盐分成50、90克各一份？
第一次：先分成70和70（140在天平两边平衡即可）
第二次：通过7和2砝码将70分成9和61
第三次：通过9克盐和2砝码将61分成50和11
11.3 有一个天平，九个砝码，其中一个砝码比另八个要轻一些，问至少要用天平称几次才能将轻的那个找出来？
需要称2次；
天平一边放三个砝码，哪边轻就在哪边，一样重就在剩下的三个砝码中；
现在已经锁定了三个砝码，天平一边放一个，哪边轻是哪个，一样重就是剩下的那个；
11.4 十组砝码每组十个，每个砝码都是10g重，但是现在其中有一组砝码每个都只有9g重，现有一个能显示克数的秤，最少称几次能找到轻的那组？
称一次即可
将砝码分组编号1~10， 第1组拿1个砝码、第2组拿2个…第10组拿10个，全部放到秤上计算总克数X； Y = (1*10 + 2 * 10 + … + 10 * 10) - X = 550 - X，Y即为轻的那组的编号
以此类推药丸问题，多瓶药丸其中一瓶变质
12. 灯泡开关问题
12.1 在房里有三盏灯，房外有三个开关，在房外看不见房内的情况，你只能进门一次，你用什么方法来区分那个开关控制那一盏灯？
打开一个开关，过10分钟后关掉开关，并打开另一个开关。进屋确认可知：
亮的灯是由第二次打开的开关控制；
摸上去发热的不发亮的灯是由第一次打开的开关控制
剩下的第三盏灯是由未操作过的开关控制
12.2 一个圆环上有 100 个灯泡，灯泡有亮和暗两种状态。按一个灯泡的开关可以改变它和与它相邻两个灯泡的状态。设计一种算法，对于任意初始状态，使所有灯泡全亮
将灯泡编号 1 ~ 100
步骤一：将灯泡变为全亮或只剩一个为暗
从 1 循环到 98 ，遇到暗的则按它下一个，使之变亮。循环完毕，1 ~ 98 必然全亮。99 和 100可能为亮亮、暗亮、亮暗、暗暗四种状态
若为亮亮，皆大欢喜，满足题目要求
暗亮、亮暗，达到只剩一个为暗的状态；
若为暗暗。则按下编号 100 的灯泡，使编号 99 、100 变为亮，编号 1 的灯泡变为暗，从而达到只剩一个为暗的状态
步骤二：将灯泡变为全暗
由于灯泡环形摆放，我们指定暗的灯泡编号为 1 ，将剩下 99 个亮着的灯泡每 3 个为一组。按下每组中间的灯泡后，使得所有灯泡变为暗
步骤三：将灯泡变为全亮
将所有灯泡按一下，灯泡变为全亮;
扩展:对于 N 个灯泡的任意初始状态 ( N > 3 ) ，能否经过若干次操作使得所有灯泡全亮？
答案：N 个灯泡做分类讨论。
N = 3k+1一定可以。方法与上述步骤相同，在步骤二中可以将3k个亮的灯泡分为k组。
N = 3k+2一定可以。将上述步骤一目标状态的只剩一个为暗改成剩两个相邻为暗，其余 3 * k 个灯泡分组按即可。因为，对于任意只剩一个为暗的状态，按下该灯泡左右任意一个就可以变成剩两个相邻为暗的状态！
N = 3*k不一定。如果经过上述步骤一可以将灯泡变成全亮的状态则有解；否则，无解。（该结论有待证明）
附:
对于这道题，以下两个状态可以相互转化
全暗 <=> 全亮。全暗和全亮状态可以相互转化，方法就是将每个灯泡按一次。这样每个灯泡都被改变了 3 次状态，使得全暗变为全亮，全亮也可变为全暗。
剩一个为暗 <=> 剩两个相邻为暗。剩一个为暗时，按下该灯泡左右任意一个，就变成了剩两个相邻为暗的状态；剩两个相邻为暗时，按下第二个暗，便可变成了剩一个为暗的状态
13. 蓝眼/疯狗/耳光问题
13.1 蓝眼睛问题
问题：有个岛上住着一群人，有一天来了个游客，定了一条奇怪的规矩：所有蓝眼睛的人都必须尽快离开这个岛。每晚8点会有一个航班离岛。每个人都看得见别人眼睛的颜色，但不知道自己的（别人也不可以告知）。此外，他们不知道岛上到底有多少人是蓝眼睛的，只知道至少有一个人的眼睛是蓝色的。所有蓝眼睛的人要花几天才能离开这个岛？
有多少个蓝眼睛的人就会花多少天。
c=1
假设岛上所有人都是聪明的，蓝眼睛的人四处观察之后，发现没有人是蓝眼睛的。但他知道至少有一人是蓝眼睛的，于是就能推导出自己一定是蓝眼睛的。因此，他会搭乘当晚的飞机离开。
c=2
两个蓝眼睛的人看到对方，并不确定c是1还是2，但是由上一种情况，他们知道，如果c = 1，那个蓝眼睛的人第一晚就会离岛。因此，发现另一个蓝眼睛的人仍在岛上，他一定能推断出c = 2，也就意味着他自己也是蓝眼睛的。于是，两个蓝眼睛的人都会在第二晚离岛
c>2
逐步提高c时，我们可以看出上述逻辑仍旧适用。如果c = 3，那么，这三个人会立即意识到有2到3人是蓝眼睛的。如果有两人是蓝眼睛的，那么这两人会在第二晚离岛。因此，如果过了第二晚另外两人还在岛上，每个蓝眼睛的人都能推断出c = 3，因此这三人都有蓝眼睛。他们会在第三晚离岛
不论c为什么值，都可以套用这个模式。所以，如果有c人是蓝眼睛的，则所有蓝眼睛的人要用c晚才能离岛，且都在同一晚离开
13.2 疯狗问题
问题：有50家人家，每家一条狗。有一天警察通知，50条狗当中有病狗，行为和正常狗不一样。每人只能通过观察别人家的狗来判断自己家的狗是否生病，而不能看自己家的狗，如果判断出自己家的狗病了，就必须当天一枪打死自己家的狗。结果，第一天没有枪响，第二天没有枪响，第三天开始一阵枪响，问：一共死了几条狗？
死了3条（第几天枪响就有几条）
如果只有一条病狗，病狗的主人会发现其他49条狗都是健康的，那么第一天晚上就会有枪响。
如果有两条病狗，两条病狗的主人会发现其他48条狗都是健康的，有一条是病狗。那么他们都会期待第一天晚上会有一声枪响（情况1）。但是第一天晚上没有枪响，那么第二天晚上这两个猎人会开枪杀死自己狗。
如果有三条病狗，三条病狗的主人会发现其他47条狗都是健康的，有两条是病狗。那么他们都会期待第二天晚上会有两声枪响（情况2）。但是第二天晚上没有枪响，那么第三天晚上这三个猎人会开枪杀死自己狗
13.3 耳光问题
问题：一群人开舞会，每人头上都戴着一顶帽子。帽子只有黑白两种，黑的至少有一顶。每个人都能看到其他人帽子的颜色，却看不到自己的。主持人先让大家看看别人头上戴的是什么帽子，然后关灯，如果有人认为自己戴的是黑帽子，就打自己一个耳光。第一次关灯，没有声音。于是再开灯，大家再看一遍，关灯时仍然鸦雀无声。一直到第三次关灯，才有劈劈啪啪打耳光的声音响起。问有多少人戴着黑帽子？
有三个人戴黑帽
假设有N个人戴黑帽，当N＝1时，戴黑帽的人看见别人都为白则能肯定自己为黑。于是第一次关灯就应该有声。可以断定N＞1。对于每个戴黑帽的人来说，他能看见N-1顶黑帽，并由此假定自己为白。但等待N-1次还没有人打自己以后，每个戴黑人都能知道自己也是黑的了。所以第N次关灯就有N个人打自己
14. 圆桌放置硬币
问题：双人游戏在一个圆桌上进行。每个游戏者都有足够多的硬币。他们需要在桌子上轮流放置硬币，每次必需且只能放置一枚硬币，要求硬币完全置于桌面内（不能有一部分悬在桌子外面），并且不能与原来放过的硬币重叠。谁没有地方放置新的硬币，谁就输了。游戏的先行者还是后行者有必胜策略？这种策略是什么？
先行者在桌子中心放置一枚硬币，以后的硬币总是放在与后行者刚才放的地方相对称的位置。这样，只要后行者能放，先行者一定也有地方放。先行者必胜
15. 狼吃羊问题
问题：故事发生在某个神奇的草原：草原上有100只狼和1只羊。狼可以吃草也可以吃羊。按照常理，狼当然更喜欢吃羊。但是，如果狼吃了羊，狼就会变成羊，从而可以被其他狼追上，并吃掉。这些狼的奔跑速度各不同，但是都非常理性。假设羊不能被两只或者更多狼分吃。
请问：羊会不会被狼吃？请写出推理过程。
情况1：2只狼和1只羊时，吃了羊的狼会被另一只狼吃掉，所以2只狼一只羊会稳定
情况2：3只狼和1只羊时，一只狼吃了羊后会变成情况1，所以不会被吃，则2最终会变成1
情况3：4只狼和1只羊时，一只吃了羊后会变成情况2，会被其他狼吃掉，所以情况3会稳定
…
递推可得：偶数只狼时，羊不会被吃掉；奇数只狼时，羊会被吃掉。
