Matematické Fórum

Andrejka3

Ahoj,
$n \in \mathbb{N}, \;(a_i)_{i=1}^n,\:(b_i)_{i=1}^n \subset \mathbb{R} \text{ (psl)}$ .
$a_i \neq a_j,\:b_i \neq b_j \text{ pro }i \neq j \Rightarrow \exists \text{ ppsl indexů }(i_j)_{j=1}^{k}:\; a_{i_j}, \text{ resp. }b_{i_j} \text{ ryze monotónní}\;,$
kde $k:=\left\lceil \sqrt[4]{n} \right\rceil$ .

Potřebuji to dokázat

Mám k dispozici větu:

Autor skryl část textu. Zobrazit/skrýt!

Protože zadání považuju za jakési rozšíření Erdös-Szekeres lemmatu na problém s + 1 dimenzí (dvě posloupnosti místo jedné), doufala jsem, že důkaz bude možné provést podobně.

Pokus:

Autor skryl část textu. Zobrazit/skrýt!

Anebo antiřetězec definovaného uspořádání mi k ničemu není? Připadá mi, že abych interpretovala, co pro posloupnosti antiřetězec znamená, musela bych probrat příliš mnoho možností.

Andrejka3

↑ Andrejka3:
Napadlo mě zkusit roztřídit ty možnosti jinak. Sporem, mějme aspoň tříprvkový antiřetězec (menší triviální). Předpokládejme, že příslušné podposloupnosti jím určené nejsou monotónní (a nebo b podposl.)
To mě rozčlení na případy, kdy dva jsou symetrické (právě jedna z ppsl není monotonni). Pokud z toho vyjde spor, už to nějak dodělám.

Pak teda existuje triprvkovy antiretezec s vlastnosti vyse.
1. moznost: prave jedna neni monotonni:

Vlevo je a vpravo je b a dostala jsem spor, protože prostredni a treti index jsou porovnatelne.
Je jasne ze je jedno jestli ta druha bude rust nebo klesat. Je jedno jestli ta prvni bude tvaru v nebo obraceneho v.

2. moznost: obe nejsou monotonni:
obě `v' no nic jdu spat, protoze delam chyby.

Andrejka3 · 09. 01. 2013 05:59

↑ Andrejka3:
Už asi vím. Ten předchozí postup nikam nevede.
Použiju tu větu dvakrát za sebou. :D

Andrejka3

↑ Andrejka3:
Použijme nejdříve větu z úvodního příspěvku na posloupnost $(a_i)$ , abychom dostali monotónní podposloupnost $a_{i_j}$ a pak na podposloupnost $b_{i_j}$ , abychom vybrali monotónní podposloupnost $b_{i_{j_m}}$ . Takto, $i_{j_m}$ je rostoucí posloupnost indexů (tranzitivita). Ubráním některých prvků z $(a_{i_j})$ jsme charakter monotónnosti podposloupnosti nezměnili. Zbývá spočítat odhady délky podposloupnosti.\\
Označme $P_1$ , resp. $P_2$ uspořádanou množinu indexů, resp. uspořádanou množinu podposloupnosti indexů při prvním, resp.~druhém použití věty.

Autor skryl část textu. Zobrazit/skrýt!

Pro $n \in \mathbb{N}$ platí
$\left( \left\lceil \sqrt{n} \right\rceil -1 \right)^2 < n \;,$

Autor skryl část textu. Zobrazit/skrýt!

tedy musí být $\alpha (P_1) \geq \left\lceil \sqrt{n} \right\rceil \:\vee \: \omega (P_1) \geq \left\lceil \sqrt{n} \right\rceil$ , jinak by jejich součin byl menší než $n$ .
Využitím tohoto poznatku podruhé za sebou máme dolní odhad pro řetězec nebo antiřetězec $P_2$ (tedy délku hledané podposloupnosti)
$\left\lceil \sqrt{\left\lceil \sqrt{n} \right\rceil} \right\rceil \;.$
Teď si musím rozmyslet, zda $\left\lceil \sqrt{\left\lceil \sqrt{n} \right\rceil} \right\rceil = \left\lceil \sqrt[4]{n} \right\rceil$ .
Je to pravda nebo není?

Andrejka3

↑ Andrejka3:
Je $x^{1/4}=\left(x^{1/2} \right)^{1/2} \leq \left( \left\lceil \sqrt{x} \right\rceil \right)^{1/2}$ , odkud
$\left\lceil \sqrt{\left\lceil \sqrt{n} \right\rceil} \right\rceil \geq \left\lceil \sqrt[4]{n} \right\rceil$ .
To by mě prozatím k důkazu stačilo, ale nevíte někdo, jak to je s tou obrácenou nerovností?

Edit: Ta platí.
Buď $n \in \mathbb{N}$ . Existuje právě jedno $k \in \mathbb{N}: \; \sqrt[4]{n} \in [k-1,k]$ .
Pak ale $\sqrt{n} \in [(k-1)^2,k^2]$ a tedy $\left\lceil \sqrt{n} \right\rceil \in [(k-1)^2,k^2]$ a tedy
$\sqrt{\left\lceil \sqrt{n} \right\rceil} \in [k-1,k]$ . Takže platí rovnost.

Je jasné, jakým způsobek lze zobecnit tento problém na libovolné konečné množství posloupností. Příklad mi taky umožnil zpřesnit odhad veličiny: $d(n):=\min \{\max\{\alpha (P),\omega (P)\}; |X|=n\}$ , jež je dolním odhadem pro minimální délku maximální monotónní podposloupnosti dané reálné posloupnosti o n členech. Tento odhad je
$d(n) \geq \left\lceil \sqrt{n} \right\rceil$ a asi už nelze zlepšit (stejně tak obdoba u většího počtu (k) posloupností $d_k(n)=\left\lceil \sqrt[2k]{n}\right\rceil$ )..(?)
To je předmětem dalšího příkladu. Zdálo se mi to zajímavé.