Как додуматься до решения олимпиадной задачи — 2

В прошлый раз я рассказывал о ходе своих мыслей при решении олимпиадной задачи. Может быть такие рассказы помогут кому-нибудь, кто хочет выработать нестандартное мышление. В этот раз расскажу о ходе решения еще одной задачи, которую разбирал Савватеев. По его словам, за 5 минут он решения не нашел, и зрителям думать не советовал. Но я не послушал и додумался до решения самостоятельно.

Условие задачи

Есть 3 различных натуральных числа $$x$$, $$y$$, $$z$$. Эти числа оказались подобраны так, что выражение

$$A={xy+yz+zx\over x+y+x}$$

тоже натуральное. Каким числом оно может быть? Иными словами, каково пересечение множества значений этой функции трех натуральных переменных и множества натуральных чисел?

Поиск решения

Идея №1: вынести в числителе за скобки $$xyz$$. Получается

$$A={\left({1\over x}+{1\over y}+{1\over z}\right)xyz\over x+y+x}.$$

Из этого я заметил, что при замене величин $$x$$, $$y$$ и $$z$$ на обратные $$1/x$$, $$1/y$$ и $$1/z$$ выражение «переворачивается», то есть $$A$$ меняется на $$1/A$$. Дальше у идеи не было очевидного развития, я решил попробовать другие идеи.

Идея №2: масштабирование. Видно, что если выполнить замену $$x$$, $$y$$ и $$z$$ на $$kx$$, $$ky$$ и $$kz$$, то числитель $$A$$ вырастет в $$k^2$$ раз, а знаменатель в $$k$$ раз, то есть $$A$$ меняется на $$kA$$. Как это можно применить? Пусть мы выбрали натуральные числа равными 1, 2 и 3. Тогда

$$A={2+6+3\over 1+2+3}={11\over 6}.$$

Чтобы из этого набора получить целое $$A=11$$, можно взять не 1, 2 и 3, а 6, 12 и 18.

Однако я не стал развивать дальше эту идею из-за ошибки. Мне показалось, что $$A$$ меняется не на $$kA$$, а на $$k^2A$$, и я пропустил условие, что числа могут быть различными. Так что мне показалось, что, подставив $$x=y=z=1$$, можно получить квадраты натуральных чисел 1, 4, 9,... Я понимал, что задача не такая простая, поэтому хотел проанализировать случай различных $$x$$, $$y$$ и $$z$$ (хотя по условию только их и надо анализировать), и перешел к дальнейшему рассмотрению.

Идея №3: перебор вариантов.

Чтобы прочувствовать задачу, часто бывает полезно рассмотреть некоторые частные случаи. В задачах вроде этой подобрать $$x$$, $$y$$ и $$z$$, чтобы выражение действительно было целым. В геометрических задачах бывает полезно нарисовать на черновике хороший чертеж, чтобы заметить закономерности вроде расположения точек на одной прямой или окружности.

Для перебора будем фиксировать значения $$x$$, $$y$$ и изменять $$z$$. Пусть $$x=y=1$$ (я проделал эту лишнюю работу, потому что невнимательно прочитал условие).

$$A={1+z+z\over 1+1+z}={1+2z\over 2+z}={4+2z-3\over 2+z}=2-{3\over 2+z}.$$

Ясно, что $$A=1$$ при $$z=1$$, а значение $$A=2$$ ни при каком $$z$$ не будет достигнуто.

Пусть $$x=1, y=2$$. Тогда

$$A={2+2z+z\over 1+2+z}={2+3z\over 3+z}.$$

Если $$z$$ нечетное, то числитель нечетный, знаменатель четный, $$A$$ не будет целым. Если $$z$$ четное, то числитель четный, знаменатель нечетный. Здесь я сделал еще одну ошибку, подумав, что четное число не может делиться на нечетное, и вообще исключил из рассмотрения варианты с $$x$$ и $$y$$ разной четности.

Пусть $$x=1, y=3$$. Тогда

$$A={3+3z+z\over 1+3+z}={3+4z\over 4+z}.$$

Здесь исключаем случай четного $$z$$, так как нечетный знаменатель не будет делиться на четный числитель. Попробуем подставить разные нечетные $$z$$. Получим:

$$ z=1\implies A={7/5}\\ z=3\implies A={12/7}\\ z=5\implies A={23/9}\\ z=7\implies A={31/11}\\ z=9\implies A={39/13}=3\\ z=11\implies A={47/15}\\ $$

Далее, сколько бы мы ни увеличивали $$z$$, до значения 4 мы не дойдем, так как 4 достигается только в пределе $$z\to\infty$$. Таким образом, при $$x=1, y=3$$ единственное целое $$A$$ дает $$z=9$$.

Пусть $$x=1, y=5$$. Тогда

$$A={5+5z+z\over 1+5+z}={5+6z\over 6+z}.$$

Перебор $$z$$ слишком долгий, и мы понимаем, что возможных значений $$A$$ не так уж много. Поэтому решим уравнение относительно $$z$$:

$$5+6z=A(6+z)\iff(6-A)z=6A-5\implies z={6A-5\over 6-A}.$$

Отсюда видно, что $$A$$ не может быть четным. 1 и 3 не подходят, $$A=5$$ дает $$z=25$$, других значений для проверки нет.

Мы видим, что значения переменных (1, 3, 9) и (1, 5, 25) дают целые значения $$A$$. Кажется, это и есть нужная закономерность.

Решение

Подставим значения $$x=1, y=n, z=n^2$$. Тогда

$$A={n+n^3+n^2\over 1+n+n^2}=n\,{1+n^2+n\over 1+n+n^2}=n.$$

Таким образом, мы можем в качестве значения выражения получить любое натуральное число, не равное 1. То, что 1 получить нельзя, посмотрите у Савватеева или докажите самостоятельно.

Обсуждение ошибок

После подстановки $$x=1, y=n, z=n^2$$ моя ошибка с четностью стала очевидной. Сначала мне вообще не хотелось писать об ошибках. Признаваться в них не очень приятно. Но с другой стороны, благодаря ошибкам на этапе поиска решения я довольно быстро нашел правильное решение. Могло бы оказаться так, что я углубился в разработку какой-нибудь другой тупиковой идеи и не довел бы решение до конца. Особенно важно такое чутье на самой олимпиаде в условиях ограниченного времени.

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

Необычный сон и шутка про банки

Сегодня мне приснился странный сон.

В моем сне Иван Голунов ведет новости или какой-то другой прямой эфир. К этому эфиру по видеосвязи подключен Владимир Рыжков. Голунов цитирует некоторую новость, в которой использовано слово «функционал». Они обсуждают, что функционал — это не то, о чем думает большинство. Рыжков замечает, что употребление слова неправильное, но заменить его нечем (на самом деле правильный термин — «функциональность»).

Дальше Голунов говорит Рыжкову: «А помните, как та шутка — „банк — он же не on-shell“». На этом я проснулся и не поленился записать саму фразу. Давайте разбираться, какой глубокий смысл в ней скрыт, и какой могла быть эта шутка (в реальности я ничего похожего не припомню).

Термины on-shell и off-shell — это жаргон из квантовой теории поля. Дословно они означают «на (массовой) поверхности» и «вне (массовой) поверхности». Под массовой поверхностью имеется в виду многомерный график соотношения между энергией и импульсом E²−p²=m². О настоящих частицах, для которых как раз выполняется закон сохранения энергии, говорят, что они находятся на массовой поверхности. А вот для виртуальных частиц, которые возникают в квантовой теории поля как вспомогательные объекты, закон сохранения энергии не выполняется, поэтому говорят, что они вне массовой поверхности: E²−p²≠m².

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

Таким образом, фраза «банк — он же не on-shell» по смыслу эквивалента «для банка не выполняется закон сохранения». Какой закон сохранения неприменим к банкам? Очевидно, закон сохранения количества денег. Во-первых, банки не держат у себя все деньги вкладчиков. Эти деньги выдаются в виде кредитов, что увеличивает количество денег в экономике. Во-вторых, кредитные деньги ничем не отличаются от других денег. Они из оборота могут вновь попасть на депозиты, вновь могут быть выданы в виде кредитов и т. д. В экономике даже есть понятие банковского мультипликатора, которое описывает эту бесконечную историю.

Итак, шутка из сна могла быть про диалог двух физиков:
— Не могу понять, как банк может выдать кредитов больше, чем у него есть денег вкладчиков.
— Банк — он же не on-shell!
Можете воспользоваться, если окажетесь в компании физиков, обсуждающих экономику :)

Самая большая загадка: каким образом это всё оказалось в моем сне? Я иногда про себя отмечаю ошибку с употреблением слова «функционал» вместо «функциональность» в речи других, поэтому эта часть как раз не удивительна. Почему во сне были Голунов и Рыжков — не понимаю, я давно о них ничего не слышал. Термины on-shell и off-shell я не использовал много лет. И как вообще мозг во сне смог построить такую цепочку ассоциаций?

Савватеев и Шпилькин разбирают статистику с выборов

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

Пару раз они забылись и произнесли понятные только специалистам термины вроде «минимального детерминанта матрицы ковариации», но на восприятии основного посыла это не сказалось.

Переезд сайта на parpalak.com

На выходных перевел этот сайт с домена written.ru на parpalak.com. Я затеял этот переезд не только из-за красоты домена, которая не особо-то и нужна в современном интернете победивших соцсетей, а скорее из-за изменений в российском интернете.

---

Домен второго уровня я решил зарегистрировать в 2006 году. Рассматривал разные варианты. Домен parpalak.ru оказался занятым. По данным whois его зарегистрировал некий Орест Парпалак. Никакого сайта на этом домене не было, домен использовался для почты. Домен roma.ru тоже оказался занятым. Сейчас по нему открывается сообщение, что домен не продается. А вот раньше там была даже фотография, возможно того самого Ромы.

В итоге я зарегистрировал written.ru. Идею взял у Ромы Воронежского с его сайтами narisoval.ru и napisal.ru, просто перевел слово «написал» на английский.

В 2017 году я обнаружил, что домен parpalak.ru освободился, и зарегистрировал его. Через некоторое время зарегистрировал и parpalak.com, на случай если захочу сделать англоязычный сайт. Кстати, с последним доменом произошла интересная история. Я прописал у регистратора ns-серверы своего хостинга (ns1.linode.com), а в хостинге домен не добавил. Какой-то хитрый пользователь этого хостинга обнаружил это и добавил домен parpalak.com к себе. После чего у меня уже не получилось его добавить. К счастью, никакого контента на сайте по A-записям не оказалось. Я написал в поддержку и проблема была сразу же решена.

---

И вот наступил 2021 год. Государство на полном серьезе принялось «регулировать» интернет (на хабре недавно вышел обзор изменений за последние полгода). Я решил, что пора заняться вопросом информационной безопасности. Не то чтобы я ощутил какую-либо угрозу здесь и сейчас. Но и игнорировать политическую обстановку и произвол силовиков тоже нельзя. Составил контрольный список:

• хостинг — в Европе, ничего делать не надо;
• почта — яндексовская, есть риск взлома или потери;
• домены у российских регистраторов — есть риск отключения или потери.

Я решил оставить российские домены у российских регистраторов и принять соответствующие риски. Остальные домены перенес к регистратору NameSilo. Ссылка реферальная: если решите воспользоваться рекомендацией, получу немного денег. Вроде бы у них самые дешевые домены: домен .com чуть дешевле 10 долларов. Кроме покупки можно переносить имеющиеся домены. Для переноса нужно получить у текущего регистратора код авторизации (примерно так же я переносил домены от Ру-центра к Бегету). Причем NameSilo позаботился, чтобы клиенты из-за переноса ничего не теряли: сам перенос стоит чуть дешевле годовой стоимости домена, а к текущему сроку регистрации добавляется год.

В итоге я перенес от российских регистраторов домены редактора математических текстов Upmath, головоломки Арнольда и s2cms.com. Для черновиков физика зарегистрировал новый домен susy.page вместо susy.written.ru. Киноблог и сайт программы с игрой «Жизнь» остались на своих доменах kinoblog.su и life.written.ru, мне их не жалко.

Последним шагом, как и написал в самом начале, сделал основным доменом parpalak.com вместо written.ru. Этим шагом решается и проблема почты. Дело в том, что почтовым сервисом для written.ru я настроил в 2010 году яндексовскую почту для домена, которая перенаправляет все входящие на гугловскую почту. С этим я ничего делать не буду. Просто сделаю основным почтовый ящик на другом домене.

---

После переезда обнаружилась только одна небольшая проблема — feedly заново показал последние посты. Скорее всего из-за изменения УРЛов, так как они использовались как идентификаторы записей:

<guid isPermaLink="true">https://parpalak.com/blog/2021/09/12/smart_vote</guid>

При этом feedly проигнорировал поле pubDate и показал записи как свежие. Можно было избежать этой проблемы, если специально для RSS запоминать адреса записей. Но я не думаю, что хоть кто-либо когда-либо озаботился и запрограммировал такую фичу.

Умное голосование как второй тур

Умное голосование — это как второй тур на выборах без второго тура. Давайте переквалифицируемся из вирусологов и востоковедов опять в политологи и порассуждаем на эту тему.

Голосование на выборах бывает устроено множеством разных способов: в один тур часто выбирают парламенты, в два тура — президентов. В Америке президента вообще избирают промежуточные выборщики.

Голосование через неделю, 19 сентября, будет происходить по смешанной системе: половина мест в парламенте распределяется между партийными списками, половина мест — по одномандатным округам. Каждый избиратель голосует за одну из партий по общему (федеральному) списку и за одного из кандидатов по местному округу.

Стратегия голосования по федеральному списку для тех, кому надоела несменяемость власти, не изменилась: голосуй за любую партию кроме партии жуликов и воров. При следовании этой стратегии количество мест у жуликов и воров будет снижаться.

Стратегия голосования по одномандатному списку не так очевидна. Место в Думе получает кандидат, набравший наибольшее число голосов. При этом второго тура нет: даже если единорос набрал 20%, а 80% размазались по остальным кандидатам, в Думу пройдет единорос. Задача умного голосования — исключить размазывание голосов по кучке кандидатов. Если бы голосование по одномандатным округам проходило в два тура, то в первом туре можно было бы голосовать за понравившегося кандидата, а во втором туре — за наименее противного. К сожалению, второго тура нет, поэтому приходится изобретать костыли вроде умного голосования.

Оппоненты умного голосования утверждают, что в других партиях люди не сильно лучше, и даже если Единая Россия не получит большинства в думе, мы вряд ли проснемся следующий день в другой стране. Нас убеждают, что нельзя голосовать за коммунистов, сталинистов, националистов и прочих «истов». Какой тогда смысл голосовать за кого-либо?

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

Логотип Медузы и энергия

Интервью с Григорием Кравченко, автором логотипа Медузы. Извините, не могу не процитировать:

«Медуза» делалась с колоссальной энергией. Тебе сузили пространство, ты весь напрягся, и эта кинетическая энергия должна распрямиться и на максимуме сделать что-то очень быстрое, агрессивное. Это злость, но она в итоге позитивная, не вредная. Тебе нужно отреагировать, у тебя что-то отобрали — и ты хочешь сделать новое.

Тут всё хорошо, но когда сужают пространство и ты напрягаешься, накапливается потенциальная энергия, а не кинетическая.

Поиграл на рояле в аэропорту

Как просили в прошлый раз в комментариях, снял на видео, как поиграл в аэропорту. Не без ошибок, потому что клавиатура непривычная: черные клавиши оказались слишком тонкие. Да и месяц не садился за инструмент. Вот несколько фрагментов:

0:00 Разминка
1:20 Chilly Gonzales — Dot
1:51 Roman Parpalak — Ursa Minor
3:39 Ludovico Einaudi — Nightbook
5:22 Chilly Gonzales — Gogol
6:25 Secret Garden — Song from a Secret Garden

Фейковый pop3-сервер

Я оказался в ситуации почти без доступа к некоторому почтовому ящику. Пароль не помнил, но этот пароль был сохранен в почтовом клиенте The Bat. Почтовик вроде как защищает пароль: его нет в открытом виде в конфиге и его нельзя скопировать из окна настройки:

Когда-то давно в аналогичной ситуации я установил анализатор трафика и взял пароль из сетевого пакета. С тех пор поддержку нешифрованного подключения через pop3 на сервере отключили, и такой фокус уже не проходит.

Я стал думать и сообразил, что фокус с перехватом трафика получился бы, если бы я подменил pop3-сервер на свой, который не требует никакого шифрования. К счастью, The Bat позволяет изменить сервер, не требуя повторного ввода пароля. Так что я ввел в это окошко локальный адрес, отключил шифрование и смог подключиться к локальному «серверу».

Чтобы не ставить настоящий сервер, нагуглил скрипт фейкового pop3-сервера. Вместе с этим пришлось узнать, что делает команда CAPA. У меня заработал такой вариант:

#!/usr/bin/env python
import socket

c = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
c.bind(('192.168.0.203',110))
c.listen(1)

while 1:
    csock, caddr = c.accept()
    cfile = csock.makefile('rw', 0)
    print "Connection accepted."
    cfile.write("+OK POP3 PROXY server ready mail.server.com\r\n")

    line = cfile.readline().strip()
    print "LINE: " + line
    cfile.write("+OK\r\nUSER\r\n.\r\n")

    line = cfile.readline().strip()
    print "LINE: " + line
    cfile.write("+OK\r\n")

    line = cfile.readline().strip()
    print "LINE: " + line
    cfile.write("+OK\r\n")

    line = cfile.readline().strip()
    print "LINE: " + line
    cfile.write("+OK\r\n")

    line = cfile.readline().strip()
    print "LINE: " + line
    cfile.write("+OK\r\n")

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

roman@zeta:~$ sudo python pop3.py
Connection accepted.
LINE: CAPA
LINE: USER example
LINE: PASS password
LINE: STAT
LINE: QUIT

Серебристые облака — 5

Сегодня были хорошие условия для наблюдения серебристых облаков.

Кстати, а сегодня-то у этого сайта день рождения, 16 лет :)

Как додуматься до решения олимпиадной задачи?

Я иногда решаю «для себя» какие-нибудь сложные задачи по физике или математике. Практической пользы в этом нет, видимо, это мой способ проверить, что я всё еще не растерял форму. Ведь уже много времени прошло после красного диплома физтеха без четверок и серебряной медали с Международной олимпиады по физике.

Вчера решил очередную такую задачу из ролика Савватеева. Честно остановил ролик перед решением, задумался и нашел решение. Расскажу скорее не о самом решении, а о том, как можно его отыскать.

Условие задачи

В задаче требуется показать, что существует действительное число $$A\in\R$$, такое что любая натуральная степень $$n$$ этого числа после округления вверх отличается по модулю от ближайшего квадрата натурального числа ровно на 2.

Анализ условия

Запишем условие задачи формально: требуется доказать, что

$$\exists A\in\R\ \forall n\in\mathbb{N}\ \exists x\in\mathbb{N}:\left|\lceil A^n\rceil-x^2\right|=2.$$(1)

Здесь потерялось условие, что число $$x^2$$ должно быть ближайшим квадратом к $$\lceil A^n\rceil$$. Но оно будет выполнено автоматически, если $$A>5$$.

Условие выглядит страшно, и непонятно, как подступиться к задаче. В математике нет стандартных приемов по работе с округлением вверх. Придется пользоваться универсальным приемом: думать.

Перепишем условие менее формально. Для каждого $$n$$ должны найтись числа $$\varepsilon\in[0,1)$$ и $$x^2$$, для которых $$A^n+\varepsilon=x^2\pm2$$. При больших $$n$$ получаем, что $$A^n\approx x^2$$.

Озарение

Теперь самое время для озарения. Оно пришло ко мне в ходе такого рассуждения. Переход от $$n$$ к $$n+1$$ в левой части сводится к домножению на $$A$$, а в правой части — к переходу от одного квадрата к другому.

Квадраты натуральных чисел расположены по определенному шаблону. Разница между соседними квадратами — это последовательность нечетных чисел. Скорее всего в правой части при переходе от одного квадрата к другому прибавляется некоторое число, возможно связанное с $$A$$.

Вспоминаем, в каком случае домножение сводится к прибавлению? Есть известный пример для золотого сечения и для рекуррентных последовательностей типа Фибоначчи. Золотое сечение $$\varphi=(1+\sqrt5)/2$$ обладает свойством $$\varphi^{n+1}=\varphi^n+\varphi^{n-1}$$. То есть домножение $$\varphi^n$$ на $$\varphi$$ эквивалентно прибавлению $$\varphi^{n-1}$$. Возможно, число $$A$$ как-то связано с золотым сечением.

Гипотеза

Проверим гипотезу, что золотое сечение подходит на роль числа $$A$$. Вычислим для начальных $$n$$ степени золотого сечения и посмотрим, есть ли у них квадрат, отличающийся почти на 2:

$$n$$	$$\varphi^n$$	Квадрат
0	1,000000
1	1,618034
2	2,618034
3	4,236068
4	6,854102	9
5	11,090170
6	17,944272	16
7	29,034442
8	46,978714	49
9	76,013156
10	122,991869	121
11	199,005025
12	321,996894	324
13	521,001919
14	842,998814	841
15	1364,000733
16	2206,999547	2209

Для малых $$n$$ закономерности не видно. Но начиная с $$n=4$$ у каждого второго числа находится нужный квадрат! Наше вычисление показывает, что $$\varphi^2=2,\!618034$$ — неплохой кандидат для числа $$A$$. Оно подошло бы под условие, если бы не требование того, что именно ближайший квадрат, а не некоторый, должен отличаться на 2. Действительно, $$\varphi^2$$, округленное вверх до 3, отличается от квадрата 1² на 2. Чтобы учесть это требование, можем отобрать из таблицы не каждое второе число, а каждое четвертое, и положить $$A=\varphi^4$$.

Поскольку речь зашла о золотом сечении и числах Фибоначчи, мы можем понять, откуда в условии взялось округление вверх. Известно, что для чисел Фибоначчи $$F_{n}$$ есть формула Бине:

$$F_{n}={\frac {\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}}{\sqrt {5}}}={\frac {\varphi ^{n}-(-\varphi )^{-n}}{\varphi -(-\varphi )^{-1}}}={\frac {\varphi ^{n}-(-\varphi )^{-n}}{2\varphi -1}}.$$

Для нашей задачи от нее толку мало, но она подсказывает, что мы можем добавить к иррациональному $$\varphi^n$$ какое-нибудь аналогичное убывающее слагаемое, чтобы получить целое число $$\lceil A^n\rceil$$. Слагаемое легко подобрать для конкретных чисел из таблицы или увидеть из разложения $$(1\pm\sqrt{5})^n$$ через бином Ньютона (например, видно, что $$(1+\sqrt{5})^n+(1-\sqrt{5})^n$$ целое, потому что при раскрытии скобок любые слагаемые с нечетными степенями корней взаимно сократятся из-за разных знаков). Но давайте подберем. $$\varphi^4=6,\!854102$$, отличается от 7 на 0,145898. Если обратить эту разность, опять получается $$\varphi^4=1/0,\!145898$$. Таким образом, $$\varphi^{4}+1/\varphi^{4}$$ должно быть целым числом. Обобщение этих наблюдений мы и будем строго доказывать.

Строгое доказательство

Докажем теперь, что $$\varphi^{2n}+\varphi^{-2n}$$ отличается от квадрата некоторого натурального числа на 2. Для этого рассмотрим вспомогательное число $$t_n=\varphi^{n}+(-\varphi)^{-n}$$.

Заметим, что $$(-\varphi)^{-1}=-2/(1+\sqrt{5})=(1-\sqrt{5})/2$$, как и $$\varphi$$, является решением уравнения $$y^{2}=y+1$$ и, следовательно, тоже удовлетворяет условию $$y^{n+1}=y^n+y^{n-1}$$. Итого имеем рекуррентную последовательность $$t_n=\varphi^{n}+(-\varphi)^{-n}$$, подчиняющуюся определению $$t_{n+1}=t_n+t_{n-1}$$, так как она есть сумма двух других рекуррентных последовательностей с тем же определением.

Вычислим начальные элементы последовательности $$t_n$$: $$t_0=1+1=2$$, $$t_1=(1+\sqrt{5})/2+(1-\sqrt{5})/2=1$$. По принципу математической индукции любой элемент последовательности $$t_n$$ — также целое число.

Возведем элемент последовательности $$t_n$$ в квадрат:

$$t^2_n=\left(\varphi^{n}+\left({-1\over\varphi}\right)^n\right)^2=\varphi^{2n}+{1\over\varphi^{2n}}+2(-1)^n.$$(2)

Таким образом, возведение $$\varphi^2$$ в степень $$n$$ и округление вверх дает целое число $$\varphi^{2n}+1/{\varphi^{2n}}$$, отличающееся от квадрата натурального числа $$|t_n|=|\varphi^{n}+(-\varphi)^{-n}|$$ ровно на 2.

Сравнение решения с авторским

Мое решение вроде бы завязано на золотое сечение и на его свойства. Но на самом деле используется только одно свойство: золотое сечение есть решение уравнения $$y^{2}=y+1$$. Сумма степеней корней этого уравнения порождает целочисленную последовательность. Есть и другие уравнения с тем же свойством. Корни по модулю должны быть взаимно обратными, чтобы сработало равенство наподобие (2). Можно было взять действительные корни любого уравнения $$y^{2}=ky\pm1$$ с целым $$k\neq\pm2$$.

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

← сюда туда →