Beweis Schokoladentafel zerlegen

Question

"Gegeben sei eine rechteckige Tafel Schokolade, die aus m mal n Stücken besteht. Diese Tafel soll in ihre m*n einzelnen Stücke zerlegt werden. Dazu dürfen nur einzelne, zusammenhängende Stücke Schokolade entlang der vorgezeichneten Furchen gebrochen werden, sodass kleinere Rechtecke entstehen. Diese kleineren Stücke dürfen zum weiteren Brechen nicht über- oder nebeneinander gelegt werden."

Hat jemand einen Tipp, wie man beweisen könnte, dass, egal wie man die Tafel zerlegt (nach oben genannten Regeln), dass es nur genau eine Schrittanzahl gibt, bis die Tafel zerlegt ist, die da genau m * n -1 ist?

Ich hab bisher nur die Erkenntnis, dass, wenn ein Teilstück horizontal oder vertikal gebrochen wird, dafür vertikal oder horizontal mehr Schritte notwendig sind...


Danke,

Thilo

Answer 1

Nun, jedes den angegebenen Regeln entsprechendes Brechen teilt genau eines der vorhandenen Teile in genau zwei Teile. Die Gesamtanzahl aller Teile, die man hat, erhöht sich also durch jedes Brechen um genau eines.

Wenn man nun zu Beginn 1 Teil hat, etwa wie im Beispiel eine ganze Tafel Schokolade, dann hat man nach k-maligem Brechen also 1 + k Teile.

Wenn nun aber 1 + k = m * n sein soll, also im Beispiel gleich der Anzahl der einzelnen Stücke, aus denen die Tafel besteht, dann muss man also k = m * n - 1 mal brechen.

Führt man die Brüche immer nur entlang der vorgegebenen Bruchkanten aus, dann erhält man auf diese Weise genau die m * n durch die Bruchkanten vorgegebenen Stücke der Tafel, Andernfalls erhält man m * n irgendwie anders geformte Stücke. In jedem Fall aber erhält man durch m * n - 1 -maliges Brechen immer m * n Stücke.  

Comments

Absolut perfekt erklärt.