Matematický korespondenční seminář

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)

Začněte v libovolném vrcholu. Dokud to lze, tak se z vrcholu, kde se právě nacházíte, posuňte do libovolného jeho souseda, který jste ještě nenavštívili. Vrcholy a hrany, které tímto způsobem projdete tvoří cestu. Nyní již jen zbývá určit minimální délku této cesty.

Každý vrchol Qn označíme n-ticí nul a jedniček. Dva vrcholy sousedí právě když se jejich označení liší právě v jedné pozici. Podgraf Qn je izomorfní s Qk právě tehdy když z n-číselného označení vrcholu zafixujeme n-k pozic a vybereme podgraf indukovaný vrcholy, jejichž označení se na zvolených n-k pozicích shoduje se zafixovaným. Nyní již jen zbývá spočítat, kolik takových zafixování vlastně existuje.

Tvrzení lze dokázat matematickou indukcí dle k.
I) Pro k = 1 tvrzení očividně platí.
II) Nyní uvažujme, že tvrzení platí pro k a dokážeme ho pro k+1. Z indukčního předpokladu plyne, že stromy T1 až Tk mají alespoň jeden společný bod - označme ho A, a zrovnatak, že stromy T2 až T(k+1) mají alespoň jeden společný bod - označme ho B. Dále označme C společný bod stromů T1 a T(k+1). Rozmyslete si, že pokud všechny 3 vrcholy A, B, C nejsou po dvou různé, tak jsme již vyhráli. Pokud jsou po dvou různé, tak využijeme toho, že T je strom, a tak existuje právě jedna cesta z A do B, z B do C i z C do A. Tyto 3 cesty musí mít alespoň 1 společný vrchol X. Nyní dokažte, že vrchol X leží ve všech podstromech T1 až T(k+1).