Kombinatoryka i logika

XLVIII MOM - Zadanie 3

W zawodach matematycznych niektórzy uczestnicy przyjaźnią się. Przyjaźń jest zawsze wzajemna. Grupę uczestników nazwiemy kliką, jeśli każdych dwóch zawodników tej grupy przyjaźni się. (W szczególności, każda grupa złożona z mniej niż dwóch zawodników jest kliką.) Liczbę osób, jaką liczy klika nazwiemy jej rozmiarem.

Wiadomo, że w zawodach tych rozmiar największej kliki jest liczbą parzystą. Dowieść, że uczestników zawodów można rozdzielić do dwóch pokoi tak, aby rozmiar największej kliki w jednym pokoju był równy rozmiarowi największej kliki w drugim pokoju.

I MEMO - Zadanie 7

Czworościan $ T $ nazwiemy dobrym, jeżeli wszystkie długości jego krawędzi są różnymi dodatnimi liczbami całkowitymi, z których jedna jest równa 2, a jedna 3. Oznaczmy przez $ s(T) $ sumę długości krawędzi dobrego czworościanu $ T $.

  1. Znaleźć wszystkie takie dodatnie liczby całkowite $ n $, dla których istnieje dobry czworościan $ T $ spełniający warunek $ s(T)=n $.

  2. Ile istnieje nieprzystających dobrych czworościanów $ T $, dla których $ s(T)=2007 $ ?

Uwaga: Nie jest konieczne dowodzenie, że rozważane czworościany są niezdegenerowane, tzn. posiadają dodatnią objętość.

I MEMO - Zadanie 6

Niech $ P $ będzie dowolnym zbiorem pięciu różnych punktów płaszczyzny, z których żadne trzy nie leżą na jednej prostej. Oznaczmy przez $ a(P) $ liczbę trójkątów ostrokątnych, których wierzchołki należą do zbioru $ P $. Wyznaczyć największą możliwą wartość $ a(P) $.

I MEMO - Zadanie 2

Rozważamy zbiór $ n $ kul ponumerowanych liczbami $ 1, 2, 3, \ldots, n $. Danych jest $ k>1 $ takich zbiorów kul. Chcemy pokolorować wszystkie kule dwoma kolorami, białym i czarnym, tak aby

  1. kule oznaczone tym samym numerem były tego samego koloru;

  2. dowolny podzbiór $ k+1 $ kul z (niekoniecznie różnymi)
    numerami $ a_1 $, $ a_2 $, $ \ldots $, $ a_{k+1} $ spełniającymi
    warunek

    \[<br /> a_1+a_2+\ldots+a_k=a_{k+1}<br /> \]

    musiał zawierać co najmniej jedną kulę każdego koloru.

Dla każdego $ k $ znaleźć największe możliwe $ n $, dla którego istnieje pokolorowanie spełniające powyższe warunki.

XVIII ZMPB - Zadanie 10

Dana jest tablica $ 18\times 18 $, której każde pole może być białe albo czarne. Początkowo wszystkie pola są białe. Możemy wykonywać następującą operację: wybieramy kolumnę lub wiersz i zmieniamy kolory wszystkich pól w tej kolumnie lub wierszu. Czy wykonując wielokrotnie taką operację możemy otrzymać tablicę, w której będzie dokładnie 16 czarnych pól?

XVIII ZMPB - Zadanie 9

W pewnym stowarzyszeniu należy wybrać zarząd. Każdy członek wskazał 10 kandydatów do zarządu, ale będzie zadowolony, jeżeli przynajmniej jeden z nich znajdzie się w zarządzie. Dla dowolnych sześciu członków stowarzyszenia można utworzyć dwuosobowy zarząd, zadowalający wszystkich sześciu. Dowieść, że można wybrać 10-osobowy zarząd, zadowalający wszystkich członków stowarzyszenia.

XVIII ZMPB - Zadanie 8

Nazwijmy zbiór $ A $ liczb całkowitych nieizolowanym, jeżeli dla każdego $ a\in A $ przynajmniej jedna z liczb $ a-1 $, $ a+1 $ także należy do $ A $. Udowodnić, że liczba pięcioelementowych nieizolowanych podzbiorów zbioru $ \{1,2,\ldots,n\} $ wynosi $ (n-4)^2 $.

XVIII ZMPB - Zadanie 7

Potworek składa się z sześciu trójkątów równobocznych o boku $ 1 $, jak pokazuje rysunek.

zmpb18_r_img_0.jpg

Wyznaczyć wszystkie liczby całkowite $ n $, dla których trójkąt równoboczny o boku $ n $ można podzielić na potworki (obroty i odbicia potworków są dopuszczalne; potworki nie mogą na siebie zachodzić).

XVIII ZMPB - Zadanie 6

Fredek pisze liczby $ 1 $, $ 2 $, $ \ldots $, $ n $ w pewnej kolejności, po czym sporządza listę wszystkich takich par $ (i,j) $, że $ 1\le i<j\le n $ oraz $ i $-ta liczba jest większa od $ j $-tej liczby w jego permutacji. Następnie Fredek wielokrotnie wykonuje następującą operację, dopóki jest możliwa: wybiera parę $ (i,j) $ z bieżącej listy, zamienia miejscami liczbę $ i $-tą z liczbą $ j $-tą w bieżącej permutacji, i usuwa parę $ (i,j) $ z listy. Wykazać, że Fredek może wybierać pary w takiej kolejności, że po zakończeniu procesu liczby w permutacji będą uporządkowane rosnąco.

XVIII ZMPB - Zadanie 1

Dla dodatniej liczby całkowitej $ n $ rozważmy rozbicie zbioru $ \{1,2,\ldots,2n\} $ na $ n $ podzbiorów dwuelementowych $ P_1 $, $ P_2 $, $ \ldots $, $ P_n $. W każdym zbiorze $ P_i $ niech $ p_i $ będzie iloczynem obu elementów zbioru $ P_i $. Udowodnić, że

\[<br /> {1\over p_1}+{1\over p_2}+\ldots+{1\over p_n}<1.<br /> \]
Subskrybuje zawartość