Есть идея! (Гарднер) - страница 59

2. Некоему специалисту по молекулярной биологии удалось вывести редкую разновидность бактерий. Ежечасно каждая бактерия делится на 3 части, причем каждая часть мгновенно достигает размеров взрослой бактерии и час спустя претерпевает деление на 3 части.

Ровно в полдень биолог положил 1 бактерию в стерильный контейнер с питательной средой. К полночи контейнер оказался наполненным бактериями до отказа. Когда контейнер наполнился на одну треть?

Как и предыдущие задачи, эта головоломка решается «обратным ходом»; ясно, что на одну треть контейнер заполнился к 11 часам вечера, за час до полуночи.

А теперь мы предлагаем вам проверить свою сообразительность на новом замечательном варианте последней задачи. Все условия остаются прежними, за исключением одного: ровно в полдень биолог положил в стерильный контейнер с питательной средой не одну, а три бактерии. Когда наполнится контейнер? Ответ приведен в конце книги.

Когда друзья доехали до дома, где жили родители Элен, она вручила отцу сверток.

Элен. Здесь то, что ты собирался купить для дома, папочка!

Мистер Браун. Спасибо, дочка! А сколько это стоило?

Элен. Пятьсот стоили 3 доллара.

Мистер Браун. 3 доллара? Значит, по 1 доллару за штуку.

Элен. Правильно, папочка.

Что, по-вашему, Элен купила в подарок отцу?

Возможно, вы догадались, что слово «пятьсот» может иметь 2 значения: число пятьсот и 3 цифры 500, написанные подряд. Если одна цифра стоит 1 доллар, то 3 цифры стоят 3 доллара: Элен купила три цифры для номера дома, в котором живут ее родители.

Эта задача-шутка наглядно показывает, что в поисках решения иной раз бывает полезно перечитать условия задачи.

Боб. Кстати, Элен, ты до сих пор не дала мне номер своего нового телефона.

Элен. Ты знаешь, мы уговорились не сообщать его никому, но для тебя я готова нарушить уговор. Можешь задать мне любые 24 вопроса о номере телефона, на которые можно ответить «да» или «нет», и я отвечу на них.

Боб. Помилуй, Элен! Семизначных телефонных номеров почти 10 млн. Как я смогу отгадать один из них, задав всего 24 вопроса?

Элен. Подумай хорошенько, Боб, и я уверена, что ты сумеешь отгадать мой телефонный номер.

Боб не обманул ожиданий Элен и вскоре действительно придумал простой способ, позволяющий отгадывать любой семизначный телефонный номер, задавая не более 24 вопросов. Придумав такой способ, вы сможете испытать его на своих друзьях и знакомых.

Боб догадался, что с помощью вопросов, допускающих ответы «да» и «нет», выделенный элемент множества лучше всего искать, придерживаясь следующей стратегии. Если множество содержит четное число элементов, то его следует разделить на две равные части, содержащие одинаковое число элементов. Если множество содержит нечетное число элементов, то его следует разделить на две части так, чтобы они как можно меньше отличались по числу элементов. После того как множество разделено на две части, следует спросить, указывая на одну из них, содержится ли в ней выделенный элемент. Получив ответ и выбрав ту из двух частей, которая содержит выделенный элемент, надлежит повторить всю процедуру сначала. После конечного числа шагов (зависящего от числа элементов в исходном множестве) останется подмножество, содержащее только выделенный элемент — тот самый, который требовалось найти.