\nopagenumbers

\input amssym.def

\input amssym.tex

\def\geq{\geqslant}

\def\leq{\leqslant}

\centerline{LI УРАЛЬСКИЙ ТУРНИР ЮНЫХ МАТЕМАТИКОВ. КИРОВ, 16--22.02.2018}

\centerline{\bf МАТЕМАТИЧЕСКИЙ БОЙ \No 3. 21.02.2018}

\centerline{\bf СТАРШАЯ ГРУППА, ВЫСШАЯ ЛИГА}

\medskip 

1. На прямой отмечены все точки с целыми координатами. Конь начинает 
прыгать из одной из этих точек. На $k$-ом шаге конь может прыгнуть по прямой 
на любое натуральное расстояние, не превосходящее $\sqrt k$. Может ли конь 
побывать во всех отмеченных точках ровно по одному разу? 
(Украина, "В мире математики", 2017, \No1)

2. Клетки таблицы $2017\times 2017$ раскрашены в черный и белый цвета. 
Последовательность клеток $S_1$, $S_2$, \dots, $S_m$ назовём {\it путём}, 
если все эти клетки одного цвета, каждые два последовательных члена 
последовательности граничат по стороне, а никакие несоседние члены 
последовательности общей стороны не имеют. Оказалось, что все чёрные клетки 
таблицы образуют один путь, а все белые клетки -- другой. Докажите, 
что центральная клетка является одним из концов одного из этих двух путей. 
(Переработано из задачи Google Code Jam, 2010)

3. Натуральные числа $n$ и $k$ удовлетворяют неравенству $1\leq n\leq k$. 
Известно, что для любого натурального делителя $d$ числа $n$ число $d^k+k$ 
является простым. Докажите, что число $n+k$ простое. 
(Киев, отбор на Всеукраинскую олимпиаду по математике, 2018)

4. Точки $P$ и $Q$ внутри параллелограмма $ABCD$ таковы, что 
треугольники $ABP$ и $BCQ$ -- равносторонние. Докажите, что пересечение 
перпендикуляра к $PD$, восставленного в точке $P$, и перпендикуляра к $DQ$, 
восставленного в точке $Q$, лежит на высоте треугольника $ABC$, 
проведённой из вершины $B$. 
(Канада, 2017)

5. В школе учатся 2018 учеников, а в школьной столовой продаются 
пирожки 25 видов. Каждый школьник любит пирожки хотя бы одного вида; 
каждый пирожок нравится хотя бы одному школьнику. Группу школьников 
назовём {\it всеядной}, если в ней есть любители всех видов пирожков. 
{\it Контрольная группа} -- это группа школьников, в которой есть хотя бы 
один представитель каждой всеядной группы. Оказалось, что из контрольной 
группы $G$ нельзя удалить непустое множество школьников так, чтобы она 
осталась контрольной. Докажите, что есть вид пирожков, который в $G$ любят все. 
(Турция, 2017, 2 этап)

6. Точка $D$ лежит внутри треугольника $ABC$. Биссектрисы углов $BAC$ и $ACD$ 
пересекаются в точке $N$. Биссектриса угла $ABD$ и прямая, содержащая 
биссектрису угла $BDC$, пересекаются в точке $T$. Прямые $AB$ и $CD$ 
пересекаются в точке $Q$. Докажите, что точки $N$, $T$ и $Q$ лежат 
на одной прямой. 
(О.Карлюченко, "В мире математики", 2016, \No3)

7. На доске в ряд написано 100 целых чисел. Петя и Вася играют в игру. 
Ходят по очереди, начинает Петя. Своим ходом он может выбрать несколько 
(быть может, одно) идущих подряд чисел, после чего Вася может либо прибавить 
ко всем выбранным Петей числам единицу, либо вычесть из всех выбранных Петей 
чисел единицу. Докажите, что Петя может действовать так, что через некоторое 
время он получит не менее 98 чисел, кратных 4. 
(Германия, отбор на ММО, 2018)

8. Попарно различные положительные числа $x_0$, $x_1$, \dots, $x_n$ меньше 1. 
Докажите, что существует пара $(x_i, x_j)$, для которой 
$0<x_ix_j(x_i-x_j)<{1\over 3n}$. 
(Фольклор)

\medskip 

\centerline{LI УРАЛЬСКИЙ ТУРНИР ЮНЫХ МАТЕМАТИКОВ. КИРОВ, 16--22.02.2018}

\centerline{\bf МАТЕМАТИЧЕСКИЙ БОЙ \No 3. 21.02.2018}

\centerline{\bf СТАРШАЯ ГРУППА, ПЕРВАЯ ЛИГА}

\medskip 

1. На прямой отмечены все точки с целыми координатами. Конь начинает прыгать 
из одной из этих точек. На $k$-ом шаге конь может прыгнуть по прямой 
на любое натуральное расстояние, не превосходящее $\sqrt k$. Может ли конь 
побывать во всех отмеченных точках ровно по одному разу? 
("В мире математики", 2017, \No1)

2. На прямой отмечены 100 точек. Все попарные расстояния между отмеченными 
точками различны. Оказалось, что сумма расстояний от любой отмеченной точки 
до двух ближайших отмеченных -- целое число. Какое наибольшее количество 
нецелых чисел может быть среди 99 расстояний между соседними отмеченными 
точками? 
(С.Берлов, Н.Власова)

3. Докажите, что для любого натурального $n$ существует натуральное $k$ 
такое, что у числа $k+n$ ровно на один простой делитель больше, чем у $k$. 
(Турция, 2017, 2 этап)

4. На сторонах $AB$ и $AD$ ромба $ABCD$ выбраны точки $E$ и $F$ соответственно 
таким образом, что $AE=DF$. Прямые $BC$ и $DE$ пересекаются в точке $P$, 
а прямые $CD$ и $BF$ пересекаются в точке $Q$. Докажите, что 
точки $P$, $A$, $Q$ лежат на одной прямой. 
(Румыния, национальный этап, 2004)

5. В школе учатся 2018 учеников, а в школьной столовой продаются 
пирожки 25 видов. Каждый школьник любит пирожки хотя бы одного вида; 
каждый пирожок нравится хотя бы одному школьнику. Группу школьников 
назовём {\it всеядной}, если в ней есть любители всех видов пирожков. 
{\it Контрольная группа} -- это группа школьников, в которой есть 
хотя бы один представитель каждой всеядной группы. Оказалось, что 
из контрольной группы $G$ нельзя удалить непустое множество школьников 
так, чтобы она осталась контрольной. Докажите, что есть вид пирожков, 
который в $G$ любят все. 
(Турция, 2017, 2 этап)

6. Точка $D$ лежит внутри треугольника $ABC$. Биссектрисы углов $BAC$ и $ACD$ 
пересекаются в точке $N$. Биссектриса угла $ABD$ и прямая, содержащая 
биссектрису угла $BDC$, пересекаются в точке $T$. Прямые $AB$ и $CD$ 
пересекаются в точке $Q$. Докажите, что точки $N$, $T$ и $Q$ лежат 
на одной прямой. 
(О. Карлюченко, "В мире математики", 2016, \No3)

7. На доске в ряд написано 100 целых чисел. Петя и Вася играют в игру. 
Ходят по очереди, начинает Петя. Своим ходом он может выбрать несколько 
(быть может, одно) идущих подряд чисел, после чего Вася может либо прибавить 
ко всем выбранным Петей числам единицу, либо вычесть из всех выбранных Петей 
чисел единицу. Докажите, что Петя может действовать так, что через некоторое 
время он получит не менее 99 чисел, кратных 3. 
(Германия, отбор на ММО, 2018)

8. Положительные числа $a$, $b$, $c$ и $d$ удовлетворяют 
равенствам $1+a^2=c^2$ и $b^2+d^2=1$. Докажите неравенство 
$c+d\leq {a\over b}+{b\over a}$. 
(Республика Сербская (Босния и Герцеговина), респубоиканский этап, 
второй разряд, 2002)

\medskip 

\centerline{LI УРАЛЬСКИЙ ТУРНИР ЮНЫХ МАТЕМАТИКОВ. КИРОВ, 16--22.02.2018}

\centerline{\bf МАТЕМАТИЧЕСКИЙ БОЙ \No 3. 21.02.2018}

\centerline{\bf СТАРШАЯ ГРУППА, ВТОРАЯ ЛИГА}

\medskip 

1. На прямой отмечены все точки с целыми координатами. Конь начинает 
прыгать из одной из этих точек. На $k$-ом шаге конь может прыгнуть 
по прямой на любое натуральное расстояние, не превосходящее $\sqrt k$. 
Может ли конь побывать во всех отмеченных точках ровно по одному разу? 
(Украина, "В мире математики", 2017, \No1)

2. Имеется 10 одинаковых по виду монет, среди которых две фальшивые, 
а 8 настоящих. Известно, что настоящие монеты весят одинаково 
и что одна из фальшивых монет легче, а другая -- тяжелее настоящей. 
Каким наименьшим числом взвешиваний на чашечных весах можно выделить 
хотя бы одну настоящую монету? 
(С.Токарев. Ярославские дистанционные игры)

3. Докажите, что для любого натурального $n$ существует натуральное $k$ 
такое, что у числа $k+n$ ровно на один простой делитель больше, чем у $k$. 
(Турция, 2017, 2 этап)

4. На сторонах $AB$ и $AD$ ромба $ABCD$ выбраны точки $E$ и $F$ соответственно 
таким образом, что $AE=DF$. Прямые $BC$ и $DE$ пересекаются в точке $P$, 
а прямые $CD$ и $BF$ пересекаются в точке $Q$. Докажите, что 
точки $P$, $A$, $Q$ лежат на одной прямой. 
(Румыния, национальный этап, 2004)

5. В школе учатся 2018 учеников, а в школьной столовой продаются 
пирожки 25 видов. Каждый школьник любит пирожки хотя бы одного вида; 
каждый пирожок нравится хотя бы одному школьнику. Группу школьников 
назовём {\it всеядной}, если в ней есть любители всех видов пирожков. 
{\it Контрольная группа} -- это группа школьников, в которой есть хотя бы 
один представитель каждой всеядной группы. Оказалось, что из контрольной 
группы $G$ нельзя удалить непустое множество школьников так, чтобы она 
осталась контрольной. Докажите, что есть вид пирожков, который в $G$ любят все. 
(Турция, 2017, 2 этап)

6. Точка $D$ лежит внутри треугольника $ABC$. Биссектрисы углов $BAC$ и $ACD$ 
пересекаются в точке $N$. Биссектриса угла $ABD$ и прямая, содержащая 
биссектрису угла $BDC$, пересекаются в точке $T$. Прямые $AB$ и $CD$ 
пересекаются в точке $Q$. Докажите, что точки $N$, $T$ и $Q$ лежат 
на одной прямой. 
(О. Карлюченко, Украина, "В мире математики", 2016, \No3)

7. На доске в ряд написано 100 целых чисел. Петя и Вася играют в игру. 
Ходят по очереди, начинает Петя. Своим ходом он может выбрать несколько 
(быть может, одно) идущих подряд чисел, после чего Вася может либо прибавить 
ко всем выбранным Петей числам единицу, либо вычесть из всех выбранных Петей 
чисел единицу. Докажите, что Петя может действовать так, что через некоторое 
время он получит не менее 99 чисел, кратных 3. 
(Германия, отбор на ММО, 2018)

8. Двоих солдат тренируют рыть окопы. В 12:00 первый солдат начал рыть 
с постоянной скоростью окоп по прямой из точки A в точку B. Через час 
второй солдат, начиная с точки A, стал засыпать вырытый окоп 
тоже с постоянной скоростью. Когда первый дошел до половины пути, 
к нему подошел старшина и стал показывать, как надо копать, заменив 
на 15 минут первого солдата. Потом он подошел ко второму и показал ему, 
как надо закапывать окоп, заменив того на 15 минут. Известно, что старшина 
копает и закапывает в полтора раза быстрее солдат. К сожалению, 
скорость работы нерадивых солдат после вмешательства старшины не изменилась. 
До точки B оба солдата дошли одновременно в 15:00. На сколько задержалась 
бы работа (от момента начала рытья до момента засыпки), если бы старшина 
не вмешивался? 
(С.Волчёнков)

\medskip 

\centerline{LI УРАЛЬСКИЙ ТУРНИР ЮНЫХ МАТЕМАТИКОВ. КИРОВ, 16--22.02.2018}

\centerline{\bf МАТЕМАТИЧЕСКИЙ БОЙ \No 3. 21.02.2018}

\centerline{\bf МЛАДШАЯ ГРУППА, ВЫСШАЯ ЛИГА}

\medskip 

1. По кругу стоят 111 башен, в которых сидят 200 рыцарей, 100 из которых -- 
чёрные, а остальные -- белые. В конце каждого часа каждый черный рыцарь 
перемещается в соседнюю башню по часовой стрелке, а каждый белый рыцарь 
перемещается в соседнюю башню против часовой стрелки. Найдите наименьшее 
натуральное $n$ такое, что в течение любых $n$ часов заведомо найдется момент, 
когда в какой-то башне не будет ни одного рыцаря.  
(P.Calabek, Чехия, 2018, I этап, категория C)

2. У Васи есть набор из $n$ карточек, на которых написаны натуральные числа 
от 1 до $n$ (каждое по одному разу). Он разложил их в ряд в некотором порядке. 
Петя под ними положил пустые карточки. На первой из них он написал число 
с первой Васиной карточки, на второй -- удвоенное число со второй Васиной 
карточки, на третьей -- утроенное число с третьей Васиной карточки и т.д., 
на $n$-ой карточке -- число с $n$-ой Васиной карточке, умноженное на $n$. 
Оказалось, что числа на Петиных карточках идут в порядке возрастания. 
В каком порядке могли располагаться Васины карточки? 
(Республика Сербская (Босния и Герцеговина), второй разряд, 1994)

3. Найдите все натуральные числа $a$ и $b$, для которых число $a^2+a+1$ 
делится на $ab-1$. 
(Белоруссия, 2018, 3 этап)

4. Ненулевые числа $a$, $b$, $c$ и $d$ удовлетворяют равенствам $a+b+c+d=0$ 
и ${1\over a}+{1\over b}+{1\over c}+{1\over d}+{1\over abcd}=0$. Чему может 
равняться выражение $(ab-cd)(c+d)$? 
(Босния и Герцеговина, соревнование Тузланского кантона, 2013, I разряд)

5. На доске в ряд написано 100 натуральных чисел. Петя и Вася играют в игру. 
Ходят по очереди, начинает Петя. Своим ходом он может выбрать несколько 
(быть может, одно) идущих подряд чисел, после чего Вася может либо прибавить 
ко всем выбранным Петей числам единицу, либо вычесть из всех выбранных Петей 
чисел единицу. Докажите, что Петя может действовать так, что через некоторое 
время он получит не менее 98 чисел, кратных 4. 
(Германия, отбор на ММО, 2018)

6. На прямой отмечены 30 точек. Все попарные расстояния между отмеченными 
точками различны. Оказалось, что сумма расстояний от любой отмеченной точки 
до двух ближайших отмеченных -- целое число. Какое наибольшее количество 
нецелых чисел может быть среди 29 расстояний между соседними отмеченными 
точками? 
(С.Берлов, Н.Власова)

7. Положительные числа $a$, $b$, $c$ и $d$ удовлетворяют 
равенствам $1+a^2=c^2$ и $b^2+d^2=1$. Докажите неравенство 
$c+d\leq {a\over b}+{b\over a}$. 
(Республика Сербская (Босния и Герцеговина), второй разряд, 2002)

8. Четырехугольник $ABCD$ таков, что $AB=CD$ и $BC=AD$. Точки $P$ и $Q$ 
внутри этого четырехугольника таковы, что треугольники $ABP$ и $BCQ$ -- 
равносторонние. Найдите угол $PDQ$. 
(Канада, 2017)

\medskip 

\centerline{LI УРАЛЬСКИЙ ТУРНИР ЮНЫХ МАТЕМАТИКОВ. КИРОВ, 16--22.02.2018}

\centerline{\bf МАТЕМАТИЧЕСКИЙ БОЙ \No 3. 21.02.2018}

\centerline{\bf МЛАДШАЯ ГРУППА, ПЕРВАЯ ЛИГА}

\medskip 

1. По кругу стоят 111 башен, в которых сидят 200 рыцарей, 100 из которых -- 
чёрные, а остальные -- белые. В конце каждого часа каждый черный рыцарь 
перемещается в соседнюю башню по часовой стрелке, а каждый белый рыцарь 
перемещается в соседнюю башню против часовой стрелки. Найдите наименьшее 
натуральное $n$ такое, что в течение любых $n$ часов заведомо найдется 
момент, когда в какой-то башне не будет ни одного рыцаря? 
(P.Calabek, Чехия, 2018, I этап, категория C)

2. У Васи есть набор из $n$ карточек, на которых написаны натуральные числа 
от 1 до $n$ (каждое по одному разу). Он разложил их в ряд в некотором порядке. 
Петя под ними положил пустые карточки. На первой из них он написал число 
с первой Васиной карточки, на второй -- удвоенное число со второй Васиной 
карточки, на третьей -- утроенное число с третьей Васиной карточки и т.д., 
на $n$-ой карточке -- число с $n$-ой Васиной карточке, умноженное на $n$. 
Оказалось, что числа на Петиных карточках идут в порядке возрастания. 
В каком порядке могли располагаться Васины карточки? 
(Республика Сербская (Босния и Герцеговина), второй разряд, 1994)

3. Найдите все натуральные числа $a$ и $b$, для которых число $a^2+a+1$ 
делится на $ab-1$. 
(Белоруссия, 2018, 3 этап)

4. Ненулевые числа $a$, $b$, $c$ и $d$ удовлетворяют равенствам $a+b+c+d=0$ 
и ${1\over a}+{1\over b}+{1\over c}+{1\over d}+{1\over abcd}=0$. Чему может 
равняться выражение $(ab-cd)(c+d)$? 
(Босния и Герцеговина, соревнование Тузланского кантона, 2013, I разряд)

5. На доске в ряд написано 100 натуральных чисел. Петя и Вася играют в игру. 
Ходят по очереди, начинает Петя. Своим ходом он может выбрать несколько 
(быть может, одно) идущих подряд чисел, после чего Вася может либо прибавить 
ко всем выбранным Петей числам единицу, либо вычесть из всех выбранных Петей 
чисел единицу. Докажите, что Петя может действовать так, что через некоторое 
время он получит не менее 99 чисел, кратных 3. 
(Германия, отбор на ММО, 2018)

6. На прямой отметили миллион точек. Все попарные расстояния между отмеченными 
точками различны. Для любой отмеченной точки посчитали сумму расстояний 
до двух ближайших отмеченных точек. Оказалось, что все суммы, кроме одной, 
являются целыми числами. Обязательно ли найдутся две соседние отмеченные точки, 
расстояние между которыми -- целое число? 
(С.Берлов, Н.Власова, упрощение)

7. Для чисел $x$, $y$ и $z$ докажите неравенство 
$(x^2-y^2)(y^2-z^2)\leq (x-z)^2y^2$. 
(Д. Карпов, А. Храбров)

8. Четырехугольник $ABCD$ таков, что $AB=CD$ и $BC=AD$. Точки $P$ и $Q$ 
внутри этого четырехугольника таковы, что треугольники $ABP$ и $BCQ$ -- 
равносторонние. Найдите угол $PDQ$. 
(Канада, 2017)

\medskip 

\centerline{LI УРАЛЬСКИЙ ТУРНИР ЮНЫХ МАТЕМАТИКОВ. КИРОВ, 16--22.02.2018}

\centerline{\bf МАТЕМАТИЧЕСКИЙ БОЙ \No 3. 21.02.2018}

\centerline{\bf МЛАДШАЯ ГРУППА, ВТОРАЯ ЛИГА}

\medskip 

1. По кругу стоят 111 башен, в которых сидят 200 рыцарей, 100 из которых -- 
чёрные, а остальные -- белые. В конце каждого часа каждый черный рыцарь 
перемещается в соседнюю башню по часовой стрелке, а каждый белый рыцарь 
перемещается в соседнюю башню против часовой стрелки. Докажите, что найдется 
час, в течение которого хотя бы одна башня будет без рыцарей. 
(P.Calabek, Чехия, 2018, I этап, категория C)

2. Имеется 10 одинаковых по виду монет, среди которых две фальшивые, 
а 8 настоящих. Известно, что настоящие монеты весят одинаково и что 
одна из фальшивых монет легче, а другая -- тяжелее настоящей. Каким 
наименьшим числом взвешиваний на чашечных весах можно выделить 
хотя бы одну настоящую монету? 
(С.Токарев. Ярославские дистанционные игры)

3. На доске стоят числа 1, 2, 3, \dots, 250. За один ход можно взять 
два любых написанных числа $a$ и $b$, стереть их и дописать на доску 
число $a+b\over d$, где $d$ -- наибольший общий нечётный делитель 
чисел $a$ и $b$. Может ли после 249 таких операций остаться число 6? 
(С.Берлов, упрощение)

4. Двоих солдат тренируют рыть окопы. В 12:00 первый солдат начал 
рыть с постоянной скоростью окоп по прямой из точки A в точку B. 
Через час второй солдат, начиная с точки A, стал засыпать вырытый окоп 
тоже с постоянной скоростью. Когда первый дошел до половины пути, 
к нему подошел старшина и стал показывать, как надо копать, 
заменив на 15 минут первого солдата. Потом он подошел ко второму 
и показал ему, как надо закапывать окоп, заменив того на 15 минут. 
Известно, что старшина копает и закапывает в полтора раза быстрее солдат. 
К сожалению, скорость работы нерадивых солдат после вмешательства старшины 
не изменилась. До точки B оба солдата дошли одновременно в 15:00. 
Во сколько раз скорость засыпки больше скорости рытья? 
(С.Волчёнков)

5. На доске в ряд написаны четыре натуральных числа. Петя и Вася играют 
в игру. Ходят по очереди, начинает Петя. Своим ходом он может выбрать 
несколько (быть может, одно) идущих подряд чисел, после чего Вася может 
либо прибавить ко всем выбранным Петей числам единицу, либо вычесть 
из всех выбранных Петей чисел единицу. Докажите, что Петя может 
действовать так, что через некоторое время он получит не менее трёх чисел, 
кратных трём. 
(Германия, отбор на ММО, 2018)

6. На прямой отметили миллион точек. Все попарные расстояния между отмеченными 
точками различны. Для любой отмеченной точки посчитали сумму расстояний 
до двух ближайших отмеченных точек. Оказалось, что все суммы, кроме одной, 
являются целыми числами. Обязательно ли найдутся две соседние отмеченные 
точки, расстояние между которыми -- целое число? 
(С.Берлов, Н.Власова, упрощение)

7. Для чисел $x$, $y$ и $z$ докажите неравенство 
$(x^2-y^2)(y^2-z^2)\leq (x-z)^2y^2$. 
(Д. Карпов, А. Храбров)

8. Четырехугольник $ABCD$ таков, что $AB=CD$ и $BC=AD$. Точки $P$ и $Q$ 
внутри этого четырехугольника таковы, что треугольники $ABP$ и $BCQ$ -- 
равносторонние. Докажите, что треугольник $PDQ$ -- равнобедренный. 
(Канада, 2017)

\medskip 
  
\centerline{LI УРАЛЬСКИЙ ТУРНИР ЮНЫХ МАТЕМАТИКОВ. КИРОВ, 16--22.02.2018}

\centerline{\bf МАТЕМАТИЧЕСКИЙ БОЙ \No 3. 21.02.2018}

\centerline{\bf ГРУППА "СТАРТ", ВЫСШАЯ ЛИГА}

\medskip 
  
1. Какое минимальное количество ходов нужно совершить ладье, чтобы пройти 
все клетки шахматной доски $9\times 9$? (Считается, что на каждом ходу 
ладья посещает все промежуточные клетки на своем пути.) 
(Д.Ширяев)

2. По кругу стоят 111 башен, в которых сидят 200 рыцарей, 100 из которых -- 
чёрные, а остальные -- белые. В конце каждого часа каждый черный рыцарь 
перемещается в соседнюю башню по часовой стрелке, а каждый белый рыцарь 
перемещается в соседнюю башню против часовой стрелки. Докажите, что найдется 
час, в течение которого хотя бы в одной башне не будет рыцарей. 
(P.Calabek, Чехия, 2018, I этап, категория C)

3. В ряд написано 100 целых чисел. Каин и Авель играют в игру. Ходят 
по очереди, начинает Каин. Каждым ходом Каин может выбрать несколько 
(быть может, одно) идущих подряд чисел, после чего Авель может либо 
прибавить ко всем выбранным Каином числам единицу, либо вычесть 
из всех выбранных Каином чисел единицу. Докажите, что Каин может 
действовать так, что через несколько ходов не менее 98 написанных чисел 
будут кратны 4. 
(Германия, отбор на ММО, 2018)

4. В ряд стоят числа от 1 до 99 в некотором порядке. Под каждым из них 
во втором ряду написали число. Под числом, стоящим первым, написали его само, 
под вторым -- удвоенное второе, под третьим -- утроенное третье и т. д., 
под 99-ым написали 99-ое число, умноженное на 99. Оказалось, что 
во втором ряду каждое число больше всех чисел, стоящих левее него. 
Какое число в первом ряду могло стоять на 50-ом месте? 
(Республика Сербская (Босния и Герцеговина), второй разряд, 1994)

5. На доске написано 999 единиц. За один ход можно стереть два любых 
написанных числа $a$ и $b$ и дописать на доску число $a+b\over d$, 
где $d$ -- наибольший общий нечётный делитель чисел $a$ и $b$. Какое 
наименьшее число может остаться на доске после 998 ходов? 
(С.Берлов)

6. На прямой отмечены 100 точек. Все попарные расстояния между отмеченными 
точками различны. Оказалось, что сумма расстояний от любой отмеченной точки 
до двух ближайших отмеченных -- целое число. Какое наибольшее количество 
нецелых чисел может быть среди 99 расстояний между соседними отмеченными 
точками? 
(С.Берлов, Н.Власова)

7. Имеется 100 одинаковых на вид монет, среди которых две фальшивых 
и 98 настоящих. Известно, что настоящие монеты весят одинаково и что 
одна из фальшивых монет легче, а другая -- тяжелее настоящей. Каким 
наименьшим числом взвешиваний на чашечных весах можно выделить хотя бы 
одну настоящую монету? 
(С.Токарев. Ярославские дистанционные игры)

8. {\it Разверткой куба} $1\times 1\times 1$ называется фигура 
из 6 единичных квадратов, перегибая которую по сторонам квадратов, 
можно обернуть куб. Можно ли обернуть куб $2\times 2\times 2$ четырьмя 
одинаковыми развёртками куба $1\times 1\times 1$? 
(С.Токарев. Ярославские дистанционные игры)

\medskip 

\centerline{LI УРАЛЬСКИЙ ТУРНИР ЮНЫХ МАТЕМАТИКОВ. КИРОВ, 16--22.02.2018}

\centerline{\bf МАТЕМАТИЧЕСКИЙ БОЙ \No 3. 21.02.2018}

\centerline{\bf ГРУППА "СТАРТ", ПЕРВАЯ ЛИГА}

\medskip 

1. Какое минимальное количество ходов нужно совершить ладье, чтобы пройти 
все клетки шахматной доски $8\times 8$ и вернуться на исходную клетку? 
(Считается, что на каждом ходу ладья посещает все промежуточные клетки 
на своем пути.) 
(Д.Ширяев)

2. По кругу стоят 111 башен, в которых сидят 200 рыцарей, 100 из которых -- 
чёрные, а остальные -- белые. В конце каждого часа каждый черный рыцарь 
перемещается в соседнюю башню по часовой стрелке, а каждый белый рыцарь 
перемещается в соседнюю башню против часовой стрелки. Докажите, что найдется 
час, в течение которого хотя бы в одной башне не будет рыцарей. 
(P.Calabek, Чехия, 2018, I этап, категория C)

3. В ряд написано 100 целых чисел. Каин и Авель играют в игру. Ходят 
по очереди, начинает Каин. Своим ходом Каин может выбрать несколько 
(быть может, одно) идущих подряд чисел, после чего Авель может либо 
прибавить ко всем выбранным Каином числам единицу, либо вычесть из всех 
выбранных Каином чисел единицу. Докажите, что Каин может действовать так, 
что через несколько ходов не менее 99 написанных чисел будут кратны 3. 
(Германия, отбор на ММО, 2018)

4. В ряд стоят числа от 1 до 99 в некотором порядке. Под каждым из них 
во втором ряду написали число. Под стоящим первым написали его само, 
под вторым -- удвоенное второе, под третьим -- утроенное третье и т. д., 
под 99-ым написали 99-ое число, умноженное на 99. Оказалось, что 
во втором ряду каждое число больше всех чисел, стоящих левее него. 
Какое число в первом ряду могло стоять на 50-ом месте? 
(Республика Сербская (Босния и Герцеговина), второй разряд, 1994)

5. На доске написано 999 единиц. За один ход можно стереть два любых 
написанных числа $a$ и $b$ и дописать на доску число $a+b\over d$, 
где $d$ -- наибольший общий нечётный делитель чисел $a$ и $b$. Какое 
наименьшее число может остаться на доске после 998 ходов? 
(С.Берлов)

6. На прямой отмечены 100 точек. Все попарные расстояния между отмеченными 
точками различны. Оказалось, что сумма расстояний от любой отмеченной точки 
до двух ближайших отмеченных -- целое число. Могут ли все 99 расстояний 
между соседними точками быть нецелыми? 
(С.Берлов, Н.Власова)

7. Имеется 100 одинаковых на вид монет, среди которых две фальшивых 
и 98 настоящих. Известно, что настоящие монеты весят одинаково и что 
одна из фальшивых монет легче, а другая -- тяжелее настоящей. Каким 
наименьшим числом взвешиваний на чашечных весах можно выделить хотя бы 
одну настоящую монету? 
(С.Токарев. Ярославские дистанционные игры)

8. {\it Разверткой куба} $1\times 1\times 1$ называется фигура 
из 6 единичных квадратов, перегибая которую по сторонам квадратов, 
можно обернуть куб. Можно ли обернуть куб $2\times 2\times 2$ четырьмя 
одинаковыми развёртками куба $1\times 1\times 1$? 
(С.Токарев. Ярославские дистанционные игры)

\medskip 

\centerline{LI УРАЛЬСКИЙ ТУРНИР ЮНЫХ МАТЕМАТИКОВ. КИРОВ, 16--22.02.2018}

\centerline{\bf МАТЕМАТИЧЕСКИЙ БОЙ \No 3. 21.02.2018}

\centerline{\bf ГРУППА "СТАРТ", ВТОРАЯ ЛИГА}

\medskip 

1. По кругу стоят 111 башен, в которых сидят 220 рыцарей, 110 из которых -- 
чёрные, а остальные -- белые. В конце каждого часа каждый черный рыцарь 
перемещается в соседнюю башню по часовой стрелке, а каждый белый рыцарь 
перемещается в соседнюю башню против часовой стрелки. Докажите, что найдется 
час, в течение которого хотя бы в одной башне не будет рыцарей. 
(P.Calabek, Чехия, 2018, I этап, категория C)

2. В ряд написано 100 целых чисел. Каин и Авель играют в игру. Ходят 
по очереди, начинает Каин. Своим ходом Каин может выбрать несколько 
(быть может, одно) идущих подряд чисел, после чего Авель может либо 
прибавить ко всем выбранным Каином числам единицу, либо вычесть 
из всех выбранных Каином чисел единицу. Докажите, что Каин может 
действовать так, что через несколько ходов не менее 99 написанных чисел 
будут кратны 3. 
(Германия, отбор на ММО, 2018)

3. Двоих солдат тренируют рыть окопы. В 12:00 первый солдат начал рыть 
с постоянной скоростью окоп по прямой из точки A в точку B. Через час 
второй солдат, начиная с точки A, стал засыпать вырытый окоп тоже 
с постоянной скоростью. Когда первый дошел до половины пути, к нему 
подошел старшина и стал показывать, как надо копать, заменив на 15 минут 
первого солдата. Потом он подошел ко второму и показал ему, как надо 
закапывать окоп, заменив того на 15 минут. Известно, что старшина копает 
и закапывает в полтора раза быстрее солдат. К сожалению, скорость работы 
нерадивых солдат после вмешательства старшины не изменилась. До точки B 
оба солдата дошли одновременно в 15:00. Во сколько раз скорость засыпки 
больше скорости рытья? 
(С.Волчёнков)

4. Имеется пять одинаковых на вид монет, среди которых две фальшивых 
и три настоящих. Известно, что настоящие монеты весят одинаково 
и что одна из фальшивых монет легче, а другая -- тяжелее настоящей. 
Каким наименьшим числом взвешиваний на чашечных весах можно выделить 
хотя бы одну настоящую монету? 
(С.Токарев. Ярославские дистанционные игры)

5. На доске стоят числа 1, 2, 3, \dots, 250. За один ход можно взять 
два любых написанных числа $a$ и $b$, стереть их и дописать на доску 
число $a+b\over d$, где $d$ -- наибольший общий нечётный делитель 
чисел $a$ и $b$. Может ли после 249 таких операций остаться число 6? 
(С.Берлов, упрощение)

6. Найдите все тройки натуральных чисел $a$, $b$, $c$, для которых: $a+1$ 
делится на $b$, $b+1$ делится на $c$, $c+1$ делится на $a$. 
(С.Волчёнков)

7. На прямой отмечены 100 точек. Все попарные расстояния между отмеченными 
точками различны. Оказалось, что сумма расстояний от любой отмеченной точки 
до двух ближайших отмеченных -- целое число. Могут ли все 99 расстояний 
между соседними точками быть нецелыми? 
(С.Берлов, Н.Власова)

8. Докажите, что клетки квадрата $300\times 300$ можно покрасить в 3 цвета 
так, чтобы клеток каждого цвета было поровну и ни в одном столбце или строке 
не было клеток всех трех цветов. 
(Д.Ширяев)
 
\medskip 

\centerline{LI УРАЛЬСКИЙ ТУРНИР ЮНЫХ МАТЕМАТИКОВ. КИРОВ, 16--22.02.2018}

\centerline{\bf МАТЕМАТИЧЕСКИЙ БОЙ \No 3. 21.02.2018}

\centerline{\bf ГРУППА "СТАРТ", ТРЕТЬЯ ЛИГА}

\medskip 

1. Какое минимальное количество ходов нужно совершить ладье, чтобы пройти 
все клетки шахматной доски $8\times 8$ и вернуться на исходную клетку? 
(Считается, что на каждом ходу ладья посещает все промежуточные клетки 
на своем пути) 
(Д.Ширяев)

2. В ряд написано 100 целых чисел. Каин и Авель играют в игру. Ходят 
по очереди, начинает Каин. Своим ходом Каин может выбрать два любых числа, 
после чего Авель может либо прибавить ко всем выбранным Каином числам единицу, 
либо вычесть из всех выбранных Каином чисел единицу. Докажите, что Каин 
может действовать так, что через несколько ходов не менее 98 написанных чисел 
будут кратны 3. 
(Германия, отбор на ММО, 2018, упрощение)

3. Двоих солдат тренируют рыть окопы. В 12:00 первый солдат начал рыть 
с постоянной скоростью окоп по прямой из точки A в точку B. Через час 
второй солдат, начиная с точки A, стал засыпать вырытый окоп тоже 
с постоянной скоростью. Когда первый дошел до половины пути, к нему 
подошел старшина и стал показывать, как надо копать, заменив на 15 минут 
первого солдата. Потом он подошел ко второму и показал ему, как надо 
закапывать окоп, заменив того на 15 минут. Известно, что старшина копает 
и закапывает в полтора раза быстрее солдат. К сожалению, скорость работы 
нерадивых солдат после вмешательства старшины не изменилась. До точки B 
оба солдата дошли одновременно в 15:00. Во сколько раз скорость засыпки 
больше скорости рытья? 
(С.Волчёнков)

4. Имеется пять одинаковых на вид монет, среди которых две фальшивых 
и три настоящих. Известно, что настоящие монеты весят одинаково и что 
одна из фальшивых монет легче, а другая -- тяжелее настоящей. Каким 
наименьшим числом взвешиваний на чашечных весах можно выделить хотя бы 
одну настоящую монету? 
(С.Токарев. Ярославские дистанционные игры)

5. В алфавите клуба фанатов команды "Зубило" 6 букв (по алфавиту: 
Б, З, И, Л, О, У). Словом фанаты называют любую последовательность 
из 6 различных букв. На каком месте в словаре фанатов стоит слово ЗУБИЛО? 
(С.Волчёнков)

6. Найдите все тройки натуральных чисел $a$, $b$, $c$, для которых: 
$a+1$ делится на $b$, $b+1$ делится на $c$, $c+1$ делится на $a$. 
(С.Волчёнков)

7. В мешке лежат футболки ЦСКА, "Милана" и "Шинника". Какое наименьшее 
число футболок нужно вынуть наугад, чтобы нашёлся цвет, присутствующий 
в окраске не менее чем пяти вынутых футболок? (Цвета ЦСКА -- красно-синие, 
"Милана" -- красно-чёрные, а "Шинника" -- сине-чёрные). 
(С.Токарев. Ярославские дистанционные игры)

8. {\it Разверткой куба} $1\times 1\times 1$ называется фигура из 6 единичных 
квадратов, перегибая которую по сторонам квадратов, можно обернуть куб. 
Можно ли обернуть куб $2\times 2\times 2$ четырьмя одинаковыми развёртками 
куба $1\times 1\times 1$? 
(С.Токарев. с изменением)

\end 