Kombinatoryka i logika

XVIII OM - II - Zadanie 2

Na sali znajduje się 100 osób, z których każda zna co najmniej 66 spośród pozostałych 99 osób. Dowieść, iż jest możliwe, że w każdej czwórce tych osób są takie dwie, które się nie znają. Przyjmujemy, że jeśli osoba $A$ zna osobę $B$ , to również osoba $B$ zna osobę $A$ .

XVIII OM - I - Zadanie 7

Na płaszczyźnie leży $2n$ punktów. Dowieść, że istnieje prosta nie przechodząca przez żaden z tych punktów i dzieląca płaszczyznę na półpłaszczyzny, z których każda zawiera $n$ spośród danych punktów. Sformułować i udowodnić analogiczne twierdzenie dla przestrzeni.

XIX OM - III - Zadanie 4

Dana jest liczba naturalna $n>2$ . Podać taki zbiór $n$ liczb naturalnych $a_1, a_2, \ldots, a_n$ , żeby w zbiorze sum

$<br /> a_i + a_j \quad (i = 1,2, \ldots,n, \quad j= 1,2, \ldots,n, \; i\neq j)<br />$

było możliwie najmniej liczb różnych oraz taki zbiór $n$ liczb naturalnych $b_1, b_2, \ldots, b_n$ , żeby w zbiorze sum

$<br /> b_i + b_j \quad (i = 1,2, \ldots,n, \quad j= 1,2, \ldots,n, \; i\neq j)<br />$

było możliwie najwięcej liczb różnych.

XIX OM - II - Zadanie 3

Dowieść, że jeżeli przy okrągłym stole siedzi co najmniej 5 osób, to można je tak przesadzić, że każda osoba będzie miała obu sąsiadów innych niż poprzednio.

XIX OM - I - Zadanie 5

Dany jest zbiór $2n$ ( $n \geq 2$ ) różnych liczb. Jak podzielić ten zbiór na pary, żeby suma iloczynów liczb poszczególnych par była a) najmniejsza, b) największa?

XXI OM - III -Zadanie 5

Na ile sposobów zbiór złożony z dwunastu elementów można podzielić na sześć rozłączonych zbiorów dwuelementowych?

XXI OM - II -Zadanie 6

Jeśli $A$ jest podzbiorem zbioru $X$ , to przyjmujemy $A^1 = A$ , $A^{-1} = X - A$ . Podzbiory $A_1, A_2, \ldots, A_k$ nazywamy wzajemnie niezależnymi, jeśli iloczyn $A_1^{\varepsilon_1} \cap A_2^{\varepsilon_2} \ldots A_k^{\varepsilon_k}$ jest niepusty dla każdego układu liczb $\varepsilon_1, \varepsilon_2, \ldots, \varepsilon_k$ , takiego, że $|\varepsilon_2| = 1$ dla $i = 1, 2, \ldots, k$ .
Jaka jest maksymalna liczba wzajemnie niezależnych podzbiorów zbioru $2^n$ -elementowego?