Matematické Fórum

flowergo · 29. 02. 2016 20:59

Ahojte, potřebovala bych poradit z touto úlohou :

Uvažte mřížku mxn, kde m a n značí počet horizontálních a vertikálních čar. a) kolik existuje obdélníků, jejichž strany leží na této mřížce ? (Čtverec je speciální případ obdélníku)
b) kolik existuje dvojic disjunktních obdélníků, jejichž strany leží na této mřížce ? (uvažte, že je o uzavřené obdélníky, tedy včetně hranice)

U toho a) mě napado napřed tvořit jednoprvkové (z jednoho čtverečku), pak ze dvou (na stojato, na ležato), podobně ze tří, pak čtverce... až do m x n, ovšem vůbec netuším, jak dojít k nějakému vzorci...

Díky,

vanok · 01. 03. 2016 02:16

Ahoj ↑ flowergo:
A) mozes vyuzit, ze kazdy obdlznik je urceny jeho diagonalou.

vanok · 01. 03. 2016 08:39 — Editoval vanok (01. 03. 2016 08:41)

Doplnok A)
Ina metoda je uvazovat pocet vsetkych obdlznikov podla ich rozmerov... a potom scitat vsetki najdene vysledky.

zdenek1 · 01. 03. 2016 11:32

↑ flowergo:

a) ${m\choose2}\cdot{n\choose2}$

vanok · 01. 03. 2016 11:54

↑ zdenek1:,
Pozdravujem, to iste som aj ja nasiel.

Rumburak

↑ flowergo:

Ahoj.

Zdravím i ostatní účastníky vlákna.

Ad b.

Představme si to obecněji v rovině $\mathbb{R}^2$ s obdélníky, jejichž strany jsou rovnoběžné s navzájem kolmými souřadnicovými osami.

Takto orientovaný obdélník má úlopříčku $AC$ , jejíž krajní body $A = [x_A, y_A] , C = [x_C, y_C]$ splňují podmínku
$x_A < x_C \wedge y_A < y_C$ , při čemž uvažovaný obdélník je takovouto úhlopříčkou jednoznačně určen. Označme ho $\Omega_{AC}$ .

Kdy jsou obdélníky $\Omega_{AC} , \Omega_{PQ}$ disjunktní ?

flowergo

Ahojte všichni,
moc děkuju za odpovědi, ale pořád to neřeší úplně můj problém :/ Pokud si vezmu, že je obdélník určený svou diagonálou, tak si řeknu, že budu brát například diagonálu z levého horního do pravého dolního rohu.

Vyberu-li bod na pozici [1,1] - vlevo nahoře, tak mám (m-1)(n-1) možností, jak vybrat druý bod a tedy druhý obdélník.

Pro bod [2,1] je to (n-1)(m-2) možností atd... ale neumím z toho vykoukat ${m\choose2}\cdot{n\choose2}$ :/

↑ Rumburak:
obdélníky jsou disjunktní, pokud $x_P > x_C$ nebo $x_P <x_A$ a podobně pro y-souřadnici. Ale asi pořád nevidím, jak to spočítat pro obecné m,n ...

edit : to a) už mi došlo :) ale s tím b si pořád uplně nevím rady

zdenek1 · 03. 03. 2016 07:46

↑ flowergo:
k (a) Obdélník je jednoznačně určen dvěma vodorovnými a dvěma svislými stranami.
Vodorovné můžeš vybrat ${m\choose2}$ způsoby a svislé ${n\choose2}$ způsoby. + pravidlo kombinatorického součinu

Rumburak

↑ flowergo:

Situaci, kdy počet horizontálních přímek (tvořícich množinu $H$ ) je $m$ a počet vertikálnách přímek
(tvořícich množinu $V$ ) je $n$ , můžeme umístit do $\mathbb{R}^2$ tak, že

$H$ bude obsahovat právě všechny přímky o rovnicích $y = j$ , kde $j = 1, 2, ..., m$ ,

$V$ bude obsahovat právě všechny přímky o rovnicích $x = i$ , kde $i = 1, 2, ..., n$ .

Zrekapitulujme, co jiiž je jasné. Obdélníky

$\Omega_{AC}$ (charakterisovaný úhlopříčkou $AC$ ) , kde $x_A < x_C \wedge y_A < y_C$ ,
$\Omega_{PR}$ (charakterisovaný úhlopříčkou $PR$ ) , kde $x_P < x_R \wedge y_P < y_R$ ,

mají NEprázdný průnik, tj. NEJSOU disjunktní, právě tehdy, když

$(\langle x_A , x_C \rangle \cap \langle x_P , x_R \rangle \ne \emptyset) \wedge (\langle y_A , y_C \rangle \cap \langle y_P , y_R \rangle \ne \emptyset)$ .

Negací této podmínky dostaneme podmínku, kdy dotyčné obdélníky disjunktní JSOU.
Počet dvojic disjunktních obdélníků v naší úloze bude funkcí $f(m, n)$ proměnných m,n.

Možná by šlo najít rekurentní předpis pro tuto funkci, tj. vyjádření tvaru

$f(m+1, n) = F(m, n, f(m, n))$ .

Zřejmě bude $f(m, n) = f(n, m)$ , čímž se to poněkud zjednoduší.

zdenek1 · 04. 03. 2016 14:26

↑ flowergo:
Upozornění : za správnost neručím, chtělo by to ještě nějakou kontrolu

Negací podmínky od ↑ Rumburak: máme
$(\langle x_A;x_C\rangle\cap \langle x_P;x_R\rangle=\emptyset ) \vee (\langle y_A;y_C\rangle\cap \langle y_P;y_R\rangle=\emptyset )$

Nechť $A$ je množina všech dvojic splňujících první podmínku, pak by mělo platit $|A|={m\choose4}{n\choose2}{n\choose2}$
Zdůvodnění: z množiny $\{1,\dots, m\}$ vyberu 4 čísla a seřadím je podle velikosti. Každou takto utvořenou upořádanou čtveřici budu interpretovat jako $[x_A;x_C;x_P;x_R]$
počet všech čtveřic ${m\choose4}$
Z množiny $\{1,\dots, n\}$ vyberu dvakrát dvojici čísel, každou dvojici uspořádám podle velikosti a interpretuji postupně jako $[y_A;y_C]$ a $[y_P;y_R]$
počet všech dvojic ${n\choose2}$

Analogicky
Nechť $B$ je množina všech dvojic splňujících druhou podmínku, pak by mělo platit $|B|={n\choose4}{m\choose2}{m\choose2}$

Nyní $|A\cap B|={m\choose4}{n\choose4}$

Podle PIE by mělo platit $|A\cup B|={m\choose4}{n\choose2}{n\choose2}+{n\choose4}{m\choose2}{m\choose2}-{m\choose4}{n\choose4}$