Kombinatoryka i logika

XL OM - I - Zadanie 4

Dowieść, że nie można tak pociąć kwadratu wzdłuż skończonej liczby odcinków i łuków okręgów, by z otrzymanych części można było złożyć koło (części można odwracać).

W pewnym turnieju uczestniczyło $n$ zawodników. Każdy z nich rozegrał jedną partię z każdym innym zawodnikiem, nie było remisów. Dowieść, że albo można podzielić uczestników turnieju na takie dwie grupy $A$ i $B$ , że każdy zawodnik z grupy $A$ wygrał z każdym z grupy $B$ , albo można ustawić uczestników w ciąg $u_1, u_2, \ldots , u_n$ tak, że $u_1$ wygrał z $u_2$ , $u_2$ wygrał z $u_3$ , ..., $u_{n-1}$ wygrał z $u_n$ , $u_n$ wygrał z $u_1$ .

XLI OM - II - Zadanie 3

W turnieju szachowym każdy zawodnik rozegrał z każdym co najwyżej jedną partię, przy czym liczba partii rozegranych przez każdego z zawodników jest nie mniejsza od ustalonej liczby naturalnej $n$ . Udowodnić, że można podzielić zawodników na dwie grupy $A$ i $B$ w taki sposób, by liczba partii rozegranych przez każdego gracza grupy $A$ z graczami grupy $B$ była nie mniejsza niż $n/2$ i jednocześnie liczba partii rozegranych przez każdego gracza grupy $B$ z graczami grupy $A$ była nie mniejsza niż $n/2$ .

XLI OM - I - Zadanie 5

Dowieść, że krawędzi sześcianu nie da się ponumerować liczbami od 1 do 12 tak, by suma numerów krawędzi wychodzących z każdego wierzchołka była taka sama.

Czy można spełnić ten warunek numerując krawędzie dwunastoma różnymi liczbami ze zbioru $\{1,2,\ldots,13\}$ ?

XLI OM - I - Zadanie 4

Z szachownicy o wymiarach $8 \times 80$ polach pokolorowanych w zwykły sposób usunięto dwa poła różnych kolorów. Udowodnić, że pozostałe $62$ pola można pokryć 31 prostokątami o wymiarach $2\times 1$ .

XLII OM - III - Zadanie 2

Niech $X$ będzie zbiorem punktów płaszczyzny $(x.y)$ o obydwu współrzędnych całkowitych. Drogą długości $n$ nazywamy każdy taki ciąg $(P_0, P_1,\ldots, P_n)$ punktów zbioru $X$ , że $|P_{i-1}P_{i}|=1$ dla $i \in \{1,2,\ldots,n\}$ . Niech $F(n)$ będzie liczbą różnych dróg $(P_0,P_1,\ldots,P_n)$ o początku $P_0 = (0,0)$ i końcu $P_n$ położonym na prostej o równaniu $y = 0$ . Udowodnić, że

$<br /> F(n) = \binom{2n}{n}.<br />$

XLII OM - II - Zadanie 5

$P_1, P_2, \ldots, P_n$ są różnymi podzbiorami dwuelementowymi zbioru $\{1,2,\ldots,n\}$ . Zbiory $P_i$ , $P_j$ dla $i\neq j$ mają element wspólny wtedy i tylko wtedy, gdy zbiór $\{i,j\}$ jest jednym ze zbiorów $P_1, P_2, \ldots, P_n$ . Dowieść, że każda z liczb $1,2,\ldots,n$ jest elementem wspólnym dokładnie dwóch zbiorów spośród $P_1, P_2, \ldots, P_n$ .