Chat Prasátek

Matematická sekce

Miroslav Olšák | org | 20. 10. 2015 13:42:30

Přinejensím, když $a$ je prvočíslo, tak nevyjde $a$ -valuace, tedy to v takovém případě nemá řešení. Jinak nevím.

Ví se, že to má nějaké rozumný důkaz? Podobné diofantické rovnice jsou leckdy otevřený problém. Hodně známá je velká Fermatova věta (řešte $a^n+b^n=c^n$ pro $a,b,c,d$ přirozená a $n>2$ ), která byla dokázána nedávno a dost složitě.

Pokud vím, tak například je dosud otevřený problém, zdali má rovnice $n!+1=a^2$ víc než tři celočíselná řešení (a to ta tři řešení jsou do první desítky).

Ondra | 19. 10. 2015 23:15:27

Já se dostal pouze k tomuto
$\textstyle \left\lfloor\sqrt{a^a+a!-1}\right\rfloor^2<a^a+a!=\left(\sqrt{a^a+a!-1}-1\right)^2+2\sqrt{a^a+a!-1}<\left\lfloor\sqrt{a^a+a!-1}\right\rfloor^2+$ $\textstyle +2\sqrt{a^a+a!-1}<\left\lfloor\sqrt{a^a+a!-1}\right\rfloor^2+2\left(\left\lfloor\sqrt{a^a+a!-1}\right\rfloor+1\right)=$ $\textstyle =\left(\left\lfloor\sqrt{a^a+a!-1}\right\rfloor+1\right)^2+1$

Z toho ihned plyne, že pokud má rovnice řešení, pak nutně $\textstyle b=\left\lfloor\sqrt{a^a+a!-1}\right\rfloor+1$ , ale nic zajímavého se mi z toho vyzřískat nepodařilo...

Marek Pospíšil | 19. 10. 2015 19:58:14

Můj prvotní nápad byl rozložit levou stranu, neboť a! lze zapsat jako ((a umocněno na a) mínus něco), ale vyjádřit to něco může být docela fuška:-)Pak snad s tím tvarem dokážeš, že to nejde(což si osobně myslím...nebo si uhádnul nějaké řešení???). Čistě matematický postup bude asi dost komplikovaný a těžký, osobně bych to nějak doslepil úvahou...
Á propos: může se ti u toho hodit vědět, že 1+2+3+4+5=(5+5 na druhou)/2, což by mělo analogicky platit v rámci všech přirozených čísel.

Ondra | 16. 10. 2015 23:18:18

Ahojte, nevěděl by někdo, jak jít na rovnici $a^a+a!=b^2,a,b\in\mathbb N$ ? Na českém matfóru už leží pár měsíců bez odezvy a mi to přijde škoda. (:

Marián Poppr | 12. 10. 2015 23:59:26

Ahoj,
jsou tady nápovědy k první serii

úloha 1+ skrytý text

Dokáže Pepa na jednu otázku poznat, zda-li se ve dvojici PraSátek nachází vlk?

úloha 2+ skrytý text

Ano, může se mu to podařit. Podívejte se, pro jaké kružnice vyhovuje množina modrých bodů tvořící přímku.

úloha 3+ skrytý text

Místo králů prohazujte cesty. Kolik je cest? Může být stejně sypaných cest jako dlážděných?

úloha 4+ skrytý text

Můžeme se nezacyklit (můžeme navštívit patra nad patrem, kam nás pošle první teleport?)?+ skrytý text

Může být cyklus větší než dva? Kam bychom se v něm dostali z nejnižšího patra, na kterém cyklus probíhá, a kam zase toho nejvyššího?

úloha 5+ skrytý text

Pro spor předpokládejte, že žádná z 12 trojic neodbila vícekrát než 20. Ukažte, že nejvíce 20 mohla odbýt pouze každá druhá trojice (zbylé tedy nejvýše 19).+ skrytý text

Sečtěte nerovnosti a ukažte, že platí místo nerovností rovnosti a pak pro spor vhodnou kombinací několika rovnic ukažte, že dvě čarodějem přehozené cifry si jsou rovny.

úloha 6+ skrytý text

Mějme počty čarodějnic v domcích (A1,..,A99) , kde BÚNO A1 je různé od A2, a vezměme si skupinu (A1, A1+A2, A1+A2+A3,.., A1+..+ A99) a rozmyslete si, že v této skupině dává každý člen jiný zbytek po dělení stem + skrytý text

Vezměme si ještě obdobně skupinu (A2, A1+A2, A1+A2+A3,.., A1+..+ A99), no a nyní ukažte, že A1 a A2 dávají stejný zbytek po dělení stem

úloha 7+ skrytý text

Může existovat trpaslík, který krmí doplněk toho druhého? + skrytý text

Pokud existují trpaslíci, co dávají napapat množinám draků A a B, tak existuje i jejich průnik.+ skrytý text

Závěrem ukážeme existenci hledaného trpaslíka, jenž krmí průnik všech ostatních trpaslíků

úloha 8+ skrytý text

Štěpán může vyhrát+ skrytý text

Když odstraníme všechny obarvené vrcholy a hrany z nich vedoucí, tak se strom rozpadne na les. Štěpán se bude snažit udržovat stav, kdy všechny stromy z lesa sousedí maximálně se 2 obarvenými vrcholy. Proč 2?+ skrytý text

Nyní ukaž, že když všechny stromy z lesa sousedí maximálně se 2 obarvenými vrcholy, tak stačí Štěpánovi obarvit vrchol, jenž je v původním stromě spojen hranou nějakým již obarveným vrcholem+ skrytý text

Ukaž, že aby Mirek dokázal utvořit strom se 4 sousedícími obarvenými vrcholy nebo více se 3, tak se mu to musí podařit napoprvé, a pak dokaž, že se mu to nepodaří ani napoprvé

Radovan Švarc | 30. 9. 2015 17:39:18

A přichází dálší série TRiKS! Tato je pravděpodobně spíše těžší než minulá a větší výzva, ale to by vás nemělo odradit od jejího řešení! Naopak se jejím řešením jen více naučíte a více si prohloubíte své dosavadní znalosti. Proto hurá na http://iksko.org/triks/current.php!

David Hruška | org | 14. 9. 2015 22:34:41

A TriKS pokračuje! Od nejbližší půlnoci čtrnáct dní poběží nová soutěž, která je ještě lepší a jednodušší, než byla ta předchozí. Trénujte i Komputační Schopnosti!

Wanderer | 1. 9. 2015 15:49:05

Hezké vysvětlení a pomoc, nicméně já měl na mysli úlohu 8. z 1. podzimní série-"Je není jeden strom...", kdy pro "definici stromu spolu se všemi ostatními potřebnými definicemi" máme jít na mks.mff.cuni.cz/archive/34/uvod1s.pdf

Jinak souhlasím-není potřeba nic zvláštního na vyřešení úloh...

Miroslav Olšák | org | 29. 8. 2015 19:54:35

Ahoj, pro řešení první série není třeba žádná zvláštní teorie, hlavně umět dobře uvažovat a mít dobré nápady ;-) Univerzální textík napříč ročníky a sériemi (spíše pro začátečníky) je: http://mks.mff.cuni.cz/info/Jak.pdf

Někdy (což teď není případ první série) je k sérii ještě stručný doplňující text toho, co pokročilí řešitelé typicky znají, ale ostatním může pomoci. Obecný seznam sérií, textů k nim, případně i vzorových řešení je na stránce aktuálního ročníku ( http://mks.mff.cuni.cz/commentary/commentary.php ). Zatím jsme ale tuto stránku neaktualizovali na současný ročník.

A nakonec (asi to myslel Wanderer) tu bude seriál. Letošní seriál bude na téma "Do nekonečna a ještě dál". Seriál se zaobírá méně známou teorií než běžné série, takže je jeho doprovodný text výrazně delší. Seriál má tři navazující díly -- tři série a tři příslušné doprovodné texty.

Wanderer | 26. 8. 2015 20:15:47

Jediná věc, o níž vím, je sepsaný jakýsi seminář, kterých je tu nejspíš víc, a na který byl odkaz v podzimním zadání...

Sh4rP EYE | 20. 8. 2015 15:27:26

Ahoj, mám jen jednu takovou krátkou otázku. Je tady na stránkách nějaký odkaz na doporučenou teorii (nebo něco podobného), kterou je nutné znát k vyřešení aktualního zadání PraSete? Mám namysli nějaké teorémy, vzorce a podobně.

Vejtek | 3. 8. 2015 00:36:32

Řešení 4. úlohy: + skrytý text

Nakreslíme si grafy funkcí $5-x^2$ a $\sqrt{5-x}$
a všimneme si, že hledáme některá řešení soustavy
$5-y^2 = x \\5-x^2 = y$
Odečteme a upravíme na $(x-y)(x+y-1)=0$ . Nulovost první závorky
vede na kvadratickou rovnici $x^2+x-5=0$ s řešením $x=\frac{-1\pm\sqrt{21}}{2}$ , nulovost druhé závorky vede na rovnici $x^2-x-4$ s kořeny $x=\frac{1\pm\sqrt{17}}{2}$ . Mrknutím na původní obrázek vidíme, že řešením úlohy jsou čísla $\frac{\sqrt{21}-1}{2}$ a $\frac{1-\sqrt{17}}{2}$ .

Úloha 5. + skrytý text

Nalezněte všechny funkce $f\colon\mathbb{R}\setminus\{0\}\to\mathbb{R}$ splňující
$f(x) = x f(1/x)$ a $f(x + y) = f(x) + f(y) - 1$ pro všechna nenulová $x,y,x+y$ .

Tonda Le | org | 3. 7. 2015 06:00:50

Ahoj,
také chci přispět k maratonu.
Řešení 3.úlohy+ skrytý text

Uvažujme $\textstyle S_A,S_B,S_C$ Švrčkovy body oproti vrcholům $\textstyle A,B,C$ . Snadno vyúhlíme, že $\textstyle S_AS_B$ je kolmá na $\textstyle CI$ , a proto $\textstyle S_AS_B \parallel LM$ . Analogicky odvodíme dvě další podobné rovnoběžnosti, tudíž $\textstyle KLM$ a $\textstyle S_AS_BS_C$ jsou stejnolehlé a v této stejnolehlosti se střed kružnice opsané $\textstyle KLM$ , bod $\textstyle I$ , se zobrazí na střed kružnice opsané $\textstyle S_AS_BS_C$ , bod $\textstyle O$ , a ortocentrum $\textstyle KLM$ , bod $\textstyle U$ , se zobrazí na ortocentrum $\textstyle S_AS_BS_C$ , bod $\textstyle I$ . Celkově dostaneme, že $\textstyle U,I,O$ leží na jedné přímce.

Zadání 4. úlohy:+ skrytý text

Najděte všechna reálná x taková, že \sqrt{5-x}=5-x^2

Štěpán Šimsa | org | 28. 6. 2015 00:12:19

Ahoj. Jen malé upřesnění k onomu řešení: + skrytý text

Pro využití AG nerovností potřebujeme, aby $o, p, q$ byla kladná čísla. Ale snadno vidíme, že maximálně jedno z nich je záporné a pak nerovnost před přepsáním do těchto proměnných triviálně platí, protože levá strana je záporná a pravá kladná.

Josef Svoboda | 26. 6. 2015 19:09:03

Ahoj, nějak se to řešení 2. úlohy rozsypalo. Tady je ještě jednou:
+ skrytý text

Podmínky $abc=1$ se ekvivaletně zbavíme substitucí $a=x/y$ , $b=y/z$ , $c=z/x$ . Nerovnost přejde do tvaru $(x-y+z)(y-z+x)(z-x+y) \leq xyz$ . Pro důkaz této nerovnosti vyjděme z nerovnosti $opq \leq \frac{o+p}{2} \frac{p+q}{2} \frac{q+o}{2}$ , která je součinem tří jednoduchých AG nerovností. Naši nerovnost z ní dostaneme dosazením $o=x-y+z$ , $p=y-z+x$ a $q=z-x+y$ .

Josef Svoboda | 26. 6. 2015 18:24:40

Ahoj.
Pěkné řešení Danile! Protože Tvou úlohu už dva týdny nevyřešil, předkládáme naše řešení.
Řešení úlohy č.2:+ skrytý text

Podmínky $abc=1$ se ekvivaletně zbavíme substitucí $a=x/y$ , $b=y/z$ , $c=z/x$ . Nerovnost přejde do tvaru $(x-y+z)(y-z+x)(z-x+y) \\leq xyz$ . Pro důkaz této nerovnosti vyjděme z nerovnosti $opq \\leq \\frac{o+p}{2}\\frac{p+q}{2}\\frac{q+o}{2}$ , která je součinem tří jednoduchých AG nerovností. Naši nerovnost z ní dostaneme dosazením $o=x-y+z$ , $p=(y-z+x)$ , $q=(z-x+y)$ .

.

Zadání úlohy č.3:+ skrytý text

V trojúhelníku $ABC$ označme $KLM$ body dotyku kružnice vepsané se stranami trojúhelníka $ABC$ . Dále označme $O, I, U$ postupně střed kružnice opsané trojúhelníka $ABC$ , střed kružnice vepsané trojúhelníka $ABC$ a průsečík výšek trojúhelníka $KLM$ . Dokaž, že $O, I$ a $U$ leží v jedné přímce.

Pepa a Štěpán

Danil | 11. 6. 2015 12:22:01

Zdravím všechny, jelikož jsem si konečně vzpomněl na něco zajímavého, co bych tady mohl zadat, tak bych chtěl navázat v maratonu, zvěřejňuji řešení první úlohy a zadání té svojí, rovněž spíše rozjezdové.
Jelikož už je dokonce po termínu odevzdání 2. série iKSka, tak se teď můžou maratonu trochu víc věnovat i jeho řešitelé, takže počítám s tím, že má úloha moc dlouho nevydrží :)
Řešení úlohy č.1:
+ skrytý text

Sčítance na levé straně zřejmě také nabývají hodnot $-1$ a $1$ , je jich dohromady n. Bude rovna nule právě tehdy, je-li polovina z nich kladná a polovina záporná, z čehož lze vyvodit, že je n sudé. Nyní pro spor předpokládejme, že je n ve tvaru $4k+2$ pro nějaké celé k, tudíž je $2k+1$ ze sčítanců na levé straně rovno 1 a $2k+1$ rovno -1. To znamená, že je jejich součin $a_1a_2a_3a_4*a_2a_3a_4a_5*...*a_na_1a_2a_3$ roven -1, protože v něm je lichý počet -1. Lze však snadno nahlédnout, že se v daném součinu vyskytne každé číslo $a_1, a_2, ..., a_n$ čtyřikrát a je tedy roven součinu jejich čtvrtých mocnin. No a když je součin čtvrtých mocnin reálných čísel záporný, tak je něco špatně a máme požadovaný spor, proto musí být n dělitelné 4.

Zadání úlohy č.2:
+ skrytý text

Buď a, b, c kladná réalná čísla se součinem 1. Dokažte, že je hodnota součinu $(a-1+ac)(b-1+ab)(c-1+bc)$ nejvýše 1.

Štěpán Šimsa | org | 2. 6. 2015 01:22:30

Ahoj,
určitě je Ti líto, že už letos skončily všechny PraSečí série (a první dvě série na příští rok už máš dávno vyřešené) a rád by sis vyřešil nějakou matematickou úložku. Proto jsme se rozhodli obnovit matematický maraton!

Pravidla jsou jednoduchá: přečteš si aktuální úlohu, tu vyřešíš a rovnou zadáš novou. Máš tak možnost nejen řešit zajímavé úlohy, ale také se podělit o příklady, které Ti připadají zajímavé. Nudící se orgové se taky možná občas zapojí :).

Tak tedy na rozjezd první úloha:

Každé z čísel $a_1, \dots, a_n$ je $+1$ nebo $-1$ a platí $a_1a_2a_3a_4+a_2a_3a_4a_5+\cdots+a_na_1a_2a_3=0$ . Dokažte, že $n$ je dělitelné čtyřmi.

Martin Hora | org | 8. 5. 2015 09:32:35

Ahoj,
máme tady nápovědy k poslední jarní sérii.

úloha 1
a)+ skrytý text

Nejprve si rozmyslete, že musí existovat přímka, která obsahuje body právě dvou barev, nebo přímka, která obsahuje vrcholy právě tří barev. Oba tyto případy rozeberte zvlášť. + skrytý text

Na trojbarevné přímce uvažujte body A, B, C po dvou různých barev takové, že B leží na úsečce AC. Pak se podívejte na průsečík kružnice nad AC a kolmice na AC procházející B.

b)+ skrytý text

Rozdělte strany trojúhelníku na třetiny. Tím dostanete celkem 9 bodů (i s původními vrcholy trojúhelníku.). Nalezněte pravoúhlé trojúhelníky, který tyto vrcholy tvoří a následně zkuste sporem dokázat, že alespoň jeden z těchto pravoúhlých trojúhelníků má všechny vrcholy obarvené stejnou barvou.

úloha 2
a)+ skrytý text

Uvažujme společnou tečnu kružnic k a l procházející bodem Q. Tuto tečnu zobrazíme dvakrát ve stejnolehlosti. Poprvé v záporné stejnolehlosti, která převádí k na m, a podruhé v záporné stejnolehlosti, která převádí l na m. Co tím dostaneme?

b)+ skrytý text

Předpokládejme, že jsou body A, B, C, D na kružnici v tomto pořadí. Jiné případy se pak vyřeší obdobně. Označme H průsečík BC a AD a O střed AB. Dále úhlete jako diví a využívejte Thaletovy kružnice. Postupně zkuste dokázat, že DOCE je tětivový, E je střed kružnice opsané DCH, DHCF je tětivový. Poté by už měla být hračka úlohu dorazit.

úloha 3
a)+ skrytý text

Ukažte, že Tondovo číslo je kongruentní součtu čísel 11111 + 11112 + ... + 99999 modulo 11111.+ skrytý text

Tondovo čislo si napište jako sumu jednotlivých pěticiferných čísel krát vhodná mocnina desítky a využijte toho, že 100000 je kongruentní 1 mod 11111.

b)+ skrytý text

Je-li n liché, pak n^8+1 je sudé. Jaké pak bude nejmenší prvočíslo, které toto číslo dělí?
Je-li n sudé, tak n^8+1 je liché. V tomto případě dokažte, že hledané prvočíslo má tvar 8k+1 pro nějaké přirozené k.+ skrytý text

Dokažte sporem s využitím Malé Fermatovy věty, že prvočíslo nemůže být tvaru 4k+3 ani tvaru 8k+5.

úloha 4
a)+ skrytý text

Využijte rozkladu a^3 + b^3 = (a+b)(a^2 -ab + b^2). Dále využívejte rovnosti sin^2 x + cos^2 x = 1 a 2sin(x)cos(x) = sin 2x. V určité fázi budete muset nejspíše rovnici umocnit nadruhou.

b)+ skrytý text

Rovnici vynásobte sin 1° a následně využijte vzorce pro součin sínů. 2 * sin x * sin y = cos(x-y) - cos(x+y).

úloha 5
a)+ skrytý text

Rozebereme zvlášť dva případy.
1) U stolu sedí zástupci pouze 2 politických stran.
2) U stolu sedí zástupci alespoň 3 politických stran, pak musí existovat dvojice sousedních židlí, na kterých sedí 4 politici, kteří jsou členy celkem aspoň 3 politických stran.

b)+ skrytý text

Pro n=1 vyhraje první strana. Ve všech ostatních situacích vyhraje druhá strana.
Je-li n sudé, tak je lehké najít vyhrávající strategii druhé strany. + skrytý text

Jen symetricky kopíruje první stranu.

Je-li n liché, tak nám přibude prostřední liché políčko. Zkuste strategii z předchozího případu upravit tak, aby uměla správně reagovat i na soupeřův tah na prostřední pole.

úloha 6
a)+ skrytý text

Rozeberte případ, kdy jedno z čísel a, b, c je nulové. + skrytý text

Dokažte, že pak má rovnice kořeny pomocí Vietových vztahů.

Dále se podívejte co se stane, pokud jedno z čísel a, b, c má opačné znaménko než zbylé dvě. + skrytý text

Dokažte, že pak je diskriminant kladný.

b)+ skrytý text

Napište si všechny 3 rovnice Vietových vztahů platící pro tento polynom a vhodně je sečtěte. Vzniklou rovnici upravte a diskutujte, co by se stalo, kdyby žádný z kořenů neležel ve stanoveném intervalu.

úloha 7
a)+ skrytý text

Nalezněte hvězdy, jejichž stav může Zeus změnit a současně ponechat stav ostatních hvězd. Zbylé hvězdy pak splňují, že na každé linii jich leží sudý počet. Co to znamená?

b)+ skrytý text

Mřížové body můžeme rozdělit do dvou skupin. Na ty, jejichž součet souřadnic je sudý, a na ty, jejichž součet souřadnic je lichý. Ukažte, že lichý bod se rotací přesune opět na lichý bod a sudý opět na sudý.
Máme-li sudý a lichý bod, pak je tedy nemůžeme prohodit. Co dělat pokud máme dva sudé body? A co když máme dva liché?

Martin Hora | org | 18. 4. 2015 15:03:40

Ahoj,
nápovědy k třetí jarní sérii a ke třetímu dílu seriálu jsou tady.

Jarní série:

úloha 1+ skrytý text

Nejdříve zkuste nakreslit 2 souhvězdí splňující zadání a poté zkuste přidat i souhvězdí třetí.

úloha 2+ skrytý text

Ano, mohlo se mu to podařit. Každá Davidova hvězda musí sousedit hranou s dalšími šesti hvězdami.

úloha 3+ skrytý text

Co když bude většina hvězd na jedné přímce?+ skrytý text

Na jedné přímce bude ležet 98 hvězd.

úloha 4+ skrytý text

Uvažujme tři přímky procházející Zemí takové, že každé dvě svírají spolu úhel 60°. Tyto přímky rozdělí oblohu na šest částí. Dokažte, že všechny hvězdy v každé z těchto částí mohou být poryty jednou kružnicí ze zadání.

úloha 5+ skrytý text

Libovolně zvolíme astronoma A. Pokud každý další astronom hlasoval alespoň pro jednu stejnou hvězdu jako A, tak je jednoduché zadání splnit. Předpokládejme tedy, že existuje astronom B, který nehlasoval pro žádnou z hvězd, pro kterou hlasoval A.
Může existovat astronom C, který nehlasoval pro žádnou hvězdu, pro kterou hlasoval A, a ani pro žádnou hvězdu. pro kterou hlasoval B?
Zvolíme-li 20 hvězd, ty, pro které hlasoval A a B, tak budou všichni astronomové spokojeni. Nyní zbývá dokázat, že z těchto 20 hvězd můžeme 10 vypustit.+ skrytý text

Můžeme vypustit jednu z následujících 4 množin: první pětice A + první pětice B, první pětice A + druhá pětice B, druhá pětice B + první pětice A, druhá pětice A + druhá pětice B.
Zkuste si toto tvrzení dokázat sporem.

úloha 6+ skrytý text

Nejdříve si rozmyslete, že žádné tři hvězdy nemohou ležet na přímce.
Dále dokážeme, že více než 4 hvězdy nemohou tvořit pravidelnou galaxii. Pro spor předpokládáme, že máme galaxii s alespoň 5 hvězdami. Vybereme si 4 hvězdy, které tvoří rovnoběžník s největším obsahem.
Kde je pátý bod (netvořící rovnoběžník)? Může být venku z rovnoběžníku? Může být uvnitř?

úloha 7+ skrytý text

Nejvíce může mít 12 hvězd. Zkuste najít rozestavení s 12 hvězdami, které splňuje zadání.+ skrytý text

V tomto rozestavení budou 3 různé hodnoty svítivosti hvězd.

Dál dokážeme, že 13 hvězd je již příliš mnoho. Rozmyslete si, že pokud máme čtveřici hvězd, které mají všechny stejnou svítivost nebo mají všechny po dvou různou svítivost, tak jejich jediným možným rozestavením je obdélník. Dále si rozmyslete, že nemůžeme mít pětici hvězd s touto vlastností.
Máme-li 13 hvězd, kolik mohou mít různých svítivostí? Rozmyslete si, že také musíme mít 2 čtveřice hvězd dříve popsané vlastnosti takové, že sdílí 3 hvězdy. Máme pak prostor, kam umístit zbylé hvězdy těchto čtveřic?

úloha 8+ skrytý text

Hvězdy si rozdělíme do 4 skupin po 500. Dále ukážeme, že na jakýkoliv tah Jupitera může Mars zareagovat tak, aby neizoloval žádnou hvězdu.
Jak bude Mars hrát, zruší-li Jupiter most mezi hvězdami jedné skupiny? A jak bude hrát, zruší-li Jupiter most mezi 2 skupinami?

Seríál:
úloha 1+ skrytý text

Vyhovuje například graf s 5 vrcholy, který vypadá tak, že čtyři vrcholy tvoří čtverec a pátý je uvnitř tohoto čtverce a je spojený se všemi ostatními vrcholy.
Rozmyslete si, že tento graf skutečně splňuje zadání.

úloha 2+ skrytý text

Budeme předpokládat, že jeden směr úseček je rovnoběžný s osou x a druhý směr je rovnoběžný s osou y. Dále budeme předpokládat, že žádné dvě rovnoběžné úsečky neleží na stejné přímce. (Kdyžtak jednu úsečku trochu posuneme.)
Vodorovné úsečky očíslujeme zdola nahoru a svislé zleva doprava. Nyní si rozmyslete, že podmínka ze zadání za této situace musí nastat.

Dále dokážeme opačnou implikaci.
Vytvoříme si tabulku k x l. Políčko (i,j) v tabulce vybarvíme, pokud je vrchol i první partity spojen hranou s vrcholem j druhé partity. Pak v každém řádku a sloupci spojíme úsečkou nejkrajnější vybarvená políčka. Rozmyslete si, že se všechny úsečky protínají na vybavených políčkách.

úloha 3+ skrytý text

G obsahuje úplný podgraf na n vrcholech, potřebujeme tedy alespoň n barev. Dále dokážeme, že n barev stačí.
G je doplněk intervalového grafu. Kdy tedy mezi dvěma vrcholy G vede hrana?
Vrcholy si očíslujeme tak, aby odpovídaly seřazení intervalů zleva doprava. Následně začneme vrcholy grafu popořadě hladově obarvovat barvami 1 až n. Vždy použijeme barvu s nejnižším možným číslem. Co by znamenalo, že jsme při tomto algoritmu použili více než n barev?

<< < 1 2 ... 8 9 10 ... 35 36 > >>

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