Kombinatorika mix (Napredna grupa)

Sarajevo - Kombinatorika mix - napredna grupa

Klub matematike Druge gimnazije Sarajevo, Sarajevo, 5.11.2022.

Komba mix 1.

Dokaži kombinatornim argumentom:

$\begin{enumerate} \item $$\binom{n}{k} = \binom{n}{n-k}$$ \item $$\sum_{k=0}^n \binom{n}{k} = 2^n$$ \item $$\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}$$ \end{enumerate}$

Nika želi popločati pod svog vrta oblika $2n+1 \times 2n+1$ , s time da se zemlja nalazi u poljima koja su presjek redova i stupaca parnih rednih oznaka, a na ostalim mjestima se nalazi pod. Za koje vrijednosti $n$ Nika može popločati svoj vrt dominama?

Komba mix 3.

Lucija je na poklon dobila 17 prirodnih brojeva takvih da niti jedan nema prosti faktor veći od 7. Pokaži da može odabrati neka dva različita broja tako da im umnožak bude potpun kvadrat.

Komba mix 4.

Iza sedam brda i sedam mora, sedam planina i sedam dolina, sedam rijeka i sedam jezera, sedam sela i sedam šuma, negdje iza sedam Kaštela, sedam patuljaka čuva blago sakriveno iza sedam vrata, a svaka vrata čuva po sedam brava. Svaki patuljak ima neki broj ključeva, a svaki ključ otvara točno jednu bravu. Ako bilo koja tri patuljka mogu otvoriti svih sedam vrata i time doći do blaga, pokaži da patuljci zajedno imaju barem 245 ključeva.

Komba mix 5.

Pokaži da vrijedi: $\sum_{r=k}^n \binom{n}{r} \binom{r}{k} = \binom{n}{k} \cdot 2^{n-k}$

Komba mix 6.

7 učenika igraju šahovski turnir koji traje 7 dana, tako da se svaki dan odigraju po 3 meča između parova učenika, a netko je slobodan. Na kraju turnira svatko je igrao protiv svakog točno jednom. Pokaži da na kraju petog dana možemo pronaći 4 učenika koji su već svi igrali međusobno.

Komba mix 7.

Na turniru sudjeluje $2048$ tenisača i svaki je odigrao protiv svakog drugog barem jednom i meč je završio nečijom pobjedom. Pokaži da je moguće pronaći $12$ igrača tako da je prvi od njih pobjedio sve ostale, drugi sve osim prvog, treći sve osim prva dva...

Komba mix 8.

Matej ima zlatnu šipku mase 2022 gram. Odlučio je odsjesti u hotelu koji će mu naplaćivati jedan gram zlata po noćenju, što Matej mora platiti svakoga jutra. Na početku u hotelu nema zlata, no kako će Matej plaćati će hotel također dobiti neku količinu zlata koju će moći koristiti za izvraćanje. Zato Matej može na nekim šipki učiniti rezove, čime bi stvorio dvije manje šipke. Ako Matej želi u hotelu odsjesti svih 2022 dana, na koliko najmanje manjih šipki mora izrezati početnu šipku da bi mogao svakoga dana platiti točno jedan gram (uz mogućnost izvraćanja viška od hotela, ukoliko hotel posjeduje šipke kojima može izvratiti točnu količinu)?

Komba mix 9.

Matej ima zlatni lanac duljine 2022 karike (svake dvije susjedne karike su provučene jedna kroz drugu, osim onih krajnjih). Odlučio je odsjesti u hotelu koji će mu naplaćivati jednu zlatnu kariku po noćenju, što Matej mora platiti svakoga jutra. Na početku u hotelu nema zlata, no kako će Matej plaćati će hotel također dobiti neku količinu zlata koju će moći koristiti za izvraćanje. Zato Matej može na nekim karikama učiniti rezove, čime bi stvorio dva manja lanca i oslobodio tu kariku iz oba. Ako Matej želi u hotelu odsjesti svih 2022 dana, na koliko najmanje karika mora izrezati da bi mogao svakoga dana platiti točno jednu kariku (uz mogućnost izvraćanja viška od hotela ukoliko hotel posjeduje lance kojima može izvratiti točnu količinu)?

Komba mix 10.

Na stol je postavljeno 2022 karte pri čemu su sve okrenute na zlatnu stranu, a plava strana je na stolu. Matej i Emanuel igraju sljedeću igru: igrač koji je na potezu bira neku kartu koja trenutno pokazuje zlatnu stranu i okreće nju i 49 karata njoj s lijeva na drugu stranu (one koje su pokazivale zlatnu stranu sad pokazuju plavu, a one koje su pokazivale plavu stranu sad pokazuju zlatnu). Pobjednik je onaj koji odigra zadnji potez. Ako Matej ide prvi, tko će pobijediti?

Školjka