Метод спуска, индукция и последовательное конструирование в ТЧ
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Любое число 
написанное на доске, разрешается заменить либо на 
либо на ![[x].
2](/api/latex-service/v1/GetSession/189752/index-f1ea3beb9886bd49f15161a29b73553e.svg)
Докажите, что если вначале написано число 
то такими операциями можно получить любое натуральное число.
Будем доказывать по индукции по натуральным числам.
База для 
![[4]
1→ 3⋅1+1 =4 → 2 = 2.](/api/latex-service/v1/GetSession/192259/index-7f6033db098ac7d38c736bd28b26d6e2.svg)
Переход:
Докажем, что если мы умеем получать любое число от 1 до 
то сможем получить и 
Рассмотрим остаток при делении 
на
3:
Пусть 
представимо в виде 
Так как по предположению индукции мы умеем получать 
то
остаётся только заменить 
на 
Пусть 
представимо в виде 
Тогда по предположению мы умеем получать 
так как 
Остаётся
выполнить следующие преобразования:
![[ ]
2k→ 3⋅2k +1= 6k+ 1→ 6k+-1 = 3k
2](/api/latex-service/v1/GetSession/192259/index-bba7532531621c1f527a3a5b58601db4.svg)
Пусть 
представимо в виде 
. Тогда по предположению мы умеем получать 
, так как 
.
Остаётся выполнить следующие преобразования:
![[6k+-4]
2k +1→ 3 ⋅(2k+ 1)+1= 6k+ 4→ 2 = 3k+ 2](/api/latex-service/v1/GetSession/192259/index-38b915feda99379b64bb6d309e3b65d4.svg)
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
