Способа, который гарантированно угадывает с первой попытки, в «Быках и коровах» нет: при первой попытке никаких подсказок ещё нет. Зато есть способ, который угадывает любой ответ не больше чем за определённое число попыток. Если назвать это выигрышной стратегией, за сколько попыток можно гарантированно угадать?

Мы посчитали по тем же правилам, что и в приложении «Быки и коровы» (10 символов от 0 до 9, и ответ, и попытки состоят из разных символов), за сколько попыток находятся все ответы для 3 и 4 разрядов при разных стратегиях. Угадывающая попытка тоже считается за одну.

Три стратегии

  • Стратегия A (ряды, не противоречащие подсказкам, по порядку): называть первый по порядку ряд среди тех, что не противоречат прежним подсказкам. Это близко к тому, как играют на бумаге.
  • Стратегия B (уменьшать худший случай): для каждой попытки смотреть, как возможные подсказки делят варианты, и называть ряд, у которого самая большая оставшаяся группа наименьшая.
  • Стратегия C (уменьшать среднее): называть ряд, при котором среднее число оставшихся вариантов (сумма квадратов размеров групп) наименьшее.

В стратегиях B и C используются и ряды, противоречащие подсказкам. Даже если ряд заведомо не ответ, он может хорошо разделить варианты, и тогда он выгоден. Первую попытку можно выбрать любую, подсказки выпадают одинаково, поэтому начинаем с «012» для 3 разрядов и «0123» для 4 (любой ряд после переименования символов и мест превращается в такой же).

Результаты для 3 разрядов (все 720 ответов)

СтратегияВ среднемВ худшем случае
A ряды, не противоречащие подсказкам, по порядкуоколо 5,279
B уменьшать худший случайоколо 5,126
C уменьшать среднееоколо 5,076

При стратегиях B и C любой ответ находится не больше чем за 6 попыток. При стратегии A в среднем тоже около 5,3, но если не повезёт, на какой-то ответ уходит 9.

Результаты для 4 разрядов (все 5040 ответов)

СтратегияВ среднемВ худшем случае
A ряды, не противоречащие подсказкам, по порядкуоколо 5,569
B уменьшать худший случайоколо 5,347
C уменьшать среднееоколо 5,277

Для 4 разрядов при стратегиях B и C любой ответ находится не больше чем за 7 попыток. При стратегии C только на 86 ответов из 5040 ушло 7 попыток, а почти половина ответов угадана за 5.

Число попыток при стратегии CОтветов
11
24
359
4568
52423
61899
786

Здесь показаны результаты только этих трёх стратегий. Более изобретательная стратегия могла бы ещё уменьшить среднее.

Вторая попытка не обязательно из одних новых символов

Когда играет человек, понятнее и проще называть в первой и второй попытках разные символы (Советы по «Быкам и коровам»). Но расчёт показывает, что это не всегда лучший вариант.

Для 4 разрядов пусть первая попытка «0123» дала быков 0 и корову 1 (остаётся 1440 вариантов). Сравним варианты второй попытки.

Вторая попыткаСреднее остаётсяВ худшем случае остаётся
4567 (только новые символы)около 295504
1045 (2 старых символа и 2 новых)около 254408

Если сдвинуть старые символы на другие места и добавить новые, варианты делятся лучше. Вероятно, это потому, что если уже известно, что какой-то из символов первой попытки есть в ответе, то, поставив его на другое место, получаешь заодно и информацию о местах. С другой стороны, если первая подсказка «быков 0, коров 0» (остаётся 360 вариантов), то расчёт тоже показывает, что лучше всего взять только новые символы, например «4567».

Как это применить человеку

Повторять стратегии компьютера в уме трудно, но их идею использовать можно.

  1. Первая попытка может быть любой.
  2. Во второй бери символы, про которые узнали, что они есть в ответе, ставь их на другие места и добавляй новые.
  3. С третьей попытки называй ряды, не противоречащие подсказкам. Когда вариантов останется мало, выпиши их и сравни.

Цель в приложении (6 попыток для 3 разрядов и 7 для 4) совпадает с числом попыток, которое в расчёте выше при хорошей стратегии достигается всегда. Если угадал в пределах цели, это очень хороший результат. Среднее число попыток, включая 5–7 разрядов, собрано в статье За сколько попыток в среднем угадывают, а как превратить стратегию в программу, рассказано в статье Решаем на компьютере.