Beweise: In einem rechteckigen Gitter mit x Spalten und y Zeilen lassen sich auf den Gitterlinien zeichnend 1/2*x*(x+1)*1/2*y*(y+1) verschiedene Rechtecke einzeichnen. |
Definition: Ich kürze obige Formel im folgenden mit R(x,y) ab.
Damit das Gitter einen Sinn macht, müssen x und y größer 0 sein. |
Wir wenden Induktion nach x+y an, zeigen also, daß die Behauptung für x+y=2 gilt (Induktionsanfang), und daß unter der Induktionsvoraussetzung Anzahl Rechtecke in einem Gitter mit x Spalten und y Spalten = R(x,y)der Induktionschritt auf x+y+1 möglich ist. |
Induktionsanfang: x+y=2 => Einziges mögliches Gitter besteht aus 1 Spalte und 1 Zeile. Es ist R(x,y) = 1 und tatsächlich kann man nur ein Rechteck zeichnen. |
Induktionsschluß: Ein rechteckiges Gitter mit Spalten und Zeilen sei gegeben und die Summe der Anzahlen der Zeilen und Spalten sei gleich x+y+1. |
Wir wissen nicht, aus wievielen Zeilen und Spalten das Gitter besteht, wir kennen nur deren Summe. Damit wir aber formulieren und rechnen können nennen wir die Anzahl der Spalten v und die Anzahl der Zeilen w. Natürlich muß gelten v>0 und w>0 und so wie es gemacht ist, ist v+w = x+y+1. |
Wir stellen uns dieses Gitter aufgezeichnet vor und markieren das rechte obere Quadrat (machen es "rot"). Die Spalten und Zeilen numerieren wir von 1 bis v bzw. von 1 bis w, so daß das rote Quadrat in der Spalte v und in der Zeile w liegt. |
Abbildung 2: Das Quadrat links oben färbe rot. Das rote Quadrat ist in Spalte v=6 und Zeile w=4. Die Anzahl der möglichen Rechtecke in diesem Gitter mit v Spalten und w Zeilen kann man nun disjunkt aufteilen in: |
A = Menge der Rechtecke, die das rote Quadrat nicht enthalten. |
Wir betrachten folgende Teilmengen der Menge A: |
A1 = Menge der Rechtecke ohne ein Quadrat aus der Spalte v Weil es Rechtecke gibt, die weder ein Quadrat aus der Spalte v noch eines aus der Zeile w enthalten, ist das keine disjunkte Zerlegung. Darum formulieren wir noch die Schnittmenge von A1 und A2 A3 = Menge der Rechtecke ohne ein Quadrat aus der Zeile w und ohne ein Quadrat aus der Spalte v Abbildung 3: Zählen der Rechtecke in verschiedenen Teilgittern mit weniger Spalten und Zeilen Die Menge A1 ist die Menge der Rechtecke in einem Gitter mit v-1 Spalten und w Zeilen
Die Menge A2 ist die Menge der Rechtecke in einem Gitter mit v Spalten und w-1 Zeilen.
Die Menge A3 ist die Menge der Rechtecke in einem Gitter mit v-1 Spalten und w-1 Zeilen.
Es gilt A3 = A1 Ç A2. In allen Fällen ist die Summe der Anzahl der Spalten und Zeilen kleiner v+w = x+y+1. Also gilt nach Induktionsvoraussetzung: |A| = |A1| + |A2| - |A3| = R(v-1,w) + R(v,w-1) - R(v-1,w-1)Bis hierhin haben wir alle Rechtecke, die das rote Rechteck nicht enthalten, gezählt, bzw. wir haben eine rekursive Formel für die Berechnung dieser Rechtecke gefunden. Nun betrachten wir die Menge B genauer. B ist die Menge der Rechecke, die das rote Quadrat enthalten. Gesucht ist |B|. Wenn das rote Quadrat in einem Rechteck enthalten ist, dann gehören 0 bis v-1 Quadrate der Zeile w und 0 bis w-1 Quadrate der Spalte v dazu. Wir können alle Rechtecke zählen, wenn wir jeweils eine Anzahl von Quadraten aus der Spalte v wählen (w Möglicheiten weil 0 bis w-1) und anschließend die Anzahl der Quadrate aus der Zeile w wählen von keines bis alle, also v Möglichkeiten. => Die Anzahl der Rechtecke mit dem roten Quadrat ist also gleich w*v = |B|. Damit können wir die Gesamtzahl der Quadrate in einem Gitter mit v Spalten und w Ecken angeben als (mit v+w=x+y+1): |A| + |B| = R(v-1,w) + R(v,w-1) - R(v-1,w-1) + v*w Schreiben wir die durch R(,) gemeinten Formel hin: |A|+|B| = 1/4 * (v-1)*v*w*(w+1) + 1/4 *v*(v+1)*(w-1)*w - 1/4 *(v-1)*v*(w-1)*w + v*wNun kann man durch Termumformungen die Gleichheit mit dem zu beweisenden Ausdruck R(v,w) = 1/2*v*(v+1)*1/2*w*(w+1)zeigen. q.e.d. |
|