Поиск задач

В стране $N$ городов. В ней действует $N(N-1)$ дорог с односторонним движением: по одной дороге из $X$ в $Y$ для каждой упорядоченной пары городов $X\ne Y$. У каждой дороги есть цена её обслуживания. Для данного $k=1,\ldots,N$ рассмотрим все способы выделить $k$ городов и $N-k$ дорог так, чтобы из каждого города можно было попасть в какой-то выделенный город, пользуясь только выделенными дорогами. Такую систему городов и дорог с наименьшей суммарной стоимостью обслуживания назовём $k$-оптимальной. Докажите, что города можно пронумеровать от 1 до $N$ так, что при каждом $k=1,2,\ldots,N$ существует $k$-оптимальная система дорог с выделенными городами $1,2,\ldots,k$.

Изначально на доске написано 10 единиц. Гриша и Глеб играют в игру, делая ходы по очереди. Своим ходом Гриша возводит некоторые 5 чисел на доске в квадрат. Глеб своим ходом выбирает несколько (возможно, ни одного) чисел на доске и увеличивает каждое из них на 1. Если в течение 10 000 ходов на доске появится число, делящееся на 2023, то побеждает Глеб, иначе побеждает Гриша. Кто из игроков имеет выигрышную стратегию, если первым ходит Гриша?

В каждой строке таблицы $100\times n$ в некотором порядке стоят числа от 1 до 100, числа в строке не повторяются (в таблице $n$ строк и 100 столбцов). Разрешается поменять местами в строке два числа, отличающиеся на 1, если они не стоят рядом. Оказалось, что с помощью таких операций нельзя получить двух одинаковых строк. При каком наибольшем $n$ это возможно?

У 100 школьников есть стопка из 101 карточки, которые пронумерованы числами от 0 до 100. Первый школьник перемешивает стопку, затем берёт сверху из получившейся стопки по одной карточке, и при каждом взятии карточки (в том числе при первом) записывает на доску среднее арифметическое чисел на всех взятых им на данный момент карточках. Так он записывает 100 чисел, а когда в стопке остаётся одна карточка, он возвращает карточки в стопку, и далее всё то же самое, начиная с перемешивания стопки, проделывает второй школьник, потом третий, и т. д. Докажите, что среди выписанных на доске 10000 чисел найдутся два одинаковых.

Окружность $\omega$ описана около треугольника $ABC$, в котором $AB\lt AC$. Биссектрисы треугольника $ABC$ пересекаются в точке $I$. Из середины $M$ стороны $BC$ на прямую $AI$ опущен перпендикуляр $MH$. Прямые $MH$, $BI$ и $AB$ ограничивают треугольник $T_b$, а прямые $MH$, $CI$ и $AC$ ограничивают треугольник $T_c$. Описанные окружности треугольников $T_b$ и $T_c$ повторно пересекают окружность $\omega$ в точках $B'$ и $C'$ соответственно. Докажите, что точка $H$ лежит на прямой $B'C'$.

Число $x$ таково, что $\sin x+\operatorname{tg}x$ и $\cos x+\operatorname{ctg}x$ — рациональные числа. Докажите, что $\sin 2x$ является корнем квадратного уравнения с целыми коэффициентами.

Плоскость $\alpha$ пересекает рёбра $AB$, $BC$, $CD$ и $DA$ тетраэдра $ABCD$ в точках $X$, $Y$, $Z$ и $T$ соответственно. Оказалось, что точки $Y$ и $T$ лежат на окружности $\omega$, построенной на отрезке $XZ$ как на диаметре. Точка $P$ отмечена в плоскости $\alpha$ так, что прямые $PY$ и $PT$ касаются окружности $\omega$. Докажите, что середины рёбер $AB$, $BC$, $CD$, $DA$ и точка $P$ лежат в одной плоскости.

Назовём многочлен $P(x)$ бицелозначным, если числа $P(k)$ и $P'(k)$ целые при любом целом $k$. Пусть $P(x)$ — бицелозначный многочлен степени $d$, и пусть $N_d$ — произведение всех составных чисел, не превосходящих $d$ (произведение пустого множества сомножителей считаем равным 1). Докажите, что старший коэффициент многочлена $N_d\cdot P(x)$ — целый.