Koło matematyczne I LO w Białymstoku

 
Zadanie rozwiązane w PDF.

Źródło w texu.

 
\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{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]{}
\begin{document}
\title{Zadanko o pomnikach}
\date{}
\maketitle
\paragraph{Zadanie}
Mamy $n$ pomników Endrju Wspaniałego. Między każdymi dwoma pomnikami jest dwustronne bezpośrednie połączenie. Połączenia obsługiwane są przez $k$ przewoźników (dane połączenie obsługuje w obie strony ten sam przewoźnik). Udowodnić, że istnieją takie 3 pomniki, że wszystkie połączenia między nimi obsługuje ten sam przewoźnik, dla:
\begin{enumerate}
\item $n=6$, $k=2$
\item $n=17$, $k=3$
\item $n=66$, $k=4$
\end{enumerate}
\textbf{Rozwiązanie}:\\
Indukcyjnie po $k$.\\
Nazwijmy przewoźników $A,B,C,D,\cdots$.
Dla $n=6$, $k=2$ wybierzmy dowolny pomnik. Ma on $5$ połączeń do innych pomników i jest $2$ przewoźników, więc z Dirichleta ma co najmniej $\lceil\frac{5}{2}\rceil=3$ połączenia obsługiwane przez jednego przewoźnika, którego nazwiemy $A$. Jeżeli pomiędzy którymikolwiek dwoma pomnikami z tych trzech jest połączenie odsługiwane przez $A$, to mamy tezę. Jeżeli nie, to wszystkie połączenia między tymi trzema pomnikami obsługuje $B$ i też mamy tezę.\\
Jeżeli $n=17$, $k=3$, to wybieramy dowolny pomnik. Ma on co najmniej $\lceil\frac{16}{3}\rceil=6$ połączeń obsługiwanych przez jednego przewoźnika, nazywanego $A$. Jeżeli w zbiorze połączeń między tymi 6 (lub więcej) pomnikami jest połączenie obsługiwane przez $A$, to mamy tezę. Jeżeli nie, to mamy 6 pomników, pomiędzy którymi połączenia obsługują dwaj przewoźnicy. Z poprzedniego dowodu mamy tezę.\\
Jeżeli $n=66, k=4$, to analogicznie, dowolny pomnik ma co najmniej $\lceil\frac{65}{4}\rceil=17$ połączeń obsługiwanych przez 1 przewoźnika, więc jeżeli obsługuje on jeszcze jakiekolwiek połączenie między tymi pomnikami, to już mamy tezę, jeżeli nie to jest $17$ pomników i $3$ przewoźników obsługujących połączenie między nimi, z poprzedniego dowodu idzie.\\
Na rysunku widać to ładniej, bo całe zadanie jest grafowe. Liczby $n$, w zależności od $k$ nazywają się liczbami Ramseya.
\end{document}