Теория чисел на Изумруде —Каталог задач по Олимпиадной математике

Главная
Каталог задач
Каталог заданий по Олимпиады - Математика
Теория чисел на Изумруде

Тема Изумруд

Теория чисел на Изумруде

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

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

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

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

Подтемы раздела изумруд

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

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

Задача 1#79616

Натуральные числа от 1 до 8 расставили по кругу так, что каждое число делится на разность своих соседей. Известно, что числа 2 и 5 стоят рядом. Докажите, что числа 4 и 6 стоят рядом.

Источники: Изумруд-2024, 11 (см. izumrud.urfu.ru)

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

Подсказка 1

Будем отталкиваться от того, что нам уже дано. Какие числа можно поставить рядом с 2? Какие - рядом с 5?

Подсказка 2

Рядом с 2 может стоять одно из чисел 3, 4 ,6, 7. Рядом с пятеркой - 1, 3, 7. Переберем случаи! От какого еще числа удобно отталкиваться?

Подсказка 3

Помним, что соседями единицы могут быть только последовательные числа.

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

Рядом с $2$ может стоять одно из чисел $3,4,6,7$ . Рядом с пятеркой — $1,3,7$ . Заметим также, что соседями единицы могут быть только два последовательных числа. Переберем всевозможные варианты для соседа двойки:

1) Рядом с 2 стоит 3. Тогда рядом с 3 может стоять только 1. Ее сосед — это только 4 и рядом с 4 может встать только 6.

2) Рядом с 2 стоит 4. Тогда рядом с 4 может стоять $1,3$ или $6$ .

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

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

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

Задача 2#71022

Найдите количество троек натуральных чисел $m, n,k$ , являющихся решением уравнения

∘ ---√-- m+ n+ k= 2023

Источники: Изумруд-2023, 11.4 (см. izumrud.urfu.ru)

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

Подсказка 1

Для каждого значения √(n+√k) значение m будет определено однозначно. Подумайте, какие значения может принимать √(n+√k).

Подсказка 2

√(n+√k) не может быть меньше 2, так как n и k больше 1, и также не может быть больше 2022, так как 2023-m≤2022. Давайте обратим внимание на то, что в правой части уравнения стоит целое число, тогда и в левой части тоже должно быть целое. Какие должны для этого соблюдаться условия?

Подсказка 3

Для этого k и n+√k должны быть точными квадратами. Обозначим k = x² и n+√k = y². В таком случае, число n определяется однозначно, значит, для получения ответа на задачу нам нужно найти все возможные пары (x, y).

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

Чтобы левая часть была целым числом, числа $k$ и $n +√k$ должны быть точными квадратами, при этом $n+ √k ≥2,$ значит $∘ ---√-- n+ k ≥2$ и отсюда $m ≤2021.$ Так как $1≤ m ≤$ $2021,$ то $∘ ---√-- n+ k$ может принимать любое значение от $2$ до $2022$ — по этому значению число $m$ определяется однозначно.

Пусть $2 k= x$ и $√ - 2 n + k= y,$ где $2 1≤ x≤ y − 1$ и $2≤y ≤2022,$ тогда число $n$ определяется однозначно, а именно $2 n= y − x.$ Получается, необходимо посчитать число допустимых пар $(x,y).$ Всего их

( ) ( ) 22− 1+ ...+ 20222− 1 =12+ 22+ ...+20222− 2022

Формула суммы квадратов первых $n$ натуральных чисел известна:

2 2 2 n(n+ 1)(2n +1) 1 +2 + ...+ n = ------6-----

Применим эту формулу и получим

2022⋅2023 ⋅4045 12+22+ ...+ 20222− 2022 = -----6------− 2022= 27575680773

Ответ: 27575680773

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

Задача 3#71019

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

a1+ a2+...+an = 2021,

где все числа $ai$ — натуральные, больше 10 и являются палиндромами (не меняются, если их цифры записать в обратном порядке). Если студент не нашёл ни одного такого примера, он получит на зачёте 2021 задачу. Какое наименьшее количество задач может получить студент?

Источники: Изумруд-2023, 11.1 (см. izumrud.urfu.ru)

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

Подсказка 1

Легко можно придумать пример для трех. Например, 22+888+1111. Попробуйте доказать, что меньше трех придумать невозможно.

Подсказка 2

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

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

Одну задачу студент получить не может, так как 2021 не является палиндромом. Предположим, что он может получить две задачи, тогда хотя бы одно из чисел $a1,a2$ — четырёхзначное. Если оно начинается на 2, то вторая цифра 0 и само число равно 2002. В таком случае второе число равно 19, что не палиндром. Если же число начинается с 1, то его последняя цифра также 1 и у второго числа последняя цифра должна быть нулём, что неверно для палиндромов. Значит две задачи студент получить не мог. Пример на 3 задачи существует, например, $1111+ 888+ 22= 2021.$

Ответ: 3

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

Задача 4#76459

Пусть $p ,p,...,p ,... 1 2 n$ — множество всех простых чисел, расположенных в некотором порядке. Может ли случиться так, что для всех натуральных $i$ число $pipi+1−p2i+2- pi+pi+1$ является натуральным?

Источники: Изумруд-2022, 11.5 (см. izumrud.urfu.ru)

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

Подсказка 1

В задачах на делимость (а это по сути она и есть) часто выгодно рассмотреть какое-то красивое число. А поскольку у нас в задаче часто фигурируют простые, рассмотрим p_m = 2. Что тогда хорошего можно сказать про дробь?

Подсказка 2

Тогда, можно сказать, что число меньше 2, а значит равно 1, а значит, p_(m + 1) = p^2_(m + 2) + 2. А мы как-то использовали m? Может ли m быть сильно большим? Как можно ограничить m зная симметричность p_(i + 1) и p_i в нашем числе?

Подсказка 3

Если m > 1, то можно взять рассмотреть (2p_(m - 1) - p^2_(m + 1))/(2 + p_(m - 1)). Тогда, p_(m - 1) = p^2_(m + 1) + 2 = (p^2_(m + 2) + 2)^2 + 2. По какому модулю теперь удобно посмотреть, при наличии тут множественных квадратов?

Подсказка 4

Конечно, mod 3. Ведь тогда, если p_(m + 2) != 3, то p_(m + 1) кратен 3, а значит равен 3. Но тогда p_(m + 2) = 1. А если же p_(m + 2) = 3, то p_(m - 1) = 123. Значит, пришли к общему противоречию с тем, что m > 1, значит, m = 1. При этом, поняли, что mod 3 в этой задаче, как будто, играет важную роль. Давайте тогда , если уж все таки хотим делимость, рассмотрим такие p_k и p_k + 1, что их сумма кратна 3, и при этом они оба отличны от 3. Что это значит тогда для этих двух чисел? А для дроби?

Подсказка 5

Это значит, что остатки mod 3 у этих

Подсказка 6

Это числа, которые сравнимы с 2 mod 3, а после идет сама тройка. Но тогда, если после тройки стоит число = 2 mod 3, то после него идут только числа = 2 mod 3, а значит пришли к противоречию, так как числа = 1 mod 3 существуют. А значит, после 3 идут только числа = 1 mod 3, но тогда перед 3 стоит конечное число простых = 2 mod 3. А то, что таких бесконечно - остаётся вам в качестве упражнения! :)))

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

Предположим, что такое могло случиться. Тогда существует натуральное $m$ такое, что $p = 2. m$ Значит число

2pm+1 − p2m+2 p2m+2 + 4 --2+pm+1---= 2− 2+pm+1-< 2

является натуральным, откуда

p2m+2-+4 =1 и pm+1 =p2 +2 2+ pm+1 m+2

Случай $m> 1$ невозможен, так как тогда число

2pm− 1− p2 p2 + 4 --2+pm−m1+1-= 2− m2++1pm-−1 < 2

также является натуральным, откуда

p2m+1-+4 =1 и p =p2 +2= (p2 + 2)2 +2 2+ pm−1 m−1 m+1 m+2

Теперь если $pm+2 = 3,$ то $pm−1 =123,$ что невозможно. Если же $pm+2 ⁄= 3,$ то

p2 ≡ 1 и p =p2 +2 ... 3 m+2 3 m+1 m+2

Значит,

pm+1 = 3, pm+2 = 1

Это невозможно. Следовательно, $m =1.$

Предположим теперь, что нашлись числа $pk$ и $pk+1$ с различными ненулевыми остатками при делении на 3, то есть

.. pk+pk+1. 3

Поскольку число

pkpk+1 − p2 --p-+-p-k+2 k k+1

является натуральным, то

. pkpk+1 − p2k+2.. 3

Но тогда

p2k+2 ≡3 pkpk+1 ≡3 2

Это невозможно, так как квадраты имеют остатки 0 или 1 при делении на 3. В итоге мы доказали, что числа с остатками 1 и 2 при делении на 3 не могут быть соседними.

Поскольку $p1 = 2,$ это означает, что после $p1$ стоят несколько чисел с остатком 2 при делении на 3, затем где-то стоит число 3. Если после тройки стоит число с остатком 2 при делении на 3, то все числа далее будут с таким же остатком и в последовательности простых чисел не будет ни одного числа с остатком 1 при делении на 3 (такие есть, например, число 7).

Следовательно, после тройки стоит число с остатком 1 при делении на 3 и все числа за ним имеют такой же остаток. Но тогда до тройки стоит лишь конечное число простых чисел с остатком 2 при делении на 3.

Предположим, что простых чисел вида $3k+ 2$ конечное число. Обозначим все такие числа через $q1,q2,...,ql.$ Число $3q1q2...ql− 1$ не делится на простые числа $q1,q2,...,ql$ и даёт остаток 2 при делении на 3. Значит среди его простых делителей должно быть число вида $3k+ 2$ — противоречие.

Ответ: нет

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

Задача 5#76458

Назовём число $x$ полуцелым, если число $2x$ — целое. Полуцелой частью числа $x$ назовём наибольшее полуцелое число, не превосходящее $x,$ и будем обозначать $]x[.$ Решите уравнение

2 x + 2⋅]x[= 6

Источники: Изумруд-2022, 11.3 (см. izumrud.urfu.ru)

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

Подсказка 1

Так, даны какие-то полуцелые части. Понятно, что сразу же напрашивается аналогия с целой и дробной частью. Когда мы делим число x на целую —[x], и дробную — {x} части, мы можем записать, что х=[x]+{x}, где [x] — целое число, а {x} лежит на [0,1). Здесь, чтобы облегчить себе жизнь, поступим так же и запишем подобные ограничения на полуцелую часть числа и “остаток”, который получается после ее вычитания.

Подсказка 2

Если обозначить за n/2 полуцелую часть, то можно записать, что x = n/2+r. Получаем уравнение на n и r и имеем соответствующие ограничения на эти величины. Далее нужно будет активно использовать то, в каких пределах лежит r, и вспомнить, какие приемы можно использовать в подобных задачах с целой и дробной частью.

Подсказка 3

Удобнее будет отдельно рассмотреть положительные и отрицательные n. Дальше только аккуратные преобразования, нахождение n, подстановка и нахождение r :)

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

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

1) Число $x$ — полуцелое, тогда $]x[= x$ и исходное уравнение примет вид

2 x + 2x − 6 =0

Корнями данного уравнения являются числа $x1,2 = −1± √7,$ но тогда числа $2x1,2$ не являются целыми, значит решений нет.

2) Имеет место равенство

n x= 2 +r,

где $n ∈ℤ$ и $1 0 <r < 2,$ тогда

[ n ]x = 2

А также исходное уравнение примет вид

(n )2 2 + r + n− 6=0

Выразим из уравнения $r$ и получим

r= − n± √6−-n 2

Решения существуют только при $n≤ 6.$ Найдём все $n,$ удовлетворяющие неравенству

n< ±√6-− n-< n+-1 2 2

Если $n≥ 0$ , то $n+-1> 0 2$ и может иметь решение только лишь неравенство

n √ ---- n+-1 2 < 6− n < 2 ,

которое после возведения в квадрат равносильно

2 2 n < 4(6− n)< (n +1)

{ n2+ 4n− 24 <0 n2+ 6n− 23 >0

(|{ − 2− 2√7-< n< −2+ 2√7 [ n >− 3+ 4√2- |( n <− 3− 4√2-

Поскольку $√- √- 2< −3+ 4 2< 3,3< −2+ 2 7< 4,$ и $√- √- − 3− 4 2< −2− 2 7$ , то $n =3$ — единственное целое значение, удовлетворяющее системе. В этом случае

x= n + r=√6-−-n= √3 2

Если $− 1< n< 0,$ то решений нет, так как $n$ — целое.

Если $n≤ −1$ , то $n-+1 ≤0 2$ и может иметь решение только лишь неравенство

n2 > 4(6− n)> (n +1)2

{ n2+ 4n− 24 >0 n2+ 6n− 23 <0

[ (|{ n >− 2+ 2√7- n <− 2− 2√7- |( − 3− 4√2-< n< −3+ 4√2

Поскольку $√- √- − 9< −3− 4 2< −8,−8< −2 − 2 7 <− 7,$ и $√ - √- − 3+ 4 2< −2+ 2 7,$ то $n= −8$ — единственное целое значение, удовлетворяющее системе. В этом случае

x = n+ r= −√6-− n =− √14 2

Ответ:

$√3,− √14$

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

Задача 6#76420

В вершинах правильного двенадцатиугольника в некотором порядке расставили натуральные числа от 1 до 12 (каждое по одному разу). Могло ли случиться так, что суммы всех пар соседних чисел являются простыми и суммы всех пар чисел, между которыми стоят ровно два числа, тоже являются простыми?

Источники: Изумруд-2022, 11.1 (см. izumrud.urfu.ru)

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

Подсказка 1

Для начала, попробуйте взять любое число от 1 до 12 и посмотреть, сколько чисел в сумме с исходным дают простое число!

Подсказка 2

Да, для каждого числа это индивидуально, поэтому конкретно из этого факта мало что можно извлечь. Но если рассмотреть похожую идею, какие числа в сумме с исходным образуют простое число? И как нам это поможет в задаче?

Подсказка 3

Верно, каждое число влияет ровно на 4 суммы. Так что, если мы найдем два числа, для которых дополнение до простого совпадает, то мы победим! (дополнение – число, которое в сумме с исходным даёт простое)

Подсказка 4

Да, надо посмотреть на числа 6 и 12.

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

Каждое число в вершине участвует ровно в четырёх суммах. Заметим, что для получения простой суммы к числам 6 и 12 можно прибавить только 1, 5, 7 и 11. Значит для вершин, в которых стоят числа 6 и 12, наборы соседних чисел и чисел, стоящих от них через две вершины, должны совпадать. Однако, для каждой вершины эти наборы различны, поэтому хотя бы одна из сумм не будет являться простым числом.

Ответ: нет

Интенсивы

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

Предыдущий раздел

Следующий раздел