Ответ на задачу 47

Июль 4, 2009

47. Секрет задачи в том, что предложенная сумма, по-видимому, превышает стоимость всего кваса в бочке, а это значит, что в некоторый момент продавец имеет возможность вылить остатки кваса из бочки и использовать ее как дополнительную емкость. Возможен следующий порядок действий, ясный* из схемы (1-я кружка 3-х литровая)   (0,5) — (3,2) — (0,2) — (2,0) — (2,5).

Отмерив 7 л, опоражниваем бочку, сливаем в нее 7 л и действуем по схеме (третье число — квас в бочке): (0,0/7), (3,0/4)   (0,3/4)   (3,3/1)   (1,5/1)   (1,0/1)   (1,1/0).

48.1.    За 7 анализов можно найти зараженную пробу, не более чем из 27= 128 проб. Если бы число проб было более 129, то исследование на первом шаге 1-й пробы было бы нерациональным, так как (в случае отрицательного результата) осталось бы после этого по-прежнему более 128 неисследованных проб, а значит число оставшихся анализов будет более 7. Поскольку, по мнению профессора, исследование на первом шаге 1-й пробы не меняет оптимальности процедуры, то число исследуемых проб равно 129.

48.2.    Задуманное число можно угадать за 7 вопросов. Сделать это можно, например, следующим образом. Запишем числа от 1 до 16 в двоичной системе исчисления, приписав, если это необходимо, спереди несколько нулей, чтобы получилось четырехзначное число. Числу же 16 поставим в соответствие четверку нулей. Пусть это число аЬсд, где каждая из цифр 0 и 1. Зададим сначала 4 вопроса, выясняющие четность соответствующей цифры. Пятым сформулируем следующий вопрос: четна ли сумма первых трех цифр? Если ответ совпадает с уже известным нам значением, то вранья еще не было, все эти три цифры верны, и за оставшиеся два вопроса мы с гарантией уточним значение четвертой цифры. Если же ответ разойдется, то один из ответов ложен. Тогда мы выясним четность суммы двух первых цифр. При совпадении уточняем цифру с. При расхождении (при этом, ясно, что обман произошел, когда мы выясняли одну из этих первых двух цифр), задаем вопрос о четности первой цифры.

Покажем, что за 6 вопросов угадать задуманное число  нельзя.  После 6 вопросов  мы получаем последовательность из шести «да» и «нет», т. е. всего 64 различных Комбинации. Каждой из таких комбинаций соответствует из чисел от 1 до 16. Но при этом замена в какой-то «да» на «нет», или наоборот, не должна

менять соответствующего числа, т. е. одно и то же число соответствует семи наборам. Но 16Х7>64. Противоречие.

Комметирование закрыто now!