Manfred Börgens
Mathematische Probleme  # 36
Liste aller Probleme mit Lösungen
voriges Problem      nächstes Problem
zur Leitseite

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

xn    Anzahl Rumkugeln in voller Dose

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

. . .

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

. . .

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


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

(1)   xk = (xk+1 - 1)·2/3

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  xo = (8·x3 - 38)/27. Da am nächsten Morgen der Hund eine Rumkugel erhält und die Kinder danach je ein Drittel erhalten, gilt:

(2)   xo = 3·r + 1

mit natürlichem  r ; daraus folgt:

(3)   8·x3 = 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  x3  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  x3 = 79 . Für  r > 9  wird  x3  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)   xk+1 = xk·3/2 + 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  xk+1 - 1  wird ein n-tel weggenommen, um  xk  zu erhalten;  xo - 1  muss ein Vielfaches von  n  sein. Also erhält man:

(1')   xk = (xk+1 - 1)·(1 - 1/n)

(2')   xo = 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  xk  und insbesondere das gesuchte  xn  iterativ berechnen.

Berechnung von x_n-1 bis x_n-3


Vermutung:

Vermutung fuer x_n-i

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

Induktionsschritt nach n-i-1

Daraus ergibt sich, zusammen mit (2'):

n·r + 1 = xo = (xn + n - 1)·(1 - 1/n)n - n + 1

Auflösen nach  xn  ergibt:

(3')   xn = (r + 1)·nn+1/(n - 1)n - n + 1

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

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

So erhält man  xn = m·nn+1 - n + 1 ; setzt man dies oben in  xn-i  ein, erkennt man, dass alle  xk  ganzzahlig sind.

Die allgemeine Lösung ist:

In der Dose waren  m·nn+1 - 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  (xn-i+1 - 1)/n = m·nn-i+1·(n-1)i-1 - 1  Rumkugeln.

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

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

Jedes Kind erhält am Morgen  (xo - 1)/n = m·(n - 1)n - 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  xo  und formt (1') um zu

(4')   xk+1 = xk·n/n-1 + 1

Man geht wieder induktiv vor:

Berechnung von x1 bis x3

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

Vermutung fuer xk

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:

Induktionsschritt von k nach k+1

Für  k = n  ergibt sich wieder  xn = (r + 1)·nn + 1/(n - 1)n - 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.



Stand 2003-10-24
voriges Problem   |    Liste aller Probleme mit Lösungen   |    nächstes Problem
Manfred Börgens   |    zur Leitseite