Úlohy pro 1. cvičení k MAIII 2. 10. 2013 1. Dokažte trojúhelníkovou nerovnost pro Hammingovu metriku na slovech délky n. ------------------------------------------------------------ Řešení: Nechť u, v a w jsou 3 slova délky n. Jako de(x, y) (Kroneckerovo delta) označíme fci, co je 0 pro x=y a jinak je 1. Pro každou z n souřadnic i= 1, 2, ... , n máme nerovnost de(u_i, v_i) <= de(u_i, w_i) + de(w_i, v_i) --- když je levá strana 1, tj. u a v se v i-té souřadnici liší, pak se nutně w_i liší od u_i nebo od v_i a pravá strana je 1 nebo 2, a v ostatních případech platí nerovnost triviálně. Sečtením těchto n nerovností dostaneme přesně trojúhelníkovou nerovnost pro Hammingovu metriku. ------------------------------------------------------------ 2. Dokažte trojúhelníkovou nerovnost pro grafovou metriku na souvislém grafu (vzdálenost dvou vrcholů je délka nejkratší spojující cesty). ------------------------------------------------------------ Řešení: ------------------------------------------------------------ 3. Ukažte, že z troj. nerovnosti a axiomu d(x,y)=0 iff x=y plyne nezápornost metriky. ------------------------------------------------------------ Řešení: ------------------------------------------------------------ 4. Plyne symetrie (tj. d(x,y) = d(y,x)) z ostatních axiomů metriky? ------------------------------------------------------------ Řešení: Ne, např. funkce f na 2-prvkové množině M = {a, b} daná hodnotami f(a, a) = f(b, b) = 0, f(a, b) = 1 a f(b, a) = -1 splňuje axiom (i) (=0 iff argumenty rovné) i axiom (iii) (troj. nerovn.), ale není symetrická. ------------------------------------------------------------ 5. Dokažte trojúhelníkovou nerovnost pro euklidovskou vzdálenost v rovině. ------------------------------------------------------------ Řešení: ------------------------------------------------------------ 6. Totéž v R^n. Návod: pomocí Cauchyho-Schwarzovy nerovnosti (a_1b_1+...+a_nb_n)^2 <= (a_1^2+...+a_n^2)(b_1^2+...+b_n^2). Tu dokažte též. ------------------------------------------------------------ Řešení: ------------------------------------------------------------ 7. Dokažte, že žádný sférický vrchlík (část sféry odseknutá rovinou) se sférickou metrikou není izometrický množině v R^n s euklidovskou metrikou. [To je patrně těžší.] ------------------------------------------------------------ Řešení: ------------------------------------------------------------ 8. Dá se libovolný trojúhelník na sféře (se sférickou metrikou) izometricky realizovat v rovině (s euklidovskou metrikou)? ------------------------------------------------------------ Řešení: Ano, protože libovolný trojúhelník T v libovolném metr. prostoru M se dá izometricky realizovat v rovině. Nechť a >= b >= c jsou délky stran T. Podle tr. nerovnosti platí, že a <= b+c. Pro každou takovou trojici reálných čísel se snadno sestrojí rovinný trojúhelník s délkami stran a, b, c. Vezmeme úsečku v rovině U s délkou a a opíšeme kružnici K se středem v jednom konci U a poloměrem b a kružnici L se středem v druhém konci U a poloměrem c. K a L se protínají - protože existuje bod x na L, jenž leží uvnitř či na K, a bod y na L, jenž leží na K či vně K. Body x a y jsou průsečíky L s přímkou procházející U. Konce úsečky U a průsečík K a L tvoří hledaný trojúhelník. ------------------------------------------------------------ 9. Dokažte, že v ultrametrice je každý trojúhelník rovnoramenný. ------------------------------------------------------------ Řešení: Nechť a >= b >= c jsou délky stran trojúhelníka v ultrametrickém prostoru. Pak a <= max(b, c) = b, takže a <= b a tedy a = b. ------------------------------------------------------------ 10. Dokažte, že p-adická vzdálenost zlomků je ultrametrika. ------------------------------------------------------------ Řešení: p-adickou normu označíme jako |...|. Stačí ukázat, že pro každá dvě celá čísla a, b je |a + b| <= max(|a|, |b|). (|...| je multiplikativní, takže pro obecné zlomky a, b vše přenásobíme vhodným přir. číslem a převedeme úlohu do Z.) Což je, podle definice |...|, ekvivalentní s nerovností ord_p(a + b) >= min(ord_p(a), ord_p(b)). A ta je snad celkem jasná: je-li p^k (resp. p^l) nejvyšší mocnina p dělící a (resp. b) a např. k <= l, pak p^k dělí i b a tedy i a + b, což dává tu nerovnost. ------------------------------------------------------------