Kombinatoryka i logika

XXXVII OM - III - Zadanie 1

Kwadrat o boku długości 1 pokryto $m^2$ prostokątami. Dowieść, że obwód pewnego z tych prostokątów jest większy lub równy $4/m$ .

W turnieju szachowym uczestniczy 66 zawodników, każdy z każdym rozgrywa jedną partią, rozgrywki odbywają się w czterech miastach. Udowodnić, że pewna trójka zawodników rozgrywa wszystkie partie między sobą w tym samym mieście.

XXXVIII OM - III - Zadanie 6

Płaszczyznę pokryto siatką sześciokątów foremnych o boku 1. Za drogę na siatce uważamy taki ciąg boków sześciokątów siatki, że każde dwa kolejne mają wspólny koniec. Drogę na siatce nazwiemy najkrótszą, jeżeli jej końców nie można połączyć drogą krótszą. Znaleźć liczbę najkrótszych dróg na siatce o ustalonym początku i długości 60.

XXXVIII OM - III - Zadanie 1

W kwadracie o boku 1 znajduje się $n$ punktów ( $n > 2$ ). Dowieść, że można je ponumerować $P_1, P_2, ..., P_n$ tak, by \sum_{i=1}^n |P_{i-1}P_i|^2 \leq 4 (przyjmujemy $P_0=P_n$ ).

XXXVIII OM - II - Zadanie 3

Na szachownicy o wymiarach 1000 na 1000 i polach pokolorowanych w zwykły sposób na biało i czarno jest dany zbiór A złożony z 1000 pól. Każde dwa pola zbioru A można połączyć ciągiem pól zbioru A tak, by kolejne pola miały wspólny bok. Dowieść, że w zbiorze A jest co najmniej 250 pól białych.

XXXVIII OM - I - Zadanie 4

Dla danej liczby naturalnej $n$ rozpatrujemy rodzinę $W$ wszystkich takich zbiorów $A$ par liczb naturalnych nie większych od $n$ , że jeżeli $(a, b) \in A$ , to $(x, y) \in A$ dla $1 \leq x \leq a$ , $1 \leq y \leq b$ .

Wykazać, że rodzina $W$ składa się z $\binom{2n}{n}$ różnych zbiorów.

Czytaj dalej

XXXIX OM - II - Zadanie 5

Rozstrzygnąć, czy każdy prostokąt, który można pokryć 25 kołami o promieniu 2 można też pokryć 100 kołami o promieniu 1.

XL OM - III - Zadanie 3

Numerujemy krawędzie sześcianu liczbami od 1 do 12.
(a) Dowieść, że dla dowolnego ponumerowania istnieje co najmniej osiem trójek liczb całkowitych $(i,j,k)$ , gdzie $1\leq i< j < k\leq 12$ , takich, że krawędzie o numerach $i,j,k$ są kolejnymi bokami łamanej.
(b) Podać przykład ponumerowania, dla którego nie istnieje dziewięć trójek o własnościach wymienionych w (a).

XL OM - III - Zadanie 1

Do obrad przy okrągłym stole zasiadła parzysta liczba osób. Po przerwie obiadowej uczestnicy zajęli miejsca przy stole w sposób dowolny. Udowodnić, że istnieją dwie osoby przedzielone tą samą, co przed przerwą, liczbą osób.

XL OM - I - Zadanie 5

Dla danej liczby naturalnej $n$ wyznaczyć liczbę ciągów $(a_1, a_2, \ldots , a_n)$ , których wyrazy $a_i$ należą do zbioru $\{0,1,2,3,4\}$ oraz spełniają warunek $|a_i - a_{i+i}| = 1$ dla $i = 1,2,\ldots,n-1$ .

Olimpiady Matematyczne