Разделы 
Дополнительно
Задача по математике - 1212
2018-11-02 
В классе 16 учеников. Каждый месяц учитель делит класс на две группы. Какое наименьшее количество месяцев должно пройти, чтобы любые два ученика в какой-то из месяцев оказались в разных группах?
Решение:
На рис. показано, как нужно разбивать класс на две группы так, чтобы любые два ученика в какой-то из четырех месяцев оказались в разных группах. Каждому ученику соответствует столбец таблицы, а каждому месяцу -ее строка. Нуль, стоящий в клетке таблицы, означает, что данный ученик входит в первую группу, а единица означает, что данный ученик входит во вторую группу. (Таблица устроена так, что в ее i-м столбце находится двоичная запись числа i-1.)
Теперь докажем, что за три месяца выполнить требуемое условие нельзя. Составим таблицу, аналогичную приведенной выше. В ней будет 16 столбцов и 3 строки. Так как в столбце из трех клеток можно расставить нули и единицы восемью различными способами, то в таблице найдутся два одинаковых столбца. Ученики, которым соответствуют эти столбцы, в течение трех месяцев будут попадать в одну и ту же группу.
Ответ. 4 месяца.
В классе 16 учеников. Каждый месяц учитель делит класс на две группы. Какое наименьшее количество месяцев должно пройти, чтобы любые два ученика в какой-то из месяцев оказались в разных группах?
Решение:
На рис. показано, как нужно разбивать класс на две группы так, чтобы любые два ученика в какой-то из четырех месяцев оказались в разных группах. Каждому ученику соответствует столбец таблицы, а каждому месяцу -ее строка. Нуль, стоящий в клетке таблицы, означает, что данный ученик входит в первую группу, а единица означает, что данный ученик входит во вторую группу. (Таблица устроена так, что в ее i-м столбце находится двоичная запись числа i-1.)
Теперь докажем, что за три месяца выполнить требуемое условие нельзя. Составим таблицу, аналогичную приведенной выше. В ней будет 16 столбцов и 3 строки. Так как в столбце из трех клеток можно расставить нули и единицы восемью различными способами, то в таблице найдутся два одинаковых столбца. Ученики, которым соответствуют эти столбцы, в течение трех месяцев будут попадать в одну и ту же группу.
Ответ. 4 месяца.
