\documentclass[12pt]{article}
\usepackage[T2A]{fontenc}
\usepackage[cp866]{inputenc}
\usepackage[russian]{babel}
\usepackage{latexsym,amssymb,amsthm}
\usepackage{amsmath}
%%\usepackage{wrapfig}
% \RequirePackage[dvips]{graphicx}
%%\usepackage{array}

\usepackage{epsf,epic,eepic}
% \input ris.tex
% \input cells.sty
% \addrisoption{\risleftfalse}

\DeclareRobustCommand{\No}{\ifmmode{\nfss@text{\textnumero}}\else\textnumero\fi}

\oddsidemargin=0pt
\textwidth=159mm
\headheight=0pt
\headsep=0pt
\topmargin=0pt
\textheight=240mm

%%
%% Три точки для обозначения делимости
%%
\catcode`\@=11
\def\kratno{\mathrel{\smash{\lower.5ex\hbox{$\,\vdots\,$}}}}
% Это прямые три точки для обозначения делимости
\def\nekratno{\mathrel{\mathpalette\c@ncel\kratno}}
\def\c@ncel#1#2{\m@th\ooalign{$\hfil#1\mkern1mu/\hfil$\crcr$#1#2$}}
% Это перечеркнутые три точки для обозначения неделимости
\def\divis{\smash{\lower.1ex\hbox{\,\hbox{.}\kern-.22em\lower-.6ex\hbox{.}
\kern-.52em\lower-1.2ex\hbox{.}\,}} }
% А это наклонные...

\hyphenation{чис-ло чис-ла чис-лу чис-лом чис-ле чис-лам чис-ла-ми чис-лах
че-ты-рех-уголь-ник че-ты-рех-уголь-ни-ка пря-мо-уголь-ник тре-уголь-ни-ка
тре-уголь-ни-ков вне-впи-сан-ной вне-впи-сан-ных}

\def\signed(#1){{\unskip\nobreak\hfil\penalty50\hskip1em\hbox{}\nobreak\hfil
                 \rm(\small\it#1\/\rm)\parfillskip=0pt\finalhyphendemerits=0\par}}
        % macro for authorship's signature, from TeXbook
\def\be{\signed(С.~Берлов)}
\def\fp{\signed(Ф.~Петров)}
\def\frank{\signed(В.~Франк)}
\def\bah{\signed(Ф.~Бахарев)}
\def\guas{\signed(А.~Голованов)}
\def\as{\signed(А.~Смирнов)}
\def\dvk{\signed(Д.~Карпов)}
\def\is{\signed(Р.~Исмаилов)}
\def\kk{\signed(К.~Кохась)}
\def\kuz{\signed(А.~Кузнецов)}
\def\hr{\signed(А.~Храбров)}
\def\io{\signed(О.~Иванова)}
\def\sop{\signed(Е.~Сопкина)}
\def\sviv{\signed(С.~Иванов)}
\def\r7{\signed(Р.~Семизаров)}
\def\suk{\signed(К.~Сухов)}
\def\dr{\signed(Д.~Ростовский)}
\def\pas{\signed(А.~Пастор)}
\def\yul{\signed(Ю.~Лифшиц)}
\def\azh{\signed(А.~Железняк)}
\def\dm{\signed(Д.~Максимов)}
\def\asol{\signed(А.~Солынин)}
\def\chuh{\signed(А.~Чухнов)}
\def\zh{\signed(Жюри)}

\sloppy
\pagestyle{empty}

\def\q#1.{{\bf #1. }}
\def\dotline{\smallskip\hbox to \hsize{\dotfill}\medskip}

\begin{document}

\centerline{\sc САНКТ-ПЕТЕРБУРГСКАЯ}
\centerline{\sc ОЛИМПИАДА ШКОЛЬНИКОВ 2018 года ПО МАТЕМАТИКЕ}
\centerline{\sc II тур. \ 9 класс.}
\medskip
\hrule
\bigskip

\q1. Докажите, что для каждого натурального числа $N$
найдется такое целое $k\geq 0$, что $N$ удастся записать в
виде суммы чисел $2^0$, $2^1$, $2^2$, \dots,~$2^k$, каждое
из которых участвует в этой сумме 1 или 2 раза. (Например,
$12=2^0+2^0+2^1+2^2+2^2$.)
\signed(М.~Антипов)

\q2. Дано нечётное натуральное число $n>1$. На доске записаны
числа $n$, $n+1$, $n+2$, \dots, $2n-1$. Докажите, что можно
стереть одно из них так, чтобы сумма оставшихся чисел не
делилась ни на одно из оставшихся чисел.
\be

\q3. Дан остроугольный треугольник $ABC$. На отрезке $AC$ и
на продолжении стороны $BC$ за точку $C$ выбираются
переменные точки $X$ и $Y$ соответственно таким образом, что
${\angle ABX\!+\!\angle CXY=90^\circ\!}$. Точка~$T$~--- проекция
точки~$B$ на прямую $XY$. Докажите, что все такие точки~$T$
лежат на одной прямой.
\be

\q4. На круглом ожерелье висят $n>3$ бусинок, каждая
покрашена в~красный или синий цвет. Если у какой-то бусинки
соседние с ней бусинки покрашены одинаково, ее можно
перекрасить (из красного в синий или из синего в красный).
При каких $n$ из любой исходной раскраски бусинок можно
сделать ожерелье, в котором все бусинки покрашены одинаково?
\be

\dotline

\centerline{Олимпиада 2018 года. II тур. 9 класс. Выводная аудитория.}
\smallskip

\q5. Можно ли нарисовать на плоскости треугольник $ABC$ и
отметить на той же плоскости  две точки  $X$ и $Y$, так что
$AX=BY=AB$, $BX=CY=BC$,  $CX=AY=CA$?
\signed(М.~Иванов)

\q6. Даны два нечетных натуральных числа $a$ и $b$. Докажите, что
существует такое натуральное $k$, что хотя бы одно из чисел $b^k-a^2$ и
$a^k-b^2$ делится на $2^{2018}$.
\guas

\q7. В клетчатом квадрате $10\times 10$ (стороны клеток имеют
единичную длину) выбрали $n$ клеток, в каждой из них
нарисовали одну из диагоналей и поставили на этой диагонали
стрелочку в одном из двух направлений. Оказалось, что для
любых двух стрелочек либо конец одной из них совпадает с
началом другой, либо расстояние между их концами не меньше 2.
При каком наибольшем $n$ это возможно?
\signed(М.~Антипов)

\clearpage

\centerline{\sc САНКТ-ПЕТЕРБУРГСКАЯ}
\centerline{\sc ОЛИМПИАДА ШКОЛЬНИКОВ 2018 года ПО МАТЕМАТИКЕ}
\centerline{\sc II тур. \ 10 класс.}
\medskip
\hrule
\medskip

\q1. Миша приехал в страну, в которой $n$ городов и каждые два 
напрямую соединены дорогой.
Он собирается, начав с~некоторого города, объехать несколько городов, не
заезжая ни в один город дважды. Каждый раз, пока Миша едет по дороге,
президент разрушает $k$ дорог, ведущих из города, в который
ведет эта дорога. (А если там нет такого количества уцелевших дорог --- разрушает
все оставшиеся, кроме той, по которой едет Миша.) Какое наибольшее
количество городов сможет объехать Миша, независимо от действия
президента?
\signed(П.~Ходунов, А.~Кузнецов, И.~Лосев)

\q2. Раскрасим вершины 2018-угольника в два цвета так, чтобы любые две
соседние вершины были разного цвета. Если сумма углов при вершинах одного
цвета равна сумме углов при вершинах другого цвета, будем называть такой
2018-угольник \textit{интересным}. В~выпуклом 2019-уголь\-ни\-ке отметили одну
вершину. Оказалось, что при удалении любой неотмеченной вершины остается
интересный 2018-угольник. Докажите, что при удалении отмеченной вершины
также остается интересный 2018-угольник.
\kuz

\q3. Вдоль окружности расположено $n$ монет, каждая лежит орлом или решкой вверх. 
Если две соседние монеты лежат одинаково (обе орлом или обе решкой), разрешается обе перевернуть. 
Сколько имеется вариантов расположения монет, которые нельзя получить друг из друга, применяя такие операции?

\q4. Коэффициенты многочлена $f(x)$ --- целые числа, по модулю не превосходящие 5\,000\,000. 
При этом каждое из уравнений 
$$
f(x)=x, \qquad f(x)=2x, \qquad \dots,  \qquad f(x)=20x
$$ 
имеет целый корень. Докажите, что $f(0)=0$.
\signed(М.~Антипов)

\dotline

\centerline{Олимпиада 2018 года. II тур. 10 класс. Выводная аудитория.}
\smallskip

\q5. Дан вписанный четырехугольник $ABCD$. Прямая, перпендикулярная $BD$, 
пересекает отрезки $AB$, $BC$ и лучи $DA$, $DC$ 
в точках $P$, $Q$, $R$, $S$ соответственно. Известно, что $PR=QS$. 
Докажите, что середина отрезка $PQ $ равноудалена от точек $A$ и $C$.
\kuz

\q6. Пусть $a$, $b$, $c$, $d>0$. Докажите неравенство
$$
a^4+b^4+c^4+d^4-4abcd\geqslant 4(a-b)^2\sqrt{abcd}.
$$
% ФП по мотивам 436
\signed(С.~Горский, Ф.~Петров) 

\q7. Шашка передвигается из левого нижнего угла доски
$100\times 100$ в правый верхний угол, на каждом шагу перемещаясь на одну клетку вправо или на одну клетку 
вверх. Пусть $a$~--- число путей, в которых ровно 70 шагов шашка совершает
под диагональю, идущей из левого нижнего угла в правый верхний, а $b$~---
число путей, в~которых таких шагов ровно 110. Что больше: $a$ или $b$?
\signed(Фольклор)

\clearpage

\centerline{\sc САНКТ-ПЕТЕРБУРГСКАЯ}
\centerline{\sc ОЛИМПИАДА ШКОЛЬНИКОВ 2018 года ПО МАТЕМАТИКЕ}
\centerline{\sc II тур. \ 11 класс.}
\medskip
\hrule
\bigskip

\q1. Прямая $\ell$ на координатной плоскости не параллельна осям
координат. При каком наименьшем $d$ можно утверждать, что расстояние от
некоторой точки с целыми координатами до $\ell$ не превосходит $d$?
\guas

\q2. У Васи есть 100 карточек трех цветов, карточек каждого цвета не больше~50.
Докажите, что он может выложить из них квадрат ${10\times 10}$ так, чтобы
любые две соседние (по стороне) карточки оказались разного цвета.
\dm

\q3. На биссектрисе угла $B$ остроугольного треугольника $ABC$
выбрана точка $T$. Окружность $S$, построенная на $BT$ как на
диаметре, пересекает стороны $AB$ и $BC$ в точках $P$ и $Q$
соответственно. Окружность, проходящая через вершину $A$ и
касающаяся $S$ в точке $P$, вторично пересекает прямую $AC$ в точке
$X$. Окружность, проходящая через вершину~$C$ и~касающаяся $S$ в
точке $Q$, вторично пересекает прямую $AC$ в~точке~$Y$. Докажите, что
$TX=TY$.
\be

\q4. Известно, что квадратный трехчлен 
$$
(b+c)x^2+(a+c)x+(a+b)
$$ 
не имеет корней. Докажите, что $4ac-b^2\leq 3a(a+b+c)$.
\suk

\dotline

\centerline{Олимпиада 2018 года. II тур. 11 класс. Выводная аудитория.}
\smallskip

\q5. Правильный шестиугольник разбит на равные ромбы со сторонами,
параллельными сторонам шестиугольника. На трёх сторонах шестиугольника,
среди которых нет соседних, задали направления в порядке обхода шестиугольника
против часовой стрелки. Затем на каждой стороне ромба поставили стрелку,
направленную так же, как параллельная этой стороне сторона шестиугольника.
Докажите, что не существует замкнутого пути, идущего по стрелкам.
\signed(Ю.~Базлов)

\q6. Положительные иррациональные числа $\alpha$ и $\beta$ таковы,
что при всех $x>0$ выполнено равенство $[\alpha[\beta x]]=[\beta[\alpha x]]$. 
Докажите, что $\alpha=\beta$.
\signed(J. Lagarias, T. Marayama, D. Richman)

\q7. На окружности $S$ отмечены  точки $A$ и $B$.
Касательные к~ок\-руж\-ности $S$, проведенные в точках $A$ и $B$,
пересекаются в точке~$C$. Пусть $M$~--- середина отрезка $AB$.
Окружность~$S_1$, проходящая через точки $M$ и~$C$, вторично пересекает
отрезок $AB$ в~точке $D$ и~окружность $S$ --- в~точках $K$ и $L$.
Докажите, что касательные, проведенные к окружности~$S$ в~точках
$K$ и $L$, пересекаются на отрезке $CD$.
\signed(Д.~Столяров)

\end{document}