Materiały z obozu PROSerwy 2010 dostępne są w formie książeczki, jak też w formie elektronicznej poniżej.
Materiały te składają się z ponad 50 zadań olimpijskich wraz z rozwiązaniami oraz 9 wykładów z zadaniami i wskazówkami do zadań. Paczka "wszystkie materiały" zawiera również pliki źródłowe .tex oraz pliki źródłowe rysunków. Sugerujemy skorzystanie z tej paczki, a nie z poniższego źródła tex, gdyż ono nie zawiera plików z rysunkami.
Miłego czytania życzy kadra obozu:
Aleksandra Baranowska
Joachim Jelisiejew
Mateusz Jocz
Źródło tex.
\documentclass[a4paper, twoside, openright]{book} \usepackage{amssymb} \usepackage{amsmath} \textwidth 16cm \textheight 24cm \oddsidemargin 0.5cm \evensidemargin -0.5cm %\topmargin 0pt %\headheight 0pt %\headsep 0pt \usepackage[polish]{babel} \usepackage[utf8]{inputenc} \usepackage[OT4]{fontenc} %\usepackage{lmodern} \usepackage{import} \usepackage{graphicx} \usepackage[cmyk,usenames,dvipsnames]{xcolor} \usepackage{fancyhdr} \usepackage{titlesec} \usepackage{ifthen} \usepackage[pdfborder={0 0 0}]{hyperref} %\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{obs}[thm]{Obserwacja} \newtheorem{uwaga}[thm]{Uwaga} \newtheorem{useless}[thm]{}
% Numbering -------------- \def\partID{0} \def\chapterID{0} \def\sectionID{0}
\newcounter{problemNo}[section] \newcounter{lectureNo}[part]
\def\incLecID{\addtocounter{lectureNo}{1}} \def\getLecID{W\arabic{lectureNo}}
\def\getID{\addtocounter{problemNo}{1} \partID\ \sectionID.\arabic{problemNo}} %------------------------
% Srodowiska porzadne ----------------------------
\newenvironment{proof}[1][Dowód. ]{ \noindent\textsc{#1}
} {\nolinebreak[4]\hfill$\blacksquare$\\\par} \newenvironment{sol}[1][Rozwiązanie. ]{ \ifthenelse{\equal{#1}{Rozwiązanie. }} { \textbf{Rozw \getID} } { \noindent\textsc{#1} } \\ } {\hfill\par} \def\ans{
\textbf{Odpowiedź: }}
\newenvironment{problem}[2]{ \textbf{\getID} %\noindent\textsc{Zadanie} (trudność: #1, źródło: #2) \\ } {\hfill\par}
\newenvironment{hint}{ \noindent\textbf{Wskazówka \getID}
} {\hfill\par}
\newenvironment{lecture}[1][Wykład.]{ \incLecID \newsection{#1}{\getLecID} } {\hfill\par}
%------------------------------------------
\def\deg{^{\circ}}
\def\mono#1#2{ \left\lceil \begin{array}{#1} #2 \end{array} \right\rfloor }
%do tytulowej \def\person#1#2{ #1 \textsc{#2} }
\renewcommand{\thethm}{} \renewcommand{\angle}{\sphericalangle} \renewcommand{\vec}[1]{\overrightarrow{#1}} \renewcommand{\leq}{\leqslant} \renewcommand{\geq}{\geqslant} \renewcommand{\dots}{\ldots}
%\include{style}
% Liczniki ---------------------
\def\newpart#1#2{ \def\partID{#2} \part{#1} }
\def\newchapter#1#2{ \def\chapterID{#2} \begin{minipage}{8cm} \chapter{#1} \vskip 2cm
\end{minipage}\begin{minipage}{6.2cm} \includegraphics[height=3cm]{jaceklogo.pdf}
\end{minipage}
}
\def\newsection#1#2{ \def\sectionID{#2} \section{#1} }
% -----------------------------
% Zmiana wygladu rozdzialu. \newcommand{\HRule}{\rule{\linewidth}{0.2mm}} %\titleformat{\chapter} %{\normalfont\Huge\bfseries\filcenter} %{ %\includegraphics[height=0.75cm]{jaceklogo.pdf} %} %{1mm} %{}
% brak pustej strony po part \let\cleardoublepage\clearpage
% kolor okladki \definecolor{myblue}{cmyk}{0.63,0.41,0,0.04}
%\DeclareErrorFont{T1}{cmr}{bx}{sc}{10} % BEGIN DOC ---------------------------------------------------- \begin{document} \setlength{\leftmargin}{0pt}
% Aby nie bylo pustej strony po \part. \makeatletter \renewcommand\@endpart{\vfil \if@twoside \null \thispagestyle{empty}% \newpage \thispagestyle{empty}% \mbox{} \newpage \fi \if@tempswa \twocolumn \fi} \makeatother
% header ----------------- \pagestyle{fancy}
% BEGIN TEXT------------------------------------------------------------------
%% Okladka--------------------------------------------------------------------- %% OKLADKA--------------------------------------------------------------------- %\setlength{\topmargin}{-0.5in} %\eject \pdfpagewidth=216truemm \pdfpageheight=303truemm %{\selectcolormodel{cmyk}\pagecolor{myblue}}
%\begin{titlepage}
%%authors %{ %\huge \bfseries %\begin{center} %Joachim \textsc{Jelisiejew}\\ %Aleksandra \textsc{Baranowska} %Mateusz \textsc{Jocz} %\end{center} %} %\vskip 1cm
%\begin{center}
%% Upper part of the page %\begin{minipage}{7cm} % \includegraphics[height=5cm]{micek-z-matmy.png} %\end{minipage}\begin{minipage}{7cm} % \includegraphics[height=3cm]{jaceklogo-okladka.png} %\end{minipage}\\[1cm] %\textsc{\Large I Liceum Ogólnokształcące im. Adama Mickiewicza w~Białymstoku}\\[0.2cm] %\textsc{\Large Podlaskie Stowarzyszenie na~Rzecz~Uzdolnionych}\\[1.5cm]
%% Title %\HRule \\[0.4cm] %{ \Huge \bfseries Obóz Naukowy PROSERWY 2010}\\[0.1cm] %{\huge \bfseries Część matematyczna} %\HRule \\[1.5cm]
%\begin{minipage}{110mm} %\Large\emph{Kadra matematyczna:}\\ %\person{Aleksandra}{Baranowska}\\ %\person{Joachim}{Jelisiejew} (kierownik)\\ %\person{Mateusz}{Jocz}\\ %$ $\\ %\end{minipage}\begin{minipage}{70mm} %\Large\emph{Główni organizatorzy:}\\ %\person{Ireneusz}{Bujnowski}\\ %\person{Iwona}{Bujnowska}\\ %\person{Joachim}{Jelisiejew}\\ %\person{Jacek}{Tomasiewicz}\\ %\end{minipage}
%\vfill
%% Bottom of the page %{\LARGE \bfseries Serwy, 19 -- 25 września 2010}\\ %{\LARGE (wydanie drugie)}
%\end{center}
%\end{titlepage}
% STRONA TYTULOWA ----------------------------------------------------
\newpage \setlength{\topmargin}{-0.5in} % clean-up after title page \eject \pdfpagewidth=210truemm \pdfpageheight=297truemm \pagecolor{white}
\begin{titlepage}
%authors { \huge \bfseries \begin{center} Joachim \textsc{Jelisiejew}\\ Aleksandra \textsc{Baranowska}\quad Mateusz \textsc{Jocz} \end{center} } \vskip 1cm
\begin{center}
% Upper part of the page \begin{minipage}{7cm} \includegraphics{micek-5cm.jpg} \end{minipage}\begin{minipage}{7cm} \includegraphics[height=3cm]{jaceklogo.png} \end{minipage}\\[1cm] \textsc{\Large I Liceum Ogólnokształcące im. Adama Mickiewicza w~Białymstoku}\\[0.2cm] \textsc{\Large Podlaskie Stowarzyszenie na~Rzecz~Uzdolnionych}\\[1.5cm]
% Title \HRule \\[0.4cm] { \Huge \bfseries III Obóz Naukowy PROSERWY}\\[0.1cm] {\huge \bfseries Część matematyczna} \HRule \\[1.5cm]
\begin{minipage}{110mm} \Large\emph{Kadra matematyczna:}\\ \person{Aleksandra}{Baranowska}\\ \person{Iwona}{Bujnowska}\\ \person{Joachim}{Jelisiejew} (koordynator)\\ \person{Mateusz}{Jocz}\\ \end{minipage}\begin{minipage}{70mm} \Large\emph{Główni organizatorzy:}\\ \person{Iwona}{Bujnowska}\\ \person{Ireneusz}{Bujnowski}\\ \person{Joachim}{Jelisiejew}\\ \person{Jacek}{Tomasiewicz}\\ \end{minipage}
\vfill
% Bottom of the page {\LARGE \bfseries Serwy, 19 -- 25 września 2010}\\ {\LARGE (wydanie drugie)}
\end{center}
\end{titlepage} \newpage \setlength{\topmargin}{-8mm}
% Pusta strona -----------------------
\newpage \thispagestyle{empty} $ $ \newpage
%-------------------
\tableofcontents
\newpart{Grupa średnio zaawansowana}{ŚR}
\newchapter{Zadania}{1} \renewcommand{\labelenumi}{}
\newsection{Dzień I}{1} \begin{enumerate}
\item
\begin{problem}{2}{V LO w Krakowie} Niech $ABC$ będzie trójkątem ostrokątnym, zaś punkty $K,L,M$ odpowiednio środkami łuków $BC, AC, AB$ okręgu na nim opisanego, niezawierających przeciwległych wierzchołków. Wykaż, że środek okręgu wpisanego w trójkąt $ABC$ jest punktem przecięcia wysokości trójkąta $KLM$. \end{problem}
\item
\begin{problem}{1}{Olsztyn} Ciąg liczb całkowitych $(b_1,b_2,...,b_{2009})$ jest permutacją ciągu $(a_1,a_2,...,a_{2009})$. Wykaż, że iloczyn \[(a_1-b_1)\cdot(a_2-b_2)\cdot \ldots \cdot (a_{2009}-b_{2009})\] jest liczbą parzystą. \end{problem}
\item
\begin{problem}{1}{znane} Rozwiąż równanie $2^x + 2^y = 2^z$ w liczbach całkowitych dodatnich. \end{problem}
\end{enumerate}
\newsection{Dzień II}{2} \begin{enumerate}
\item
\begin{problem}{1}{znane} Jaka jest maksymalna liczba kątów ostrych w wielokącie wypukłym? \end{problem}
\item
\begin{problem}{1}{znane} Pokaż, że w każdym trójkącie zachodzi \[\frac{1}{2r} < \frac{1}{h_1} +\frac{1}{h_2} < \frac{1}{r},\] gdzie $r$ to promień okręgu wpisanego, a $h_1,h_2$ to dowolne różne wysokości trójkąta. \end{problem}
\item
\begin{problem}{1}{Yogi,znane w nieco innej formie} Pewna potęga liczby całkowitej $x$ jest podzielna przez liczbę naturalną $n$. Uzasadnij, że istnieje takie $a$ całkowite, że $(1-x)a$ daje resztę $1$ z dzielenia przez $n$. \end{problem}
\end{enumerate} \newsection{Dzień III}{3} \begin{enumerate}
\item
\begin{problem}{1}{koło II LO w Gorzowie Wielkopolskim} Trzy odcinki o długości $1$ przecinają się w jednym punkcie. Końce tych odcinków są wierzchołkami sześciokąta. Rozstrzygnij, czy jego obwód może być większy od $6$. \end{problem}
\item
\begin{problem}{0.5}{Gorzów} Znajdź wszystkie liczby całkowite dodatnie $n$, dla których liczba $n^4 + 4$ jest pierwsza. \end{problem}
\item
\begin{problem}{1}{VLO Kraków} W pewnym turnieju wystąpiło $n$ drużyn, grano systemem "każdy z każdym", bez remisów. Udowodnij, że jeżeli pewne dwie drużyny wygrały taką samą liczbę spotkań, to można wybrać takie trzy drużyny $A,B,C$, że $A$ wygrała z $B$, $B$ z $C$, $C$ z $A$. \end{problem}
\end{enumerate} \newsection{Dzień IV}{4} \begin{enumerate}
\item
\begin{problem}{1}{koło II LO w Gorzowie Wielkopolskim} Udowodnij, że w trójkącie prostokątnym o przyprostokątnych $a, b$, przeciwprostokątnej $c$ i wysokości $h$ opuszczonej z wierzchołka przy kącie prostym spełniona jest nierówność $c+h > a+b$. \end{problem}
\item
\begin{problem}{1}{znane} Dany jest kwadrat $2^n\times2^n$ z wyciętym kwadratem jednostkowym. Rozstrzygnij, w zależności od $n$, czy dla każdego położenia wyciętego kwadratu można wypełnić ten kwadrat klockami w kształcie litery $L$ -- dwa kwadraciki z jednym doklejonym obok. \end{problem}
\item
\begin{problem}{1}{mathlinks} Znajdź wszystkie liczby pierwsze takie, że $2^p + p^2$ jest również liczbą pierwszą. \end{problem}
\end{enumerate} \newsection{Dzień V}{5} \begin{enumerate}
\item
\begin{problem}{1}{Olala} Dane mamy liczby rzeczywiste $a,b,c$. Wiedząc, że $a+b+c=0$ oraz $a^2+b^2+c^2=1$, oblicz $a^4+b^4+c^4$. \end{problem}
\item
\begin{problem}{1,oczywiście nie tym sposobem :P}{znane} Udowodnij, że na płaszczyźnie ze standardowym układem współrzędnych nie istnieje trójkąt równoboczny o wszystkich wierzchołkach mających współrzędne całkowite. \end{problem}
\item
\begin{problem}{1}{mathlinks} Niech $\mathcal{S}$ będzie podzbiorem $[0,1]$ złożonym ze skończonej liczby przedziałów. Udowodnij, że jeżeli suma długości tych przedziałów jest większa niż $0.6$, to $\mathcal{S}$ zawiera dwie liczby, których różnica wynosi dokładnie $0.1$. \end{problem}
\end{enumerate} \newsection{Mecz matematyczny}{M} \begin{enumerate}
\item
\begin{problem}{1-2}{Znane} W trójkącie ostrokątnym $ABC$ wysokości $AD, BE, CF$ przecinają się w punkcie $H$. Uzasadnij, że $H$ jest środkiem okręgu wpisanego w $DEF$. \end{problem}
\item
\begin{problem}{1}{V LO w Krakowie} W trójkącie ostrokątnym $ABC$ odcinek $AD$ jest wysokością, a punkty $E, F$ rzutami punktu $D$ odpowiednio na boki $AB$ i $AC$. Dowiedź, że na czworokącie $BCFE$ da się opisać okrąg. \end{problem}
\item
\begin{problem}{2}{mathlinks} Ile maksymalnie elementów może mieć $A \subseteq \left\{ 1,2,\dots, 2\cdot 2010 +1 \right\}$ mający następującą własność: \[ \hbox{ nie istnieją } x, y, z\in A \hbox{ takie, że } x+y=z \] \end{problem}
\item
\begin{problem}{1}{Gorzów Liga} Niech $x,y > 1$ będą liczbami całkowitymi takimi, że $NWD(x,y) = 1$. Udowodnij, że jeżeli $n$ jest parzystą liczbą naturalną, to $x+y$ nie dzieli $x^n + y^n$. \end{problem}
\item
\begin{problem}{1}{znane} W trójkącie $ABC$ kąt przy wierzchołku $B$ jest dwa razy większy od kąta przy wierzchołku $A$. Wykaż, że zachodzi zależność: ${AC}^2=BC(AB+BC)$. \end{problem}
\item
\begin{problem}{1}{Olsztyn} Wykaż, że dla każdego $n\in\mathbb N$ liczba $n^2+3n+5$ nie jest podzielna przez $121$. \end{problem}
\item
\begin{problem}{1}{Soviet Math Competitions} Udowodnij, że nie istnieje takie całkowite dodatnie $m$, że $m(m+1)$ jest potęgą liczby całkowitej o~wykładniku nie mniejszym niż $2$. \end{problem}
\item
\begin{problem}{1}{znane,Szczecińskie geo(dowód lematu)} Niech $\alpha,\beta,\gamma$ będą kątami pewnego trójkąta, a $a,b,c$ długościami boków leżących naprzeciwko $\alpha, \beta, \gamma$ odpowiednio. Wykaż, że prawdziwe są nierówności: \[60^{\circ}\leq \frac{\alpha a+\beta b+\gamma c}{a+b+c}< 90^{\circ}\] \end{problem}
\item
\begin{problem}{1}{V LO Kraków} Dany jest $2n$-kąt foremny, $n\geq2$. Yogi i Mateusz grają w następującą grę: na zmianę rysują przekątne tego wielokąta, ale tak, by nie miały punktów wspólnych z dotychczas narysowanymi przekątnymi. Przegrywa ten, który nie może narysować już żadnej przekątnej. Zaczyna Yogi, który z graczy ma strategię wygrywającą? \end{problem}
\item
\begin{problem}{2}{Yogi} Niech liczby $a,b,c$ będą dodatnie. Uzasadnij, że \[a^3 + b^3 + c^3 + 3 \geq a^2 + b^2 + c^2 + a + b + c.\] \end{problem}
\end{enumerate} \newsection{Trudniejsze}{T} \begin{enumerate}
\item
\begin{problem}{1}{znane} Pokaż, że dla dowolnych liczb całkowitych $a,b$ istnieją takie liczby całkowite $c,d$, że \[c^2 + d^2 = 13(a^2 + b^2).\] \end{problem}
\item
\begin{problem}{1}{znane} W czworokącie $ABCD$ punkty $M,N,K,L$ są odpowiednio środkami boków $CD,DA,AB,BC$.
Wykaż, że \[NL+MK\leq \frac{AB + BC + CD + DA}{2}.\] \end{problem}
\item
\begin{problem}{1}{Costa Rica Final Round 2009} Liczby rzeczywiste dodatnie $x,y$ spełniają $(1+x)(1+y)=2$. Udowodnij nierówność \[xy+\frac{1}{xy}\geq 6.\] \end{problem}
\item
\begin{problem}{1}{Yogi,znane?} Danych jest $13$ odcinków, których długości są całkowite. Uzasadnij, że jeśli długości wszystkich odcinków nie przekraczają $200$, to z pewnych $3$ odcinków da się zbudować trójkąt. Czy pozostanie to prawdą, jeżeli zamiast $13$ byłoby $12$ odcinków? \end{problem}
\end{enumerate}
\newchapter{Rozwiązania}{1}
\newsection{Dzień I}{1} \begin{enumerate}
\item
\begin{sol}
\begin{minipage}[<+tb+>]{7.5cm} \includegraphics{graph_trojkaty} \end{minipage}\begin{minipage}{7.5cm} Zauważmy, że skoro punkty $K,L,M$ są odpowiednio środkami łuków $BC, AC, AB$, to proste $AK, BL, CM$ są dwusiecznymi kątów trójkąta $ABC$, przecinają się zatem w punkcie będącym środkiem okręgu wpisanego w ten trójkąt. Wystarczy zatem udowodnić, że proste $AK, BL, CM$ zawierają wysokości trójkąta $KLM$.
Rozpatrzmy kąty w trójkącie $KLM$. Oznaczmy jako $\alpha$ kąt $BLK$. Łuki $BK$ i $KC$ są równe, zatem również $\angle KMC=\alpha$. Analogicznie otrzymamy $\angle BLM= \angle MKA=\gamma$ oraz $\angle AKL=\angle LMC=\beta$. Suma kątów w trójkącie $KLM$ wynosi $2(\alpha+\beta+\gamma)$, zatem $\alpha+\beta+\gamma=90\deg$.
Oznaczmy jako $X$ punkt przecięcia prostych $AK$ i $ML$. Suma miar kątów w trójkącie $KXL$ wynosi $\alpha+\beta+\gamma+\angle KXL$. Kąt $KXL$ jest więc prosty, zatem istotnie prosta $AK$ zawiera wysokość trójkąta $KLM$. Analogicznie przeprowadzamy dowód dla prostych $BL$ i $CM$. \end{minipage}
\end{sol}
\item
\begin{sol} Niech $P$ będzie ilością liczb parzystych wśród $a_1,\dots,a_{2009}$, a $NP$ -- nieparzystych.
Skoro $P + NP = 2009$, to jedna z tych liczb jest nie większa niż $1004$.
Zastanówmy się, ile może być maksymalnie par $(a_i, b_i)$ takich, że $a_i$ i $b_i$ nie są tej samej parzystości.
Para $(a_i,b_i)$ liczb o różnej parzystości, zawiera jedną liczbę parzystą i jedną nieparzystą, a wśród liczb $a_1, a_2,\dots, a_{2009}, b_1, b_2,\dots, b_{2009}$ jest dokładnie $2\cdot P$ parzystych i $2\cdot NP$ nieparzystych, więc może być najwyżej $\min(2\cdot P, 2\cdot NP) \leq 2008 < 2009$ takich par. Powstanie więc przynajmniej jedna para liczb o tej samej parzystości.
Jako że liczby o tej samej parzystości dają parzystą różnicę, cały iloczyn $(a_1-b_1)\cdot(a_2-b_2)\cdot\ldots\cdot (a_{2009}-b_{2009})$ jest liczbą parzystą. \end{sol}
\item
\begin{sol} Jeżeli $(x,y,z)$ spełniają dane równanie to $2^z > 2^x, 2^y$, zatem $z > x,y$, czyli $z-1\geq x,y$. Wtedy jednak \[2^z = 2\cdot 2^{z-1} = 2^{z-1} + 2^{z-1} \geq 2^x + 2^y\] i równość zachodzi wtedy i tylko wtedy gdy $x=y=z-1$.
Ostatecznie rozwiązaniami równania są trójki $(n, n, n+1)$, gdzie $n$ jest całkowite dodatnie. \end{sol}
\end{enumerate} \newsection{Dzień II}{2} \begin{enumerate}
\item
\begin{sol}
Oznaczmy przez $m$ liczbę kątów ostrych wielokąta, a przez $n$ liczbę wszystkich kątów. Wiemy, że suma miar kątów w wielokącie mającym $n$ kątów wynosi $180\deg \cdot (n-2)$. Zatem prawdziwe jest: \[ 180\deg\cdot (n-2)=\hbox{ suma kątów ostrych }+ \hbox{ suma }n-m\hbox{ pozostałych kątów}<m \cdot 90\deg + (n-m)\cdot 180\deg,\] która to nierówność jest równoważna kolejno nierównościom: \[-360\deg<-90\deg \cdot m\] \[m<4\] \[m\leq 3\] Zauważmy, że trójkąt ostrokątny ma trzy kąty ostre, więc największą liczbą kątów ostrych wielokąta wypukłego jest liczba 3.
\end{sol}
\item
\begin{sol}
Niech $a,b$ będą długościami boków trójkąta, na które opuszczone są wysokości $h_1,h_2$ odpowiednio, $c$ będzie długością trzeciego boku trójkąta, a $S$ polem tego trójkąta.
Okrąg wpisany w trójkąt jest styczny do wszystkich jego boków, więc pole trójkąta możemy zapisać jako sumę trzech trójkątów o podstawach odpowiednio $a,b,c$ i wysokości $r$: $S=\frac{(a+b+c)r}{2}$, skąd $r=\frac{2S}{a+b+c}$. Oczywiście $S=\frac{ah_1}{2}=\frac{bh_2}{2}$, więc $h_1=\frac{2S}{a}, h_2=\frac{2S}{b}$.
Podstawiamy $r,h_1,h_2$ do nierówności: \[\frac{a+b+c}{4S} < \frac{a}{2S} +\frac{b}{2S} < \frac{a+b+c}{2S}\] \[a+b+c < 2a +2b < 2a+2b+2c.\] Prawa nierówność jest oczywista, a odejmując od lewej stronami wyrażenie $a+b$, otrzymujemy nierówność trójkąta: $c<a+b$. \end{sol}
\item
\begin{sol} Załóżmy, że $k$ jest takie, że $n|x^k$.
Zauważmy, że \[(1 - x)(1+x+x^2 + \dots +x^{k-1}) = 1^k - x^k \equiv 1 \mod n\] Zatem liczba $a=1+x+x^2 + \dots + x^{k-1}$ spełnia warunki zadania. \end{sol}
\end{enumerate}
\newsection{Dzień III}{3} \begin{enumerate}
\item
\begin{sol} \begin{minipage}{4cm} \includegraphics[height=40mm]{szesciokat_ola} \end{minipage}\begin{minipage}{12cm}
Zapiszmy sześciokrotnie nierówność trójkąta z oznaczeniami jak na rysunku: $$a \leq (1-y)+(1-z) \quad b \leq (1-x) + (1-y) \quad c \leq (1-x)+z$$ $$d \leq y+z \quad e \leq x+y \quad f \leq (1-z)+x$$
Dodając nierówności stronami otrzymujemy: $$a+b+c+d+e+f \leq 6.$$ Widzimy zatem, że obwód danego sześciokąta nie może być większy niż $6$. \end{minipage}
\end{sol}
\item
\begin{sol} Zauważmy, że \[n^4 + 4 = (n^4 + 4n^2 + 4) - 4n^2 = (n^2 + 2)^2 - (2n)^2 = (n^2 - 2n + 2)(n^2 + 2n + 2)\] Jeżeli $n > 1$ to każda z tych liczb jest większa od $1$, zatem $n^4 + 4$ nie jest pierwsze.
Dla $n=1$ liczba $1^4 + 4 = 5$ jest pierwsza. \end{sol}
\item
\begin{sol}
Niech drużyny $X$ i $Y$ będą tymi, które wygrały po $k$ spotkań, przegrały zatem po $n-k-1$.
Po ewentualnej zamianie nazw możemy założyć, że drużyna $X$ wygrała z drużyną $Y$. Wśród spotkań z pozostałymi drużynami $X$ ma $k-1$ wygranych i~$n-k-1$ przegranych, $Y$ natomiast $k$ wygranych i $n-k-2$ przegranych.
Zauważmy, że zbiory drużyn, z którymi drużyna $Y$ wygrała i $X$ przegrała, nie mogą być rozłączne, gdyż $k+(n-k-1)=n-1>n-2$. Istnieje zatem drużyna $Z$, która wygrała z $X$ i przegrała z~$Y$. Drużyny $X,Y,Z$ są szukanymi drużynami.
\end{sol}
\end{enumerate}
\newsection{Dzień IV}{4} \begin{enumerate}
\item
\begin{sol}
Zauważmy, że pole trójkąta możemy tu zapisać na dwa sposoby: $P = \frac{1}{2}ab = \frac{1}{2}ch$.
Teza jest równoważna nierówności $(c+h)^2 > (a+b)^2$, gdyż rozpatrywane przez nas wartości są dodatnie.
Zauważmy, że $(a+b)^2 = (a^2 + b^2) + 2ab$, co na mocy twierdzenia Pitagorasa oraz zależności między polami równe jest $c^2 + 2ch = (c+h)^2 - h^2$. Zachodzi zatem $(a+b)^2 < (c+h)^2$, czyli teza. \end{sol}
\item
\begin{sol}
Pokażmy, że wypełnienie takie jest zawsze możliwe przez indukcję względem $n$.
Jeżeli $n=1$, czyli mamy do czynienia z kwadratem $2\times 2$, to jest jasne, że można tak wypełnić --- wystarczy odpowiednio ułożyć jeden klocek.
Załóżmy, że udowodniliśmy, że da się wypełnić każdy kwadrat o boku $2^{n-1}$ i chcemy teraz pokazać, jak wypełnić kwadrat o boku $2^n$.
\begin{minipage}[<+tb+>]{2cm} \includegraphics{kwadrat} \end{minipage} \begin{minipage}{13cm} Podzielmy kwadrat $2^n \times 2^n$ z wyciętym polem na cztery przystające kwadraty i trzy pełne z nich połączmy klockiem, jak na rysunku (szare pole to wycięty kwadracik, a trzy niebieskie to klocek).
Otrzymujemy cztery kwadraty o boku $2^{n-1}$ z wyciętym jednym polem. Każdy z nich da się wypełnić klockami, a więc i cały kwadrat można wypełnić klockami. \end{minipage} \end{sol}
\item
\begin{sol} Po pierwsze przeliczamy, że dla $p=2$ liczba $2^p + p^2 = 8$ nie jest pierwsza, a dla $p=3$ liczba $2^p + p^2 = 17$ jest pierwsza.
Załóżmy teraz, że $p\neq 3$ i $p\neq 2$. Liczba $p$ jest nieparzysta: $p=2k+1$ dla pewnego $k$ całkowitego, więc \[2^p = 2^{2k+1} = 4^k \cdot 2 \equiv 1^k \cdot 2 = 2 \mod 3\] oraz $p^2 \equiv 1 \mod 3$, co sprawdzamy przeliczając dwie możliwe reszty $p$ z dzielenia przez $3$.
Łącznie \[2^p + p^2 \equiv 2 + 1 \equiv 0 \mod 3\] i $2^p + p^2$ jest pierwsze, zatem $2^p + p^2 = 3$, ale $p>2$, więc $2^p > 4$, sprzeczność.
Ostatecznie jedyną liczbą spełniającą warunki zadania jest $p=3$. \end{sol}
\end{enumerate}
\newsection{Dzień V}{5} \begin{enumerate}
\item
\begin{sol}
Z danych zależności obliczyć możemy: $$ab+bc+ca=\frac{1}{2}((a+b+c)^2-(a^2+b^2+c^2))=-\frac{1}{2}.$$
Zauważmy następnie, że $(ab+bc+ca)^2=a^{2}b^{2}+b^{2}c^{2}+c^{2}a^{2}+2abc(a+b+c)$, a więc $$a^{2}b^{2}+b^{2}c^{2}+c^{2}a^{2}=\frac{1}{4}.$$
Wreszcie $(a^2+b^2+c^2)^2=a^4+b^4+c^4+2(a^{2}b^{2}+b^{2}c^{2}+c^{2}a^{2})$, więc $$1=a^4+b^4+c^4+\frac{1}{2} \hbox{ czyli } a^4+b^4+c^4=\frac{1}{2}.$$
\end{sol}
\item
\begin{sol}
\begin{minipage}[<+tb+>]{4.5cm} \includegraphics{pick} \end{minipage}\begin{minipage}{10cm} Załóżmy, że taki trójkąt istnieje. Zauważmy, że jeżeli ma on bok $a$, to liczba $a^2$ jest liczbą całkowitą.
Wielokąt wypukły, którego wszystkie wierzchołki mają współrzędne całkowite ma pole postaci $\frac{1}{2}K$, gdzie $K$ jest liczbą całkowitą. Faktycznie, jeżeli dobudujemy do boków trójkąty prostokątne, otrzymamy wielokąt o polu całkowitym, a dobudowywane trójkąty mają pola postaci $\frac{1}{2}\cdot$\emph{liczba całkowita}, patrz rysunek.
A więc nasz trójkąt ma pole równe $\frac{1}{2}k$, gdzie $k\in \mathbb{Z}$. \end{minipage}
Z drugiej strony trójkąt równoboczny o boku $a$ ma pole równe $\frac{a^2\sqrt{3}}{4}$: \[ \frac{1}{2}k = \frac{a^2\sqrt{3}}{4} \] \[ \frac{2k}{a^2} = \sqrt{3} \] Stwierdziliśmy wcześniej, że $a^2, k$ są liczbami całkowitymi. Z powyższego wzoru wynika więc, że $\sqrt{3}$ jest liczbą wymierną, a to nieprawda. Sprzeczność. \end{sol}
\item
\begin{sol} Dzielimy przedziały z $\mathcal{S}$ tak, by były one parami rozłączne i każdy z nich był zawarty albo w $[0,0.9]$ albo w $[0.9,1]$. Nie zmienia to sumy długości przedziałów.
Niech $A_1,\dots,A_n$ będą tymi przedziałami z $\mathcal{S}$, które leżą w odcinku $[0, 0.9]$.
Oczywiście suma długości przedziałów $A_1,\dots,A_n$ jest większa niż $0.6 - 0.1 = 0.5$.
Rozważmy przedziały przesunięte o $0.1$: \[A_1 + 0.1, A_2 + 0.1, \dots, A_n + 0.1\] Gdyby którykolwiek z punktów tych przedziałów należał do przedziału z $\mathcal{S}$, to mielibyśmy tezę. Załóżmy zatem, że $A_1 + 0.1,\dots,A_n + 0.1$ są rozłączne z $\mathcal{S}$.
Suma długości przedziałów $A_1+0.1,\dots,A_n + 0.1$ jest taka sama jak suma długości $A_1,\dots,A_n$, czyli większa od $0.5$. Ale $A_1,\dots,A_n \subseteq [0,0.9]$, zatem $A_1+0.1,\dots, A_n +0.1 \subseteq [0,1]$.
Odcinek $[0,1]$ zawiera więc parami rozłączne przedziały $A_1,\dots,A_n,A_1 + 0.1, \dots, A_n + 0.1$ o sumie długości większej niż $0.5 + 0.5 = 1$. Sprzeczność. \end{sol}
\end{enumerate}
\newsection{Mecz matematyczny}{M} \begin{enumerate}
\item
\begin{sol}
\begin{minipage}{7cm} \includegraphics{orthocenter_as_inscribed} \end{minipage}\begin{minipage}{8cm} Mamy $\angle HEC = \angle HDC = 90\deg$, a więc $\angle HEC + \angle HDC = 180\deg$, czyli punkty $H,E,C,D$ leżą na jednym okręgu.
Kąty $\angle HDE$ i $\angle HCE$ są oparte na tym samym łuku, ergo $\angle HDE = \angle HCE = 90\deg - \angle CAB$.
Analogicznie przeliczamy $\angle HDF = 90\deg - \angle CAB$, a~więc $\angle HDF = \angle HDE$.
Identycznie argumentując $\angle HFE = \angle HFD$.
Punkt $H$ jest środkiem okręgu wpisanego w $DEF$ jako punkt przecięcia dwusiecznych kątów $\angle EDF$ i~$\angle DFE$. \end{minipage} \phantom{.} \end{sol}
\item
\begin{sol}
\begin{minipage}[<+tb+>]{5.5cm} \includegraphics{6_7graph} \end{minipage}\begin{minipage}{9.5cm} Zauważmy na początek, że $\angle AED + \angle AFD = 90 \deg + 90\deg = 180\deg$, więc da się opisać okrąg na czworokącie $AEDF$.
Oznaczmy teraz kąt $\angle DAF$ jako $\alpha$. Z twierdzenia o kątach wpisanych opartych na tym samym łuku mamy $\angle DEF = \angle DAF = \alpha$, więc $\angle BEF = \angle BED + \angle DEF = 90\deg+\alpha$.
Z sumy kątów w trójkącie $ACD$ obliczamy $\angle ACD = 90\deg-\alpha$, zatem suma miar kątów $\angle BEF$ i $\angle BCF$ równa jest $180\deg$, co~jest warunkiem wystarczającym do tego, by na czworokącie $BCFE$ dało się opisać okrąg. \end{minipage} \end{sol}
\item
\begin{sol} Taki zbiór może mieć maksymalnie $2011$ elementów.
\begin{enumerate} \item Zbiór $2011$-elementowy, mający zadane własności istnieje -- jest to zbiór wszystkich liczb nieparzystych z $\left\{ 1,2,\dots,2\cdot 2010+1 \right\}$: \[ A = \left\{ 1, 3, 5, 7, \dots, 2\cdot 2010 + 1 \right\} \] Suma dwóch liczb z $A$ jest liczbą parzystą, zatem nie należy do $A$. \item Załóżmy, że zbiór $A \subseteq \left\{ 1,2,\dots,2\cdot 2010+1 \right\}$ ma co najmniej $2012$ elementów.
Niech $a$ będzie najmniejszym elementem $A$. Rozważmy zbiór \[ A_{min} := \left\{ b - a\ |\ b\in A, b\neq a \right\} \subseteq \left\{ 1,2,\dots,2\cdot 2010 \right\}\]
Zbiór $A_{min}$ ma $|A| - 1$ elementów, więc $A$ i $A_{min}$ mają łącznie $2|A| - 1 \geq 2\cdot 2012 - 1 > 2\cdot 2010 + 1$. Zbiory te muszą więc mieć element wspólny: \[ \hbox{ istnieją } b,c\in A: \quad b - a = c \] Elementy $a,b,c$ zbioru $A$ spełniają równość $ a + c = b$, zatem zbiór $A$ nie spełnia warunków zadania. \end{enumerate} \end{sol}
\item
\begin{sol} Załóżmy, że $x, y$ spełniają warunki zadania oraz $x+y | x^{2k} + y^{2k}$ dla pewnego $k$ całkowitego dodatniego.
Zastosujmy kongruencje $\mod x+y$. Bezpośrednio widać, że $$x \equiv -y \mod x+y$$ Stąd $$x^{2k} \equiv y^{2k} \mod x+y, \quad x^{2k}+y^{2k} \equiv 2y^{2k} \mod x+y$$ Z założenia $x+y | x^{2k} + y^{2k}$, czyli $x+y | 2y^{2k}$.
Zauważmy, że $NWD(x+y, y^{2k}) = 1$.
Faktycznie, jeżeli liczba pierwsza $p$ dzieli $y^{2k}$, to $p|y$, a jeżeli oprócz tego $p | x+y$, to $p|x$, czyli $p$ jest wspólnym dzielnikiem $x$ i $y$, ale $NWD(x,y)=1$ -- $x,y$ nie mają wspólnych dzielników. Sprzeczność.
Skoro $x+y|2y^{2k}$ i $NWD(x+y, y^{2k}) = 1$, to $x+y|2$. Ale $x+y > 1 + 1 = 2$. Sprzeczność. \end{sol}
\item
\begin{sol}
\begin{minipage}[<+tb+>]{2.5cm} \includegraphics[height=4cm]{graph_trojkatyjocz} \end{minipage}\begin{minipage}{12.5cm}
Niech $D$ będzie punktem przecięcia dwusiecznej kąta $ABC$ i boku $AC$. Wtedy $\angle{CBD}=\angle{ABD}=\angle{BAC}$. Trójkąty $CBD$ i $CAB$ są więc podobne, skąd $\frac{CD}{BC}=\frac{BC}{AC}$.
Z twierdzenia o dwusiecznej uzyskujemy $\frac{AD}{AB}=\frac{CD}{BC}$. \[AC=AD+CD=CD\frac{AB}{BC}+CD=CD\left(1+\frac{AB}{BC}\right) =CD\left(\frac{AB+BC}{BC}\right)=\] \[\frac{CD}{BC}\left(AB+BC\right)=\frac{BC}{AC}\left(AB+BC\right)\] co jest równoważne tezie.
\end{minipage} \end{sol}
\begin{sol}[II rozwiązanie]
\begin{minipage}[<+tb+>]{5cm} \includegraphics{graph_trojkaty2jocz} \end{minipage}\begin{minipage}{10cm} Niech $D$ będzie takim punktem leżącym na półprostej $CB$, że $AB=BD$.
Dla prostoty oznaczmy $\alpha:=\angle CAB$, wtedy $\angle ABC = 2\alpha$.
Obliczamy $\angle BDA = \angle BAD= (180\deg-(180\deg-\angle ABC))/2=(2\alpha) /2= \alpha$. Niech $O$ będzie środkiem okręgu opisanego na $ABD$.
Zauważmy, że $\alpha = \angle ADB < 90\deg$, zatem ostry kąt $\angle AOB = 2\cdot \angle ADB = 2\alpha$.
Zachodzi $\angle OAB = \frac{1}{2}\left( 180\deg - \angle AOB \right) = 90\deg - \alpha$, więc $\angle OAC = \angle OAB+ \angle BAC= 90\deg - \alpha +\alpha=90\deg$, a więc okrąg opisany na trójkącie $ABD$ jest styczny do prostej $AC$.
Z twierdzenia o stycznej i siecznej dla okręgu opisanego na $\triangle ABD$ i punktu $C$ uzyskujemy zależność: $AC^2=BC\cdot CD=BC(BD+BC)=BC(AB+BC)$. \end{minipage} \end{sol}
\item
\begin{sol} Zapiszmy trójmian $n^2+3n+5$ w postaci $n^2+3n-28+33=(n+7)(n-4)+33$. Rozpatrzmy dwa przypadki: \begin{enumerate} \item $11|n+7$.
Wtedy również $11|n-4$, zatem $121|(n+7)(n-4)$, czyli $121\not|(n+7)(n-4)+33$. \item $11\not|n+7$.
Wtedy $11\not|n-4$ więc $11\not|(n+7)(n-4)$, $11\not|(n+7)(n-4)+33$ i tym bardziej
$121\not|(n+7)(n-4)+33$. \end{enumerate} \end{sol}
\item
\begin{sol}
\begin{lem} Jeżeli największy wspólny dzielnik liczb naturalnych $a$ i $b$ jest równy $1$ oraz $ab = k^n$ dla pewnych naturalnych $k,n$, to \[ a = x^n \hbox{ i } b = y^n \hbox{ dla pewnych }x,y\hbox{ naturalnych.} \] \end{lem}
\begin{proof}[Dowód lematu]
Rozważmy rozkłady na czynniki pierwsze: \[ k = p_1^{t_1}p^{t_2}_{2}\ldots p^{t_l}_{l}\quad a = p_1^{s_1}\ldots p_l^{s_l} \quad b = p_1^{r_1}\ldots p_l^{r_l} \] Skoro $k^n = ab$ to \[ n t_i = s_i + r_i \hbox{ dla każdego }i. \] Przy tym $NWD(a,b) = 1$, innymi słowy $a$ i $b$ nie mają wspólnych dzielników pierwszych, a więc \[ \hbox{ dla każdego }i \hbox{ albo } s_i = 0 \hbox{ albo } r_i = 0 \] Przy każdym $i$ są 2 możliwości: \[ s_i = n\cdot t_i,\ r_i = 0 \hbox{ albo } s_i = 0,\ r_i = n\cdot t_i \] We wszystkich przypadkach wszystkie liczby $s_1,\dots,s_l,r_1,\dots,r_l$ są podzielne przez $n$, zatem $a$ i $b$ są $n$-tymi potęgami liczb naturalnych. \end{proof}
Mamy pokazać, że równanie: $m(m+1)=k^n$ nie ma rozwiązań w liczbach całkowitych dodatnich $m, k$ dla $n>1$.
Zauważmy, że liczby $m$ i $m+1$ są względnie pierwsze. Jeżeli bowiem $d|m$ i $d|m+1$ to $d|m+1-m=1$, $d=1$. Z lematu wynika zatem, że istnieją $a, b$ całkowite takie, że \[m = a^n,\ m+1=b^n.\] Obliczam \[a^n + 1 = m+1 = b^n \quad 1 = b^n - a^n.\] Skoro tak, to $b \geq a+1 > 1$ i możliwe jest szacowanie \[ b^n - a^n \geq b^{n-1}(a+1) - a^n = b^{n-1} + a(b^{n-1} - a^{n-1}) > b^{n-1} \geq b > 1. \] Sprzeczność z $b^n - a^n = 1$. \end{sol}
\item
\begin{sol}
\begin{lem} W dowolnym trójkącie $ABC$ nierówność $AB\geq BC $ jest równoważna $ \angle ACB \geq \angle BAC$. \end{lem} \begin{proof}[Dowód lematu]
Załóżmy $AB \geq BC$.
Niech $D$ będzie takim punktem na boku $AB$, że $BD = BC$. Wtedy $\angle ACB \geq \angle DCB = \angle CDB = \angle DCA + \angle BAC \geq \angle BAC$.
Załóżmy teraz $\angle ACB \geq \angle BAC$.
Niech $D$ będzie takim punktem leżącym na $AB$, że $\angle DCA = \angle BAC$. Trójkąt $DCA$ jest równoramienny zatem $CD = DA$. Stosując nierówność trójkąta do punktów $B, D, C$ uzyskujemy \[BC \leq BD + DC = BD + DA = AB.\] \end{proof}
Aby uzasadnić dolne oszacowanie, przekształcamy równoważnie: \[60^{\circ}\leq \frac{\alpha a+\beta b+\gamma c}{a+b+c}\] \[\frac{\alpha+\beta+\gamma}{3}\leq \frac{\alpha a+\beta b+\gamma c}{a+b+c}\] \[(\alpha+\beta+\gamma)(a+b+c)\leq 3(\alpha a+\beta b+\gamma c)\] \[0\leq 3(\alpha a+\beta b+\gamma c)-(\alpha+\beta+\gamma)(a+b+c)\] \[0\leq a(3\alpha -(\alpha+\beta +\gamma))+b(3\beta-(\alpha+\beta +\gamma))+c(3\gamma- (\alpha+\beta +\gamma))\] \[0\leq a((\alpha -\beta) +(\alpha-\gamma))+b((\beta-\alpha)+(\beta -\gamma))+c((\gamma- \alpha)+(\gamma-\beta))\] \[0\leq (\gamma-\alpha)(c-a)+(\gamma -\beta)(c-b)+(\beta -\alpha)(b-a)\] Na mocy lematu mamy: $\gamma-\alpha \geq 0 \Leftrightarrow c-a\geq 0$, czyli oba czynniki są tego samego znaku, a więc ich iloczyn jest nieujemny. Analogicznie pokazujemy, że pozostałe składniki są nieujemne, a więc ich suma jest również nieujemna.
Teraz udowadniamy prawdziwość górnego oszacowania, przekształcając równoważnie: \[\frac{\alpha a+\beta b+\gamma c}{a+b+c}< 90^{\circ}\] \[\frac{\alpha a+\beta b+\gamma c}{a+b+c}<\frac{\alpha+\beta+\gamma}{2} \] \[2(\alpha a+\beta b+\gamma c)<(\alpha+\beta+\gamma)(a+b+c) \] \[0<\alpha(a+b+c-2a)+\beta(a+b+c-2b)+\gamma(a+b+c-2c) \] \[0<\alpha(b+c-a)+\beta(a+c-b)+\gamma(a+b-c) \] Z nierówności trójkąta mamy: $b+c>a$, co oznacza, że $\alpha(b+c-a)>0$. Analogicznie pokazujemy, że pozostałe składniki są dodatnie, co dowodzi dodatniości sumy. \end{sol}
\item
\begin{sol} Pokażemy, że strategię wygrywającą ma Yogi.
W pierwszym ruchu rysuje on jedną z najdłuższych przekątnych, dzieląc $2n$-kąt na dwa przystające $n+1$-kąty, w których dalej toczyć się będzie gra. Następnie gra on symetrycznie do Mateusza -- jeśli Mateusz narysuje jakąś przekątną w jednym z $n+1$-kątów, Yogi rysuje taką samą w drugim. Yogi zawsze może wykonać ruch, czyli nigdy nie przegrywa.
Gra zakończy się po skończonej liczbie ruchów, zatem w którymś momencie jeden z graczy przegra. Powyżej wykazaliśmy, że nie będzie to Yogi, zatem będzie to Mateusz. \end{sol}
\item
\begin{sol} Zauważmy, że dla każdej liczby dodatniej $x$ wyrażenie \[x^3 - x^2 - x + 1 = (x+1)(x-1)^2\] jest nieujemne.
Zatem \[(a^3 - a^2 - a +1) + (b^3 - b^2 - b +1) + (c^3 - c^2 - c + 1) \geq 0\] co jest równoważne tezie. \end{sol}
\end{enumerate}
\newsection{Trudniejsze}{T} \begin{enumerate}
\item
\begin{sol}
Pokażemy, że liczby $c=2a+3b$ i $d=3a-2b$ spełniają tezę zadania. Oczywiście są one całkowite, a ponadto: \[c^2+d^2=(2a+3b)^2+(3a-2b)^2=4a^2+12ab+9b^2+9a^2-12ab+4b^2=13(a^2+b^2)\] \end{sol}
\item
\begin{sol}
Zauważmy, że \[ \vec{MK} = \vec{MD} + \vec{DA} +\vec{AK} \hbox{ oraz } \vec{MK} = \vec{MC} + \vec{CB} + \vec{BK}. \] \[2\vec{MK}=\vec{MD}+\vec{DA}+\vec{AK}+\vec{MC}+\vec{CB}+\vec{BK}=(\vec{MD}+\vec{MC})+(\vec{AK}+\vec{BK})+\vec{DA}+\vec{CB}=\] \[\vec{0}+\vec{0}+\vec{DA}+\vec{CB}=\vec{DA}+\vec{CB}\] Skorzystamy z faktu, że $\left|\vec{u}+\vec{v}\right|\leq \left|\vec{u}\right|+\left|\vec{v}\right|$, który jest nierównością trójkąta zapisaną w języku wektorów: \[2\cdot MK = \left|2\vec{MK}\right|=\left|\vec{DA}+\vec{CB}\right|\leq\left|\vec{DA}\right|+\left|\vec{CB}\right| = DA + CB\] Analogicznie otrzymujemy nierówność: \[2\cdot NL = \left|2\vec{NL}\right|=\left|\vec{DC}+\vec{AB}\right|\leq\left|\vec{DC}\right|+\left|\vec{AB}\right| = DC + AB\] Po zsumowaniu stronami obu nierówności dostajemy tezę: \[2\left(MK + NL\right)\leq DA + BC + DC + AB\] \end{sol}
\begin{sol}[II rozwiązanie]
\emph{Przy odrobinie wysiłku i pewnej utracie naturalności można uniknąć języka wektorów i zastosować nierówność trójkąta w klasycznej postaci.}
\begin{lem} Niech $M$ będzie środkiem boku $BC$ trójkąta $ABC$. Wtedy \[2\cdot AM \leq AB + AC\] \end{lem}
\begin{proof}[Dowód lematu.]
Niech punkt $D$ będzie taki, że $ABCD$ jest równoległobokiem. Wtedy $AD = 2AM$ oraz $BD = AC$. Zatem nierówność \[2\cdot AM \leq AB + AC\] jest równoważna nierówności trójkąta: \[AD \leq AB + BD\] \end{proof}
\begin{minipage}[<+tb+>]{4.5cm} \includegraphics{graph_czworokatjocz} \end{minipage}\begin{minipage}{10.5cm}
Niech punkt $P$ będzie taki, że $MKPC$ jest równoległobokiem, a~punkt $R$ taki, że $P$ jest środkiem $BR$.
Jeżeli $P = B$, to $R = P = B$, czyli $KBCM$ jest równoległobokiem, w~szczególności $KM = BC$ i $MC || KB$, stąd $DM || AK$, ale również $DM = CM = BK = AK$, zatem $AKMD$ jest równoległobokiem, czyli $KM = AD$, a więc $2\cdot KM = AD + BC$.
Dalej zakładam, że $B\neq P$ a więc i $B\neq R$.
\end{minipage}
Oczywiście $\frac{BA}{BK} = \frac{BR}{BP} = 2$, więc $KP || AR$ i z twierdzenia Talesa \[\frac{AR}{KP} = \frac{BR}{BP} = 2,\ AR = 2\cdot KP = 2\cdot MC = CD\]
Zachodzą równoległości prostych: $AR || KP || MC || CD$, więc $AR || CD$. Ale również $AR = CD$, więc czworokąt $ARCD$ jest równoległobokiem, ergo $CR = AD$.
Stosujemy lemat do trójkąta $\triangle CBR$: \[2\cdot KM = 2\cdot CP \leq CB + CR = CB + AD.\]
Analogicznie $2\cdot NL \leq AB + CD$, razem $2\left( MK + NL\right)\leq DA + BC + DC + AB.$ \end{sol}
\item
\begin{sol}
Niech $a=x+1$ i $b=y+1$. Oczywiście $a,b$ są rzeczywiste dodatnie.
Założenie przyjmuje postać: $ab=2$, a teza: $(a-1)(b-1)+\frac{1}{(a-1)(b-1)}\geq 6$. Przekształcamy ją dalej równoważnie wykorzystując warunek $ab=2$. \[ab-(a+b)+1+\frac{1}{ab-(a+b)+1}\geq 6\] \[3-(a+b)+\frac{1}{3-(a+b)}\geq 6\] \[\frac{1}{3-(a+b)}\geq 3+(a+b)\] \[1\geq (3+(a+b))(3-(a+b))\] \[1\geq 9-(a+b)^2\] \[(a+b)^2\geq 8\] \[(a+b)^2\geq 4ab\] \[a^2+b^2\geq 2ab\] \[(a-b)^2\geq 0\] \end{sol}
\begin{sol}[Inne rozwiązanie]
Z nierówności pomiędzy średnią arytmetyczną a geometryczną wynika $x + y \geq 2\sqrt{xy}$, zatem \[ 2 = (1+x)(1+y) = 1 + x + y + xy \geq 1 + xy + 2\sqrt{xy} \] \[ 1 - xy \geq 2\sqrt{xy} \] Zachodzi $1 - xy \geq 2\sqrt{xy} > 0$ -- strony nierówności są dodatnie, więc zachowa ona prawdziwość po podniesieniu obu stron do kwadratu: \[ 1 - 2xy + (xy)^2 = (1 - xy)^2 \geq 4xy \] \[ 1 + (xy)^2 \geq 6xy \] \[ \frac{1}{xy} + xy \geq 6. \] \end{sol}
\item
\begin{sol} Niech liczby całkowite dodatnie $a_1 \leq a_2 \leq\dots \leq a_{13}$ będą długościami odcinków z zadania.
Oczywiście na to, żeby z odcinków $x, y, z$ dało się zbudować trójkąt, potrzeba i wystarcza $x < y+z,\ y<x+z,\ z<x+y$.
Jeżeli $0 < x \leq y \leq z$ to automatycznie $x+z > y$ i $y + z > x$, zatem wystarczy $x+y > z$.
Załóżmy, że nie da się zbudować trójkąta z żadnych trzech odcinków. Z odcinków $a_i,a_{i+1},a_{i+2}$ nie da się zbudować trójkąta, a więc $a_{i+2} \geq a_{i+1} + a_{i}$ dla każdego $i$.
Oszacowujemy z dołu kolejne wyrazy ciągu: \[\begin{array}{c} a_{1} \geq 1\\ a_2 \geq 1\\ a_3 \geq a_2 + a_1 \geq 2\\ a_4 \geq a_3 + a_2 \geq 3\\ a_5 \geq a_4 + a_3 \geq 5\\ a_6 \geq a_5 + a_4 \geq 8\\ \dots\\ a_{13} \geq a_{12} + a_{11} \geq 144 + 89 = 233 \end{array}\] Ale $a_{13} \leq 200$. Sprzeczność.
Jeżeli byłoby $12$ liczb to być może nie dałoby się zbudować trójkąta. Naturalny przykład pochodzący z poprzedniego rozwiązania to początkowe wyrazy tzw.\ ciągu Fibonacciego: \[\begin{array}[<+position+>]{|c||c|c|c|c|c|c|c|c|c|c|c|c|} \hline n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\\ \hline F_n & 1 & 1 & 2 & 3 & 5 & 8 &13 & 21& 34& 55 & 89& 143\\ \hline \end{array}\] Liczby są budowane następująco: \[F_1 = F_2 = 1 \quad F_{n+2} = F_{n+1} + F_n \hbox{ dla }n\geq 0\] Dla dowolnych $k > j > i$ zachodzi $F_k = F_{k-1} + F_{k-2} \geq F_j + F_i$, zatem nie da się zbudować trójkąta z odcinków o długościach $F_i, F_j, F_k$. \end{sol}
\end{enumerate}
\newchapter{Wykłady}{W} \renewcommand{\labelenumi}{\theenumi}
\begin{lecture}[Kombinatoryczne kolorowanki] \renewcommand{\labelenumi}{} \begin{enumerate} \item \begin{problem}{1}{delta} Czy planszę $8\times8$, z której usunięto dwa przeciwległe narożne pola, można pokryć kostkami domina $1\times2$? \end{problem} \item \begin{problem}{1}{delta} Czy planszę $10\times10$ można pokryć klockami: \begin{enumerate} \item w kształcie $T$ - 3 kwadraciki w rzędzie z jednym doklejonym pośrodku; \item w kształcie $L$ - 3 kwadraciki z jednym doklejonym obok; \item $1\times4$? \end{enumerate} \end{problem} \item \begin{problem}{1}{delta} Czy szachownicę $13\times13$ z wyciętym środkowym polem można pokryć klockami $1\times4$? \end{problem} \item \begin{problem}{1}{delta} Czy poziomą szachownicę $11\times10$ można pokryć poziomymi klockami $2\times1$ i pionowymi $1\times3$? \end{problem} \item \begin{problem}{1}{delta} Na szachownicy $8\times8$ ułożono $21$ klocków $3\times1$. Które pole zostało puste? \end{problem} \item \begin{problem}{1}{delta} Na szachownicy $11\times11$ ułożono $15$ klocków $2\times2$. Wykaż, że można zmieścić jeszcze jeden taki klocek. \end{problem} \end{enumerate} \end{lecture}
\begin{lecture}[Geometria] \renewcommand{\labelenumi}{} \begin{enumerate}
\item \begin{problem}{1}{Australia, 1996} Na bokach $AB$ i $AD$ czworokąta $ABCD$ wpisanego w okrąg obrano takie punkty $P$ i $Q$, że $AP=CD$ oraz $AQ=BC$. Odcinki $AC$ i $PQ$ przecinają się w punkcie $M$. Wykaż, że $PM=MQ$. \end{problem}
\item \begin{problem}{1}{Kanada, 1997} Wewnątrz równoległoboku $ABCD$ obrano w taki sposób punkt $O$, że $\angle AOB+\angle COD=180^{\circ}$. Udowodnij, że $\angle OBC=\angle ODC$. \end{problem}
\item \begin{problem}{1}{Hiszpania, 1991} Na zewnątrz trójkąta $ABC$ budujemy na jego bokach $AB$ i $AC$ kwadraty $ABPE$ i $ACRD$. Środkami odcinków $BC$ i $ED$ są odpowiednio punkty $M$ i $N$. Wykaż, że prosta $AM$ jest prostopadła do prostej $ED$, zaś $AN$ do $BC$. \end{problem}
\item \begin{problem}{1}{Wlk. Brytania, 1995} W czworokącie $ABCD$ wpisanym w okrąg bok $AB$ jest równy przekątnej $BD$. Punkt $M$ jest rzutem prostokątnym wierzchołka $B$ na przekątną $AC$. Udowodnij, że $AM=DC+CM$. \end{problem}
\item \begin{problem}{1}{Wlk. Brytania, 1996} Dany jest trójkąt ostrokątny $ABC$. Punkt $O$ jest środkiem okręgu opisanego na tym trójkącie. Okrąg opisany na trójkącie $AOB$ przecina proste $CA$ i $CB$ jeszcze w punktach odpowiednio $P$ i $Q$. Udowodnij, że proste $CO$ i $PQ$ są do siebie prostopadłe. \end{problem}
\item \begin{problem}{1}{Bułgaria, 1987} Dany jest trójkąt $ABC$. Punkt wewnętrzny $E$ środkowej $AD$ tego trójkąta rzutujemy prostokątnie na bok $BC$, otrzymując punkt $F$. Punkt wewnętrzny $M$ odcinka $EF$ rzutujemy prostokątnie na boki $AC$ i $AB$, otrzymując punkty odpowiednio $N$ i $P$. Udowodnij, że jeżeli punkty $N$,$E$ i $P$ leżą na jednej prostej, to $M$ należy do dwusiecznej kąta $BAC$. \end{problem}
\item \begin{problem}{1}{Australia, 1991} W trójkącie $ABC$ punkt $M$ jest środkiem boku $BC$, zaś $P$ i $R$ są dowolnymi punktami wewnętrznymi odpowiednio boków $AB$ i $AC$. Odcinki $AM$ i $PR$ przecinają się w punkcie $Q$. Udowodnij, że jeżeli $Q$ jest środkiem odcinka $PR$, to $PR$ jest równoległy do boku $BC$. \end{problem}
\item \begin{problem}{2}{Wlk. Brytania, 1983} W trójkącie $ABC$ boki $AB$ i $AC$ są równe. Punkt $D$ jest środkiem boku $AB$, $E$ - środkiem ciężkości trójkąta $ACD$, zaś $O$ jest środkiem okręgu opisanego na trójkącie ABC. Udowodnij, że proste $OE$ i $CD$ są prostopadłe. \end{problem}
\end{enumerate} \end{lecture}
\begin{lecture}[Wielomiany] \begin{defn} Wielomianem nazywamy funkcję $W$: $\mathbb{R} \longrightarrow \mathbb{R}$ daną wzorem: $W(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0$ dla pewnych liczb rzeczywistych $a_n,a_{n-1},\ldots,a_0$. Liczby te nazywamy współczynnikami wielomianu $W$, zaś $n$ jego stopniem. Liczbę $b$ taką, że $W(b)=0$ nazywamy pierwiastkiem wielomianu. \end{defn} \begin{obs} Wielomiany dzielimy z resztą, podobnie jak liczby całkowite.
Dla $a,b$ naturalnych ($b\neq 0$) istnieje dokładnie jedna para liczb całkowitych $q,r$ spełniająca warunki: \[a=qb+r\ \ i\ \ 0\leq r < b\]
Dla wielomianów $F,G$ ($G\neq 0$) istnieje dokładnie jedna para wielomianów $Q,R$ spełniająca warunki: \[F(x)=Q(x)G(x)+R(x) \ \ i \ \ 0\leq st\ R(x) < st\ G(x)\] Jeżeli $R(x)=0$ to mówimy, że wielomian $F$ jest podzielny przez $G$, a wielomian $G$ dzieli wielomian $F$ i piszemy: $G|F$.
\end{obs}
\begin{thm} Liczba rzeczywista $x_0$ jest pierwiastkiem wielomianu $F$ wtedy i tylko wtedy, gdy wielomian $F$ można przedstawić w postaci $(x-x_0)Q(x)$ dla pewnego wielomianu $Q$ (jeśli $x_0$ jest całkowite i $F$ ma współczynniki całkowite to $Q$ również ma współczynniki całkowite).(Twierdzenie B\`ezout) \end{thm} \begin{proof} Rozważmy dzielenie z resztą wielomianu $F$ przez dwumian $x-x_0$. \[F(x)=(x-x_0)Q(x)+R(x) \ \wedge \ st\ R(x)<st\ x-x_0 = 1 \] $st \ R(x)=0$, tym samym $R$ jest wielomianem stałym, czyli $R(x)=r$ dla pewnego $r$ całkowitego. \[F(x)=(x-x_0)Q(x)+r\] Bierzemy $x=x_0$: \[F(x_0)=r\] \[F(x)=(x-x_0)Q(x)+F(x_0)\] \[F(x_0)=0 \Leftrightarrow x-x_0|F(x)\] \end{proof}
\begin{problem}{1}{Staszic} Znajdź reszty z dzielenia wielomianu $(x^2- x - 1)^{2010}$ przez wielomiany: $x-1$ i $x^2-1$. \end{problem}
\begin{problem}{1}{Staszic} Niech $W$ będzie wielomianem o współczynnikach całkowitych takim, że istnieją 4 różne argumenty całkowite $x_1, x_2, x_3, x_4$ spełniające: \[W(x_1) = W(x_2) = W(x_3) = W(x_4) = 1\] Wykaż, że nie istnieje takie całkowite $x_5$, by $W(x_5) = -1$. \end{problem}
\begin{problem}{1}{Staszic} Pokaż, ze jeśli wielomian o współczynnikach całkowitych $W$ dla siedmiu różnych liczb całkowitych przyjmuje wartość $2010$, to nie ma pierwiastków całkowitych. \end{problem}
\begin{problem}{2}{Zwardoń} Wielomian $P$, stopnia co najwyżej $n > 2$, o współczynnikach rzeczywistych dla dowolnej liczby $k=0, 1,\ldots,n$ spełnia równość $P(k) = \frac{k}{k+1}$. Oblicz $P(n + 1)$. \end{problem}
\begin{thm} Jeśli $W$ ma wszystkie współczynniki całkowite, to dla dowolnych całkowitych, różnych liczb $a,b$ zachodzi $a-b|W(a)-W(b)$. \end{thm} \begin{proof} Z twierdzenia B\`ezouta wynika, że dla dowolnie wybranego całkowitego $b$ mamy: \[W(x)=(x-b)Q(x)+W(b)\] \[W(x)-W(b)=(x-b)Q(x)\] \[x-b|W(x)-W(b)\] W szczególności dla $x=a$ jest: \[a-b|W(a)-W(b)\] \end{proof}
\begin{problem}{1}{Staszic} Rozstrzygnij, czy istnieje wielomian o współczynnikach całkowitych taki, by: $W(7) = 11$ i $W(11) = 13$. \end{problem}
\begin{problem}{1}{Staszic} Dany jest wielomian o współczynnikach całkowitych $P(x)$, taki, że $3|P(7)$ oraz $7|P(3)$. Wykaż, że $21|P(10)$. \end{problem}
\begin{problem}{1}{matma.ilo.pl} Wykaż, że dla dowolnego wielomianu o współczynnikach całkowitych $W$ mającego pierwiastek całkowity $x_0$ można znaleźć takie $c$, że dla każdego $k$ jest $2^k|W(2^k-c)$. \end{problem}
\begin{problem}{1}{Staszic} Wielomian $W(x)$ o współczynnikach całkowitych spełnia warunki: $$17|W(15), 13|W(0), 9|W(11)$$ Pokaż, że $1989|W(1001)$. \end{problem}
\begin{problem}{1}{Staszic} Wielomian $Q$ o współczynnikach całkowitych dla $k$ kolejnych liczb całkowitych przyjmuje wartości podzielne przez $k$. Udowodnij, że dla dowolnego $x$ całkowitego $Q(x)$ jest podzielne przez $k$. \end{problem}
\end{lecture}
\begin{lecture}[Równania diofantyczne]
\begin{enumerate} \item Doprowadzanie do postaci iloczynowej.
\begin{problem}{1}{} Rozwiązać równania w liczbach naturalnych:
\begin{enumerate} \item $xy+3x-2y=36$ \item $x^2=y^2+2y+12$ \item $2x^2+5xy-12y^2=17$ \end{enumerate} \end{problem}
\begin{problem}{1}{} Rozwiązać równania w liczbach całkowitych:
\begin{enumerate} \item $(2x+y)(5x+3y)=7$ \item $xy=x+y+3$ \item $x^2=y^2+14$ \item $x^2+4x-y^2-2y=8$ \item $xy+9x-4y=51$ \item $x^2+x+41=y^2$
\item $x^2(y-1)+y^2(x-1)=1$
\end{enumerate} \end{problem}
\item Znajomość reszt z dzielenia.
\begin{problem}{1}{Blah} Rozwiązać równania w liczbach całkowitych:
\begin{enumerate} \item $x^2-7y=10$ \item $15x^2-7y^2=9$
\end{enumerate} \end{problem}
\item Liczby pierwsze.
\begin{problem}{1}{} Rozwiązać równania w liczbach pierwszych:
\begin{enumerate} \item $p^2-2q^2=1$ \item $pqr=5(p+q+r)$ \item $p+q+r=pq+1$
\end{enumerate} \end{problem}
\begin{problem}{1}{} Zbadać, czy istnieją trzy różne liczby pierwsze $p,q,r$, dla których $\frac{1}{p}+\frac{1}{q}+\frac{1}{r}$ jest liczbą naturalną. \end{problem} \begin{problem}{1}{} Znaleźć wszystkie liczby pierwsze $p,q$ oraz wszystkie liczby naturalne $n$, które spełniają równanie: $\frac{1}{p}+\frac{1}{q}+\frac{1}{pq}=\frac{1}{n}$. \end{problem}
\begin{problem}{1}{} Znaleźć pary $(x,y)$ liczb całkowitych, dla których $x^4+4y^4$ jest liczbą pierwszą. \end{problem}
\item Nieskończone schodzenie.
\begin{problem}{1}{} Wykazać, że jedynym rozwiązaniem $(x,y,z)$ równania w liczbach całkowitych jest rozwiązanie zerowe $(0,0,0)$:
\begin{enumerate} \item $x^2+y^2+z^2=2xyz$ \item $x^3=2y^3+4z^3$ \item $x^2+y^2=3z^2$
\end{enumerate} \end{problem}
\item Postać ilorazowa.
\begin{problem}{1}{} Rozwiązać równania w liczbach całkowitych: \begin{enumerate} \item $3x-5y=7$ \item $21x+48y=6$ \end{enumerate} \end{problem}
\begin{problem}{1}{} Wyznaczyć takie liczby całkowite $x$, aby liczba $\frac{7x+1}{3x+4}$ była całkowita. \end{problem}
\item Inne.
\begin{problem}{1}{} Rozwiązać równania w liczbach całkowitych:
\begin{enumerate} \item $x^2+y^2=x+y+2$ \item $3x^2+5y^2=345$ \item $(x^2+1)(y^2+1)=(x+y)^2+1$
\end{enumerate} \end{problem} \end{enumerate}
\end{lecture}
\begin{lecture}[Kryptografia] \begin{enumerate}
\item Najprostsze szyfry: \begin{enumerate} \item szyfr Cezara - każda litera tekstu jawnego zastępowana jest literą oddaloną od niej o stałą liczbę pozycji w alfabecie. Juliusz Cezar używał przesunięcia 3, najczęściej używane jest ROT13.
Przykłady:
MATEMATYKA $\longrightarrow$ PDWHPDWBND (przesunięcie o 3)
CEMRFHAVRPVR $\longrightarrow$ PRZESUNIĘCIE (ROT13)
\item szachownica Polibiusza - każdej literze przypisywana jest liczba dwucyfrowa zgodnie z poniższą tabelą. Cyfra dziesiątek to numer wiersza, a cyfra jedności - nr kolumny, w której znajduje się dana litera.
\begin{tabular}{cccccc} \ &1&2&3&4&5\\ 1&A&B&C&D&E\\ 2&F&G&H&I/J&K\\ 3&L&M&N&O&P\\ 4&Q&R&S&T&U\\ 5&V&W&X&Y&Z\\\\ \end{tabular}
Przykłady:
ZASZYFROWANY TEKST $\longrightarrow$ 55 11 43 55 54 21 42 34 52 11 33 54 44 15 25 43 44
52 24 11 14 34 32 34 43 13 $\longrightarrow$ WIADOMOŚĆ
\item AtBash - polega na zamianie litery leżącej na i-tej pozycji od początku alfabetu na literę leżącą na i-tej pozycji od końca.
Przykłady:
KRYPTOGRAFIA $\longrightarrow$ PIBKGLTIZURZ
LWHABUILDBDZMRV $\longrightarrow$ ODSZYFROWYWANIE
\item alfabet Morse'a - polega na zamianie poszczególnych liter na ciągi kropek i kresek według wzoru:
\begin{tabular}{ll} A $\cdot -$&N $-\cdot$\\ B $-\cdots$&O $---$\\ C $-\cdot-\cdot$&P $\cdot--\cdot$\\ D $-\cdot\cdot$&Q $--\cdot-$\\ E $\cdot$&R $\cdot-\cdot$\\ F $\cdot\cdot-\cdot$&S $\cdots$\\ G $--\cdot$&T $-$\\ H $\cdots\cdot$&U $\cdot\cdot-$\\ I $\cdot\cdot$&V $\cdots-$\\ J $\cdot---$&W $\cdot--$\\ K $-\cdot-$&X $-\cdot\cdot-$\\ L $\cdot-\cdot\cdot$&Y $-\cdot--$\\ M $--$&Z $--\cdot\cdot$\\\\ \end{tabular}
Przykłady:
Morse $\longrightarrow$ $--|---|\cdot-\cdot|\cdots|\cdot$
$--|---|\cdot-\cdot|--\cdot\cdot|\cdot||-\cdots|\cdot-|\cdot-\cdot\cdot|-|-\cdot--|-\cdot-\cdot|-\cdot-|\cdot\cdot|\cdot$ $\longrightarrow$ Morze Bałtyckie
\item szyfr cmentarny - litery zastępowane są odpowiadającymi im symbolami:
\includegraphics[scale=0.75]{sz.pdf}
\begin{minipage}{3.5cm} SZYFROGRAM $\longrightarrow$ \end{minipage}\begin{minipage}{7cm} \includegraphics[scale=0.5]{sz1.pdf} \end{minipage}
\begin{minipage}{6.5cm} \includegraphics[scale=0.5]{sz2.pdf} \end{minipage}\begin{minipage}{5cm} $\longrightarrow$ REMEMBER DEATH \end{minipage}
\item Playfair - do szyfrowania używamy klucza o niepowtarzających się literach. Tworzymy tabelkę $5\times5$, przy czym najpierw zapisujemy klucz, a następnie resztę alfabetu (litery I i J zapisujemy jako jedną). Tekst jawny dzielimy na bloki dwuliterowe (jeśli jest nieparzysta ilość liter, to na końcu dopisujemy $X$). Dla każdego bloku możliwe są 2 sytuacje: \begin{enumerate} \item litery leżą w tym samym wierszu lub kolumnie - zastępujemy je literami następnymi w~danym wierszu/kolumnie; \item litery leżą w różnych wierszach i kolumnach - literę pierwszą zastępujemy literą z wiersza I i kolumny II litery, natomiast drugą - literą z wiersza II i kolumny I.
\end{enumerate}
Przykłady:
Dla klucza SZYFR i następującej tabelki:
\begin{tabular}{ccccc}
S&Z&Y&F&R\\ A&B&C&D&E\\ G&H&I/J&K&L\\ M&N&O&P&Q\\ T&U&V&W&X\\\\ \end{tabular}
KO-NI-EC-WA-KA-CJ-IX $\longrightarrow$ IP-OH-AD-TD-GD-IO-LV
Dla klucza PIATEK i tabelki:
\begin{tabular}{ccccc} P&I/J&A&T&E\\ K&B&C&D&F\\ G&H&L&M&N\\ O&Q&R&S&U\\ V&W&X&Y&Z\\\\ \end{tabular}
UY-ZD-SU-TS-PE-SX-FX-MZ $\longrightarrow$ SZ-YF-RS-YM-ET-RY-CZ-NY
\item szyfr Vigen\`ere'a - potrzebujemy tu tablicy $26\times26$, w której każdy wiersz jest alfabetem przesuniętym odpowiednio o $0,1,2,...,25$, oraz klucza. Jego kolejne litery zapisujemy pod literami tekstu jawnego, w razie potrzeby powtarzając go wielokrotnie. Pierwsza litera z~każdej pary wyznacza wiersz, a druga kolumnę, na przecięciu których znajdujemy kolejną literę szyfrogramu.
Przykłady:
Dla klucza SERWY:
TEKST JAWNY $\longrightarrow$ LIBOR BENJW
Dla klucza KLUCZ:
GJDCSUZQQ SKUHC VSLXQLYDW $\longrightarrow$ WYJĄTKOWO TAJNA WIADOMOŚĆ
\item szyfr Ottendorfa (książkowy) - każda litera zapisana jest przez trzy liczby X-Y-Z, oznaczające odpowiednio numer strony w danej książce, numer wersu i nr litery w tym wersie.
Przykłady w jednostronnym tekście "`Romantyczności"' (wersy 66-69):
\emph{Martwe znasz prawdy, nieznane dla ludu,\\ Widzisz świat w proszku, w każdej gwiazd iskierce.\\ Nie znasz prawd żywych, nie obaczysz cudu!\\ Miej serce i patrzaj w serce!\\ }
TEKST $\longrightarrow$ np. 1-66-4, 1-68-3, 1-67-19, 1-68-7, 1-69-13
1-66-1, 1-67-30, 1-69-8, 1-67-22, 1-68-2, 1-66-20, 1-67-9, 1-69-10, 1-68-31, 1-69-15 $\longrightarrow$
MICKIEWICZ
\end{enumerate} \item RSA - asymetryczny algorytm szyfrujący opublikowany w 1977r. przez R. Rivesta, A. Shamira i L. Adlemana. Jego zasadniczą cechą są dwa klucze: publiczny do szyfrowania i prywatny do odczytywania danych.
Etapy tworzenia kluczy i szyfrowania danych: \begin{enumerate} \item wybieramy dwie duże liczby pierwsze $p$ i $q$
\emph{np. $p=5$, $q=11$} \item obliczamy liczbę $n=p\cdot q$ oraz wartość funkcji Eulera dla $n$: $\phi(n)=(p-1)(q-1)$
\emph{$n=55$, $\phi(n)=40$} \item znajdujemy liczbę nieparzystą $e$ taką, że $1<e<n$ oraz $NWD(e,\phi(n))=1$
\emph{$e=7$} \item wyznaczamy liczbę $d$ spełniającą: $d\cdot e\equiv1 \ mod \ \phi(n)$
\emph{$d=23$} \item klucz publiczny jest parą $(e,n)$, natomiast klucz prywatny - $(d,n)$
\emph{klucz publiczny: $(7,55)$, klucz prywatny: $(23,55)$} \item tekst do zaszyfrowania zamieniamy według wcześniej ustalonego systemu na liczby naturalne $t$ takie, że $0<t<n$
\emph{np. $t=15$} \item szyfrujemy liczby $t$ według wzoru: $c=t^e \ mod \ n$
\emph{$c=15^{\emph{7}}$ mod $55$ $\Rightarrow$ $c=5$} \item odszyfrowywanie przebiega analogicznie, z zastosowaniem klucza prywatnego: $t=c^d \ mod \ n$
\emph{$t=5^{\emph{23}}$ mod 55 $\Rightarrow$ $t=15$}
\end{enumerate}
\end{enumerate}
\begin{problem}{1}{własne}
Rozszyfrować poniższy tekst:
Khduv, khduv altb gh nvyhtp, gh shzhtp gfsh zvipl wplruh rzplgupjgrh. \end{problem} \begin{problem}{2}{własne}
UAYCCKA. PZAYXCWP XKV EU MYXXUPRTQ TU ZJLYJRF. XUXMJ: TUXHAMCN.
Podpowiedź: KDVOR. \end{problem}
\end{lecture}
\newchapter{Wskazówki do wykładów}{WW} \renewcommand{\labelenumi}{}
\newsection{Kombinatoryczne kolorowanki}{W1}
\begin{hint} Niech nasza plansza będzie szachownicą. Zauważmy, że usunięte zostały pola tego samego koloru. Jakie pola pokrywa każdy klocek i czemu nie da się tymi klockami pokryć szachownicy? \end{hint}
\begin{hint} \renewcommand{\labelenumi}{\theenumi} \begin{enumerate} \item[(a)] Znów weźmy pod uwagę szachownicę. Każdy klocek pokrywa $1$ lub $3$ pola czarne. Jaka musi być liczba klocków, żeby pokryć 50 czarnych pól? Dlaczego nie może być równa 25? \item[(b)] Pokolorujmy planszę w paski. Wtedy zadanie sprowadza się do poprzedniego przypadku. \item[(c)] Spróbujmy znaleźć takie kolorowanie, żeby każdy klocek pokrywał dokładnie 3 pola czarne. Istnieje takie, że liczba czarnych pól nie jest podzielna przez 3. \end{enumerate} \renewcommand{\labelenumi}{} \end{hint}
\begin{hint} Pokolorujmy planszę na 4 kolory tak, żeby każdy klocek zakrywał dokładnie jedno pole każdego koloru. Przy pewnym kolorowaniu pól jednego koloru może być więcej niż innego. \end{hint}
\begin{hint} Pokolorujmy planszę w pionowe paski zaczynając od czarnego. Można udowodnić, że ilość klocków $2\times1$ jest postaci $3k+1$. Każdy klocek poziomy zakrywa $1$ pole białe, a pionowy $0$ lub $3$. Zapiszmy zatem ilość białych pól ($50$) w zależności od ilości klocków poziomych i pionowych. Chcemy dojść do sytuacji, gdy liczba klocków nie jest całkowita. \end{hint}
\begin{hint} Kolory możemy zastąpić liczbami tak, żeby każdy klocek zakrywał tę samą sumę (na przykład 3). Jak mają się do siebie suma liczb na wszystkich polach i suma liczb na klockach? Prawdopodobnie trzeba będzie rozważyć kilka kolorowań. \end{hint}
\begin{hint} Na planszy można zaznaczyć $16$ takich kwadratów, że każdy klocek ma pola wspólne z dokładnie jednym z nich. Możliwe więc będzie położenie szesnastego klocka na ostatnim, niezakrytym kwadracie. \end{hint}
\newsection{Geometria}{W2}
\begin{hint} Niech $X$ będzie takim punktem półprostej $DA$, że $XA=AQ$. Korzystając z własności czworokąta wpisanego w okrąg i założeń zadania chcemy wykazać przystawanie trójkątów $XAP$ i $BCD$. Wykorzystując własności kątów wpisanych opartych na tym samym łuku wykazujemy równoległość prostych $PX$ oraz $AM$. Używamy twierdzenia Talesa do pokazania, że $QM=MP$. \end{hint}
\begin{hint} Niech $S$ będzie obrazem punktu $O$ w translacji o wektor $\vec{DA}$. Wykorzystując założenie zadania pokazujemy, że punkty $A,O,B,S$ leżą na jednym okręgu. Korzystając z faktu, że kąty wpisane $\angle SAB$ i $\angle SOB$ oparte na tym samym łuku mają równe miary oraz z równości kątów odpowiadających udowadniamy, że~$\angle OBC=\angle ODC$. \end{hint}
\begin{hint} Dobudujmy równoległobok $ADFE$. Korzystając z cechy bok-kąt-bok wykazujemy przystawanie trójkątów $DFA$ i $ABC$. W połączeniu z prostopadłościami: $DF\bot AB$ i $DA\bot AC$ pokazujemy równoważną tezie własność: $FA\bot BC$. Analogicznie udowadniamy, że $AM\bot ED$ lub piszemy, że idzie to analogicznie (;p). \end{hint}
\begin{hint} Niech $N$ będzie rzutem prostokątnym punktu $B$ na prostą $CD$. Wykazujemy, że $\angle BCM=\angle BCN$ w~celu pokazania przystawania trójkątów $BCM$ i $BCN$. Następnie udowadaniamy przystawanie trójkątów prostokątnych $BAM$ i $BDN$. \end{hint}
\begin{hint} Oznaczmy przez $M$ punkt przecięcia $CO$ i $PQ$, chcemy pokazać że $\angle CMQ =90^{\circ}$. Przeprowadzamy rachunki na kątach, wykorzystując następujące fakty: suma kątów przeciwległych w czworokącie wynosi $180^{\circ}$, kąt półpełny ma $180^{\circ}$, kąt środkowy jest dwa razy większy od kąta wpisanego opartego na tym samym łuku, trójkąt równoramienny ma równe kąty przy podstawie, suma kątów w trójkącie wynosi $180^{\circ}$. \end{hint}
\begin{hint} Poprowadźmy przez punkt $E$ prostą równoległą do $BC$. Jej punkty przecięcia z bokami $AB$ i $AC$ oznaczmy przez $X$ i $Y$. Zauważmy, że punkty $E,X,P,M$ oraz $M,Y,N,E$ leżą czwórkami na jednym okręgu. Z tego oraz z współliniowości punktów $P,E,N$ wywnioskujmy, że punkty $A,X,M,Y$ leżą na jednym okręgu. Korzystając z twierdzenia Talesa wykażmy, że $XE=EY$ i tym samym, że trójkąty $EMX$ i $EMY$ są przystające. Wywnioskujmy, że $\angle XAM=\angle MAY$. \end{hint}
\begin{hint} Załóżmy, że $Q$ jest środkiem $PR$ i $PR$ nie jest równoległe do $BC$. Poprowadźmy przez $Q$ prostą równoległą do $BC$, przecinającą boki $AB$ i $AC$ odpowiednio w punktach $X$ i $Y$. Wykorzystajmy twierdzenie Talesa do pokazania, że $XQ=QY$. Zauważmy, że trójkąty $PQX$ i $RQY$ są przystające, z czego wynika równość: $\angle PXQ=\angle RYQ$ stojąca w sprzeczności z nierównoległością odcinków $AB$ i $AC$. \end{hint}
\begin{hint} Niech $F$ będzie punktem przecięcia się prostych $DE$ i $AC$, $G$ - prostych $AO$ i $CD$, zaś $H$ - prostych $AO$ i $BC$. Na odcinku $BC$ obieramy taki punkt $I$, aby $HI=\frac{1}{3}HC$. Pokażmy, że $GH=\frac{1}{3}AH$, z czego wynika $GI || AC$. Następnie pokazujemy podobieństwo trójkątów prostokątnych (dlaczego prostokątnych?) $ADO$ i $GHI$. Układamy odpowiednią proporcję i wykorzystujemy związki $HI=\frac{1}{2}DE$ i $GH=\frac{1}{2}AG$, które wcześniej udowadniamy. Wykazujemy podobieństwa trójkątów $ADG$ i $DOE$. Dlaczego wystarcza ono do wykazania tezy? \end{hint}
\newsection{Wielomiany}{W3}
\begin{hint} Pamiętajmy, że reszta z dzielenia wielomianu $W(x)$ przez dwumian $x-x_0$ wynosi $W(x_0)$. Aby policzyć resztę z dzielenia wielomianu $W(x)$ przez wielomian $x^2-1$, najpierw policzmy reszty z dzielenia wielomianu $W(x)$ przez dwumiany $x-1$ i $x+1$, a następnie ułóżmy odpowiedni układ równań. \end{hint}
\begin{hint} Zastanówmy się, co możemy powiedzieć o pierwiastkach wielomianu $W(x)-1$. Pamiętajmy także, że $x_1,x_2,x_3,x_4, x_5$ są całkowite oraz o tym, że jeżeli $P(x)=(x-x_0)Q(x)$ i $P(x)$ ma współczynniki całkowite, to $Q(x)$ również ma współczynniki całkowite. \end{hint}
\begin{hint} Podobnie jak w poprzednim zadaniu pomyślmy, jakie pierwiastki ma wielomian $W(x)-2010$. Oczywiście nie możemy zapomnieć, że jeśli $x_0$ jest pierwiastkiem $W(x)$ to $W(x_0)=0$. \end{hint}
\begin{hint} Rozważmy wielomian $W(x)=(x+1)P(x)-x$. Zauważmy, że jego pierwiastkami są liczby $0,1,\ldots, n$. Skorzystaj z Twierdzenie B\`ezouta. Pamiętajmy, że aby wielomiany były równe, muszą mieć równe stopnie. Policzenie $W(-1)$ pozwala nam ustalić współczynnik przy najwyższej potędze $x$ wielomianu $W(x)$. \end{hint}
\begin{hint} Zastosujmy wprost Twierdzenie dla liczb $a=11$ i $b=7$, a następnie skorzystajmy z równości danych w zadaniu. \end{hint}
\begin{hint} Warto w taki sposób dobrać $a,b$ w Twierdzeniu, aby po prawej stronie wystąpiło wyrażenie $P(10)$ z~innym znanym nam wyrażeniem. Należy również pamiętać o dwóch fakcikach: jeżeli dzielnik dzieli dwie liczby to dzieli również ich różnicę; jeżeli dwie względnie pierwsze liczby dzielą daną liczbę, to ich iloczyn również ją dzieli. \end{hint}
\begin{hint} W Twierdzeniu połóżmy $a=2^k-c$. Dobierzmy odpowiednie $b$ i zastanówmy się, czym musi być $x$, żeby było $2^k|W(x)$ dla każdego $k$. \end{hint}
\begin{hint} Zauważmy, że $1989=9\cdot 13\cdot 17$ oraz że: $17|1001-15$, $13|1001-0$, $9|1001-11$. \end{hint}
\begin{hint} Jeżeli mamy zbiór $\mathbb{A}$ złożony z $k$ kolejnych liczb całkowitych, to każdą liczbę całkowitą $z$ możemy przedstawić w postaci $z=sk+\alpha $, gdzie $s \in \mathbb{Z}$ i $\alpha \in \mathbb{A}$. W Twierdzeniu połóżmy $a=z$ i $b = \alpha$. \end{hint}
\newsection{Równania diofantyczne}{W4}
\begin{hint} Znajdź dla jakiego $x$ uzależnionego od $y$ lewa strona się zeruje. Oznacza to, że musi być ona podzielna przez pewien dwumian. \end{hint}
\begin{hint} Przemnóż obie strony przez stałą, aby po zwinięciu otrzymać kwadrat całkowitego wyrażenia.
Wykorzystaj skończoność liczby możliwości rozkładu liczby $a$ na $2$ czynniki. \end{hint}
\begin{hint}
Kwadrat liczby całkowitej przy dzieleniu przez 7 może dawać jedynie resztę $0,1,2$ lub $4$.
Wykorzystaj fakty: \begin{itemize} \item jeśli liczba pierwsza $p$ dzieli $a^2$, to $p$ dzieli $a$; \item jeśli liczba $a$ dzieli iloczyn $bc$ oraz liczby $a$ i $b$ są względnie pierwsze, to $a$ dzieli $c$; \item kwadrat liczby całkowitej przy dzieleniu przez 3 może dawać jedynie resztę $0$ lub $1$. \end{itemize}
\end{hint}
\begin{hint}
Jeżeli $s$ jest pierwsze i parzyste, to $s=2$.
Zauważ, że w tym równaniu liczby $p,q,r$ pełnią tę samą rolę, bo możemy zamienić miejscami dowolne dwie z nich i sens równania się nie zmieni. W takich przypadkach, wiedząc, że jedna z~liczb $p,q,r$ ma pewną własność, możemy przyjąć, że konkretnie któraś z nich ma tę własność (Jeżeli wiemy, że jedna z~liczb dzieli się przez $5$, to możemy przyjąć, że to $p$ dzieli się przez $5$). Przy tej metodzie należy jedynie pamiętać, aby w końcowym rozwiązaniu uwzględnić wszystkie permutacje wyniku, który otrzymamy.
Skorzystaj z faktu, że jeżeli liczba pierwsza $p$ jest iloczynem dwóch liczb naturalnych, to są to czynniki $1$ i $p$. \end{hint}
\begin{hint} Ułóż i przekształć równanie, aby otrzymać je w języku liczb całkowitych. \end{hint}
\begin{hint} Wyznacz $n$. Pamiętaj o szczególnych własnościach liczb pierwszych. Rozważ cztery przypadki. \end{hint}
\begin{hint} Przekształć na różnicę dwóch kwadratów. \end{hint}
\begin{hint} Wykorzystaj następujący fakt:
Jeżeli liczba całkowita $b$ jest podzielna przez $a^n$, gdzie $a\neq1$, dla dowolnego $n\in \mathbb{N}$, to $b=0$. \end{hint}
\begin{hint} Wyznacz z równania $x$, następnie zastanów się, jakiej postaci musi być $y$, aby wyrażenie przedstawiające $x$ było całkowite. \end{hint}
\begin{hint} Spróbuj wyodrębnić część całkowitą danej liczby (całkowitą dla każdego $x$), doprowadzając do zmniejszenia licznika liczby, której całkowitość mamy określić. Skorzystaj z faktu, który mówi, że aby liczba wymierna $\frac{a}{b}$ była całkowita, to musi zachodzić $a \geq b$. \end{hint}
\begin{hint} Iloczyn dwóch kolejnych liczb całkowitych jest dodatni i parzysty.
Uprość równanie, a następnie zauważ, że tylko dla skończonej ilości liczb lewa strona równania nie przekracza prawej.
Zauważ, że jeżeli $abc=0$, to $a=0$ lub $b=0$ lub $c=0$. \end{hint}
\newsection{Kryptografia}{W5}
\begin{hint} Używając szyfru Cezara z przesunięciem o 7, otrzymamy zdanie: Dawno, dawno temu za~górami, za~lasami żyła sobie piękna księżniczka. \end{hint}
\begin{hint} Szyfr Cezara z przesunięciem 3:
KDVOR$\longleftarrow$HASLO
Szyfr Vigen\`ere'a z kluczem HASLO:
UAYCCKA. PZAYXCWP XKV EU MYXXUPRTQ TU ZJLYJRF. XUXMJ: TUXHAMCN.$\longleftarrow$NAGRODA. XOMRXKLB QKD TG FYFMGIRBF FN ZRAKCRN. MGQMR: IGQHIBOG.
Playfair z kluczem NAGRODA:
XOMRXKLB QKD TG FYFMGIRBF FN ZRAKCRN. MGQMR: IGQHIBOG.$\longleftarrow$ZGŁOŚCIE SIĘ PO CZEKOLADĘ DO YOGIEGO. HASŁO: KAPIBARA. \end{hint}
\newpart{Grupa olimpijska}{OL}
\newchapter{Zadania}{1} \renewcommand{\labelenumi}{}
\newsection{Dzień I}{1}
\begin{enumerate}
\item
\begin{problem}{2}{warsztaty WWW 5} Udowodnij, że układ równań: \[ \left\{ \begin{array}{l} a^2+b^2+c^2=2011\\ 3a+8b+44c=2010 \end{array}\right.\] nie ma rozwiązań w liczbach rzeczywistych. \end{problem}
\item
\begin{problem}{2}{Jocz} Dla jakich $n$ naturalnych zachodzi podzielność $5|(2^n+n^3)$? \end{problem}
\item
\begin{problem}{2}{Yogi} Punkt $P$ leży na zewnątrz okręgu o środku $O$; $Q, R$ są punktami styczności stycznych do okręgu przechodzących przez $P$, a $K$ jest punktem przecięcia prostych $PO$ i $QR$.
Prosta $k$, niebędąca średnicą, przechodzi przez $P$ i przecina okrąg w punktach $A$ i $B$. Uzasadnij, że punkty $A, B, O, K$ leżą na jednym okręgu. \end{problem}
\end{enumerate} \newsection{Dzień II}{2} \begin{enumerate}
\item
\begin{problem}{2-3}{mathlinks} Udowodnij, że dla żadnej liczby naturalnej $n>0$ liczba $2^{n-1}(2^{n+1} - 1)$ nie jest sześcianem liczby całkowitej. \end{problem}
\item
\begin{problem}{2}{Yogi} Dowiedź, że rozwiązań układu równań $$\left\{ \begin{array}[c]{c} a + b + c = 3\\ a^2 + b^2 + c^2 = 2(ab + bc + ca) \end{array}\right.$$ jest nieskończenie wiele oraz każda trójka $(a,b,c)$ spełniająca ten układ równań jest nieujemna tj. $a,b,c\geq 0$.
\emph{Wskazówka: Trójka $\left( \frac{3}{2}, \frac{3}{2}, 0 \right)$ spełnia ten układ (sprawdź!).} \end{problem}
\item
\begin{problem}{2}{mathlinks} Dana jest liczba całkowita $n \geq 2$. Zbiór $X$ ma $n$ elementów, a $A_1, A_2, \dots, A_{101}$ są takimi podzbiorami $X$, że suma dowolnych $50$ z nich ma więcej niż $\displaystyle{\frac{50}{51}n}$ elementów.
Udowodnij, że wśród tych podzbiorów istnieją trzy, z których każde dwa mają niepustą część wspólną. \end{problem}
\end{enumerate} \newsection{Dzień III}{3} \begin{enumerate}
\item
\begin{problem}{1}{kółko II LO w Gorzowie Wlkp.} Liczby $a,b,k$ są całkowite, przy czym $k\neq 0$. Wiadomo, że rozwiązaniami równania \[kx^2+ax-bk+k^3=0\] są niezerowe liczby całkowite. Udowodnij, że liczba $a^2+b^2$ jest złożona. \end{problem}
\item
\begin{problem}{2}{Yogi} Udowodnij, że na płaszczyźnie ze standardowym układem współrzędnych nie istnieje trapez o obu kątach przy jednej z podstaw równych $60\deg$, którego wszystkie wierzchołki mają współrzędne całkowite. \end{problem}
\item
\begin{problem}{2}{znane?} Dana jest nieskończona szachownica. Ireneusz i Iwona wykonują ruchy naprzemiennie stawiając pionki na polach. Udowodnij, że Iwona może powstrzymać Ireneusza od ustawienia w~rzędzie lub kolumnie pięciu jego pionków sąsiadujących ze sobą. \end{problem}
\end{enumerate} \newsection{Mecz matematyczny}{M} \begin{enumerate}
\item
\begin{problem}{2}{kółko V LO w Krakowie} Liczby rzeczywiste dodatnie $a,b,c,d,e$ spełniają $a^{2010}+b^{2010}+c^{2010}+d^{2010}+e^{2010}=2010$. Jaka jest największa możliwa wartość wyrażenia \[a^{400}b^{401}c^{402}d^{403}e^{404}?\] \end{problem}
\item
\begin{problem}{2}{Jocz} Wielomian $W(x)$ o współczynnikach całkowitych spełnia warunek: \[W(k)W(2k)\ldots W(nk)=\frac{k+2k+ \ldots +nk}{n}\] dla ustalonych względnie pierwszych liczb całkowitych $n, k$, $n>1$.
Udowodnij, że $W(x)$ nie ma pierwiastków całkowitych. \end{problem}
\item
\begin{problem}{2}{Jocz} W prostokącie o wymiarach $5$ na $3k$ ($k \in \mathbb{N}$) umieszczono $2k+2$ punktów.
Pokaż, że pewne dwa punkty są oddalone od siebie o nie więcej niż $\sqrt{13}$. \end{problem}
\item
\begin{problem}{1}{koło II LO w Gorzowie Wielkopolskim} Trzy odcinki o długości $1$ przecinają się w jednym punkcie. Końce tych odcinków są wierzchołkami sześciokąta. Rozstrzygnij, czy \begin{enumerate} \item jego obwód może być większy od $6$, \item jego obwód może być większy od $5.999999999$. \end{enumerate} \end{problem}
\item
\begin{problem}{2}{MIMUW} Wielokąt wypukły $A$ leży we wnętrzu wielokąta $B$. Udowodnij, że obwód $A$ jest nie większy niż obwód $B$. \end{problem}
\item
\begin{problem}{3}{mathlinks} Trójkąt $ABC$ jest ostrokątny, a $AD, BE, CF$ są jego wysokościami.
Punkty $X,Y,Z$ leżą na bokach $AB, BC, CA$ odpowiednio. Udowodnij, że $$XY + YZ + ZX \geq FD + DE + EF$$ \end{problem}
\item
\begin{problem}{1/3 - w zależności, czy ktoś wie jak robić}{Olala, inspiracja bodajże z Kourliandtchika} Rozwiąż w liczbach rzeczywistych układ równań: $$\left\{ \begin{array}{c c c} x+y+z=4\\ x^2+y^2+z^2=78\\ x^3+y^3+z^3=226\\ \end{array} \right.$$ \end{problem}
\item
\begin{problem}{2}{V LO w Krakowie} Udowodnij, że w dowolnym trójkącie $R\geq 2r$, gdzie $R,r$ - promienie okręgów opisanego i wpisanego. \end{problem}
\item
\begin{problem}{2-3,śr.--zaaw.\ kęsim!}{Soviet Math Competitions} Danych jest $2n+1$ różnych liczb całkowitych o wartościach bezwzględnych nie większych niż $2n-1$. Udowodnij, że można spośród nich wybrać $3$ liczby, których suma wynosi $0$. \end{problem}
\item
\begin{problem}{1--2}{Kieza, delta} W czworościanie $ABCS$ wszystkie kąty płaskie przy wierzchołku $S$ są proste, a ponadto $SA = SB + SC$. Wykaż, że suma kątów płaskich przy wierzchołku $A$ jest równa $90\deg$. \end{problem}
\end{enumerate} \newsection{Trudniejsze}{T} \begin{enumerate}
\item
\begin{problem}{3}{Yogi} Wielomian $W$ o współczynnikach całkowitych nazwiemy \emph{podzielnym przez liczbę naturalną} $n$, jeżeli wszystkie jego współczynniki są podzielne przez $n$, innymi słowy, gdy $W = n\cdot V$, gdzie wielomian $V$ ma współczynniki całkowite.
Liczba $p$ jest pierwsza, a niezerowy wielomian $P$ o współczynnikach całkowitych jest stopnia mniejszego niż $p$. Udowodnij, że jeśli dla każdej liczby całkowitej wartość $P$ jest podzielna przez $p$, to $P$ jest podzielny przez $p$ w sensie powyższej definicji. \end{problem}
\item
\begin{problem}{3}{Zwardoń} Niech $O$ i $I$ oznaczają odpowiednio środek okręgu opisanego i wpisanego w nierównoramienny trójkąt $ABC$. Udowodnij, że $\angle AIO \leq 90^{\circ}$ wtedy i tylko wtedy, gdy $2BC \leq AB+AC$. \end{problem}
\item
\begin{problem}{3}{znane} Rozstrzygnij, czy istnieje taka funkcja $f:\mathbb{Z}_+\rightarrow\mathbb{Z}_+$, że dla dowolnego $x\in\mathbb{Z}_+$ zachodzi $f(f(x))=5x$. \end{problem}
\item
\begin{problem}{2}{stary OM, zmodyfikowany} Dane są trzy nieskończone ciągi różnych liczb całkowitych dodatnich $(a_n), (b_n), (c_n)$. Udowodnij, że istnieje nieskończony rosnący ciąg $(i_s)$ liczb naturalnych: $i_1 < i_2 < i_3 < \ldots < i_k < \ldots$ taki, że \[a_{i_1} < a_{i_2} < \ldots < a_{i_k} < \ldots\] \[b_{i_1} < b_{i_2} < \ldots < b_{i_k} < \ldots\] \[c_{i_1} < c_{i_2} < \ldots < c_{i_k} < \ldots\] \end{problem}
\end{enumerate}
\newchapter{Rozwiązania}{ROL}
\newsection{Dzień I}{1} \begin{enumerate}
\item
\begin{sol} Załóżmy, że istnieje rozwiązanie $(a,b,c)$ danego układu.
Zastosujmy \begin{thm}[Nierówność Schwarza] Jeżeli $n$ jest liczbą całkowitą, a $u_1,u_2,\dots,u_n,t_1,t_2,\dots,t_n$ są liczbami rzeczywistymi, to $$(u_1^2 + \dots + u_n^2)(t_1^2 + \dots + t_n^2) \geq (u_1t_1 + \dots + u_nt_n)^2$$ \end{thm} \begin{proof}[Dowód nierówności] Oczywiście dla dowolnej liczby rzeczywistej $x$ zachodzi $(u_ix - t_i)^2 \geq 0$ dla $i=1,2,\dots,n$.
Zatem $$(u_1^2 + \dots + u_n^2)x^2 - 2(u_1t_1 + \dots + u_nt_n)x + (t_1^2 + \dots + t_n^2) = (u_1x - t_1)^2 + (u_2x - t_2)^2 + \dots + (u_nx - t_n)^2 \geq 0$$
Lewa strona nierówności to funkcja kwadratowa ze względu na $x$. Funkcja ta jest stale nieujemna, zatem musi ona mieć niedodatni wyróżnik (deltę): $$\Delta = 4(u_1t_1 + \dots + u_nt_n)^2 - 4(u_1^2 + \dots +u_n^2)(t_1^2 + \dots + t_n^2) \leq 0$$ co dowodzi nierówności z tezy. \end{proof}
Biorąc $(u_1, u_2, u_3) := (a, b, c), (t_1, t_2, t_3) := (3, 8, 44)$ uzyskujemy $$(a^2 + b^2 + c^2)(3^2 + 8^2 + 44^2)\geq (3a + 8b + 44c)^2.$$ Podstawiając wartości liczbowe otrzymujemy $$2011 \cdot 2009\geq 2010^2,$$ ale $2011\cdot 2009 = 2010^2 - 1 < 2010^2$. Sprzeczność. \end{sol}
\begin{sol}[Inny dowód] Jak w poprzednim rozwiązaniu załóżmy, że liczby $a,b,c$ spełniają dany układ równań.
Zauważmy, że $$(a^2 + b^2 + c^2) - 2(3a + 8b + 44c) + 3^2 + 8^2 + 44^2 = (a - 3)^2 + (b - 8)^2 + (c - 44)^2$$ Podstawiając warunki z zadania obliczamy: $$(a^2 + b^2 + c^2) - 2(3a + 8b + 44c) + 3^2 + 8^2 + 44^2 = 2011 - 2\cdot 2010 + 2009 = 0$$ Zatem $(a - 3)^2 + (b - 8)^2 + (c - 44)^2 = 0$, czyli $a=3, b=8, c=44$.
Jeżeli tak, to $2011 = a^2 + b^2 + c^2 = 3^2 + 8^2 + 44^2 = 2009$. Sprzeczność. \end{sol}
\item
\begin{sol}
Zauważmy że: \[n \equiv 0 \mod 4 \Rightarrow n=4k \Rightarrow 2^n \equiv 2^{4k}\equiv (2^4)^k \equiv 1^k \equiv 1 \mod 5\] \[n \equiv 1 \mod 4 \Rightarrow n=4k+1 \Rightarrow 2^n \equiv 2^{4k+1}\equiv 2^{4k} \cdot 2 \equiv 1\cdot 2 \equiv 2 \mod 5\] \[n \equiv 2 \mod 4 \Rightarrow n=4k+2 \Rightarrow 2^n \equiv 2^{4k+2}\equiv 2^{4k} \cdot 2^2 \equiv 1\cdot 4 \equiv 4 \mod 5\] \[n \equiv 3 \mod 4 \Rightarrow n=4k+3 \Rightarrow 2^n \equiv 2^{4k+3}\equiv 2^{4k} \cdot 2^3 \equiv 1\cdot 8 \equiv 8 \equiv 3 \mod 5\] Zatem prawdziwa jest tabelka: $$ \begin{array}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline n \mod 20& 0 & 1&2&3&4&5 & 6&7&8&9&10 & 11&12&13&14&15 & 16&17&18&19\\ \hline n \mod 4&0&1&2&3&0&1&2&3&0&1&2&3&0&1&2&3&0&1&2&3\\ \hline 2^n \mod 5&1&2&4&3&1&2&4&3&1&2&4&3&1&2&4&3&1&2&4&3\\
\hline n \mod 5 & 0& 1&2&3&4&0 & 1&2&3&4&0 & 1&2&3&4&0 & 1&2&3&4\\ \hline n^3 \mod 5& 0&1&3&2&4& 0&1&3&2&4& 0&1&3&2&4& 0&1&3&2&4\\
\hline 2^n+n^3 \mod 5& 1&3&2&0&0& 2&0&1&3&1& 4&4&4&4&3& 3&2&0&1&2\\
\hline \end{array}$$ z której wynika, że wyrażenie $2^n+n^3$ jest podzielne przez 5 wtedy i tylko wtedy, gdy $n$ jest postaci $20k+r$, gdzie $k$ jest całkowite nieujemne, a $r\in \left\{ 3,4,6,17 \right\}$.
\end{sol}
\item
\begin{sol}
\begin{minipage}{6.5cm} \includegraphics{polarline} \end{minipage}\begin{minipage}{9.5cm} Proste $AB$ i $KO$ przecinają się w $P$, więc wystarczy wykazać, że \[ PA \cdot PB = PK \cdot PO. \]
Z twierdzenia o siecznych wynika, że $$PA \cdot PB = PQ^2$$
Trójkąty $PKQ$ i $PQO$ są prostokątne i mają kąt miary $\angle KPQ = \angle OPQ$, więc są podobne: \[ \triangle PKQ \simeq \triangle PQO \]
\end{minipage}
\[ \hbox{ Stąd }\frac{PK}{PQ} = \frac{PQ}{PO} \hbox{ czyli } PK \cdot PO = PQ^2 = PA \cdot PB. \] \end{sol}
\end{enumerate}
\newsection{Dzień II}{2} \begin{enumerate}
\item
\begin{sol} Załóżmy, że taka liczba istnieje: $n$ jest takie, że $$2^{n-1}(2^{n+1} - 1) = k^3$$ Liczby $2^{n-1}, 2^{n+1} - 1$ są względnie pierwsze, a ich iloczyn jest sześcianem liczby całkowitej. Patrząc na rozkład na czynniki pierwsze stwierdzamy, że każda z nich jest sześcianem liczby całkowitej.
Liczba $2^{n-1}$ jest sześcianem liczby całkowitej wtedy i tylko wtedy, gdy $3|n-1$. Zatem $n = 3k + 1$.
$$2^{n+1} - 1 = 2^{3k+2} - 1 = 8^k\cdot 4 - 1 \equiv 4 - 1 = 3 \mod 7$$ jeżeli więc wykażemy, że sześcian liczby całkowitej nie może dać reszty $3$ z dzielenia przez $7$, to dojdziemy do sprzeczności.
Udowadniamy to przez bezpośrednie przeliczenie wszystkich możliwych reszt: $$\begin{array}{|c||c|c|c|c|c|c|c|} \hline n \mod 7 & 0 & 1 & 2 & 3 & 4 & 5 & 6\\ \hline n^3 \mod 7 & 0 & 1 & 1 & 6 & 1 & 6 & 6\\ \hline \end{array}$$ \end{sol}
\item
\begin{sol} Układ przekształcamy równoważnie przez dodanie do obu stron drugiego równania $a^2 + b^2 +c^2$: $$\left\{ \begin{array}[c]{c} a + b + c = 3\\ 2(a^2 + b^2 + c^2) = (a+b+c)^2 \end{array}\right.$$ oraz podstawienie pierwszego równania do prawej strony drugiego i podzielenie przez $2$: $$\left\{ \begin{array}[c]{c} a + b + c = 3\\ a^2 + b^2 + c^2 = \frac{9}{2} \end{array}\right.$$
Popatrzmy na ten układ równań geometrycznie. Równanie $a^2 + b^2 + c^2 = 9/2$ opisuje pewną sferę o środku w $(0,0,0)$, a równanie $a+b+c=3$ pewną płaszczyznę. Można policzyć rozwiązania tego układu stosując narzędzia geometrii analitycznej, my jednak pójdziemy trochę inną drogą.
Zauważmy, że trójka $C = \left( \frac{3}{2}, \frac{3}{2}, 0 \right)$, a więc i trójki $B = \left( \frac{3}{2}, 0, \frac{3}{2}\right)$ oraz $A = \left(0, \frac{3}{2}, \frac{3}{2}\right)$ spełniają ten układ. Płaszczyzna i sfera mają więc co najmniej trzy punkty przecięcia. Część wspólna płaszczyzny i sfery może być $\emptyset$, punktem lub okręgiem. W tym przypadku jest więc ona okręgiem $o$ opisanym na trójkącie $ABC$, czyli układ ma nieskończenie wiele rozwiązań.
Pozostaje pokazać, że ten okrąg $o$ nie zawiera punktów o ujemnych współrzędnych, czyli leży w~zbiorze $\{a\geq 0, b\geq 0, c\geq 0\}$.
Aby to udowodnić, wystarczy dowieść, że okrąg $o$ nie ma punktów wspólnych z płaszczyzną $c=0$ innych niż $C = \left( \frac{3}{2}, \frac{3}{2}, 0 \right)$, z płaszczyzną $a=0$ innych niż $A$, a z płaszczyzną $b=0$ innych niż $B$.
Załóżmy, że trójka $(a,b,0)$ jest punktem okręgu $o$, czyli spełnia równania układu. Wtedy $a+b=3$ oraz $a^2 + b^2 = \frac{9}{2}$, zatem $(a-b)^2 = 2(a^2 + b^2) - (a+b)^2 = 9 - 9 = 0$, czyli $a=b=3/2$, zatem $(a,b,0) = C$. Pozostałych własności dowodzę analogicznie. \end{sol}
\item
\begin{sol} Rozważmy $A_1,\dots,A_{50}$. Suma tych zbiorów ma więcej niż $\frac{50}{51}n$ elementów, więc wśród nich istnieje taki, który ma więcej niż $\frac{n}{51}$ elementów. Dla uproszczenia oznaczeń załóżmy, że $A_1$ ma więcej niż $\frac{n}{51}$ elementów.
Zauważmy, że $A_1$ ma puste przecięcia z najwyżej $49$ zbiorami spośród $A_2,\dots,A_{101}$. Faktycznie, gdyby $A_1$ miało puste przecięcia z pewnymi $50$ zbiorami, to miałoby puste przecięcie i z ich sumą. Ale suma tych zbiorów łączne z $A_1$ ma więcej niż $\frac{50}{51}n + \frac{1}{51}n = n$ elementów, zatem więcej niż $X$. Sprzeczność.
Zatem $A_1$ ma niepuste przecięcie z co najmniej $51$ zbiorami, niech dla uproszczenia oznaczeń będą to zbiory $A_2,\dots,A_{52}$.
Teraz powtarzamy powyższe rozumowanie.
Wśród $50$ zbiorów $A_2,\dots,A_{51}$ istnieje zbiór mający więcej niż $\frac{n}{51}$ elementów, niech będzie to $A_2$.
Rozumując jak wyżej dochodzimy do wniosku, że $A_2$ ma puste przecięcia z najwyżej $49$ zbiorami, zatem $A_2$ ma niepuste przecięcie z pewnym zbiorem $A_i$ z $50$ zbiorów $A_3,\dots,A_{52}$.
Każde dwa ze zbiorów $A_1, A_2, A_i$ mają niepuste przecięcie. \end{sol}
\end{enumerate}
\newsection{Dzień III}{3} \begin{enumerate}
\item
\begin{sol} Niech $x_1,x_2$ będą rozwiązaniami danego równania. Ze wzorów Viete'a mamy: \[x_1+x_2=-\frac{a}{k}\] \[x_1x_2=\frac{-bk+k^3}{k}=k^2-b\]
Wyznaczamy $a,b$: \[a=-k(x_1+x_2)\] \[b=k^2-x_1x_2\]
Obliczamy $a^2+b^2$: \[a^2+b^2=k^2(x_1+x_2)^2+(k^2-x_1x_2)^2=k^2(x^2_1+x^2_2)+2k^2x_1x_2+k^4-2k^2x_1x_2+(x_1x_2)^2=\] \[=k^4+k^2(x^2_1+x^2_2)+(x_1x_2)^2=(k^2+x^2_1)(k^2+x^2_2)\] Liczby $k,x_1,x_2$ są całkowite i niezerowe, zatem $k^2,x^2_1,x^2_2\geq 1$, czyli $k^2+x^2_1\geq 2, k^2+x^2_2\geq 2$.
Wyrażenie $a^2+b^2$ jest więc iloczynem dwóch liczb naturalnych większych od 1, zatem jest liczbą złożoną. \end{sol}
\item
\begin{sol} Załóżmy, że taki trapez istnieje.
Oznaczmy wierzchołki trapezu jako $ABCD$; $AB$ i $CD$ są podstawami, $\angle BAD = \angle ABC = 60\deg$. Oczywiście $AB > CD$.
Niech punkt $E$ będzie taki, że $EDCB$ jest równoległobokiem. Wtedy $\angle AED = \angle ABC = 60\deg$ i~$\angle EAD = \angle BAD = 60\deg$, zatem $AED$ jest trójkątem równobocznym.
Z definicji punkt $E$ jest przesunięciem $B$ o wektor $CD$, więc ma współrzędne całkowite.
Trójkąt $AED$ jest równoboczny i wszystkie jego wierzchołki mają współrzędne całkowite. Dowód sprowadza się zatem do następującego:
\emph{Udowodnić, że nie istnieje trójkąt równoboczny, którego wszystkie wierzchołki mają współrzędne całkowite.}
\begin{minipage}[<+tb+>]{4.5cm} \includegraphics{pick} \end{minipage}\begin{minipage}{10cm} Załóżmy, że taki trójkąt istnieje. Zauważmy, że jeżeli ma on bok $a$, to liczba $a^2$ jest liczbą całkowitą.
Wielokąt wypukły, którego wszystkie wierzchołki mają współrzędne całkowite, ma pole postaci $\frac{1}{2}K$, gdzie $K$ jest liczbą całkowitą. Faktycznie, jeżeli dobudujemy do boków trójkąty prostokątne, otrzymamy wielokąt o polu całkowitym, a dobudowywane trójkąty mają pola postaci $\frac{1}{2}\cdot$\emph{liczba całkowita}, patrz rysunek.
A więc nasz trójkąt ma pole równe $\frac{1}{2}k$, gdzie $k\in \mathbb{Z}$. \end{minipage}
Z drugiej strony trójkąt równoboczny ma boku $a$ ma pole równe $\frac{a^2\sqrt{3}}{4}$: \[ \frac{1}{2}k = \frac{a^2\sqrt{3}}{4} \] \[ \frac{2k}{a^2} = \sqrt{3} \] Stwierdziliśmy wcześniej, że $a^2, k$ są liczbami całkowitymi. Z powyższego wzoru wynika więc, że~$\sqrt{3}$ jest liczbą wymierną, a to nieprawda. Sprzeczność. \end{sol}
\item
\begin{sol} \begin{minipage}[<+tb+>]{2.5cm} \includegraphics{coloring1} \end{minipage}\begin{minipage}{12.5cm} Wprowadźmy jakikolwiek układ współrzędnych na tej szachownicy. Każdy kwadrat $4\times 4$, którego wierzchołki mają współrzędne całkowite i podzielne przez $4$ kolorujemy jak na rysunku.
Zauważmy, że każdy prostokąt $1 \times 5$ odpowiadający pięciu pionkom w rzędzie lub kolumnie zakrywa pewną parę pól z tą samą liczbą wpisaną, leżących obok siebie. \end{minipage}
\begin{minipage}[<+tb+>]{7cm} \includegraphics{coloring2} \end{minipage}\begin{minipage}{8cm} \emph{Na przykładowym rysunku pionowy prostokąt zawiera 2 piątki, a poziomy -- 2 dwójki.}
\phantom{.}
Rozważmy następującą strategię Iwony: \begin{center} Gdy Ireneusz stawia pionek na polu o pewnym numerze $i$, Iwona stawia pionek na sąsiadującym polu o numerze $i$. \end{center}
Przy takiej strategii Iwony Ireneusz nie może ustawić pięciu pionków w rzędzie lub kolumnie, gdyż to oznaczałoby, że ustawił swoje pionki na obu polach pewnej pary, a to nie jest możliwe. \end{minipage} \end{sol}
\end{enumerate}
\newsection{Mecz matematyczny}{M} \begin{enumerate}
\item
\begin{sol} Na mocy nierówności między średnią arytmetyczną a geometryczną \[1=\frac{a^{2010}+b^{2010}+c^{2010}+d^{2010}+e^{2010}}{2010}=\] \[=\frac{\underbrace{\frac{1}{400}a^{2010}+\ldots+\frac{1}{400}a^{2010}}_{400}+\underbrace{\frac{1}{401}b^{2010}+\ldots+\frac{1}{401}b^{2010}}_{401}+\underbrace{\frac{1}{402}c^{2010}+\ldots+\frac{1}{402}c^{2010}}_{402}}{2010}+\] \[+\frac{\underbrace{\frac{1}{403}d^{2010}+\ldots+\frac{1}{403}d^{2010}}_{403}+\underbrace{\frac{1}{404}e^{2010}+\ldots+\frac{1}{404}e^{2010}}_{404}}{2010}\geq\] \[ \geq a^{400}b^{401}c^{402}d^{403}e^{404}\sqrt[2010]{\frac{1}{400^{400}401^{401}402^{402}403^{403}404^{404}}}\] Po przekształceniu otrzymujemy: $a^{400}b^{401}c^{402}d^{403}e^{404} \leq \sqrt[2010]{400^{400}401^{401}402^{402}403^{403}404^{404}}$.
Wartość ta jest osiągnięta, gdy między średnimi zachodzi równość, czyli kiedy spełniony jest warunek: $\frac{1}{400}a^{2010}=\frac{1}{401}b^{2010}=\frac{1}{402}c^{2010}=\frac{1}{403}d^{2010}=\frac{1}{404}e^{2010}$, który wraz z warunkiem $a^{2010}+b^{2010}+c^{2010}+d^{2010}+e^{2010}=2010$ pociąga za sobą $a=\sqrt[2010]{400},b=\sqrt[2010]{401},c=\sqrt[2010]{402},d=\sqrt[2010]{403},e=\sqrt[2010]{404}$.
Sprawdzamy: \[(\sqrt[2010]{400})^{400}(\sqrt[2010]{401})^{401}(\sqrt[2010]{402})^{402}(\sqrt[2010]{403})^{403}(\sqrt[2010]{404})^{404}=\sqrt[2010]{400^{400}401^{401}402^{402}403^{403}404^{404}}.\]
Największą możliwą wartością wyrażenia $a^{400}b^{401}c^{402}d^{403}e^{404}$ jest liczba
$\sqrt[2010]{400^{400}401^{401}402^{402}403^{403}404^{404}}$. \end{sol}
\item
\begin{sol} Przekształcamy prawą stronę równania: \[\frac{k+2k+ \ldots +nk}{n}=\frac{kn(n+1)}{2n}=\frac{k(n+1)}{2}\]
Przeprowadzamy dowód nie wprost.
Załóżmy, że liczba całkowita $a$ jest pierwiastkiem $W(x)$. Z twierdzenia B\`ezouta wiemy że: $W(x)=(x-a)Q(x)$, gdzie $Q(x)$ jest wielomianem o współczynnikach całkowitych.
Warunek z zadania przyjmuje postać:
\[(k-a)(2k-a)\ldots (nk-a)\cdot Q(k)Q(2k)\ldots Q(nk)=\frac{k(n+1)}{2}\]
Liczby $Q(k),Q(2k),\ldots ,Q(nk)$ są całkowite.
Liczby $k-a,2k-a,\ldots ,nk-a$ dają różne reszty z dzielenia przez $n$. Jeżeli bowiem $ik-a\equiv jk-a \mod n$, dla $i,j\in \{1,2,\ldots ,n\},$ to $n|(ik-a)-(jk-a)=k(i-j)$, a skoro $k$ i $n$ są względnie pierwsze to $n|i-j$, ale $0\leq i-j<n$, zatem $i-j=0$, $i=j$.
Liczby $k-a,2k-a,\ldots ,nk-a$ dają $n$ różnych reszt, zatem wypełniają cały zbiór możliwych reszt z dzielenia przez $n$, w szczególności któraś z nich daje resztę $0$ z dzielenia przez $n$.
Lewa strona warunku z zadania jest podzielna przez $n$, a więc i prawa jest podzielna:
$$n \Big| \frac{k(n+1)}{2}.$$
Liczby $k$ i $n$ są względnie pierwsze, zatem $n|n+1$, a więc $n|n+1-n=1$, $n=1$, co stoi w~sprzeczności z warunkiem $n>1$. \end{sol}
\item
\begin{sol} Figura $I$ powstaje z kwadratu $K$ o wymiarach $3 \times 3$ poprzez odcięcie dwóch górnych narożników w~postaci trójkątów prostokątnych równoramiennych o przyprostokątnych długości $1$, a jej środkiem nazwiemy środek kwadratu $K$.
Figura $II$ jest obrazem figury $I$ w obrocie o kąt $180\deg$ wokół środka figury $I$. Środkiem figury $II$ także nazwiemy środek kwadratu $K$.
\includegraphics{zad7szesciokaty.pdf}
Umieśćmy dany prostokąt w układzie współrzędnych w ten sposób, że jego wierzchołki znajdują się w punktach: $(0,5), (0,0), (3k,0), (3k,5)$.
Umieśćmy $k$ figur $I$ w tym prostokącie w następujący sposób: $i$-tą figurę $I$ umieszczamy w ten sposób, że jej środek jest w punkcie $(\frac{3}{2}+3(i-1), \frac{3}{2})$, gdzie $i\in \left\{ 1,2,\dots,k \right\}$.
Następnie umieśćmy $k+1$ figur $II$ w następujący sposób: środek $i$-tej figury znajduje się w punkcie $(\frac{1}{2}+3(i-1), \frac{7}{2})$, gdzie $i \in \left\{ 1,2,\dots,k+1 \right\}$. W ten sposób cały prostokąt został przykryty:
\includegraphics{zad7calosc.pdf}
Z zasady szufladkowej Dirichleta wynika, że skoro w prostokącie jest $2k+2$ punktów, a umieszczonych jest w nim $2k+1$ figur, które całkowicie pokrywają prostokąt (każdy punkt leży w którejś z~figur), to w pewnej figurze znajdują się dwa punkty.
Wiadomo, że najdłuższy odcinek zawarty w wielokącie wypukłym jest jedną z przekątnych lub boków wielokąta, zatem najdłuższy odcinek zawarty w figurze $I$ lub $II$ ma długość $\sqrt{2^2+3^2}=\sqrt{13}$, innymi słowy odległość między punktami leżącymi w jednej figurze jest nie większa niż $\sqrt{13}$. \end{sol}
\item
\begin{sol}
\textbf{Podpunkt a.}
\emph{Poniższe rozwiązanie jest powtórzeniem rozwiązania zadania z grupy początkującej.}
\begin{minipage}{4cm} \includegraphics[height=40mm]{szesciokat_ola} \end{minipage}\begin{minipage}{12cm}
Zapiszmy sześciokrotnie nierówność trójkąta z oznaczeniami jak na rysunku: $$a \leq (1-y)+(1-z) \quad b \leq (1-x) + (1-y) \quad c \leq (1-x)+z$$ $$d \leq y+z \quad e \leq x+y \quad f \leq (1-z)+x$$
Dodając nierówności stronami otrzymujemy: $$a+b+c+d+e+f \leq 6.$$ Widzimy zatem, że obwód danego sześciokąta nie może być większy niż $6$. \end{minipage}
\textbf{Podpunkt b.}
Rozważmy następującą sytuację: wszystkie odcinki dzielą się w takich samych stosunkach, patrz rysunek:
\begin{minipage}{5cm} \includegraphics[height=4.5cm,width=4.5cm]{szesciokat_ola_plaski} \end{minipage}\begin{minipage}{10cm}
Stwierdzam, że jeżeli wezmę $$\varepsilon < \frac{1}{12}\left( 6 - 5.999999999\right),$$ to obwód sześciokąta, czyli suma długości odcinków niebieskich, będzie większy od $5.999999999$.
Zaiste dla każdego z trójkątów o jednym boku niebieskim, jednym długości $\varepsilon$ a jednym długości $1 - \varepsilon$ możemy zapisać nierówność trójkąta:
$$\hbox{\textcolor{Blue}{niebieski bok}} + \varepsilon \geq 1 - \varepsilon$$ $$\hbox{\textcolor{Blue}{niebieski bok}} \geq 1 - 2\cdot\varepsilon$$
\end{minipage}
Sumując $$\hbox{ Obwód } \geq 6 - 12\varepsilon > 6 - (6 - 5.999999999) = 5.999999999.$$
Widzimy, że istnieje sześciokąt o obwodzie większym niż $5.999999999$. \end{sol}
\item
\begin{sol}
\begin{minipage}{7cm} \includegraphics{wypukle_yogi} \end{minipage}\begin{minipage}{8cm} Poprowadźmy przez wierzchołki $A$ proste prostopadłe do odpowiednich boków $A$, jak na rysunku. Wielokąt $A$ jest wypukły, więc fragmenty obwodu $B$ odcięte przez kolejne proste (na rysunku pogrubione) są rozłączne. Aby udowodnić tezę, wystarczy więc pokazać, że długość boku jest nie większa od długości odpowiedniego fragmentu obwodu $B$ np.\ na rysunku fragmentu pomiędzy $A'$ i $B'$.
Proste $AA'$ i $BB'$ są równoległe i odległość pomiędzy tymi prostymi wynosi $AB$, bo $AB$ jest prostopadły do tych prostych.
$A'\in AA', B'\in BB'$, więc odległość pomiędzy punktami $A'$ i $B'$ jest nie mniejsza niż odległość pomiędzy prostymi $AA'$ i $BB'$.
Łącznie $$\hbox{ długość obwodu pomiędzy }A'\hbox{ i }B' \geq A'B' \geq AB$$ co kończy dowód. \end{minipage} $ $ \end{sol}
\item
\begin{sol}
\begin{lem} Przy oznaczeniach z zadania $\angle EDA = \angle FDA$ innymi słowy wysokość $AD$ jest dwusieczną w trójkącie $DEF$. \end{lem}
\begin{proof}[Dowód lematu] Niech $H$ oznacza ortocentrum trójkąta $ABC$. Mamy $\angle HEC = \angle HDC = 90\deg$, zatem $\angle HEC + \angle HDC = 180\deg$, czyli punkty $H,E,C,D$ leżą na jednym okręgu.
Kąty $\angle ADE = \angle HDE$ i $\angle HCE$ są oparte na tym samym łuku, czyli $\angle HDE = \angle HCE = 90\deg - \angle CAB$.
Analogicznie przeliczam $\angle ADF = 90\deg - \angle CAB$. A więc $\angle ADF = \angle ADE$. \end{proof}
\begin{minipage}{7cm} \includegraphics[width=6cm, height=6cm]{orthic} \end{minipage}\begin{minipage}{9cm} Niech $E', E''$ będą odbiciami $E$ względem $BC, BA$. Zauważmy, że $\angle E'DF = \angle EDF + 2\cdot \angle EDC = 2\cdot \angle EDA + 2\cdot \angle EDC = 2\cdot (\angle ADE + \angle EDC) = 2\cdot 90\deg = 180\deg$. Punkty $D,F,E'$ leżą więc na jednej prostej! Analogicznie dowodzę, że $D,F,E''$ leżą na jednej prostej. Reasumując $E',D,F,E''$ leżą na jednej prostej i $$E'E'' = E'D + DF + FE'' = ED + DF + FE$$
Popatrzmy teraz na trójkąt $BE'E''$. W trójkącie tym $BE' = BE'' = BE$ i $\angle E'BE'' = \angle E'BE + \angle EBE'' = 2\cdot (\angle CBE + \angle ABE) = 2\angle CBA$. \end{minipage}
\begin{minipage}{10cm} Rozważmy analogicznie odbicia $Y', Y''$ punktu $Y$ względem $BC, BA$. Z nierówności trójkąta $$Y'Y'' \leq Y'Z + ZX + XY'' = YZ + ZX + XY$$
Aby pokazać tezę, wystarczy więc dowieść, że \[E'E'' \leq Y'Y''.\]
Popatrzmy na trójkąt $Y'BY''$. Identycznie jak przy trójkącie $E'BE''$ dowodzimy, że $Y'B = Y''B = YB$ i $\angle Y'BY'' = 2\angle CAB$.
Trójkąty $Y'BY''$ i $E'BE''$ są równoramienne i mają taki sam kąt pomiędzy ramionami. Zatem są one podobne. W szczególności $$\frac{Y'Y''}{E'E''} = \frac{BY'}{BE'} = \frac{BY}{BE} \geq 1$$ gdyż wysokość jest najkrótszym odcinkiem pomiędzy $B$ a bokiem $AC$.
\end{minipage}\begin{minipage}{6cm} \includegraphics[width=6cm, height=6cm]{orthic_randompoints} \end{minipage}
Podsumowując: $$ED + DF + FE = E'E'' \leq Y'Y'' \leq YZ + ZX + XY.$$ \end{sol}
\item
\begin{sol}
Aby rozwiązać to zadanie, wykorzystajmy metodę wielomianu pomocniczego.
Załóżmy, że $(x,y,z)$ spełniają układ równań z zadania i weźmy wielomian postaci $W(x)=(t-x)(t-y)(t-z) = t^3+\sigma_{1}t^2+\sigma_{2}t+\sigma_{3}$. Zauważmy, że każdy ze współczynników $\sigma$ można na mocy wzorów Viete'a przedstawić za pomocą wyrażeń z wyjściowego układu: $$\sigma_{1}=-(x+y+z)=-4$$ $$\sigma_{2}=xy+yz+zx=\frac{1}{2}((x+y+z)^2-(x^2+y^2+z^2))=\frac{1}{2}(16-78)=-31$$ $$\sigma_{3}=-xyz$$ Aby obliczyć $\sigma_{3}=-xyz$, zapiszmy jeden z ciekawszych wzorów skróconego mnożenia: $$x^3+y^3+z^3=(x+y+z)(x^2+y^2+z^2-(xy+yz+zx))+3xyz$$ $$226 = 4(78 + 31) - 3\sigma_{3} \hbox{ więc }\sigma_{3}=70$$ Otrzymaliśmy zatem wielomian $W(x)=t^3-4t^2-31t+70$, którego pierwiastki, a zarazem rozwiązania układu równań, znajdziemy w tradycyjny sposób.
Nietrudno zauważyć, że jednym z pierwiastków jest $2$. Stosując schemat Hornera z łatwością znajdujemy pozostałe pierwiastki: $-5$ i $7$.
Otrzymaliśmy zatem rozwiązania -- wszystkie permutacje trójki $(-5, 2, 7)$: $$(-5,2,7), (-5, 7,2), (2, -5, 7), (2, 7, -5), (7, 2, -5), (7, -5, 2)$$
Wszystkie przejścia w rozumowaniu były równoważne, zresztą nietrudno stwierdzić, że powyższe trójki spełniają układ równań z zadania. \end{sol}
\item
\begin{sol}
\begin{minipage}[<+tb+>]{5.5cm} \includegraphics[height=4.5cm]{graph_geo_ineq} \end{minipage}\begin{minipage}{10cm} Oznaczmy odległości wierzchołków $A,B,C$ od punktów styczności sąsiednich boków z okręgiem wpisanym jako $x,y,z$ odpowiednio. Zachodzą równości $AB=x+y,\ BC = y+z,\ CA= z+x$.
Zapiszmy wzór na pole trójkąta na dwa sposoby: \[P=(x+y+z)r=\frac{(x+y)(y+z)(z+x)}{4R}.\] Porównując te wzory ze wzorem Herona: \end{minipage}
\[P=\sqrt{(x+y+z)(x+y+z-x-z)(x+y+z-y-z)(x+y+z-x-y)}=\sqrt{(x+y+z)xyz},\] wyznaczyć możemy długości promieni w zależności od $x,y,z$: \[\sqrt{(x+y+z)xyz}=(x+y+z)r\Leftrightarrow r=\sqrt{\frac{xyz}{x+y+z}}\] \[\frac{(x+y)(y+z)(z+x)}{4R}=\sqrt{(x+y+z)xyz}\Leftrightarrow R=\frac{(x+y)(y+z)(z+x)}{4\sqrt{(x+y+z)xyz}}.\]
Teza głosi, że $\frac{R}{r}\geq 2$, co równoważne jest nierówności \[\frac{(x+y)(y+z)(z+x)}{4\sqrt{(x+y+z)xyz}}\cdot \sqrt\frac{x+y+z}{xyz}\geq 2.\] Po przekształceniu otrzymujemy nierówność: \[(x+y)(y+z)(z+x)\geq8xyz,\] \[\frac{(x+y)(y+z)(z+x)}{8}\geq xyz,\] \[\frac{x+y}{2}\cdot\frac{y+z}{2}\cdot\frac{z+x}{2}\geq\sqrt{xy}\cdot\sqrt{yz}\cdot\sqrt{zx}=\sqrt{x^2 y^2 z^2}.\] Ostatnia nierówność jest iloczynem trzech nierówności pomiędzy średnią arytmetyczną a geometryczną, które są prawdziwe dla wszystkich liczb dodatnich. Nierówność ta jest więc prawdziwa, a~że jest ona równoważna tezie, to i teza jest prawdziwa. \end{sol}
\item
\begin{sol}
Niech dla zwięzłości $D$ oznacza zbiór $2n+1$ liczb z zadania, $D_+$ oznacza podzbiór liczb nieujemnych $D$, a $D_-$ -- podzbiór liczb ujemnych.
Rozważmy liczbę $a \in D$ mającą najmniejszą wartość bezwzględną spośród liczb z $D$.
Załóżmy, że $a \leq 0$.
Rozważmy zbiór \[a + D_- = \left\{ a + d\ |\ d\in D_- \right\}\] Wszystkie elementy tego zbioru leżą w przedziale $[a-(2n-1), a]$. Oczywiście w przedziale $[a-(2n-1), -2n]$ może leżeć maksymalnie $-2n-(a-(2n-1)) + 1 = - a$ liczb. Tak więc w przedziale $[-(2n-1), a]$ leży co najmniej $|D_-| + a$ liczb (\emph{liczba $|D_-| +a$ może być ujemna, ale w niczym nie psuje to rozwiązania}).
Z definicji $a$ jako elementu mającego najmniejszą wartość bezwzględną wszystkie elementy $D_+$ leżą w $[|a|, 2n-1]$, a więc wszystkie elementy zbioru $-D_+ = \left\{ -d\ |\ d\in D_+ \right\}$ leżą w przedziale $[-(2n-1), a]$.
W przedziale $[-(2n-1), a]$ leży więc $|D_-| + a$ różnych elementów zbioru $a+D_-$ oraz $|D_+|$ różnych elementów zbioru $-D_+$.
Przedział ten ma długość $2n - 1 + a + 1$, a elementów jest łącznie $|D_-| + a + |D_+| = 2n + 1 + a$, czyli więcej niż wynosi długość przedziału. Zatem istnieją takie $b\in D_-, c\in D_+$ że \[a+b = -c\hbox{ czyli } a+b+c=0.\]
Gdy $a > 0$ rozważamy zbiór $a + D_+$, $-D_-$ i analogicznie dochodzimy do tezy. \end{sol}
\item
\begin{sol}
\begin{minipage}[<+tb+>]{3.5cm} \includegraphics{threedim} \end{minipage}\begin{minipage}{11.5cm} Niech $P$ i $Q$ będą punktami leżącymi na przedłużeniach krawędzi $SB$ i $SC$, tak aby $SP = SQ = SA$.
Rozważmy kwadrat $SPRQ$, a w nim trójkąty $RCB$, $RCQ$, $RBP$. Trójkąty $RCQ$ i $RBP$ są przystające odpowiednio do trójkątów $ABS$ i $ACS$, a więc trójkąt $RBC$ jest przystający do trójkąta $ACB$. Stąd \[\angle CAS + \angle CAB + \angle BAS = \angle PRB + \angle BRC + \angle CRQ = \angle PRQ = 90\deg.\] \end{minipage} \end{sol}
\end{enumerate}
\newsection{Trudniejsze}{T} \begin{enumerate}
\item
\begin{sol} Udowadniamy tezę przez indukcję po stopniu wielomianu $P$.
Baza indukcji -- stopień $0$. Jeżeli wielomian jest stopnia $0$, to jest on stały, zatem teza zachodzi dla niego trywialnie.
Krok indukcyjny. Załóżmy, że dla wielomianów stopnia mniejszego od $n$ ($n<p$) teza zachodzi. Weźmy wielomian $P$ stopnia $n$: $$P(x) = a_nx^n + a_{n-1}x^{n-1} + \dots + a_0$$
Rozważmy dwa przypadki: \begin{enumerate} \item $p|a_n$. Wtedy wielomian $P(x) - a_nx^n$ jest stopnia mniejszego od $n$ i dla każdej liczby całkowitej wartość $P(x) - a_nx^n$ jest podzielna przez $p$, zatem z założenia indukcyjnego $P(x) - a_nx^n$ jest podzielny przez $p$ a więc i $P(x)$ jest podzielny przez $p$. \item $p\not|a_n$.
Rozważmy wielomian $Q(x) := P(x+1) - P(x) = n\cdot a_nx^{n-1} + \hbox{ wyrazy niższego stopnia}$.
Dla każdej liczby całkowitej wartości $P(x+1), P(x)$ są podzielne przez $p$, zatem i wartość $Q(x)$ jest podzielna przez $p$.
Wielomian $Q$ jest stopnia mniejszego niż $n$ i spełnia założenia, zatem z indukcji spełnia tezę. W szczególności współczynnik $n\cdot a_n$ jest podzielny przez $p$. Ale $p$ jest liczbą pierwszą i $p\not|a_n$. Zatem $p|n$, $p\leq n$. Sprzeczność. \end{enumerate} \end{sol}
\item
\begin{sol}
\begin{minipage}{7.5cm} \includegraphics{6_07graph} \end{minipage}\begin{minipage}{7.5cm} Skoro trójkąt $ABC$ nie jest równoramienny, to punkty $A, O, I$ nie leżą na jednej prostej.
Przedłużmy odcinek $AI$ i oznaczmy punkt jego przecięcia z okręgiem opisanym na $\triangle ABC$ jako $K$. Niech będzie $D$ środkiem $AK$, wtedy $OD \perp AK$.
Oczywistym jest, że $\angle AIO \leq 90\deg$ wtedy i tylko wtedy, gdy punkt $I$ leży po przeciwnej stronie punktu $D$ niż punkt $A$, czyli gdy $AI \geq IK$.
Zauważmy, że $CK=BK$, gdyż odcinek $AI$ zawiera się w dwusiecznej kąta $BAC$. \begin{lem} Długość odcinka $IK$ równa jest długości odcinków $CK$ i $BK$. \end{lem}
\end{minipage}
\begin{proof} Oznaczmy $\angle CAK = \angle KAB = \alpha$ oraz $\angle ABI = \angle IBC = \beta$.
Z twierdzenia o kątach wpisanych opartych na tym samym łuku $\angle CBK = \alpha$, więc $\angle IBK = \alpha + \beta$.
Ponadto $\angle AIB = 180^{\circ} - \alpha - \beta$, a zatem $\angle BIK = \alpha + \beta$, więc trójkąt $BKI$ jest równoramienny -- $BK=IK$. \end{proof}
Zastosujmy znany fakt.
\begin{thm}[Ptolemeusza] W dowolnym czworokącie $ABCD$ suma iloczynów długości przeciwległych boków jest większa bądź równa iloczynowi długości przekątnych: \[AB\cdot CD+BC\cdot DA\geq AC\cdot BD\] Równość zachodzi wtedy i tylko wtedy, gdy czworokąt da się wpisać w okrąg. \end{thm}
Skoro czworokąt $ABKC$ wpisany jest w okrąg, zachodzi $AB\cdot CK+AC\cdot BK=AK\cdot CB$.
Mając $CK=IK=BK$, możemy zapisać tę zależność w postaci: \[AB\cdot IK+AC\cdot IK=BC\cdot(AI+IK) \Leftrightarrow AB+AC=BC+\frac{AI}{IK}BC\] Zauważmy, że prawa strona równości jest większa lub równa $2BC$ wtedy i tylko wtedy, gdy $\frac{AI}{IK}\geq1$, czyli $AI \geq IK$, co jest równoważne nierówności $\angle AIO \leq 90^{\circ}$. Tak więc udowodniliśmy, że $\angle AIO \leq 90^{\circ} \Leftrightarrow 2BC \leq AB+AC$. \end{sol}
\begin{sol}[Inne rozwiązanie] Zadanie to można rozwiązać nie znając twierdzenia Ptolemeusza.
Tak jak w poprzednim rozwiązaniu dowodzimy, że $\angle AIO \leq 90\deg \Leftrightarrow AI \geq IK$ oraz $BK = CK = IK$.
Niech $B'$ oznacza punkt styczności okręgu wpisanego w $\triangle ABC$ z $AC$, zaś $M$ oznacza środek boku $BC$.
Zachodzą równości kątów $\angle MCK = \angle CAK$ oraz $\angle CMK = \angle AB'I = 90\deg$. Zatem trójkąty $\triangle AIB'$ i $\triangle CKM$ są podobne. Z podobieństwa tych trójkątów wynika
\[\frac{IK}{AI} = \frac{CK}{AI} = \frac{CM}{AB'} = \frac{\frac{1}{2}BC}{\frac{1}{2}\left( AB + AC - BC \right)} = \frac{BC}{AB + AC - BC}.\]
Tak więc $IK \leq AI \Leftrightarrow BC \leq AB + AC - BC \Leftrightarrow 2\cdot BC \leq AB + AC$. \end{sol}
\item
\begin{sol} Funkcja taka istnieje.
Niech $Tri$ będzie zbiorem takich liczb, w których rozkładzie na czynniki pierwsze trójka występuje w nieparzystej potędze, w szczególności liczby ze zbioru $Tri$ są podzielne przez $3$.
Szukana funkcja ma postać: \[ f(x)=\left\{ \begin{array}{c c} \frac{1}{3}x$ dla $x\in Tri\\ 15x$ dla $x\notin Tri\\ \end{array} \right. \]
Funkcja $f$ dla naturalnych argumentów przyjmuje naturalne wartości. Dla elementów z jednego ze zbiorów $Tri, \mathbb{Z}_+ - Tri$ funkcja $f$ przyjmuje wartości ze zbioru drugiego.
Przy dwukrotnym złożeniu funkcji wykonane zostaną więc oba działania, mianowicie $f(f(x))=\frac{1}{3}\cdot 15x=5x$ lub $f(f(x))=15\cdot\frac{1}{3}x=5x$. \end{sol}
\item
\begin{sol} Rozwiązanie poprzedzimy dwoma uwagami. \begin{uwaga} Dla każdych $i, N_a, N_b, N_c$ naturalnych istnieje takie $i' > i$, że \[a_{i'} > N_a \quad b_{i'} > N_b \quad c_{i'} > N_c.\] \end{uwaga} \begin{proof}[Dowód uwagi] Liczb całkowitych dodatnich nie większych od $N_a$ jest $N_a$ i każda z nich może się pojawiać w ciągu $(a_n)$ co najwyżej raz, zatem co najwyżej $N_a$ wyrazów ciągu $(a_{i+1}, a_{i+2},\dots)$ może być nie większych od $N_a$.
Identyczne rozumowanie pokazuje, że co najwyżej $N_b$ wyrazów ciągu $(b_{i+1}, b_{i+2},\dots)$ jest nie większych od $N_b$ i co najwyżej $N_c$ wyrazów ciągu $(c_{i+1},c_{i+2},\dots)$ jest nie większych od $N_c$.
Rozważmy dowolny indeks $j > i$.
Nie spełnia on warunków na $i'$ z uwagi wtedy i tylko wtedy, gdy $a_j \leq N_a$ lub $b_j \leq N_b$ lub $c_j \leq N_c$, czyli gdy $j$ jest jednym z co najwyżej $N_a + N_b + N_c$ indeksów. Ale w ciągu $(i+1, i+2,\dots)$ jest nieskończenie wiele (a więc więcej niż $N_a + N_b + N_c$) indeksów, więc istnieje indeks, który spełnia warunki na $i'$. \end{proof}
\begin{uwaga} Dla dowolnego $i$ istnieje takie $i' > i$, że $a_i < a_{i'},\ b_i < b_{i'} \hbox{ oraz } c_i < c_{i'}$. \end{uwaga}
\begin{proof} Wystarczy zastosować poprzednią uwagę dla $N_a := a_i,\ N_b := b_i,\ N_c := c_i$. \end{proof}
Przystąpmy do dowodu zadania. Skonstruujemy ciąg $(i_s)$ indukcyjnie.
Wybieramy $i_1 := 1$.
Jeżeli mamy wybrane $(i_1,\dots,i_k)$, to z drugiej uwagi istnieje $i' > i_k$ takie, że $a_{i'} > a_{i_k},\ b_{i'} > b_{i_k} \hbox{ oraz } c_{i'} > c_{i_k}$. Kładziemy $i_{k+1} := i'$, tak więc \[a_{i_{k+1}} > a_{i_k},\ b_{i_{k+1}} > b_{i_k} \hbox{ oraz } c_{i_{k+1}} > c_{i_k}.\]
Przez indukcję skonstruowaliśmy nieskończony ciąg $(i_s)$, powyższe nierówności wskazują, że spełnia on założenia z zadania. \end{sol}
\end{enumerate}
% Wykłady----------------------------------------------------------------------------------------------------------
\newchapter{Wykłady}{W} \renewcommand{\labelenumi}{\theenumi}
\begin{lecture}[$\varepsilon$-otoczki] \renewcommand{\labelenumi}{}
\begin{defn} $\varepsilon$-otoczką figury $\mathcal{F}$ nazwiemy figurę złożoną ze wszystkich punktów odległych od $\mathcal{F}$ o co najwyżej $\varepsilon$. \end{defn}
Własności i przykłady: \begin{itemize} \item Figura $\mathcal{F}$ jest równa $0$-otoczce $\mathcal{F}$. \item Dla $\varepsilon \leq \varphi$ $\varepsilon$-otoczka $\mathcal{F}$ jest zawarta w $\varphi$-otoczce $\mathcal{F}$, a wiec każda otoczka $\mathcal{F}$ zawiera figurę $\mathcal{F}$. \item $\varepsilon$-otoczką koła o środku $O$ i promieniu $r$ jest koło o środku $O$ i promieniu $r + \varepsilon$ (mówimy tutaj o $\varepsilon$-otoczce w dwóch wymiarach). \item $\varepsilon$-otoczka sześcianu o krawędzi $a$ to ``sześcian z zaokrąglonymi rogami'' i ma ona objętość $a^3 + 6a^2\varepsilon + 3\pi\cdot a\varepsilon^2 + \frac{4}{3}\pi \varepsilon^3$. \item Figury $\mathcal{F}$ i $\mathcal{G}$ są odległe o więcej niż $\varepsilon$ wtedy i tylko wtedy, gdy ich $\frac{\varepsilon}{2}$-otoczki są rozłączne. \end{itemize}
\subsection{Zadania} \begin{enumerate} \item \begin{problem}{1}{stare kółka ilo} W kwadracie o boku $10$ umieszczono $70$ odcinków długości $1$. Udowodnij, że pewne dwa z tych odcinków leżą w odległości mniejszej niż $1$. \end{problem} \item \begin{problem}{2}{stare kółka ilo} Kwadrat $1 \times 1$ jest pokryty przez $n$ kół. Udowodnij, że można wybrać spośród nich koła o łącznym polu nie mniejszym niż $1/9$, z których każde dwa są rozłączne. \end{problem} \item \begin{problem}{2}{stare kółka ilo} Sześcian $1 \times 1 \times 1$ jest pokryty przez $n$ kul. Udowodnij, że można wybrać spośród nich kule o łącznej objętości nie mniejszej niż $1/27$, z których każde dwie są rozłączne. \end{problem} \item \begin{problem}{2}{Prasołow} W kwadracie o boku $15$ leży $20$ parami rozłącznych kwadratów o boku $1$. Udowodnij, że jest możliwe umieszczenie w dużym kwadracie koła o promieniu $1$, nieprzecinającego wnętrza żadnego z kwadracików. \end{problem} \item \begin{problem}{2}{Prasołow} Figurę złożoną z przekątnych kwadracika jednostkowego nazwiemy $X$. Udowodnij, że w kole o promieniu $1000$ może umieścić tylko skończenie wiele parami nieprzecinających się $X$-ów. \end{problem} \item \begin{problem}{2.5}{Prasołow} Danych jest $n$ punktów $A_1,A_2,\dots,A_n$. Odległość pomiędzy każdymi dwoma z tych punktów wynosi więcej niż $2$.
Figura $\mathcal{F}$ ma pole mniejsze niż $\pi$. Udowodnij, że istnieje taki wektor o długości nie większej niż $1$, że $\mathcal{F}$ przesunięta o ten wektor nie zawiera żadnego z punktów $A_1,\dots,A_n$. \end{problem}
\item \begin{problem}{2}{Prasołow} Zaznaczmy na szachownicy $8 \times 8$ środki wszystkich pól. Czy można tak narysować $13$ prostych dzielących szachownicę, aby w każdym fragmencie był nie więcej niż $1$ zaznaczony punkt? \end{problem} \end{enumerate}
\end{lecture}
\begin{lecture}[Ciągi jednomonotoniczne] \renewcommand{\labelenumi}{}
\subsection{Teoria}
Ze względu na wygodę wprowadza się zwykle zapis, który nie jest na początku zbyt intuicyjny, ale potem okazuje się być czytelniejszy.
Załóżmy, że mamy skończenie wiele ciągów: $(a_1,\dots,a_n), (b_1,\dots,b_n), (c_1,\dots,c_n),\dots$.
Oznaczamy \[\mono{c c c c}{ a_1 & a_2 & \dots & a_n\\ b_1 & b_2 & \dots & b_n\\ c_1 & c_2 & \dots & c_n\\ \dots & \dots & \dots & \dots\\ } = a_1b_1c_1\cdot\ldots + a_2b_2c_2\cdot\ldots + \ldots + a_nb_nc_n\cdot\ldots \] czyli sumę iloczynów wszystkich kolumn. Ważne, że wartość tego iloczynu nie zmienia się przy zamianie kolumn ani wierszy, np. $ \mono{c c}{ a_1 & a_2\\ b_1 & b_2\\ } = \mono{c c}{ a_2 & a_1\\ b_2 & b_1\\ }, \mono{c c}{ a_1 & a_2\\ b_1 & b_2\\ } = \mono{c c}{ b_1 & b_2\\ a_1 & a_2\\ } $
\begin{thm}[Nierówność dla dwóch ciągów jednomonotocznicznych] Załóżmy, że mamy dane $n$-elementowe ciągi \textbf{niemalejące} $(a_1,a_2,\dots,a_n)$ i $(b_1, b_2, \dots, b_n)$, a ciąg $(b_1', b_2', \dots, b_n')$ jest dowolną permutacją ciągu $(b_1, b_2, \dots, b_n)$. Wtedy \[ \mono{c c c c}{ a_1 & a_2 & \dots & a_n\\ b_1 & b_2 & \dots & b_n\\ } \geq \mono{c c c c}{ a_1 & a_2 & \dots & a_n\\ b_1' & b_2' & \dots & b_n'\\ } \] \end{thm} Innymi słowy: jeżeli robimy iloczyny wyrazów z dwóch ciągów, to największą wartość uzyskamy stosując zasadę ``największy z największym''.
\begin{proof}[Szkic dowodu] Na początek udowadniany twierdzenie dla ciągów dwuelementowych: zakładamy, że $a_1 \leq a_2$ i $b_1 \leq b_2$. Jedyna nietrywialna permutacja $(b_1, b_2)$ to ciąg $(b_2, b_1)$, więc teza przekształca się równoważnie do: \[ \mono{c c}{ a_1 & a_2\\ b_1 & b_2\\ } \geq \mono{c c}{ a_1 & a_2\\ b_2 & b_1\\ } \] \[a_1b_1 + a_2b_2 \geq a_1b_2 + a_2b_1\] \[ (a_2 - a_1)(b_2 - b_1) \geq 0\] co jest prawdą.
W ogólnym przypadku (dla ciągów $n$-elementowych) pokazujemy, że da się stopniowo dojść od
$ \mono{c c c c}{ a_1 & a_2 & \dots & a_n\\ b_1' & b_2' & \dots & b_n'\\ } $ do $ \mono{c c c c}{ a_1 & a_2 & \dots & a_n\\ b_1 & b_2 & \dots & b_n\\ } $ nie zmniejszając wartości w żadnym kroku.
W $ \mono{c c c c}{ a_1 & a_2 & \dots & a_n\\ b_1' & b_2' & \dots & b_n'\\ } $ wybieramy kolumnę, w której jest wyraz równy $b_1$, załóżmy że jest to $k$-ta kolumna: \[ \mono{c c c c}{ a_1 & a_2 & \dots & a_n\\ b_1' & b_2' & \dots & b_n'\\ } = \mono{c c c c c c}{ a_1 & a_2 & \dots & a_k & \dots & a_n\\ b_1' & b_2' & \dots & b_1 & \dots & b_n'\\ } \] Z uprzednio udowodnionej nierówności wynika ($a_1 \leq a_k$ i $b_1 \leq b_1'$), że $ \mono{c c}{ a_1 & a_k\\ b_1'& b_1\\ } \leq \mono{c c}{ a_1 & a_k\\ b_1 & b_1'\\ } $, a stąd \[ \mono{c c c c}{ a_1 & a_2 & \dots & a_n\\ b_1' & b_2' & \dots & b_n'\\ } \leq \mono{c c c c c c}{ a_1 & a_2 & \dots & a_k & \dots & a_n\\ b_1 & b_2' & \dots & b_1' & \dots & b_n'\\ }. \] Analogicznie ``sortujemy'' ciąg $(b_1, b_2',\dots,b_1',\dots, b_n')$, potem $(b_1, b_2, \dots)$, itd.\ aż do otrzymania $(b_1,b_2,\dots,b_n)$. \end{proof}
\subsection{Zadania} \begin{enumerate} \item \begin{problem}{1}{Pawł.} Wykaż, że dla dowolnych liczb dodatnich $a,b$ zachodzi \[a^3 + b^3 \geq a^2b + ab^2\] \end{problem} \item \begin{problem}{1}{Pawł.} Wykaż, że jeżeli liczby $a,b$ są dodatnie, to \[ \sqrt{\frac{a^2}{b}} + \sqrt{\frac{b^2}{a}} \geq \sqrt{a} + \sqrt{b}\] \end{problem} \item \begin{problem}{1.5}{Pawł.} Udowodnij, że dla liczb dodatnich $a,b,c$ prawdziwa jest nierówność \[ \frac{a^2}{b+c} + \frac{b^2}{a+c} + \frac{c^2}{a+b} \geq \frac{a+b+c}{2}\] \end{problem} \item \begin{problem}{1.5}{Pawł.} Udowodnij, że dla liczb dodatnich $a,b,c$ prawdziwa jest nierówność \[ 2(a^3 + b^3 + c^3) \geq ab(a+b) + bc(b+c) + ca(c+a) \] \end{problem} \item \begin{problem}{2}{Pawł.} Udowodnij: \begin{thm}{Nierówność Czebyszewa}
Ciągi $(a_n)$ i $(b_n)$ są niemalejące. Udowodnij, że \[ n(a_1b_1 + \dots + a_nb_n) \geq (a_1 + \dots + a_n)(b_1 + \dots + b_n).\] \end{thm} \end{problem} \end{enumerate}
\subsection{Uogólniona teoria} \begin{thm} Jeżeli ciągi $(a_{1,1},\dots,a_{1,n}), (a_{2,1}, a_{2,2}, \dots ,a_{2, n}), \dots, (a_{k,1}, \dots, a_{k,n})$ są niemalejące i mają wyrazy \textbf{nieujemne}, to \[ \mono{c c c c}{ a_{1,1} & a_{1,2} & \dots & a_{1,n}\\ a_{2,1} & a_{2,2} & \dots & a_{2,n}\\ \dots & \dots & \dots & \dots\\ a_{k,1} & a_{k,2} & \dots & a_{k,n}\\ } \geq \mono{c c c c}{ a_{1,1}' & a_{1,2}' & \dots & a_{1,n}'\\ a_{2,1}' & a_{2,2}' & \dots & a_{2,n}'\\ \dots & \dots & \dots & \dots \\ a_{k,1}' & a_{k,2}' & \dots & a_{k,n}'\\ } \] gdzie ciąg $(a_{i, 1}', a_{i,2}', \dots, a_{i,n}')$ jest permutacją ciągu $(a_{i,1}, a_{i,2}, \dots, a_{i,n})$. \end{thm} \begin{proof}[Zarys dowodu]
Dowód jest analogiczny do dowodu poprzedniego twierdzenia. Najpierw wprost udowadniamy twierdzenie dla $n=2$, a potem korzystamy z tego wyniku w ogólnym przypadku. Po szczegóły odsyłam np. do książki ``Wędrówki po krainie nierówności'', podrozdział 4.3. \end{proof}
\subsection{Zadania II} \begin{enumerate} \setcounter{enumi}{5} \item \begin{problem}{2}{Kour.} Udowodnij, że dla dowolnych liczb dodatnich $a_1,\dots,a_n$ zachodzi \[\sqrt[n]{a_1a_2\dots a_n} \leq \frac{a_1 + \dots + a_n}{n} \leq \sqrt{\frac{a_1^2 + \dots + a_n^2}{n}}.\] \end{problem} \item \begin{problem}{1}{Pawł.} Udowodnij, że jeżeli $a,b,c$ są dodatnie, to \[ a^7 + b^7 + c^7 \geq a^2b^2c^2(a+b+c)\] \end{problem} \item \begin{problem}{1.5}{own} Liczby dodatnie $a,b,c$ spełniają warunek $a+b+c=3$. Udowodnij, że \[ \frac{b+c}{\sqrt{a}} + \frac{c + a}{\sqrt{b}} + \frac{a + b}{\sqrt{c}} \geq 6 \] \end{problem} \end{enumerate}
\end{lecture}
\begin{lecture}[Menelaos i Ceva] \renewcommand{\labelenumi}{}
\subsection{Teoria} \begin{thm}[Menelaosa] Dany jest $\Delta ABC$ i prosta przecinająca boki $BC$ i $CA$ odpowiednio w punktach $D$ i $E$ oraz przedłużenie boku $AB$ w punkcie $F$. Wówczas zachodzi: \[AF\cdot BD\cdot CE=BF\cdot DC\cdot EA\] \end{thm} \begin{proof}
\includegraphics{menelaos}
Poprowadźmy prostą równoległą do $AC$ przechodzącą przez $B$ i oznaczmy jako $K$ punkt jej przecięcia z prostą $DF$. Otrzymujemy trójkąty podobne $BKF$ i $AEF$, dla których możemy zapisać proporcje \[\frac{BF}{AF}=\frac{BK}{AE}.\] Zauważmy, że również trójkąty $ECD$ i $KBD$ są do siebie podobne, zatem \[\frac{CD}{DB}=\frac{EC}{BK}.\] Z równości tych możemy zapisać \[\frac{BF\cdot AE}{AF}=BK=\frac{EC\cdot DB}{CD},\] skąd otrzymujemy \[\frac{AF\cdot BD\cdot CE}{BF\cdot DC\cdot EA}=1\] równoważną żądanej równości. \end{proof} Prawdziwe jest również twierdzenie odwrotne do twierdzenia Menelaosa.
\begin{thm}[Cevy] Jeśli trzy proste $AD, BE, CF$ przechodzące przez wierzchołki trójkąta $ABC$ przecinają się w jednym punkcie, to zachodzi: \[AF\cdot BD\cdot CE=FB\cdot DC\cdot EA.\] \end{thm} \begin{proof} \includegraphics{ceva}
Rozpatrzmy zależności pomiędzy bokami i polami trójkątów o podstawach zawierających się w $AB$. Mamy zatem \[\frac{AF}{FB}=\frac{P_{AFC}}{P_{FBC}}=\frac{P_{AFO}}{P_{BFO}}\] Prowadzi to do równości \[\frac{AF}{FB}= \frac{P_{AFC} - P_{AFO}}{P_{FBC} - P_{BFO}} = \frac{P_{ACO}}{P_{BCO}}.\]
Analogicznie otrzymujemy \[\frac{BD}{DC}=\frac{P_{BAO}}{P_{CAO}}\] oraz \[\frac{CE}{EA}=\frac{P_{CBO}}{P_{ABO}}.\] Z trzech powyższych równości mamy: \[\frac{AF}{FB}\cdot\frac{BD}{DC}\cdot\frac{CE}{EA}=\frac{P_{ACO}}{P_{BCO}}\cdot\frac{P_{BAO}}{P_{CAO}}\cdot\frac{P_{CBO}}{P_{ABO}}=1\] \end{proof} Twierdzenie odwrotne do Twierdzenia Cevy prawdziwe jest wtedy i tylko wtedy, gdy proste $AD, BE, CF$ nie są równoległe.
\subsection{Zadania} \begin{enumerate} \item \begin{problem}{2}{znane} Udowodnić (korzystając z powyższej teorii), że w dowolnym trójkącie w jednym punkcie przecinają się: \begin{enumerate} \item wysokości; \item środkowe; \item dwusieczne. \end{enumerate} \end{problem} \item \begin{problem}{1}{znane} Udowodnić twierdzenie Cevy za pomocą twierdzenia Menelaosa. \end{problem} \item \begin{problem}{2}{znane} W trójkącie $ABC$ punkt $D$ jest środkiem boku $AB$, punkt $E$ leży na boku $BC$ tak, że $BE=2EC$, a kąty $ADC$ i $BAE$ są równe. Wyznaczyć miarę kąta $BAC$. \end{problem} \item \begin{problem}{2}{X} Na przeciwprostokątnej $AC$ trójkąta prostokątnego $ABC$ obrano punkt $D$ taki, że $AB=CD$. Udowodnij, że w trójkącie $ABD$ dwusieczna kąta $A$, środkowa wychodząca z wierzchołka $B$ i~wysokość poprowadzona z wierzchołka $D$ przecinają się w jednym punkcie. \end{problem} \item \begin{problem}{2}{X} Na bokach $BC,CA$ i $AB$ trójkąta $ABC$ wybrano punkty $A_1, B_1, C_1$ takie, że odcinki $AA_1, BB_1, CC_1$ przecinają się w jednym punkcie. Proste $A_1B_1$ i $A_1C_1$ przecinają prostą równoległą do $BC$ przechodzącą przez $A$ w punktach $X$ i $Y$. Wykazać, że $AX=AY$. \end{problem} \item \begin{problem}{2}{X} Dane są trzy okręgi: $o_1,o_2,o_3$ o środkach odpowiednio $O_1,O_2,O_3$. Wspólne styczne wewnętrzne okręgów $o_2$ i $o_3$ przecinają się w punkcie $P_1$, okręgów $o_3$ i $o_1$ w punkcie $P_2$, okręgów $o_1$ i $o_2$ w~punkcie $P_3$. Udowodnij, że proste $O_1P_1,O_2P_2,O_3P_3$ przecinają się w jednym punkcie. \end{problem} \item \begin{problem}{2}{X} W czworokącie wypukłym $ABCD$ przekątne przecinają się w punkcie $E$, a przedłużenia boków $AD$ i $BC$ w $F$. Udowodnij, że środki odcinków $AB, CD, EF$ leżą na jednej prostej. \end{problem} \end{enumerate} \end{lecture}
\begin{lecture}[Pochodne wielomianów]
\subsection{Teoria} \paragraph{Definicje} \begin{defn}[Pochodna wielomianu.] Pochodną wielomianu $f(x) = a_nx^n + a_{n-1}x^{n-1} + \dots + a_2x^2 + a_1x + a_0$ nazywamy wielomian $f'(x)$ postaci \[f'(x) = a_n \cdot n \cdot x^{n-1} + a_{n-1}\cdot (n-1)\cdot x^{n-2} + \dots + a_2\cdot 2 \cdot x + a_1\cdot 1\] \end{defn}
Wszystkie rozważane poniżej wielomiany mają współczynniki rzeczywiste, aczkolwiek to założenie nie jest zawsze potrzebne.
Niech $f(x), g(x)$ będą dowolnymi wielomianami, a $c$ liczbą.
Bezpośrednio z definicji wynikają następujące własności pochodnej: \begin{enumerate} \item $(cf(x))' = cf'(x)$, \item $(f(x) + g(x))' = f'(x) + g'(x)$, \item $f'(x) = 0$ wtedy i tylko wtedy, gdy $f$ jest wielomianem stałym. \end{enumerate}
Pochodna ma jeszcze jedną własność, bardzo ułatwiającą liczenie: \[(f(x)\cdot g(x))' = f'(x)\cdot g(x) + f(x) \cdot g'(x)\] \begin{proof}[Szkic dowodu własności] Jeżeli $f(x) = a_nx^n$ i $g(x) = b_mx^m$ to \[f'(x) = a_nnx^{n-1}, \quad g'(x) = b_mmx^{m-1}, \quad (f(x)g(x))' = (a_nb_mx^{n+m})' = a_nb_m(n+m)x^{n+m-1} = \] \[a_nb_mnx^{n+m-1} + a_nb_mmx^{n+m-1} = a_nnx^{n-1}b_mx^m + a_nx^nb_mmx^{m-1} = f'(x)g(x) + f(x)g'(x).\] Ogólny przypadek sprowadza się do tego przez korzystanie z $(f(x) + g(x))' = f'(x) + g'(x)$. \end{proof}
\emph{Przykład:}
$((x+1)(x^2 - x +1) + 3x)' = (x+1)'(x^2 - x + 1) + (x+1)(x^2 - x + 1)' + 3 = x^2 - x + 1 + (x+1)(2x - 1) + 3 = 3x^2 + 3$. Albo inaczej:
$(x+1)(x^2 - x +1) + 3x = x^3 + 3x + 1$ więc $((x+1)(x^2 - x +1) + 3x)' = (x^3 + 3x + 1)' = 3x^2 + 3$.
% \begin{defn}[Pochodne wyższych rzędów] % Niech $f(x)$ będzie wielomianem. Pierwszą pochodną tego wielomianu % nazywamy $f'(x)$, drugą pochodną nazywamy pochodną pierwszej % pochodnej: $(f'(x))'$ itd. $n$-tą pochodną oznaczamy $f^{(n)}(x)$. % \end{defn}
\paragraph{Pierwiastki} \begin{defn} Mówimy, że liczba $a$ jest $k$-krotnym pierwiastkiem wielomianu $f(x)$ jeżeli $f(x) = (x-a)^kg(x)$ dla pewnego wielomianu $g(x)$.
Ta definicja ma sens tylko jeśli $k > 0$ i tylko dla $k > 0$ definiujemy pierwiastek $k$-krotny. \end{defn}
\emph{``Zwykłe'' pierwiastki wielomianu to dokładnie $1$-krotne pierwiastki. Mówi o tym tw.\ B\'ezout.}
\begin{lem} Niech $k \geq 2$.
Wielomian $W(x)$ ma pierwiastek $k$-krotny $a$ wtedy i tylko wtedy, gdy $W(a) = 0$ i $W'(x)$ ma pierwiastek $k-1$ krotny $a$. \end{lem} \begin{proof} $ \Rightarrow $
Wielomian $W(x)$ możemy przedstawić w postaci $W(x) = (x-a)^k\cdot V(x)$. Oczywiste jest więc, że $W(a) = 0$.
Obliczam $W'$: \[W'(x) = ( (x-a)^k\cdot V(x))' = ((x-a)^k)'V(x) + (x-a)^kV'(x) = \] \[(k(x-a)^{k-1})V(x) + (x-a)^kV'(x) = (x-a)^{k-1}(kV(x)+ (x-a)V'(x))\] Tak więc $W'$ ma pierwiastek $k-1$ krotny $a$.
$ \Leftarrow $
Niech $W'(x) = (x-a)^{k-1}S(x)$.
Załóżmy, że $W(x) = (x-a)^lV(x)$ i $V(x)$ nie jest podzielne przez $x-a$, innymi słowy $V(a) \neq 0$. Wiemy, że $l \geq 1$, chcemy wykazać $l \geq k$.
Załóżmy przeciwnie: $l < k$.
\[(x-a)^{k-1}S(x) = W'(x) = ((x-a)^l)'V(x) + (x-a)^lV'(x) =\] \[l(x-a)^{l-1}V(x) + (x-a)^lV'(x) = (x-a)^{l-1}(lV(x) + (x-a)V'(x))\] \[(x-a)^{k-l}S(x) = lV(x) + (x-a)V'(x)\] \[(a-a)^{k-l}S(a) = lV(a) + (a-a)V'(x),\quad lV(a) = 0, V(a) = 0.\] Doszliśmy do sprzeczności. \end{proof}
\begin{lem}[O maksimum wielomianu] Jeżeli $x_0$ jest takie, że dla $x$ dostatecznie bliskich $x_0$ (tzn. dla $x$ leżących w pewnym ustalonym przedziale otwartym zawierającym $x_0$) zachodzi $W(x) \leq W(x_0)$ to $W'(x_0) = 0$. \end{lem}
\begin{proof}
\emph{Niestety dowód musi być nieco formalny, żeby precyzyjnie ująć ``dla $x$ leżących w pewnym przedziale otwartym zawierającym $x_0$''.}
Niech $M:=W(x_0)$. Rozważmy wielomian \[P(x) := W(x) - M.\] $P(x_0) = W(x_0) - M = 0$. Z twierdzenia B\`ezout wynika, że $P(x) = (x-x_0)Q(x)$.
Będziemy starali się wykazać, że $Q(x_0) = 0$.
Załóżmy, że przedział z zadania to $(x_0 - a, x_0 + a)$ tzn. że dla $x\in (x_0 - a, x_0 +a)$ zachodzi $W(x) \leq W(x_0)$.
Nierówność $W(x) \leq W(x_0)$ jest równoważna $P(x) \leq P(x_0) = 0$, czyli \[(x-x_0)Q(x) \leq 0\]
Dla $x\in (x_0 - a, x_0)$ jest $x-x_0 < 0$, a więc $Q(x) < 0$.
Dla $x\in (x_0, x_0+a)$ zachodzi natomiast $x-x_0 > 0$ a więc $Q(x) >0$.
Stąd wnioskujemy (jako że wielomian jest funkcją ciągłą), że $Q(x_0) = 0$, z twierdzenia B\`ezout $Q(x) = (x-x_0)R(x)$.
Podstawiając: $P(x) = (x-x_0)Q(x) = (x-x_0)^2R(x)$. Wielomian $P(x)$ ma pierwiastek dwukrotny w $x_0$, zatem z poprzedniego lematu jego pochodna ma pierwiastek w $x_0$: \[P'(x_0) = 0\]
Ale $P'(x) = (W(x) - M)' = W'(x) - (M)' = W'(x)$, więc $W'(x_0) = 0$. \end{proof}
\begin{lem}[O minimum wielomianu] Jeżeli $x_0$ jest takie, że dla $x$ dostatecznie bliskich $x_0$ (tzn. dla $x$ leżących w pewnym ustalonym przedziale otwartym zawierającym $x_0$) zachodzi $W(x) \geq W(x_0)$, to $W'(x_0) = 0$. \end{lem} \begin{proof} Wystarczy zastosować powyższy lemat o maksimum wielomianu do wielomianu $-W(x)$. \end{proof}
\subsection{Zadania} \renewcommand{\labelenumi}{}
\begin{enumerate} \item \begin{problem}{1}{Pawłowski -- MKdOlimp} Niech $f(x) = x^n - mx^{n-1} + mx -1$, gdzie $n,m$ ($n \geq 3$) są liczbami naturalnymi. Wyznacz takie wartości $m$ i $n$, aby wielomian $f(x)$ był podzielny przez $(x-1)^2$. \end{problem}
\item \begin{problem}{2}{Pawłowski -- MKdOlimp, XXVIII OM} Wykaż, że dla żadnego $n=1,2,\dots$ wielomian \[Q(x) = 1 + \frac{x}{1!} + \frac{x^2}{2!} + \dots + \frac{x^n}{n!}\] nie ma pierwiastków wielokrotnych. \end{problem}
\item \begin{problem}{2}{Pawłowski -- MKdOlimp, XXXVIII OM} Wielomian $P(x) = a_nx^n +a_{n-1}x^{n-1} + \dots + a_0$ spełnia warunki \[P(1) = 0 \hbox{ oraz } P(x) \geq 0 \hbox{ dla }x\in \mathbb{R}\] Udowodnij, że $a_n + 2a_{n-1} + \dots + (n+1)a_0 = 0$. \end{problem}
\item \begin{problem}{2.5}{Pawłowski -- MKdOlimp} Wielomiany $P(x) = x^n + a_{n-1}x^{n-1}\dots + a_0$ oraz $Q(x) = x^m + b_{m-1}x^{m-1} + \dots + b_0$ spełniają warunek \[P(x)^2 = (x^2 - 1)Q(x)^2 + 1\] Udowodnij, że \[P'(x) = nQ(x)\] \end{problem} \item \begin{problem}{2}{Pawłowski -- KMdOlimp} Udowodnij, że dla każdej liczby naturalnej $n \geq 2$ liczba $n^{n-1} - 1$ jest podzielna przez $(n-1)^2$. \end{problem} \item \begin{problem}{2}{Pawłowski -- KMdOlimp} Udowodnij, że dla każdej liczby naturalnej $n\geq 2$ liczba $n^n - n^2 + n -1$ dzieli się przez $(n-1)^2$. \end{problem} \item \begin{problem}{1}{znane} Uzasadnij, że jeżeli $x_1 \leq x_2 \leq x_3 \dots \leq x_k$ są pierwiastkami wielomianu $W(x)$, to w każdym przedziale (być może będącym punktem) $[x_i, x_{i+1}]$ leży pierwiastek $W'(x)$, wzmacniając tezę wywnioskuj, że jeżeli $W$ ma $n$ pierwiastków, to jego pochodna ma $n-1$. \end{problem} \end{enumerate}
\end{lecture}
\newchapter{Wskazówki do wykładów}{W} \renewcommand{\labelenumi}{}
\newsection{$\varepsilon$-otoczki}{W1} \begin{hint} Rozważ $1/2$-otoczki odcinków. Nie mieszczą się one w $1/2$-otoczce kwadratu (policz!). \end{hint}
\begin{hint} Rozważ dla każdego okręgu $o$ o promieniu $r$ $2r$-otoczkę. Udowodnij, że jeżeli inny okrąg o promieniu nie większym niż $r$ wystaje poza tę otoczkę, to jest rozłączny z~$o$.
Wybieraj okręgi zaczynając od tego o największym promieniu. \end{hint}
\begin{hint} Przenieś w przestrzeń rozumowanie z zadania o kwadracie i okręgach. \end{hint}
\begin{hint} Rozważmy dowolny kwadrat $K$. Obszar, na którym leżą środki okręgów (o promieniu $1$) przecinających $K$ to $1$-otoczka $K$ -- ma ona pole $5+\pi$.
Rozważmy kwadrat o boku $13$ umieszczony centralnie w dużym kwadracie. Ma on pole $13^2 > 20(5+\pi)$, więc istnieje w nim punkt nieleżący w żadnej $\varepsilon$-otoczce. \end{hint}
\begin{hint} Dla każdego $X$ rozważ okrąg o promieniu $\frac{1}{\sqrt{2}}$ i środku w środku $X$. Udowodnij, że jeżeli dwa takie okręgi przecinają się, to $X$-y również. \end{hint}
\begin{hint} Rozważ koła jednostkowe $S_1,S_2,\dots,S_n$ o środkach w $A_1,A_2,\dots,A_n$. Skoro odległości są większe niż $2$, to koła $S_1,S_2,\dots,S_n$ są rozłączne.
Rozważ teraz $S_1 \cap \mathcal{F}, S_2 \cap \mathcal{F}, \dots, S_n \cap \mathcal{F}$. Te figury są także rozłączne, zatem suma ich pól wynosi nie więcej niż $|\mathcal{F}| < \pi$.
Zaznacz dowolny punkt $O$, koło jednostkowe $o$ o środku w $O$ i dowolny punkt $B$ leżący wewnątrz $o$. Zauważ, że w figurze $\mathcal{F} + \vec{BO}$ leży punkt $A_i$ wtedy i tylko wtedy gdy $A_i + \vec{OB}$ leży w $S_i \cap \mathcal{F}$ (zrób rysunek!), czyli gdy $B$ leży w $S_i \cap \mathcal{F} + \vec{A_iO}$.
Figury $S_1 \cap \mathcal{F} + \vec{A_1O}, S_2 \cap \mathcal{F} + \vec{A_2O}, \dots, S_n \cap \mathcal{F} + \vec{A_nO}$ leżą w $o$ i mają łączne pole mniejsze niż $\pi$. Zatem w $o$ istnieje punkt $B_0$ nieleżący w żadnej z tych figur. Wektor $\vec{B_0O}$ jest szukanym wektorem. \end{hint}
\begin{hint} Rozważmy punkty leżące na obwodzie szachownicy i połączmy kolejne odcinkami. Każda z prostych może przecinać najwyżej dwa z tych odcinków, a odcinków jest $28 > 2\cdot 13$. \end{hint}
\newsection{Ciągi jednomonotoniczne}{W2}
\begin{hint} Po ewentualnej zamianie zmiennych można założyć, że $a \geq b$, więc ciągi $(a,b)$ i $(a^2, b^2)$ są niemalejące: \[a^3 + b^3 = \mono{c c}{ a & b\\ a^2 & b^2\\ } \geq \mono{c c}{ a & b\\ b^2 & a^2\\ } =ab^2 + a^2b \] \end{hint}
\begin{hint} \[ \mono{c c}{ a & b\\ \frac{1}{\sqrt{b}} & \frac{1}{\sqrt{a}}\\ } \geq \mono{c c}{ a & b\\ \frac{1}{\sqrt{a}} & \frac{1}{\sqrt{b}}\\ } \] \end{hint}
\begin{hint} Nierówność jest symetryczna (sprawdź!), więc można założyć $a\leq b\leq c$. Wtedy $ \mono{c c c}{ a^2 & b^2 & c^2\\ \frac{1}{b+c} & \frac{1}{a+c} & \frac{1}{a+b}\\ } \geq \mono{c c c}{ a^2 & b^2 & c^2\\ \frac{1}{a+c} & \frac{1}{b+a} & \frac{1}{c+b}\\ } $ oraz $ \mono{c c c}{ a^2 & b^2 & c^2\\ \frac{1}{b+c} & \frac{1}{a+c} & \frac{1}{a+b}\\ } \geq \mono{c c c}{ a^2 & b^2 & c^2\\ \frac{1}{a+b} & \frac{1}{b+c} & \frac{1}{c+a}\\ } $ Łącznie \[ 2\left( \frac{a^2}{b+c} + \frac{b^2}{a+c} + \frac{c^2}{a+b}\right) \geq \frac{a^2 + b^2}{a + b} + \frac{b^2 + c^2}{b + c} + \frac{c^2 + a^2}{c + a} \geq a + b + c\] \end{hint}
\begin{hint} \[ \mono{c c c}{ a & b & c\\ a^2 & b^2 & c^2\\ } \geq \mono{c c c}{ a & b & c\\ b^2 & c^2 & a^2\\ }, \mono{c c c}{ a & b & c\\ c^2 & a^2 & b^2\\ } \] \end{hint}
\begin{hint} Rozważmy $n$ różnych permutacji ciągów $(a_1,a_2,\dots,a_n)$ i $(b_1,\dots,b_n)$ i zsumujmy $n$ nierówności. \end{hint}
\begin{hint} Aby udowodnić pierwszą część nierówności, rozważmy $n$ ciągów o wyrazach $(\sqrt[n]{a_1}, \sqrt[n]{a_2}, \dots, \sqrt[n]{a_n})$. Wtedy w twierdzeniu lewa strona nierówności wynosi $a_1 + \dots +a_n$. Trzeba tak ustawić permutacje, żeby otrzymać z prawej strony $n \sqrt[n]{a_1a_2 \dots a_n}$.
Do dowodu drugiej nierówności stosujemy nierówność Czebyszewa z obydwoma ciągami równymi $(a_1, \dots, a_n)$. \end{hint}
\begin{hint} Ze względu na symetryczność zakładamy $a \leq b\leq c$. Rozważmy ciągi $(a^2, b^2, c^2)$, $(a^2, b^2, c^2)$, $(a^3, b^3, c^3)$. \end{hint}
\begin{hint} Załóżmy $a\leq b\leq c$. Najpierw stosujemy nierówność Czebyszewa, aby otrzymać \[ \frac{b+c}{\sqrt{a}} + \frac{c + a}{\sqrt{b}} + \frac{a + b}{\sqrt{c}} \geq \frac{1}{3}(b+c + c + a + a + b)\left(\frac{1}{\sqrt{a}} + \frac{1}{\sqrt{b}} + \frac{1}{\sqrt{c}}\right). \] Pozostaje uzasadnić, że ostatni nawias przyjmuje wartości nie mniejsze niż $3$. Można tutaj stosować nierówność pomiędzy średnimi potęgowymi lub klasyczne nierówności pomiędzy średnimi. \end{hint}
\newsection{Menelaos i Ceva}{W3}
\begin{hint} We wszystkich trzech przypadkach korzystamy oczywiście z twierdzenia Cevy. \renewcommand{\labelenumi}{\theenumi} \begin{enumerate} \item[(a)] Należy znaleźć trójkąty podobne, zapisać odpowiednie proporcje i wyciągnąć wnioski. \item[(b)] Wystarczy zauważyć, jak środkowe dzielą boki. \item[(c)] Trzeba trzykrotnie skorzystać z twierdzenia o dwusiecznej. \end{enumerate} \renewcommand{\labelenumi}{} \end{hint}
\begin{hint} Wystarczy zapisać twierdzenie Menelaosa dla dwóch sąsiednich trójkątów (dopełniających się do dużego trójkąta). \end{hint}
\begin{hint} Z twierdzenia Menelaosa dla trójkąta $DBC$ wynika, że $DK=KC$. To już wystarczy do wyznaczenia miary kąta. \end{hint}
\begin{hint} Trzeba skorzystać z twierdzenia o dwusiecznej i twierdzenia Talesa (skoro wysokość poprowadzona z~$D$ jest równoległa do $BC$), a otrzymane zależności sprowadzić do twierdzenia Cevy. \end{hint}
\begin{hint} Należy skorzystać z trójkątów podobnych (kąty wierzchołkowe przy $B_1$ i $C_1$) oraz twierdzenia Cevy dla trójkąta $ABC$. \end{hint}
\begin{hint} Wystarczy znaleźć pary trójkątów podobnych i zapisać proporcje, korzystając na przykład z długości promieni. Łącząc wszystkie zależności, otrzymujemy założenie twierdzenia odwrotnego do twierdzenia Cevy. \end{hint}
\begin{hint} Warto zastosować jednokładność o środku w środku ciężkości trójkąta $BDF$ i skali $-\frac{1}{2}$ oraz przedłużyć bok równoległy do $DB$ aż do przecięcia z $CD$. Możemy zauważyć, że stosunki boków z~twierdzenia Menelaosa dla trójkąta $BDF$ równe są stosunkom boków z nowo otrzymanego trójkąta. \end{hint}
\newsection{Pochodne wielomianów}{W4}
\begin{hint} Podzielność zachodzi wtedy i tylko wtedy, gdy $f(1) = 0$ i $f'(1) = 0$. Otrzymujemy równanie, które zwija się do $(m-1)(n-2) = 2$. \end{hint}
\begin{hint} Jeżeli $Q(x)$ ma pierwiastek wielokrotny $a$, to $Q(a) = 0$ i $Q'(a) = 0$, więc $Q(a) - Q'(a) = \frac{a^n}{n!} = 0$. \end{hint}
\begin{hint} Z lematu o minimum wielomianu $P'(1) = 0$.
Stąd $0 = (n+1)P(1) - P'(1)$, a to jest teza. \end{hint}
\begin{hint} Po pierwsze $m = n-1$.
Zauważmy, że $P(x)$ i $Q(x)$ nie mają wspólnych dzielników tj.\ nie istnieje wielomian $A(x)$ inny niż $\pm 1$ taki, że $A(x) | P(x)$ i $A(x) | Q(x)$.
Zaiste dowolny wielomian $A(x)$ dzielący $P(x)$ i $Q(x)$ dzieli także $P(x)^2 - (x^2 - 1)Q^2(x) = 1$, więc musi być równy $\pm 1$.
Bierzemy pochodną obu stron równania: \[2P(x)P'(x) = Q(x)\cdot (pewien wielomian)\]
Skoro $P(x)$ i $Q(x)$ nie mają wspólnych dzielników, to $Q(x) | 2P'(x)$, z porównania stopni $P'(x) = rQ(x)$, gdzie $r$ jest liczbą rzeczywistą.
Z drugiej strony współczynnik przy najwyższym stopniu $P'(x)$ wynosi $n$, więc $P'(x) = nQ(x)$. \end{hint}
\begin{hint} Rozważmy wielomian $x^{n-1} - 1 = (x-1)Q(x)$. Chcemy $n-1 | Q(n)$.
Liczymy pochodną: $(n-1)x^{n-2} = (x-1)Q'(x) - Q(x)$. Podstawiając $x=n$ otrzymujemy $n-1 | Q(n)$. \end{hint}
\begin{hint} Najprościej skorzystać z poprzedniego zadania: $n^n \equiv n \mod (n-1)^2$, więc $n^n - n^2 + n - 1 \equiv -n^2 + 2n -1 = -(n-1)^2 \equiv 0 \mod (n-1)^2$. \end{hint}
\begin{hint} Do rozważenia są dwa przypadki: $x_i = x_{i+1}$ oraz $x_i \neq x_{i+1}$. W pierwszym przypadku zastosuj lemat o~pierwiastkach wielokrotnych, a w drugim uzasadnij, że wielomian $W$ musi mieć minimum lub maksimum (w sensie lematu o maksimum) na przedziale $(x_i, x_{i+1})$. \end{hint}
\begin{thebibliography}{} \bibitem{5} Czasopismo ``Delta'': \url{http://www.mimuw.edu.pl/delta/}, \bibitem{3} Koło matematyczne II LO w Gorzowie \url{http://www.2lo.gorzow.pl/instytuty/kolko_mat/}, \bibitem{1} Koło matematyczne V LO w Krakowie, \bibitem{8} Koło matematyczne XIV LO im. Staszica w Warszawie \url{http://wm.staszic.waw.pl/}, \bibitem{7} Obóz matematyczny OM w Zwardoniu \url{http://www.om.edu.pl/}, \bibitem{6} Olimpiady Matematyczne: Australii, Bułgarii, Hiszpanii, Kostaryki, Polski, Wielkiej Brytanii, ZSRR, \bibitem{2} Olsztyńskie warsztaty matematyczne, \bibitem{11} Pawłowski H., ,,Kółko matematyczne dla olimpijczyków'', \bibitem{4} Portal Mathlinks \url{http://www.mathlinks.ro/}, \bibitem{10} Prasolov V. V. ,,Plane Geometry'', \bibitem{9} Wakacyjne Warsztaty Wielodyscyplinarne \url{http://warsztatywww.wikidot.com/}. \end{thebibliography}
\end{document} |