Ответ в «Быках и коровах» (в Японии игру называют Hit & Blow) — это ряд из разных символов, выбранных из 10 (здесь это цифры 0–9). Давай посчитаем, сколько таких рядов бывает.
Как считать
Возьмём 3 разряда.
- Первая цифра: любая из 0–9, то есть 10 вариантов.
- Вторая: нельзя повторять первую, поэтому 9 вариантов.
- Третья: нельзя повторять первую и вторую, поэтому 8 вариантов.
Всего 10 × 9 × 8 = 720 вариантов. С каждым новым разрядом умножаем ещё на число оставшихся цифр (7, 6, 5…).
Число вариантов по разрядам
| Разрядов | Вычисление | Вариантов |
|---|---|---|
| 3 (★1) | 10×9×8 | 720 |
| 4 (★2) | 10×9×8×7 | 5040 |
| 5 (★3) | 10×9×8×7×6 | 30240 |
| 6 (★4) | 10×9×…×5 | 151200 |
| 7 (★5) | 10×9×…×4 | 604800 |
Ответов для 7 разрядов больше 600 тысяч. Шанс угадать с первой попытки наугад меньше одной шестисоттысячной.
Если цифры можно повторять
Если по правилам одну цифру можно использовать сколько угодно раз, каждый разряд даёт 10 вариантов: 10 × 10 × 10 = 1000 для 3 разрядов и 10000 для 4.
| Разрядов | Без повторов | С повторами |
|---|---|---|
| 3 | 720 | 1000 |
| 4 | 5040 | 10000 |
Правило «все символы разные» не просто немного уменьшает число вариантов. Оно ещё и упрощает подсчёт быков и коров: если одинаковых цифр две, трудно понять, какая из них корова (Чем отличается Mastermind).
Как подсказки сокращают число вариантов
После одной попытки остаются только те ответы, что не противоречат подсказке. Вот сколько вариантов остаётся при каждой подсказке для 3 разрядов, если названа попытка «012».
| Подсказка | Осталось вариантов |
|---|---|
| быков 0, коров 0 | 210 |
| быков 0, коров 1 | 252 |
| быков 0, коров 2 | 63 |
| быков 0, коров 3 | 2 |
| быков 1, коров 0 | 126 |
| быков 1, коров 1 | 42 |
| быков 1, коров 2 | 3 |
| быков 2, коров 0 | 21 |
| быков 3 (угадано) | 1 |
В сумме получается ровно 720. Чаще всего выходит «быков 0, коров 1»: 252 варианта из 720 (35%). После одной попытки в худшем случае остаётся 252 варианта.
Если так сокращать несколько раз, то даже из 720 вариантов при хороших попытках ответ угадывается не больше чем за 6 попыток (Есть ли выигрышная стратегия в «Быках и коровах»?).
Насколько труднее с ростом разрядов?
От 3 до 7 разрядов число вариантов вырастает более чем в 800 раз. Но число попыток растёт не так сильно: с числом разрядов растёт и число возможных подсказок, и одна попытка сообщает больше. Цель в приложении «Быки и коровы» — 6 попыток для 3 разрядов и 10 для 7.
