Ця гра дуже добре і давно відома. За англійськи вона називається MasterMind.
Тільки тому вона для дітей, то замість цифр кольору.
в 70-е Кнут писав про стратегії для цієї гри (4-х значні числа з цифрами 0..5)
Перш ніж шукати оптимальну стратегію, треба визначитися як порівнювати дві стратегії.
Два найбільш типових підходу - в середній і найгірший випадок, тобто скільки питань в середньому і скільки питань потрібно в гіршому випадку.
Найчастіше оптимальні стратегії при цих двох підходах різні.
Але навіть обравши спосіб порівняння, може виникнути ситуація, коли відразу кілька стратегій оптимальні, в цьому випадку Ваш питання (про ймовірність відгадати за k ходів) може бути некоректен - у різних оптимальних стратегій відповіді можуть відрізнятися.
Оптимальну стратегія (вона очевидно є в силу кінцівки гри) науці не відома, так що наявність будь-яких формул сумнівно
Наприклад, Кнут пропонує стратегію з питань в середньому (для 6 кольорів).
Ніби як для Вашої гри можна побудувати стратегію, з не більш ніж 8 питаннями в гіршому випадку
Дякуємо. І все таки?
Якщо максимум потрібно 8 ходів, при цьому р = 1, то при 7-й ходах наскільки ймовірним є? При 6-й? При 5-й? І т. Д. Хоча б орієнтовно.
Я вже не пам'ятаю підрахунків в точності, але, по-моєму, було досить 6 ходів. Існує деталі, пов'язані, наприклад, з тим, чи можна в питанні повторювати цифри.
Відповідь на питання дати важко, оскільки він сильно залежить від стратегії вгадує. Припустимо вгадують обирає стратегію, спрямовану на гарантоване вгадування за 6 ходів. Він зробив 3 ходу. Далі у нього є вибір - зробити чи хід, що оптимізує угаиваніе на наступному ході, або зробити хід, який гарантує вгадування за 6 ходів. Малоймовірно, що ці варіанти дадуть один і той же хід. Тому можна ставити питання про вгадуванні на -ом ходу при конкретної стратегії вгадування. ,
Порівнюючи з Mastermind, корисно мати на увазі, що в Mastermind дозволені повторення. Тому там можливо 1296 варіантів.
А взагалі вважати нецікаво. Завдання з повною інформацією, доступною PC кінцевим перебором, і незрозумілою математичної цінністю.