|
|
 |
Условие
В классе 16 учеников. Каждый месяц учитель делит класс на две группы.
Какое наименьшее количество месяцев должно пройти, чтобы каждые два ученика в какой-то из месяцев оказались в разных группах?
Решение
Пример. На рисунке показано, как нужно разбивать класс на две группы так, чтобы каждые два ученика в какой-то из четырёх месяцев оказались в разных группах. Каждому ученику соответствует столбец таблицы, а каждому месяцу – её строка. Нуль, стоящий в клетке таблицы, означает, что данный ученик входит в первую группу, а единица означает, что данный ученик входит во вторую группу. Поскольку совпадающих столбцов нет, каждые два ученика хотя бы одни месяц из четырёх находятся в разных группах.
Оценка. Докажем, что за три месяца выполнить условие нельзя. Составим аналогичную таблицу 3×16. В столбце можно расставить нули и единицы только 8 способами, поэтому найдутся два одинаковых столбца. Соответствующие этим столбцам ученики все три месяца попадают в одну группу.
Ответ
4 месяца.
Замечания
Идеология. В i-м столбце таблицы находится двоичная запись числа i – 1.
