Подвиг разведчика

Бонд и штаб должны сформировать 4 списка (из 6 объектов каждый), чтобы каждая пара из 10 объектов встречалась вместе хотя бы в одном из списков. Тогда Бонд сможет передать номер списка (два бита информации как раз дадут возможность выбрать 1 из 4 номеров), после чего все шесть объектов этого списка можно будет защитить.

Обозначим секретные объекты цифрами от 0 до 9.

Пусть первый список (00) — это {0, 1, 2, 3, 4, 5}, второй (01) — {0, 1, 6, 7, 8, 9}, третий (10) — {2, 3, 6, 7, 8, 9}, четвертый (11) — {4, 5, 6, 7, 8, 9}. Как мы уже предположили в подсказке, Бонд будет передавать номер списка, а сами списки согласованы с МИ-6 заранее.

Если «Спектр» не собирается атаковать ни один из объектов списка 00, то Бонду достаточно передать любой из остальных трех списков. Если оба атакуемых объекта из списка 00, то именно его Бонд и передаст. Если же один объект входит в список 00, а второй не входит, то второй объект — один из {6, 7, 8, 9} — присутствует во всех остальных списках, и Бонд выберет тот из списков 01, 10, 11, в который входит еще и первый атакуемый объект. Например, если атака будет на объекты 3 и 7, то Бонд выберет список 10.

Как можно было догадаться до такого способа формирования списков? Ну, например, можно было заметить, что и 10, и 6 делятся на 2, поэтому напрашивается объединение пар объектов в одно множество. Тогда новых «парных» объектов всего 5, а в каждый из списков должны войти три из них. Требование «каждая пара вошла вместе хотя бы в один список» безусловно сохраняется, потому что для пар, которые мы объединили, оно будет выполнено точно, а для всех остальных пар мы должны его обеспечить. Группировка в пары упрощает задачу просто потому, что прокомбинировать 5 объектов в списки длины 3 намного быстрее, чем перебирать комбинации из 10 объектов в списках длины 6.

Само по себе решение на этом закончено, однако один важный вопрос остался совершенно непроясненным: а если бы секретных объектов у МИ-6 было не 10, а, к примеру, 1000, а одновременно защитить можно было бы не 600, а всего 599, — можно ли было бы это обеспечить?

Ответ на этот вопрос отрицателен, и чтобы доказать это, мы перейдем к пределу (устремив число объектов к бесконечности). Или, выражаясь проще, вместо дискретной задачи об объектах перейдем к «непрерывной» задаче.

Пусть роль множества объектов играет отрезок, длину которого будем считать равной 1, роль двух атакуемых «Спектром» объектов будут играть две точки этого отрезка, а роль списка, сообщаемого Бондом, достанется копии отрезка, на которой некоторые точки мы будем считать выделенными (например, покрашенными). Бонд должен сообщить номер копии (по-прежнему, от 00 до 11), в которой покрашены обе выбранных противником точки, причем это должно быть возможно при любом выборе противника. То, что Бонду удастся это сделать с четырьмя копиями, у которых покрашенная часть имеет длину 0,6 (3/5 от единичного отрезка), очевидно из приведенного выше решения дискретной задачи. Докажем, что покрасить в каждой копии меньше, чем 0,6, нельзя.

Предположим противное: покрашенная часть каждого отрезка имеет длину x < 0,6. Заметим, что каждая точка отрезка должна быть покрашена не менее чем в двух копиях, потому что иначе вместе с нею в покрашенной копии встретилась только часть, имеющая длину x, а остальная часть длины 1 − x не встретилась.

Пусть A — часть отрезка, покрашенная в двух копиях, B — часть, покрашенная трижды, а C — часть, покрашенная во всех четырех копиях.

Тогда 2A + 3B + 4C = 4x. Кроме этого, A + B + C = 1 (это равенство означает, что каждая точка отрезка окажется либо в двух, либо в трех, либо в четырех покрашенных копиях). Умножим второе равенство на 3 и вычтем из первого. Получим C − A = 4x − 3, откуда

С другой стороны, часть A состоит из нескольких кусков, каждый из которых покрашен в каких-то конкретных двух копиях. Обозначим эти куски «12», «13», «14», «23», «24», «34» — по номерам соответствующих копий. Если таких кусков в A больше трех, то в какой-то из пар «12»+«34», «13»+«24», «14»+«23» оба слагаемых присутствуют. Без ограничения общности можно считать, что в A есть куски «12» и «34». Но тогда можно отметить одну точку в куске «12», а другую — в куске «34», и получится, что ни в какой копии отрезка эти точки не окрашены вместе.

Следовательно, в A может быть не более трех кусков. Рассмотрим наибольший из этих кусков, пусть его длина равна y. Так как выше доказано, что длина A больше 0,6, то y > 0,2. Но тогда в каждой из двух своих копий этот кусок дополняется какими-то другими частями (длина которых равна x − y), так что два этих дополнения в сумме равны 2x − 2y. А так как общая длина остальных кусков (всех, кроме куска длины y) равна 1 − y, то должно выполняться неравенство 2x − 2y ≥ 1 − y, откуда y ≤ 2x − 1 < 2·0,6 − 1 = 0,2. Мы получили противоречие: неравенства y > 0,2 и y < 0,2 одновременно не могут выполняться.

Следовательно, наше предположение о том, что можно как-то покрасить четыре копии менее чем по 0,6 каждую, неверно.

О комбинаторных задачах группового тестирования я однажды уже рассказывал — в задаче «Меченые шарики» и послесловии к ней.

Задача о Бонде и двух отмеченных точках относится к соседней комбинаторной области — задачах о покрытии множества его подмножествами (covering problems). Как ни удивительно, этой области науки очень долго «не везло» — математики не рассматривали ее всерьез, а наиболее интересные результаты в ней были получены... любителями призовых лотерей. Казалось бы, какая связь между математической задачей и лотереями? На самом деле — прямая. Если вы играете в лотерею типа «6 из 45», а в выигрышном билете должны быть угаданы не менее трех чисел, то возникает естественный вопрос: сколько билетов надо купить и как именно их заполнить, чтобы гарантированно выиграть? Теперь представьте, что вы с Джеймсом Бондом заранее составили такой план покупки и заполнения билетов, а в «момент Ч» он вам сообщит просто номер выигравшего билета... В нашей задаче мы сыграли в точно такую игру в лотерее «6 из 10», если выигрышным объявлялся билет, в котором угаданы два числа. Точнее, мы убедились в том, что выигрыш в такой игре возможен при покупке всего четырех лотерейных билетов.

К счастью, в какой-то момент математики подключились к поиску оптимальных стратегий выигрышей в лотереи и составили для решения подобных задач целые таблицы, например La Jolla Covering Repository. Если в форму на этом сайте ввести t = 2, size = 4 и нажать на search, то в результатах поиска будет очень много строчек, соответствующих различным значениям (n, k), где n — число всех объектов, а k — длина списка. Если приведенное в решении доказательство вас не до конца убедило, можете самостоятельно убедиться, что во всех этих строчках отношение k/n не меньше 3/5.