Kombinatoryka i logika

XLV OM - III - Zadanie 4

Dysponujemy trzema naczyniami bez podziałki: pustym $m$ -litrowym, pustym $n$ -litrowym oraz napełnionym wodą $(m+n)$ -litrowym. Liczby $m$ i $n$ są liczbami naturalnymi względnie pierwszymi. Udowodnić, że dla każdej liczby $k \in \{1,2, \ldots , m+n-1\}$ można za pomocą przelewania wody otrzymać w trzecim naczyniu dokładnie $k$ litrów wody.

XLV OM - II - Zadanie 4

Każdemu wierzchołkowi sześcianu przyporządkowano liczbę $1$ lub $-1$ , a każdej ścianie - iloczyn liczb przyporządkowanych wierzchołkom tej ściany. Wyznaczyć zbiór wartości, które może przyjąć suma $14$ liczb przyporządkowanych ścianom i wierzchołkom.

XLV OM - I - Zadanie 9

W konferencji bierze udział $2n$ osób. Każdy uczestnik konferencji ma wśród pozostałych uczestników co najmniej $n$ znajomych. Udowodnić, że wszystkich uczestników konferencji można zakwaterować w pokojach dwuosobowych tak, by każdy uczestnik mieszkał ze swoim znajomym.

XLVI OM - III - Zadanie 2

Przekątne pięciokąta wypukłego dzielą ten pięciokąt na pięciokąt i dziesięć trójkątów. Jaka jest maksymalna możliwa do uzyskania liczba trójkątów o równych polach?

XLVI OM - III - Zadanie 1

Wyznaczyć liczbę podzbiorów zbioru $\{1,2, \ldots , 2n\}$ , w których równanie $x + y = 2n+1$ nie ma rozwiązań.

XLVI OM - I - Zadanie 4

W pewnej szkole 64 uczniów bierze udział w pięciu olimpiadach przedmiotowych. W każdej z tych olimpiad uczestniczy co najmniej 19 uczniów tej szkoły; żaden z nich nie jest uczestnikiem więcej niż trzech olimpiad. Udowodnić, że jeżeli każde trzy olimpiady mają wspólnego uczestnika, to pewne dwie mają ich co najmniej pięciu.

XLVII OM - I - Zadanie 8

Ze środka kwadratu wybiega promień świetlny, który odbija się od boków kwadratu zgodnie z zasadą kąt padania jest równy kątowi odbicia. Po pewnym czasie promień wraca do środka kwadratu. Promień nigdy nie trafił w wierzchołek, ani nie przeszedł wcześniej przez środek. Dowieść, że liczba odbić od boków kwadratu jest nieparzysta.

XLVII OM - I - Zadanie 3

W pewnej grupie $kn$ osób każda osoba zna więcej niz $(k - 1)n$ innych ( $k$ , $n$ są liczbami naturalnymi). Wykazać, że można z tej grupy wybrać $k + 1$ osób, z których każde dwie sie znają.

Uwaga: Jeżeli osoba $A$ zna osobę $B$ , to osoba $B$ zna osobę $A$ .

XLVIII OM - I - Zadanie 12

Grupa złożona z $n$ osób stwierdziła, że codziennie przez pewien okres czasu trzy z nich mogą wspólnie zjeść obiad w restauracji, przy czym każde dwie z nich spotkają się na dokładnie jednym obiedzie. Dowieść, że liczba $n$ przy dzieleniu przez $6$ daje resztę $1$ lub $3$ .

XLVIII OM - I - Zadanie 8

Niech $a_n$ będzie liczbą wszystkich niepustych podzbiorów zbioru $\{1,2,\ldots,6n\}$ , których suma elementów daje przy dzieleniu przez 6 resztę 5 oraz niech $b_n$ będzie liczbą wszystkich niepustych podzbiorów zbioru $\{1,2,\ldots,7n\}$ , których iloczyn elementów daje przy dzieleniu przez 7 resztę 5. Obliczyć iloraz $a_n/b_n$ .

Olimpiady Matematyczne