33
«КВАНТ»
ДЛЯ
МЛАДШИХ
Сто замков и сто ключей
С.ДОРИЧЕНКО
Сэру Майкрофту Холмсу Прошу прощения за это тревожное письмо, но Шерлок Холмс сейчас в ужасном состоянии. Отсутствие дел, способных занять его ум, крайне пагубно сказалось на его здоровье. Моему другу совершенно необходима сложная задача. Если преступный мир уже не способен отвечать на такие вызовы, то, быть может, спасительной станет какая-то логическая загадка, достойная этого великого ума? С надеждой, Доктор Ватсон
Доктору Джону Ватсону Я бесконечно благодарен Вам за заботу о моем брате. Сейчас я как раз занят одной математической задачей и пока не смог ее решить. Она не вполне криминалистическая, но вызов тут бросает сам Мориарти. Быть может, это заинтересует Шерлока? Условие прилагаю. Искренне Ваш, Майкрофт Холмс
– Итак, Ватсон, имеются 100 одинаковых с виду замков и 100 ключей от них, сваленные в кучу? – Да, причем к каждому замку подходит ровно один ключ. И требуется выяснить, какой замок каким ключом открывается. – Что ж, занятие малоприятное, но, имея запас времени и некоторое терпение, сделать это нетрудно. Выложим замки в ряд и начнем проверять ключи… – Но в худшем случае это 10000 проверок! Даже если тратить на одну проверку секунды четыре, это 40 тысяч секунд – больше 11 часов! – Сразу видно, мой друг, что вас неважно учили математике. Вы что же, собираетесь вставлять каждый ключ в каждый замок? – Разумеется, ведь может все время не везти.
ШКОЛЬНИКОВ
– Но первый ключ достаточно вставить 99 раз: если он так и не подошел, то он от последнего замка. – Пожалуй. Значит, всего 9900 проверок? – Снова мимо. Мы отбросим найденную пару «ключ-замок», и для второго ключа хватит 98 проверок. – И правда. А третий ключ придется проверять не больше 97 раз и так далее. Получается жуткая сумма: 99 98 … 2 1 0. Странно, сотый ключ у меня требует 0 проверок? – Конечно, его замок определится автоматически. – А чему же равна эта сумма? – По легенде, маленький Гаусс вычислил ее почти мгновенно с помощью небольшой хитрости. Он взял две такие суммы и разбил слагаемые на 100 пар 99 0, 98 1, 97 2, …, 0 99, каждая пара дает 99. Значит, исходная сумма равна , это 4950 проверок. По четыре секунды на проверку – ровно пять с половиной часов. А теперь оставьте меня – право, эти пустяки лишь ухудшают мое состояние. – Но Холмс, в своем дневнике Мориарти утверждает, будто нашел способ распределить ключи быстрее, чем за 4950 проверок, причем с гарантией! Правда, излагать он его не стал – мол, способ столь сложен, что в дневнике просто не хватит места… – Ох уж эта его страсть к дешевым эффектам. Быстрее, чем за 4950 проверок? Холмс погрузился в долгое молчание. Невероятно, но спустя какое-то время лицо его начало оживать, а в глазах появился знакомый блеск. – Очень занятно, Ватсон. Мориарти был профессором математики, но, похоже, тут он ошибся. И я это докажу! – Докажете? Как же это можно доказать? Вдруг у него был хитроумный, никому не известный способ… – Ватсон, а вы хорошо знакомы с математическими доказательствами? Дайте-ка я вас проверю. Согласны ли вы с тем, что сначала надо найти хоть одну подходящую пару «замок-ключ»? – Эээ… пожалуй, да, так как совершенно не видно, как тут еще можно действо-
34
КВАН T 2023/№1
вать. Постойте… Но тогда все ясно! Первую пару при полном невезении не найти быстрее, чем за 99 проверок, вторую – за 98, … И вот она, наша сумма, это минимум! – Сразу попались. Почему нельзя вставлять разные ключи в разные замки, сделать много таких проверок, а потом вдруг понять сразу про несколько ключей и замков, что к чему подходит? – Это кажется неправдоподобным… – Гарантируете, что точно не выйдет? – Право, не знаю. – Тогда у вас еще нет доказательства. – Как же быть? – Попробуем рассуждать по порядку. Интуиция подсказывает мне, что алгоритма, гарантирующего успех быстрее, чем за 4950 попыток, не существует. А этот дьявол Мориарти утверждает, что алгоритм есть. Что ж, допустим, профессор прав. И загоним его в ловушку – мысленно, разумеется. – Но ведь для этого надо предложить ему, пусть даже мысленно, набор ключей и замков, да так, чтобы он не справился? – Именно этим мы и займемся. Представьте, мы выдали ему замки и ключи. Профессор берет какой-то ключ и вставля-
ет в какой-то замок… Если он угадал, мы тут же меняем внутренность этого замка с каким-то другим так, чтобы ключ не подошел. – Мы джентльмены, а не шулеры, и не станем… – Ватсон, мы лишь проверяем, что алгоритм работает во всех случаях. Поэтому такая подмена вполне законна – замки ведь неразличимы, и профессору мог попасться замок с другой внутренностью. – А дальше? – Он проверяет какую-то следующую пару «ключ-замок». А мы снова, если нужно, меняем внутренности замков между собой так, чтобы и этот ключ не подошел – лишь бы все предыдущие проверки не изменили результата… – Но ведь так нельзя делать до бесконечности, в какой-то момент очередной ключ уже точно подойдет. – Вы правы. Но постойте! А зачем тогда этот ключ проверять? – Простите, Холмс, я не понял. – Мориарти же не дурак. У него есть записи всех совершенных им проверок. Пока ни один ключ ни разу не подошел. И вот он вставляет ключ Х в замок Y, и – о ужас – мы не можем ничего поменять
35
«КВАНТ»
ДЛЯ
МЛАДШИХ
местами, не испортив предыдущих результатов, чтобы ключ не подошел. Но тогда это поймет и сам Мориарти! – Но как, Холмс? – Он может мысленно перебрать все возможные соответствия замков и ключей. И раз нет соответствия, сохраняющего результаты предыдущих проверок, при котором ключ X и замок Y не подходят друг к другу, он это обнаружит. – А почему такого соответствия нет? – Иначе мы бы его нашли и сделали бы результат очередной проверки отрицательным. – Немного мудрено… – Зря сомневаетесь, Ватсон. Но если хотите – мы тогда просто подскажем профессору по-джентльменски, что он угадал и эту проверку может не делать. – Но зачем, Холмс? – Я чувствую, что это важно для доказательства! Ведь теперь мы вправе считать, что алгоритм профессора таков: он делает много проверок, результаты всегда отрицательны, и в какой-то момент вдруг понимает про все ключи, какой от какого замка! – Про все ключи? – Ну да. Может, сначала про какой-то один ключ или несколько сразу. Когда про какие-то ключи ему становится все ясно, он их не проверяет, а действует далее по своему алгоритму, делая лишь те проверки, которые могут дать отрицательный результат. А мы будем этот отрицательный результат обеспечивать. Пока он не поймет все про все ключи. – А потом? – Ваши предложения, мой друг? – Ни малейших идей. – Похоже, мы движемся с вами в одном направлении… Тогда у меня просьба – разработайте пока для профессора удобный и компактный способ записи результатов его проверок, а я еще немного подумаю. Холмс откинулся на спинку кресла и затянулся трубкой. Прошло около получаса, как вдруг… – Эврика! Ватсон, мне все ясно. А как дела у вас? – Как врач, регулярно делающий записи
ШКОЛЬНИКОВ
о состоянии своих больных, я подумал было, что можно заносить подряд все проверки в книгу. Но если экономить место, лучше, пожалуй, занумеровать ключи и замки и нарисовать большую клеток. А при проверке, скажем, пары «6-й ключ, 75-й замок», ставить в 6-й строке на 75-м месте плюс, если ключ подошел, и минус – если не подошел. – Браво, Ватсон. Этот способ крайне удобен. Только напомню, что Мориарти все время ставит минусы. Он поставит их меньше, чем 4950 штук, и внезапно все поймет, верно? – Да, по окончании работы алгоритма он просто расставит все плюсы. Шерлок Холмс поморщился. – Эти плюсы, они же могут образовать довольно хаотическую картину… Ничего, мы ее сейчас упорядочим. Ведь эти 100 плюсов расположены по одному в каждом столбце и в каждой строке. Но заметьте, Ватсон – в нашей таблице можно переставлять строки и столбцы, и ничего не испортится – если соответственно переставлять ключи и замки, не так ли? – Пожалуй, да. – Тогда отыщем плюс в первом столбце и переставим строку с этим плюсом на самый верх, затем найдем плюс во втором столбце и поставим строку с этим плюсом прямо под первой строкой и так далее. – Вы хотите, чтобы плюсы аккуратно выстроились по диагонали? – Да. Это не обязательно, но так решение будет особенно наглядным. Итак, в таблицу ставят меньше 4950 минусов, после чего плюсы однозначно выстраиваются по диагонали, никаких других вариантов. Но что такое 4950? Сколько всего клеток в таблице? – Таблица у нас 100 u 100, всего 10000 клеток. – А сколько клеток на диагонали? – Разумеется, 100. – Значит, остается 9900 клеток для минусов, которых меньше 4950 – меньше половины от числа оставшихся клеток! – К чему вы клоните, Холмс? – Надо разбить клетки на пары симметричных относительно диагонали! Вот, я