Тема Функции

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

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

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

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

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

Подтемы раздела функции

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

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

Задача 1#77208

Дана функция $f(x)$ , определенная на множестве целых чисел и принимающая целые значения.

Известно, что $f(1)=1$ и для любого целого $x$ выполняются неравенства

f(x+ 4)≥ f(x)+ 4

f(x+ 1)≤ f(x)+ 1

Найдите $f(2025)$ .

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

Подставим во второе неравенство $x+ 4:$

f(x+ 4)≤ f(x+ 3)+1 ≤f(x+ 2)+1+ 1≤

≤ f(x +1)+ 1+1 +1≤ f(x)+1+ 1+ 1+ 1= f(x)+ 4.

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

f(x)+4 ≥f(x+ 4)≥f(x)+4.

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

f(x+ 1)=f(x)+1.

Тогда $f(2025)= 1+ f(2024)=...= 2024+ f(1)= 2025.$

Ответ: 2025

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

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

Задача 2#76651

Найдите количество функций $f :{1,2,3,4,5,6} → {1,2,3,4,5,6}$ для которых верно $f(f(f(x)))=x$ для всех $x∈ {1,2,3,4,5,6}$ .

Источники: ЮМШ-2023, 11 класс, отборочный тур (см. yumsh.ru) | ЮМШ-23/24, 11 класс, 1 отборочный тур (см. yumsh.ru)

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

Возьмем какое-нибудь число $a ∈{1,2,3,4,5,6}.$ Тогда возможны два варианта:

1. Если $f(a)= a,$ то и $f(f(f(a)))= a.$

2. Предположим $f(a)= b и b⁄= a.$ Тогда $f(b)= c, где c⁄= a,c⁄= b.$ Иначе
(а) Если $f(b)= a, то f(f(f(a)))= f(f(b)) =f(a)=b ⁄=a.$
(b) Если $f(b)= b, то f(f(f(a)))= f(f(b))= f(b) =b⁄= a.$
И так как $a =f(f(f(a)))= f(f(b))= f(c),$ то $f(c)=a.$

Таким образом, для любого $a∈ {1,2,3,4,5,6}$ либо $f(a)=a,$ либо есть три различных числа таких, что $f(a)= b,f(b) =c и f(c)= a.$

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

1. Нет ни одной тройки элементов, что $f(a)= b,f(b)= c, и f(c)= a.$ Значит, для всех чисел $a∈{1,2,3,4,5,6}$ верно $f(a)= a.$ Такая функция одна.

2. Есть одна тройка элементов, что $f(a)= b,f(b)= c, и f(c)=a.$ Выбрать тройку можно $C36$ способами. При этом есть два способа задать функцию в тройке. Итого $2C36$ функций.

3. Есть две тройки элементов, что $f(a)= b,f(b)= c, и f(c)= a.$ Выбрать первую тройку можно $C36$ способами, остальные три элемента образуют вторую тройку. Но варианты, в которых выбрали в первую тройку $a,b,c$ и выбрали все кроме $a,b,c$ одинаковые. То есть $C36 :2$ способов разбить элементы на две тройки. При этом в каждой тройке есть два способа задать функцию. Итого $2⋅2⋅C36 :2 =2C36$ функций.

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

1 +2C36 + 2C36 = 81

Ответ: 81

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

Задача 3#88706

Функция $f(n)$ определена для целых положительных чисел, удовлетворяет условию $f(1)= 1$ и двум соотношениям

f(3n)= 3f(n), f(3n+ 1)= 9f(n)

Найдите числа $n$ , удовлетворяющие равенству $f(n) =81.$

Источники: САММАТ - 2024, 11.4 (см. sammat.samgtu.ru)

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

Подсказка 1

Попробуем ручками посчитать какие-то первые значения. У нас есть несколько «цепочек» значений функции, которые мы можем расписать по условию.

Подсказка 2

f(1) = 1, f(3) = 3, f(4) = 9. Попробуем найти следующие значения - когда достигнем 81? Что будет, если мы вдруг перепрыгнем его?

Подсказка 3

Будем продолжать искать так значения, равные 81. Заметим, что значения в одной цепочке возрастают! Значит, искать придется не так много)

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

Используя равенство $f(1)= 1$ и соотношения, получаем $f(3)= 3,f(4)= 9$ . Далее, используя эти равенства, получаем $f(9)=9,f(10)= 27,f(12) =27,f(13)= 81$ . Значит, $n = 13$ подходит.

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

f(27)=27, f(28)=81, f(30)= 81, f(31)= 243, f(36)= 81, f(37)= 243.

Таким образом, $n= 28,30,36$ подходят, а продолжая цепочку из равенств $f(31)=243$ и $f(37)= 243,$ мы уже не получим $81$ . Осталось равенство $f(27)=27$ , откуда $f(81)= 81,f(82)= 243$ .

Ответ: 13, 28, 30, 36, 81

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

Задача 4#90278

a) перестановка $f$ чисел ${0,1,...,6}$ задана таблицей:


$x$	0	1	2	3	4	5	6

$f(x)$	3	2	4	0	5	6	1

Например, $f(2)= 4$ . Найдите две различные перестановки $g$ и $h$ такие, что для всех $x ∈{0,1,...,6}$ выполняется

f(x)≡ (g(x)+h(x))(mod7)

b) перестановка $f$ задана на чётном количестве чисел ${0,1,...,2n− 1}$ таблицей:


$x$	0	1	2	..	$2n− 2$	$2n− 1$

$f(x)$	$i0$	$i1$	$i2$	..	$i2n−2$	$i2n−1$

Здесь $(i0,i1,...,i2n−1)$ - перестановка чисел ${0,1,...,2n− 1}$ .

Докажите, что не существует перестановок $g$ и $h$ таких, что для всех $x∈ {0,1,...,2n− 1}$ выполняется $f(x)≡(g(x)+ h(x))(mod (2n))?$

Источники: Верченко - 2024, 11.3 (см. ikb.mtuci.ru)

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

Пункт а, подсказка 1

Просто пытаться найти перестановки функции перебором очень тяжело. Однако можно заметить, что если мы домножим каждое значение перестановки f(x) на число взаимно простое с 7 и возьмём от получившихся чисел остатки при делении на 7, то мы получим перестановку. Попробуйте найти такие перестановки, подходящие под условие.

Пункт а, подсказка 2

Нужно взять два числа, взаимно простых с 7, чтобы их сумма имела остаток 1 при делении на 7. Тогда, умножив f(x) на эти числа, мы получим перестановки g(x) и h(x). Они подходят под условие.

Пункт b, подсказка 1

Мы почти ничего не знаем про расположение элементов перестановки. Однако точно знаем, чему равна сумма значений перестановки. Ведь её значения - 0,1,...,2n-1. То же самое можно сказать про перестановки g(x) и h(x). Попробуйте доказать требуемое от противного, записав условие через сумму перестановки.

Пункт b, подсказка 2

Суммы значений всех трёх перестановок равны (2n+1)*n. Тогда, используя условие пункта b, получаем, что (2n+1)*n = (2n+1)*n+(2n+1)*n(mod 2n). Попробуйте получить противоречие, рассматривая по модулю 2n.

Показать доказательство

а) Так как $НОД (2,7) =НО Д(6,7)=1,$ то $g(x)≡ 2f(x)(mod7)$ и $h(x)≡ 6f(x)(mod7)$ являются перестановками. Но тогда, например, $g(x)=2f(x),h(x)=6f(x)$ и выполняется

g(x)+ h(x)=2f(x)+6f(x)≡f(x)(mod7)

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

2∑n− 1 2n∑−1 f(x)= x = (2n+ 1)n =n(mod(2n)) i=0 i=0

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

2∑n−1 2∑n− 1 2n∑−1 f(x)= g(x)+ h(x)=2(2n+ 1)n≡ 0(mod(2n)), i=0 i=0 i=0

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

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

Задача 5#65396

Решите уравнение

f(xy) =f(x)f(y),

где $f :ℕ→ ℕ.$

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

Подсказка 1

Равенство, данное в условии, очень похоже на работу с натуральными числами) А какая известная теорема, связанная с произведением, приходит на ум при виде условия?

Подсказка 2

Основная теорема арифметики! Но при работе с разложением на множители, единичке нужно особо внимание. Попробуем подставить y=1. Подумаем, на значения в каких точках условие почти не влияет, а в каких - условие помогает определить точное значение?

Подсказка 3

Значения в f(x), где x - составное, полностью определяются значениями в точках f(p_i), где p_i --- i-тое простое число. Возьмем f(p_i) = c_i и убедимся, что c_i может быть произвольным!

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

Если взять $y = 1,$ мы получим равенство $f(x)= f(x)f(1),$ откуда $f(1)= 1.$

По основной теореме арифметики любой аргумент $x> 1$ функции $f$ представляется в виде $a1 ak x= p1 ⋅...⋅pk ,$ где $pi$ — простые числа. Поэтому

a a f(x)=f(p1)1 ⋅...⋅f(pk) k

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

Ответ:

Если $x =1,$ то $f(1)= 1;$ иначе $x =pa1⋅...⋅pak 1 k$ — каноническое разложение, и $f(pa1⋅...⋅pak)=ca1⋅...⋅cak, 1 k 1 k$ где $k ∈ℕ , 0$ $ci ∈ ℕ ∀i∈ ℕ0$

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

Задача 6#65397

Решите функциональное уравнение $f: ℤ → ℤ$

f(x− y)+f(x+ y)=2f(x)+2f(y).

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

Подсказка 1

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

Подсказка 2

Для этого удобно подставить y=x и y=-x и получим, что f(x)=f(-x) и f(2x)=4f(x).

Подсказка 3

Попробуйте подставить y=2x, тогда преобразовав получим f(3x)=9f(x), отсюда можно видеть что значения функции как бы вычисляются рекуррентно, и сделать предположение о том, чему эта функция может быть равна.

Подсказка 4

Докажите индукцией по n что f(nx)=n^2*f(x), отсюда сразу находится f(x)=c*x^2.

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

Для начала подставим $x= y = 0$ и поймём, что $f(0) =0$ . Далее подставим $y =− x$ и получим равенство $f(y)=f(−y)$ , то есть функция чётная. Если подставить $y = x$ , мы получим, что $f(2x)=4f(x)$ . Если подставить $y =2x$ , мы получим, что $f(3x) =9f(x)$ . Возникает желание доказать индукцией по $n$ , что $2 f(nx)=n f(x)$ . Чтобы доказать переход, надо просто подставить $x= nx$ , $y = x$ и воспользоваться предположением $2 f((n− 1)x) =(n− 1)x$ , $2 f(nx)=n f(x)$ .

Таким образом, $2 2 f(x)= x f(1)= cx,c∈ ℤ$ .

Ответ:

$f(x)= cx2,c∈ℤ$

Курсы

Всё необходимое для достижения цели

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

Задача 7#65399

Пусть функция $f: ℕ → ℕ$ такова, что $f(n +1)> f(n)$ и

f(f(n))=3n

при всех $n.$ Вычислите $f(2001).$

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

Подсказка 1

Подумайте над тем, как оценить значения f(x) для всех натуральных х, и найти значение f(1)

Подсказка 2

Можем ли мы куда-то подставить f(1) и что нам это даст? Попробуйте найти f(3), f(6), f(9), f(18). Есть ли в них закономерность?

Подсказка 3

Найдите значения f(1458) и f(729) и поймите, как можно найти значения в точках 730,731,…,1457, используя условие f(n+1)>f(n)

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

В силу условия $f(n+ 1)>f(n)$ и того, что функция возвращает натуральные значения, понятно, что $f(1)≥ 1,f(2)≥2,f(3)≥ 3,f(4)≥ 4.$ Также по условию $f(f(1))= 3.$ Отсюда следует, что $f(1)$ принимает какое-то значение из $1,2,3.$ Если $f(1)= 1,$ то $f(f(1)) =f(1)=3,$ противоречие. Если $f(1)= 3,$ то $f(f(1))= f(3)= 3,$ но $f(3)>f(1),$ противоречие. Значит $f(1)= 2$ и $f(f(1))= f(2)= 3.$ При $n =2$ имеем $f(f(2))= f(3)= 6.$ Далее продолжаем аналогичные вычисления: $f(f(3))=f(6)= 9$ и так дальше до тех пор, пока не вычислим $f(729)= 1458,f(1458)= 2187.$ Заметим, что между $1458$ и $2187$ ровно $728$ натуральных чисел. Также заметим, что в силу условия $f(n+ 1)>f(n)$ между $f(729)$ и $f(1458)$ находятся $728$ натуральных чисел $f(730)< f(731)< ...< f(1457).$ Понятно, что такое возможно лишь когда $f(730)= 1459,f(731)= 1460,...,f(1457)= 2186.$ Но тогда $f(1272)= 2001.$ Подставим $n= 1272$ в функциональное равенство и получим ответ $f(f(1272))= f(2001)=3816.$

Ответ:

$3816$

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

Задача 8#65400

Найдите все функции $g: ℕ → ℕ$ такие, что для всех натуральных $n$ и $k$ верны равенства

g(nk)=g(n)g(k) и g◟(g(◝..◜.(g◞(n))...))= n n буквg

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

Подсказка 1

Сначала попробуем понять, чему равно g(1). Какие n и k надо для этого взять?

Подсказка 2

Возьмём n = k = 1, получим g(1) = 1. Может ли функция g принимать значение 1 в каких-то других точках?

Подсказка 3

На самом деле не может, иначе получаем противоречие из формулы gₙ(n) = n (gₙ(n) — n-ая итерация функции g). Тогда для каждого составного n g(n) является тоже составным числом. А что если n — простое число?

Подсказка 4

В простых точках функция возвращает простые числа, ведь если это не так, то для простого p опять получаем противоречие из gₚ(p) = p. Пусть k — минимальное число, такое что gₖ(p) = p. Как можно связать k и p?

Подсказка 5

Попробуйте поиграться с вложением функций в равенстве gₚ(p) = p, используя идею деления p на k с остатком, чтобы получить противоречие с минимальностью k. Отсюда выведите, что либо k = 1, либо k = p (т.е. k - делитель p). Рассмотрите случай k = p.

Подсказка 6

Используйте идею из предыдущей подсказки, чтобы доказать, что k делит ещё одно простое число, а именно g(p). Тогда k = 1 и для любого простого p g(p) = p. Какой вывод тогда можно сделать для любого натурального n?

Подсказка 7

Воспользуемся условием g(nk) = g(n)g(k) и основной теоремой арифметики, получим, что g(n) = n для любого n ∈ ℕ. Задача решена!

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

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

Тогда понятно, что из каждого составного числа функция возвращает составное число: $g(bc)= g(b)g(c).$ Предположим, что в простых точках функция также возвращает составные числа, но тогда при простом $p$ число $gp(p)$ должно быть составным, противоречие. Значит в простых точках функция является простым числом.

Пусть $k$ — такое минимальное число, что $gk(p)= p.$ В таком случае, $k$ должно быть делителем $p.$ иначе $gp(p)= gp−k(gk(p))= gp−k(p)=...=gr(p),r$ — остаток от деления $p$ на $k.$ Заметим, что $r <k,$ а мы выбрали $k$ наименьшим таким, что $gk(p)= p.$ Это означает, что либо $k= 1,$ либо $k =p.$ Предположим, что $k= p,$ тогда пусть $g(p)= q,q$ — простое, отличное от $p.$ Заметим, что справедливо равенство $gk+1(p)= g(p).$ Если вместо $g(p)$ подставить $q,$ то получим $gk(q)= q,$ значит $k$ делит $q.$ То есть $k$ — общий делитель двух простых чисел, откуда $k= 1.$ Но тогда при любом простом $p$ имеем $g(p)=p.$

Осталось лишь воспользоваться условием $g(nk)=g(n)g(k)$ и ОТА для того, чтобы убедиться в том, что $g(n)=n$ при любом натуральном $n.$

Ответ:

$g(n)=n$

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

Задача 9#67676

Дана строго возрастающая функция $f :ℕ −→ ℕ 0 0$ (где $ℕ 0$ — множество целых неотрицательных чисел), которая удовлетворяет соотношению $f(n+f (m ))= f(n)+ m+ 1$ для любых $m,n ∈ℕ0.$ Найдите все значения, которые может принимать $f(2023).$

Источники: ММО-2023, 11.1 (см. mmo.mccme.ru)

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

Подсказка 1

Смотрим на условие задачи внимательно и ищем, за что зацепиться: "функция строго возрастающая", "числа целые неотрицательные", ещё и равенство для функции без всяких степеней, ещё и единичка прибавляется с одной стороны... Мы видим, что правая часть равенства из условия при увеличении m на 1 увеличивается ровно на 1 (эта идея возникает из возрастания функции и целых значений), тогда имеет смысл посмотреть, а как в таком случае меняется левая часть?

Подсказка 2

Если мы оставим n таким же, а m увеличим на 1, то видим, что левая часть изменилась ровно на 1, а, значит, f(n + f(m+1)) = f(n + f(m)) + 1. То есть слева аргумент функции "почти" увеличился на 1 (на самом деле увеличился на 1 аргумент функции внутри аргумента нашей функции:)), а справа увеличилась на 1 сама часть, вне функции... А вспомним-ка про возрастание функции и применим f(m+1) >= 1 + f(m).

Подсказка 3

Теперь мы должны прийти к тому, что вместо неравенства должно выполняться равенство f(m + 1) = f(m) + 1 для любого целого неотрицательного m.

Подсказка 4

Мы уже связали f(m) и f(m+1), остаётся лишь найти f(0), чтобы стартовать от этого значения. Попробуйте подставить в условие самые базовые значения переменных - нули - и найдите f(0).

Подсказка 5

Теперь окончательно получается f(m) = m + 1. Остаётся найти f(2023) и написать ответ!

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

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

Так как функция $f :ℕ0 −→ ℕ0$ строго возрастает, то

f(n+ f(m + 1))≥ f(n +f(m)+ 1)≥f(n+ f(m ))+1

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

f(m+ 1)= f(m )+1

Остаётся найти $f(0).$ Для этого в исходное условие подставим $m =0$ и получим

f(n +f(0)) =f(n)+1 =f(n+ 1) =⇒ f(0) =1

В итоге для любого $n∈ ℕ0$ получаем $f(n)= n+ 1,$ откуда $f(2023)= 2024.$

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

Подставим $m = 0.$ Получаем $f(n+ f(0))= f(n)+ 1.$

После подстановки $n =0$ получаем $f(f(0))= f(0)+ 1.$ Тогда $f(a)= a+ 1,$ где $a =f(0).$ Заметим, что при $a⁄= 0,$ ведь иначе $f(0)=f(0)+1.$ Итак, $a∈ ℕ.$

После подстановки $n =a$ получаем $f(a+ a)=f(a)+1 =a +2.$ Поэтому значения функции на концах отрезка $[a;2a]$ являются двумя последовательными натуральными числами.

По условию функция $f :ℕ0 −→ ℕ0$ строго возрастает, а значит, на отрезке $[a;2a]$ не должно быть других целых точек помимо $a$ и $2a,$ так как в противном случае значения в этих точках совпадали бы с $a +1$ или $a+ 2,$ что противоречило бы строгому возрастанию. Тогда $2a− a= 1,$ откуда получаем $a= 1.$

Итак, $f(0)=1,f(n+ 1)= f(n)+1,$ откуда для любого $n∈ ℕ 0$ получаем $f(n)= n+ 1.$

В итоге $f(2023)=2024.$

Ответ: 2024

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

Задача 10#49764

Функция $F$ определена на множестве троек целых чисел и принимает действительные значения. Известно, что для любых четырёх целых чисел $a,b,c$ и $n$ выполняются равенства $F (na,nb,nc)= n⋅F(a,b,c),F(a+ n,b+ n,c+n)= F(a,b,c)+n$ , $F (a,b,c)= F(c,b,a)$ . Найдите $F(58,59,60).$

Источники: ОММО-2022, номер 9, (см. olympiads.mccme.ru)

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

Подсказка 1

Давайте посмотрим на нашу функцию и на то, что с ней можно делать. Во-первых, можно выносить общий множитель из аргумента. Во вторых, можно вычитать, прибавлять что угодно и к аргументам функции, и к её значению, при этом равенство останется верным. Ещё наша функция симметрична относительно первой и второй переменной. Теперь подумаем, как нам можно получить F(58,59,60). Это три последовательных числа. Значит, чтобы получить значение на этих значениях, мы можем найти значение в точке F(k-1,k,k+1) и потом по второму свойству найти требуемое. При этом как-то надо воспользоваться двумя другими условиями. Попробуйте подобрать такое k, чтобы значение в нём можно было бы найти с помощью двух других условий.

Подсказка 2

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

Подсказка 3

Если мы хотим, чтобы функция в точках была равна минус себе, то так как n*F(a,b,c) = n*F(c,b,a) = F(na,nb,nc), мы хотим, чтобы na = -nc, nb = - nb, nc = -na. Но из второго равенства следует, что nb=0, а значит и b = 0(иначе, n = 0, и у нас просто функция от нулей равна 0. Что не подходит нам под условие на k-1,k,k+1. Значит, b = 0, a = -1, c = 1. И значит, F(-1,0,1)= 0 = F(58,59,60) - 59.

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

Заметим, что для $n= −1$

F(−1,0,1)= F(1,0,−1)= (−1)⋅F(−1,0,1) =⇒ F (− 1,0,1)= 0

Отсюда легко видеть $F(58,59,60)= F(−1,0,1)+59 =59.$

Ответ:

$59$

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

Задача 11#70777

Функция $f$ определена на множестве положительных рациональных чисел. Известно, что для любых чисел $a$ и $b$ из этого множества выполнено равенство $f(ab)=f(a)+f(b),$ и при этом $f(p) =[p∕4]$ для любого простого числа $p$ ( $[x]$ обозначает наибольшее целое число, не превосходящее $x).$ Найдите количество пар натуральных чисел $(x;y)$ таких, что $3≤ x≤ 27,$ $3 ≤y ≤27$ и $f(x∕y)< 0.$

Источники: Физтех-2022, 11.5 (см. olymp.mipt.ru)

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

Подсказка 1

Нам надо как-то искать ƒ(x/y). Какие a и b надо подставить, чтобы получить ƒ(x/y) и что-то еще, не очень плохое...

Подсказка 2

Разумно взять b=x/y, где x и y- натуральные числа. Возьмем тогда a=y, чтобы их произведение было натуральным числом. Тогда ƒ(y)+ƒ(x/y)=ƒ(y*x/y)=ƒ(x) ⇒ ƒ(x/y)=ƒ(x)-ƒ(y). Если ƒ(x/y)<0, то что можно сказать про ƒ(y/x)?

Подсказка 3

ƒ(y/x)=ƒ(y)-ƒ(x)=-(ƒ(x)-ƒ(y))=-ƒ(x/y)>0. Это означает, что количество пар (x; y) таких, что ƒ(x/y)<0 равно количеству пар (x; y) таких, что ƒ(x/y)>0. Тогда нам осталось лишь посчитать количество пар, в которых ƒ(x/y)=0. Как это сделать?

Подсказка 4

Мы знаем, что ƒ(x/y)=ƒ(x)-ƒ(y)⇒ нам достаточно посчитать количество пар (x;y) таких, что f(x)=f(y). Т.к. нам известны значения ƒ(x), если x- простое, то мы можем найти все ƒ(x), где x- любое натуральное число от 3 до 27, ведь x раскладывается в произведение простых. Сколько тогда будет пар (x; y) таких, что ƒ(x)=ƒ(y)?

Подсказка 5

Таких пар будет 167. Т.к. всего пар 25²=625, то искомых пар будет (625-167)/2=229.

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

Подставляя $a= 1$ в равенство $f(ab)= f(a)+f(b)$ , получаем

f(b)= f(1)+ f(b)⇒ f(1)=0

Если же для произвольных натуральных $x,y$ положить $a= x,b= y y$ , то получаем

(x ) (x) f(x)= f y ⋅y = f y + f(y)

(x ) f y = f(x)− f(y)

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

Для простых чисел и единицы значения функции мы уже знаем. Для составных чисел значения функции могут быть найдены, если их разложить на простые множители и воспользоваться равенством $f(ab)= f(a)+ f(b)$ , например, $f(15)= f(3 ⋅5)= f(3)+$ $+f(5)=[34]+ [54]= 0+1 =1.$ Аналогичным образом вычисляем значения функции для $n∈ [3;27]$ и записываем их в таблицу:

|--n--|3-|-4-|5-|-6-|7--|8-|-9-|10|11-|12-|13-|14-|15| |f(n)-|0-|-0-|1-|-0-|1--|0-|-0-|1-|-2-|0--|3-|-1-|1-| |-----|--|---|--|---|---|--|---|--|---|---|--|---|--| |--n--|16-|17-|18|19-|20-|21-|22-|23|24-|25-|26-|27-|--| -f(n)--0---4--0---4--1---1---2--5---0--2---3---0-----

Поскольку $(x) (y) f y +f x = f(1)= 0,$ то из $(x) f y <0$ следует, что $(y) f x >0.$ Таким образом, количество пар натуральных чисел $(x;y)$ таких, что $( ) f xy <0$ совпадает с количеством пар, для которых $( ) f xy > 0.$ Посчитаем количество пар $(x;y),$ при которых $( ) f xy = 0.$ Ввиду того, что $( ) f xy = f(x)− f(y),$ нужно найти количество пар $(x;y)$ из таблицы выше, для которых $f(x)=f(y).$ Рассмотрим несколько случаев:

$∙$ $x= y.$ В данном случае имеется 25 вариантов.

$∙$ $x⁄= y,$ а $f(x)= f(y)= 0.$ В таблице есть 10 аргументов, при которых $f = 0.$ Выбирая пару таких аргументов, первый можно выбрать 10 способами, а второй – 9 способами. Значит, количество пар такого типа равно $10⋅9= 90.$

$∙$ $x⁄= y,$ а $f(x)= f(y)= 1.$ Аналогично предыдущему пункту получаем $7⋅6= 42$ пары.

$∙$ $x⁄= y,$ а $f(x)= f(y)= 2.$ Здесь $3 ⋅2 =6$ пар.

$∙$ $x⁄= y,$ a $f(x)= f(y)= 3.$ Здесь $2 ⋅1 =2$ пары.

$∙$ $x⁄= y,$ a $f(x)= f(y)= 4.$ Здесь также $2 ⋅1 =2$ пары.

Итого, есть $25+ 90+ 42+6+ 2+ 2= 167$ пар натуральных чисел $(x;y),$ для которых $f(x) =0. y$ Всего имеется $252 = 625$ пар, поэтому тех, при которых $( x) f y < 0,$ ровно $625−167 --2---=229.$

Ответ: 229

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

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

Задача 12#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$ не имеет решений.

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

Ответ: нет

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

Задача 13#80945

Найдите все функции $f: ℕ → ℕ$ , для которых $f(f(n))=n +2011.$

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

Покажем, что функция $f$ инъективна. Пойдём от противного, пусть нашлись такие $a⁄= b,$ что $f(a)= f(b).$ Тогда $f(f(a))=a +2011$ и $f(f(b))= b+2011.$ Заметим, что левые части равенств равны, а правые — нет, противоречие. Таким образом, функция инъективна.

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

Предположим, что функция не принимает ни одного значения из $[1;2011].$ Рассмотрим число $n0$ из данного отрезка. Пусть $f(n0)=2011+ k.$ По условию $f(f(k))=2011+ k.$ В силу инъективности $f(k) =n0,$ значит всё же значение $n0$ принимается.

Из условия ясно, что $f(f(n)) >2011,$ значит $f(f(n))> n0.$ Но тогда функция $f(n)$ не может принимать значение $k.$ В противном случае если при некотором $t$ $f(t)= k,$ то $f(f(t)) =f(k)=n0 =t+ 2011$ — противоречие. Тогда понятно, что $k$ также лежит в отрезке $[1;2011],$ поскольку другие значения принимаются.

Тогда все натуральные числа от $1$ до $2011$ можно разбить на пары $(a,b)$ такие, что значение $b$ функцией не принимается и $f(b)=a.$ Очевидно, что внутри пары числа не могут совпадать. Теперь поймём от противного, что не может быть пар с одинаковыми числами. Рассмотрим случаи:

$1.$ Пусть нашлись пары $(a,b)$ и $(c,a).$ Тогда из одной пары следует, что значение $a$ принимается, а из другой — что значение не принимается, противоречие.

$2.$ Пусть нашлись пары $(a,b)$ и $(a,c),$ тогда $f(b)=a =f(c),$ а значит в силу инъективности $b= c,$ то есть это одна и та же пара.

$3.$ Пусть нашлись пары $(b,a)$ и $(c,a),$ тогда $f(a)= b$ и $f(a)= c,$ откуда $b= c,$ то есть опять же пары совпали.

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

Ответ:

Таких функций не существует

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

Задача 14#80946

Найдите все $f :ℚ → ℚ , >0 >0$ для любого $x∈ ℚ >0$ удовлетворяющие $f(x)+f (1)= 1 x$ и $f(1+ 2x)= f(x). 2$

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

Докажем, что значение функции определено однозначно для любой рациональной точки $p q$ где $p,q$ — натуральные взаимно простые числа. Доказывать будем индукцией по $p +q.$ Проверим базу для $p+ q = 2.$ Подставив $x= 1$ в первое уравнение, получаем, что $1 f(1)= 2.$

Теперь будем доказывать переход. Пусть верно для $2≤ p+q ≤n,$ докажем для $p+q =n +1.$ Предположим, что $p> q$ и оба числа нечетные. Подставим во второе уравнение $p−q- x = 2q .$ Тогда $p p−q- f(q)= f(2q )∕2,$ причем у дроби $p−q 2q$ числитель и знаменатель четны, тогда их сумма в несократимой записи меньше, чем $p+ q,$ следовательно мы однозначно восстановили значение в этой точке.

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

Запустим следующий процесс. Изначально напишем на доске дробь $p q.$ Далее, если на очередном шаге написана дробь $a b,$ где $b$ — четное, $a,b$ взаимно просты, $a+ b=p +q,$ то заменяем ее на дробь $2 ab +1 = 2a+bb-= a+bb∕∕22,$ если же четным числом является $a,$ а также $a,b$ взаимно просты, $a+ b= p+q,$ то сначала заменим дробь на $ba,$ а потом сделаем то же самое. Заметим. что сумма числителя и знаменателя дроби на доске не увеличивается. Если она уменьшилась, то мы пришли к дроби, для которой значение функции определено. Тогда откатившись назад с помощью $2$ уравнений из условия мы однозначно восстановим значение нашей дроби. Если же сумма всегда равна $p+ q,$ то поскольку дробей конечное число, то рано или поздно мы зациклимся (то есть из некоторой дроби придем в нее же). Пусть значение функции $f$ от этой дроби равно $x.$ Тогда на каждом шаге значение заменялось либо на $1− x,$ либо на $x∕2.$ И в итоге мы пришли опять в $x.$ Заметим, что у нас получилось линейное уравнение относительно $x,$ причем коэффициент при $x$ не равен $0,$ поскольку с одной стороны он равен $1,$ а с другой — $± 12k-$ для некоторого натурального $k.$ То есть из этого уравнения мы однозначно восстановим $x,$ но тогда откатившись из $x$ назад, мы восстановим значение $f$ и в исходной точке.

То есть мы доказали, что $f$ определена однозначно. Осталось лишь проверить, что $f(x)= x1+1$ подходит.

Ответ:

$f(x)=-1- 1+x$

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

Задача 15#80947

Найдите все функции $f: ℕ ×ℕ → ℕ,$ для которых выполнены соотношения

f(x,x)= x,f(x,y)=f(y,x),(x +y)f(x,y)= yf(x,x+ y)

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

Пусть $[x,y]$ — НОК $(x,y).$ Введём такую функцию $g(x,y): ℕ ×ℕ → ℤ,$ что $f(x,y)= [x,y]+g(x,y).$ Индукцией по сумме $x+ y$ покажем, что $g(x,y)$ — тождественный ноль.

База: $f(1,1)= 1+g(x,y) =1,$ откуда $g(1,1)=0,$ что и требовалось.

Переход: Распишем равенство $(x+ y)f(x,y)=yf(x,x +y)$ через функцию $g$ ( $x$ и $y$ будем записывать как $′ ax$ и $′ ay,$ где $a$ — $(x,y)$ ):

(ax′+ ay′)(ax′y′+g(x,y))= ay′(ax′(x′+ y′)+ g(x,x+ y))

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

$(x+ y)g(x,y) =yg(x,x+ y).$

Теперь рассмотрим выражение $g(x,n +1 − x),$ где $x$ — натуральное число, не большее $n+1- 2 .$ Пусть $n+1 − x =x +t,$ тогда $g(x,n +1− x)= g(x,x+ t).$

По полученному выше равенству имеем: $(x+ t)g(x,t)=tg(x,x+ t).$ Заметим, что $x+t≤ n,$ тогда по предположению $g(x,t)= 0,$ а значит и $g(x,x +t)= 0.$

Таким образом, единственная подходящая функция — $f(x,y)=$ НОК $(x,y).$

Ответ:

$f(x,y)=$ НОК $(x,y)$

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

Задача 16#80948

Найдите все $f :ℤ → ℤ , ≥0 ≥0$ для которых при любых $x,y ∈ ℤ ≥0$ выполнено $f(x2 +y2)= x⋅f(x)+ y⋅f(y)$

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

Сначала подставим $x =y =0$ в исходное уравнение. Получим $f(0)=2f(0),$ откуда $f (0)= 0.$ Далее, подставив $y = 0,$ получаем, что $( 2) f x = xf(x).$

Докажем индукцией по $n,$ что $f(n)=nf (1).$

Базу будем проверять для всех $n = 1,2,3,4,5,6,8,10.$

Утверждение для $n =1$ очевидно.

Утверждение для $n =2$ следует из подстановки $x= y = 1.$

Утверждение для $n =5$ следует их подстановки $x= 2,y = 1.$

Утверждение для $n =4$ следует из того, что $(2) f x = xf(x).$

Утверждение для $n =8$ следует из подстановки $x= y = 2.$

Далее заметим, что при подстановке $( ) x= ka2− b2 ,y =2kab:$

( ( ) ) ( ) ( ( )) ( ) ( ( )) f k2 a2+ b2 2 = k a2+b2 f k a2+b2 =k a2− b2f k a2− b2 + 2kabf(2kab)

k (a2+ b2)f (k (a2+ b2))= k(a2− b2)f(k(a2− b2))+ 2kabf(2kab)

Утверждение для $n =3$ следует из подстановки в полученное равенство $a= 2,b=1,k= 1.$

Утверждение для $n =10$ следует из подстановки в исходное уравнение $x =3,y = 1.$

Утверждение для $n =6$ следует из подстановки в последнее равенство $a= 2,b =1,k= 2$ и предыдущих утверждений.

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

( ) ( ( ) ) ( ( ) ) kf(k)+ k−-5f k−-5 = f k2+ k-− 5 2 = f (k− 2)2+ k-+3 2 = 2 2 2 2

( ) ( ( ) ) = (k− 2)f (k− 2)+ k+-3f k+-3 =f (1) (k− 2)2+ k-+3 2 2 2 2

То есть

( ( )2 ( )2) kf (k)= f(1) (k − 2)2+ k+-3 − k−-5 =k2f(1) 2 2

откуда $f(k)= kf(1).$

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

k− 10 (k− 10) ( ( k− 10)2) ( ( k+6 )2) kf (k)+ --2--f --2-- =f k2+ --2-- = f (k− 4)2 + -2-- =

k+-6 (k+-6) ( 2 (k-+6)2) = (k− 4)f (k− 4)+ 2 f 2 =f (1) (k− 4)+ 2

То есть

( ( ) ( ) ) kf(k)= f(1) (k− 4)2+ k-+6 2− k−-10- 2 = k2f(1) 2 2

откуда $f(k)= kf(1).$

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

Ответ:

$f(x)= kx$ для всех $x∈ ℤ ≥0$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

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

Задача 17#44071

Найдите наибольшее значение выражения

(5n− 18)НОД-(n-+9,n+-2) F = НОК(n+ 9,n +2)

на множестве натуральных чисел. При каком $n$ оно достигается?

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

Подсказка 1

Числа n+2 и n+9 это же достаточно близкие числа, при этом их разность равна 7. Что тогда можно сказать про их НОД?

Подсказка 2

Да, их НОД либо равен 1, либо равен 7. Обозначим его за d. Какая замена тогда просится, если у нас есть НОК и НОД одних и тех же чисел?

Подсказка 3

Ну конечно, замена НОК(a,b)=ab/НОД(a,b). Тогда наше выражение принимает понятный вид. Осталось исследовать функцию, которая получается делением нашего выражения на d^2 и понять, где она принимает максимальное значение.

Подсказка 4

Да! В точке 12. А что еще принимает максимальное значение в точке 12? Поймите это и получите ответ!

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

Обозначим $d= НОД (n +9,n+ 2).$ Так как $n+ 9$ и $n+ 2$ делятся на $d,$ то их разность $(n +9)− (n +2)= 7$ делится на $d.$ Тогда $d =1$ или $d= 7.$

Как известно, $НОК(a,b)⋅НО Д(a,b)= a⋅b,$ откуда выражение из условия принимает вид

(5n− 18)⋅d2 F (n)= (n+-2)(n+-9)

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

G (x)= ---5x-− 18-, x> 0 (x+ 2)(x+ 9)

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

′ 5(x2+-11x+-18)−-(5x−-18)(2x+-11)- (x-− 12)(5x+-24) G(x)= (x +9)2(x+ 2)2 =− (x+ 2)2(x+9)2

Производная при $x> 0$ имеет ровно одну точку экстремума $x =12$ (это кстати натуральное число), которая является точкой максимума, потому является глобальным максимумом при $x> 0.$ А ещё удачным образом при $n= 12$ имеем $d =7$ — также принимает максимальное значение, потому при $n = 12$ достигает максимума и функция $F.$ Равен этот максимум

--5⋅12−-18-- F(12)= (12+9)(12+ 2) ⋅49= 7

Ответ:

$7$ при $n= 12$

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

Задача 18#65398

Функция $g$ определена на целых числах и принимает целые значения, причем $g(x)⁄=x$ для каждого целого $x$ . Назовем число $a$ красивым, если для любого целого числа $x$ выполнено $g(x)=g(a− x)$ . Может ли каждое из чисел 739 и 741 быть красивым?

Источники: ОММО-2021, номер 9, (см. olympiads.mccme.ru)

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

Подсказка 1

Попробуйте предположить, что оба этих числа являются красивыми, и используйте условие для установления связи между f(x+2) и f(x)

Подсказка 2

Эти значения функции должны оказаться одинаковыми для любого х! Какие свойства функции нам это дает?

Подсказка 3

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

Подсказка 4

Можно подставить x=0 и использовать условие "красивости" числа 739 для того, чтобы установить f(x)≡c. Осталось использовать условие, что не может быть f(x)=x, и задача в кармане!

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

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

g(x+ 2)=g(741 − (x+ 2))= g(739− x)= g(x)

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

С другой стороны, если $739$ оказалось красивым, то $b= g(0)= g(739− 0)= c.$ Тогда $g(x)$ равна какой-то целочисленной константе для любого аргумента $x.$ Получаем противоречие с условием $g(x)⁄= x$ при значении аргумента, равном этой челочисленной константе.

Ответ: нет

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

Задача 19#65465

Для всех неотрицательных значений вещественной переменной $x$ функции $f(x)$ выполняется условие

-----43---- f(x+ 1)+1= f(x)+(x+ 1)(x+ 2)

Вычислите $101 f(2020)$ , если $f(0)= 2020$ .

Источники: ШВБ-2020, (см. olymp.bmstu.ru)

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

Подсказка 1

В равенстве из условия можно выразить f(x+1) через f(x). Кажется, это намекает на какую-то рекурсию, попробуем выразить f(x) через f(x-1) и т.д. Заметна ли какая-то закономерность?

Подсказка 2

Да, на самом деле для натурального n можно выразить f(n) через f(0) = 2020, получится равенство f(n) = 2020 - n + 43(1/(1×2) + 1/(2×3) + ... + 1/(n×(n+1))). Подумайте, как можно свернуть сумму дробей в скобках.

Подсказка 3

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

Подсказка 4

1/(k(k+1)) = 1/k - 1/(k+1), тогда все члены сокращаются, кроме первого и последнего, получаем f(n) = 2020 - n + 43(1 - 1/(n+1)). Что можно применить, чтобы доказать эту формулу для любого натурального n?

Подсказка 5

Конечно же, индукцию! База легко проверяется, переход также несложно доказывается. Остаётся посчитать f(2020) :)

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

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

-1-- f(n)= 2020− n +43(1− n+ 1)

_________________________________________________________________________________________________________________________________________________________________________________

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

f(0)= 2020− 0 +43(1 − 1)= 2020

_________________________________________________________________________________________________________________________________________________________________________________

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

43 ( 1 ) 43 f(n+ 1)=− 1+f(n)+ (n-+1)(n-+2)-=2020− n +43 1− n+1- − 1+ (n-+1)(n-+2) =

( ) ( ) 2020− (n+ 1)+ 43 1+ -----1-----− --n-+2---- = 2020− (n +1)+ 43 1− ---1---- (n+ 1)(n+ 2) (n +1)(n +2 (n+ 1)+ 1

_____________________________________________________________________________________

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

f(2020)= 2020− 2020+ 43(1−--1---)= 2020= 101⋅20- 2020+ 1 47 47

_________________________________________________________________________________________________________________________________________________________________________________

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

f(n)=f(n− 1)− 1+---43---= f(n − 2)− 2+43(--1---+---1---)= n(n+ 1) n(n+ 1) n(n− 1)

1 1 1 = f(n− 3)− 3+ 43(n(n+-1) + (n-− 1)n + (n−-2)(n−-1))=

= f(0)− n+ 43(--1---+ ---1---+...+ -1-)= n(n+ 1) (n− 1)n 1⋅2

1 --1- --1- 1 1 1 =f(0)− n +43(n − n+ 1 + n − 1 − n + ...+ 1 − 2)=

1 =2020− n+43(1− n+-1)

Ответ:

$47 20$

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

Задача 20#124047

Найдите и докажите явное выражение (в терминах известных операций на целых числах) для функции $g(m,n),$ вычисляющей пару чисел $(p,q),$ и определенной следующим образом для любых целых значений $m ∈[0...100]$ и любых целых значений $n ≥0 :$

g(m,n)= (m,n+ 1), если m = 100, иначе (p− 1,q), где (p,q)= = g(g(m +1,n)).

Источники: Иннополис - 2020, 11.2 (см. lk-dovuz.innopolis.university)

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

Подсказка 1

Давайте для начала попробуем вычислить некоторые значения функции g.

Подсказка 2

Возьмем m, близкое к 100, например, 98.

Подсказка 3

g(98, n) = (p₁ - 1, q₁). Заметьте, что (p₁, q₁) = g(g(99, n)). Продолжите эти вычисления, пока не сможете выразить g(98, n) через числа и, возможно, n.

Подсказка 4

У нас должны получиться явные выражения для g(98, n), g(99, n) и (p₁, q₁). Это будет в следующей подсказке, но постарайтесь дойти самостоятельно.

Подсказка 5

g(98, n) = (98, (n + 4)); g(99, n) = (99, (n + 2)); g(100, n) = (100, (n + 1)). Есть ли тут какая-то зависимость?

Подсказка 6

Возникает предположение, что g(m, n) = (m, (2¹⁰⁰⁻ᵐ + n)). Попробуйте это доказать.

Подсказка 7

Перепишем формулу следующим образом: g((100 - m), n) = ((100 - m), (2ᵐ + n)). Докажем это индукцией по m ≥ 0.

Подсказка 8

При m = 0 все получится, это база индукции. Теперь надо доказать для (m + 1). Подставим его в формулу.

Подсказка 9

По предположению индукции, g((100 - m), n) = ((100 - m), (2ᵐ + n)) (при k = m). Раскройте выражения, как в самом начале, и получите требуемое.

Показать доказательство

Докажем индукцией по $m ≥ 0,$ что для любого целого положительного $n≥ 0$ выполняется

m g((100− m),n) =((100− m),(2 +n))

База индукции $(m =0)$ :

g((100− 0),n)= g(100,n)= (100,(1+n))

По формуле, которую мы доказываем, при $m = 0$ :

((100 − 0),(20+ n))= (100,(1 +n))

База верна.

Индукционная предположение: Пусть для всех $k∈ [0,...,m]$ и для любого $n≥ 0$ верно

g((100− k),n)= ((100 − k),(2k+ n))

Шаг индукции (для $m+ 1$ ):

Нам нужно доказать, что

g((100− (m + 1)),n)=((100− (m+ 1)),(2m+1 +n))

1.: $g((100− (m + 1)),n)=(p− 1,q),$ где $(p,q)= g(g((100− m),n))$ (по определению функции $g,$ если первый аргумент не $100).$
2.: $g((100− m),n)=((100− m),(2m + n))$ по предположению индукции (для $k= m).$
3.: $g(g((100 − m ),n))=g((100− m),(2m +n))$ согласно пункту $2.$
4.: $g((100− m),(2m +n))= ((100− m ),(2m+ (2m + n)))$ по предположению индукции, применяя его к $g((100− k),n′)$ где $k =m$ и $n′ =2m + n.$
5.: $g(g((100 − m ),n))=((100− m ),(2⋅2m + n))= ((100− m),(2m+1+ n))$ согласно пунктам $3$ и $4.$
6.: $(p,q)= ((100− m),(2m+1+ n))$ согласно пунктам $1$ и $5.$
7.: $g((100− (m + 1)),n)=((100− m)− 1,(2m+1 +n))= ((100 − (m +1)),(2m+1 + n))$ согласно пунктам $1$ и $6.$

Что и требовалось доказать.

_________________________________________________________________________________________________________________________________________________________________________________

Замечание. Чтобы догадаться до решения, можно было проделать этот эксперимент: вычислим «символически» значение функции $g$ для какого-либо значения $m,$ близкого к $100,$ например, вычислим $g(98,n) :$

1.: $g(98,n)= (p − 1,q), 1 1$ где $(p ,q)= g(g(99,n)); 1 1$
2.: $g(99,n)= (p − 1,q), 2 2$ где $(p ,q)= g(g(100,n))=g(100,(n+ 1))= (100,(n +2)); 2 2$
3.: $g(99,n)= (p − 1,q)= (99,(n+2)) 2 2$ следует из п. $2;$
4.: $(p ,q )= g(g(99,n)) =g(99,(n+ 2)) 1 1$ следует из п. $1$ и $3;$
5.: $g(99,(n+ 2))= (p3 − 1,q3),$ где $(p3,q3)= g(g(100,(n+ 2)))= g(100,(n+ 3))= (100,(n +4));$
6.: $(p1,q1)= (99,(n +4))$ следует из п. $4$ и $5;$
7.: $g(98,n)= (98,(n +4))$ следует из п. $1$ и $6.$

Из этого эксперимента видно, что

$g(100,n)= (100,n +1)= (100,(2100−100+ n))$ — см. определение функции (предполагая, что $g(100,n)=(100,n+ 1)$ и $100−100 2 +n = 1+n);$
$100−99 g(99,n)= (99,(n +2))= (99,(2 + n))$ — см. пункт $3$ эксперимента;
$100−98 g(98,n)= (98,(n +4))= (98,(2 + n))$ — см. пункт $7$ эксперимента.

Поэтому возникает предположение, что

g(m,n)= (m,(2100−m +n))

$для любых m ∈ [0,...,100] и n ≥ 0,n,m ∈ℤ$