Kombinatoryka i logika

XXXV OM - III - Zadanie 5

Sześciokąt foremny o boku 1 zawarty jest w sumie mnogościowej sześciu kół mających średnicę 1. Wykazać, że żaden z wierzchołków sześciokąta nie należy do dwóch z tych kół.

XXXV OM - III - Zadanie 2

Dla ustalonej liczby naturalnej $ n $ oraz każdego $ i = 1, 2, \ldots, n $, $ j = 1, 2, \ldots $ określamy

\[<br /> a_{j,i} = \begin{cases}<br /> 1 &\text{ dla }j=i \\<br /> 0 &\text{ dla }j\neq i<br /> \end{cases}<br /> \]

natomiast dla $ i = n + 1,\ldots, 2n $ $ j = 1,2,\ldots, n $

\[<br /> a_{j,i} = -\frac{1}{n}.<br /> \]

Udowodnić, że dla każdej permutacji $ p $ zbioru $ \{1, 2,\ldots, 2n\} $ spełniona jest nierówność

\[<br /> \sum_{j=1}^n \left| \sum_{k=1}^n a_{j, p(k)}\right| \geq \frac{n}{2}.<br /> \]

XXXV OM - III - Zadanie 1

Wyznaczyć liczbę takich funkcji $ f $ odwzorowujących zbiór $ n $-elementowy w ten sam zbiór, że $ f^{n-1} $ jest funkcją stałą, zaś $ f^{n-2} $ nie jest funkcją stałą, gdzie $ f^k = f\circ f \circ \ldots \circ f $, $ n $ jest ustaloną liczbą naturalną większą od 2.

XXXV OM - II - Zadanie 5

Obliczyć kres dolny pól sześciokątów wypukłych, których wszystkie wierzchołki mają współrzędne całkowite.

XXXV OM - II - Zadanie 3

Dane są ciągi $ (x_1, x_2, \ldots, x_n) $, $ (y_1, y_2, \ldots, y_n) $ o wyrazach dodatnich. Udowodnić, że istnieje taka permutacja $ p $ zbioru $ \{1, 2, \ldots, n\} $, że dla każdego rzeczywistego $ t $ ciąg

\[<br /> (x_{p(1)}+ty_{p(1)}, x_{p(2)}+ty_{p(2)}, \ldots, x_{p(n)}+ty_{p(n)})<br /> \]

ma następującą własność: istnieje taka liczba $ k $, że $ 1 \leq k \leq n $ oraz wszystkie niezerowe wyrazy ciągu o wskaźnikach mniejszych od $ k $ są jednakowego znaku i wszystkie niezerowe wyrazy ciągu o wskaźnikach nie mniejszych od $ k $ są jednakowego znaku.

XXXV OM - I - Zadanie 10

Na płaszczyźnie dane jest $ 3n $ punktów, wśród których nie ma trzech punktów współliniowych. Dowieść, że istnieje $ n $ rozłącznych trójkątów o wierzchołkach w danych punktach.

XXXVI OM - III - Zadanie 2

Dany jest kwadrat o boku długości 1 oraz liczby dodatnie $ a_1, b_1, a_2, b_2, \ldots, a_n, b_n $ nie większe od 1 takie, że $ a_1b_1 + a_2b_2 + \ldots + a_nb_n > 100 $. Udowodnić, że można pokryć ten kwadrat prostokątami $ P_i $ ($ i = 1,2,\ldots,n $) o bokach długości $ a_i, b_i $ równoległych do boków kwadratu.

XXXVI OM - II - Zadanie 5

Udowodnić, że dla liczby naturalnej $ n $ większej od 1 następujące warunki są równoważne:

a) $ n $ jest liczbą parzystą,

b) istnieje permutacja $ (a_0, a_1, a_2, \ldots, a_{n-1}) $ zbioru $ \{0,1,2,\ldots,n—1\} $ o tej własności, że ciąg reszt z dzielenia przez $ n $ liczb $ a_0, a_0 + a_1, a_0 + a_1 + a_2, \ldots, a_0 + a_1 + a_2 +\ldots a_{n-1} $ jest też permutacją tego zbioru.

XXXVI OM - I - Zadanie 7

Dana jest rodzina $ A $ dwuelementowych podzbiorów zbioru liczb naturalnych. Udowodnić, że istnieje taki podzbiór nieskończony $ M $ zbioru liczb naturalnych, że albo wszystkie dwuelementowe podzbiory zbioru $ M $ należą do $ A $, albo żaden dwuelementowy podzbiór $ M $ nie należy do $ A $.

XXXVII OM - III - Zadanie 5

W turnieju szachowym uczestniczy $ 2n $ ($ n > 1 $) zawodników, przy czym każdych dwóch spośród nich rozgrywa między sobą co najwyżej jedną partię. Dowieść, że taki przebieg rozgrywek, w którym żadna trójka uczestników nie rozgrywa trzech partii między sobą jest możliwy wtedy i tylko wtedy, gdy liczba wszystkich partii rozegranych w turnieju nie przekracza $ n^2 $.

Subskrybuje zawartość