Let \(P_n\) be the set of ordered pairs of lattice points \((a,b)\) present after \(n\) days, starting from the two initial states \(((1,0),(0,1))\) and \(((0,0),(0,0))\). The quantity asked for in the problem is \(g(n)=|P_n|\), and the implementations evaluate it at \(n=16\).
The naive process expands every state by extracting its first endpoint, second endpoint, and displacement vector, then rebuilding all states compatible with those three projections. That expansion is useful only for tiny \(n\). The real solution compresses one whole day into two scalar counts \(k_d\) and \(q_d\), then evaluates a closed formula in constant time.
For a fixed day \(d\), write
\[ A_d=\{a:(a,b)\in P_d\},\qquad B_d=\{b:(a,b)\in P_d\},\qquad C_d=\{b-a:(a,b)\in P_d\}. \]
These are the left endpoints, right endpoints, and displacement vectors visible on day \(d\). The next day is built from exactly the three constructions used in the implementations.
If we denote the three day-\(d\) production rules by
\[ X_d=A_d\times B_d,\qquad Y_d=\{(b-c,b):b\in B_d,\ c\in C_d\},\qquad Z_d=\{(a,a+c):a\in A_d,\ c\in C_d\}, \]
then
\[ P_{d+1}=X_d\cup Y_d\cup Z_d. \]
Projecting this identity onto first coordinates, second coordinates, and differences gives three exact recurrences:
\[ A_{d+1}=B_d-C_d,\qquad B_{d+1}=A_d+C_d,\qquad C_{d+1}=B_d-A_d. \]
So the process is governed by three sets on the triangular lattice, not by an arbitrary cloud of pairs.
The three projection sets are congruent by the symmetries of the update rule, so they always have the same size. Define
\[ k_d = |A_d| = |B_d| = |C_d|. \]
Each of \(X_d\), \(Y_d\), and \(Z_d\) therefore has size \(k_d^2\). The only remaining issue is overlap. A pair \((a,b)\) belongs to \(X_d\cap Y_d\) exactly when \(a\in A_d\), \(b\in B_d\), and \(b-a\in C_d\). But that same condition is also exactly what places \((a,b)\) in \(Z_d\). Hence all pairwise intersections and the triple intersection coincide. If we define
\[ q_d = \#\{(a,b): a\in A_d,\ b\in B_d,\ b-a\in C_d\}, \]
then inclusion-exclusion collapses to
\[ |P_{d+1}| = 3k_d^2 - 2q_d. \]
This is the origin of the formula used by all three implementations:
\[ g(0)=2,\qquad g(n)=3k_{n-1}^2-2q_{n-1}\quad (n\ge 1). \]
Once the recurrences for \(A_d,B_d,C_d\) are written out for a few small days, a rigid geometric pattern appears: each set is a lattice hexagon bounded by three strip constraints in the directions \(x\), \(y\), and \(x+y\). The three sets are the same hexagon seen under a \(120^\circ\) cyclic relabeling of those directions.
A convenient parameter is \(t\), which alternates with the day parity:
\[ t= \begin{cases} \dfrac{2^d-1}{3}, & d\ \text{even},\\[6pt] \dfrac{2^d-2}{3}, & d\ \text{odd}. \end{cases} \]
For example, on an even day the set \(A_d\) can be written as
\[ A_d=\{(x,y)\in\mathbb Z^2:\ -t\le x\le t+1,\ -t\le y\le t,\ -t\le x+y\le t+1\}, \]
and the other two sets are the same shape after cyclically shifting the three directions. On an odd day, the same description holds with the side-length triple changing from \((t,t,t+1)\) to \((t,t+1,t+1)\).
For a lattice hexagon with side-length triple \((u,v,w)\), the number of lattice points is
\[ uv+vw+wu+u+v+w+1. \]
Substituting \((u,v,w)=(t,t,t+1)\) or \((t,t+1,t+1)\) gives
\[ k_d= \begin{cases} 3t^2+5t+2, & d\ \text{even},\\[4pt] 3t^2+7t+4, & d\ \text{odd}. \end{cases} \]
The overlap term is a compatibility count between the three lattice hexagons. Fix \(c\in C_d\). Every valid pair \((a,b)\) with \(b-a=c\) is obtained by choosing \(a\in A_d\cap(B_d-c)\). Therefore
\[ q_d = \sum_{c\in C_d} |A_d\cap (B_d-c)|. \]
Because \(A_d\), \(B_d\), and \(C_d\) are aligned hexagons, each intersection \(A_d\cap(B_d-c)\) is again a smaller aligned hexagon or a boundary-degenerate version of one. Grouping the displacements \(c\) by their position in the hexagon turns the sum into quadratic row profiles, and summing those profiles yields the quartic closed forms
\[ q_d= \begin{cases} \dfrac{21t^4+70t^3+87t^2+46t+8}{4}, & d\ \text{even},\\[8pt] \dfrac{21t^4+98t^3+171t^2+134t+40}{4}, & d\ \text{odd}. \end{cases} \]
At that point the problem is finished: evaluate \(k_{n-1}\) and \(q_{n-1}\), then substitute them into \(g(n)=3k_{n-1}^2-2q_{n-1}\).
After one day, the projection sets are
\[ A_1=\{(0,0),(0,1),(1,-1),(1,0)\}, \]
\[ B_1=\{(-1,1),(0,0),(0,1),(1,0)\}, \]
\[ C_1=\{(-1,0),(-1,1),(0,0),(0,1)\}. \]
So \(k_1=4\), and each production rule contributes \(4^2=16\) candidate pairs. The overlap term is
\[ q_1 = \sum_{c\in C_1} |A_1\cap(B_1-c)| = 2+3+3+2 = 10. \]
Therefore
\[ g(2)=|P_2| = 3\cdot 4^2 - 2\cdot 10 = 28, \]
which matches the small-value checks in the implementations. The same inclusion-exclusion mechanism is what drives the large-day formula.
The C++, Python, and Java implementations all use the same mathematics, but only the C++ version keeps a literal day-by-day set expansion for validation. It stores the current set \(P_d\), extracts \(A_d\), \(B_d\), and \(C_d\), applies the three production rules, and confirms that the closed formula reproduces the exact counts for the first few days.
The production path never materializes the lattice hexagons. It computes the day parameter \(d=n-1\), converts that to the parity-dependent value of \(t\), evaluates the polynomial formulas for \(k_d\) and \(q_d\), and finally returns \(3k_d^2-2q_d\). The C++ implementation uses 128-bit integers because the intermediate quartic expressions are already much larger than 64-bit signed limits; the Java version uses arbitrary-precision integers; Python gets exact big integers automatically.
All three implementations keep the easy base case \(g(0)=2\), and the C++ and Python implementations also verify small known values such as \(g(1)=8\) and \(g(2)=28\).
The closed-form solver is \(O(1)\) time and \(O(1)\) memory: it evaluates a handful of powers, products, and additions on fixed-size formulas. The only reason the language implementations differ is numeric representation, not algorithmic structure.
The validation model is exponentially and then combinatorially explosive because it explicitly stores whole state sets \(P_d\). That version is intentionally confined to very small \(d\); it exists only to confirm the geometry and the inclusion-exclusion formula before the constant-time evaluator is used for the actual target \(n=16\).
Sei \(P_n\) die Menge aller geordneten Paare von Gitterpunkten \((a,b)\), die nach \(n\) Tagen vorhanden sind, ausgehend von den beiden Startzuständen \(((1,0),(0,1))\) und \(((0,0),(0,0))\). Gesucht ist \(g(n)=|P_n|\), und die Implementierungen werten diese Größe für \(n=16\) aus.
Die naive Dynamik erweitert jeden Zustand, indem sie ersten Endpunkt, zweiten Endpunkt und Verschiebungsvektor extrahiert und daraus alle mit diesen drei Projektionen verträglichen neuen Zustände erzeugt. Das funktioniert nur für sehr kleine \(n\). Die eigentliche Lösung komprimiert einen ganzen Tag auf zwei skalare Größen \(k_d\) und \(q_d\) und berechnet danach eine geschlossene Formel in konstanter Zeit.
Für einen festen Tag \(d\) definieren wir
\[ A_d=\{a:(a,b)\in P_d\},\qquad B_d=\{b:(a,b)\in P_d\},\qquad C_d=\{b-a:(a,b)\in P_d\}. \]
Das sind die linken Endpunkte, die rechten Endpunkte und die Verschiebungsvektoren, die an Tag \(d\) sichtbar sind. Der nächste Tag entsteht genau aus den drei Konstruktionen der Implementierungen.
Bezeichnen wir die drei Produktionsregeln von Tag \(d\) mit
\[ X_d=A_d\times B_d,\qquad Y_d=\{(b-c,b):b\in B_d,\ c\in C_d\},\qquad Z_d=\{(a,a+c):a\in A_d,\ c\in C_d\}, \]
so gilt
\[ P_{d+1}=X_d\cup Y_d\cup Z_d. \]
Projiziert man diese Identität auf erste Koordinaten, zweite Koordinaten und Differenzen, erhält man drei exakte Rekurrenzen:
\[ A_{d+1}=B_d-C_d,\qquad B_{d+1}=A_d+C_d,\qquad C_{d+1}=B_d-A_d. \]
Damit wird klar: Die Dynamik wird nicht von einer beliebigen Zustandswolke bestimmt, sondern von drei Mengen auf dem Dreiecksgitter.
Wegen der Symmetrien der Update-Regel sind die drei Projektionsmengen kongruent und haben daher immer dieselbe Größe. Wir setzen
\[ k_d = |A_d| = |B_d| = |C_d|. \]
Jede der drei Produktionsmengen \(X_d\), \(Y_d\) und \(Z_d\) hat also Größe \(k_d^2\). Übrig bleibt nur die Überlappung. Ein Paar \((a,b)\) liegt genau dann in \(X_d\cap Y_d\), wenn \(a\in A_d\), \(b\in B_d\) und zugleich \(b-a\in C_d\) gilt. Genau dieselbe Bedingung charakterisiert auch die Zugehörigkeit zu \(Z_d\). Daher stimmen alle paarweisen Schnitte und der Dreifachschnitt überein. Definiert man
\[ q_d = \#\{(a,b): a\in A_d,\ b\in B_d,\ b-a\in C_d\}, \]
dann vereinfacht sich Inklusion-Exklusion zu
\[ |P_{d+1}| = 3k_d^2 - 2q_d. \]
Genau daraus stammt die Formel aller drei Implementierungen:
\[ g(0)=2,\qquad g(n)=3k_{n-1}^2-2q_{n-1}\quad (n\ge 1). \]
Schreibt man die Rekurrenzen für \(A_d\), \(B_d\) und \(C_d\) für einige kleine Tage aus, erscheint ein starres geometrisches Muster: Jede dieser Mengen ist ein Gitterhexagon, das durch drei Streifenbedingungen in den Richtungen \(x\), \(y\) und \(x+y\) beschrieben wird. Die drei Mengen sind dieselbe Figur unter einer zyklischen Umbenennung dieser drei Richtungen um \(120^\circ\).
Ein bequemer Parameter ist \(t\), der von der Parität des Tages abhängt:
\[ t= \begin{cases} \dfrac{2^d-1}{3}, & d\ \text{gerade},\\[6pt] \dfrac{2^d-2}{3}, & d\ \text{ungerade}. \end{cases} \]
Beispielsweise kann \(A_d\) an einem geraden Tag als
\[ A_d=\{(x,y)\in\mathbb Z^2:\ -t\le x\le t+1,\ -t\le y\le t,\ -t\le x+y\le t+1\} \]
geschrieben werden; die beiden anderen Mengen haben dieselbe Form nach zyklischem Vertauschen der drei Richtungen. An ungeraden Tagen bleibt die Beschreibung gleichartig, aber das Seitenlängentripel wechselt von \((t,t,t+1)\) zu \((t,t+1,t+1)\).
Für ein Gitterhexagon mit Seitenlängentripel \((u,v,w)\) ist die Anzahl der Gitterpunkte
\[ uv+vw+wu+u+v+w+1. \]
Setzt man \((u,v,w)=(t,t,t+1)\) oder \((t,t+1,t+1)\) ein, erhält man
\[ k_d= \begin{cases} 3t^2+5t+2, & d\ \text{gerade},\\[4pt] 3t^2+7t+4, & d\ \text{ungerade}. \end{cases} \]
Der Term \(q_d\) ist eine Verträglichkeitszählung zwischen den drei Gitterhexagonen. Fixiere \(c\in C_d\). Jedes zulässige Paar \((a,b)\) mit \(b-a=c\) entsteht genau durch die Wahl eines Punktes \(a\in A_d\cap(B_d-c)\). Daher
\[ q_d = \sum_{c\in C_d} |A_d\cap (B_d-c)|. \]
Weil \(A_d\), \(B_d\) und \(C_d\) ausgerichtete Hexagone sind, ist jeder Schnitt \(A_d\cap(B_d-c)\) wieder ein kleineres ausgerichtetes Hexagon oder ein Randentartungsfall davon. Gruppiert man die Verschiebungen \(c\) nach ihrer Lage im Hexagon, zerfällt die Summe in quadratische Zeilenprofile; deren Summation liefert die geschlossenen quartischen Formeln
\[ q_d= \begin{cases} \dfrac{21t^4+70t^3+87t^2+46t+8}{4}, & d\ \text{gerade},\\[8pt] \dfrac{21t^4+98t^3+171t^2+134t+40}{4}, & d\ \text{ungerade}. \end{cases} \]
Danach ist die Aufgabe erledigt: Man berechnet \(k_{n-1}\) und \(q_{n-1}\) und setzt sie in \(g(n)=3k_{n-1}^2-2q_{n-1}\) ein.
Nach einem Tag lauten die Projektionsmengen
\[ A_1=\{(0,0),(0,1),(1,-1),(1,0)\}, \]
\[ B_1=\{(-1,1),(0,0),(0,1),(1,0)\}, \]
\[ C_1=\{(-1,0),(-1,1),(0,0),(0,1)\}. \]
Also ist \(k_1=4\), und jede Produktionsregel liefert \(4^2=16\) Kandidatenpaare. Der Überlappungsterm ist
\[ q_1 = \sum_{c\in C_1} |A_1\cap(B_1-c)| = 2+3+3+2 = 10. \]
Damit folgt
\[ g(2)=|P_2| = 3\cdot 4^2 - 2\cdot 10 = 28, \]
genau wie in den Kleintests der Implementierungen. Derselbe Inklusion-Exklusion-Mechanismus erzeugt auch die Formel für große Tage.
Die Implementierungen in C++, Python und Java verwenden dieselbe Mathematik, aber nur die C++-Version behält zur Validierung eine explizite Tag-für-Tag-Erweiterung der Zustandsmenge bei. Sie speichert das aktuelle \(P_d\), extrahiert daraus \(A_d\), \(B_d\) und \(C_d\), wendet die drei Produktionsregeln an und bestätigt damit, dass die geschlossene Formel die exakten Werte der ersten Tage reproduziert.
Der Produktionspfad materialisiert die Gitterhexagone nie explizit. Er berechnet den Tagesparameter \(d=n-1\), bestimmt daraus den paritätsabhängigen Wert \(t\), wertet die Polynomformeln für \(k_d\) und \(q_d\) aus und gibt schließlich \(3k_d^2-2q_d\) zurück. Die C++-Implementierung benutzt 128-Bit-Ganzzahlen, weil die quartischen Zwischenterme bereits deutlich über die Grenzen vorzeichenbehafteter 64-Bit-Werte hinausgehen; die Java-Version verwendet beliebig große Ganzzahlen; Python bekommt exakte Big Integers automatisch.
Alle drei Implementierungen behandeln den einfachen Basisfall \(g(0)=2\), und die C++- und Python-Versionen überprüfen zusätzlich kleine bekannte Werte wie \(g(1)=8\) und \(g(2)=28\).
Der geschlossene Löser benötigt \(O(1)\) Zeit und \(O(1)\) Speicher: Er wertet nur eine feste Anzahl von Potenzen, Produkten und Summen aus. Die Unterschiede zwischen den Sprachversionen betreffen daher nur die Zahlenrepräsentation, nicht die Algorithmik.
Das Validierungsmodell wächst erst exponentiell und dann kombinatorisch, weil es die vollständigen Zustandsmengen \(P_d\) explizit speichert. Deshalb wird diese Variante absichtlich nur für sehr kleine \(d\) verwendet; ihr Zweck ist ausschließlich, die Geometrie und die Inklusion-Exklusion-Formel zu bestätigen, bevor für das eigentliche Ziel \(n=16\) die konstante Formel zum Einsatz kommt.
\(P_n\), \(n\) gün sonunda elde bulunan sıralı kafes noktası çiftlerinin \((a,b)\) kümesi olsun; başlangıç durumları \(((1,0),(0,1))\) ve \(((0,0),(0,0))\) olarak verilir. Problemde istenen büyüklük \(g(n)=|P_n|\)'dir ve uygulamalar bunu \(n=16\) için hesaplar.
Naif süreç, her durumu ilk uç nokta, ikinci uç nokta ve yer değiştirme vektörü olarak ayırıp sonra bu üç izdüşümle uyumlu bütün yeni durumları üretir. Bu yaklaşım sadece çok küçük \(n\) değerlerinde işe yarar. Gerçek çözüm, bir tam günü iki skaler büyüklüğe \(k_d\) ve \(q_d\) indirger, ardından kapalı formülü sabit zamanda değerlendirir.
Sabit bir \(d\) günü için
\[ A_d=\{a:(a,b)\in P_d\},\qquad B_d=\{b:(a,b)\in P_d\},\qquad C_d=\{b-a:(a,b)\in P_d\} \]
tanımlarını yapalım. Bunlar, \(d\). günde görülen sol uç noktalar, sağ uç noktalar ve fark vektörleridir. Bir sonraki gün tam olarak uygulamalardaki üç yapıdan oluşur.
\(d\). gündeki üç üretim kuralını
\[ X_d=A_d\times B_d,\qquad Y_d=\{(b-c,b):b\in B_d,\ c\in C_d\},\qquad Z_d=\{(a,a+c):a\in A_d,\ c\in C_d\} \]
şeklinde yazarsak
\[ P_{d+1}=X_d\cup Y_d\cup Z_d \]
olur. Bu özdeşliği birinci koordinata, ikinci koordinata ve farklara izdüşürdüğümüzde üç tam yineleme elde edilir:
\[ A_{d+1}=B_d-C_d,\qquad B_{d+1}=A_d+C_d,\qquad C_{d+1}=B_d-A_d. \]
Yani süreç rastgele bir durum bulutu tarafından değil, üçgensel kafes üzerindeki üç küme tarafından yönetilir.
Güncelleme kuralının simetrileri nedeniyle bu üç izdüşüm kümesi eş şekillidir ve her zaman aynı sayıda eleman taşır. Dolayısıyla
\[ k_d = |A_d| = |B_d| = |C_d| \]
olarak tanımlarız. O zaman \(X_d\), \(Y_d\) ve \(Z_d\) kümelerinin her biri \(k_d^2\) elemanlıdır. Kalan tek mesele örtüşmedir. Bir \((a,b)\) çifti tam olarak \(a\in A_d\), \(b\in B_d\) ve \(b-a\in C_d\) koşulları sağlandığında \(X_d\cap Y_d\) içine düşer. Aynı koşul \((a,b)\)'yi \(Z_d\)'ye de sokar. Demek ki bütün ikili kesişimler ve üçlü kesişim aynıdır. Şimdi
\[ q_d = \#\{(a,b): a\in A_d,\ b\in B_d,\ b-a\in C_d\} \]
dersek, dahil etme-dışlama doğrudan
\[ |P_{d+1}| = 3k_d^2 - 2q_d \]
şeklinde sadeleşir. Üç uygulamanın da kullandığı formül tam olarak buradan gelir:
\[ g(0)=2,\qquad g(n)=3k_{n-1}^2-2q_{n-1}\quad (n\ge 1). \]
\(A_d\), \(B_d\) ve \(C_d\) için yinelemeler birkaç küçük gün boyunca açıkça yazıldığında sert bir geometrik desen ortaya çıkar: her küme, \(x\), \(y\) ve \(x+y\) doğrultularındaki üç şerit koşuluyla tanımlanan bir kafes altıgenidir. Bu üç küme, yalnızca yönlerin \(120^\circ\)'lik döngüsel yeniden etiketlenmesiyle birbirine dönüşen aynı şekildir.
Uygun parametre \(t\) olup günün paritesine göre değişir:
\[ t= \begin{cases} \dfrac{2^d-1}{3}, & d\ \text{çift},\\[6pt] \dfrac{2^d-2}{3}, & d\ \text{tek}. \end{cases} \]
Örneğin çift bir günde \(A_d\) kümesi
\[ A_d=\{(x,y)\in\mathbb Z^2:\ -t\le x\le t+1,\ -t\le y\le t,\ -t\le x+y\le t+1\} \]
şeklinde yazılabilir; diğer iki küme de bu üç yönü döngüsel kaydırınca elde edilen aynı şekildir. Tek günlerde açıklama aynı kalır, fakat kenar uzunluğu üçlüsü \((t,t,t+1)\)'den \((t,t+1,t+1)\)'e döner.
Kenar uzunluğu üçlüsü \((u,v,w)\) olan böyle bir kafes altıgeninin nokta sayısı
\[ uv+vw+wu+u+v+w+1 \]
olur. \((u,v,w)=(t,t,t+1)\) veya \((t,t+1,t+1)\) yerine koyunca
\[ k_d= \begin{cases} 3t^2+5t+2, & d\ \text{çift},\\[4pt] 3t^2+7t+4, & d\ \text{tek} \end{cases} \]
elde edilir.
\(q_d\) terimi, bu üç kafes altıgeni arasındaki uyumluluk sayımıdır. Sabit bir \(c\in C_d\) seçelim. \(b-a=c\) koşulunu sağlayan her geçerli \((a,b)\) çifti, tam olarak \(a\in A_d\cap(B_d-c)\) seçimine karşılık gelir. Bu nedenle
\[ q_d = \sum_{c\in C_d} |A_d\cap (B_d-c)|. \]
\(A_d\), \(B_d\) ve \(C_d\) hizalı altıgenler olduğundan, her \(A_d\cap(B_d-c)\) kesişimi yine daha küçük bir hizalı altıgen veya onun sınırda bozulmuş bir sürümüdür. \(c\) vektörlerini altıgen içindeki konumlarına göre gruplayınca toplam, satır satır kuadratik profillere ayrılır; bu profiller toplanınca kapalı dördüncü derece formüller çıkar:
\[ q_d= \begin{cases} \dfrac{21t^4+70t^3+87t^2+46t+8}{4}, & d\ \text{çift},\\[8pt] \dfrac{21t^4+98t^3+171t^2+134t+40}{4}, & d\ \text{tek}. \end{cases} \]
Bundan sonra problem biter: \(k_{n-1}\) ve \(q_{n-1}\) hesaplanır, sonra \(g(n)=3k_{n-1}^2-2q_{n-1}\) içine yerleştirilir.
Bir günün sonunda izdüşüm kümeleri
\[ A_1=\{(0,0),(0,1),(1,-1),(1,0)\}, \]
\[ B_1=\{(-1,1),(0,0),(0,1),(1,0)\}, \]
\[ C_1=\{(-1,0),(-1,1),(0,0),(0,1)\} \]
olur. Dolayısıyla \(k_1=4\)'tür ve her üretim kuralı \(4^2=16\) aday çift üretir. Örtüşme terimi ise
\[ q_1 = \sum_{c\in C_1} |A_1\cap(B_1-c)| = 2+3+3+2 = 10 \]
şeklindedir. Sonuç olarak
\[ g(2)=|P_2| = 3\cdot 4^2 - 2\cdot 10 = 28 \]
elde edilir; bu da uygulamalardaki küçük değer kontrolleriyle tam uyumludur. Büyük gün formülünü de aynı dahil etme-dışlama mekanizması üretir.
C++, Python ve Java uygulamaları aynı matematiği kullanır; fakat yalnızca C++ sürümü doğrulama amacıyla açık bir gün-gün küme genişletmesi tutar. Bu sürüm, mevcut \(P_d\) kümesini saklar, ondan \(A_d\), \(B_d\) ve \(C_d\)'yi çıkarır, üç üretim kuralını uygular ve kapalı formülün ilk birkaç gün için tam sayımla uyuştuğunu doğrular.
Asıl çözüm yolu kafes altıgenlerini hiç açıkça üretmez. Önce gün parametresi \(d=n-1\) hesaplanır, buradan pariteye bağlı \(t\) bulunur, sonra \(k_d\) ve \(q_d\) için polinom formülleri değerlendirilir ve son olarak \(3k_d^2-2q_d\) döndürülür. C++ sürümü, dördüncü derece ara ifadeler 64 bit işaretli sınırı rahatlıkla aştığı için 128 bit tamsayı kullanır; Java sürümü keyfi hassasiyetli tamsayılarla çalışır; Python ise büyük tamsayıları doğal olarak tam doğrulukla işler.
Üç uygulamanın tamamı kolay taban durumunu \(g(0)=2\) olarak işler; ayrıca C++ ve Python sürümleri \(g(1)=8\) ve \(g(2)=28\) gibi küçük bilinen değerleri de kontrol eder.
Kapalı form çözümü \(O(1)\) zaman ve \(O(1)\) bellek kullanır: yalnızca sabit sayıda üs alma, çarpma ve toplama yapar. Bu yüzden diller arasındaki fark algoritmadan değil, kullanılan sayı temsilinden kaynaklanır.
Doğrulama modeli ise tüm \(P_d\) kümelerini açıkça sakladığı için önce üstel, sonra kombinatorik biçimde patlar. Bu sürüm özellikle çok küçük \(d\) değerleriyle sınırlandırılmıştır; amacı yalnızca geometriyi ve dahil etme-dışlama formülünü doğrulamaktır. Gerçek hedef olan \(n=16\) için kullanılan yol sabit zamanlı kapalı formüldür.
Sea \(P_n\) el conjunto de pares ordenados de puntos de la red \((a,b)\) presentes después de \(n\) días, partiendo de los dos estados iniciales \(((1,0),(0,1))\) y \(((0,0),(0,0))\). La cantidad pedida por el problema es \(g(n)=|P_n|\), y las implementaciones la evalúan en \(n=16\).
El proceso ingenuo expande cada estado extrayendo su primer extremo, su segundo extremo y su vector desplazamiento, y luego reconstruye todos los estados compatibles con esas tres proyecciones. Eso solo sirve para valores muy pequeños de \(n\). La solución real comprime un día completo en dos cantidades escalares \(k_d\) y \(q_d\), y después evalúa una fórmula cerrada en tiempo constante.
Para un día fijo \(d\), escribimos
\[ A_d=\{a:(a,b)\in P_d\},\qquad B_d=\{b:(a,b)\in P_d\},\qquad C_d=\{b-a:(a,b)\in P_d\}. \]
Estos son los extremos izquierdos, los extremos derechos y los vectores de desplazamiento visibles en el día \(d\). El día siguiente se construye exactamente con las tres operaciones que aparecen en las implementaciones.
Si llamamos
\[ X_d=A_d\times B_d,\qquad Y_d=\{(b-c,b):b\in B_d,\ c\in C_d\},\qquad Z_d=\{(a,a+c):a\in A_d,\ c\in C_d\} \]
a las tres reglas de producción del día \(d\), entonces
\[ P_{d+1}=X_d\cup Y_d\cup Z_d. \]
Al proyectar esta identidad sobre la primera coordenada, la segunda coordenada y las diferencias, aparecen tres recurrencias exactas:
\[ A_{d+1}=B_d-C_d,\qquad B_{d+1}=A_d+C_d,\qquad C_{d+1}=B_d-A_d. \]
Así, la dinámica está gobernada por tres conjuntos sobre la red triangular, no por una nube arbitraria de pares.
Las simetrías de la regla de actualización hacen que los tres conjuntos proyectados sean congruentes, y por eso siempre tengan el mismo tamaño. Definimos
\[ k_d = |A_d| = |B_d| = |C_d|. \]
Cada uno de \(X_d\), \(Y_d\) y \(Z_d\) tiene entonces tamaño \(k_d^2\). El único problema que queda es el solapamiento. Un par \((a,b)\) pertenece a \(X_d\cap Y_d\) exactamente cuando \(a\in A_d\), \(b\in B_d\) y además \(b-a\in C_d\). Pero esa misma condición es también la que lo coloca en \(Z_d\). Por lo tanto, todas las intersecciones por parejas y la intersección triple coinciden. Si definimos
\[ q_d = \#\{(a,b): a\in A_d,\ b\in B_d,\ b-a\in C_d\}, \]
entonces inclusión-exclusión se reduce a
\[ |P_{d+1}| = 3k_d^2 - 2q_d. \]
Ese es el origen de la fórmula que usan las tres implementaciones:
\[ g(0)=2,\qquad g(n)=3k_{n-1}^2-2q_{n-1}\quad (n\ge 1). \]
Si se desarrollan las recurrencias de \(A_d\), \(B_d\) y \(C_d\) durante unos pocos días, aparece un patrón geométrico rígido: cada conjunto es un hexágono de puntos de red acotado por tres familias de rectas en las direcciones \(x\), \(y\) y \(x+y\). Los tres conjuntos son la misma figura vista tras una relabelización cíclica de \(120^\circ\) entre esas direcciones.
Un parámetro cómodo es \(t\), que depende de la paridad del día:
\[ t= \begin{cases} \dfrac{2^d-1}{3}, & d\ \text{par},\\[6pt] \dfrac{2^d-2}{3}, & d\ \text{impar}. \end{cases} \]
Por ejemplo, en un día par el conjunto \(A_d\) puede escribirse como
\[ A_d=\{(x,y)\in\mathbb Z^2:\ -t\le x\le t+1,\ -t\le y\le t,\ -t\le x+y\le t+1\}. \]
Los otros dos conjuntos tienen la misma forma tras desplazar cíclicamente las tres direcciones. En un día impar se mantiene la misma descripción geométrica, pero el triple de longitudes laterales pasa de \((t,t,t+1)\) a \((t,t+1,t+1)\).
Para un hexágono de red con triple de lados \((u,v,w)\), el número de puntos de red es
\[ uv+vw+wu+u+v+w+1. \]
Al sustituir \((u,v,w)=(t,t,t+1)\) o \((t,t+1,t+1)\), obtenemos
\[ k_d= \begin{cases} 3t^2+5t+2, & d\ \text{par},\\[4pt] 3t^2+7t+4, & d\ \text{impar}. \end{cases} \]
El término \(q_d\) es un conteo de compatibilidad entre los tres hexágonos de la red. Fijemos \(c\in C_d\). Todo par válido \((a,b)\) con \(b-a=c\) se obtiene eligiendo \(a\in A_d\cap(B_d-c)\). Por tanto,
\[ q_d = \sum_{c\in C_d} |A_d\cap (B_d-c)|. \]
Como \(A_d\), \(B_d\) y \(C_d\) son hexágonos alineados, cada intersección \(A_d\cap(B_d-c)\) vuelve a ser un hexágono alineado más pequeño o una versión degenerada sobre la frontera. Si agrupamos los desplazamientos \(c\) según su posición dentro del hexágono, la suma se convierte en perfiles cuadráticos por filas, y al sumarlos aparecen las fórmulas cerradas de grado cuatro
\[ q_d= \begin{cases} \dfrac{21t^4+70t^3+87t^2+46t+8}{4}, & d\ \text{par},\\[8pt] \dfrac{21t^4+98t^3+171t^2+134t+40}{4}, & d\ \text{impar}. \end{cases} \]
En ese punto el problema está resuelto: se calculan \(k_{n-1}\) y \(q_{n-1}\), y luego se sustituyen en \(g(n)=3k_{n-1}^2-2q_{n-1}\).
Después de un día, los conjuntos proyectados son
\[ A_1=\{(0,0),(0,1),(1,-1),(1,0)\}, \]
\[ B_1=\{(-1,1),(0,0),(0,1),(1,0)\}, \]
\[ C_1=\{(-1,0),(-1,1),(0,0),(0,1)\}. \]
Así que \(k_1=4\), y cada regla de producción aporta \(4^2=16\) pares candidatos. El término de solapamiento vale
\[ q_1 = \sum_{c\in C_1} |A_1\cap(B_1-c)| = 2+3+3+2 = 10. \]
Por lo tanto
\[ g(2)=|P_2| = 3\cdot 4^2 - 2\cdot 10 = 28, \]
exactamente como en las comprobaciones pequeñas de las implementaciones. El mismo mecanismo de inclusión-exclusión es el que produce la fórmula para días grandes.
Las implementaciones en C++, Python y Java usan la misma matemática, pero solo la versión en C++ conserva una expansión literal día a día para validar. Guarda el conjunto actual \(P_d\), extrae \(A_d\), \(B_d\) y \(C_d\), aplica las tres reglas de producción y confirma que la fórmula cerrada reproduce los conteos exactos de los primeros días.
La ruta de producción nunca materializa los hexágonos de la red. Calcula el parámetro de día \(d=n-1\), lo convierte en el valor \(t\) dependiente de la paridad, evalúa las fórmulas polinómicas de \(k_d\) y \(q_d\), y finalmente devuelve \(3k_d^2-2q_d\). La implementación en C++ usa enteros de 128 bits porque las expresiones cuárticas intermedias superan con comodidad el rango con signo de 64 bits; la versión en Java usa enteros de precisión arbitraria; Python obtiene enteros exactos grandes de manera automática.
Las tres implementaciones mantienen el caso base \(g(0)=2\), y las versiones en C++ y Python además verifican valores pequeños conocidos como \(g(1)=8\) y \(g(2)=28\).
El solucionador en forma cerrada es \(O(1)\) en tiempo y \(O(1)\) en memoria: solo evalúa una cantidad fija de potencias, productos y sumas. Por eso, las diferencias entre lenguajes se deben únicamente a la representación numérica y no a la estructura algorítmica.
El modelo de validación crece primero de forma exponencial y luego combinatoria porque almacena explícitamente los conjuntos completos \(P_d\). Esa variante está confinada de forma intencionada a valores muy pequeños de \(d\); su función es únicamente confirmar la geometría y la identidad de inclusión-exclusión antes de usar el evaluador en tiempo constante para el objetivo real \(n=16\).
记 \(P_n\) 为第 \(n\) 天后出现的所有有序格点对 \((a,b)\) 的集合，初始状态只有 \(((1,0),(0,1))\) 与 \(((0,0),(0,0))\) 这两个。题目要求的是 \(g(n)=|P_n|\)，而三份实现最终都把它算到 \(n=16\)。
如果直接按定义推进，每个状态都要拆成“左端点、右端点、位移向量”三部分，再用这三类投影去生成下一天所有兼容的状态。这样的暴力扩张只能用于很小的 \(n\)。真正的解法把一天的全部信息压缩成两个标量 \(k_d\) 与 \(q_d\)，随后用闭式在常数时间内得到答案。
对固定的第 \(d\) 天，定义
\[ A_d=\{a:(a,b)\in P_d\},\qquad B_d=\{b:(a,b)\in P_d\},\qquad C_d=\{b-a:(a,b)\in P_d\}. \]
这三个集合分别记录第 \(d\) 天所有状态里出现过的左端点、右端点和差向量。下一天的状态，正是由实现中出现的三种构造拼出来的。
把第 \(d\) 天的三条生成规则记为
\[ X_d=A_d\times B_d,\qquad Y_d=\{(b-c,b):b\in B_d,\ c\in C_d\},\qquad Z_d=\{(a,a+c):a\in A_d,\ c\in C_d\}, \]
那么就有
\[ P_{d+1}=X_d\cup Y_d\cup Z_d. \]
把这个恒等式分别投影到第一坐标、第二坐标以及差向量上，会得到三个完全精确的递推式：
\[ A_{d+1}=B_d-C_d,\qquad B_{d+1}=A_d+C_d,\qquad C_{d+1}=B_d-A_d. \]
这一步很重要，因为它说明整个过程并不是在一个无结构的状态云里乱长，而是在三角晶格上的三个集合之间做确定的几何演化。
由更新规则的对称性可知，\(A_d\)、\(B_d\)、\(C_d\) 三个投影集合始终全等，因此它们的大小总是相同。记
\[ k_d = |A_d| = |B_d| = |C_d|. \]
于是 \(X_d\)、\(Y_d\)、\(Z_d\) 三个生成集合的大小都等于 \(k_d^2\)。剩下唯一需要处理的就是它们之间的重叠。一个点对 \((a,b)\) 属于 \(X_d\cap Y_d\)，当且仅当 \(a\in A_d\)、\(b\in B_d\)，并且 \(b-a\in C_d\)。但这恰好也是它属于 \(Z_d\) 的条件。因此，三种两两交集与三重交集其实是同一个集合。定义
\[ q_d = \#\{(a,b): a\in A_d,\ b\in B_d,\ b-a\in C_d\}, \]
则容斥原理立刻化简为
\[ |P_{d+1}| = 3k_d^2 - 2q_d. \]
这就是三份实现最终都在用的核心公式：
\[ g(0)=2,\qquad g(n)=3k_{n-1}^2-2q_{n-1}\quad (n\ge 1). \]
把 \(A_d\)、\(B_d\)、\(C_d\) 的递推展开几天之后，会看到一个非常稳定的几何图像：每个集合都是由三组平行边界围成的晶格六边形，边界方向对应 \(x\)、\(y\) 和 \(x+y\)。三个集合本质上是同一个六边形，只是这三个方向做了 \(120^\circ\) 的循环重命名。
方便的参数是 \(t\)，它随天数奇偶而变化：
\[ t= \begin{cases} \dfrac{2^d-1}{3}, & d\ \text{为偶数},\\[6pt] \dfrac{2^d-2}{3}, & d\ \text{为奇数}. \end{cases} \]
例如，在偶数日里，\(A_d\) 可以写成
\[ A_d=\{(x,y)\in\mathbb Z^2:\ -t\le x\le t+1,\ -t\le y\le t,\ -t\le x+y\le t+1\}. \]
另外两个集合只是在这三条方向上做循环置换后的同形区域。到了奇数日，几何描述保持不变，但六边形的三参数边长会从 \((t,t,t+1)\) 变成 \((t,t+1,t+1)\)。
如果一个晶格六边形的三参数边长是 \((u,v,w)\)，那么其中的晶格点数为
\[ uv+vw+wu+u+v+w+1. \]
代入 \((u,v,w)=(t,t,t+1)\) 或 \((t,t+1,t+1)\)，就得到
\[ k_d= \begin{cases} 3t^2+5t+2, & d\ \text{为偶数},\\[4pt] 3t^2+7t+4, & d\ \text{为奇数}. \end{cases} \]
\(q_d\) 并不是额外凭空出现的神秘量，它就是这三个晶格六边形之间的兼容性计数。固定一个 \(c\in C_d\)。只要满足 \(b-a=c\)，那么所有合法的 \((a,b)\) 都恰好对应于 \(a\in A_d\cap(B_d-c)\) 的选择。因此
\[ q_d = \sum_{c\in C_d} |A_d\cap (B_d-c)|. \]
由于 \(A_d\)、\(B_d\)、\(C_d\) 都是方向一致的六边形，所以每个 \(A_d\cap(B_d-c)\) 仍然是一个更小的同向六边形，或者是它在边界上的退化情形。把位移向量 \(c\) 按它们在六边形中的位置分组后，这个总和会变成若干条二次的行长度轮廓；把这些轮廓求和，就会得到四次闭式
\[ q_d= \begin{cases} \dfrac{21t^4+70t^3+87t^2+46t+8}{4}, & d\ \text{为偶数},\\[8pt] \dfrac{21t^4+98t^3+171t^2+134t+40}{4}, & d\ \text{为奇数}. \end{cases} \]
到这里题目就已经结束了：求出 \(k_{n-1}\) 与 \(q_{n-1}\)，再代回 \(g(n)=3k_{n-1}^2-2q_{n-1}\) 即可。
经过一天之后，三个投影集合分别是
\[ A_1=\{(0,0),(0,1),(1,-1),(1,0)\}, \]
\[ B_1=\{(-1,1),(0,0),(0,1),(1,0)\}, \]
\[ C_1=\{(-1,0),(-1,1),(0,0),(0,1)\}. \]
因此 \(k_1=4\)，三条生成规则各自产生 \(4^2=16\) 个候选点对。重叠项为
\[ q_1 = \sum_{c\in C_1} |A_1\cap(B_1-c)| = 2+3+3+2 = 10. \]
于是
\[ g(2)=|P_2| = 3\cdot 4^2 - 2\cdot 10 = 28, \]
这与实现中的小规模校验完全一致。大天数公式背后的逻辑，本质上就是同一个容斥计数过程。
C++、Python 与 Java 三份实现使用的是同一套数学结构，不过只有 C++ 版本保留了按天显式展开状态集合的校验路径。它会存储当前的 \(P_d\)，提取 \(A_d\)、\(B_d\)、\(C_d\)，应用三条生成规则，并据此确认闭式公式确实复现了前几天的精确计数。
真正的求值路径从不显式构造这些六边形。它先计算日参数 \(d=n-1\)，再转成依赖奇偶性的 \(t\)，接着代入 \(k_d\) 与 \(q_d\) 的多项式公式，最后返回 \(3k_d^2-2q_d\)。由于四次多项式的中间结果已经远远超出 64 位有符号整数范围，C++ 版本使用 128 位整数；Java 版本使用任意精度整数；Python 则天然支持精确大整数。
三份实现都保留了简单的基例 \(g(0)=2\)，而 C++ 与 Python 版本还会额外核对 \(g(1)=8\)、\(g(2)=28\) 这类已知小值。
闭式求解器的时间复杂度是 \(O(1)\)，空间复杂度也是 \(O(1)\)：它只需要计算固定数量的幂、乘法和加法。不同语言版本之间的差异只体现在数值类型上，不体现在算法层面。
校验用的暴力模型则会先指数增长、随后呈现组合爆炸，因为它显式保存完整的 \(P_d\) 状态集合。这个版本被有意限制在很小的 \(d\) 上，只负责验证几何结构与容斥公式；真正的目标输入 \(n=16\) 使用的是常数时间闭式。
Пусть \(P_n\) обозначает множество всех упорядоченных пар точек решетки \((a,b)\), существующих после \(n\) дней, если стартовать из двух начальных состояний \(((1,0),(0,1))\) и \(((0,0),(0,0))\). Требуемая величина равна \(g(n)=|P_n|\), и реализации вычисляют ее для \(n=16\).
Наивная динамика расширяет каждое состояние, выделяя первый конец, второй конец и вектор смещения, а затем заново строит все состояния, совместимые с этими тремя проекциями. Такой перебор годится только для совсем малых \(n\). Реальное решение сжимает один полный день в две скалярные величины \(k_d\) и \(q_d\), после чего использует закрытую формулу за постоянное время.
Для фиксированного дня \(d\) введем
\[ A_d=\{a:(a,b)\in P_d\},\qquad B_d=\{b:(a,b)\in P_d\},\qquad C_d=\{b-a:(a,b)\in P_d\}. \]
Это, соответственно, левые концы, правые концы и векторы разностей, видимые в день \(d\). Следующий день строится ровно из тех трех конструкций, которые присутствуют в реализациях.
Обозначим три правила порождения на дне \(d\) через
\[ X_d=A_d\times B_d,\qquad Y_d=\{(b-c,b):b\in B_d,\ c\in C_d\},\qquad Z_d=\{(a,a+c):a\in A_d,\ c\in C_d\}, \]
тогда
\[ P_{d+1}=X_d\cup Y_d\cup Z_d. \]
Если спроецировать это равенство на первую координату, вторую координату и разность, получаются три точные рекуррентные формулы:
\[ A_{d+1}=B_d-C_d,\qquad B_{d+1}=A_d+C_d,\qquad C_{d+1}=B_d-A_d. \]
Значит, эволюция управляется не произвольным облаком пар, а тремя множествами на треугольной решетке.
Из симметрий правила обновления следует, что множества \(A_d\), \(B_d\) и \(C_d\) конгруэнтны и потому всегда имеют одинаковый размер. Обозначим
\[ k_d = |A_d| = |B_d| = |C_d|. \]
Тогда каждое из множеств \(X_d\), \(Y_d\) и \(Z_d\) имеет размер \(k_d^2\). Остается разобраться только с перекрытием. Пара \((a,b)\) принадлежит \(X_d\cap Y_d\) тогда и только тогда, когда \(a\in A_d\), \(b\in B_d\) и одновременно \(b-a\in C_d\). Но это ровно то же условие, которое помещает \((a,b)\) и в \(Z_d\). Следовательно, все попарные пересечения и тройное пересечение совпадают. Если ввести
\[ q_d = \#\{(a,b): a\in A_d,\ b\in B_d,\ b-a\in C_d\}, \]
то формула включений-исключений упрощается до
\[ |P_{d+1}| = 3k_d^2 - 2q_d. \]
Именно отсюда возникает формула, используемая всеми тремя реализациями:
\[ g(0)=2,\qquad g(n)=3k_{n-1}^2-2q_{n-1}\quad (n\ge 1). \]
Если выписать рекурсии для \(A_d\), \(B_d\) и \(C_d\) на нескольких первых днях, проявляется жесткая геометрическая структура: каждое из этих множеств является решетчатым шестиугольником, ограниченным тремя полосами в направлениях \(x\), \(y\) и \(x+y\). Все три множества представляют собой одну и ту же фигуру, только направления циклически переименованы на \(120^\circ\).
Удобный параметр здесь равен \(t\) и зависит от четности дня:
\[ t= \begin{cases} \dfrac{2^d-1}{3}, & d\ \text{четный},\\[6pt] \dfrac{2^d-2}{3}, & d\ \text{нечетный}. \end{cases} \]
Например, в четный день множество \(A_d\) можно записать как
\[ A_d=\{(x,y)\in\mathbb Z^2:\ -t\le x\le t+1,\ -t\le y\le t,\ -t\le x+y\le t+1\}. \]
Два других множества имеют ту же форму после циклического сдвига этих трех направлений. В нечетный день описание остается тем же по духу, но тройка длин сторон меняется с \((t,t,t+1)\) на \((t,t+1,t+1)\).
Для решетчатого шестиугольника с тройкой параметров \((u,v,w)\) число решетчатых точек равно
\[ uv+vw+wu+u+v+w+1. \]
Подставляя \((u,v,w)=(t,t,t+1)\) или \((t,t+1,t+1)\), получаем
\[ k_d= \begin{cases} 3t^2+5t+2, & d\ \text{четный},\\[4pt] 3t^2+7t+4, & d\ \text{нечетный}. \end{cases} \]
Величина \(q_d\) есть точный счет совместимости трех решетчатых шестиугольников. Зафиксируем \(c\in C_d\). Любая допустимая пара \((a,b)\) с условием \(b-a=c\) получается ровно тогда, когда выбран \(a\in A_d\cap(B_d-c)\). Следовательно,
\[ q_d = \sum_{c\in C_d} |A_d\cap (B_d-c)|. \]
Поскольку \(A_d\), \(B_d\) и \(C_d\) являются согласованно ориентированными шестиугольниками, каждое пересечение \(A_d\cap(B_d-c)\) снова представляет собой меньший шестиугольник той же ориентации или его вырожденный пограничный вариант. Если сгруппировать векторы \(c\) по их положению внутри шестиугольника, сумма распадается на квадратичные профили по строкам, а их суммирование дает закрытые формулы четвертой степени
\[ q_d= \begin{cases} \dfrac{21t^4+70t^3+87t^2+46t+8}{4}, & d\ \text{четный},\\[8pt] \dfrac{21t^4+98t^3+171t^2+134t+40}{4}, & d\ \text{нечетный}. \end{cases} \]
После этого задача фактически завершена: нужно вычислить \(k_{n-1}\) и \(q_{n-1}\), а затем подставить их в \(g(n)=3k_{n-1}^2-2q_{n-1}\).
После одного дня проектированные множества имеют вид
\[ A_1=\{(0,0),(0,1),(1,-1),(1,0)\}, \]
\[ B_1=\{(-1,1),(0,0),(0,1),(1,0)\}, \]
\[ C_1=\{(-1,0),(-1,1),(0,0),(0,1)\}. \]
Значит, \(k_1=4\), и каждое правило порождения дает \(4^2=16\) кандидатных пар. Член перекрытия равен
\[ q_1 = \sum_{c\in C_1} |A_1\cap(B_1-c)| = 2+3+3+2 = 10. \]
Отсюда
\[ g(2)=|P_2| = 3\cdot 4^2 - 2\cdot 10 = 28, \]
что в точности совпадает с малыми проверками в реализациях. Та же схема включений-исключений лежит и за формулой для больших дней.
Реализации на C++, Python и Java используют одну и ту же математику, но только версия на C++ сохраняет явное посуточное расширение множества состояний для проверки. Она хранит текущее \(P_d\), извлекает из него \(A_d\), \(B_d\) и \(C_d\), применяет три правила порождения и подтверждает, что закрытая формула воспроизводит точные значения для первых нескольких дней.
Основной путь вычисления никогда явно не строит сами шестиугольники. Он берет параметр дня \(d=n-1\), переводит его в зависящее от четности значение \(t\), вычисляет полиномиальные формулы для \(k_d\) и \(q_d\), а затем возвращает \(3k_d^2-2q_d\). Версия на C++ использует 128-битные целые, потому что промежуточные выражения четвертой степени уже намного превосходят границы знакового 64-битного типа; версия на Java использует целые произвольной точности; Python автоматически работает с точными большими целыми.
Все три реализации учитывают простой базовый случай \(g(0)=2\), а версии на C++ и Python дополнительно проверяют малые известные значения вроде \(g(1)=8\) и \(g(2)=28\).
Решение в закрытой форме имеет сложность \(O(1)\) по времени и \(O(1)\) по памяти: требуется вычислить только фиксированное число степеней, произведений и сумм. Поэтому различия между языками связаны лишь с числовым представлением, а не с алгоритмической схемой.
Проверочный вариант сначала растет экспоненциально, а затем комбинаторно, поскольку явно хранит полные множества состояний \(P_d\). Именно поэтому он ограничен очень малыми \(d\): его задача состоит только в подтверждении геометрии и формулы включений-исключений перед тем, как для реального целевого значения \(n=16\) используется закрытое вычисление.
لتكن \(P_n\) مجموعة الأزواج المرتبة من نقاط الشبكة \((a,b)\) الموجودة بعد \(n\) يومًا، انطلاقًا من حالتي البداية \(((1,0),(0,1))\) و\(((0,0),(0,0))\). الكمية المطلوبة في المسألة هي \(g(n)=|P_n|\)، وجميع التطبيقات تحسبها عند \(n=16\).
الطريقة الساذجة توسع كل حالة باستخراج النهاية الأولى والنهاية الثانية ومتجه الإزاحة، ثم تعيد بناء كل الحالات المتوافقة مع هذه الإسقاطات الثلاثة. هذا يصلح فقط للقيم الصغيرة جدًا من \(n\). أما الحل الحقيقي فيضغط يومًا كاملًا في عددين فقط هما \(k_d\) و\(q_d\)، ثم يقيّم صيغة مغلقة بزمن ثابت.
لليوم الثابت \(d\) نعرّف
\[ A_d=\{a:(a,b)\in P_d\},\qquad B_d=\{b:(a,b)\in P_d\},\qquad C_d=\{b-a:(a,b)\in P_d\}. \]
هذه هي النهايات اليسرى والنهايات اليمنى ومتجهات الفرق الظاهرة في اليوم \(d\). واليوم التالي يُبنى تمامًا من التراكيب الثلاثة الموجودة في التطبيقات.
إذا سمّينا قواعد التوليد الثلاث في اليوم \(d\) كما يلي
\[ X_d=A_d\times B_d,\qquad Y_d=\{(b-c,b):b\in B_d,\ c\in C_d\},\qquad Z_d=\{(a,a+c):a\in A_d,\ c\in C_d\}, \]
فإن
\[ P_{d+1}=X_d\cup Y_d\cup Z_d. \]
وبإسقاط هذه الهوية على الإحداثي الأول والإحداثي الثاني وعلى الفرق، نحصل على ثلاث علاقات عودية دقيقة:
\[ A_{d+1}=B_d-C_d,\qquad B_{d+1}=A_d+C_d,\qquad C_{d+1}=B_d-A_d. \]
وهذا يوضح أن العملية محكومة بثلاث مجموعات على الشبكة المثلثية، لا بسحابة عشوائية من الأزواج.
بسبب تناظرات قاعدة التحديث، تبقى المجموعات الإسقاطية الثلاث \(A_d\) و\(B_d\) و\(C_d\) متطابقة شكليًا، ولذلك تملك دائمًا الحجم نفسه. نضع
\[ k_d = |A_d| = |B_d| = |C_d|. \]
عندئذ يكون حجم كل من \(X_d\) و\(Y_d\) و\(Z_d\) مساويًا لـ \(k_d^2\). ولم يبقَ إلا حساب التداخل. فالزوج \((a,b)\) ينتمي إلى \(X_d\cap Y_d\) إذا وفقط إذا كان \(a\in A_d\) و\(b\in B_d\) و\(b-a\in C_d\). لكن هذا هو الشرط نفسه الذي يضع \((a,b)\) في \(Z_d\) أيضًا. إذن جميع التقاطعات الثنائية والتقاطع الثلاثي هي في الحقيقة المجموعة نفسها. فإذا عرفنا
\[ q_d = \#\{(a,b): a\in A_d,\ b\in B_d,\ b-a\in C_d\}, \]
فإن مبدأ الاحتواء والاستبعاد يختزل إلى
\[ |P_{d+1}| = 3k_d^2 - 2q_d. \]
ومن هنا تأتي الصيغة التي تستخدمها التطبيقات الثلاثة:
\[ g(0)=2,\qquad g(n)=3k_{n-1}^2-2q_{n-1}\quad (n\ge 1). \]
عندما نكتب العوديات الخاصة بـ \(A_d\) و\(B_d\) و\(C_d\) لعدة أيام صغيرة، يظهر نمط هندسي صارم: كل مجموعة منها عبارة عن سداسي نقاط شبكي محدود بثلاث عائلات من المستقيمات في الاتجاهات \(x\) و\(y\) و\(x+y\). والمجموعات الثلاث هي الشكل نفسه بعد إعادة تسمية دورية لهذه الاتجاهات بزاوية \(120^\circ\).
المعامل المناسب هنا هو \(t\)، وهو يعتمد على زوجية اليوم:
\[ t= \begin{cases} \dfrac{2^d-1}{3}, & d\ \text{even},\\[6pt] \dfrac{2^d-2}{3}, & d\ \text{odd}. \end{cases} \]
فعلى سبيل المثال، في يوم زوجي يمكن كتابة \(A_d\) على الصورة
\[ A_d=\{(x,y)\in\mathbb Z^2:\ -t\le x\le t+1,\ -t\le y\le t,\ -t\le x+y\le t+1\}. \]
أما المجموعتان الأخريان فلهما الشكل نفسه بعد تدوير الاتجاهات الثلاثة دوريًا. وفي اليوم الفردي يبقى الوصف الهندسي من النوع نفسه، لكن ثلاثية أطوال الأضلاع تنتقل من \((t,t,t+1)\) إلى \((t,t+1,t+1)\).
إذا كان لسداسي شبكي ثلاثية أضلاع \((u,v,w)\)، فإن عدد نقاط الشبكة فيه يساوي
\[ uv+vw+wu+u+v+w+1. \]
وبالتعويض بـ \((u,v,w)=(t,t,t+1)\) أو \((t,t+1,t+1)\) نحصل على
\[ k_d= \begin{cases} 3t^2+5t+2, & d\ \text{even},\\[4pt] 3t^2+7t+4, & d\ \text{odd}. \end{cases} \]
الحد \(q_d\) هو عدّ دقيق للتوافق بين السداسيات الشبكية الثلاثة. ثبّت متجهًا \(c\in C_d\). كل زوج صالح \((a,b)\) يحقق \(b-a=c\) ينتج بالضبط من اختيار \(a\in A_d\cap(B_d-c)\). ولذلك
\[ q_d = \sum_{c\in C_d} |A_d\cap (B_d-c)|. \]
وبما أن \(A_d\) و\(B_d\) و\(C_d\) سداسيات مصطفة في الاتجاهات نفسها، فإن كل تقاطع من الشكل \(A_d\cap(B_d-c)\) يكون بدوره سداسيًا أصغر من الاتجاه نفسه أو حالة حدية متدهورة منه. وعندما نُجَمِّع متجهات الإزاحة \(c\) بحسب موضعها داخل السداسي، تتحول هذه الصيغة إلى مقاطع صفية تربيعية؛ وبجمع هذه المقاطع نحصل على الصيغ المغلقة من الدرجة الرابعة
\[ q_d= \begin{cases} \dfrac{21t^4+70t^3+87t^2+46t+8}{4}, & d\ \text{even},\\[8pt] \dfrac{21t^4+98t^3+171t^2+134t+40}{4}, & d\ \text{odd}. \end{cases} \]
وعند هذه النقطة تكون المسألة قد حُلّت: نحسب \(k_{n-1}\) و\(q_{n-1}\)، ثم نعوض بهما في \(g(n)=3k_{n-1}^2-2q_{n-1}\).
بعد يوم واحد تصبح المجموعات الإسقاطية هي
\[ A_1=\{(0,0),(0,1),(1,-1),(1,0)\}, \]
\[ B_1=\{(-1,1),(0,0),(0,1),(1,0)\}, \]
\[ C_1=\{(-1,0),(-1,1),(0,0),(0,1)\}. \]
إذًا \(k_1=4\)، وكل قاعدة توليد تعطي \(4^2=16\) زوجًا مرشحًا. أما حد التداخل فيساوي
\[ q_1 = \sum_{c\in C_1} |A_1\cap(B_1-c)| = 2+3+3+2 = 10. \]
ومن ثم
\[ g(2)=|P_2| = 3\cdot 4^2 - 2\cdot 10 = 28, \]
وهو تمامًا ما تؤكده اختبارات القيم الصغيرة في التطبيقات. والآلية نفسها، أي الاحتواء والاستبعاد مع عدّ التوافق، هي التي تنتج صيغة الأيام الكبيرة.
تستخدم تطبيقات C++ وPython وJava الرياضيات نفسها، لكن نسخة C++ وحدها تحتفظ بتوسعة يومية صريحة لمجموعة الحالات من أجل التحقق. فهي تخزن \(P_d\) الحالي، وتستخرج منه \(A_d\) و\(B_d\) و\(C_d\)، ثم تطبق قواعد التوليد الثلاث وتؤكد أن الصيغة المغلقة تعيد العدّ الدقيق للأيام الأولى.
المسار الفعلي للحل لا يبني هذه السداسيات صراحةً. بل يحسب أولًا معامل اليوم \(d=n-1\)، ثم يحوله إلى القيمة \(t\) التابعة للزوجية، ثم يقيّم كثيرات الحدود الخاصة بـ \(k_d\) و\(q_d\)، وأخيرًا يعيد \(3k_d^2-2q_d\). تستخدم نسخة C++ أعدادًا صحيحة من 128 بت لأن التعابير الرباعية الوسيطة تتجاوز بكثير حدود 64 بت الموقعة؛ وتستخدم نسخة Java أعدادًا صحيحة ذات دقة غير محدودة؛ أما Python فيتعامل تلقائيًا مع الأعداد الصحيحة الكبيرة بدقة تامة.
وتتعامل التطبيقات الثلاثة مع الحالة الأساسية \(g(0)=2\)، كما تتحقق نسختا C++ وPython أيضًا من قيم صغيرة معروفة مثل \(g(1)=8\) و\(g(2)=28\).
الحل ذو الصيغة المغلقة يعمل بزمن \(O(1)\) وذاكرة \(O(1)\): فهو لا ينفذ إلا عددًا ثابتًا من عمليات الأس والضرب والجمع. لذلك فإن الفروق بين اللغات تعود فقط إلى تمثيل الأعداد، لا إلى البنية الخوارزمية.
أما نموذج التحقق فينمو أولًا نموًا أسيًا ثم انفجارًا توافقيًا لأنه يخزن مجموعات الحالات الكاملة \(P_d\) بشكل صريح. ولهذا يُقصر عمدًا على القيم الصغيرة جدًا لـ \(d\)؛ فوظيفته الوحيدة هي تأكيد البنية الهندسية وصيغة الاحتواء والاستبعاد قبل استخدام الصيغة الثابتة للهدف الحقيقي \(n=16\).