Ну а вот — результат наложения, маленькая чёрно-белая ёлочка. Ещё раз — с Новым Годом!

https://mccme.ru/free-books/

Дед Мороз напоминает про страницу, на которой бесплатно доступны файлы множества книг (в основном издательства МЦНМО)

брошюры библиотеки «Математическое просвещение» и Летней школы «Современная математика», доклады семинара «Глобус» и материалы выездного семинара учителей, книги Арнольда и Гельфанда, Прасолова и Шеня и многое другое.

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

5 января (по старому стилю) 1901 года родился выдающийся человек – Иван Георгиевич Петровский. Математик, уникальный ректор Московского Университета, по некоторым воспоминаниям «совершивший не менее десяти тысяч добрых дел». Пользуясь случаем, напомним некоторые материалы о нём.

Начать, наверное, стоит со статьи Владимира Михайловича Тихомирова (с добавлениями А.А. Кириллова и Э.Э. Шноля) в сборнике «Математическое просвещение» https://www.mccme.ru/free-books/matpros7.html

А вот две видеозаписи воспоминаний Владимира Андреевича Успенского
https://youtu.be/csR_APaxZuU
https://youtu.be/i3aA7uSo3Xw
(В печатном виде некоторые воспоминания В.А. Успенского вошли в статью «Ректоры МГУ» в пятую книгу «Трудов по нематематике» https://mccme.ru/free-books/uspenskii/vau_book5.pdf )

Воспоминания (аудиозапись и текст) ученицы И.Г. Петровского, впоследствии заведовавшей его кафедрой, Ольги Арсеньевны Олейник
http://oralhistory.ru/talks/orh-580
(Обратите внимание и на сам сайт «Устная история»!)

Видеозапись воспоминаний В.А. Успенского и Ю.С. Ильяшенко
https://youtu.be/Zda7IbfHVU0

Документальный фильм 1983 года «Академик И.Г. Петровский»
https://youtu.be/opF5HcgC9GI

Запись выступления Ивана Георгиевича на закрытии Международного математического конгресса 1966 года в Москве
https://youtu.be/PEBFT1bJeew

Некоторые статьи об Иване Георгиевиче можно найти на сайте mathedu.ru https://www.mathedu.ru/indexes/authors/petrovskiy_i_g/.

В 2001 году МГУ выпустило книгу
https://msupress.com/catalogue/books/book/akademik-i-g-petrovskiy-rektor-mgu/

на мат. кружках для начинающих нередко режут какие-нибудь фигуры на уголки из трех клеток

и ясно, что площадь прямоугольника, который можно разрезать, должна делиться на 3… но 3×(2n+1) разрезать нельзя, 3×(2n) разрезать легко — возникает гипотеза, что даже на 6 должно количество клеток делиться

и все же прямоугольник 5×9 на уголки разрезать можно



давно хотел научиться пользоваться SAT-солверами для задач на разрезание и тому подобных дискретных задач, а это пусть будет модельный пример

для базового введения посмотрите лучше вот например https://youtu.be/4K1MyG4ljI8 (спасибо — и не только за это видео! — Саше Куликову), но всё же кратко поясню

SAT-солвер умеет только одно: подбирать значения булевых перменных, чтобы выполнялся набор условий, где каждое условие — выбор из вариантов «такая-то переменная равна такой-то константе»¹

в pycosat условия записываются в духе [1 -3 -4] («x1 or (not x3) or (not x4)»)

в нашей задаче мы заведем по одной переменной для каждого потенциального положения уголка внутри прямоугольника:

placements = []
covers = {}
for shape in TILES:
    for i, j in allcells():
        cells = [(i+dx, j+dy) for dx, dy in shape]
        if all(inside(*cell) for cell in cells):
            pid = len(placements) + 1
            placements.append(cells)
            for cell in cells:
                covers.setdefault(cell, []).append(pid)

все такие положения теперь лежат в массиве placements, а в словаре covers для каждой клетки указано, какие есть потенциальные способы ее покрыть

теперь пишем условия: 1) что каждая клетка покрыта; 2) что она не покрыта дважды (т.е. что из каждой пары способов покрытия хоть один не выбран):

clauses = []
for cell in allcells():
    ps = covers.get(cell, [])
    clauses.append(ps)
    for a, b in combinations(ps, 2):
        clauses.append([-a, -b])

и… всё! — можно говорить solve(clauses) и наслаждаться ответом

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

¹ прошу прощения у логиков и сочувствующих за терминологию, но от формулировки «нормальная форма, в которой булева формула имеет вид конъюнкции дизъюнкций литералов» я теряю нить

https://youtu.be/FsJvpDnx4Vs

свежее интервью с Денисом Гайцгори