Задача 669
Королевский банкет

Рыцари ордена Фибоначчи готовят большой пир для своего короля. Всего рыцарей $n$, и каждому рыцарю присвоено уникальное число от 1 до $n$.

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

Когда $n$ рыцарей все пытаются рассесться за круглым столом с $n$ стульями, несмотря на все приложенные усилия, они не могут найти подходящий порядок рассаживания для любого $n>2$. Уже готовые сдаться, они вспоминают, что король тоже будет сидеть с ними за столом на троне.

Предположим, что рыцарей $n=7$ и за круглым столом 7 стульев, не считая королевский трон. После нескольких попыток они приходят к следующему порядку рассаживания (К обозначает короля):

Круглый стол

Заметим, что суммы $4+1$, $1+7$, $7+6$, $6+2$, $2+3$ и $3+5$ все являются числами Фибоначчи, как и требовалось. Также упомянем, что король всегда предпочитает расположение, при котором номер рыцаря слева от него меньше, чем номер рыцаря справа. С этим дополнительным правилом показанное выше расположение является единственным возможным для $n=7$ и номер рыцаря, сидящего на 3-м стуле слева от короля, равен 7.

Позже, в орден приняты несколько новых рыцарей, что увеличило число рыцарей и стульев, не считая королевский трон, до 34. Рыцари в конце концов определяют, что существует один единственный порядок рассаживания для $n=34$, удовлетворяющий условиям выше, и в этот раз на 3-м стуле слева от короля сидит рыцарь с номером 30.

Теперь предположим, что всего есть $n=99\,194\,853\,094\,755\,497$ рыцарей и столько же стульев за круглым столом (не считая королевский трон). После большого количества попыток и споров они наконец смогли к единственному порядку рассаживания, удовлетворяющему условиям выше, для этого значения $n$.

Найдите номер рыцаря, сидящего на $10\,000\,000\,000\,000\,000$-м стуле слева от короля.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net