The King’s Banquet

The Knights of the Order of Fibonacci are preparing a grand feast for their king. There are $n$ knights, and each knight is assigned a distinct number from $1$ to $n$.
When the knights sit down at the roundtable for their feast, they follow a peculiar seating rule: two knights can only sit next to each other if their respective numbers sum to a Fibonacci number.
When the $n$ knights all try to sit down around a circular table with $n$ chairs, they are unable to find a suitable seating arrangement for any $n>2$ despite their best efforts. Just when they are about to give up, they remember that the king will sit on his throne at the table as well.
Suppose there are $n=7$ knights and $7$ chairs at the roundtable, in addition to the king’s throne. After some trial and error, they come up with the following seating arrangement ($K$ represents the king):

Notice that the sums $4+1$, $1+7$, $7+6$, $6+2$, $2+3$, and $3+5$ are all Fibonacci numbers, as required. It should also be mentioned that the king always prefers an arrangement where the knight to the his left has a smaller number than the knight to his right. With this additional rule, the above arrangement is unique for $n=7$, and the knight sitting in the 3rd chair from the king’s left is knight number $7$.
Later, several new knights are appointed to the Order, giving $34$ knights and chairs in addition to the king’s throne. The knights eventually determine that there is a unique seating arrangement for $n=34$ satisfying the above rules, and this time knight number $30$ is sitting in the 3rd chair from the king’s left.
Now suppose there are $n=99\,194\,853\,094\,755\,497$ knights and the same number of chairs at the roundtable (not including the king’s throne). After great trials and tribulations, they are finally able to find the unique seating arrangement for this value of $n$ that satisfies the above rules.
Find the number of the knight sitting in the $10\,000\,000\,000\,000\,000$th chair from the king’s left.

This problem can be solved using a concept called the “Fibonacci sequence”, which is defined by

F(0) = 0,
F(1) = 1,
F(n) = F(n – 1) + F(n – 2) for n > 1.

The first thing to note is that the sequence of knight numbers in any arrangement is a permutation of the sequence of the first n Fibonacci numbers (1-indexed). The second point to see is that each knight in the sequence generates the knight number to its right: for example, in the given setup for n = 7, knight number 4 generates knight number 1 (since 4 + 1 = 5, a Fibonacci number), knight number 1 generates number 7 (since 1 + 7 = 8, a Fibonacci number), and so forth.

Given these two points, we can create a “Fibonacci tree”, in which the root node is the number 1, and each node generates its children as follows:

– The left child is the number obtained by subtracting the parent node’s number from the next Fibonacci number in the sequence.
– The right child is the next Fibonacci number in the sequence.

Thirdly, the knights are seated from the left child to the right child in the Fibonacci tree. Hence, the arrangement of the knights is simply the in-order traversal of this tree (left child, parent, right child).

Therefore, to compute the knight in the m-th position from the king’s left, we perform an in-order traversal of the Fibonacci tree and count the traversed nodes.

However, the number n = 99,194,853,094,755,497 and m = 10,000,000,000,000,000 are extremely big. To deal with these big numbers, we can use the property of Fibonacci sequence that F(n) approximately equals to F(n-2) + F(n-1). We can divide the big numbers into smaller segments that each one contains approximate 2 Fibonacci numbers. Because in-order traversal visits left child, parent, and then right child, we know that the size of the left subtree of the tree rooted at a certain Fibonacci number is equal to the Fibonacci number two places before it. Thus we can use binary search to find the segment which contains the m-th position.

This algorithm ensures we find the knight number in log(m) time complexity, which makes it feasible for very large input sizes.

Finally, implement this algorithm in your favourite programming language to get the final answer.

More Answers: