ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 98612
Темы:    [ Перестановки и подстановки (прочее) ]
[ Десятичная система счисления ]
[ Четность и нечетность ]
[ Примеры и контрпримеры. Конструкции ]
Сложность: 4-
Классы: 10,11
В корзину
Прислать комментарий

Условие

Сто номерков выложили в ряд в порядке возрастания: 00, 01, 02, 03, ..., 99. Затем номерки переставили так, что каждый следующий номерок стал получаться из предыдущего увеличением или уменьшением ровно одной из цифр на 1 (например, после 29 может идти 19, 39 или 28, а 30 или 20 – не может). Какое наибольшее число номерков могло остаться на своих местах?


Решение

  Оценка. После перестановки суммы цифр соседних чисел отличаются на единицу. Поэтому либо чётность суммы цифр каждого номерка совпадает с чётностью его места, либо, наоборот, эти чётности у всех номерков различны. А до перестановки чётности совпадали ровно в половине случаев: в каждом втором десятке. Значит, результат сравнения изменился у 50 номерков, и они не могли остаться на месте.
  Пример, где на месте ровно 50 номерков (выделены жирным): переворачиваем десятки с первой нечётной цифрой. Получится 00, 01, …, 09, 19, 18, ..., 10, 20, 21, ..., 29, 39, 38, ..., 91, 90.


Ответ

50 номерков.

Замечания

5 баллов

Источники и прецеденты использования

олимпиада
Название Турнир городов
Турнир
Дата 2002/2003
Номер 24
вариант
Вариант весенний тур, тренировочный вариант, 10-11 класс
Задача
Номер 4

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .