Сто замков и сто ключей

Сергей Дориченко
«Квантик» №1, 2023

— Итак, Ватсон, имеются 100 одинаковых с виду замков и 100 ключей от них, сваленные в кучу?

— Да, причём к каждому замку подходит ровно один ключ. И требуется выяснить, какой замок каким ключом открывается.

— Что ж, занятие малоприятное, но, имея запас времени и некоторое терпение, сделать это нетрудно. Выложим замки в ряд и начнём проверять ключи...

— Но в худшем случае это 10 000 проверок! Даже если тратить на одну проверку секунды четыре, это 40 тысяч секунд — больше 11 часов!

— Сразу видно, мой друг, что вас неважно учили математике. Вы что же, собираетесь вставлять каждый ключ в каждый замок?

— Разумеется, ведь может всё время не везти.

— Но первый ключ достаточно вставить 99 раз: если он так и не подошёл, то он от последнего замка.

— Пожалуй. Значит, всего 9 900 проверок?

— Снова мимо. Мы отбросим найденную пару «ключ-замок», и для второго ключа хватит 98 проверок.

— И правда. А третий ключ придётся проверять не больше 97 раз, и так далее. Получается жуткая сумма: 99 + 98 + ... + 2 + 1 + 0. Странно, сотый ключ у меня требует 0 проверок?

— Конечно, его замок определится автоматически.

— А чему же равна эта сумма?

— По легенде, маленький Гаусс вычислил её почти мгновенно с помощью небольшой хитрости. Он взял две такие суммы и разбил слагаемые на 100 пар 99 + 0, 98 + 1, 97 + 2, ..., 0 + 99, каждая пара даёт 99. Значит, исходная сумма равна 50 · 99, это 4 950 проверок. По четыре секунды на проверку — ровно пять с половиной часов. А теперь оставьте меня — право, эти пустяки лишь ухудшают моё состояние.

— Но, Холмс, в своём дневнике Мориарти утверж дает, будто нашёл способ распределить ключи быстрее, чем за 4 950 проверок, причём с гарантией! Правда, излагать он его не стал — мол, способ столь сложен, что в дневнике просто не хватит места...

— Ох уж эта его страсть к дешёвым эффектам. Быстрее, чем за 4 950 проверок? Холмс погрузился в долгое молчание. Невероятно, но спустя какое-то время лицо его начало оживать, а в глазах появился знакомый блеск.

— Очень занятно, Ватсон. Мориарти был профессором математики, но тут, похоже, он ошибся. И я это докажу!

— Докажете? Как же это можно доказать? Вдруг у него был хитроумный, никому не известный способ...

— Ватсон, а вы хорошо знакомы с математическими доказательствами? Дайте-ка я вас проверю. Согласны ли вы с тем, что сначала надо найти хоть одну подходящую пару «замок-ключ»?

— Эээ... пожалуй, да, так как совершенно не видно, как тут ещё можно действовать. Постойте... Но тогда всё ясно! Первую пару при полном невезении не найти быстрее, чем за 99 проверок, вторую — за 98, ... и вот она, наша сумма, это минимум!

— Сразу попались. Почему нельзя вставлять разные ключи в разные замки, сделать много таких проверок, а потом вдруг понять сразу про несколько ключей и замков, что к чему подходит?

— Это кажется неправдоподобным...

— Гарантируете, что точно не выйдет?

— Право, не знаю.

— Тогда у вас ещё нет доказательства.

— Как же быть?

— Попробуем рассуждать по порядку. Интуиция подсказывает мне, что алгоритма, гарантирующего успех быстрее, чем за 4 950 попыток, не существует. А этот дьявол Мориарти утверждает, что алгоритм есть. Что ж, допустим, профессор прав. И загоним его в ловушку — мысленно, разумеется.

— Но ведь для этого надо предложить ему, пусть даже мысленно, набор ключей и замков, да так, чтобы он не справился?

— Именно этим мы и займёмся. Представьте, мы выдали ему замки и ключи. Профессор берёт какой-то ключ и вставляет в какой-то замок... Если он угадал, мы тут же меняем внутренность этого замка с каким-то другим так, чтобы ключ не подошёл.

— Мы джентльмены, а не шулеры, и не станем...

— Ватсон, мы лишь проверяем, что алгоритм работает во всех случаях. Поэтому такая подмена вполне законна — замки ведь неразличимы, и профессору мог попасться замок с другой внутренностью.

— А дальше?

— Он проверяет какую-то следующую пару «ключ-замок». А мы снова, если нужно, меняем внутренности замков между собой так, чтобы и этот ключ не подошёл — лишь бы все предыдущие проверки не изменили результата...

— Но ведь так нельзя делать до бесконечности, в какой-то момент очередной ключ уже точно подойдёт.

— Вы правы. Но постойте! А зачем тогда этот ключ проверять?

— Простите, Холмс, я не понял.

— Мориарти же не дурак. У него есть записи всех совершённых им проверок. Пока ни один ключ ни разу не подошёл. И вот он вставляет ключ Х в замок Y, и — о ужас — мы не можем ничего поменять местами, не испортив предыдущих результатов, чтобы ключ не подошёл. Но тогда это поймёт и сам Мориарти!

— Но как, Холмс?

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

— А почему такого соответствия нет?

— Иначе мы бы его нашли и сделали бы результат очередной проверки отрицательным.

— Немного мудрёно...

— Зря сомневаетесь, Ватсон. Но если хотите — мы тогда просто подскажем профессору по-джентльменски, что он угадал и эту проверку может не делать.

— Но зачем, Холмс?

— Я чувствую, что это важно для доказательства! Ведь теперь мы вправе считать, что алгоритм профессора таков: он делает много проверок, результаты всегда отрицательны, и в какой-то момент вдруг понимает про все ключи, какой от какого замка!

— Про все ключи?

— Ну да. Может, сначала про какой-то один ключ или несколько сразу. Когда про какие-то ключи ему становится всё ясно, он их не проверяет, а действует далее по своему алгоритму, делая лишь те проверки, которые могут дать отрицательный результат. А мы будем этот отрицательный результат обеспечивать. Пока он не поймёт всё про все ключи.

— А потом?

— Ваши предложения, мой друг?

— Ни малейших идей.

— Похоже, мы движемся с вами в одном направлении... Тогда у меня просьба — разработайте пока для профессора удобный и компактный способ записи результатов его проверок, а я ещё немного подумаю. Холмс откинулся на спинку кресла и затянулся трубкой. Прошло около получаса, как вдруг...

— Эврика! Ватсон, мне всё ясно. А как дела у вас?

— Как врач, регулярно делающий записи о состоянии своих больных, я подумал было, что можно заносить подряд все проверки в книгу. Но если экономить место, лучше, пожалуй, занумеровать ключи и замки и нарисовать большую таблицу, 100 × 100 клеток. А при проверке, скажем, пары «6-й ключ, 75-й замок» ставить в 6-й строке на 75-м месте плюс, если ключ подошёл, и минус — если не подошёл.

— Браво, Ватсон. Этот способ крайне удобен. Только напомню, что Мориарти всё время ставит минусы. Он поставит их меньше, чем 4 950 штук, и внезапно всё поймёт, верно?

— Да, по окончании работы алгоритма он просто расставит все плюсы. Шерлок Холмс поморщился.

— Эти плюсы, они же могут образовать довольно хаотическую картину... Ничего, мы её сейчас упорядочим. Ведь эти 100 плюсов расположены по одному в каждом столбце и в каждой строке. Но заметьте, Ватсон — в нашей таблице можно переставлять строки и столбцы, и ничего не испортится — если соответственно переставлять ключи и замки, не так ли?

— Пожалуй, да.

— Тогда отыщем плюс в первом столбце и переставим строку с этим плюсом на самый верх, затем найдём плюс во втором столбце и поставим строку с этим плюсом прямо под первой строкой, и так далее.

— Вы хотите, чтобы плюсы аккуратно выстроились по диагонали?

— Да. Это не обязательно, но так решение будет особенно наглядным. Итак, в таблицу ставят меньше 4 950 минусов, после чего плюсы однозначно выстраиваются по диагонали, никаких других вариантов. Но что такое 4 950? Сколько всего клеток в таблице?

— Таблица у нас 100 × 100, всего 10 000 клеток.

— А сколько клеток на диагонали?

— Разумеется, 100.

— То есть остаётся 9 900 клеток для минусов, которых меньше 4 950 — меньше половины от числа оставшихся клеток!

— К чему вы клоните, Холмс?

— Надо разбить клетки на пары симметричных относительно диагонали! Вот, я отметил красным несколько пар на салфетке. Видите? Пар ровно 4 950, а минусов — меньше. Значит, найдётся пара, в которой нет ни одного минуса. Скажем, клетка в третьей строке и седьмом столбце, условно клетка (3,7), и симметричная клетка (7,3). В них пусто.

— Видимо, проверять их не было необходимости.

— Всё ещё не понимаете? Давайте я вам нарисую. Мориарти поставил плюсы в клетки (3,3) и (7,7). Но ведь клетки (3,7) и (7,3) пусты — значит, ничего не мешает переставить эти два плюса туда. Короче говоря, поменять внутренность замков 3 и 7 местами. Ни одна предыдущая проверка не нарушится. Значит, Мориарти не мог всё понять про ключи 3 и 7 — есть альтернативный вариант. Противоречие, Ватсон!

— Но как, Холмс? Как вы догадались?

— Вы застали меня в полном расстройстве, Ватсон. Я даже надел на ноги разные ботинки и всё пытался понять, почему они не симметричны. После вашей задачи мне гораздо лучше. Но без очередного дела...

— Мистер Холмс, к вам посетитель. Судя по всему, учёный или учитель математики.

— Почему вы так решили, миссис Хадсон?

— Пиджак испачкан мелом, бормочет под нос какие-то вычисления.

— Может это маркёр или бухгалтер?

— Бухгалтеры и маркёры не настолько рассеяны, чтобы являться в чужой дом в разных ботинках.

Художник Алексей Вайнер