Как написано в следующем посте в этом паблике, эта задача связана с кластерными алгебрами, которые придумали Фомин с Зелевинским около 20 лет назад. Год назад я как раз ходил на курс про кластерные алгебры, который читал Фомин, а усложнённая версия этой задачи была в одном из домашних заданий.
Кластерные алгебры это такие коммутативные алгебры, у которых есть выделенные наборы образующих элементов, которые называются кластерами. Более того, есть некоторая комбинаторная операция, которая позволяет переходить от одного кластера к другому. Операция эта называется “мутированием”. То есть можно промутировать одну образующую и получить новый кластер, который отличается от старого одной образующей. Что замечательно, старая образующая X отличается от новой Y очень понятным образом: верна формула XY = M + M’, где M, M’ это мономы от старых образующих. Самое главное свойство кластерных алгебр заключается в феномене Лорана: новые кластерные образующие (те, которые мы получаем мутированием) это полиномы Лорана от старых.
Как это связано с задачей? Иногда кластерные алгебры приходят из колчанов и правило мутирования соответствует очень простой комбинаторной операции с колчанами. Конструкция простая, но рассказывать я её не буду, будем использовать её как чёрный ящик. Так вот трюк в том, что эта рекуррента это просто алгебраически записанное правило мутирования в некотором колчане (pic.). А если в его вершины поместить кластерные образующие z_1, z_2, z_3, z_4, то все остальные кластерные образующие z_n будут полиномами Лорана от первых четырёх, а поскольку мы придали всем четырём образующим значение 1, то все кластерные образующие специализируются в целые числа!
Более интересная задача: что будет если z_1=z_2=1, z_3=2, z_4=5? Тут уже чуть хитрее, но не сильно. Я приложу своё решение (неоптимальное), но по большому счёту всё опять следует из феномена Лорана.