Welche Rechtecke kann man auf ein gegebenes Rechteck legen?
-
Hallo allerseits,
ich habe ein kleines Problem ... Und zwar habe ich folgende Problematik:
Ich habe eine Matrix mit z.B. 6*6 Feldern.x11 x12 x13 x14 x15 x16 x21 x22 x23 x24 x25 x26 x31 x32 x33 x34 x35 x36 x41 x42 x43 x44 x45 x46 x51 x52 x53 x54 x55 x56 x61 x62 x63 x64 x65 x66Die Frage ist nun:
Wieviele Möglichkeiten gibt es, vier xe auszuwählen, so dass die gewählten xe die Kanten eines Rechtecks bilden? Dazu sei gesagt, dass die Matrix quasi zur Seite und nach oben/unten miteinander verbunden sein soll.Auf gut deusch also:
Wie viele Möglichkeiten gibt es, vier Xe aus dieser Matrix "auszuwählen", so dass in genau zwei beliebigen Spalten jeweils genau 2 xe ausgewählt sind und in genau zwei beliebigen Spalten ebenfalls.
Eine Möglichkeit wäre also z.B. x11, x13, x41, x43.Meine Idee wäre folgende:
1. Schritt: Wähle ein x[1]. 66 Möglichkeiten.
2. Schritt: Wähle ein x[2], dass in derselben Zeile ist wie x[1]. 6-1 = 5 Möglichkeiten.
3. Schritt: Wähle ein x[3], dass in derselben Spalte ist wie x[1]. 6-1 = 5 Möglichkeiten.
4. Schritt: Wähle ein x[4], dass in derselben Spalte ist wie x[2]. 6-1 = 5 Möglichkeiten.
Also insgesamt 6*6*55 = 900 Möglichkeiten.Irgendwie habe ich aber ein ungutes Gefühl dabei. Ist meine Überlegung soweit richtig? Falls - was ich vermute - nicht, hat vlt. jemand einen Denkanstoß für mich? Ich tippe ansonsten nämlich völlig im Dunkeln ...
Vielen Dank schonmal
-
Sorry, da habe ich mich oben vertippt. Es soll natürlich heißen:
Wie viele Möglichkeiten gibt es, vier Xe aus dieser Matrix "auszuwählen", so dass in genau zwei beliebigen Zeilen jeweils genau 2 xe ausgewählt sind und in genau zwei beliebigen Spalten ebenfalls.
Danke
-
(Angenommen, jede Untermatrix muss mindestens 2 Zeilen und 2 Spalten enthalten, was deinem Ansatz nach gegeben ist. Ein einzelnes x22 wäre also kein gültiges 1x1-Rechteck.)
Ich würde sagen, du kannst Spalten und Zeilen getrennt betrachten, weil das eine das andere nicht beeinflusst. Wenn du A Möglichkeiten hast, zwei Spalten auszusuchen, und B Möglichkeiten für die zwei Zeilen, dann gibt es insgesamt A*B Möglichkeiten, ein Rechteck zu bilden.
2 aus 6 ungeordnet auswählen ist der Binomialkoeffizient $$\binom{6}{2}$$, was 15 ergibt. Insgesamt sollte es also 15*15 = 225 Möglichkeiten geben.
-
Hi!
Vielen Dank für deinen Ansatz.
Aber ich habe da noch so ein kleines Verständnisproblem:Gesetzt den Fall, ich wähle aus einer beliebigen Spalte 2 von den 6 xen aus, dann sind das $$\binom{6}{2}$ = 15$ Möglichkeiten. z.B.
x11 O x13 x14 x15 x16 x21 x22 x23 x24 x25 x26 x31 x32 x33 x34 x35 x36 x41 O x43 x44 x45 x46 x51 x52 x53 x54 x55 x56 x61 x62 x63 x64 x65 x66Dann habe ich doch keine 15 Möglichkeiten mehr für die Rechteckstruktur, sondern kann nur aus Folgenden Möglichketien wählen, weil die Position der festgelegten Spalten-Xe die Distanz der Zeilen-Xe zueinander eindeutig bestimmt, und ich diese quasi nur noch in den verbliebenen freien "Zeilen" verschieben kann:
(x11, x41) oder (x13, x43) oder
(x14, x44) oder (x15, x45) oder
(x16, x46)
Also 6-1 (weil eine Spalte schon "belegt" ist) = 5 Möglichkeiten?Demnach hätte $$\binom{6}{2} Möglichkeiten? Das erscheint mir aber wieder ziemlich wenig? Wo ist da mein Denkfehler?
Nochmal Danke
-
Och menno, schon wieder ... ich meinte natürlich "in den freien Spalten verschieben ..."
-
Mopp schrieb:
Hi!
Vielen Dank für deinen Ansatz.
Aber ich habe da noch so ein kleines Verständnisproblem:Gesetzt den Fall, ich wähle aus einer beliebigen Spalte 2 von den 6 xen aus, dann sind das $$\binom{6}{2}$ = 15$ Möglichkeiten. z.B.
x11 O x13 x14 x15 x16 x21 x22 x23 x24 x25 x26 x31 x32 x33 x34 x35 x36 x41 O x43 x44 x45 x46 x51 x52 x53 x54 x55 x56 x61 x62 x63 x64 x65 x66Dann habe ich doch keine 15 Möglichkeiten mehr für die Rechteckstruktur,...
Doch, hast du. Du hast beides Mal die Spalte "2" ausgewählt, das geht laut Aufgabe aber nicht. Ich nehme deswegen mal an, dass du zuerst die Zeilen auswählt und dann die Spalten.
Du hast also die Zeilen 1 und 4 ausgewählt (aber noch keine Elemente aus diesen Zeilen). Jetzt kannst du aus allen 6 Spalten 2 beliebige auswählen, zum Beispiel die Spalten 1 und 2. Wir haben also Zeilen 1, 4 und Spalten 1, 2, was dieses Rechteck beschreibt:
* * x13 x14 x15 x16 x21 x22 x23 x24 x25 x26 x31 x32 x33 x34 x35 x36 * * x43 x44 x45 x46 x51 x52 x53 x54 x55 x56 x61 x62 x63 x64 x65 x66Bei der Wahl der Spalten gab es keine Einschränkungen, also hat man 15 Möglichkeiten, die Spalten zu wählen, nachdem man die beiden Zeilen festgelegt hat.
-
Ohje ... Natürlich! Ich hab' nicht in Zeilen und Spalten gedacht, sondern in einzelnen Elementen, daher kam das Problem. Aber so betrachtet hast du natürlich Recht, logisch!
Vielen Dank für deine super Erklärung