День паркетчика

[xaxam]

NP-смешные задачи

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

В математике такое тоже бывает. Вот, скажем, задача - сколькими разными способами можно настелить на бесконечной плоскости паркет из выпуклых пятиугольных плиток. Конечно, надо объяснить, какие способы считать разными, а какие одинаковыми, но это не очень сложно: все такие паркеты устроены в конце концов двоякопериодически: из нескольких плиток собирают (невыпуклый) многоугольник ("фундаментальную область") так, что его параллельными копиями можно замостить плоскость. Считать надо число пятиугольных плиток и способ их прикладывания друг к другу так, чтобы они образовывали фундаментальную область.

До недавнего времени таких способов было найдено 14 (начиная с 1918 года, когда задачу сформулировали). И вот сенсация, на стенку лезет пресса: спустя почти сто лет и после 30-летнего перерыва найдено пятнадцатое решение! Конечно, я полез было на сайт автора, - там ничего нет. Полез смотреть на arXiv - и там ничего не заметил. Утка? Fake news? как такое может быть?

Может. Решение предъявлено в газете "Вертухай" по ссылке выше: указаны углы и стороны пятиугольника, такого, что три его (повёрнутые) копии собираются в фундаментальную 9-угольную область. Voilá!

Конечно, авторы напишут статью по этому поводу, расскажут, как они нашли это решение (компьютерным перебором, конечно, но перебирать тоже надо уметь). Но в принципе отличный пример NP-смешной задачи: ответ на одной картинке умещается, а пойди найди. А может, уже и не напишут: статья в "Вертухае" - трёхлетней давности.