Тема ЮМШ - задания по годам

ЮМШ 2022

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

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

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

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

Подтемы раздела юмш - задания по годам

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

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

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

Вася посмотрел на граф $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)

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

Пункт а, подсказка 1

Нам нужно как-то оценить f. При этом в числителе мы видим сумму всех попарных произведений, а в знаменателе — сумму квадратов. Как можно связать квадраты и попарные произведения?

Пункт а, подсказка 2

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

Пункт а, подсказка 3

Внесём двойку под знак суммы. Получится, что числитель — это сумма всех возможных удвоенных произведений, каждое из которых не больше, чем сумма квадратов множителей. Оценим так каждое слагаемое. Сколько раз в итоговой сумме встретится квадрат каждого из чисел xᵢ?

Пункт а, подсказка 4

Столько же, сколько каждое из чисел xᵢ встречается во всевозможных попарных произведениях! Или столько же, сколько рёбер выходит из вершины xᵢ.

Пункт а, подсказка 5

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

Пункт а, подсказка 6

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

Пункт b, подсказка 1

Подумаем, а что будет, если граф нельзя покрасить в [M]+1 цветов так, чтобы никакие две соседние вершины не были одноцветными?

Пункт b, подсказка 2

Это значит, что найдется такой подграф, степени всех вершин которого не меньше [M]+1. Например, это может быть полный подграф из [M]+1 вершине. Попробуйте как-нибудь использовать это при подсчёте f.

Пункт b, подсказка 3

Чему будет равно значение f, если в каждой вершине выбранного подграфа будет стоять единичка, а в остальных вершинах — ноль?

Пункт b, подсказка 4

Верно, значение функции будет равно [M]+1. Постойте, а не противоречит ли это условию?

Пункт c, подсказка 1

Нам нужно доказать, что максимальное значение суммы всех попарных произведений равно определенному выражению. Утверждение не самое очевидное, поэтому попробуйте проверить, выполняется ли это на каком-нибудь простом графе.

Пункт c, подсказка 2

В задаче фигурирует клика — подмножество вершин графа, в котором любые 2 вершины соединены ребром. Будем рассматривать максимальную клику, ведь в ней как раз w вершин. Кажется, отделив вершины этой клики от остальных, гораздо проще придумать пример!

Пункт c, подсказка 3

В вершины максимальной клики поставим 1/w, а в остальные вершины — 0. Тогда искомое значение Z действительно достигается! Ура, мы доказали, что есть такие расстановки (по крайней мере одна) при которых утверждение задачи верно! Теперь попробуем доказать, что при изменении такой расстановки утверждение остаётся верным! Не забудьте учесть, что сумма всех чисел на вершинах равна 1.

Пункт c, подсказка 4

Обратите внимание на вершины, в которых стоит 0. Можно ли их просто убрать?

Пункт c, подсказка 5

Да, можно, ведь они никак не влияют на сумму попарных произведений. Однако придётся учесть изменения в размере максимальной клики! После этого у нас получится граф с положительными числами в каждой вершине. Пусть S(v) — сумма чисел в вершинах, смежных с v. Остался последний рывок! Подумайте, что можно сказать об этой величине для несмежных вершин.

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

(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Максимум баллов за задание: 7

$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, подсказка 1

Если мы докажем, что с какого-то момента a_(n+2) - a_n = a_(n+1) - a_(n-1) (mod 3^2022), то и требуемое тоже будет доказано. Попробуйте выразить a_(n+2) - a_n через a_(n+1) и a_(n-1).

Пункт 1, подсказка 2

Мы получаем, что если a_(n+1) - a_(n-1) делится на 3^k, то и a_(n+2) - an делится на 3^k. Теперь, если мы докажем, что a_(n+1) - a_(n-1) делится на 3^(k+1), то сможем сказать, что с какого-то момента k станет >= 2022. Попробуйте для этого доказать, что a_(n+1) и a_(n-1) имеют одинаковые остатки при делении на 3.

Пункт 1, подсказка 3

Для этого посмотрите на значение a_n по mod 3.

Пункт 2, подсказка 1

Как подсказывает нам прошлый пункт задачи, нужно рассматривать остатки от деления a_n на степени 3. Попробуйте найти таким способом зацикливание.

Пункт 2, подсказка 2

Отлично! Теперь мы знаем, что остатки от деления a_n на 9 и на 27 зацикливаются. Тогда, зная, что степень вхождения 3 в выражение a_(n+1) - a_(n-1) каждый раз растёт, попробуйте вывести рекуррентную формулу для этой степени вхождения.

Пункт 2, подсказка 3

Если v_n - степень вхождения 3 в a_(n+1) - a_(n-1), то v_2 = 1, v_3 = 2, v_(2k+1) = v_2k + 2 и v_(2k+2) = v_(2k+1). Теперь осталось лишь решить неравенство v_k < 2022.

Пункт 3, подсказка 1

Нам нужно определить такое B, чтобы для него нашлось A, такой, что ни один r_k не равен B. Сразу сделать это довольно трудно. Попробуйте для начала подставлять небольшие A и посмотреть на значения полинома.

Пункт 3, подсказка 2

Отлично! Мы знаем, что f(2) = 2. Очень удобно будет доказывать, что есть такое A, что не будет остатка 2, ведь M - квадрат нечётного числа. Осталось лишь подобрать такое A и доказать, что r_k никогда не равен 2. Попробуйте найти A так, чтобы в нём как слагаемое присутствовало q (M = q^2).

Пункт 3, подсказка 3

Можно взять A = 2 + k*q (k и q взаимно просты). Теперь попробуйте рассмотреть f(A) по mod M.

Пункт 4, подсказка 1

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

Пункт 4, подсказка 2

Так, теперь мы знаем, что для 7 многочлен стабилен. Тогда попробуем доказать, что это верно и для 7^k. Легче всего сделать это по индукции. База уже есть, осталось доказать переход. И победа!

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

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$ .