Функции на Иннополисе
Ошибка.
Попробуйте повторить позже
Найдите и докажите явное выражение (в терминах известных операций на целых числах) для функции 
вычисляющей пару
чисел 
и определенной следующим образом для любых целых значений ![m ∈[0...100]](/api/latex-service/v1/GetSession/255449/index-0089bc9f25dbad385721d6cc88cebf11.svg)
и любых целых значений
Источники:
Подсказка 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). Раскройте выражения, как в самом начале, и получите требуемое.
Докажем индукцией по 
что для любого целого положительного 
выполняется
База индукции 
:
По формуле, которую мы доказываем, при 
:
База верна.
Индукционная предположение: Пусть для всех ![k∈ [0,...,m]](/api/latex-service/v1/GetSession/257619/index-a1064ea732a4b9193d4ab9d66d55535d.svg)
и для любого 
верно
Шаг индукции (для 
):
Нам нужно доказать, что
- 1.
-
где 
(по определению функции 
если первый аргумент не
- 2.
-
по предположению индукции (для 
- 3.
-
согласно пункту 
- 4.
-
по предположению индукции, применяя его к 
где
и 
- 5.
-
согласно пунктам 
и 
- 6.
-
согласно пунктам 
и 
- 7.
-
согласно пунктам 
и 
Что и требовалось доказать.
_________________________________________________________________________________________________________________________________________________________________________________
Замечание. Чтобы догадаться до решения, можно было проделать этот эксперимент: вычислим «символически» значение функции 
для какого-либо значения 
близкого к 
например, вычислим 
- 1.
-
где 
- 2.
-
где 
- 3.
-
следует из п. 
- 4.
-
следует из п. 
и 
- 5.
-
где 
- 6.
-
следует из п. 
и 
- 7.
-
следует из п. 
и 
Из этого эксперимента видно, что
— см. определение функции (предполагая, что 
и
— см. пункт 
эксперимента;
— см. пункт 
эксперимента.
Поэтому возникает предположение, что
![для любых m ∈ [0,...,100] и n ≥ 0,n,m ∈ℤ](/api/latex-service/v1/GetSession/257619/index-fc2c39b3a4d73aba0aa3fb259ca0cfdb.svg)
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
