Теория чисел на ОММО

Рассмотрим следующую последовательность чисел:

На нечетных позициях стоит последовательность чисел от 1014 до 2027, на четных — последовательность чисел от 1 до 1013. Покажем, что этот пример удовлетворяет условию задачи.

Пусть тогда перепишем ряд в следующем виде:

Покажем делимость на сгруппируем крайние члены:

Каждая такая сумма кратна что и требовалось.

Покажем теперь делимость на вычислим частичную сумму этого ряда:

По формуле суммы арифметической прогрессии получаем

где каждое слагаемое делится на

Обозначим числа, стоящие рядом с точками на окружности, как:

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

Теперь рассмотрим следующее выражение:

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

Тогда

Итак, максимальное значение равно 18.

Пример. для всех

Обозначим числа, стоящие рядом с точками на окружности, как:

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

Теперь рассмотрим следующее выражение:

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

Тогда

Итак, максимальное значение равно 50.

Пример. для всех

Разобьем числа на пары с суммой

В каждой такой паре нужно “испортить” хотя бы одно число. За каждую операцию мы “портим” числа, то есть можем “испортить” максимум две пары. Нужно “испортить” пар, поэтому нужно минимум операций. Приведем пример на действий:

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

Ряд не содержит числа , а также никакие несколько чисел не дают в сумме , так как их сумма как минимум

Разобьем числа на пары с суммой и ещё просто само число (будем считать, что оно в паре с

В каждой такой паре нужно “испортить” хотя бы одно число. За каждую операцию мы “портим” числа, то есть можем “испортить” максимум две пары. Нужно “испортить” пар, поэтому нужно минимум операций. Приведем пример на действий:

Сложим сначала с затем с и так далее до И ещё с После проделанных действий получаем

Ряд не содержит числа а также никакие несколько чисел не дают в сумме так как их сумма как минимум

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

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

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

Докажем теперь, что пять цветов достаточно. Для этого разобьём все натуральные числа на группы по 5 подряд идущих чисел, а группы покрасим так: первую - в первый, вторую - во второй, ..., пятую - в пятый, шестую - в первый, седьмую - во второй, .... При такой раскраске числа одного цвета будут или отличаться не более чем на 4, если лежат в одной пятёрке, или хотя бы на 21 - если в разных. Значит, числа, отличающиеся на и 18, будут покрашены в разные цвета.

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

Поскольку , то по модулю имеем

_________________________________________________________________________________________________________________________________________________________________________________

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

Докажем утверждение задачи для целых неотрицательных индукцией по

База: Если то — делится на

Переход: Предположим, что при число делится на и докажем, что при число также делится на Заметим, что

Первое слагаемое в правой части делится на по предположению индукции, а второе — потому что содержит множитель Значит, и вся сумма делится на Переход доказан.

Заметим, что

Значит,

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

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

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

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

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

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

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

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

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

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

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

По малой теореме Ферма и

Теперь взглянем на исходное выражение по модулю

Теперь взглянем на исходное выражение по модулю

Итак, и . По Китайской теореме об остатках решение такой системы сравнений по модулю, равном произведению модулей, существует и единственно, легко находим, что это

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

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

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

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

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

То есть поскольку все остальные факториалы либо кратны либо дают остатки, не кратные получаем Остаётся учесть симметрию и написать ответ.

Пусть первое из чисел равно тогда сумма арифметической прогрессии этих подряд идущих чисел равна

что эквивалентно

Поскольку чётно, то скобки имеют разную чётность, следовательно, чётна ровно одна из них.

Если чётно, то при этом но из условия на произведение получаем противоречие.

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

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

Число 20 повторилось, значит, процесс зациклится. Через 3 минуты после начала на доске будет записано 20, и через каждые 5 минут оно снова будет появляться. Тогда через минут на доске запишут число 20. Можно продолжить цепочку:

Заметим, что при обоих разрешённых действиях дробь не уменьшается и всегда остается меньше единицы.

Действительно, от второго действия величина дроби не меняется, осталось проверить первое действие.

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

просто перемножим крест-накрест, получив

что равносильно

Последнее неравенство очевидно следует из .

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

Так как не делится на 10, то последняя цифры — не Пусть где — цифры.

Из условия следует уравнение

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

Так как оканчивается на 0, а сами эти цифры нулю равняться не могут, то Тогда оканчивается на 10, поэтому Получаем

_________________________________________________________________________________________________________________________________________________________________________________

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

Запишем слагаемые левой части по определению десятичной записи

Приводим подобные слагаемые

Так как делится на то на тоже делится. Тогда и

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

Пусть Вернемся к нашему равенству, и подставим в него и

Сокращаем на 10

Справа число, делящееся на Так как то Так как то

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

Теперь найдем

Пусть в числе двоек, троек, четвёрок. Тогда всего цифр . При делении на число даёт такой же остаток, какой даёт его сумма цифр, то есть

Пусть даны числа . Тогда

Перемножим все эти неравенства и получится

Тогда

Напомним, что при нечётном число делится на при любом натуральном

Так как то взяв получаем, что число делится на

Взяв , получаем, что делится на

В итоге

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