Миша загадал N-значное число, все цифры которого различны, а Игорь пытается его угадать (Игорь знает, чему равно N). За один ход Игорь может выбрать несколько разрядов числа, а Миша в произвольном порядке сообщает цифры, стоящие в этих разрядах. Порядок, в котором сообщать цифры, выбирает Миша. Например, если задумано число 67890, а Игорь спросил про цифры в разрядах 1 и 5, то Миша может ответить как «6 и 0», так и «0 и 6». Для какого максимального числа N Игорь сможет гарантированно узнать число за 3 хода?
More Questions From This User See All
Answers & Comments
Verified answer
Пронумеруем разряды числа номерами от 1 до N. Пусть три хода Игоря выделяют подмножества разрядов M₁, M₂ и M₃. Каждому разряду с номером k сопоставим тройку чисел s(k)=(a₁,a₂,a₃) по правилуM₁={1,2,3,7}, M₂={1,5,6,7}, M₃={3,4,5,7} (см. рисунок).
В ответе Миши будут названы цифры, стоящие в разрядах с соответствующими номерами.
Тогда та цифра, которая будет фигурировать во всех трех ответах Миши, находится в 7-ом разряде, т.к. s(7)=111 и с такой сигнатурой этот разряд единственный.
Та цифра, которая будет фигурировать в 1-ом и 2-ом, но не в 3-м ответе Миши находится в разряде с номером 1 (см. рисунок), т.к. s(1)=110 и опять, с этой сигнатурой имеется только один разряд.
Цифра, которая будет фигурировать, например в 3-м ответе Миши, но не в 1-ом и не во 2-ом, соответствует позиции 4, т.к. s(4)=001 и т.д. Итак, по ответам Миши мы определяем сигнатуру каждой упомянутой цифры (смотрим, в каких ответах эта цифра есть, а в каких ее нет), и поскольку сигнатура однозначно связана с номером разряда, мы определяем позицию этой цифры.
Заметим, что если бы число было записано в восьмеричной системе счисления, то Игорь мог бы определить все цифры при N=8, т.к. определив семь позиций у него оставалась бы одна не задействованная цифра на 8-ую позицию.