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

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

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

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

В задаче требуется показать, что существует действительное число $$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$$.

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

Анализ данных — В кресле препода №7

За последние несколько месяцев было крупных новостей, связанных с анализом данных. Мне как физику такие новости интересны и понятны, потому что современную физику нельзя представить без анализа данных. В очередном выпуске «В кресле препода» объясняю на конкретных примерах, как работает анализ и представление данных.

00:00 Резонансные новости, связанные с анализом данных
01:03 Анализ данных пришел из физики высоких энергий
02:25 Обработка данных с Большого адронного коллайдера
03:30 Настоящая Big Data на Большом адронном коллайдере: в «гриде» LHC идет запись 300 мегабайт данных в секунду
05:03 Визуализация и анализ данных на примере графика заболеваемости коронавирусом Яндекса
12:40 Как понять истинный масштаб заражений коронавирусом в России по избыточной смертности
19:38 Как распознать фальсификации на голосовании
29:39 Расследование Грозева об отравлении Навального
32:27 Анализ данных как современный научный метод против средневековой пропаганды

Алгоритмическая сложность

Одна из тем, которые я обязательно поднимаю на собеседовании, — это сложность алгоритмов. Кандидату на мои вакансии достаточно назвать сложность наилучшей сортировки — O(n·ln n). Еще о структурах данных речь заходит при обсуждении работы индексов БД. Кандидат должен объяснить, за счет чего индексы ускоряют выполнение запросов.

Если кандидат не дает ответа O(n·ln n), это тревожный звоночек. В зависимости от вакансии я могу еще попросить оценить сложность простейшей сортировки, например, пузырьком, чтобы отличить пробел в знаниях от неспособности понимать эту тему.

Почему важно иметь представление об алгоритмической сложности? Что будет, если писать код без этого представления? Недавно нашелся пример: если на рабочем столе создать 1000 файлов, Windows тратит 20 секунд на открытие главного меню. И всё потому, что какой-то криворукий программист написал алгоритм сложности O(n²) там, где можно было обойтись O(n). Подробности читайте на хабре.

Визуальная конструкция элементов интерфейса

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

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

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

Фирменный оранжевый цвет должен был показать активацию переключателя. Но у меня усилилось ощущение того, что белый квадрат, представляющий ручку переключателя, переместился налево. А оранжевый цвет говорит: «Внимание, выключено!».

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

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

Фирменный стиль не должен быть помехой для разработки и внедрения понятных элементов интерфейса.

Деление на код и данные в ООП

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

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

Правильный код в стиле ООП разделяет объекты-данные и объекты-сервисы. Первые (сущности, объекты-значения и т. д.) — обобщение понятия структуры. Вторые — обобщение понятия процедуры и функции.

Читайте о правильном подходе в статье Дмитрия Елисеева «Структуры с процедурами или объекты?». Он подробно разобрал тезис о разном применении разных типов объектов и проиллюстрировал всё на примерах для PHP.

Электронная медицинская карта и утечки

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

Зашел, посмотрел. Есть данные из «районной» поликлиники. Из частных поликлиник — нет.

И вот о чем еще подумал: в свете новых методов расследования, примененных к отравлению Навального, насколько легко получить доступ к базам медицинских карт?

Связь между физикой и программированием: абстракции и язык — В кресле препода №6

Я заметил нетривиальную связь между физикой и программированием. Она находится в области используемых и там и там абстракций и обозначений. Записал видео с объяснением и примерами.

Придумал название «В кресле препода» для таких видео, где я обсуждаю какие-то вопросы и делюсь опытом. Встречайте выпуск №6.

00:00:47 Зачем слушать этот рассказ
00:01:33 Замечание о формате презентаций
00:03:15 План рассказа
00:04:01 Математический аппарат физических теорий
00:05:39 Механика Ньютона и двойной маятник
00:09:45 Уравнения Максвелла: векторная и компонентная форма записи
00:14:17 Четырехвекторы и скорость света
00:18:01 Принцип наименьшего действия
00:21:25 Разнообразие форм уравнений Максвелла
00:23:41 Причем здесь программирование?
00:28:28 Уровни абстракций в языках программирования: физический, процедурный, ООП
00:33:26 Кто создает больше абстракций: физик или программист?
00:37:23 Практический пример
00:41:21 Разбор примера обработки тач-событий из MDN
00:48:50 Переписывание примера из документации в объектном стиле и добавление функциональности на примере головоломки Арнольда (исходник на гитхабе)
01:17:58 О «пользе» MVC и что такое ООП на самом деле
01:20:35 Сравнение процедурного и объектного подходов и принцип High Cohesion Low Couping
01:23:42 Наследования и полиморфизма нет, а дух ООП есть

Описание головоломки Арнольда в предыдущем посте и на хабре.

Головоломка Арнольда ★

Постоянные читатели помнят, что мы с коллегами по учебе лет 10 назад занимались задачей Арнольда. В ней остались открытые вопросы, и я недавно решил к ним вернуться. Дописал одну из программ, отрисовывающих и распрямляющих конфигурации, и понял, что получилась хорошая игровая механика для головоломки. Переписал код визуализации и моделирования на js, и получилась браузерная головоломка.

Правила

В этой игре выполняются простые правила:

1. На плоскости проведены несколько линий, каждая пара линий пересекается в одной точке.
2. Линии разбивают плоскость на области, раскрашенные в шахматном порядке.
3. Вы можете перестраивать разбиение, «схлопывая» и «выворачивая» треугольники.
4. Ваша цель — получить максимально возможное количество темных областей.

В простейшем случае 5 линий процесс игры выглядит так:

Пользовательский опыт

При небольшом количестве линий решить головоломку можно случайным перебором. Нужно помнить, что иногда надо «пожертвовать» счетом (количеством темных областей), так как не всегда есть «прямая дорога» к цели, на которой счет только увеличивается.

Я довольно быстро «прошел» все уровни до 19 линий. 21 линию (на скриншоте в начале) собрал часа за полтора. Правда, я знал, что существует вращательно-симметричная конфигурация (поворот на 120° переводит ее в себя), и специально делал ее симметричной. 23 линии пытался собрать дважды, и оба раза не получилось набрать последнее очко.

С увеличением уровня сложность игры растет не только количественно (нужно дольше идти к цели), но и качественно: приходится придумывать новые приемы и подходы, так как старых становится недостаточно.

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

Игра полностью отвлекает от происходящего вокруг, подходит для убивания времени в метро.

Математическая основа

Напомню формулировку задачи Арнольда:

На плоскости проведены N прямых. Найти максимальную разность между числом черных и белых областей шахматной раскраски дополнения.

Это открытая математическая проблема. Она является частным случаем 16-й проблемы Гильберта для многочленов специального вида — произведения линейных сомножителей ax+by+c.

Таким образом, переворачивая треугольники в головоломке, вы на самом деле решаете в частном случае 16-ю проблему Гильберта! :)

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

Также задача Арнольда тесно связана с задачей о треугольниках Кобона.

Вместе со мной Денис Уткин и Сергей Белёв потратили немало времени на попытки решения, результаты которого есть во многостраничном pdf-отчете. Я хочу выразить благодарность Денису и Сергею за совместный интерес, без которого в конечном итоге не появилась бы эта головоломка. Бонус для внимательных читателей: в отчете есть примеры конфигураций, на которых достигается цель головоломки.

Вычислительная модель игры

В основе визуализации — математическое моделирование некоторой «механической» системы. В этой системе массивные точки соединены ломаными линиями, отталкиваются друг от друга, испытывают сопротивление среды. В узлах ломаных — распрямляющие «пружинки». Концы ломаных прибиты внешними зафиксированными точками. Для расчетов движения точек по законам механики применяется метод Рунге — Кутты четвертого порядка с оценкой ошибок и плавающим шагом. Преподаватели вычматов были бы довольны :) Код, как обычно, открыт на гитхабе.

Рубаков

С удовольствием посмотрел интервью Рубакова. Он крутой специалист по космологии — области науки, изучающей крупномасштабное устройство и развитие Вселенной. Рассказывает о себе, научном пути, последних открытиях, развитии науки.

Не совсем интервью, правда. Из видео вопросы вырезали, добавили текст при монтаже. Но всё равно тут главное послушать Рубакова.

Понятие формата в дизайне интерфейсов — В кресле препода №5

Когда-то давно хотел написать огромную статью о понятии формата в дизайне интерфейсов. Но так и не собрался, её всё равно никто не стал бы читать. А сейчас вспомнил об этом и записал видео.

Когда формулировал, почему моим словам стоит доверять, осознал, что у меня уже почти 13 лет опыта в коммерческой веб-разработке. Незаметно время летит :)

00:11 Почему моим словам стоит доверять: 13 лет опыта
00:42 Собирался рассказать о понятии формата давно
01:11 Для затравки: чем плохи выпадайки в вебе, пример личного кабинета интернет-банка
03:28 Понятие формата
04:56 Пример 1: формат веба и формат окон настройки старых операционных систем (сравнение из старой статьи на хабре)
08:03 Комментарий к статье, обращающийся к понятию формата
10:42 OS/2 умер
12:09 Окно настройки — почему такое? Ограничение 1: физический размер экранов
14:24 Ограничение 2: размер видеопамяти
15:26 Ограничение 3: частота обновления
18:53 Ограничение 4: работа без драйверов
19:54 640*480 — естественное ограничение в конце 90-х
20:58 Особенности формата веба
22:47 Сравнивать надо функциональность
25:28 Бессмысленность претензий к вебу
26:52 Эволюция интерфейса настройки Windows
32:28 Пример 2: Одностраничные приложения
33:54 Админка моего движка как пример одностраничного приложения
37:25 Как бы сейчас спроектировал интерфейс админки
41:42 Обсуждаем извлеченные уроки и дизайн выпадайки из личного кабинета интернет-банка
46:17 Итог

← сюда туда →