Разделы 
Дополнительно
Задача по математике - 3163
2019-05-26 
В ботаническом определителе растения описываются ста признаками. Каждый из признаков может либо присутствовать, либо отсутствовать. Определитель считается хорошим, если любые два растения различаются более чем по половине признаков. Доказать, что в хорошем определителе не может быть описано более 50 растений.
Решение:
Пусть $m$ - количество растений в хорошем определителе. Оценим суммарное количество различий между всеми парами растений по всем признакам. Количество пар растений равно $\frac{m(m-1)}{2}$, и каждая пара различается не меньше, чем по 51 признаку, поэтому общее число различий $S \geq 51 \frac{m(m-1)}{2}$.
Оценим $S$ другим способом. Пусть $m_i$ - количество растений, обладающих признаком $i$, тогда число пар растений, которые $i$-й признак различает, равно $m_i(m-m_i)$, и общее число различий между растениями равно:
$S = m_1(m-m_1)+ m_2(m - m_2)+ \cdots + m_{100}(m - m_{100})$.
В силу известного неравенства, $m_i(m-m_i) \leq \frac{m^2}{4}$. Поэтому
$S \leq 100 \frac{m^2}{4} = 25m^2$.
Значит, $51 \frac{m(m-1)}{2} \leq S \leq 25m^2$, откуда $m \leq 51$.
Осталось доказать, что $ m \neq 51$. Допустим, что $m = 51$, тогда получаем строгое неравенство $m_i(m-m_i) < \frac{m^2}{4}$ (так как слева стоит целое число, а справа - дробное), и $51 \frac{m(m-1)}{2} \leq S < 25m^2$, откуда $m<51$. Противоречие. Значит, $m \leq 50$.
Комментарии. 1. Напрашивается предположение, что в хорошем определителе может быть описано 50 растений. Однако это не так. Давайте добавим к описанию растений еще один признак - четность числа имеющихся у данного растения признаков. Получим определитель, в котором для описания используется уже 101 признак, причем любые описания различаются по крайней мере по 52 признакам (если исходные описания различались только по 51 признаку, то четности числа имеющихся у этих растений признаков различны).
Действуя тем же методом, что и в решении исходной задачи, получаем: $52 \frac{m(m-1)}{2} \leq S \leq 101\frac{m^2}{4}$, откуда $m \leq 34$. Итак, в новом определителе, а значит, и в исходном, описано не больше 34 растений.
2. Эта задача связана с кодами, исправляющими ошибки. Вместо растений рассматриваются сообщения, а вместо описаний - последовательности из нулей и единиц заданной длины $n$; минимальное число различий двух последовательностей называется кодовым расстоянием $d$ (в нашей задаче $d = 51$), а сам определитель называется кодом. Заметим, что если исказить любое сообщение произвольным образом, но не больше, чем в $\frac{d-1}{2}$ позициях, то его можно отличить от любого другого сообщения в коде. Именно это свойство и понимается под исправлением ошибок.
Общая задача определения максимального размера (т. е. числа различных сообщений) кода длины $n$ с кодовым расстоянием $d$ до сих пор не решена.
Однако в теории кодов известна теорема Плоткина-Левенштейна. Она устанавливает границу для размера кода с большим кодовым расстоянием $d (2d>n)$ и утверждает, что при некотором естественном предположении есть коды соответствующего размера. В условии нашей задачи $n = 100, d = 51$, и решение демонстрирует оценку Плоткина для этих параметров: размер кода не превышает 34. Оказывается, что эта оценка достижима: можно придумать код из 34 сообщений.
В ботаническом определителе растения описываются ста признаками. Каждый из признаков может либо присутствовать, либо отсутствовать. Определитель считается хорошим, если любые два растения различаются более чем по половине признаков. Доказать, что в хорошем определителе не может быть описано более 50 растений.
Решение:
Пусть $m$ - количество растений в хорошем определителе. Оценим суммарное количество различий между всеми парами растений по всем признакам. Количество пар растений равно $\frac{m(m-1)}{2}$, и каждая пара различается не меньше, чем по 51 признаку, поэтому общее число различий $S \geq 51 \frac{m(m-1)}{2}$.
Оценим $S$ другим способом. Пусть $m_i$ - количество растений, обладающих признаком $i$, тогда число пар растений, которые $i$-й признак различает, равно $m_i(m-m_i)$, и общее число различий между растениями равно:
$S = m_1(m-m_1)+ m_2(m - m_2)+ \cdots + m_{100}(m - m_{100})$.
В силу известного неравенства, $m_i(m-m_i) \leq \frac{m^2}{4}$. Поэтому
$S \leq 100 \frac{m^2}{4} = 25m^2$.
Значит, $51 \frac{m(m-1)}{2} \leq S \leq 25m^2$, откуда $m \leq 51$.
Осталось доказать, что $ m \neq 51$. Допустим, что $m = 51$, тогда получаем строгое неравенство $m_i(m-m_i) < \frac{m^2}{4}$ (так как слева стоит целое число, а справа - дробное), и $51 \frac{m(m-1)}{2} \leq S < 25m^2$, откуда $m<51$. Противоречие. Значит, $m \leq 50$.
Комментарии. 1. Напрашивается предположение, что в хорошем определителе может быть описано 50 растений. Однако это не так. Давайте добавим к описанию растений еще один признак - четность числа имеющихся у данного растения признаков. Получим определитель, в котором для описания используется уже 101 признак, причем любые описания различаются по крайней мере по 52 признакам (если исходные описания различались только по 51 признаку, то четности числа имеющихся у этих растений признаков различны).
Действуя тем же методом, что и в решении исходной задачи, получаем: $52 \frac{m(m-1)}{2} \leq S \leq 101\frac{m^2}{4}$, откуда $m \leq 34$. Итак, в новом определителе, а значит, и в исходном, описано не больше 34 растений.
2. Эта задача связана с кодами, исправляющими ошибки. Вместо растений рассматриваются сообщения, а вместо описаний - последовательности из нулей и единиц заданной длины $n$; минимальное число различий двух последовательностей называется кодовым расстоянием $d$ (в нашей задаче $d = 51$), а сам определитель называется кодом. Заметим, что если исказить любое сообщение произвольным образом, но не больше, чем в $\frac{d-1}{2}$ позициях, то его можно отличить от любого другого сообщения в коде. Именно это свойство и понимается под исправлением ошибок.
Общая задача определения максимального размера (т. е. числа различных сообщений) кода длины $n$ с кодовым расстоянием $d$ до сих пор не решена.
Однако в теории кодов известна теорема Плоткина-Левенштейна. Она устанавливает границу для размера кода с большим кодовым расстоянием $d (2d>n)$ и утверждает, что при некотором естественном предположении есть коды соответствующего размера. В условии нашей задачи $n = 100, d = 51$, и решение демонстрирует оценку Плоткина для этих параметров: размер кода не превышает 34. Оказывается, что эта оценка достижима: можно придумать код из 34 сообщений.
