Тема ТЕОРИЯ ЧИСЕЛ

Оценка + пример в задачах по теории чисел

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

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

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

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

Подтемы раздела теория чисел

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

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

Задача 61#78887Максимум баллов за задание: 7

Найдите следующее после $2020$ число, которое оканчивается на $2020$ и делится на $2020.$

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

Заметим, что раз число оканчивается на $2020$ и делится на $2020,$ то делится и на $101.$ Значит, если записать наше число в виде $--- abc2020$ (далее станет понятно, почему трёх цифр перед $2020$ достаточно), то $--- 4 abc⋅10$ должно делиться на $101$ ( $2020$ уже делится и всё число по условию должно делится). При этом $4 10$ взаимно просто со $101,$ но делится на $20,$ а наименьшее число делящееся на $101$ равно $101$ (понятно, что однозначные и двухзначные не подходят). Итого, получаем число $1012020.$

Ответ:

$1012020$

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

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

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

Задача 62#78897Максимум баллов за задание: 7

В строку записано $2020$ натуральных чисел. Каждое из них, начиная с третьего, делится и на предыдущее, и на сумму двух предыдущих. Какое наименьшее значение может принимать последнее число в строке?

Источники: Тургор - 2020, 11.1, устный тур (см. turgor.ru)

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

Подсказка 1

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

Подсказка 2

Докажите, что каждое следующее число должно быть значительно больше предыдущего. Если aₖ делится на aₖ₋₁ и на (aₖ₋₁ + aₖ₋₂), как это ограничивает минимальное значение?

Подсказка 3

Попробуйте взять первые два числа равными 1. Как будет выглядеть последовательность? Почему факториалы — это единственный способ достичь минимального последнего числа?

Подсказка 4

Допустим, для первых k чисел минимальная последовательность — это факториалы. Как доказать, что aₖ₊₁ должно быть не меньше k! ? Используйте условие делимости на сумму двух предыдущих. aₖ₊₁ должно делиться на aₖ + aₖ₋₁ = (k-1)! + (k-2)! = (k-1)·(k-2)! + (k-2)! = k·(k-2)!

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

Пример. Условию задачи, очевидно, удовлетворяют числа $1,1,2!,3!,...,2019!,$ так как при любом натуральном $k$ число $(k+2)!$ делится как на $(k +1)!,$ так и на $(k +1)!+k!= k!(k+ 2).$

Оценка. Пусть $a,b,c$ — три подряд идущих числа в строке, но не первые три числа. Докажем, что $c -b b ≥a +1.$ По условию, $-b c a = x,b = y,$ где $x$ и $y$ натуральные. Тогда $c= by = axy,$ причём $c$ делится на $b+ a= ax+a = a(x+ 1).$ Получаем, что $axy$ делится на $a(x+ 1),$ откуда $xy$ делится на $x+ 1,$ и так как $x$ и $x +1$ взаимно просты, $y$ делится на $x+1,$ то есть $y ≥ x+ 1,$ что и требовалось.

Заметим, что первые два числа не меньше $1$ каждое. Третье число больше второго (так как делится на сумму второго и первого), а значит, хотя бы в два раза больше второго (так как делится на него и не равно ему). По доказанному выше, четвёртое число тогда хотя бы в $3$ раза больше третьего, пятое — хотя бы в $4$ раза больше четвёртого, и так далее, откуда по индукции получаем, что $k$ -е число не меньше, чем ( $k− 1$ )! при всех натуральных $k.$

Ответ:

$2019!$

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

Задача 63#81492Максимум баллов за задание: 7

Какое наибольшее количество нечетных натуральных чисел от $1$ до $3600$ можно покрасить в черный цвет, чтобы нельзя было выбрать такую тройку различных черных чисел $a,b$ и $c,$ что $a$ делится на $b$ и $b$ делится на $c?$

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

Подсказка 1

Попробуйте разбить возможные значения нечётных чисел, меньших либо равных 3600, на семейства.

Подсказка 2

Например, можно рассмотреть n, не кратные 3.

Подсказка 3

Попробуйте в качестве примера придумать геометрическую прогрессию.

Подсказка 4

Нам может пригодиться такая прогрессия для n, не кратного 3: n, 3n, ... , 3ᵏn.

Подсказка 5

Посчитайте, сколько всего есть таких прогрессий, обратите внимание на первый член.

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

Для любого нечётного $n ≤3600,$ не кратного $3,$ рассмотрим геометрическую прогрессию $n,3n,32n,...,3tn.$ Очевидно, что прогрессии, у которых различные первые члены, не имеют общих членов. Также отметим, что любое число от $1$ до $3600$ входит в какую-то прогрессию.

Всего существует $1200$ таких прогрессий и $800$ из них имеют первый член, больший $1200.$ По условию в прогрессии может быть не более двух чёрных чисел. В прогрессий, у которой первый член больше $1200,$ не более одного чёрного числа (потому что их вторые члены уже больше $3600$ ). Поэтому, всего не более $(1200− 800)⋅2+ 800= 1600$ чёрных чисел.

Предъявим пример: покрасим все нечётные числа между $400$ и $3600.$ Предположим, что нашлись такие чёрные числа $a,b,c,$ что $.. a.b$ и $.. b.c,$ тогда $a≥ 3b≥ 9c≥ 9⋅401= 3609> 3600,$ поскольку числа нечётные, противоречие.

Ответ:

$1600$

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

Задача 64#38876Максимум баллов за задание: 7

Внутри шляпы волшебника живут $100$ кроликов: белые, синие и зелёные. Известно, что если произвольным образом вытащить из шляпы $81$ кролика, то среди них обязательно найдутся три разноцветных. Какое наименьшее количество кроликов нужно достать из шляпы, чтобы среди них точно было два разноцветных?

Источники: Школьный этап - 2019, Москва, 11.6

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

Подсказка 1

Перефразируем условие: кроликов любых двух цветов вместе не более 80 (почему?)

Подсказка 2

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

Подсказка 3

Если синие это те, которые идут по своему количеству на втором месте, то в сумме их с красными не менее a + (100-a)/2 (почему?). Какой вывод можно сделать с учетом первой подсказки?

Подсказка 4

a + (100-a)/2 <= 80, значит a <= 60. А теперь вспомним, что a - это наибольшее количество кроликов одного цвета и сделаем из этого выводы)

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

Пусть в шляпе живёт $a$ белых кроликов и их больше всего. Пусть синие кролики вторые по количеству живущие в шляпе. Тогда их хотя бы $100−a 2$ . Из условия следует, что общее количество белых и синих кроликов должно быть не больше $80$ (иначе можно вытащить $81$ кролика, среди которых не найдётся трёх разноцветных) и верно неравенство $100−a a+ 2 ≤ 80$ . Отсюда находим, что $a≤ 60$ . В силу того, что $a$ — это наибольшее количество кроликов одного цвета, это означает, что если произвольным образом вытащить $61$ кролика из шляпы, то среди них точно найдутся два разноцветных. Заметим, что если вытащить $60$ кроликов, то этого может не хватить, например, если в шляпе живут $60$ белых и по $20$ синих и зелёных кроликов.

Ответ: 61

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

Задача 65#42225Максимум баллов за задание: 7

У натурального числа $N$ выписали все его делители, затем у каждого из этих делителей подсчитали сумму цифр. Оказалось, что среди этих сумм нашлись все числа от $1$ до $9$ . Найдите наименьшее значение $N$ .

Источники: Муницип - 2019, Москва, 8.5

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

Подсказка 1

Вспомним, что сумма цифр неразрывна связана с признаком делимости на 3 и на 9, поэтому что можно сказать про наше число N?

Подсказка 2

Верно, N делится на 9, а значит уже можно перебирать числа все числа кратные 9 и надеяться, что через небольшое время найдётся то самое наименьшее подходящее. Но можно попытаться ещё сократить перебор! Для этого нам нужно найти такой делитель d, который был бы взаимно прост с 9, т.е. не делился бы на 3, чтобы мы могли проверять только числа вида 9dk, где k - натуральное число. А какой признак нам поможет сказать, что число не делится на 3?)

Подсказка 3

Можно снова воспользоваться, тем, что если сумма цифр числа НЕ делится на 3, то и само число НЕ делится на 3. Тогда каким свойством может обладать d?

Подсказка 4

Например, 8 не делится на 3, а значит можно взять d с суммой цифр 8, остаётся только перебрать все числа d с суммой цифр 8 в порядке возрастания.

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

Заметим, что у числа $288$ есть делители $1,2,3,4,32,6,16,8,9.$ Поэтому это число удовлетворяет условию задачи. Докажем, что меньшего числа, удовлетворяющего условию, не существует.

Действительно, так как $N$ должно иметь делитель с суммой цифр $9$ , то $N$ делится на $9.$ Рассмотрим теперь делитель $d$ с суммой цифр 8. $d$ не делится на $3,$ поэтому числа $d$ и $9$ — взаимно простые, значит, $N$ делится на $9d.$ При этом, если $d≥ 32$ , то $9d≥ 288$ , то есть $2N ≥288.$ Значит, остается проверить $d= 26,d= 17$ и $d= 8$ . Если $d= 26$ , то $9d= 234.$ У этого числа нет делителя с суммой цифр 5, а любое число, ему кратное, больше, чем $288.$

Если $d= 17$ , то $9d =153.$ У этого числа нет делителя с суммой цифр 2 , а любое число, ему кратное, больше, чем $288.$

Если $d= 8$ , то $9d= 72$ . Ему кратные и меньшие, чем 288 - это 144 и 216. Но у этих чисел нет делителя с суммой цифр $5.$

Ответ: 288

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

Задача 66#49163Максимум баллов за задание: 7

По кругу записаны $2019$ чисел. Для любых двух соседних чисел $x$ и $y$ выполняются неравенства $|x− y|≥ 2,x +y ≥6$ . Найдите наименьшую возможную сумму записанных чисел.

Источники: Звезда - 2019 (см. zv.susu.ru)

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Скажем, если бы нашлись три подряд идущих числа x,y,z : x>=y>=z , то что бы это дало? Как бы мы могли оценить такую тройку чисел?

Подсказка 4

Да, мы могли бы сказать, что y-z>=2 , y+z>=6 => y>=4. Однако, так же можно оценить x>=y+2>=6 , но при этом y+z>=6, значит x+y+z>=12. То есть, сумма чисел в этой тройке хотя бы 12. И также, мы можем оценить по парам остальные числа(которых четное кол-во). Но остается один вопрос, а правда, что найдутся три таких подряд идущих числа, что x>=y>=z?

Подсказка 5

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

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

Всего чисел нечётное количество, поэтому найдутся такие три подряд идущих числа $x,y,z$ , что $x ≥y ≥z$ . Тогда $y− z ≥ 2,y+ z ≥ 6$ , откуда $y ≥ 4$ . Отсюда $x≥ y+ 2≥ 6$ , то есть хотя бы одно из чисел не меньше $6$ . Остальные разбиваем на пары (в каждой паре сумма не меньше $6$ ) и получаем, что сумма чисел по всему кругу не меньше $6+1009⋅6= 6060$ .

В качестве примера рассмотрим последовательность

...4,2,6,4,2,4,2,4,2,4,2...

Ответ:

$6060$

Курсы

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

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

Задача 67#92083Максимум баллов за задание: 7

Известно, что дробь $m(n+-69m) n(m +69n)$ сократимая для некоторых взаимно простых целых чисел $m$ и $n$ . Найти наибольшее простое число $d$ , на которое делится числитель и знаменатель дроби.

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

Подсказка 1

Если дробь A/B сократима на d, это значит, что и числитель A, и знаменатель B делятся на d без остатка. Запишите это по-умному.

Подсказка 2

Раз у нас d делит произведения, давайте рассмотрим возможные комбинации. Всего их четыре.

Подсказка 3

Посмотрите на условие: m и n — взаимно простые. Может ли у них быть общий простой делитель d? Подумайте, что это значит.

Подсказка 4

Вспоминаем важный приём из теории чисел: если d | a и d | b, то d делит и их линейную комбинацию (например, сумму). Примените это здесь.

Подсказка 5

Если d делит (m + 69n) и d делит m, то d делит их разность ((m + 69n) - m) = 69n. Мы знаем, что d простое. Может ли d делить n?

Подсказка 6

Разложите 69 на простые множители и сделайте вывод, каким может быть d. Разберите симметричный случай.

Подсказка 7

В последнем случае надо доказать, что d не может делить n, и тогда d будет делить (69² - 1). Разложите это число на простые множители.

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

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

Если $m$ делится на $d$ , и $m+ 69n$ делится на $d$ , то и их разность делится на $d$ , поэтому $69n$ делится на $d$ , но $n$ взаимно просто с $m$ , следовательно и с $d$ . Откуда $69 =3 ⋅23$ делится на $d$ , значит, $d≤ 23$ .

Случай: $n$ делится на $d$ , и $n+ 69m$ делится на $d$ разбирается аналогично.

Если же $n +69m$ и $m + 69n$ делятся на $d$ , то и число $( 2 ) 69(n+ 69m)− (m + 69n)= m 69 − 1$ делится на $d$ .

Случай, когда $m$ делится на $d$ был рассмотрен выше. Значит, можно считать, что $2 3 69 − 1= 68⋅70 =17⋅2 ⋅5⋅7$ делится на $d$ , откуда в этом случае $d≤ 17 <23$ .

Осталось привести пример на $d =23$ . Подходят $m =23,n= 1$ .

Ответ: 23

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

Задача 68#96562Максимум баллов за задание: 7

Назовём трёхзначное число интересным, если хотя бы одна его цифра делится на $3.$ Какое наибольшее количество подряд идущих интересных чисел может быть? Приведите пример и докажите, что больше чисел получить нельзя.

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

Числа $289,290,...,299,300,...,399,400,...,409,410$ являются интересными (напомним, что 0 делится на 3), и их всего 122. Докажем, что большего количества быть не может.

Предположим, что нам удалось найти большее количество подряд идущих интересных чисел; выберем из них 123 подряд идущих. Назовём сотню подряд идущих чисел, у которых разряд сотен одинаков и делится на 3, интересной сотней. Заметим, что до любой интересной сотни идут только 11 интересных чисел, оканчивающихся на $89,90,...,99$ , а 12-е число оканчивается на 88 и интересным не будет. Аналогично после интересной сотни идут тоже только 11 интересных чисел, оканчивающихся на $00,...,09,10$ , а 12-е число оканчивается на 11 и также не интересное.

Если наша последовательность из 123 чисел пересекается с некоторой интересной сотней, то она содержит хотя бы 12 чисел либо до, либо после этой сотни. Следовательно, хотя бы одно число в ней не интересное.

Если же наша последовательность из 123 чисел не пересекается с интересной сотней, то она содержит хотя бы одно число, оканчивающееся на 55 (как и на любую другую комбинацию цифр). Но это число не интересное, так как ни один разряд в нём на 3 не делится.

Ответ: 122

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

Задача 69#73723Максимум баллов за задание: 7

Пусть $x$ и $y$ — пятизначные числа, в десятичной записи которых использованы все десять цифр ровно по одному разу. Найдите наибольшее возможное значение $x,$ если $∘ ∘ ∘ ∘ tgx − tgy = 1+ tgx tgy$ ( $∘ x$ обозначает угол в $x$ градусов).

Источники: ММО-2018, задача 11.3(см. mmo.mccme.ru)

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

Подсказка 1

С равенством в первоначальном виде работать трудно. Попробуйте его преобразовать.

Подсказка 2

Вспомните базовые тригонометрические формулы. В какой встречается разность тангенсов и сумма их произведения с единицей?

Подсказка 3

Как насчёт формулы тангенса разности?

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

Данное равенство при условии, что $tgx∘$ и $tgy∘$ определены, эквивалентно равенству $tg(x − y)∘ = 1,$ откуда $x − y = 45+ 180n,$ где $n ∈ℤ.$ Следовательно, разность $x − y$ делится нацело на $45,$ а значит, на $5$ и на $9.$ Поскольку сумма всех цифр делится на $9,$ то каждое из чисел $x$ и $y$ делится на $9.$

Наибольшее пятизначное число, все цифры которого различны, равно $98765.$ Ближайшее к нему меньшее число, делящееся на $9,$ равно $98757$ и содержит повторяющиеся цифры. Последовательно уменьшая это число на $9,$ получаем числа $98748,98739,98730,98721.$ Первые два из них также содержат повторяющиеся цифры. Третье состоит из различных цифр, но поскольку $98730= 90 +180⋅548,$ то его тангенс не определён. Число $x =98721$ также состоит из различных цифр. Если взять, например, $y =54036,$ то получим $x − y = 44685 =45+ 180⋅248,$ поэтому число $98721$ искомое.

Ответ:

$98721$

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

Задача 70#78812Максимум баллов за задание: 7

Найдите наименьшее натуральное $k$ такое, что для некоторого натурального числа $a,$ большего $500000,$ и некоторого натурального числа $b$ выполнено равенство $1 -1- 1 a + a+k = b.$

Источники: Олимпиада Эйлера, 2018, ЗЭ, 2 задача(см. old.mccme.ru)

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

Подсказка 1

Обозначим за c сумму a и k, за d нод a и c, тогда есть представления a=da₁ и c=dc₁. Приведём дроби к общему знаменателю, чтобы выразить сумму. Что получаем?

Подсказка 2

Получаем 1/b равна дроби с числителем a₁+c₁ и знаменателем da₁c₁. Отсюда можно сделать вывод о делимости d на a₁+c₁,тогда d² больше либо равно a+c. Какую оценку на d можно получить?

Подсказка 3

Верно, поскольку a+c больше 10⁶, d больше либо равно 1001, соответственно и k больше либо равно 1001. Получили оценку, осталось построить пример.

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

Оценка. Положим $a +k =c$ и НОД $(a,c)= d.$ Тогда $a= da ,c= dc 1 1$ и $1+ 1= a1+c1. a c da1c1$ Так как числа $a c 11$ и $a + c 1 1$ взаимно просты, $d$ должно делиться на $a1+ c1.$ Поэтому $d ≥a1+ c1$ и $2 6 d ≥d(a1+ c1)= a+ c> 10 ,$ откуда $d≥ 1001$ и $k =d(c1− a1)≥ 1001.$

Пример. $--1-- --1-- --1-- a =500500,k= 1001 :500500 +501501 = 250500.$

Ответ:

$k =1001$

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

Задача 71#81384Максимум баллов за задание: 7

Имеется натуральное $1001$ -значное число $A.$ $1001$ -значное число $Z$ — то же число $A,$ записанное от конца к началу (например, для четырёхзначных чисел это могли быть $7432$ и $2347$ ). Известно, что $A> Z.$ При каком $A$ частное $A∕Z$ будет наименьшим (но строго больше $1$ )?

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

Подсказка 1

Пусть A = a₁₀₀₀a₉₉₉...a₀. (Где a_i — цифры). Что можно сказать про a₀, a₁,..., a₄₉₉, учитывая A > Z?

Подсказка 2

Верно! Они не могут быть все девятками! Теперь уже легко указать максимальное значение Z. Какое?

Подсказка 3

Правильно! 9...989...9 (в начале 499 девяток, а в конце 501 девятка). Обозначим за Z₀ это число. Теперь будем пытаться оценить A - Z снизу. Для начала давайте поймём, как действовать, если мы найдем точную оценку на A - Z снизу, и она будет достигаться при Z = Z₀.

Подсказка 4

Останется только вычесть из дроби A/Z единицу, подставить Z₀ и получить ответ. Какая оценка на A - Z напрашивается, если мы хотим равенство при Z = Z₀?

Подсказка 5

Верно! 10⁵⁰¹ - 10⁴⁹⁹. Давайте будем доказывать эту оценку. Для удобства введем обозначения φ_n = a_{501 + n} - a_{499 - n} и △_n = 10⁵⁰¹⁺ⁿ - 10⁴⁹⁹⁻ⁿ. Как тогда записывается число A - Z?

Подсказка 6

Ага! A - Z = φ₄₉₉△₄₉₉ + ... + φ₁△₁ + φ₀ △₀. Прежде чем оценивать это выражение, давайте попробуем оценить снизу отношение △_{i +1} / △_i.

Подсказка 7

Оно всегда больше 10. Пусть j — максимальный индекс такой, что φ_j ≠ 0. Попробуйте написать оценку на |φ_j△_j + ... + φ₁△₁ + φ₀ △₀| используя неравенство треугольника и нашу оценку на отношение △_{i +1} / △_i. Также стоит помнить, что φ_i является разностью цифр, а, значит, не больше 9.

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

Первое решение. Пусть $A = a--a---...a. 1000 999 0$ Поскольку $A >Z,$ среди цифр $a,a ,...,a 0 1 499$ есть хотя бы одна недевятка. Значит, $Z ≤ Z0 = 99◟. ◝4.◜99.9◞89◟95..◝◜0.19◞.$ Покажем, что $501 499 A − Z ≥10 − 10 .$ Отсюда будет следовать, что

A 10501− 10499 Z-− 1≥ ----Z0----

Эта оценка достигается при $Z =Z0,$ что и даёт ответ. Имеем

( ) ( ) ( ) A− Z =(a1000− a0) 101000− 1 + (a999− a1) 10999− 10 + ⋅⋅⋅+ (a501− a499)10501− 10499 =

= φ499Δ499+φ498Δ498 +⋅⋅⋅+ φ0Δ0

где $φi =a501+i− a499−i$ и $501+i 499−i Δi = 10 − 10$ при $i= 0,1,...,499.$ Заметим, что $Δi+1 > 10Δi.$ Пусть $j−$ наибольший индекс, при котором $φj ⁄= 0.$ Тогда

|φjΔj + φj−1Δj−1+ ⋅⋅⋅+ φ0Δ0|≥|φjΔ(j|− |φj−1Δj−1|− ⋅⋅⋅− |φ)0Δ0|≥ ≥Δj 1− 9-− -9-− ⋅⋅⋅− -9j- = Δjj ≥ Δ0 10 100 10 10

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

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Ясно, что можно минимизировать (положительное) число $AZ-− 1= A−ZZ.$ Пронумеруем цифры в $A$ слева направо $a ,a,...,a . 1 2 1001$ Пусть $k$ — наименьший номер, для которого $a ⁄= a k 1002−k$ (тогда $k≤ 500$ и $a >a , k 1002−k$ ибо $A > Z$ ).

Рассмотрим произвольный оптимальный пример. Заменим первые и последние $k− 1$ цифр на девятки. $A− Z$ не изменится, $Z$ не уменьшится, то есть наша дробь не увеличится. По этой же причине $a501$ можно заменить на $9.$ Заменим $ak$ на $9,$ а $a1002−k$ на $8.$ При этом $A− Z$ не увеличится, а $Z$ не уменьшится. Заменим все цифры $ak+1,...,a500$ на нули, а $a502,...,a1001−k$ на девятки. Тогда $A − Z$ не увеличится, а $Z$ если и уменьшится, то на меньшую величину (это произойдёт только тогда, когда вторая половина и так была девятками!). Поскольку в оптимальном примере $A− Z <Z$ (в первом просто меньше цифр), то, ясно, $A−Z- Z$ не возрастёт. Итак, можно считать, что $A$ имеет вид

9◟9.◝.◜.9 ◞0◟0.◝.◜.0◞999◟ ◝..◜.9◞89◟9..◝◜.9◞ k 500−k 500−k k−1

В этом случае

501 500 k k−1 A − Z = 10 +10 − 10 − 10

Это выражение достигает минимума при $k= 500,$ и при этом же $k$ достигается максимум значения рассматриваемых $Z.$ Значит, это и есть ответ.

Ответ:

При $A,$ запись которого (слева направо) такая: $501$ девятка, восьмёрка, $499$ девяток

Интенсивы

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

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

Задача 72#82709Максимум баллов за задание: 7

Найдите такое наименьшее натуральное число, что его половина есть пятая степень некоторого целого числа, а пятая часть есть квадрат некоторого целого числа.

Источники: ПВГ 2018

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

Подсказка 1

Запишите условие задачи в форме системы уравнений.

Подсказка 2

Воспользуйтесь тем, что 2 и 5 — взаимно простые числа.

Подсказка 3

Проанализируйте делимость искомого числа на 2 и 5 и представьте его в виде 2ᵏ5ᵐtⁿ.

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

Пусть $n$ — число, удовлетворяющее условию задачи. Тогда существуют такие целые числа $p$ и $s,$ что верна система

{ 1n =p5 21 2 5n =s

Умножаем на $2$ и $5$ соответственно первое и второе уравнение. Система приобретает вид

{ n =2p5 n =5s2

Из первого получаем, что $n ... 2.$ Тогда из второго уравнения, так как числа 2 и 5 взаимно просты, следует, что $s2 ... 2,$ то есть $s ... 2,$ и, стало быть, $. n .. 4.$ Аналогично получаем, что $. 55.. n.$

Пусть $n= 22 ⋅55k.$ Подставим в систему

{ 22⋅55k = 2p5 22⋅55k = 5s2

Сокращаем на 2 и 5 уравнения соответственно

{ 2⋅55k= p5 22⋅54k= s2

Из первого уравнения получаем, что $2 ... p,$ следовательно, $k ... 24.$ Наименьшее $k,$ удовлетворяющее этому условию равно $4 2 .$ Пусть $4 k= 2 ,$ тогда $6 5 n = 2⋅5 .$ Видим, что оно удовлетворяет системе, значит, это и есть нужное минимальное число.

Ответ:

$26⋅55$

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

Задача 73#95546Максимум баллов за задание: 7

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

Источники: Лига открытий - 2018

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

Пример. $1,3,9,27,54,108,216,432,2160.$

Оценка. На последнем месте могут быть $10$ различных цифр. Пусть $10$ возможно. После четного числа могут идти только четные, значит нечетные идут вначале. Но если среди них есть число, оканчивающееся на $5,$ то следующее число может оканчиваться только на $0,$ других четных не будет, и чисел вообще не больше шести.

Ответ:

$9$ чисел

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

Задача 74#96249Максимум баллов за задание: 7

В стопке было $9$ карточек с цифрами от $1$ до $9.$ Из двух каких-то карточек склеили одну, на которой теперь написано двузначное число. Потом карточки (их теперь восемь) разложили на две стопки. Оказалось, что произведение чисел в первой стопке в полтора раза больше произведения чисел во второй стопке. Какое число написано на склеенной карточке? Переворачивать $6$ и $9$ нельзя.

Источники: Лига открытий - 2018

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

Если цифра $5$ остается в разряде единиц, то произведение в одной части делится на $5,$ а в другой — не делится. Следовательно, цифра $5$ будет в разряде десятков. Склеить $57$ нельзя, так как это число делится на $19,$ а произведение чисел в другой стопке не будет делиться. Поэтому цифра $7$ остается в виде однозначного числа. Так как произведение в обоих стопках должно делиться на $7,$ а единственное двузначное число, начинающееся на $5$ и делящееся на $7$ — это $56,$ то склеили именно $56.$

Ответ:

$56$

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

Задача 75#48591Максимум баллов за задание: 7

Рассматриваются всевозможные наборы, которые состоят из $2017$ различных натуральных чисел и в каждом из которых ни одно из чисел нельзя представить в виде суммы двух других чисел этого набора. Какое наименьшее значение может принимать наибольшее число в таком наборе?

Источники: Ломоносов-2017, 11.8 (см. olymp.msu.ru)

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

Подсказка 1

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

Подсказка 2

Существует такой пример(который основывается на идее пред. подсказки): {2016,2017,….,4032}. Он, очевидно, подходит. Осталось доказать оценку на 4032. В предыдущем пункте мы взяли именно наибольшее число. Во-первых, потому что оно понятное, то есть это не какое-то там число, которое не понятно где стоит, а самое наибольшее. Во-вторых, как-будто именно с ним и может быть больше всего проблем, так как именно его можно получить наибольшим кол-вом способов и именно оно дает нам больше всего запретов на некоторые пары чисел в наборе.

Подсказка 3

Думается, нужно попробовать как-то разбить на пары , в соответствии с максимальным числом набора, остальные числа, и получить желаемую оценку. Вот если у нас число максимальное 2023 , к примеру, то можем ли мы взять 1 и 2022 , оба числа? А допустим 4 и 2019? 1022 и 1001? Видите закономерность? А если наибольшее число - это А?

Подсказка 4

Да! Если наибольшее число-это А, то мы не можем одновременно взять x и A-x! Значит нужно при доказательстве оценки разбивать числа на пары вида x и A-x. Из каждой пары тогда можно взять не больше одного(и это мы используем только противоречие с наибольшим числом, а в теории два каких-то числа в сумме могут дать не наибольшее). Попробуйте построить на этом доказательство оценки(напомню, что вы хотите доказать, что А>=4032, то есть предполагать нужно обратное).

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

Заметим, что нам подойдёт набор ${2016,2017,...4032}$ , в которым максимальным будет $4032$ . Пусть нам удалось найти какой-то меньший ответ $A≤ 4031$ . Поделим числа на пары $(1,A− 1),(2,A − 2),...$ . Таких пар будет не более $4031 ⌊ 2 ⌋= 2015$ (пара $(A∕2,A∕2)$ нас тоже устроит), при этом в парах учтены все элементы, меньшие $A$ . Из каждой пары мы можем взять не более одного элемента, откуда с учётом $A$ чисел не больше $2016$ . Значит, $A ≥ 4032$ .

Ответ:

$4032$

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

Задача 76#77771Максимум баллов за задание: 7

Найдите наименьшее возможное число $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

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

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

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

Задача 77#92482Максимум баллов за задание: 7

Каждую букву русского алфавита закодировали последовательностью из нулей и единиц (последовательности могут быть разной длины). Используя этот код, Сеня записал слово “ЛИГА”. Оказалось, что полученная последовательность нулей и единиц расшифровывается однозначно. Какое наименьшее количество цифр могло в ней быть?

Источники: Лига открытий - 2017

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

Оценка. Если цифр не больше $6,$ то какие-то две из четырёх букв должны быть закодированы последовательностью длины $1,$ т. е. одна из них закодирована цифрой $0,$ а другая — цифрой $1.$ Но тогда наша последовательность имеет расшифровку, в которой участвуют только эти две буквы, что противоречит условию.

Пример. Закодируем буквы, например, так: Л — $10,$ И — $11,$ Г — $0,$ А — $01,$ все остальные буквы закодируем разным количеством единиц, большим $3.$ Нашему слову будет соответствовать последовательность $1011001.$ Буквы, закодированной “ $1$ ”, нет, а буква, начинающаяся с “ $10$ ”, ровно одна — “ $10$ ”. Таким образом, первая буква однозначно восстанавливается. Так как не существует буквы, начинающейся с “ $110$ ”, вторая буква тоже расшифровывается однозначно. Буквы, код которой начинается с “ $00$ ”, нет, поэтому третья буква закодирована символом “ $0$ ”. Если код четвёртой буквы — “ $0$ ”, то пятая буква должна быть закодирована символом “ $1$ ”, а таких букв нет, значит, четвёртая буква закодирована “ $01$ ”.

_________________________________________________________________________________________________________________________________________________________________________________

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

Ответ:

$7$ цифр

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

Задача 78#93380Максимум баллов за задание: 7

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

Источники: Лига открытий - 2017

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

Разобьём цифры на пары: ${9,8},{7,4},{6,5},{3,0},{2,1}.$ В каждой паре сумма чисел является простым числом. Таким образом, в искомом числе имеется не более одной цифры из каждой пары, а значит, оно не более чем пятизначное. Из разбиения на пары следует, что наибольшие первые две цифры — $9$ и $7.$ Так как $6 +7= 13$ — простое число, то третья цифра не больше $5.$ Максимальная из оставшихся цифр — $3.$ Из последней пары приходится выбрать $1,$ так как $2+3 =5$ — простое число.

Ответ:

$97531$

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

Задача 79#93535Максимум баллов за задание: 7

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

Источники: Лига открытий - 2017

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

Если первое из чисел оканчивается не на $9,$ то суммы цифр отличаются на $1.$ Таких пар соседних квадратов нет. Если первое число оканчивается на $k$ девяток, то суммы цифр отличаются на $9k − 1.$ Разность последовательных квадратов нечетна, поэтому $k$ — чётно. При $k= 2$ первая такая пара соседних квадратов — $64$ и $81,$ и наименьшие числа с такой суммой цифр приведены в ответе. При $k≥ 4$ количество цифр в числах будет больше, а значит, и сами числа будут больше.

Ответ:

$1999999899,1999999900$

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

Задача 80#93730Максимум баллов за задание: 7

Какое наименьшее количество подряд идущих четырехзначных чисел нужно записать, чтобы в их записи встретились все цифры хотя бы по разу?

Источники: Лига открытий - 2017

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

Пример. Подходят числа $5679,5680,5681,5682,5683,5684.$

Оценка. Покажем, что $5$ чисел не хватит. Если в этой пятерке нет перехода между разрядами, то первые три цифры этих четырехзначных чисел одинаковые, а различаются лишь последние цифры. Итого не более $3 +5 =8$ различных цифр.

Пусть переход есть, тогда он всего один. Первое число после перехода оканчивается на несколько нулей, а следующие отличаются лишь одной цифрой. Значит, каждое из них добавляет лишь одну новую цифру. А первое число после перехода отличается от предыдущего не более, чем двумя цифрами: $9$ меняется на $0,$ а также одна из цифр увеличивается на $1.$ Итого получаем, что если до перехода было $a$ чисел, а после перехода — $5− a,$ то различных цифр не более $3+ a+ 2+ (5− a− 1)= 9.$

Ответ:

$6$