Тема Высшая проба

Теория чисел на Высшей пробе

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

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

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

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

Подтемы раздела высшая проба

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

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

Задача 1#80738

Можно ли число 2024 представить в виде $a5+b3$ , где $a$ и $b$ — натуральные числа?

Источники: Высшая проба - 2024, 11.1 (см. olymp.hse.ru)

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

Подсказка 1

Если a ≥ 5, то левая часть уже слишком большая. Остаётся перебрать четыре значения для а и проверить, чему равно b

Подсказка 2

Должен найтись подходящий вариант!

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

3 10 5 3 2024 =1000+ 1024= 10 +2 = 4 +10

Ответ: да

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

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

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

Задача 2#80739

В некотором числе 10 единиц, 100 двоек, 1000 троек, …, $109$ девяток, расположенных в некотором порядке. Каждую секунду в нём стирают последнюю цифру. Правда ли, что в какой-то момент после начального получится число, делящееся на 9?

Источники: Высшая проба - 2024, 11.2 (см. olymp.hse.ru)

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

Подсказка 1

Давайте подумаем, каким образом нам можно число, которое кратно 9, независимо от остатка, который будет нами получен на каждом этапе вычеркивания. Удобная конструкция для нас - чтобы в течение 9 шагов у нас постоянно менялся остаток и не повторялся. Тогда, за 9 шагов у нас точно будет момент, когда остаток равнялся 0. Попробуйте придумать такую конструкцию.

Подсказка 2

Давайте попробуем вычеркнуть все 9 из числа(действительно, к чему бы они, если на деление на 9 они никак не влияют). Значит, если докажем, что в какой-то момент было число кратное 9 у полученного числа, то и у начального оно тоже было. Также, заметим, что под нашу конструкцию из первой подсказки подходит вариант, когда у нас стоит много одинаковых цифр подряд(хотя бы 9), взаимнопростых с 9, ведь там будет постоянно меняться остаток. То есть, нам надо набрать много одинаковых цифр подряд. Как это можно сделать?

Подсказка 3

Заметим, что чисел 8 у нас очень много. Больше чем 9 раз суммарно всех остальных. Давайте разобьем наше число на блоки по 9 цифр, которые не пересекаются. Что можно сказать про эти блоки? А что тогда надо доказывать в условиях на восьмерку?

Подсказка 4

Остается доказать, что найдется блок из цифр, равных 8. И это правда, так как иначе, в каждом блоке есть цифра, которая не 8 и тогда, цифр, не равных 8, у нас хотя бы 1/9 от общего количества. Противоречие. Значит, есть блок восьмерок. Победа.

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

Заметим, что если для исходного числа существует такой момент, то и для числа $A$ , полученного вычеркиванием всех девяток из исходного, он так же существует, поскольку каждое вычеркивание не меняет остаток при делении суммы цифр на 9.

Рассмотрим число $A$ . В силу неравенства $8 7 10 > 9⋅(10 + ...+ 10)$ , отношение количества восьмерок к оставшимся числам, больше 9. Отметим подряд идущие блоки по 9 чисел. Докажем, что существует блок, элементами которого являются лишь восьмерки. Пусть это не так, тогда в каждом блоке есть цифра отличная от восьмерки, следовательно, количество цифр, не являющихся восьмерками, хотя бы $1∕9$ от общего количество, что противоречит полученному неравенству.

Рассмотрим блок, состоящий только из восьмерок. Пусть число, полученное из $A$ вычеркиванием всех цифр до найденного блока, имеет остаток $s <9$ при делении на 9. Каждое вычеркивание 8 увеличивает остаток при делении на 9 на 1, следовательно, вычеркнув $9− s$ элементов в блоке, мы получим искомое число.

Ответ: да

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

Задача 3#67768

Натуральные числа $a,b,c$ таковы, что $1≤ a< b< c≤ 3000.$ Найдите наибольшее возможное значение величины

НОД(a,b)+ НОД (b,c)+ НОД (c,a)

Источники: Высшая проба - 2023, 11.3 (см. olymp.hse.ru)

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

Подсказка 1

Хочется получить какую-то оценку на эти НОДы. Понятно, что НОД(а,b) не больше чем a. Может попробовать что-то поделать с такой оценкой?

Подсказка 2

Если оценить так каждый НОД, получается как-то слишком грубо. Какой алгоритм приходит в голову, когда речь идёт о НОДах? Конечно же, алгоритм Евклида! Может, как-то улучшить оценку для НОД(a,b) с помощью него?

Подсказка 3

Если воспользоваться алгоритмом Евклида получиться, что: НОД(a,b)=НОД(a,b-a). Тогда т.к. НОД(a,b-a) не больше чем b-a, то и НОД(a,b) будет не больше чем b-a. если сделать тоже самое с НОД(b,c), что получится?

Подсказка 4

Итак, мы имеем что НОД(a,b) не больше b-a, а НОД(b,c) не больше c-b. Если их сложить, получится, что их сумма не больше чем (b-a)+(c-b)=с-а. Если оценить, что НОД(а,с) не больше чем a, то окончательно сумма всех НОДов будет не больше с, которое не больше 3000. Осталось только придумать пример...

Подсказка 5

Понятно, что с=3000. Чтобы достигалась оценка, необходимо, чтобы НОД(a,c)=a. Тогда с делится на a. Если мы сделаем так, что b тоже поделится на a, то, возможно, придумаем пример

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

Воспользуемся алгоритмом Евклида для $Н ОД(a,b),$ получим

НОД(a,b)= НО Д(a,b− a)

Заметим, что, так как НОД двух натуральных чисел не превосходит каждое из них,

НОД (a,b− a)≤ b− a⇒ НО Д(a,b)≤b − a

Аналогично получаем, что

НО Д(b,c)≤c− b

А также

Н ОД(c,a)≤ a

Складывая эти три неравенства, получаем

Н ОД(a,b)+ НОД(b,c)+ НОД(c,a)≤ (b− a)+ (c− b)+a = c≤3000

В качестве примера на $3000$ можно предъявить, например, $a= 1000,b= 2000,c= 3000.$ В этом случае

НО Д(a,b)+Н ОД(b,c)+Н ОД(c,a)= 1000+ 1000 +1000= 3000

Ответ: 3000

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

Задача 4#92985

Найдите все натуральные числа $a,b,c,d$ такие, что выполнены равенства $a +b= cd,c+ d= ab.$

Источники: Высшая проба - 2021, 11

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

Подсказка 1

Вот если бы было равенство a + b = ab, вы бы его сразу записали в виде 1 = (a - 1)(b - 1) и быстро с ним разобрались. Подумайте, как это применить к этой задаче.

Подсказка 2

Конечно, уравнения надо сложить! Ведь тогда мы получим равенство (ab - a - b) + (dc - d - c) = 0.

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

Если сложить равенства и к полученному прибавить $2,$ то мы получим равенство $(ab− a− b+1)+ (cd− c− d+ 1)= 2.$ Или же $(a− 1)(b− 1)+ (c− 1)(d− 1)= 2.$ То есть сумма двух целых неотрицательных равна $2,$ а значит либо одно $0,$ второе $2,$ либо оба равны $1.$ Осталось перебрать и написать ответ.

Ответ:

$(2,2,2,2),(1,5,2,3),(5,1,2,3),(5,1,3,2),(1,5,3,2),(2,3,1,5),(2,3,5,1),(3,2,5,1),(3,2,1,5)$

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

Задача 5#61459

Имеется дробь $1 n$ . Семиклассник Семёнов каждую минуту прибавляет к её числителю и знаменателю по $1$ и смотрит, можно ли сократить полученную дробь. Семёнов утверждает, что первый раз сократимая дробь получилась после $1000$ шагов. Стоит ли ему верить?

Источники: Высшая проба - 2020, 7.3 (см. olymp.hse.ru)

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

Подсказка 1

Давайте сначала поверим юному математику и посмотрим на дробь через 1000 минут. Какой вывод можно тогда сделать о делимости её знаменателя?

Подсказка 2

Верно, знаменатель кратен какому-то из простых делителей числа 1001. Пусть этот делитель равен p. Если бы мы хотели опровергнуть слова семиклассника, то скорее всего слова о том, что дробь сократилась впервые, верно?

Подсказка 3

Нужно найти такое число, которое выражается через слагаемые n и p и при этом делится на p. Хороша идея взглянуть на знаменатель дроби.

Подсказка 4

Мы обнаружили число n + p - 1, которое делится на р. Это как будто знаменатель дроби через р-1 минуту. А что с её числителем? Найдём противоречие, которое искали в подсказке 2?

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

Предположим, что Семёнов сказал правду, то есть в первый раз числитель и знаменатель $1+k n+k$ имеют общий делитель больше единицы через $k= 1000$ минут.

Получится $-1001- 7⋅11⋅13 n+1000 = n+1000$ , откуда $n +1000$ делится на какое-то число из множества ${7,11,13},$ давайте это число обозначим буквой $p.$

Заметим, что $1001$ делится на $p$ (если непонятно, то посмотрите, что такое $p$ ). Тогда $p+ (n+ 1000)− 1001= n+ p− 1$ тоже делится на $p$ .

Но отсюда сразу следует, что дробь уже через $p− 1$ шагов сократима: $1+p−1- --p-- n−1+p = n+p−1$ . А Семёнов сказал, что первый раз дробь сократима будет через $1000$ шагов. Но $p− 1 <1000$ . Семёнов, ты не прав!

Ответ:

нет

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

Задача 6#89083

В последовательности чисел Фибоначчи $1,1,2,3,5,8,13,21,...$ каждое следующее число, начиная с третьего, равно сумме двух предыдущих. Докажите, что среди чисел Фибоначчи нет ни одной натуральной степени числа $7.$

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

Подсказка 1

Какое первое число в последовательности чисел Фибоначчи кратно 7? Чему равен его индекс?

Подсказка 2

Первое число Фибоначчи, кратное 7 - это 21, которое является 8 числом Фибоначчи. Продолжив выписывать элементы данной последовательности можно заметить, что первые несколько членов, индексы которых кратны 8, делятся на 7. Докажите, что на 7 делятся те и только те члены последовательности чисел Фибоначчи, индексы которых кратны 8. Как можно доказать, что никакое из данных чисел не является степенью 7?

Подсказка 3

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

Подсказка 4

Да, достаточно показать, что на 3 делятся те и только те числа Фибоначчи, номер которых делится на 4.

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

Для начала докажем, что на $7$ делятся те и только те числа Фибоначчи, номер которых делится на $8.$ Докажем это по индукции. База: Первое число Фибоначчи, кратное $7$ — это $21,$ которое является $8$ числом Фибоначчи.

Переход: Пусть этот факт был верен для всех чисел Фибоначчи с номерами от $1$ до $8k.$ Докажем, что он верен для чисел от $8k+1$ до $8k+ 8.$ Пусть число с номером $8k − 1$ имело остаток $a$ от деления на $7(a ⁄=0).$ Тогда числа с номерами $8k +1,...,8k +8$ будут иметь следующие остатки: $a,a,2a,3a,5a,a,6a,0.$

Теперь докажем, что на $3$ делятся те и только те числа Фибоначчи, номер которых делится на $4.$ Доказательство аналогично.

Следовательно, если число Фибоначчи делится на $7,$ то его номер делится на $8.$ Значит его номер делится на $4,$ а значит, само число обязано делиться на $3.$ Значит оно не может быть равно натуральной степени числа $7.$

Курсы

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

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

Задача 7#80965

Найдите все натуральные числа, у которых разность между суммой двух самых больших собственных делителей и суммой двух самых маленьких собственных делителей является простым числом. (Делитель натурального числа называется собственным, если он отличен от $1$ и самого этого числа.)

Источники: Высшая проба - 2019, 9.5(см. olymp.hse.ru)

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

Подсказка 1

Ну, во-первых, нужно обрести понимание о том, как устроены наименьшие собственные делители. Для этого вспомним, что по Основной Th. Арифметики n = p₁^a₁*p₂^a₂*...*p_k^a_k (p₁ < ... < p_k) для любого натурального n. Тогда какой наименьший собственный делитель?

Подсказка 2

Верно! Это p₁. Что насчёт следующего по величине собственного наименьшего делителя?

Подсказка 3

Очевидно, что это не p₃, p₄ и т.д. Значит это что-то связанное с p₂ или p₁, причём очевидно, что степень тоже не больше 2. Итого?

Подсказка 4

Верно, либо p₁^2, либо p₂. Пусть эти два наим. делителя это a и b. Что тогда можно сказать про наибольшие собственные делители?

Подсказка 5

Так точно! Это n/a и n/b. Теперь стоит рассмотреть случаи.

Подсказка 6

1-ый случай. a = p₁, b = p₂ - простые. Тогда p = (n/a + n/b) - a - b, где p - простое. То есть pab = (n - ab)(a+b). Посмотрим на делимость, не забывая о том, что a, b, p - простые.

Подсказка 7

Проделайте это сами и поймите, что p = (p₁+p₂). Отсюда в силу чётности и простоты: p₁ = 2, n = 4p₂. Отсюда найдите ответ. Попробуйте разобрать второй случай самостоятельно.

Подсказка 8

2 случай. a = p₁, b = p₁^2. Тогда аналогично получаем, что p₁^2*p = (p₁ + 1)(n - p₁^3). Теперь осталось немного.

Подсказка 9

Воспользуйтесь взаимной простотой p₁ и p₁ + 1 и решите задачу) Успехов!

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

Имеет место один из двух случаев.
(a) Пусть оба наименьших делителя $p$ и $q$ — простые числа. Тогда простым будет число $n n r= (p + q)− (p+ q),$ откуда $pqr= (p +q)(n − pq).$ Поскольку числа $p+q$ и $pq$ взаимно просты, то $r =p +q,$ откуда $p= 2$ и $n = 4q.$ Но тогда в силу выбора $q$ получаем $q = 3$ и $n= 12.$
(b) Пусть наименьшие делители имеют вид $p$ и $2 p ,$ где $p$ простое. Тогда простым будет число $n n- 2 r= (p + p2)− (p+ p),$ откуда $2 3 p r= (p +1)(n − p ).$ Поскольку числа $p$ и $p+1$ взаимно просты, то $r= p+ 1.$ Это возможно только в случае $p= 2,r =3.$ В этом случае $2 3 p =n − p ,$ откуда $n= 12.$ Но этот случай невозможен, так как у $12$ один из двух наименьших делителей это $3.$

Ответ:

$12$

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

Задача 8#77850

Чётное число $2N > 2$ называется подходящим, если оно делится на модуль разницы между наибольшим из своих чётных делителей, отличных от $2N$ , и наибольшим из своих нечётных делителей. Сколько существует подходящих чётных чисел, не превосходящих $2018?$

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

Подсказка 1

Попробуем записать число в виде 2^k*m, где m - нечетно. Запишем условие и подумаем, какие ограничения можно наложить на переменные!

Подсказка 2

2^k*m должно делиться на m(2^(k-1) - 1). При каких k это возможно? Обратим внимание не четность.

Подсказка 3

При k >= 2 решение только 1 (какое?) А что если k =1? Как нам выделить наибольший четный делитель?

Подсказка 4

Запишем m как p*s, где p - минимальный простой нечетный делитель. Теперь мы можем записать условие с помощью новых переменных и найти p!

Подсказка 5

Число p обязательно равно трём! Получается, что 2N = 2*3*s. Теперь попробуем поискать такие числа среди чисел от 1 до 2018...

Подсказка 6

Обратите внимание на остатки от деления числа 2N на 4 и 6. Тогда все числа от 1 до 2018 можно разбить на последовательности, в которых мы точно знаем количество подходящих чисел!

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

Предположим, что число $2N$ подходящее. Пусть $2N = 2km,$ где $m$ нечётное. Если $k≥ 2,$ то условие говорит, что $k 2 m$ делится на $k−1 k−1 2 m − m= m (2 − 1),$ что возможно только при условии $k= 2.$ Если $k= 1$ и $m =ps,$ где $p$ минимальный простой нечетный делитель $m,$ то $2ps$ делится на $2s− ps= (2− p)s,$ откуда имеем $. p.. (p− 2),$ значит, $p =3.$ Число $N$ или имеет остаток $2$ по модулю $4$ или имеет остаток $3$ по модулю $6.$ Тем самым число $2N$ является подходящим, если число $N$ может иметь остаток $2, 3, 6, 9, 10$ по модулю $12.$ Это значит, что в каждом ряду из $12$ последовательных четных чисел ровно пять подходящих. Используя равенство $2018= 2⋅(12⋅84+ 1),$ получаем ответ $420= 5⋅84.$

Ответ: 420

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

Задача 9#61644

Найдите все натуральные числа $n$ от $1$ до $100$ включительно такие, что если перемножить все делители числа $n$ (включая $1$ и $n$ ), получим число $3 n .$

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

Подсказка 1

Хочется как-то в общем виде записать, чему равно произведение всех делителей. Мы знаем, что в большинстве случаев делители можно разбить на пары (потому что если у числа n есть делитель k, то есть также делитель n/k), но у некоторых чисел есть лишь нечетное количество делителей. Что это за числа?

Подсказка 2

Если число является точным квадратом, то оно имеет нечётное число делителей! Подойдёт ли нам какой-то из точных квадратов?

Подсказка 3

Пусть у точного квадрата n кроме делителя √n есть еще s пар делителей. Заметим, что произведение делителей в каждой паре равно n, тогда произведение всех делителей равно n^(s+1/2) = n³, а это верно только при n = 1.

Подсказка 4

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

Подсказка 5

Так как n^s = n³, у нашего числа есть всего 6 делителей! Давайте попробуем понять, сколько простых чисел может быть делителями числа n, может ли у n быть больше двух простых делителей?

Подсказка 6

Нет, у n есть максимум два простых делителя! Ведь если бы n делилось на р₁, р₂ и р₃, то у него были бы делители р₁р₂, р₁р₃ и р₂р₃, а так как делителей всего шесть, среди этих чисел есть число 1, что невозможно, ведь 1 не является простым числом. Таким образом, мы можем разложить n на простые множители и перебрать все возможные варианты.

Подсказка 7

Получаем, что n = p⁵ или n = р₁р₂². В первом случае легко угадываем пятую степень некоторого числа, не превосходящую 100, а во втором вариантов будет гораздо больше! Так как р₁ ≥ 2, р₂² ≤ 100/2 = 50, отсюда получаем возможные варианты р₂, перебираем их и находим подходящие числа!

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

Ясно, что $n= 1$ подходит, ведь произведение из условия будет равно $1 =n3.$ Рассмотрим теперь $n> 1.$ Обозначим произведение его делителей буквой $P.$

Если число $n$ не является точным квадратом, то его делители можно разбить на $s$ пар с произведением $n$ в каждой (если число $n$ делится нацело на $√ - k < n$ , то оно делится нацело и на $n n-- √- m = k > √n = n$ ). Например, $18 =1 ⋅18= 2⋅9= 3⋅6$ . Так что делители бьются на пары с произведением $n$ в каждой, откуда $s P =n .$

По условию $3 P =n$ , тогда $s= 3.$ Число должно иметь $6$ делителей.

Если число является точным квадратом, то есть ещё делитель $√- n,$ поэтому $s+1 3 P = n 2 = n$ — противоречие с тем, что $s$ — целое число пар.

Для $k k n =p11⋅...ptt ,ki ∈ℕ$ количество различных делителей равно $t (1+ k1)...(1+ kt)≥ 2$ (берём каждое простое в каждой степени, считая нулевую). Если число $n$ должно иметь ровно $6$ делителей, то $6≥ 2t =⇒ t= 1 или t =2$ .

При $t= 1$ получаем $n= p5$ . Среди чисел от $1$ до $100$ подходит только $n =32.$

При $t= 2$ получаем $n= p1p22.$ Из условия на промежуток

$p22 ≤ 1020= 50 ⇐⇒ p2 ≤7 ⇐ ⇒ p2 ∈ {2,3,5,7}$ .

Добавим также условие $p22 ≥ 4 =⇒ p1 ≤ 25$ , затем остаётся просто перебрать по очереди все $p2$ , а затем выбрать подходящие простые $p1 ≤ 25$ , получим числа

22⋅3 =12,22 ⋅5 =20,22 ⋅7 =28,22⋅11 =44,22 ⋅13= 52,22⋅17= 68,22⋅19= 76,22⋅23= 92

32⋅2= 18,32⋅5= 45,32⋅7= 63,32⋅11= 99

52⋅2=50,52⋅3= 75

72⋅2= 98

Ответ:

$1,12,18,20,28,32,44,45,50,52,63,68,75,76,92,98,99$

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

Задача 10#75971

Тройка целых чисел $(x,y,z),$ наибольший общий делитель которых равен $1,$ является решением уравнения

2 2 3 2 2 y z+ yz =x + x z− 2xz

Докажите, что $z$ является кубом целого числа.

Источники: Высшая проба - 2017, 11.4(см. olymp.hse.ru)

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

Подсказка 1

В исходном выражении уже есть куб. Можно ли как-то его переписать так, чтобы получилось, что z делит этот куб?

Подсказка 2

Верно! z(y² + yz - x² + 2xz) = x³. Теперь, если доказать, что НОД z и y² + yz - x² + 2xz, то задача будет решена. Как это сделать?

Подсказка 3

По алгоритму Евклида можно получить, что НОД этих чисел такой же, как НОД z и y² - x². Пойдем от противного: может ли этот НОД быть равен t > 1?

Подсказка 4

Точно! Если t > 1, то x³ делится на t. Кроме того, t делится на некоторое простое q, а тогда и x делится на это q. Какой вывод можно сделать?

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

Запишем равенство в следующем виде: $z(y2+ yz− x2 +2xz)= x3.$ Если мы докажем, что НОД $z$ и $y2+yz− x2+ 2xz$ равен $1,$ то тогда $z$ будет кубом. Предположим, что $z$ в этой ситуации не является кубом. Тогда в разложение $z$ входит какое-то простое число $p$ в степени, не кратной $3.$ Скобка $2 2 y + yz− x +2xz$ на $p$ не делится, значит $p$ входит в $3 x$ в степени, не кратной $3,$ чего быть не может.

Итак, докажем взаимною простоту $z$ и $2 2 y + yz− x + 2xz.$ Ясно, что НОД этих чисел равен НОДу $z$ и $2 2 y − x .$ предположим, что этот НОД равен $t> 1.$ Тогда $3 x$ делится на $t.$ Пусть $t$ делится на некоторое простое число $q,$ тогда на $q$ делится $x$ и $2 2 y − x .$ Значит, $y$ также делится на $q.$ Также $z$ делится на $t,$ а значит и на $q.$ Получается, что НОД $x,y$ и $z$ больше $1,$ противоречие. Значит, НОД $z$ и $2 2 y − x$ равен $1,$ что и требовалось.

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

Задача 11#88130

Найдите все натуральные числа $n$ от 400 до 600 такие, что если перемножить все делители числа $n$ (включая 1 и $n$ ), получим число $5 n$ .

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

Утверждается, что $n$ удовлетворяет условию задачи, если и только если его разложение $n= pk1...pks 1 s$ на простые множители имеет вид либо $9 n =p$ , либо $4 n= p1p2$ .

Действительно, для каждого $j =1,...,k1$ имеется $(k2+ 1)...(ks+ 1)$ делителей числа $n$ , содержащих $p1$ в степени $j$ в разложении на простые множители: все эти делители имеют вид $j m1 ms p1p2 ...ps , mi ∈ {0,...,ki}$ . Следовательно, произведение всех делителей числа $n$ содержит $p1$ в степени $1 (k2+ 1)...(ks +1)(1+...+k1)= 2(k1+1)...(ks+1)k1$ . Условие, что произведение всех делителей равно $5 n$ , эквивалентно утверждению, что каждое $pj$ входит в их произведение в степени $5kj$ , и, тем самым, предыдущее выражение равно $5k1$ . Другими словами,

1 2 (k1+ 1)...(ks+ 1)= 5.

С другой стороны, $kj ≥ 1$ . Отсюда следует, что $s≤ 2$ . Пусть $s= 2$ . Тогда одно из $kj$ , скажем, $k1$ равно 1 , а тогда $k2 = 4$ (простота числа 5). В случае, когда $s= 1,k1 = k$ , получаем уравнение $12(k+ 1)= 5$ , то есть $k =9$ . Итак, все числа $n ⁄= 1$ , удовлетворяющие условию задачи, имеют разложение на простые множители вида либо $n= p1p42,p1 ⁄= p2$ , либо $n = p9;p1,p2,p>1$ . Перечислим те из них, которые лежат между 400 и 600.

Числа $n= p1p42$ . Имеем $p42 ≤600∕2= 300$ , тем самым, $p2 ≤ 4,p2 ∈ {2,3}$ . Итак, $16 ≤p42 ≤ 81$ . Следовательно, $4 =[400∕81]< p1 ≤ [600∕16]= 37$ , а, значит,

p1 ∈ {5,7,11,13,17,19,23,29,31,37},p2 ∈{2,3}.

Выписывая всевозможные произведения $n =p1p42$ , лежащие в промежутке от 400 до 600 , с вышеуказанными $p1$ и $p2$ , получаем $5⋅34 = 405,7⋅34 = 567,29⋅24 = 464,31⋅24 =496,37⋅24 = 592$ .

Единственное $n =p9$ , лежащее между 400 и 600 , есть $512=29$ . Итого получаем список всех возможных чисел $n$ :

n =405,464,496,512,567,592.

Ответ: 405,464,496,512,567,592

Интенсивы

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

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

Задача 12#94877

На доске написано несколько цифр (среди них могут быть одинаковые). На каждом шаге две цифры стираются и пишутся цифры, из которых состоит их произведение. (Например, вместо $5$ и $6$ пишется $3$ и $0$ , а вместо $2$ и $4$ пишется $8$ ). Доказать, что через несколько шагов на доске останется одна цифра.

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

Подсказка 1

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

Подсказка 2

Возьмём две произвольные цифры a, b. Не умоляя общности, а ≥ b. b, a ≤ 9, значит, 10b > ab. То есть ab ≤ 10b - 1. Посмотрим внимательно на десятичные записи этих чисел. Какой вывод о них можно сделать?

Подсказка 3

Либо ab < 10 и оно однозначное, либо первая цифра ab < min(a,b) = b. Теперь надо выбрать, полуинвариант или индукция?

Подсказка 4

Допустим, полуинвариант. Нууу, у нас есть цифры на доске, причём перемножаться они могут хаотично. Как тогда следить за первыми цифрами получаемых произведений? Сумма цифр на доске, произведение — не подходят. Остальное тоже странно связано. Интересно, что же там насчёт индукции?

Подсказка 5

Начнём с базовых идей. Попробуем зацепиться за количество цифр на доске. Пусть изначальное количество цифр на доске — n. База для n = 1 тривиальна. Попробуем сделать переход.

Подсказка 6

Пусть мы доказали для n = k, докажем для n = k + 1. Заметим, что если в какой-то момент цифр на доске стало меньше, то в этом случае переход доказан, просто пользуемся предыдущими шагами индукции. Хорошо, а что если цифр не станет меньше? Как быть в этом случае? Напомню, первая цифра ab < min(a,b). На какую мысль нас это наталкивает?

Подсказка 7

Верно! Мы понимаем, что после каждого шага, на доске появляется цифра, которая меньше чем те, что были взяты. Ну предположим, что минимальная цифра не уменьшается бесконечно долго. Значит, она не участвует в операциях. Аналогично посмотрим на минимальную из оставшихся, она тоже бесконечно долго не уменьшается (иначе стала бы меньше глобального минимума). И так далее. Получаем что все цифры бесконечно долго не уменьшаются. Противоречие. (Это надо оформлять в общем виде) И так, что мы имеем?

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

При решении задачи будем использовать свойство уменьшения первого разряда. Оно состоит в том, что при умножении двух цифр $a$ и $b$ получается либо однозначное число (цифра), либо двузначное, и в последнем случае первая цифра двузначного произведения меньше, чем минимальная из цифр $a,b$ .

Действительно, двузначные числа $a0 =10× a$ и $b0 =10× b$ больше, чем $ab$ , так как $a,b< 9$ . Тем самым на каждом шаге либо получается на цифру меньше (первый случай), либо число цифр сохраняется, но минимальная из всех цифр, написанных на доске, не увеличивается.

_________________________________________________________________________________________________________________________________________________________________________________

Будем доказывать утверждение задачи индукцией по числу $n.$ При $n = 1$ утверждение очевидно. Утверждение для $n = 2$ следует из свойства уменьшения первого разряда, в силу которого через несколько шагов останется одна цифра.

_________________________________________________________________________________________________________________________________________________________________________________

Пусть утверждение доказано для $n =k$ . Пусть $m$ — минимальная из цифр, написанных на доске. Достаточно показать, что через несколько шагов либо число цифр уменьшится, либо минимальная цифра уменьшится: появится цифра меньше $m$ .

Предположим противное. Тогда число цифр не уменьшается и в каждый момент есть цифра $m$ , к которой очередной шаг задачи не применяется: каждый шаг не затрагивает хотя бы одну цифру $m$ . В противном случае, если осталась одна или две цифры $m$ , и к ней (соответственно, к ним обеим) применен шаг задачи, и при этом число цифр не уменьшается, то минимальная цифра уменьшится в силу свойства уменьшения первого разряда.

Вышесказанное эквивалентно тому, что все шаги задачи применяются к меньшему набору цифр: ко всем, кроме одной из цифр $m$ . А тогда по предположению индукции через несколько шагов на доске, кроме цифры $m$ , останется одна цифра. Это сводит шаг индукции к случаю двух цифр, для которого утверждение задачи доказано.

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

Задача 13#73180

На доске написаны числа $1∕2,1∕3,...,1∕100$ . Разрешается стереть любые два числа $a$ и $b$ и записать вместо них $a+b− ab$ . После нескольких таких операций на доске осталось одно число. Чему оно может быть равно?

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

Подсказка 1

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

Подсказка 2

Давайте отдельно посмотрим на выражение a + b - ab. Ничего не напоминает?

Подсказка 3

Верно! -(a-1)(b-1) = (a-1)(1-b) = a + b - ab - 1. То есть у нас были числа a, b. А появилось число -(a-1)(b-1) + 1. Давайте сначала определимся, инвариант у нас будет в виде произведения или в виде суммы?

Подсказка 4

Вот это слагаемое ab всё портит, если рассматривать сумма. Мы про него особо ничего не понимаем. Значит нужно пробовать искать инвариант в виде произведения.

Подсказка 5

Вот мы видим скобки (a-1), (b-1). Давайте попробуем что-нибудь с ними сделать. Что первое приходит на ум?

Подсказка 6

Конечно, давайте попробуем следить за произведением (x₁ - 1)(x₂ - 1)...(x_k - 1), где {x_i} - числа на доске в какой-то момент. Вспомним, что числа a, b заменяются на -(a-1)(b-1) + 1. То есть инвариант заменяется с (а-1)(b-1)... на -(a-1)(b-1).... То есть просто меняет знак. Какой вывод из этого можно сделать?

Подсказка 7

Пусть A — итоговое число. То (A-1) = (1/2 - 1)(1/3 - 1)...(1/100 - 1). Знак остался прежним, так как убрали 98 чисел, значит, знак сменился чётное количество раз. (1/2 - 1)…(1/100 - 1) = (-1/2)*(-2/3)*...*(-99/100) = -1/100. Итого, A = 1 - 1/100 = 99/100.

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

Если на доске написаны числа $x,x ,...,x 1 2 k$ , то будем следить за величиной $(x − 1)(x − 1)...(x − 1) 1 2 k$ . Заметим, что вместо выражения вида $(a− 1)(b− 1)$ будет выражение $a+ b− 1 − ab= −(a− 1)(b− 1)$ . То есть за каждый ход рассматриваемое выражение меняет знак. Изначально оно было равно

( 1 ) (1 ) ( 1 ) 1 2 99 1 2 − 1 3 − 1 ... 100 − 1 = −2 ⋅3 ⋅...⋅100 = − 100.

Значит, и через 98 операций наше выражение будет равно $− 1100-$ . То есть в конце будет выписано число $− 1100 + 1= 0,99.$

Ответ: 0,99

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

Задача 14#89720

Найдите наименьшее натуральное число, представимое в виде $20x2+ 80xy+ 95y2$ для целых $x$ и $y.$

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

Подсказка 1

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

Подсказка 2

Итак, мы получили выражение 4x² + 16xy + 19y². Первые два слагаемых похожи на формулу полного квадрата. Как насчёт того, чтобы его выделить? Сумму квадратов оценить не так уж трудно. Хм, а для чего мы это сделали..?

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

Поделим все на $5.$

2 2 2 2 4x +16xy+ 19y = 4(x+ 2y) + 3y

По модулю $4$ полученное выражение сравнимо либо с $0,$ либо с $3.$ Тогда это выражение, раз оно принимает натуральное значение, хотя бы $3.$ Причем значение, равное $3,$ достигается при $y = 1,x= −2.$ Тогда минимальное натуральное значение исходного выражения равно $15.$

Ответ:

$15$

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

Задача 15#96543

В ряд выписаны цифры $987654321.$ Поставьте между ними ровно два знака минус так, чтобы значение полученного выражения было минимальным. (Например, при расстановке $9876− 54− 321$ получается $9501.$ ) Не забудьте объяснить свой пример.

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

Подсказка 1

Значение нового выражения должно быть минимальным. Попробуем исходя из этого поставить первый минус. Можно ли сделать выражение отрицательным?

Подсказка 2

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

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

Давайте для начала попробуем поставить один знак минус, чтобы значение выражение стало минимальным. Тогда понятно, что можно сделать выражение отрицательным, причём максимальным по модулю. Это значит, что минус нужно разместить таким образом $9− 87654321.$ Остался второй минус, и чтобы выражение было минимальным, нам нужно максимальное количество разрядов. Получается достаточно просто вычесть $1.$ Конечная расстановка $9− 8765432− 1.$

Ответ:

$9− 8765432− 1$

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

Задача 16#72110

Найдите все натуральные числа $n$ , такие, что число $n2+ 77n$ является точным квадратом натурального числа.

Источники: Высшая проба - 2015, задача 9.6(см. olymp.hse.ru)

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

Подсказка 1

В уравнениях с целыми числами полезно приводить выражение к виду (что-то)*(что-то)=число, попробуйте сделать что-то в этом духе

Подсказка 2

В условии фигурируют квадраты чисел. Какую ФСУ требуется применить к квадратам чтобы получить разложение на скобки?

Подсказка 3

Выделите полный квадрат с n и распишите разность квадратов.

Подсказка 4

Вы получили уравнение: (2n-2q+77)(2n+2q+77)=77². Осталось перебрать варианты. Как можно упростить перебор?

Подсказка 5

Заметим, что: 2n-2q+77 < 2n+2q+77. Осталось разобрать случаи!

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

Решим уравнение $n2+ 77n =q2$ в натуральных числах. Преобразуем левую часть следующим образом:

2 77 772 772- 2 n + 2⋅2 ⋅n+ 4 − 4 = q

Теперь запишем уравнение в виде

77 772 (n +-2 )2− q2 = 4-

Домножим равенство на $4$ и разложим левую часть на множители через разность квадратов:

(2n − 2q+ 77)(2n+ 2q +77)= 772

Осталось перебрать возможные варианты. Для упрощения перебора заметим, что

2n − 2q+ 77< 2n +2q+ 77

Следовательно, для скобочек возможны следующие варианты: $1$ и $2 77 ,$ $7$ и $2 7⋅11,$ $11$ и $2 7 ⋅11,$ $49$ и $121.$ Осталось разобрать каждый случай и написать ответ.

Ответ:

$1444,175,99,4$

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

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

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

Задача 17#94021

Пусть $p> 2$ — натуральное число, не делящееся на $3.$ Рассмотрим все целые числа $a,a ,...,a 1 2 k$ из интервала $(− p,p) 22$ такие, что $ai ≡ p (mod 3)$ для всех $i=1,2,3,...,k.$ Докажите, что произведение

p− a1 p− a2 p− ak -|a1|-⋅-|a2|-⋅...⋅-|ak|-

является натуральной степенью тройки.

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

Подсказка 1

Рассмотрим, например, p - a₁. Выделим из него максимальную степень тройки. То есть представим в виде p - a₁ = k₁b₁, где k₁ — степень тройки, а b₁ не делится на 3. Если так сделать для всех i, то получится, что нужно разделить произведение степеней тройки и каких-то чисел b₁b₂..., не делящихся на 3, на произведение чисел, не делящихся на 3, |a₁a₂...|. Если доказать, что эти произведения равны, то все получится. Как можно это сделать?

Подсказка 2

Чисел b₁... столько же, сколько чисел a₁... Попробуем доказать, что на самом деле они равны. Для этого сначала исследуем числа |a₁|... Можно ли доказать, что они различны?

Подсказка 3

Верно! Они не равны, поскольку тогда мы бы получили, что какие-то два из них противоположны, что означало бы, что 2p делится на 3, что по условию неверно. А можно ли теперь доказать, что |a₁|... — на самом деле и есть все числа в интервале (0;p/2), не делящиеся на 3.

Подсказка 4

Верно! Если возьмем число t, не делящееся на 3 в промежутке (0;p/2), то либо t, либо -t совпадает с p по модулю 3. А, если вспомнить определение чисел a₁..., то получится, что t или -t с одним из них совпадает. А тогда и получится нужное утверждение. А можно ли теперь и про числа b₁... доказать то же самое?

Подсказка 5

Легко проверить, что все b₁... лежат в интервале (0;p/2). А можно ли теперь проверить, что все они различны?

Подсказка 6

Предположим, что какие-нибудь два из этих чисел совпали и обозначим их e и f, а соответствующие им числа из a₁, ... g и h. Как мы знаем, g и h различны. Тогда что можно сказать о величине (p - g)/(p - h)?

Подсказка 7

Верно! Мы предположили, что e = f, а поскольку g и h различны, можно считать, что p - g > p - h. Тогда это отношение не меньше трех. С другой стороны, поскольку g и h — числа из промежутка (-p/2;p/2) получаем, что это отношение строго меньше трех. Тогда все числа b₁... различны. Как теперь доказать, что эти числа являются ровно теми числами, которые не делятся на 3 из промежутка (0; p/2)?

Подсказка 8

Возьмем некоторое t, не делящееся на 3, из промежутка (0;p/2). Тогда можно указать такую степень тройки k, что p - kt тоже число из промежутка (0;p/2), при этом p - kt имеет тот же остаток, что и p при делении на 3. Какой вывод можно сделать?

Подсказка 9

Верно! Тогда p - kt является одним из чисел a₁... Тогда и t является одним из чисел b₁. Как теперь доказать, что значение искомого выражения является степенью тройки?

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

Ясно, что все $|a | i$ принадлежат интервалу $(0,p) 2$ и различны, поскольку если $a = −a , i j$ то $a +a = 0, i j$ откуда $2p ≡0 (mod 3),$ что неверно по условию задачи.

Еще заметим, что каждое число, не делящееся на $3,$ из интервала $p (0,2)$ совпадает с одним из $|ai|.$ Действительно, пусть $p t∈ (0,2)$ и $t$ не делится на $3.$ Тогда либо $t≡ p (mod 3),$ либо $− t≡ p (mod 3).$ Тогда одно из чисел $± t$ совпадает с $ai,$ откуда получаем, поскольку $t> 0$ , что $t= |ai|.$ Тогда получаем, что множество всех $|ai|$ совпадает с множеством всех чисел из интервала $p (0;2),$ не делящихся на $3.$

Пусть $c 3 i$ — максимальная степень тройки, делящая $(p− ai).$ Поскольку $p ≡ai (mod 3),$ имеем $ci > 0.$ Пусть $c p− ai = 3ibi,$ где $bi$ не делится на $3.$ Заметим, что все $bi$ лежат в интервале $p (0,2),$ поскольку $p p − 2 < ai < 2$ и, следовательно $p−ai p 0< -3ci-< 2.$ Докажем, что все $bi$ различные. Предположим противное: $bi = bj$ для некоторых $i,j.$ Мы знаем, что $p− ai ⁄= p− aj,$ поэтому $ci ⁄= cj.$ Пусть $ci >cj$ Тогда

ci pp−− aai-= 33cjbbi≥ 3 j j

С другой стороны,

p−-ai< 3p∕2-< 3 p− aj p∕2

Таким образом, мы получаем противоречие, и $bi ⁄= bj$ для всех $i,j.$ Докажем теперь, что любое число, не делящееся на $3$ из интервала $p (0,2)$ совпадает с одним из $bi.$ Действительно, пусть $p t∈ (0,2),$ $3⁄|p.$ Тогда существует такое $c,$ что $c p 3p t⋅3 ∈(2,2 ),$ следовательно, $c p p p− t⋅3 ∈(−2,2)$ и при этом $c p− t⋅3 ≡p (mod 3).$ Тогда $c p− t⋅3 = ai$ при некотором $i.$ Но тогда $c p − t⋅3 = ai,$ откуда $t= bi.$

Итак, множество всех чисел $bi$ совпадает с множеством всех чисел, не делящихся на $3$ в интервале $p (0,2),$ поэтому совпадает с множеством $|ai|.$

Тогда имеем

c1+c2+...+ck p− a1-⋅ p− a2-⋅...⋅ p−-ak-= 3-----⋅b1b2...bk= 3c1+c2+...+ck |a1| |a2| |ak| |a1||a2|...|ak|

что и требовалось.

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

Задача 18#64855

Найдите все пары взаимно простых натуральных чисел $a$ и $b$ такие, что $2a2 +3b2$ делится на $2a+3b.$

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

Подсказка 1

Пусть m = 2а+3b. Тогда отсюда выражается, например, 2а, которое при возведении в квадрат превращается в 4а^2. А у нас в изначальном выражении есть 2а^2, значит таким образом мы сможем узнать что-то о соотношении b и m. Аналогично узнаем про число а и m.

Подсказка 2

Верно, и 15b^2 кратно m, и 10a^2. Используя понимание взаимной простоты чисел а и b мы должны осознать, какие простые делители есть у m.

Подсказка 3

Могут ли простые делители числа m входить в него больше, чем в первой степени? Получив ответ на этот вопрос, мы найдем единственно возможные варианты числа m = 2а+3b и проверим их, помня, что работаем с натуральными числами.

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

Заметим, что $4a2− 9b2 = (2a+ 3b)(2a − 3b) ≡ 0, 2a+3b$ отсюда $4a2 − 9b2− 2(2a2+3b2)=− 15b2 ≡ 0 2a+3b$ и $4a2− 9b2+ 3(2a2+ 3b2)= 10a2 ≡ 0. 2a+3b$ Пусть $2a+ 3b$ содержит некоторый делитель $d,$ который взаимно прост с $10$ и $15$ — тогда на это число должны делиться $a2$ и $b2,$ что невозможно, поскольку $(a2,b2)= 1.$ Отсюда $2a +3b$ делится только на $2,3,5$ (из простых чисел). Если какое-то простое число $p$ входит в него большей степени $q > 1,$ то $pq−1$ делит $a2$ и $b2,$ значит, степень каждого простого не больше первой. То есть $2a+ 3b$ может принимать значения $1,2,3,5,6,10,15,30.$ Первые три невозможны, пятёрка даёт нам $a= b= 1,$ что подходит. Пятый случай также невозможен, в шестом $a =b =2,$ условие взаимной простоты не выполнено. Для $15$ есть случаи $a =b =3$ и $a= 6,b= 1,$ нам подойдёт только второй. Для $30$ получаем $(3,8),(6,6),(9,4)$ — подойдут первый и третий случаи. Остаётся выписать ответ.

Ответ:

$(1,1),(6,1),(3,8),(9,4)$

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

Задача 19#89286

Найдите все пары взаимно простых натуральных чисел $a$ и $b$ такие, что $a2+3b2$ делится на $a+ 3b$ .

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

Подсказка 1

Давайте найдём какое-нибудь выражение, которое точно делится на (a + 3b) и может быть нам полезно в данной задаче. Нам отлично подойдёт a² + 3ab. И правда! Выражение a² + 3b² - a² - 3ab легко сворачивается в 3b(b - a), а также оно должно делиться на (a + 3b).

Подсказка 2

С помощью алгоритма Евклида легко доказать, что (b, a+3b) = 1 ≥ 3*(b - a) делится на (a + 3b). Теперь необходимо сравнить между собой a и b и рассмотреть разные случаи

Подсказка 3

Если a = b, то с учётом взаимной простоты двух чисел, этот случай очевиден. Если же b > a, то решений также не будет по понятным причинам. Остаётся единственный содержательный случай — a > b.

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

Заметим, что $a2+3ab$ делится на $a+ 3b$ тогда