Coffee with cinnamon

Решение задачи о бандитах и квасе

Во-первых, сразу хочу попросить у всех прощения. Выкладывая эту задачу я забыл указать важную деталь - бандитов не сколько-нибудь, а вполне конкретное число - пятеро. И это число важно для того, чтобы получить максимально правильный ответ.

Во-вторых, и это вытекает из “во-первых”, несколько человек предложили решение, которое очень близко к правильному, но только численно. По формуле 240 - (240 / n) / (n - 1), где n - это число бандитов, мы получим одно из допустимых решений. В случае с пятью бандитами оно довольно высоко - 228, и с практической точки зрения, наверное, вполне устраивает всех (действительно, 12 бочек врядли станут большой потерей).

Но есть другой вариант решения, который позволяет абсолютно точно вычислить ту самую, единственную отравленную бочку. Очень подробно (я бы даже сказал, слишком подробоно) это решение описанно здесь: http://alexsmail.blogspot.com/2011/01/blog-post_26.html. Я углубляться не стану и опишу только общую идею.

Отношение каждого из бандитов к каждой из 240 бочек можно описать одним из трёх случаев: 

• бандит выпивает из этой бочки в первый день
• бандит выпивает из этой бочки во второй день
• бандит вообще не пьёт из этой бочки

Это значит, что каждой бочке мы можем присвоить уникальное число, состоящее из пяти цифр в троичной системе счисления, где каждый разряд будет соответствовать одному из бандитов, а значение этого разряда - отношению между этим бандитом и бочкой.

Например, из бочки с номером 11220 первый и второй бандит будут пить в первый день, третий и четвёртый - во второй, а пятый не будет пить вообще. А значит, если и первый и второй бандит отравятся в первый день, третий и четвёртый - во второй, а пятый бандит останется жив - значит в этой бочке и был яд.

Всего такой системой можно пронумеровать 3 ^ 5 = 243 бочки, т.е. даже больше, чем нужно по условиям задачи, а значит мы сможем точно установить единственную отравленную бочку.

Спасибо всем, кому было интересно!