Тема Высшая проба

Функции на Высшей пробе

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

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

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

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

Подтемы раздела высшая проба

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

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

Задача 1#74778

В этой задаче запись $x modn,$ где $x$ — целое а $n$ — натуральное, обозначает такое целое число $y$ от 0 до $n− 1,$ что $x− y$ делится на $n.$

Существует ли такая функция $f,$ определенная для целых значений аргумента и принимающая целые значения, что при любом целом $x$ верно

(( 2 ) ) ( 2 ) f x +1 mod 7 = f(x) +1 mod 11 ?

Источники: Высшая проба - 2022, 11.1 (см. olymp.hse.ru)

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

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

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

x20− x0 +1 ≡0

1±√ −3- 1±√ −3+-7 {3 − 1} {3 +7 −1 +7} x0 ≡--2----≡ ----2----≡ 2,-2- ≡ --2-,--2-- ≡ {5,3}

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

Что же нам дает равенство $3 =32+ 1mod 7?$ Просится от обоих частей взять функцию $f,$ а затем воспользоваться условием задачи. Имеем:

f(3)=f ((32+ 1)mod7)= (f(3)2+ 1) mod11

Чтобы подчеркнуть полученное, обозначим $f(3)= y$ и выбросим среднюю часть:

( 2 ) y = y + 1 mod11

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

y2− y+ 1≡ 0

Отметим что это именно следствие, а не равносильность. Выясним, имеет ли сравнимость решения, действуя стандартно $√ -- y ≡ 1±-2−3.$ А извлекается ли квадратный корень из -3 по модулю 11? Заметим что $12 ≡ (−1)2 ≡1,22 ≡(−2)2 ≡ 4,32 ≡ (− 3)2 ≡ 9,$ $42 ≡ (− 4)2 ≡ 5$ и $52 ≡ (−5)2 ≡3.$ Мы перебрали все остатки, среди квадратов не нашлось -3, значит корень не извлекается, значит уравнение $y2− y+ 1≡ 0$ не имеет решений.

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

Ответ: нет