Kombinatoryka i logika

XLIX OM - I - Zadanie 11

W turnieju tenisowym uczestniczyło $ n $ graczy. Każdy rozegrał z każdym innym jeden mecz; nie było remisów. Udowodnić, że istnieje taki gracz $ A $, który każdego innego gracza $ B $ pokonał bezpośrednio lub pośrednio, tzn. gracz $ A $ wygrał z $ B $ lub gracz $ A $ pokonał pewnego zawodnika $ C $, który wygrał z tym graczem $ B $.

XLIX OM - I - Zadanie 7

Rozstrzygnąć, czy istnieje wielościan wypukły mający $ k $ krawędzi oraz płaszczyzna nie przechodząca przez żaden z jego wierzchołków i przecinająca $ r $ krawędzi, przy czym $ 3r > 2k $.

XLIX OM - I - Zadanie 7

Dane są liczby całkowite dodatnie $ m $ oraz $ n $. Niech $ A=\{1,2,3,\ldots,n\} $. Wyznaczyć liczbę funkcji $ f:A \to A $ przyjmujących dokładnie $ m $ wartości oraz spełniających warunek:

\[<br /> \textrm{jeżeli } k,l \in A,\ k \leq l, \textrm{ to } f(f(k)) = f(k) \leq f(l).<br /> \]

XLVIII OM - III - Zadanie 6

Na okręgu o promieniu $ 1 $ leży $ n $ różnych punktów ($ n \geq 2 $). Niech $ q $ będzie liczbą odcinków o końcach w tych punktach i długości większej niż $ \sqrt{2} $. Dowieść, że $ 3q \leq n^2 $.

XLVIII OM - II - Zadanie 3

Dany jest zbiór $ n $ punktów ($ n \geq 2 $), z których żadne trzy nie leżą 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ą liczbę kolorów, dla której istnieje takie pokolorowanie.

XLIX OM - III - Zadanie 6

Rozważamy na płaszczyźnie kwadraty jednostkowe, których wierzchołki mają obie współrzędne całkowite. Niech $ S $ będzie szachownicą, której polami są wszystkie kwadraty jednostkowe zawarte w kole określonym nierównością $ x^2+y^2 \leq 1998^2 $. Na wszystkich polach szachownicy piszemy liczbę $ +1 $. Wykonujemy ciąg operacji. Każda z nich polega na wybraniu dowolnego rzędu poziomego, pionowego lub ukośnego i zmianie znaków wszystkich liczb napisanych na polach wybranego rzędu. (Rząd ukośny tworzą wszystkie pola szachownicy $ S $, których środki leżą na pewnej prostej przecinającej osie układu współrzędnych pod kątem $ 45^\circ $.)

Rozstrzygnąć, czy w ten sposób można doprowadzić do sytuacji, w której na jednym polu będzie napisana liczba $ -1 $, a na pozostałych $ +1 $.

L OM - II - Zadanie 2

Sześcian $ S $ o krawędzi $ 2 $ jest zbudowany z ośmiu sześcianów jednostkowych. Klockiem nazwiemy bryłę otrzymaną przez usunięcie z sześcianu $ S $ jednego spośród ośmiu sześcianów jednostkowych. Sześcian $ T $ o krawędzi $ 2^n $ jest zbudowany z $ (2^n)^3 $ sześcianów jednostkowych. Udowodnić, że po usunięciu z sześcianu $ T $ dowolnego spośród $ (2^n)^3 $ sześcianów jednostkowych powstaje bryła, którą daje się szczelnie wypełnić klockami.

L OM - I - Zadanie 8

Dana jest liczba naturalna $ n \geq 2 $ oraz zbiór $ n $-elementowy $ S $. Wyznaczyć najmniejszą liczbę naturalną $ k $, dla której istnieją podzbiory $ A_1, A_2,\ldots, A_k $ zbioru $ S $ o następującej własności:

dla dowolnych dwóch różnych elementów $ a, b \in S $, istnieje taka liczba $ j \in \{1, 2,\ldots, k\} $, że zbiór $ A_j \cap \{a, b\} $ jest jednoelementowy.

LI OM - III - Zadanie 5

Dla danej liczby naturalnej $ n \geq 2 $ znaleźć najmniejszą liczbę $ k $ o następującej własności. Z dowolnego $ k $-elementowego zbioru pól szachownicy $ n \times n $, można wybrać taki niepusty podzbiór, że liczba pól tego podzbioru w każdym wierszu i w każdej kolumnie szachownicy jest parzysta.

LI OM - II - Zadanie 3

Na polach szachownicy $ n \times n $ rozmieszczono $ n^2 $ różnych liczb całkowitych, po jednej na każdym polu. W każdej kolumnie pole z największą liczbą pomalowano na czerwono. Zbiór $ n $ pól szachownicy nazwiemy dopuszczalnym, jeżeli żadne dwa z tych pól nie znajdują się w tym samym wierszu, ani w tej samej kolumnie. Spośród wszystkich zbiorów dopuszczalnych wybrano zbiór, dla którego suma liczb umieszczonych na jego polach jest największa.

Wykazać, że w tak wybranym zbiorze jest czerwone pole.

Subskrybuje zawartość