СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Математика профильного уровня
≡ математика
сайты - меню - вход - новости


Задания
Версия для печати и копирования в MS Word
Задание 19 № 505621

Леша задумал двузначное число (от 10 до 99). Гриша пытается его отгадать, называя двузначные числа. Если Гриша правильно называет число, или же одну цифру называет правильно, а в другой ошибается не более чем на единицу, то Леша отвечает «тепло»; в остальных случаях Леша отвечает «холодно». (Например, если задумано число 65, то назвав 65, 64, 66, 55 или 75, Гриша услышит в ответ «тепло», а в остальных случаях услышит «холодно».)

а) Покажите, что нет способа, при котором Гриша гарантированно узнает число, истратив 18 попыток.

б) Придумайте способ, при котором Гриша гарантированно узнает число, истратив 24 попытки (какое бы число ни задумал Леша).

в) А за 22 попытки получится?

Решение.

а) Расположим двузначные числа в клетках прямоугольника высоты 9 и ширины 10 (по горизонтали откладываем единицы, по вертикали – десятки). Каждой попытке Гриши соответствует крестик из пяти клеток: в центре названное им число, а по бокам четыре числа, отличающиеся в одной цифре на единицу (если названное число содержит цифру 0 или 9, некоторые клетки крестика выходят за края прямоугольника; таким клеткам никакие числа не соответствуют). Задача Гриши – покрыть прямоугольник 9 × 10 такими крестиками. Убедимся, что 18 крестиков ему не хватит. Суммарная площадь крестиков равна 18 × 5 = 90, т. е. равна площади прямоугольника. Но, покрывая угловую клетку, мы неизбежно выйдем за пределы прямоугольника, и эта потеря помешает покрыть весь прямоугольник.

б, в) Решим сразу пункт в) — убедимся, что 22 попыток хватит. Покрытие из 22 крестиков легко найти, если заметить, что крестиками можно выложить плоскость без перекрытий (правда, придётся ещё добавить несколько крестиков по краям прямоугольника). Например, Гриша может назвать числа 11, 13, 17, 25, 29, 30, 32, 37, 44, 49, 51, 56, 63, 68, 70, 75, 82, 87, 89, 90, 94, 97.

 

Примечание Александра Иванова.

Давайте рассмотрим предложенную картинку. Прямоугольник замощен фигурами разной формы: крест (5 клеток), Т-образный (4 клетки), трехклеточные (угловые и прямые), двухклеточные фигуры и две одиночные клетки.

Услышав «холодно», мы (Гриша) сразу отбрасываем все клетки названной фигуры, услышав «тепло», — начинаем проверять. Для проверки разных фигур требуется разное максимальное количество дополнительных ходов: для креста — 3 хода, для Т-образного и трехклеточных фигур — 2 хода, для двухклеточных — 1 ход.

Стратегия состоит в следующем.

Сначала называем числа, соответствующие крестам, так как для них требуется больше проверочных ходов: 25, 32, 37, 44, 51, 56, 63, 68, 75, 82, 87 (всего 11 чисел). Если мы услышали «тепло», то для угадывания числа нам потребовалось максимум 11 + 3 = 14 ходов, если же всё время мы слышали «холодно», то мы потратили 11 ходов и исключили 55 чисел.

Далее называем числа, соответствующие Т-образным и трехклеточным: 11, 13, 17, 29, 30, 49, 70, 89, 94 (таких чисел 9). Если мы теперь услышали «тепло», то для угадывания числа нам потребовалось максимум 11 + 9 + 2 = 22 хода (Ура!!!), если же всё время мы и теперь слышали «холодно», то мы потратили 11+9=20 ходов и исключили 55 + 31 = 86 чисел.

Далее называем число 90, это был двадцать первый ход. Если слышим «тепло», то проверяем одним ходом и отгадываем число за 21+1=22 хода (Ура!!!), а если слышим «холодно», то вычеркиваем еще 2 числа. Итого вычеркнуто 86 + 2 = 88 чисел, за 21 ход. Осталось два невычеркнутых числа.

ФИНАЛ (последний, 22-й ход): называем число 96. Если «тепло», то загадано число 96, если «холодно», то загадано число 98. УРА!!!

Таким образом, Гриша (с нашей помощью), при правильной стратегии максимум за 22 хода обязательно отгадает задуманное Лёшей двузначное число.

Источник: А. Ларин: Тре­ни­ро­воч­ный вариант № 45.
Раздел кодификатора ФИПИ/Решу ЕГЭ: Сюжетные задачи: кино, театр, мотки верёвки, Сюжетные задачи: кино, театр, мотки верёвки