今日面试题:可怜的小老鼠

有11瓶酒,只有一瓶有毒。喝酒之后,三天会死,只有三天时间。请问至少需要多少只老鼠,可以找出9瓶没有毒的酒。

===============================================

Google赛马分析

原题

想必田忌赛马的故事,大家都耳熟能详。但是,大家知道Goolge的童鞋们是怎么赛马的么?不过,首先,大家要先尝试一下:有25匹马,每次只能五匹一起跑,那么最少跑几次,才能确定前三甲呢?

分析

这样的题目,该如何分析呢?没有任何的名次信息,没有秒表,没有相机记录距离(题目中疏忽了:)),我们先简单一点,如何确定第一名呢?6次是可以的,例如可以有如下的方法:

每5匹马比赛一次,找到5个第一名,然后这5匹马进行比赛,得到第一名,6次; 首先5匹马进行比赛,得到第一名,此时剩下20匹马没有参与比赛。每次4匹,分为5组,一次和第一名比较。也是6次得到最终的第一名 ... 我们采用继续第一种方法分析,前三名的情况,如下表:

A1 B1 C1 D1 E1
A2 B2 C2 D2 E2
A3 B3 C3 D3 E3
A4 B4 C4 D4 E4
A5 B5 C5 D5 E5

上表中A>B>C>D>E,A1>A2>A3>A4>A5。是由前五次得出的结果,因为我们只要前3的名次,排除掉不可能的马匹,变为如下的表格:

A1 B1 C1
A2 B2
A3

B3为何要排除呢,因为,如果B3不排除,则A1>A2>A3>B3。就是前四的名次了。剩下的6个里面,A1是第一名已经确定,那么剩下的5匹取前两名,即可得到全部前三甲。此时又赛了场。则总共赛了7场。

本文来自微信:待字闺中,2013-08-02发布,原创@陈利人 ,欢迎大家继续关注微信公众账号“待字闺中”。