智力题整合
地球上是否存在一个点， 向南10m， 东10m， 北10m回到原点（作业帮）page 45
北极点。
除了北极之外，还有另一类解在南极附近存在。设想你在某个点出发，先向南走10米，到达一个纬圈。如果这个纬圈的周长正好是10米的整数分之一（即10/n米，其中 n 是正整数），那么向东走10米时，你会正好绕该纬圈转动整数圈，回到同一点。再向北走10米，自然也回到了原点。这样的点在南极附近存在无数个。
36匹马6个跑道无计时器，决出前三。（小鹏）page 45
8次。我们将马平均分为 A B C D E F 6个区域 因为我们要决出前三名 一开始将6个区域各跑一次留下每个区域的前三 A区前三的命名为A1 A2 A3 B区前三的命名为B1 B2 B3 C区前三的命名为C1 C2 C3 D区前三的命名为D1 D2 D3 E区前三的命名为E1 E2 E3 F区前三的命名为F1 F2 F3 此时一共跑了6次 然后我们将每个区域的第一 A1 B1 C1 D1 E1 F1 放一起跑一次决出冠军 这时我们假设A1>B1>C1>D1>E1>F1 此时A1获得了冠军 一共跑了6+1=7次 这个时候我们要决出亚军和季军 每个区域的前两名保留 所以还剩 A2 A3 （因为A1是冠军，所以A区前两名为A2 A3） B1 B2 C1 C2 D1 D2 E1 E2 F1 F2 因为 B1 C1 D1 E1 F1作为各个区域的第一 又因为 B1>C1>D1>E1>F1 所以D区E区和F区全部淘汰（因为D1、E1和F1作为他们各个区域最快的，却跑不过B1和C1） C区只剩下C1 (因为 B1>C1，C1>C2,所以C2争夺不了亚军和季军) 这时还剩 A2 A3 （因为A1是冠军，所以A区前两名为A2 A3） B1 B2 C1 此时，剩下的五匹马就可以决出亚军和季军 7+1=8次
64匹马8个跑道，决出前4（字节）page 158
分组赛：8轮。
冠军赛：把每组第一名进行一场比赛。假设A1最快，而A1>B1>C1>C2，因此C3，C4直接淘汰。同理B4，D2-D4，E1-E4，F1-F4，G1-G4，H1-H4直接淘汰。
最后一轮：现在A1已经晋级，在A2-A4，B1-3，C1-2，D1这9匹马选3，此时D1是最危险的，因为已经知道有2匹马比他快，选择除了D1之外的8匹马比赛。
如果C1是第二名晋级，也就是除D1的比赛中的第二名，那么还要把剩下的拉上D1再赛一场。
如果C1以第三名至第第七名，则无需加赛。
总结：10场或11场。
100匹马，4赛道，决出前4（腾讯）
TODO
有100枚硬币，其中有一枚是假币，已知假币的重量较轻。现只有一个天平，要求用尽量少的比较次数找出这枚假币。（恒生）page 1
是一个经典的分治算法问题。我们可以通过逐步减少硬币的数量来找到假币，每次比较都将硬币分成三组。
将100枚硬币分成三组：33枚、33枚和34枚。 使用天平比较前两组（33枚 vs 33枚）。 比较结果分析：
如果两组重量相等，则假币在第三组（34枚）中。 如果两组重量不等，则假币在较轻的那一组中。 递归处理：
将包含假币的那一组继续分成三组，重复上述步骤，直到找到假币。 最小比较次数：
通过这种分组策略，每次比较可以减少三分之一的硬币数量。 理论上，最少需要比较的次数为 log₃(100)，为5次。
井盖为什么是圆的？（腾讯）page 1
参考。
圆形的井盖在任何角度都不会掉下去。
圆柱形能最大程度承受周围土地的压力。
一家人过桥问题。小明一家人过桥，现在是黑夜，所以必须要有灯。小明过桥要1秒，弟弟要3秒，爸爸要6秒，妈妈要8秒，爷爷要12秒。此桥每次最多可过2人，过桥速度依最慢者而定，灯在点燃后30秒就会熄灭。请问小明一家应如何过桥？（字节）page 53
最简单方案。每次都让小明与其他人过桥，小明单独返回取灯。总时间=（3+1）+（6+1）+（8+1）+12=32秒。
优化思路。让耗时接近的人一起过桥，用小明和弟弟作为快递员，送回灯具。1.小明和弟弟过桥，小明带灯返回。2.妈妈和爷爷过桥，弟弟带灯返回。3.小明和爸爸过桥，小明带灯返回。4.小明和弟弟过桥。
8个小球，其中7个质量相同，1个质量小，现在给你一个称，最少称几次可以确保一定能找到不同的小球。（腾讯）page 44
2次。
第一次称重。将8个小球分成3、3、2三组。如两边平衡，则较轻的在剩下两个中。如果不平衡，则较轻的一边中3个球必有一个是较轻的小球。
第二次称重。如果平衡，那将剩下两个小球直接比较，较轻者就是答案。如果不平衡，则从较轻的3个球任意取两个。
现有若干不均匀的绳子，烧完这根绳子需要一个小时，问如何准确计时15分钟，30分钟，45分钟，75分钟 page 1
30分钟：取一根绳子A，同时将A两端点燃。A完全燃尽过去30分钟。
15分钟：取两根绳子A B，A从两端开始点燃，B从一端点燃，当A燃尽时，熄灭B。此时绳子B燃尽所需的时间就是30分钟，从绳子B两端点燃，就是15分钟。
45分钟：取30分钟和15分钟相加。
75分钟：取60分钟和15分钟相加。
有100名犯人排成一列，每人头上戴一顶黑帽子或白帽子。每个人只能看到自己前面所有人的帽子，看不到自己的和身后人的。从最后面（能看最多人帽子的那位）开始，依次向前报“黑”或“白”各一次，所有人都能听到他报的结果。报对自己帽子颜色的存活，报错被处决；其他人听到报什么，但不知道对错。事先可以开会商量策略，之后不能再交流。问：在最优策略下，100人中最多能保证有多少人存活？ page 1
最多99人存活。约定黑色帽子的奇偶作为校验位。最后一位报出的黑或白代表他看到前面的99顶帽子中黑帽子的奇偶（如黑代表奇数，白代表偶数）。从倒数第二位，每个人都能通过，后面的人报的是校验位，可以推断出自己的帽子颜色。
有100名犯人排成一列，每人头上戴一顶黑帽子或白帽子。每个犯人只能看见前面一个人帽子颜色，看不到自己的和身后人的。从最后面（能看最多人帽子的那位）开始，依次向前报“黑”或“白”各一次，所有人都能听到他报的结果。报对自己帽子颜色的存活，报错被处决；其他人听到报什么，但不知道对错。事先可以开会商量策略，之后不能再交流。问：在最优策略下，100人中最多能保证有多少人存活？ page 1
奇数犯人获取信息100%存活，偶数犯人50%几率存活。约定偶数位犯人说前一个人的帽子颜色。
一个小猴子边上有100根香蕉，它要走过50米才能到家，每次它最多搬50根香蕉，（多了就被压死了），它每走1米就要吃掉一根，请问它最多能把多少根香蕉搬到家里 page 1
最多能把16根香蕉搬到家里。分为两个阶段。阶段一，起点距离超过50根香蕉，要满载前进1米，空载返回1米，再满载前进1米，等效1米消耗3根香蕉。当在某点x处，存放的香蕉刚好等于运载上限50根，就不需要回撤取货，可以进入阶段二。阶段二，只需一次装载，1米消耗1根香蕉。
走到16米时，吃掉48根香蕉，剩余52根。此时他可以直接搬50往前走，也可以再来搬一次，但结果是一样的。到17米时，还剩49根香蕉。把剩下的50减去17即33米走完，还剩49减去33即16根香蕉。
有2个鸡蛋，从100层楼上往下扔，以此来测试鸡蛋的硬度。比如鸡蛋在第9层没有摔碎，在第10层摔碎了，那么鸡蛋不会摔碎的临界点就是9层。问：如何用最少的尝试次数，测试出鸡蛋不会摔碎的临界点？ page 1
二分法。把鸡蛋从一半楼层，50层往下扔。如果第一枚鸡蛋在50层碎了，则用第二枚鸡蛋从1到49层线性试。如果第一枚鸡蛋没有碎，则扔在第75层，若碎了，则用第二枚鸡蛋从51层到74层线性试。若没碎则继续二分。最坏要试50次。
数学推导。1.假设最坏情况允许最大投掷次数为T，用等差递减法：第一次用T层扔，若没碎再上升T-1层扔，若再没碎上升T-2层扔，不停继续。如果在第一次在T层碎了，最多还要用第二个鸡蛋线性试1到T-1共T次。而事实上，不论第一次在T层碎或者没有碎，最坏都是T次。2.此时覆盖的最大楼层数是T加T-1加T-2一直加到1，即T乘以T加一除以2。要覆盖100层，需要其值大于等于100，解出来T的值为14，即14次就能测出。
一共有N颗石子，每次最多取M颗最少取1颗，A，B轮流取，谁最后会获得最后一颗石子获胜？（假设他们每次都取最优解） page 1
如果N对M加一取模不为0，则先手A有必胜策略，最终会取到最后一颗石子。如果N对M加一取模为0，则后手B必胜。
可以验证M加一是输态。
放N只蚂蚁在一条长度为M树枝上，蚂蚁与蚂蚁之间碰到就各自往反方向走，问总距离或者时间 page 1
当两只蚂蚁相碰后各自掉头，其实等价于两只蚂蚁“穿过”对方，彼此身份互换，运动轨迹不变。我们只要把每只蚂蚁当作独立个体，按其初始方向一直走到树枝端点即可，碰撞不需要特别处理。对于蚂蚁i，初始位置为x i，如其初始运动方向为向左，则其走过距离为x i，如其运动方向为向右，则其走过距离为M减去x i。总距离为所有蚂蚁之和。
5个海盗抢到了100枚金币，每一颗都一样的大小和价值，全体（还活着的）海盗对该方案投票，只要赞成票严格超过反对票（>半数），就按该方案分；否则，提出方案的海盗被扔进海里喂鲨鱼，死亡，轮到下一个编号的海盗提出方案。重复上述投票／淘汰，直到有人通过分配方案 page 1
从小规模海盗群体向上推。1.只剩1人编号5时，他拿走全部100枚。2.剩2人编号4 5时，要2票通过，他自己会投赞成，5号若投反对，4号死，5号独享100，因此无论4号给5号多少，5号都反对。3.剩3人编号3 4 5时，要2票通过，如果3号死，则进入2人局面，4号必死，因此4号在下一轮会死，只要给他至少1枚，他都会赞成，即99 1 0。4.剩4人编号2 3 4 5，需要3人通过，若2号死，进入3人局面，只要给两个后继得最少的海盗，多给一个即可，即97 0 2 1。5.剩5人，需要3票通过，若1号死，进入上面4人局面，应该拉拢后继得最少的两个人，即97 0 1 0 2。
彼此痛恨的甲、乙、丙三个枪手准备决斗。甲枪法最好，十发八中；乙枪法次之，十发六中；丙枪法最差，十发四中。如果三人同时开枪，并且每人每轮只发一枪；那么枪战后，谁活下来的机会大一些？ page 1
丙（最差枪法）的存活概率最高。每轮三人同时开枪，目标都是最强的活着的对手，因为要最大化自己活下来的机会，最强对手最危险，甲瞄准乙，乙瞄准甲，丙瞄准甲。经过概率计算，丙存活概率最大。
有5个囚犯被判处死刑，他们请求上诉，于是法官愿意给他们一个机会。犯人抽签分好顺序，按序每人从100粒豆子中随意抓取，最多可以全抓，最少可以不抓，可以和别人抓的一样多。最终，抓的最多的和最少的要被处死。他们的原则是先求保命。如果不能保命，就拉人陪葬。100颗不必都分完。若有重复的情况，则也算最大或最小，一并处死（中间重复不算）。谁活下来的可能性最大？ page 1
没有一个人活下来。保命的原则是只选前人的数字加一或减一。循环结束时，可选的数始终只有两个相邻值n和n加一，所有人被处决。