Pferch

Stell dir vor, du möchtest kreisrunde Plätzchen backen. Du bereitest den Teig vor und rollst ihn aus. Für das Ausstechen hast du aber nur einen Versuch. Deine Aufgabe ist also, so viele Plätzchen wie möglich aus dem Teig auszustechen, ohne dabei Teig zu verschwenden. Aber wie könnte eine optimale Lösung dieses Problems aussehen? Du wirst schnell feststellen, dass es in Abhängigkeit von der Fläche und Form des ausgerollten Teiges und der Größe deiner Ausstechform eine Anzahl von Keksen gibt, die du höchstens aus dem Teig ausstechen kannst. Aber selbst wenn du diese Zahl kennen würdest, ist es nicht klar, in welcher Anordnung du sie ausstechen musst.

Bei unserem Exponat „Pferch“ kannst du genau dies untersuchen. Auf unserem Exponatstisch findest du 7 Spielflächen, in denen du die dort angegebene Anzahl an Spielmünzen in die umrandeten Formen „einpferchen“ musst. Die Lösung ist dabei oft viel weniger symmetrisch, als man zuerst denken würde. In der Mathematik ist dieses Problem verwandt mit dem sogenannten „Kugelpackungsproblem“. Dabei ist die Aufgabe, die dichteste Kugelpackung, also die effizienteste Anordnung gleich großer Kugeln zu finden, die sich höchstens berühren und einen minimalen Zwischenraum lassen. Seinen Ursprung findet das Problem in der Frage nach der dichtesten Anordnung von Kanonenkugeln. Im Jahre 1611 stellte Johannes Kepler die Vermutung auf, dass die dichteste Kugelpackung das hexagonale Gitter ist, welches du in Abbildung 2 erkennen kannst. Jedoch konnte erst im Jahre 1831 von Carl Friedrich Gauß bewiesen werden, dass dies tatsächlich die effizienteste Anordnung ist.

Und nun … die Mathematik

Im Folgenden wollen wir uns mit dem Kugelpackungsproblem im zweidimensionalen euklidischen Raum $\mathbb{R}^2$ beschäftigen. In diesem Fall sind die Kugeln Kreisscheiben. Außerdem ist das Problem zur Auffindung der dichtesten Kugelpackung abhängig davon, ob die Fläche, in der wir die Kreisscheiben anordnen wollen, einen Rand hat, oder unbeschränkt ist. Beim Exponat Pferch soll eine bestimmte Anzahl der Scheiben in ein Quadrat, einen Kreis oder ein Dreieck eingefügt werden. Die Lösung hierbei ist aber viel weniger symmetrisch als wenn man die Scheiben auf einem unberandeten Gebiet möglichst dicht anordnen möchte. Wir studieren im Folgenden beide Fragestellungen.

Dichteste Kugelpackung bei beschränkten Flächen

Quadrat

Als ersten Fall betrachten wir ein Quadrat mit Seitenlänge $1$ . Wir wollen nun eine maximale Länge $r \in (0,\infty)$ angeben, sodass $N$ Kreise mit Radius $r$ passgenau in das Einheitsquadrat „eingepfercht“ werden können (Problem 1). Wir suchen also nach der dichtesten Kugelpackung im Quadrat. Eine andere Fragestellung wäre, eine minimale Seitenlänge $\ell \in (0,\infty)$ zu bestimmen, sodass $N$ Kreise mit einem Radius von $1$ in dieses Quadrat passen (Problem 2). In beiden Fällen wollen wir aber die \emph{Packungsdichte} $\delta$ , also das Verhältnis des Flächeinhalts aller Kreise $F_K$ zu dem des Quadrats $F_Q$

(1) $\begin{align*}\delta = \frac{F_K}{F_Q},\end{align*}$

minimieren. Tatsächlich sind beide Fragestellungen äquivalent, also Problem 1 und 2. Dies kann man sich wie folgt überlegen. Bei Problem 1 ist die Packungsdichte $\delta$ gegeben als

(2) $\begin{align*}\delta = N \pi r^2.\end{align*}$

Falls wir nun auch Problemstellung 2 beantworten wollen, müssen wir uns zuerst überlegen, wie die Packungsdichte $\delta$ in diesem Fall berechnet werden kann. Wir suchen hier eine minimale Seitenlänge $\ell \in (0,\infty)$ des Quadrats, sodass $N$ Kreise mit Radius $1$ hineinpassen, sprich

$\delta = \frac{N\pi}{\ell^2}.$

Da die Packungsdichte in beiden Fällen gleich sein muss, können wir die in (1) und (2) berechnete Packungsdichte gleichsetzen, das heißt

$N \pi r^2 = \frac{N\pi}{\ell^2}.$

Mittels kürzen der Parameter $N$ und $\pi$ und anschließendes Wurzelziehen erhalten wir

$r = \frac{1}{\ell}.$

Wir haben also gezeigt, dass das Reziproke des Radius $r$ aus Problem 1 die zu bestimmende Seitenlänge aus Problem 2 ist, und andersherum. Mit anderen Worten, beide Probleme sind äquivalent. Falls wir also ein Problem gelöst haben, dann haben wir automatisch das jeweils andere auch beantwortet. Übrigens kannst du mit dieser Überlegung auch die Anzahl an Plätzchen berechnen, die du aus einem quadratisch ausgerollten Teig maximal ausstechen kannst, ohne zu viel Teig zu verschwenden.

Die optimale Anordnung für $N \in \{1, \dots, 6\}$ kannst du in Abbildung 3 sehen. Hier ist die Lösung noch sehr symmetrisch. Falls die Anzahl der Kreise $N$ aber größer wird, werden die Anordnungen jedoch alles andere als symmetrisch bzw. sind noch gar keine (optimalen) Lösungen bewiesen wurden. Bis jetzt konnte eine optimale Anordnung für $N \leq 30$ gezeigt werden und für $N \leq 10.000$ ist eine nicht notwendigerweise optimale Lösung bekannt. In der untenstehenden Tabelle findest du die Radien und das Verhältnis $\delta$ aus (2) für $N \in \{1,2,3,4,5,6\}$ .

Anzahl $N$	Radius $r$	Verhältnis $\delta$
1	$\frac{1}{2 + \sqrt{2}} \approx 0,2929$	$53,9\%$
2	$\frac{1}{2 + \sqrt{2}} \approx 0,2929$	$53,9\%$
3	$\frac{1}{2 + \frac{\sqrt{2}}{2} + \frac{\sqrt{6}}{2}} \approx 0,2343$	$60,69\%$
4	$\frac{1}{4}$	$78,54\%$
5	$\frac{1}{2 + 2\sqrt{2}} \approx 0,2071$	$67,38\%$
6	$\frac{1}{2 + \frac{12}{\sqrt{13}}} \approx 0,1877$	$66,4\%$

Übrigens ist die quadratische Anordnung, welche bei $N \in \{1,4\}$ optimal ist, auch optimal bei $N \in \{9, 16, 25, 36\}$ , also genau wenn $N$ eine der ersten sechs Quadratzahlen ist. Jedoch ist die quadratische Anordnung für $N \geq 49$ ineffizient.

Kreis

Wir betrachten nun einen Kreis mit Radius $1$ im euklidischen Raum $\mathbb{R}^2$ . Genauso wie im ersten Fall ist es unsere Aufgabe, eine maximale Zahl $r \in (0,\infty)$ zu bestimmen, sodass $N$ Kreisscheiben mit Radius $r$ in die Kreisform eingesetzt werden können (Problem 1). Genauso könnte man sich fragen, was der minimale Radius $\ell \in (0,\infty)$ der Kreisform sein muss, damit $N$ Kreisscheiben mit Radius 1 hineinpassen. In beiden Fällen ist die Packungsdichte aber gegeben als das Verhältnis der Flächeninhalte aller Kreise $F_K$ und des Flächeinhalts der Kreisform $F_{Kf}$ , sprich

$\begin{align*}\delta = \frac{F_K}{F_{Kf}}.\end{align*}$

Mit einer ähnlichen Überlegung wie im ersten Fall erhalten wir

$\begin{align*}Nr^2 = \frac{N}{\ell^2}.\end{align*}$

Nach Kürzen des Parameters $N$ und anschließenden Wurzelziehen sehen wir, dass der maximale Radius aus Problem 1 genau dem Reziproken des minimalen Radius der Kreisform aus Problem 2 entspricht, sprich beide Probleme sind wieder äquivalent.

In der obigen Abbildung kannst du die optimale Anordnung für $N \in \{1,\dots,5\}$ Kreise im Einheitskreis sehen. Übrigens gibt es für $N = 6$ zwei optimale Lösungen, wie du in Abbildung 5 erkennen kannst.

Bis jetzt konnte eine optimale Anordnung für $N \in \{1,\dots,14\} \cup \{19\}$ bewiesen werden. Für $N \in \{15, \dots 18\} \cup \{20,22,23,27,30,31,33,37,61,91\}$ konnte bis jetzt nur eine optimale Anordnung vermutet werden. In der unten stehenden Tabelle findest du die Radien und das Verhältnis $\delta$ für $N \in \{1,\dots,6\}$ .

Anzahl $N$	Radius $r$	Verhältnis $\delta$
1	$1$	$100\%$
2	$\frac{1}{2}$	$50\%$
3	$\frac{1}{1 + \frac{2}{\sqrt{3}}} \approx 0,4641$	$64,66\%$
4	$\frac{1}{1 + \sqrt{2}} \approx 0,4142$	$68,64\%$
5	$\frac{1}{\sqrt{2(1 + \frac{1}{\sqrt{5}})}} \approx 0,3702$	$68,54\%$
6	$\frac{1}{3}$	$66,66\%$

Gleichseitiges Dreieck

Abschließend betrachten wir ein gleichseitiges Dreieck mit Seitenlänge $1$ , für welches wir eine größtmögliche Zahl $r \in (0,\infty)$ bestimmen wollen, sodass $N$ Kreise mit Radius $r$ in dieses Dreieck passen. Kannst du zeigen, dass diese Fragestellung äquivalent dazu ist, eine minimale Seitenlänge $\ell$ für ein gleichseitiges Dreieck anzugeben, sodass $N$ Einheitskreise hinein passen?

In Abbildung 6 kannst du die optimale Anordnung für $N \in \{1,\dots,6\}$ erkennen. Bis zum heutigen Tage wurde nur für $N < 13$ eine optimale Packung gefunden. Paul Erdös behauptete, dass, falls $N$ eine Dreieckszahl ist, der maximale Radius $r$ bzw. die minimale Seitenlänge $\ell$ bei $N$ und $N - 1$ Kreisscheiben gleich sind. Für die ersten Fälle $N \in \{1,\dots,6\}$ kannst du dich in der unten stehenden Tabelle selbst überzeugen.

Anzahl $N$	Radius $r$	Verhältnis $\delta$
1	$\frac{1}{2\sqrt{3}} \approx 0,2887$	$60,45\%$
2	$\frac{1}{2 + \sqrt{3}} \approx 0,183$	$48,6\%$
3	$\frac{1}{2 + \sqrt{3}} \approx 0,183$	$72,9\%$
4	$\frac{1}{4\sqrt{3}} \approx 0,14434$	$60,46\%$
5	$\frac{1}{4 + 2 \sqrt{3}} \approx 0,1340$	$65,11\%$
6	$\frac{1}{4 + 2 \sqrt{3}} \approx 0,1340$	$78,13\%$

Dichteste Kugelpackung im $\mathbb{R}^2$

Ein gänzlich anderes Problem ist eine dichteste Packung für Einheitskreise in der gesammten euklidischen Ebene $\mathbb{R}^2$ zu finden. Anstelle einer endlichen Fläche, wie bei den Beispielen oben, ist die Fläche des $\mathbb{R}^2$ unendlich. Wir müssen demnach unendlich viele Kreise auf einer unendlich großen Fläche so platzsparend wie möglich anordnen. Man kann sich leicht vorstellen, dass die Aufgabe sehr schwierig ist, unter allen möglichen Anordnungen diejenige Packung zu finden, die am dichtesten ist. Selbst wenn man eine Vermutung hat, ist es nicht trivial zu beweisen, dass sie unter allen Möglichkeiten auch die dichteste ist.

Unsere Methode zur Bestimmung von $\delta$ , wie in den obigen Beispielen, wird hier fehlschlagen. Wir benötigen einen neuen Ansatz. Um $\delta$ für dieses Problem zu definieren, betrachten wir zuerst ein Quadrat $D$ mit Seitenlänge $\ell \in (0,\infty)$ . In dieses Quadrat packen wir so viele Einheitskreise so platzsparend wie möglich. Der Flächeninhalt von $D$ ist dabei $F_D = \ell^2$ und der Flächeninhalt aller Kreise in $D$ ist $F_K^\ell = N(\ell)\pi$ , wobei die Anzahl $N(\ell)$ der Kreise von der Seitenlänge $\ell$ abhängt. Nun lassen wir $\ell$ immer größer werden und packen wieder so viele Kreisscheiben wie möglich in das größere Quadrat. Die Packungsdichte $\delta$ ist dann definiert über den Grenzwert

$\begin{align*}\delta \coloneqq \lim_{\ell \to \infty} \frac{N(\ell) \pi}{\ell^2}.\end{align*}$

Wir haben die dichteste Kugelpackung gefunden, falls $\delta$ unter allen anderen möglichen Kugelpackungen am größten ist. Nun könnte man denken, dass die optimale Packung das quadratische Gitter ist, welches genau die dichteste Kugelpackung im Einheitsquadrat bei $N \in \{1,4,9,16,25,36\}$ ist. Wie oben festgestellt gilt in diesem Fall

$\begin{align*}\delta \approx 78,54\%.\end{align*}$

Jedoch konnte László Fejes Tóth im Jahre 1942 beweisen, dass unter allen Kugelpackungen des $\mathbb{R}^2$ nicht die quadratische Anordnung die dichteste ist, sondern die hexagonale (siehe auch Abbildung 7). Bei dieser Anordnung gilt

$\begin{align*}\delta \approx 90,69\%,\end{align*}$

was deutlich effizienter ist als bei der Anordnung im Quadratischen Gitter.

Es sei bemerkt, dass man das Kugelpackungsproblem allgemein in $\mathbb{R}^d$ für jede Dimension $d \in \mathbb{N}$ formulieren kann. Bis jetzt sind nur optimale Packungen für $d \in \{1,2,3,8,24\}$ bekannt.

Unser Logo: Die Biesterformen

In Abbildung 7 und 8 kannst du erkennen, dass jeder Kreis im hexagonalen Gitter 6 benachbarte Zwischenräume besitzt. Wählt man ein paar davon aus und „klebt“ sie an den Kreis, erhält man bis auf Kongruenz insgesamt 13 verschiedene Formen, die du in Abbildung 9 erkennen kannst.

Unser Logo besteht genau aus diesen 13 verschiedenen Formen. Da sie sich nur widerspenstig zusammensetzen lassen, ist der Name „Biester“ entstanden. Beim Exponat „Biesterhocker“, welches sich am Eingangsbereich befindet, kannst du dich selbst einmal darin versuchen, unser Logo zusammenzusetzen. Es gibt übrigens über 20 000 verschiedene Möglichkeiten, dies zu tun.

Es ist auch möglich, eine zusammenhängende Fläche im $\mathbb{R}^2$ mit den Biesterformen zu überdecken. Jedoch kann man zeigen, dass es nicht möglich ist, alle Teile dabei gleich häufig zu verwenden.

Literatur

https://en.wikipedia.org/wiki/Packing_problems
https://en.wikipedia.org/wiki/Packing_problems
Abbildung 2: https://www.spektrum.de/kolumne/keplersche-vermutung-wie-ein-pirat-die-mathematik-praegte/2096145