|
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} |
Materiały z PROSerw 2010
