Koło matematyczne I LO w Białymstoku

 
Zadanir PDF.

 
Rozwiązanie PDF.

Źródło zadań w texu.

 
%        File: zad.tex
%     Created: Tue Jan 10 08:00 PM 2012 C
% Last Change: Tue Jan 10 08:00 PM 2012 C
\documentclass[10pt]{article}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\textwidth 16cm
\textheight 24cm
\oddsidemargin 0cm
\topmargin 0pt
\headheight 0pt
\headsep 0pt
\usepackage[polish]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{polski}
\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]{}
 
\newenvironment{sol}[1][Rozwiązanie. ]{
\vskip 3mm
\noindent\emph{#1}
 
}
{\hfill\par}
 
\newcounter{problem}
\newenvironment{problem}[1][Zadanie]{
\stepcounter{problem}
\vskip 3mm
\noindent{\textsc{\bfseries #1 \theproblem}}\\}
{\hfill\par}
 
\def\abs #1{\left\vert #1\right\vert}
 
\renewcommand{\angle}{\sphericalangle}
\renewcommand{\vec}[1]{\overrightarrow{#1}}
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\renewcommand{\dots}{\ldots}
 
\subimport{./}{style.sty}
%\include{style}
 
\def\headpicture{./images.jpeg}
\def\author{kółko ILO Białystok}
\def\date{na 17 stycznia}
\begin{document}
\section{IV zadanie domowe}
 
\emph{Mam nadzieję, że tym razem dokładniej opisane definicje.}
 
\begin{problem}
    Czwórka do brydża to cztery osoby \emph{z~których każda chce grać z~każdą
    inną z~czwórki}.
 
    Okazało się, że w~gronie $20$ osób nie udało się znaleźć czwórki do
    brydża, wobec czego Yogi, zniechęcony, powiedział ``Na pewno za to znajdą
    się cztery osoby, z~których żadna nie chce grać z~żadną inną''.
 
    Udowodnij, że Yogi miał rację.
\end{problem}
 
\begin{sol}
\begin{enumerate}
    \item Chcemy wykazać, że wśród $20$ osób istnieje czwórka parami
        chętnych do gry lub czwórka niechętna.
        Ogólnie: zamiast $4$ (parami chętne) i~$4$ (parami niechętne) możemy
        wziąć $r$ i~$s$. Niech $R(r, s)$~--- najmniejsza liczba osób taka, że wystąpi $r$
        osób parami chętnych lub $s$ parami niechętnych. Chcemy $R(4, 4) \leq 20$.
    \item Jakieś warunki początkowe: $R(2,s), R(s, 2)$.
    \item Chcemy udowodnić, że $R(r, s) \leq R(r-1,s) + R(r, s-1)$, stąd teza
        przez kolejne oszacowania.
    \item Wybierzmy dowolną $A$ osobę i~rozważmy liczbę $d$ osób, ``z~którymi jest
        chętna''. Pokazać $d \geq R(r-1, s)$ lub $r-1-d \geq R(r, s-1)$.
    \item W~pierwszym przypadku rozważyć osoby ``chętne z~$A$''; pokazać, że
        z~nich da się wybrać $r-1$ chętnych lub $s$ niechętnych; pokazać, że
        łącznie da się wybrać $r$ chętnych lub $s$ niechętnych.
    \item Pokazać to samo w~drugim przypadku.
    \item {\it Wartości $R(5,5)$ oraz $R(6, 6)$ nie są znane dokładnie,
        domniemywa się, że wartość $R(6,6)$ może nie być poznana nigdy;
        w~każdym razie za obliczenie którejkolwiek z~nich jest sporo
        zaszczytów i~spore
        wynagrodzenie.}
\end{enumerate}
\end{sol}
 
\end{document}
 

Źródło rozwiązania w texu.

 
%        File: zad.tex
%     Created: Tue Jan 10 08:00 PM 2012 C
% Last Change: Tue Jan 10 08:00 PM 2012 C
\documentclass[10pt]{article}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\textwidth 16cm
\textheight 24cm
\oddsidemargin 0cm
\topmargin 0pt
\headheight 0pt
\headsep 0pt
\usepackage[polish]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{polski}
\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]{}
 
\newenvironment{sol}[1][Rozwiązanie. ]{
\vskip 3mm
\noindent\emph{#1}
 
}
{\hfill\par}
 
\newcounter{problem}
\newenvironment{problem}[1][Zadanie]{
\stepcounter{problem}
\vskip 3mm
\noindent{\textsc{\bfseries #1 \theproblem}}\\}
{\hfill\par}
 
\def\abs #1{\left\vert #1\right\vert}
 
\renewcommand{\angle}{\sphericalangle}
\renewcommand{\vec}[1]{\overrightarrow{#1}}
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\renewcommand{\dots}{\ldots}
 
\subimport{./}{style.sty}
\def\sectionwidth{10cm}
%\include{style}
 
\def\headpicture{./images.jpeg}
\def\author{kółko ILO Białystok}
\def\date{na 17 stycznia}
\begin{document}
\section{IV zadanie domowe. Rozwiązanie}
 
 
\begin{problem}
    Czwórka do brydża to cztery osoby \emph{z~których każda chce grać z~każdą
    inną z~czwórki}.
 
    Okazało się, że w~gronie $20$ osób nie udało się znaleźć czwórki do
    brydża, wobec czego Yogi, zniechęcony, powiedział ``Na pewno za to znajdą
    się cztery osoby, z~których żadna nie chce grać z~żadną inną''.
 
    Udowodnij, że Yogi miał rację.
\end{problem}
 
\begin{sol}
    Osoby, które chcą ze sobą grać nazwiemy \emph{połączonymi}, osoby, które
    nie chcą~--- \emph{niepołączonymi}. Zbiór $r$ osób parami połączonymi nazwiemy
    \emph{$r$-kliką}, a~zbiór $s$ osób parami niepołączonych nazwiemy
    \emph{$s$-antykliką}.
 
    Niech $R(r, s)$ będzie najmniejszą liczbą osób taką, że w~każdym zbiorze
    $R(r, s)$ osób wystąpi $r$-klika
    lub $s$-antyklika. Chcemy udowodnić, że
    $R(4, 4) \leq 20$.
 
    Zauważmy na początek, że $R(2, s) = s$ dla każdego $s\geq 2$. Wynika to
    z~dwóch obserwacji:
    \begin{enumerate}
        \item Jeżeli mamy $s-1$ osób, z~których żadne nie są
    połączone, to nie mamy $2$-kliki, ani $s$-antykliki, więc $R(2,s) \geq s$.
 
        \item Jeżeli weźmiemy $s$ osób to albo pewne dwie z~nich są połączone (więc
    tworzą $2$-klikę) albo wszystkie osoby są niepołączone, więc tworzą
    $s$-klikę. Stąd $R(2, s) \leq s$.
    \end{enumerate}
    Analogicznie dowodzimy $R(s, 2) = s$ (\emph{lub ogólniej $R(r, s) = R(s,
    r)$}).
 
    Chcemy teraz udowodnić, że $R(r, s) \leq R(r-1,s) + R(r, s-1)$.
 
    Niech $R:=R(r-1,s) + R(r, s-1)$. Rozważmy dowolny zbiór $R$ osób i~dowolną
    osobę $\alpha$. Chcemy pokazać, że istnieje w~tym (dowolnie wybranym!) zbiorze $r$-klika lub
    $s$-antyklika, co z~definicji $R(r, s)$ pokaże $R\geq R(r, s)$, czyli
    $R(r, s) \leq R(r-1, s) + R(r, s-1)$.
 
    Załóżmy, że $\alpha$ jest połączona z~$d$ osobami. Wtedy
    $\alpha$ jest niepołączona z~$R-1-d$ osobami.
 
    Chcemy pokazać, że $d \geq R(r-1, s)$ lub $R-1-d \geq R(r, s-1)$. Zaiste,
    gdyby żadna z~tych nierówności nie zaszła, to $d \leq R(r - 1, s) - 1$
    oraz $R - 1 - d \leq R(r, s-1) - 1$, stąd $R - 1 = (R - 1 - d) + d\leq
    R(r-1,s) - 1 + R(r, s-1) - 1 = R-2$, sprzeczność.
 
    \def\D{\mathcal{D}}
    \def\ND{\mathcal{ND}}
    Rozważmy dwa przypadki
    \begin{enumerate}
        \item $d \geq R(r-1, s)$.\\
            Niech $\D$ oznacza zbiór osób połączonych
            z~$\alpha$. Skoro $|\D| \geq R(r-1, s)$ to w~$\D$ istnieje
            $r-1$-klika lub $s$-antyklika. Wobec tego w~$\D \cup \left\{
            \alpha\right\}$ istnieje $r$-klika (bo wszystkie elementy $\D$ są
            połączone z~$\alpha$ lub $s$-antyklika, co dowodzi naszej tezy.
        \item $R - 1 - d \geq R(r, s-1)$.\\
            Niech $\ND$ oznacza zbiór osób
            niepołączonych z~$\alpha$, wtedy w~$\ND$ istnieje $r$-klika lub
            $s-1$-antyklika, więc w~$\left\{ \alpha \right\} \cup \ND$
            istnieje $r$-klika lub $s$-antyklika.
    \end{enumerate}
 
    Teraz oszacowujemy:
    \begin{align*}
    R(3,3) \leq R(3, 2) + R(2, 3) = 6\quad R(4,3) \leq R(4,2) + R(3,3) =
    10\\ R(3,4) \leq R(2,4) + R(3,3) = 10\quad R(4,4) \leq R(4,3) + R(3, 4) = 20.
    \end{align*}
 
 
    \emph{Liczby $R(r, s)$ nazywają się \emph{liczbami Ramseya}. Dokładna
    wartość $R(4,4)$ to $18$.}
\end{sol}
 
\end{document}