Задания
Версия для печати и копирования в MS Word
Задания Д19 C7 № 505645

В ботаническом справочнике каждое растение характеризуется 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 признаку, то чётности числа имеющихся признаков у них различны). Действуя так же, как в пункте а), получаем, что общее число различий не меньше 52m левая круглая скобка m минус 1 правая круглая скобка /2, но не больше 101m в квадрате /4. Из неравенства 52m левая круглая скобка m минус 1 правая круглая скобка /2\leqslant101m в квадрате /4 следует, что m меньше или равно 34. Итак, в новом, а значит, и в исходном справочнике описано не более 34 попарно непохожих растений.

Спрятать критерии
Критерии проверки:

Критерии оценивания выполнения заданияБаллы
Верно получены все перечисленные (см. критерий на 1 балл) результаты.4
Верно получены три из перечисленных (см. критерий на 1 балл) результатов.3
Верно получены два из перечисленных (см. критерий на 1 балл) результатов.2
Верно получен один из следующий результатов:

— обоснованное решение в п. а;

— пример в п. б;

— искомая оценка в п. в;

— пример в п. в, обеспечивающий точность предыдущей оценки.

1
Решение не соответствует ни одному из критериев, перечисленных выше.0
Максимальный балл4
Источник: А. Ларин: Тренировочный вариант № 48.