Материалы по математике

И. В. Яковлев

|

Материалы по математике

|

MathUs.ru

Теорема Шпернера

Многие математические задачи (например, ребусы или взвешивания) связаны с важной идеей

извлечения информации. Данный листок посвящён задачам, в которых для извлечения инфор-

мации используются некоторые комбинаторные соображения.

Информация требует кодирования. Мы будем работать с двоичными кодами — конечны-

ми последовательностями нулей и единиц. Для двух кодов a = α

1

α

2

. . . α

n

и b = β

1

β

2

. . . β

n

одинаковой длины n введём упорядочение:

a 6 b

⇔

α

1

6 β

1

, α

2

6 β

2

, . . . , α

n

6 β

n

.

Например, 010

6 011. В то же время не всякие два кода данной длины можно сравнить друг

с другом — например, коды 110 и 101 несравнимы

1

.

Несравнимые коды бывают полезны в ситуациях, где требуется извлекать информацию.

Рассмотрим в качестве примера «игрушечный» вариант задачи

8

, которая предлагалась 11-

классникам на Московской математической олимпиаде в 2017 году.

Задача. Детектив расследует преступление. Он знает, что в круге подозреваемых лиц помимо

преступника имеется свидетель (но кто это — неизвестно). В каждый из дней детектив может

пригласить к себе одного или нескольких подозреваемых, и если среди приглашённых есть

свидетель, но нет преступника, то свидетель сообщит, кто преступник. При каком наибольшем

количестве подозреваемых детектив гарантированно раскроет дело за четыре дня?

Решение. Присвоим каждому подозреваемому двоичный код длины 4 (по числу дней): еди-

ница на данной позиции означает, что подозреваемый вызывается в этот день к детективу,

а ноль — что не вызывается (например, подозреваемый с кодом 1010 вызывается к детективу

в первый и третий день и не вызывается во второй и четвёртый). Дело раскроется в том и

только в том случае, если на одинаковых позициях в коде свидетеля будет стоять единица, а

в коде преступника — ноль.

Но детектив ведь заранее не знает ни преступника, ни свидетеля, и поэтому ему нужно

организовать процесс так, чтобы для любых двух подозреваемых A и B нашёлся день, когда

к нему явится A, но не B, и нашёлся другой день, когда к нему явится B, но не A. Иными

словами, коды A и B должны быть несравнимы! Дело будет гарантированно раскрыто, если

детектив сможет снабдить всех подозреваемых несравнимыми кодами. Таким образом, наша

задача сводится к вопросу о наибольшей величине набора несравнимых кодов длины 4.

1. Закончите решение этой задачи.

Перейдём к рассмотрению кодов произвольной длины n. Обозначим a

k

код, в котором имеет-

ся ровно k единиц. Заметим, что коды a

0

= 00 . . . 0 и a

n

= 11 . . . 1 сравнимы со всеми остальными

кодами.

Цепью назовём любой набор сравнимых кодов a

0

6 a

1

6 a

2

6 . . . 6 a

n

(в каждом коде цепи

единиц на одну больше, чем в предыдущем). Антицепь — это набор несравнимых кодов.

2. Покажите, что имеется в точности n! цепей.

3. Покажите, что данный код a

k

содержится ровно в k!(n − k)! цепях.

4. Покажите, что величина k!(n − k)! достигает минимума при k = [n/2].

1

По этой причине отношение 6 на кодах называют отношением частичного порядка, а множество всех

кодов фиксированной длины, снабжённое указанным отношением, служит примером частично упорядоченного

множества.

1

5. а) Докажите, что любая антицепь содержит не более C

[n/2]

n

кодов.

б) Приведите пример антицепи длины C

[n/2]

n

.

Фактически вы доказали теорему Шпернера, которая обычно формулируется в теоретико-

множественных терминах. Именно, пусть S есть n-элементное множество, а P(S) — множество

всех его подмножеств. Семейство A ⊂ P(S) называется антицепью, если ни для какой пары

множеств M, N ∈ A не выполнено M ⊂ N .

Теорема Шпернера. Антицепь в P(S) может содержать самое большее C

[n/2]

n

множеств.

6. Объясните, почему теорема Шпернера вами уже доказана.

7. (ММО, 1958, 10.3 ) В школе изучают 2n предметов. Все ученики учатся на 4 и 5. Никакие

два ученика не учатся одинаково, ни про каких двух нельзя сказать, что один из них учится

лучше другого. Доказать, что число учеников в школе не больше C

n

2n

.

(Мы считаем, что ученик p учится лучше ученика q, если у p оценки по всем предметам не

ниже, чем у q, а по некоторым предметам — выше.)

8. (ММО, 2017, 11.3 ) Детектив Ниро Вульф расследует преступление. В деле замешаны 80 че-

ловек, среди которых один — преступник, ещё один — свидетель преступления (но неизвестно,

кто это). Каждый день детектив может пригласить к себе одного или нескольких из этих 80 че-

ловек, и если среди приглашённых есть свидетель, но нет преступника, то свидетель сообщит,

кто преступник. Может ли детектив заведомо раскрыть дело за 12 дней?

9. (Продолжение про Ниро Вульфа) а) При каком наибольшем количестве подозреваемых Ниро

Вульф сможет заведомо раскрыть дело за 12 дней?

б) За какое наименьшее количество дней Ниро Вульф сможет гарантированно раскрыть

дело при 80 подозреваемых?

10. (Турнир городов, 1986, 7–10 ) 30 учеников одного класса решили побывать друг у друга

в гостях. Известно, что ученик за вечер может сделать несколько посещений, и что в тот вечер,

когда к нему кто-нибудь должен прийти, он сам никуда не уходит. Покажите, что для того,

чтобы все побывали в гостях у всех,

а) четырёх вечеров недостаточно,

б) пяти вечеров также недостаточно,

в) а десяти вечеров достаточно,

г) и даже семи вечеров тоже достаточно.

2