Chat Prasátek

Matematická sekce

Miško | org | 16. 11. 2013 00:05:51

Ja mám niečo trochu menej stredoškolské a trochu viac informatické. Jedná sa o Halting problem.

Slávna veta z teoretickej informatiky hovorí, že neexistuje program, ktorý rozhodne, či daný program na danom vstupe skončí. (Čiže vstup tohoto programu je: nejaký program $\textstyle P$ , a vstup $\textstyle V$ pre tento program). Učene hovoríme, že neexistuje algoritmus riešiaci Halting problem.

Relatívne jednoduchý dôsledok tej to vety je, že neexistuje program ktorý rozhodne, či daný program skončí pre každý vstup. (Tentokrát je teda vstup iba program $\textstyle P$ ).

A teraz príde to zaujímavé. Predstavme si na chvíľu, že by taký program existoval, nazvime ho Mlynček. Potom by sme vedeli algoritmicky rozhodnúť, či platí hypotéza prvočíselných dvojčiat! Ako? Vytvorme program $\textstyle P$ ktorý na vstupe dostane číslo $\textstyle n$ , a postupne bude overovať, či čísla $\textstyle k, k+2$ sú obe prvočísla pre $\textstyle k \geq n$ . Ak by sme vedeli, že skončí pre každé $\textstyle n$ , tak je hypotéza pravdivá, ináč neplatí.

Nie je ťažké si rozmyslieť, že podobným trikom by sme vedeli rozhodnúť o platnosti Veľkej Fermatovej vety alebo Collatzovho problému. Môžeme však úvahu posunúť o rád ďalej: ak by Mlynček existoval, vedeli by sme algoritmicky overiť platnosť každej matematickej vety!
+ skrytý text

Majme matematickú vetu $\textstyle V$ . Zostrojme program $\textstyle P$ , na jeho vstupe nebude záležať. $\textstyle P$ bude postupne prechádzať všetky možné dokazy -- to ide, pretože dôkaz je len konečná postupnosť písmen -- a pre každý overí, či je to dôkaz pre $\textstyle V$ . Ak Mlynček povie, že $\textstyle P$ skončí, tak vieme, že veta platí. (Aby to celé fungovalo, musíme nejak rozumne vedieť povedať, čo je to veta, čo je to dôkaz, a musíme vedieť algoritmicky overiť správnosť dôkazu. To sa dá.)

Záver? Možno teoretická informatika má viac spoločného so základmi matematiky, než si myslíme. Možno dôkazy a algoritmy sú v skutočnosti veľmi príbuzné. Možno som len okľukou dokázal, že Mlynček nemôže existovať, pretože matematické vety nejde rozhodovať algoritmicky. A možno iba celý čas zavádzam. Či nie?

E.T. | org | 9. 11. 2013 20:10:18

Ahoj,

je tu další várka hintů. (Pro všechny, kteří v anketě zvolili poslední možnost jen opakuji, že po termínu odeslání každé série se na našich stránkách objeví hinty ke všem úlohám dané série, abyste si mohli dořešit ty úlohy, které jste sami nerozlouskli. Víc toho najdete zde na matematickém chatu v příspěvku s prvními hinty.) Nyní k samotným radám:

obecná:
+ skrytý text

Přečtěte si název série a zkuste jej nějak využít při řešení. Hledejte tedy nějaké podobné trojúhelníky nebo nějaké jiné útvary.

úloha 1:
+ skrytý text

Najděte 4 čísla $\textstyle a, b, c, d$ taková, že $\textstyle \frac{a}{b}=\frac{b}{c}=\frac{c}{d}$ a že trojice $\textstyle a, b, c$ a $\textstyle b, c, d$ splňují trojúhelníkovou nerovnost.

úloha 2:
+ skrytý text

Ukažte že $\textstyle \triangle BCP$ a $\textstyle \triangle DEP$ jsou rovnoramenné a navzájem podobné. ( $\textstyle P$ je průsečík $\textstyle BE$ a $\textstyle CD$ .)

úloha 3:
+ skrytý text

Ukažte, že $\textstyle \triangle KBA$ a $\textstyle \triangle KDY$ jsou podobné. Stejně tak jsou podobné $\textstyle \triangle KXB$ a $\textstyle \triangle KAD$ . Navíc je koeficient podobnosti stejný.

úloha 4:
+ skrytý text

Středy úseček $\textstyle BM, AM, AO, BO$ po řadě označme $\textstyle W, X, Y, Z$ . Ukažte, že pak čtyřúhelník $\textstyle WXYZ$ je kosočtverec. Tedy, že má všechny strany stejně dlouhé a dvojice protějších stran rovnoběžné.

úloha 5:
(i)+ skrytý text

Pomocí zadaných rovností úhlů najděte dvě vhodné dvojice podobných trojúhelníků.

(ii)+ skrytý text

Podobnosti zapište jako rovnosti poměrů délek stran. Tyto rovnosti vhodně upravte a sečtěte.

úloha 6:
(i)+ skrytý text

Dokažte podobnost $\textstyle \triangle BO_1C\sim \triangle AO_2D$ .

(ii)+ skrytý text

Dokažte podobnost $\textstyle \triangle BO_1E\sim\triangle AO_2E$ .

úloha 7:
(i)+ skrytý text

Zobrazte bod $\textstyle D$ ve stejnolehlosti, která zobrazuje $\textstyle C$ na $\textstyle A$ a $\textstyle B$ na $\textstyle E$ . Jeho obraz si označme $\textstyle D_1$ .

(ii)+ skrytý text

Ukažte, že čtyřúhelník $\textstyle AD_1DE$ je tětivový.

úloha 8:
(i)+ skrytý text

Označme středy $\textstyle \triangle MKB, \triangle MKA$ postupně $\textstyle I_1$ , $\textstyle I_2$ . Ukažte, že $\textstyle \triangle MKA, \triangle MBK$ a $\textstyle \tringle MI_1I_2$ jsou navzájem podobné.

(ii)+ skrytý text

Ukažte, že "směr" přímky $\textstyle I_1I_2$ je přesně "mezi směry" přímek $\textstyle AK, BK$ .

Přeji příjemné řešení.

pozn.: Jen připomínám, že se nás můžete zeptat na jakékoliv další hinty a my vám je rádi dáme. Můžete si radit i navzájem či zde prezentovat svá řešení, ale prosíme vás, abyste tak činili minimálně den po termínu odeslání úloh příslušné série.

@Rado (návrh na přesun hintů jinam): Možná u příštích sérií. Uvidíme. ;-)

Miroslav Olšák | org | 7. 11. 2013 02:03:45

To se vám to řeší, když umíte (narozdíl ode mně) řešit Apollionovy úlohy.

To prohazování (Problém 17) je nějak jasné :-)
+ skrytý text

Je to n-1 prohození.
To stačí:+ skrytý text

Prohazuji postupně sousední dvojičky zprava doleva.

a je potřeba:+ skrytý text

V každém kroku posunu doprava jenom jedno číslo.

Problém 18: V rovině je dáno několik bodů, každému je přiřazeno nezáporné reálné číslo nepřevyšující 1006 a navíc vzdálenost žádných dvou bodů nepřevyšuje rozdíl jejich hodnot. Ukažte, že je možné tyto body ohraničit uzavřenou křivkou délky menší než 2013.

Josef Tkadlec | 7. 11. 2013 00:32:54

petr: Na druhý pokus jsem nápovědu pochopil. Hodně, hodně dobré :).

Tak teď co s tím BakyXovým přehazováním dvojic?

petr | 29. 10. 2013 19:59:08

To katka - k elipse - nápověda jak dál
+ skrytý text

Představte si kružnici se středem v tom zadaném bodě elipsy, procházející zadaným ohniskem, přidejte ty dva body, které již máte (zrcadlové obrazy ohniska podle tečen) a řeště standardní apolloniovu úlohu kružnice-bod-bod. Pochopitelně potřebujeme vnitřní dotyk.

katka | 28. 10. 2013 02:38:41

Aby sa na to celkom nezabudlo, napisem nieco k tej elipse.

Zial, zatial sa mi s tym problemom podarilo pohnut len trochu. Konkretne, prisla som na toto:
+ skrytý text

Viem zostrojit priamku, na ktorej lezi druhe ohnisko (vyuzivam pri tom len tie 2 dotycnice a ohnisko, ten bod elipsy nie).

Ako na to? Dam len drobnu, trochu mysticku napovedu :)
+ skrytý text

uhol odrazu sa rovna uhlu dopadu...

A z toho je zrejme, ze treba uz "len"
+ skrytý text

najst to druhe ohnisko pomocou toho jedneho zadaneho bodu elipsy.

Lenze ja zatial neviem ako. Mozno to bude vediet niekto dokoncit, a mozno ma presvedcite, ze tadialto cesta nevedie :)

BakyX | 27. 10. 2013 01:02:33

Super, takže:

Riešenie problému 16:

+ skrytý text

Pomocný odhad:

$\textstyle \frac{9}{a+b^2+c^3} \leq a^3+b^2+c$ , pretože $\textstyle (a^3+b^2+c)(a+b^2+c^3) \ge (a^2+b^2+c^2)^2=9$ .

Ak tak odhadneme každý člen ľavej strany a navyše použijeme $\textstyle a+b+c \leq 3$ , čo plynie z $\textstyle (a^2+b^2+c^2)(1+1+1) \ge (a+b+c)^2$ , tak dostávame presne to, čo chceme.

Problém 17:

Máme danú usporiadanú $\textstyle n$ -ticu $\textstyle (1,2,...,n)$ . V jednom kroku môžeme urobiť vzájomnú výmenu dvoch čísel v tejto $\textstyle n$ -tici. Najmenej koľko krokov potrebujeme, aby sme dosiahli $\textstyle n$ -ticu $\textstyle (n,1,2,...,n-1)$ ?

Rado | 27. 10. 2013 00:22:10

Jajks. Samozřejmě jsem strašně hloupý a zapomněl jsem dopsat podmínku: $\textstyle a^2+b^2+c^2=3$ . Teď už by to snad mělo fungovat :)

Xellos | 27. 10. 2013 00:06:14

Fakt. Dokonca ked a,b,c idu do nuly, tak L strana ide do nekonecna a prava do 6. Nechce to vazbu nahodou?

BakyX | 26. 10. 2013 23:33:09

Tá nerovnosť je akosi divná, napr. neplatí pre $\textstyle a=b=c=\frac{1}{2}$ .

Rado | 26. 10. 2013 16:40:27

No, elipsu neumim, ale zato umim vyřešit problém 15 (který byl nesprávně nazván jako problém 14).

Řešení problému 15: + skrytý text

Nechť $\textstyle C$ je obraz bodu $\textstyle C$ podle $\textstyle P$ . Potom protože $\textstyle Q$ je obraz $\textstyle D$ v tomto zobrazení) $\textstyle DC$ , takže $\textstyle A$ , $\textstyle D$ a $\textstyle C$ leží na přímce. Analogicky pokud definujeme $\textstyle A$ jako obraz $\textstyle A$ podle $\textstyle Q$ a $\textstyle B$ jako obraz $\textstyle B$ podle $\textstyle D$ , dostaneme, že $\textstyle A$ leží na $\textstyle DC$ a $\textstyle B$ je průsečík $\textstyle PA$ a $\textstyle QC$ . K tomu $\textstyle AB\parallel CD\parallel C$ a $\textstyle AD\parallel PA$ . Chceme dokázat, že $\textstyle AA$ , $\textstyle BB$ a $\textstyle CC$ procházejí jedním bodem.
Nyní z vlastností rovnoběžníků a sinovky: $\textstyle {\sin BAA$ . Proto z analogických rovností dostaneme $\textstyle {\sin BAA$ , čímž jsme z goniometrické Cevovky hotovi.
Q.E.D.

Otázka k této úloze:+ skrytý text

Existuje jednoduší/hezčí způsob, jak dokázat, že $\textstyle AA$ , $\textstyle BB$ a $\textstyle CC$ se protínají v jednom bodě? Ještě to umím analyticky po tom, co se "velký rovnoběžník" afinně narovná na obdélník, ale to je celkem hnus...

Bonusová úloha pro zájemce na podobný princip: (její řešení sem nepište) + skrytý text

Máte daný trojúhelník $\textstyle \triangle ABC$ a dvě přímky $\textstyle p$ a $\textstyle q$ , které nejsou rovnoběžné a žádná z nich není kolmá k žádné ze stran trojúhelníka. Kolmice k $\textstyle p$ resp. $\textstyle q$ skrze $\textstyle A$ , resp. $\textstyle B$ , resp. $\textstyle C$ označíme postupně $\textstyle p_a$ , $\textstyle q_a$ , $\textstyle p_b$ , $\textstyle q_b$ , $\textstyle p_c$ , $\textstyle q_c$ . Průniky $\textstyle p_a$ , $\textstyle q_a$ , $\textstyle p_b$ , $\textstyle q_b$ , $\textstyle p_c$ , $\textstyle q_c$ postupně s $\textstyle q_b$ , $\textstyle p_b$ , $\textstyle q_c$ , $\textstyle p_c$ , $\textstyle q_a$ , $\textstyle p_a$ označíme postupně $\textstyle K,L,P,Q,M,N$ . Dokažte, že $\textstyle KL$ , $\textstyle MN$ a $\textstyle PQ$ se protínají v jednom bodě.

A nakonec problém 16: Pro kladná čísla $\textstyle a,b,c$ ukažte nerovnost ${9\over a+b^2+c^3}+{9\over a^2+b^3+c}+{9\over a^3+b+c^2}\le a^3+b^3+c^3+6$

Alena Skálová | 21. 10. 2013 21:31:52

Není, ale to není podstatné.
Důležité je, jak se řeší elipsa. (-:

OD | 21. 10. 2013 14:31:31

Zdravim,

je ta nejmenovana stredni skola z Brna? :-)

Alena Skálová | 20. 10. 2013 23:16:07

Ahoj,

mám úlohu, kterou neumím vyřešit ani já, ani žádný matikář z nejmenované střední školy (tam jsem se o ní dozvěděla). Je ze sbírky, takže řešitelná by snad být měla... no, posuďte sami. (-:

Je dáno jedno ohnisko elipsy, její dvě tečny a jeden bod elipsy. Nalezněte druhé ohnisko (samosebou rozumí se, že synteticky).

Pokud vyřešíte, dejte řešení prosím do spoileru, ať mohou zkoušet i ostatní. A budete-li umět dobře hintit, vítám... třeba to vyřeším aspoň s nápovědou. (-:

abstract nonsense | 19. 10. 2013 20:58:37

Reseni 14 + skrytý text

Postupujme sporem, predpokladejme
$\textstyle |a + b| \leq 1$
$\textstyle |b + c| \leq 1$
$\textstyle |c + a| \leq 1$
Sectenim dostaneme $\textstyle |a + b| + |b + c| + |c + a| \leq 3$ , z trojuhelnikove nerovnosti dostaneme $\textstyle 2|a + b + c| \leq |a + b| + |b + c| + |c + a|$ , tedy z tranzitivity plyne
$\textstyle |a + b + c| \leq \frac{3}{2}$
Pro $\textstyle a \neq -b$ je podminka ekvivalentni s $\textstyle c = \frac{1 - ab}{a + b}$ , dosazenim dostaneme
$\left|\frac{a^2 + ab + b^2 + 1}{a + b}\right| \leq \frac{3}{2}$
Pro dukaz ulohy nam tedy staci dokazat
$\left|\frac{a^2 + ab + b^2 + 1}{a + b}\right| > \frac{3}{2}$
Zrejme $\textstyle a^2 + ab + b^2 + 1 = \left(\frac{a}{2} + b\right)^2 + \frac{3a^2}{4} + 1 > 0$
1) Pokud $\textstyle a + b > 0$ , pak zrejme plati $\frac{(4a + 2b - 3)^2 + 12\left(b - \frac{1}{2}\right)^2 + 4}{16(a + b)} > 0$ ale tahle nerovnost je ekvivalentni s kyzenou $\frac{a^2 + ab + b^2 + 1}{a + b} > \frac{3}{2}$
2) Pokud $\textstyle a + b < 0$ , pak $\frac{(4a + 2b + 3)^2 + 12\left(b + \frac{1}{2}\right)^2 + 4}{-16(a + b)} > 0$ ale to je ekvivalentni s pozadovanou nerovnosti $\frac{a^2 + ab + b^2 + 1}{-(a + b)} > \frac{3}{2}$
3) Pokud $\textstyle a = -b$ , pak $\textstyle a^2 = -1$ a to je spor.

Problem 14
Nechť $\textstyle ABCD$ je rovnoběžník, bod $\textstyle P$ , resp. $\textstyle Q$ leží na přímce $\textstyle AB$ , resp. $\textstyle BC$ . Body $\textstyle P$ , $\textstyle Q$ , $\textstyle D$ jsou po řadě středy úseček $\textstyle QD$ , $\textstyle DP$ , $\textstyle PQ$ . Dokažte, že přímky $\textstyle AQ$ , $\textstyle BD$ , $\textstyle CP$ se protínají právě v jednom bodě.

Kenny | 19. 10. 2013 13:43:07

Oprava:

Ukažte, že nějaká dvě mají absolutní hodnotu součtu větší než jedna.

Kenny | 19. 10. 2013 13:33:00

Nazdar b..orci!

Na to, že tu úloha visí týden, to není taková hrůza.

Problém 13
+ skrytý text

Úseku 2000 po sobě jdoucích čísel budu říkat interval.

1) Rozdíl počtu modrých a červených je v každém intervalu sudý.
2) Pokud najdu jeden "modřejší" a jeden "červenější" interval, pak někde mezi nimi bude i interval vyrovnaný. Posouvám interval totiž po jedné a rozdíl se mění max. po dvou. Díky 1) nelze nula přeskočit.

3) Kdyby byly všechny intervaly modřejší, vezmu jich dost (stačí 501) navazujících. Vzniklá množina je tvořena po sobě jdoucími čísly a porušuje tak podmínku o celkovém rozdílu modrých a červených.

Problém 14

Pro reálná čísla $a,b,c$ platí, že $ab+bc+ca = 1.$

Ukažte, že nějaké dvě z těchto tří čísel mají součet větší než 1.

Bonus: Jakou největší konstantou lze nahradit jednička v tvrzení úlohy?

Servus aus Wien!

Miško | org | 18. 10. 2013 14:02:45

byk7: Ja si myslim, ze je to vec definicie, prave preto sa pytam. Mozno lepsia otazka by bola: "Co sa povazuje za 5-uholnik v matematickej olympiade?"

byk7 | 14. 10. 2013 21:19:51

@Misko: Takove OT, ale mam za to, ze $n$ -uhelnik, ma $n$ vnitrnich uhlu. Peticipa hvezda jich ma ale 10. Nebo se pletu?

Rado | 10. 10. 2013 14:56:28

Hinty jsou cool, ale (jestli je plánujete, jak jsem pochopil, zveřejňovat pravidelně) možná by nebylo od věci je nestrkat sem a místo toho pro ně vymyslet nějaké spešl místo :)

Není to úplně moje starost, ale rád bych všem připomněl, že je v běhu první série TRiKS, že na ní zbývají už jen čtyři dny a (protože já už ji mám za sebou) potvrdit, že je fakt cool :) (a taky, že je i pro orgy).

A co se týče maramatonu, jsem rád že se to takhle rozběhlo a tudíž bych rád taktéž přispěl svou troškou, takže: Problém 12:
+ skrytý text

Nechť průsečík $\textstyle EA$ a $\textstyle AB$ s $\textstyle CD$ jsou body $\textstyle X$ a $\textstyle Y$ . Protože úhly $\textstyle \angle AED$ a $\textstyle \angle CDE$ jsou shodné, jsou shodné i $\textstyle \angle XED$ a $\textstyle \angle XDE$ , takže $\textstyle XDE$ je rovnoramenný trojúhelník, takže osa úsečky $\textstyle BC$ splývá s osou úhlu $\textstyle \angle EXD$ , neboli s osou úhlu $\textstyle \angle AXY$ . Analogicky osa $\textstyle BC$ splývá s osou $\textstyle \angle BYC=\angle AYX$ , takže tyto osy se protínají ve vepsišti $\textstyle \triangle AXY$ , tudíž tímto bodem prochází i osa $\textstyle \angle XAY$ , neboli osa $\textstyle \angle EAB$ , což jsme chtěli dokázat.
Q.E.D.

Problém 13: Každé celé číslo obarvíme červenou nebo modrou barvičkou. Víme, že v libovolné množině za sebou jdoucích čísel je absolutní hodnota rozdílu počtu červených a modrých čísel maximálně 1000. Ukažte, že existuje 2000 za sebou jdoucích čísel, mezi kterými je právě 1000 modrých (a právě 1000 červených).

<< < 1 2 ... 13 14 15 ... 36 37 > >>

Kontakt

email	info (zavináč) prase.cz
pošta	Matematický korespondenční seminář KAM MFF UK Malostranské náměstí 25 118 00 Praha 1

Organizátoři

Matematický korespondenční seminář je organizovaný studenty Matematicko-fyzikální fakulty UK pod záštitou Informatického ústavu UK a Oddělení propagace a mediální komunikace MFF UK.

Partneři

Realizace projektu byla podpořena Ministerstvem školství, mládeže a tělovýchovy

Matematický korespondenční seminář

Kalendář

Z naší fotogalerie

Kontakt

Organizátoři

Partneři