Если честно, я долго думал, как начать этот текст так, чтобы его дочитали до конца. Потому что это не просто история про задачу. Это история про мышление. Про тот редкий момент, когда ты понимаешь: перед тобой не просто ученик — перед тобой человек, который видит иначе. И кажется, что что классическая задача ещё не сказала своего последнего слова.
И да — мне нужна ваша помощь. Потому что есть гипотеза, которая либо ломает классическое решение, либо требует строгого опровержения.
Начну с того, что сегодня с учеником мы решали классическую олимпиадную задачу, которую знают, наверное, все айтишники:
Какое минимальное количество вопросов с ответом «да/нет» нужно, чтобы гарантированно угадать число от 1 до 20?
И скорее всего многие предложат приблизительно следующее решение (даже Gemeni и ChatGPT предлагают именно его):
Для поиска ответа используется алгоритм бинарного поиска (метод деления пополам).
1. Суть метода
Каждый вопрос должен разделять оставшееся множество чисел на две максимально равные части. Ответ «да» или «нет» исключает ровно половину вариантов.
2. Математическая модель
Чтобы найти число среди ( N ) вариантов, нужно такое количество вопросов ( i ), чтобы выполнялось условие: 2^i ≥ N
3. Расчёт для 20 чисел
- Если задать 4 вопроса, можно различить только 2^4 = 16 чисел — этого недостаточно для диапазона из 20 чисел.
- Если задать 5 вопросов, можно различить до 2^5 = 32 чисел. Пяти вопросов достаточно.
4. Пример стратегии вопросов
- Вопрос 1: «Число больше 10?»
(Остаётся 10 чисел: либо 1–10, либо 11–20)- Вопрос 2: «Число больше 5 (или 15)?»
(Остаётся 5 чисел)- Вопрос 3: «Число больше 3 (или 8/13/18)?»
(Остаётся 2 или 3 числа)- Вопрос 4:
(Остаётся 1 или 2 числа)- Вопрос 5:
Финальное определение конкретного числаЕсли число будет угадано раньше — это удача, но гарантированно (в худшем случае) потребуется именно 5 вопросов.
✅ Ответ: Минимальное количество вопросов — 5.
Но сегодня на занятии Николай (мой ученик) делает первую попытку решения и задаёт вопрос:
А сумма делителей числа больше 14?
Да-да! Не «число больше 10?» Не деление пополам. Не классика. Он, как мне кажется, просто меняет пространство задачи. И дальше мы быстро составили таблицу. И видим, что если смотреть не на числа от 1 до 20, а на сумму их делителей, то множество из 20 элементов превращается в множество из 17. А 17 — это ещё не 16, но это уже опасно близко к 2 в 4 степени.
То есть фактически, как это вижу я, Николай начал искать способ сжать пространство задачи. Осознанно или нет – я не знаю, но факт остается фактом: он задал такой вопрос. И как результат – мы приблизились к 4 вопросам, но их вес равно не хватало.
После занятия я не смог остановиться и начал искать другие трансформации. И в качестве одного из вариантов я рассмотрел такой: взял делители числа и посчитал сколько будет «наибольший минус сумма остальных». В результате было получено множество уже из 13 значений. А это меньше 2 в 4 степени!!!
И теперь главный вопрос:
Если мы можем: преобразовать множество из 20 чисел в множество из 13 (≤16) значений, то означает ли это, что задачу можно решить за 4 вопроса? Или здесь есть фундаментальное ограничение, которое не позволит это сделать, даже при таких преобразованиях дальнейших множеств?
Поэтому, если вы любите математику, занимаетесь теорией информации или просто любите красивые задачи — подключайтесь. Я буду очень благодарен, даже если кто-то покажет уже существующее решение или докажет, что такой подход невозможен. Потому что сейчас для меня это редкое состояние, когда кажется, что классическая задача ещё не сказала своего последнего слова.
PS И немного личного. Я написал маме Николая и сказал, что у неё растёт очень сильный ребёнок. Потому что такие идеи: не заучиваются не натаскиваются не приходят «по программе». Они возникают там, где есть настоящее нестандартное мышление.
