55
А. Орлов
Понск предмета
Номер квартиры
Послушайте, какую историю рассказала мне моя соседка Люся *).
— В нашем новом восем叨тажном доме два подъезда. На каждуюlectnичную клетку выходят двери четырех квартир. Вчера во дворе меня встретили ребята и спросили, в какой квартире я живу. Я ответила:
— А вы отгадайте. Может задать мне вопросы, только имеете в виду, что я буду ответать лишь «да» или «нет».
Один мальчишка сразу сказал:
— Нет ничего прошее. Я буду тебя спрашивать, верно ли, что ты живешь в квартире № 1, № 2, № 3, № 4, …
…, № 63, пока ты не скажешь «да».
А если ты все время будешь говорить «нет», то ты живешь в квартире № 64.
Мне понадбится самоое больше шестьдесят три вопроса.
Но тут его перебила девочка:
— Подумаешь, шестьдесят три!
Мне хватит и тридцати двух вопросов! Сначала я узнал, в каком подъезде ты живешь. Я спросу: «Ты живешь в первом подъезде?» Ответшь «да» — значит, в первом; ответшь «нет» — во втором. А затем переберу по порядку все квартиры в подъезде.
— А мне хватит и четырнадцати!— радостно закричал самый маленький
из всей компании. — Этаж я узнал за семь вопросов, а квартиру на этажке — еще за семь!
— А как вы думаете, — спросила Люся меня, — сколько вопросов понадобится, чтобы узнать номер квартиры?
Я сразу ответил Люсе: «Пяты вопросы мало, а шести хватит». Сначала я спросил:
— Верно ли, что ты живешь в первом подъезде?
Люся ответила: «Нет», — и я понял, что ее квартира находится во втором подъезде. Второй вопрос был хитрее:
— Верно ли, что ты живешь ниже этажка?
— Да.
— А верно ли, что ниже треться?
— Нет.
— На треться?
— Нет.
Значит, Люся живет во втором подъезде на четвертом этажке. У меня осталось два вопроса на четыре «подозрительные» квартиры — № 45, № 46, № 47 и № 48 (легко подсчитать, что на площадку четвертого этажка во втором подъезде выходят двери этих четырех квартир).
— Верно ли, что номер твоей квартиры больше 46?
— Нет.
— Ты живешь в квартире № 45?
— Нет.
— Значит, ты живешь в квартире № 46, — сказал я с торжеством.
Понляли ли вы, почему понадобилось так мало问卷ов? Каждай мой вопрос делил номера «подозрительные» квартир (тек, среди которых находится номера, для которых ответ «да», и номера, для которых ответ «нет». В любом случае число «подозрительных» квартир уменшалосьровно вдвое.
Можно доказать, что наверняка уложиться в пять вопросов нельзя.
56
Здесь нам помогет такая таблица:
0 0 0 0 0
0 0 0 0 1
0 0 0 1 0
0 0 0 1 1
0 0 1 0 0
1 1 1 1 0
1 1 1 1 1
Люсины ответы мы запишем с помощью цифр 1, 0. Если она ответает «да», будем писать «1», а если нет, то «0». Первый ответ запишем в разделе единиц, второй — в разделе десятов и так далее. Тогда мы можем единицами и нулями записать любое сочетание из пяти ответов, оно будет пятизначным числом, каждая цифра которого — нуль или единица. Выпишем все такие числа в порядке возрастания — получится наша таблица. Всего в ней 32 числа.
Тепер допустим, что нам всегда удается угадать квартиру за пять вопросов. Это означает, что, зная, какое получилось пятизначное число из нуля и единиц, мы можем точно назвать номер квартиры. Но так как пятизначных чисел у нас 32, то и квартир мы можем назвать лишь 32, а не 64, как в условия.
Номер телефона
Вы хотите узнать семизначный номер моego телефонa, задавая мне вопросы, на которые я буду ответать только «да» или «нет». Придумайте способ, гарантирующий успех за наименьшее число вопросов.
Одна фальшивая монета
Имеются 26 одинаковых по виду монет. Среди них одна фальшивая, она легче остальных. Есть чашечные весы (без стрелки и гирь). За какое наименьшее число взвешивания можно найти фальшивую монету?
Эту задачу можно решать точно так же, как и предыдущую. Только число «подозрительных» монет надо попытаться уменшать не в два раза,
57
a в три: ведь у каждой взвешивания три возможных результата — левая чашка перевесила, правая чашка перевесила, чашки уравновесились. Поэтому сначала положим на каждую чашку по 9 монет. Если левая чашка перевесила, то фальшивая монета на правой чашке; если правая чашка перевесила, то фальшивая монета на левой чашке; если чашки уравновесились, то фальшивая монета — средний воскми монет, не положенных на весы. Значит, после первого взвешивания остается 9 или даже 8 «подозрительные» монет. Потом положим на чашки по три «подозрительные» монеты. После второго взвешивания остатруется три или две «подозрительные» монеты. Положив по одной из них на чашки, выясним, какая монета фальшивая.
Способа наверняка обнаружить фальшивую монету за два взвешивания нет, потому что фальшивой может оказаться любая из 26 монет, а взвешных исходов двух взвешивания всего 9 (каждый из трех исходов первого взвешивания может комбинировать с каждым из трех исходов второго), и 9 меншше, чем 26.
Обсуждение
Поннимаете ли вы, что общего в расстоянии нами задачах? Там — квартиры, здесь — монеты; там — вопросы, здесь — взвешивания. И все же в них много общено. И тут, и там мы задаем вопросы: в одном случае Люсе, в другом — весам, и получаем ответы: в одном случае от Люси, в другом — от весов.
To же самое делают учены, когда ставят опыт, — они задают вопросы. Известно выражение: «Физическая эксперимент — это вопрос, который мы задаем природа». Конечно, так могут сказаать о своих опитах не только физики, но и химики, и биологии — все, кто изучает природу. И если вы хотите быть настоящими математikами, то вам надо уметь задавать вопросы.
Наши задачи связи с одним из современных разделов математики — теории информации. Скажем, как быстрее всего передать сообщение о номере телефонна, если в нашем распоряжении есть сигналы только двух видов? Это — типичная задача теории информации. Подробно об этой теории можно прочитать в книге «Вероятность и информации» А. М. Яглома и И. М. Яглома (М., «Наука», 1973).
Еще две фальшивые монеты
a) Перед вам лежат шесть одинаковых по виду монет, две из которых фальшивые (каждая из них тяжелее настоящего на 1 е). Еще у вас есть чашчные весы без стрелки и гриь. Весы эти, правда, не очень чувствительны и реагируют на разность грузов не менее 2 е. Найдите способ за четыре взвешивания выявить обе фальшивые монеты.
- Имеются шесть одинаковых по виду монет. Четыре из них настоящие, по 4 е каждой, а две — фальшивые, общей массой 8 е: одна чуть более тяжелая, другая более легкая. Какое наименьшее число взвешивания на чашечных весах без стрелки и гриь потребуется, чтобы вывить обе фальшивые монеты и установить, какая из них легче, а какая — тяжелее?
Универсальные грири
Подберите массы четырех гриры так, чтобы им можно было отмерить на чашечных весах любое число граммов от 1 до 40. (Грири можно класть на обе чашки.)
Отгадаки с препятствиями
Вы опять отгадаваете семизначный номер телефонна, но теперь на один из ваших вопросов я могу дать неправильный ответ. Какие тогда вопросы вы будете задать и какое наименьшее число вопросов вам понадобится?