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

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

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

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

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

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

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

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

ЮМШ до 2020

ЮМШ 2020

ЮМШ 2021

ЮМШ 2022

ЮМШ 2023

ЮМШ 2024

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

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

Задача 1#108600

На $n$ карточках написали по $k$ чисел, сумма на каждой карточке равна $m$ . Оказалось, что любой набор из $k$ неотрицательных чисел с суммой 1 можно получить, уменьшив некоторые числа на одной из карточек (наборы неупорядоченные). Пусть $a(n,k)$ — наименьшее $m$ , при котором это возможно.

1. Найдите $a(2,2)$ .

2. Докажите, что найдется $n$ такое, что $a(n,10100) ≤1+ 10−100$ .

3. Докажите, что $a(2,4)<√3-$ .

4. Ограничена ли последовательность $a(2,k)− a(1,k)$ ?

Источники: Изумруд - 2020, 11.3 (см. izumrud.urfu.ru)

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

1. Пример: наборы ( $1;14$ ) и ( $34;12$ ).

Оценка. Ясно, что должен быть набор, содержащий 1, чтобы мажорировать ( $1;0$ ), и набор, в котором оба числа больше $12$ , чтобы мажорировать $( ) 12;12$ . Если это одна и та же пара, то сумма уже $32$ . Если разные, то посмотрим на набор $( ) 34;14$ : чтобы набор $(1;x)$ мажорировал его, должно быть $x ≥ 14$ , а чтобы набор с парой чисел, больших $12$ мажорировал — это должен быть набор, как минимум $( ) 34;12$ . Легко видеть также, что указанный набор подходит.

_________________________________________________________________________________________________________________________________________________________________________________

2. Рассмотрим все возможные способы записать число $1+ 10− 100$ в виде суммы положительных рациональных дробей со знаменателем $10200$ (не обязательно несократимых). Очевидно, что это количество конечно, его и обозначим за $n$ — записав все соответствующие наборы на карточки, убедимся, что такой набор карточек подходит. Действительно, рассмотрим любой набор с единичной суммой. Заменим в нём каждое число на ближайшую сверху дробь со знаменателем $10200$ . При таком округлении сумма увеличится не более, чем на $10100⋅--1200 = 1∕10100 10$ , значит получится один из наших наборов или аналогичный набор с меньшей суммой. Произвольно увеличив числители некоторых дробей так, чтобы сумма стала равной $1+10−100$ , мы превратим набор в числа на одной из карточек, которая, таким образом, мажорирует исходный набор с единичной суммой.

_________________________________________________________________________________________________________________________________________________________________________________

3. Рассмотрим, например, следующую пару наборов:

( ) ( ) 2314,12,13,14 и 1,1334,1638, 11032 .

Сумма в каждом равна $324704-$ , это даже меньше,чем 1,71 , а $√3-= 1,73...$ . Проверим, что эта пара наборов мажорирует все нужные четвёрки. Ясно (*), что в упорядоченной тройке с суммой $x$ среднее число - не больше, чем $x2$ , а малое - не больше, чем $x3$ ; аналогичное верно для четвёрок. Действительно, если максимальное число в четвёрке больше $2314$ , то второе по величине - не больше,чем $1334$ , третье не больше $1638$ а самое маленькое не больше $11302$ , значит такая четверка мажорируется вторым набором. Аналогично, если максимальное число не больше, чем $21 34$ , то оно мажорируется первым набором.

_________________________________________________________________________________________________________________________________________________________________________________

4. Вычислим $a(1,k)$ . Как уже отмечалось, для всякого $l≤ k$ должна быть карточка, в которой $l$ -ое по величине число не меньше, чем $1 l$ . Если карточка всего одна, то сумма на этой карточке, таким образом, не меньше $1 1 1+ 2 + ...+ k$ . С другой стороны, карточка $( 1 1) 1,2,...,k$ , очевидно, подходит, т.к. в наборе с единичной суммой $l$ -ое по величине число не больше $1 -l$ , так что $1 1 a(1,k)=1 +2 +...+k$ . Теперь рассмотрим произвольную пару натуральных чисел $l<k$ , соотношение между которыми мы уточним позднее, и предъявим два набора, вдвоём мажорирующих все наборы с единичной суммой: а именно

1 1 1 --1- -1---1-- 1 (◟l,l,.◝◜..,l◞,l+ 1,l+2,l+ 3,...,k) lраз

( 1 1 1 l− 1 l− 1 l− 1 l− 1 ) 1,2,3,...,l,-l2-,l(l+1),l(l+2),...,l(k−-1)

Действительно, рассмотрим любой упорядоченный по убыванию набор ( $a1 ≥ a2 ≥ ...≥ ak$ ) с единичной суммой. Ясно, что $ai ≤1∕i$ при любом $i$ и поэтому первая карточка мажорирует любой набор с единичной суммой, в котором все числа не превосходят $1∕l$ .

Пусть, напротив, $a1 > 1l$ . Тогда для любого $i$ имеем

a2+ a3+ ...+al+i < 1− 1, откуда al+i ≤--l−-1--. l l(l+ i− 1)

Поэтому любой набор с $1 a1 > l$ мажорируется второй из наших карточек.

Осталось убедиться, что разность между $a(1,k)$ и максимумом из сумм в этих двух наборах может быть сделана (при подходящем выборе $l$ и $k$ ) сколь угодно большой. Действительно, сумма на первой карточке отличается от $a(1,k)$ на

1 1 l− 1 1 1 1+ 2 +...+l−-1 −--l-> 2 + ...+ l−-1

и эта величина при достаточно больших $l$ может быть сделана, как известно, сколь угодно большой. Теперь зафиксируем произвольное $l$ и посмотрим на вторую карточку: сумма чисел на ней меньше, чем $a(1,k)= 1+ 12 + ...+ 1k$ , на

( ) --1-+ -1--+⋅⋅⋅+ 1− l− 1 1 +--1-+ ...+ -1-- = l+ 1( l+2 k l l) l+ 1 k−( 1 ) = 1 -1--+ -1--+⋅⋅⋅+--1- + 1− l−21> 1 -1--+--1-+ ...+ -1-- − 1 l l+ 1 l+2 k − 1 k l l l+1 l+ 2 k− 1

Поскольку выражение в скобках при фиксированном $l$ и неограниченном $k$ может быть сделано сколь угодно большим, то можно выбрать $k$ так, что эта разность будет больше разности между $a(1,k)$ и первой суммой, которая одним лишь выбором $l$ может быть сделана сколь угодно большой для произвольного $k> l$ . Утверждение доказано, последовательность из условия не ограничена.

Ответ:

1. $5 4$

2. что и требовалось доказать

3. что и требовалось доказать

4. нет

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

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

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

Задача 2#108601

Две окружности, вписанные в угол с вершиной $R$ , пересекаются в точках $A$ и $B$ . Через $A$ проведена прямая, пересекающая меньшую окружность в точке $C$ , а большую — в точке $D$ . Оказалось, что $AB =AC = AD$ .

1. Пусть $C$ и $D$ совпали с точками касания окружностей и угла. Докажите, что угол $R$ прямой.

2. Пусть $C$ и $D$ совпали с точками касания окружностей и угла. Чему может быть равен угол $ADR$ ?

3. Докажите, что если $∠R$ прямой, то $C$ и $D$ совпадают с точками касания окружностей и угла.

4. Какие значения может принимать угол $RAO1$ , где $O1$ — центр меньшей окружности?

Источники: Изумруд - 2020, 11.3 (см. izumrud.urfu.ru)

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

1. Треугольник $BCD$ прямоугольный (медиана — половина гипотенузы). Значит, сумма дуг $AC$ и $AD$ соответствующих окружностей равна $2⋅90∘ = 180∘$ , а сумма соответствующих углов между хордой и касательной $CDR + DCR = 90∘$ , поэтому $∠R = 90∘$ .

_________________________________________________________________________________________________________________________________________________________________________________

2. Треугольник $RAB$ равносторонний $− RA = CD ∕2 =AB$ и $RA =RB$ по симметрии. Отсюда симметричные отрезки $RA,RB$ образуют со сторонами углы, равные $90∘−260∘-= 15∘$ и этому же равен $∠ADR$ (т.к. $AD = AR$ ).

_________________________________________________________________________________________________________________________________________________________________________________

3. Выполним инверсию $i$ относительно окружности с центром в $A$ и радиусом $AB$ . Имеем $i(B )=B,i(C)= C,i(D)= D$ , и наши две окружности превращаются в прямые $BC, BD$ , образующие прямой угол, а стороны исходного угла - в пару окружностей, вписанных в этот угол, перпендикулярных друг другу (как и соответствующие прямые до инверсии) и пересекающихся в точках $A,S =i(R)$ . Вычислим отношение их радиусов — это легко делается применением теоремы Пифагора к треугольнику $AO1O2$ со сторонами $√- r1,r2, 2(r2− r1)$ (здесь $O1,O2$ — центры новых окружностей, $r1 < r2$ - радиусы). Получается $r2 √- r1 = 2+ 3$ ; будем считать $√- r1 = 1,r2 = 2+ 3$ .

Введём связанную с нашим прямым углом систему координат, тогда центры имеют координаты $(1,1)$ и $√- √ - (2+ 3,2+ 3)$ , а точки касания — $√- √- X1 = (1,0),X2 = (0,1),Y1 = (0,2+ 3),Y2 = (2+ 3,0)$ . Середина $X1Y1$ — это $(1 √3) 2,1+ 2-$ , и, считая расстояния от неё до $O1$ и $O2$ , убеждаемся, что это точка пересечения наших окружностей,как и середина $X2Y2$ . Значит, эти середины — точки $A,R$ . Поскольку $A$ не лежит на биссектрисе угла, то прямая, из которой наш угол высекает отрезок с серединой $A$ , единственна, так что соответствующая пара точек $Xi,Yi$ совпадает с парой $C,D$ .

_________________________________________________________________________________________________________________________________________________________________________________

4. Исполним ту же самую инверсию, что и в предыдущем пункте, вновь получим прямой угол и вписанную в него пару окружностей. Прямая $AS$ пересекает стороны угла под 45 градусов, значит, то же делает эта же прямая $(i(AS)= AR =AS )$ с исходными окружностями. Поэтому и угол $RAO$ ( $O$ — центр меньшей окружности) равен $90∘− 45∘ = 45∘$ .

Ответ:

1. что и требовалось доказать

2. $15∘$

3. что и требовалось доказать

4. $∘ 45$

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

Задача 3#108602

В этом сюжете разрешается использовать (без обоснования) так называемую малую теорему Ферма, гласящую, что для всякого целого числа $a$ и простого натурального числа $p$ справедливо соотношение:

$p a− a$ делится на $p$ без остатка.

_________________________________________________________________________________________________________________________________________________________________________________

Итак, $p >2$ — простое число. Маша должна понять, есть ли среди чисел

a1+b1,a2+b2,...,ap−1+ bp−1

значения, дающие одинаковые остатки от деления на $p$ .

1. Пусть $a= 4,b= 9$ . Докажите, что искомая пара найдётся.

2. Пусть $a= 4,b= 3$ . Докажите, что найдётся искомая пара, содержащая одно из крайних чисел.

3. Докажите, что искомая пара найдётся при $a= 4,b= 7$ .

4. Докажите, что искомая пара найдётся, если $a= 2,b= 3$ , а $p−1 -2-$ - простое.

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

1. По МТФ $4p−1+ 9p−1 ≡2$ , но в то же время и $p−1 p−-1 4 2 + 9 2 = 2p−1+ 3p−1 ≡ 2$ .

_________________________________________________________________________________________________________________________________________________________________________________

2. Если $p= 3$ , то всё ясно. Если $3(p−1)∕2 ≡ 1$ , то остальное как в предыдущем пункте. Иначе же $3(p−1)∕2 ≡ −1$ . Например, потому что из МТФ $3p− 1 ≡ 1$ , значит,

(3p−21− 1) (3 p−21-+1):p

Тогда

p−21+2 p−21 +2 1 1 4 + 3 ≡16− 9≡ 7= 4 + 3.

______________________________________________________________________________________________________________________________________________________

3. Случаи $p≤7$ разбираются руками. Дальше, аналогично предыдущим пунктам, если $7(p−1)∕2 ≡ 1$ , то всё ясно. Иначе $7(p−1)∕2 ≡− 1$ , а тогда для $k =1,...,p−1 2$

k k p−1+k p−1+k k p−1+k k 4 + 7 + 4 2 +7 2 ≡ 4 + 4 2 ≡2 ⋅4 .

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

p+1 2(4+ 42+ ...+4p−21) =2⋅ 4-2-− 4 ≡ 4⋅(4p−21− 2) ≡ 4⋅−1⁄≡ 0 4− 1 3 3

_________________________________________________________________________________________________________________________________________________________________________________

4. Предположим, что все остатки различны. Посмотрим на порядки 2 и 3 по модулю $p$ . (Порядок $a$ по модулю $p$ - минимальное натуральное $k$ такое, что $ak− 1$ (или числитель соответствующей несократимой дроби,если $a$ - дробь) кратно $p$ ; это $k$ мы будем обозначать $ordp(a)$ .) По МТФ они могут быть равны лишь $1,2,q,2q =p− 1$ . Первые два случая проигнорируем, а случаи, когда хотя бы один из порядков равен $q$ , идентичны разобранным в пунктах 1 и 3 . Пусть порядки $2q$ , в частности все остатки $2,22,...,2p−1$ , различны (иначе, если $2a$ и $2b$ дают одинаковые остатки, то $2a− 2b$ , а значит и $2a−b− 1$ , кратно $p$ , но $a− b< p− 1$ ) и найдётся такое $m$ , что $2m = 3$ . Отметим также, что в этом случае $2q =3q =−1$ , так что если при некотором $k$ имеем $2k +3k = 0$ , то и $( ) 2k±q +3±q = − 2k+ 3k = 0$ , так что нарушается условие различности остатков. Поэтому в нашей последовательности встречаются по разу все ненулевые остатки.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма 1. Пусть $q >2$ простое и $k <q$ таково, что для любого $x= 1,2,...,q − 1$ число $x$ и остаток $kx$ от деления на $q$ имеют разную чётность. Тогда $k= q− 1$ .

Следствие 1. Пусть $q$ простое, $k$ нечётное, $k +1$ не кратно $2q$ . Тогда найдется $l$ такое, что $y$ обоих чисел $l,kl$ остатки по модулю $2q$ заключены строго между $0$ и $q$ .

Доказательство. Действительно, попробуем в качестве $l$ все числа от 1 до $q − 1$ . Пусть все пары $l,kl$ не подошли, т.е. все $kl$ имеют остатки по модулю $2q$ , большие $q$ . Это значит, что чётность остатка $kl$ по модулю $q$ противоположна четности остатка $kl$ по модулю $2q$ ( $q$ - нечётно), а она совпадает с четностью $l$ (т.к. $k$ нечётно), и мы попадаем в условия леммы.

_________________________________________________________________________________________________________________________________________________________________________________

Подберём по следствию 1 такое $0< l<q$ , что $− ml$ при делении на $2q$ имеет остаток меньше $q$ , назовём этот остаток $r,r+ ml$ делится на $2q$ .

Теперь изучим сумму $∑p−1(2k+ 3k)r+l k=1$ по модулю $p$ . С одной стороны, выражение в скобках пробегает все ненулевые остатки, а число $r+ l<q +q$ не кратно $p − 1= 2q = ord(2)$ , так что эту сумму можно посчитать как сумму геометрической прогрессии с неединичным знаменателем $r+l 2$ , и она равна нулю.

Посчитаем эту же сумму другим способом. Раскрыв все скобки по биному, перегруппировав слагаемые и переставив множители в показателях степеней, мы получим сумму геометрических прогрессий вида $i ∑ (i r+l−i)k Cr+l 23$ . Докажем, что ровно одна из этих прогрессий постоянна, а значит, ровно одно из указанных выражений ненулевое (тут надо отметить, что $r,l< q$ , так что $r +l< 2q = p− 1$ , поэтому появляющиеся биномиальные коэффициенты не кратны $p$ ). Это даст требуемое противоречие.

Действительно, при $i= r$ получаем, учитывая $m 2 = 3$ , что $rr+l−r r+ml 23 = 2 = 1$ , т.к. $r+ ml$ делится на $2q$ . С другой стороны, если $r+sr+l−r−s 2 3 =1$ , при некотором $s∈ [−r,l]$ то, деля, получаем $s−s 23 = 1$ то есть $s (2∕3) = 1$ . Получаем, что $ordp(2∕3)≤max(r,l)< q$ , значит $ordp(2∕3)$ равен 1 или 2 , что может быть лишь при $p= 5$ ; этот случай проверяется непосредственно.

Предыдущая подтема

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