Matematické Fórum

↑ Akqj10:

Ahoj,

vzhledem k tomu, že jde o úplný graf, tak každých k vrcholů v něm tvoří kružnici délky k. První krok je tedy určit počet způsobů, kolika můžu zbylých k-1 vrcholů k onomu libovolnému pevně zvolenému vrcholu přidat tak, aby vždy vznikla jedinečná k-tice.

(dokonce nějakých konkrétních k vrcholů v Kn, kde k>3, bude tvořit těch kružnic více - rozmysli proč, a budeš vědět, jak tuto úlohu řešit.)

EDIT: Teď se koukám, chybka, napsal jsem n místo k. Takže omluva a oprava (vyznačeno červeně).

↑ Akqj10:

Té první části věřím, že bylo rozumět (a pokud ne, tak napiš, prosím, co je na tom nejasného).

Navíc prozradím, proč nějakých k vrcholů z kružnice bude tvořit víc než jednu kružnici pro k>3:

Řekněme, že vrcholy grafu jsou nějakým způsobem očíslovány, my máme třeba určit (BÚNO), kolik kružnic délky k=4 prochází vrcholem 1. Uvažme, že jsme k vrcholu 1 vybrali do oné k-tice vrcholy 2,3,4.
No a teď kolik je kružnic délky 4 na těchto vrcholech? Jsou to kružnice (1-2-3-4-1), (1-2-4-3-1), (1-4-2-3-1) a víc jich tam není. Když si ale nakreslíš obrázek, uvidíš, že to jsou tři různé kružnice a všechny jsou podgrafem úplného grafu na n>=4 vrcholech (taky uvidíš, že jich víc na těchto čtyřech vrcholech nevymyslíš).

Takže se úloha dá vlastně rozčlenit na dvě podúlohy:

1) Kolika způsoby vyberu (k-1) vrcholů k onomu zafixovanému vrcholu, vzhledem ke kterému úlohu řeším?
2) Když už nějakých těch k vrcholů (tedy k-1 vybraných plus ten jeden zafixovaný) mám, kolik na nich samotných bude kružnic délky k?

Pozn: Kroky 1) a 2) se dají v podstatě provést taky naráz, ale řekl bych, že takto je to jednodušší na představivost.