Ответ в «Быках и коровах» (в Японии игру называют Hit & Blow) — это ряд из разных символов, выбранных из 10 (здесь это цифры 0–9). Давай посчитаем, сколько таких рядов бывает.

Как считать

Возьмём 3 разряда.

  • Первая цифра: любая из 0–9, то есть 10 вариантов.
  • Вторая: нельзя повторять первую, поэтому 9 вариантов.
  • Третья: нельзя повторять первую и вторую, поэтому 8 вариантов.

Всего 10 × 9 × 8 = 720 вариантов. С каждым новым разрядом умножаем ещё на число оставшихся цифр (7, 6, 5…).

Число вариантов по разрядам

РазрядовВычислениеВариантов
3 (★1)10×9×8720
4 (★2)10×9×8×75040
5 (★3)10×9×8×7×630240
6 (★4)10×9×…×5151200
7 (★5)10×9×…×4604800

Ответов для 7 разрядов больше 600 тысяч. Шанс угадать с первой попытки наугад меньше одной шестисоттысячной.

Если цифры можно повторять

Если по правилам одну цифру можно использовать сколько угодно раз, каждый разряд даёт 10 вариантов: 10 × 10 × 10 = 1000 для 3 разрядов и 10000 для 4.

РазрядовБез повторовС повторами
37201000
4504010000

Правило «все символы разные» не просто немного уменьшает число вариантов. Оно ещё и упрощает подсчёт быков и коров: если одинаковых цифр две, трудно понять, какая из них корова (Чем отличается Mastermind).

Как подсказки сокращают число вариантов

После одной попытки остаются только те ответы, что не противоречат подсказке. Вот сколько вариантов остаётся при каждой подсказке для 3 разрядов, если названа попытка «012».

ПодсказкаОсталось вариантов
быков 0, коров 0210
быков 0, коров 1252
быков 0, коров 263
быков 0, коров 32
быков 1, коров 0126
быков 1, коров 142
быков 1, коров 23
быков 2, коров 021
быков 3 (угадано)1

В сумме получается ровно 720. Чаще всего выходит «быков 0, коров 1»: 252 варианта из 720 (35%). После одной попытки в худшем случае остаётся 252 варианта.

Если так сокращать несколько раз, то даже из 720 вариантов при хороших попытках ответ угадывается не больше чем за 6 попыток (Есть ли выигрышная стратегия в «Быках и коровах»?).

Насколько труднее с ростом разрядов?

От 3 до 7 разрядов число вариантов вырастает более чем в 800 раз. Но число попыток растёт не так сильно: с числом разрядов растёт и число возможных подсказок, и одна попытка сообщает больше. Цель в приложении «Быки и коровы» — 6 попыток для 3 разрядов и 10 для 7.