Kółko 22 X 2004 - kilka zadanek z kombinatoryki

1. W pewnej grupie kn osób, gdzie k, n ∈ ℕ każda osoba zna wi_{}ecej niż (k − 1)n innych. Wykazać, że można z tej grupy wybrać k + 1 osób, z których każde dwie si_{}e znaj _{}a. Uwaga. Jeżeli osoba A zna osob_{}e B, to osoba B zna osob_{}e A.

2. Grupa złożona z n osób stwierdziła, że codziennie przez pewien okres czasu trzy z nich mog _{}a wspólnie zjeść obiad w restauracji, przy czym każde dwie z nich spotkaj _{}a si_{}e na dokładnie jednym obiedzie. Dowieść, że liczba n przy dzieleniu przez 6 daje reszt_{}e 1 lub 3.

3. Dany jest zbiór n gdzie n 2 punktów, z których żadne trzy nie leż _{}a na jednej prostej. Kolorujemy wszystkie odcinki o końcach w tym zbiorze tak, by każde dwa odcinki o wspólnym końcu miały różne kolory. Wyznaczyć najmniejsz _{}a liczb_{}e kolorów, dla której istnieje takie pokolorowanie.

4. Dana jest liczba n ∈ ℕ, n 2 oraz n-elementowy zbiór S. Wyznaczyć najmniejsz _{}a liczb_{}e naturaln _{}a k, dla której istniej _{}a podzbiory A_{1}, A_{2}, …, A_{k} zbioru S o nast_{}epuj _{}acej własności: dla dowolnych dwóch różnych elementów a, b ∈ S, istnieje taka liczba j ∈ {1, 2, …, k}, że zbiór A_{j} ∩ {a, b} jest jednoelementowy.

5. Noe ma umieścić na arce osiem gatunków zwierz _{}at w czterech zagrodach, przy czym zamierza wykorzystać wszystkie zagrody. Okazało si_{}e, że dla każdego gatunku istniej _{}a co najwyżej trzy inne gatunki, z którymi nie może on dzielić zagrody. Udowodnić, że można rozmieścić zwierz_{}eta w zagrodach w taki sposób, by każdy gatunek był w zagrodzie z odpowiednimi dla siebie innymi gatunkami.

6. Jury olimpiady składa si_{}e na pocz _{}atku z 30 członków. Każdy członek jury uważa niektórych swoich kolegów za kompetentnych, a wszystkich pozostałych za niekompetentnych. Opinie w tej sprawie nie ulegaj _{}a zmianie. Na pocz _{}atku zebrania odbywa si_{}e głosowanie lustracyjne. Po tym głosowaniu ci członkowie, których za niekompetentnych uznała wi_{}ecej niż głosuj _{}acych w ich sprawie, s _{}a usuwani z jury. Udowodnić, że po najwyżej 15 głosowaniach skład jury przestanie si_{}e zmieniać. Uwaga: nikt nie głosuje we własnej sprawie, natomiast głosuje w sprawie wszystkich pozostałych członków jury.

7. Rozważmy mecz ping-ponga mi_{}edzy dwiema drużynami, z których każda składa si_{}e z 1000 graczy. Każdy gracz grał przeciwko każdemu z graczy z przeciwnej drużyny dokładnie raz (w ping-pongu nie ma remisów). Udowodnić, że istnieje dziesi_{}eciu graczy z jednej drużyny, takich, że każdy z graczy drużyny przeciwnej przegrał z co najmniej jednym z tych graczy.

8. Na egzamin przygotowano 8 pytań. Każdy uczeń otrzymał 3 z nich. Żadnych dwóch uczniów nie otrzymało wi_{}ecej niż jedno pytanie wspólne. Rozstrzygn _{}ać jaka najwi_{}eksza możliwa liczba uczniów mogła wzi _{}ać udział w egzaminie.