Matematické Fórum

1) Zvolme tu nejjednodušší triangulaci (všechny úhlopříčky z jednoho bodu), ta je tvořena n-2 trojúhlníky, každý má součet vnitřních úhlů 180°, součet úhlů v n-úhelníku je (n-2)*180°. Proto když zvolíme jinou triangulaci, musí mít n-2 trojúhelníků.

2)V i-tý den bude družstvo Aj bojovat s družstvem Bk, kde k=(i+j mod 7)+1. Dokaž, že tohle funguje.

u té dvojky není těžké napsat ten rozpis (řádky jsou dny, sloupce jsou A-týmy, tzn. pokud je v i-tém řádku a j-tém sloupci k, pak Bk hraje i-tý den s Aj):

1234567
2345671
3456712
4567123
5671234
6712345
7123456

Není to ten rozpis, co jsem psal výše, ale snadno nahlédneme, že podmínky splní.

U jedničky by šlo taky postupovat míň trikově, a to pomocí Eulerova vzorce. Ten nám říká, že
F-E+n=1
protože se jedná o triangulaci, tak 3F+n=2E (pokud pro každou plochu započteme tři hrany, počítáme každou krom obvodových dvakrát. Proto přičteme obvodové a máme dvojnásobek počtu hran). Máme dvě rovnice pro dvě neznámé, spočítáme F.

Trojúhelníků je n-2, s n-úhelníkem mají celkem společných n hran. Každý z nich s ním má společnou jednu hranu (těch je a) nebo dvě hrany (těch je b). Máme tedy a+b=n-2 (počet trojúhelníků), a+2b=n (počet společných hran). Rovnice odečteme a výsledek b=2 je pro nás znamením dobře udělané práce :o)

↑ Phoenix22:F počet ploch, E počet hran, n počet vrcholů. A  F vypočítáš z těch dvou rovnic, od druhé odečteš dvakrát první.

↑ Phoenix22:Chceme dokázat, že F=n-2 (zadání). Máme rovnici F-E+n=1 (Eulerova věta) a 3F+n=2E (z vlastnstí triangulace). Vhodným odečtením těch rovnic získáme přesně to, co chceme dokázat ... nevím, co víc k tomu říct.

Ta dvojka se dá načrtnout jako bipolární graf, kdy na jedné straně máš A1 - A7 a na druhé straně máš B1 - B7 a můžeš zkusit propojit podle téhle tabulky:
Tabulka se zápasy v jednotlivých dnech.  Ale nejsem si jistý musím se poptat tady zkušených matematiku.

↑ Phoenix22:
Podle zadání máš předložit rozpis jednotlivých zápasů,
v ten  který den. Podle mě to ta tvoje tabulka splňuje.
Jako doplnění bych použil graf 1).

Chtěl by se zeptat. Myslíte, že bude stačit následovné řešešní, které uvedu zde, zda tady to řešešní můžu odevzdat i z komentáři atd...?
Doplnili by jste tam něco, jestli jo tak mi pisněte, co anebo jak by jste to provedli vy. Díky

Řešení:
Divize A, divize B
Družstva z divize A: A_1,A_2,A_3,〖A_4 〖,A〗_5,A〗_6,A_7
Družstva z divize B: B_1,B_2,B_3,〖B_4 〖,B〗_5,B〗_6,B_7

Jednotlivé zápasy si můžeme znázornit pomocí grafů o 14 vrcholech každý stupeň jedna. Dále vidíme, že pro jeden den zápasu jsme zvolili jeden graf, jde hlavně o to, aby bylo přehledněji znázorněné, ve který den bude hrát jednotlivé družstvo.





Výsledná tabulka se seznamem zápasů vypadá následovně.




Pokud bychom vzali a na sebe naskládali všechny odehrané dny, dostaneme tady ten graf, viz níže, který má celkem 14 vrcholů, každý jeden vrchol obsahuje sedmý stupeň. Jak je vidět je dost nepřehledné. Představme si, že by bylo ještě více družstev – více vrcholu a více odehraných zápasu. V jednom grafu, jak jsem uvedl níže, by to nebylo ale už vůbec čitelné. 

↑ cinique:S tou Eulerovou větou: asi nejjednodušší zpusob, jak rozpor vysvětlit, je ten, že já do F nepočítám tu nekonečnou oblast mimo n-úhelník.

Co se týče kombinatorického řešení, dalo by se postupovat indukcí. Pro trojúhelník i čtyřúhelník je oblastí n-2. Předpokládáme, že to funguje pro k-úhelník a ukážeme to pro k+1-úhelník. Takový k+1-úhelník je úhlopříčkou rozdělen na t-úhelník a s-úhelník, ty jsou dalšími úhlopříčkami dle indukčního předpokladu rozděleny na t-2 a s-2 oblastí. Teď musíme najít vztah mezi k, t a s, ale to již jistě nebude problém.

Další alternatiou je použít součet vnitřních úhlů, to je také řešení na pár řádků.

Ten dovětek o těch "právě dvou" oblastech jsem vyřešil bez grafových pojmů i před tím a pro ten mě žádné alternativní řešení nenapadá.

Na tomto je  pěkně vidět, že jsou kombinatorika a teorie grafů provázané, na jednom konkurenčním fóru mají třeba kategorii kombinatorika a cpou do ní i teorii grafů.

↑ Phoenix22: Taky se připojuju k Phoenixovi, jestli by to nešlo ukázat. Moc by mi to pomohlo. Díky moc.

http://bart.math.muni.cz/~brkos/files/r … ni146.pdf, úloha 6.2.

Chtěl jsem se ještě zeptat, našel jsem tuto větu - Celý mnohoúhelník je tedy těmito úhlopříčkami a úhlopříčkou (u) rozdělen na:
(r − 2) + (s − 2) = r + s − 4 = n − 1 = (n + 1) − 2 trojúhelníkových oblastí. Když uvážíme například 6-úhelník, tedy by jsme měli dostat to, že je tvořen 4.trojúhelníky, a dosadíme za (n + 1) − 2, dostaneme 5.trojúhelníkových oblastí. Nemělo by to být -> (n + 1) − 3 ? tím by jsme dostali správně, že 6-úhelník je tvořen 4.trojúhelníkami.