Быки и коровы

Играют двое. Один игрок заду­мывает четырехзначное число, а другой должен его отга­дать. Все цифры числа разные. Каждым ходом отгадыва­ющий называет число, также четырехзначное и также с разными цифрами. Если задуманное и названное числа имеют общие цифры, стоящие на одних и тех же местах, то такая ситуация называется «быком», которую в даль­нейшем будем обозначать «Б». Если общие цифры есть, но они стоят на разных местах, то это «корова», которую будем обозначать «К».

В ответ на ход партнера задумавший сравнивает свое число с названным и сообщает количество «быков» и «ко­ров». Например, если задуманное число 5239, а назван­ное — 2735, то ответ — «1 бык, 2 коровы» (1Б, 2К), по­скольку цифра 3 имеется в обоих числах и стоит на одина­ковых местах, цифры 2 и 5 общие, но стоят на разных местах, а цифры 7 и 9 не являются общими. Разумеется, из каждого хода извлекается некоторая ин­формация о задуманном числе, и в конце концов его уда­ется угадать. Для того чтобы игра была интересной, заду­мывает свое число каждый из партнеров. Они ходят по очереди, и выигрывает тот, кто раньше отгадает число противника.

Приведем пример. Предположим, что задумано число 3594. Тогда на первый ход 1568 получим ответ 1Б. Это означа­ет, что в задуманном числе имеется одна цифра из назван­ных, причем стоящая на своем месте. Постараемся отга­дать ее, не привлекая пока (чтобы не запутаться) других цифр. Сделаем второй ход 1586. Ответ 1Б говорит о том, что на своем месте стоит цифра 1 или 5 (а при другом возможном ответе 1К — цифра 6 или 8). Теперь следует третий ход 1658, и ответ 1К дает нам такую информацию: в задуманном числе на втором месте стоит 5, а цифр 1, б и 8 в нем нет. Ходом 2570 постараемся выяснить наличие цифр 2, 7 и 0. Ответ 1Б свидетельствует, что ход весьма удачен — этих цифр в искомом числе нет. Теперь ясно, что задуманное число состоит из цифр 3, 4, 5, 9 и на втором месте — 5. Сделаем следующий ход 4539. Ответ 1Б, ЗК означает, как легко видеть, что задумано одно из чи­сел 3594 или 9543. Чтобы «разделить» эти числа, достаточно сделать ход любым из них. Ход 3594 и ответ 4Б приводят к цели (ответ 1Б, ЗК означал бы, что задума­но число 9543). Итак, нам понадобилось шесть ходов, чтобы найти за­думанное число. Некоторый опыт игры показывает, что при рациональных действиях обычно хватает 7 или 8 хо­дов. При наиболее неблагоприятных ответах требуется, видимо, не менее 10 ходов, однако точная верхняя оценка числа ходов неизвестна.