Koło matematyczne I LO w Białymstoku

Zadania przygotowała (oraz kółko poprowadziła) Ola Baranowska.

 
Zadania PDF.

 
Rozwiązania PDF.

Źródło rozwiązań w texu.

%        File: rozw.tex
%     Created: wto lut 23 03:00  2010 C
% Last Change: wto lut 23 03:00  2010 C
\documentclass[10pt]{article}
\usepackage{amssymb}
\usepackage{amsmath}
\textwidth 16cm
\textheight 24cm
\oddsidemargin 0cm
\topmargin 0pt
\headheight 0pt
\headsep 0pt
\usepackage[polish]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{import}
%\usepackage{MnSymbol}
% ----------------------------------------------------------------
\vfuzz4pt % Don't report over-full v-boxes if over-edge is small
\hfuzz4pt % Don't report over-full h-boxes if over-edge is small
% THEOREMS -------------------------------------------------------
\newtheorem{thm}{Twierdzenie}[section]
\newtheorem{cor}[thm]{Wniosek}
\newtheorem{lem}[thm]{Lemat}
\newtheorem{defn}[thm]{Definicja}
\newtheorem{tozs}[thm]{Tożsamość}
\newtheorem{hyp}[thm]{Hipoteza}
\newtheorem{useless}[thm]{}
 
\def\rozw{$ $\\\textbf{Rozwiązanie}: \\}
\def\deg{^{\circ}}
 
 
\subimport{../}{style}
%\include{style}
\def\source#1{\\Źródło: #1}
 
\begin{document}
\section{Co Ty wiesz o kombinowaniu?}
\author{Ola Baranowska}
 
\begin{enumerate}
    \item W przestrzeni danych jest $6$ punktów, z których żadne cztery nie leżą
        na jednej płaszczyźnie. Łącząc niektóre z tych punktów narysowano $10$
        odcinków.
        Wykaż, że w ten sposób uzyskano co najmniej jeden trójkąt.
        \rozw
        Wybieramy punkt $A$, z którego wychodzi najwięcej narysowanych odcinków.
        Pokażemy najpierw, że z punktu $A$ wychodzą co najmniej $4$ odcinki.\\
        Przypuśćmy
        więc, że jest inaczej. Z każdego punktu wychodzą zatem co najwyżej $3$
        odcinki. Ponieważ
        mamy $6$ punktów, więc łącznie mamy co najwyżej $6 \cdot 3 = 18$ końców tych
        odcinków,
        a więc mamy co najwyżej $9$ narysowanych odcinków. To jednak jest
        sprzeczne z założeniem.\\
        Z punktu $A$ wychodzą zatem co najmniej $4$ odcinki: $AB, AC, AD\hbox{
        i }AE$.
        Teraz zauważamy,
        że $6$ punktów można połączyć dokładnie $\displaystyle{\binom{6}{2} =
        15}$ odcinkami. Zatem wśród
        $6$ odcinków
        $$BC, BD, BE, CD, CE \hbox{ i }DE$$
        narysowano co najmniej jeden. Końce tego
        odcinka wraz z punktem A są wierzchołkami narysowanego trójkąta.
    \item W turnieju uczestniczy $2n$ graczy; każdych dwóch gra ze sobą co
        najwyżej raz. Udowodnij, że jeśli nie istnieje trojka graczy, którzy
        rozegrali ze sobą
        wszystkie trzy mecze, to łączna liczba rozegranych meczów nie
        przekracza $n^2$.
        \rozw
        Wybieramy gracza $A$, który rozegrał najwięcej gier. Niech $k$ będzie
        liczbą gier rozegranych przez gracza $A$ i niech $S$ będzie zbiorem graczy, z
        którymi gracz $A$ grał.\\
        Niech $T$ będzie zbiorem tych graczy, z którymi gracz $A$ nie grał.
        Oczywiście zbiór $T$ ma
        $2n-k-1$ elementów. Zauważmy, że gracze ze zbioru $S$ nie grali ze sobą.
        Gdyby bowiem
        gracze $B,C \in S$ grali ze sobą, to razem z graczem $A$ tworzyliby trojkę
        graczy, którzy rozegrali ze sobą wszystkie trzy mecze.\\
        Zatem w każdym meczu musiał uczestniczyć
        gracz $A$ lub któryś z graczy ze zbioru $T$. Każdy z tych graczy rozegrał
        jednak co najwyżej $k$ gier (gdyż $A$ wybraliśmy jako tego, kto
        rozegrał najwięcej). Zatem liczba wszystkich gier jest nie większa od 
        $k + (2n - k - 1)\cdot k$ i pozostaje nam udowodnić nierówność
        $$k + (2n - k - 1) \cdot k \leq n^2$$
        równoważną
        $$(2n - k) \cdot k \leq n^2$$
        $$\sqrt{(2n - k) \cdot k} \leq \frac{(2n - k) + k}{2}$$
        czyli nierówności pomiędzy średnimi.
    \item W każdej z trzech szkół uczy się $n$ uczniów. Każdy uczeń ma w
        pozostałych szkołach razem co najmniej $n + 1$ znajomych.
        Udowodnij, że z każdej szkoły można wybrać
        po jednym uczniu tak, że wszyscy wybrani uczniowie się znają.
        \rozw
        Wybieramy ucznia mającego największą liczbę znajomych w jednej z
        pozostałych
        szkół. Przypuśćmy, że tym uczniem jest uczeń $A$ ze szkoły $S_1$.
        Zakładamy, że
        w szkole $S_2$ zna on $k$ uczniów, przy czym liczba $k$ jest wspomnianą
        największą liczbą znajomych.\\
        Ponieważ uczeń A nie może znać $n + 1$ uczniów w szkole $S_2$ (ma ona
        $n$ uczniów), więc zna co
        najmniej jednego ucznia w szkole $S_3$; niech tym uczniem będzie $B$. Uczeń
        $B$ zna co najwyżej $k$ osób w szkole $S_1$, a więc zna co najmniej 
        $n + 1 - k$ uczniów w szkole $S_2$.
        Gdyby znajomi uczniów $A$ i $B$ w szkole $S_2$ tworzyli dwa zbiory rozłączne,
        to szkoła $S_2$ miałaby co najmniej $k+(n+1-k) = n+1$ uczniów, co jest sprzeczne z
        założeniem.\\
        Zatem w szkole $S_2$ istnieje uczeń znający zarówno $A$ jak i $B$; wraz z
        uczniami $A$ i $B$ tworzy on szukaną trojkę uczniów.
    \item W konferencji bierze udział $2n$ osób. Każdy uczestnik konferencji ma
        wśród pozostałych uczestników co najmniej $n$ znajomych. Udowodnij, że
        wszystkich
        uczestników konferencji można zakwaterować w pokojach dwuosobowych
        tak, by
        każdy uczestnik mieszkał ze swoim znajomym.
        \source{XLV OM}
        \rozw
        Wybieramy największą liczbę rozłącznych par znajomych:
        $$\{a_1, b_1\}, \{a_2, b_2\}, \dots, \{a_m, b_m\}$$
        Jeśli $m = n$, to te pary kwaterujemy w oddzielnych pokojach. Niech więc
        $m < n$.\\
        Z maksymalności $m$ wynika, że żadne dwie pozostałe osoby nie znają się.
        Wybieramy
        dwie z nich: $x$ i $y$. W każdej parze $\{a_i, b_i\}$ zliczamy
        znajomych $x$ i $y$.
        Jeśli w każdej
        parze osoby $x$ i $y$ znają co najwyżej 2 osoby, to mają łącznie co
        najwyżej $2m < n+n$ znajomych,
        wbrew założeniu.\\
        Istnieje zatem para, w której znają łącznie co
        najmniej $3$ osoby. Bez
        zmniejszenia ogólności możemy założyć, że osoba $x$ zna obie osoby
        $a_i$ i $b_i$, a osoba $y$ zna osobę $a_i$. Zastępując parę 
        $\{a_i, b_i\}$ parami $\{x, b_i\}$ oraz $\{y, a_i\}$,
        otrzymujemy $m + 1$
        rozłącznych par znajomych, wbrew wyborowi liczby $m$. Otrzymana
        sprzeczność dowodzi, że $m = n$.
 
\end{enumerate}
 
\end{document}