Тема Росатом

Теория чисел на Росатоме

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела росатом

Решаем задачи

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

Задача 1#119614

Для каждого натурального $n$ определим число $φ(n),$ равное количеству целых чисел $m,1 ≤m ≤ n$ взаимно простых с $n.$ Найти $φ(1947).$

Источники: Росатом - 2025, 11.3 (см. olymp.mephi.ru)

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

Подсказка 1

Заметим, что у 1947 в разложении на простые ровно 3 простых делителя. Давайте попробуем решить задачу в общем виде для чисел с 3 простыми делителями в некоторых степенях.

Подсказка 2

В данном случае будет проще посчитать, сколько всего чисел, не взаимно простых с n, и потом вычесть.

Подсказка 3

Как насчёт того, чтобы сначала отдельно посчитать количество чисел, делящихся на первый простой делитель, затем — на второй, третий, после — на первый и второй и так дальше.

Подсказка 4

А как теперь найти количество не взаимно простых, зная результаты вычислений из предыдущей подсказки? Нужно немного манипуляций с формулой включения-исключения.

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

Пусть $n =pr1⋅pr2 ⋅pr3, 1 2 3$ где $p,p ,p 1 2 3$ — различные простые числа, $r ,r ,r 1 2 3$ — их (натуральные) кратности. Количество чисел, не больших $n,$ делящихся на $p1 :$

r1−1 r2 r3 n1 = p1 ⋅p2 ⋅p3

Количество чисел, не больших $n,$ делящихся на $p : 2$

r1 r2−1 r3 n2 = p1 ⋅p2 ⋅p3

Количество чисел, не больших $n,$ делящихся на $p3 :$

r1 r2 r3−1 n3 = p1 ⋅p2 ⋅p3

Количество чисел, не больших $n,$ делящихся на $p1⋅p2 :$

n = pr1−1⋅pr2−1⋅pr3 4 1 2 3

Количество чисел, не больших $n,$ делящихся на $p1⋅p3 :$

n5 = pr11−1⋅pr22⋅pr33−1

Количество чисел, не больших $n,$ делящихся на $p2⋅p3$

n6 = pr11 ⋅pr22−1⋅pr33−1

И наконец, количество чисел, делящихся на $p1⋅p2⋅p3 :$

n7 = pr11−1 ⋅pr22−1⋅pr33−1

Общее количество чисел, не взаимно простых с $n,$ по формуле включений-исключений равно

n1+ n2+n3 − n4− n5− n6+n7 =pr11−1⋅pr22−1⋅pr33−1(p1⋅p2+ p1⋅p3+p2⋅p3− p1− p2− p3+ 1)

Тогда

φ(n)= n− n1− n2 − n3+ n4+ n5+n6 − n7 =

= pr1−1⋅pr2−1⋅pr3−1(p ⋅p ⋅p − p ⋅p − p ⋅p − p ⋅p +p + p +p − 1)= 1 2 3 1 2 3 1 2 1 3 2 3 1 2 3

= pr1−1⋅pr2−1⋅pr3−1(p1− 1)(p2− 1)(p3− 1) 1 2 3

Таким образом, при $n =1947= 3⋅11 ⋅59$ имеем

φ(1947)= (3− 1)(11− 1)(59− 1)= 1160

Ответ:

1160

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

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

Задача 2#83298

Найти сумму максимальных нечетных делителей каждого из целых чисел на отрезке $[61;120]$ .

Источники: Росатом - 2024, московский вариант, 11.3 (см. olymp.mephi.ru)

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

Подсказка 1

Интересно, что чисел от 61 до 120 ровно столько же, сколько нечётных от 1 до 120.

Подсказка 2

Чем нечётные отличаются от чётных? Наличием степени двойки. Тогда как удобно представить все числа?

Подсказка 3

Из первого замечания про количество нечётных хочется посмотреть, а сколько чисел вида n * 2ᴷ для каждого нечётного n (меньшего 120) лежит в промежутке от 61 до 120.

Подсказка 4

Оказывается, для каждого такого n одно своё n * 2ᴷ в промежутке от 61 до 120. Попробуйте понять, почему это так, и досчитать искомую сумму нечётных n!

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

Для каждого нечетного числа $n$ в промежутке 1 до 119 рассмотрим числа вида $n⋅2k$ , где $k∈ ℕ∪ {0}.$ Докажем, что для каждого $n$ найдётся ровно одно число вида $k n⋅2$ на промежутке от 61 до 120.

Пусть на нашем промежутке не нашлось нужного числа. Тогда должна найтись такая пара чисел $k k+1 (n⋅2 ;n ⋅2 )$ , что

k k+1 n⋅2 ≤ 60, n⋅2 ≥121,

что невозможно, поскольку из первого следует, что

k+1 n ⋅2 ≤ 120

Тогда из нашего утверждения следует, что для любого нечётного числа $n$ , меньшего 120, найдётся число от 61 до 120, что его наибольшим нечетным делителем будет $n$ . Причём для каждого $n$ такое число уникально. При этом нечётных чисел от 1 до 120 ровно 60, как и чисел от 61 до 120. Получается, что искомая сумма равна сумме всех нечётных чисел от 1 до 120.

1+-119- 1+3+ ...+ 119= 2 ⋅60= 3600

Ответ: 3600

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

Задача 3#83308

Натуральное число $n ≥2023$ имеет простой делитель $p >2$ и другой делитель $q,$ связанный с $p$ соотношением $(p− 1)(q+ 2)=n − 2$ . Найти наименьшее возможное при этих условиях число $n$ .

Источники: Росатом - 2024, региональный вариант, 11.3 (см. olymp.mephi.ru)

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

Подсказка 1

Давайте раскроем скобки, приведём подобные и посмотрим на выражения слева и справа. Что можно сказать про p и q, исходя из того, что они делители числа n? Ведь слева у нас выражение без свободного коэффициента, зависящее от p и q, а справа n.

Подсказка 2

Верно, можно сказать, что 2p кратно q и q кратно p. Как можно сделать оценки на p и q?

Подсказка 3

Можно сказать, что q = kp. Но тогда 2p кратно kp. Равенства быть не может по условию, остаётся только вариант 2p^2 = n. Отсюда понятно, как искать min n: нужно найти min p при 2p^2 ≥ 2023.

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

Раскроем скобки:

(p− 1)(q +2)= n− 2 =⇒ pq− q+ 2p − 2 =n − 2

pq− q+2p= n

Раз $p$ и $q$ — это делители $n,$ то выражение в левой части должно делиться на $p$ и $q.$ Следовательно, получаем

(|{ .. q. p |( 2p ... q

То есть $q = kp,$ тогда $2p ... kp,$ откуда следует, что $k =1$ или $k= 2.$ Но так как $q ⁄= p,$ подходит только $q = 2p.$ Подставим:

2 2p − 2p+ 2p= n

2p2 =n

Осталось перебрать чётные $n,$ которые является удвоенным квадратом простого числа. Перебирая $n ≥2023,$ получаем ответ $2⋅372 = 2738.$

Проверка:

(37− 1)(2 ⋅37+ 2)= 2⋅372− 2

(37− 1)(37+ 1)= 372− 1

Ответ: 2738

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

Задача 4#94430

Натуральное число $n ≥2024$ имеет простой делитель $p >3$ и другой делитель $q,$ связанный с $p$ соотношением

(p− 1)(q+ 3)= n− 3

Найти наименьшее возможное при эти этих условиях число $n.$

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

Раскроем скобки:

pq− q+3p= n

(1)

По условию, $p$ — делитель числа $n,$ поэтому из $(1)$ следует, что $q$ делится на $p.$ Следовательно, $q = kp,$ $q$ — делитель $n,$ поэтому из $(1)$ следует, что $3p$ делится на $q.$ Следовательно, $k =3⇒ q = 3p$ (случай не $k= 1$ подходит, так как $p ⁄=q).$ Тогда, следуя $(1),$ получаем, что $n =3p2.$ Теперь следует выбрать минимальное простое число $p,$ для которого $3p2 ≥ 2024.$ Таким простым числом является $p =29⇒ n = 2523.$

Ответ:

$2523$

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

Задача 5#76634

Длины рёбер $a ,a,a 1 2 3$ и $b,b ,b 1 2 3$ прямоугольных параллелепипедов $P A$ и $P B$ — целые числа. Если в параллелепипеде $P A$ увеличить на $1$ длину одного из рёбер $a1,a2$ или $a3,$ то отношение объёмов $VA :VB$ изменится на 3, на 5 или на 7 единиц соответственно. Найдите наименьшее возможное при этих условиях значение отношение объёмов $VA :VB.$

Источники: Росатом-2022, региональный вариант, 11.4 (см. olymp.mephi.ru)

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Отношение объемов = 3*(a1) = 5*(a2) = 7*(a3). Подумаем, как использовать целочисленность сторон. Получается, что пришли к уравнениям в целых числах?) вспомним, как решать! 3, 5 и 7 даны не зря...

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

Обозначим

a1⋅a2⋅a3 C =VA :VB = b1 ⋅b2⋅b3

Из условий получаем

(a1+b-1⋅)b⋅a⋅2b⋅a3-− a1b⋅⋅ab2⋅⋅ab3= 3= 1b-⋅a⋅2b⋅a⋅3b = 1a-⋅C ⇒ C = 3⋅a1 1 2 3 1 2 3 1 2 3 1

Аналогично $C =5 ⋅a2$ и $C =7 ⋅a3.$

В этом случае целое число $C$ делится на $3,5$ и $7.$ С учетом взаимной простоты этих чисел, $C =105k,k ∈ℤ$ и $C ≥ 105.$

Покажем, что $C = 105$ реализуется как отношение объемов некоторых $PA$ и $PB.$ Например, $a1 =35,a2 =21,a3 = 15,b1 = 3,b2 = 5,b3 = 7.$ Тогда

36⋅21-⋅15-− 35⋅21⋅15= -21⋅15 =3 3⋅5⋅7 3⋅5⋅7 3⋅5⋅7

Аналогично,

35⋅22-⋅15- 35⋅21⋅15- -35⋅15 3⋅5⋅7 − 3⋅5⋅7 = 3⋅5⋅7 =5

35⋅21-⋅16-− 35⋅21⋅15= -35⋅21 =7 3⋅5⋅7 3⋅5⋅7 3⋅5⋅7

Ответ: 105

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

Задача 6#44070

При каких целых числах $b$ и $c$ выражение $√4x2-+bx+-c$ целое при любых целых $x?$

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

Подсказка 1

Сперва прибегнем к идее, которая часто используется, когда под корнем есть квадратный трёхчлен: выделение полного квадрата. Возможно, это натолкнёт нас на какую-то идею...

Подсказка 2

После выделения полного квадрата под корнем к нему добавляется константа c - (b/4)². По условию корень должен быть целым числом для любого целого x. И тут возникает вопрос: а что будет при достаточно больших x? Не будет ли каких-то проблем с извлечением корня?

Подсказка 3

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

Подсказка 4

Это значит, что необходимо равенство добавки нулю. Тогда нетрудно понять, что для достаточности этого условия числу b достаточно быть кратным четвёрке. Попробуем доказать необходимость этого факта. В таких задачах часто помогает подстановка различных "хороших" значений х. Попробуйте поэкспериментировать!

Подсказка 5

Например, обязательно надо подставить x = 0. Тогда получаем, что c = k², k ∈ ℤ. А теперь можно использовать это соотношение и равенство добавки нулю!

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

Выделим полный квадрат под корнем:

∘--------- ∘ ------------(-)2- s= 4x2+ bx+c = (2x + b)2+ c− b 4 4

Легко понять, что условий $b= 4k,k ∈ℤ$ и $c− (b)2 = 0 4$ будет достаточно. Покажем, что они необходимы.

При $x= 0$ выражение $√c-$ должно быть целым, значит, необходимо $c= k2,k ∈ℤ.$

Если $s$ является целым числом, то целым является и $4s − 8x− b= 4⋅(s− (2x+ b)). 4$ Применим для выражения в скобках формулу $n2−m2 n − m = n+m$ и получим

2 b 2 b2 44√x-+bx+-c−-(2x+-4)b-= 4√-----c−-16-----b 4x2+ bx+ c+2x+ 4 4x2+ bx +c+ 2x+ 4

Но при достаточно больших $x$ правая часть становится по модулю меньше единицы. И при этом должна быть целой. Значит, должна быть равна нулю. Следовательно, $b2 2 2 c= 16 =⇒ b= 16k =⇒ b= 4k, где k∈ ℤ.$

Ответ:

при $b =4k,c= k2, k∈ℤ$

Курсы

Всё необходимое для достижения цели

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

Задача 7#44071

Найдите наибольшее значение выражения

(5n− 18)НОД-(n-+9,n+-2) F = НОК(n+ 9,n +2)

на множестве натуральных чисел. При каком $n$ оно достигается?

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

Подсказка 1

Числа n+2 и n+9 это же достаточно близкие числа, при этом их разность равна 7. Что тогда можно сказать про их НОД?

Подсказка 2

Да, их НОД либо равен 1, либо равен 7. Обозначим его за d. Какая замена тогда просится, если у нас есть НОК и НОД одних и тех же чисел?

Подсказка 3

Ну конечно, замена НОК(a,b)=ab/НОД(a,b). Тогда наше выражение принимает понятный вид. Осталось исследовать функцию, которая получается делением нашего выражения на d^2 и понять, где она принимает максимальное значение.

Подсказка 4

Да! В точке 12. А что еще принимает максимальное значение в точке 12? Поймите это и получите ответ!

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

Обозначим $d= НОД (n +9,n+ 2).$ Так как $n+ 9$ и $n+ 2$ делятся на $d,$ то их разность $(n +9)− (n +2)= 7$ делится на $d.$ Тогда $d =1$ или $d= 7.$

Как известно, $НОК(a,b)⋅НО Д(a,b)= a⋅b,$ откуда выражение из условия принимает вид

(5n− 18)⋅d2 F (n)= (n+-2)(n+-9)

Поскольку $d$ может принимать значения только двух констант: $1$ или $7,$ то нам достаточно будет максимизировать функцию

G (x)= ---5x-− 18-, x> 0 (x+ 2)(x+ 9)

Эта функция определена уже при всех действительных $x$ , потом учтём, что у нас было натуральное $n$ . Для максимизации посмотрим на её производную:

′ 5(x2+-11x+-18)−-(5x−-18)(2x+-11)- (x-− 12)(5x+-24) G(x)= (x +9)2(x+ 2)2 =− (x+ 2)2(x+9)2

Производная при $x> 0$ имеет ровно одну точку экстремума $x =12$ (это кстати натуральное число), которая является точкой максимума, потому является глобальным максимумом при $x> 0.$ А ещё удачным образом при $n= 12$ имеем $d =7$ — также принимает максимальное значение, потому при $n = 12$ достигает максимума и функция $F.$ Равен этот максимум

--5⋅12−-18-- F(12)= (12+9)(12+ 2) ⋅49= 7

Ответ:

$7$ при $n= 12$

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

Задача 8#61648

Сколько существует пар натуральных чисел $(a,b)$ , у которых $НО К(a,b)= 23 ⋅32⋅5⋅72 = 17640$ , а $НОД(a,b)= 12$ ? (пары неупорядоченные, то есть $(a,b)$ и ( $b,a)$ считайте одинаковыми)

Среди всех таких пар укажите ту, для которой $a +b$ принимает минимально возможное значение, и найдите это значение.

Источники: Росатом - 2021, 11.3, комплект 1 (см. olymp.mephi.ru)

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

Подсказка 1

Вспомним основную теорему арифметики - из нее следует, что НОК и НОД это взятие соответственно максимума и минимума по степеням простых множителей в наших двух числах. У наших чисел всего максимум 4 вида простых множителей -2,3,5,7. Попробуйте с этим знанием понять, какие степени этих множителей могут быть в наших числах.

Подсказка 2

Например, в 12 двойка входит во 2 степени, а в 17640 в 3. Тогда получаем min(степень 2 в первом числе, степень 2 во втором числе}= 2,max = 3. Попробуйте применить аналогичное рассуждение к остальным делителям и посчитать количество вариантов!

Подсказка 3

Подумаем о минимальной сумме: Мы знаем, что из основной теоремы арифметики следует, что a⋅b= НОК (a,b)⋅НОД(a,b)= 12⋅17640! Тогда мы знаем произведение чисел. Давайте попробуем понять, когда сумма двух чисел минимальна, если произведение фиксировано!

Подсказка 4

Это происходит, когда числа максимально близки друг к другу! Например, 4*5 = 20 = 10*2, то 4+5 < 2+10. Для того, чтобы строго это доказать, можем обратить к производной этого выражения. Осталось подобрать числа, которые будут максимально близки, при этом давать в произведении 12*17640! И проверку не забыть :)

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

Из основной теоремы арифметики следует, что $НО К$ и $НО Д$ двух чисел можно рассматривать как взятие соответственно максимума и минимума по степеням простых множителей в этих двух числах. Пусть $a2,a3,a5,a7$ — степени соответствующих простых в числе $a$ . Пусть $b2,b3,b5,b7$ — степени соответствующих простых в числе $b$ .

Поскольку $2 12= 2 ⋅3$ , то получаем $min{a2,b2}= 2,max{a2,b2}= 3$ , то есть для степеней двоек есть два случая $(a2,b2)= (2,3),(3,2)$ , которые мы считаем одним. Для степеней троек аналогично получаем $(a3,b3)= (1,2),(2,1)$ , для остальных действуем полностью аналогично. В итоге получается $4 2$ случаев. В условии написано, что пары $(a,b)$ неупорядоченные, т.е. $(a,b) =(b,a)$ , поэтому общее число пар должно быть уменьшено вдвое.

Для поиска наименьшей суммы приведём два способа:

Первый способ.

Из основной теоремы арифметики следует, что $a⋅b= НОК (a,b)⋅Н ОД(a,b)= 12⋅17640$ . По неравенству о средних при фиксированном произведении чисел их сумма тем больше, чем больше одно число отличается от другого (сумма вида $x+ 1764x0⋅12$ , производная которой равна $1− 1764x0⋅212$ возрастает при $√------- √---- x> 17640 ⋅12= 12 1470$ ). Поэтому нам нужно найти максимально близкое значение к корню из этого произведения. $12$ это общий НОД, так что остаётся составить из имеющихся множителей ближайшее к $√---- 1470≈ 38$ число.

a′ = 2⋅3⋅5= 30→ b′ =49→ a1+ b1 = 79→ a+ b= 12 ⋅79= 948

Второй способ.

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

2 1 0 0 3 2 1 2 22 ⋅31⋅50⋅72+23⋅32⋅51⋅70= 12 +17640 =17652 2 ⋅3 ⋅5 ⋅7 +2 ⋅3 ⋅5 ⋅7 = 588+ 360= 948 22 ⋅31⋅51⋅70+23⋅32⋅50⋅72 = 60 +3528= 3588 22 ⋅31⋅51⋅72+23⋅32⋅50⋅70 = 2940+ 72= 3012 22 ⋅32⋅50⋅70+23⋅31⋅51⋅72 = 36 +5880= 5916 22 ⋅32⋅50⋅72+23⋅31⋅51⋅70 = 1764+ 120 =1884 22 ⋅32⋅51⋅70+23⋅31⋅50⋅72 = 180+ 1176 =1356 22 ⋅32⋅51⋅72+23⋅31⋅50⋅70 = 8820+ 24= 8844

Осталось выбрать наименьшую сумму и выписать ответ.

Ответ:

$8$ пар, наименьшее значение суммы равно $948$

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

Задача 9#80500

Представить число 2021 в виде суммы трех взаимно простых чисел.

Источники: Росатом - 2021, 11.3, комплект 2 (см. olymp.mephi.ru)

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

Подсказка 1

Давайте попробуем идейно сконструировать, что мы вообще хотим. То есть, какая бы ситуация нас устраивала. А устраивала бы нас ситуация, если бы у нас было число x, потом число кратное х, мы бы вычли 1 из второго числа и получили бы искомую тройку. Осталось подобрать такой х.

Подсказка 2

Поскольку все знают разложение на простые номеров ближайших лет(одно из самых полезных знаний на любой олимпиаде), то всем известно, что 2021 = 43 * 47(не очень то сложный был год), а значит можно представить 2021 как сумму 43, 1 и 43 * 46 - 1 и это будет выполнять условие задачи.

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

2021 =43⋅47= 43+ 43 ⋅46= 43+ 1+ (43⋅46− 1)

Ответ:

$43+ 1+ (43⋅46− 1)$

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

Задача 10#44067

Найдите целые числа $x$ и $y$ , для которых

( x- y) -x y log2 17 + 5 = log217 +log2 5

Источники: Росатом-20, 11.1 (см. mephi.ru)

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

Подсказка 1

Учитывая ОДЗ, преобразуем логарифм суммы и напишем уравнение на x и y без логарифмов. Как решить получившееся уравнение и как оно выглядит?

Подсказка 2

5x + 17y = xy. Запишем как x(5-y) + 17y = 0 и попробуем разложить на множители для дальнейшего удобства)

Подсказка 3

(x-17)(y-5) = 17*5. Числа целые, поэтому можно делать выводы о значении скобок. У 85 маленькое количество делителей, поэтому остается лишь перебрать значения x-17 и y - 5!

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

Для того, чтобы правая часть была определена, получаем, что $x> 0,y >0.$ Тогда на ОДЗ уравнение эквивалентно

(-x y) xy log2 17 + 5 =log285 ⇐⇒ 5x+ 17y =xy

Попробуем разложить на множители: $x(5− y)+17y = 0 ⇐⇒ x(5− y)− 17(5− y)+ 17⋅5= 0 ⇐⇒ (x − 17)(y− 5)=17⋅5.$

С учётом того, что $y − 5> −5$ и $x − 17> −17,$ по основной теореме арифметики возможны только такие пары: $(y− 5,x − 17)∈{(1,85),(5,17),(17,5),(85,1)}.$ Соответственно $(x,y)∈ {(102,6),(34,10),(22,22),(18,90)}.$

Ответ:

$(102,6),(34,10),(22,22),(18,90)$

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

Задача 11#44068

Докажите, что существует набор натуральных чисел $a ,a,...,a , 1 2 2019$ для которых $2⋅НОК (a ,a,...,a )=a + a + ...+a . 1 2 2019 1 2 2019$

Источники: Росатом - 2020, 11.3 (см. olymp.mephi.ru)

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

Подсказка 1

Для каких чисел удобно находить НОК?

Подсказка 2

Для наборов, в которых много единичек!

Подсказка 3

Можно сделать все числа, кроме одного, сделать единицами. Попробуем из равенства подобрать оставшееся!

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

Возьмём

a1 = ...= a2018 = 1,a2019 =2018

Тогда

2⋅НОК(a1,a2,...,a2019)= 2⋅2018

a1+ a2+ ...+a2019 =2 ⋅2018

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

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

Задача 12#51001

Петя, Вася и Иван каждый на своей карточке написал наугад по одной цифре и передали карточки Маше так, чтобы она не видела написанных цифр. Маша случайным образом перемешала карточки и выложила их в ряд на стол. Найти вероятность того, что на столе можно увидеть трехзначное число, кратное $5$ и имеющее при делении на $7$ остаток $3.$

Источники: Росатом - 2020, 11.4 (см. olymp.mephi.ru)

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

Можно считать, что мы получаем на столе равновероятно любое число от $0$ (на трёх карточках могут быть нули) до $999$ . Тогда для вычисления вероятности нужно число благоприятных исходов поделить на число возможных исходов — на $1000.$

Первое решение.

Используя Китайскую теорему об остатках, получаем, что среди любых $35$ подряд идущих чисел нам подходит ровно одно с остатком $10$ по модулю $35$ . Первое такое трёхзначное число — $115$ , затем идут $150,185,...115+ 35 ⋅25= 990$ : всего чисел $26$ . Осталось поделить на $1000$ и получить ответ.

Второе решение.

По условию искомое трёхзначное число $x$ кратно $5$ и при делении на $7$ даёт остаток $3$ , то есть

x= 7n+ 3= 5n+ 5+(2n− 2),n∈ ℤ

С учётом этих условий получаем

2n− 2= 5k,k∈ ℤ =⇒ k= 2t,t∈ℤ =⇒ n= 5t+ 1 =⇒ x= 7(5t+ 1)+3 =35t+ 10

Осталось учесть условие на трёхзначность:

90 989- 100 ≤35t+ 10 <999 ⇐⇒ 2< 35 < 3≤ t≤ 28 < 35 <29

Подходят $28− 3+ 1= 26$ значений $t$ .

Ответ:

$0,026$

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

Задача 13#80503

Сколько существует натуральных чисел $n≤ 2020$ , для которых дробь

6n3-+n2−-5n+-12 6n2+7n +2

сократимая?

Источники: Росатом - 2020, 11.1 (см. olymp.mephi.ru)

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

Подсказка 1

Первое, что стоит сделать, когда хотим сократить дробь — выделить её целую часть! Поэтому попробуем поделить числитель на знаменатель и будем работать уже с новой дробью, у которой числитель является остатком от деления ;)

Подсказка 2

Итак, имеем новую дробь с числителем, равным 14. А на какие числа вообще может сокращаться такая дробь?

Подсказка 3

У числа 14 всего 3 делителя, больших 1, поэтому можно разобрать случаи НОДа числителя и знаменателя.

Подсказка 4

Если наибольший общий делитель равен 2, то можно сделать выводы о чётности n.

Подсказка 5

Если НОД равен 7, то какой остаток будет давать 6n²+1 при делении на 7? Что можно сказать про n?

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

Распишем числитель дроби следующим образом:

3 2 3 2 2 2 6n +n − 5n+ 12= 6n +7n + 2n− 7n − 2n+ n − 5n − 2 +2+ 12=

= n(6n2 +7n+ 2)− (6n2+ 7n +2)+ 14= (n − 1)(6n2+ 7n+ 2)+ 14

Выделим целую часть в дроби:

6n3+-n2− 5n-+12= (n−-1)(6n2+-7n-+2)+-14= n− 1+----14----- 6n2+ 7n+ 2 6n2+ 7n+ 2 6n2+7n+ 2

Если исходная дробь сократимая, то дробь $--14--- 6n2+7n+2$ так же сократимая, то есть числа $(6n2 +7n+ 2)$ и 14 имеют общий делитель, больший 1. При этом у 14 есть три натуральных делителя, больших 1: 2, 7, 14. Пусть $p$ — наибольший общий делитель 14 и $(6n2+7n+ 2).$ При этом, так как у 14 есть три натуральных делителя, больших 1: 2, 7, 14, — то у нас есть три варианта:

$1)p= 2.$ Заметим, что $2 6n + 2n$ — чётное при любом натуральном $n,$ а значит, чтобы все число $2 (6n + 7n +2)$ делилось на 2, $7n$ должно делиться на 2, откуда $n$ — чётное. Существует 1010 четных натуральных чисел, не превосходящих 2020.

$2)p= 7.$ Заметим, что $2 6n + 2$ должно делиться на 7, чтобы $2 (6n + 7n+ 2)$ делилось на 7, так как $7n$ делится на 7 при любом натуральном $n.$ Отсюда, $2 6n$ должно иметь остаток 5 при делении на 7. Посмотрим, при каких $n$ это возможно, рассмотрев все остатки по модулю 7. Для этого начертим таблицу, где слева будет число, а справа его остаток при делении на 7.


$n$	0	1	2	3	4	5	6

$n2$	0	1	4	2	2	4	1

$6n2$	0	6	3	5	5	3	6

Получается, если $n$ имеет остаток 3 или 4 при делении на 7, то $2 (6n +7n+ 2)$ делится на 7. Существует 145 нечётных натуральных чисел, не превосходящих 2020 и имеющих остаток 3 по модулю 7, и 144 нечётных натуральных числа, не превосходящих 2020 и имеющих остаток 4 по модулю 7.

$3)p= 14.$ Заметим, что $2 (6n +7n+ 2)= (3n+ 2)(2n+ 1).$ Если $(3n+ 2)$ делится на 14, то оно делится ещё и на 2, то есть $n$ — чётное, а все четные $n$ мы уже учли. А $(2n+ 1)$ на 14 делиться не может, так как это нечётное число. Получается, если $(3n+ 2)(2n+ 1)$ делится на 14, то $(3n +2)$ делится на 2, а $(2n+ 1)$ делится на 7, но это верно только при чётный $n,$ которые мы уже посчитали.

Итак, всего чисел, при которых исходная дробь сократима: $1010+ 144 +145= 1299.$

Ответ:

1299

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

Задача 14#102482

Представить число 2020 в виде суммы кубов пяти целых чисел. Доказать, что любое целое число можно представить в виде суммы кубов пяти целых чисел.

Источники: Росатом - 2020, 11.5 (см. olymp.mephi.ru)

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

Подсказка 1

Давайте попробуем найти явную формулу для разложения числа. Чтобы было удобно, можно попробовать выражать слагаемые через некоторое число n. Какие тогда можно сложить кубы, чтобы результат получится "красивым" (многое в сумме сократилось)?

Подсказка 2

Попробуйте сложить кубы чисел, которые по модулю отличаются друг от друга на не более, чем 2. Тогда, если аккуратно раскрыть результат по формулам сокращенного умножения, многое сократится.

Подсказка 3

Что получится, если сложить кубы чисел, по модулю равных (n+1) и n? Какой вывод из этого можно сделать и как быть с остальными числами?

Подсказка 4

Отлично, мы пришли к тому, что числа вида 6n можно выразить в виде суммы четырёх кубов! Осталось лишь аккуратно придумать, как "добрать" отстаток по модулю 6 у остальных чисел при помощи кубов и выразить 2020 по придуманным формулам!

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

Заметим, что для любого $n∈ Z$

3 3 3 3 (n+ 1) +(n− 1)+ (−n) +(−n) = 6n

т.е. любое целое число вида $a= 6n$ можно представить в виде суммы кубов четырех, а значит, с учетом нуля, и пяти целых чисел. Числа вида $a =6n± 1$ могут быть представлены в форме

3 3 3 3 3 a= (n +1) + (n − 1) +(−n) + (− n)+ (±1)

Числа вида $a= 6n +2 =6(n− 1)+8$ представляются суммой пяти кубов:

3 3 3 3 3 a =n + (n− 2) + (−n+ 1)+ (−n+ 1)+ 2

Для чисел вида $a= 6n− 2=6(n+ 1)− 8$ справедливо представление:

a= (n+ 2)3+ n3+ (− n− 1)3+ (− n− 1)3+ (− 2)3

Наконец, для $a= 6n+ 3= 6(n − 4)+ 27$ справедливо представление:

a= (n − 3)3+(n− 5)3+(−n +4)3+(−n +4)3+(3)3

Представление числа $a= 2020 =337⋅6− 2$ может быть получено по формуле (3) для $n= 337$ :

2020= (339)3+ 3373 +(−338)3+ (−338)3+ (− 2)3

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

Задача 15#92083

Известно, что дробь $m(n+-69m) n(m +69n)$ сократимая для некоторых взаимно простых целых чисел $m$ и $n$ . Найти наибольшее простое число $d$ , на которое делится числитель и знаменатель дроби.

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

Рассмотрим три случая

Если $m$ делится на $d$ , и $m+ 69n$ делится на $d$ , то и их разность делится на $d$ , поэтому $69n$ делится на $d$ , но $n$ взаимно просто с $m$ , следовательно и с $d$ . Откуда $69 =3 ⋅23$ делится на $d$ , значит, $d≤ 23$ .

Случай: $n$ делится на $d$ , и $n+ 69m$ делится на $d$ разбирается аналогично.

Если же $n +69m$ и $m + 69n$ делятся на $d$ , то и число $( 2 ) 69(n+ 69m)− (m + 69n)= m 69 − 1$ делится на $d$ .

Случай, когда $m$ делится на $d$ был рассмотрен выше. Значит, можно считать, что $2 3 69 − 1= 68⋅70 =17⋅2 ⋅5⋅7$ делится на $d$ , откуда в этом случае $d≤ 17 <23$ .

Осталось привести пример на $d =23$ . Подходят $m =23,n= 1$ .

Ответ: 23

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

Задача 16#82710

Найдите натуральное число, делящееся на 225 и имеющее 15 различных делителей.

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

Заметим, что $225 =32⋅52.$ Пусть $n$ — число, которое мы ищем. Тогда $n =32+k⋅52+t⋅s,$ где $k$ и $t$ — неотрицательные целые числа, а $s$ — натуральное, не делящееся на $3$ и $5$ .

Пусть $r$ — число делителей $s,$ Заметим, что число $n$ имеет $(2+ k+ 1)(2+ t+1)r$ делителей. Так как всего делителей у нас $15,$ то получаем уравнение

(3+ k)(3+ t)r= 15

Так как $3+ k≥ 3$ и $3+t≥ 3,$ а также $15 =3⋅5,$ то либо $k= 0$ и $t= 2,$ либо $k= 2$ и $t =0.$ Таким образом, $n = 32⋅54$ или $4 2 n =3 ⋅5 .$

Ответ:

$n =32⋅54$ или $n= 34⋅52.$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

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

Задача 17#46229

Целые числа $2a2$ и $3a$ имеют одинаковые остатки при делении на $18$ . Какие ненулевые остатки может иметь число $a> 0$ при делении на $18$ ?

Источники: Росатом-17, 11.3 (см. rsr-olymp.ru)

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

Подсказка 1!

Попробуем рассмотреть некоторый модуль, например, 3! Посмотрите, чему равны остатки наших чисел по модулю три.

Подсказка 2!

Да, 0! У 3а точно ноль, а так как его остаток при делении на 18 тоже делится на 3, то и у 2а^2 тоже!

Подсказка 3!

Вспомните, что если число делится на 3, то его квадрат - делится на 9!

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

По условию $2a2− 3a$ делится на $18$ , значит, и на $3$ . Так как $3a$ делится на $3$ , то и $2a2$ делится на $3$ . Так как $2$ и $3$ взаимнопросты, то $2 a$ делится на $3$ , значит, и на $9$ , причём $a$ делится на $3$ .

По условию $2 2a − 3a$ делится на $18$ , значит, и на $2$ . Так как $2 2a$ делится на $2$ , то и $3a$ делится на $2$ . Так как $3$ и $2$ взаимнопросты, то $a$ делится на $2$ .

В итоге $a$ должно делиться на $6$ . Ненулевые остатки по модулю $18$ могут быть только $6$ или $12$ .

Если $a ≡186$ , то $2 2a ≡18 0 ≡183a.$

Если $a ≡1812 ≡18−6$ , то аналогично.

Ответ:

$6$ и $12$

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

Задача 18#46231

Целые, положительные, шестизначные числа $a 1$ и $a 2$ такие, что если к сумме цифр числа $a 1$ прибавить сумму цифр числа $a 2$ , то получится $36.$ Найти наибольшее возможное при этих условиях значение $a1 ⋅a2$ .

Источники: Росатом-17, 11.3 (см. rsr-olymp.ru)

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

Подсказка 1!

Сумма 36 - не так уж много! Давайте попробуем понять, какая максимальная сумма у наших чисел! Каждое из них не больше 990000...

Подсказка 2!

Осталось оценить произведение и не забыть, что нужен пример!

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

Посмотрим сначала на сумму этих чисел. Заметим, что она не превосходит $990000+ 990000= 18 ⋅100000 +18⋅10000$ . Действительно, каждая цифра отвечает за то, сколько раз нам взять число $k 10,k∈ {0,...5}$ . Каждая цифра не больше $9$ , потому сумму больше мы получить просто не можем — выгоднее всего брать максимальные степени $10$ , что мы и сделали.

Итак, мы знаем, что $2 a1+ a2 ≤ 2⋅990000 =⇒ a1⋅a2 ≤ 990000$ (по неравенству о средних максимум произведения при фиксированной сумме достигается при равенстве чисел). То есть наша оценка достигается при $a1 = a2 =990000$ , что удовлетворяет условию.

Ответ:

$9900002$

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

Задача 19#80455

Для каждой пары целых положительных чисел $(m,n)$ , связанных соотношением

3m + 2n = 19,

найти решение $x$ уравнения

rnx x 2 + rm ⋅2 − 8 =0,

где $rk$ — остаток от деления $k$ на $3.$

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

Заметим, что $2n≡ 19 ≡4 3 3$ . Отсюда следует, что $n ≡2 3$ и отсюда $r = 2 n$ . Тогда можно представить $n$ как $3t+ 2$ и тогда $m = 5− 2t≡3 t− 1$ и такое число может давать любой остаток при делении на 3. Значит, нам нужно решить уравнение

x x 4 + rm2 − 8 =0

Давайте заменим $2x$ на $y$ . Получим

y2+ r y− 8= 0 m

Если $t=0$ , то $rm = 2$ и у уравнения $y2+ 2y− 8$ есть 1 положительный корень $y = 2= 2x =⇒ x =1$ .

Если $t=1$ , то $rm = 0$ от уравнения $y2 =8$ получаем $x =1,5.$

Если $t=2$ , то $rm = 1$ и от уравнения $y2+ 2y − 8$ получаем $x =log2(√33− 1)− 1.$

Ответ:

$1$ при $m = 5,n= 2$

$1,5$ при $m = 3,n= 5$

$√ -- log2( 33 − 1)− 1$ при $m = 1,n = 8$

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

Задача 20#44069

Сколько пар $(x;y)$ целых чисел, являющихся решениями уравнения $7x − 5y = 23,$ удовлетворяют неравенству $x2+ y2 ≤37?$ Найти пару $(x;y),$ для которой $x+ y$ наибольшее.

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

Подсказка 1

Попробуйте сделать оценку на модули x и y, а так же запишем 7x - 5y = 23 как x = (23+5y) / 7. Что можно сказать об y?

Подсказка 2

y = -6 или y = 1! Проделайте аналогичные действия с x, тогда несложно будет найти наибольшее значение x+y.

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

Легко видеть, что $|x|≤ 6,|y|≤6.$ При $y ∈ [−6,6]$ выражение $23+ 5y$ кратно семи только при $y ∈ {− 6,1}.$ Для $x$ имеем соответственно ${−1,4}.$ Наибольшее значение $x+ y$ равно $5.$

Ответ:

$2$ пары, наибольшую сумму имеет пара $(4,1)$