Тема . ПитерГор (Санкт-Петербургская олимпиада)

Теория чисел на Питергоре

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

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

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

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

Подтемы раздела питергор (санкт-петербургская олимпиада)

Решаем задачу:

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

Задача 1#89870

Дано натуральное число $a> 1.$ Определим функцию

√ - f(n)= n +[a{n 2}].

Докажите, что существует такое натуральное $n,$ что $f(f(n))= f(n)$ , но $f(n)⁄= n.$

Напомним, что $[x]$ — целая часть $x,$ то есть наибольшее целое число, не превосходящее $x,$ а ${x} =x − [x]$ — дробная часть $x.$

Источники: СПБГОР - 2023, 11.5 (см.pdmi.ras.ru)

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

Для решения задачи нам понадобится два классических утверждения из теории чисел.

_________________________________________________________________________________________________________________________________________________________________________________

Теорема Дирихле. Для любого иррационального числа $𝜃$ и натурального числа $m$ найдется такое число $k$ , $1≤ k≤ m− 1$ , что $1- {k𝜃}< m$ или $1- {k𝜃}> 1− m$ .

_________________________________________________________________________________________________________________________________________________________________________________

Теорема Кронекера. Для любого иррационального числа $𝜃$ и любых чисел $α$ , $β$ , $0 ≤α <β < 1$ , найдется такое натуральное число $n$ , что ${n𝜃}∈ (α,β)$ .

_________________________________________________________________________________________________________________________________________________________________________________

Применим теорему Дирихле для $√ - 1 𝜃 = 2+ a$ и $m =a$ и найдем такое $1≤ k≤ a− 1$ , что

{ √- 1 } 1 { √- 1 } 1 k( 2+ a) < a или k( 2+ a) > 1− a.

______________________________________________________________________________________________________________________________________________________

В первом случае имеем неравенство $a−ak< {k√2}< a+1a−k$ . Применим теорему Кронекера для

𝜃 =√2, α= k и β = a+-1− {k√2}> k, a a a

получим, что найдется такое $n$ , что $k< {n√2}< a+1− {k√2} a a$ . Для этого $n$ имеем

k< a{n√2}< a(a+-1− {k√2})< a( a+1-− a−-k)= k+ 1. a a a

Следовательно, $√- [a{n 2}]=k$ и $f(n)= n+ k$ . Поскольку

k a− k √- √ - a+1- 1= a + a < {n 2}+{k 2} < a ,

дробная часть числа $√- (n+ k) 2$ меньше, чем $1 a$ , поэтому

√- [a{(n +k) 2}]=0.

В итоге $f(n)= n+ k,$ поэтому

f(f(n))= f(n+ k)= n +k= f(n)⁄= n

______________________________________________________________________________________________________________________________________________________

В случае ${k(√2 + 1)}> 1− 1 a a$ выполняется неравенство

a-− k √ - a+1-− k a < {k 2} < a .

Применяя теорему Кронекера для

√ - √ - k+ 1 k+ 1 𝜃 = 2, α= 1− {k 2}< -a-- и β =--a-,

получим, что найдется такое $n$ , что $√- k+1 1< {n 2}< -a-$ . Для этого $n$ имеем

k< a{n√2}< k+ 1.

Следовательно, $√- [a{n 2}]=k$ и $f(n)= n+ k$ . Поскольку

√ - √- 1< {n 2}+{k 2} <1− ka + k+a1-= a+a-1,

дробная часть числа $√- (n+ k) 2$ меньше, чем $1a$ , поэтому

[a{(n +k)√2}]=0.

В итоге $f(n)= n+ k,$ поэтому

f(f(n))= f(n+ k)= n +k= f(n)⁄= n

Нужна консультация? Задайте нам вопрос в чате.

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

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

Бесплатное онлайн-обучение

Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

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

Бесплатное онлайн-обучение

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

Теория чисел на Питергоре

Специальные программы

Программалояльности v2.0

Крути рулеткуи выигрывай призы!

Бесплатное онлайн-обучение

Налоговые вычеты

Специальное предложениедля учителей

Вернём деньги за курсза твою сотку на ЕГЭ

Программалояльности v2.0

Крути рулеткуи выигрывай призы!

Бесплатное онлайн-обучение

Налоговые вычеты

Специальное предложениедля учителей

Вернём деньги за курсза твою сотку на ЕГЭ

Программа
лояльности v2.0

Крути рулетку
и выигрывай призы!

Специальное предложение
для учителей

Вернём деньги за курс
за твою сотку на ЕГЭ

Программа
лояльности v2.0

Крути рулетку
и выигрывай призы!

Специальное предложение
для учителей

Вернём деньги за курс
за твою сотку на ЕГЭ