Kółeczko z kombinatoryki - zadania  29 października 2009

1. Jaka jest liczba permutacji zbioru liczb od 1 do 100, w których liczby 2,3,5,8 pojawiają się w tej właśnie kolejności?

2. Jaka jest liczba permutacji zbioru liczb od 1 do 100, w których liczby 13 i 21 występują obok siebie?

3. Na ile sposobów można ustawić n chłopców i m dziewczynek tak, aby pierwsza stała dziewczynka?

4. Na ile sposobów możemy dojść z jednego z rogów szachownicy n×m do przeciwległego rogu?

5. Ile jest różnych ciągów z n zer i m jedynek?

6. Dane są liczby m, d, 0 ≤ m ≤ d. Ile jest różnych rozwiązań równania x_{1}+x_{2}+…+x_{m} = d, jeśli: a) x_{i} ∈ {1, 2}; b) x_{i} ∈ ℕ ∪ {0}; c) x_{i} ∈ ℕ?

7. Na ile sposobów można posadzić n osób przy okrągłym stole? Dwa sposoby są identyczne, jeśli każda osoba ma tych samych sąsiadów.

8. Na ile sposobów można wybrać k pól z szachownicy n × m tak, by każde dwa z nich leżały w różnych wierszach i w różnych kolumnach?

9. Udowodnij, że \binom{n}{k} = \binom{n}{n−k} oraz \binom{n}{k}+\binom{n}{k+1} = \binom{n+1}{k+1} oraz \binom{n−1}{k−1}\binom{n}{k+1}\binom{n+1}{k} = \binom{n−1}{k}\binom{n+1}{k+1}\binom{n}{k−1}.

10. Udowodnij, że ∑_{k=0}^{n} \binom{n}{k} = 2^{n}.

11. Udowodnij, że ∑_{k=0}^{n}(−1)^{k}\binom{n}{k} = 0.

12. Udowodnij, że ∑_{k=0}^{n} k\binom{n}{k} = n2^{n−1}.

13. Udowodnij, że ∑_{k=0}^{n} \binom{n}{k}^{2} = \binom{2n}{n}.

14. Udowodnij, że ∑_{k=0}^{n}(−1)^{k}\binom{n}{k}k^{2} = 0.

15. Udowodnij, że ∑_{k=m+1}^{n+1} \binom{k−1}{m} = \binom{n+1}{m+1}.

16. Udowodnij, że ∑_{k=0}^{n} \binom{n−k}{m}\binom{k}{m} = \binom{n+1}{2m+1}.

17. Udowodnij, że ∑_{j=0}^{k} \binom{n−j−1}{k−j} = \binom{n}{k}.

18. Udowodnij, że ∑_{k=0}^{n} \binom{2n−k}{n}2^{k} = 4^{n}.

19. Udowodnij, że ∑_{k=0}^{r} \binom{r−k}{m}\binom{s+k}{m} = \binom{r+s+1}{m+n+1} dla s ≤ n.

20. Udowodnij, że szachownicy 8 × 8 z wyciętymi dwoma przeciwległymi rogami nie da się pokryć klockami domino.

Kółeczko z kombinatoryki - zadania  29 października 2009

21. Udowodnij, że szachownicy 10 × 10 nie da się pokryć klockami 4 × 1.

22. Udowodnij, że poziomej szachownicy 11 × 10 nie można przykryć klockami poziomymi 2 × 1 i pionowymi 1 × 3.

23. Udowodnij, że skoczek nie może przejść po wszystkich polach planszy 4 × n dokładnie raz i wrócić na pole startowe.

24. Są 3 pudełka. W pierwszym jest n − 2, w drugim jest n, w trzecim jest n + 2 kulek. Ruch polega na wybraniu jednego z pudełek i przełożeniu do niego z każdego innego pudełka po jednej kulce. Czy możliwe jest, aby po wykonaniu pewnej liczby ruchów w pudełkach było po tyle samo kulek?

25. Niech S będzie zbiorem n osób. Każda z nich zna dokładnie k osób z tego zbioru, dla każdych dwóch znających się istnieje dokładnie l znanych przez obie, dla każdych dwóch nie znających się istnieje dokładnie m znanych przez obie. Udowodnij, że m(n− k) − k(k − l) + k − m = 0.

26. Na drodze w kształcie okręgu stoją stacje benzynowe. W sumie jest na nich dość paliwa na przejechanie całej trasy. Udowodnij, że kierowca może wybrać taką stację, że rozpoczynając z niej trasę (i mając wcześniej pusty bak) przejedzie całą trasę w kierunku zgodnym z ruchem wskazówek zegara.

27. Niech n > 5 oznacza liczbę całkowitą. Wykaż, że w zbiorze {n + 1, n + 2, …, n + 30} jest co najwyżej osiem liczb pierwszych.

28. Ile jest liczb czterocyfrowych niepodzielnych ani przez 3, ani przez 5, ani przez 7?

29. Ile jest liczb całkowitych mniejszych od miliona o sumie cyfr równej 27?

30. Spośród liczb 1, 2, …, 2n wybrano n + 1. Wykaż, że wśród nich są dwie takie, że ich iloraz jest potęgą dwójki.

31. W sali jest n ≥ 2 osób. Wykaż, że co najmniej dwie z nich mają tę samą liczbę znajomych wśród obecnych.

32. Spośród liczb 1, 2, …, 2n − 1 wybrano n + 1 liczb. Wykaż, że są wśród wybranych liczb takie trzy, że jedna z nich jest sumą dwóch pozostałych.

33. W kwadracie o boku 130 umieszczono w dowolny sposób 2009 małych kwadracików o boku 1. Wykaż, że w tym kwadracie można zmieścić koło o promieniu 1 rozłączne ze wszystkimi kwadracikami.

34. Wykaż, że wśród liczb Fibonacciego F_{n}, gdzie n < 10^{6}, istnieje podzielna przez 1000.

35. Na kwadratowym terenie o boku 1 km rośnie 4500 drzew o średnicy pnia 50 cm. Udowodnij, że można znaleźć na nim taki prostokąt 10 m × 20 m, na którym nie rośnie żadne drzewo.