kombinatorika

Příklad 331

Na kružnici je 5 červených, 7 žlutých a 9 zelenýrch bodů. Kolik existuje trojúhelníků, které mají všechny vrcholy
(a) zelené?
(b) každý jiné barvy?

Řešení	Ukázat
(a) ${9\choose3}$ (b) $5\cdot7\cdot9$

Příklad 332

V pravidelném dvanáctiúhelníku jsou vrcholy označené $\mathsf A_1$ , $\mathsf A_2$ ,... $\mathsf A_{12}$ . Kolik existuje
(a) trojúhelníků s vrcholy v těchto bodech?
(b) trojúhelníků s vrcholy v těchto bodech, které nemají společné body s přímkou $\mathsf{A_2A_8}$ ?

Řešení	Ukázat
(a) ${12\choose3}$ (b) Daná přímka rozděluje body na dvě části po pěti. Z každé pětice musíme vybírat nezávisle: $2\cdot{5\choose3}$

Příklad 333

Určete počet všech trojúhelníků, které mají vrcholy ve vrcholech pravidelného šestnáctiúhelníku a které nejsou pravoúhlé.

Řešení	Ukázat
Pravoúhlé trojúhelníky budou ležet nad průměrem opsané kružnice. Ty musíme vyloučit. 1. bod můžeme vybrat 16 způsoby. 2. bod můžeme vybrat 14 způsoby (už ne 1. bod a také ne bod na průměru) 3. bod můžeme vybrat 12 způsoby (ne 1. a 2. bod a také ne body na průměrech) Ale nezáleží na pořadí vybíraných bodů. Protože 3 body můžeme přerovnat $3!$ způsoby, je celkový počet hledaných trojúhelníků $\dfrac{16\cdot14\cdot12}{3!}$

Řešení

Ukázat

Pravoúhlé trojúhelníky budou ležet nad průměrem opsané kružnice. Ty musíme vyloučit.
1. bod můžeme vybrat 16 způsoby.
2. bod můžeme vybrat 14 způsoby (už ne 1. bod a také ne bod na průměru)
3. bod můžeme vybrat 12 způsoby (ne 1. a 2. bod a také ne body na průměrech)
Ale nezáleží na pořadí vybíraných bodů. Protože 3 body můžeme přerovnat

$3!$ způsoby, je celkový počet hledaných trojúhelníků

$\dfrac{16\cdot14\cdot12}{3!}$

Příklad 334

Určete počet všech trojúhelníků, jejichž jeden vrchol leží ve středu pravidelného osmiúhelníku a zbývající vrcholy ve vrcholech tohoto osmiúhelníku.

Řešení	Ukázat
Potřebujeme vybrat 2 body z osmi. To lze ${8\choose2}$ způsoby. Musíme ale odečíst dvojice ležící na diagonále, ty jsou 4. Celkem tedy ${8\choose2}-4.$

Příklad 335

Jaký je počet všech rovnoramenných trojúhelníků, které mají všechny vrcholy ve vrcholech pravidelného sedmiúhelníka?

Řešení	Ukázat
Jak ukazuje obrázek, existují tři typy rovnoramenných trojúhelníků v sedmiúhelníku. Každý typ můžeme sedmkrát otočit. Celkem tedy existuje $3\cdot7=21$ rovnoramenných trojúhelníků.

Příklad 336

Kolik existuje trojúhelníků, které mají vrcholy totožné s vrcholy pravidelného dvanáctiúhelníku a přitom žádná strana trojúhelníku není totožná se stranou dvanáctiúhelníku? Řešte i obecně.

Řešení	Ukázat
Nejprve vyřešíme obecně. Musí být $n\geq3$ , jinak úloha nemá řešení. Všech trojúhelníků je ${n\choose3}$ . Trojúhelníků, které mají právě jednu stranu totožnou se stranou $n$ -úhelníka je $n(n-4)$ (počet stran krát počet vhodných třetích vrcholů). Trojúhelníků, které mají právě dvě strany totožné se stranou $n$ -úhelníka je $n$ . Celkem je tedy $n(n-4)+n=n(n-3)$ nevhodných trojúhelníků. Požadovaných trojúhelníků je pak ${n\choose3}-n(n-3).$ Speciálně pro dvanáctiúhelník je ${12\choose3}-12\cdot9=112.$

Řešení

Ukázat

Nejprve vyřešíme obecně. Musí být

$n\geq3$ , jinak úloha nemá řešení. Všech trojúhelníků je

${n\choose3}$ .
Trojúhelníků, které mají právě jednu stranu totožnou se stranou

$n$ -úhelníka je

$n(n-4)$ (počet stran krát počet vhodných třetích vrcholů).
Trojúhelníků, které mají právě dvě strany totožné se stranou

$n$ -úhelníka je

$n$ .
Celkem je tedy

$n(n-4)+n=n(n-3)$ nevhodných trojúhelníků. Požadovaných trojúhelníků je pak

${n\choose3}-n(n-3).$
Speciálně pro dvanáctiúhelník je

${12\choose3}-12\cdot9=112.$

Příklad 337

Kolik úhlopříček má pravidelný $n$ -úhelník?

Řešení	Ukázat
První bod můžeme vybrat $n$ způsoby, druhý $(n-3)$ způsoby. Na pořadí nezáleží. $\dfrac{n(n-3)}2$

Příklad 338

V rovině leží 6 různých bodů, z nichž žádné 3 neleží v jedné přímce. Kolik přímek tyto body určují?

Řešení	Ukázat
${6\choose2}$

Příklad 339

Deset bodů leží v rovině tak, že žádné 3 neleží na přímce. Kolik trojúhelníků určují?

Řešení	Ukázat
${10\choose3}$

Příklad 340

V rovině máme 25 bodů, z nichž žádné 3 nejsou kolineární. Kolik přímek a kolik trojúhelníků těchto 25 bodů určuje?

Řešení	Ukázat
přímek ${25\choose2},$ trojúhelníků ${25\choose3}$

Příklad 341

V kolika bodech se protíná 9 přímek, z nichž 4 jsou navzájem rovno běžné a z ostatních pěti žádné dvě nejsou rovnoběžné?

Řešení	Ukázat
5 různoběžných přímek se protíná v ${5\choose2}$ bodech. Každá ze čtyř rovnoběžných přímek se protíná s oněmi pěti různoběžnými v pěti bodech. Celkem ${5\choose2}+4\cdot5=30$ průsečíků.

Příklad 342

Kolik přímek lze proložit 7 body, jestliže
(a)) žádné tři body neleží v přímce?
(b) právě tři body leží v přímce?

Řešení	Ukázat
(a) ${7\choose2}$ (b) kdyby tři body neležely v přímce, tvořily by ${3\choose2}$ přímek. Tyto přímky musíme odečíst od celkového počtu. Přičíst musíme přímku tvořenou těmi třemi body: ${7\choose2}-{3\choose2}+1$

Příklad 343

Kolik přímek určuje 10 bodů v rovině, z nichž
(a) žádné tři neleží v přímce,
(b) právě šest leží na jedné přímce?

Řešení	Ukázat
(a) ${10\choose2}$ (b) ${10\choose2}-{6\choose2}+1$ (vyvětlení v příkladu 342.)

Příklad 344

Kolik kružnic určuje 10 bodů v rovině, z nichž
(a) žádné čtyři neleží na kružnici a žádné tři na přímce,
(b) právě šest leží na jedné přímce a zbývající čtyři neleží na kružnici a žádné tři z těchto čtyř na přímce?

Řešení	Ukázat
(a) ${10\choose3}$ (b) ${10\choose3}-{6\choose3}$

Příklad 345

Jsou dány dvě rovnoběžky $p$ a $q.$ Na přímce $p$ je 5 různých bodů a na přímce $q$ 4 různé body. Z těchto bodů žádné 4 neleží na kružnici. Kolik kružnic prochází právě třemi z daných bodů?

Řešení	Ukázat
1. postup: Všech trojic je ${9\choose3}.$ Od nich musíme odečíst trojice nas $p$ - ${5\choose3}$ a trojice na $q$ - ${4\choose3}.$ Celkem ${9\choose3}-{5\choose3}-{4\choose3}=70$ kružnic. 2. postup: Vybereme dva body na $p$ ${5\choose2}$ způsoby a k nim jeden bod na $q$ 4 způsoby nebo vybereme dva body na $q$ ${4\choose2}$ způsoby a k nim jeden bod na $p$ 5 způsoby. Celkem $4\cdot{5\choose2}+5\cdot{4\choose2}=70$ kružnic.

Řešení

Ukázat

1. postup: Všech trojic je

${9\choose3}.$ Od nich musíme odečíst trojice nas

$p$ -

${5\choose3}$ a trojice na

$q$ -

${4\choose3}.$
Celkem

${9\choose3}-{5\choose3}-{4\choose3}=70$ kružnic.
2. postup: Vybereme dva body na

$p$

${5\choose2}$ způsoby a k nim jeden bod na

$q$ 4 způsoby nebo vybereme dva body na

$q$

${4\choose2}$ způsoby a k nim jeden bod na

$p$ 5 způsoby.
Celkem

$4\cdot{5\choose2}+5\cdot{4\choose2}=70$ kružnic.

Příklad 346

Máme dvě rovnoběžné přímky. Na jedné leží 10 bodů, na druhé 11 bodů.
(a) Kolik určují trojúhelníků?
(b) Kolik určují čtyřúhelníků?

Řešení	Ukázat
(a) $10\cdot{11\choose2}+11\cdot{10\choose2}$ (b) ${11\choose2}\cdot{10\choose2}$

Příklad 347

Je dáno 12 bodů v rovině, z nichž 5 leží na jedné přímce. Žádné další tři na jedné přímce neleží. Kolik přímek je těmito body určeno?

Řešení	Ukázat
${12\choose2}-{5\choose2}+1$

Příklad 348

Je dán obdélník $\mathsf{ABCD}$ a na každé jeho straně je 6 bodů. Kolik různých trojúhelniků s vrcholy v daných bodech lze setrojit tak, aby každý vrchol ležel na jiné straně obdelníka?

Řešení	Ukázat
Vybereme tři strany, na nichž budou vrcholy. Na každé straně pak vybereme jeden bod: ${4\choose1}\cdot\left[{6\choose1}\right]^3=4\cdot6^3$

Příklad 349

Máme dány dvě mimoběžky. Na jedné je 5 bodů, na druhe 6 bodů. Kolik lze sestrojit čtyřstěnů s vrcholy v daných bodech?

Řešení	Ukázat
Na každé mimoběžce musíme vybrat 2 body: ${5\choose2}\cdot{6\choose2}$

Příklad 350

Je dána krychle $\mathsf{A B C D E F G H}.$ Na každé hraně zvolíme 8 vnitřních bodů.
(a) Určete počet všech trojúhelníků, jejichž vrcholy leží v daných bodech
(b) Určete počet všech trojúhelníků, jejichž vrcholy leží v daných bodech a navíc trojúhelníky leží na povrchu krychle.

Řešení	Ukázat
(a) Celkem je $12\cdot8=96$ bodů. Z nich vybíráme trojice a odečteme trojice ležící na jedné hraně: ${96\choose3}-12\cdot{8\choose3}$ (b) Spočítáme trojúhelníky v jedné stěně a vynásobíme počtem stěn: $6\left[{32\choose3}-4\cdot{8\choose3}\right]$

Příklad 351

Je dán konvexní čtyřúhelník $\mathsf{ABCD}.$ Určete počet všech přímek, které jsou určeny vrcholy tohoto čtyřúhelníka.

Řešení	Ukázat
${4\choose2}$

Příklad 352

V prostoru je dáno 10 různých bodů, z nichž žádné 3 neleží v jedné přímce a žádné 4 neleží v jedné rovině
(a) Kolik rovin lze jimi určit?
(b) Kolik rovin lze jimi určit, leží-li 4 body v jedné rovině?

Řešení	Ukázat
(a) ${10\choose3}$ (b) ${10\choose3}-{4\choose3}+1$

Příklad 353

Kolik existuje různých kvádrů jejichž strany jsou přirozená čísla z množiny $\{1\dots10\}?$ Dva kvádry lišící se otočením považujeme za shodné.

Řešení	Ukázat
Z deseti čísel vybíráme 3 na jejichž pořadí nezáleží, ale čísla se mohou opakovat. Jsou to tedy kombinace s opakováním. ${10+3-1\choose3}={12\choose3}$ za předpokladu, že i krychle počítáme jako kvádry. Pokud krychle nepočítáme, musíme ještě odečíst 10.

Příklad 354

Je dán trojúhelník $\mathsf{ABC}$ a na každé jeho straně je dáno $m$ vnitřních bodů. Určete počet
(a) všech trojúhelníků s vrcholy v daných $3m$ bodech.
(b) všech trojúhelníků s vrcholy v daných $3m$ bodech, jejichž žádná strana neleží na straně trojúhelníka $\mathsf{ABC}.$

Řešení	Ukázat
(a) ${3m\choose3}-3\cdot{m\choose3}=m^2(4m-3)$ (b) $m^3$

Příklad 355

V rovině leží 100 přímek, z nichž žádné dvě nejsou rovnoběžné a žádné tři neprocházejí stejným bodem. V kolika bodech se tyto přímky protínají? Na kolik oblastí dělí tyto přímky rovinu?

Řešení	Ukázat
Průsečíků je ${100\choose2}.$ Oblasti: $k$ -tá přímka protíná $k-1$ přímek. Každý průsečík znamená výstup z jedné oblasti a je tam ještě jedna oblast, ve které pokračuje "do nekonečna". To znamená, že $k$ -tá přímka prochází $k$ oblastmi a každou rozdělí na dvě části, což znamená, že přidává $k$ oblastí. To můžeme zapsat vztahem $O_k=O_{k-1}+k$ Protože na začátku byla jedna oblast a každá přímka přidá tolik oblastí, kolik je její pořadové číslo, dostáváme vztah $O_n=1+\sum_{i=1}^ni=1+\dfrac{n(n+1)}2=\dfrac{n^2+n+2}2$ Pro $n=100$ je $O_{100}=5051$

Řešení

Ukázat

Průsečíků je

${100\choose2}.$
Oblasti:

$k$ -tá přímka protíná

$k-1$ přímek. Každý průsečík znamená výstup z jedné oblasti a je tam ještě jedna oblast, ve které pokračuje "do nekonečna". To znamená, že

$k$ -tá přímka prochází

$k$ oblastmi a každou rozdělí na dvě části, což znamená, že přidává

$k$ oblastí.
To můžeme zapsat vztahem

$O_k=O_{k-1}+k$
Protože na začátku byla jedna oblast a každá přímka přidá tolik oblastí, kolik je její pořadové číslo, dostáváme vztah

$O_n=1+\sum_{i=1}^ni=1+\dfrac{n(n+1)}2=\dfrac{n^2+n+2}2$
Pro

$n=100$ je

$O_{100}=5051$

Příklad 356

Kolik existuje trojúhelníků s velikostmi stran z množiny $\{n+ 1, n+2,\dots, 2n\}?$ Kolik jich je rovnoramenných a kolik rovnostranných?

Řešení	Ukázat
Libovolná tři čísla z dané množiny vždy splňují trojúhelníkou nerovnost. (a) ${n+2\choose3}$ - kombinace s opakováním (b) libovolná dvojice různých čísel určuje dva rovnoramenné trojúhelníky - $2\cdot{n\choose2}$ (c) $n$

666 příkladů z kombinatoriky

Geometrie

Příklad 331

Příklad 332

Příklad 333

Příklad 334

Příklad 335

Příklad 336

Příklad 337

Příklad 338

Příklad 339

Příklad 340

Příklad 341

Příklad 342

Příklad 343

Příklad 344

Příklad 345

Příklad 346

Příklad 347

Příklad 348

Příklad 349

Příklad 350

Příklad 351

Příklad 352

Příklad 353

Příklad 354

Příklad 355

Příklad 356

Napsat komentář Zrušit odpověď na komentář