Matematický korespondenční seminář

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

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.

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?

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.

Ukažte, že Tondovo číslo je kongruentní součtu čísel 11111 + 11112 + ... + 99999 modulo 11111.+ 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

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.

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).

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.

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
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.

Rozeberte případ, kdy jedno z čísel a, b, c je nulové. + skrytý text
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

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.

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á?

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é?

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

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

Co když bude většina hvězd na jedné přímce?+ 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í.

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

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ř?

Nejvíce může mít 12 hvězd. Zkuste najít rozestavení s 12 hvězdami, které splňuje zadání.+ skrytý text
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?

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?

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í.

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.

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?

Zadání vyhovuje například polynom druhého stupně s absolutním členem rovným nule. Zkuste nějaký takový najít.

Je-li x kořenem P(x) i Q(x), pak musí být i kořenem P(x)-Q(x). Zkuste se tedy zaměřit na kořeny polynomu P(x)-Q(x).

Nejprve zvolme x = 0. Zjistíme, že P(0) = 0. Dále zkuste určit jakých funkčních hodnot polynom nabývá na přirozených číslech.+ skrytý text

Takový polynom neexistuje. Důkaz se provede sporem. Předpokládejme, že takový polynom existuje a má nějaký racionální kořen p/q, kde p a q jsou nesoudělné. Zkusme tento kořen dosadit do polynomu a podívat se na vzniklou rovnici modulo dvěma.

Ze zadaného polynomu P(x) vytkneme (x-2015). Dostaneme P(x) = (x-2015)Q(x), kde Q(x) je polynom stupně o jedna menší než P(x). Nahlédneme, že polynom Q(x) má opět celočíselné koeficienty.
Dále budeme postupovat sporem. Budeme předpokládat, že všechny koeficienty P(x) jsou větší než -2015. Co z toho plyne pro polynom Q(x)?

Uvažte polynomy třetího stupně P(t) a Q(t) takové, že P(t) má kořeny a, b, c a Q(t) má kořeny x, y, z. Jak tyto polynomy vypadají?
Rozmyslete si, jak vypadají grafy těchto polynomů uvážíte-li podmínky ze zadání. Do obou polynomů dosaďte maximum z čísel a, b, c. Z tohoto dosazení získáte nějakou zajímavou nerovnost.
Následně do obou polynomů dosaďte minimum z čísel a, b, c.

Klíčem k této úloze jsou Vietovy vztahy. Zkuste pomocí nich dokázat, že všechny vyhovující polynomy mají stupeň nejvýše 3. Pak již jen stačí pro všechny z těchto polynomů ověřit, zdli splňují zadání.+ skrytý text

Označme d stupeň polynomu P(x). Uvažme polynom Q(x) stupně d takový, že Q(k) = f(k) pro k = 1, 2, ... , d + 1. Nyní je potřeba ověřit, že tento polynom Q(x) vyhovuje zadání
Polynom Q(x) má racionální koeficienty. Existuje tedy nějaké celé číslo M, že MQ(x) má celočíselné koeficienty. Pro všechna celá čísla n pak platí, že n-k dělí M(f(n)-f(k)) - M(Q(n)-Q(k)). Platí tedy že f(n) = Q(n), anebo je M(f(n)-Q(n)) větší než nejmenší společný násobek čísel n-1, n-2, ..., n-d-1. Výraz M(f(n)-Q(n)) však můžeme shora odhadnout nějakým násobkem polynomu P(x). Z těchto faktů lze sérií úvah odvodit, že Q(n) = f(n) pro dostatečně vysoká n.
Dokázat platnost tvrzení pro ostatní n by poté již nemělo být tak těžké.

Nemusí. Stačí vytvořit vhodné rozložení preferencí voličů PraSestánu takové, že splňuje zadání a nadpoloviční většina voličů dává přednost Vepříkovi před Pašíkem.

Zde je potřeba zkonstruovat síť ministerstev, která vyhovuje zadání. Dobrým základem je začít pouze se 4 ministerstvy a následně konstrukci pro 4 ministerstva vhodně rozšířit.

Pokud m = 0, tak má politik (n-1)! možností jak vybrat pořadí měst v jakém je bude projíždět.
Uvažujme dvě města A a B (různé od hlavního města), které jsou spojena opravenou cestou. Politik musí během své kampaně navštívit obě dvě tato města. Pokud navštíví jako první z těchto dvou měst město A, tak z něj pak musí odjet přímo do města B po opravené silnici. Navštíví-li z nich dřívě město B, pak musí z něj po opravené silnici do města A. Z toho plyne, že města A a B musí na politikově turné následovat hned po sobě. Tyto 2 města tedy můžeme považovat za jedno, u kterého má politik 2 možnosti jak ho projet.
Zbývá ještě odlišit dva případy, pokud z hlavního města vede opravená silnice a pokud ne. Rozmyslete si v čem se tyto 2 případy liší a dopočtěte kolika způsoby může politik uskutečnit svou kampaň.

Tuto úlohu vyřešíme sporem. Předpokládejme, že taková trojice politiků neexistuje. Pak se zaměřme na toho politika (označme ho x a jeho stranu A), jehož y přátel náleží do jedné strany (tu označme B), přičemž platí že y je maximální takové. (Tedy neexistuje žádný jiný politik, jehož y+1 přátel by bylo z jedné strany). Politik x má určitě nějakého přítele w ve třetí straně C. Kolik přátel má w ve stranách B a A? Co z toho plyne?

Kdyby po propouštění zbylo více než 100 000 úředníků, tak by z Dirichletova principu museli existovat dva úředníci, kterří mají shodné poslední pětičíslí. Kódy těchto dvou úředníků by se tedy nelišily alespoň ve dvou cifrách.
Nyní zbývá dokázat, že stačí propustit jen 900 000 úředníků. To znamená, že existuje 100 000 úředníků, kde kód libovolných 2 se liší alespoň na dvou pozicích. + skrytý text

Předpokládejme, že ve městě je alespoň jedna hlavní ulice. (Druhý případ je nezajímavý.) Pak je ve městě jistě ulice, která vede ven z města. (Opak by znamenal, že existuje neobdélníková čtvrť, která obkružuje celý zbytek města.) My po této silnici do města vejdeme a pokračujeme po ní rovně, dokud nenarazíme na její konec. Konec této ulice musí být nutně křižovatka tvaru T. (Rozmyslete si proč.) Na této křižovatce se rozhlédneme vpravo a vlevo. Nejvýše na jedné straně uvidíme okraj města. My se dále vydáme na stranu, kde okraj města nevidíme. (Jsou-li dvě, tak je jedno na kterou.) Opět dojdeme až na konec této ulice a celý proces opakujeme.
Ulic i křižovatek je v městě jen konečně mnoho, takže časem během naší procházky musíme přijít na místo, kde už jsme jedou byli. Co z toho plyne?

Na tuto úlohu použijeme matematickou indukci. Pokud je na nádvoří poze jedna židle nebo tam není žádná židle, tak politiky určitě rozesadit umím. Předpokládejme, že umíme rozesadit politiky máme-li 0 až k židlí. Podívejme se nyní na situaci, máme-li k+1 židlí. Pak mohou nastat dvě situace.
1) Existuje řada/sloupec ve které je pouze jedna židle.
2) Neexistuje sloupec ani řada, ve které by byla právě 1 židle.
V obou těchto případech umíme odebrat nějakou neprázdnou množinu židlí. Z indukčního předpokladu umíme rozesadit politiky na zbylé židle. Následně opět vrátíme odebranou množinu židlí a ukážeme, že na ně vždy můžeme dosadit politiky, ta aby bylo zadání splněno.
Zkuste si rozmyslet jakou množinu židlí budeme odebírat v případě 1) a jakou v případě 2).

Uspořádejme hlasovací lístky do kruhu libovolným způsobem.
Nyní v kruhu každý hlas pro A nahraďme +1 a každý hlas pro B nahraďme -k. Začněme na nějakém místě v kruhu sčítat tato čísla po směru hodinových ručiček. Pokud všechny průběžné součty, které takto dostaneme jsou kladné, tak místo odkud jsme začali označme jako dobré. Jinak toto místo označme jako špatné.
Nyní začněme pozice v kruhu označovat jako špatné. Postupně budeme procházet všechny -k v kruhu. Každé -k označíme jako špatné a pro každé -k půjdeme proti směru hodinových ručiček a prvních k plus jedniček , na které narazíme a které nejsou ještě nijak označeny, označíme jako špatné. Rozmyslete si, že takto označíme všechny špatné pozici a všechny pozice, které zbydou jsou dobré.
Kolik v každém kruhu zbyde dobrých pozic?
Pro každou posloupnost sčítání hlasů existuje právě jeden kruh. (Pootočené kruhy jsou stejné). Je-li v jednom kruhu nějaká posloupnost sčítání hlasů obsažena vícekrát, (to znamená, že kruh je po nějakém pootočení totožný), pak jsou všechny posloupnosti, kterým odpovídá daný kruh, obsaženy stejněkrát.
Na základě těchto poznatků určete jaká je výsledná pravděpodobnost.

Dokážte, že hranová barevnost grafu je d. Důkaz má 2 části.
1) barevnost je alespoň d. Tato část je jednoduchá.
2) d barev nám stačí.+ skrytý text

Duální graf G* ze zadání je rovinný. Z věty o 4-obarvitelnosti rovinného grafu jsme tedy dostaneme jednu implikaci.
Označme barvy G* a, b, c, d a barvy hran G x, y, z. Hrany G, které oddělují stěny G(vrcholy G*) s barvami (a,b) a (c,d) obarvíme barvou x, oddělující (a,c) a (b,d) barvou y a oddělující (a,d) a (b,c) barvou z. Dokažte, že toto vybarvení odpovídá zadání.

Prozradím, že se výsledném výrazu vyskytuje nějaké Fibonacciho číslo. Zkuste vymyslet vhodný výraz pro malá n. Důkaz se pak provede matematickou indukcí.
Správný výsledek:+ skrytý text

dokažte
+ skrytý text

Každé odpočívání nějakého hráče trvá nebo kol.

Uvažte hráče ,, kteří spolu hráli v prvním kole, BÚNO pak odpočíval kol, zatímco odpočíval kol. Pro spor předpokládejte, že hráč někdy (poprvé) odpočíval jen kol. Pak označte hráče, se kterým hrál po této pauze. Spor naleznete už na hráčích , , .

Označte , extrémní polohy bodů , (když ten druhý je v nekonečnu). Doplňte na rovnoběžník .

je společným stejnoúhlým kamarádem bodu ve všech trojúhelnících .

Uměli byste úlohy vyřešit, kdyby místo 11 bylo to prvočíslo 2? To je ještě docela lehké. A jak to teď to zobecnit pro prvočíslo 3...

Řešte úlohu, kde místo počítání nulových bodů sčítáte (mod 11) všech hodnot polynomu. Jaká musí být v takovém případě podmínka na stupeň polynomu, aby součet nutně vyšel nula?

Označme 2014x = y. Pak se nás úloha ptá, kolik řešení má rovnice sin(y)=0 pro y z uzavřeného intervalu [0, 2014 pí].

Obor hodnot funkcí sinus a kosinus je uzavřený interval [-1, 1]. To je podmnožina intervalu (-pi/2, pi/2).+ skrytý text

Rovnici vydělte 2. Vzniklé reálné konstanty před goniometrickými funkcemi nahraďte vhodnými hodnotami funkcí sinus a kosinus tak, abyste dostali na levé straně rovnice vzorec pro sinus součtu.

Zkuste do rovnice dosadit x = pi/2 a y = 0. Dále dosaďte x = -pi/2, y = pi.

Pomocí sinové věty je možno vyjádřit siny dvou z úhlů pomocí sinu třetího úhlu a délek stran trojúhelníka. Hodnota sinu třetího úhlu se v poměrech navíc zkrátí. Vzniklý poměr můžeme rozložit na soustavu rovnic a pomocí ní zjistíme, že délky stran trojúhelníku jsou v poměru 3:4:5. Dopočtení potřebného kosinu v takovémto trojúhleníka je již jednoduché.

Rozmyslete si, že minima po k+1 zmáčknutích tlačítka na přístroji lze dosáhnout buď sinem minima dosažitelného po zmáčknutí k tlačítek, nebo cosinem maxima po zmáčknutí k tlačítek. Žádným jiným způsobem minima dosáhnout nelze. Obdobně maxima po k+1 operacích lze dosáhnout buď kosinem minima po k operacích nebo sinem maxima po k operacích.
Dále je potřeba rozebrat, za kterých podmínek nastává která možnost.

Z podmínek ze zadání víme, že všechny goniometrické funkce v nerovnici jsou větší než 0. Můžeme tedy nerovnici vydělit součinem všech sinů. Dále můžeme zlomek na levé straně rovnice rozšířít součinem kosinů všech 3 úhlů ze zadání. Nyní přichází čas na využití podmínky ze zadání a aplikování několika goniometrických identit.+ skrytý text
Pak již jen stačí vhodně použít AG nerovnost a jsme hotovi.

Klíčem k úloze je dokázat, že umíme dostat odmocninu z libovolného kladného racionlního čísla. Pokud umíme toto, tak umíme dostat i každé racionální číslo. (Racionální číslo na druhou je opět racionální a odmocninu z tohoto čísla umíme dostat.)
K tomu nám poslouží 2 základní operace. tan(arccos(x)) a cos(arctan(x)). Rozmyslete si, že první z těchto operací udělá z čísla sqrt(a/b) číslo sqrt((b-a)/a). Druhá pak z čísla sqrt(a/b) udělá číslo sqrt(b/(a+b)).
Dále zbývá dokázat, že každou odmocninu z racionálního čísla dokážeme převést na číslo 1 = cos(0).

(sqrt(x) znamená druhá odmocnina z x)