Weihnachtsmann rot

Aufgabe vom 18. Dezember

Der Weihnachtsmann hat Bauchweh - Logische Analyse von Plätzchen

Autoren: Katinka Becker, Alexander Bockmayr

Aufgabe:

Der Schnee liegt wie ein dichter, weißer Teppich über dem Weihnachtszauberland. Das Weihnachtshaus scheint still und friedlich, fast verschlafen. Doch dieser Eindruck täuscht. Öffnet man eine der versteckten Eingangsluken befindet man sich sofort mitten im größten Vorweihnachtstrubel, den man sich vorstellen kann. Es sind nur noch ein paar Tage bis zum Heiligen Abend und die Vorbereitungen laufen auf Hochtouren. Zwischen all dem fröhlich-fleißigen Sägen, Lackieren, Nähen und Geschenke Verpacken, stehen zwei Weihnachtshelfer in der Heiligabend-Planungszentrale mit tief besorgten Blicken.

„So etwas wie letztes Jahr darf nicht noch einmal passieren“, sagt Willi Wichtel seufzend. „Wir müssen uns etwas überlegen, Ella! Der Heilige Abend mit einem kranken Weihnachtsmann – das geht nicht!“

Ella Elfe nickt zustimmend: „Du hast Recht. Wir brauchen einen Plan.“

Wie in jedem Jahr hatte der Weihnachtsmann auch im vergangenen Jahr bei den Kindern, die er beschenkt hat, immer einen Teller mit Plätzchen vorgefunden. Und wie in jedem vorangegangenen Jahr hatte er ohne Ende davon genascht. Vanillekipferl, Spekulatius, Zimtsterne, Spritzgebäck, Pfeffernüsse – er liebte sie alle. Bis zum letzten Jahr war dies auch nie ein Problem gewesen. Aber im letzten Jahr hatte er nach dem Abliefern der Geschenke und dem Essen von einem Teller Plätzchen oftmals furchtbare Bauchschmerzen. Die Bauchschmerzen waren dann so stark, dass er jedes Mal eine Pause machen musste um sich wieder zu entspannen. Nach einer halben Weihnachtsstunde ging es ihm dann auch wieder so gut als ob nie etwas gewesen wäre. Erst dann konnte er zum nächsten Haus fliegen um die Geschenke abzuliefern und dort wieder einen Teller voller Plätzchen zu vertilgen. Ganz abgesehen davon, dass es dem armen Weihnachtsmann in dieser Nacht immer wieder schlecht ging, ist für Pausen einfach keine Zeit am Heiligen Abend. Die beiden mussten sich dringend etwas überlegen, damit es in diesem Jahr anders läuft.

„Wir können ihm nicht verbieten von den Plätzchen zu essen. Es ist seine Leibspeise und irgendwie gehört es doch zum Heiligen Abend dazu, das Schenken und Beschenktwerden“, sagt Willi Wichtel.

„Nein, das können wir nicht. Aber es gab ja auch Plätzchenteller von denen er keine Bauchschmerzen bekommen hat. Es scheint, als ob bestimmte Plätzchen oder vielleicht Kombinationen von Plätzchen die Bauchschmerzen bei ihm auslösen“, erwidert Ella Elfe. „Ich habe im letzten Jahr den Inhalt von ein paar Plätzchentellern notiert und jeweils mit aufgeschrieben, ob der Weihnachtsmann Bauchweh hatte oder nicht. Sieh mal!“


PIC

Abbildung 1: Acht Beobachtungen vom letzten Jahr. Jede Zeile ist ein Plätzchenteller, der vom Weihnachtsmann gegessen wurde. Jede Spalte steht für eine Sorte Plätzchen. In den oberen fünf Fällen bekam der Weihnachtsmann Bauchschmerzen, in den unteren drei Fällen nicht.

Ella Elfes Aufzeichnungen (s. Abbildung 1) vom letzten Jahr enthalten acht Beobachtungen von acht verschiedenen Plätzchentellern, deren Inhalt der Weihnachtsmann am Heiligen Abend gegessen hat. Notiert hat Ella Elfe für sieben verschiedene Plätzchensorten (andere Plätzchen kommen auf den Plätzchentellern niemals vor), ob der Weihnachtsmann sie gegessen hat (notiert mit 1) oder nicht (notiert mit 0). Die Reihenfolge, in der er sie gegessen hat, spielt dabei keine Rolle. Sie hat dann jeweils vermerkt, ob der Weihnachtsmann Bauchschmerzen hatte oder nicht.

Willi Wichtel ist skeptisch: „Das wird er sich doch nie alles merken können! Du weißt doch, dass unser Weihnachtsmann kein gutes Gedächtnis hat.“

„Das muss er auch nicht“, entgegnet Ella Elfe. „Wir sehen uns die Aufzeichnungen genauer an und suchen nach kürzeren Mustern, die seine Bauchschmerzen erklären.“

Ella Elfe ist den Rest des Jahres Mathematikerin. Sie nimmt sich Stift und Papier und legt los:

Wir sind auf der Suche nach logischen Mustern in unserer Aufzeichnung. Wir haben sieben Plätzchensorten x1,,x7. Jedes Muster besteht aus einer Menge von Plätzchenempfehlungen.

Eine Plätzchenempfehlung L ist eine Variable x mit Werten in der Menge {0, 1} oder ihre Negation x = 1 - x. Für jede Plätzchensorte kann die Empfehlung also sein „Iss das Plätzchen!“ oder „Iss das Plätzchen nicht!“.

Eine Plätzchenregel t ist eine Menge von Plätzchenempfehlungen, die durch Multiplikation miteinander verknüpft sind, was logisch der Operation und entspricht. Wir schreiben dafür

t = L1 ⋅ L2 ⋅ ... ⋅ Lk = L1L2 ...Lk,

wobei {L1,,Lk} die Menge der Plätzchenempfehlungen in t ist. Eine Plätzchenregel ist demnach eine Kombination von Plätzchenempfehlungen.

Wie bei Mengen üblich, kommt es dabei nicht auf die Reihenfolge der Plätzchenempfehlungen an, d. h. wir unterscheiden nicht zwischen der Plätzchenregel L1L2 und L2L1, die beide der Menge {L1,L2} entsprechen. Auch darf jede Plätzchensorte in einer Plätzchenregel höchstens einmal vorkommen, d. h. entweder positiv in der Form xi oder negativ in der Form xi oder gar nicht.

Der Grad einer Plätzchenregel t ist die Anzahl der verschiedenen Plätzchensorten bzw. Plätzchenempfehlungen in t.

„Mensch, Ella! Wie soll man das denn als normaler Wichtel verstehen?“, beschwert sich Willi Wichtel.

„Warte! Ich werde es dir an einem Beispiel erklären“, beschwichtigt ihn Ella. „Für n=2 sind x1, x1, x2, x2 die Plätzchenregeln vom Grad 1 und

x1x2, x1x2, x1x2, x1x2-

die Plätzchenregeln vom Grad 2, wobei es nicht auf die Reihenfolge der Plätzchenempfehlungen ankommt. Plätzchenregeln vom Grad 3 oder höher gibt es für n=2 nicht, da ja jede Plätzchenempfehlung höchstens einmal pro Plätzchenregel vorkommen darf. Die Plätzchenregel x1x2 bedeutet zum Beispiel: ‚Iss Plätzchen der Sorte 1, aber keine der Sorte 2‘

„Ok, jetzt hab’ ich’s verstanden.“, meint Willi erleichtert.

Zufrieden fährt Ella fort zu kritzeln: Durch Auswertung der Negation und Multiplikation erhält man zu jeder Plätzchenregel t eine Funktion

ft : {0,1}n → {0,1}.

Wir notieren mit t(v) = ft(v) den Wert der Funktion ft angewendet auf einen Plätzchenteller v ∈{0, 1}n. Wir sagen dann, dass eine Plätzchenregel t den Plätzchenteller v ∈{0, 1}n überdeckt, wenn t(v) = 1.

„Laaangsam!“, fährt Willi wieder dazwischen. „Kannst du mir nicht wieder ein Beispiel zeigen?“
„Na, klar!“, entgegnet Ella. „Für n = 4 definiert die Plätzchenregel t = x1x2x4 zum Beispiel die Funktion

         4
ft : {0,1} →  {0,1},(v1,v2,v3,v4) ↦→  ft(v1,v2,v3,v4) = v1 ⋅ (1 - v2) ⋅ v4.

Wenden wir ft auf den Plätzchenteller v = (1, 0, 0, 1) an, erhalten wir

t(v) = ft(v ) = ft(1,0,0,1 ) = 1 ⋅ (1 - 0) ⋅ 1 = 1 ⋅ 1 ⋅ 1 = 1.“

Ella überlegt weiter: Eine Plätzchenregel t heißt Muster von unserer Aufzeichnung, wenn t mindestens einen der beobachteten Plätzchenteller überdeckt, die zu Bauchweh geführt haben, und keinen der Teller überdeckt, die nicht zu Bauchweh geführt haben.

„In der Aufzeichnung in Abbildung 1 ist ein Muster in orange markiert. Das Muster t = x2x4 überdeckt zwei der beobachteten Teller, die zu Bauchweh geführt haben, und keinen der Teller, die nicht zu Bauchweh geführt haben“, erläutert Ella.

„Wow!“, Willi Wichtel ist sprachlos. „Das ist toll! Aber denk daran, dass der Weihnachtsmann kein gutes Gedächtnis hat! Ich glaube nicht, dass er sich Muster merken kann, die mehr als 3 Plätzchenempfehlungen enthalten.“

„Ja, das mache ich“, sagt Ella Elfe eifrig. „Wir werden nach kurzen Mustern mit einer bestimmten Eigenschaft suchen. Nach Primmustern! Dabei heißt ein Muster t Primmuster, wenn keine echte Teilmenge der Menge der Plätzchenempfehlungen in t ein Muster bildet. Außerdem heißen zwei Primmuster t und tgenau dann verschieden, wenn die Mengen der Plätzchenempfehlungen in t und tverschieden sind, d. h. es kommt nicht auf die Reihenfolge der Plätzchenempfehlungen an und Plätzchenempfehlungen (oder Plätzchensorten) tauchen nicht mehrfach auf.“

Ella und Willi wollen nun von euch wissen: Wie viele verschiedene Primmuster vom Grad 3 gibt es zu den Aufzeichnungen in Abbildung 1?


Illustration: Julia Nurit Schönnagel

Die Aufgabe als PDF runterladen

Antwortmöglichkeiten:

  1. Die Anzahl der Primmuster vom Grad 3 ist 1.

  2. Die Anzahl der Primmuster vom Grad 3 ist 2.

  3. Die Anzahl der Primmuster vom Grad 3 ist 3.

  4. Die Anzahl der Primmuster vom Grad 3 ist 4.

  5. Die Anzahl der Primmuster vom Grad 3 ist 5.

  6. Die Anzahl der Primmuster vom Grad 3 ist 6.

  7. Die Anzahl der Primmuster vom Grad 3 ist 7.

  8. Die Anzahl der Primmuster vom Grad 3 ist 8.

  9. Die Anzahl der Primmuster vom Grad 3 ist 9.

  10. Die Anzahl der Primmuster vom Grad 3 ist 0 (d. h. es gibt kein Primmuster vom Grad 3).

Sie müssen sich einloggen um die Aufgaben abgeben zu können.

Bemerkung:

Wir empfehlen, zuerst die Plätzchenregeln vom Grad 2 zusammen mit den von ihnen überdeckten Tellern, die zu Bauchweh führen, und den von ihnen überdeckten Tellern, die nicht zu Bauchweh führen, zu betrachten.

Projektbezug:

In der mathematischen Modellierung von biologischen und medizinischen Anwendungen besteht fast immer das Problem, dass Daten unvollständig und fehlerbehaftet sind. Anstatt unsichere Annahmen zu treffen um ein eindeutiges Modell zu erhalten, besteht ein anderer Ansatz darin einen Modell-Pool zu generieren, der alle bekannten Beobachtungen erfüllt. Die Analyse und Klassifizierung solcher Modell-Pools führt zu direkten Verbindungen zwischen den Bedingungen, die aus dem Datensatz entstehen, und den Eigenschaften der Modelle. Auf diese Weise können Modell-Pools verschiedene Ansätze aufzeigen, die den gleichen biologischen Mechanismus erklären.

Die Logische Analyse ist eine Methode zur Klassifizierung von Daten. Wir nutzen die Logische Analyse zur Mustersuche in Daten bestehend aus Proteinmessungen in Zellsignalwegen. Muster aus aktivierten und inaktivierten Proteinen können unter anderem dabei helfen gesunde von mutierten Zellen zu unterscheiden.