Mathematik: Eifallzahlen
Released by matroid on So. 17. April 2022 20:18:43 [Statistics]
Written by Nuramon - 251 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\opn}{\operatorname} \newcommand\ceil[1]{\left\lceil #1 \right\rceil} \newcommand\floor[1]{\left\lfloor #1 \right\rfloor}\)

Eifallzahlen

Erst vor wenigen Tagen hat der Postillon über die bizarren Brauchtümer des "offenbar schwer gestörten Ehepaars" Sabrina und Dennis M. aus Kaiserslautern berichtet. Und jetzt sind die beiden Eifallspinsel schon wieder mit einem neuen Ritual aufgefallen: Sie suchen sich ein Hochhaus vor dem Dennis wartet, während Sabrina sich mit einem Korb voll Eier Zugang zum Balkon eines von ihr gewählten Stockwerkes verschafft. Von dort lässt sie dann eines der Eier auf die Straße fallen. Falls das Ei dabei nicht zerbricht, wirft Dennis es zu ihr zurück. Das wiederholen die beiden einige Male von verschiedenen Stockwerken aus, bis Sabrina ein besonders schön gefärbtes goldenes Ei aus großer Höhe fallen lässt, ohne das dieses zerbricht. Die beiden haben sich zu einem Interview mit der Mathe-Redaktion bereit erklärt, in dem sie die Details des Eifall-Rituals vorstellen und die ausgeklügelte Strategie offenbaren, mit der sie es schaffen, jedes Mal das goldene Ei zu werfen, bevor die Polizei sie stoppen kann.

Das Eifall-Ritual

Familie M. malt jedes Jahr ein Ei golden an. Dennis M. gibt zu: "Wir lieben unser goldenes Ei. Für ein paar Wochen im Jahr werden wir alles dafür geben, dass es nicht zerbricht." Sabrina M. erzählt weiter: "Noch viel mehr lieben wir es aber unser goldenes Ei aus großer Höhe fallen zu lassen. Zum Glück gibt es in unserer näheren Umgebung viele Hochhäuser mit schier unbegrenzter Anzahl an Stockwerken." Sie lächelt und führt fort: "Unser Ziel ist es, das goldene Ei von möglichst weit oben fallen zu lassen. Zerbrechen darf es dabei natürlich nicht. Darum nehme ich immer einen Korb mit $k$ Eiern mit, die wir zur Probe fallen lassen um herauszufinden, wie hoch wir mit dem goldenen Ei gehen können." "Leider sind die Bewohner der Hochhäuser nicht so begeistert davon, dass wir Eier von ihren Balkonen fallen lassen. Manche faseln irgendwas von Hausfriedensbruch und rufen dann die Polizei. Darum spähen wir im Voraus die Lage immer ganz genau aus, um die Anzahl $n$ der Probewürfe herauszufinden, die wir höchstens durchführen können um gerade noch Zeit für den Wurf des goldenen Eis zu haben und dann zu verschwinden, bevor die Polizei auftaucht." sagt Dennis M. Alle Eier der Familie M. sind gleich stabil. Bei der Landung bleibt ein Ei entweder intakt (an der Stabilität ändert sich durch den Aufprall nichts) oder es geht kaputt. Wenn ein Ei beim Fall aus einer bestimmten Höhe $h$ kaputt geht, dann würde jedes Ei beim Fall aus einer Höhe $\geq h$ kaputt gehen. Wenn ein Ei nach einem Fall nicht kaputt ist, dann wirft Dennis es zu seiner Ehefrau zurück. Diese fängt es jedes Mal und kann es daher bei Bedarf nochmal aus beliebiger Höhe fallen lassen. Auf die Frage, wie die einheitliche Qualität sichergestellt werden kann, erklärt Dennis stolz: "Wir brauchen viele Eier. Dass diese von glücklichen Hühnern stammen, ist uns ein großes Anliegen. Alle unserer Eier stammen daher aus einem freundlichen Familienbetrieb, nämlich der Tierhaltung, die seit Generationen von Familie M. und unseren Nachbarn, der Familie Assen, geführt wird." Wenn ein Probeei beim Fall aus dem $i$-ten Stock ganz bleibt, dann weiß man, dass das goldene Ei den Fall aus den Stockwerken $1,2,\ldots, i$ überleben würde. Wenn das Probeei beim Fall aus dem $i$-ten Stock zerbricht, dann kann hingegen keine Aussage darüber gemacht werden, ob es sicher ist, das goldene Ei aus den Stockwerken $1,2,\ldots, i-1$ fallen zu lassen. Das Eifall-Ritual wirft daher folgende Frage auf: Was ist die höchste Etage $E(n,k)$, für die das Ehepaar M. nach bis zu $n$ Probewürfen mit $k$ Probeeiern in jedem Fall für jedes der Stockwerke $1,2,\ldots, E(n,k)$ vorhersagen kann, ob das goldene Ei beim Fall aus diesem Stockwerk zerbrechen würde?
    Beispiel für $k=1$ (also genau ein Probeei):
  • $n=1$: Angenommen Sabrina macht einen Probewurf von der zweiten Etage (oder noch höher). Falls das Probeei dabei kaputt geht, kann sie sich nicht sicher sein, ob das goldene Ei beim Fall aus der ersten Etage kaputt gehen würde. Daher sollte Sabrina den Probewurf von der ersten Etage aus machen. Wenn das Probeei dabei ganz bleibt, dann ist es sicher, das goldene Ei von der ersten Etage aus fallen zu lassen. Falls nicht, dann bleibt nur der Fall aus dem Erdgeschoss übrig, den das goldene Ei immer überleben wird. Also ist $E(1,1)=1$.
  • $n=2$: Da nur ein Probeei zur Verfügung steht, gilt wieder, dass der erste Probewurf von der ersten Etage erfolgen sollte. Falls das Probei diesen ersten Probewurf überlebt, dann kann der zweite Probewurf von der zweiten Etage aus stattfinden. Ist auch dieser erfolgreich, dann kann Sabrina das goldene Ei von der zweiten Etage fallen lassen. Würde der zweite Probewurf hingegen von einer Etage $\geq 3$ erfolgen, so kann sich Sabrina bei Misserfolg des Probewurfs nicht sicher sein, ob sie das goldene Ei von der zweiten Etage werfen kann. Also ist $E(2,1)=2$.
  • Allgemein lässt sich induktiv einsehen, dass $E(n,1)=n$ gilt: Da der erste Probewurf scheitern könnte, muss dieser von Etage 1 aus erfolgen. Ist er erfolgreich, dann hat Sabrina noch $n-1$ weitere Probewürfe und weiß bereits, dass die erste Etage sicher ist. Es gilt also nach Induktionsvoraussetzung $E(n,1)=1+E(n-1,1)$.
    Beispiel für $k=2$ (also zwei Probeeier):
  • $n=1$: Wenn nur für einen Probewurf Zeit ist, dann spielt es keine Rolle ob ein oder zwei Probeeier zur Verfügung stehen. Es gilt also $E(1,2)=E(1,1)=1$.
  • $n=2$: Es bringt keinen Vorteil, den ersten Probewurf vom dritten oder höheren Stockwerken durchzuführen, denn wenn das erste Probeei dabei zerbricht, bleibt wieder nur ein Probeei und ein Probewurf übrig, womit nur das erste Stockwerk garantiert überprüft werden kann. Lässt Sabrina das erste Probeei hingegen vom zweiten Stock aus fallen, dann weiß sie bei Misserfolg, dass alle Stockwerke ab dem zweiten nicht sicher für das goldene Ei sind. Mit dem zweiten Probeei kann sie dann noch den ersten Stock überprüfen und weiß somit sogar für alle Stockwerke, ob sie sicher sind. Falls das erste Probeei den Fall aus dem zweiten Stock überlebt, kann Sabrina mit dem zweiten Probewurf auch noch das dritte Stockwerk überprüfen. Also gilt $E(2,2)=3$.
  • Mit $n=6$ Probewürfen können in jedem Fall die ersten $21$ Stockwerke überprüft werden. Dazu wirft Sabrina das erste Probeei von der sechsten Etage aus. Falls es dabei zerbricht, weiß sie, dass alle Stockwerke $\geq 6$ das goldene Ei zerbrechen würden. Mit dem zweiten Probeei überprüft Sabrina dann nacheinander (bis das Ei zerbricht oder die restlichen $5$ Probewürfe aufgebraucht sind), die Stockwerke $1,2,3,4,5$. Falls das erste Probeei den Fall aus dem sechsten Stock überstanden hat, wirft Sabrina das Ei beim zweiten Probewurf von der elften Etage. Falls es dabei zerbricht, benutzt sie die verbleibenden vier Probewürfe um mit dem zweiten Probeei die Stockwerke $7,8,9,10$ zu überprüfen. Zerbricht es nicht, erfolgt der dritte Probewurf von der 15. Etage usw., siehe Tabelle: $$\begin{array}{r|l} \text{Erstes Ei} & \text{Zweites Ei, falls erstes Ei zerbricht}\\ \hline 6& \phantom01 \to \phantom02 \to \phantom03 \to \phantom04 \to \phantom05\\ 11& \phantom07 \to \phantom08 \to \phantom09 \to 10\\ 15 & 12\to 13\to 14\\ 18 & 16\to 17\\ 20 & 19\\ 21 & \\\hline \end{array}$$

Berechnung der Eifallzahlen $E(n,k)$

Für die Randfälle $k=0$ bzw. $n=0$ stellen wir fest, dass $\forall n\in \IN: E(n,0)=0$ und $\forall k\in \IN: E(0,k)=0$ gilt. Seien jetzt $n,k\geq 1$. Angenommen der erste Probewurf erfolgt von Etage $e$. Falls das Probeei dabei zerbricht, kann Sabrina M. für alle Stockwerke $\geq e$ korrekt vorhersagen, dass das goldene Ei von diesen aus zerbrechen würde. Mit den verbliebenen $n-1$ Probewürfen und $k-1$ Probeeiern kann sie zudem noch die Stockwerke $1,2,\ldots, E(n-1,k-1)$ überprüfen. Für diesen Fall wäre es also am besten $e\leq E(n-1,k-1)+1$ zu wählen, denn dann kann Sabrina für jedes Stockwerk vorhersagen, ob das goldene Ei zerbrechen würde. Falls das Probeei hingegen beim Fall aus der Etage $e$ ganz bleibt, weiß Sabrina, dass das goldene Ei auch den Sturz aus den Etagen $1,2,\ldots, e$ überstehen würde. Mit den verbliebenen $n-1$ Probewürfen und $k$ Probeeiern kann sie zusätzlich noch die Etagen $e+1, e+2,\ldots, e+ E(n-1,k)$ überprüfen. Für diesen Fall wäre es ideal $e$ so groß wie möglich zu wählen. Insgesamt ergibt sich, dass $e=E(n-1,k-1)+1$ die optimale Wahl für den ersten Probewurf ist und dass $$\boxed{ E(n,k) = E(n-1,k-1)+E(n-1,k)+1}$$ gilt. Damit können wir $E(n,k)$ rekursiv berechnen: $$\begin{array}{|r| rrrrrrrrrrr|} \hline & k &0&1&2&3&4&5&6&7&8&9\\\hline n & E(n,k) &&&&&&&&&&\\ 0 && 0&0&0&0&0&0&0&0&0&0 \\ 1 && 0&1&1&1&1&1&1&1&1&1 \\ 2 && 0&2&3&3&3&3&3&3&3&3 \\ 3 && 0&3&6&7&7&7&7&7&7&7 \\ 4 && 0&4&10&14&15&15&15&15&15&15 \\ 5 && 0&5&15&25&30&31&31&31&31&31 \\ 6 && 0&6&21&41&56&62&63&63&63&63 \\ 7 && 0&7&28&63&98&119&126&127&127&127 \\ 8 && 0&8&36&92&162&218&246&254&255&255 \\ 9 && 0&9&45&129&255&381&465&501&510&511 \\\hline \end{array}$$ Als nächstes betrachten wir die erzeugende Funktion $$ F(x,y):=\sum_{n\geq 0}\sum_{k\geq 0} E(n,k)x^ny^k. $$ Aus der Rekursionsgleichung folgt $$\begin{align*} F(x,y) &= \sum_{n\geq 1}\sum_{k\geq 1} (E(n-1,k-1) + E(n-1,k)+1)x^ny^k\\ &= xy F(x,y) + xF(x,y) + \sum_{n\geq 1}x^n\sum_{k\geq 1}y^k\\ &= x(y+1)F(x,y) + \frac{x}{1-x}\frac y{1-y}. \end{align*}$$ Somit ergibt sich $$ F(x,y) = \frac{xy}{(1-x)(1-y)}\frac 1{1-(1+y)x}.$$ Mit der Formel für die geometrische Reihe folgt weiter $$\begin{align*} F(x,y) &= \sum_{a\geq 1}x^a\sum_{b\geq 1}y^b\sum_{c\geq 0}(1+y)^cx^c\\ &= \sum_{n\geq 0} x^n \sum_{b\geq 1}y^b\sum_{c=0}^{n-1}(1+y)^c\\ &= \sum_{n\geq 0} x^n \sum_{b\geq 1}y^b \frac{(1+y)^n-1}{(1+y)-1}\\ &= \sum_{n\geq 0} x^n \sum_{b\geq 0}y^b ((1+y)^n-1)\\ &= \sum_{n\geq 0} x^n \sum_{b\geq 0}y^b \sum_{d\geq 1}\binom nd y^d\\ &= \sum_{n\geq 0} x^n \sum_{k\geq 0}y^k \sum_{d= 1}^k\binom nd \end{align*}$$ Ein Koeffizientenvergleich liefert die Formel $$ \boxed{E(n,k) = \sum_{d=1}^k \binom nd}.$$ Dennis M. verrät uns noch eine kombinatorische Herleitung dieser Formel: "Sabrina wählt für jeden Probewurf immer die optimale Etage. Wenn sie bereits nach weniger als $n$ Probewürfen die höchste Etage gefunden hat, die sicher für das goldene Ei ist, dann führen wir zum Spaß auch noch die restlichen Probewürfe von dieser Etage aus. Immer wenn Sabrina ein Probeei fallen lässt, schreibe ich das Resultat auf: Wenn bei einem Probewurf das Probeei ganz bleibt, dann male ich ein kleines Ei auf meinen Notizblock. Das sieht dann ungefähr so aus." Er malt eine Null in die Luft. "Wenn bei einem Probewurf das Probeei zerbricht, dann heißt das, die Etage ist für das goldene Ei nicht sicher. Daher notiere ich mir dann 'Ei n.s.', oder wenn es schnell gehen muss einfach nur '1'. Nach den $n$ Probewürfen habe ich mir dann eine Folge der Länge $n$ aus Nullen und Einsen notiert, in der höchstens $k$ Einsen vorkommen. Es gibt genau $\sum_{d=0}^k \binom nd$ solche Folgen. Jede dieser Folgen entspricht einem der möglichen Abwurforte für das goldene Ei, also dem Erdgeschoß oder den Etagen $1,2,\ldots, E(n,k)$."

Quellen

Auf die Frage, inwiefern dieser seltsame Brauch noch in die heutige Zeit passt, antwortet Dennis M.: "Das haben wir schon immer so gemacht. Früher war das natürlich ineffizienter, aber die Methode für das heutige Eifall-Ritual wurde uns überliefert von Michael Boardman im Artikel The Egg-Drop Numbers." "Hier in der Oster-EI-Suchmaschine findet man auch immer mal wieder Leute, die sagen, wir sollten die Eier bei den Hühnern im Nest lassen. Stattdessen könnten wir doch einfach Teller für unser Ritual verwenden. Aber für uns ist das einfach nicht dasselbe.", sagt Sabrina M. Frohe Ostern!
\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist nicht im Verzeichnis der Arbeitsgruppe Alexandria eingetragen.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 251
 
Aufrufstatistik des Artikels
Insgesamt 1 externer Seitenaufruf zwischen 2022.05 und 2022.05 [Anzeigen]
DomainAnzahlProz
https://matheplanet.de1100%100 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 1 Aufruf in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2022.05.14 20:07https://matheplanet.de/

[Top of page]

"Mathematik: Eifallzahlen" | 1 Comment
The authors of the comments are responsible for the content.

Re: Eifallzahlen
von: Slash am: Mo. 18. April 2022 08:58:26
\(\begingroup\)Schön, dass du dich des Oster-Themas angenommen hast und danke für diesen kurzweiligen Artikel. 👍 In diesem Sinne: Frohe Ostern! 😎\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]