Тема ЮМШ (олимпиада Юношеской Математической Школы)

ЮМШ - задания по годам → .04 ЮМШ 2022

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

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

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

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

Подтемы раздела юмш (олимпиада юношеской математической школы)

Разделы подтемы ЮМШ - задания по годам

ЮМШ до 2020

ЮМШ 2020

ЮМШ 2021

ЮМШ 2022

ЮМШ 2023

ЮМШ 2024

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

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

Задача 1#79619

Вася посмотрел на граф $G$ на $n$ вершинах и поставил на каждую вершину $v$ переменную $x . v$ После чего рассмотрел выражение

∑ xixj f (x1,...,xn)=2⋅(i,j)−-ребро--- n∑ x2i i=1

Пусть $m$ и $M$ — минимум и максимум $f.$

(a) Пусть степень каждой вершины в графе равна $d.$ Найдите $M.$

(b) Докажите, что вершины графа $G$ можно покрасить в $[M ]+1$ цвет, так что любые две соседние вершины получат разные цвета.

( ) Z = 1 1 −-1 , 2 w

где $w$ — максимальный размер множества вершин графа $G,$ попарно соединенных ребрами.

Источники: ЮМШ-2022, 11 класс, сюжет 1 (см. yumsh.ru)

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

(a)

Оценка. Занесём 2 в числитель и оценим каждое слагаемое следующим образом

2 2 2xixj ≤ xi +xj

Получим

∑ 2xixj ∑ (x2 +x2) (i,j)−-ребро---- ≤ (i,j)−-ребро-i---j- n∑ x2 ∑nx2 i=1 i i=1 i

Так как у каждой вершины степень у каждой вершины в графе равны $d,$ то каждая $2 xi$ в числителе встретиться ровно $d$ раз, следовательно

∑ 2 2 n∑ 2 ∑n 2 (i,j)− ребро(xi +xj) i=1dxi di=1xi -----∑n-2------= -n∑--2-= -n∑--2-= d i=1xi i=1xi i=1xi

Пример. Поставим во все вершины $1,$ получим

dn f(1,...,1)= n = d

(b) Предположим, что это не так, то есть граф так покрасить нельзя. Тогда по теореме Брукса найдётся подграф, в котором степени вершин хотя бы $[M ]+1.$ Поставим в вершины этого подграфа $1,$ а во все остальные вершины графа $0.$ Тогда значение выражения $f$ станет равным $[M ]+1> M,$ а это противоречит тому, что $M$ — максимум выражения $f.$

(c) Кликой графа называется подмножество его вершин, любые две из которых соединены ребром. Аналогично определяется антиклика

Пример. Найдём в графе максимальную клику, в его вершины поставим $1 w,$ а в остальные $0.$

Оценка.

( ) Z ≤ 1 1− 1- 2 w

Рассмотрим расстановку, на которой достигается $Z.$ Если там есть вершина с 0, удалим её. По предположение

( ) Z ≤ 1 1− -1 , 2 w

если максимальная антиклика не уменьшилась, и

1( 1 ) 1 ( 1) Z ≤ 2 1− w−-1 <2 1− w- ,

если максимальная антиклика уменьшилась. Таким образом сделаем все числа ненулевыми.

Обозначим $S(v)$ — сумму чисел в смежных с $v$ вершинах. Заметим, что если $a$ и $b$ — несмежные вершины и $S(a)< S(b),$ то можно заметить $(xa,xb)$ на $(0,xa+ xb).$ Общая сумма не измениться, а $Z$ увеличиться, противоречие. Следовательно, если $a$ и $b$ — несмежные вершины, то $S(a)=S (b).$

Рассмотрим антиграф, проверим два случая:

1) Если он связен. Значит, для любых вершин $a$ и $b$ $S(a)= S(b),$ обозначим это число за $S.$ Следовательно по предположению

1 1 1- 1- Z = 2S > 2(1− w)⇒ S > 1− w

Рассмотрим вершину $A$ максимальной антиклики.

1 S(A)> 1− w-

Следовательно, число в $A$ плюс в вершинах, не смешных с $A,$ меньше $1 w-.$ Просуммируем по врем вершинам максимальной антиклики. Мы посчитали каждое число неменее 1 раза, значит сумма всех меньше, чем $w⋅ 1-= 1 w$ . Противоречие, следовательно, такое невозможно.

2) Антиграф не связен.

Ответ:

(a) d

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

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

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

Задача 2#83912

$P$ — некий полином с целыми коэффициентами, $A$ и $M$ — целые числа. Построим последовательность $a n$ , где $a = A 1$ , и $a =P (a) n+1 n$ и пусть $rn$ — остаток от деления $an$ на $M$ .

1. Пусть $P(x)= x2+ x+ 1,A = 1,M = 32022$ . Докажите, что период последовательности $rn$ (то есть, такое наименьшее $t$ , что $rn+t = rn$ при достаточно больших $n$ ) равен 2.

2. Найдите длину предпериода той же последовательности (то есть такое наибольшее $n$ , что $an+t ⁄= an$ , где $t$ — период).

3. Назовем полином стабильным по модулю $M$ , если существует $B$ , такое что для любого $A$ найдется $k$ , для которого $rk = B$ . Докажите, что полином $3 2 f = x − x − 2$ нестабилен по модулю $M$ , если $M$ является квадратом нечётного числа.

4. Докажите, что многочлен $P (x)= x2− 3x +12$ стабилен для бесконечного числа натуральных $M$ .

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

1. Легко видеть, что остатки $an$ от деления на 3 чередуются с периодом 2 (1, 0, 1, 0, . . .) поэтому период остатков по модулю $M = 32022$ тем более не равен 1.
Покажем что он равен 2.
Заметим, что $an+2 − an =a2n+1− a2n−1+an+1− an−1 = (an+1− an−1)(an+1+ an−1 +1)$
Отсюда следует, что если $an+1 − an−1$ делится на $3k$ , то тем же свойством обладает и $an+2− an$ , а если вдобавок $an+1$ , $an−1$ дают остаток от 1 деления на 3, то $an+2 − an$ делится на $3k+1$ .
Учитывая, что такая ситуация имеет место при каждом четном $n$ , получаем, что соответствующее $k$ может неограниченно увеличиваться, в частности, $an+2− an$ делится на $32022$ при некотором $n= n0$ (а значит и при всех $n >n0$ ). Поэтому период $rn$ равен двум.

2. Выпишем остатки от деления $an$ на 9 и на 27: легко убедиться, что это 2-периодические последовательности $1,3,4,3,4,...$ и $1,3,13,21,13,21,...$ соответственно.
Поэтому число $(an+1+ an−1+ 1)$ не делится на 3 при нечетных $n$ , делится на 3, но не на 9 при $n= 2$ и делится на 9, но не на 27 при четных $n >2$ .
То есть если $v n$ — степень вхождения 3 в число $a − a n+1 n−1$ , то $v = 1 2$ , $v =2 3$ а дальше $v =v + 2 2k+1 2k$ и $v = v 2k+2 2k+1$ .
Отсюда легко видеть, что наибольшее $s$ такое, что $v <2022 s$ равно 2022, то есть $a − a 2023 2021$ — последняя среди разностей вида $an+2− an$ не кратная $M$ .

3. Пусть $M =Q2$ , тогда $Q$ - нечетное число.
Заметим, что $f(2)= 23− 22− 2= 2$ ,значит, достаточно показать, что существует число, проделывая операцию из условия над которым мы не получим 2.
Рассмотрим числа вида $t= 2+ kQ$ , где НОД $(k;Q)= 1$
$f(t)= (2+ kQ)3 − (2+ kQ )2 − 2= Q3k3+ 5Q2k2+8Qk +2$
Нетрудно заметить, что $f(t)≡ 8Qk + 2(mod M )$
То есть числа вида $t= 2+ kQ$ , где НОД $(k;Q)= 1$ переходят в себя, но число 2 не имеет такого вида, поэтому полином $f = x3− x2 − 2$ нестабилен по модулю $M$ , если $M$ является квадратом нечётного числа.

4. Индукцией по $k$ докажем, что для $M = 7k$ многочлен $x2− 3x+ 12$ стабилен.
Обозначим через $a → b$ , то что $P(a)≡b(modM )$
База $k =1$

0→ 5→ 1 → 31 → 3→ 5→ 12 → 3→ 5→ 13→ 5 → 1→ 34→ 2→ 3→ 5→ 15→ 1 → 36 → 5→ 1→ 3

Таким образом, имеем цикл длины 3 везде одинаковый.
Переход $k→ k+ 1$
Пусть по модулю $M = 7k$ многочлен стабилизируется так, что всегда встретится $r$
Тогда по модулю $M = 7k+1$ остаток $r$ будет $7km+ r= r1$
$P (r1)≡r2− 3r+ 12 +7kn(2r− 3)(Mod 7k+1)$ , что не зависит от $n$ , при $0≡ 2r− 3(Mod 7)$
$0 ≡2r− 3(Mod 7)⇔ 5 ≡r(Mod 7)$ , что бывает по базе индукции, поэтому многочлен стабилизируется и по модулю $7k+1$ .