Matematický korespondenční seminář

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)