Ein klassisches Geometrieproblem
Quadrate in einem Quadrat packen
Wie klein kann ein Quadrat sein, das n Quadrate der Seitenlänge 1 ohne Überlappung aufnimmt? Ein einfaches Raster ist oft nicht die Antwort. Velmar Cut hat die beste bekannte Seitenlänge bei 26 Größen erreicht, bei denen sie keine ganze Zahl ist, jeweils mit Bild, CAD-Dateien, Zeit und einer Prüfung, die Sie selbst ausführen können.
Das Problem
n Quadrate der Seitenlänge 1 sollen ohne Überlappung in ein möglichst kleines Quadrat passen.
Ein einfaches Raster ist oft nicht die beste Antwort. Gedrehte Quadrate können mit weniger auskommen, und deshalb sehen diese Zahlen so seltsam aus: lange Dezimalzahlen statt ganzer Zahlen.
Ein einfaches Raster: Seitenlänge 5
Bester bekannter Wert: Seitenlänge 4,6755300936
Blaue Quadrate stehen aufrecht, orange Quadrate sind gedreht. Beide Bilder haben denselben Maßstab.
Die von Velmar Cut erreichten Größen
26 Größen, bei denen das Ergebnis von Velmar Cut dem besten bekannten Wert entspricht und dieser Wert keine ganze Zahl ist.
| Quadrate | Beste bekannte Seitenlänge | Velmar Cut | Differenz | Gefunden von | Zeit bis zum Ergebnis | Threads |
|---|---|---|---|---|---|---|
| 5 | 2,7071067812 | 2,7071067812 | +3.700E-13 | Frits Göbel, 1979 | 0,05 s, ein Lauf | 16 |
| 10 | 3,7071067812 | 3,7071067812 | +5.700E-13 | Frits Göbel, 1979 | 0,075 s, ein Lauf | 16 |
| 11 | 3,8770835900 | 3,8770835900 | +5.800E-13 | Walter Trump, 1979 | 1,762 s, ein Lauf | 16 |
| 17 | 4,6755300936 | 4,6755300936 | +7.500E-13 | John Bidwell, 1998 | 4,838 s, ein Lauf | 16 |
| 18 | 4,8228756555 | 4,8228756555 | +8.200E-13 | Pertti Hämäläinen, 1980 | 0,471 s, ein Lauf | 16 |
| 19 | 4,8856180832 | 4,8856180832 | +8.050E-13 | Robert Wainwright, 1979 | 13,528 s, ein Lauf | 16 |
| 26 | 5,6213203436 | 5,6213203436 | +9.700E-13 | Erich Friedman, 1997 | 1,226 s, ein Lauf | 16 |
| 27 | 5,7071067812 | 5,7071067812 | +1.065E-12 | Frits Göbel, 1979 | 0,837 s, ein Lauf | 16 |
| 28 | 5,8244446167 | 5,8244446167 | +1.105E-12 | David Ellsworth, 2025 | insgesamt 3238,437 s, mehrere Läufe | 4 oder mehr |
| 29 | 5,9338334627 | 5,9338334627 | +1.045E-12 | Thomas Schadt, optimiert von David Ellsworth, 2025 | 14,006 s, ein Lauf | 16 |
| 37 | 6,5986196092 | 6,5986196092 | +1.670E-12 | David W. Cantrell, 2002 | 39,892 s, ein Lauf | 16 |
| 38 | 6,7071067812 | 6,7071067812 | +1.470E-12 | Frits Göbel, 1979 | 2,116 s, ein Lauf | 16 |
| 39 | 6,8107220831 | 6,8107220831 | +1.220E-12 | Thomas Schadt, optimiert von David Ellsworth, 2026 | insgesamt 1134,659 s, mehrere Läufe | 4 oder mehr |
| 40 | 6,8284271247 | 6,8284271247 | +1.300E-12 | Frits Göbel, 1979 | 0,166 s, ein Lauf | 16 |
| 41 | 6,9266930945 | 6,9266930945 | +1.545E-12 | Thomas Schadt, optimiert von David Ellsworth, 2026 | insgesamt 1660,447 s, mehrere Läufe | 4 oder mehr |
| 50 | 7,5714285714 | 7,5714285714 | +4.101E-12 | Thomas Schadt, optimiert von David Ellsworth, 2025 | insgesamt 656,624 s, mehrere Läufe | 8 oder mehr |
| 52 | 7,7071067812 | 7,7071067812 | +1.755E-12 | Frits Göbel, 1979 | 1,011 s, ein Lauf | 8 |
| 53 | 7,8228756555 | 7,8228756555 | +1.645E-12 | David Ellsworth, 2026 | 86,758 s, ein Lauf | 8 |
| 65 | 8,5355339059 | 8,5355339059 | +1.560E-12 | Frits Göbel, 1979 | 0,922 s, ein Lauf | 16 |
| 66 | 8,6568542495 | 8,6568542495 | +1.820E-12 | Evert Stenlund, 1980 | 15,243 s, ein Lauf | 8 |
| 67 | 8,7071067812 | 8,7071067812 | +4.083E-12 | Evert Stenlund, 1980 | 2,907 s, ein Lauf | 8 |
| 70 | 8,8816667570 | 8,8816667570 | +3.675E-12 | Joe DeVincentis, 2014 | insgesamt 1089,879 s, mehrere Läufe | 4 oder mehr |
| 82 | 9,5355339059 | 9,5355339059 | +5.310E-12 | Frits Göbel, 1979 | 65,524 s, ein Lauf | 8 |
| 84 | 9,7071067812 | 9,7071067812 | +4.160E-12 | Evert Stenlund, 1980 | 13,482 s, ein Lauf abschließender Schritt für die Exaktheit nicht eingerechnet | 8 |
| 85 | 9,7426406871 | 9,7426406871 | +2.690E-12 | Erich Friedman, 1997 | 64,973 s, ein Lauf | 8 |
| 89 | 9,9497474683 | 9,9497474683 | +2.815E-12 | Evert Stenlund, 1980 | 96,19 s, ein Lauf | 8 |
Das sind die Zeiten bis zum jeweiligen Ergebnis auf einem Desktop-PC, Intel Core i5-12600K, 10 Kerne, 16 Threads. Jede Zeile nennt die Threads ihres Laufs.
Aufgeführt sind nur Größen, bei denen das Ergebnis von Velmar Cut dem besten bekannten Wert entspricht. Zu allen anderen Größen machen wir keine Aussage.
5 Quadrate: Seitenlänge 2,7071067812
10 Quadrate: Seitenlänge 3,7071067812
11 Quadrate: Seitenlänge 3,8770835900
17 Quadrate: Seitenlänge 4,6755300936
18 Quadrate: Seitenlänge 4,8228756555
19 Quadrate: Seitenlänge 4,8856180832
26 Quadrate: Seitenlänge 5,6213203436
27 Quadrate: Seitenlänge 5,7071067812
28 Quadrate: Seitenlänge 5,8244446167
29 Quadrate: Seitenlänge 5,9338334627
37 Quadrate: Seitenlänge 6,5986196092
38 Quadrate: Seitenlänge 6,7071067812
39 Quadrate: Seitenlänge 6,8107220831
40 Quadrate: Seitenlänge 6,8284271247
41 Quadrate: Seitenlänge 6,9266930945
50 Quadrate: Seitenlänge 7,5714285714
52 Quadrate: Seitenlänge 7,7071067812
53 Quadrate: Seitenlänge 7,8228756555
65 Quadrate: Seitenlänge 8,5355339059
66 Quadrate: Seitenlänge 8,6568542495
67 Quadrate: Seitenlänge 8,7071067812
70 Quadrate: Seitenlänge 8,8816667570
82 Quadrate: Seitenlänge 9,5355339059
84 Quadrate: Seitenlänge 9,7071067812
85 Quadrate: Seitenlänge 9,7426406871
89 Quadrate: Seitenlänge 9,9497474683
Wo ein einfaches Raster die Antwort ist
Ist die beste bekannte Seitenlänge eine ganze Zahl, lautet die Antwort: ein einfaches Raster. Diese Größen sind trivial, daher stehen dort keine Zeiten, und sie sind kein Verdienst von Velmar Cut.
| Seitenlänge | Quadrate | Als optimal bewiesen |
|---|---|---|
| 1 | 1 | Keiner genannt |
| 2 | 2, 3, 4 | 2: Frits Göbel, 1979; 3: Frits Göbel, 1979 |
| 3 | 6, 7, 8, 9 | 6: Michael Kearney and Peter Shiu, 2001; 7: Erich Friedman, 1999; 8: Erich Friedman, 1999 |
| 4 | 12, 13, 14, 15, 16 | 13: Wolfram Bentz, 2009; 14: Erich Friedman, 1999; 15: Erich Friedman, 1999 |
| 5 | 20, 21, 22, 23, 24, 25 | 22: Wolfram Bentz, 2018; 23: Hiroshi Nagamochi, 2005; 24: Erich Friedman, 1999 |
| 6 | 30, 31, 32, 33, 34, 35, 36 | 33: Wolfram Bentz, 2018; 34: Hiroshi Nagamochi, 2005; 35: Erich Friedman, 1999 |
| 7 | 42, 43, 44, 45, 46, 47, 48, 49 | 46: Wolfram Bentz, 2009; 47: Hiroshi Nagamochi, 2005; 48: Hiroshi Nagamochi, 2005 |
| 8 | 56, 57, 58, 59, 60, 61, 62, 63, 64 | 62: Hiroshi Nagamochi, 2005; 63: Hiroshi Nagamochi, 2005 |
| 9 | 72, 73, 74, 75, 76, 77, 78, 79, 80, 81 | 79: Hiroshi Nagamochi, 2005; 80: Hiroshi Nagamochi, 2005 |
| 10 | 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100 | 98: Hiroshi Nagamochi, 2005; 99: Hiroshi Nagamochi, 2005 |
Die genannten Beweise sind Sätze dieser Personen, nicht Ergebnisse von Velmar Cut.
Zwei getrennte Fragen
Ob eine Packung gültig ist und wie nah sie dem besten bekannten Wert kommt, sind zwei verschiedene Dinge mit jeweils eigener Antwort.
Ist die Packung gültig?
Ein exaktes Ja oder Nein: Jedes Teil ist ein Einheitsquadrat, jedes liegt im Rahmen, keine zwei überlappen sich, und die Anzahl stimmt. Ein Referenzwert spielt dabei keine Rolle.
Wie nah ist sie am besten bekannten Wert?
Eine eigene Messung: die Differenz zwischen der Seitenlänge von Velmar Cut und dem besten bekannten Wert, ungerundet für jede Größe. Auch eine gültige Packung kann den Wert verfehlen.
Erreicht heißt: Das Zertifikat besteht die exakte Prüfung, und |L - bester bekannter Wert| <= 1E-11, wobei die Differenz für jede Größe ungerundet veröffentlicht wird. L ist die Seitenlänge des Rahmens im Zertifikat, auf 15 Dezimalstellen aufgerundet.
Sie müssen uns nicht vertrauen
Das kann jeder ausführen, mit reinem Python und ohne weitere Software. Jedes Ergebnis wird neu geprüft, mit exakter rationaler Arithmetik und ohne Rundung.
Archiv herunterladen und entpacken, dann alles prüfen:
python verify_exact.py --records=records.jsonEine einzelne Größe prüfen:
python verify_exact.py 17/17-squares-in-a-square.csv --squares=17 --reference=4.67553009360455 --epsilon=1e-11test_verify_exact.py testet das Prüfskript selbst, auch darauf, dass es gerundete Ecken und gemischte Dateien ablehnt.
Was es beweist
- Jedes Teil ist exakt ein Einheitsquadrat. Jedes ist durch seinen Mittelpunkt und t = tan(halbe Drehung) gegeben, sodass cos und sin exakt sind.
- Jedes Teil liegt im Rahmen der Seitenlänge L.
- Keine zwei Teile haben gemeinsame innere Punkte. Berührungen sind erlaubt.
- Die Anzahl stimmt.
- |L - Referenzwert| liegt innerhalb des angegebenen Epsilon.
Was es nicht beweist
- Dass eine Packung optimal ist.
- Dass der Referenzwert der aktuell beste bekannte Wert ist.
- Wie die Anordnung gefunden wurde.
Dateien
Quellen
Die besten bekannten Werte stammen aus „Squares in Squares“ von David Ellsworth, nach dem Original von Erich Friedman.
Zu jeder Größe steht, von wem ihr Wert stammt und seit wann. Deren Ergebnis hat Velmar Cut erreicht.
Fragen
Wie groß ist das kleinste Quadrat für n Einheitsquadrate?
Das hängt von n ab. Für manche n ist die beste bekannte Antwort ein einfaches Raster, für andere eine Anordnung mit gedrehten Quadraten. Die Tabellen auf dieser Seite nennen die Seitenlänge für jede Größe.
Warum sehen die Zahlen so seltsam aus?
Gedrehte Quadrate bringen Längen wie ½√2 ins Spiel, und bei manchen Größen ist die Seitenlänge eine Nullstelle eines Polynoms ohne jede glatte Form. Als Dezimalzahlen brechen solche Werte nie ab.
Verbessern diese Ergebnisse die besten bekannten Werte?
Nein. Nach der Regel auf dieser Seite entsprechen ihnen die Ergebnisse von Velmar Cut. Die kleine Differenz bedeutet, dass die Seitenlänge von Velmar Cut etwas größer ist. Sie liegt nie unter dem Referenzwert.
Beweist ein erreichter Wert, dass die Packung die kleinstmögliche ist?
Nein. Für die meisten Größen ist kein Beweis genannt. Die Quelltabelle kennzeichnet die bewiesenen.
Warum fehlen manche Größen?
Aufgeführt sind nur Größen, bei denen das Ergebnis von Velmar Cut dem besten bekannten Wert entspricht. Zu allen anderen Größen machen wir keine Aussage.
Kostenloser Testzeitraum
Sieben Tage mit allen Editionen
Installieren Sie Velmar Cut, geben Sie Teile und Rohmaterial eines laufenden Auftrags ein und drucken Sie die Zuschnittliste. Der Testzeitraum beginnt beim ersten Start und braucht weder Konto noch Karte.