\nopagenumbers

\input amssym.def

\input amssym.tex

\def\geq{\geqslant}

\def\leq{\leqslant}

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

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

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

\medskip 

1. В каждой клеточке таблицы $10\times 10$ нарисована стрелка, направленная 
вверх, вниз, вправо или влево. При каком наименьшем $n$ из любой такой таблицы 
можно вычеркнуть не более $n$ стрелок так, чтобы среди оставшихся стрелок 
никакие две не были направлены друг на друга? Стрелки считаются 
направленными друг на друга, даже если между ними есть другие стрелки.
(Польша, олимпиада для юниоров, 2021) 
% комбинаторика, 8

2. Натуральное число $n$ таково, что $3n^2+3n+1$ -- точный квадрат. Докажите, 
что $\sqrt{3n^2+3n+1}$ -- сумма квадратов двух последовательных натуральных 
чисел. 
(Н.Станчу, Revista Matematica Timisoara, 195) 
% теория чисел, 3

3. В треугольнике $ABC$, в котором $AB>AC$, точка $D$ на стороне $AB$ 
такова, что $CD=BD$. Точка $M$~-- середина $AC$, точки $F$ на стороне $AC$ 
и $E$ на луче $BM$ таковы, что точки $D$, $E$ и $F$ лежат на одной прямой, 
которая параллельна $BC$. Докажите, что $CE=CF$.
(форум Art of Problem Solving, частное сообщение) 
% геометрия, 7-8

4. Дан треугольник $ABC$, в котором $AB+AC>3BC$. Внутри этого 
треугольника отмечены точки $P$ и $Q$ такие, 
что $\angle ABP=\angle PBQ=\angle QBC$ 
и $\angle ACQ=\angle QCP=\angle PCB$. Докажите, что $AP+AQ>2BC$. 
(К.Сатылханов, Казахстан, финал, 2021) 
% Геометрия, надеемся <=4

5. Множество $A$, состоящее из рациональных чисел, таково,
что если $p$, $q\in A$, то $p/q\in A$. Кроме того, если
$100\leqslant p\leqslant 101$, то $p\in A$. Докажите, что 
$A$ содержит все положительные рациональные числа.
(Индонезия, региональный этап, 2021) 
% алгебра, 5-7

6. За круглым столом сидят $N$ гостей и $N$ хозяев ($N\geq 4$). 
Два гостя разговаривают друг с другом, если между ними сидит не более одного 
человека, или если между ними сидят ровно два человека, среди которых 
по крайней мере один хозяин. Докажите, что, как бы эти $2N$ человек ни 
располагались за столом, не менее $N$ пар гостей будут разговаривать друг 
с другом. 
(Канада, 2021) 
% комбинаторика, 6-8

7. В стране некоторые пары городов соединены односторонними дорогами; 
между двумя городами может быть не более одной дороги. Правительство 
страны хочет провести реформу, поменяв направления на некоторых дорогах, 
чтобы выполнялись два свойства: 

{\it 1.} нельзя выехать из города, и, проехав по каким-то дорогам, вернуться 
в него; 

{\it 2.} самый длинный простой путь по дорогам после реформы не длиннее,
чем самый длинный простой путь до реформы. 

Докажите, что правительство сможет это сделать. Простой путь -- это такой 
путь, который через каждый город проходит не более одного раза.
(Контрольная по комбинаторике 10.01.2017, журнал Математика (Болгария), 2017 \No 1) 
% граф, надеемся не 0, но и не 3

8. Докажите, что если $x$, $y$, $z\geq 1$, то 
$$x|y-z|+y|z-x|+z|x-y|+4(x+y+z)+3xyz\geq 4(xy+yz+zx).$$ 
(М.Кукоанеш, М.Дрэган, Revista Matematica Timisoara, 164) 

\medskip 

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

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

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

\medskip 

1. В каждой клеточке таблицы $10\times 10$ нарисована стрелка, направленная 
вверх, вниз, вправо или влево. При каком наименьшем $n$ из любой такой таблицы 
можно вычеркнуть не более $n$ стрелок так, чтобы среди оставшихся стрелок 
никакие две не были направлены друг на друга? Стрелки считаются 
направленными друг на друга, даже если между ними есть другие стрелки.
(Польша, олимпиада для юниоров, 2021)
% комбинаторика 8

2. Натуральное число $n$ таково, что $3n^2+3n+1$ -- точный квадрат. Докажите, 
что $\sqrt{3n^2+3n+1}$ -- сумма квадратов двух последовательных натуральных 
чисел. 
(Н.Станчу, Revista Matematica Timisoara, 195) 
% теория чисел, 0-1

3. В треугольнике $ABC$, в котором $AB>AC$, точка $D$ на стороне $AB$ 
такова, что $CD=BD$. Точка $M$~-- середина $AC$, точки $F$ на стороне $AC$ 
и $E$ на луче $BM$ таковы, что точки $D$, $E$ и $F$ лежат на одной прямой, 
которая параллельна $BC$. Докажите, что $CE=CF$.
(форум Art of Problem Solving, частное сообщение)
% геометрия, 6

4. Дан треугольник $ABC$, в котором $AB+AC>3BC$. Внутри этого 
треугольника отмечены точки $P$ и $Q$ такие, 
что $\angle ABP=\angle PBQ=\angle QBC$ 
и $\angle ACQ=\angle QCP=\angle PCB$. Докажите, что $AP+AQ>2BC$. 
(К.Сатылханов, Казахстан, финал, 2021) 
% геометрия, 0-1

5. На доске написано число 2021. Разрешается умножать его на 
любое рациональное число от $1/2$ до $2$. Вася задумал рациональное 
положительное число. Докажите, что с помощью описанных операций Вася 
сможет получить задуманное им число.
(Индонезия, региональный этап, 2021, упрощение) 
% алгебра, 3-4

6. За круглым столом сидят $N$ гостей и $N$ хозяев ($N\geq 4$). 
Два гостя разговаривают друг с другом, если между ними сидит не более одного 
человека, или если между ними сидят ровно два человека, среди которых 
по крайней мере один хозяин. Докажите, что, как бы эти $2N$ человек ни 
располагались за столом, не менее $N$ пар гостей будут разговаривать друг 
с другом. 
(Канада, 2021) 
% комбинаторика, 4-5

7. $n\geq 2$ учеников решали $2^{n-1}$ задач. Оказалось, что для 
каждых двух задач есть ученик, который решил обе эти задачи, и ученик, 
который решил ровно одну из них. Докажите, что есть задача, которую решили все. 
(Румыния, олимпиада "Gazeta Matematica", 2021, финал) 
% комбинаторика 5

8. При каком наибольшем $n$ среди любых десяти различных натуральных чисел, не 
превосходящих $n$, обязательно найдутся три таких числа $a$, $b$ и $c$, 
что $ab>c$, $bc>a$ и $ca>b$?
(Босния и Герцеговина, отбор на юниорскую Балканиаду, 2021) 
% алгебра 6

\medskip 

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

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

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

\medskip 

1. В каждой клеточке таблицы $10\times 10$ нарисована стрелка, направленная 
вверх, вниз, вправо или влево. При каком наименьшем $n$ из любой такой таблицы 
можно вычеркнуть не более $n$ стрелок так, чтобы среди оставшихся стрелок 
никакие две не были направлены друг на друга? Стрелки считаются 
направленными друг на друга, даже если между ними есть другие стрелки.
(Польша, олимпиада для юниоров, 2021) 
% комбинаторика 7

2. Решите в натуральных числах уравнение 
$${2021-a\over a}\cdot {2021-b\over b}=2.$$
(Математический турнир Гарвард-MIT, февраль 2020, обновление) 
% теория чисел, 6

3. В треугольнике $ABC$, в котором $AB>AC$, точка $D$ на стороне $AB$ 
такова, что $CD=BD$. Точка $M$~-- середина $AC$, точки $F$ на стороне $AC$ 
и $E$ на луче $BM$ таковы, что точки $D$, $E$ и $F$ лежат на одной прямой, 
которая параллельна $BC$. Докажите, что $CE=CF$.
(форум Art of Problem Solving, частное сообщение) 
% геометрия, 4

4. В треугольнике $ABC$ угол $\angle A$ тупой и $AB=AC$. Точка $M$ 
такова, что $C$~-- середина $AM$. Серединный перпендикуляр к отрезку $AM$ 
пересекает прямую $AB$ в точке $P$. Известно, что прямые $PM$ и $BC$ 
перпендикулярны. Докажите, что $APM$~-- равносторонний треугольник.
(Казахстан, региональный этап, 2015)
% геометрия, 8

5. На доске написано число 2021. Разрешается умножать его на 
любое рациональное число от $1/2$ до $2$. Вася задумал рациональное 
положительное число. Докажите, что с помощью описанных операций Вася 
сможет получить задуманное им число.
(Индонезия, региональный этап, 2021, упрощение) 
% алгебра, 2-3

6. За круглым столом сидят $N$ гостей и $N$ хозяев ($N\geq 4$). 
Два гостя разговаривают друг с другом, если между ними сидит не более одного 
человека, или если между ними сидят ровно два человека, среди которых 
по крайней мере один хозяин. Докажите, что, как бы эти $2N$ человек ни 
располагались за столом, не менее $N$ пар гостей будут разговаривать друг 
с другом. 
(Канада, 2021) 
% комбинаторика, 2-3

7. $n\geq 2$ учеников решали $2^{n-1}$ задач. Оказалось, что для 
каждых двух задач есть ученик, который решил обе эти задачи, и ученик, 
который решил ровно одну из них. Докажите, что есть задача, которую решили все. 
(Румыния, олимпиада "Gazeta Matematica", 2021, финал) 
% комбинаторика 4

8. При каком наибольшем $n$ среди любых десяти различных натуральных чисел, не 
превосходящих $n$, обязательно найдутся три таких числа $a$, $b$ и $c$, 
что $ab>c$, $bc>a$ и $ca>b$?
(Босния и Герцеговина, отбор на юниорскую Балканиаду, 2021) 
 
\medskip 

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

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

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

\medskip 

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

2. Решите в натуральных числах уравнение 
$${2021-a\over a}\cdot {2021-b\over b}=2.$$
(Математический турнир Гарвард-MIT, февраль 2020, обновление) 
% алгебра, скорее сложная

3. Про четырёхугольник $ABCD$ известно, что $AD=AB+CD$. Биссектрисы 
углов $BAD$ и $ADC$ пересекаются в точке $P$. Докажите, что $BP=CP$.
(Киев, городская олимпиада, 2014) 

4. В треугольнике $ABC$ угол $\angle A$ тупой и $AB=AC$. Точка $M$ 
такова, что $C$~-- середина $AM$. Серединный перпендикуляр к отрезку $AM$ 
пересекает прямую $AB$ в точке $P$. Известно, что прямые $PM$ и $BC$ 
перпендикулярны. Докажите, что $APM$~-- равносторонний треугольник.
(Казахстан, региональный этап, 2015)

5. На доске написано число 1. Вася и Петя по очереди (начинает Вася) 
могут умножать или делить это число на 2, 3 или 5. Они заранее договорились, 
что тот, кто получит натуральное число от 95 до 105, будет награждён конфетой. 
В итоге число из требуемого диапазона получилось. Кто мог получить конфету? 
(А.Голованов) 

6. В государстве $n$ городов и $k$ дорог, каждые два города соединены не более чем одной дорогой.
Достигатель и Стиратель играют в игру. Сначала Стиратель помещает в один город автомобиль, а в другой город -- приз. Ход Достигателя состоит в том, что он едет на автомобиле по дороге в какой-то город;
ход Стирателя состоит в том, что он уничтожает одну дорогу. Сначала ходит Достигатель, потом Стиратель,
потом снова Достигатель и т.д. Цель Достигателя -- попасть в город с призом,
а Стиратель хочет ему помешать. При каком наименьшем $k$ Достигатель всегда 
может выиграть?

7. Клетки таблицы $11\times 1024$ (11 строчек, 1024 столбца) покрашены 
в два цвета: красный и синий. Известно, что для любых двух столбцов
есть строчка, которая пересекает их по двум синим клеткам, а также 
есть строчка, которая пересекает их по синей и красной клетке. Докажите, 
что есть столбец, в котором все клетки синие. 
% комбинаторика, скорее сложная

8. Докажите, что среди любых десяти различных натуральных чисел, 
не превосходящих 50, обязательно найдутся три таких числа $a$, $b$ и $c$, 
что $ab>c$, $bc>a$ и $ca>b$.
% алгебра, скорее средняя

\medskip 

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

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

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

\medskip 

1. Дано натуральное $n>10$. Докажите, что из всех натуральных чисел 
от 1 до $2n$ можно единственным способом выбрать $n+1$ число так, 
чтобы среди них не было трёх попарно различных, одно из которых 
является суммой двух других.
(Всеукраинский математический турнир им. академика Ляшко, устная олимпиада, 2020)

2. На празднике собрались $n$ хозяев и $n$ гостей, $n\geq 3$. Они сели 
за круглый стол. Два гостя будут говорить друг с другом, если между ними 
не более 1 человека, или если между ними два человека, хотя бы один 
из которых хозяин. Докажите, что как бы ни сели собравшиеся за круглый 
стол, хотя бы $n$ пар гостей будут друг с другом разговаривать.
(Канада, 2021)
% можно чуть усложнить, если скрыть ответ: n -- точная оценка

3. Два бегуна выбежали одновременно навстречу друг другу из пунктов A и Б 
с разными, но постоянными скоростями, при этом расстояние между ними 
сокращалось на 1 километр за 3 минуты. Бегуны встретились в точке В, 
мгновенно развернулись и побежали обратно, при этом каждый из них 
уменьшил скорость на 1 км$/$ч. Каждый из них, добежав до точки старта, 
снова развернулся и побежал навстречу другому (это могло произойти 
не одновременно). Они встретились в точке Г, мгновенно развернулись, 
и снова каждый из них уменьшил скорость на 1 км$/$ч. После очередного 
разворота в точках старта они встретились в точке Д. Известно, что 
расстояние от А до Г на 130 метров меньше, чем от А до В. Найдите 
расстояние между Г и Д.
(Япония, Вступительный экзамен Nada School, Japan, 2019) 

4. В группе из семи депутатов некоторые тройки депутатов образовали коалиции 
(депутат может быть членом нескольких коалиций). Всего образовано 6 коалиций. 
Докажите, что депутатов можно разбить на две подгруппы таким образом, 
чтобы ни одна коалиция не оказалась целиком внутри одной подгруппы.
(Задача турнира в Екатеринбурге, взятая с форума ArtofProblemSolving)

5. В каждой клетке таблицы $101\times 101$ расставлены числа 1 или $-1$. 
Для каждой строки и каждого столбца посчитали сумму чисел, стоящих в них. 
Произведение этих сумм отрицательное. Какое наибольшее (наименьшее по модулю) 
значение может принимать это произведение?
(Казахстан, городская олимпиада г. Алматы, 2012) 

6. Назовем множество натуральных чисел {\it перестановочным}, если 
для любых двух чисел из этого множества можно так переставить цифры 
в квадрате одного из них, чтобы получился квадрат второго. Например, 
множество $\{13, 14, 31\}$~-- перестановочное, так как 
$\{13^2, 14^2, 31^2\}=\{169, 196, 961\}$. Но $\{119, 121\}$~-- 
НЕ перестановочное, так как $119^2=14161$ и $121^2=14641$ имеют 
одинаковые наборы цифр, но единицы встречаются разное число раз. 
Существует ли перестановочное множество из 100 различных нечётных чисел?
(Норвегия, олимпиада им. Абеля, 2021) 

7. На доске $50\times 50$ стоит хромая ладья. За один ход она может 
смещаться только по горизонтали или только по вертикали, причем 
первым своим ходом она смещается на одну клетку, вторым~-- на две, 
третьим~-- на три, четвертым~-- на четыре, затем опять на одну, две, 
три, четыре и так далее. Можно ли выбрать клетку на доске так, чтобы, 
начав с неё, ладья могла за 2499 ходов посетить каждую клетку доски 
ровно один раз?
(Чехия и Словакия, 2016, третий тур, категория A, по мотивам)

8. Натуральные числа $x$ и $y$ таковы, что $3x^2+3x+1=y^2$. Докажите, 
что $y$ представляется в виде суммы квадратов двух последовательных 
натуральных чисел.

\medskip 

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

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

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

\medskip 

1. Дано натуральное $n>10$. Докажите, что из всех натуральных чисел 
от 1 до $2n$ можно единственным способом выбрать $n+1$ число так, 
чтобы среди них не было трёх попарно различных, одно из которых 
является суммой двух других.
(Всеукраинский математический турнир им. академика Ляшко, устная олимпиада, 2020)

2. Два бегуна выбежали одновременно навстречу друг другу из пунктов A и Б 
с разными, но постоянными скоростями, при этом расстояние между ними 
сокращалось на 1 километр за 3 минуты. Бегуны встретились в точке В, 
мгновенно развернулись и побежали обратно, при этом каждый из них 
уменьшил скорость на 1 км$/$ч. Каждый из них, добежав до точки старта, 
снова развернулся и побежал навстречу другому (это могло произойти 
не одновременно). Они встретились в точке Г, мгновенно развернулись, 
и снова каждый из них уменьшил скорость на 1 км$/$ч. После очередного 
разворота в точках старта они встретились в точке Д. Известно, что 
расстояние от А до Г на 130 метров меньше, чем от А до В. Найдите 
расстояние между Г и Д.
(Япония, Вступительный экзамен Nada School, Japan, 2019) 

3. В группе из семи депутатов некоторые тройки депутатов образовали коалиции 
(депутат может быть членом нескольких коалиций). Всего образовано 6 коалиций. 
Докажите, что депутатов можно разбить на две подгруппы таким образом, 
чтобы ни одна коалиция не оказалась целиком внутри одной подгруппы.
(Задача турнира в Екатеринбурге, взятая с форума ArtofProblemSolving)

4. В каждой клетке таблицы $101\times 101$ расставлены числа 1 или $-1$. 
Для каждой строки и каждого столбца посчитали сумму чисел, стоящих в них. 
Произведение этих сумм отрицательное. Какое наибольшее (наименьшее по модулю) 
значение может принимать это произведение?
(Казахстан, городская олимпиада г. Алматы, 2012) 

5. Назовем множество натуральных чисел {\it перестановочным}, если 
для любых двух чисел из этого множества можно так переставить цифры 
в квадрате одного из них, чтобы получился квадрат второго. Например, 
множество $\{13, 14, 31\}$~-- перестановочное, так как 
$\{13^2, 14^2, 31^2\}=\{169, 196, 961\}$. Но $\{119, 121\}$~-- 
НЕ перестановочное, так как $119^2=14161$ и $121^2=14641$ имеют 
одинаковые наборы цифр, но единицы встречаются разное число раз. 
Существует ли перестановочное множество из 100 различных нечётных чисел?
(Норвегия, олимпиада им. Абеля, 2021) 

6. На доске $50\times 50$ стоит хромая ладья. За один ход она может 
смещаться только по горизонтали или только по вертикали, причем 
первым своим ходом она смещается на одну клетку, вторым~-- на две, 
третьим~-- на три, четвертым~-- на четыре, затем опять на одну, две, 
три, четыре и так далее. Можно ли выбрать клетку на доске так, чтобы, 
начав с неё, ладья могла за 2499 ходов посетить каждую клетку доски 
ровно один раз?
(Чехия и Словакия, 2016, третий тур, категория A, по мотивам)

7. Найдите все такие пары $(a, b)$ натуральных чисел, что $a!+1=(b!-1)^2$.
(Исландия, 2019/20) 

8. В квартире живут двуногие люди, четырехногие кошки, шестиногие тараканы 
и восьминогие пауки, причём все виды присутствуют. Пауков вдвое больше, 
чем людей. Известно, что среднее количество ног у всех существ является 
целым числом. Каких существ в квартире больше всего?
(турнир в Серове, 2019)

\medskip 

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

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

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

\medskip 

1. Петя выбрал из пятидесяти первых натуральных чисел ровно 26 штук. 
Оказалось, что среди них нет трёх чисел таких, что одно из них является 
суммой двух других. Докажите, что среди выбранных Петей чисел нет числа 2.
(Упрощение задачи из высшей лиги)

2. Известно, что $A$ -- натуральное число, а $[A, 120]<500$. 
Сколько разных значений может принимать $A$?

3. Два бегуна выбежали одновременно навстречу друг другу из пунктов A и Б 
с разными, но постоянными скоростями, при этом расстояние между ними 
сокращалось на 1 километр за 3 минуты. Бегуны встретились в точке В, 
мгновенно развернулись и побежали обратно, при этом каждый из них 
уменьшил скорость на 1 км$/$ч. Каждый из них, добежав до точки старта, 
снова развернулся и побежал навстречу другому (это могло произойти 
не одновременно). Они встретились в точке Г. Середину пути между А и Б 
назовём М. Известно, что расстояние от В до Г равно 130 метрам. 
Найдите расстояние от В до М.

4. В группе из семи депутатов некоторые тройки депутатов образовали коалиции 
(депутат может быть членом нескольких коалиций). Всего образовано 6 коалиций. 
Докажите, что депутатов можно разбить на две подгруппы таким образом, 
чтобы ни одна коалиция не оказалась целиком внутри одной подгруппы.
(Задача турнира в Екатеринбурге, взятая с форума ArtofProblemSolving)

5. В каждой клетке таблицы $101\times 101$ расставлены числа 1 или $-1$. 
Для каждой строки и каждого столбца посчитали сумму чисел, стоящих в них. 
Произведение этих сумм отрицательное. Какое наибольшее (наименьшее по модулю) 
значение может принимать это произведение?
(Казахстан, городская олимпиада г. Алматы, 2012) 

6. Существует ли стозначное нечетное число $N$, сумма цифр которого равна 3, 
а в записи числа $N^2$ есть цифра 3?

7. На доске $6\times 6$ стоит хромая ладья. За один ход она может 
смещаться только по горизонтали или только по вертикали, причем ходы 
на 1 и на 2 клетки чередуются. Можно ли выбрать клетку на доске так, 
чтобы, начав с неё, ладья могла за 35 ходов посетить каждую клетку доски 
ровно один раз?
(Чехия и Словакия, 2016, третий тур, категория A, по мотивам)

8. В квартире живут двуногие люди, четырехногие кошки, шестиногие тараканы 
и восьминогие пауки, причём все виды присутствуют. Пауков вдвое больше, 
чем людей. Известно, что среднее количество ног у всех существ является 
целым числом. Каких существ в квартире больше всего?
(турнир в Серове, 2019)

\medskip 

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

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

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

\medskip 

1. Петя выбрал из пятидесяти первых натуральных чисел ровно 26 штук. 
Оказалось, что среди них нет трёх чисел таких, что одно из них является 
суммой двух других. Докажите, что среди выбранных Петей чисел нет числа 2.
(Упрощение задачи из высшей лиги)

2. Известно, что $A$ -- натуральное число, а $[A, 120]<500$. 
Сколько разных значений может принимать $A$?

3. Два бегуна выбежали одновременно навстречу друг другу из пунктов A и Б 
с разными, но постоянными скоростями, при этом расстояние между ними 
сокращалось на 1 километр за 3 минуты. Бегуны встретились в точке В, 
мгновенно развернулись и побежали обратно, при этом каждый из них 
уменьшил скорость на 1 км$/$ч. Каждый из них, добежав до точки старта, 
снова развернулся и побежал навстречу другому (это могло произойти 
не одновременно). Они встретились в точке Г. Середину пути между А и Б 
назовём М. Известно, что расстояние от В до Г равно 130 метрам. 
Найдите расстояние от В до М.

4. В группе из шести депутатов некоторые тройки депутатов образовали 
коалиции (депутат может быть членом нескольких коалиций). Всего 
образовано 9 коалиций. Докажите, что депутатов можно разбить 
на две подгруппы таким образом, чтобы ни одна коалиция не оказалась 
целиком внутри одной подгруппы.
(Задача турнира в Екатеринбурге, взятая с форума ArtofProblemSolving)

5. В каждой клетке таблицы $101\times 101$ расставлены числа 1 или $-1$. 
Для каждой строки и каждого столбца посчитали сумму чисел, стоящих в них. 
Произведение этих сумм отрицательное. Какое наибольшее (наименьшее по модулю) 
значение может принимать это произведение?
(Казахстан, городская олимпиада г. Алматы, 2012) 

6. Каждая буква русского алфавита имеет некоторую положительную цену 
(в рублях и копейках). Известно, что слово ДОКЛАД стоит ровно 50 рублей, 
МАТБОЙ -- ровно 40 рублей, КОМАНДА -- ровно 100 рублей. Может ли 
КАПИТАН стоить меньше 10 рублей?
(Кировские районные олимпиады, 2013/14 учебный год, переделка)

7. На столе лежат 4 внешне одинаковые монеты. Вес каждой монеты может 
равняться 8, 9 или 10 грамм, причем известно, что не все монеты весят 
одинаково. Есть электронные весы, которые могут указать суммарный вес 
лежащих на них монет. Как за три взвешивания выяснить, сколько монет 
каждого веса на столе? Определять, где какая монета, не обязательно.
(задача турнира в Екатеринбурге)

8. В квартире живут двуногие люди, четырехногие кошки, шестиногие тараканы 
и восьминогие пауки, причём все виды присутствуют. Пауков вдвое больше, 
чем людей. Известно, что среднее количество ног у всех существ является 
целым числом. Каких существ в квартире больше всего?
(турнир в Серове, 2019)

\medskip 

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

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

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

\medskip 

1. На озере по кругу расположены 23 камня. На них сидят 22 лягушки 
(на некоторых камнях может сидеть несколько лягушек), пронумерованные 
числами 1, 2,\dots, 22 (каждое число встречается ровно один раз). 
Каждую минуту все лягушки прыгают по следующему правилу: лягушка номер $i$ 
прыгает ровно на $i$ камней по часовой стрелке (например, лягушка 
с номером 22 прыгает на следующий против часовой стрелки камень). 
Докажите, что в какой-то момент не менее 6 камней будут свободны 
от лягушек.
(Иран, олимпиада по комбинаторике, 2021, 2 тур)

2. На доске $50\times 50$ стоит хромая ладья. За один ход она может 
смещаться только по горизонтали или только по вертикали, причем 
первым своим ходом она смещается на одну клетку, вторым~-- на две, 
третьим~-- на три, четвертым~-- на четыре, затем опять на одну, две, 
три, четыре и так далее. Можно ли выбрать клетку на доске так, чтобы, 
начав с неё, ладья могла за 2499 ходов посетить каждую клетку доски 
ровно один раз?
(Чехия и Словакия, 2016, третий тур, категория A, по мотивам)

3. Назовем множество натуральных чисел {\it перестановочным}, 
если для любых двух чисел из этого множества можно так переставить 
цифры в квадрате одного из них, чтобы получился квадрат второго. 
Например, множество $\{13, 14, 31\}$~-- перестановочное, так как 
$\{13^2, 14^2, 31^2\}=\{169, 196, 961\}$. Но $\{119, 121\}$~-- НЕ 
перестановочное, так как $119^2=14161$ и $121^2=14641$ имеют 
одинаковые наборы цифр, но единицы встречаются разное число раз. 
Существует ли перестановочное множество из 100 различных нечётных чисел?
(Норвегия, конкурс Абеля, 2021) 

4. Натуральные числа $a_1< a_2< \dots < a_n$ дают различные остатки 
при делении на $n$. Оказалось, что числа $a_1$, $a_2-a_1$, $a_3-a_2$, 
\dots, $a_n-a_{n-1}$ также дают различные остатки при делении на $n$. 
При каких $n$ такое могло случиться?
(Турция, отбор на юниорскую Балканиаду, 2021)

5. По кругу стоят 100 красных и 100 синих точек в некотором порядке. 
Пара точек одного цвета называется {\it интересной}, если между ними 
или 8, или 9 других точек. Каково наименьшее возможное количество 
интересных пар?
(Канада, 2021, существенное упрощение)  

6. В каждой клетке таблицы $7\times 7$ стоит число $1$ или $-1$. 
Для каждой строки и каждого столбца посчитали сумму чисел, стоящих в них. 
Оказалось, что произведение этих $14$ сумм отрицательно. Какое наибольшее 
значение может принимать это произведение?
(городская олимпиада г. Алматы, 2012) 

7. Можно ли каждое из чисел 1, 2, \dots, 2021 окрасить 
в один из 11 цветов таким образом, чтобы все цвета присутствовали 
и никакие три различные натуральные числа вида $(a, b, a+b)$, 
не превосходящие 2021, не были бы покрашены в три различных цвета?
(Global Quarantine Mathematical Olympiad, упрощение)

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

\medskip 

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

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

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

\medskip 

1. Квадрат можно разрезать на три прямоугольника, периметр каждого 
из которых равен 15 см, а можно разрезать на три прямоугольника, 
периметры которых одинаковые, но другие. Какие? 

2. На доске $50\times 50$ стоит хромая ладья. За один ход она может 
смещаться только по горизонтали или только по вертикали, причем первым 
своим ходом она смещается на любое нечетное число клеток, вторым~-- 
на любое четное число клеток, третьим~-- снова на любое нечетное, 
четвертым~-- снова на любое четное, и так далее. Можно ли выбрать 
клетку на доске так, чтобы, начав с неё, ладья могла за 2499 ходов 
посетить каждую клетку доски ровно один раз?
(Чехия и Словакия, 2016, третий тур, категория A, по мотивам, упрощение задачи высшей лиги)

3. Назовем множество натуральных чисел {\it перестановочным}, если 
для любых двух чисел из этого множества можно так переставить цифры 
в квадрате одного из них, чтобы получился квадрат второго. Например, 
множество $\{13, 14, 31\}$~-- перестановочное, так как 
$\{13^2, 14^2, 31^2\}=\{169, 196, 961\}$. Но $\{119, 121\}$~-- 
НЕ перестановочное, так как $119^2=14161$ и $121^2=14641$ имеют 
одинаковые наборы цифр, но единицы встречаются разное число раз. 
Существует ли перестановочное множество из 100 различных чисел?
(Норвегия, конкурс Абеля, 2021) 

4. Натуральные числа $a_1< a_2< \dots < a_n$ дают различные остатки 
при делении на $n$. Оказалось, что числа $a_1$, $a_2-a_1$, $a_3-a_2$, 
\dots, $a_n-a_{n-1}$ также дают различные остатки при делении на $n$. 
При каких $n$ такое могло случиться?
(Турция, отбор на юниорскую Балканиаду, 2021)

5. По кругу стоят 50 красных и 50 синих точек в некотором порядке. 
Пара точек одного цвета называется {\it интересной}, если они стоят 
или рядом, или через одну. Каково наименьшее возможное количество 
интересных пар?
(Канада, 2021, существенное упрощение)

6. В каждой клетке таблицы $7\times 7$ стоит число $1$ или $-1$. 
Для каждой строки и каждого столбца посчитали сумму чисел, стоящих в них. 
Оказалось, что произведение этих $14$ сумм отрицательно. Какое наибольшее 
значение может принимать это произведение?
(городская олимпиада г. Алматы, 2012) 

7. Можно ли каждое из чисел 1, 2, \dots, 2021 окрасить 
в один из 11 цветов таким образом, чтобы все цвета присутствовали 
и никакие три различные натуральные числа вида $(a, b, a+b)$, 
не превосходящие 2021, не были бы покрашены в три различных цвета?
(Global Quarantine Mathematical Olympiad, упрощение)

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

\medskip 

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

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

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

\medskip 

1. Квадрат можно разрезать на три прямоугольника, периметр каждого 
из которых равен 15 см, а можно разрезать на три прямоугольника, 
периметры которых одинаковые, но другие. Какие? 

2. На доске $12\times 12$ стоит хромая ладья. За один ход она может 
смещаться только по горизонтали или только по вертикали, причем в каждый 
свой нечетный ход ладья смещается на одну клетку, а в каждый четный ход~-- 
на две. Считается, что при ходе на две клетки она посещает и ту клетку, 
которую перепрыгнула. На каких полях может стоять хромая ладья в начале, 
чтобы она могла обойти каждое поле доски, не посещая ни одну клетку дважды?
(Чехия и Словакия, 2016, третий тур, категория A, модификация) 

3. Аня и Беня играют в игру. Перед ними две кучки спичек: 
в первой 100 спичек, во второй 200. Игроки по очереди (начинает Аня) 
должны брать 1 или 2 спички из большей кучки (если в кучках спичек 
поровну -- из любой). Проигрывает тот, кто не может сделать ход. 
Кто может обеспечить себе победу?
(С. Волченков по фольклорным мотивам)

4. Натуральные числа $a_1< a_2< \dots < a_{11}$ дают различные остатки 
при делении на 11. Может ли так случиться, что числа $a_1$, $a_2-a_1$, 
$a_3-a_2$, \dots, $a_{11}-a_{10}$ также дают различные остатки при делении 
на 11?
(Турция, отбор на юниорскую Балканиаду, 2021, упрощение) 

5. По кругу стоят 50 красных и 50 синих точек в некотором порядке. 
Пара точек одного цвета называется {\it интересной}, если они стоят 
или рядом, или через одну. Каково наименьшее возможное количество 
интересных пар?
(Канада, 2021, существенное упрощение)

6. В каждой клетке таблицы $7\times 7$ стоит число $1$ или $-1$. 
Для каждой строки и каждого столбца посчитали сумму чисел, стоящих в них. 
Оказалось, что произведение этих $14$ сумм отрицательно. Какое наибольшее 
значение может принимать это произведение?
(городская олимпиада г. Алматы, 2012) 

7. Назовем множество натуральных чисел {\it перестановочным}, если 
для любых двух чисел из этого множества можно так переставить цифры 
в квадрате одного из них, чтобы получился квадрат второго. Например, 
множество $\{13, 14, 31\}$~-- перестановочное, так как 
$\{13^2, 14^2, 31^2\}=\{169, 196, 961\}$. Но $\{119, 121\}$~-- 
НЕ перестановочное, так как $119^2=14161$ и $121^2=14641$ имеют 
одинаковые наборы цифр, но единицы встречаются разное число раз. 
Существует ли перестановочное множество из 100 различных чисел?
(Норвегия, конкурс Абеля, 2021) 

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

\medskip 

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

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

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

\medskip 

1. Квадрат можно разрезать на три прямоугольника, периметр каждого 
из которых равен 15 см, а можно разрезать на три прямоугольника, 
периметры которых одинаковые, но другие. Какие? 

2. На доске $6\times 6$ стоит хромая ладья. За один ход она может смещаться 
только по горизонтали или только по вертикали, причем в каждый свой нечетный 
ход ладья смещается на одну клетку, а в каждый четный ход~-- на две. 
Считается, что при ходе на две клетки хромая ладья посещает и ту клетку, 
которую перепрыгнула. На каких полях может стоять хромая ладья в начале, 
чтобы она могла обойти каждое поле доски, не побывав ни на одном поле дважды?
(Чехия и Словакия, 2016, третий тур, категория A, модификация) 

3. Аня и Беня играют в игру. Перед ними две кучки спичек: 
в первой 100 спичек, во второй 200. Игроки по очереди (начинает Аня) 
должны брать 1 или 2 спички из большей кучки (если в кучках спичек 
поровну -- из любой). Проигрывает тот, кто не может сделать ход. 
Кто может обеспечить себе победу?
(С. Волченков по фольклорным мотивам)

4. Натуральные числа $a_1< a_2< \dots < a_{10}$ заканчиваются 
на различные цифры. Может ли случиться, что числа $a_1, a_2-a_1, a_3-a_2, 
\dots, a_{10}-a_{9}$ также заканчиваются на различные цифры? 
(Турция, отбор на юниорскую Балканиаду, 2021, частный случай) 

5. Какое наименьшее количество последовательных чисел, меньших 2021, 
можно перемножить, чтобы результат поделился на 2021? 
(Ярославские дистанционные игры) 

6. В мастерской выбивают надписи на камне. За каждую букву установлена цена.
Слово ВОЛ обойдётся заказчику в 150 рублей, ОЛОВО -- в 230 рублей, 
СТОК -- в 200 рублей. Сколько надо заплатить за слово ОТКОС?
(Кировская районная олимпиада, 2013/14, переделка)

7. Пожилой математик в своих мемуарах вспомнил, что в $N$-м году 
он записал на доске числа 1, 2, 3, \dots , $N$, некоторые красным 
маркером, остальные -- зелёным. Оказалось, что разность между 
суммой красных чисел и суммой зелёных чисел равна $N$. Дело происходило, 
по его воспоминаниям, то ли в 2021-м, то ли в 2022-м году. Так в какие 
из этих лет такое могло произойти?
(Индонезия, региональный этап, 2021, вольный перевод) 

8. На болоте в ряд расположена 2021 кочка. В соревнованиях по прыжкам 
участвуют лягушки с номерами от 1 до 2021, все стартуют с первой кочки. 
Лягушка с номером $k$ делает прыжки на $k$ кочек вперёд. Если прыгать 
дальше некуда, лягушка останавливается. Есть ли такая кочка, на которой 
остановятся больше 30 лягушек?
(С. Волченков. по мотивам Ярославских дистанционных игр) 

\end 

