We have two cubes, each carrying 6 distinct digits chosen from \(\{0,1,\dots,9\}\). By placing the cubes side by side, we want to display every two-digit square below 100: \(01, 04, 09, 16, 25, 36, 49, 64, 81\).
The cubes are unlabeled, so swapping them does not create a new arrangement. The only geometric subtlety is that a face marked 6 can be turned upside down and read as 9, and the same goes in the other direction. The task is therefore to count all unordered pairs of 6-digit cubes that satisfy those nine display constraints exactly.
The solution is an exact finite count. Once the digit-pair constraints are written correctly, the search space is so small that exhaustive enumeration is already the clean mathematical method.
Let \(U=\{0,1,\dots,9\}\). A single cube is a subset \(D\subseteq U\) with \(\lvert D\rvert=6\). Hence the number of possible cubes is
$$N_{\text{cube}}=\binom{10}{6}=210.$$
We do not distinguish the ordered pair \((D_1,D_2)\) from \((D_2,D_1)\), and identical cubes are allowed, so we are counting unordered pairs with repetition. That gives
$$N_{\text{pairs}}=\binom{210}{2}+210=\binom{211}{2}=22155.$$
That number is tiny: even before any optimization, checking every candidate pair is completely practical.
The implementations treat 6 and 9 as a single rotational class. If a cube contains either one, it can serve as both when we read a square number. It is convenient to encode that by replacing each cube \(D\) with its effective digit set
$$\widehat{D}=\begin{cases} D\cup\{6,9\}, & D\cap\{6,9\}\neq\varnothing,\\ D, & D\cap\{6,9\}=\varnothing. \end{cases}$$
This is the only nontrivial invariant in the problem. After taking the closure, every square check is just a membership question in \(\widehat{D}_1\) and \(\widehat{D}_2\).
Write the required squares as ordered digit pairs
$$P=\{(0,1),(0,4),(0,9),(1,6),(2,5),(3,6),(4,9),(6,4),(8,1)\}.$$
A pair of cubes is valid exactly when, for every \((a,b)\in P\), one cube can show \(a\) while the other shows \(b\). Because the cubes may be swapped, the condition is
$$\bigl(a\in\widehat{D}_1 \land b\in\widehat{D}_2\bigr)\ \lor\ \bigl(a\in\widehat{D}_2 \land b\in\widehat{D}_1\bigr).$$
There is a useful structural simplification. If we collapse 6 and 9 into a single class \(s\), then the distinct unordered requirements become
$$E=\bigl\{\{0,1\},\{0,4\},\{0,s\},\{1,s\},\{2,5\},\{3,s\},\{4,s\},\{1,8\}\bigr\},\qquad s=\{6,9\}.$$
So \(49\) and \(64\) are different square numbers, but after the 6/9 rule they impose the same underlying constraint: one cube must contribute 4 and the other must contribute a rotatable 6/9 face. The implementations keep the original list of nine squares, which is perfectly fine because the digit test already merges 6 and 9.
Take \(D_1=\{0,1,2,3,4,5\}\) and \(D_2=\{0,1,2,6,7,8\}\). Since \(D_2\) contains 6, its effective set is \(\widehat{D}_2=\{0,1,2,6,7,8,9\}\).
Now check the required squares. \(01\) is immediate from \(0\in D_1\) and \(1\in D_2\). \(04\) works after swapping the cubes: use 4 from the first cube and 0 from the second. \(09\) works because the second cube's 6 also acts as 9. \(16\) and \(36\) use the same 6/9 face together with 1 and 3 from the first cube. \(25\) works by taking 2 from the second cube and 5 from the first. Both \(49\) and \(64\) are satisfied by 4 on the first cube and 6/9 on the second. Finally, \(81\) uses 8 from the second cube and 1 from the first. So this pair is valid.
Nothing in the actual mathematics suggests a deeper recurrence or a closed-form count. Once the problem is reduced to 22155 unordered cube pairs and 9 constant-size tests per pair, an exhaustive count is not a fallback; it is the natural exact solution. The code therefore does the mathematically simplest thing: generate every admissible cube, test every unordered pair, and count the successes.
The Python implementation generates all 6-element digit choices directly as combinations. The C++ and Java implementations represent a cube as a 10-bit mask and scan all 1024 masks, keeping exactly those with 6 set bits. Both approaches produce the same 210 candidate cubes.
After the candidate list is built, the outer loop selects the first cube and the inner loop starts at the same index, so each unordered pair is visited once and identical cube pairs are included. For each pair, the implementation checks the nine required square pairs one by one using the 6/9-aware digit test. The pair is counted only if every square passes.
In C++ and Java, digit membership is a bit operation on the mask, with a special case that treats a request for 6 or 9 as “does the mask contain either one?”. In Python, each cube is a fixed-length tuple and membership is tested directly. The representations differ, but the logical predicate is identical in all three languages.
Generating the 210 cubes costs \(O\!\left(\binom{10}{6}\right)\) conceptually, or \(O(2^{10})\) in the bitmask implementations; either way it is tiny. The main work is the unordered pair loop:
$$\binom{210+1}{2}=22155$$
candidate pairs, with 9 square checks for each one. So the total number of square tests is
$$22155\times 9 = 199395.$$
That is effectively constant time for this problem. The memory usage is \(O(210)\) for the stored cube list, plus negligible overhead for the fixed square table.
Wir haben zwei Würfel, die jeweils 6 verschiedene Ziffern aus \(\{0,1,\dots,9\}\) tragen. Legt man die beiden Würfel nebeneinander, sollen damit alle zweistelligen Quadratzahlen unter 100 dargestellt werden: \(01, 04, 09, 16, 25, 36, 49, 64, 81\).
Die Würfel sind nicht beschriftet, daher erzeugt ein Tausch der beiden Würfel keine neue Anordnung. Die einzige geometrische Feinheit ist, dass eine 6 durch Drehen auch als 9 gelesen werden kann und umgekehrt. Gesucht ist also die Anzahl aller ungeordneten Paare von 6-Ziffern-Würfeln, die diese neun Bedingungen genau erfüllen.
Die Lösung ist eine exakte endliche Zählung. Sobald man die Ziffernpaare korrekt als Bedingungen formuliert, ist der Suchraum so klein, dass vollständige Enumeration bereits die sauberste mathematische Methode ist.
Sei \(U=\{0,1,\dots,9\}\). Ein einzelner Würfel ist eine Teilmenge \(D\subseteq U\) mit \(\lvert D\rvert=6\). Daher gibt es insgesamt
$$N_{\text{cube}}=\binom{10}{6}=210$$
mögliche Würfel. Die geordneten Paare \((D_1,D_2)\) und \((D_2,D_1)\) werden nicht unterschieden, und zwei identische Würfel sind erlaubt. Also zählen wir ungeordnete Paare mit Wiederholung:
$$N_{\text{pairs}}=\binom{210}{2}+210=\binom{211}{2}=22155.$$
Diese Zahl ist sehr klein. Schon ohne ausgefeilte Optimierung ist es vollkommen praktikabel, jedes Kandidatenpaar zu testen.
Die Implementierungen behandeln 6 und 9 als eine gemeinsame Rotationsklasse. Enthält ein Würfel eine der beiden Ziffern, kann er beim Lesen einer Quadratzahl beide darstellen. Zweckmäßig ersetzt man deshalb jeden Würfel \(D\) durch seine effektive Ziffernmenge
$$\widehat{D}=\begin{cases} D\cup\{6,9\}, & D\cap\{6,9\}\neq\varnothing,\\ D, & D\cap\{6,9\}=\varnothing. \end{cases}$$
Das ist die zentrale Invariante des Problems. Nach diesem Abschluss ist jede Quadratprüfung nur noch eine einfache Zugehörigkeitsfrage in \(\widehat{D}_1\) und \(\widehat{D}_2\).
Schreibe die geforderten Quadrate als geordnete Ziffernpaare
$$P=\{(0,1),(0,4),(0,9),(1,6),(2,5),(3,6),(4,9),(6,4),(8,1)\}.$$
Ein Würfelpaar ist genau dann gültig, wenn für jedes \((a,b)\in P\) ein Würfel die Ziffer \(a\) und der andere die Ziffer \(b\) liefern kann. Weil die Würfel vertauschbar sind, lautet die Bedingung
$$\bigl(a\in\widehat{D}_1 \land b\in\widehat{D}_2\bigr)\ \lor\ \bigl(a\in\widehat{D}_2 \land b\in\widehat{D}_1\bigr).$$
Strukturell kann man das noch vereinfachen. Fasst man 6 und 9 zu einer einzigen Klasse \(s\) zusammen, dann bleiben als verschiedene ungeordnete Anforderungen
$$E=\bigl\{\{0,1\},\{0,4\},\{0,s\},\{1,s\},\{2,5\},\{3,s\},\{4,s\},\{1,8\}\bigr\},\qquad s=\{6,9\}.$$
Damit sieht man sofort: \(49\) und \(64\) sind zwar verschiedene Quadratzahlen, erzwingen nach der 6/9-Regel aber dieselbe Grundbedingung, nämlich 4 auf einem Würfel und eine drehbare 6/9-Fläche auf dem anderen. Die Implementierungen behalten trotzdem die ursprüngliche Liste von neun Quadraten bei; das ist korrekt, weil der Zifferntest 6 und 9 bereits zusammenführt.
Nehmen wir \(D_1=\{0,1,2,3,4,5\}\) und \(D_2=\{0,1,2,6,7,8\}\). Da \(D_2\) die 6 enthält, ist \(\widehat{D}_2=\{0,1,2,6,7,8,9\}\).
Nun prüfen wir die geforderten Quadrate. \(01\) ist direkt möglich durch \(0\in D_1\) und \(1\in D_2\). \(04\) funktioniert nach Vertauschung der Rollen: 4 vom ersten Würfel, 0 vom zweiten. \(09\) klappt, weil die 6 des zweiten Würfels zugleich als 9 gelesen werden darf. \(16\) und \(36\) benutzen dieselbe 6/9-Fläche zusammen mit 1 und 3 des ersten Würfels. \(25\) erhält man mit 2 vom zweiten und 5 vom ersten Würfel. Sowohl \(49\) als auch \(64\) werden durch 4 auf dem ersten und 6/9 auf dem zweiten erfüllt. Schließlich liefert \(81\) die Kombination 8 vom zweiten und 1 vom ersten Würfel. Dieses Paar ist also gültig.
Die eigentliche Mathematik deutet weder auf eine tiefere Rekursion noch auf eine geschlossene Formel hin. Ist das Problem einmal auf 22155 ungeordnete Würfelpaare und 9 Prüfungen konstanter Größe pro Paar reduziert, dann ist vollständiges Durchzählen kein Notbehelf, sondern die natürliche exakte Lösung. Genau das tun die Programme: alle zulässigen Würfel erzeugen, jedes ungeordnete Paar testen und die Erfolge zählen.
Die Python-Implementierung erzeugt alle 6-elementigen Ziffernwahlmöglichkeiten direkt als Kombinationen. Die C++- und Java-Implementierungen repräsentieren einen Würfel als 10-Bit-Maske und durchsuchen alle 1024 Masken, behalten aber nur diejenigen mit genau 6 gesetzten Bits. Beide Wege liefern dieselben 210 Kandidatenwürfel.
Nachdem die Kandidatenliste aufgebaut ist, wählt die äußere Schleife den ersten Würfel und die innere Schleife beginnt beim selben Index. So wird jedes ungeordnete Paar genau einmal besucht, und identische Würfelpaare bleiben eingeschlossen. Für jedes Paar prüft die Implementierung nacheinander die neun Quadratpaare mit dem 6/9-bewussten Zifferntest. Gezählt wird nur, wenn alle neun Bedingungen erfüllt sind.
In C++ und Java ist die Ziffernzugehörigkeit eine Bitoperation auf der Maske, ergänzt um den Spezialfall, dass eine Anfrage nach 6 oder 9 bedeutet: „Ist eine der beiden Ziffern vorhanden?“ In Python wird jeder Würfel als Tupel fester Länge gespeichert und direkt durchsucht. Die Darstellung unterscheidet sich, aber das logische Prädikat ist in allen drei Sprachen identisch.
Die Erzeugung der 210 Würfel kostet begrifflich \(O\!\left(\binom{10}{6}\right)\), beziehungsweise \(O(2^{10})\) in den Bitmasken-Implementierungen; beides ist verschwindend klein. Die Hauptarbeit steckt in der Schleife über die ungeordneten Paare:
$$\binom{210+1}{2}=22155$$
Kandidatenpaare mit jeweils 9 Quadratprüfungen. Die Gesamtzahl der Quadratprüfungen ist also
$$22155\times 9 = 199395.$$
Für dieses Problem ist das praktisch konstante Laufzeit. Der Speicherbedarf beträgt \(O(210)\) für die gespeicherte Würfelliste, plus vernachlässigbaren Zusatzaufwand für die feste Tabelle der Quadrate.
Her biri \(\{0,1,\dots,9\}\) kümesinden seçilmiş 6 farklı rakam taşıyan iki küpümüz var. Bu iki küp yan yana getirilerek 100'den küçük tüm iki basamaklı kareler gösterilmek isteniyor: \(01, 04, 09, 16, 25, 36, 49, 64, 81\).
Küpler etiketli değildir; dolayısıyla ikisini yer değiştirmek yeni bir düzen oluşturmaz. Tek geometrik incelik, 6 yazılı bir yüzün ters çevrilerek 9 gibi okunabilmesi ve bunun tersinin de geçerli olmasıdır. Bu nedenle problem, bu dokuz gösterim koşulunu tam olarak sağlayan tüm sırasız 6-rakamlı küp çiftlerini saymaktır.
Çözüm tam ve sonlu bir sayımdır. Rakam çiftlerini doğru biçimde koşullara dönüştürdüğümüzde arama uzayı o kadar küçülür ki tam tarama zaten en temiz matematiksel yöntem haline gelir.
\(U=\{0,1,\dots,9\}\) olsun. Tek bir küp, \(\lvert D\rvert=6\) olacak şekilde \(D\subseteq U\) alt kümesidir. Dolayısıyla mümkün küp sayısı
$$N_{\text{cube}}=\binom{10}{6}=210$$
olur. \((D_1,D_2)\) ve \((D_2,D_1)\) sıralı çiftlerini farklı saymıyoruz; ayrıca iki küpün aynı olması da serbest. Bu yüzden tekrar içeren sırasız çiftleri sayıyoruz:
$$N_{\text{pairs}}=\binom{210}{2}+210=\binom{211}{2}=22155.$$
Bu sayı çok küçüktür. En basit haliyle bile bütün aday çiftleri tek tek denemek tamamen uygulanabilir durumdadır.
Uygulamalar 6 ile 9'u tek bir dönme sınıfı gibi ele alır. Bir küp bu iki rakamdan birini içeriyorsa, kare sayıyı okurken ikisini de temsil edebilir. Bunu ifade etmenin en uygun yolu, her \(D\) küpünü etkili rakam kümesiyle değiştirmektir:
$$\widehat{D}=\begin{cases} D\cup\{6,9\}, & D\cap\{6,9\}\neq\varnothing,\\ D, & D\cap\{6,9\}=\varnothing. \end{cases}$$
Problemin tek ciddi değişmezi budur. Bu kapanış alındıktan sonra her kare kontrolü yalnızca \(\widehat{D}_1\) ve \(\widehat{D}_2\) içinde üyelik testi haline gelir.
Gerekli kareleri sıralı rakam çiftleri olarak yazalım:
$$P=\{(0,1),(0,4),(0,9),(1,6),(2,5),(3,6),(4,9),(6,4),(8,1)\}.$$
Bir küp çifti, ancak ve ancak her \((a,b)\in P\) için bir küp \(a\) rakamını, diğer küp de \(b\) rakamını gösterebiliyorsa geçerlidir. Küpler yer değiştirebildiği için koşul şu olur:
$$\bigl(a\in\widehat{D}_1 \land b\in\widehat{D}_2\bigr)\ \lor\ \bigl(a\in\widehat{D}_2 \land b\in\widehat{D}_1\bigr).$$
Yapısal açıdan bir sadeleşme daha vardır. 6 ile 9'u tek bir \(s\) sınıfına indirgersek, farklı sırasız gereksinimler
$$E=\bigl\{\{0,1\},\{0,4\},\{0,s\},\{1,s\},\{2,5\},\{3,s\},\{4,s\},\{1,8\}\bigr\},\qquad s=\{6,9\}$$
şeklinde kalır. Böylece \(49\) ile \(64\)'ün farklı kareler olmasına rağmen 6/9 kuralından sonra aynı temel koşulu dayattığı görülür: bir küpte 4, ötekinde döndürülebilir 6/9 yüzü bulunmalıdır. Uygulamalar yine de özgün dokuz kare listesini korur; bu tamamen doğrudur, çünkü rakam testi zaten 6 ile 9'u birleştirmektedir.
\(D_1=\{0,1,2,3,4,5\}\) ve \(D_2=\{0,1,2,6,7,8\}\) alalım. \(D_2\) küpü 6 içerdiği için etkili kümesi \(\widehat{D}_2=\{0,1,2,6,7,8,9\}\) olur.
Şimdi gerekli kareleri kontrol edelim. \(01\), \(0\in D_1\) ve \(1\in D_2\) ile hemen sağlanır. \(04\), roller ters çevrilerek elde edilir: ilk küpten 4, ikinciden 0 alınır. \(09\), ikinci küpteki 6'nın 9 gibi de okunabilmesi sayesinde mümkündür. \(16\) ve \(36\), ilk küpteki 1 ve 3 ile ikinci küpteki aynı 6/9 yüzünü kullanır. \(25\), ikinci küpten 2 ve ilk küpten 5 alınarak kurulur. Hem \(49\) hem de \(64\), ilk küpteki 4 ve ikinci küpteki 6/9 ile sağlanır. Son olarak \(81\), ikinci küpteki 8 ile ilk küpteki 1'i kullanır. Dolayısıyla bu çift geçerlidir.
Problemin gerçek matematiği daha derin bir özyineleme ya da kapalı formül işareti vermez. Problem 22155 sırasız küp çifti ve çift başına 9 sabit boyutlu test düzeyine indirildiğinde, tam tarama bir yedek çözüm değil, doğal kesin çözümdür. Kod da tam olarak bunu yapar: tüm uygun küpleri üretir, her sırasız çifti test eder ve başarılı olanları sayar.
Python uygulaması tüm 6 elemanlı rakam seçimlerini doğrudan kombinasyonlar olarak üretir. C++ ve Java uygulamaları ise bir küpü 10 bitlik bir maske olarak temsil eder ve 1024 maskenin tamamını tarayıp yalnızca 6 biti açık olanları saklar. Her iki yaklaşım da aynı 210 aday küpü üretir.
Aday liste kurulduktan sonra dış döngü ilk küpü seçer, iç döngü ise aynı indisten başlar. Böylece her sırasız çift tam bir kez ziyaret edilir ve iki küpün aynı olduğu durumlar da sayımda kalır. Her çift için uygulama, 6/9 duyarlı rakam testiyle dokuz kare çiftini sırayla sınar. Yalnızca dokuz koşulun tamamı geçtiğinde sayaç artırılır.
C++ ve Java'da bir rakamın varlığı maskede bit işlemiyle sorgulanır; 6 ya da 9 istenirse “ikiden biri var mı?” biçimindeki özel durum uygulanır. Python'da her küp sabit uzunluklu bir demet olarak tutulur ve üyelik doğrudan sınanır. Temsil farklı olsa da üç dilde kullanılan mantıksal koşul aynıdır.
210 küpün üretilmesi kavramsal olarak \(O\!\left(\binom{10}{6}\right)\), bit maskeli sürümlerde ise \(O(2^{10})\) maliyetlidir; her iki durumda da bu aşama çok küçüktür. Asıl iş, sırasız çift döngüsündedir:
$$\binom{210+1}{2}=22155$$
aday çift ve her biri için 9 kare testi vardır. Dolayısıyla toplam kare testi sayısı
$$22155\times 9 = 199395$$
olur. Bu problem için çalışma süresi fiilen sabittir. Bellek kullanımı, saklanan küp listesi için \(O(210)\), sabit kare tablosu için ise ihmal edilebilir ek yük kadardır.
Tenemos dos cubos, cada uno con 6 dígitos distintos elegidos de \(\{0,1,\dots,9\}\). Al colocarlos uno al lado del otro, queremos poder mostrar todos los cuadrados de dos cifras menores que 100: \(01, 04, 09, 16, 25, 36, 49, 64, 81\).
Los cubos no están etiquetados, de modo que intercambiarlos no produce una disposición nueva. La única sutileza geométrica es que una cara marcada con 6 puede girarse y leerse como 9, y lo mismo vale en sentido contrario. Por tanto, el problema consiste en contar todos los pares no ordenados de cubos de 6 dígitos que satisfacen exactamente esas nueve restricciones.
La solución es un conteo exacto y finito. Una vez que las restricciones se escriben correctamente como pares de dígitos, el espacio de búsqueda es tan pequeño que la enumeración exhaustiva ya es el método matemático natural.
Sea \(U=\{0,1,\dots,9\}\). Un cubo individual es un subconjunto \(D\subseteq U\) con \(\lvert D\rvert=6\). Por tanto, el número de cubos posibles es
$$N_{\text{cube}}=\binom{10}{6}=210.$$
No distinguimos el par ordenado \((D_1,D_2)\) del par \((D_2,D_1)\), y además se permiten dos cubos idénticos. Así que estamos contando pares no ordenados con repetición:
$$N_{\text{pairs}}=\binom{210}{2}+210=\binom{211}{2}=22155.$$
Ese número es muy pequeño. Incluso sin optimizaciones sofisticadas, revisar todos los pares candidatos es completamente factible.
Las implementaciones tratan 6 y 9 como una misma clase rotacional. Si un cubo contiene uno de esos dígitos, al leer un cuadrado puede servir para ambos. Es conveniente codificar esto reemplazando cada cubo \(D\) por su conjunto efectivo de dígitos
$$\widehat{D}=\begin{cases} D\cup\{6,9\}, & D\cap\{6,9\}\neq\varnothing,\\ D, & D\cap\{6,9\}=\varnothing. \end{cases}$$
Éste es el único invariante realmente delicado del problema. Después de aplicar el cierre, cada comprobación de un cuadrado se reduce a una simple prueba de pertenencia en \(\widehat{D}_1\) y \(\widehat{D}_2\).
Escribamos los cuadrados requeridos como pares ordenados de dígitos:
$$P=\{(0,1),(0,4),(0,9),(1,6),(2,5),(3,6),(4,9),(6,4),(8,1)\}.$$
Un par de cubos es válido exactamente cuando, para todo \((a,b)\in P\), un cubo puede mostrar \(a\) y el otro puede mostrar \(b\). Como los cubos se pueden intercambiar, la condición es
$$\bigl(a\in\widehat{D}_1 \land b\in\widehat{D}_2\bigr)\ \lor\ \bigl(a\in\widehat{D}_2 \land b\in\widehat{D}_1\bigr).$$
Hay una simplificación estructural útil. Si comprimimos 6 y 9 en una sola clase \(s\), entonces las restricciones no ordenadas distintas pasan a ser
$$E=\bigl\{\{0,1\},\{0,4\},\{0,s\},\{1,s\},\{2,5\},\{3,s\},\{4,s\},\{1,8\}\bigr\},\qquad s=\{6,9\}.$$
Esto explica por qué \(49\) y \(64\) son cuadrados diferentes pero, después de aplicar la regla 6/9, imponen la misma condición de fondo: un cubo debe aportar 4 y el otro una cara rotatoria 6/9. Las implementaciones conservan la lista original de nueve cuadrados, y eso sigue siendo correcto porque la prueba de dígitos ya fusiona 6 y 9.
Tomemos \(D_1=\{0,1,2,3,4,5\}\) y \(D_2=\{0,1,2,6,7,8\}\). Como \(D_2\) contiene 6, su conjunto efectivo es \(\widehat{D}_2=\{0,1,2,6,7,8,9\}\).
Ahora comprobamos los cuadrados requeridos. \(01\) es inmediato con \(0\in D_1\) y \(1\in D_2\). \(04\) funciona al intercambiar los papeles de los cubos: 4 del primero y 0 del segundo. \(09\) funciona porque el 6 del segundo cubo también cuenta como 9. \(16\) y \(36\) usan esa misma cara 6/9 junto con 1 y 3 del primer cubo. \(25\) se obtiene tomando 2 del segundo cubo y 5 del primero. Tanto \(49\) como \(64\) quedan cubiertos por 4 en el primer cubo y 6/9 en el segundo. Finalmente, \(81\) usa 8 del segundo cubo y 1 del primero. Por tanto, este par es válido.
La matemática real del problema no sugiere una recurrencia más profunda ni una fórmula cerrada útil. Cuando todo se reduce a 22155 pares no ordenados y a 9 pruebas de tamaño constante por par, el conteo exhaustivo no es una solución de emergencia: es la solución exacta natural. Por eso el código hace exactamente eso: generar todos los cubos admisibles, probar cada par no ordenado y contar los éxitos.
La implementación en Python genera directamente todas las elecciones de 6 dígitos como combinaciones. Las implementaciones en C++ y Java representan un cubo como una máscara de 10 bits y recorren las 1024 máscaras posibles, quedándose sólo con las que tienen 6 bits encendidos. Ambos enfoques producen los mismos 210 cubos candidatos.
Una vez construida la lista de candidatos, el bucle exterior elige el primer cubo y el interior empieza en ese mismo índice. Así, cada par no ordenado se visita una sola vez y también se incluyen los pares de cubos idénticos. Para cada par, la implementación verifica uno a uno los nueve pares de dígitos requeridos usando la prueba de pertenencia adaptada a la equivalencia 6/9. El contador sólo aumenta si las nueve comprobaciones son satisfactorias.
En C++ y Java, la pertenencia de un dígito se decide con una operación de bits sobre la máscara, con el caso especial de que pedir 6 o 9 significa “¿está presente alguno de los dos?”. En Python, cada cubo es una tupla de longitud fija y la pertenencia se comprueba de forma directa. La representación cambia, pero el predicado lógico es el mismo en los tres lenguajes.
Generar los 210 cubos cuesta conceptualmente \(O\!\left(\binom{10}{6}\right)\), o bien \(O(2^{10})\) en las versiones con máscaras de bits; en ambos casos es un coste diminuto. El trabajo principal está en el bucle sobre pares no ordenados:
$$\binom{210+1}{2}=22155$$
pares candidatos, con 9 comprobaciones de cuadrados para cada uno. En consecuencia, el número total de pruebas de cuadrados es
$$22155\times 9 = 199395.$$
Para este problema, el tiempo es efectivamente constante. El uso de memoria es \(O(210)\) por la lista de cubos almacenada, más un coste despreciable por la tabla fija de cuadrados.
我们有两个立方体，每个立方体的 6 个面上放置的是从 \(\{0,1,\dots,9\}\) 中选出的 6 个不同数字。把两个立方体并排放在一起，希望它们能够显示 100 以下所有两位平方数：\(01, 04, 09, 16, 25, 36, 49, 64, 81\)。
这两个立方体本身没有先后顺序，所以交换左右位置不会形成新的方案。唯一需要特别处理的几何事实是：写着 6 的面旋转后可以当作 9，写着 9 的面也可以当作 6。于是题目就变成：满足这九个显示条件的无序立方体对一共有多少个。
这个问题本质上是一个精确的有限计数。只要把平方数要求写成正确的数字配对约束，搜索空间就会小到足以直接枚举，因此穷举本身就是最自然的数学解法，而不是权宜之计。
设 \(U=\{0,1,\dots,9\}\)。一个立方体对应于一个子集 \(D\subseteq U\)，并且满足 \(\lvert D\rvert=6\)。因此单个立方体的可能数目为
$$N_{\text{cube}}=\binom{10}{6}=210.$$
我们不区分有序对 \((D_1,D_2)\) 和 \((D_2,D_1)\)，而且允许两个立方体完全相同，所以这里数的是“允许重复的无序二元组”。于是候选对的总数是
$$N_{\text{pairs}}=\binom{210}{2}+210=\binom{211}{2}=22155.$$
这个数量非常小。哪怕不做任何复杂优化，把所有候选对逐一检查也完全可行。
三个实现都把 6 和 9 当成同一个旋转等价类来看待。只要一个立方体拥有其中任意一个数字，它在读平方数时就可以同时承担 6 和 9 的角色。最方便的写法是把每个立方体 \(D\) 换成它的“有效数字集”
$$\widehat{D}=\begin{cases} D\cup\{6,9\}, & D\cap\{6,9\}\neq\varnothing,\\ D, & D\cap\{6,9\}=\varnothing. \end{cases}$$
这就是本题唯一真正需要保留的结构性不变量。做完这个闭包之后，每个平方数的验证都只剩下 \(\widehat{D}_1\) 和 \(\widehat{D}_2\) 上的成员判断。
把所需的平方数写成有序数字对：
$$P=\{(0,1),(0,4),(0,9),(1,6),(2,5),(3,6),(4,9),(6,4),(8,1)\}.$$
一个立方体对恰好在什么条件下有效？答案是：对每个 \((a,b)\in P\)，必须能让一个立方体显示 \(a\)，另一个立方体显示 \(b\)。由于左右两个立方体可以互换，这个条件写成
$$\bigl(a\in\widehat{D}_1 \land b\in\widehat{D}_2\bigr)\ \lor\ \bigl(a\in\widehat{D}_2 \land b\in\widehat{D}_1\bigr).$$
从结构上看，还可以进一步压缩。若把 6 与 9 合并成一个类别 \(s\)，那么真正不同的无序要求只剩下
$$E=\bigl\{\{0,1\},\{0,4\},\{0,s\},\{1,s\},\{2,5\},\{3,s\},\{4,s\},\{1,8\}\bigr\},\qquad s=\{6,9\}.$$
这说明 \(49\) 与 \(64\) 虽然是两个不同的平方数，但在 6/9 互换规则生效后，它们施加的是同一种底层要求：一个立方体要提供 4，另一个立方体要提供可旋转读取的 6/9。实现代码仍然保留原始的九个平方数列表，这完全没有问题，因为数字判定本身已经把 6 和 9 合并处理了。
取 \(D_1=\{0,1,2,3,4,5\}\)，\(D_2=\{0,1,2,6,7,8\}\)。由于 \(D_2\) 含有 6，它的有效数字集就是 \(\widehat{D}_2=\{0,1,2,6,7,8,9\}\)。
现在逐项检查。\(01\) 很直接：\(0\in D_1\)、\(1\in D_2\)。\(04\) 通过交换左右角色成立：从第一个立方体取 4，从第二个立方体取 0。\(09\) 成立，因为第二个立方体上的 6 也可以当成 9。\(16\) 和 \(36\) 分别用第一个立方体上的 1、3 搭配第二个立方体上的同一个 6/9 面。\(25\) 可以取第二个立方体上的 2 和第一个立方体上的 5。\(49\) 与 \(64\) 都由“第一个立方体上的 4 + 第二个立方体上的 6/9”来满足。最后 \(81\) 使用第二个立方体上的 8 和第一个立方体上的 1。因此这一对立方体是有效的。
本题的真实数学结构并没有指向某个更深的递推式，也没有显露出一个比直接计数更好的闭式公式。一旦问题被压缩为 22155 个无序立方体对、每对只做 9 次常数规模的检查，那么穷举就不是“最后手段”，而是最自然的精确算法。因此实现采用的正是最朴素也最正确的策略：生成全部合法立方体，测试每个无序对，然后统计成功的个数。
Python 实现直接把所有 6 元数字选择生成为组合。C++ 和 Java 实现则把一个立方体表示为 10 位位掩码，枚举全部 1024 个掩码，只保留其中恰好有 6 个置位的那些。两种表示方式最终得到的都是同样的 210 个候选立方体。
候选列表建立之后，外层循环选第一个立方体，内层循环从同一个下标开始，因此每个无序对只会访问一次，而且相同立方体配对的情况也会被纳入统计。对每一对候选，实现都会依次检查九个平方数对应的数字对，并使用带有 6/9 等价规则的成员判断。只有九个条件全部通过，这一对才会被计数。
在 C++ 和 Java 中，数字是否出现由位掩码上的位运算决定；如果请求的是 6 或 9，则判定逻辑会变成“这两个数字中是否至少出现了一个”。在 Python 中，每个立方体被保存为一个定长元组，成员关系直接测试即可。表示方式不同，但三种语言实现的逻辑谓词完全相同。
生成 210 个立方体在概念上需要 \(O\!\left(\binom{10}{6}\right)\) 时间，在位掩码版本里则可以看作 \(O(2^{10})\)；无论哪种写法，代价都极小。真正的主成本来自无序配对循环：
$$\binom{210+1}{2}=22155$$
个候选对，而每个候选对要做 9 次平方数检查。因此总的检查次数是
$$22155\times 9 = 199395.$$
对这道题来说，这几乎就是常数时间。空间复杂度为 \(O(210)\)，用于保存候选立方体列表；额外的平方数表是固定大小，可以忽略不计。
У нас есть два кубика, на каждом из которых размещены 6 различных цифр из множества \(\{0,1,\dots,9\}\). Поставив кубики рядом, мы хотим уметь показывать все двузначные квадраты меньше 100: \(01, 04, 09, 16, 25, 36, 49, 64, 81\).
Сами кубики не различаются по порядку, поэтому перестановка левого и правого кубика не создает новую конфигурацию. Единственная геометрическая тонкость состоит в том, что грань с 6 можно перевернуть и читать как 9, и наоборот. Значит, нужно посчитать все неупорядоченные пары 6-цифровых кубиков, которые удовлетворяют этим девяти условиям показа.
Решение представляет собой точный конечный подсчет. Как только ограничения записаны в виде корректных пар цифр, пространство перебора оказывается настолько маленьким, что полный перебор уже является естественным математическим методом.
Пусть \(U=\{0,1,\dots,9\}\). Один кубик — это подмножество \(D\subseteq U\) мощности \(\lvert D\rvert=6\). Следовательно, число возможных кубиков равно
$$N_{\text{cube}}=\binom{10}{6}=210.$$
Мы не различаем упорядоченные пары \((D_1,D_2)\) и \((D_2,D_1)\), а также разрешаем два одинаковых кубика. Поэтому считаем неупорядоченные пары с повторениями:
$$N_{\text{pairs}}=\binom{210}{2}+210=\binom{211}{2}=22155.$$
Это очень малое число. Даже без специальных оптимизаций можно проверить каждый кандидат напрямую.
Все реализации рассматривают 6 и 9 как один вращательный класс. Если кубик содержит хотя бы одну из этих цифр, то при чтении квадрата он может изображать обе. Удобно заменить каждый кубик \(D\) его эффективным множеством цифр
$$\widehat{D}=\begin{cases} D\cup\{6,9\}, & D\cap\{6,9\}\neq\varnothing,\\ D, & D\cap\{6,9\}=\varnothing. \end{cases}$$
Это и есть главный инвариант задачи. После такого замыкания каждая проверка квадрата превращается в обычный вопрос о принадлежности в \(\widehat{D}_1\) и \(\widehat{D}_2\).
Запишем нужные квадраты в виде упорядоченных пар цифр:
$$P=\{(0,1),(0,4),(0,9),(1,6),(2,5),(3,6),(4,9),(6,4),(8,1)\}.$$
Пара кубиков является допустимой тогда и только тогда, когда для каждого \((a,b)\in P\) один кубик может показать \(a\), а другой — \(b\). Поскольку кубики можно менять местами, условие имеет вид
$$\bigl(a\in\widehat{D}_1 \land b\in\widehat{D}_2\bigr)\ \lor\ \bigl(a\in\widehat{D}_2 \land b\in\widehat{D}_1\bigr).$$
Есть и полезное структурное упрощение. Если объединить 6 и 9 в один класс \(s\), то различными неупорядоченными требованиями останутся
$$E=\bigl\{\{0,1\},\{0,4\},\{0,s\},\{1,s\},\{2,5\},\{3,s\},\{4,s\},\{1,8\}\bigr\},\qquad s=\{6,9\}.$$
Отсюда видно, что \(49\) и \(64\) — разные квадратные числа, но после правила 6/9 они налагают одно и то же базовое требование: один кубик должен содержать 4, а другой — поворачиваемую грань 6/9. В реализациях все равно хранится исходный список из девяти квадратов, и это корректно, потому что сама проверка цифры уже объединяет 6 и 9.
Возьмем \(D_1=\{0,1,2,3,4,5\}\) и \(D_2=\{0,1,2,6,7,8\}\). Так как \(D_2\) содержит 6, его эффективное множество равно \(\widehat{D}_2=\{0,1,2,6,7,8,9\}\).
Проверим нужные квадраты. \(01\) получается сразу из \(0\in D_1\) и \(1\in D_2\). Для \(04\) достаточно поменять роли кубиков: взять 4 с первого и 0 со второго. \(09\) работает, потому что 6 на втором кубике можно читать как 9. Числа \(16\) и \(36\) используют ту же грань 6/9 вместе с 1 и 3 на первом кубике. Для \(25\) берутся 2 со второго кубика и 5 с первого. И \(49\), и \(64\) покрываются сочетанием 4 на первом кубике и 6/9 на втором. Наконец, \(81\) дается цифрами 8 со второго и 1 с первого. Следовательно, такая пара кубиков допустима.
Математика самой задачи не подсказывает ни более глубокой рекурсии, ни полезной замкнутой формулы. После того как все сведено к 22155 неупорядоченным парам кубиков и 9 проверкам постоянного размера на пару, полный перебор перестает быть запасным вариантом и становится естественным точным решением. Именно это и делают программы: строят все допустимые кубики, проверяют каждую неупорядоченную пару и считают количество успешных случаев.
Реализация на Python сразу генерирует все выборы из 6 цифр как комбинации. Реализации на C++ и Java представляют кубик 10-битной маской и перебирают все 1024 маски, оставляя только те, у которых установлено ровно 6 битов. Оба способа дают один и тот же набор из 210 кандидатов.
После построения списка кандидатов внешний цикл выбирает первый кубик, а внутренний начинается с того же индекса. Поэтому каждая неупорядоченная пара посещается ровно один раз, и случаи с двумя одинаковыми кубиками тоже учитываются. Для каждой пары реализация последовательно проверяет девять нужных цифровых пар с помощью теста принадлежности, который знает про эквивалентность 6 и 9. Счетчик увеличивается только тогда, когда проходят все девять проверок.
В C++ и Java наличие цифры проверяется битовой операцией над маской; для запросов 6 и 9 используется специальное правило «присутствует ли хотя бы одна из этих двух цифр». В Python каждый кубик хранится как кортеж фиксированной длины, и принадлежность проверяется напрямую. Представления различаются, но логическое условие во всех трех языках одно и то же.
Построение 210 кубиков стоит концептуально \(O\!\left(\binom{10}{6}\right)\), либо \(O(2^{10})\) в версиях с битовыми масками; в любом случае это ничтожно мало. Основная работа находится в цикле по неупорядоченным парам:
$$\binom{210+1}{2}=22155$$
кандидатных пар, и для каждой пары выполняются 9 проверок квадратов. Поэтому общее число таких проверок равно
$$22155\times 9 = 199395.$$
Для этой задачи это фактически постоянное время работы. Память составляет \(O(210)\) на список кубиков, плюс пренебрежимо малый объем под фиксированную таблицу квадратов.
لدينا مكعبان، وعلى كل واحد منهما 6 أرقام مختلفة مختارة من \(\{0,1,\dots,9\}\). وعند وضع المكعبين جنبًا إلى جنب نريد أن نستطيع تمثيل جميع المربعات المكونة من رقمين والأصغر من 100، وهي: \(01, 04, 09, 16, 25, 36, 49, 64, 81\).
المكعبان غير مميزين بالترتيب، ولذلك فإن تبديل موضعيهما لا يعطي ترتيبًا جديدًا. والنقطة الهندسية الوحيدة التي تحتاج إلى انتباه هي أن الوجه الذي يحمل 6 يمكن قلبه ليُقرأ 9، والعكس صحيح أيضًا. إذن المطلوب هو عد جميع الأزواج غير المرتبة من المكعبات ذات الأرقام الستة التي تحقق هذه الشروط التسعة بالضبط.
الحل هنا هو عد دقيق ومنتهٍ. فبمجرد تحويل شروط المسألة إلى قيود صحيحة على أزواج الأرقام، يصبح فضاء البحث صغيرًا جدًا، بحيث يكون التعداد الكامل هو المنهج الرياضي الطبيعي نفسه.
لنضع \(U=\{0,1,\dots,9\}\). المكعب الواحد هو مجموعة جزئية \(D\subseteq U\) تحقق \(\lvert D\rvert=6\). ولذلك فإن عدد المكعبات الممكنة يساوي
$$N_{\text{cube}}=\binom{10}{6}=210.$$
نحن لا نميز بين الزوج المرتب \((D_1,D_2)\) والزوج \((D_2,D_1)\)، كما أن وجود مكعبين متطابقين مسموح به. لذا فنحن نعد الأزواج غير المرتبة مع السماح بالتكرار:
$$N_{\text{pairs}}=\binom{210}{2}+210=\binom{211}{2}=22155.$$
وهذا عدد صغير جدًا. حتى من دون أي تحسينات معقدة، فإن فحص كل زوج مرشح على حدة أمر عملي بالكامل.
تتعامل التطبيقات الثلاثة مع 6 و9 على أنهما فئة دوران واحدة. فإذا احتوى المكعب على أحدهما، أمكن استخدامه لتمثيل الاثنين عند قراءة مربع من مربعات المسألة. والطريقة الأنسب لصياغة ذلك هي استبدال كل مكعب \(D\) بمجموعة أرقامه الفعالة
$$\widehat{D}=\begin{cases} D\cup\{6,9\}, & D\cap\{6,9\}\neq\varnothing,\\ D, & D\cap\{6,9\}=\varnothing. \end{cases}$$
وهذا هو الثابت البنيوي الأساسي في المسألة. وبعد أخذ هذا الإغلاق تصبح كل عملية تحقق لمربع ما مجرد اختبار عضوية داخل \(\widehat{D}_1\) و\(\widehat{D}_2\).
لنكتب المربعات المطلوبة على صورة أزواج مرتبة من الأرقام:
$$P=\{(0,1),(0,4),(0,9),(1,6),(2,5),(3,6),(4,9),(6,4),(8,1)\}.$$
يكون زوج المكعبات صالحًا بالضبط إذا كان لكل \((a,b)\in P\) مكعبٌ يستطيع إظهار \(a\) والآخر يستطيع إظهار \(b\). وبما أن المكعبين قابلان للتبديل، فإن الشرط يكتب هكذا:
$$\bigl(a\in\widehat{D}_1 \land b\in\widehat{D}_2\bigr)\ \lor\ \bigl(a\in\widehat{D}_2 \land b\in\widehat{D}_1\bigr).$$
وهناك تبسيط بنيوي مفيد. فإذا دمجنا 6 و9 في فئة واحدة نرمز لها بـ \(s\)، فإن الشروط غير المرتبة المختلفة تصبح
$$E=\bigl\{\{0,1\},\{0,4\},\{0,s\},\{1,s\},\{2,5\},\{3,s\},\{4,s\},\{1,8\}\bigr\},\qquad s=\{6,9\}.$$
وهذا يوضح أن \(49\) و\(64\) عددان مربعان مختلفان، لكنهما بعد تطبيق قاعدة 6/9 يفرضان القيد البنيوي نفسه: يجب أن يقدّم أحد المكعبين الرقم 4، وأن يقدّم الآخر وجهًا يمكن قراءته 6 أو 9. والتطبيقات تبقي قائمة المربعات التسعة كما هي، وهذا صحيح تمامًا لأن اختبار الأرقام نفسه يدمج بين 6 و9.
خذ \(D_1=\{0,1,2,3,4,5\}\) و\(D_2=\{0,1,2,6,7,8\}\). وبما أن \(D_2\) يحتوي على 6، فإن مجموعة أرقامه الفعالة هي \(\widehat{D}_2=\{0,1,2,6,7,8,9\}\).
لنراجع الآن المربعات المطلوبة. العدد \(01\) يتحقق مباشرة من \(0\in D_1\) و\(1\in D_2\). أما \(04\) فيتحقق بعد تبديل الدورين: نأخذ 4 من المكعب الأول و0 من الثاني. والعدد \(09\) يتحقق لأن 6 في المكعب الثاني يمكن قراءته أيضًا على أنه 9. أما \(16\) و\(36\) فيستخدمان الوجه نفسه 6/9 مع 1 و3 من المكعب الأول. والعدد \(25\) يتحقق بأخذ 2 من المكعب الثاني و5 من الأول. وكل من \(49\) و\(64\) يتحقق بالاعتماد على 4 في المكعب الأول و6/9 في المكعب الثاني. وأخيرًا فإن \(81\) يستخدم 8 من المكعب الثاني و1 من الأول. إذن هذا الزوج صالح.
البنية الرياضية الحقيقية للمسألة لا تشير إلى علاقة عودية أعمق ولا إلى صيغة مغلقة أنفع من العد المباشر. فبعد اختزال المسألة إلى 22155 زوجًا غير مرتب من المكعبات و9 اختبارات ثابتة الحجم لكل زوج، لا يعود التعداد الكامل حلًا احتياطيًا، بل يصبح الحل الدقيق الطبيعي. ولهذا تقوم الشيفرة بما هو أبسط رياضيًا: توليد كل المكعبات المسموح بها، ثم اختبار كل زوج غير مرتب، ثم عد الحالات الناجحة.
تنشئ نسخة Python جميع اختيارات الأرقام ذات العناصر الستة مباشرة على هيئة تراكيب. أما نسختا C++ وJava فتمثلان المكعب بقناع مكوَّن من 10 بتات، ثم تمسحان الأقنعة الممكنة وعددها 1024، مع الاحتفاظ فقط بالأقنعة التي تحتوي على 6 بتات مفعلة. وفي الحالتين نحصل على قائمة المرشحين نفسها وعددها 210 مكعبات.
بعد بناء قائمة المرشحين، تختار الحلقة الخارجية المكعب الأول، وتبدأ الحلقة الداخلية من الفهرس نفسه. وبهذا يزار كل زوج غير مرتب مرة واحدة فقط، كما تُحتسب أيضًا حالة المكعبين المتطابقين. ولكل زوج، تفحص الشيفرة الأزواج التسعة المطلوبة رقمًا رقمًا باستخدام اختبار عضوية يراعي تكافؤ 6 و9. ولا يزداد العداد إلا إذا نجحت الشروط التسعة كلها.
في C++ وJava تُحسَم عضوية الرقم بواسطة عملية بتية على القناع، مع حالة خاصة تجعل السؤال عن 6 أو 9 بمعنى: «هل يوجد أحدهما؟». وفي Python يُحفظ كل مكعب في بنية ثابتة الطول، ثم تُفحص العضوية مباشرة. التمثيلات مختلفة، لكن القضية المنطقية نفسها مطبقة حرفيًا في اللغات الثلاث.
تكلفة توليد 210 مكعبات هي مفهوميًا \(O\!\left(\binom{10}{6}\right)\)، أو \(O(2^{10})\) في النسخ المعتمدة على الأقنعة البتية؛ وفي كلتا الحالتين تبقى هذه المرحلة صغيرة جدًا. أما العمل الأساسي فهو في الحلقة الخاصة بالأزواج غير المرتبة:
$$\binom{210+1}{2}=22155$$
زوجًا مرشحًا، ولكل زوج 9 اختبارات خاصة بالمربعات. ومن ثم فإن العدد الكلي لاختبارات المربعات هو
$$22155\times 9 = 199395.$$
وبالنسبة إلى هذه المسألة فهذا الزمن يعد ثابتًا عمليًا. أما الذاكرة فهي \(O(210)\) لحفظ قائمة المكعبات، مع زيادة مهملة بسبب جدول المربعات الثابت.