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

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

Условие

Автор: Анджанс А.

Десятичные записи натуральных чисел выписаны подряд, начиная с единицы, до некоторого n включительно:   12345678910111213...(n).
Существует ли такое n, что в этой записи все десять цифр встречаются одинаковое количество раз?

Решение

  Индукцией по числу знаков докажем, что единиц в такой записи всегда больше, чем нулей. База (выписаны несколько первых цифр) очевидна: нулей в записи нет, а единица есть.
  Шаг индукции. Пусть число n  (k+1)-значно. Разобьём запись, начиная с числа 10k, на блоки по 10k чисел; последний блок может быть неполным. В каждом полном блоке сотрём первые цифры у всех чисел. Получится запись, в которой выписаны все k-значные числа от 0...0 до 9...9. Ясно, что в ней все цифры встречаются одинаковое число раз. В неполном блоке также сотрём первые цифры у всех чисел. При этом появится некоторое количество чисел, начинающихся с нулей. Эти нули переставим (спереди) к соответствующим "старым" числам, у которых было не более k знаков, (эти числа не вошли в блоки) и припишем спереди нули к тем "старым" числам, для которых нулей не хватило. Число 0...0, образовавшееся из первого числа неполного блока, переставим в начало записи и тоже будем считать "старым" k-значным числом. Теперь у "старых" k-значных чисел (после приписывания нулей "старых" чисел с меньшим числом знаков не осталось) нулей столько же, сколько единиц, а у "новых" чисел (в которые превратились (k+1)-значные числа неполного блока) по предположению индукции единиц больше, чем нулей. Но по сравнению с исходной ситуацией число нулей не уменьшилось, а число единиц уменьшилось.


Ответ

Не существует.

Замечания

3 балла

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

олимпиада
Название Турнир городов
Турнир
Номер 15
Дата 1993/1994
вариант
Вариант осенний тур, основной вариант, 10-11 класс
Задача
Номер 2
журнал
Название "Квант"
год
Год 1994
выпуск
Номер 2
Задача
Номер М1428

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

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