Kombinatoryka i logika

LIV OM - I - Zadanie 10

Mamy talię 52 kart. Tasowaniem będziemy nazywać wykonanie następujących czynności: dowolny podział talii na część górną i dolną, a następnie dowolne zmieszanie kart z zachowaniem porządku w obrębie każdej części. Mówiąc formalnie, tasowaniem jest dowolne przemieszanie kart, w którym $ i $-ta karta od wierzchu przechodzi na pozycję $ p_i $, przy czym istnieje takie $ m\in \{ 1, 2, 3, \ldots, 51\} $, że $ p_i < p_{i+1} $ dla $ i<m $ oraz dla $ i > m $.

Rozstrzygnąć, czy rozpoczynając od ustalonego początkowego uporządkowania kart, można uzyskać każde inne uporządkowanie wykonując pięć tasowań.

LIV OM - I - Zadanie 7

U cioci Reni spotkało się (łącznie z ciocią) $ n \geq 4 $ osób. Każdy z obecnych podarował co najmniej jednej z pozostałych osób co najmniej jeden prezent. Okazało się, że każdy podarował trzykrotnie więcej prezentów niż sam otrzymał, z jednym wyjątkiem: ciocia Renia podarowała zaledwie $ \frac{1}{6} $ liczby prezentów, które dostała. Wyznaczyć, w zależności od $ n $, najmniejszą możliwą liczbę prezentów, które mogła otrzymać ciocia Renia.

LIV OM - I - Zadanie 4

Rozpatrujemy zbiór wszystkich $ k $-wyrazowych ciągów o wyrazach ze zbioru $ \{1, 2, 3,\ldots , m\} $. Z każdego takiego ciągu wybieramy wyraz najmniejszy i sumujemy wybrane wyrazy. Udowodnić, że otrzymana suma jest równa

\[<br /> 1^k + 2^k + 3^k + \ldots + m^k.<br /> \]

LV OM - III - Zadanie 5

Wyznaczyć największą liczbę prostych w przestrzeni, przechodzących przez ustalony punkt i takich, że każde dwie przecinają się pod jednakowym kątem.

LV OM - III - Zadanie 3

W pewnym turnieju wzięło udział $ n $ zawodników $ (n \geq 3) $. Każdy grał z każdym dokładnie jeden raz, nie było remisów. Trójelementowy zbiór zawodników nazwiemy trójką remisową, jeśli można tak ponumerować tych trzech zawodników, że pierwszy wygrał z drugim, drugi z trzecim, a trzeci z pierwszym. Wyznaczyć największą liczbę trójek remisowych, jaka mogła się pojawić w turnieju.

LV OM - II - Zadanie 6

Na przyjęciu spotkało się $ n $ osób $ (n \geq 5) $. Wiadomo, że wśród dowolnych trzech osób pewne dwie znają się. Dowieść, że spośród uczestników przyjęcia można wybrać nie mniej niż $ n/2 $ osób i posadzić przy okrągłym stole tak, aby każdy siedział między dwoma swoimi znajomymi.

LV OM - I - Zadanie 10

Dany jest wielokąt wypukły o parzystej liczbie boków. Każdy bok wielokąta ma długość 2 lub 3, przy czym liczba boków każdej z tych długości jest parzysta. Dowieść, że istnieją dwa wierzchołki wielokąta, które dzielą jego obwód na dwie części jednakowej długości.

LV OM - I - Zadanie 5

Dla liczb całkowitych dodatnich $ m $, $ n $ niech $ N(m,n) $ oznacza liczbę $ m $-wyrazowych ciągów niemalejących o wyrazach ze zbioru

\[<br /> \{1,2, 3,\ldots,n\}.<br /> \]

Dowieść, że $ N(m, n+1) =N(n, m+1) $.

LV OM - I - Zadanie 1

Dany jest wielokąt o bokach długości wymiernej, w którym wszystkie kąty wewnętrzne są równe $ 90^{\circ} $ lub $ 270^{\circ} $. Z ustalonego wierzchołka wypuszczamy promień świetlny do wnętrza wielokąta w kierunku dwusiecznej kąta wewnętrznego przy tym wierzchołku. Promień odbija się zgodnie z zasadą: kąt padania jest równy kątowi odbicia. Udowodnić, że promień trafi w jeden z wierzchołków wielokąta.

LVI OM - II - Zadanie 3

W przestrzeni danych jest $ n $ punktów ($ n\geq 2 $) z których żadne cztery nie leżą w jednej płaszczyźnie. Niektóre z tych punktów zostały połączone odcinkami. Niech $ K $ będzie liczbą poprowadzonych odcinków ($ K\geq 1 $), a $ T $ liczbą powstałych trójkątów. Udowodnić, że

\[<br /> 9T^{2}<2K^{3}.<br /> \]
Subskrybuje zawartość