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

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

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

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

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

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

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

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

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

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

Задача 1#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,$ то в выбранной паре произведение чисел делится на их же сумму.

Ответ: да

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

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

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

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

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

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

Пример. Возьмём числа $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)

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

Подсказка 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.$ После нескольких операций на доске осталось одно число. Какое максимальное значение оно может принимать?

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

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

$√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 в синий и красный цвета так, чтобы оба цвета встречались и произведение всех красных чисел было взаимно просто с произведением всех синих чисел.

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

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

Ответ: 62

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

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

Курсы

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

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

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

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

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

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

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

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

Задача 10#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$ — отношение двух модных.

Ответ:

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

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

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

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

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