Kombinatoryka i logika

XXXII - I - Zadanie 2

Dana jest liczba całkowita nieujemna $n$ . Dowieść, że liczba takich układów liczb całkowitych $n_1 \geq n_2 \geq \ldots \geq n_k \geq 0$ , że

$<br /> 2^{n_1}+2^{n_2}+\ldots + 2^{n_k} = 2^n<br />$

jest nie mniejsza niż $2^n$ .

XXXIII OM - III - Zadanie 4

Na płaszczyźnie dany jest skończony zbiór punktów. Dowieść, że zbiór ten można pokryć otwartymi kwadratami rozłącznymi $Q_1, Q_2, \ldots, Q_n$ , tak, że

$<br /> 1\leq \frac{N_j}{S_j} \leq 4<br />$

( $j = 1, 2,\ldots, n$ ) gdzie $N_j$ jest liczbą punktów zbioru leżących w kwadracie $Q_j$ , zaś $S_j$ jest polem kwadratu $Q_j$ .

Wskazać taki sposób rozmieszczenia przy okrągłym stole $n$ dziewcząt i $n$ chłopców, aby liczba $d_n - c_n$ była największa, gdzie $d_n$ jest liczbą dziewcząt, siedzących między dwoma chłopcami, zaś $c_n$ - liczbą chłopców siedzących, między dwiema dziewczętami.

XXXIII OM - II - Zadanie 6

Dany jest takt skończony zbiór $B$ punktów przestrzeni, że każde dwie odległości między punktami tego zbioru są różne. Każdy punkt zbioru $B$ łączymy odcinkiem z najbliższym mu punktem zbioru $B$ . Otrzymamy w ten sposób zbiór odcinków, z których jeden (dowolnie wybrany) malujemy na czerwono, wszystkie pozostałe odcinki malujemy na zielono. Dowieść, że istnieją takie dwa punkty zbioru $B$ , których nie można połączyć łamaną złożoną z odcinków pomalowanych na zielono.

XXXIII OM - II - Zadanie 2

Płaszczyznę pokryto kołami w ten sposób, że środek każdego z tych kół nie należy do żadnego innego koła. Dowieść, że każdy punkt płaszczyzny należy do co najwyżej pięciu kół.

XXXIII OM - I - Zadanie 5

W pewnym zakładzie pracy każdy pracownik jest członkiem dokładnie jednego ze 100 związków zawodowych. Pracownicy mają wybrać dyrektora spośród dwóch kandydatów. Członkowie każdego ze związków umawiają się, czy wstrzymują się od głosu lub na którego z dwóch kandydatów będą głosować. Dowieść, że istnieje taki związek, że jeśli jego członkowie wstrzymają się od głosowania, a członkowie wszystkich innych związków będą głosować na któregoś z dwóch kandydatów, to kandydaci na dyrektora nie otrzymają równej liczby głosów.

XXXIV - III - Zadanie 3

Rozważamy grę jednoosobową na nieskończonej szachownicy opartą na następującej regule. Jeżeli na dwóch polach mających wspólny bok stoją plony i następne pole jest puste (trzy omawiane pola leżą na jednej linii poziomej lub pionowej), to możemy te piony usunąć i postawić jeden pion na trzecim z tych pól (które było puste).
Udowodnić, że jeżeli w pozycji początkowej piony wypełniają prostokąt o liczbie pól podzielnej przez 3, to nie możemy otrzymać pozycji, w której na szachownicy jest tylko jeden pion.

XXXIV OM - III - Zadanie 1

Na płaszczyźnie dany jest $n$ -kąt wypukły $P_1, \ldots, P_n$ oraz punkt $Q$ w jego wnętrzu nie należący do żadnej przekątnej. Dowieść, że jeśli $n$ jest liczbą parzystą, to liczba trójkątów $P_iP_jP_k$ ( $i,j,k= 1,2,\ldots,n$ ), które zawierają punkt $Q$ jest parzysta.

XXXIV OM - I - Zadanie 11

Wyznaczyć liczbę takich podzbiorów zbioru $\{1, 2, \ldots, n\}$ które nie zawierają dwóch kolejnych liczb.

XXXV OM - III - Zadanie 6

Miejscowości $P_1,\ldots, P_{1025}$ są obsługiwane przez linie lotnicze $A_1, \ldots, A_{10}$ , przy czym dla każdych miejscowości $P_k$ i $P_m$ ( $k \neq m$ ) istnieje taka linia, której samoloty latają bezpośrednio z $P_k$ do $P_m$ oraz bezpośrednio z $P_m$ do $P_k$ . Udowodnić, że któraś z tych linii może oferować podróż z nieparzystą liczbą lądowań rozpoczynającą i kończącą się w tej samej miejscowości.

Olimpiady Matematyczne