Функции в натуральных/целых/рациональных числах

Подставим во второе неравенство

Тогда получаем:

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

Тогда

Возьмем какое-нибудь число Тогда возможны два варианта:

1. Если то и

2. Предположим Тогда Иначе
(а) Если
(b) Если
И так как то

Таким образом, для любого либо либо есть три различных числа таких, что

При этом любая функция с таким свойством подходит. Тогда найдем число функций с необходимым свойством.

1. Нет ни одной тройки элементов, что Значит, для всех чисел верно Такая функция одна.

2. Есть одна тройка элементов, что Выбрать тройку можно способами. При этом есть два способа задать функцию в тройке. Итого функций.

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

Всего число функций равно

Используя равенство и соотношения, получаем . Далее, используя эти равенства, получаем . Значит, подходит.

Используя остальные равенства, получим

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

а) Так как то и являются перестановками. Но тогда, например, и выполняется

b) Из условия получим

С другой стороны, если указанное условии пункта b) представление существует, то

а это доказывает невозможность указанного представления.

Если взять мы получим равенство откуда

По основной теореме арифметики любой аргумент функции представляется в виде где — простые числа. Поэтому

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

Для начала подставим и поймём, что . Далее подставим и получим равенство , то есть функция чётная. Если подставить , мы получим, что . Если подставить , мы получим, что . Возникает желание доказать индукцией по , что . Чтобы доказать переход, надо просто подставить , и воспользоваться предположением , .

Таким образом, .

В силу условия и того, что функция возвращает натуральные значения, понятно, что Также по условию Отсюда следует, что принимает какое-то значение из Если то противоречие. Если то но противоречие. Значит и При имеем Далее продолжаем аналогичные вычисления: и так дальше до тех пор, пока не вычислим Заметим, что между и ровно натуральных чисел. Также заметим, что в силу условия между и находятся натуральных чисел Понятно, что такое возможно лишь когда Но тогда Подставим в функциональное равенство и получим ответ

При имеем откуда Из условия следует, что больше ни при каких других функция не принимает значение ( — -я итерация функции ).

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

Пусть — такое минимальное число, что В таком случае, должно быть делителем иначе — остаток от деления на Заметим, что а мы выбрали наименьшим таким, что Это означает, что либо либо Предположим, что тогда пусть — простое, отличное от Заметим, что справедливо равенство Если вместо подставить то получим значит делит То есть — общий делитель двух простых чисел, откуда Но тогда при любом простом имеем

Осталось лишь воспользоваться условием и ОТА для того, чтобы убедиться в том, что при любом натуральном

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

Так как функция строго возрастает, то

Но по условию правая часть равна и левая часть равна значит, в обоих неравенствах должно достигаться равенство, то есть при увеличении аргумента на 1, значение функции тоже увеличивается ровно на 1:

Остаётся найти Для этого в исходное условие подставим и получим

В итоге для любого получаем откуда

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

Подставим Получаем

После подстановки получаем Тогда где Заметим, что при ведь иначе Итак,

После подстановки получаем Поэтому значения функции на концах отрезка являются двумя последовательными натуральными числами.

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

Итак, откуда для любого получаем

В итоге

Заметим, что для

Отсюда легко видеть

Подставляя в равенство , получаем

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

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

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

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

В данном случае имеется 25 вариантов.

а В таблице есть 10 аргументов, при которых Выбирая пару таких аргументов, первый можно выбрать 10 способами, а второй – 9 способами. Значит, количество пар такого типа равно

а Аналогично предыдущему пункту получаем пары.

а Здесь пар.

a Здесь пары.

a Здесь также пары.

Итого, есть пар натуральных чисел для которых Всего имеется пар, поэтому тех, при которых ровно

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

Задумаемся, а существует ли такое Условие равносильно квадратному уравнению в остатках(в этом абзаце все сравнимости по модулю 7):

Или можно было просто перебором остатков, благо их всего 7, убедиться, что любой из 3 и 5 подходят.

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

Чтобы подчеркнуть полученное, обозначим и выбросим среднюю часть:

Отсюда следует (далее все сравнимости будут по модулю 11)

Отметим что это именно следствие, а не равносильность. Выясним, имеет ли сравнимость решения, действуя стандартно А извлекается ли квадратный корень из -3 по модулю 11? Заметим что и Мы перебрали все остатки, среди квадратов не нашлось -3, значит корень не извлекается, значит уравнение не имеет решений.

Итак, требуемой функции не существует.

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

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

Предположим, что функция не принимает ни одного значения из Рассмотрим число из данного отрезка. Пусть По условию В силу инъективности значит всё же значение принимается.

Из условия ясно, что значит Но тогда функция не может принимать значение В противном случае если при некотором то — противоречие. Тогда понятно, что также лежит в отрезке поскольку другие значения принимаются.

Тогда все натуральные числа от до можно разбить на пары такие, что значение функцией не принимается и Очевидно, что внутри пары числа не могут совпадать. Теперь поймём от противного, что не может быть пар с одинаковыми числами. Рассмотрим случаи:

Пусть нашлись пары и Тогда из одной пары следует, что значение принимается, а из другой — что значение не принимается, противоречие.

Пусть нашлись пары и тогда а значит в силу инъективности то есть это одна и та же пара.

Пусть нашлись пары и тогда и откуда то есть опять же пары совпали.

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

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

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

Нам осталось разобраться со случаем, когда одно из чисел четное, а другое — нечетное. Не нарушая общности пусть — четное число.

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

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

Пусть — НОК Введём такую функцию что Индукцией по сумме покажем, что — тождественный ноль.

База: откуда что и требовалось.

Переход: Распишем равенство через функцию ( и будем записывать как и где — ):

Раскроем скобочки, приведём подобные и домножим полученное равенство на

Теперь рассмотрим выражение где — натуральное число, не большее Пусть тогда

По полученному выше равенству имеем: Заметим, что тогда по предположению а значит и

Таким образом, единственная подходящая функция — НОК

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

Докажем индукцией по что

Базу будем проверять для всех

Утверждение для очевидно.

Утверждение для следует из подстановки

Утверждение для следует их подстановки

Утверждение для следует из того, что

Утверждение для следует из подстановки

Далее заметим, что при подстановке

Утверждение для следует из подстановки в полученное равенство

Утверждение для следует из подстановки в исходное уравнение

Утверждение для следует из подстановки в последнее равенство и предыдущих утверждений.

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

То есть

откуда

Если же четно, то

То есть

откуда

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

Обозначим Так как и делятся на то их разность делится на Тогда или

Как известно, откуда выражение из условия принимает вид

Поскольку может принимать значения только двух констант: или то нам достаточно будет максимизировать функцию

Эта функция определена уже при всех действительных , потом учтём, что у нас было натуральное . Для максимизации посмотрим на её производную:

Производная при имеет ровно одну точку экстремума (это кстати натуральное число), которая является точкой максимума, потому является глобальным максимумом при А ещё удачным образом при имеем — также принимает максимальное значение, потому при достигает максимума и функция Равен этот максимум

Предположим, что каждое из чисел и оказалось красивым. Тогда

Значит, найдутся такие целые числа и , что во всех чётных числах функция принимает значение , а во всех нечётных — значение

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

Докажем по индукции, что

_________________________________________________________________________________________________________________________________________________________________________________

База очевидна:

_________________________________________________________________________________________________________________________________________________________________________________

Переход несложно доказать:

_____________________________________________________________________________________

Таким образом, по доказанной формуле

_________________________________________________________________________________________________________________________________________________________________________________

Замечание. Вот как прийти к решению:

Вычислим значение функции в произвольной чётной точке :

Более формально равенство можно доказать индукцией по . Таким образом, .