The 81 cards of the SET deck can be modeled as the 81 points of \(D=\mathbb F_3^4\). For an \(n\)-card subset \(A\subseteq D\), let \(X(A)\) be the number of SETs contained entirely in \(A\). The problem defines
$$F(n)=\sum_{\substack{A\subseteq D\\|A|=n}} X(A)^4$$
and asks for \(F(12)\), with the checkpoints \(F(3)=1080\) and \(F(6)=159690960\). The implemented solution does not enumerate the \(\binom{81}{12}\) subsets. Instead, it rewrites the fourth moment in terms of ordered quadruples of affine lines and counts those quadruples by the size of their union.
The four attributes of a SET card each have three possible values, so \(\mathbb F_3^4\) is the natural ambient space. In that model, every valid SET is exactly a 3-point affine line.
Encode each attribute value by \(0\), \(1\), or \(2\). Then a card becomes a vector in \(\mathbb F_3^4\). Three cards \(u,v,w\) form a SET exactly when, coordinate by coordinate, the values are either all equal or all distinct. Over \(\mathbb F_3\), both cases are equivalent to
$$u+v+w=0.$$
So once two cards are known, the third one is forced:
$$w=-(u+v).$$
Geometrically, every SET is an affine line of the form
$$\{a,\ a+d,\ a+2d\},\qquad d\ne 0.$$
The number of possible directions is the number of 1-dimensional subspaces of \(\mathbb F_3^4\):
$$\frac{3^4-1}{3-1}=40.$$
Each direction partitions the 81 points into \(81/3=27\) parallel lines, hence the total number of SETs is
$$L=40\cdot 27=1080.$$
Equivalently, every point lies on one line in each direction, so every card belongs to exactly \(40\) SETs.
For any \(n\)-card subset \(A\subseteq D\), \(X(A)\) counts how many affine lines are fully contained in \(A\). Therefore
$$X(A)^4=\sum_{(\ell_1,\ell_2,\ell_3,\ell_4)} \mathbf{1}_{\ell_1\cup\ell_2\cup\ell_3\cup\ell_4\subseteq A},$$
where the sum runs over ordered quadruples of SET-lines. Summing over all \(A\) with \(|A|=n\) yields
$$F(n)=\sum_{(\ell_1,\ell_2,\ell_3,\ell_4)} \#\{A\subseteq D:\ |A|=n,\ \ell_1\cup\ell_2\cup\ell_3\cup\ell_4\subseteq A\}.$$
This is the key transformation: instead of choosing subsets first and counting SETs afterward, we choose ordered quadruples of SETs first and then ask how many subsets contain them.
For one ordered quadruple \((\ell_1,\ell_2,\ell_3,\ell_4)\), define
$$m=\left|\ell_1\cup\ell_2\cup\ell_3\cup\ell_4\right|.$$
If that union has size \(m\), then any \(n\)-card subset containing it is formed by choosing the remaining \(n-m\) cards from the other \(81-m\) cards. Thus each such quadruple contributes
$$\binom{81-m}{n-m}$$
to \(F(n)\). Now define the histogram
$$N_m=\#\left\{(\ell_1,\ell_2,\ell_3,\ell_4):\left|\ell_1\cup\ell_2\cup\ell_3\cup\ell_4\right|=m\right\}.$$
Because each line has exactly three points, the union size can only range from \(3\) to \(12\). Therefore
$$\boxed{F(n)=\sum_{m=3}^{12} N_m\binom{81-m}{n-m}.}$$
The original problem has now become a finite-geometry counting problem: determine the ten integers \(N_3,N_4,\dots,N_{12}\).
A brute-force count over all ordered quadruples would require \(L^4=1080^4\) cases. The implementations avoid that by representing each line as an 81-bit mask with exactly three set bits. Then the union size of several lines is just the popcount of the bitwise OR of those masks.
The crucial simplification is symmetry: the affine automorphism group of \(\mathbb F_3^4\) sends any line to any other line, so the union-size distribution does not depend on which first line is chosen. One may therefore fix a single line \(\ell_1\), enumerate all ordered triples \((\ell_2,\ell_3,\ell_4)\), record the resulting union sizes, and multiply the histogram by \(L=1080\) at the end.
This turns the dominant work into \(O(L^3)\) union operations instead of \(O(L^4)\), while preserving the exact values of all \(N_m\).
If \(n=3\), then a 3-card subset \(A\) either is a SET or it is not. In the first case \(X(A)=1\); in the second case \(X(A)=0\). Hence \(X(A)^4=X(A)\), and so
$$F(3)=\sum_{\substack{A\subseteq D\\|A|=3}} X(A)=1080.$$
This is exactly the first validation checkpoint used by the implementation.
The same union-size formula also explains the range of \(m\). If all four ordered lines are identical, then \(m=3\) and each quadruple contributes \(\binom{78}{n-3}\). If the four lines are pairwise disjoint, then \(m=12\) and each quadruple contributes \(\binom{69}{n-12}\). All intermediate overlap patterns fall into the bins \(m=4,5,\dots,11\).
A second checkpoint, obtained from the same histogram formula after summing all bins, is
$$F(6)=159690960.$$
Matching both checkpoints is strong evidence that the union-size counts are correct before evaluating the target case \(n=12\).
The C++, Python, and Java implementations all follow the same mathematics. They first list the 81 points of \(\mathbb F_3^4\), then enumerate SETs by choosing pairs of points, computing the unique third point \(w=-(u+v)\), sorting each triple, and discarding duplicates. That produces exactly 1080 distinct lines.
Each line is then stored as an 81-bit mask split across machine words. The implementation fixes one reference line, scans all ordered triples of additional lines, computes the popcount of the OR-union, and increments the histogram entry for that union size. After multiplying by 1080, it has all values \(N_m\).
Finally, the implementation evaluates
$$F(n)=\sum_{m=3}^{12} N_m\binom{81-m}{n-m}$$
with exact integer arithmetic. The C++ and Java implementations parallelize the outer part of the triple scan across threads. The Python implementation delegates to the same compiled counting strategy. All three implementations also verify structural identities such as the total number of lines, the 40 lines through each point, and the checkpoints \(F(3)\) and \(F(6)\).
Generating the line list is inexpensive: it comes from scanning unordered point pairs, so that stage is bounded by \(O(81^2)\) work plus deduplication. The dominant phase is the fixed-line histogram count, which performs \(O(L^3)\) iterations with \(L=1080\). Each iteration uses only a constant number of bitwise OR and popcount operations, so the method is fast enough in practice despite the large constant \(1080^3\).
Memory usage is \(O(L)\): the program stores one bit mask per line and a small histogram for the possible union sizes. No large table over subsets is needed.
Die 81 Karten des Spiels SET lassen sich als die 81 Punkte von \(D=\mathbb F_3^4\) modellieren. Für eine \(n\)-elementige Teilmenge \(A\subseteq D\) bezeichne \(X(A)\) die Anzahl der vollständig in \(A\) enthaltenen SETs. Gesucht ist
$$F(n)=\sum_{\substack{A\subseteq D\\|A|=n}} X(A)^4$$
und speziell der Wert \(F(12)\), wobei die Kontrollwerte \(F(3)=1080\) und \(F(6)=159690960\) gegeben sind. Die Lösung zählt nicht direkt die \(\binom{81}{12}\) möglichen 12er-Mengen, sondern zerlegt den vierten Moment in geordnete Linien-4-Tupel und gruppiert diese nach ihrer Vereinigungsgröße.
Jede der vier Eigenschaften einer SET-Karte hat drei mögliche Ausprägungen. Deshalb ist \(\mathbb F_3^4\) das natürliche Modell, und ein gültiges SET ist dort genau eine affine Gerade mit drei Punkten.
Jeder Eigenschaftswert wird durch \(0\), \(1\) oder \(2\) codiert. Eine Karte ist dann ein Vektor in \(\mathbb F_3^4\). Drei Karten \(u,v,w\) bilden genau dann ein SET, wenn in jeder Koordinate entweder alle Werte gleich oder alle verschieden sind. Über \(\mathbb F_3\) ist beides äquivalent zu
$$u+v+w=0.$$
Sind also zwei Karten gegeben, so ist die dritte eindeutig bestimmt:
$$w=-(u+v).$$
Geometrisch ist jedes SET eine affine Gerade der Form
$$\{a,\ a+d,\ a+2d\},\qquad d\ne 0.$$
Die Anzahl möglicher Richtungen ist die Anzahl 1-dimensionaler Unterräume von \(\mathbb F_3^4\):
$$\frac{3^4-1}{3-1}=40.$$
Jede Richtung zerlegt die 81 Punkte in \(81/3=27\) parallele Geraden. Damit gibt es insgesamt
$$L=40\cdot 27=1080$$
verschiedene SETs. Entsprechend liegt jeder Punkt auf genau \(40\) solchen Geraden.
Für jede \(n\)-elementige Teilmenge \(A\subseteq D\) zählt \(X(A)\), wie viele affine Geraden vollständig in \(A\) liegen. Damit gilt
$$X(A)^4=\sum_{(\ell_1,\ell_2,\ell_3,\ell_4)} \mathbf{1}_{\ell_1\cup\ell_2\cup\ell_3\cup\ell_4\subseteq A},$$
wobei über geordnete 4-Tupel von SET-Geraden summiert wird. Summiert man nun über alle \(A\) mit \(|A|=n\), so erhält man
$$F(n)=\sum_{(\ell_1,\ell_2,\ell_3,\ell_4)} \#\{A\subseteq D:\ |A|=n,\ \ell_1\cup\ell_2\cup\ell_3\cup\ell_4\subseteq A\}.$$
Das ist der zentrale Perspektivwechsel: Nicht zuerst Mengen \(A\) auswählen und darin SETs zählen, sondern zuerst geordnete SET-4-Tupel auswählen und dann fragen, wie viele \(A\) sie enthalten.
Für ein geordnetes 4-Tupel \((\ell_1,\ell_2,\ell_3,\ell_4)\) setzen wir
$$m=\left|\ell_1\cup\ell_2\cup\ell_3\cup\ell_4\right|.$$
Hat diese Vereinigung Größe \(m\), dann entsteht jede \(n\)-Menge, die sie enthält, durch die Wahl von \(n-m\) weiteren Karten aus den übrigen \(81-m\) Karten. Daher trägt jedes solche 4-Tupel genau
$$\binom{81-m}{n-m}$$
zu \(F(n)\) bei. Definiert man
$$N_m=\#\left\{(\ell_1,\ell_2,\ell_3,\ell_4):\left|\ell_1\cup\ell_2\cup\ell_3\cup\ell_4\right|=m\right\},$$
so folgt wegen der festen Liniengröße \(3\), dass nur \(m=3,4,\dots,12\) möglich sind. Also
$$\boxed{F(n)=\sum_{m=3}^{12} N_m\binom{81-m}{n-m}.}$$
Damit ist das Problem auf die Berechnung der zehn Histogrammwerte \(N_3,\dots,N_{12}\) reduziert.
Eine naive Zählung aller geordneten 4-Tupel würde \(L^4=1080^4\) Fälle benötigen. Die Implementationen vermeiden das, indem sie jede Gerade als 81-Bit-Maske mit genau drei gesetzten Bits darstellen. Die Größe einer Vereinigung ist dann einfach die Popcount des bitweisen ORs.
Der entscheidende Punkt ist die Symmetrie des affinen Raums: Die affinen Automorphismen von \(\mathbb F_3^4\) schicken jede Gerade auf jede andere Gerade. Deshalb hängt die Verteilung der Vereinigungsgrößen nicht davon ab, welche erste Gerade gewählt wird. Man kann also eine Referenzgerade \(\ell_1\) fixieren, alle geordneten Tripel \((\ell_2,\ell_3,\ell_4)\) durchlaufen, deren Vereinigungsgrößen zählen und das resultierende Histogramm am Ende mit \(L=1080\) multiplizieren.
So sinkt der dominante Aufwand von \(O(L^4)\) auf \(O(L^3)\), ohne dass Information verloren geht.
Ist \(n=3\), dann ist eine 3-elementige Teilmenge \(A\) entweder selbst ein SET oder nicht. Im ersten Fall gilt \(X(A)=1\), im zweiten \(X(A)=0\). Also ist \(X(A)^4=X(A)\), und damit
$$F(3)=\sum_{\substack{A\subseteq D\\|A|=3}} X(A)=1080.$$
Genau das ist die erste Prüfung, die auch von der Implementierung verwendet wird.
Die gleiche Vereinigungsformel erklärt auch die möglichen Werte von \(m\). Fallen alle vier geordneten Geraden zusammen, so ist \(m=3\) und jedes 4-Tupel trägt \(\binom{78}{n-3}\) bei. Sind vier Geraden paarweise disjunkt, so ist \(m=12\) und der Beitrag lautet \(\binom{69}{n-12}\). Alle anderen Überlappungsmuster landen in den Zwischenklassen \(m=4,\dots,11\).
Ein zweiter Kontrollwert, der aus demselben Histogramm folgt, ist
$$F(6)=159690960.$$
Wenn beide Werte stimmen, ist die Histogrammzählung mit hoher Sicherheit korrekt und man kann \(F(12)\) zuverlässig auswerten.
Die C++-, Python- und Java-Implementierungen folgen demselben kombinatorischen Plan. Zuerst werden die 81 Punkte von \(\mathbb F_3^4\) erzeugt. Danach werden alle SETs gebildet, indem man Punktpaare auswählt, den eindeutigen dritten Punkt \(w=-(u+v)\) berechnet, das entstehende Triple sortiert und Duplikate entfernt. So entstehen exakt 1080 verschiedene Geraden.
Anschließend wird jede Gerade als 81-Bit-Maske gespeichert. Die Implementierung fixiert eine Referenzgerade, durchläuft alle geordneten Tripel zusätzlicher Geraden, berechnet die Popcount der OR-Vereinigung und erhöht den Zähler der entsprechenden Vereinigungsgröße. Nach der Multiplikation mit 1080 liegen alle Werte \(N_m\) vor.
Zum Schluss wird
$$F(n)=\sum_{m=3}^{12} N_m\binom{81-m}{n-m}$$
mit exakter Ganzzahlarithmetik ausgewertet. Die C++- und Java-Implementierungen parallelisieren den äußeren Teil des Tripelscans über mehrere Threads. Die Python-Implementierung verwendet dieselbe kompilierte Zählstrategie. Zusätzlich werden strukturelle Identitäten wie die Gesamtzahl der Geraden, die 40 Geraden durch jeden Punkt sowie die Kontrollwerte \(F(3)\) und \(F(6)\) überprüft.
Das Erzeugen der Geradenliste ist relativ klein: Es basiert auf einem Scan über ungeordnete Punktpaare und ist daher durch \(O(81^2)\) Arbeit plus Deduplikation beschränkt. Dominant ist die Histogrammphase mit fixierter erster Gerade. Sie benötigt \(O(L^3)\) Zeit bei \(L=1080\). Jede Iteration verwendet nur eine konstante Zahl von OR- und Popcount-Operationen auf Maschinenworten.
Der Speicherbedarf ist \(O(L)\): gespeichert werden eine Bitmaske pro Gerade und ein kleines Histogramm der möglichen Vereinigungsgrößen. Eine große Tabelle über Teilmengen ist nicht nötig.
SET destesindeki 81 kart, \(D=\mathbb F_3^4\) uzayının 81 noktası olarak modellenebilir. \(|A|=n\) olan bir \(A\subseteq D\) altkümesi için \(X(A)\), tamamen \(A\) içinde kalan SET sayısı olsun. Problem
$$F(n)=\sum_{\substack{A\subseteq D\\|A|=n}} X(A)^4$$
fonksiyonunu tanımlıyor ve özellikle \(F(12)\) değerini istiyor; ayrıca kontrol olarak \(F(3)=1080\) ve \(F(6)=159690960\) veriliyor. Uygulanan yöntem \(\binom{81}{12}\) farklı 12'li kümeyi tek tek gezmiyor. Bunun yerine dördüncü momenti sıralı dört doğruya ayırıp bu doğruları birleşim büyüklüklerine göre sayıyor.
SET kartının dört özelliğinin her biri üç değer alabildiği için doğal model \(\mathbb F_3^4\) uzayıdır. Bu modelde her geçerli SET tam olarak üç noktalı bir afin doğrudur.
Her özellik değeri \(0\), \(1\) veya \(2\) ile kodlanır. Böylece her kart \(\mathbb F_3^4\) içinde bir vektör olur. Üç kart \(u,v,w\), her koordinatta değerler ya tamamen aynı ya da tamamen farklı olduğunda bir SET oluşturur. \(\mathbb F_3\) üzerinde bu iki durum da
$$u+v+w=0$$
eşitliğiyle aynıdır. Dolayısıyla iki kart biliniyorsa üçüncü kart zorunlu olarak
$$w=-(u+v)$$
olur. Geometrik olarak her SET
$$\{a,\ a+d,\ a+2d\},\qquad d\ne 0$$
şeklinde bir afin doğrudur. Olası yön sayısı, \(\mathbb F_3^4\) içindeki 1-boyutlu altuzayların sayısıdır:
$$\frac{3^4-1}{3-1}=40.$$
Her yön 81 noktayı \(81/3=27\) paralel doğruya böler. Bu yüzden toplam SET sayısı
$$L=40\cdot 27=1080$$
olur. Eşdeğer biçimde her kart tam \(40\) farklı SET'in içindedir.
\(A\subseteq D\) ve \(|A|=n\) için \(X(A)\), \(A\) içinde tamamen bulunan afin doğruların sayısıdır. Bu nedenle
$$X(A)^4=\sum_{(\ell_1,\ell_2,\ell_3,\ell_4)} \mathbf{1}_{\ell_1\cup\ell_2\cup\ell_3\cup\ell_4\subseteq A}$$
olur; burada toplam sıralı SET doğrusu dörtlüleri üzerindedir. Şimdi tüm \(n\)-elemanlı \(A\) kümeleri üzerinde toplarsak
$$F(n)=\sum_{(\ell_1,\ell_2,\ell_3,\ell_4)} \#\{A\subseteq D:\ |A|=n,\ \ell_1\cup\ell_2\cup\ell_3\cup\ell_4\subseteq A\}$$
elde edilir. Ana dönüşüm budur: önce altkümeleri seçip sonra içlerindeki SET sayısını ölçmek yerine, önce sıralı SET dörtlülerini seçip onları içeren altkümeleri sayarız.
Bir sıralı doğru dörtlüsü için
$$m=\left|\ell_1\cup\ell_2\cup\ell_3\cup\ell_4\right|$$
olsun. Birleşimin boyu \(m\) ise, bunu içeren bir \(n\)-kartlı altküme seçmek için kalan \(n-m\) kartı geriye kalan \(81-m\) kart arasından seçmek yeterlidir. Dolayısıyla böyle her dörtlünün katkısı
$$\binom{81-m}{n-m}$$
olur. Şimdi
$$N_m=\#\left\{(\ell_1,\ell_2,\ell_3,\ell_4):\left|\ell_1\cup\ell_2\cup\ell_3\cup\ell_4\right|=m\right\}$$
tanımını yapalım. Her doğru 3 nokta içerdiği için \(m\) yalnızca \(3\) ile \(12\) arasında olabilir. Böylece
$$\boxed{F(n)=\sum_{m=3}^{12} N_m\binom{81-m}{n-m}.}$$
Yani asıl problem, \(N_3,N_4,\dots,N_{12}\) histogramını bulmaktır.
Tüm sıralı doğru dörtlülerini kaba kuvvetle saymak \(L^4=1080^4\) durum gerektirir. Uygulama bunu önlemek için her doğruyu tam üç biti açık olan 81 bitlik bir maske ile temsil eder. O zaman birkaç doğrunun birleşim boyu, bu maskelerin bit düzeyinde OR birleşiminin popcount değeridir.
Temel sadeleşme simetriden gelir: \(\mathbb F_3^4\) uzayının afin otomorfizmaları herhangi bir doğruyu başka herhangi bir doğruya götürür. Bu yüzden birleşim büyüklüğü dağılımı ilk doğrunun hangisi seçildiğine bağlı değildir. Dolayısıyla tek bir referans doğru \(\ell_1\) sabitlenir, tüm sıralı \((\ell_2,\ell_3,\ell_4)\) üçlüleri dolaşılır, oluşan birleşim boyları histogramlanır ve sonuç en sonda \(L=1080\) ile çarpılır.
Böylece baskın iş yükü \(O(L^4)\) yerine \(O(L^3)\) olur ve tüm \(N_m\) değerleri eksiksiz biçimde korunur.
\(n=3\) olduğunda 3 kartlı bir \(A\) altkümesi ya bir SET'tir ya da değildir. İlk durumda \(X(A)=1\), ikinci durumda \(X(A)=0\). Dolayısıyla \(X(A)^4=X(A)\) ve
$$F(3)=\sum_{\substack{A\subseteq D\\|A|=3}} X(A)=1080$$
elde edilir. Bu, uygulamanın kullandığı ilk doğrulama değeridir.
Aynı birleşim formülü \(m\) aralığını da açıklar. Eğer dört sıralı doğru tamamen aynıysa \(m=3\) olur ve her dörtlü \(\binom{78}{n-3}\) katkı yapar. Eğer dört doğru ikişer ikişer ayrık ise \(m=12\) olur ve katkı \(\binom{69}{n-12}\) olur. Diğer tüm örtüşme kalıpları \(m=4,5,\dots,11\) kutularına düşer.
Aynı histogram formülünden çıkan ikinci kontrol değeri ise
$$F(6)=159690960$$
şeklindedir. Bu iki değerin tutması, hedef durum olan \(n=12\) hesaplanmadan önce birleşim histogramının doğru kurulduğunu güçlü biçimde gösterir.
C++, Python ve Java uygulamaları aynı kombinatorik planı izler. Önce \(\mathbb F_3^4\) uzayının 81 noktası listelenir. Sonra nokta çiftleri seçilir, tekil üçüncü nokta \(w=-(u+v)\) hesaplanır, elde edilen üçlü sıralanır ve tekrarlar atılır. Böylece tam 1080 farklı doğru üretilir.
Her doğru daha sonra 81 bitlik bir maske olarak saklanır. Uygulama bir referans doğruyu sabitler, kalan doğru seçimlerinin tüm sıralı üçlülerini gezer, OR birleşiminin popcount değerini hesaplar ve ilgili birleşim boyu sayacını artırır. Sonuç 1080 ile çarpıldığında tüm \(N_m\) değerleri elde edilir.
Son adımda
$$F(n)=\sum_{m=3}^{12} N_m\binom{81-m}{n-m}$$
ifadesi tam sayı aritmetiğiyle değerlendirilir. C++ ve Java sürümleri dış döngünün bir kısmını çok iş parçacıklı çalıştırır. Python sürümü aynı derlenmiş sayım stratejisine başvurur. Ayrıca toplam doğru sayısı, her noktanın 40 doğru üzerinde bulunması ve \(F(3)\), \(F(6)\) kontrol değerleri gibi yapısal kimlikler de doğrulanır.
Doğru listesini üretmek görece ucuzdur: sırasız nokta çiftleri üzerinden gidildiği için bu aşama \(O(81^2)\) iş ve tekrar eleme maliyeti ile sınırlıdır. Baskın aşama, ilk doğru sabitlenmiş histogram sayımıdır ve \(L=1080\) için \(O(L^3)\) zaman gerektirir. Her iterasyon yalnızca sabit sayıda bit düzeyinde OR ve popcount işlemi yapar.
Bellek kullanımı \(O(L)\) düzeyindedir: her doğru için bir maske ve birleşim boyları için küçük bir histogram tutulur. Altkümeler üzerinde büyük bir tablo kurmaya gerek yoktur.
Las 81 cartas de SET se pueden modelar como los 81 puntos de \(D=\mathbb F_3^4\). Para un subconjunto \(A\subseteq D\) con \(|A|=n\), sea \(X(A)\) el número de SETs contenidos por completo en \(A\). El problema define
$$F(n)=\sum_{\substack{A\subseteq D\\|A|=n}} X(A)^4$$
y pide calcular \(F(12)\), dando además los puntos de control \(F(3)=1080\) y \(F(6)=159690960\). La solución implementada no recorre los \(\binom{81}{12}\) subconjuntos posibles. En cambio, reescribe el cuarto momento en términos de cuádruplas ordenadas de líneas afines y cuenta esas cuádruplas por el tamaño de su unión.
Cada una de las cuatro características de una carta SET tiene tres valores posibles, así que \(\mathbb F_3^4\) es el espacio natural. En ese modelo, cada SET válido es exactamente una línea afín de 3 puntos.
Codificamos cada valor posible como \(0\), \(1\) o \(2\). Así, cada carta se vuelve un vector de \(\mathbb F_3^4\). Tres cartas \(u,v,w\) forman un SET exactamente cuando, en cada coordenada, los valores son todos iguales o todos distintos. En \(\mathbb F_3\), ambas situaciones equivalen a
$$u+v+w=0.$$
Por tanto, si conocemos dos cartas, la tercera queda determinada de manera única:
$$w=-(u+v).$$
Geométricamente, cada SET es una línea afín de la forma
$$\{a,\ a+d,\ a+2d\},\qquad d\ne 0.$$
El número de direcciones posibles es el número de subespacios de dimensión 1 de \(\mathbb F_3^4\):
$$\frac{3^4-1}{3-1}=40.$$
Cada dirección particiona los 81 puntos en \(81/3=27\) líneas paralelas. Por eso el número total de SETs es
$$L=40\cdot 27=1080.$$
Equivalentemente, cada carta pertenece a exactamente \(40\) SETs.
Para cualquier subconjunto \(A\subseteq D\) con \(|A|=n\), \(X(A)\) cuenta cuántas líneas afines quedan contenidas por completo en \(A\). Entonces
$$X(A)^4=\sum_{(\ell_1,\ell_2,\ell_3,\ell_4)} \mathbf{1}_{\ell_1\cup\ell_2\cup\ell_3\cup\ell_4\subseteq A},$$
donde la suma recorre cuádruplas ordenadas de líneas-SET. Al sumar sobre todos los \(A\) con \(|A|=n\), obtenemos
$$F(n)=\sum_{(\ell_1,\ell_2,\ell_3,\ell_4)} \#\{A\subseteq D:\ |A|=n,\ \ell_1\cup\ell_2\cup\ell_3\cup\ell_4\subseteq A\}.$$
Ese es el cambio de punto de vista decisivo: en lugar de elegir primero un subconjunto y después contar sus SETs, elegimos primero las cuádruplas ordenadas de SETs y luego contamos cuántos subconjuntos las contienen.
Para una cuádrupla ordenada \((\ell_1,\ell_2,\ell_3,\ell_4)\), definimos
$$m=\left|\ell_1\cup\ell_2\cup\ell_3\cup\ell_4\right|.$$
Si la unión tiene tamaño \(m\), entonces cualquier subconjunto de tamaño \(n\) que la contenga se forma eligiendo los \(n-m\) elementos restantes entre los otros \(81-m\) puntos. Por ello, cada cuádrupla de ese tipo aporta
$$\binom{81-m}{n-m}$$
a \(F(n)\). Definimos entonces
$$N_m=\#\left\{(\ell_1,\ell_2,\ell_3,\ell_4):\left|\ell_1\cup\ell_2\cup\ell_3\cup\ell_4\right|=m\right\}.$$
Como cada línea tiene exactamente 3 puntos, \(m\) solo puede tomar valores entre \(3\) y \(12\). Por tanto,
$$\boxed{F(n)=\sum_{m=3}^{12} N_m\binom{81-m}{n-m}.}$$
El problema original queda reducido a calcular el histograma \(N_3,N_4,\dots,N_{12}\).
Un conteo ingenuo de todas las cuádruplas ordenadas requeriría \(L^4=1080^4\) casos. Las implementaciones lo evitan representando cada línea mediante una máscara de 81 bits con exactamente tres bits activados. Así, el tamaño de la unión de varias líneas se obtiene como el popcount del OR bit a bit de esas máscaras.
La simplificación clave es la simetría: el grupo de automorfismos afines de \(\mathbb F_3^4\) envía cualquier línea a cualquier otra. Por eso, la distribución de tamaños de unión no depende de cuál sea la primera línea elegida. Basta fijar una línea de referencia \(\ell_1\), recorrer todas las ternas ordenadas \((\ell_2,\ell_3,\ell_4)\), registrar el tamaño de la unión resultante y multiplicar el histograma final por \(L=1080\).
De ese modo, el trabajo dominante baja de \(O(L^4)\) a \(O(L^3)\), manteniendo exactamente los valores correctos de todos los \(N_m\).
Si \(n=3\), un subconjunto \(A\) de tres cartas o bien es un SET o bien no lo es. En el primer caso \(X(A)=1\); en el segundo \(X(A)=0\). Entonces \(X(A)^4=X(A)\), y por tanto
$$F(3)=\sum_{\substack{A\subseteq D\\|A|=3}} X(A)=1080.$$
Ese es exactamente el primer punto de comprobación usado por la implementación.
La misma fórmula por tamaños de unión también aclara el rango posible de \(m\). Si las cuatro líneas ordenadas son la misma línea, entonces \(m=3\) y cada cuádrupla aporta \(\binom{78}{n-3}\). Si las cuatro líneas son disjuntas entre sí, entonces \(m=12\) y el aporte es \(\binom{69}{n-12}\). Todos los demás patrones de solapamiento caen en las clases intermedias \(m=4,5,\dots,11\).
Un segundo punto de control que sale del mismo histograma es
$$F(6)=159690960.$$
Cuando ambos valores coinciden, el recuento por tamaños de unión queda bien validado antes de evaluar el caso objetivo \(n=12\).
Las implementaciones en C++, Python y Java siguen el mismo plan combinatorio. Primero enumeran los 81 puntos de \(\mathbb F_3^4\). Luego generan cada SET tomando pares de puntos, calculando el tercer punto único \(w=-(u+v)\), ordenando la terna resultante y eliminando duplicados. Así se obtienen exactamente 1080 líneas distintas.
Después, cada línea se almacena como una máscara de 81 bits. La implementación fija una línea de referencia, recorre todas las ternas ordenadas de líneas adicionales, calcula el popcount de la unión mediante OR y acumula ese tamaño en el histograma correspondiente. Tras multiplicar por 1080, ya dispone de todos los valores \(N_m\).
Por último evalúa
$$F(n)=\sum_{m=3}^{12} N_m\binom{81-m}{n-m}$$
con aritmética entera exacta. Las versiones en C++ y Java paralelizan la parte exterior del recorrido triple. La versión en Python delega en la misma estrategia compilada de conteo. Las tres implementaciones también verifican identidades estructurales como el total de líneas, las 40 líneas que pasan por cada punto y los valores de control \(F(3)\) y \(F(6)\).
La generación de la lista de líneas es pequeña en comparación con la fase principal: proviene de recorrer pares no ordenados de puntos, así que queda acotada por \(O(81^2)\) trabajo más la eliminación de duplicados. El costo dominante es el histograma con primera línea fija, que usa \(O(L^3)\) tiempo con \(L=1080\). Cada iteración realiza solamente un número constante de operaciones OR y popcount.
La memoria utilizada es \(O(L)\): una máscara por línea y un histograma pequeño para los tamaños de unión posibles. No se necesita ninguna estructura grande sobre subconjuntos del mazo.
SET 牌组共有 81 张牌，可以自然地看成 \(D=\mathbb F_3^4\) 的 81 个点。对任意满足 \(|A|=n\) 的子集 \(A\subseteq D\)，记 \(X(A)\) 为完全包含在 \(A\) 中的 SET 数量。题目定义
$$F(n)=\sum_{\substack{A\subseteq D\\|A|=n}} X(A)^4$$
并要求求出 \(F(12)\)，同时给出两个校验值 \(F(3)=1080\) 与 \(F(6)=159690960\)。实现并不是去枚举 \(\binom{81}{12}\) 个 12 张牌子集，而是把这个四次矩问题改写成“有序四条 SET 直线”的计数问题，再按四条直线并集的大小分类统计。
每张 SET 牌有四个属性，每个属性有三种取值，因此 \(\mathbb F_3^4\) 正好给出最自然的数学模型。在这个模型里，每一个合法 SET 都恰好对应一条包含 3 个点的仿射直线。
把每个属性值编码成 \(0\)、\(1\)、\(2\)。这样每张牌就对应 \(\mathbb F_3^4\) 中的一个向量。三张牌 \(u,v,w\) 构成一个 SET，当且仅当在每个坐标上它们的取值要么全相同，要么全不同。在 \(\mathbb F_3\) 中，这两种情况都等价于
$$u+v+w=0.$$
因此，一旦给定两张牌，第三张牌就被唯一确定：
$$w=-(u+v).$$
从几何上看，每个 SET 都是一条形如
$$\{a,\ a+d,\ a+2d\},\qquad d\ne 0$$
的仿射直线。可能的方向数等于 \(\mathbb F_3^4\) 中 1 维子空间的个数：
$$\frac{3^4-1}{3-1}=40.$$
每个方向都会把 81 个点划分成 \(81/3=27\) 条平行直线，所以整副牌中的 SET 总数是
$$L=40\cdot 27=1080.$$
换句话说，每一张牌都恰好落在 40 个不同的 SET 里。
对任意 \(|A|=n\) 的子集 \(A\subseteq D\)，\(X(A)\) 表示完全落在 \(A\) 中的仿射直线条数。因此有
$$X(A)^4=\sum_{(\ell_1,\ell_2,\ell_3,\ell_4)} \mathbf{1}_{\ell_1\cup\ell_2\cup\ell_3\cup\ell_4\subseteq A},$$
其中求和对象是所有有序的 SET 直线四元组。再对所有 \(|A|=n\) 的子集求和，就得到
$$F(n)=\sum_{(\ell_1,\ell_2,\ell_3,\ell_4)} \#\{A\subseteq D:\ |A|=n,\ \ell_1\cup\ell_2\cup\ell_3\cup\ell_4\subseteq A\}.$$
这一步是整个解法的核心视角转换：不再是“先选子集，再数其中的 SET”，而是“先选四条有序 SET，再数有多少个子集把它们都包含进去”。
对于一个有序四元组 \((\ell_1,\ell_2,\ell_3,\ell_4)\)，记
$$m=\left|\ell_1\cup\ell_2\cup\ell_3\cup\ell_4\right|.$$
如果这四条直线的并集大小为 \(m\)，那么任何包含它们的 \(n\) 元子集，都只需要再从剩余的 \(81-m\) 个点里补选 \(n-m\) 个点。因此每个这样的四元组对 \(F(n)\) 的贡献都是
$$\binom{81-m}{n-m}.$$
于是定义直方图
$$N_m=\#\left\{(\ell_1,\ell_2,\ell_3,\ell_4):\left|\ell_1\cup\ell_2\cup\ell_3\cup\ell_4\right|=m\right\}.$$
由于每条直线只有 3 个点，四条直线的并集大小只能在 \(3\) 到 \(12\) 之间变化，所以
$$\boxed{F(n)=\sum_{m=3}^{12} N_m\binom{81-m}{n-m}.}$$
至此，原问题被压缩成一个有限几何计数问题：求出 \(N_3,N_4,\dots,N_{12}\) 这十个数。
如果直接枚举所有有序四元组，需要处理 \(L^4=1080^4\) 种情况。实现采用的办法是把每条直线编码成一个 81 位掩码，其中恰好有 3 位为 1。这样，多条直线的并集大小就等于这些掩码按位 OR 之后的 popcount。
真正的简化来自对称性：\(\mathbb F_3^4\) 的仿射自同构群可以把任意一条直线映到任意另一条直线，因此“并集大小的分布”与第一条直线具体选哪一条无关。于是可以固定一条参考直线 \(\ell_1\)，只枚举所有有序三元组 \((\ell_2,\ell_3,\ell_4)\)，把得到的并集大小记入直方图，最后再整体乘上 \(L=1080\)。
这样，主计算量就从 \(O(L^4)\) 降到了 \(O(L^3)\)，而且所有 \(N_m\) 的精确值都被完整保留下来。
当 \(n=3\) 时，一个 3 张牌的子集 \(A\) 要么本身就是一个 SET，要么不是。如果是，则 \(X(A)=1\)；如果不是，则 \(X(A)=0\)。因此 \(X(A)^4=X(A)\)，于是
$$F(3)=\sum_{\substack{A\subseteq D\\|A|=3}} X(A)=1080.$$
这正是实现里使用的第一个校验值。
同一个按并集大小分类的公式，也能解释为什么 \(m\) 只会落在 \(3\) 到 \(12\) 之间。如果四条有序直线其实完全相同，那么 \(m=3\)，每个四元组贡献 \(\binom{78}{n-3}\)。如果四条直线彼此完全不相交，那么 \(m=12\)，每个四元组贡献 \(\binom{69}{n-12}\)。其他所有重叠模式都对应中间的 \(m=4,5,\dots,11\)。
同一套直方图公式还给出第二个校验值
$$F(6)=159690960.$$
当这两个值都吻合时，就说明并集大小的统计已经足够可靠，可以继续计算目标值 \(F(12)\)。
C++、Python 和 Java 三个实现遵循的是同一套组合数学思路。首先列出 \(\mathbb F_3^4\) 的 81 个点。然后通过枚举点对、计算唯一的第三个点 \(w=-(u+v)\)、对三元组排序并去重的方式，把所有 SET 直线都生成出来，最终得到恰好 1080 条不同的直线。
接着，每条直线都被存成一个 81 位掩码。实现固定一条参考直线，遍历其余直线的所有有序三元组，计算 OR 并集后的 popcount，并把对应的并集大小计入直方图。最后整体乘上 1080，就得到全部 \(N_m\) 值。
最后一步用精确整数运算计算
$$F(n)=\sum_{m=3}^{12} N_m\binom{81-m}{n-m}.$$
C++ 和 Java 实现把外层一部分循环分配给多个线程。Python 实现则调用同样的编译后计数策略。三种实现还都会检查若干结构性事实，例如直线总数、每个点恰好落在 40 条直线上，以及校验值 \(F(3)\) 与 \(F(6)\)。
生成直线列表的代价相对较小，因为它只需要扫描无序点对，所以这一阶段由 \(O(81^2)\) 的工作量和去重开销控制。真正占主导的是固定第一条直线之后的直方图统计阶段，其时间复杂度为 \(O(L^3)\)，其中 \(L=1080\)。每一次迭代只需要常数次按位 OR 和 popcount 操作。
空间复杂度是 \(O(L)\)：只需为每条直线保存一个掩码，再加上一个很小的并集大小直方图。不需要按子集建立任何庞大的表。
81 карту игры SET удобно моделировать как 81 точку пространства \(D=\mathbb F_3^4\). Для любого подмножества \(A\subseteq D\) размера \(|A|=n\) обозначим через \(X(A)\) число SETов, целиком содержащихся в \(A\). В задаче вводится функция
$$F(n)=\sum_{\substack{A\subseteq D\\|A|=n}} X(A)^4$$
и требуется найти \(F(12)\), причем в качестве контрольных значений даны \(F(3)=1080\) и \(F(6)=159690960\). Решение не перебирает все \(\binom{81}{12}\) 12-элементных подмножеств. Вместо этого четвертая степень переписывается через упорядоченные четверки аффинных прямых, после чего такие четверки группируются по размеру их объединения.
У каждой карты SET есть четыре признака, и каждый признак принимает три значения. Поэтому естественным пространством становится \(\mathbb F_3^4\). В этой модели любой корректный SET - это ровно аффинная прямая из трех точек.
Каждое значение кодируется числом \(0\), \(1\) или \(2\). Тогда карта становится вектором из \(\mathbb F_3^4\). Три карты \(u,v,w\) образуют SET тогда и только тогда, когда в каждой координате значения либо все одинаковы, либо все различны. Над \(\mathbb F_3\) оба случая эквивалентны условию
$$u+v+w=0.$$
Значит, если заданы две карты, то третья определяется однозначно:
$$w=-(u+v).$$
Геометрически любой SET имеет вид
$$\{a,\ a+d,\ a+2d\},\qquad d\ne 0,$$
то есть является аффинной прямой. Число возможных направлений равно числу одномерных подпространств в \(\mathbb F_3^4\):
$$\frac{3^4-1}{3-1}=40.$$
Каждое направление разбивает 81 точку на \(81/3=27\) параллельных прямых, поэтому общее число SETов равно
$$L=40\cdot 27=1080.$$
Иначе говоря, каждая карта лежит ровно на \(40\) различных SETах.
Для любого \(A\subseteq D\) размера \(|A|=n\) величина \(X(A)\) считает аффинные прямые, целиком лежащие в \(A\). Следовательно,
$$X(A)^4=\sum_{(\ell_1,\ell_2,\ell_3,\ell_4)} \mathbf{1}_{\ell_1\cup\ell_2\cup\ell_3\cup\ell_4\subseteq A},$$
где сумма берется по упорядоченным четверкам SET-прямых. После суммирования по всем подмножествам \(A\) размера \(n\) получаем
$$F(n)=\sum_{(\ell_1,\ell_2,\ell_3,\ell_4)} \#\{A\subseteq D:\ |A|=n,\ \ell_1\cup\ell_2\cup\ell_3\cup\ell_4\subseteq A\}.$$
Это и есть главный переход: вместо того чтобы сначала выбирать подмножество, а потом считать в нем SETы, мы сначала выбираем упорядоченные четверки SETов, а потом считаем, сколько подмножеств их содержит.
Для упорядоченной четверки \((\ell_1,\ell_2,\ell_3,\ell_4)\) положим
$$m=\left|\ell_1\cup\ell_2\cup\ell_3\cup\ell_4\right|.$$
Если размер объединения равен \(m\), то любое \(n\)-элементное подмножество, содержащее это объединение, получается выбором еще \(n-m\) точек из оставшихся \(81-m\). Значит, каждая такая четверка вносит вклад
$$\binom{81-m}{n-m}$$
в \(F(n)\). Введем числа
$$N_m=\#\left\{(\ell_1,\ell_2,\ell_3,\ell_4):\left|\ell_1\cup\ell_2\cup\ell_3\cup\ell_4\right|=m\right\}.$$
Поскольку каждая прямая содержит 3 точки, возможные размеры объединения лежат только в диапазоне от \(3\) до \(12\). Поэтому
$$\boxed{F(n)=\sum_{m=3}^{12} N_m\binom{81-m}{n-m}.}$$
Тем самым исходная задача свелась к нахождению десяти значений \(N_3,\dots,N_{12}\).
Наивный перебор всех упорядоченных четверок потребовал бы \(L^4=1080^4\) случаев. Реализация избегает этого, представляя каждую прямую 81-битной маской с тремя единичными битами. Тогда размер объединения нескольких прямых равен popcount от их побитового OR.
Главное упрощение дает симметрия: группа аффинных автоморфизмов пространства \(\mathbb F_3^4\) переводит любую прямую в любую другую. Значит, распределение размеров объединения не зависит от того, какая первая прямая выбрана. Можно зафиксировать одну эталонную прямую \(\ell_1\), перебрать все упорядоченные тройки \((\ell_2,\ell_3,\ell_4)\), собрать гистограмму размеров объединения и затем умножить ее на \(L=1080\).
Тем самым основная работа уменьшается с \(O(L^4)\) до \(O(L^3)\), при этом точные значения всех \(N_m\) сохраняются.
Если \(n=3\), то любое 3-элементное подмножество \(A\) либо само является SETом, либо нет. В первом случае \(X(A)=1\), во втором \(X(A)=0\). Поэтому \(X(A)^4=X(A)\), и значит
$$F(3)=\sum_{\substack{A\subseteq D\\|A|=3}} X(A)=1080.$$
Это в точности первый контроль, который использует реализация.
Та же формула по размерам объединения объясняет и диапазон возможных \(m\). Если все четыре упорядоченные прямые совпадают, то \(m=3\), и каждая такая четверка дает вклад \(\binom{78}{n-3}\). Если четыре прямые попарно не пересекаются, то \(m=12\), и вклад равен \(\binom{69}{n-12}\). Все остальные схемы пересечений попадают в промежуточные корзины \(m=4,5,\dots,11\).
Второй контроль, получаемый из той же гистограммной формулы, равен
$$F(6)=159690960.$$
Совпадение обоих значений служит надежной проверкой правильности подсчета перед вычислением целевого случая \(n=12\).
Реализации на C++, Python и Java следуют одному и тому же комбинаторному плану. Сначала они перечисляют 81 точку пространства \(\mathbb F_3^4\). Затем все SETы строятся через пары точек: для пары вычисляется единственная третья точка \(w=-(u+v)\), тройка сортируется, а повторы удаляются. В итоге получается ровно 1080 различных прямых.
После этого каждая прямая хранится как 81-битная маска. Реализация фиксирует одну опорную прямую, перебирает все упорядоченные тройки остальных прямых, вычисляет popcount от OR-объединения и увеличивает соответствующую ячейку гистограммы. После умножения на 1080 получаются все коэффициенты \(N_m\).
На последнем этапе вычисляется
$$F(n)=\sum_{m=3}^{12} N_m\binom{81-m}{n-m}$$
с использованием точной целочисленной арифметики. Версии на C++ и Java распараллеливают внешнюю часть тройного перебора по потокам. Версия на Python использует ту же скомпилированную стратегию подсчета. Все реализации также проверяют структурные факты: общее число прямых, 40 прямых через каждую точку и контрольные значения \(F(3)\) и \(F(6)\).
Построение списка прямых относительно дешево: оно основано на переборе неупорядоченных пар точек, поэтому эта стадия ограничена величиной порядка \(O(81^2)\) плюс удаление повторов. Главная стоимость приходится на гистограмму при фиксированной первой прямой, что дает \(O(L^3)\) времени при \(L=1080\). Каждая итерация выполняет только постоянное число операций OR и popcount.
Память имеет порядок \(O(L)\): хранится одна битовая маска на прямую и небольшой массив для гистограммы размеров объединения. Никаких больших таблиц по подмножествам не требуется.
يمكن تمثيل بطاقات SET البالغ عددها 81 على أنها النقاط الـ 81 في الفضاء \(D=\mathbb F_3^4\). ولكل مجموعة جزئية \(A\subseteq D\) حجمها \(|A|=n\)، نرمز بـ \(X(A)\) إلى عدد مجموعات SET الموجودة بالكامل داخل \(A\). تعرف المسألة الدالة
$$F(n)=\sum_{\substack{A\subseteq D\\|A|=n}} X(A)^4$$
وتطلب حساب \(F(12)\)، مع قيمتي تحقق هما \(F(3)=1080\) و \(F(6)=159690960\). الحل المطبق لا يعدد جميع المجموعات الممكنة وعددها \(\binom{81}{12}\)، بل يعيد كتابة اللحظة الرابعة بدلالة رباعيات مرتبة من المستقيمات الأفينية، ثم يعد هذه الرباعيات بحسب حجم اتحادها.
لكل بطاقة في SET أربع صفات، ولكل صفة ثلاث قيم ممكنة، لذلك فإن \(\mathbb F_3^4\) هو النموذج الطبيعي للمسألة. وفي هذا النموذج، كل SET صحيح هو بالضبط مستقيم أفيني مكوَّن من ثلاث نقاط.
نرمز لكل قيمة من القيم الثلاث بالعدد \(0\) أو \(1\) أو \(2\). وعندها تصبح كل بطاقة متجهًا في \(\mathbb F_3^4\). وتشكل ثلاث بطاقات \(u,v,w\) مجموعة SET إذا وفقط إذا كانت القيم في كل إحداثي إما كلها متساوية أو كلها مختلفة. وفوق \(\mathbb F_3\) فإن الحالتين تكافئان الشرط
$$u+v+w=0.$$
لذلك إذا عرفت بطاقتان، فإن البطاقة الثالثة تتحدد بصورة وحيدة:
$$w=-(u+v).$$
هندسيًا، كل SET هو مستقيم أفيني من الشكل
$$\{a,\ a+d,\ a+2d\},\qquad d\ne 0.$$
وعدد الاتجاهات الممكنة يساوي عدد الفضاءات الجزئية أحادية البعد في \(\mathbb F_3^4\):
$$\frac{3^4-1}{3-1}=40.$$
وكل اتجاه يقسم النقاط الـ 81 إلى \(81/3=27\) مستقيمًا متوازيًا، ولذلك فإن العدد الكلي لمجموعات SET هو
$$L=40\cdot 27=1080.$$
وبصورة مكافئة، تنتمي كل بطاقة إلى \(40\) مجموعة SET بالضبط.
لكل \(A\subseteq D\) بحيث \(|A|=n\)، فإن \(X(A)\) يعد المستقيمات الأفينية الموجودة بالكامل داخل \(A\). ومن ثم
$$X(A)^4=\sum_{(\ell_1,\ell_2,\ell_3,\ell_4)} \mathbf{1}_{\ell_1\cup\ell_2\cup\ell_3\cup\ell_4\subseteq A},$$
حيث يكون الجمع على رباعيات مرتبة من مستقيمات SET. وإذا جمعنا بعد ذلك على جميع المجموعات \(A\) ذات الحجم \(n\)، حصلنا على
$$F(n)=\sum_{(\ell_1,\ell_2,\ell_3,\ell_4)} \#\{A\subseteq D:\ |A|=n,\ \ell_1\cup\ell_2\cup\ell_3\cup\ell_4\subseteq A\}.$$
وهذا هو التحويل الأساسي في الحل: بدل أن نختار المجموعة الجزئية أولًا ثم نعد ما فيها من SETات، نختار أولًا رباعيات SET المرتبة ثم نعد كم مجموعة جزئية تحتويها.
لرباعية مرتبة \((\ell_1,\ell_2,\ell_3,\ell_4)\) نكتب
$$m=\left|\ell_1\cup\ell_2\cup\ell_3\cup\ell_4\right|.$$
إذا كان حجم الاتحاد يساوي \(m\)، فإن أي مجموعة من \(n\) بطاقة تحتوي هذا الاتحاد تتكون باختيار \(n-m\) بطاقة إضافية من بين \(81-m\) بطاقة الباقية. لذلك فإن مساهمة كل رباعية من هذا النوع هي
$$\binom{81-m}{n-m}.$$
ونعرّف الآن
$$N_m=\#\left\{(\ell_1,\ell_2,\ell_3,\ell_4):\left|\ell_1\cup\ell_2\cup\ell_3\cup\ell_4\right|=m\right\}.$$
وبما أن كل مستقيم يحوي ثلاث نقاط فقط، فإن \(m\) لا يمكن أن يأخذ إلا القيم من \(3\) إلى \(12\). وعليه نحصل على
$$\boxed{F(n)=\sum_{m=3}^{12} N_m\binom{81-m}{n-m}.}$$
وهكذا تصبح المسألة الأصلية مسألة عدّ في هندسة منتهية: إيجاد القيم العشر \(N_3,N_4,\dots,N_{12}\).
العد المباشر لجميع الرباعيات المرتبة يحتاج إلى \(L^4=1080^4\) حالة. وتتجنب التطبيقات ذلك بتمثيل كل مستقيم بقناع مكوَّن من 81 بت مع ثلاث بتات فعالة فقط. وعندها يصبح حجم اتحاد عدة مستقيمات هو popcount للناتج OR بين هذه الأقنعة.
وجوهر التبسيط يأتي من التناظر: زمرة التحويلات الأفينية للفضاء \(\mathbb F_3^4\) ترسل أي مستقيم إلى أي مستقيم آخر. لذلك فإن توزيع أحجام الاتحادات لا يعتمد على اختيار المستقيم الأول. ومن ثم يمكن تثبيت مستقيم مرجعي واحد \(\ell_1\)، ثم تعداد جميع الثلاثيات المرتبة \((\ell_2,\ell_3,\ell_4)\)، وتسجيل حجم الاتحاد الناتج، ثم ضرب المدرج التكراري كله في \(L=1080\) في النهاية.
وبهذا ينخفض العمل الغالب من \(O(L^4)\) إلى \(O(L^3)\)، مع الحفاظ الكامل على القيم الدقيقة لجميع \(N_m\).
عندما \(n=3\)، فإن أي مجموعة جزئية \(A\) من ثلاث بطاقات إما أن تكون SET بحد ذاتها أو لا تكون. في الحالة الأولى \(X(A)=1\)، وفي الثانية \(X(A)=0\). لذلك \(X(A)^4=X(A)\)، ومن ثم
$$F(3)=\sum_{\substack{A\subseteq D\\|A|=3}} X(A)=1080.$$
وهذه هي قيمة التحقق الأولى المستعملة في التنفيذ.
كما أن الصيغة نفسها القائمة على حجم الاتحاد تفسر مجال \(m\). فإذا كانت المستقيمات الأربعة المرتبة متطابقة تمامًا، فإن \(m=3\) وتكون مساهمة كل رباعية \(\binom{78}{n-3}\). وإذا كانت المستقيمات الأربعة متباينة تمامًا ولا تتقاطع، فإن \(m=12\) وتكون المساهمة \(\binom{69}{n-12}\). أما أنماط التداخل الأخرى كلها فتقع في الصناديق الوسطى \(m=4,5,\dots,11\).
وقيمة تحقق ثانية تنتج من نفس صيغة المدرج التكراري هي
$$F(6)=159690960.$$
وتطابق هاتين القيمتين يعطي ثقة قوية في صحة العدّ قبل تقييم الحالة المطلوبة \(n=12\).
تتبع تطبيقات C++ وPython وJava الخطة التوافقية نفسها. فهي تبدأ بتعداد النقاط الـ 81 في \(\mathbb F_3^4\)، ثم تولد كل SET عبر اختيار زوج من النقاط، وحساب النقطة الثالثة الوحيدة \(w=-(u+v)\)، وترتيب الثلاثية الناتجة، ثم حذف التكرارات. وبذلك نحصل على 1080 مستقيمًا مختلفًا بالضبط.
بعد ذلك يُخزَّن كل مستقيم على هيئة قناع من 81 بت. يثبت التنفيذ مستقيمًا مرجعيًا، ثم يمر على جميع الثلاثيات المرتبة من المستقيمات الأخرى، ويحسب popcount لاتحاد OR، ويزيد العداد الموافق لحجم هذا الاتحاد. وبعد الضرب في 1080 نحصل على جميع القيم \(N_m\).
وفي الخطوة الأخيرة يحسب التنفيذ
$$F(n)=\sum_{m=3}^{12} N_m\binom{81-m}{n-m}$$
باستخدام حساب صحيح دقيق. وتقوم نسختا C++ وJava بتوزيع الجزء الخارجي من المسح الثلاثي على عدة خيوط. أما نسخة Python فتستدعي الاستراتيجية المترجمة نفسها. كما تتحقق التطبيقات الثلاثة من حقائق بنيوية مثل العدد الكلي للمستقيمات، ومرور 40 مستقيمًا بكل نقطة، وقيمتي التحقق \(F(3)\) و\(F(6)\).
توليد قائمة المستقيمات ليس مكلفًا مقارنة بالمرحلة الرئيسية، لأنه يعتمد على مسح أزواج النقاط غير المرتبة، ولذلك تحده كلفة من رتبة \(O(81^2)\) مع حذف التكرار. أما المرحلة المسيطرة فهي عدّ المدرج التكراري بعد تثبيت المستقيم الأول، وزمنها \(O(L^3)\) عندما يكون \(L=1080\). وكل دورة لا تستخدم إلا عددًا ثابتًا من عمليات OR وpopcount.
أما الذاكرة فهي من رتبة \(O(L)\): قناع واحد لكل مستقيم ومدرج تكراري صغير لأحجام الاتحادات الممكنة. ولا توجد حاجة إلى أي جدول ضخم على مستوى المجموعات الجزئية.