Условие:
Имеется тысяча колодцев и десять мышей, ровно один из колодцев отравлен . Раз в день можно напоить мышей водой из колодцев, одна мышь может выпить за раз воды из нескольких колодцев, из одно колодца можно напоить сколько угодно мышей. В течении дня мышь, выпившая воды из отравленного колодца, умирает. За какое минимальное количество дней заведомо можно определить отравленный колодец?
Решение:
Сколько возможно исходов после одного дня? Каждая мышь или умрет или нет, то есть всего 1024, что больше тысячи. Это навевает на мысль, что одного дня достаточно, так как разные исходы могут быть лишь при случаях, когда отравлены разные колодцы.
Если зашифровать исходы как последовательность из нулей и единичек, то получатся двоичные числа от нуля до 1023. Пронумеруем колодцы от нуля до 999. Как теперь произвести соответствие? Просто: i-тая выпьет из колодца под номером n, если в двоичном представлении на i-том месте стоит единица, и не выпьет в противном случае. Таким образом умершие мыши кодируют номер отравленного колодца.
Но почему, если умершие мыши соответствуют, исходя из нашего алгоритма, некоему-колодцу, то он отравлен? Очевидно что, если мышь пившая из некого колодца не умерла, то колодец не отравлен. Так же, если умерла мышь не пившая из некоего колодца, то он не отравлен. То есть никакой другой, помимо предложенного колодца, не может быть отравлен, следовательно это он.