\nopagenumbers

\input amssym.def

\input amssym.tex

\def\geq{\geqslant}

\def\leq{\leqslant}

\input cells.sty

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

\centerline{\bf МАТЕМАТИЧЕСКИЙ БОЙ \No1. 02.05.2021}

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

\medskip 

1. Натуральное число $n>1$ таково, что для любого натурального делителя $d$ 
числа $n$ число $n^2+n+1$ делится на число $d^2+d+1$. Докажите, что 
$n$ -- или простое число, или квадрат простого числа.
(Математический турнир Гарвард-MIT, февраль 2021)

2. На окружности отмечены $n\geqslant 5$ точек. Розенкранц провел $k<n$ 
отрезков с концами в отмеченных точках так, что любые два проведённых 
отрезка имеют общую точку (возможно, конец отрезка). Докажите,
что Гильденстерн может провести ещё один отрезок, который также будет 
иметь общую точку со всеми уже проведёнными.
% по мотивам USAMTS 2020/21

3. Последовательность $a_1$, $a_2$, \dots, $a_n$ ($n\geqslant 2$) натуральных 
чисел назовём {\it крутой}, если 
$${a_n\over a_{n-1}}\geqslant {a_{n-1}\over a_{n-2}}\geqslant \dots \geqslant {a_2\over a_1}>1.$$
Докажите, что если последовательность $a_1$, $a_2$, \dots, $a_n$ 
крута, то $a_n\geqslant {3\over 4}n^2-n$.
(Олимпиада Rioplatense, 2019) 

4. В выпуклом четырёхугольнике $ABCD$: $\angle ABD=30^\circ$, 
$\angle BCA=75^\circ$, $\angle ACD=25^\circ$ и $CD=CB$. 
Прямая $BC$ пересекает описанную окружность треугольника $DAC$ 
в точках $C$ и $E$. Докажите, что $CE=BD$.
(Индия, 2021)

5. В треугольнике $ABC$ с наибольшей стороной $BC$ биссектриcы $AD$, $BE$ 
и $CF$ пересекаются в точке $I$. Точки $G$ и $H$ на отрезках $BD$ и $CD$ 
соответственно таковы, что $\angle GID=\angle ABC$, $\angle HID=\angle ACB$.
Докажите, что $\angle BHE=\angle CGF$.
(Испания, местный этап, 2020/21)

6. Пусть $a>b$ -- натуральные числа такие, что 
$\sqrt{\sqrt{a}+\sqrt{b}}+\sqrt{\sqrt{a}-\sqrt{b}}$ --
целое число. Можно ли утверждать, что $a$ -- точный квадрат? 
(Математический турнир Гарвард-MIT, февраль 2021)

7. На вечеринке присутствовали 2021 человек, некоторые из них являются 
друзьями. Назовём {\it популярностью} человека размер наибольшей группы 
людей, в которую он входит, такой, что любые двое из этой группы дружат 
между собой. Если у человека нет друзей на вечеринке, его популярность 
равна единице. Какое наибольшее число различных популярностей может быть 
у присутствующих на вечеринке?
(2021 CCA Math Bonanza Tiebreaker, Round 3)

8. На клетчатую доску $100\times 100$ положили по клеткам 800 
неперекрывающихся фигурок вида 
\cells{
 _
|_|_ _
|_|_|_|}
(Г-тетрамино; фигурки можно поворачивать и переворачивать). Докажите, 
что на доску можно положить ещё одно Г-тетрамино так, чтобы
оно не перекрывалось с остальными.
(K\"ozepiskolai Matematikai Lapok, 2021)

\medskip 

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

\centerline{\bf МАТЕМАТИЧЕСКИЙ БОЙ \No1. 02.05.2021}

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

\medskip 

1. Натуральное число $n>1$ таково, что для любого натурального делителя $d$ числа $n$
число $n^2+n+1$ делится на число $d^2+d+1$. Докажите, что 
$n$ -- или простое число, или квадрат простого числа.
(Математический турнир Гарвард-MIT, февраль 2021)

2. На окружности расставлены $n\geqslant 5$ точек. Розенкранц и
Гильденстерн по очереди делают ходы в следующей игре (начинает
Розенкранц): своим ходом игрок должен соединить две точки отрезком
так, чтобы этот отрезок имел хотя бы одну общую точку (возможно,
конец) с каждым из ранее проведенных отрезков. Проигрывает не имеющий
хода. При каких $n$ выигрывает Розенкранц?
(USAMTS, 2020/21) 

3. Последовательность $a_1$, $a_2$, \dots, $a_n$ ($n\geqslant 2$) натуральных 
чисел назовём {\it крутой}, если 
$${a_n\over a_{n-1}}\geqslant {a_{n-1}\over a_{n-2}}\geqslant \dots\geqslant {a_2\over a_1}>1.$$
Найдите для каждого $n$ крутую последовательность $a_1$, $a_2$, \dots, $a_n$, 
в которой $a_n\leqslant n^2$.
(Олимпиада Rioplatense, 2019) 

4. В выпуклом четырёхугольнике $ABCD$: $\angle ABD=30^\circ$, 
$\angle BCA=75^\circ$, $\angle ACD=25^\circ$ и $CD=CB$. 
Прямая $BC$ пересекает описанную окружность треугольника $DAC$ 
в точках $C$ и $E$. Докажите, что $CE=BD$.
(Индия, 2021)

5. В треугольнике $ABC$ с наибольшей стороной $BC$ биссектриcы $AD$, $BE$ 
и $CF$ пересекаются в точке $I$. Точки $G$ и $H$ на отрезках $BD$ и $CD$ 
соответственно таковы, что $\angle GID=\angle ABC$, $\angle HID=\angle ACB$.
Докажите, что $\angle BHE=\angle CGF$.
(Испания, местный этап, 2020/21)

6. Пусть $a>b$ -- натуральные числа такие, что 
$\sqrt{\sqrt{a}+\sqrt{b}}+\sqrt{\sqrt{a}-\sqrt{b}}$ --
целое число. Можно ли утверждать, что $a$ -- точный квадрат? 
(Математический турнир Гарвард-MIT, февраль 2021)

7. На вечеринке присутствовали 2021 человек, некоторые из них являются 
друзьями. Назовём {\it популярностью} человека размер наибольшей группы 
людей, в которую он входит, такой, что любые двое из этой группы дружат 
между собой. Если у человека нет друзей на вечеринке, его популярность 
равна единице. Какое наибольшее число различных популярностей может быть 
у присутствующих на вечеринке?
(2021 CCA Math Bonanza Tiebreaker, Round 3)

8. На клетчатую доску $100\times 100$ положили по клеткам 800 
неперекрывающихся фигурок вида 
\cells{
 _
|_|_ _
|_|_|_|}
(Г-тетрамино; фигурки можно поворачивать и переворачивать). Докажите, 
что на доску можно положить ещё одно Г-тетрамино так, чтобы
оно не перекрывалось с остальными.
(K\"ozepiskolai Matematikai Lapok, 2021)

\medskip 

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

\centerline{\bf МАТЕМАТИЧЕСКИЙ БОЙ \No1. 02.05.2021}

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

\medskip 

1. Натуральное число $n>1$ таково, что для любого натурального делителя $d$ числа $n$
число $n^2+n+1$ делится на число $d^2+d+1$. Докажите, что 
$n$ -- или простое число, или квадрат простого числа.
(Математический турнир Гарвард-MIT, февраль 2021)

2. На окружности расставлены $n\geqslant 5$ точек. Розенкранц и
Гильденстерн по очереди делают ходы в следующей игре (начинает
Розенкранц): своим ходом игрок должен соединить две точки отрезком
так, чтобы этот отрезок имел хотя бы одну общую точку (возможно,
конец) с каждым из ранее проведенных отрезков. Проигрывает не имеющий
хода. При каких $n$ выигрывает Розенкранц?
(USAMTS, 2020/21) 

3. Последовательность $a_1$, $a_2$, \dots, $a_n$ ($n\geqslant 2$) натуральных 
чисел назовём {\it крутой}, если 
$${a_n\over a_{n-1}}\geqslant {a_{n-1}\over a_{n-2}}\geqslant \dots\geqslant {a_2\over a_1}>1.$$
Найдите для каждого $n$ крутую последовательность $a_1$, $a_2$, \dots, $a_n$, 
в которой $a_n\leqslant n^2$.
(Олимпиада Rioplatense, 2019) 

4. В выпуклом четырёхугольнике $ABCD$: $\angle ABD=30^\circ$, 
$\angle BCA=75^\circ$, $\angle ACD=25^\circ$ и $CD=CB$. 
Прямая $BC$ пересекает описанную окружность треугольника $DAC$ 
в точках $C$ и $E$. Докажите, что $CE=BD$.
(Индия, 2021)

5. В треугольнике $ABC$ с наибольшей стороной $BC$ биссектриcы $AD$, $BE$ 
и $CF$ пересекаются в точке $I$. Точки $G$ и $H$ на отрезках $BD$ и $CD$ 
соответственно таковы, что $\angle GID=\angle ABC$, $\angle HID=\angle ACB$.
Докажите, что $\angle BHE=\angle CGF$.
(Испания, местный этап, 2020/21)

6. Пусть $a>b$ -- натуральные числа такие, что 
$\sqrt{\sqrt{a}+\sqrt{b}}+\sqrt{\sqrt{a}-\sqrt{b}}$ --
целое число. Можно ли утверждать, что $a$ -- точный квадрат? 
(Математический турнир Гарвард-MIT, февраль 2021)

7. На вечеринке присутствовали 2021 человек, некоторые из них являются 
друзьями. Назовём {\it популярностью} человека размер наибольшей группы 
людей, в которую он входит, такой, что любые двое из этой группы дружат 
между собой. Если у человека нет друзей на вечеринке, его популярность 
равна единице. Какое наибольшее число различных популярностей может быть 
у присутствующих на вечеринке?
(2021 CCA Math Bonanza Tiebreaker, Round 3)

8. На клетчатую доску $100\times 100$ положили по клеткам 800 
неперекрывающихся фигурок вида 
\cells{
 _
|_|_ _
|_|_|_|}
(Г-тетрамино; фигурки можно поворачивать и переворачивать). Докажите, 
что на доску можно положить ещё одно Г-тетрамино так, чтобы
оно не перекрывалось с остальными.
(K\"ozepiskolai Matematikai Lapok, 2021)

\medskip 

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

\centerline{\bf МАТЕМАТИЧЕСКИЙ БОЙ \No1. 02.05.2021}

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

\medskip 

1. На доске написано 10-значное число. За одну операцию число на доске умножают на 
6 и стирают его первую цифру. Через несколько операций на доске оказалось число, 
равное исходному. Докажите, что оно делится на 1024.
(Д. Ширяев)

2. На окружности расставлены $n\geqslant 5$ точек. Розенкранц и
Гильденстерн по очереди делают ходы в следующей игре (начинает
Розенкранц): своим ходом игрок должен соединить две точки отрезком
так, чтобы этот отрезок имел хотя бы одну общую точку (возможно,
конец) с каждым из ранее проведенных отрезков. Проигрывает не имеющий
хода. При каких $n$ выигрывает Розенкранц?
(USAMTS, 2020/21) 

3. Найдите все четвёрки вещественных чисел $a$, $b$, $c$ и $d$, для которых 
выполнено
$$a^2+b^2+c^2+d^2=a+b+c+d-ab=3.$$
(Косово, 2021)

4. В треугольнике $ABC$ таком, что $\angle BAC=50^\circ$,
на стороне $AB$ нашлась точка $D$ такая, что $\angle ACD=30^\circ$ и $AB=CD$.
Найдите величину угла $\angle BCD$.
(фольклор)

5. В треугольнике $ABC$ с наибольшей стороной $BC$ биссектриcы $AD$, $BE$ 
и $CF$ пересекаются в точке $I$. Точки $G$ и $H$ на отрезках $BD$ и $CD$ 
соответственно таковы, что $\angle GID=\angle ABC$, $\angle HID=\angle ACB$.
Докажите, что $\angle BHE=\angle CGF$.
(Испания, местный этап, 2020/21)

6. Пусть $a>b$ -- натуральные числа такие, что 
$\sqrt{\sqrt{a}+\sqrt{b}}+\sqrt{\sqrt{a}-\sqrt{b}}$ --
целое число. Можно ли утверждать, что $a$ -- точный квадрат? 
(Математический турнир Гарвард-MIT, февраль 2021)

7. Сколькими способами можно выписать в строку все натуральные числа
от 1 до $n$ таким образом, чтобы для каждого $k\leqslant n$ первые $k$
чисел в строке давали разные остатки при делении на $k$?
(Канада, соревнование для юниоров, 2021)

8. На клетчатую доску $100\times 100$ положили по клеткам 800 
неперекрывающихся фигурок вида 
\cells{
 _
|_|_ _
|_|_|_|}
(Г-тетрамино; фигурки можно поворачивать и переворачивать). Докажите, 
что на доску можно положить ещё одно Г-тетрамино так, чтобы
оно не перекрывалось с остальными.
(K\"ozepiskolai Matematikai Lapok, 2021)

\medskip 

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

\centerline{\bf МАТЕМАТИЧЕСКИЙ БОЙ \No1. 02.05.2021}

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

\medskip 

1. На вечеринке присутствовали 2021 человек, некоторые из них являются 
друзьями. Назовём {\it популярностью} человека размер наибольшей группы 
людей, в которую он входит, такой, что любые двое из этой группы дружат между 
собой. Если у человека нет друзей на вечеринке, его популярность равна единице. 
Какое наибольшее число различных популярностей может быть у присутствующих 
на вечеринке?
(2021 CCA Math Bonanza Tiebreaker, Round 3)

2. В углу квадрата $n\times n$, $n>1$, стоит фишка. Федя и Серёжа делают 
ходы по очереди, начинает Федя. Ход заключается в том, чтобы выбрать одно 
из четырёх направлений, после чего несколько раз (хотя бы один) передвинуть 
фишку на одну клетку в этом направлении. Дважды бывать в одной клетке нельзя. 
Проигрывает тот, кто не может сделать ход. Кто из игроков может обеспечить себе 
победу?
(Дания, 2021)

3. Найдите все четвёрки вещественных чисел $a$, $b$, $c$ и $d$, для которых 
выполнено
$$a^2+b^2+c^2+d^2=a+b+c+d-ab=3.$$
(Косово, 2021)

4. Натуральное число $n$ назовём {\it надёжным}, если сумма 
нескольких его различных делителей, среди которых есть $1$, равна $n$. 
Любое ли число является делителем некоторого надёжного числа? 
(Великобритания, 2021)

5. Клетки прямоугольника с $m$ строками и $n$ столбцами ($2\leq m\leq n$) 
раскрашены в черный и белый цвета так, что любые две строки раскрашены по-разному. При каком наибольшем значении $k$ для любой первоначальной раскраски можно закрасить $k$ столбцов в красный цвет так, чтобы любые две строки по-прежнему были раскрашены по-разному?
(Гонконг, отбор на ММО, 2018)

6. В треугольнике $ABC$ с наибольшей стороной $BC$ биссектрисы $AD$, $BE$ 
и $CF$ пересекаются в точке $I$. Точки $G$ и $H$ на отрезках $BD$ и $CD$ 
соответственно таковы, что $\angle GID=\angle ABC$, $\angle HID=\angle ACB$.
Докажите, что $\angle BHE=\angle CGF$.
(Испания, местный этап, 2020/21)

7. Пусть $p_1<p_2<\dots<p_k$~-- это $k$ наименьших простых чисел 
($p_1=2$, $p_2=3$, $p_3=5$ и т.д.), и $N=p_1\cdot p_2 \cdot \dots \cdot p_k$. 
Докажите, что среди чисел от 1 до $N$ ровно ${N\over 2}$ делятся на нечетное 
число простых $p_i$, где $i \leqslant k$.
(Польша, финал, 2021)

8. В выпуклом восьмиугольнике провели все диагонали. На какое наименьшее 
количество частей он мог оказаться разрезан?
(Предложил В. Брагин)

\medskip 

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

\centerline{\bf МАТЕМАТИЧЕСКИЙ БОЙ \No1. 02.05.2021}

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

1. На доске написано 10-значное число. За одну операцию число на доске 
умножают на 6 и стирают его первую цифру. Через 2021 операцию на доске 
оказалось число, равное исходному. Чему оно может быть равно?
(Д. Ширяев)

2. На вечеринке присутствовали 2021 человек, некоторые из них являются 
друзьями. Назовём {\it популярностью} человека размер наибольшей группы 
людей, в которую он входит, такой, что любые двое из этой группы дружат между 
собой. Если у человека нет друзей на вечеринке, его популярность равна единице. 
Какое наибольшее число различных популярностей может быть у присутствующих 
на вечеринке?
(2021 CCA Math Bonanza Tiebreaker, Round 3)

3. В углу квадрата $n\times n$, $n>1$, стоит фишка. Федя и Серёжа делают 
ходы по очереди, начинает Федя. Ход заключается в том, чтобы выбрать одно 
из четырёх направлений, после чего несколько раз (хотя бы один) передвинуть 
фишку на одну клетку в этом направлении. Дважды бывать в одной клетке нельзя. 
Проигрывает тот, кто не может сделать ход. Кто из игроков может обеспечить себе 
победу?
(Дания, 2021)

4. В какое наименьшее количество цветов можно покрасить клетки доски 
$2021 \times 2021$, чтобы в любом прямоугольнике $2\times 3$ и $3\times 2$ 
все клетки были разных цветов?
(Болгария, отбор на юниорскую Балканиаду, 2018)

5. У Оли есть $n$ гирек, масса каждой из которых составляет натуральное 
число граммов, а суммарная масса -- 2021 грамм. При каком наименьшем $n$ 
гирьки обязательно можно разбить на несколько (больше, чем одну) групп 
с равными массами?
(В.Брагин по мотивам фольклора) 

6. В треугольнике $ABC$ с наибольшей стороной $BC$ биссектрисы $AD$, $BE$ 
и $CF$ пересекаются в точке $I$. Точки $G$ и $H$ на отрезках $BD$ и $CD$ 
соответственно таковы, что $\angle GID=\angle ABC$, $\angle HID=\angle ACB$.
Докажите, что $\angle BHE=\angle CGF$.
(Испания, местный этап, 2020/21)

7. В треугольнике $ABC$ таком, что $\angle BAC=50^\circ$,
на стороне $AB$ нашлась точка $D$ такая, что $\angle ACD=30^\circ$ и $AB=CD$.
Найдите величину угла $\angle BCD$.
(фольклор)

8. Пусть $p_1<p_2<\dots<p_k$~-- это $k$ наименьших простых чисел 
($p_1=2$, $p_2=3$, $p_3=5$ и т.д.), и $N=p_1\cdot p_2 \cdot \dots \cdot p_k$. 
Докажите, что среди чисел от 1 до $N$ ровно ${N\over 2}$ делятся на нечетное 
число простых $p_i$, где $i \leqslant k$.
(Польша, финал, 2021)

\medskip 

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

\centerline{\bf МАТЕМАТИЧЕСКИЙ БОЙ \No1. 02.05.2021}

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

\medskip 

1. На доске написано 10-значное число. За одну операцию число на доске 
умножают на 6 и стирают его первую цифру. Через несколько операций на доске 
оказалось число, равное исходному. Докажите, что оно делится на 1024.
(Д. Ширяев)

2. В какое наименьшее количество цветов можно покрасить клетки доски 
$2021 \times 2021$, чтобы в любом прямоугольнике $2\times 3$ и $3\times 2$ 
все клетки были разных цветов?
(Болгария, отбор на юниорскую Балканиаду, 2018)

3. У Оли есть $n$ гирек, масса каждой из которых составляет натуральное 
число граммов, а суммарная масса -- 2021 грамм. При каком наименьшем $n$ 
гирьки обязательно можно разбить на несколько (больше, чем одну) групп 
с равными массами?
(В.Брагин по мотивам фольклора) 

4. В треугольнике $ABC$ таком, что $\angle BAC=50^\circ$,
на стороне $AB$ нашлась точка $D$ такая, что $\angle ACD=30^\circ$ и $AB=CD$.
Найдите величину угла $\angle BCD$.
(фольклор)

5. В компании из 8 человек некоторые пары знакомы, знакомства взаимны. 
Оказалось, что любые двое могут взять двоих других и вчетвером сесть 
за круглый стол, чтобы каждый сидел по соседству со знакомыми. Какое 
наименьшее количество пар знакомств может быть?
(Д. Белов, В. Брагин)

6. В автобусе продаются шестизначные билеты от 000000 до 999999. 
Митя считает билет счастливым, если сумма первых трёх цифр равна сумме 
последних трёх, а Петя -- если сумма цифр, стоящих на чётных местах, 
равна сумме цифр, стоящих на нечётных местах. Митя и Петя вместе зашли 
в автобус, купили два последовательных билета, и для каждого его билетик 
оказался счастливым (для Мити по митиному правилу, а для Пети -- по 
петиному). При этом Митя взял билет с меньшим номером. Для скольких пар 
соседних билетов это могло случиться?
Билеты 999999 и 000000 последовательными не считаем.

7. Попарно различные действительные числа $a, b, c$ таковы, что 
$$a^2-bc=b^2+ac=c^2+ab=10.$$
Найдите $a^2+b^2+c^2$.

8. На доске написаны числа от 1 до 2020. Сначала Паша зачёркивает $k$ 
из них, затем Вова зачёркивает ещё $1010-k$. Цель Вовы сделать так, 
чтобы сумма зачёркнутых чисел была равна сумме незачёркнутых. При каком 
наибольшем $k$ Паша не сможет гарантированно ему помешать?
(Olimpiada de Mayo, 2016, по мотивам)

\medskip 

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

\centerline{\bf МАТЕМАТИЧЕСКИЙ БОЙ \No1. 02.05.2021}

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

\medskip

1. На доске $100\times 100$ лежит 800 фигурок Г-тетрамино 
\cells{
 _
|_|_ _
|_|_|_|}
так, что они не перекрываются, и любая такая фигурка занимает ровно 4 клетки 
доски (фигурки можно поворачивать и переворачивать). Докажите, что на доску 
можно положить ещё хотя бы одну фигурку Г-тетрамино так, чтобы они все ещё 
не перекрывались.
(K\"ozepiskolai Matematikai Lapok, 2021)

2. В ряд расположено 100 монет. Изначально первые 50 монет лежат 
орлом вверх, а остальные~-- решкой. Аня и Ваня ходят по очереди, начинает 
Аня. За один ход Аня может выбрать две соседние монеты, одна из которых лежит 
орлом вверх, а другая~-- решкой, и перевернуть обе эти монеты. Ваня за свой 
ход может выбрать две соседние монеты, обе лежащие орлом вверх или обе 
лежащие решкой вверх, и перевернуть их. Если какой-то из игроков не может 
сделать свой ход, игра заканчивается. Ваня хочет, чтобы в какой-нибудь момент 
все монеты оказались решкой вверх. Может ли он играть так, чтобы 
гарантированно добиться желаемого?
(NICE Olympiad, 2021)

3. На вечеринке присутствовали 2021 человек, некоторые из них являются 
друзьями. Назовём популярностью человека размер наибольшей группы людей, 
в которую он входит, такой, что любые двое из этой группы дружат между собой.
Если у человека нет друзей на вечеринке, его популярность равна единице. 
Какое наибольшее число различных популярностей может быть у присутствующих 
на вечеринке?
(2021 CCA Math Bonanza Tiebreaker, Round 3)
 
4. Пусть $p_1<p_2<\dots<p_k$~-- $k$ наименьших простых чисел 
($p_1=2$, $p_2=3$, $p_3=5$ и т.д.), и $N=p_1\cdot p_2 \cdot \dots \cdot p_k$. 
Докажите, что среди чисел от 1 до $N$ ровно $N\over 2$ чисел имеют 
нечётное число различных простых делителей, не превосходящих $p_k$.
(Польша, финал, 2021)

5. Вася выбрал 800 различных натуральных чисел, не превосходящих 1000, 
и расставил их по кругу. Докажите, что найдутся два соседних числа, сумма 
которых не делится на следующее по часовой стрелке число.
(С. Берлов) 

6. В каждом из 6 мешков лежит по 12 монет. В одном мешке все монеты 
имеют вес 1 г, в другом все имеют вес 2 г, и т.д., в каком-то все имеют 
вес 6 г.  Мешки снабжены надписями 1 г, 2 г, \dots, 6 г. Мы хотим 
убедиться, что каждый мешок подписан правильно. Для этого у нас есть 
двухчашечные весы. Можно ли провести проверку с помощью всего лишь 
одного взвешивания, если разрешается использовать в нем не более 12 монет?
(Таня Хованова) 

7. В Азкабане 2021 камера. Камеры расположены в ряд $1\times 2021$. 
В первой (самой левой) камере сидят 100 узников, а в оставшихся камерах~-- 
по одному узнику. Узники хотят сбежать из Азкабана и для этого ломают стены 
между камерами, а из последней камеры (самой правой)~-- стену наружу. 
Ровно в полночь каждый узник начинает ломать стену между камерой, в которой 
он находится, и следующей за ней справа камерой. А узник в самой правой 
камере ломает стену наружу. Если узники сломали стену, то они мгновенно 
перемещаются в следующую камеру и начинают ломать стену там. Все узники 
работают с постоянной скоростью 1 стена в час. Все узники оказались 
на свободе через ${m\over n}$ часов. Найдите $m+n$, если известно, что 
дробь ${m\over n}$ несократима. 
(NICE Olympiad, 2021)

8. На доске написано 2021-значное число. За одну операцию число 
на доске умножают на 6 и стирают его первую цифру. Через несколько операций 
на доске оказалось число, равное исходному. Докажите, что ни в какой момент 
на доске не могло быть числа, отличающегося от исходного только в 1011-ом 
разряде.

\medskip

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

\centerline{\bf МАТЕМАТИЧЕСКИЙ БОЙ \No1. 02.05.2021}

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


\medskip

1. На доске $100\times 100$ лежит 800 фигурок Г-тетрамино 
\cells{
 _
|_|_ _
|_|_|_|}
так, что они не перекрываются, и любая такая фигурка занимает ровно 4 клетки 
доски (фигурки можно поворачивать и переворачивать). Докажите, что на доску 
можно положить ещё хотя бы одну фигурку Г-тетрамино так, чтобы они все ещё 
не перекрывались.
(K\"ozepiskolai Matematikai Lapok, 2021)

2. В ряд расположено 100 монет. Изначально первые 50 монет лежат 
орлом вверх, а остальные~-- решкой. Аня и Ваня ходят по очереди, начинает 
Аня. За один ход Аня может выбрать две соседние монеты, одна из которых лежит 
орлом вверх, а другая~-- решкой, и перевернуть обе эти монеты. Ваня за свой 
ход может выбрать две соседние монеты, обе лежащие орлом вверх или обе 
лежащие решкой вверх, и перевернуть их. Если какой-то из игроков не может 
сделать свой ход, игра заканчивается. Ваня хочет, чтобы в какой-нибудь момент 
все монеты оказались решкой вверх. Может ли он играть так, чтобы 
гарантированно добиться желаемого?
(NICE Olympiad, 2021)

3. На вечеринке присутствовали 2021 человек, некоторые из них являются 
друзьями. Назовём популярностью человека размер наибольшей группы людей, 
в которую он входит, такой, что любые двое из этой группы дружат между собой.
Если у человека нет друзей на вечеринке, его популярность равна единице. 
Какое наибольшее число различных популярностей может быть у присутствующих 
на вечеринке?
(2021 CCA Math Bonanza Tiebreaker, Round 3)

4. Пусть $p_1<p_2<\dots<p_{100}$~-- $100$ наименьших нечётных простых 
чисел ($p_1=3$, $p_2=5$, $p_3=7$ и т.д.), 
и $N=p_1\cdot p_2 \cdot \dots \cdot p_{100}$. Докажите, что среди чисел 
от 1 до $N$ ровно ${N-1\over 2}$ чисел имеют нечётное число различных 
простых делителей, не превосходящих $p_{100}$.
(Польша, финал, 2021, модификация)

5. Вася выбрал 800 различных натуральных чисел, не превосходящих 1000, 
и расставил их по кругу. Докажите, что найдутся два соседних числа, сумма 
которых не делится на следующее по часовой стрелке число.
(С. Берлов) 

6. У Оли есть $n$ гирек, масса каждой из которых натуральное число граммов, 
а суммарная масса -- 2021 грамм. При каком наименьшем $n$ гирьки обязательно 
можно разбить на несколько групп с равными массами?
(из 7 класса)

7. В Азкабане 2021 камера. Камеры расположены в ряд $1\times 2021$. 
В первой (самой левой) камере сидят 100 узников, а в оставшихся камерах~-- 
по одному узнику. Узники хотят сбежать из Азкабана и для этого ломают стены 
между камерами, а из последней камеры (самой правой)~-- стену наружу. 
Ровно в полночь каждый узник начинает ломать стену между камерой, в которой 
он находится, и следующей за ней справа камерой. А узник в самой правой 
камере ломает стену наружу. Если узники сломали стену, то они мгновенно 
перемещаются в следующую камеру и начинают ломать стену там. Все узники 
работают с постоянной скоростью 1 стена в час. Все узники оказались 
на свободе через ${m\over n}$ часов. Найдите $m+n$, если известно, что 
дробь ${m\over n}$ несократима. 
(NICE Olympiad, 2021)

8. На доске написано 10-значное число. За одну операцию число на доске 
умножают на 6 и стирают его первую цифру. Через несколько операций на доске 
оказалось число, равное исходному. Докажите, что оно делится на 1024.

\medskip

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

\centerline{\bf МАТЕМАТИЧЕСКИЙ БОЙ \No1. 02.05.2021}

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

\medskip

1. На доске $60\times 50$ лежит 220 фигурок Г-тетрамино 
\cells{
 _
|_|_ _
|_|_|_|}
так, что они не перекрываются, и любая такая фигурка занимает ровно 4 клетки доски (фигурки можно поворачивать и переворачивать). Докажите, что на доску можно положить ещё хотя бы одну фигурку Г-тетрамино так, чтобы они всё ещё не перекрывались.
(K\"ozepiskolai Matematikai Lapok, 2021)

2. В ряд расположено 50 монет. Изначально первые 25 монет лежат орлом вверх, 
а остальные~-- решкой. Аня и Ваня ходят по очереди, начинает Аня. 
За один ход Аня может выбрать две соседние монеты, одна из которых лежит 
орлом вверх, а другая~-- решкой, и перевернуть обе эти монеты. Ваня 
за свой ход может выбрать две соседние монеты, обе лежащие орлом вверх 
или обе лежащие решкой вверх, и перевернуть их. Если какой-то из игроков 
не может сделать свой ход, то игра заканчивается. Ваня хочет, чтобы 
в какой-нибудь момент все монеты оказались решкой вверх. Может ли он 
играть так, чтобы гарантированно добиться желаемого?
(Упрощение задачи 2 из высшей лиги)

3. На вечеринке присутствовали 200 человек, некоторые из них являются 
друзьями. Назовём популярностью человека размер наибольшей группы людей, 
в которую он входит, такой, что любые двое из этой группы дружат между собой. 
Если у человека нет друзей на вечеринке, его популярность равна единице. 
Могло ли на вечеринке оказаться больше 100 человек с различной популярностью?

4. Назовём натуральное число $N$ {\it вековым}, если можно выбрать 100 
последовательных натуральных чисел, сумма всех цифр в десятичной записи 
которых равна $N$. Найдите все вековые числа.
(Центральноевропейская математическая олимпиада, 2019, модификация) 

5. Вася расставил по кругу числа от 1 до 1000. Докажите, что найдутся 
два соседних числа, сумма которых не делится на следующее по часовой 
стрелке число.
(С. Берлов, упрощение)

6. У Оли есть $n$ гирек, масса каждой из которых натуральное число граммов, 
а суммарная масса -- 2021 грамм. При каком наименьшем $n$ гирьки обязательно 
можно разбить на несколько групп с равными массами?
(из 7 класса)

7. Азкабан представляет собой 30 пронумерованных камер, расположенных 
в один ряд друг за другом. В первой (самой левой) камере сидит 10 узников, 
а в оставшихся камерах~-- по одному узнику. Узники решили сбежать 
из Азкабана и для этого ровно в полночь каждый узник из камеры 
под номером $i$ начинает ломать стену, общую с камерой под номером $i+1$, 
а узник из 30-й камеры начинает ломать стену наружу. Если узники сломали 
стену, то они мгновенно перемещаются в следующую камеру и продолжают 
ломать стену там. Все узники работают с постоянной скоростью, позволяющей 
сломать в одиночку одну стену за час. Работая таким образом, узники 
окажутся на свободе через ${m\over n}$ часов. Найдите $m+n$, если известно, 
что дробь ${m\over n}$ несократима.

8. На доске написано 10-значное число. Каждую минуту число на доске 
умножают на 6 и стирают его первую цифру. Через полчаса число на доске 
снова оказалось 10-значное число. Докажите, что в какой-то момент на доске 
было число, делящееся на 1024.

\medskip

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

\centerline{\bf МАТЕМАТИЧЕСКИЙ БОЙ \No1. 02.05.2021}

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

\medskip

1. Какое наименьшее количество уголков из трёх клеток можно вырезать 
из доски $6\times 10$, чтобы из оставшейся ``дырявой'' доски  нельзя 
было бы вырезать больше ни одного уголка?
(С. Волченков по мотивам K\"ozepiskolai Matematikai Lapok, 2021)

2. В ряд расположено 50 монет. Изначально первые 25 монет лежат орлом вверх, 
а остальные~-- решкой. Аня и Ваня ходят по очереди, начинает Аня. За один 
ход Аня может выбрать две соседние монеты, одна из которых лежит орлом вверх, 
а вторая~-- решкой, и перевернуть обе эти монеты. Ваня за свой ход может 
выбрать две соседние монеты, обе лежащие орлом вверх или обе лежащие решкой 
вверх, и перевернуть их. Если какой-то из игроков не может сделать свой ход, 
игра заканчивается. Ваня хочет, чтобы в конце игры все монеты лежали решкой 
вверх. Может ли он играть так, чтобы гарантированно добиться желаемого?
(Упрощение задачи 2 из высшей лиги)

3. На вечеринку пришло 20 человек, некоторые из которых знакомы друг с другом. 
Назовём группу из пришедших {\it кликой}, если в ней каждый знаком с каждым. 
{\it Крутизной} человека назовём количество людей в наибольшей клике, 
куда он входит. Может ли на вечеринке оказаться 10 человек различной крутизны?

4. На доске написано число 2021. Петя приписывает к нему опять число 2021. 
Потом ещё и ещё. Так он делает 2021 раз. Докажите, что в какой-то момент 
на доске образуется число, делящееся на $2021^2$.

5. Вася расставил по кругу числа от 1 до 1000. Докажите, что найдутся 
два соседних числа, сумма которых не делится на следующее по часовой стрелке 
число.
(С. Берлов, упрощение)

6. В каждом из 4 мешков лежит по 4 монеты. В одном мешке все монеты 
имеют вес 1 г, в другом все имеют вес 2 г, в каком-то все имеют вес 3 г, 
и в каком-то все имеют вес 4 г.  Мешки снабжены надписями 1 г, 2 г, 3 г, 4 г. 
Мы хотим убедиться, что каждый мешок подписан правильно. Для этого у нас 
есть двухчашечные весы. Можно ли провести проверку с помощью всего лишь 
одного взвешивания, если разрешается использовать в нем не более 4 монет?
(Таня Хованова)

7. {\it Палиндром} -- это число, которое одинаково читается слева направо 
и справа налево. Найдите наименьший палиндром с суммой цифр 2021.
(С. Волченков. Ярославские дистанционные игры)

8. Однажды Красная Шапочка убегала от Кабана. Она бросила корзину в 30 м 
от избушки, а Кабан, оказавшийся у корзины через 5 секунд, съел пирожки 
и продолжил погоню. У избушки он оказался ровно в тот момент, 
когда Красная Шапочка захлопнула дверь. Если бы не пирожки, Красная Шапочка 
была бы поймана в 5 м от избушки. Сколько секунд Кабан ел пирожки?
(С. Токарев, Ярославские дистанционные игры)

\end 
