• 2012-09-20

    12 小球问题 - [IT]

    版权声明:转载时请以超链接形式标明文章原始出处和作者信息及本声明
    http://www.blogbus.com/ma3r-logs/222443966.html

    一个朋友出了一道难题,确实挺难,但是也很有意思。
    相信大家都做过一道比较简单的——
    27 只小球,其中 1 只稍重(或轻),要求用天平把它称出来,而且只能称 3 次。
    而这道难的呢,虽然减到了 12 只小球,但是不知道那只特殊的小球是轻还是重。
    同样也只有 3 次机会,不但要把那只特殊的小球称出来,还要称出来它是重了还是轻了。
    我也是想了好几天(虽然不是整天想)才想出来的,下面说一下解决方案。

    为了简化叙述,我们先作一些约定。
    假设我们在小球上涂色,未知的涂黑色,可能重的涂红色,可能轻的涂蓝色,确定不特殊的涂白色。
    那么我们开始的时候就是 12 只黑球,而任务是把 11 只小球变成白色,另一只变成红色或蓝色。
    下面就是全套解决方案。

    每边 4 黑。
    若平,天平上 8 白(余 4 黑)。
        一边 3 黑,一边 3 白。
        若平,天平上 3 黑变白(11 白 1 黑)。
            一边 1 黑,一边 1 白。
            黑变红或蓝,成功。
        否则,天平上 3 黑变红(或蓝,下略),天平外 1 黑变白(9 白 3 红)。
            每边 1 红。
            若平,天平上 2 红变白,成功。
            否则,天平上 1 红、天平外 1 红变白,成功。
    否则,天平上 4 红 4 蓝,天平外 4 白。
        每边 2 红 1 蓝。
        若平,天平上 6 球变白(10 白 2 蓝)。
            每边 1 蓝。
            1 蓝变白,成功。
        否则,天平上 2 红(重侧)1 蓝(轻侧)不变,其余均变白(9 白 2 红 1 蓝)。
            每边 1 红。
            若平,2 红变白,成功。
            否则,1 红 1 蓝变白,成功。

    分享到: