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

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

Условие

Автор: Фомин С.В.

Натуральное число n записано в десятичной системе счисления. Известно, что если какая-то цифра входит в эту запись, то n делится нацело на эту цифру (0 в записи не встречается). Какое максимальное число различных цифр может содержать эта запись?


Решение

Если в запись числа входит цифра 5, то число должно оканчиваться на 5. Тогда оно нечётно и, следовательно, содержит лишь нечётные цифры. Тем самым оно не может содержать более пяти цифр. Если же 5 не входит в десятичную запись числа, то в нём могут встречаться все остальные 8 цифр. Вот пример: 1471963248. Это число делится на 1, 2, 3, 4, 6, 7, 8, 9.


Ответ

8 цифр.

Замечания

  1. Идеология. Как построить пример? Обеспечить делимость на 8 нетрудно (число, составленное из трёх последних цифр, должно делиться на 8). Сумма всех цифр от 1 до 9 делится на 9. Изъяв пятёрку, мы можем, например, заменить её единицей и четвёркой. (Разумеется, можно также взять одну из пар (2, 3), (6, 8), (7, 7) или 5 единиц...) Осталось добиться делимости на 7.
  Это можно сделать разными способами:
  1) Расставим цифры 1, 1, 3, 4, 4, 6, 7, 8, 9 в каком-нибудь порядке, обеспечив делимость на 8. Если полученное число на 7 не делится, припишем спереди несколько девяток. Приписывание очередной девятки меняет остаток от деления на 7, так что в конце концов мы добьёмся делимости.
  2) Расставим девять из указанных десяти цифр, а десятую будем пытаться вставлять на одно из первых семи мест. Скорее всего, такой способ тоже приведёт к успеху.
  3) Пожалуй, самый простой и быстрый способ. Заметим, что 112 делится и на 7, и на 8. Поставим 112 в конец числа, а остальные цифры сгруппируем в числа, кратные 7: 49, 63, 7, 84. Из этих групп можно составить несколько различных чисел, например, 4963784112.

  2. Число 1471963248, приведённое в решении, также "устроено" по принципу, изложенному в способе 3: 14-7-196-3248. Оно меньше чем "простое" число, указанное нами, но не наименьшее. Наименьшее число с нужными свойствами – 1123449768.

 3. 6 баллов

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

олимпиада
Название Турнир городов
Турнир
Номер 7
Дата 1985/1986
вариант
Вариант весенний тур, 7-8 класс
Задача
Номер 2

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

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