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

Оценка. Так как любые два записанных числа взаимно просты, то каждое из простых чисел 2, 3, 5 и 7 может войти в разложение на множители не более, чем одного из них. Если на доске пять или более чисел, то все простые множители в разложении какого-то из них должны быть не меньше чем 11. Но это составное число, значит, оно не меньше чем 121. Это противоречит условию. Следовательно, на доске записано не более четырёх чисел.

Пример. 25, 26, 33, 49.

Пусть — сумма цифр числа Тогда суммы цифр полученных чисел будут равны …, Три из этих сумм будут делиться на По признаку делимости на соответствующие три числа на доске также будут делиться на При этом они будут больше а значит, будут составными. Поэтому больше 6 простых чисел на доске оказаться не может.

Шесть простых чисел может оказаться даже при — например, если Петя получит, среди прочих, числа и

Пусть всего шариков . Тогда (оно должно быть кратно ). Зелёных и красных вместе оранжевых и голубых — а синих и жёлтых Если фиолетовых то имеем

Если то откуда фиолетовых хотя бы Всех шариков будет целое число и в сумме они дадут потому можем писать ответ.

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

Если их ровно , то в силу условий выше мы можем сделать только набор

(иначе найдётся чисел, в которых суммарная степень больше, чем у оставшихся чисел)

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

Пример на простых чисел построим так: обозначим и рассмотрим

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

_________________________________________________________________________________________________________________________________________________________________________________

Замечание.

Для простых пример (где ) уже не сработает, ведь можно взять набор

произведение чисел которого содержит множитель в сотой степени и не делит произведение оставшихся чисел.

Очевидно, не подходит, поэтому нечётно. Поскольку сумма всех чисел равна она делится на Значит, либо количество блоков делится на либо сумма чисел в каждом блоке делится на Первый случай невозможен, поскольку тогда блоков ровно и они все состоят из одиночных чисел, а значит, во всех блоках разные суммы. Следовательно, сумма чисел в каждом блоке делится на Рассмотрим первый блок, пусть последнее число в нём равно тогда сумма чисел в этом блоке равна и она делится на Это возможно, только если Тогда второй блок состоит лишь из числа и должно выполняться равенство поэтому Это возможно:

Сумма чисел от до равна . Если стереть хотя бы одно число, то сумма оставшихся чисел не превосходит . Давайте последовательно перебирать варианты:

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

2) Если сумма то стереть Даша могла только число тогда оставшиеся числа можно разбить на три группы с суммой :

3) Если сумма то стереть Даша могла только число тогда оставшиеся числа можно разбить на две группы с суммой :

4) Если сумма то стереть Даша могла только число тогда оставшиеся числа можно разбить на пять групп с суммой :

5) Если сумма то стереть Даша могла только число тогда оставшиеся числа можно разбить на две группы с суммой :

6) Если Даша стёрла число то на доске остались числа с суммой их можно было бы разбить или на групп с суммой , или на групп с суммой , или на группы с суммой в какую-то группу попадёт число поскольку вариантов с суммой у нас нет, то в эту группу попадёт ещё хотя бы одно число: поэтому сумма в этой группе будет хотя бы значит, в этом случае разбить числа на группы с одинаковой суммой не получится.

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

Для есть пример:

Пусть наименьшее подходящее число имеет вид Из условия следует, что среди его цифр нет и Если в числе есть цифры или то их можно заменить на или соответственно и получить меньшее число с тем же свойством. Таким образом, искомое число состоит из цифр от до

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

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

Поскольку не делится на заключаем, что делится на поэтому наименьшее возможное равно Таким образом, наименьшее возможное число состоит не менее чем из восьми знаков. Остается заметить, что число удовлетворяет условию задачи, а поскольку оно начинается с то это число и будет наименьшим.

Запись 00000 на экране появиться не может, поскольку она может получиться только из 00000 . Запись из четырёх нулей и единицы тоже не может, поскольку тогда последняя цифра не равна остатку от деления суммы четырёх первых на 10.

А вот сумма цифр 2 возможна. Например, “обратным ходом” можно найти пример получения записи 00011 (или 10001):

Составив наименьшую сумму чисел А и Б, а также наибольшее число В, мы получим наименьшее значение выражения А + Б - В: . Но такое разбиение не подходит: у двух чисел есть одинаковые цифры. Поменяв в разряде единиц местами цифры 6 и 8 получим нужное разбиение: . Почему такое разбиение - лучшее? При любом другом варианте расстановки в разряде сотен цифр мы получим вклад сотен, равный 200 , или . А в разрядах десятков и единиц мы получим положительные значения, так как сумма любых двух из цифр больше любой третьей цифры. Значит, число А + Б - В будет больше 200. Итак, А и Б начинаются с цифр 5 , а В - с цифры 9. Аналогично получаем, что вторые цифры чисел А и Б должны быть 6 , а числа В - 8. Про единицы сказано выше.

Докажем, что к 6-значному числу , меньшему 888 888, все цифры которого чётны, можно добавить число, не большее 111112 так, что вновь все его цифры будут чётные. Если среди цифр числа , кроме первой, есть цифра, меньшая 8 , то можно увеличить её на 2. В противном случае число имеет вид . Так как , то к нему можно добавить 111112 и получится . Если же , то все большие 6-значные числа содержат в себе нечётную цифру, поэтому среди них не может найтись подходящее число .

Осталось проверить, что разность 111112 бывает. Рассуждения из оценки подсказывают, что примером могут быть числа и . И правда: у любого числа между ними есть или цифра 3, или цифра 9.

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

или, что то же самое,

Разложив обе части на множители, придем к соотношению

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

Например, можно положить

и Тогда первые два равенства будут выполнены по определению; с другой стороны, делит делит поэтому из равенства произведений вытекают написанные равенства.

Следовательно,

Таким образом, число представляется в виде произведения двух натуральных чисел, больших 1, и, значит, не является простым.

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

имеет три делителя.

_________________________________________________________________________________________________________________________________________________________________________________

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

Будем считать, что Тогда число

делится на и меньше, чем Следовательно, число

положительно и кратно Тогда первая скобка положительна и

поэтому она не делится на Вторая скобка также положительна и

поэтому она также не делится на Мы пришли к противоречию, поэтому предположение неверно. Таким образом, — составное число и, значит, оно имеет хотя бы три делителя.

Итак, почему вообще это задача на оценку и пример? Нас просят найти ближайший год, поэтому, кроме ответа (примера), нужно объяснение, почему более близкие года нам не подойдут.

Рассказ решения в таких задачах разумно начать с ответа, чтобы люди знали, что мы вообще собираемся доказывать. Итак, наш ответ 2031, и сразу убедимся, что он подходит.

Теперь докажем, что меньшие числа не подойдут. Сейчас 2020-й год, поэтому нужно проверить числа от 2021 до 2030. Заметим, что числа от 2021 до 2029 будут содержать две двойки, значит, они нам не подходят. Число 2030 содержит два нуля, значит, тоже не подходит.

Итак, мы доказали, что более близких вариантов, чем 2031, нет, поэтому мы можем быть уверены, что это ближайшие год. Задача решена.

Заметим, что чисел больше , поскольку сумма квадратов меньше суммы модулей, которая меньше .

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

То есть чисел хотя бы . В качестве примера рассмотрим числа (по каждого вида).

Оценка. Вычислим сумму наименьших нечётных натуральных чисел: Значит, слагаемых меньше, чем , но сумма нечётных слагаемых является чётным числом, поэтому слагаемых не больше, чем

Пример.

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

Так как нечётно, то каждый из сомножителей и чётен. При этом одно из чисел или делится на 4 , поэтому произведение трёх этих сомножителей делится на

Осталось показать, что если число больше, чем , то оно не удовлетворяет условию. Заметим, что разность степеней любых простых чисел, больших , должна делиться на Возьмём сначала простые числа 13 и 11 и вычислим разность их четвёртых степеней: Теперь возьмём числа 17 и 11: Поскольку , то не может быть больше, чем

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

Теперь приведём алгоритм, как получить 2011: будем последовательно выбирать два наибольших простых числа из всех, игнорируя Так всегда будет оставаться меньшее из этих чисел, поскольку большее остаться не может, при этом на каждом шаге мы рассматриваем два последовательных простых (это доказывается по индукции, поскольку на первом шаге мы оставим из пары и и так далее). То есть на каждом шаге при этом — последовательные простые, поэтому между ними других простых нет и мы будем выбирать

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

_________________________________________________________________________________________________________________________________________________________________________________

Замечание.

Можно чисто алгебраически доказать неравенство при условии Для этого достаточно возвести его в квадрат и использовать откуда сразу же получаем требуемое

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

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

Докажем, что число не может быть покрашено. Действительно, пусть например, синее, тогда красное, синее, красное. Заметим, что не может быть ни красным, ни синим: если красное, то в пример входят три красных числа, а если синее, то в пример входят три синих числа.

Пример. Числа от до покрасим синим, числа от до — красным, числа от до — снова синим.

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

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

Покажем, что полученная оценка реализуется. Покрасим числа а также все числа от до Пусть и — зеленые числа. Нам достаточно проверить, что не является степенью двойки. Если то это очевидно. В случае мы получаем

Наконец, если и то