theJam.ru

Логические задачиПоследние k цифр

16 ноября 2008 | Добавил: SoVictor

Вот нашёл одну интересную и несложную задачку, которую нам давали на тренинге

"Есть два натуральных числа а и b, последние k цифр которых совпадают

Докажите, что при любом натуральном n последние k цифр чисел a^n и b^n так же будут совпадать"

Хотите регулярно получать новые задачи и познавательные топики? Подпишитесь на рассылку

Комментариев: 10

  1. rin пишет:

    Чё то не понятно, надо доказать, что если а=b(частный случай, не искажающий условий), то a^n=b^n? это и так ясно :)

  2. Victor пишет:

    это да
    Но надо доказать для общего случая
    Тоесть а может быть и не равно b, но последние k цифр у них одинаковые

  3. rin пишет:

    Я имел в виду, что у исходных чисел мы просто отбрасываем ненужные первые цифры. Пока не останется k последних. Т.е. а(k)=b(k)
    Почему это допустимо? Да потому, что возведение в степень это умножение, умножение происходит по извесным правилам.

  4. rin пишет:

    Я не представляю просто, как можно придумать доказательство. Для меня эт чёт-то затруднительно :)

  5. Victor пишет:

    В том то и суть. Это кажется интуитивно понятным и возможно даже очевидным, но нужно сформулировать строгое математическое доказательство :)

  6. Andrew пишет:

    числа а и b можно продставить в таком виде:
    a=f*10^k+y
    b=m*10^k+y
    а стало быть, при воззведении их в степень n, получится:
    a^n=(f*10^k+y)^n
    b^n=(m*10^k+y)^n
    а дальше простой примитив, расскладываем в ряд(помоему это называется так, вроде уже подзабыл),и получается, вот что:
    ...нас интересую два последних члена...
    ...+(m*10^k)*k^(n-1)+y^n
    ...+(f*10^k)*k^(n-1)+y^n

    откуда видно, что последние k цифр будут одинаковы, т.к. число которое они состовляют. получается из одинаковых слагаемых

    P.S. у второго справа члена ещё множитель должно стоять, но я уже забыл что, уже непомню точно, но на доказательство оно не влияет

  7. Victor пишет:

    Верно
    Но есть куда более красивое решение
    Приведу его завтра, если никто не придумает чего-то нового

  8. Andrew пишет:

    Ну можно и иначе.
    Что харрактеризует в первую очередь числа a и b? То, что их разница дает некое число, с k нулей в конце:
    a-b=y*10^k
    Значит, чтобы решить задачу, нужно показать, что числа a^n и b^n после вычитания, тоже, дадут некое число с k нулей в конце.
    Представим числа а и b в таком виде:
    a=f*10^k+y
    b=m*10^k+y
    Найдём разницу a^n и b^n:
    a^n-b^n=(f*10^k+y)^n-(m*10^k+y)^n=....тут опять расскладываем на ряды...=
    =...y^n сокращается...=...в итоге, в каждом оставшемся члене есть общий множетель 10^k...=
    =...выносим его за скобки и получаем...=10^k(...тут всякая фигня...)
    В результате мы показали, что разница a^n и b^n дает некое число с k нулей в конце.

  9. Victor пишет:

    Ну, можно и ещё проще :)
    Как вы верно заметили, последние k цифр числа a-b - нули
    a^n - b^n = (a-b)(неполный_многочлен_степени_n-1)
    так как число а^n - b^n делится на a-b, последние k его цифр - нули
    Значит, последние k цифр у чисел а и b совпадают

  10. Virtus пишет:

    Остатки от деления на натуральное N образуют кольцо, доказывается элементарно
    a=b(mod N) => a^n=b^n(mod N). Равенство последних k цифр - частный случай при N=10^k

Комментировать!

Друзья, обращаю ваше внимание, что все бессмысленные и пустые сообщения будут удаляться, ровно как и комментарии с заведомо не существующми e-mail адресами. Спасибо!


Случайное:
ОБЗОР ИГРЫ ASSASIN’S CREED ROGUE
Assassin’s Creed Rogue, последняя на сегодняшний день «полноценная», если так можно сказать, часть и
Полезные советы перед началом прохождения The Witcher 3
Относительно недавно состоялся выход, наверное, одной из самых ожидаемых игр как в жанре RPG, так
История возникновения компьютерных игр
Многие пользователи интересуются феноменом огромной популярности индии - игр, несмотря на то, что мн
Обзор Игры FAR CRY 3
Far Cry 3 – это игра, которая у многих ассоциируется всего лишь с одним словом – «безумие». Мы играе
Какие бывают на данный момент типы компьютерных игр?
Классификация компьютерных игр – это достаточно спорный вопрос, поскольку на данный момент предостав


 
2005-2011 theДжем.ru - сайт для тех, кто умеет читать и думать. ↑ вверх
полезно знать