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

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

Условие

  Назовём натуральное число хорошим, если все его цифры ненулевые. Хорошее число назовём особым, если в нём хотя бы k разрядов и цифры идут в порядке строгого возрастания (слева направо).
  Пусть имеется некое хорошее число. За ход разрешается приписать с любого края или вписать между любыми его двумя цифрами особое число или же, наоборот, стереть в его записи особое число. При каком наибольшем k можно из каждого хорошего числа получить любое другое хорошее число с помощью таких ходов?


Решение

  Очевидно, в особом числе не более девяти цифр. Если  k = 9,  то при каждой операции число цифр меняется ровно на 9, то есть остаток от деления на 9 числа его цифр не меняется, и из однозначного числа нельзя сделать двузначное.
  Пусть  k = 8.  Поскольку все операции обратимы, то достаточно доказать, что можно вставить любую цифру. Докажем индукцией по n, что можно вставить цифру n.
  База. Чтобы вставить 1, вставим сначала 123456789, а затем вычеркнем 23456789.
  Шаг индукции. Пусть мы умеем вставлять (и вычёркивать) цифры от 1 до  n – 1 < 9.   Чтобы вставить n, вставим сначала 123456789, сотрём 12...(n–1) по одной цифре, затем по одной цифре вставим 12...(n–1) справа от n и наконец вычеркнем число 12...(n–1)(n+1)...9 (при  n = 9  последние два действия не нужны, а при  n = 8  вычёркивается число 12...79).


Ответ

При  k = 8.

Замечания

7 баллов.

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

олимпиада
Название Турнир городов
Турнир
Дата 2011/2012
Номер 33
вариант
Вариант осенний тур, сложный вариант, 10-11 класс
Задача
Номер 5

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

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