Миша загадал N-значное число, все цифры которого различны, а Игорь пытается его угадать...

Question

Миша загадал N-значное число, все цифры которого различны, а Игорь пытается его угадать (Игорь знает, чему равно N). За один ход Игорь может выбрать несколько разрядов числа, а Миша в произвольном порядке сообщает цифры, стоящие в этих разрядах. Порядок, в котором сообщать цифры, выбирает Миша. Например, если задумано число 67890, а Игорь спросил про цифры в разрядах 1 и 5, то Миша может ответить как «6 и 0», так и «0 и 6». Для какого максимального числа N Игорь сможет гарантированно узнать число за 3 хода?

Answer 1

Для N = 7.

Для каждой позиции числа запомним строчку из трёх значков, в которой на i-м месте стоит +, если Игорь спросил про эту позицию на i-м шаге, и -, если не спросил. Например, строчка +-+ соответствует позиции, про которую спросили в первом и третьем вопросах.

Заметим, что если такие строчки для каких-то двух позиций совпадут, то Игорь не сможет узнать, на каком из этих двух мест какое число стоит, эти позиции для него ничем не отличаются. Так как различных строчек из трёх символов 2^3 = 8, то N <= 8.<br>
N = 8 не подходит, про какую-то позицию он будет вынужден не спросить ни разу (это соответствует строчке ---), но тогда он не будет уверен, какая цифра стоит на этой позиции: есть 3 возможных варианта.

N = 7 подходит. 
Пусть на первом шаге он спрашивает про позиции 1, 3, 5, 7; на втором — про 2, 3, 6 и 7; на третьем — про 4, 5, 6 и 7. Тогда по тому, на каком шаге какое число появилось, он легко определит, где какая цифра где стоит. Например, если цифра 7 появилась в ответах на вопросы 1 и 3, то она на пятой позиции.

Ответ. 7