Семь карт на троих

Полезно пронумеровать все карты от 0 до 6 (это можно сделать вслух, так как набор карт исходно видели все) и размышлять о числах от 0 до 6, а не о картах.

Сумма 0 + 1 + 2 + 3 + 4 + 5 + 6 равна 21.

Фактически нам нужны два утверждения:
    1) Гриша и Леша могут передать друг другу информацию о своих картах (числах);
    2) Коля при этой передаче ничего нового не узнает.

    1) Способ передачи информации довольно прост: сначала Гриша, а потом и Леша сообщают вслух сумму своих чисел по модулю 7, \(S_{\text Г}\) и \(S_{\text Л}\) соответственно. Зная \(S_{\text Г}\) и \(S_{\text Л}\), каждый из них легко может найти \(21-S_{\text Г}-S_{\text Л}\). Остаток от деления этого числа на 7 и будет картой Коли. Понятно, что когда Гриша и Леша узнали карту Коли, они узнали и карты друг друга.

    2) Докажем, что с точки зрения Коли ничего не изменилось.

Пусть Гриша назвал сумму \(S_{\text Г}\). Может ли у него быть карта \(k\)? Да, если сумма двух остальных карт Гриши может быть равна \((S_{\text Г}-k) \mod7\). Но каждое значение по модулю 7 может быть представлено в виде суммы двух различных чисел тремя способами (например, 6 = 1 + 5 = 2 + 4 = 0 + 6). Один из таких способов Коля может исключить потому, что в него входит его собственное число. Еще один из способов Коля исключит, так как в него входит число \(k\), возможность нахождения которого Коля и анализирует. Третий способ исключить невозможно!

Следовательно, с точки зрения имеющейся у Коли информации число \(k\) может находиться у Гриши. Совершенно аналогично оно может быть и у Леши. А это и означает, что Коля не знает, у кого из остальных ребят какие числа.

Эта задача предлагалась участникам Московской математической олимпиады в 2000 году, ее автор — А. В. Шаповалов.

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

1) Во-первых, насколько надежна защита информации в рассмотренном решении? Пусть, например, и Леша, и Гриша сообщили, что их суммы по модулю 7 равны 0. В этот момент оба они, разумеется, понимают, что у Коли карта 0, а значит, знают карты друг друга. Однако и Коля точно знает, что у одного из них набор карт 1 + 2 + 4, а у другого — набор 3 + 5 + 6. Иначе говоря, Коля знает весь расклад с вероятностью 0,5. Можно ли придумать за Гришу и Лешу более надежный протокол передачи информации?

2) Насколько этот способ может быть обобщен?

Ясно, что если Грише и Леше выдавать все карты, кроме какой-то одной, то все сработает аналогично. А что, если Коле достанется более одной карты? Пусть, скажем, 8 карт раздаются так: по три Грише и Леше, а две оставшиеся — Коле? Если мы, как и раньше, закодируем карты числами от 0 до 7, то сумма всех карт будет \(28 \equiv 4 \mod 8\). Позволяет ли это Грише и Леше определить карты друг друга?

Увы, не всегда. Например, пусть как и раньше каждый из них объявил, что сумма его карт равна нулю. Тогда они вычисляют, что сумма двух карт Коли равна 4, но не могут определить эту пару карт: 2 + 2 и 6 + 6, несомненно, невозможны, но еще есть пары 0 + 4, 1 + 3 и 5 + 7. Если у Гриши есть по одному числу из двух пар (из этих трех), например, 1 + 2 + 5, то он уже понимает, что у Коли должна быть третья пара (а мы понимаем, что и у Леши в этом случае тоже есть числа из двух остальных пар и число 6). Но что, если у Гриши, скажем, 1 + 3 + 4? Тогда у Коли 5 + 7, а у Леши 0 + 2 + 6, и Гриша это понимает, а вот задача Леши неразрешима: он не может выбрать между этим вариантом распределения карт и вариантом «4 + 5 + 7 у Гриши и 1 + 3 у Коли».

Иначе говоря, наш способ не работает, а существует ли для этой версии задачи работающий способ — неизвестно.

Приведем еще одну задачу о публичном протоколе обмена информацией. Ее автор — американский математик Питер Манн Уинклер, книга которого «Математические головоломки. Коллекция гурмана» переведена на русский и вышла в 2024 году в МЦНМО, но мы процитируем (с минимальными изменениями) более ранний перевод условия из замечательной статьи Сергея Гашкова Разностные множества, конечные геометрии, матрицы Царанкевича и экстремальные графы.

Два шерифа соседних городов составили список из 7 подозреваемых в совершении преступления. Потом каждый из них, проведя оперативно-разыскные действия, сократил список подозреваемых до двух человек. Эти списки различны, то есть пересекаются только по одному подозреваемому, поэтому шерифы, обменявшись информацией, могут совместно арестовать преступника (а в одиночку они этого сделать не могут). Но если эта информация будет перехвачена и станет известна жителям, то они поймут, кто преступник, и линчуют его, не дожидаясь ареста (список из семи подозреваемых им известен). Как шерифам обменяться информацией, чтобы арестовать преступника (и тем самым не допустить суда Линча)?

Эта задача о двух шерифах, впервые опубликованная в 1997 году для восьми подозреваемых и мотивированная (по утверждению Уинклера) игрой в бридж, к сегодняшнему дню уже породила целое ответвление криптографии, получившее название криптогенография. Группа игроков общается с целью узнать (и, возможно, раскрыть) секрет, которым изначально владел один из них. Их разговор отслеживается подслушивающим, не имеющим ограничений по вычислительным ресурсам, который хочет узнать личность обладателя секрета. Оказывается, этому можно противодействовать! В простейшем сценарии секрет представляет собой бит X, хранящийся у одного из \(k > 2\) сотрудничающих игроков; изначально ни секретный бит, ни личность его владельца не известны остальным членам группы. В конечном итоге секретный бит раскрывается, но личность первоначального владельца бита — нет. В 2014 году было доказано, что два игрока могут заставить подслушивающего ошибочно угадать происхождение секретного бита с вероятностью не менее 1/3 и не более чем 3/8.