beweis dass n-1 schritte notwendig sind?
Hallo, wir sollen einen Beweis als Hausübung machen, leider habe ich keine Ahnung wo ich anfangen soll und hoffe jemand kann mir weiterhelfen.
Sie haben ein rechteckiges, kariertes Blatt Papier, das n = a x b Kästchen groß ist. Sie sollen dieses Blatt mit einer Schere so oft zerschneiden, bis nur mehr Stucke übrig sind, die genau ein Kästchen groß sind.
Dazu wählen Sie in jedem Schritt aus dem vor Ihnen liegenden Haufen genau ein Papierstück, welches noch größer als ein Kästchen ist. Dieses Stuck zerschneiden Sie entlang einer beliebigen Gerade in zwei Teile. Sind nur mehr 1 x 1 große Stucke übrig, sind Sie fertig. Die jeweils gewählte Schnittgerade ist strichliert gezeichnet. Es gibt natürlich viele weitere Pfade, um dieses Papierstück zu zerschneiden. Beweisen Sie: egal wie und in welcher Reihenfolge Sie Ihr Papier zerschneiden, Sie werden immer genau n - 1 Schnitte brauchen.
3 Antworten
Ich habe es noch nicht zur Gänze durchdacht, aber: fange von hinten an:
Der letzte Schnitt ist das Trennen der Kästchen eine 2*1 Rechtecks.
Da es auf der Grund der Schnittführung immer nur Rechtecke (bzw als Sonderfall: Quadrate) geben kann (und keine "komplizierteren) Formen, gibt es für die Entstehung eines 2*1 Rechtecks nur folgende Möglichkeiten:
Es entstand aus einem d*1 Rechteck oder aus eine e*2 Rechteck.
Als Lösungsidee: Vollständige Induktion über die Anzahl Kästchen.
Wenn du ein Stück Papier mit n Kästchen hast und es an einer Stelle schneidest, hast du zwei Teile mit einmal p und einmal q Kästchen mit p + q = n. Nach IV sind das also p-1 Schnitte + q-1 Schnitte + den einen Schnitt, den wir gemacht haben, um das ursprüngliche Papier mit n Kästchen zu teilen. Mit p + q = n ergibt sich dann n-1-1+1 = n-1.
Tipp: Wie verändert sich die Anzahl der Papierstücke durch einen Schnitt?
Die Überlegung ist wohl wesentlich effizienter als meine!