KÓŁECZKO O KOMBINOWANIU (6.02.2008)

ZADANIA

1. Wyznaczyć liczb_{}e podzbiorów zbioru {1, 2, …, 2n}, w których równanie x + y = 2n + 1 nie ma rozwi _{}azań.

2. Na każdym polu nieskończonej szachownicy napisano liczb_{}e całkowit _{}a, przy czym każda napisana liczba wyst_{}epuje na tej szachownicy tylko raz. Dowieść, że dla każdej liczby a ∈ ℝ istniej _{}a takie dwa s _{}asiednie pola szachownicy, że różnica liczb napisanych na tych polach jest wi_{}eksza niż a.

3. Niech k, n ∈ ℕ. Ile jest rozwi _{}azań nierówności x_{1}+x_{2}+…+x_{k} < n w liczbach całkowitych nieujemnych? A x_{1} + x_{2} + … + x_{k} n?

4. Dany jest 541-wyrazowy ci _{}a paami różnych liczb rzeczywistych. Dowieść, że z tego ci _{}agu można wybrać 20-wyrazowy podci _{}ag rosn _{}acy lub 27-wyrazowy podci _{}ag malej _{}acy.

5. Jaś chce pokryć kafelkami podłog_{}e swojej łazienki maj _{}acej kształt prostok _{}ata m × n. ma w tym celu do zużycia mn kafelków białych i mn czarnych, każdy w kształcie trójk _{}ata prostok _{}atnego równoramiennego o przyprostok _{}atnej długości 1. Chce z nich ułożyć całe pokrycie podłogi łazienki tak, by każdy kafelek s _{}asiadował bokami tylko z kafelkami innego koloru. Na ile sposobów może to zrobić?

6. Niech n, p, r b_{}ed _{}a liczbami całkowitymi dodatnimi takimi, że n p+r. Oblicz ∑ _{i=0}^{n} \binom{i}{p} \binom{n−i}{r}.

7. Ufoludek zaatakował dom (złożony z piwnicy, parteru, pierwszego pi_{}etra oraz dachu) i zaczyna poruszać si_{}e w nim losowo zaczynaj _{}ac od parteru, przy czy za każdym razem kiedy wyjdzie na dach nadaje sygnał za pomoc _{}a jednego ze swoich 2 nadajników, a gdy pojawi si_{}e w piwnicy przeszukuje j _{}a za pomoc _{}a jednego z dwóch rozpoznawaczy rzeczy nieufolskich (czynności te wykonuje nawet, jeśli kończy tam swoj _{}a tras_{}e). Ile jest możliwych tras ufoludka, jeśli n razy użył schodów (dwie trasy s _{}a identyczne jeśli maj _{}a t_{}e sam _{}a kolejnośc odwiedzanych pi_{}eter i uźywanych urz _{}adzeń)?