Тема ММО (Московская математическая олимпиада)

Теория чисел на ММО

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела ммо (московская математическая олимпиада)
Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#85484

Докажите, что если при n∈ ℕ  число 2+ 2√12n2+-1  целое, то оно точный квадрат.

Источники: ММО - 2024, второй день, 11.3 (см. mmo.mccme.ru)

Подсказки к задаче

Подсказка 1

Внимательно посмотрим на выражение. Если наше выражение целое при любых натуральных n, то оно четное. Обозначим его за 2k.

Подсказка 2

Что можно сказать про k после возведения в квадрат полученного уравнения на n и k?

Подсказка 3

Что k — чётное, то есть k = 2m. Получили, что произведение взаимно простых равно квадрату числа. А часто ли такое происходит?

Подсказка 4

Нужно разобрать 2 случая, один из которых не подойдет из-за остатков по модулю 3

Показать доказательство

Если число 2+ 2√12n2+1-  целое при n∈ ℕ  , то оно чётное. Обозначим 2 +2√12n2+-1=  2k,k ∈ℕ  . Тогда √12n2+-1= k− 1  . Возводя это равенство в квадрат, получаем

   2  2
12n = k − 2k

Число k  чётное: k= 2m  , где m ∈ ℕ  .

Тогда

   2    2
12n = 4m  − 4m

3n2 =(m − 1)m

Поскольку числа m  и m − 1  взаимно просты, следует рассмотреть два случая:

1) m− 1= u2,m = 3v2  , где u,v ∈ ℕ,u⋅v = n  ;

2) m− 1= 3u2,m = v2  , где u,v ∈ ℕ,u⋅v = n  .

В первом случае имеем 3v2− 1= u2  , то есть u2  даёт остаток 2 при делении на 3 . Это невозможно, так как точный квадрат может давать при делении на 3 только остатки 0 или 1.

Во втором случае получаем 2+ 2√12n2+-1= 4m =(2v)2  - точный квадрат.

Ошибка.
Попробуйте повторить позже

Задача 2#72975

Некоторые неотрицательные числа a,b,c  удовлетворяют равенству a+ b+c =2√abc.  Докажите, что bc≥ b+c.

Источники: ММО-2022, 11.1 (см. mmo.mccme.ru)

Подсказки к задаче

Подсказка 1

Числа неотрицательны, присутствует и произведение, и сумма... Как их можно связать?

Подсказка 2

Неравенством о средних!

Подсказка 3

Также можно попробовать рассмотреть равенство из условия как квадратный трëхчлен относительно чего-нибудь.

Показать доказательство

Первое решение. По неравенству о средних:

       √ ---
a+ bc≥ 2 abc= a+ b+ c⇒ bc≥b+ c

Второе решение. Числа a,b  и c  неотрицательны, поэтому исходное равенство можно рассматривать как квадратное уравнение относительно √a:

(√a)2+ 2√bc√a +b+ c= 0

По условию это уравнение имеет хотя бы одно решение, а значит, D ∕4=bc− b− c≥0.

Ошибка.
Попробуйте повторить позже

Задача 3#72978

Таня последовательно выписывала числа вида n7− 1  для натуральных чисел n= 2,3,...  и заметила, что полученное при n= 8  число делится на 337.  А при каком наименьшем n >1  она получит число, делящееся на 2022?

Источники: ММО-2022, 11.2, (см. mmo.mccme.ru)

Подсказки к задаче

Подсказка 1

Никому ещё не вредило разложение чисел на простые множители в задачках на теорию чисел. Давайте разложим 2022 и поймём, какие условия накладывает каждый из множителей.

Подсказка 2

Мы понимаем, что нам достаточно просто перебрать все остатки по каждому из модулю, чтобы найти все условия на n, но как бы ускорить этот перебор?

Подсказка 3

Попробуйте подумать, какое максимальное кол-во решений может иметь сравнение n^7 = 1 (mod 337) на отрезке [0;336], а ещё подумать, что происходит с решением сравнения, если его возвести в произвольную положительную степень?

Подсказка 4

Мы понимаем, что решений не больше 7 и что возведение решения в положительную степень не портит сравнение, остаётся перебрать маленькие n, пока мы не сможем применить эти 2 факта, проверить, что хотя бы одно из них удовлетворяет остальным условиям, полученным из сравнений по mod 2 и mod 3, и выбрать из них наименьшее.

Показать ответ и решение

Пусть натуральное число n  таково, что n7− 1  делится на 2022 =2⋅3⋅337.  Тогда n7− 1  делится на 2  и на 3,  поэтому n  — нечётное число, имеющее остаток 1  при делении на 3.  Помимо того,  7
n − 1  делится на 337.  Заметим, что если два числа сравнимы по модулю 337  (т.е. дают одинаковые остатки при делении на 337  ), то седьмые степени этих чисел также сравнимы по модулю 337.  Это означает, что для нахождения искомого числа достаточно рассмотреть все целые числа n  из промежутка [0;336],  удовлетворяющие сравнению  7
n ≡ 1(mod337).

Мы будем пользоваться следующим утверждением. Пусть p  — простое число, Pk  — многочлен степени k  с целыми коэффициентами, старший коэффициент которого не делится на p;  тогда сравнение Pk(n) ≡0(modp)  имеет не более k  решений среди целых чисел 0 ≤n <p.

Найдём теперь все решения сравнения  7
n ≡ 1(mod337)  на отрезке [0;336].  Нам известны два решения: n1 =1  , n2 = 8.  Заметим, что если n  — решение сравнения n7 ≡ 1  (mod337),  то для любого натурального s  числа ns  также являются решениями. Следовательно, решениями данного сравнения являются числа

82 = 64≡ 64(mod337)
83 = 512 ≡175(mod337)
84 ≡ 8⋅175 ≡52(mod337)
 5
8 ≡ 8⋅52≡ 79(mod337)
86 ≡ 8⋅79≡ 295(mod337)

Итак, мы нашли семь решений на отрезке [0;336]:n1 = 1,n2 =8,n3 = 52,n4 = 64,n5 =79,n6 = 175,n7 = 295.  Так как число 337  простое, по сформулированному выше утверждению других решений на этом отрезке нет. Из них нечётными и имеющими остаток 1  при делении на 3  являются n1 =1,n5 = 79,n6 =175  и n7 = 295.  Из них наименьшее, большее 1,  есть n5 = 79.

Ответ:

 79

Ошибка.
Попробуйте повторить позже

Задача 4#79881

На доске записано натуральное число. Если у него стереть последнюю цифру (в разряде единиц), то останется ненулевое число, которое будет делиться на 20,  а если первую — то на 21.  Какое наименьшее число может быть записано на доске, если его вторая цифра не равна 0?

Источники: ММО-2021, 11.1(см. mmo.mccme.ru)

Подсказки к задаче

Подсказка 1

Раз у нас число без последней цифры делится на 20, то и предпоследняя цифра равна 0. Тогда что можно сказать про кол-во цифр в числе, если учитывать второе условие на наше число?

Подсказка 2

Верно! Наше число хотя бы четырёхзначное. Теперь попробуем посмотреть на число, оставшееся после стирания последней цифры. Оно хотя бы трёхзначное. Попробуем перебирать трёхзначные числа, делящиеся на 20, и посмотреть в каждом случае, выполняется ли условие с делимостью на 21.

Подсказка 3

Отлично! Мы получили, что 100, 120, 140 не подходят. В случае же с 160 найти противоречие не получается. Тогда попробуем построить пример.

Показать ответ и решение

Предпоследняя цифра числа равна 0,  так как число без последней цифры делится на 20.  Значит, число хотя бы четырехзначное. Заметим, что число, оставшееся после стирания последней цифры, не может равняться 100  по условию. Также это число не может равняться 120  и 140,  так как числа вида ---
20a  и ---
40a  не делятся на 21.  Для 160  существует единственный пример: 1609.

Ответ:

 1609

Ошибка.
Попробуйте повторить позже

Задача 5#79883

Найдите наименьшее натуральное число N > 9,  которое не делится на 7,  но если вместо любой его цифры поставить семёрку, то получится число, которое делится на 7.

Источники: ММО-2021, 11.3 второй день(см. mmo.mccme.ru)

Подсказки к задаче

Подсказка 1

Подумаем, какие цифры не могут входить в искомое число. А если ещё использовать и то условие, что наше число минимальное из возможных?

Подсказка 2

Теперь, когда понятно, какие цифры могут входить в искомое число, можно рассмотреть две соседние цифры. Если заменить k-ую или (k+1)-ую цифру на 7, то получатся кратные семи числа, но тогда и их разность будет кратна 7. Значит можно найти эту разность и попробовать связать между собой соседние цифры (по модулю 7).

Подсказка 3

Должно получиться, что 10*a_k и а_(k+1) сравнимы по модулю 7, где a_k и а_(k+1) — k-ая и (k+1)-ая цифры числа. Заметим также, что если отбросить последнюю цифру от искомого числа, получится число, кратное 7. Теперь, используя это, можно преобразовать искомое число без последней цифры (преобразования по модулю 7) и с помощью этого получить оценку на количество цифр в нашем числе.

Подсказка 4

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

Показать ответ и решение

Пусть наименьшее подходящее число имеет вид a-a-...a-.
 1 2   n  Из условия следует, что среди его цифр нет 0  и 7.  Если в числе есть цифры 8  или 9,  то их можно заменить на 1  или 2  соответственно и получить меньшее число с тем же свойством. Таким образом, искомое число состоит из цифр от 1  до 6.

Рассмотрим соседние цифры ak  и ak+1.  По условию числа с замененными семеркой цифрами ---------------
a1a2 ...7ak+1...an  и -------------
a1a2...ak7...an  делятся на 7,  следовательно, их разность также кратна 7,  то есть 10ak ≡ak+1 (mod 7)  для любого k.  Значит, запись числа может быть устроена только следующим образом: за 1  следует 3,  за 3  следует 2  (поскольку цифры 9  в числе нет) и так далее.

По условию исходное число, у которого вместо последней цифры стоит 7,  делится на 7.  Следовательно, исходное число без последней цифры делится на 7.  Используя несколько раз сравнение 10ak ≡ ak+1 (mod 7),  получаем:

a1a2...an−1-=a110n− 2+a210n− 3+a310n−4+...+an−1 ≡ 10a1⋅10n−3+ a210n−3+ a310n−4+

                n−3     n−4
+ ...+an−1 ≡ 2a2⋅10  +a310   +...+ an−1 ≡ ...≡ (n− 1)an−1 (mod 7)

Поскольку a
 n−1  не делится на 7,  заключаем, что n− 1  делится на 7,  поэтому наименьшее возможное n  равно 8.  Таким образом, наименьшее возможное число состоит не менее чем из восьми знаков. Остается заметить, что число 13264513  удовлетворяет условию задачи, а поскольку оно начинается с 1,  то это число и будет наименьшим.

Ответ:

 13264513

Ошибка.
Попробуйте повторить позже

Задача 6#92164

Верхней целой частью числа x  называют наименьшее целое число, большее или равное x  . Существует ли такое число A  , что для любого натурального n  расстояние от верхней целой части   n
A  до ближайшего квадрата натурального числа всегда равно 2 ?

Источники: ММО - 2021, первый день, 11.6 (см. mmo.mccme.ru)

Подсказки к задаче

Подсказка 1

Есть два возможных ответа — да или нет. Если нет, то нужно доказывать, что абсолютно для любого числа в последовательность {A^i} найдется не подходящее число, что кажется очень непростой задачей. Тогда будем доказывать, что ответ «да». Если мы хотим, чтобы верхняя целая часть Aⁿ отличалось от ближайшего натурального квадрата на 2, то хотелось бы понять, чему равна эта верхняя целая часть. Вернее, что нам было бы удобнее взять за верхнюю целую часть, чтобы она отличалась от какого-то квадрата на 2? А если вспомнить как возводится число вида t+1/t в квадрат?

Подсказка 2

Хотелось бы сделать так, чтобы число вида Aⁿ + 1/Aⁿ было бы целым и A было некоторым квадратом, чтобы как раз получить t^2n + 1/(t^2n) = (tⁿ + 1/tⁿ)²-2. Осталось только понять, чему должно быть равно t, чтобы каждое выражение вида Aⁿ + 1/Aⁿ при A = t², было бы целым. Здесь вас на поиск подходящего t может натолкнуть либо мысль о процессе построения бесконечных цепных дробей, либо же тот факт, что число вида (a+b√c)^k, где a, b, k - целые, это выражение вида t+l√c. Заметьте, это верно и для отрицательных k.

Подсказка 3

Да, можно просто сказать, что t — корень некоторого уравнения с целыми коэффициентами и отрицательным коэффициентом при x, ведь тогда t+1/t = c, где с — целая положительная константа. Тогда, по модулю факта про возведение таких иррациональностей в степень можно сказать, что задача решена, поскольку мы нашли такое t, что любое выражение вида t^k + 1/t^k — целое, а значит, мы нашли подходящее А.

Показать ответ и решение

Пусть t  — больший корень многочлена x2− 10x+ 1  , тогда t+ 1 =10
  t  .

Докажем по индукции, что число  n  1-
t + tn  целое при любом целом неотрицательном n  .

Действительно, это верно при n = 0,1  . Кроме того,

n+1   1    ( n  1 )(   1)  ( n−1   1  )
t  + tn+1 = t + tn-  t+ t  − t   + tn−1- ,

что позволяет проделать шаг индукции.

Положим A = t2  , тогда

         (      )2
An + 1-=  tn+ -1  − 2
     An       tn

-1-
An <1

Значит,  n  -1
A + An  и есть верхняя целая часть  n
A  , а ближайший к ней квадрат целого числа равен (n  -1)2
 t+ tn  .

Ответ: да

Ошибка.
Попробуйте повторить позже

Задача 7#73723

Пусть x  и y  — пятизначные числа, в десятичной записи которых использованы все десять цифр ровно по одному разу. Найдите наибольшее возможное значение x,  если    ∘    ∘        ∘  ∘
tgx − tgy = 1+ tgx tgy (  ∘
x обозначает угол в x  градусов).

Источники: ММО-2018, задача 11.3(см. mmo.mccme.ru)

Показать ответ и решение

Данное равенство при условии, что tgx∘ и tgy∘ определены, эквивалентно равенству tg(x − y)∘ = 1,  откуда x − y = 45+ 180n,  где n ∈ℤ.  Следовательно, разность x − y  делится нацело на 45,  а значит, на 5  и на 9.  Поскольку сумма всех цифр делится на 9,  то каждое из чисел x  и y  делится на 9.

Наибольшее пятизначное число, все цифры которого различны, равно 98765.  Ближайшее к нему меньшее число, делящееся на 9,  равно 98757  и содержит повторяющиеся цифры. Последовательно уменьшая это число на 9,  получаем числа 98748,98739,98730,98721.  Первые два из них также содержат повторяющиеся цифры. Третье состоит из различных цифр, но поскольку 98730= 90 +180⋅548,  то его тангенс не определён. Число x =98721  также состоит из различных цифр. Если взять, например, y =54036,  то получим x − y = 44685 =45+ 180⋅248,  поэтому число 98721  искомое.

Ответ:

 98721

Ошибка.
Попробуйте повторить позже

Задача 8#79882

Можно ли представить число 112018  в виде суммы кубов двух натуральных чисел?

Подсказки к задаче

Подсказка 1

Существует ряд модулей, по которым кубы натуральных чисел дают "приятные остатки". К их числу относиться, например, модуль 8 - куб натурального числа может давать только остатки 0,1,3, -3, -1 по данному модулю. А по какому модулю можно рассмотреть данное уравнение?

Подсказка 2

Ясно, что при этом нам придется рассматривать число 11^2018 по данному модулю, поэтому будет проще, если 11^2018 будет давать какой-то понятный остаток по рассматриваемому модулю (точнее остаток, который мы сможем найти, что не всегда бывает просто).

Подсказка 3

Давайте рассмотрим уравнение по модулю 9. Какие остатки могут давать кубы натуральных чисел по этому модулю?

Подсказка 4

Только остатки 0, 1 или -1. С чем в свою очередь сравнимо число 11^2018 по модулю 9?

Подсказка 5

Ясно, что 11^2018 сравнимо с 2^2018 по данному модулю. Осталось заметить, что 2^6=64 сравнимо с 1 по модулю 9. Вообще говоря, для каждого числа a существует число b такое, что a^b сравнимо с 1 по данному модулю. В некоторых задачах данное число b можно найти перебором, тем более в тех задачах, где в качестве основания рассматриваются 2, потому что ее первые степени считаются довольно быстро. Закончите решение, воспользовавшись этим сравнением.

Показать ответ и решение

С одной стороны, поскольку 26 = 64≡ 1 (mod 9)  и 2018 ≡2 (mod 6= φ(9)),  имеем

  2018   2018   2
11   ≡ 2   ≡ 2 = 4 (mod 9)

То есть число 112018  даёт остаток 4  при делении на 9.  С другой стороны, кубы натуральных чисел дают только остатки 0,1  и   8  при делении на 9.  Значит, сумма кубов двух натуральных чисел может дать лишь остатки 0,1,2,7  или 8  при делении на 9,  но не может дать 4.

Ответ:

Нет

Ошибка.
Попробуйте повторить позже

Задача 9#91095

Известно, что в десятичной записи числа 229  все цифры различны. Есть ли среди них цифра 0?

Подсказки к задаче

Подсказка 1

Разумно начать решать от обратного, предположить, что 0 там нет. Но как тогда искать противоречие? Вообще число очень большое и единственная информация, которую можно относительно просто узнать, это остатки при делении на некоторые числа.

Подсказка 2

Попробуйте определить количество цифр у числа, тогда сразу поймëте, какой остаток надо искать.

Показать ответ и решение

Заметим, что

   29  30       3     9
2⋅2  = 2 = (1024) <2 ⋅10

Следовательно, 229 < 109.  С другой стороны,

29   10 2 9     2          8
2 = (2 ) ⋅2  =1024 ⋅512> 5⋅10

Поэтому в записи числа 229  ровно девять цифр. Если среди них нет нуля, то сумма цифр в десятичной записи этого числа равна 1+ 2+ ...+ 9= 45.  Отсюда следует, что 229  делится на 3,  что не так. Противоречие.

Ответ:

да

Ошибка.
Попробуйте повторить позже

Задача 10#31222

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

Источники: ММО-2017, 9.1, автор - М.А. Евдокимов, (см. mmo.mccme.ru)

Подсказки к задаче

Подсказка 1

Попробуйте представить число так, чтобы оно имело вид суммы двух слагаемых, одно из которых-число после зачеркивания.

Подсказка 2

Да, мы представили n=a*10^(k-1)+m, где a-первая цифра, k-кол-во цифр. Но ведь тогда a*10^(k-1)=4m. Попробуйте оценить k, зная, что в числе нет одинаковых цифр.

Подсказка 3

Ура! Мы получили, что k<=4(так как иначе на конце будет две одинаковые цифры-нули). Остается перебрать варианты и выбрать максимальное число.

Показать ответ и решение

По условию aA-= 5A  (где A− число, составленное из всех цифр, кроме первой, a  — первая цифра). Пусть n  – количество цифр в числе ---
aA.  Отсюда

        n−1           n−3
4A =a ⋅10   ⇒ A = 25a ⋅10

Если n> 4,  то у числа A,  а значит, и у искомого числа, есть две совпадающие цифры (два нуля на конце). Если же n =4,  то

A = 250a

Ясно, что чем больше a,  тем больше исходное число. При a≥ 4  число 250a  состоит из 4  цифр, а не из трех. При a= 3  мы получаем A = 750,  а исходное число равно 3750.  Значит, наибольшее искомое число равно 3750.

Ответ:

 3750

Ошибка.
Попробуйте повторить позже

Задача 11#91098

Найдите все такие пары натуральных чисел a  и k,  что для всякого натурального n,  взаимно простого c a,  число akn+1 − 1  делится на n.

Подсказки к задаче

Подсказка 1

Понятно, что a=1 подходит. Пусть теперь a больше 1, попробуйте тогда подобрать какой-то пример для n, который сделает выполнение условия невозможным.

Подсказка 2

Показатель степени у а слишком сложный. Попробуйте подобрать такое n, чтобы внутри этой степени возник остаток 1.

Показать ответ и решение

Если a =1,  то akn+1− 1= 0,  а значит, делится на n.

Пусть a≥2.  Возьмём     k
n =a − 1,  тогда k
a ≡n 1,  и следовательно,

    kn+1       kkn−1
0≡n a    − 1≡n (a)  ⋅a− 1≡n a− 1

Если k> 1,  то в силу неравенства a >1  получаем неравенство        k
a− 1< a − 1 =n,  что противоречит a− 1≡n 0.

Если k= 1,  то  n
ak+1 − 1= a2− 1  должно делиться на все n,  что невозможно.

Таким образом, пары, в которых a≥ 2,  нам не подходят.

Ответ:

 a =1,k  - любое натуральное число.

Ошибка.
Попробуйте повторить позже

Задача 12#34908

Найдите наименьшее натуральное число, десятичная запись квадрата которого оканчивается на 2016.

Показать ответ и решение

Пусть это число n  . Тогда n2− 2016..10000
       .  . Отсюда n2 − 2016..2000
       .  и n2− 16= (n − 4)(n +4)..2000
                  .  . Тогда так как разница множителей равна 8, то ровно одно из них делится на 5 и поэтому оно делится сразу на  3
5  и оба множителя кратны 4 (так как если один не кратен, то и второй не кратен и тогда их произведение не может быть равно  4 3
2 ⋅5  ). Отсюда один из множителей делится на 500 =  2  3
2 ⋅5  . Значит, n = 500a± 4  . Давайте проверим эти числа

   2
496 = 246016

5042 = 254016

9962 = 992016

Итак, минимальное число равно 996.

Ответ: 996

Ошибка.
Попробуйте повторить позже

Задача 13#35425

Найдите наименьшее натуральное число, кратное 99, в десятичной записи которого участвуют только чётные цифры.

Показать ответ и решение

Обозначим через a  и b  сумму цифр, стоящих на чётных и нечётных местах соответственно. Из признаков делимости на 9 и на 11 следует, что a +b  кратно 9, а |a− b| кратно 11. Но все цифры чётные, поэтому a+ b  делится на 18, а |a − b| — на 22. Также заметим, что |a− b|≤ a+ b  . Если a +b= 18  , то |a − b|= 0  . Но из этого следует, что a= b= 9  , чего не может быть в силу чётности a  и b  . Если a+ b≥ 54  , то в нашем числе будет не менее 7 цифр, поскольку 8·6 = 48 < 54. Пусть a +b= 36  . Тогда |a − b|=22  или |a− b|= 0  . В первом случае одно из чисел a  и b  равно 29, а другое – 7, чего не может быть. Во втором случае a= b= 18  . Заметим, что 18 нельзя представить в виде суммы менее чем трёх чётных цифр, поэтому наше число хотя бы шестизначное. Осталось заметить, что наименьшее шестизначное число, удовлетворяющее условиям задачи, — это 228888. Действительно, первая цифра не может быть меньше 2, вторая — тоже, поскольку если она равна 0, то общая сумма цифр не больше 2+ 8⋅4< 36  .

Ответ: 228888

Ошибка.
Попробуйте повторить позже

Задача 14#91094

Будем называть натуральное число почти квадратом, если это либо точный квадрат, либо точный квадрат, умноженный на простое число. Могут ли 8  почти квадратов идти подряд?

Подсказки к задаче

Подсказка 1

Вам дано 8 последовательных чисел. Подумайте, почему именно 8, а не меньше.

Подсказка 2

Это сделано для того, чтобы они имели разные остатки при делении на 8. Рассмотрите числа 8k, 8k + 1, ..., 8k + 7 в контексте условия задачи.

Подсказка 3

Давайте посмотрим на число 8k + 2. Что вы видите? Конечно, оно делится на 2, но не делится на 4. А что это значит? А про другие числа что можно сказать?

Показать ответ и решение

Cреди восьми последовательных натуральных чисел найдутся числа, дающие остатки 2  и 6  при делении на 8.  Они делятся на 2,  но не делятся на 4,  так что они обязаны иметь вид   2
2k  и    2
2m .  Тогда  2    2
2k − 2m = 4,  то есть  2   2
k − m = 2,  что невозможно. Противоречие.

Ответ:

нет

Ошибка.
Попробуйте повторить позже

Задача 15#46233

Докажите, что для любого натурального n  найдётся натуральное число, десятичная запись квадрата которого начинается n  единицами, а заканчивается какой-то комбинацией из n  единиц и двоек.

Подсказки к задаче

Подсказка 1!

Воспользуйтесь индукцией! Попробуем построить такие числа по индукции. База простая, верно?

Подсказка 2!

Да! M1 = 1. Попробуем теперь по Mn построить число M(n+1). Для этого нужно рассмотреть все возможные такие числа.

Подсказка 3!

Давайте попробуем сделать так: Mn + k*10^n, чтобы условие выполнилось про единицы, рассмотрим все числа для k от 0 до 9. Осталось разобраться со вторым!

Показать ответ и решение

Положим m  =1
 1  и построим по индукции такие числа m
 n  , что десятичная запись m
 n  оканчивается на единицу, а десятичная запись числа  2
mn  оканчивается на комбинацию из n единиц и двоек.

Пусть число mn  уже построено, то есть выполнено предположение для n  . Рассмотрим числа вида             n
pk = mn +k⋅10  , где k ∈{0,1,2,...,9} . Десятичная запись каждого из них оканчивается на 1. Кроме того,

 2   2         n   2 2n
pk = mn +2kmn ⋅10 + k 10

Посмотрим на последние n+ 1  цифр десятичной записи каждого из слагаемых этой суммы.

Запись числа  2
mn  оканчивается на комбинацию из n  единиц и двоек по предположению индукции. Обозначим через a  n +1  -ю с конца цифру этого числа. Нетрудно видеть, что десятичная запись        n
2kmn⋅10  оканчивается на n  нулей, перед которыми идет последняя цифра числа 2k  (так как mn  оканчивается на единицу). Десятичная же запись слагаемого  2   2n
k ⋅10  оканчивается на 2n  нулей.

Имеем, что последние n  цифр десятичной записи чисел  2
pk  совпадают с последними n  цифрами десятичной записи числа  2
mn  . При этом n +1  -я с конца цифра числа  2
pk  совпадает с последней цифрой суммы a+ 2k  . Если a  нечётно, то для некоторого k  сумма a+ 2k  оканчивается на единицу (помним, что k∈ {0,...9} . Если a  чётно, то для некоторого k сумма a +2k  оканчивается на двойку. Следовательно, одно из чисел pk  можно взять в качестве числа mn+1  .

Итак, мы получили числа, которые заканчиваются на какую-то комбинацию из единиц и двоек. Более того, мы даже знаем, что последняя цифра всегда будет единицей.

Пусть cn =1◟..◝◜.1◞⋅104n
     n  и dn =cn+ 104n  . Тогда в силу                 √--
cn,dn < 105n =⇒    cn <103n  получаем

∘ --   --                 4n        4n
  dn− √ cn = √dn−-c√n-= √-10-√-> 210⋅103n > 1
            dn+  cn    dn+  cn

Следовательно, найдётся такое натуральное число qn  , которое не меньше √cn  , но меньше √dn-  . Тогда десятичная запись квадрата этого числа начинается на n  единиц.

Рассмотрим число qn ⋅10ℓ+ mn  , где ℓ  больше количества цифр в десятичных записях чисел 2pkmn  и m2n  . Тогда первые n  цифр десятичной записи числа

(q ⋅10ℓ+ m )2 = q2⋅102ℓ+ 2q10ℓ⋅m +m2
  n      n     n       n     n    n

совпадают с первыми n  цифрами десятичной записи числа q2n  , а последние n  цифр — с последними цифрами десятичной записи числа m2n  . Следовательно, число qn ⋅10ℓ+ mn  удовлетворяет условию задачи.

Ответ:

что и требовалось доказать

Ошибка.
Попробуйте повторить позже

Задача 16#91096

Натуральные числа от 1  до 2014  как-то разбили на пары, числа в каждой из пар сложили, а полученные 1007  сумм перемножили. Мог ли результат оказаться квадратом натурального числа?

Подсказки к задаче

Подсказка 1

Чтобы понять, стоит ли придумывать пример, или доказывать, что не мог, попробуйте придумать примеры для меньшего количества чисел.

Подсказка 2

Например, можно большинство чисел разбить на чётное количество пар равной суммой.

Показать ответ и решение

Разбив числа от 7  до 2014  на пары

7,2014,8,2013,...,1010,1011

получим чётное число пар с суммой 2021.  Числа от 1  до 6  можно разбить так: 1,5,2,4,3,6.  Для них в результате получим произведение 62 ⋅9 =182.  Значит, в итоге получится полный квадрат.

Ответ:

да

Ошибка.
Попробуйте повторить позже

Задача 17#91093

Ваня записал несколько простых чисел, использовав ровно по одному разу все цифры от 1  до 9.  Сумма этих простых чисел оказалась равной 225.  Можно ли, использовав ровно по одному разу те же цифры, записать несколько простых чисел так, чтобы их сумма оказалась меньше?

Подсказки к задаче

Подсказка 1

У вас есть конкретный набор цифр. Попробуйте понять, какие у вас могут быть простые числа, какие на них могут быть ограничения?

Подсказка 2

Давайте посмотрим, например, на цифру 4. Она явно не может быть на первом месте в простом числе. Подумайте в эту сторону и с остальными цифрами.

Показать ответ и решение

Например,

207 =2+ 3+ 5+ 41+67+ 89=

= 2+ 3+ 5+47+ 61+ 89 =2 +5+ 7+ 43+61+ 89
Ответ:

да

Ошибка.
Попробуйте повторить позже

Задача 18#92992

Что больше: 20112011+ 20092009  или 20112009 +20092011?

Подсказки к задаче

Подсказка 1

Неравенства a > b и a - b > 0 эквивалентны. Попробуем вместо сравнения исходных чисел сравнить их разность с нулем. Как можно преобразовать разность, чтобы было удобно ее оценивать?

Подсказка 2

Конечно! Перегруппируем слагаемые так, чтобы получилась разность двух скобок, внутри каждой у степеней одинаковое основание, а затем вынесем общий множитель. Как теперь сравнить числа?

Подсказка 3

Верно! Используем, что 2011 > 2009 и докажем, что в разности какое-то из чисел больше.

Показать ответ и решение

Запишем разность двух чисел, которые хотим сравнить, и преобразуем её:

   2011     2009      2011     2009
2011   + 2009   − (2009   + 2011   )=

     2011     2009      2011     2009
= 2011   − 2011   − (2009   − 2009   )=

= 20112009(20112− 1)− 20092009(20092− 1)

Заметим, что 20112009 > 20092009 >0  и 20112− 1 >20092− 1 >0.  Следовательно, уменьшаемое больше вычитаемого, то есть разность положительна. Значит, первое число больше, будет знак > .

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 19#73199

Найдите наименьшее натуральное n,  для которого число nn  не является делителем числа 2008!

Источники: ММО-2008, 11.2(см. mmo.mccme.ru)

Показать ответ и решение

Если n2 ≤2008,  то 2008!  делится на nn  (так как числа n,2n,...,(n − 1)n  и n2  содержатся среди чисел 1,2,...,2007,2008  ). Так как   2         2
44 < 2008 <45 ,  то достаточно проверить делимость 2008!  на n
n  при n >45.

Ясно, что 2008!  делится на   45   45  90
45  =5  ⋅3 ,  так как среди чисел 1,2,...,2007,2008  заведомо найдётся 45  чисел, кратных 5,  и  90  чисел, кратных 3  (5⋅45= 22< 2008  и 3⋅90= 270<2008  ).

2008!  делится на   46  46  46
46  = 2 23 ,  так как среди чисел 1,2,...,2007,2008  заведомо найдётся 46  чётных чисел и 46  чисел, кратных 23  (23⋅46= 1058< 2008  ).

2008!  не делится на  47
47  ,  так как число 47  простое, и поэтому среди чисел 1,2,...,2007,2008  есть лишь 42  числа, кратных 47  (47⋅42 =1974< 2008 <2021= 43 ⋅47  ).

Ответ:

 47

Ошибка.
Попробуйте повторить позже

Задача 20#38870

Чему может быть равно произведение нескольких различных простых чисел, если оно кратно каждому из них, уменьшенному на 1?  Найдите все возможные значения.

Подсказки к задаче

Подсказка 1!

1) Давайте попробуем восстанавливать наши множители с самого начала. Важное свойство почти всех простых чисел - нечетность. Значит перемножение будет делиться на двойку!

Подсказка 2!

2) Итак, поняли, что одно из простых чисел это 2. Попробуем понять, что тогда может быть следующим по возрастанию множителем в числе. Пусть это p2. Тогда раз наше число делится на p2-1, чему может быть равно p2?

Подсказка 3!

3) Верно, p2-1 может быть только двойкой, тогда p2 это 3! Теперь попробуйте таким же раскручиванием цепочки довести ее до конца, до момента, когда все множители, которые могут получиться, будут составными!

Показать ответ и решение

Хотя бы одно из простых чисел нечётно, потому число кратно двум. Пусть это N =p ⋅...⋅p ,p <p  ,i∈ {1,...k− 1},
    1     k i   i+1  где p =2.
1  Далее будем находить числа по порядку

Число содержит p2,  делителем p2− 1  может быть только 2,  поскольку остальные делители больше p2− 1,  откуда оно равно 2  и p2 = 3.  Подойдёт N = 6,  пойдём дальше.

Число содержит p3,  делителями p3− 1  могут быть только p1,p2,  но оба они меньше p3− 1,  потому p1⋅p2 = 6 ⇐⇒   p3 =7.  Подойдёт N =2 ⋅3 ⋅7 =42.

Число содержит p4,p4 − 1  может быть равно только p1p3 = 14,p1p2p3 = 42,  поскольку p1p2 <p3.  В первом случае 15= 14+ 1  составное, во втором p4 = 43  и подходит N = 2⋅3⋅7⋅43 =1806.

Пусть теперь число содержит p5,  отсюда p5 − 1  равно одному из чисел p1p4 =86,p1p2p4 = 258,p1p3p4 = 602,p1p2p3p4 = 1806,  где все числа, увеличенные на один, будут составными, откуда больше четырёх простых чисел быть не может.

Ответ:

 6,42,1806

Рулетка
Вы можете получить скидку в рулетке!