Антигеометрические шутки

а, тривиально, соотношение "не типа меньше" транзитивно

Ещё одна задача на геометрическую интуицию.

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

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

Вопрос - для любого ли набора найдётся многоугольник, который "типа меньше" всех остальных из набора?

https://t.me/geometrykanal/2156 кажется, знаю, как почти безболезненно просчитать

Про проверку сходимости численно — сначала очень затупил, пока пишу промежуточный отчёт

Первая кувалдоидея - рассмотреть функцию от M переменных - сумму квадратов уравнений. Она вычисляется за O(M), как и её градиент, и попробовать численно бежать в локальный минимум от случайного старта.

Метод, который прилично работает вдалеке от локального минимума, а потом начинает тупить, я нарисовал почти сразу (потом распишу отдельно)

Вблизи от локального минимума качественно работает Broyden–Fletcher–Goldfarb–Shanno, но у него итерация стоит O(M^2) (то есть O(n^4))
И только сейчас дошло, что можно делать два шага в параллель:
1. Зафиксировали разделяющие прямые, можем независимо минимизировать по переменным, привязанным к каждому квадрату (их 24 + 4*(n-1) - 8 координат, для каждой координаты по две фиктивные переменные для неравенств, для каждой связанной с квадратом разделяющей прямой по 4 фиктивных переменных) - тут BFGS легко потянет
2. Зафиксировали многоугольники, для каждой разделяющей прямой задача сужается на 11 независимых переменных (3 -координаты прямой, 4 - неравенства для первого квадрата, 4 - неравенства для второго квадрата). Систем (n^2-n)/2, он они сверхмалые, при этом для не пересекающихся многоугольников легко ищется точное решение.

Осталось это написать

#упаковка_квадратов
Пока беру паузу, профайлер меня удивил

и для 5яти почти оптимум численно нашёлся

о, ускоренная версия сгенерила какое-то нетривиальное для 17ти

#упаковка_квадратов продолжение
Задача "войдут ли n квадратов со стороной 1 в квадрат со стороной C" сводится к проверке (вещественной) выполнимости системы уравнений от О(n^2) переменных. (в комментариях сведение)

Дальше начинаем проверять выполнимость численно

Продолжение следует

n=11

n=11

n=11

n = 10

#упаковка_квадратов
Тут происходит эпопея. Началось всё с вот этой записи
https://t.me/avvablog/1634 , и тут у меня возникло острое желание помахать тяжёлым тупым предметом (предположительно, дубиной)

Для затравки скину парочку сгенерированных упаковок для малых n

https://t.me/geometrykanal/2022 странная формулировка

Шесть красных отрезков равны 1.

1. Найдите R (это просто)
2. Найдите угол между красными диаметрами (это уже вроде бы не так просто)

По-моему, очевидно, что задача рушится в противоположном порядке.

Ещё одна задача https://t.me/c/1141607031/29044 , чуть посложнее.

Эквивалентная формулировка - красная окружность, проходящая через точки A и B и касающаяся вписанной окружности треугольника ABC, проходит через середину отрезка KIc, где K - точка касания вписанной окружности и прямой AB, а Ic - центр вневписанной окружности, касающейся внешней стороны AB

Доказательство
Вписанную окружность полагаем единичной с радиусом в начале координат, точку касания внешней и красной - (-1,0), координаты точки K (2p/(1+p^2), (1-p^2)/(1+p^2)), длина отрезка AK - q

Далее:
Координаты точки A по сумме K и перпендикулярного К умноженного на q

Уравнение красной окружности по точке A(фокус 1)

Координаты точки B(фокус2, красная окружность, точки A и K)

Точка A2, лежащая на прямой AC: строим прямую, проходящую через I перпендикулярно AI, её пересечение с AB - A1, симметричная ей относительно I точка лежит на AC

Продолжение и код в комментарии

Задача чуть сложнее https://t.me/geometrykanal/2077

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

Доказательство:
Красная - единичная с центром в (0, 0), общая точка касания красной и описанной - (-1, 0), параметризуем D(2p/(1+p^2), (1-p^2)/(1+p^2)), E(2q/(1+q^2), (1-q^2)/(1+q^2))

Далее последовательно считаем:
Координаты точки A как пересечения касательных к красной в точках D и E

Уравнение описанной окружности (через фокус1 и координаты A)

Координаты точки B(фокус2, A и D)

Координаты точки C(фокус2, A и E)

Координаты точки F (середина отрезка DE)

Расстояние от F до AB (по симметрии совпадает с расстоянием от F до AC) (точнее, квадрат расстояния)

Квадрат расстояния от F до BC

Убеждаемся в тождестве, доказано.

Код в комментариях

Продолжение. Простая и классическая "Лемма Архимеда"
https://ru.wikipedia.org/wiki/%D0%9E%D0%BA%D1%80%D1%83%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C#%D0%9B%D0%B5%D0%BC%D0%BC%D0%B0_%D0%90%D1%80%D1%85%D0%B8%D0%BC%D0%B5%D0%B4%D0%B0

Если окружность вписана в сегмент окружности, стягиваемый хордой BC, и касается дуги в точке A, а хорды — в точке K, то прямая AK является биссектрисой угла BAC

Доказательство:
полагаем вписанную окружность единичной с центром в начале координат, точке A соответствуют координаты (0, -1), точке K - координаты (2p/(1+p^2), (1-p^2)/(1+p^2)). Длину отрезка KB полагаем равным q, координаты B восстанавливаются по сумме вектора K и вектора, перпендикулярного K, умноженного на q. После этого восстанавливаем координаты центра внешней окружности (фокус1), после - координаты точки C (фокус 2).
Осталось проверить свойство биссектрисы AB/BK = AC/CK (точнее, проверяем (AB/BK)^2 = (AC/CK)^2). Коротко и симпатично. Код в комментариях

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

полагаем одну из окружностей единичной и с центром в нуле, общую точку касания помещаем в (-1, 0), параметризуем две точки рациональными функциями двух переменных (например, точка на окружности параметризуется одной переменной способом (2p/(1+p^2), (1-p^2)/(1+p^2)), далее выражаем координаты точек, уравнения прямых и так далее через рациональные функции от этих двух переменных, пока не получаем требуемое утверждение как тождество рациональных функций).

Естественно, использую python/sympy, руками считать лень и незачем.

Фокусы:
1. окружность с уравнением x^2 + (y-h)^2 = (h+1)^2 проходит через точку (x0, y0), x0 != 0. h восстанавливается однозначно как рациональная функция от x0, y0

2. Точка (x0, y0) лежит на окружности С с центром в (0, h), прямая l проходит через (x0, y0) и (x1, y1). Вторую точку пересечения l и С можно выразить как рациональную функцию от x0, y0, x1,y1, h (тривиально через параметрическое уравнение l)

3. точка пересечения двух прямых - рациональная функция от коэффициентов прямых (тривиальное)

Файл с фокус-функциями - в комментариях

Тестовая запись