|
|
 |
Условие
Имеется множество билетов с номерами от 1 до 30 (номера могут повторяться). Каждый из учеников вытянул один билет. Учитель может произвести следующую операцию: прочитать список из нескольких (возможно – одного) номеров и попросить их владельцев поднять руки. Сколько раз он должен проделать такую операцию, чтобы узнать номер каждого ученика? (Учеников не обязательно 30.)
Решение
Закодируем билеты двоичными числами от 00001 до 11110. На k-м этапе учитель включает в список все номера, k-й разряд которых равен единице (например, на 3-м этапе номера 4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23, 28, 29, 30). После пятого этапа учитель узнает двоичный код номеров у всех учеников.
Четырёх этапов недостаточно даже для одного ученика: число его "возможных" номеров после каждого этапа (если учителю "не повезёт") может сократиться не более чем вдвое.
Замечания
5 баллов
