Как додуматься до решения олимпиадной задачи?
Я иногда решаю «для себя»
Вчера решил очередную такую задачу из ролика Савватеева. Честно остановил ролик перед решением, задумался и нашел решение. Расскажу скорее не о самом решении, а о том, как можно его отыскать.
Условие задачи
В задаче требуется показать, что существует действительное число $$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 | |
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, отличается от квадрата 12 на 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$$
Строгое доказательство
Докажем теперь, что $$\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 Анализ данных как современный научный метод против средневековой пропаганды
Алгоритмическая сложность
Одна из тем, которые я обязательно поднимаю на собеседовании, — это сложность алгоритмов. Кандидату на мои вакансии достаточно назвать сложность наилучшей сортировки —
Если кандидат не дает ответа
Почему важно иметь представление об алгоритмической сложности? Что будет, если писать код без этого представления? Недавно нашелся пример: если на рабочем столе создать 1000 файлов, Windows тратит 20 секунд на открытие главного меню. И всё потому, что
Визуальная конструкция элементов интерфейса
Нашел в некотором личном кабинете вот такой пример интерфейса. Я хочу остановиться на внешнем виде его элементов, и не буду сейчас подробно обсуждать проблему с теорией близости. Замечу лишь, что проблема не только в том, что переключатели находятся далеко от подписей. Кнопка «удалить аккаунт»
Можете ли вы понять по переключателям, включены ли они, или нет? Я воспринимаю этот элемент интерфейса как белый квадрат, перемещающийся внутри черного прямоугольника. Он находится справа, поэтому переключатель включен. Но
Выходит, что по задумке дизайнера черный прямоугольник перемещается без просвета внутри черной прямоугольной рамки. Хорошо, пробуем переключить:
Фирменный оранжевый цвет должен был показать активацию переключателя. Но у меня усилилось ощущение того, что белый квадрат, представляющий ручку переключателя, переместился налево. А оранжевый цвет говорит: «Внимание, выключено!».
Чтобы избавиться от неправильного восприятия элемента интерфейса, нужно изменить его конструкцию. Например, попробуем в отладчике скруглить уголки:
Получилось грубо, но состояние переключателей считывается однозначно. Полупрозрачный фон без рамки тоже хорошо работает:
Фирменный стиль не должен быть помехой для разработки и внедрения понятных элементов интерфейса.
Деление на код и данные в ООП
Любая программа, выполняемая на современных процессорах, состоит из данных и кода — набора инструкций, обрабатывающих эти данные. Такое деление четко прослеживается как в ассемблерном коде, так и в процедурных языках.
В
Правильный код в стиле ООП разделяет
Читайте о правильном подходе в статье Дмитрия Елисеева «Структуры с процедурами или объекты?». Он подробно разобрал тезис о разном применении разных типов объектов и проиллюстрировал всё на примерах для PHP.
Электронная медицинская карта и утечки
На сайте госуслуг каждый может получить доступ к своей медицинской карте, посмотреть старые анализы, историю визита к врачам.
Зашел, посмотрел. Есть данные из «районной» поликлиники. Из частных поликлиник — нет.
И вот о чем еще подумал: в свете новых методов расследования, примененных к отравлению Навального, насколько легко получить доступ к базам медицинских карт?
Связь между физикой и программированием: абстракции и язык — В кресле препода №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 Разбор примера обработки
00:48:50 Переписывание примера из документации в объектном стиле и добавление функциональности на примере головоломки Арнольда (исходник на гитхабе)
01:17:58 О «пользе» MVC и что такое ООП на самом деле
01:20:35 Сравнение процедурного и объектного подходов и принцип High Cohesion Low Couping
01:23:42 Наследования и полиморфизма нет, а дух ООП есть
Описание головоломки Арнольда в предыдущем посте и на хабре.
Головоломка Арнольда ★
Постоянные читатели помнят, что мы с коллегами по учебе лет 10 назад занимались задачей Арнольда. В ней остались открытые вопросы, и я недавно решил к ним вернуться. Дописал одну из программ, отрисовывающих и распрямляющих конфигурации, и понял, что получилась хорошая игровая механика для головоломки. Переписал код визуализации и моделирования на js, и получилась браузерная головоломка.
Правила
В этой игре выполняются простые правила:
- На плоскости проведены несколько линий, каждая пара линий пересекается в одной точке.
- Линии разбивают плоскость на области, раскрашенные в шахматном порядке.
- Вы можете перестраивать разбиение, «схлопывая» и «выворачивая» треугольники.
- Ваша цель — получить максимально возможное количество темных областей.
В простейшем случае 5 линий процесс игры выглядит так:
Пользовательский опыт
При небольшом количестве линий решить головоломку можно случайным перебором. Нужно помнить, что иногда надо «пожертвовать» счетом (количеством темных областей), так как не всегда есть «прямая дорога» к цели, на которой счет только увеличивается.
Я довольно быстро «прошел» все уровни до 19 линий. 21 линию (на скриншоте в начале) собрал часа за полтора. Правда, я знал, что существует
С увеличением уровня сложность игры растет не только количественно (нужно дольше идти к цели), но и качественно: приходится придумывать новые приемы и подходы, так как старых становится недостаточно.
По ощущениям игра похожа на паззл, каждый кусочек которого подходит к любому другому кусочку, но общая картина из них всё никак не складывается.
Игра полностью отвлекает от происходящего вокруг, подходит для убивания времени в метро.
Математическая основа
Напомню формулировку задачи Арнольда:
На плоскости проведены N прямых. Найти максимальную разность между числом черных и белых областей шахматной раскраски дополнения.
Это открытая математическая проблема. Она является частным случаем
Таким образом, переворачивая треугольники в головоломке, вы на самом деле решаете в частном случае
Для преобразования конфигураций в головоломке именно схлопывание треугольников выбрано не случайно. Оказывается, с помощью таких схлопываний можно перевести произвольную конфигурацию в любую другую конфигурацию. Действительно, линии на плоскости, описанные в правилах, называются конфигурацией (псевдо)прямых. Они представляют элемент из группы кос. Суть теоремы Артина об образующих группы кос как раз и состоит в возможности перевода конфигураций друг в друга последовательностью преобразований треугольников.
Также задача Арнольда тесно связана с задачей о треугольниках Кобона.
Вместе со мной Денис Уткин и Сергей Белёв потратили немало времени на попытки решения, результаты которого есть во многостраничном
Вычислительная модель игры
В основе визуализации — математическое моделирование некоторой «механической» системы. В этой системе массивные точки соединены ломаными линиями, отталкиваются друг от друга, испытывают сопротивление среды. В узлах ломаных — распрямляющие «пружинки». Концы ломаных прибиты внешними зафиксированными точками. Для расчетов движения точек по законам механики применяется метод Рунге — Кутты четвертого порядка с оценкой ошибок и плавающим шагом. Преподаватели вычматов были бы довольны :) Код, как обычно, открыт на гитхабе.
Рубаков
С удовольствием посмотрел интервью Рубакова. Он крутой специалист по космологии — области науки, изучающей крупномасштабное устройство и развитие Вселенной. Рассказывает о себе, научном пути, последних открытиях, развитии науки.
Не совсем интервью, правда. Из видео вопросы вырезали, добавили текст при монтаже. Но всё равно тут главное послушать Рубакова.
Понятие формата в дизайне интерфейсов — В кресле препода №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 — естественное ограничение в конце
20:58 Особенности формата веба
22:47 Сравнивать надо функциональность
25:28 Бессмысленность претензий к вебу
26:52 Эволюция интерфейса настройки Windows
32:28 Пример 2: Одностраничные приложения
33:54 Админка моего движка как пример одностраничного приложения
37:25 Как бы сейчас спроектировал интерфейс админки
41:42 Обсуждаем извлеченные уроки и дизайн выпадайки из личного кабинета
46:17 Итог