Тема ТурГор (Турнир Городов)

Турнир городов - задания по годам

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела тургор (турнир городов)

Разделы подтемы Турнир городов - задания по годам

Турнир городов 2015 и ранее

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 21#76582Максимум баллов за задание: 7

Назовём расположенный в пространстве треугольник $ABC$ удобным, если для любой точки $P$ вне его плоскости из отрезков $PA,PB$ и $P C$ можно сложить треугольник. Какие углы может иметь удобный треугольник?

Подсказки к задаче

Подсказка 1

Если поразмыслить над этой задачей, порисовать какие-то треугольники и точки Р, можно понять, что если брать точку Р очень близко к одной из вершин (допустим, к А), выполнение неравенства треугольника для РА, РВ, РС сводится к тому, что АВ и АС не могут быть сильно отличны по длине.

Подсказка 2

Конечно, мысли из первой подсказки нужно формализовать. Тогда мы придем к тому, что если условие задачи выполнено, то треугольник АВС равносторонний. Теперь для равностороннего треугольника нужно доказать, что для любой точки P условие задачи выполнено.

Подсказка 3

Доказывать это можно по-разному. Один из способов (красивый) — явно построить треугольник со сторонами, равными PA, PB и РС, используя подобия.

Показать ответ и решение

$PIC$

Докажем сначала, что неравносторонний треугольник под условие подходить не может. Предположим противное, пусть такой треугольник $ABC$ есть и в нём $AB ⁄= AC,$ причём длины этих сторон различаются хотя бы на $d.$

Рассмотрим точку $P,$ расположенную на перпендикуляре к плоскости $ABC,$ проходящем через точку $A,$ на расстоянии $𝜀$ от $A.$ Тогда

∘ ------- ∘ ------- PB = AB2+ 𝜀2, PC = AC2 +𝜀2

Можно выбрать $P$ настолько близко к вершине $A,$ уменьшая $𝜀,$ чтобы $PB$ и $P C$ отличались соответственно от $AB$ и $AC$ меньше, чем на $d∕3,$ и чтобы $𝜀$ было меньше $d∕3.$ Тогда стороны $PB$ и $P C$ будут различаться более чем на $d∕3,$ а длина стороны $P A$ меньше $d∕3$ — противоречие с неравенством треугольника.

Покажем теперь, что равносторонний треугольник удобен. Пусть $AB = BC =CA.$ Отметим на лучах $PA,PB,P C$ точки $A1,B1,C1$ так, чтобы выполнялись равенства:

AB ⋅P A1 = PB ⋅PC

BC ⋅PB1 = PC ⋅PA

CA ⋅PC1 = PB ⋅PA

Треугольники $APB$ и $B1P A1$ подобны по углу и отношению двух сторон, откуда

A1B1 = AB-⋅P-A1= PC PB

$PIC$

Аналогично вычисляем длины остальных сторон. Получаем, что треугольник $A1B1C1$ — искомый.

Ответ:

$60∘,60∘,60∘$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 22#76583Максимум баллов за задание: 7

Дан клетчатый квадрат $n× n,$ где $n> 1.$ Кроссвордом будем называть любое непустое множество его клеток, а словом — любую горизонтальную и любую вертикальную полоску (клетчатый прямоугольник шириной в одну клетку), целиком состоящую из клеток кроссворда и не содержащуюся ни в какой большей полоске из клеток кроссворда (ни горизонтальной, ни вертикальной). Пусть $x$ количество слов в кроссворде, $y$ — наименьшее количество слов, которыми можно покрыть кроссворд. Найдите максимум отношения $x y$ при данном $n.$

Источники: Турнир городов - 2022, 11.3 (см. www.turgor.ru)

Подсказки к задаче

Подсказка 0

Минимальное количество слов в кроссворде не совпадает с общим количеством слов в случае, когда какие-то слова идут параллельно друг другу и имеют общую границу клеток.

Подсказка 1

Для начала получим оценку. Рассмотрим, ско́льким словам может принадлежать одна клетка. Сколько среди них может быть вертикальных и горизонтальных? Сколько могут не принадлежать минимальному разложению?

Подсказка 2

Верно, каждая клетка содержится максимум в одном горизонтальном и одном вертикальном слове. Назовём слова из минимального покрытия кроссворда правильными, все остальные - неправильными. Каждая клетка должна принадлежать хотя бы одному правильному слову. Что тогда можно сказать об общем количестве клеток в неправильных словах?

Подсказка 3

Правильно, каждая клетка входит не более чем в одно неправильное слово, тогда сумма клеток в таких словах не больше общего количества клеток в кроссворде (пусть всего их z). Теперь, когда нам известна верхняя граница на количество клеток в таких словах, мы можем найти верхнее ограничение на количество самих неправильных слов, если разделим z на минимум клеток в одном неправильном слове

Подсказка 4

Так как слова, состоящие из одной клетки точно правильные, то в одном неправильном слове хотя бы 2 клетки. Аналогично найдём количество правильных слов: сначала выясним, сколько суммарно букв в правильных словах (воспользуемся тем, что правильные слова покрывают все клетки) и поделим на минимальное количество букв в одном правильном слове.

Подсказка 5

Остаётся только найти искомое отношение и составить подходящий пример. Такой случай легко находится, если вспомнить, что максимальное количество неправильных слов достигается, когда в одном неправильном слове 2 клетки.

Показать ответ и решение

Пример. Для прямоугольника $n ×2$ получаем $x =n +2,y = 2.$

Оценка. Пусть в кроссворде $z$ клеток. Выберем некоторое его покрытие наименьшим количеством слов. Слова из этого покрытия назовём правильными, а остальные неправильными.

Каждая клетка содержится не более чем в одном горизонтальном и одном вертикальном слове. Хотя бы одно из этих слов правильное, так как правильные слова покрывают весь кроссворд. Значит, каждая клетка принадлежит не более чем одному неправильному слову. Поэтому сумма количеств клеток в неправильных словах не больше $z.$

Если клетка является словом, то к ней не примыкает другая клетка кроссворда ни по горизонтали, ни по вертикали. Следовательно, клетка входит в любое покрытие кроссворда словами и, значит, является правильным словом. Поэтому все неправильные слова содержат не меньше чем по две клетки и количество неправильных слов не больше $z 2.$

Так как правильные слова покрывают весь кроссворд, сумма количеств клеток в них не меньше $z.$ Каждое слово содержит не больше $n$ клеток, поэтому количество правильных слов не меньше $z n$ Отсюда

z xy ≤ 1+ 2z-=1 + n2 n

Ответ:

$1+ n 2$

Ошибка.
Попробуйте повторить позже

Задача 23#76584Максимум баллов за задание: 7

На доске написана функция $sinx +cosx.$ Разрешается написать на доске производную любой написанной ранее функции, а также сумму и произведение любых двух написанных ранее функций, так можно делать много раз. В какой-то момент на доске оказалась функция, равная для всех действительных $x$ некоторой константе $c.$ Чему может равняться $c?$

Источники: Турнир городов - 2022, 11.4 (см. www.turgor.ru)

Подсказки к задаче

Подсказка 1

Для начала давайте попробуем взять несколько производных, перемножить что-нибудь — в общем, сделать несколько итераций. Видно, что все, что окажется на доске - многочлены от sin(x) и cos(x). Это можно и нужно доказать, но давайте сначала идейно. Если мы уже пощупали как себя ведут выражения, то может нам теперь попытаться что-то явно получить? Какую-то константу, к примеру.

Подсказка 2

Заметим, что эту константу только синусом или только косинусом не получить. Давайте возьмем f(x) = cos(x) + sin(x) и посмотрим на производные. Заметим, что f(x) * f(x) + f’(x) * f’(x) = 2. То есть все целые, четные значения, больше 0, мы можем получить. А что с целыми, четными и меньшими 0?

Подсказка 3

Верно, их тоже можно получить, к примеру, как сумму f(x) * f’’(x) + f’(x) * f’’’(x) = -2. Но ведь это всего лишь целые, и то не все. Попробовав так по складывать, да по умножать, можно понять эмпирически, что нечетные целые не получить, а уж что делать с не целыми и ума не приложить. В таких моментах не стоит ничего говорить, а только попытаться доказать, что это невозможно. Как? А мы использовали где-то наши рассуждения про многочлен? Может быть самое время?

Подсказка 4

Мы же можем посмотреть на значение в нуле. Ведь, тогда и sin(x), и cos(x) - целые числа. Значит, и многочлен от них - целое число в этой точке, а значит, если он тождественно константа, то эта константа - целая. Тогда, остается доказать про нечетные целые числа, что их нельзя получить. Давайте сделаем такой трюк. Если у нас все выражается через sin и cos, то это значит, что все выражается через sin(x) + cos(x) и sin(x) - cos(x). Но эти числа равны sqrt(2) * cos(x - pi/4) и sqrt(2) * sin(x - pi/4). Появилась иррациональность. А у нас только целые числа могут быть. Что из этого можно выгадать?

Подсказка 5

А в общем-то, все, что нам и нужно. Ведь если подставить pi/4, то получим, что при нечетных степенях, у cos будет либо иррациональный коэффициент, либо нулевой. А это значит, что сумма коэффициентов перед нечетными степенями равна 0), но ровно это и означает, что значение четно. Победа.

Показать ответ и решение

Любая функция, полученная описанным способом, — многочлен от $sinx$ и $cosx$ с целыми коэффициентами. Доказательство индукцией по числу шагов: исходная функция имеет такой вид; производная многочлена с целыми коэффициентами — многочлен с целыми коэффициентами; аналогичное верно для суммы и произведения. При $x= 0$ синус и косинус принимают целые значения, поэтому значение многочлена от них с целыми коэффициентами — целое, то есть $c$ целое.

Положим

f(x)= sinx+ cosx

Запишем на доску

′ f (x)= cosx− sinx

′′ f (x)= − sinx − cosx

f′′′(x)= − cosx+ sinx

Тогда

f2(x)+f′2(x)= (sin x+cosx)2 +(cosx − sinx)2 = 2

Аналогично

f(x)f′′(x)+ f′(x)f′′′(x)= −2

Суммируя такие функции, получаем все чётные константы.

Покажем, что нечётную константу получить нельзя. Заметим, что

(π ) π ( π) √- ( π) sinx+ cosx =sin x+ sin 2 − x = 2sin 4 cos x− 4 = 2 cos x− 4

Поэтому все функции, которые можно получить, — это многочлены от $√- ( ) 2cosx− π4$ и $√- ( ) 2 sin x− π4$ с целыми коэффициентами и нулевым свободным членом. При $x= π4$ остаются лишь члены с косинусом (равным 1). Коэффициенты при чётных степенях косинуса чётны, а при нечётных либо иррациональны, либо равны нулю. Целочисленное значение получится, если сумма коэффициентов при нечётных степенях равна 0, но тогда значение чётно, что и требовалось доказать.

Ответ:

Любому чётному числу.

Ошибка.
Попробуйте повторить позже

Задача 24#76585Максимум баллов за задание: 7

На доске написана буква А. Разрешается в любом порядке и количестве:

а) приписывать А слева;

б) приписывать Б справа;

в) одновременно приписывать Б слева и А справа.

Например, БААБ так получить можно ( А $→$ БАA $→$ БААБ), а АББА — нельзя.

Докажите, что при любом натуральном $n$ половину слов длины $n$ получить можно, а другую половину — нельзя.

Источники: Турнир городов - 2022, 11.6 (см. www.turgor.ru)

Подсказки к задаче

Подсказка 1

В задаче фигурирует n, поэтому имеет смысл порешать ее индукцией. Количество всех слов посчитать несложно, поэтому мы знаем, сколько слов хочется сделать достижимыми. А что делать при переходе? Какие случаи нужно разобрать?

Подсказка 2

Для каждой из операций нужно посмотреть, сколько таких слов существует. Однако заметим, что могут быть повторы слов. Слова при каких операциях могут пересекаться?

Подсказка 3

Посчитайте, сколько есть слов вида AWБ. Заметим, что именно такое количество слов посчитано дважды :)

Показать доказательство

Назовем слова, которые можно получить, достижимыми. Всего существует $2n$ различных слов длины $n,$ поэтому достаточно доказать, что количество достижимых слов длины $n$ равно $n−1 2 .$ Докажем это утверждение по индукции.

База индукции. Для $n =1$ и $n =2$ это легко проверяется: А $→$ АА, А $→$ АБ.

Шаг индукции. Пусть для всех длин, не превосходящих $n,$ утверждение верно. Посмотрим, как можно получить слово длины $n +1:$

1.: из слова длины $n,$ применив операцию а): W $→$ АW
2.: из слова длины $n,$ применив операцию б): W $→$ WБ
3.: из слова длины $n − 1,$ применив операцию в): W $→$ БWА

Слов 1-го и 2-го типа по $2n−1,$ а слов 3-го типа $− 2n−2.$ При этом слова 3-го типа не могут совпадать со словами 1-го и 2-го типа. А вот множества слов 1-го и 2-го типа пересекаются. Их общие слова имеют вид А $w$ Б. Докажем, что слова $w$ (которые находятся между буквами А и Б) — это все достижимые слова длины $n − 1.$ Понятно, что если $w$ — достижимое слово, то за две операции из него можно получить А $w$ Б. С другой стороны, если слово $w$ Б достижимое, то посмотрим, как оно было получено. Если проделать все те же операции, но пропустить приписывание последней буквы Б, то будет получено слово $w,$ значит, оно достижимое.

Таким образом, общих слов 1-го и 2-го типа столько же, сколько достижимых слов длины $n− 1,$ то есть $2n−2.$ Следовательно, количество слов длины $n+ 1$ равно $2n−1+ 2n−1− 2n−2+ 2n−2 = 2n,$ что и требовалось доказать.

Ошибка.
Попробуйте повторить позже

Задача 25#76741Максимум баллов за задание: 7

Дан отрезок $[0;1]$ . За ход разрешается разбить любой из имеющихся отрезков точкой на два новых отрезка и записать на доску произведение длин этих двух новых отрезков. Докажите, что ни в какой момент сумма чисел на доске не превысит $1 2$ .

Источники: Турнир городов - 2022, осенний тур, базовый вариант, 11.5

Подсказки к задаче

Подсказка 1

Давайте попытаемся понять, как выглядит сумма чисел на доске в общем виде. Начнём разбивать наш отрезок и записывать числа. На втором разбиении попробуйте заменить один из отрезков на сумму двух. У вас получится просто сумма попарных произведений всех длин. Как тогда наша сумма будет выглядеть в общем виде? Докажите это по индукции.

Подсказка 2

Верно, в итоге, у нас получится сумма всевозможных попарных произведений отрезков. База понятна, а дальше нужно по аналогии в сумме заменить длину вновь разбитого отрезка через сумму двух новых. Отлично, с этим справились! Заметим, что нам известна сумма всех отрезков. Как можно выразить теперь сумму попарных произведений для удобной оценки?

Подсказка 3

Точно, ведь нашу сумму можно выразить через разность квадрата суммы всех отрезков и суммы квадратов каждого из отрезков. Только нужно ещё поделить пополам. Вот тут нам и пригодится знание про сумму отрезков. Осталось понять, почему мы получили требуемое, и победа!

Показать доказательство

Пусть через $n$ шагов мы поделили отрезок на отрезки $x ,x,...,x 1 2 n$ . Индукцией по $n$ покажем, что сумма чисел, записанных на доске, равна сумме всевозможных попарных произведений чисел $x1,x2,...,xn$ .

База очевидна.

Переход: Пусть на $n−$ шаге сумма равна $x1x2+ ...+ xn−1xn$ . На $n+ 1$ -м шаге мы делим $i$ -й отрезок на отрезки $a$ и $b$ , тогда сумма примет вид:

x1x2+ ...+ xn−1xn+ (a+ b)(x1+ x2+...+xn)+ ab

В данном случае $xx + ...+ x x 1 2 n−1n$ — попарные произведения чисел $x,x ,...,x 1 2 n$ без $x i$ , а $x + x + ...+x 1 2 n$ — сумма этих же чисел без $xi$ . Таким образом, на $n+ 1$ -м шаге также получили всевозможные попарные произведения.

Тогда задача свелась к тому, что нужно доказать, что сумма всевозможных попарных произведений чисел меньше $1 2$ , если их сумма равна $1$ , а это следует, например, из того, что:

(x1+ x2+...+xn)2− (x2+ x2+...+x2) x1x2+ ...+xn−1xn =----------------2--1---2------n- =

2 2 2 = 1−-(x1+-x2+-...+xn)-< 1. 2 2

Ошибка.
Попробуйте повторить позже

Задача 26#82168Максимум баллов за задание: 7

Дан отрезок $AB.$ Точки $X, Y, Z$ в пространстве выбираются так, чтобы $ABX$ был правильным треугольником, а $ABY Z$ – квадратом. Докажите, что ортоцентры всех получающихся таким образом треугольников $XY Z$ попадают на некоторую фиксированную окружность.

Источники: Турнир городов - 2022, осенний тур, базовый вариант, 11.4

Подсказки к задаче

Подсказка 1

Что мы имеем? Равносторонний треугольник — симметричная фигура, квадрат тоже крут в этом плане. Может быть тогда треугольник XYZ имеет похожие свойства?

Подсказка 2

Попробуйте доказать, что треугольник XYZ — равнобедренный. Как же это сделать? Ну, например, можно честно, рас писать равенства сторон и так далее. Либо же воспользоваться прекрасным преобразованием — симметрией.

Подсказка 3

Отметим серединки AB и ZY — M, N соответственно, рассмотрим плоскость NMX, скажем пару волшебных слов и готово:) Что же дальше?

Подсказка 4

Треугольник XYZ — равнобедренный. Что тогда можно сказать про его ортоцентр?

Подсказка 5

Он лежит на XN — серпере к YZ. Уже неплохо:) Ключевая идея в подобных задачах: угадать окружность или сферу (от задачи зависит), но изредка, прям редко, может быть иначе (не стоит об этом забывать). Итак, хотим угадать сферу. Всё так симметрично относительно плоскости XMN. Кажется, стоит искать эту окружность в этой плоскости. Теперь, следующее понимание: весь сюжет вращается вокруг AB, кажется, что центр искомой окружности тоже лежит на нём. Итак, что мы имеем?

Подсказка 6

Гипотеза: центр искомой окружности — точка M. Что же делать с радиусом? Угадать бы какую-нибудь точку окружности было бы славно. Как же это можно делать? Ну, например, рассмотреть экстремальные случаи. Ну, советую рассмотреть случай, когда квадрат и треугольник в одной плоскости (ну и там уже можно координатно или в синусах посчитать, или в теорема Пифагора)

Подсказка 7

Так или иначе вы доказали, что одно из положений ортоцентра — это точка X. Теперь хотим в общем виде доказать, что все ортоценты лежат на окружности с центром в M и радиусом MX. Теперь подумаем, как же это сделать? Для этого стоит отметить точки S, T на прямой MN по обе стороны от M так, чтобы MS = MT = MX (T на отрезке MN). Как быть дальше?

Подсказка 8

Считать уголки — так себе идея... Но что мы еще умеем делать, чтоб доказывать вписанность?

Подсказка 9

Степень точки! Самой приятной кажется точка N. То есть осталось доказать, что NT*NS = NH*NX, где H — ортоцентр XYZ. Теперь пусть AB = a. Осталось написать пару теорем Пифагора, немного повыражать и доказать равенство, а как следствие, и решение задачи у нас в кармане)

Показать доказательство

$PIC$

Пусть $M$ — середина $AB, N$ — середина $YZ.$ Рассмотрим плоскость $AXB.$ Заметим, что прямая $AB$ перпендикулярна прямым $XM$ и $MN,$ а значит она перпендикулярна плоскости $XMN.$ Следовательно, $XMN ⊥ ABY.$ Нетрудно видеть, что при симметрии относительно плоскости $XMN$ отрезок $XZ$ перейдёт в отрезок $XY,$ то есть $XY = XZ.$ Таким образом, ортоцентр $H$ треугольника $XY Z$ лежит на отрезке $XN$ — серединном перпендикуляре $Y Z.$

Покажем, что $H$ лежит на окружности $ω$ с центром $M,$ радиусом $XM,$ лежащей в плоскости $XMN.$ Для этого определим на отрезке $MN$ точку $T$ такую, что $MT =XM,$ и точку $S$ — вторичное пересечение прямой $MN$ с $ω.$ Осталось посчитать, что четырёхугольник $SMHX$ — вписанный, то есть доказать равенство $NT ⋅NS = NH ⋅NX.$

Пусть длина стороны квадрата и правильного треугольника равна $2a.$ Из подобия треугольников $HNZ$ и $NXZ$ нетрудно получить, что $NH ⋅NX =a2.$ Также понятно, что

NT = MN − XM = (2− √3)a

NS = MN +XM = (2+ √3)a

откуда $NT ⋅NS = a2.$ Получили нужное равенство.

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 27#92423Максимум баллов за задание: 7

Каждая из функций $f(x)$ и $g(x)$ определена на всей числовой прямой и не является строго монотонной. Может ли быть, что и их сумма, и их разность строго монотонны на всей числовой прямой?

Источники: Тургор - 2021, 11.1, устный тур (см. turgor.ru)

Подсказки к задаче

Подсказка 1

Запишем сумму и разность f(x) и g(x). Как сами f(x) и g(x) выражаются через них? Помните, что сумма и разность – строго монотонные функции.

Подсказка 2

Положим F(x) = f(x) + g(x), G(x) = f(x) – g(x). Заметим, что f(x) = (F(x) + G(x))/2, g(x) = (F(x) – G(x))/2. Теперь попробуем искать противоречие. Нам говорят, что и сумма, и разность – монотонны. Предположим, что они ведут себя одинаково (либо обе возрастают, либо обе убывают). Что тогда?

Подсказка 3

Если F(x) и G(x) ведут себя одинаково, то f(x) будет либо монотонно возрастать, либо монотонно убывать! Такс, а если одна из функций (F(x) или G(x)) возрастающая, а вторая убывающая?

Подсказка 4

В таком случае посмотрим на g(x) и заменим F(x) на –F(x) или G(x) на –G(x)! Мы получим ситуацию, аналогичную с f(x).

Показать ответ и решение

Положим

F(x) =f(x)+g(x), G(x) =f(x)− g(x)

Тогда

F-(x)+-G(x) F(x)− G-(x) f(x)= 2 , g(x)= 2

Пусть $F$ и $G$ строго возрастают (соответственно, строго убывают). Тогда $f$ как их полусумма строго возрастает (соответственно, строго убывает), что противоречит условию.

Если же какая-то из функций $F$ и $G$ строго возрастает, а другая строго убывает, то обе функции $F$ и $− G$ строго возрастают или строго убывают. Следовательно, их полусумма $g$ строго монотонна — снова противоречие с условием.

Ответ: нет

Ошибка.
Попробуйте повторить позже

Задача 28#92424Максимум баллов за задание: 7

Петя и Вася по очереди красят рёбра $N$ -угольной пирамиды: Петя — в красный цвет, а Вася — в зелёный (ребро нельзя красить дважды). Начинает Петя. Выигрывает Вася, если после того, как все рёбра окрашены, из любой вершины пирамиды в любую другую вершину ведёт ломаная, состоящая из зелёных рёбер. В противном случае выигрывает Петя. Кто из игроков может действовать так, чтобы всегда выигрывать, как бы ни играл его соперник?

Источники: Тургор - 2021, 11.2, устный тур (см. turgor.ru)

Подсказки к задаче

#92424

Подсказка 1
Если у каждой вершины будет зелёный "выход" к верхней, то Вася победит. У пирамиды N ребёр в основании и N ведут к основанию — попробуем разбить на пары рёбра с общей вершиной по принципу (боковое, в основании) и рассмотреть картинку.

Подсказка 2

Пусть Вася каждым ходом красит ребро, "парное" тому, которое только что покрасил Петя. Что будет, если Петя хотя бы раз покрасит одно ребро в основании пирамиды?

Подсказка 3

Верно, Вася сможет соединить все вершины "зелёным путём". Тогда что, если Петя решит красить исключительно боковые рёбра?

Подсказка 4

Рассмотрите предпоследний ход Васи!

Показать ответ и решение

Пусть $O$ — вершина пирамиды, $A A ...A 1 2 N$ — её основание. Разобьём все рёбра пирамиды на пары смежных, одно из которых боковое, а другое лежит в основании:

(OA1,A1A2),(OA2,A2A3),...,(OAN,AN A1)

На каждый ход Пети Вася может отвечать в ту же пару, то есть красить в зелёный цвет ребро из той пары, в которой Петя только что покрасил второе ребро в красный. Если Петя покрасит хотя бы одно ребро в основании пирамиды, то в ответ Вася покрасит боковое ребро из той же пары, пусть это, например, ребро $OA N$ . Так как в конце игры вершина $A N− 1$ соединена зелёным ребром либо с $O$ , либо с $A N$ , то из неё можно дойти по зелёным рёбрам до $O$ . Далее, вершина $A N−2$ соединена либо с $O$ , либо с $A N− 1$ , из которой есть путь по зелёным рёбрам до $O$ . Следовательно, и из вершины $AN−2$ можно добраться до $O$ по зелёным рёбрам. Продолжая эти рассуждения, получим, что из всех вершин можно дойти по зелёным рёбрам до вершины $O$ , а это значит, что Вася победил.

Таким образом, чтобы не проиграть, Петя должен красить только боковые рёбра. После его предпоследнего хода неокрашенными останутся ребро из пары, в которую он только что сходил, и два ребра ещё из одной пары. Тогда в ответ Вася может покрасить в зелёный цвет последнее неокрашенное боковое ребро, после чего они покрасят ещё по одному ребру в основании. В итоге зелёным цветом будут покрашены все рёбра в основании пирамиды, кроме одного, а также одно боковое ребро, поэтому каждые две вершины будут соединены путём из зелёных рёбер. Значит, и в этом случае Вася победит.

Ответ: Вася

Ошибка.
Попробуйте повторить позже

Задача 29#92425Максимум баллов за задание: 7

Точка $I$ — центр вписанной окружности треугольника $ABC$ , а $T$ — точка касания этой окружности со стороной $AC$ . Пусть $P$ и $Q$ — ортоцентры треугольников $BAI$ и $BCI$ соответственно. Докажите, что точки $T,P,Q$ лежат на одной прямой.

Источники: Тургор - 2021, 11.3, устный тур (см. turgor.ru)

Подсказки к задаче

Подсказка 1

Самый простой способ доказать, что точки Q, T, P лежат на одной прямой - это показать, что ∠QTC = ∠ATP. Однако простым счётом уголков к ∠QTC и ∠ATP не подобраться. Тогда можно попробовать доказать это через подобие треугольников ATP и QTC.

Подсказка 2

Воспользуемся тем, что P и Q — ортоцентры. Мы получаем, что AP ⊥ BE и QC ⊥ BE. Что тогда можно сказать про прямые AP и BE?

Подсказка 3

Верно! Они же параллельные, а значит, ∠PAT = ∠QCT. Отлично! Теперь для подобия осталось лишь показать, что AT/AP = CT/CQ. Но мы ещё никак не использовали, что T — точка касания. Отметьте две другие точки касания вписанной окружности с треугольником и попробуйте переносить отрезки.

Подсказка 4

Теперь мы получаем, что достаточно доказать, что AK/AP = CL/CQ (L - точка касания вписанной окружности с BC). Можно заметить, что это стороны △APK и △CQL. Что можно сказать про эти треугольники?

Показать доказательство

Первое решение.

Случай $AB =BC$ очевиден. Иначе основания $F$ и $E$ высот $AF$ и $CE$ лежат на биссектрисе $BI$ по разные стороны от $AC$ , прямые $AP$ и $CQ$ параллельны и $∠PAT = ∠FAT =∠ECT =∠QCT$ . Задача будет решена, если мы докажем подобие треугольников $TAP$ и $TCQ$ (тогда равные углы $CT Q$ и $ATP$ вертикальны и точки $P,Q,T$ лежат на одной прямой). Для этого достаточно проверить, что $AT ∕AP = CT∕CQ$ .

$PIC$

Пусть $K$ и $L$ — точки касания окружности со сторонами $AB$ и $BC$ соответственно. Тогда $AT = AK,CT = CL$ , и осталось доказать равенство $AK ∕AP = CL∕CQ$ . Оно следует из подобия треугольников $AP K$ и $CQL$ : они прямоугольные, а поскольку $BI$ — биссектриса угла $B$ , углы $BAP$ и $BCQ$ равны.

Второе решение.

Так как $AP$ содержит высоту треугольника $ABI$ , то $AP ⊥ BI$ . Пусть $K$ — точка касания $AB$ со вписанной окружностью, так что $K = PI∩ AB$ . Тогда

TA∕PA = KA∕PA = sin∠AP K = sin∠ABI = sin ∠B 2

Аналогично $CQ ⊥ BI$ , откуда $CQ ∥AP$ . И также $TC∕QC = sin∠B- 2$ , откуда $T A∕PA =TC ∕QC$ . Таким образом, $△T AP ∼ △TCQ$ . Значит, $∠AT P =∠CT Q$ , откуда и следует, что $T,P,Q$ на одной прямой.

Ошибка.
Попробуйте повторить позже

Задача 30#92426Максимум баллов за задание: 7

Возрастающая последовательность натуральных чисел $a < a <... 1 2$ такова, что при каждом целом $n> 100$ число $a n$ равно наименьшему натуральному числу, большему чем $an−1$ и не делящемуся ни на одно из чисел $a1,a2,...,an−1$ . Докажите, что в такой последовательности лишь конечное количество составных чисел.

Источники: Тургор - 2021, 11.4, устный тур (см. turgor.ru)

Подсказки к задаче

Подсказка 1

Нам нужно доказать, что начиная с какого-то m все числа нашей последовательности станут простыми. Допустим, что для какого-то n > m выполняется aₙ = d*t, где t ≤ d. Из условия мы понимаем, что d у нас не является числом вида aₖ, где k < m. Тогда как мы можем оценить d?

Подсказка 2

Точно! Мы можем тогда сказать, что aₖ < d < aₖ₊₁ для k < m. Тогда если мы возьмём достаточно большое m (например, 100), то мы также знаем, что d > a₁₀₀. Что теперь можно сказать про делители числа d, если мы знаем, что d не является членом нашей последовательности?

Подсказка 3

Верно! Мы получаем, что d делится на какое-то aₚ, где p ≤ k. Тогда какое противоречие мы получаем для aₙ?

Показать доказательство

Докажем, что все $a m$ , большие $(a )2 100$ , — простые числа. Предположим противное, тогда некоторое $a >(a )2 m 100$ раскладывается как $am = dt$ , где $1< t≤ d< am$ , и следовательно $a100 < d< am$ . Согласно определению $am,d$ не является ни одним из $a1,a2,...,am−1$ . Тогда $ak < d< ak+1$ для какого-то $k∈ {100,101,...,m− 1}$ . Раз $d$ не было выбрано в качестве $ak+1$ , оно делится на какое-то $ai,i∈ {1,2,...,k}$ . Но тогда и $am$ делится на $ai$ . Противоречие.

Ошибка.
Попробуйте повторить позже

Задача 31#92427Максимум баллов за задание: 7

Полиция задержала 50 человек, из которых 35 — преступники, которые говорят, что захотят, а 15 — свидетели, которые всегда говорят правду. Все задержанные знают, кто преступники. Какое наименьшее число человек достаточно выбрать, чтобы, спросив потом у каждого, кто именно преступники, по ответам вычислить хотя бы одного преступника?

Источники: Тургор - 2021, 11.5, устный тур (см. turgor.ru)

Подсказки к задаче

Подсказка 1

Полезная мысль: разбить людей на группы так, чтобы внутри каждой группы ответы были одинаковыми! При этом никто, разумеется, не назвал себя (иначе всё очевидно).

Подсказка 2

Допустим, мы опросили почти всех и взяли группу с минимальным количеством человек. Тогда, если в ней есть хотя бы 1 свидетель, свидетелями вместе с ним могут быть только люди из его группы и те, кого не опросили. А если это количество будет меньше 15, то мы сразу вычислим преступников...

Подсказка 3

Так же очевидно, что в каждой группе не более 15 человек, ведь каждый должен назвать 35 человек, и ни один из них не должен быть в этой группе. А как нам найти группу с минимальным количеством человек? Допустим, мы опросили n человек и поделили на х групп. Тогда 15х точно не меньше n. Воспользуемся принципом Дирихле, чтобы определить, сколько максимум человек может быть во всех группах! С помощью этого мы и сможем получить противоречие.

Показать ответ и решение

Пусть мы опросили $k <47$ людей. Опросим еще $46− k$ случайных людей из оставшихся. Разобьем 46 опрошенных людей на 4 группы по 11,11,11,13 человек. Пусть групшы, где 11 человек, будут отвечать на вопросы так, будто свидетели они и 4 неопрошенных человека, а группа из 13 человек будет отвечать на вопросы так, будто свидетели они и 2 любых неопрошенных. Так как мы не можем понять, какая из версий настоящая, то и преступника мы найти не сможем, ведь любой человек в какой-то из версий свидетель.

_________________________________________________________________________________________________________________________________________________________________________________

Выберем 47 человек и каждого спросим «Кто из жителей преступники?». Пусть каждый назвал 35 человек и никто не назвал себя, иначе преступник определяется очевидно. Разобьем всех людей на групшы так, что внутри одной группы ответы одинаковые.

Заметим, что в одной группе не больше 15 человек, иначе каждый из них обвинил бы менее 35 человек. Докажем, что найдется группа, в которой менее 12 человек.

Действительно, если в каждой группе хотя бы 12 человек, то если этих групп хотя бы 4 , то всего людей хотя бы $12⋅4 =48> 47$ , а если групп не более, чем 3 , то всего людей не более, чем $15⋅3=45 <47$ — противоречие.

Возьмем ту группу, где меньше 12 человек. Если бы кто-то из них был свидетелем, то вместе с ним свидетелем могли быть только люди из его группы и неопрошенные люди, то есть менее 15 человек, противоречие. Значит, люди этой группы — преступники.

Ответ: 47

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 32#92428Максимум баллов за задание: 7

Существует ли описанный 2021-угольник, все вершины и центр вписанной окружности которого имеют целочисленные координаты?

Источники: Тургор - 2021, 11.6, устный тур (см. turgor.ru)

Подсказки к задаче

Подсказка 1

Есть два возможных ответа - да или нет. Если нет, то нужно доказывать, что абсолютно для любого числа в последовательность {A^i} найдется не подходящее число, что ну кажется очень непростой задачей. Тогда будем доказывать, что ответ «да».

Подсказка 2

Если мы хотим, чтобы верхняя целая часть A^n отличалось от ближайшего натурального квадрата на 2, то хотелось бы понять, чему равна эта верхняя целая часть. Вернее, что нам было бы удобнее взять за верхнюю целую часть, чтобы она отличалась от какого-то квадрата на 2? А если вспомнить как возводится число вида t + 1/t в квадрат?

Подсказка 3

Хотелось бы сделать так, чтобы число вида A^n + 1/A^n было бы целым и A было некоторым квадратом, чтобы как раз получить t^2n + 1/t^2n = (t^n + 1/t^n)^2 - 2. Осталось только понять, чему должно быть равно t, чтобы каждое выражение вида A^n + 1/A^n, при A = t^2, было бы целым.

Подсказка 4

Здесь вас на поиск подходящего t может натолкнуть либо мысль о процессе построения бесконечных цепных дробей, либо же тот факт, что число вида (a + b * sqrt(c))^k, где a, b, k - целые, это выражение вида t + l * sqrt(c). Заметьте, это верно и для отрицательных k.

Подсказка 5

Да, можно просто сказать, что t — корень некоторого уравнения с целыми коэффициентами и отрицательным коэффициентом при x, ведь тогда t + 1/t = c, где с - целая положительная константа.

Подсказка 6

Тогда, по модулю факта про возведение таких иррациональностей в степень, можно сказать, что задача решена, поскольку мы нашли такое t, что любое выражение вида t^k + 1/t^k - целое, а значит, нашли подходящее А.

Показать ответ и решение

Будем называть точку с рациональными координатами рациональной. Рассмотрим окружность $x2 +y2 = 1$ . Докажем, что на ней существует сколь угодно много рациональных точек.

Рассмотрим прямую вида $y =kx+ 1$ с рациональным $k$ . Она проходит через точку $(0,1)$ окружности, и вторая точка пересечения с окружностью тоже будет рациональной (поскольку квадратное уравнение $2 2 x + (kx +1) = 1$ с рациональными коэффициентами имеет рациональный корень 0 , второй корень также рационален).

Выбирая разные рациональные $k$ , отметим на окружности 2021 рациональную точку, включая точки $(−1,0),(1,0),(0,1),(0,− 1)$ . Через каждую из этих 2021 точек проведём касательную к окружности и отметим точки пересечения соседних касательных, получим описанный 2021-угольник (строго это можно обосновать, например, так: сначала получим описанный квадрат, проведя касательные в четырёх указанных точках, а затем по очереди проведём остальные касательные: каждая будет отсекать от уже имеющегося многоугольника треугольник, примыкающий к вершине).

Заметим, что уравнения касательных имеют рациональные координаты (поскольку касательные перпендикулярны прямым, соединяющим начало координат с рациональными точками касания). Точка пересечения прямых с рациональными координатами рациональна (как единственное решение системы линейных уравнений с рациональными коэффициентами). Значит, вершины нашего 2021-угольника рациональны. Приведём координаты вершин к общему знаменателю $N$ и рассмотрим гомотетию с центром в начале координат и коэффициентом $N$ . Она переведёт наш 2021-угольник в удовлетворяющий условию задачи.

Ответ: да

Ошибка.
Попробуйте повторить позже

Задача 33#94424Максимум баллов за задание: 7

Существует ли такое натуральное $n,$ что для любых вещественных чисел $x$ и $y$ найдутся вещественные числа $a ,a ,...,a , 1 2 n$ удовлетворяющие равенствам

1 1 1 x =a1+ a2+ ...+an; y = a1 + a2 + ...+ an?

Источники: Турнир городов - 2021, весенний тур, сложный вариант, 11.2

Подсказки к задаче

Подсказка 1:

Не совсем понятно, как можно доказывать отрицательный ответ. Поэтому стоит придумать пример!

Подсказка 2:

Вот вам одна из идей, как построить пример. Придумайте при некотором n такое разложение для пары (x, 0). Тогда разложение для (x, y) вы сможете получить из 2n слагаемых как сумму разложений (x, 0) и (0, y).

Показать ответ и решение

Докажем, что подходит $n= 6.$ Предварительно заметим, что любую пару $(0,y)$ с ненулевым $y$ можно получить так:

3- 3- 3 2y 2y y 0= 2y + 2y − y,y = 3 + 3 − 3

Аналогично можно получить любую пару $(x,0)$ с ненулевым $x.$ Тогда любую пару $(x,y)$ с отличными от нуля $x$ и $y$ можно получить как «сумму» двух рассмотренных выше пар. Пару $(x,0)$ можно получить как сумму двух пар $(x2,0),$ аналогично можно получить пару $(0,y),$ а пару $(0,0)$ — как $1+ 1+ 1− 1− 1− 1.$

Ответ:

Существует

Ошибка.
Попробуйте повторить позже

Задача 34#98464Максимум баллов за задание: 7

В прямоугольный треугольник с гипотенузой длины $1$ вписали окружность. Через точки её касания с его катетами провели прямую. Отрезок какой длины может высекать на этой прямой окружность, описанная около исходного треугольника?

Подсказки к задаче

Подсказка 1

Пусть ABC — треугольник с прямым углом B, O — центр его описанной окружности, M и N — точки касания вписанной окружности с катетами AB и BC соответственно. Что можно сказать о точках пересечения прямой MN с окружностью?

Подсказка 2

Может, они являются серединами дуг? Попробуйте это доказать.

Подсказка 3

А можно ли тут воспользоваться леммой 255?

Показать ответ и решение

Пусть $ABC$ — треугольник с прямым углом $B,O$ — центр его описанной окружности, $M$ и $N$ — точки касания вписанной окружности с катетами $AB$ и $BC$ соответственно, $X$ и $Y$ — середины дуг $AB$ и $BC$ . Достаточно доказать, что точки $M$ и $N$ лежат на хорде $XY$ .

$PIC$

Пусть точка $P$ — проекция точки $A$ на биссектрису угла $C$ , точка $Q$ — проекция точки $C$ на биссектрису угла $A$ . По Задаче 255 точки $P$ и $Q$ лежат на прямой $MN$ . Так как $90∘ = ∠B = ∠APC = ∠AQC$ , точки $P$ и $Q$ совпадают соответственно с $X$ и $Y$ .

Ответ:

$√2 2$

Ошибка.
Попробуйте повторить позже

Задача 35#104459Максимум баллов за задание: 7

Пусть $p$ и $q$ — взаимно простые натуральные числа. Лягушка прыгает по числовой прямой, начиная в точке $0.$ Каждый раз она прыгает либо на $p$ вправо, либо на $q$ влево. Однажды лягушка вернулась в $0.$ Докажите, что для любого натурального $d <p+ q$ найдутся два числа, посещённые лягушкой и отличающиеся ровно на $d.$

Подсказки к задаче

Подсказка 1

Какой есть частный случай пары (p;q)?

Подсказка 2

p = q = 1. С ним все понятно, теперь считаем, что p и q различны, пусть p < q. Что можно сказать о длине пути, который пропрыгала лягушка?

Подсказка 3

Заметим, что его длина делится на p и q, тогда и на pq, так как p и q взаимно просты.

Подсказка 4

Тогда длина пути равна kpq, сколько прыжков сделала лягушка?

Подсказка 5

Лягушка сделает kq "коротких" прыжков вправо и kp "длинных" прыжков влево. Подумайте, как при взаимно простых p и q можно представить d.

Подсказка 6

d = ap - bq. Подумайте, какими можно выбрать a и b.

Подсказка 7

Давайте назовем каждую серию из a+b последовательных прыжков лягушки окном. Сколько всего будет окон?

Подсказка 8

Окон будет ровно k(p+q). Нам нужно окно, где лягушка сделала a коротких и b длинных прыжков и сдвинулась на d = ap - bq.

Подсказка 9

Такое окно найдётся, если есть окно, где коротких прыжков не менее a, и окно, где их не более a. Докажите, что существует такое окно.

Подсказка 10

А что, если сдвигать первое окно по кругу, пока мы не дойдем до второго? Сколько всего будет коротких прыжков в окнах?

Показать доказательство

Первое решение. Случай $p= q = 1$ очевиден. Иначе $p$ и $q$ различны, пусть $p< q.$ Всего лягушка пропрыгала путь, длина которого делится на $p$ и на $q,$ а значит, и на $pq,$ так как $p$ и $q$ взаимно просты. Тогда длина пути равна $kpq$ для некоторого натурального $k,$ и лягушка сделала $kq$ «коротких» прыжков вправо и $kp$ «длинных» прыжков влево.

Известно, что при взаимно простых $p$ и $q$ можно представить $d$ в виде $d= ap− bq$ с целыми $a$ и $b.$ Это равенство, очевидно, сохранится, если одновременно увеличить (или уменьшить) $a$ на $q$ и $b$ на $p.$ Поэтому можно выбрать $a$ натуральным и не превосходящим $q.$ При этом будет неотрицательным (иначе $d> p+q),$ и так как $a≤ q,$ то $b<p$ (ведь $d >0).$ Поэтому $a+ b< p+ q ≤ k(p+ q).$

Назовём каждую серию из $a+ b$ последовательных прыжков лягушки окном. Условно считаем, что за последним прыжком лягушки идёт её первый прыжок (как при движении по кругу), поэтому окно может состоять и из нескольких последних и первых прыжков. Тогда всего окон ровно $k(p+ q)$ штук.

Надо найти окно, где лягушка сделала ровно $a$ коротких прыжков (и $b$ длинных) — тогда она сдвинется на $d$ за эти $a+ b$ прыжков. Такое окно найдётся, если есть окно, где коротких прыжков не менее $a,$ и окно, где их не более $a:$ можно сдвигать первое окно по кругу, пока не дойдём до второго, число коротких прыжков в окне каждый раз меняется максимум на $1,$ поэтому будет момент, когда оно равно $a.$

Сложим число коротких прыжков во всех окнах — получим $kq(a +b),$ ведь каждый прыжок учил $a+b$ раз. Окон $k(p+ q),$ и в среднем на окно придётся $kqk(a(p++bq))$ коротких прыжков. Это число равно

kq(a+-b)-= qa-+qb= pa+-qa−-d= a− -d-- k(p +q) p +q p+q p+ q

что больше $a− 1$ и меньше $a.$ Значит, найдётся окно, где коротких прыжков не менее $a,$ и окно, где их не более $a.$

______________________________________________________________________________________________________________________________________________________

Второе решение. Лягушку из условия назовём старой. Будем считать, что она пропрыгивает свою последовательность ходов бесконечное число раз по циклу. Посадим на прямую новую лягушку в точку $d$ и заставим её прыгать ту же последовательность прыжков, что прыгает старая (тоже в бесконечном цикле).

Множество чисел, посещённых новой лягушкой, получается из множества чисел, посещённых старой, сдвигом на $d.$ Если хотя бы одно число из нового множества совпадет с числом из старого, то обратный сдвиг даст нам искомую пару чисел. Предположим, что этого не произойдёт.

Как и в предыдущем решении, представим число $d$ в виде $ap− bq$ для некоторых неотрицательных $a$ и $b.$ Заставим старую лягушку пропрыгать $a +b$ ходов по её циклу; она окажется в точке $e =xp− yq,$ где $x+ y = a+b.$ Так как $a− x = y− b,$ разность координат новой и старой лягушек кратна $p +q :$

d− e= (a − x)p− (b− y)q = (a− x)(p+ q)

Далее пустим лягушек прыгать одновременно: старую по продолжению исходной траектории, а новую — по сдвинутой. На каждом шаге разность их координат будет либо не меняться (если они прыгают в одну сторону), либо меняться на $p +q$ (если одна прыгает на $+ p,$ а другая на $− q).$ Таким образом, разность всегда будет оставаться кратной $p+q;$ при этом она, по предположению, не может становиться нулевой, поэтому она всегда будет сохранять знак.

Пусть лягушки пропрыгали полный цикл и вернулись (новая в $d,$ а старая в $e).$ Количество ходов в цикле обозначим через $T.$ Сумму всех чисел, посещённых новой лягушкой (без учёта начальной позиции), обозначим через $S, 1$ а сумму чисел, посещённых старой, — через $S.$ С одной стороны, числа на соответствующих ходах отличались не менее чем на $p +q,$ причём разность всегда имела один и тот же знак, поэтому $|S1 − S|≥ T(p+q).$ С другой стороны, набор чисел, посещённых новой лягушкой за цикл, отличается от аналогичного набора старой лягушки сдвигом на $d,$ поэтому $|S1− S|= Td$ (отметим, что эти наборы могут содержать некоторые числа по несколько раз, если в течение цикла лягушка посещала их неоднократно). Подставляя и сокращая на $T,$ получаем $d≥ p+ q,$ что противоречит условию задачи.

_________________________________________________________________________________________________________________________________________________________________________________

Третье решение. Как и в решении $2,$ будем считать, что лягушка прыгает в бесконечном цикле. Также воспользуемся представлением $d =ap− bq$ для неотрицательных $a$ и $b,$ сумму $a +b$ обозначив через $r.$

Через $δi$ обозначим разность между положениями лягушки в момент $i+r$ (то есть через $i+ r$ шагов после начала) и в момент $i.$ Так как их разделяет $r$ шагов, то

δi = xp− (r− x)q = ap +(x− a)p− bq− (r− x− b)q =

= d+ (x − a)p+(x− (r− b))q = d+ (x− a)(p+q)

Если $δi$ равно $d,$ то мы нашли искомые позиции. Предположим противное, пусть $δi ⁄= d$ для всех $i.$ Тогда все числа $δi$ имеют вид $d+ (p+q)ki$ для целых $ki ⁄= 0.$

Заметим, что разность между $δi$ и $δi+1$ определяется тем, какими были $(i+ 1)$ -й и $(i+r+ 1)$ -й шаги; разобрав случаи, нетрудно убедиться, что она равна $± (p+q)$ или $0.$ Это означает, что числа $δi$ либо все меньше $0,$ либо все больше $0.$

Рассмотрим позицию лягушки через $rT$ шагов, где $T$ — количество шагов в её цикле. С одной стороны, она равна сумме $δ0+ δr +δ2r+...+δr(r − 1),$ которая по доказанному выше должна быть либо отрицательной, либо положительной. С другой стороны, через $rT$ шагов лягушка вернётся на позицию $0.$ Противоречие.

Ошибка.
Попробуйте повторить позже

Задача 36#104674Максимум баллов за задание: 7

В куче $n$ камней, играют двое. За ход можно взять из кучи количество камней, либо равное простому делителю текущего числа камней в куче, либо равное $1.$ Выигрывает взявший последний камень. При каких $n$ начинающий может играть так, чтобы всегда выигрывать, как бы ни играл его соперник?

Подсказки к задаче

Подсказка 1

Какое количество камней стоит оставлять в куче, если можно брать только 1 камень и количество камней, равное простому делителю?

Подсказка 2

Хотелось бы оставлять такое число камней, чтобы противник не мог забрать все сразу, но при любых его ходах мы забрали рано или поздно оставшееся.

Подсказка 3

Возможно, n должно быть кратно какому-нибудь "приятному" числу.

Подсказка 4

Рассмотрите n, кратные 4.

Показать ответ и решение

Стратегия: каждый раз оставлять в куче кратное $4$ число камней: при $n = 4k +1$ надо взять один камень, при $n= 4k+2$ — два камня; при $n = 4k +3$ надо взять $p$ камней, где $p$ — простой делитель числа $n$ вида $4q +3$ (такой есть, иначе все простые делители $n$ имеют вид $4m + 1,$ а произведение чисел такого вида тоже имеет такой вид и не равно $4k+ 3).$ Противник из кучи с кратным $4$ числом камней не может взять число камней, кратное $4$ (это будет не простое число), поэтому начинающий и дальше может играть по стратегии.

Ответ:

При $n,$ не кратном $4$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 37#78897Максимум баллов за задание: 7

В строку записано $2020$ натуральных чисел. Каждое из них, начиная с третьего, делится и на предыдущее, и на сумму двух предыдущих. Какое наименьшее значение может принимать последнее число в строке?

Источники: Тургор - 2020, 11.1, устный тур (см. turgor.ru)

Подсказки к задаче

Подсказка 1

Начните с малого: попробуйте построить последовательность из 3-4 чисел, удовлетворяющих условиям. Какие минимальные значения можно выбрать для первых двух чисел? Как будет расти последовательность?

Подсказка 2

Докажите, что каждое следующее число должно быть значительно больше предыдущего. Если aₖ делится на aₖ₋₁ и на (aₖ₋₁ + aₖ₋₂), как это ограничивает минимальное значение?

Подсказка 3

Попробуйте взять первые два числа равными 1. Как будет выглядеть последовательность? Почему факториалы — это единственный способ достичь минимального последнего числа?

Подсказка 4

Допустим, для первых k чисел минимальная последовательность — это факториалы. Как доказать, что aₖ₊₁ должно быть не меньше k! ? Используйте условие делимости на сумму двух предыдущих. aₖ₊₁ должно делиться на aₖ + aₖ₋₁ = (k-1)! + (k-2)! = (k-1)·(k-2)! + (k-2)! = k·(k-2)!

Показать ответ и решение

Пример. Условию задачи, очевидно, удовлетворяют числа $1,1,2!,3!,...,2019!,$ так как при любом натуральном $k$ число $(k+2)!$ делится как на $(k +1)!,$ так и на $(k +1)!+k!= k!(k+ 2).$

Оценка. Пусть $a,b,c$ — три подряд идущих числа в строке, но не первые три числа. Докажем, что $c -b b ≥a +1.$ По условию, $-b c a = x,b = y,$ где $x$ и $y$ натуральные. Тогда $c= by = axy,$ причём $c$ делится на $b+ a= ax+a = a(x+ 1).$ Получаем, что $axy$ делится на $a(x+ 1),$ откуда $xy$ делится на $x+ 1,$ и так как $x$ и $x +1$ взаимно просты, $y$ делится на $x+1,$ то есть $y ≥ x+ 1,$ что и требовалось.

Заметим, что первые два числа не меньше $1$ каждое. Третье число больше второго (так как делится на сумму второго и первого), а значит, хотя бы в два раза больше второго (так как делится на него и не равно ему). По доказанному выше, четвёртое число тогда хотя бы в $3$ раза больше третьего, пятое — хотя бы в $4$ раза больше четвёртого, и так далее, откуда по индукции получаем, что $k$ -е число не меньше, чем ( $k− 1$ )! при всех натуральных $k.$

Ответ:

$2019!$

Ошибка.
Попробуйте повторить позже

Задача 38#123414Максимум баллов за задание: 7

На высотах $AA ,BB ,CC 0 0 0$ остроугольного неравностороннего треугольника $ABC$ отметили соответственно точки $A ,B ,C 1 1 1$ так, что $AA1 = BB1 = CC1 =R,$ где $R$ — радиус описанной окружности треугольника $ABC.$ Докажите, что центр описанной окружности треугольника $A1B1C1$ совпадает с центром вписанной окружности треугольника $ABC.$

Источники: Тургор - 2020, 11.2, устный тур (см. turgor.ru)

Подсказки к задаче

Подсказка 1

Рассмотрите симметрию относительно биссектрис: как связаны точки А₁, B₁, C₁ с центром описанной окружности О? Обратите внимание на равенство расстояний AA₁= BB₁= CC₁= R. Намёк: Проверьте, что О симметричен А относительно биссектрисы угла А)

Подсказка 2

Докажите, что IO = IA₁= IB₁= IC₁, где I — центр вписанной окружности. Какое свойство объединяет все точки, равноудалённые от I?

Подсказка 3

Почему А₁ и О относительно биссектрисы AI? Используйте равенство АA = R = AO и свойства высот. Точка А, лежит на высоте, а О — на серединном перпендикуляре. Как биссектриса связывает эти объекты?

Подсказка 4
Соберите всё вместе: если I равноудалён от всех трёх точек А₁, В ₁, C₁, то что это означает для △АВС ?

Показать доказательство

Пусть $O$ — центр описанной окружности треугольника $ABC,$ а $I$ — центр вписанной окружности данного треугольника.

$PIC$

Заметим, что $∠ACO = ∠C0CB.$ Тогда из равенства углов и того, что $CO = CC1$ по условию, точки $C1$ и $O$ симметричны относительно биссектрисы $CI.$ Следовательно, $IO = IC1.$ Аналогичными рассуждениями получаем, что $IO = IA1 = IB1.$ Из равенств следует, что $I$ и есть центр описанной окружности треугольника $A1B1C1.$

Ошибка.
Попробуйте повторить позже

Задача 39#123415Максимум баллов за задание: 7

На клетчатой плоскости отметили $40$ клеток. Всегда ли найдётся клетчатый прямоугольник, содержащий ровно $20$ отмеченных клеток?

Источники: Тургор - 2020, 11.3, устный тур (см. turgor.ru)

Подсказки к задаче

Подсказка 1

Нас спрашивают, всегда ли найдётся клетчатый прямоугольник, содержащий 40 клеток. Значит, нам нужно привести либо построение такого прямоугольника в общем виде, либо контрпример. Для начала предположим, что такой прямоугольник всегда существует, тогда либо мы опишем его, либо получим противоречие. Попробуйте рассмотреть какой-нибудь пример.

Подсказка 2

Возьмите квадрат 11×11. Какие клетки можно в нем закрасить?

Подсказка 3

Посмотрите на рамку: она будет содержать ровно 40 клеток.

Подсказка 4

Собственно, надо доказать, что не найдётся прямоугольника, содержащего ровно 20 из 40 клеток рамки. Предположим, что такой прямоугольник найдётся. Что если этот прямоугольник будет содержать клетки из вертикальных сторон рамки?

Подсказка 5

Тогда горизонтальные стороны рамки по отдельности либо будут полностью включены в прямоугольник, либо не будут включены вовсе. Как это будет влиять на количество отмеченных клеток? Посчитайте все случаи и задача будет решена.

Подсказка 6

Если у Вас не получилось самостоятельно придумать прошлый пример, можете попробовать ещё раз: возьмите какой-нибудь прямоугольник и удалите из него несколько клеток.

Показать ответ и решение

Первое решение.

Рассмотрим клетчатый квадрат размером $11× 11$ и удалим из него внутренний центральный квадрат $9× 9,$ оставив только рамку толщиной 1. В рамке будет как раз 40 клеток. Докажем, что на плоскости нет клетчатого прямоугольника, содержащего ровно 20 из этих 40 клеток.

$PIC$

Допустим, такой прямоугольник есть. Пусть в нём есть клетки из обеих вертикальных сторон рамки. Тогда каждая горизонтальная сторона рамки либо полностью включена в прямоугольник, либо вовсе не включена. Если включена ровно одна горизонтальная сторона, число клеток в прямоугольнике нечётно, если обе — клеток 40 (слишком много), а если ни одной — клеток максимум $9+ 9=18$ (слишком мало).

Значит, в прямоугольнике могут быть клетки лишь из одной вертикальной стороны рамки, и, аналогично, лишь из одной горизонтальной стороны рамки. Но эти стороны соседние, и суммарно в них максимум 19 клеток — слишком мало. Противоречие.

Второе решение.

Рассмотрим клетчатый прямоугольник $[1,14]×[1,3],$ и удалим из него клетки $(7,1)$ и $(7,3).$ Останется ровно 40 клеток. Предположим, что нашёлся клетчатый прямоугольник, в котором ровно 20 отмеченных клеток. Он может затрагивать одну, две или три горизонтали с номерами $1,2,3.$

$PIC$

Если он затрагивает одну горизонталь, то в нём не более 14 отмеченных клеток.

Если он задевает 2 горизонтали (одна из них — вторая), то он задевает вертикаль с номером 7 (иначе в нём не более 14 клеток). Тогда эта вертикаль вносит в прямоугольник нечётное число отмеченных клеток, а остальные — чётное. Поэтому общее число отмеченных клеток в прямоугольнике нечётно.

Если он задевает все три горизонтали, то число отмеченных клеток в нём либо кратно 3 (если он не задевает 7-й вертикали), либо имеет остаток 1 при делении на 3 (иначе).

В каждом из случаев получаем противоречие.

Замечание. Возможны другие решения. Например, подходит квадрат $7× 7$ с вырезанным центральным квадратом $3× 3,$ но доказательство более длинное.

Ответ:

Нет

Ошибка.
Попробуйте повторить позже

Задача 40#123416Максимум баллов за задание: 7

Для бесконечной последовательности $a,a ,... 1 2$ её первая производная — это последовательность $a′= a − a n n+1 n$ (где $n= 1,2,...),$ а её $k$ -я производная — это первая производная её $(k− 1)$ -й производной $(k =2,3,...).$ Назовём последовательность хорошей, если она и все её производные состоят из положительных чисел. Докажите, что если $a1,a2,...$ и $b1,b2,...$ — хорошие последовательности, то и $a1⋅b1,a2⋅b2,...$ — хорошая последовательность.

Источники: Тургор - 2020, 11.4, устный тур (см. turgor.ru)

Подсказки к задаче

Подсказка 1

Давайте попробуем доказать некоторые простые свойства производной последовательности. Например, производная суммы равна сумме производных.

Подсказка 2

Теперь попробуйте показать, что вторая производная последовательности aₙbₙ состоит только из положительных чисел. Не забывайте использовать, что последовательности a и b — хорошие.

Подсказка 3

Попробуйте расширить рассуждения из предыдущей подсказки. Пусть есть некоторые хорошие последовательности a_m и b_k. Что можно сказать про вторую производную последовательности a_m • b_k?

Показать доказательство

Сначала докажем два вспомогательных утверждения.

Утверждение 1. Покажем, что при таком определении производной для последовательности выполняется: производная суммы — это сумма производных.

Пусть дана последовательность, являющаяся суммой нескольких других последовательностей:

(1) (2) (t) kn =kn + kn + ...+ kn ,

где $k(1),...,k(t)$ — какие-то $t$ произвольных последовательностей. Тогда производная этой суммы:

$pict$

В силу произвольности $t,$ наше утверждение доказано.

Утверждение 2. Пусть $a1,a2,...$ и $b1,b2,...$ — две произвольные хорошие последовательности. Тогда покажем, что производная произведения двух произвольных членов этих последовательностей положительна. То есть для всех $m,k∈ {1,2,...}$ выполнено:

(am ⋅bk)′ > 0

А также, что производная состоит из суммы слагаемых того же вида — произведений членов из двух хороших последовательностей.

Запишем по определению производной:

$pict$

Так как обе последовательности хорошие, то полученное выражение положительно, и каждое из слагаемых — произведение членов хороших последовательностей. Следовательно, утверждение доказано.

Теперь вернёмся к решению задачи. Пусть $cn = an⋅bn.$ Тогда по утверждению 2 для любого $n:$

(cn)′ = (an⋅bn)′> 0

Значит, первая производная $cn$ (и, соответственно, произведения любых двух хороших последовательностей) состоит из положительных чисел.

Кроме того, мы представили $c′n$ в виде суммы двух произведений хороших последовательностей. Далее по индукции, используя утверждения 1 и 2, получаем, что и все производные $cn$ состоят из положительных чисел.

Следующая подтема