Kombinatoryka i logika

LVI OM - I - Zadanie 8

Na okręgu jest umieszczonych $ n $ lampek; każda może być włączona albo wyłączona. Wykonujemy serię ruchów; w każdym ruchu wybieramy $ k $ kolejnych lampek i zmieniamy ich stan: wyłączone włączamy, a włączone wyłączamy (liczba $ k $ nie zmienia się w trakcie tego po­stępowania). Na początku wszystkie lampki są wyłączone. Dla ustalonej liczby naturalnej $ n $ wyznaczyć wszystkie liczby naturalne $ k \leq n $, dla których jest możliwe uzyskanie stanu z dokładnie jedną lampką włączoną.

LVII OM - III - Zadanie 4

Na trójce liczb wykonujemy następującą operację. Wybieramy dwie spośród tych liczb i zastępujemy je ich sumą oraz ich iloczynem, pozostała liczba nie ulega zmianie. Rozstrzygnąć, czy rozpoczynając od trójki (3,4,5) i wykonując tę operację możemy ponownie uzyskać trójkę liczb będących długościami boków trójkąta prostokątnego.

LVII OM - II - Zadanie 6

Dana jest liczba pierwsza $ p $ oraz liczba całkowita $ n $, przy czym $ p \geq n \geq 3 $. Zbiór $ A $ składa się z $ n $-wyrazowych ciągów o wyrazach ze zbioru $ \{0,1,2,\dots ,p-1\} $ i ma następującą własność:

Dla dowolnych dwóch ciągów $ (x_1,x_2,\dots ,x_n) $ oraz $ (y_1,y_2,\dots ,y_n) $ ze zbioru $ A $ istnieją takie różne liczby
$ k, l, m $, że

\[<br /> x_k\neq y_k,\quad x_l\neq y_l,\quad x_m\neq y_m.<br /> \]

Wyznaczyć największą możliwą liczbę elementów zbioru $ A $.

LVII OM - I - Zadanie 4

Uczestnicy zawodów matematycznych rozwiązywali sześć zadań, każde oceniane jedną z ocen 6, 5, 2, 0. Okazało się, że
dla każdej pary uczestników $ A, B $ można wskazać takie dwa zadania, że w każdym z nich $ A $ uzyskał inną ocenę niż $ B $.

Wyznaczyć największą liczbę uczestników, dla której taka sytuacja jest możliwa.

I OM - B - Zadanie 16

Złożyć prostokąt z dziewięciu kwadratów o bokach 1, 4, 7, 8, 9, 10, 14, 15 i 18.

III MEMO - Zadanie 8

Każde z pól szachownicy o wymiarach $ 2009\times 2009 $ kolorujemy jednym z $ n $ kolorów (nie każdy kolor musi być wykorzystany). Mówimy, że kolor jest spójny, jeżeli dla dowolnych dwóch pól tego koloru można za pomocą ciągu ruchów przeprowadzić hetmana z jednego pola na drugie, stawiając go jedynie na polach w tym kolorze. W szczególności, jeśli pewnym kolorem pomalowano tylko jedno pole, to również jest on spójny. Wyznaczyć największą liczbę $ n $, dla której przy dowolnym kolorowaniu szachownicy co najmniej jeden z kolorów jest spójny.

Uwaga: Ruch hetmanem polega na przesunięciu go o dowolną liczbę pól w pionie, poziomie lub po skosie.

III MEMO - Zadanie 7

Na tablicy napisano liczby $ 0,1,2,\dots,n $ ($ n\geq2 $). W każdym kroku wymazujemy liczbę będącą średnią arytmetyczną dwóch różnych, jeszcze nie wymazanych liczb. Postępowanie to kontynuujemy tak długo, jak jest to możliwe. Niech $ g(n) $ będzie najmniejszą możliwą ilością liczb pozostawionych na tablicy. Wyznaczyć $ g(n) $ w zależności od $ n $.

III MEMO - Zadanie 2

Dane jest $ n\geq3 $ różnych kolorów. Niech $ f(n) $ będzie największą liczbą całkowitą o następującej własności: Możliwe jest takie pokolorowanie wszystkich boków i przekątnych wielokąta wypukłego o $ f(n) $ wierzchołkach, że

  1. wykorzystane są co najmniej dwa różne kolory,

  2. każde trzy wierzchołki wielokąta wyznaczają trójkąt o wszystkich bokach jednakowego koloru lub o wszystkich bokach różnego koloru.

Dowieść, że $ f(n)\leq(n-1)^2 $ oraz że równość zachodzi dla nieskończenie wielu wartości $ n $.

L MOM - Zadanie 6

Liczby $ a_1,a_2,\dots,a_n $ są parami różnymi dodatnimi liczbami całkowitymi, zaś $ M $ jest zbiorem $ n-1 $ dodatnich liczb całkowitych, przy czym $ M $ nie zawiera liczby $ s=a_1+a_2+\dots+a_n $. Konik polny skacze wzdłuż osi liczbowej w dodatnim jej kierunku. Zaczyna w punkcie 0 i wykonuje $ n $ skoków, których długościami są liczby $ a_1,a_2,\dots,a_n $, wzięte w pewnej kolejności. Udowodnić, że kolejność tę można wybrać w taki sposób, by po żadnym ze skoków konik polny nie wylądował w punkcie należącym do zbioru $ M $.

IX CPS - Zadanie 6

Dana jest liczba całkowita $ n\geq 16 $. Rozważmy zbiór

\[<br /> G=\left\{(x,y)\colon x,y\in\{1,2,\dots,n\}\right\},<br /> \]

składający się z $ n^2 $ punktów płaszczyzny. Niech $ A $ będzie dowolnym podzbiorem $ G $, zawierającym co najmniej $ 4n\sqrt{n} $ punktów. Udowodnić, że istnieje co najmniej $ n^2 $ czworokątów wypukłych, o wierzchołkach w zbiorze $ A $, takich że przekątne każdego z nich przechodzą przez jeden ustalony punkt płaszczyzny.

Subskrybuje zawartość