Теория чисел: Игра в тепло-холодно

Должно быть, многие из нас слышали про «обучение в формате игры». Оказывается, слоганы «играй и развивайся» применимы далеко не только к дошкольникам! Вспомните, сколько математических задач представляют собой описание игры со своими особыми – математическими – правилами? А еще в математике существует очень интересный раздел – Теория чисел, и здесь формат игры имеют практически все задачи, с которыми вам предстоит столкнуться. Вы спросите, где они могут вам встретиться? Невероятно, но факт: задачи такого типа входят во вторую часть профильного ЕГЭ по математике.

Разумеется, в этот раз наша с вами задача тоже будет про игру. По условию, Миша и Гриша придумали свой вариант игры «тепло-холодно»: Миша загадывает двузначное число и отвечает «тепло» Грише тогда и только тогда, когда число, названное Гришей, имеет хотя бы одну верную цифру, а другая отличается от правильной не более чем на единицу. Нам с вами предстоит играть на стороне Гриши – попробуем угадать Мишино число за как можно меньшее число попыток?

Первый вопрос задачи звучит не очень оптимистично: нужно доказать, что способа гарантированно узнать загадочное число, истратив только 18 попыток, не существует. Но уже на этом моменте можно заметить ключевое для всего решения преобразование! Миша не использует однозначные числа, поэтому все-все значения, которые он может загадать, укладываются в прямоугольник 9*10, причем очень удобно откладывать по вертикали десятки, а по горизонтали – единицы.

Спрашивается, чем такое представление чисел может нам помочь? В таком формате легко видеть, какую область чисел покрывают Мишины ответы «тепло» или «холодно» - подходящими по условию будут числа в пяти клетках, образующих крестик с названным Гришей числом в середине. Сможем ли мы закрыть весь прямоугольник возможных чисел, используя 18 крестиков? С одной стороны, 9*10 = 90 и 5*18 = 90 – площади будет достаточно. Но, с другой стороны, чтобы замостить угловые клетки прямоугольника, Грише придется называть сами угловые числа – по-другому до них не дотянуться. При этом две клетки каждого такого крестика окажутся за пределами прямоугольника, и мы не можем их учитывать при подсчете закрытой нами площади – в итоге площади 18 крестиков просто не хватит, чтобы замостить прямоугольник, и у Гриши останутся числа, про которые он ничего не знает. Итак, справиться за 18 попыток Грише не удастся.

Перейдем ко второму вопросу задачи: в этот раз нужно показать, что 22 попыток хватит в любом случае. Что ж, у нас с вами уже есть готовая модель – прямоугольник с числами. Осталось показать Грише на его примере, как нужно действовать. В первую очередь придумаем, как замостить прямоугольник 22 крестиками: там, где крестики не помещаются, у нас остаются фигуры по 4 клетки в виде Т, трёхклеточные фигуры уголком и прямые, одна фигуры из 2 клеток и две клетки отдельно – всего ровно 23. Мы не уложились в 22, но помешает ли это решению? Увидим вместе!

Теперь нужно проанализировать, что происходит, когда Гриша называет центр очередной фигуры. Если Миша отвечает «холодно», мы отбрасываем все клетки этой фигуры и двигаемся дальше. Но если ответ «тепло», клетки фигуры (и только их) нужно проверять. Разумеется, для разных фигур на такую проверку уйдет различное максимальное число попыток: для крестика 3 хода, для фигур по 3 или 4 клетки – 2 хода, для двухклеточной фигуры – 1 ход. Попробуйте проверить это самостоятельно!

Из-за того, что на проверку крестиков уйдет больше всего попыток, предлагаем Грише начинать отгадывать именно с них. Всего крестиков 11, поэтому если хотя бы раз Миша ответил «тепло», то на полное отгадывание числа у нас уйдет 11 + 3 = 14 попыток. Отличный результат! Если же Гриша все время получает в ответ «холодно», то за 11 ходов мы отбрасываем все числа из крестиков.

Продолжим отгадывать с фигурами по 3 или 4 клетки – их всего 9. Абсолютно аналогично, если мы слышим в ответ «тепло», то максимальное число попыток для разгадывая числа окажется равным 11 + 9 + 2 = 22. Мы все еще укладываемся в рамки условия! Если же «тепло» так и не прозвучало, после 11 + 9 = 20 ходов переходим к фигуре из 2 клеток. Плюс 1 ход на проверку в случае, если Миша отвечает «тепло» - и мы отгадываем число за 20 + 1 + 1 = 22 попытки. И второй случай: если «холодно» исключает фигуры из двух клеток, последней попыткой проверяем одну из двух отдельных клеток – например, 96. Если в ответ прозвучит «тепло», то загадано 96, если «холодно» - то 98. Мы справились!

Итак, при правильной стратегии Гриша отгадает любое загаданное Мишей число за 22 попытки, а те, кто правильно решил задачу – 4 первичных балла на профильном экзамене!