Brain Teaser Miscs

http://www.shuatiblog.com/blog/2014/09/16/bottles-of-spills/

You have 20 bottles of pills. 19 bottles have 1.0 gram pills, but one has pills of weight 1.1 grams.

Given a scale, how to find the heavy bottle only scaling ONCE?

Solution

Take 1 pill from Bottle 1, 2 pills from Bottle 2, and so on. We’ll expect (1 + 2 + … + 20) = 210 gram of pills.

The answer would be {(weight – 210 grams) / 0.1}.

http://www.chaozh.com/conde-interview-brain-teasers-guess-rewards/
一个猜测游戏中，某一个瓶子中装有奖品。游戏者需要猜出奖品在哪个瓶子中，并且在m次结束游戏。（即m次猜中）

有n个黑色的瓶子（以至于游戏中看不到瓶中是否有东西）设从0到n-1编号，一字排开。每一次如果游戏者猜错了，那么奖品会各以50%的概率移动到左边或者右边的瓶子中。当奖品位于最左边或者最右边，游戏者猜错时，奖品必然右移或者左移。

问题：请设计一个满足n和m的策略，帮助游戏者完成游戏。

最多需要m=2n次 必能猜中
第一轮 先从0开始顺序往右猜，即0,1,…n-1,这样 如果奖品初始位于偶数位置处 必定能猜中
如果奖品初始是位于奇数处，则需要第二轮
如果n为偶数 则第一轮结束后奖品仍在奇数处
这样第二轮从1开始往右，即1,2,…,n-1 这样必中
如果n为奇数 则第一轮结束后奖品已经跳到偶数处
这样第二轮从0开始往右，即0,1,…,n-1 必中

http://www.chaozh.com/interesting-questions-about-binary/

题目1：有 1000 个一模一样的瓶子，其中有 999 瓶是普通的水，有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在，你只有 10 只小白鼠和一星期的时间，如何检验出哪个瓶子里有毒药？

个人解答：显然需要参考二进制的表示方法，但是腾讯面试当时纠结在时间只有一个星期，而喝下毒药死亡也需要一个星期，似乎只能验证一次。实际上，这个限制正说明我们确实只能利用这10只小白鼠验证一次。于是问题就简单了。将1000瓶水按照二进制编码的顺序给对应的小白鼠喝，比如编号3的水（二进制表示为11）就喂给编号1与编号2小白鼠喝。这样，一星期后看哪几只小白鼠死亡就可以判断哪个编号的水有毒。这个结论成立的前提是只有一瓶毒药，这样只有对应编号的小白鼠才会不幸死亡。

进一步题目：如果你有两个星期的时间，为了从 1000 个瓶子中找出毒药，你最少需要几只老鼠？注意，在第一轮实验中死掉的老鼠，就无法继续参与第二次实验了。

个人解答：有两个星期就可以进行两次实验，每个没死成的小白鼠就能再喝一次，也就是说一个小白鼠可以表示3个状态：第一周死，第二周死，最终也没死。显然就是参考三进制，于是需要3^7 > 1000，即最少7只。方法与之前类似，先给三进制表示为2的位对应的小白鼠喝，再实验三进制表示为1的位对应的小白鼠即可。

 结论：类似地，我们可以证明， n 只小白鼠 t 周的时间可以从 (t+1)^n 个瓶子中检验出毒药来。

题目2：100个开关控制100个灯，开关在一个房间灯在一个房间，最少走几趟能够确定他们的一一对应关系

个人解答：据说3的情况，只要一次即可（需要引入热这种状态。。。即存在亮，热，不亮三种状态）