Problem des Monats Dezember 2003

Annika, Björn und Christina sind Geschwister. Eine Tante kommt im Advent zu Besuch und bringt den Kindern eine Dose mit Süßigkeiten mit. Es ist schon spät am Tag, deshalb soll die Dose erst am nächsten Morgen aufgemacht und dann ihr Inhalt gerecht geteilt werden.

Als die Tante die Dose kaufte, hatte sie leider ihre Brille nicht dabei. So merkte sie nicht, dass sie den Kindern Rumkugeln mitbrachte, für die sie eigentlich noch zu jung waren.

In der Nacht wacht Annika auf, verspürt Hunger und beschließt, sich ihr Drittel vom Geschenk der Tante zu nehmen. Sie öffnet die Dose und stellt fest, dass bei der Aufteilung in drei gleiche Anteile eine Rumkugel übrig bleibt. Da der Hund der Familie zuschaut und zu bellen droht, besticht Annika ihn mit der überzähligen Rumkugel und isst dann ihren Anteil auf. Natürlich will sie am nächsten Morgen ihren Geschwistern sagen, dass sie sich die ihr zustehenden Rumkugeln schon genommen hat.

Als Annika wieder schläft, wacht Björn auf und hat die gleiche Idee wie seine Schwester. Er weiß nicht, dass Rumkugeln fehlen und nimmt sich also ein Drittel der verbliebenen, was allerdings erst dann aufgeht, als er den Hund mit einer Rumkugel bestochen hat.

Später in der Nacht macht es Christina ebenso wie ihre Geschwister. Auch sie muss erst den Hund mit einer Rumkugel bestechen und nimmt dann ein Drittel der restlichen Rumkugeln. - Kein Kind musste eine Rumkugel zerteilen. Alle drei wollen sich am nächsten Morgen offenbaren und sind zu Recht der Meinung, nichts Böses getan zu haben.

Am nächsten Morgen entfaltet der Alkohol seine Wirkung. Die drei Kinder sind ziemlich benommen und fühlen sich elend. Sie erinnern sich nicht mehr daran, dass sie ihren Geschwistern etwas sagen müssten. Sie leeren die Dose auf den Tisch aus und teilen den Inhalt in drei gleiche Teile, ohne Rumkugeln zu zerteilen. Dabei bleibt eine Rumkugel übrig; die erhält der Hund, der auch schon anfängt, etwas benommen zu wirken.

Wieviele Rumkugeln enthielt die volle Dose?
Die Lösung wird eindeutig, wenn wir uns auf eine zweistellige Anzahl von Rumkugeln festlegen. Das erscheint auch plausibel, da Annika sonst am nächsten Morgen kaum noch hätte aufstehen können.

Wie lautet die Lösung für eine andere Geschwisterzahl?
Wenn man dieses allgemeine Problem zuerst löst, fällt natürlich die Lösung für drei Kinder mit ab.

Lösung

n     Anzahl der Kinder

x_n    Anzahl Rumkugeln in voller Dose

x_n-1  Anzahl Rumkugeln, nachdem sich das 1. Kind in der Nacht bedient hat

. . .

x_n-i  Anzahl Rumkugeln, nachdem sich das i. Kind in der Nacht bedient hat

. . .

x_o    Anzahl Rumkugeln, nachdem sich alle Kinder in der Nacht bedient haben

In der Problemstellung ist  n = 3 . Dafür gilt

(1)   x_k = (x_k+1 - 1)·²/₃

denn man kommt von einem Kind zum anderen, indem man eine Rumkugel für den Hund abzieht und dann ein Drittel wegnimmt. In drei Iterationsschritten (k = 2, 1, 0)  erhält man  x_o = (8·x₃ - 38)/27. Da am nächsten Morgen der Hund eine Rumkugel erhält und die Kinder danach je ein Drittel erhalten, gilt:

(2)   x_o = 3·r + 1

mit natürlichem  r ; daraus folgt:

(3)   8·x₃ = 81·r + 65

Dies ist eine diophantische Gleichung, d.h. eine Gleichung, für die nur ganzzahlige Lösungen zugelassen sind. Unser Problem ist also auf eine lineare diophantische Gleichung mit zwei Unbekannten zurückgeführt worden. Für solche Gleichungen gibt es ein allgemeines Lösungsverfahren, das man in den meisten Büchern über elementare Zahlentheorie findet. Da hier nur zweistellige  x₃  gesucht werden, findet man die Lösung schnell, indem man die kleinen ungeraden  r  durchprobiert: Für  r = 1, 3, 5, 9  geht die Gleichung (3) nicht ganzzahlig auf, aber für  r = 7  ist  x₃ = 79 . Für  r > 9  wird  x₃  zu groß. Damit ist das Problem (für drei Kinder) gelöst:

In der Dose waren 79 Rumkugeln.

Man kommt zum gleichen Ergebnis, wenn man bei (2) beginnt und (1) umformt in

(4)   x_k+1 = x_k·³/₂ + 1

Hier setzt man iterativ  k = 0, 1, 2  ein und erhält wieder die Gleichung (3).

Allgemeine Lösung für  n  Kinder

Von  x_k+1 - 1  wird ein n-tel weggenommen, um  x_k  zu erhalten;  x_o - 1  muss ein Vielfaches von  n  sein. Also erhält man:

(1')   x_k = (x_k+1 - 1)·(1 - ¹/_n)

(2')   x_o = n·r + 1  mit natürlichem  r

(Wir wissen schon aus dem Fall  n = 3 , dass nicht alle natürlichen  r  in Frage kommen.) Aus diesen Gleichungen lassen sich alle  x_k  und insbesondere das gesuchte  x_n  iterativ berechnen.

Vermutung:

Diese Vermutung beweist man induktiv. Die Gleichung ist richtig für  i = 0 . Dass sie für alle größeren  i  (bis  n) richtig ist, erkennt man aus

Daraus ergibt sich, zusammen mit (2'):

n·r + 1 = x_o = (x_n + n - 1)·(1 - ¹/_n)ⁿ - n + 1

Auflösen nach  x_n  ergibt:

(3')   x_n = (r + 1)·nⁿ⁺¹/(n - 1)ⁿ - n + 1

n  und  n - 1  sind teilerfremd, also lässt sich  nⁿ⁺¹/(n - 1)ⁿ  nicht kürzen.  x_n  wird somit genau dann ganzzahlig, wenn  r + 1  ein Vielfaches von  (n - 1)ⁿ  ist, also

r = m·(n - 1)ⁿ - 1   mit beliebigem natürlichem  m.

So erhält man  x_n = m·nⁿ⁺¹ - n + 1 ; setzt man dies oben in  x_n-i  ein, erkennt man, dass alle  x_k  ganzzahlig sind.

Die allgemeine Lösung ist:

In der Dose waren  m·nⁿ⁺¹ - n + 1  Rumkugeln.

So ergeben sich alle anderen Werte, die für unser Problem von Interesse sind:

Das i-te Kind isst in der Nacht  (x_n-i+1 - 1)/n = m·n^n-i+1·(n-1)^i-1 - 1  Rumkugeln.

Das i-te Kind lässt übrig:  x_n-i = m·n^n-i+1·(n - 1)ⁱ - n + 1  Rumkugeln.

Am nächsten Morgen sind noch übrig:  x_o = m·n·(n - 1)ⁿ - n + 1  Rumkugeln.

Jedes Kind erhält am Morgen  (x_o - 1)/n = m·(n - 1)ⁿ - 1  Rumkugeln.

Der Hund frisst  n + 1  Rumkugeln.

Wie im Fall  n = 3  kann man mit aufsteigenden statt mit absteigenden Indizes arbeiten, d.h. man beginnt mit  x_o  und formt (1') um zu

(4')   x_k+1 = x_k·ⁿ/_n-1 + 1

Man geht wieder induktiv vor:

Daraus ergibt sich zusammen mit (2') die Vermutung:

Diese Vermutung ist richtig für  k = 0 . Dass sie für alle größeren  k  (bis  n) stimmt, rechnet man leicht mit (4') nach:

Für  k = n  ergibt sich wieder  x_n = (r + 1)·nⁿ + 1/(n - 1)ⁿ - n + 1  wie in (3').

Ein Sonderfall sollte noch betrachtet werden: Ist  n = 2  und  m = 1 , enthält die Dose beim Öffnen am Morgen lediglich eine Rumkugel für den Hund. Will man diesen Fall ausschließen, muss man für  n = 2  fordern, dass  m > 1  gilt.