Let \(F_1=F_2=1\) and \(F_{j+2}=F_{j+1}+F_j\). On the vertex set \(\{1,2,\dots,n\}\), we join \(u\) and \(v\) exactly when \(u+v\) is a Fibonacci number. The problem asks for the label at a specified place in a Hamiltonian path when \(n=F_{83}\). The crucial point is that for Fibonacci-sized graphs \(n=F_k\), the path used by the implementations is not found by search; it is given by a closed arithmetic rule.
For graphs of size \(F_k\), the path can be described with modular arithmetic. The reason this works is that consecutive Fibonacci numbers are coprime, so stepping by \(F_{k-1}\) permutes the residue classes modulo \(F_k\).
Define
$$G_k=(\{1,2,\dots,F_k\},E),\qquad \{u,v\}\in E \iff u+v\in\{F_j:j\ge 1\}.$$
A Hamiltonian path is an ordering \(a_1,a_2,\dots,a_{F_k}\) that uses every vertex exactly once and satisfies
$$a_i+a_{i+1}\in\{F_j:j\ge 1\},\qquad 1\le i \lt F_k.$$
Because the graph is undirected, reversing such an ordering still gives a valid Hamiltonian path. The implementations therefore describe the path from the right end first and convert the requested left-side position only at the end.
For \(m\ge 1\), let \(\rho_m\) be the unique integer with
$$\rho_m \equiv mF_{k-1}\pmod{F_k},\qquad 1\le \rho_m \lt F_k.$$
Then the right-to-left order is
$$a_1=F_k,\qquad a_{2m}=\rho_m,\qquad a_{2m+1}=F_k-\rho_m,$$
for every \(m\) for which the index exists. If \(F_k\) is even, the path simply ends with its final even term; for the target case \(F_{83}\) is odd, so all nonterminal terms after \(a_1\) come in even-odd pairs.
This is equivalent to the compact position formula used in the implementations. If \(r\) is the position counted from the right and \(m=\lfloor r/2\rfloor\), compute
$$t \equiv mF_{k-1}\pmod{F_k},\qquad 0\le t \lt F_k,$$
and interpret residue \(0\) as the vertex \(F_k\). Then
$$v(r)=\begin{cases} F_k, & r=1,\\ t, & r\equiv 0 \pmod{2},\\ (F_k-t)\bmod F_k, & r\equiv 1 \pmod{2}. \end{cases}$$
There are three kinds of neighboring pairs in the right-end description.
The opening edge is valid because
$$a_1+a_2=F_k+\rho_1=F_k+F_{k-1}=F_{k+1}.$$
Each even-odd pair is valid because
$$a_{2m}+a_{2m+1}=\rho_m+(F_k-\rho_m)=F_k.$$
Finally, between one pair and the next, we use
$$\rho_{m+1}\equiv \rho_m+F_{k-1}\pmod{F_k}.$$
So \(\rho_{m+1}\) is either \(\rho_m+F_{k-1}\) or \(\rho_m+F_{k-1}-F_k\), which gives
$$a_{2m+1}+a_{2m+2}=(F_k-\rho_m)+\rho_{m+1}\in\{F_{k+1},F_{k-1}\}.$$
All three possible sums, \(F_{k-1}\), \(F_k\), and \(F_{k+1}\), are Fibonacci numbers. Hence every consecutive pair in the constructed order is an edge of the graph.
Since consecutive Fibonacci numbers are coprime,
$$\gcd(F_{k-1},F_k)=1.$$
Therefore multiplication by \(F_{k-1}\) permutes the nonzero residue classes modulo \(F_k\), so the values \(\rho_m\) are all distinct.
The complementary values \(F_k-\rho_m\) are also distinct. A collision between the two families would require
$$\rho_m=F_k-\rho_j,$$
which implies
$$(m+j)F_{k-1}\equiv 0\pmod{F_k}.$$
Because \(F_{k-1}\) is invertible modulo \(F_k\), this forces \(m+j\equiv 0\pmod{F_k}\). But in the relevant range we have \(1\le m+j \lt F_k\), so this cannot happen. Thus the construction uses each label exactly once and is a Hamiltonian path.
The problem gives a position counted from the left, while the closed form is easiest from the right. If the path length is \(F_k\) and the requested left position is \(L\), then the corresponding right position is
$$r=F_k-L+1.$$
Since reversing the path preserves adjacency, evaluating \(v(r)\) gives the required knight directly.
Here \(F_{k-1}=8\). The modular residues are
$$\rho_m \equiv 8m\pmod{13}\qquad(m=1,\dots,6),$$
namely
$$8,\ 3,\ 11,\ 6,\ 1,\ 9.$$
So the right-end order is
$$13,\ 8,\ 5,\ 3,\ 10,\ 11,\ 2,\ 6,\ 7,\ 1,\ 12,\ 9,\ 4.$$
Reversing it gives the left-to-right order
$$4,\ 9,\ 12,\ 1,\ 7,\ 6,\ 2,\ 11,\ 10,\ 3,\ 5,\ 8,\ 13.$$
The consecutive sums are
$$13,\ 21,\ 13,\ 8,\ 13,\ 8,\ 13,\ 21,\ 13,\ 8,\ 13,\ 21,$$
all Fibonacci numbers, so the construction is visible on a small instance.
The C++, Python, and Java implementations all follow the same arithmetic plan. They precompute Fibonacci numbers up to the required index, set \(n=F_{83}\), convert the requested left position \(10^{16}\) to the right-side index \(r=n-10^{16}+1\), and then evaluate the modular formula above.
For the target instance they use
$$F_{82}=61305790721611591,\qquad F_{83}=99194853094755497,\qquad r=89194853094755498.$$
One modular multiplication by \(F_{82}\), followed by a parity test and possibly a complement with respect to \(F_{83}\), produces the final label
$$56342087360542122.$$
The C++ implementation also includes small sanity checks: it finds a Hamiltonian path by brute force on a tiny graph, and for the Fibonacci-sized test case \(n=34\) it compares the entire closed form against a brute-force path. The Java implementation protects the modular product with arbitrary-precision arithmetic, Python relies on native big integers, and C++ uses a wider integer intermediate.
If the target size is \(F_k\), generating Fibonacci numbers up to index \(k\) costs \(O(k)\) time and \(O(k)\) memory. After that one-time setup, answering the question needs only a subtraction, an integer division by \(2\), one modular multiplication, and a parity-dependent branch, so the main computation runs in \(O(1)\) time with \(O(1)\) extra working memory. The brute-force search used for validation is confined to very small checkpoints and is not part of the large-instance algorithm.
Seien \(F_1=F_2=1\) und \(F_{j+2}=F_{j+1}+F_j\). Auf den Knoten \(\{1,2,\dots,n\}\) gibt es genau dann eine Kante zwischen \(u\) und \(v\), wenn \(u+v\) eine Fibonacci-Zahl ist. Gesucht ist die Beschriftung an einer vorgegebenen Position eines Hamilton-Pfads für \(n=F_{83}\). Der entscheidende Punkt ist: Für Fibonacci-Größen \(n=F_k\) wird der Pfad nicht gesucht, sondern durch eine geschlossene arithmetische Vorschrift beschrieben.
Für Graphen der Größe \(F_k\) lässt sich der Pfad mit modularer Arithmetik angeben. Das funktioniert, weil aufeinanderfolgende Fibonacci-Zahlen teilerfremd sind und deshalb Schritte der Größe \(F_{k-1}\) die Restklassen modulo \(F_k\) permutieren.
Definiere
$$G_k=(\{1,2,\dots,F_k\},E),\qquad \{u,v\}\in E \iff u+v\in\{F_j:j\ge 1\}.$$
Ein Hamilton-Pfad ist eine Reihenfolge \(a_1,a_2,\dots,a_{F_k}\), die jeden Knoten genau einmal verwendet und
$$a_i+a_{i+1}\in\{F_j:j\ge 1\},\qquad 1\le i \lt F_k.$$
erfüllt. Da der Graph ungerichtet ist, bleibt ein Hamilton-Pfad auch nach dem Umdrehen gültig. Deshalb beschreiben die Implementierungen den Pfad zunächst vom rechten Ende aus und wandeln die links gezählte Position erst am Schluss um.
Für \(m\ge 1\) sei \(\rho_m\) die eindeutige Zahl mit
$$\rho_m \equiv mF_{k-1}\pmod{F_k},\qquad 1\le \rho_m \lt F_k.$$
Dann lautet die Ordnung von rechts nach links
$$a_1=F_k,\qquad a_{2m}=\rho_m,\qquad a_{2m+1}=F_k-\rho_m,$$
für jedes \(m\), für das der Index noch existiert. Ist \(F_k\) gerade, endet die Folge einfach beim letzten geraden Term; im Zielproblem ist \(F_{83}\) ungerade, daher erscheinen nach \(a_1\) alle nichtterminalen Terme paarweise.
Das ist äquivalent zur kompakten Positionsformel der Implementierungen. Ist \(r\) die von rechts gezählte Position und \(m=\lfloor r/2\rfloor\), berechnet man
$$t \equiv mF_{k-1}\pmod{F_k},\qquad 0\le t \lt F_k,$$
und interpretiert den Rest \(0\) als Knoten \(F_k\). Dann gilt
$$v(r)=\begin{cases} F_k, & r=1,\\ t, & r\equiv 0 \pmod{2},\\ (F_k-t)\bmod F_k, & r\equiv 1 \pmod{2}. \end{cases}$$
In der Beschreibung vom rechten Ende gibt es drei Arten benachbarter Paare.
Die Anfangskante ist gültig, denn
$$a_1+a_2=F_k+\rho_1=F_k+F_{k-1}=F_{k+1}.$$
Jedes gerade-ungerade Paar ist gültig, weil
$$a_{2m}+a_{2m+1}=\rho_m+(F_k-\rho_m)=F_k.$$
Zwischen einem Paar und dem nächsten verwenden wir
$$\rho_{m+1}\equiv \rho_m+F_{k-1}\pmod{F_k}.$$
Also ist \(\rho_{m+1}\) entweder \(\rho_m+F_{k-1}\) oder \(\rho_m+F_{k-1}-F_k\). Damit folgt
$$a_{2m+1}+a_{2m+2}=(F_k-\rho_m)+\rho_{m+1}\in\{F_{k+1},F_{k-1}\}.$$
Alle drei möglichen Summen, also \(F_{k-1}\), \(F_k\) und \(F_{k+1}\), sind Fibonacci-Zahlen. Somit ist jedes aufeinanderfolgende Paar im konstruierten Pfad eine Kante des Graphen.
Da aufeinanderfolgende Fibonacci-Zahlen teilerfremd sind, gilt
$$\gcd(F_{k-1},F_k)=1.$$
Multiplikation mit \(F_{k-1}\) permutiert daher die von \(0\) verschiedenen Restklassen modulo \(F_k\), also sind die Werte \(\rho_m\) paarweise verschieden.
Die komplementären Werte \(F_k-\rho_m\) sind ebenfalls paarweise verschieden. Eine Kollision zwischen beiden Familien würde
$$\rho_m=F_k-\rho_j$$
bedeuten und damit
$$(m+j)F_{k-1}\equiv 0\pmod{F_k}.$$
Wegen der Invertierbarkeit von \(F_{k-1}\) modulo \(F_k\) müsste dann \(m+j\equiv 0\pmod{F_k}\) gelten. Im relevanten Bereich ist aber \(1\le m+j \lt F_k\), also unmöglich. Damit erscheint jede Beschriftung genau einmal und die Konstruktion ist tatsächlich ein Hamilton-Pfad.
Die Aufgabe gibt die Position von links an, die geschlossene Formel arbeitet aber am bequemsten von rechts. Hat der Pfad Länge \(F_k\) und ist die gewünschte Linksposition \(L\), so gehört dazu die Rechtsposition
$$r=F_k-L+1.$$
Da das Umkehren des Pfads die Adjazenz erhält, liefert die Auswertung von \(v(r)\) direkt den gesuchten Ritter.
Hier ist \(F_{k-1}=8\). Die modularen Reste lauten
$$\rho_m \equiv 8m\pmod{13}\qquad(m=1,\dots,6),$$
also
$$8,\ 3,\ 11,\ 6,\ 1,\ 9.$$
Damit ergibt sich von rechts nach links die Folge
$$13,\ 8,\ 5,\ 3,\ 10,\ 11,\ 2,\ 6,\ 7,\ 1,\ 12,\ 9,\ 4.$$
Umdrehen liefert die Reihenfolge von links nach rechts
$$4,\ 9,\ 12,\ 1,\ 7,\ 6,\ 2,\ 11,\ 10,\ 3,\ 5,\ 8,\ 13.$$
Die aufeinanderfolgenden Summen sind
$$13,\ 21,\ 13,\ 8,\ 13,\ 8,\ 13,\ 21,\ 13,\ 8,\ 13,\ 21,$$
also durchgehend Fibonacci-Zahlen. An diesem kleinen Fall sieht man die Konstruktion direkt.
Die C++-, Python- und Java-Implementierungen folgen demselben arithmetischen Plan. Zuerst werden die Fibonacci-Zahlen bis zum benötigten Index erzeugt, dann wird \(n=F_{83}\) gesetzt, die angefragte Linksposition \(10^{16}\) in \(r=n-10^{16}+1\) umgerechnet und schließlich die obige Modularformel ausgewertet.
Für den Zielwert verwenden die Implementierungen
$$F_{82}=61305790721611591,\qquad F_{83}=99194853094755497,\qquad r=89194853094755498.$$
Eine modulare Multiplikation mit \(F_{82}\), ein Paritätstest und gegebenenfalls die Ergänzung zu \(F_{83}\) liefern den Endwert
$$56342087360542122.$$
Die C++-Implementierung enthält zusätzlich kleine Plausibilitätsprüfungen: Zunächst wird auf einem winzigen Graphen ein Hamilton-Pfad per Brute Force gefunden, anschließend wird für den Fibonacci-Fall \(n=34\) die geschlossene Formel vollständig mit einem Brute-Force-Pfad verglichen. Die Java-Implementierung schützt das modulare Produkt mit beliebig großer Ganzzahlarithmetik, Python nutzt eingebaute Big Integers und C++ ein breiteres Zwischenformat.
Ist die Zielgröße \(F_k\), dann kostet das Erzeugen der Fibonacci-Zahlen bis Index \(k\) \(O(k)\) Zeit und \(O(k)\) Speicher. Nach dieser einmaligen Vorbereitung braucht die eigentliche Anfrage nur eine Subtraktion, eine Ganzzahldivision durch \(2\), eine modulare Multiplikation und einen kleinen Verzweigungsschritt. Die Laufzeit ist also \(O(1)\) bei \(O(1)\) zusätzlichem Arbeitsspeicher. Die Brute-Force-Suche dient nur der Validierung winziger Testfälle und gehört nicht zum Großinstanz-Algorithmus.
\(F_1=F_2=1\) ve \(F_{j+2}=F_{j+1}+F_j\) olsun. Düğümleri \(\{1,2,\dots,n\}\) olan grafikte \(u\) ile \(v\) arasında ancak ve ancak \(u+v\) bir Fibonacci sayısıysa kenar vardır. Soru, \(n=F_{83}\) için bir Hamilton yolundaki belirli bir konumdaki etiketi istemektedir. Kritik nokta şudur: Fibonacci boyutlu \(n=F_k\) durumlarında kullanılan yol aramayla bulunmuyor; kapalı bir aritmetik kural ile doğrudan yazılıyor.
\(F_k\) boyutlu graflarda yol modüler aritmetik ile tarif edilebilir. Bunun sebebi ardışık Fibonacci sayılarının aralarında asal olmasıdır; dolayısıyla \(F_{k-1}\) adımıyla ilerlemek, mod \(F_k\) altında kalan sınıfları permüte eder.
Şunu tanımlayalım:
$$G_k=(\{1,2,\dots,F_k\},E),\qquad \{u,v\}\in E \iff u+v\in\{F_j:j\ge 1\}.$$
Hamilton yolu, her düğümü tam bir kez kullanan ve
$$a_i+a_{i+1}\in\{F_j:j\ge 1\},\qquad 1\le i \lt F_k.$$
koşulunu sağlayan \(a_1,a_2,\dots,a_{F_k}\) sıralamasıdır. Graf yönsüz olduğu için, bu sıralamayı ters çevirmek de yine geçerli bir Hamilton yolu verir. Bu nedenle uygulamalar önce yolu sağ uçtan tarif eder, soldan verilen pozisyonu ise en sonda dönüştürür.
\(m\ge 1\) için \(\rho_m\),
$$\rho_m \equiv mF_{k-1}\pmod{F_k},\qquad 1\le \rho_m \lt F_k$$
koşulunu sağlayan tek sayı olsun. O zaman sağdan sola doğru sıra
$$a_1=F_k,\qquad a_{2m}=\rho_m,\qquad a_{2m+1}=F_k-\rho_m,$$
şeklindedir; burada indeks var oldukça devam edilir. Eğer \(F_k\) çiftse dizi son çift terimde biter; hedef durumunda \(F_{83}\) tek olduğu için \(a_1\)'den sonraki tüm bitişik olmayan terimler çift-tek çiftleri halinde gelir.
Bu, uygulamaların kullandığı kompakt konum formülüyle aynıdır. Sağdan sayılan konum \(r\) ve \(m=\lfloor r/2\rfloor\) olmak üzere
$$t \equiv mF_{k-1}\pmod{F_k},\qquad 0\le t \lt F_k$$
hesaplanır ve kalan \(0\), düğüm \(F_k\) olarak yorumlanır. Böylece
$$v(r)=\begin{cases} F_k, & r=1,\\ t, & r\equiv 0 \pmod{2},\\ (F_k-t)\bmod F_k, & r\equiv 1 \pmod{2}. \end{cases}$$
Sağ uçtan yazılan bu dizide üç tip komşu çift vardır.
İlk kenar geçerlidir, çünkü
$$a_1+a_2=F_k+\rho_1=F_k+F_{k-1}=F_{k+1}.$$
Her çift-indeksli ve ardından gelen tek-indeksli terim de geçerlidir:
$$a_{2m}+a_{2m+1}=\rho_m+(F_k-\rho_m)=F_k.$$
Bir çift ile sonraki çift arasındaki geçişte ise
$$\rho_{m+1}\equiv \rho_m+F_{k-1}\pmod{F_k}$$
kullanılır. Bu yüzden \(\rho_{m+1}\) ya \(\rho_m+F_{k-1}\) ya da \(\rho_m+F_{k-1}-F_k\) olur. Sonuç olarak
$$a_{2m+1}+a_{2m+2}=(F_k-\rho_m)+\rho_{m+1}\in\{F_{k+1},F_{k-1}\}.$$
Ortaya çıkan üç toplam da, yani \(F_{k-1}\), \(F_k\) ve \(F_{k+1}\), Fibonacci sayılarıdır. Dolayısıyla kurulan sıradaki her ardışık çift gerçekten grafın bir kenarıdır.
Ardışık Fibonacci sayıları aralarında asal olduğundan
$$\gcd(F_{k-1},F_k)=1.$$
Bu nedenle \(F_{k-1}\) ile çarpmak, mod \(F_k\) altında sıfır dışındaki kalan sınıflarını permüte eder; yani \(\rho_m\) değerlerinin hepsi birbirinden farklıdır.
Tamamlayıcı değerler \(F_k-\rho_m\) de birbirinden farklıdır. İki aile arasında bir çakışma olması için
$$\rho_m=F_k-\rho_j$$
gerekir; bu da
$$(m+j)F_{k-1}\equiv 0\pmod{F_k}$$
demektir. \(F_{k-1}\), mod \(F_k\) altında terslenebilir olduğundan buradan \(m+j\equiv 0\pmod{F_k}\) çıkar. Oysa ilgili aralıkta \(1\le m+j \lt F_k\) olduğundan bu imkansızdır. Böylece her etiket tam bir kez görülür ve yapı gerçekten bir Hamilton yoludur.
Soruda verilen sıra soldan sayılır; kapalı form ise sağdan sayıldığında en kolay halini alır. Yolun uzunluğu \(F_k\) ve soldan istenen konum \(L\) ise buna karşılık gelen sağ konum
$$r=F_k-L+1$$
olur. Yolun ters çevrilmesi komşuluğu bozmadığı için \(v(r)\) doğrudan aranan şövalyeyi verir.
Burada \(F_{k-1}=8\) olur. Modüler kalıntılar
$$\rho_m \equiv 8m\pmod{13}\qquad(m=1,\dots,6)$$
şeklindedir; yani
$$8,\ 3,\ 11,\ 6,\ 1,\ 9.$$
Buna göre sağdan sola sıra
$$13,\ 8,\ 5,\ 3,\ 10,\ 11,\ 2,\ 6,\ 7,\ 1,\ 12,\ 9,\ 4$$
olur. Ters çevrilince soldan sağa ziyafet sırası
$$4,\ 9,\ 12,\ 1,\ 7,\ 6,\ 2,\ 11,\ 10,\ 3,\ 5,\ 8,\ 13$$
elde edilir. Ardışık toplamlar
$$13,\ 21,\ 13,\ 8,\ 13,\ 8,\ 13,\ 21,\ 13,\ 8,\ 13,\ 21$$
olup hepsi Fibonacci sayısıdır. Küçük bir örnekte yapı açıkça görülebilir.
C++, Python ve Java uygulamalarının üçü de aynı aritmetik planı izler. Önce gerekli indekse kadar Fibonacci sayıları üretilir, sonra \(n=F_{83}\) alınır, soldan verilen \(10^{16}\) konumu \(r=n-10^{16}+1\) ile sağdan sayılan konuma çevrilir ve yukarıdaki modüler formül uygulanır.
Hedef örnekte kullanılan sayılar şunlardır:
$$F_{82}=61305790721611591,\qquad F_{83}=99194853094755497,\qquad r=89194853094755498.$$
\(F_{82}\) ile tek bir modüler çarpım, bir parite kontrolü ve gerekirse \(F_{83}\)'e göre tümleme işlemi sonunda
$$56342087360542122$$
etiketi elde edilir. C++ uygulaması ayrıca küçük doğrulamalar yapar: önce çok küçük bir graf üzerinde brute-force Hamilton yolu bulur, sonra Fibonacci boyutlu \(n=34\) durumunda kapalı formu brute-force yol ile tamamen karşılaştırır. Java uygulaması modüler çarpımda taşmayı önlemek için keyfi büyüklükte tamsayı aritmetiği kullanır; Python yerleşik büyük tamsayılara, C++ ise daha geniş bir ara tam sayı türüne dayanır.
Hedef boyut \(F_k\) olsun. Fibonacci sayılarının \(k\) indeksine kadar üretilmesi \(O(k)\) zaman ve \(O(k)\) bellek gerektirir. Bu bir defalık hazırlıktan sonra asıl sorgu yalnızca bir çıkarma, \(2\)'ye tam bölme, bir modüler çarpım ve pariteye bağlı küçük bir dallanma içerir. Dolayısıyla ana hesaplama \(O(1)\) zamanda ve \(O(1)\) ek çalışma belleğiyle yapılır. Brute-force arama yalnızca çok küçük kontrol örnekleri içindir; büyük örnek algoritmasının parçası değildir.
Sean \(F_1=F_2=1\) y \(F_{j+2}=F_{j+1}+F_j\). En el conjunto de vértices \(\{1,2,\dots,n\}\), unimos \(u\) y \(v\) exactamente cuando \(u+v\) es un número de Fibonacci. La tarea pide la etiqueta en una posición dada de un camino hamiltoniano cuando \(n=F_{83}\). El punto clave es que, para tamaños de Fibonacci \(n=F_k\), el camino usado por las implementaciones no se obtiene por búsqueda: viene dado por una regla aritmética cerrada.
Para grafos de tamaño \(F_k\), el camino puede describirse con aritmética modular. Esto funciona porque dos números consecutivos de Fibonacci son coprimos, de modo que avanzar de \(F_{k-1}\) en \(F_{k-1}\) permuta las clases residuales módulo \(F_k\).
Definimos
$$G_k=(\{1,2,\dots,F_k\},E),\qquad \{u,v\}\in E \iff u+v\in\{F_j:j\ge 1\}.$$
Un camino hamiltoniano es un orden \(a_1,a_2,\dots,a_{F_k}\) que usa cada vértice exactamente una vez y cumple
$$a_i+a_{i+1}\in\{F_j:j\ge 1\},\qquad 1\le i \lt F_k.$$
Como el grafo es no dirigido, invertir el orden sigue produciendo un camino hamiltoniano válido. Por eso las implementaciones describen primero el camino desde el extremo derecho y convierten la posición pedida desde la izquierda al final.
Para \(m\ge 1\), sea \(\rho_m\) el único entero tal que
$$\rho_m \equiv mF_{k-1}\pmod{F_k},\qquad 1\le \rho_m \lt F_k.$$
Entonces el orden de derecha a izquierda es
$$a_1=F_k,\qquad a_{2m}=\rho_m,\qquad a_{2m+1}=F_k-\rho_m,$$
para todo \(m\) cuyo índice exista. Si \(F_k\) es par, la secuencia simplemente termina en su último término par; en el caso objetivo \(F_{83}\) es impar, así que todos los términos no terminales después de \(a_1\) aparecen en pares par-impar.
Esto equivale a la fórmula compacta de posición usada por la implementación. Si \(r\) es la posición contada desde la derecha y \(m=\lfloor r/2\rfloor\), calculamos
$$t \equiv mF_{k-1}\pmod{F_k},\qquad 0\le t \lt F_k,$$
e interpretamos el residuo \(0\) como el vértice \(F_k\). Entonces
$$v(r)=\begin{cases} F_k, & r=1,\\ t, & r\equiv 0 \pmod{2},\\ (F_k-t)\bmod F_k, & r\equiv 1 \pmod{2}. \end{cases}$$
En la descripción desde la derecha aparecen tres tipos de pares vecinos.
La arista inicial es válida porque
$$a_1+a_2=F_k+\rho_1=F_k+F_{k-1}=F_{k+1}.$$
Cada par par-impar es válido porque
$$a_{2m}+a_{2m+1}=\rho_m+(F_k-\rho_m)=F_k.$$
Entre un par y el siguiente usamos
$$\rho_{m+1}\equiv \rho_m+F_{k-1}\pmod{F_k}.$$
Por tanto, \(\rho_{m+1}\) es o bien \(\rho_m+F_{k-1}\), o bien \(\rho_m+F_{k-1}-F_k\). En consecuencia,
$$a_{2m+1}+a_{2m+2}=(F_k-\rho_m)+\rho_{m+1}\in\{F_{k+1},F_{k-1}\}.$$
Las tres sumas posibles, \(F_{k-1}\), \(F_k\) y \(F_{k+1}\), son números de Fibonacci. Así, cada par consecutivo del orden construido es una arista del grafo.
Como números consecutivos de Fibonacci son coprimos,
$$\gcd(F_{k-1},F_k)=1.$$
Entonces multiplicar por \(F_{k-1}\) permuta las clases residuales no nulas módulo \(F_k\), de modo que los valores \(\rho_m\) son todos distintos.
Los complementos \(F_k-\rho_m\) también son todos distintos. Una colisión entre las dos familias exigiría
$$\rho_m=F_k-\rho_j,$$
lo cual implica
$$(m+j)F_{k-1}\equiv 0\pmod{F_k}.$$
Puesto que \(F_{k-1}\) es invertible módulo \(F_k\), eso fuerza \(m+j\equiv 0\pmod{F_k}\). Pero en el rango relevante se cumple \(1\le m+j \lt F_k\), así que es imposible. Por tanto, la construcción recorre cada etiqueta exactamente una vez y realmente forma un camino hamiltoniano.
El problema da una posición contada desde la izquierda, mientras que la fórmula cerrada es más cómoda desde la derecha. Si la longitud del camino es \(F_k\) y la posición pedida desde la izquierda es \(L\), entonces la posición correspondiente desde la derecha es
$$r=F_k-L+1.$$
Como invertir el camino conserva la adyacencia, evaluar \(v(r)\) da directamente el caballero buscado.
Aquí \(F_{k-1}=8\). Los residuos modulares son
$$\rho_m \equiv 8m\pmod{13}\qquad(m=1,\dots,6),$$
es decir,
$$8,\ 3,\ 11,\ 6,\ 1,\ 9.$$
Por tanto, el orden desde la derecha es
$$13,\ 8,\ 5,\ 3,\ 10,\ 11,\ 2,\ 6,\ 7,\ 1,\ 12,\ 9,\ 4.$$
Al invertirlo obtenemos el orden de izquierda a derecha
$$4,\ 9,\ 12,\ 1,\ 7,\ 6,\ 2,\ 11,\ 10,\ 3,\ 5,\ 8,\ 13.$$
Las sumas consecutivas son
$$13,\ 21,\ 13,\ 8,\ 13,\ 8,\ 13,\ 21,\ 13,\ 8,\ 13,\ 21,$$
todas ellas números de Fibonacci. En un ejemplo pequeño la construcción se ve de forma directa.
Las implementaciones en C++, Python y Java siguen el mismo plan aritmético. Primero precalculan los números de Fibonacci hasta el índice requerido, después fijan \(n=F_{83}\), convierten la posición pedida desde la izquierda \(10^{16}\) en \(r=n-10^{16}+1\) y finalmente evalúan la fórmula modular anterior.
Para la instancia objetivo usan
$$F_{82}=61305790721611591,\qquad F_{83}=99194853094755497,\qquad r=89194853094755498.$$
Una multiplicación modular por \(F_{82}\), seguida de una comprobación de paridad y, si hace falta, el complemento respecto de \(F_{83}\), produce la etiqueta final
$$56342087360542122.$$
La implementación en C++ también incluye comprobaciones pequeñas: encuentra un camino hamiltoniano por fuerza bruta en un grafo diminuto y luego compara la fórmula cerrada con un camino por fuerza bruta en el caso de tamaño Fibonacci \(n=34\). La implementación en Java protege el producto modular con aritmética de precisión arbitraria; Python usa enteros grandes nativos y C++ un entero intermedio más ancho.
Si el tamaño objetivo es \(F_k\), generar los números de Fibonacci hasta el índice \(k\) cuesta \(O(k)\) tiempo y \(O(k)\) memoria. Tras esa preparación única, responder la consulta requiere solo una resta, una división entera por \(2\), una multiplicación modular y una bifurcación según la paridad. Por ello, el cálculo principal funciona en \(O(1)\) tiempo y \(O(1)\) memoria extra. La búsqueda por fuerza bruta se limita a verificaciones diminutas y no forma parte del algoritmo para la instancia grande.
设 \(F_1=F_2=1\)，并且 \(F_{j+2}=F_{j+1}+F_j\)。在顶点集合 \(\{1,2,\dots,n\}\) 上，如果且仅如果 \(u+v\) 是斐波那契数，就在 \(u\) 与 \(v\) 之间连边。题目要求的是当 \(n=F_{83}\) 时，某条哈密顿路径上指定位置对应的标签。关键事实是：当图的规模恰好是某个斐波那契数 \(F_k\) 时，实现并不是在巨大图上做搜索，而是直接使用一条闭式的算术规则来写出整条路径。
对于大小为 \(F_k\) 的图，这条路径可以用模运算精确描述。其根本原因在于相邻两个斐波那契数互素，因此用步长 \(F_{k-1}\) 在模 \(F_k\) 意义下反复前进，会把所有剩余类重新排列一遍。
定义
$$G_k=(\{1,2,\dots,F_k\},E),\qquad \{u,v\}\in E \iff u+v\in\{F_j:j\ge 1\}.$$
哈密顿路径就是一个顺序 \(a_1,a_2,\dots,a_{F_k}\)，它恰好使用每个顶点一次，并满足
$$a_i+a_{i+1}\in\{F_j:j\ge 1\},\qquad 1\le i \lt F_k.$$
由于图是无向的，把一条合法路径整体反过来仍然合法。因此实现先从右端描述这条路径，最后再把题目给出的“从左数的位置”换成“从右数的位置”。
对每个 \(m\ge 1\)，令 \(\rho_m\) 为满足下式的唯一整数：
$$\rho_m \equiv mF_{k-1}\pmod{F_k},\qquad 1\le \rho_m \lt F_k.$$
那么从右到左的顺序可写成
$$a_1=F_k,\qquad a_{2m}=\rho_m,\qquad a_{2m+1}=F_k-\rho_m,$$
其中 \(m\) 取到对应下标仍然存在为止。如果 \(F_k\) 是偶数，那么序列只是在最后一个偶数位置结束；而目标情形里 \(F_{83}\) 是奇数，所以除去起点 \(a_1\) 之外，其余非终点项都以“偶位一项、奇位一项”的形式成对出现。
这与实现里使用的紧凑位置公式完全等价。若 \(r\) 表示从右端开始计数的位置，且 \(m=\lfloor r/2\rfloor\)，先计算
$$t \equiv mF_{k-1}\pmod{F_k},\qquad 0\le t \lt F_k,$$
并把余数 \(0\) 解释成顶点 \(F_k\)。于是
$$v(r)=\begin{cases} F_k, & r=1,\\ t, & r\equiv 0 \pmod{2},\\ (F_k-t)\bmod F_k, & r\equiv 1 \pmod{2}. \end{cases}$$
从右端写出的序列里，一共会出现三类相邻关系。
第一类是开头那条边：
$$a_1+a_2=F_k+\rho_1=F_k+F_{k-1}=F_{k+1}.$$
第二类是每个偶位和紧随其后的奇位：
$$a_{2m}+a_{2m+1}=\rho_m+(F_k-\rho_m)=F_k.$$
第三类是一个奇位与下一对中的偶位之间。因为
$$\rho_{m+1}\equiv \rho_m+F_{k-1}\pmod{F_k},$$
所以 \(\rho_{m+1}\) 只能是 \(\rho_m+F_{k-1}\) 或 \(\rho_m+F_{k-1}-F_k\)。于是有
$$a_{2m+1}+a_{2m+2}=(F_k-\rho_m)+\rho_{m+1}\in\{F_{k+1},F_{k-1}\}.$$
也就是说，相邻两项的和只可能是 \(F_{k-1}\)、\(F_k\) 或 \(F_{k+1}\)，它们全都是斐波那契数。因此构造出来的每一对相邻顶点都确实有边相连。
由于相邻斐波那契数互素，
$$\gcd(F_{k-1},F_k)=1.$$
因此，模 \(F_k\) 下乘以 \(F_{k-1}\) 会把所有非零剩余类做一个置换，所以 \(\rho_m\) 两两不同。
对应的补数 \(F_k-\rho_m\) 也两两不同。如果这两类数发生碰撞，就必须有
$$\rho_m=F_k-\rho_j,$$
从而推出
$$(m+j)F_{k-1}\equiv 0\pmod{F_k}.$$
因为 \(F_{k-1}\) 在模 \(F_k\) 下可逆，所以必有 \(m+j\equiv 0\pmod{F_k}\)。但在这里 \(m\) 和 \(j\) 的取值范围满足 \(1\le m+j \lt F_k\)，所以这是不可能的。于是整条构造路径恰好访问每个标签一次，确实是一条哈密顿路径。
题目给的是“从左往右”的位置，而闭式公式从“右端往左”写起来最自然。若整条路径长度为 \(F_k\)，从左数的位置是 \(L\)，那么对应的右侧位置就是
$$r=F_k-L+1.$$
因为把路径整体反向不会破坏相邻性，所以只要代入 \(v(r)\) 就能直接得到答案。
这时 \(F_{k-1}=8\)。模余数序列满足
$$\rho_m \equiv 8m\pmod{13}\qquad(m=1,\dots,6),$$
具体为
$$8,\ 3,\ 11,\ 6,\ 1,\ 9.$$
于是从右端读到的顺序是
$$13,\ 8,\ 5,\ 3,\ 10,\ 11,\ 2,\ 6,\ 7,\ 1,\ 12,\ 9,\ 4.$$
反过来之后，从左到右的顺序变成
$$4,\ 9,\ 12,\ 1,\ 7,\ 6,\ 2,\ 11,\ 10,\ 3,\ 5,\ 8,\ 13.$$
相邻两项的和为
$$13,\ 21,\ 13,\ 8,\ 13,\ 8,\ 13,\ 21,\ 13,\ 8,\ 13,\ 21,$$
全部都是斐波那契数，所以在小规模例子上也能直观看到这套构造是正确的。
C++、Python 和 Java 三个实现都遵循同一套算术流程。它们先预计算所需范围内的斐波那契数，然后取 \(n=F_{83}\)，把题目给出的左侧位置 \(10^{16}\) 换成 \(r=n-10^{16}+1\)，最后代入上面的模公式。
对目标实例，实际使用的是
$$F_{82}=61305790721611591,\qquad F_{83}=99194853094755497,\qquad r=89194853094755498.$$
做一次关于 \(F_{83}\) 的模乘，再根据奇偶性决定是否取补数，就得到最终标签
$$56342087360542122.$$
C++ 实现还带有小规模校验：它先在极小的图上用暴力法找哈密顿路径，再在斐波那契规模 \(n=34\) 的情形下，把整条闭式结果与暴力路径逐项比较。Java 实现用任意精度整数保护模乘不溢出；Python 依赖原生大整数；C++ 则使用更宽的中间整数类型。
若目标规模为 \(F_k\)，那么把斐波那契数预处理到第 \(k\) 项需要 \(O(k)\) 时间和 \(O(k)\) 空间。完成这一步之后，真正回答题目只需要一次减法、一次整除 \(2\)、一次模乘以及一次基于奇偶性的分支，因此主计算部分的时间复杂度是 \(O(1)\)，额外工作空间也是 \(O(1)\)。C++ 中的暴力搜索只用于很小的校验点，不属于大实例算法本身。
Пусть \(F_1=F_2=1\) и \(F_{j+2}=F_{j+1}+F_j\). На множестве вершин \(\{1,2,\dots,n\}\) ребро между \(u\) и \(v\) проводится тогда и только тогда, когда \(u+v\) является числом Фибоначчи. Требуется определить метку в заданной позиции гамильтонова пути при \(n=F_{83}\). Важнейший факт состоит в том, что для размеров вида \(n=F_k\) путь не ищется перебором: он задается замкнутым арифметическим правилом.
Для графов размера \(F_k\) путь описывается с помощью модульной арифметики. Это работает потому, что соседние числа Фибоначчи взаимно просты, а значит, шаг на \(F_{k-1}\) переставляет классы вычетов по модулю \(F_k\).
Определим
$$G_k=(\{1,2,\dots,F_k\},E),\qquad \{u,v\}\in E \iff u+v\in\{F_j:j\ge 1\}.$$
Гамильтонов путь — это порядок \(a_1,a_2,\dots,a_{F_k}\), который использует каждую вершину ровно один раз и удовлетворяет условию
$$a_i+a_{i+1}\in\{F_j:j\ge 1\},\qquad 1\le i \lt F_k.$$
Поскольку граф неориентированный, обращение такого порядка тоже дает допустимый гамильтонов путь. Поэтому реализации сначала описывают путь от правого конца и лишь затем переводят позицию, заданную слева.
Для \(m\ge 1\) обозначим через \(\rho_m\) единственное число, для которого
$$\rho_m \equiv mF_{k-1}\pmod{F_k},\qquad 1\le \rho_m \lt F_k.$$
Тогда порядок справа налево имеет вид
$$a_1=F_k,\qquad a_{2m}=\rho_m,\qquad a_{2m+1}=F_k-\rho_m,$$
для всех \(m\), пока соответствующий индекс существует. Если \(F_k\) четно, последовательность просто заканчивается на последнем четном члене; в целевом случае \(F_{83}\) нечетно, поэтому после \(a_1\) все нетерминальные элементы идут парами.
Это эквивалентно компактной формуле позиции, используемой в реализации. Если \(r\) — позиция, считаемая справа, а \(m=\lfloor r/2\rfloor\), то вычисляется
$$t \equiv mF_{k-1}\pmod{F_k},\qquad 0\le t \lt F_k,$$
а остаток \(0\) интерпретируется как вершина \(F_k\). После этого
$$v(r)=\begin{cases} F_k, & r=1,\\ t, & r\equiv 0 \pmod{2},\\ (F_k-t)\bmod F_k, & r\equiv 1 \pmod{2}. \end{cases}$$
В описании от правого края есть три типа соседних пар.
Первая дуга допустима, потому что
$$a_1+a_2=F_k+\rho_1=F_k+F_{k-1}=F_{k+1}.$$
Каждая четно-нечетная пара тоже допустима:
$$a_{2m}+a_{2m+1}=\rho_m+(F_k-\rho_m)=F_k.$$
Для перехода между соседними парами используем
$$\rho_{m+1}\equiv \rho_m+F_{k-1}\pmod{F_k}.$$
Значит, \(\rho_{m+1}\) равно либо \(\rho_m+F_{k-1}\), либо \(\rho_m+F_{k-1}-F_k\). Поэтому
$$a_{2m+1}+a_{2m+2}=(F_k-\rho_m)+\rho_{m+1}\in\{F_{k+1},F_{k-1}\}.$$
Все три возможные суммы, \(F_{k-1}\), \(F_k\) и \(F_{k+1}\), являются числами Фибоначчи. Следовательно, каждая соседняя пара в построенном порядке действительно образует ребро графа.
Так как соседние числа Фибоначчи взаимно просты, имеем
$$\gcd(F_{k-1},F_k)=1.$$
Значит, умножение на \(F_{k-1}\) переставляет все ненулевые классы вычетов по модулю \(F_k\), и потому значения \(\rho_m\) попарно различны.
Дополнительные значения \(F_k-\rho_m\) тоже попарно различны. Совпадение между двумя семействами потребовало бы
$$\rho_m=F_k-\rho_j,$$
а это означает
$$(m+j)F_{k-1}\equiv 0\pmod{F_k}.$$
Поскольку \(F_{k-1}\) обратим по модулю \(F_k\), получаем \(m+j\equiv 0\pmod{F_k}\). Но в нужном диапазоне выполняется \(1\le m+j \lt F_k\), что невозможно. Значит, конструкция проходит по каждой метке ровно один раз и действительно задает гамильтонов путь.
В условии позиция задана слева, а замкнутая формула удобнее справа. Если длина пути равна \(F_k\), а нужная позиция слева равна \(L\), то соответствующая позиция справа равна
$$r=F_k-L+1.$$
Так как обращение пути не нарушает смежность, подстановка в \(v(r)\) сразу дает искомого рыцаря.
Здесь \(F_{k-1}=8\). Модульные остатки удовлетворяют
$$\rho_m \equiv 8m\pmod{13}\qquad(m=1,\dots,6),$$
то есть равны
$$8,\ 3,\ 11,\ 6,\ 1,\ 9.$$
Тогда порядок справа налево таков:
$$13,\ 8,\ 5,\ 3,\ 10,\ 11,\ 2,\ 6,\ 7,\ 1,\ 12,\ 9,\ 4.$$
После обращения получаем порядок слева направо
$$4,\ 9,\ 12,\ 1,\ 7,\ 6,\ 2,\ 11,\ 10,\ 3,\ 5,\ 8,\ 13.$$
Суммы соседних вершин равны
$$13,\ 21,\ 13,\ 8,\ 13,\ 8,\ 13,\ 21,\ 13,\ 8,\ 13,\ 21,$$
и все они входят в последовательность Фибоначчи. На маленьком примере конструкция видна полностью.
Реализации на C++, Python и Java используют один и тот же арифметический план. Сначала они вычисляют числа Фибоначчи до нужного индекса, затем берут \(n=F_{83}\), переводят заданную слева позицию \(10^{16}\) в \(r=n-10^{16}+1\) и после этого применяют модульную формулу.
Для целевого случая используются числа
$$F_{82}=61305790721611591,\qquad F_{83}=99194853094755497,\qquad r=89194853094755498.$$
Одно модульное умножение на \(F_{82}\), проверка четности и при необходимости дополнение до \(F_{83}\) дают окончательную метку
$$56342087360542122.$$
В C++-реализации есть и маленькие проверки: сначала гамильтонов путь ищется полным перебором на крошечном графе, а затем для случая Fibonacci-размера \(n=34\) вся замкнутая формула сравнивается с найденным перебором путем. Java защищает модульное умножение арифметикой произвольной точности; Python опирается на встроенные длинные целые; C++ использует более широкий промежуточный тип.
Если целевой размер равен \(F_k\), то построение чисел Фибоначчи до индекса \(k\) требует \(O(k)\) времени и \(O(k)\) памяти. После этой однократной подготовки ответ на вопрос требует только вычитания, деления на \(2\), одного модульного умножения и ветвления по четности. Значит, основное вычисление работает за \(O(1)\) времени и использует \(O(1)\) дополнительной памяти. Полный перебор применяется только для микроскопических контрольных примеров и не входит в алгоритм для большой задачи.
لنأخذ \(F_1=F_2=1\) و \(F_{j+2}=F_{j+1}+F_j\). على مجموعة الرؤوس \(\{1,2,\dots,n\}\)، نصل بين \(u\) و \(v\) إذا وفقط إذا كان \(u+v\) عددًا من أعداد فيبوناتشي. المطلوب هو معرفة التسمية الموجودة في موضع محدد من مسار هاملتوني عندما \(n=F_{83}\). الفكرة الحاسمة هي أن الحالة ذات الحجم الفيبوناتشي \(n=F_k\) لا تُحل بالبحث في الرسم الضخم، بل بقاعدة حسابية مغلقة تعطي ترتيب المسار مباشرة.
عندما يكون حجم الرسم \(F_k\)، يمكن وصف المسار بالكامل باستخدام الحساب بترديد \(F_k\). سبب ذلك أن عددين متتاليين من فيبوناتشي متباينان أوليًا، وبالتالي فإن التقدم بخطوة مقدارها \(F_{k-1}\) يعيد ترتيب جميع الفئات الباقية بترديد \(F_k\).
نعرّف
$$G_k=(\{1,2,\dots,F_k\},E),\qquad \{u,v\}\in E \iff u+v\in\{F_j:j\ge 1\}.$$
المسار الهاملتوني هو ترتيب \(a_1,a_2,\dots,a_{F_k}\) يستعمل كل رأس مرة واحدة بالضبط ويحقق
$$a_i+a_{i+1}\in\{F_j:j\ge 1\},\qquad 1\le i \lt F_k.$$
وبما أن الرسم غير موجه، فإن قلب الترتيب يعطي أيضًا مسارًا هاملتونيًا صحيحًا. لهذا تصف التطبيقات المسار أولًا من الطرف الأيمن، ثم تحوّل الموضع المطلوب من العد من اليسار إلى العد من اليمين في النهاية.
لكل \(m\ge 1\)، لتكن \(\rho_m\) هي القيمة الوحيدة التي تحقق
$$\rho_m \equiv mF_{k-1}\pmod{F_k},\qquad 1\le \rho_m \lt F_k.$$
عندئذٍ يكون الترتيب من اليمين إلى اليسار هو
$$a_1=F_k,\qquad a_{2m}=\rho_m,\qquad a_{2m+1}=F_k-\rho_m,$$
لكل \(m\) ما دام الفهرس موجودًا. وإذا كان \(F_k\) زوجيًا فإن السلسلة تنتهي ببساطة عند آخر حد ذي فهرس زوجي؛ أما في الحالة المطلوبة فإن \(F_{83}\) فردي، لذا تأتي جميع الحدود غير النهائية بعد \(a_1\) على شكل أزواج متعاقبة.
وهذا مكافئ تمامًا للصيغة المختصرة التي تستعملها التطبيقات. إذا كان \(r\) هو الموضع المعدود من اليمين و \(m=\lfloor r/2\rfloor\)، نحسب
$$t \equiv mF_{k-1}\pmod{F_k},\qquad 0\le t \lt F_k,$$
ثم نفسر الباقي \(0\) على أنه الرأس \(F_k\). وبعد ذلك تصبح التسمية
$$v(r)=\begin{cases} F_k, & r=1,\\ t, & r\equiv 0 \pmod{2},\\ (F_k-t)\bmod F_k, & r\equiv 1 \pmod{2}. \end{cases}$$
في الوصف الآتي من الطرف الأيمن توجد ثلاثة أنواع من الأزواج المتجاورة.
الحافة الأولى صحيحة لأن
$$a_1+a_2=F_k+\rho_1=F_k+F_{k-1}=F_{k+1}.$$
وكل زوج من حد زوجي يليه حد فردي صحيح أيضًا لأن
$$a_{2m}+a_{2m+1}=\rho_m+(F_k-\rho_m)=F_k.$$
أما الانتقال من زوج إلى الزوج التالي فيعتمد على
$$\rho_{m+1}\equiv \rho_m+F_{k-1}\pmod{F_k}.$$
ومن ثم فإن \(\rho_{m+1}\) يساوي إما \(\rho_m+F_{k-1}\) أو \(\rho_m+F_{k-1}-F_k\). ولذلك
$$a_{2m+1}+a_{2m+2}=(F_k-\rho_m)+\rho_{m+1}\in\{F_{k+1},F_{k-1}\}.$$
أي أن مجموع كل حدين متتاليين لا يخرج عن \(F_{k-1}\) أو \(F_k\) أو \(F_{k+1}\)، وجميعها أعداد فيبوناتشي. وهكذا يكون كل زوج متتالٍ في الترتيب المبني حافة صحيحة في الرسم البياني.
بما أن عددين متتاليين من فيبوناتشي متباينان أوليًا، فإن
$$\gcd(F_{k-1},F_k)=1.$$
إذًا الضرب في \(F_{k-1}\) يعيد ترتيب جميع البواقي غير الصفرية بترديد \(F_k\)، ولهذا تكون القيم \(\rho_m\) كلها مختلفة.
كما أن القيم المكملة \(F_k-\rho_m\) كلها مختلفة أيضًا. ولو حدث تصادم بين العائلتين لوجب أن
$$\rho_m=F_k-\rho_j,$$
ومن ثم
$$(m+j)F_{k-1}\equiv 0\pmod{F_k}.$$
وبما أن \(F_{k-1}\) قابل للعكس بترديد \(F_k\)، فإن هذا يفرض \(m+j\equiv 0\pmod{F_k}\). لكن في المجال الذي نعمل فيه لدينا \(1\le m+j \lt F_k\)، وهذا مستحيل. لذلك تزور البنية كل تسمية مرة واحدة بالضبط، أي أنها مسار هاملتوني فعلاً.
المسألة تعطي الموضع محسوبًا من اليسار، بينما الصيغة المغلقة تُكتب بسهولة أكبر من اليمين. إذا كان طول المسار \(F_k\) وكان الموضع المطلوب من اليسار هو \(L\)، فإن الموضع الموافق من اليمين يساوي
$$r=F_k-L+1.$$
ولأن قلب المسار لا يغيّر خاصية التجاور، فإن تقييم \(v(r)\) يعطينا الفارس المطلوب مباشرة.
في هذا المثال يكون \(F_{k-1}=8\). البواقي المعيارية تحقق
$$\rho_m \equiv 8m\pmod{13}\qquad(m=1,\dots,6),$$
أي أنها
$$8,\ 3,\ 11,\ 6,\ 1,\ 9.$$
ومن ثم يصبح الترتيب من اليمين إلى اليسار
$$13,\ 8,\ 5,\ 3,\ 10,\ 11,\ 2,\ 6,\ 7,\ 1,\ 12,\ 9,\ 4.$$
وبعد قلبه نحصل على الترتيب من اليسار إلى اليمين
$$4,\ 9,\ 12,\ 1,\ 7,\ 6,\ 2,\ 11,\ 10,\ 3,\ 5,\ 8,\ 13.$$
أما المجاميع المتتالية فهي
$$13,\ 21,\ 13,\ 8,\ 13,\ 8,\ 13,\ 21,\ 13,\ 8,\ 13,\ 21,$$
وجميعها من أعداد فيبوناتشي، ولذلك يظهر البناء بوضوح في حالة صغيرة.
تنفذ تطبيقات C++ وPython وJava الخطة الحسابية نفسها. فهي تحسب أولًا أعداد فيبوناتشي حتى الفهرس المطلوب، ثم تأخذ \(n=F_{83}\)، وتحول الموضع المعطى من اليسار \(10^{16}\) إلى \(r=n-10^{16}+1\)، ثم تطبق الصيغة المعيارية السابقة.
وفي الحالة المستهدفة تستعمل القيم
$$F_{82}=61305790721611591,\qquad F_{83}=99194853094755497,\qquad r=89194853094755498.$$
وبضربة معيارية واحدة في \(F_{82}\)، ثم فحص الزوجية، ثم أخذ المتمم بالنسبة إلى \(F_{83}\) عند الحاجة، نحصل على التسمية النهائية
$$56342087360542122.$$
كما تتضمن نسخة C++ اختبارات صغيرة للتأكد: فهي تجد مسارًا هاملتونيًا بالبحث الكامل على رسم ضئيل، ثم تقارن الصيغة المغلقة مع مسار مُستخرج بالبحث الكامل في الحالة الفيبوناتشية \(n=34\). وتستخدم نسخة Java ضربًا بدقة غير محدودة لحماية العملية المعيارية من الفيض، بينما تعتمد Python على الأعداد الصحيحة الكبيرة المدمجة، وتستعمل C++ نوعًا وسيطًا أوسع.
إذا كان الحجم الهدف هو \(F_k\)، فإن توليد أعداد فيبوناتشي حتى الفهرس \(k\) يحتاج إلى زمن \(O(k)\) وذاكرة \(O(k)\). وبعد هذا الإعداد لمرة واحدة، لا يحتاج الجواب الفعلي إلا إلى عملية طرح واحدة، وقسمة صحيحة على \(2\)، وضرب معياري واحد، وفرع بسيط يعتمد على الزوجية. لذلك يعمل الجزء الرئيسي في \(O(1)\) زمنًا مع \(O(1)\) ذاكرة إضافية. أما البحث الكامل فموجود فقط من أجل نقاط تحقق صغيرة جدًا، وليس جزءًا من خوارزمية الحالة الكبيرة.