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

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

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

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

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

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

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

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

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

Задача 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)

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

Подсказка 1

Такс, перед нами функциональное уравнение, да еще и аргумент функции мы берем по модулю 7… Давайте вспомним, что мы обычно делаем в функциональных уравнениях?

Подсказка 2

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

Подсказка 3

Да, хочется найти такие x, для которых верно: x = x²+1 по модулю 7. Почему так хочется сделать? Если получится найти такой x, то дальше уравнение сведется к f(x) = (f(x)²+1) (по модулю 11). А понять, решается ли такое уравнение уже проще, чем решить исходное! Остаётся найти такие x.

Подсказка 4

Заметим, что 3 = 3²+1 по модулю 7! То есть, 3 нам подходит. Что можно сказать про f(3)?

Подсказка 5

Верно, f(3) = f(3)²+1 по модулю 11. Мы получили почти то же самое, что и на одном из предыдущих шагов, только теперь по модулю 11! Остаётся показать, что таких y не существует.

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

Стандартным ходом при решении задач на функциональные уравнения является подставить какое-то значение переменной, при котором два часто возникающих и не равных друг-другу тождественно выражения оказываются равны, и посмотреть, какие следствия из этого удастся вывести. Применительно к данной задаче на роль такой подстановки простится значение $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$ не имеет решений.