ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 98184
Темы:    [ Сочетания и размещения ]
[ Подсчет двумя способами ]
[ Неравенство Коши ]
[ Задачи с неравенствами. Разбор случаев ]
Сложность: 5-
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

В ботаническом справочнике каждое растение характеризуется 100 признаками (каждый признак либо присутствует, либо отсутствует). Растения считаются непохожими, если они различаются не менее, чем по 51 признаку.
  а) Покажите, что в справочнике не может находиться больше 50 попарно непохожих растений.
  б) А может ли быть ровно 50?


Решение

  а) Пусть непохожих растений 51 и k из них имеют данный признак, а  51 – k  – не имеют. Число несовпадающих по этому признаку пар равно
k(51 – k) ≤ 25·26.  В сумме получаем не более 100·25·26 несовпадений. Но по условию их должно быть больше чем  51·51·50 : 2 > 100·25·26.  Противоречие.

  б) Пусть в справочнике есть m видов попарно непохожих растений. Добавим к описанию еще один признак: чётность числа имеющихся у данного растения признаков. Получим справочник, где для описания растения используется уже 101 признак, причем любые описания различаются по крайней мере по 52 признакам (если исходные описания различались ровно по 51 признаку, то чётности числа имеющихся признаков у них различны).
  Действуя так же, как в а), получаем, что общее число различий не меньше  52·m(m–1)/2,  но не больше  101·m²/4,  а из неравенства  52·m(m–1)/2 ≤ 101·m²/4  следует, что
m ≤ 34.  Итак, в новом, а значит, и в исходном справочнике описано не более 34 попарно непохожих растений.

Ответ

б) Не может.

Замечания

1. Баллы: 4 + 4.

2. На Московской олимпиаде предлагался только пункт а).

3. Задача связана с кодами, исправляющими ошибки. Вместо растений рассматриваются сообщения, а вместо описаний – последовательности из нулей и единиц заданной длины n; минимальное число различий двух последовательностей называется кодовым расстоянием d (в задаче  d = 51),  а сам определитель называется кодом. Если исказить сообщение не более чем в d–1/2 позициях, то его можно отличить от любого другого сообщения в коде. Это свойство и понимается под исправлением ошибок. Общая задача определения максимального размера (то есть числа различных сообщений) кода длины с кодовым расстоянием до сих пор не решена. Однако теорема Плоткина – Левенштейна устанавливает границу для размера кода с большим кодовым расстоянием  (2d > n)  и утверждает, что при некотором естественном предположении есть коды соответствующего размера. При   n = 100,  d = 51   решение задачи демонстрирует оценку Плоткина: размер кода не превышает 34. Эта оценка достижима: можно предъявить код из 34 сообщений.

Источники и прецеденты использования

олимпиада
Название Турнир городов
Турнир
Дата 1992/1993
Номер 14
вариант
Вариант весенний тур, основной вариант, 10-11 класс
Задача
Номер 7
олимпиада
Название Московская математическая олимпиада
год
Номер 56
Год 1993
вариант
Класс 10
задача
Номер 5

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .