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

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

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

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

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

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

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

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

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

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

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

Задача 1#68029

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

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

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

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

Подсказка 1

Вот пусть у нас все эти НОДы - n-1 различных чисел. У нас сами числа так-то расположены очень плотно: идут подряд, то есть самое маленькое меньше самого большого всего на n. Тогда как удобно было бы оценить НОД двух чисел?

Подсказка 2

Например, через разность: НОД(a, b) = НОД(b, a-b) ≤ |a-b|. А еще мы знаем, что разность двух наших чисел точно не больше чем n-1....Теперь что можно сказать про все НОДы?)

Подсказка 3

Что все НОДы - это числа от 1 до n-1, да и еще все НОДы совпадают с разностями чисел. Это намекает посмотреть на делимости самих чисел на разность в паре.....

Подсказка 4

Например, выходит что четные разности могут быть только между четными числами. Тогда ясно, что двух рядом нечетных чисел быть не может...Звучит как уже достаточно сильное условие, но давайте еще подумаем: а может ли в таком случае быть много пар соседних чисел вида "чет - нечет"?

Подсказка 5

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

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

Пример. Возьмем числа $36,37,38,39,40$ и расставим их в следующем порядке:

39,36,40,38,37

В этой цепочке НОД первых двух чисел равен $3,$ второго и третьего — $4,$ третьего и четвёртого — $2,$ четвёртого и пятого — $1.$

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

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

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

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

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

Заметим, что пара чисел отличается на нечетное число, только если одно из нечетное, а другое — четное. Но так как четные числа стоят подряд, то нечетные должны стоят по «краям». То есть нечетных чисел не более $2.$ Тогда, если $n ≥6,$ то нечетных чисел хотя бы $3,$ противоречие.

Ответ: 5

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

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

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

Задача 2#68025

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

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Используем факториал!

Подсказка 4

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

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

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

Ответ: да

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

Задача 3#70782

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

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

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

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

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

Подсказка 1

Заметим сразу, что если A-B = p - простому числу, то НОД(A, B) либо 1, либо p. Попробуйте понять, что случай с НОДом равным p - невозможен из-за второго условия)

Подсказка 2

Окей, теперь у нас НОД = 1. Но тогда раз произведение этих чисел - точный квадрат, то что можно сказать про сами числа?

Подсказка 3

Что они сами являются квадратами! А теперь давайте вернемся к тому, что разность этих чисел - простое число. Эти же числа являются квадратами. А разность квадратов хорошо раскладывается на произведение) Что можно отсюда выяснить?

Подсказка 4

Если разложить разность квадратов как (a-b)(a+b), то станет понятно, что она может быть равна простому числу только если a-b = 1. Получается, A и B - просто последовательные квадраты) Остался небольшой перебор и все значения найдены!

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

Пусть $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)

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

Подсказка 1

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

Подсказка 2

Оно лежит между числами, которые заменили на него!(почему?). Тогда становится ясно, что 2017 не получить. А что получить можно и как?

Подсказка 3

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

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

Докажем неравенство $a< √a2-− ab+-b2 <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 .$

Поскольку знаки везде строгие, то мы получаем простое следствие — число $2017$ получиться не может, потому что каждое полученное простое будет меньше $2017.$ Поэтому наибольшее число, которое мы теоретически можем получить, это $2011$ (наибольшее простое меньше, чем $2017$ ).

Теперь покажем, как строится пример: будем последовательно выбирать два наибольших простых числа из всех, игнорируя $2017.$ Так всегда будет оставаться меньшее из этих чисел, поскольку большее остаться не может, при этом на каждом шаге мы рассматриваем два последовательных простых (это доказывается по индукции, поскольку на первом шаге мы оставим $2003$ из пары $2003$ и $2011,$ и так далее). То есть на каждом шаге $√--------- a< a2− ab +b2 < 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$ также можно произвести через теорему косинусов для угла $∘ 60$ (в центре стоит длина третий стороны). При этом важно, что напротив угла в $∘ 60$ всегда лежит средняя сторона треугольника. Также сразу можно определить критерий равенства.

Ответ:

$2011$

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

Задача 5#76739

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

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

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

Подсказка 1

Сначала не очень понятно, каким должно быть n. Нам интересно именно n, так как оно фиксировано и его степень не меняется. Тогда попробуем понять что-то про n. Для этого посмотрим на выражение, если мы поменяем степень у m.

Подсказка 2

Да, если как-то уменьшать степень у m, то это не особо и меняет картину. А если посмотреть на m + n, при условии, что оно делится на mn? Возможно, отсюда получится вывести общий вид n?

Подсказка 3

Верно, можно действовать по индукции! Причем, индукция будет по степени числа m. Из индукции ясно, что n = km²⁰¹⁹. Остаётся разобраться с тем, каким может быть k

Подсказка 4

Да, k+1 должно делиться на km, из условия задачи. Получается, вариантов не так уж и много, ведь k+1 должно делиться на k, а это возможно только при k = 1.

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

Индукцией по $α$ покажем, что если $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$

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

Задача 6#77771

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

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

Подсказка 1

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

Подсказка 2

Верно, нужно разбить числа на группы, так чтобы любые два числа в группе давали в сумме простое число. Если мы верим в светлое будущее, то нам нужно составлять группы из 2 чисел, так как их должно быть в группе хотя бы 2, но если в какой то 3, то будет уже групп меньше, чем если во всех 2 числа. Поэтому надо попробовать разбить числа на группы по 2, так чтобы сумма в каждой была равна простому.

Подсказка 3

Существует такое разбиение: (2, 1), (3, 8), (4, 7), (5, 6), (9, 14), (10, 13), (11, 12), (15, 16), (17, 20), (18, 19). Оценку сверху мы получили. Если взять любые 11 чисел, то этого хватит. А почему нельзя взять только 10? Может быть, есть пример?

Подсказка 4

Верно, можно взять только четные числа. Сумма любых двух будет кратна 2 и больше 2, значит, будет непростое. Оценка снизу тоже есть. Значит, мы нашли ответ!

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

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

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

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

Ответ: 11

Курсы

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

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

Задача 7#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$

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

Задача 8#46230

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

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

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

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

Подсказка 1!

Пусть изначально было n чисел. Давайте запишем условия на математическом языке, то есть системой! Обозначим сумму этих n чисел за Mn

Подсказка 2!

Первое уравнение - (Mn+15)/(n+1) = M + 2, осталось составить второе и дорешать уравнение!

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

Пусть изначально на доске было $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$

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

Задача 9#47215

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

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

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

Подсказка 1

Как не раз говорил ДА, давайте сначала попробуем не целиком пример придумать, а постепенно его сделать. Вот сразу придумать такие числа, чтобы оба числа были модными и при этом делились друг на друга сложно. А можно ли придумать число, которые являлось бы заведомо модным и при этом делилось бы на наше? А как его найти?

Подсказка 2

Искать подобные числа в явном виде, зачастую, затруднительно, потому надо рассматривать набор и в доказывать, что в нем есть такое число. Если число N является k-значным (N-то на что нужно, чтобы делилось), то из набора вида 201600…0,201600…1,….,201699…9(после 2016 идут k-значные числа), по принципу Дирихле можно выбрать такое число, которое будет делиться на N. Пусть оно равно A, при этом, A/N=B. Но вот незадача, В необязательно модное. С другой стороны, если приписать что-то понятное к A, при этом делящееся на N, то можно получить число, которое делится на N, которое модное(из-за того, что содержит в себе A). Осталось так приписать это «что-то», чтобы после деления на N оно было модным.

Подсказка 3

Удобно было бы приписать к A число 2016N. Подумайте , что произойдет после того, как поделить данное число на N и почему вообще оно такое удобное для нас. После этого, задача сама решится:)

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

Пусть мы хотим получить число $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$ — отношение двух модных.

Ответ:

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

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

Задача 10#41297

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

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

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

Подсказка 1

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

Подсказка 2

Вы получили, что 10<x<11. То есть нам осталось перебрать 8 вариантов. При этом если подставить 11 вместо х, то получится значение более близкое к тому, что нам требуется , чем если подставить 10. Что это может значить?

Подсказка 3

Это значит, что искомая дробь ближе к 11 чем к 10. Значит перебор надо начинать сверху(при этом, если мы уже получили решение, не значит, что дальше по перебору не будет еще одного). Осталось перебрать и получить ответ.

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

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

Пусть $[x]$ равна $a$ . Тогда

[ 1 1) x∈ a −2,a+ 2

2x ∈[2a− 1,a+ 1)

4x ∈[4a − 2,4a +2]

[ 5 ) 5x∈ 5a −2,5a

Отсюда

11a − 5= 2a− 1+ 4a − 2+ 5a− 2≤ [2x]+[4x]+ [5x]≤2a+ 1+ 4a+ 2+5a+ 2= 11a+5

Значит, из целых $a$ нам подходит только $[x]= a= 11$ .

Функция $f(x)= [2x]+ [4x]+[5x]$ целая и возрастает скачками, значит осталось найти места, где она возрастает с 119 до 120 и с 120 до 121.

Заметим, что если $x≥ 10.9$ , то $[2x]+[4x]+ [5x]≥ 121$ , если $x< 10.875$ , то $[2x]+[4x]+ [5x]≥ 119$ , если $x∈ [10.875,10.9)$ , то $[2x]+ [4x]+[5x]≥121$ .

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

Давайте число $a$ после округления обозначать $R(a),$ а сумму $R(2x)+ R(4x)+ R(5x)$ обозначим $S.$ Докажем, что $1079 < x< 11.$ Воспользуемся тем, что если $a≤ b,$ то и $R (a)≤ R(b).$ Если $x ≤1079,$ то $( ) ( ) ( ) S ≤R 2159 + R 4319 + R 5389 = 22+43+ 54= 119 <120.$ А если $x≥ 11,$ то $S ≥ R(22)+ R(44)+R(55)=121> 120.$ В указанном интервале есть только одно число со знаменателем $9$ — это $1089.$ Оно подходит: $S = R(2179)+ R(4359)+R (5449) =22+ 44+54 =120.$

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

Ответ:

$98 9$

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

Задача 11#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 баллов.

Интенсивы

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

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

Задача 12#34659

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

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

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

Подсказка 1

Как здорово, что у нас существуют признаки делимости! К сожалению, человечество еще не придумало признака делимости на 495, но может быть, можно как-то решить этот вопрос?

Подсказка 2

Ага, смотрите-ка: если число делится на Х, то оно должно делиться на множители этого Х, а в нашем случае на множители 495! Например, на 5, 9 и 11! А что это значит..?

Подсказка 3

Смотрим, изменилась ли делимость на 5 (смотрим на последнюю цифру), на 9 (смотрим на сумму цифр), на 11 (смотрим на знакопеременную сумму цифр). Задача решена!

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

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

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

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

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

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

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

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