Kombinatoryka i logika

LI OM - I - Zadanie 11

Dana jest liczba całkowita dodatnia $n$ oraz zbiór $M$ , złożony z $n^2 + 1$ różnych liczb całkowitych dodatnich i mający następującą własność: wśród $n+1$ liczb dowolnie wybranych ze zbioru $M$ znajduje się para liczb, z których jedna dzieli się przez drugą. Udowodnić, że w zbiorze $M$ istnieją różne liczby $a_1,a_2,\ldots,a_{n+1}$ spełniające warunek: dla $i = 1,2,\ldots,n$ liczba $a_i$ dzieli się przez $a_{i+1}$ .

LI OM - I - Zadanie 4

Każdy punkt okręgu jest pomalowany jednym z trzech kolorów. Dowieść, że pewne trzy punkty jednego koloru są wierzchołkami trójkąta równoramiennego.

LII OM - III - Zadanie 6

Dane są liczby całkowite dodatnie $n_1 <n_2 < \ldots <n_{2000} < 10^{100}$ . Dowieść, że ze zbioru $\{n_1,n_2,\ldots,n_{2000}\}$ można wybrać niepuste rozłączne podzbiory $A$ i $B$ mające tyle samo elementów, taką samą sumę elementów i taką samą sumę kwadratów elementów.

LII OM - II - Zadanie 6

Dla danej liczby całkowitej dodatniej $n$ rozstrzygnąć, czy podzbiorów $n$ -elementowych zbioru $\{1,2,3,\ldots,2n-1,2n\}$ mających sumę elementów parzystą jest tyle samo, co podzbiorów $n$ -elementowych mających nieparzystą sumę elementów. Jeśli nie, to rozstrzygnąć, których jest więcej i o ile.

LII OM - I - Zadanie 11

Układ liczb całkowitych dodatnich $c_1,c_2,\ldots,c_n$ nazwiemy dopuszczalnym, gdy za pomocą wagi szalkowej i dwóch kompletów odważników o ciężarach $c_1,c_2,\ldots,c_n$ można zważyć dowolny przedmiot o ciężarze będącym liczbą naturalną nie przekraczającą $2(c_1 + c_2 +\ldots + c_n)$ . Dla każdej liczby $n$ wyznaczyć maksymalną sumę $n$ liczb tworzących układ dopuszczalny.

Uwaga: Odważniki można kłaść na obie szalki wagi.

LII OM - I - Zadanie 8

Rozstrzygnąć, dla jakich par liczb naturalnych $m$ i $n$ prostokąt o bokach długości $m$ i $n$ można pociąć na części przystające do figury na rysunku. Każdy z czterech kwadratów na rysunku ma bok długości $1$ .

LII OM - I - Zadanie 4

Rozstrzygnąć, czy w sześciennym pudełku o krawędzi 4 można umieścić 65 kul o średnicy 1.

LIII OM - III - Zadanie 3

Na tablicy są napisane trzy nieujemne liczby całkowite. Wybieramy z tej trójki dwie liczby $k$ , $m$ i zastępujemy je liczbami $k + m$ i $|k - m|$ , a trzecia liczba pozostaje bez zmiany. Z otrzymaną trójką postępujemy tak samo. Rozstrzygnąć, czy z każdej początkowej trójki liczb całkowitych nieujemnych, kontynuując to postępowanie, można otrzymać trójkę, w której co najmniej dwie liczby są zerami.

LIII OM - II - Zadanie 3

W $n$ -osobowym stowarzyszeniu działa sześć komisji. W skład każdej z nich wchodzi nie mniej niż $n/4$ osób. Dowieść, że istnieją dwie komisje oraz grupa licząca nie mniej niż $n/30$ osób, należących do obu tych komisji.

LIV OM - III - Zadanie 6

Niech n będzie dodatnią liczbą całkowitą parzystą. Udowodnić, że istnieje permutacja $(x_1,x_2, \ldots ,x_n)$ zbioru $\{1,2,\ldots,n\}$ , spełniająca dla każdego $i \in \{1,2,\ldots ,n\}$ warunek: