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

Тема Курчатов

Теория чисел на Курчатове (с комбинаторными элементами)

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

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

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

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

Подтемы раздела курчатов

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

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

Задача 1#68025

На доске написаны 100 различных натуральных чисел. Петя записал на доску красным цветом все их попарные суммы, а синим цветом — все их попарные произведения. Может ли оказаться так, что для каждого красного числа найдётся делящееся на него синее? (Допускается, что одно и то же синее число может делиться на разные красные числа).

Источники: Курчатов-2023, 11.1 (см. olimpiadakurchatov.ru)

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

Пусть на доске записаны числа $200!⋅1,200!⋅2,200!⋅3,...,200!⋅100.$ Сумма любой пары имеет вид $200!⋅x, где 2≤ x≤ 199.$ А произведение - $2 (200!) ⋅y,$ где $y ∈ ℕ.$ Так как $200!$ делится на все возможные значения $x,$ то в выбранной паре произведение чисел делится на их же сумму.

Ответ: да

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

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

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

Задача 2#68029

У Пети есть $n$ карточек с $n$ последовательными натуральными числами (на каждой карточке написано ровно одно число). Он выложил эти карточки в ряд в некотором порядке.

У каждых двух чисел на соседних карточках Петя нашёл наибольший общий делитель. При каком наибольшем $n$ все эти наибольшие общие делители могут оказаться различными числами?

Источники: Курчатов-2023, 11.5 (см. olimpiadakurchatov.ru)

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

Пример. Возьмём числа $12,13,14,15,16$ и расставим их в следующем порядке:

13,15,12,16,14

Тогда НОДы будут $1,3,4,2.$

Оценка. Здесь и далее $(a,b)$ — это НОД $(a,b).$ Прежде всего отметим, что:

(a,b)= (a− b,b)≤|a− b|

То есть НОД двух соседних чисел не превосходит модуля их разности. Но модуль разности любых двух из $n$ последовательных натуральных чисел принимает значения от $1$ до $n− 1.$ Всего Петя получит как раз $n− 1$ пару соседних чисел. Значит, в качестве НОДов должны встретиться все числа от $1$ до $n− 1$ по одному разу.

Докажем, что четные числа могут стоять только подряд.

1.: Пусть $n$ четно: $n = 2k.$ Тогда произвольная пара чисел отличается на величину от $1$ до $2k− 1,$ то есть всего четных разностей $k− 1,$ а самих четных чисел — $k.$ Значит они должны стоять подряд.
2.: Пусть $n$ нечетно: $n = 2k +1.$ Тогда произвольная пара чисел отличается на величину от $1$ до $2k.$ всего четных разностей $k.$ Но заметим, что четных чисел на карточках может быть всего $k$ или $k +1.$ Если их $k,$ то мы получим максимум $k − 1$ четных разностей. Тогда их ровно $k+ 1$ и они должны стоят подряд.

Заметим, что НОД двух различных нечётных чисел не больше половины от их разности, поскольку разность чётная делит НОД, при этом сам НОД нечётный.

Теперь снова рассмотрим случаи в зависимости от чётности $n.$

1.: $n =2k+ 1.$ Тогда, как мы уже знаем, чётных чисел $k+1.$ Пусть они $x,x+ 2,...,x+ 2k.$ НОД $2k$ можно получить только поставив рядом $x$ и $x +2k.$ Получить НОД $2k− 1$ можно или парой $x,x+ 2k − 1$ или $x+ 1,x +2k,$ поскольку наибольшая нечётая разность как раз $2k− 1,$ а НОД не может быть больше разности. Будем считать, что выбрана первая пара. Покажем, что так можно сделать без ограничения общности. Заменим все числа на противоположные, а потом добавим $xn!$ . От этого НОДы соседних чисел не поменяются (поскольку мы добавили $n!$ несколько раз, что в любом случае делится на НОД (ведь он не более $n− 1).$ Числа всё ещё натуральные и последовательные ( $xn!− (x+ n− 1)> 0).$ При этом теперь наибольшее число перешло в наименьшее, то есть выбор пары тоже сменился. Тогда посмотрим, как идут в другую сторону чётные элементы. Для НОДа $2k − 2$ рядом с $x+ 2k$ обязательно стоит $x+ 2,$ поскольку наибольшая из доступных на текущий момент разностей как раз $2k− 2,$ а НОД не может быть больше разности. Для НОДа $2k − 4$ далее стоит $x+ 2k− 4.$ Далее мы снова будем чередовать самое маленькое из оставшихся чётных чисел и самое большое. В итоге, придём к $x+ k$ или к $x+ k+ 1$ (в зависимости от чётности $k).$ Попробуем получить НОД $2k− 3.$ НОД нечётных чисел не более $k− 1,$ поскольку их максимальная разность $2k− 2$ (наименьшее — $x+ 1,$ наибольшее — $x+ 2k − 1).$ С крайним чётным числом разность не более чем $k.$ Для $k≥ 4,2k − 3> k,$ поэтому такого НОД не получится. Противоречие. Для $k =3$ получаем последовательность $x +5,x,x +6,x+ 2,x +4,x+ 1.$ Но $(x+ 6,x)$ и $(x +4,x+ 1)$ не могут одновременно делится на $3.$ Противоречие.
2.: $n =2k.$ Без ограничения общности будем считать $x$ чётным. Рядом с $x$ должно стоять $x +2k− 1,$ чтобы получить НОД $2k− 1.$ Аналогично, другим крайним элементом последовательности чётных будет $x+k$ или $x+ k− 1$ в зависимости от чётности $k.$ Тогда снова попробуем получить НОД $2k− 3.$ Для двух нечётных он снова не более $k− 1.$ С крайним чётным числом разность не более $k − 1,$ ведь максимальное нечётное $x +2k− 1$ уже занято с другой стороны, а наименьшее нечётное $x +1.$ Для $k≥ 3,$ получаем $2k− 3> k− 1.$ противоречие.

Ответ:

$5$

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

Задача 3#70782

Натуральное число $A$ назовём интересным, если существует натуральное число $B$ такое, что:

$A > B$ ;
разность чисел $A$ и $B$ — простое число;
произведение чисел $A$ и $B$ — точный квадрат.

Найдите все интересные числа, большие 200 и меньшие 400.

Источники: Курчатов-2022, 11.3 (см. olimpiadakurchatov.ru)

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

Пусть $A − B = p$ — простое число. По условию $AB = B(B +p)= n2$ для некоторого натурального $n.$ Заметим, что НОД чисел $B$ и $B + p$ делит их разность, равную $p,$ поэтому он равен либо $p,$ либо 1. Разберём два случая.

Предположим, $НОД(B,B +p)= p.$ Тогда $B =ps$ и $B+ p= p(s +1)$ для некоторого натурального $s.$ Тогда $2 n =B (B +p)= ps⋅p(s+ 1),$ т.е. $2 2 n = ps(s+ 1).$ Отсюда следует, что $n$ делится на $p,$ поэтому $(n)2 s(s+1)= p$ — точный квадрат. Но $2 2 s <s(s+1)< (s+1) ,$ т. е. число $s(s+ 1)$ находится между двумя последовательными точными квадратами, поэтому само не может быть точным квадратом. Противоречие.
Предположим, $НОД (B,B +p)= 1.$ Произведение взаимно простых чисел $B$ и $B +p$ является точным квадратом тогда и только тогда, когда сами числа $B$ и $B+ p$ являются точными квадратами. Тогда $B =b2$ и $A =B + p= a2$ для некоторых натуральных $a >b,$ откуда следует, что $p =a2− b2 =$ $(a − b)(a+ b).$ Из того, что произведение натуральных чисел $a − b$ и $a+ b$ равно простому числу $p,$ следует, что $a− b=1$ и $a +b= p.$ Тогда $a= p+21$ и $b= p−21,$ поэтому $( )2 B = p−21$ и $( )2 A = p+12- .$ Поскольку число $p$ является простым, получаем несколько случаев:
- Если $p≤ 23,$ то $A≤ 122 < 200$ — не подходит под условие задачи.
- Если $p= 29,$ то $2 A= 15 = 225$ и $2 B = 14 =196$ — подходит под условие задачи.
- Если $p= 31,$ то $A= 162 = 256$ и $B = 152 =225$ — подходит под условие задачи.
- Если $p= 37,$ то $A= 192 = 361$ и $B = 182 =324$ — подходит под условие задачи.
- Если $p≥ 41,$ то $A≥ 212 > 400$ — не подходит под условие задачи.

Ответ: 225, 256, 361

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

Задача 4#70797

На доске написаны числа $2,3,5,...,2003,2011,2017,$ т. е. все простые числа, не превосходящие $2020.$ За одну операцию можно заменить два числа $a,b$ на максимальное простое число, не превосходящее $√-2------2 a − ab+ b.$ После нескольких операций на доске осталось одно число. Какое максимальное значение оно может принимать?

Источники: Курчатов - 2020, 11.3 (см. olimpiadakurchatov.ru)

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

$√a2-− ab+-b2$ по теореме косинусов это длина стороны напротив угла в $60∘$ в треугольнике, поэтому она является средней из трёх сторон. В связи с этим число $2017$ получиться не может, потому что каждое полученное в результате данной операции простое будет меньше $2017.$ Поэтому наибольшее число, которое мы теоретически можем получить, это $2011.$

Теперь приведём алгоритм, как получить 2011: будем последовательно выбирать два наибольших простых числа из всех, игнорируя $2017.$ Так всегда будет оставаться меньшее из этих чисел, поскольку большее остаться не может, при этом на каждом шаге мы рассматриваем два последовательных простых (это доказывается по индукции, поскольку на первом шаге мы оставим $2003$ из пары $2003$ и $2011,$ и так далее). То есть на каждом шаге $√-2------2 a< a − ab+b < b,$ при этом $a,b$ — последовательные простые, поэтому между ними других простых нет и мы будем выбирать $a.$

Наконец, останутся числа $2,2017,$ для них покажем, что $2011$ подходит:

∘--------------- 20172− 2⋅2017+22 >2011 ⇐⇒ 20172− 2⋅2017+ 22 > 20112 ⇐⇒ 6⋅4028> 4030

_________________________________________________________________________________________________________________________________________________________________________________

Замечание.

Можно чисто алгебраически доказать неравенство $√-2------2 a< a − ab+b < b$ при условии $a< b, a,b∈ ℕ.$ Для этого достаточно возвести его в квадрат и использовать $2 2 2 2 a< b =⇒ a < ab< b ⇐ ⇒ a − ab< 0, −ab+b > 0,$ откуда сразу же получаем требуемое $2 2 2 2 a < a − ab+b < b.$

Ответ:

$2011$

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

Задача 5#90886

Найдите количество способов раскрасить все натуральные числа от 1 до 20 в синий и красный цвета так, чтобы оба цвета встречались и произведение всех красных чисел было взаимно просто с произведением всех синих чисел.

Источники: Курчатов - 2020, 11.2 (см. olimpiadakurchatov.ru)

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

Заметим, что все чётные числа должны быть одного цвета. Так как среди них содержатся числа 6, 10 и 14, то числа, кратные 3, 5 и 7 должны быть того же цвета. Остались числа $1,11,13,17$ и 19. Заметим, что их можно распределить как угодно по двум цветам. Таким образом, у нас есть 6 групп, каждая из которых может быть любого цвета, т. е. всего $6 2$ способов раскраски. Заметим, что из них не подходят 2 варианта, в которых все числа одного цвета, Итого получается $6 2 − 2 =62$ способа.

Ответ: 62

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

Задача 6#102555

Докажите, что при натуральном $n >2$ числа от 1 до $n$ можно разбить на два множества так, чтобы произведения чисел в множествах отличались не более чем в $n−1 n−2$ раз.

Источники: курчатов - 2020, 11.5 (см. olimpiadakurchatov.ru)

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

Докажем это утверждение индукцией по $n$ .

_________________________________________________________________________________________________________________________________________________________________________________

База при $n= 3,4,5$ .

При $n =3$ разобьём на множества ${1,2}$ и ${3}$ , отношение равно $3 2$ , что меньше $2 1$ .

При $n =4$ разобьём на множества ${1,2,3}$ и ${4}$ . Отношение будет $6 4$ , что как раз равно $3 2$ .

При $n =5$ разобьём на множества ${1,2,5}$ и ${3,4}$ . Отношение равно $12 10$ , что меньше $4 3$ .

_________________________________________________________________________________________________________________________________________________________________________________

Переход индукиии от $n$ к $n+ 2$ при $n≥ 4$ .

Пусть у нас есть разбиение чисел от 1 до $n$ , удовлетворяющее условию. Добавим в множество с меньшим произведением $P1$ число $n +2$ , а в множество с бОльшим произведением $P2$ число $n+ 1$ . Докажем, что произведения отличаются не более чем в $n+2−1 n+1 n+2−2-= -n-$ раз.

Так как $P1 ≤ P2$ , то

P1⋅(n+-2)≤ n+-2< n+-1 P2⋅(n+ 1) n+ 1 n

С другой стороны, так как $P2 ≤ P1(nn−−1)2$ , то

P2⋅(n-+1)≤ (n−-1)(n+-1)= n2−-1= 1+ --3-- P1⋅(n +2) (n− 2)(n+ 2) n2− 4 n2− 4

Докажем, что это не больше $n+1 1 n = 1+ n$ . Это равносильно

3 1 2 n2−-4 ≤ n ⇔ 3n≤ n − 4 ⇔ ⇔ 0≤ n2− 3n − 4 ⇔ 0≤ (n− 4)(n+ 1)

что верно при $n≥ 4$ . Таким образом, переход доказан.

Курсы

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

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

Задача 7#103076

Докажите, что при натуральном $n >2$ числа от $1$ до $n$ можно разбить на два множества так, чтобы произведения чисел в множествах отличались не более чем в $n−1 n−2$ раз.

Источники: курчатов - 2020, 11.5 (см. olimpiadakurchatov.ru)

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

Докажем это утверждение индукцией по $n$ . База при $n= 3,4,5.$

При $n =3$ разобьём на множества ${1,2}$ и ${3}$ , отношение равно $3 2$ , что меньше $2 1$ .

При $n =4$ разобьём на множества ${1,2,3}$ и ${4}$ . Отношение будет $6 4$ , что как раз равно $3 2$ .

При $n =5$ разобьём на множества ${1,2,5}$ и ${3,4}$ . Отношение равно $12 10$ , что меньше $4 3$ .

Переход индукиии от $n$ к $n+ 2$ при $n≥ 4$ . Пусть у нас есть разбиение чисел от 1 до $n$ , удовлетворяющее условию. Добавим в множество с меньшим произведением $P1$ число $n+ 2$ , а в множество с большим произведением $P2$ число $n +1$ . Докажем, что произведения отличаются не более чем в $n+2−1- n+1 n+2−2 = n$ раз. Так как $P1 ≤ P2$ , то

P ⋅(n+ 2) n+ 2 n+ 1 P12⋅(n+-1) ≤ n+-1 <-n-

С другой стороны, так как $P2 ≤ P1(nn−−1)2$ , то

P2⋅(n-+1)≤ (n−-1)(n+-1)= n2−-1= 1+ --3-- P1⋅(n +2) (n− 2)(n+ 2) n2− 4 n2− 4

Докажем, что это не больше $n+1= 1+ 1 n n$ . Это равносильно

--3-- 1 2 n2− 4 ≤ n ⇔ 3n≤ n − 4 ⇔ ⇔ 0≤ n2− 3n − 4 ⇔ 0≤ (n− 4)(n+ 1)

что верно при $n≥ 4$ . Таким образом, переход доказан.

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

Задача 8#76739

Найдите все такие пары натуральных чисел $m$ и $n$ , что $m2019+ n$ делится на $mn$ .

Источники: Лига победителей - 2017, 9 класс (со степенью 2017), Курчатов - 2019, 11.2 (со степенью 2019)

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

Индукцией по $α$ покажем, что если $m α+ n$ кратно $mn$ , то $n$ представимо в виде $km α$ .

База: если $m +n$ делится на $mn$ , то $n$ делится на $m$ , из этого следует требуемое.

Переход: если $α+1 m + n$ кратно $mn$ , то $n= n1m$ , то есть $α m +n1$ кратно $mn1$ , а по предположению $α n1 =km$ , откуда $α+1 n =km$ .

Теперь, возвращаясь к задаче, имеем: $2019 n = km$ . Тогда условие можно записать в виде: $2019 (k+ 1)m$ кратно $2020 km$ . Таким образом, $k+ 1$ делится на $km$ , это возможно лишь при $k= 1$ и $m = 2$ или $m = 1$ , откуда подходят $m =1,n= 1$ или $2019 m = 2,n = 2$ .

Ответ:

$m = 1,n = 1$ или $m = 2,n =22019$

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

Задача 9#101215

Определите все пары натуральных чисел $n$ и $m,$ для которых числа $n2+ 4m$ и $m2+ 5n$ являются квадратами.

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

Разберем два случая. Сначала предположим, что $m ≤n.$ Тогда

2 2 2 2 n < n +4m ≤ n +4n <(n+ 2)

Следовательно, $n2+4m = (n +1)2,$ откуда $4m = 2n +1,$ что невозможно из соображений четности.

Теперь предположим, что $n < m.$ Тогда

2 2 2 2 m <m + 5n < m + 6n< (m + 3)

Следовательно, либо $m2 + 5n= (m + 1)2,$ либо $m2+ 5n= (m+ 2)2,$ откуда либо $5n= 2m+ 1,$ либо $5n= 4m+ 4.$ Изучим каждый из этих подслучаев отдельно.

Если $5n= 2m + 1,$ то $4m =10n− 2$ и число $n2 +4m = n2+10n− 2$ является квадратом, тогда

2 2 2 n < n + 10n − 2< n + 10n +25

Это квадрат числа, большего $n$ и меньшего $n+ 5,$ той же четности, что и $n.$ Следовательно, либо

n2 +10n− 2= (n +2)2 = n2+4n +4,

либо

n2+ 10n− 2= (n +4)2 = n2+8n+ 16

В итоге или $n= 1$ и $m = 2,$ или $n= 9$ и $m =22.$

Если же $5n =4m +4,$ то $4m = 5n− 4$ и число $n2+ 4m =n2 +5n− 4$ является квадратом, значит,

n2 < n2+ 5n− 4< n2+6n+ 9

Это квадрат числа, большего $n$ и меньшего $n+ 3.$ Следовательно, либо

n2+ 5n − 4 =n2+ 2n+ 1,

либо

2 2 n + 5n− 4= n +4n+ 4

Первое уравнение имеет нецелый корень, а второе дает $n = 8,$ откуда $m = 9.$

Все полученные ответы подходят.

Ответ:

$(m,n)∈ {(2,1), (22,9), (9,8)}$

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

Задача 10#46230

На доске было выписано несколько чисел, их среднее арифметическое было равно $M$ . $K$ ним дописали число $15$ , при этом среднее арифметическое выросло до $M +2$ . После этого дописали ещё и число $1$ , и среднее арифметическое уменьшилось до $M + 1$ . Сколько чисел было на доске изначально?

(Найдите все варианты и докажите, что других нет.)

Источники: Курчатов-2017, 11.1 (см. olimpiadakurchatov.ru)

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

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

{ Mn+15 = M +2 { Mn +15= Mn + 2n+ M +2 { 13 =2n +M Mnn++116 = M +1 ⇐ ⇒ Mn +16= Mn + 2M +n +2 ⇐ ⇒ 14 =2M + n n+2

Откуда имеем единственное решение $n= 4,M =5$ .

Ответ:

$4$

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

Задача 11#75127

Пусть $d ,d,...,d 1 2 n$ — это все натуральные делители числа $10!= 1⋅2⋅...⋅10.$ Найдите сумму

----1--- ---1---- ---1---- d1+ √10! + d2+ √10! +...+ dn+ √10!

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

Обозначим указанную сумму за $S.$ Тогда, так как для каждого $d j$ число $10!∕d j$ — также делитель,

∑n 1 1 n∑ dj S = 10!∕d-+-√10! = √10! √10!+-d- j=1 j j=1 j

Следовательно, складывая исходное и последнее выражение для $S,$ умноженные на $√10!,$ получаем

√ --- √--- ∑n ( √10!- dj ) 10!S+ 10!S = dj-+√10! + dj +-√10! = n j=1

При этом $n$ — количество делителей числа $10!$ — вычисляется по формуле

$n =(8+ 1)(4+ 1)(2+ 1)(1+1)= 270$

( $10!= 28⋅34 ⋅52⋅71,$ каждый из простых множителей может входить в делитель в любой степени от $0$ до своей степени вхождения в число $10!$ ). Таким образом, $-270-- ----270----- -3-- S = 2√10! = 2⋅24 ⋅32⋅5⋅√7 = 16√7.$

Ответ:

$--3√- 16 7$

Интенсивы

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

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

Задача 12#77771

Найдите наименьшее возможное число $k$ такое, что при выборе любых $k$ различных чисел от 1 до 20, среди выбранных чисел гарантированно можно выделить пару различных с простой суммой.

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

Очевидно, что $10$ чисел недостаточно — можно выбрать все четные числа и сумма любых двух будет четной, большей двух, то есть составным числом. Покажем, что при выборе любых $11$ чисел найдется пара с простой суммой. Для этого разобьем все числа на пары:

(1,2), (3,8), (4,7), (5,6), (9,14), (10,13), (11,12), (15,16), (17,20), (18,19).

В каждой паре сумма чисел простая. При выборе $11$ чисел какая-то из пар будет выбрана целиком.

Ответ: 11

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

Задача 13#102758

Сколько решений в натуральных числах имеет уравнение

2017 (2x+y)(2y +x)= 2017 ?

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

Пусть $A = 2x +y$ — выражение в первой скобке, а $B = 2y +x$ — выражение во второй скобке. Заметим, что

A + B = 2x+ y+ 2y +x =3x+ 3y = 3(x +y),

то есть $A +B$ делится на 3. При этом ни $A,$ ни $B$ не могут делиться на 3, так как иначе $AB = 20172017$ делилось бы на 3, что неверно. Если $A$ имеет остаток 1 при делении на 3, то $B$ имеет остаток 2. Если $A$ имеет остаток 2, то $B$ имеет остаток 1. В обоих случая произведение $AB$ имеет остаток 2 при делении на 3. Но 2017 имеет остаток 1 при делении на 3, откуда $20172017$ тоже имеет остаток 1. Получается, левая и правая части уранений дают разные остатки при делении на 3, то есть решений нет.

Ответ:

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

Задача 14#47215

Назовем натуральное число модным, если в его записи встречается группа цифр $2016$ (например, числа $32016,1120165$ модны, а $3,216,20516$ — нет). Докажите, что всякое натуральное число можно получить как частное от деления модного числа на модное.

Источники: Курчатов-2016, 11.4 (см. olimpiadakurchatov.ru)

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

Пусть мы хотим получить число $N$ , которое содержит $k$ знаков. Рассмотрим числа $2016 0...0, ...20169...9 ◟ ◝k◜ ◞ ◟ ◝k◜ ◞$ . Среди этих чисел хотя бы одно делится на $N$ по принципу Дирихле, пусть оно равно $A$ , при этом $A∕N = B$ .

Пусть также $C = 2016 ⋅N$ — $m$ -значно. Рассмотрим число $D = B0◟..◝◜.0◞2016 m−4$ , тогда $E = D ⋅N = A-2016⋅N-$ . В итоге $N = E∕D$ — отношение двух модных.

Ответ:

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

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

Задача 15#38688

Митя сложил все нечётные натуральные делители некоторого чётного числа $N$ (включая единицу), а Ваня сложил все чётные натуральные делители числа $N$ (включая само число). Затем Ванину сумму умножили на Митину. Может ли произведение быть квадратом натурального числа?

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

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

По условию число имеет вид $k 2 ⋅m,$ где $m$ — нечётное. Заметим, что любому нечётному делителю $d$ числа $N$ взаимнооднозначно соответствует группа чётных делителей

2 k 2d,2 d,...,2 d

Тогда если обозначить Митину сумму через $S,$ то Ванина сумма примет вид

2 k k (2+ 2 +...+2 )S = 2(2 − 1)S

Если перемножить суммы, то мы получим

2(2k− 1)S2

Теперь видно, что вопрос задачи сводится к тому, может ли быть квадратом число вида $2(2k − 1).$ Очевидно, что нет, потому что оно делится на $2,$ но не делится на $4.$

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

Разложим число из условия по основной теореме арифметике

N = 2k⋅pk1⋅...pkr 1 r

Из такого представления известно, что сумма всех делителей числа $K =pk11⋅...pkrr$ равна

(1 +p1+ ...+ pk11)...(1+pr+ ...+ pkrr )= S

При этом это является суммой всех нечётных делителей $N.$ Для получения суммы только чётных делителей формула принимает вид

S⋅(2+22+ ...+ 2k)

В итоге произведение сумм равно $S2⋅(2+ 22 +...+ 2k)= 2S2 ⋅(2k− 1),$ однако легко видеть, что в левую часть двойка входит в нечётной степени, потому сумма не может быть точным квадратом.

Ответ: нет

Критерии оценки

За выражение произведения в виде S² * (2 + 2² + … + 2^k) – не менее 2 баллов.

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

Задача 16#41297

Ученику дано число $x:$ это обыкновенная дробь со знаменателем $9.$ Ученик вычислил три новых числа $2x,4x$ и $5x,$ каждое из этих трёх чисел округлил до ближайшего целого и результаты округлений сложил. Получилось $120.$ Найдите $x.$ (Число округляется в меньшую сторону, если его дробная часть меньше $1∕2,$ и в большую, если дробная часть больше либо равна $1∕2.)$

Источники: Курчатов-2015, 11.1 (см. olimpiadakurchatov.ru)

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

Давайте число $a$ после округления обозначать $R (a).$ Будем пользоваться тем, что если $a≤ b,$ то и $R(a)≤ R(b).$

Докажем, что

7 109 <x <11.

Пусть $S = R(2x)+ R(4x)+R(5x).$

Если $7 x≤ 10 9,$ то

( 5) ( 1) ( 8) S ≤ R 219 + R 439 +R 539 =22+ 43+54 =119< 120

Если $x≥ 11,$ то

S ≥R (22)+R (44)+R (55)= 121 >120

В указанном интервале есть только одно число со знаменателем $9$ — это $1089.$ Оно подходит:

( ) ( ) ( ) S = R 217 + R 435 + R 544 = 22 +44+ 54= 120 9 9 9

_________________________________________________________________________________________________________________________________________________________________________________

Замечание. Более естественно другое решение: показать, что $10< x< 11,$ а дальше просто перебрать все числа со знаменателем $9$ между ними. Если всё сделано верно, то это тоже полное решение.

Ответ:

$98 9$

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

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

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

Задача 17#34659

Дано натуральное число, кратное $495.$ Между его цифрами вставили два нуля подряд. Докажите, что полученное число тоже делится на $495.$

Источники: Курчатов-2014, 10.1 (см. olimpiadakurchatov.ru)

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

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

После разложения на взаимнопростые множители $495= 9⋅5⋅11$ нужно использовать критерии делимости для старого и нового (после вставки двух нулей) чисел.

$1$ ) Сумма цифр при вставке двух нулей не меняется, поэтому не меняется и делимость на $9.$

$2$ ) Знакопеременная сумма цифр также не меняется, поэтому не меняется и делимость на $11$ (или можно сказать, что суммы цифр на чётных и нечётных местах остались равны).

$3$ ) Последняя цифра не изменилась, так как нули вставляют между цифрами, поэтому не изменилась и делимость на $5.$

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

Обозначим число до вставленных цифр, у которого следующие цифры сделаем нулями, через $x$ (сразу заметим, что $x$ делится на $10$ , потому что у этого числа на конце нули), после — через $y.$