Автор Тема: Докажите, что нет нулей  (Прочитано 1962 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн vrug

  • Новичок
  • *
  • Сообщений: 12
    • Просмотр профиля
Докажите, что нет нулей
« : 21 Сентябрь 2012, 13:59:30 »
Докажите, что если последняя цифра числа n не нуль,то существует целое k такое, что в десятичной записи числа kn нет ни одного нуля.

Оффлайн ira-sm

  • Старожил
  • ****
  • Сообщений: 320
    • Просмотр профиля
    • E-mail
Re: Докажите, что нет нулей
« Ответ #1 : 22 Сентябрь 2012, 12:51:35 »
Это не трудно доказать, представив умножение в столбик.
Я приведу алгоритм нахождения числа k, к примеру, для числа 100037:
Будем записывать число k с конца. Последнюю цифру выбираем так, чтобы последняя цифра произведения не была равна 0 (только при умножении на 5 четного числа может получится 0. Значит если исходное число заканчивается на 5, то берем нечетную цифру, иначе - любую цифру, отличную от 0)

   100037
            2   
  _______
   200074

Далее подберем вторую с конца цифру (число десятков).
Для нашего примера очевидно, что если мы выберем цифру 9, то при умножении 7*9=63 в записи столбика произойдет следующее:
   100037
           92
  _______
   200074
  900333
 ...
_________
        ...04
А это нам как раз и не нужно. Значит на место второго разряда нам нужно подобрать цифру так, чтобы произведение заканчивалось на цифру, не дающую в сумме с предыдущими произведениями числа, оканчивающегося на 0.
Для нашего примера это любая цифра, отличная от 9 (возьмем 3):
   100037
          32
  _______
   200074
  300111
 ________
  3201184

Поскольку в нижней строке мы все еще видим 0, продолжим подбирать дальше.
Очевидно, что третьей с конца цифрой не может быть 7.
И так далее.


Оффлайн CD_Eater

  • Эксперт
  • ******
  • Сообщений: 1906
    • Просмотр профиля
Re: Докажите, что нет нулей
« Ответ #2 : 23 Сентябрь 2012, 02:16:16 »
и почему это когда-нибудь закончится?

Оффлайн CD_Eater

  • Эксперт
  • ******
  • Сообщений: 1906
    • Просмотр профиля
Re: Докажите, что нет нулей
« Ответ #3 : 23 Сентябрь 2012, 17:06:34 »
Частный случай.
Если n = 2k, то методом, описанным ira-sm, можно, выгнать нули из k младших разрядов и обнулить все более старшие разряды.  Получим Tk - k-значное число без нулей, кратное 2k
Аналогично можно получить Fk  - k-значное число без нулей, кратное 5k.

Теперь общий случай.
Если n оканчивается на 1,3,7,9, то число из фи(n) девяток будет делиться на n.
Если n оканчивается на 2,4,6,8, то n = 2k * m, где m оканчивается на 1,3,7,9.  Берём число Tk и записываем его фи((10k-1)*m) раз подряд.
Если n оканчивается на 5, то n = 5k * m, где m оканчивается на 1,3,7,9.  Берём число Fk и записываем его фи((10k-1)*m) раз подряд.