Решение задачи 453

Условие:

За столом сидят 2018 джедаев. Любознательный Энакин хочет узнать, как их зовут (у всех джедаев разные имена). Он может показать на несколько джедаев пальцем и попросить магистра Йоду перечислить все их имена. К сожалению, порядок, в котором Йода перечисляет имена, может быть произвольным. Какое наименьшее количество раз Энакину придется отвлечь магистра Йоду от медитации?

Решение:

Закодируем джедаев разными двоичными последовательностями длины 11 без последовательности из одних нулей. Это получится сделать, так как 2¹¹−1>2018.

Покажем в первый раз пальцем на джедаев, у которых в их двоичном коде в первом разряде стоит 1, во второй раз покажем на джедаев, у которых во втором разряде стоит 1, и так далее. То есть мы отвлекли мэра 11 раз. Покажем, что теперь мы может восстановить все имена.

Понятно, что набор всех имен у нас есть, потому что про каждого джедая мы спросили хоть раз. Возьмем имя из набора, например Люк. Сопоставим ему конкретного джедая. Составим последовательность из нулей и единиц длины 11. На k-ом месте будет стоять 1, если в k-ом ответе Йоды присутствует имя Люк и 0 иначе. По полученному коду однозначно восстанавливается джедай — выберем из джедая того, чей код совпадает с нашим только что составленным. Понятно, что такой джедай найдется и причем один.

Почему нельзя за 10 вопросов (или меньше)? Пусть мы 10 раз спросили Йоду, и теперь пытаемся по ответам восстановить имена. Опять же каждому джедаю сопоставим код (длины 10): на k-ом разряде в двоичном коде джедая стоит 1, если мы на него показали пальцем, когда k-ый раз обращались к Йоде. Тогда получится 2018 двоичных кодов длины 10. По принципу Дирихле найдутся хотя бы два джедая с одинаковыми кодами. Понятно, что мы их никак не сможем различить.

Ответ: 11 раз.