Последняя цифра
Ошибка.
Попробуйте повторить позже
Маша, скучая на уроке математики, проделала с некоторым 2015-значным натуральным числом следующую операцию: от десятичной записи этого числа она отбросила последнюю цифру и к умноженному на 3 получившемуся числу прибавила удвоенную отброшенную цифру. С полученным числом она опять проделала ту же операцию и так далее. После многократного применения этой операции получающиеся у Маши числа перестали меняться, и тогда она остановилась.
(a) Какое число оказалось у Маши в конце?
(b) Какое наименьшее число могло быть у Маши в самом начале (укажите две его последние цифры)?
Пункт а), подсказка 1
Нам говорят, что числа у Маши перестали меняться - намекают на уравнение! Попробуйте его составить, грамотно обозначив число, получившееся у Маши.
Пункт а), подсказка 2
Подумайте, как часто такое уравнение имеет решение, если одна из наших переменных - цифра
Пункт б), подсказка 1
Изначально у нас было какое-то гигантское число, а стало 17 ⇒ число уменьшилось. Это произошло из-за того, что у Маши было какое-то специальное число? Или так всегда происходит?
Пункт б), подсказка 2
Верно, большое число всегда уменьшается после применения такой операции. Мы должны получить 17 в какой-то момент, надо бы понять что-то про изначальное число из этого. А какое число могло быть у Маши перед тем, как она получила 17? Видите что-то общее у этих чисел?
Пункт б), подсказка 3
Давайте попробуем доказать в общем виде, что если получилось число, делящееся на 17, то и до этого число делилось на 17. Попробуйте связать (10x + y) и (3x + 2y) так, чтобы там фигурировало 17.
Пункт б), подсказка 4
Можно заметить, что если к 3х + 2y добавить 17x, получится 2(10x + y). То есть изначальное число должно делиться на 17, надо просто найти наименьшее такое ⇒ надо взять 10²⁰¹⁴ и добавить к нему недостающий остаток
Пункт б), подсказка 5
17 - простое число. Помните теорему, помогающую найти остаток от деления на простое число?
Пункт б), подсказка 6
Конечно, это Малая теорема Ферма! Остаётся только представить 2014 в виде 16k + r, и задачка убита!
a) Пусть в конце осталось число 
, оканчивающееся на цифру 
. Тогда 
после очередной операции станет равным
Равенство 
равносильно 
и, так как 
– цифра, то 
. Поэтому 
.
b) Заметим, что если число 
, тогда оно обязательно уменьшается: 
равносильно 
. (что для 
всегда
верно). Из соотношения
следует, что число 
делится на 
тогда и только тогда, когда 
делится на 
. Поскольку стабилизация операции
происходит на числе 
, то исходное число также должно делиться на 
Найдём наименьшее 
-значное число, которое делится на 
. По малой теореме Ферма 
поэтому
Тогда число 
- наименьшее число, которое делится на 
нацело, значит, это и будет наименьшее число, которое могла
выписать Маша. Его последние две цифры 
.
a) 
b) 
(число 
)
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
