8 瓶水 2 瓶有毒 6 个耗子的解

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1298 天前的主题，其中的信息可能已经有所发展或是发生改变。

原帖： https://www.v2ex.com/t/771969

很抱歉在原帖 1 楼发了一个错误的答案，想的太快导致逻辑出了 bug 。

8 选 2 一共 28 种可能的组合。由于毒药混合只要有一瓶是毒药，结果则是毒药，属于逻辑或运算，不符合二进制与的条件，所以我们不混合 8 选 2，而是混合选出来后剩下的 6 瓶，8 选 6 。这样混合出来的 28 瓶里只有 1 瓶是无毒的，再根据 5 位 2 进制编码，给 5 只老鼠喝，就能找到哪一瓶有毒了。

下面是 js 写的一个验证。随机从 water 数组里投毒 2 瓶，然后根据上面的方式计算结果并 log 出来。可以直接在浏览器控制台运行。

(() => {
  let water = [
    [0, false],
    [1, false],
    [2, false],
    [3, false],
    [4, false],
    [5, false],
    [6, false],
    [7, false],
  ]

  // 随机投毒 2 瓶
  let pCount = 0;
  while (pCount < 2) {
    const index = Math.floor(Math.random() * 8)
    if (!water[index][1]){
      water[index][1] = true
      pCount += 1
    }
  }

  const poisonous = water.filter(v => v[1]).map(v => v[0]).join(', ')
  console.log('投毒了: ', poisonous)

  const mix = []
  
  for (let no = 0, i = 0; i < water.length; i += 1) {
    for (let j = i + 1; j < water.length; j += 1) {
      mix.push({
        no,
        bottle: [water[i], water[j]],
        harmless: water[i][1] && water[j][1],
      })
      no += 1;
    }
  }

  const mix2 = []

  for (let i = 0; i < 5; i += 1) {
    const key = 2 ** i
    const mix2Item = mix.filter(v => Boolean(key & v.no))
    const isHarmless = mix2Item.some(v => v.harmless)
    mix2.push({
      i,
      isHarmless,
    })
  }

  const resultNumber = mix2.filter(v => v.isHarmless).map(v => 2 ** v.i).reduce((p, c) => p + c)

  const resultPoisonous = mix[resultNumber].bottle.map(v => v[0]).join(', ')
  console.log('计算出来投毒了: ', resultPoisonous)
})()

题外，可以思考一下，如果不是固定 2 瓶毒药，而是可能是 0/1/2 瓶，这个应该如何解?

第 1 条附言 · 2021-04-21 02:38:04 +08:00

此解有问题。第一次混合出 28 瓶后，只有 1 瓶是无毒的。将 28 瓶再次混合成 5 瓶后，无论怎么混合 5 瓶都是有毒的。毒药不像二进制异或，两瓶毒药相加是还是毒药，而 1 加 1 模 2 的结果是 0 。先休息了，明天再来研究

11 条回复 • 2021-04-22 09:09:44 +08:00