Тема Закл (финал) 10 класс

Закл до 2015

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

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

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

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

Подтемы раздела закл (финал) 10 класс

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

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

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

K натуральному числу $N$ прибавили наибольший его делитель, меньший $N,$ и получили степень десятки. Найдите все такие $N.$

Источники: Всеросс., 2014, ЗЭ, 10.5(см. olympiads.mccme.ru)

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

Пусть $m$ — наибольший делитель числа $N,$ меньший, чем $N.$ Тогда $n= mp,$ где $p$ — наименьший простой делитель числа $N.$ Имеем $k m (p+ 1)= N +m = 10.$ Число в правой части не делится на $3,$ поэтому $p> 2.$ Отсюда следует, что $N$ нечётно, а тогда и $m$ нечётно. Поскольку $k 10$ делится на $m,$ $s m = 5.$

Если $m =1,$ то $N = p= 10k − 1,$ что невозможно, так как $k 10 − 1$ делится на $9,$ то есть не является простым. Значит, $s≥ 1,$ число $N$ кратно $5,$ и потому $p≤ 5.$

Если $p= 3,$ то $s k 4⋅5 =10 ,$ откуда $k= 2,m = 25$ и $N = 75.$

Если же $p =5,$ то $p+ 1= 6,$ и число $k 10$ делится на $3,$ что невозможно.

Ответ:

$75$

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

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

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

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

Дана функция $f,$ определенная на множестве действительных чисел и принимающая действительные значения. Известно, что для любых $x$ и $y$ таких, что $x> y,$ верно неравенство $2 (f(x)) ≤f(y).$ Докажите, что множество значений функции содержится в промежутке $[0,1].$

Источники: Всеросс., 2014, ЗЭ, 10.2(см. olympiads.mccme.ru)

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

По условию $f(y)≥ (f(y+ 1))2 ≥ 0$ для любого $y,$ поэтому все значения функции неотрицательны.

Пусть теперь $f(x0) =1+ a> 1$ для некоторого $x0.$ Докажем индукцией по $n,$ что для любого $y < x0$ верно неравенство $n f(y)>1 +2 a.$ При $n= 1$ имеем

2 2 f(y)≥(f(x0)) = 1+ 2a +a > 1+ 2a

Для перехода от $n$ к $n+1$ заметим, что $y < x0+y< x , 2 0$ и потому $f( x0+y) >1+ 2na 2$ по предположению индукции. А тогда

( (x0+ y))2 n+1 n 2 n+1 f(y)≥ f --2-- =1 +2 a+ (2 a) >1 +2 a

что и требовалось.

Итак, для любого фиксированного $y < x0$ имеем $f(y)> 1+$ $+2na$ при любом натуральном $n.$ Но это невозможно, так как существует $n,$ при котором $2n > f(y)a−1.$ Стало быть, $f(x)≤ 1$ при всех $x.$

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

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

Каждые два из действительных чисел $a,a ,a ,a,a 1 2 3 4 5$ отличаются не менее чем на $1.$ Оказалось, что для некоторого действительного $k$ выполнены равенства $a1+ a2+ a3 +a4+ a5 = 2k$ и $2 2 2 2 2 2 a1 +a2+ a3+a4+ a5 = 2k.$ Докажите, что $2 25 k ≥ 3 .$

Источники: Всеросс., 2012, ЗЭ, 10.3(см. olympiads.mccme.ru)

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

Без ограничения общности можно считать, что $a < ...< a . 1 5$ По условию, $a − a ≥ 1 i+1 i$ при всех $i= 1,2,3,4.$ Значит, $aj − ai ≥j− i$ при всех $1 ≤i< j ≤ 5.$ Возведём каждое из полученных неравенств в квадрат и сложим их все. Получим $∑ 2 ∑ 2 2 2 2 2 1≤i<j≤5(aj − ai) ≥ 1≤i<j≤5(j− i) =4 ⋅1 + 3⋅2 + 2⋅3 +4 = 50,$ то есть

∑5 ∑ 4 a2i − 2 aiaj ≥50 (1) i=1 1≤i<j≤5

С другой стороны, по условию имеем

∑5 ∑ a2i + 2 aiaj = (a1 +...+ a5)2 =4k2 (2) i=1 1≤i<j≤5

Складывая $(1)$ и $(2),$ получаем

∑5 5 a2i =10k2 ≥ 50+4k2 i=1

откуда $2 6k ≥ 50,$ или $2 k ≥25∕3.$

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

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

Таблица состоит из $n$ строк и $10$ столбцов. В каждой клетке таблицы написана цифра. Известно, что для каждой строки $A$ и каждой пары столбцов $B$ и $C$ существует строка, отличающаяся от $A$ в точности в столбцах $B$ и $C.$ Докажите, что $n ≥512.$

Источники: Всеросс., 2011, ЗЭ, 10.1(см. olympiads.mccme.ru)

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

Пусть $R 0$ — первая строка таблицы. Рассмотрим любой набор из чётного количества столбцов и пронумеруем их слева направо: $C1,...,C2m.$ Тогда в таблице есть строка $R1,$ отличающаяся от $R0$ ровно в столбцах $C1$ и $C2;$ далее, есть строка $R2,$ отличающаяся от $R1$ ровно в столбцах $C3$ и $C4$ и так далее; наконец, есть строка $Rm,$ отличающаяся от $Rm −1$ ровно в столбцах $C2m −1$ и $C2m$ (если $m =0,$ то $Rm = R0$ ). Итак, строка $Rm$ отличается от $R0$ ровно в столбцах $C1,...,C2m.$ Значит, строки $Rm,$ построенные по различным наборам столбцов, различны. Поскольку количество наборов из чётного числа столбцов равно $9 2 = 512,$ то и количество строк в таблице не меньше $512.$

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

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

Даны $10$ попарно различных чисел. Для каждой пары данных чисел Вася записал у себя в тетради квадрат их разности, а Петя записал у себя в тетради модуль разности их квадратов. Могли ли в тетрадях у мальчиков получиться одинаковые наборы из $45$ чисел?

Источники: Всеросс., 2011, ЗЭ, 10.5(см. olympiads.mccme.ru)

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

Предположим противное. Если среди исходных чисел есть ноль, то для любого другого числа $a$ имеем $a2− 02 = (a − 0)2.$ Значит, если вычеркнуть ноль, то останутся $9$ чисел, также удовлетворяющих условию.

Итак, можно считать, что исходных чисел $9$ или $10,$ и все они ненулевые. Пусть среди них есть числа разных знаков; рассмотрим минимальное и максимальное из них - обозначим их $a< 0< b.$ Тогда у Васи присутствует число $2 (b− a) ,$ которое больше как $2 a ,$ так и $2 b ;$ у Пети же любое число не превосходит $( 2 2) max a ,b .$ Противоречие.

Значит, все исходные числа — одного знака; заменив, если надо, все числа на противоположные, можно считать, что все они положительны. Опять обозначив через $a$ и $b$ соответственно минимальное и максимальное из этих чисел, имеем

b2− a2 = (b− a)(b+ a)>(a− b)2 ≥ (c− d)2

где $c$ и $d$ — произвольные два исходных числа. Тогда число $2 2 b − a$ не встретится на листке у Пети, но встретится у Васи — противоречие.

Ответ:

Не могли

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

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

Периметр треугольника $ABC$ равен $4.$ На лучах $AB$ и $AC$ отмечены точки $X$ и $Y$ так, что $AX = AY =1.$ Отрезки $BC$ и $XY$ пересекаются в точке $M.$ Докажите, что периметр одного из треугольников $ABM$ или $ACM$ равен $2.$

Источники: Всеросс., 2011, ЗЭ, 10.4(см. olympiads.mccme.ru)

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

Подсказка 1

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

Подсказка 2:

Итак, вы, вероятно, вычислили длину отрезков AX' и AY', где X' и Y' - точки касания вневписанной окружности с продолжениями сторон. А что можно сказать про отрезок XY в треугольнике AX'Y'?

Подсказка 3:

Обратите на точку A и вневписанную окружность. Где их радикальная ось? В дальнейшем останется только посчитать отрезки.

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

Пусть вневписанная окружность треугольника $ABC$ напротив вершины $A$ касается стороны $BC$ в точке $Z ′,$ а прямых $AB$ и $AC$ в точках $′ X$ и $′ Y$ соответственно. Из условия периметр $ABC$ равен $4,$ а значит, отрезки $′ AX$ и $′ AY$ равны $2.$ То есть прямая $XY$ является средней линей треугольника $′′ AX Y .$ Значит, $XY$ радикальная ось вневписанной окружности и точки $A.$ Откуда $′ MZ = MA.$ Пусть $Y$ лежит на отрезке $AC.$ Тогда периметр треугольника $ABM$ равен

AB +AM +BM =AB + MZ ′+BM =

′ ′ ′ =AB + BZ = AB + BX = AX =2

$PIC$

Курсы

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

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

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

В треугольнике $ABC$ проведена биссектриса $BD$ (точка $D$ лежит на отрезке $AC$ ). Прямая $BD$ пересекает окружность $Ω,$ описанную около треугольника $ABC,$ в точках $B$ и $E.$ Окружность $ω,$ построенная на отрезке $DE$ как на диаметре, пересекает окружность $Ω$ в точках $E$ и $F.$ Докажите, что прямая, симметричная прямой $BF$ относительно прямой $BD,$ содержит медиану треугольника $ABC.$

Источники: Всеросс., 2009, ЗЭ, 10.2(см. olympiads.mccme.ru)

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

Подсказка 1

Так, нужно подумать… То есть у нас есть биссектриса и середина стороны в задаче, а также есть описанная окружность. На какой факт нам это намекает?

Подсказка 2

Верно, на тот факт, что биссектриса и серпер пересекаются на описанной окружности треугольника. Тогда пусть они пересеклись в точке Е. Что интересного можно заметить если продлить отрезок EM до пересечения с описанной окружностью(пусть точка пересечения - точка Х)?

Подсказка 3

Конечно, можно заметить, что F,D,X - лежат на 1 прямой. Почему это так? Ну понятно почему, XFE - прямой, так как опирается на диаметр окружности (ABC), и DFE - прямой, так как опирается на диаметр окружности, построенной на DE как на диаметре. Хмм… А что теперь нам это дает? Какие равные углы теперь можно отметить?

Подсказка 4

Действительно, мы можем заметить равенство углов FBE и FXE, в силу того, что они опираются на одну хорду FE. Значит, нам надо доказать, что углы FXE и MBE равны! А как это можно удобно переформулировать?

Подсказка 5

Это можно переформулировать как доказательство вписанности BDMX. Осталось понять почему сумма углов EBX и XMA равна 180 градусов, и задача будет решена!

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

Первое решение. Пусть $BM$ — медиана треугольника. Так как биссектриса $BE$ и серединный перпендикуляр к $AC$ проходят через одну и ту же точку (середину дуги $AC$ ), то $EM ⊥AC.$ Пусть $EM$ пересекается с окружностью в точке $X.$ Из сказанного выше следует, что $EX$ — диаметр окружности $Ω.$

$PIC$

Надо доказать, что $BF$ и $BM$ симметричны относительно биссектрисы, то есть

∠MBE = ∠FBE

При этом $∠FBE = ∠F XE$ как опирающиеся на одну дугу вписанные углы.

По условию $∠DF E$ прямой, а ещё опирающийся на диаметр вписанный угол $∠XFE$ тоже прямой. Поэтому точки $F,D,X$ коллинеарны. Тогда $∠FXE =∠DXM.$ Остаётся доказать равенство

∠MBD =∠MXD

Это равенство следует из того, четырёхугольник $BDMX$ можно вписать в окружность. Действительно, $∘ ∠XMC = 90 ,$ при этом $∘ ∠EBX = ∠DBX = 90 = ∠XMC.$

______________________________________________________________________________________________________________________________________________________

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

$PIC$

Сделаем симметрию относительно биссектрисы угла $B$ и инверсию с таким радиусом, чтобы $A ∗ = C$ и $C∗ = A,$ где звездочкой обозначаем образ точки под действием композиции преобразований. Заметим что $D∗ = E$ и $E ∗ = D$ так как прямая $AC$ переходит в дугу $C∗A∗ =AC$ и наоборот, а прямая $BD$ переходит сама в себя. Окружность, построенная на $DE$ тем самым переходит в окружность, центр которой все лежит на $BD,$ а точки ее пересечения с $BD$ это $D$ и $E.$ То есть, эта окружность переходит в себя. Точка $F$ переходит в точку $M$ вторую точку пересечения окружности и прямой $AC.$ Известно, что $E$ – середина дуги $AC,$ а $∠EMD = 90∘$ так как $ED$ – диаметр окружности. Получаем, что $EM$ высота в равнобедренном треугольника $AEC,$ значит $M$ – середина $AC.$ Получается, что $BM$ содержит медиану треугольника $ABC,$ причем $BM$ симметрична $BF$ относительно биссектрисы угла $B.$

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

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

В неравнобедренном остроугольном треугольнике $ABC$ проведены высоты $AA 1$ и $CC 1$ , $H$ — точка пересечения высот, $O$ — центр описанной окружности, $B0$ — середина стороны $AC$ . Прямая $BO$ пересекает сторону $AC$ в точке $P$ , а прямые $BH$ и $A1C1$ пересекаются в точке $Q$ . Докажите, что прямые $HB0$ и $P Q$ параллельны.

Источники: Всеросс., 2008, ЗЭ, 10.6(см. olympiads.mccme.ru)

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

По свойству ортоцентра $HB 0$ пересекает описанную около $ABC$ окружность в точке, диаметрально противоположной вершине $B.$ Назовём эту точку $′ B .$

$PIC$

По свойству ортоцентра $△ABC ∼△A1BC1.$ Диаметры $BH$ и $BB ′$ описанных около подобных треугольников окружностей относятся так же, как отрезки $BQ$ и $BP$ , соединяющие вершину соответственного треугольника с точкой пересечения диаметра описанной окружности со стороной.

Итак, по обратной теореме Фалеса $BQ :BP = BH :BB′ =⇒ PQ∥HB ′.$

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

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

Грани куба $9× 9× 9$ разбиты на единичные клетки. Куб оклеен без наложений бумажными полосками $2× 1$ (стороны полосок идут по сторонам клеток). Докажите, что число согнутых полосок нечетно.

Источники: Всеросс-2007, ЗЭ, 10.1 (см. olympiads.mccme.ru)

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

Покрасим клетки каждой грани куба в шахматном порядке так, чтобы угловые клетки были чёрными. При этом каждая грань содержит $41$ чёрную и $40$ белых клеток. Заметим, что все согнутые полоски будут одноцветными, а все остальные — нет. Так как количество чёрных клеток на $6$ больше чем количество белых, то число чёрных согнутых полосок на $3$ больше чем число белых. Следовательно, эти числа разной чётности, и их сумма нечётна.

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

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

На дугах $AB$ и $BC$ окружности, описанной около треугольника $ABC,$ выбраны соответственно точки $K$ и $L$ так, что прямые $KL$ и $AC$ параллельны. Докажите, что центры вписанных окружностей треугольников $ABK$ и $CBL$ равноудалены от середины дуги $ABC.$

Источники: Всеросс., 2006, ЗЭ, 10.6(см. math.ru)

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

Подсказка 1.

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

Подсказка 2.

Правильно, лемма о трезубце! Давайте отметим середины дуг AK и CL и обозначим их через P и Q соответственно. Теперь надо бы кое-что понять про точки P и Q. Для этого надо вспомнить, что KL ∥ AC.

Подсказка 3.

Пусть R — середина дуги ABC, а I и J — центры вписанных окружностей. Доказать равенство отрезков IR и RJ довольно проблематично. Но можно доказать равенство некоторых объектов, в которые они входят, из которого будет следовать их равенство.

Подсказка 4.

Попробуйте доказать равенство треугольников IRP и JRQ

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

Обозначим через $I,J$ — центры вписанных окружностей соответственно, через $P,Q,R$ — середины дуг $AK, CL,ABC$ соответственно. Пары точек $A$ и $C,$ $P$ и $Q$ симметричны относительно серединного перпендикуляра к стороне $AC,$ следовательно,

PA = QC, RP = RQ.

По лемме о трезубце же

P I = PA, QJ = QC.

Наконец, углы $BP R$ и $BQR$ равны, поскольку опираются на равные дуги, следовательно, равны треугольники $IP R$ и $JQR.$

$PIC$

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

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

Докажите, что для любого нечетного простого $p$ найдется неприводимый над $ℤ p$ многочлен степени $2.$

Источники: Всеросс., 2006, ЗЭ, 10.2(см. math.ru)

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

Подсказка 1

Пусть дан произвольный многочлен степени 2 в Z_p. В каком случае он имеет корень?

Подсказка 2

Если изначальный вопрос кажется лишком сложным, то рассмотрите частный случай, когда многочлен имеет вид x^2-b.

Подсказка 3

Тогда и только тогда, когда b (или дискриминант исходного уравнения) является квадратичным невычетом по модулю p. Осталось вспомнить почему существует квадратичный невычет по каждому простому модулю

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

Рассмотрим уравнение $x2− b ≡0$ в $ℤ p$ . Его разрешимость эквивалентна тому, что $b$ является квадратичным вычетом. Как известно, существует всего $p− 1 2$ квадратичных вычетов, и столько же невычетов. Тогда в качестве $b$ берем любой невычет и получаем неприводимый многочлен.

Интенсивы

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

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

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

Сумма кубов трёх последовательных натуральных чисел оказалась кубом натурального числа. Докажите, что среднее из этих трёх чисел делится на $4.$

Источники: Всеросс., 2006, ЗЭ, 10.2(см. math.ru)

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

Подсказка 1

Необходимо показать, что если для некоторых натуральных чисел x, y верно (x−1)³+x³+(x+1)³=y³, то x кратно 4. Раскройте скобки и приведите подобные слагаемые.

Подсказка 2

Мы получили, что 3(x²+2)=y³. Как можно воспользоваться тем, что y кратно 3?

Подсказка 3

Пусть y=3z. Тогда имеем, x(x²+2)=9z³. Что можно сказать о числе НОД(x, x²+2)?

Подсказка 4

Он равен 1 или 2. Если он равен 1, то что можно сказать про произвольное простое число p, отличное от 3, делящее z?

Подсказка 5

Оно делит ровно одно из чисел x и x²+2, причем входит в него в степени, кратной 3. Тогда x =9u³ и x²+2=v³, либо x =u³, x²+2 =9v³ при некоторых натуральных u,v. Докажите, что каждый из этих случаев невозможен.

Подсказка 6

Осталось разобрать случай НОД(x, x²+2). Почему при этом x кратно 4?

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

Пусть среднее из последовательных чисел равно $x.$ Тогда для некоторого натурального $y$ верно уравнение

3 3 3 3 (x− 1) + x +(x+ 1) =y

что экививалентно

(2 ) 3 3x x + 2 = y

Таким образом, $y$ делится на $3,$ следовательно, $y = 3z$ для некоторого натурального $z.$ Уравнение теперь имеет вид

(2 ) 3 x x +2 = 9z

Очевидно, что $НОД (x,x2+ 2)≤ 2.$ Пусть $НОД (x,x2+ 2)= 1.$ Тогда либо $x =9u3$ и $x2+ 2= v3,$ либо $x =u3,x2+2 =9v3$ при некоторых натуральных $u,v.$ В первом случае $81u6$ $+2 =v3,$ что невозможно, так как куб целого числа при делении на $9$ даёт остаток $0$ или $±1.$ Аналогично второе равенство влечёт, что $u6+2 =9v3,$ что невозможно по тем же причинам. Итак, $НОД (x,x2+ 2) =2,x(x2+2)= 9z3.$ Тогда $x$ (и, следовательно, $z$ ) чётно, поэтому $x(x2+ 2)$ делится на $8.$ Поскольку $x2+ 2$ не делится на $4,$ получаем, что $x$ делится на $4.$

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

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

Найдите наименьшее натуральное число, не представимое в виде $2a−2b, 2c−2d$ где $a,b,c,d$ – натуральные числа.

Источники: Всеросс., 2005, ЗЭ, 10.1(см. math.ru)

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

4− 2 8−-4 8-− 2 16− 8 32− 2 1 = 4− 2, 2= 4− 2, 3= 4 − 2, 4= 4− 2 , 5= 8− 2

16− 4 16− 2 32 − 16 128− 2 64− 4 6= -4− 2-, 7=-4−-2 , 8 = 4-− 2-, 9 = 16−-2 , 10=-8−-2

Предположим, что $11= 22ac−−2b2d.$ Не уменьшая общности, положим $a> b, c> d.$ Обозначим $m = a− b, n= c− d, k= b− d.$ Получаем $11(2n− 1)= 2k(2m− 1).$ Так как в левой части целое нечётное число, то $k= 0.$ Понятно, что $m >n.$ Заметим, что $n= 1$ не подходит. Если же $m > n> 1,$ то $2m − 1$ и $2n − 1$ дают остаток $3$ при делении на $4.$ Значит, левая и правая части дают соответственно остатки $1$ и $3$ при делении на $4.$ Противоречие.

Ответ:

$11$

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

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

В таблице $2× n$ расставлены положительные числа так, что в каждом из $n$ столбцов сумма двух чисел равна $1.$ Докажите, что можно вычеркнуть по одному числу в каждом столбце так, чтобы в каждой строке сумма оставшихся чисел не превосходила $n+1 4 .$

Источники: Всеросс., 2005, ЗЭ, 10.2(см. math.ru)

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

Подсказка 1

Первым делом давайте упорядочим числа в верхней строке по возрастанию. Ясно, что числа под ними тогда убывают. Что же если сумма чисел в верхней строке меньше либо равна (n+1)/4, то можем зачеркнуть все числа из нижней. Однако могло так и не повезти, какие числа тогда естественно попробовать оставить в верхней строке?

Подсказка 2

В таком случае найдётся k, для которого сумма чисел, меньших k-ого по величине меньше (n+1)/4. Ясно, что нам нужно оставить в верхней строке числа с как можно большей суммой, потому логично попробовать найти максимальное такое k и зачеркнуть в верхней строке все числа, начиная с k-ого по величине.

Подсказка 3

Осталось оценить сумму чисел в нижней строке под вычеркнутыми сверху - это n+1-k наименьших чисел нижней строки. В силу выбора k можем оценить k-ое по величине число сверху, оно хотя бы (n+1)/4k, а отсюда можно оценить и числа под зачёркнутыми как (1-(n+1)/4k). Так, умножив оценку одного числа на их количество, получаем оценку и на сумму незачёркнутых чисел в нижней строке.

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

Пусть в верхней строке стоят числа $a,a ,...,a . 1 2 n$ Можно считать, что $a i$ стоит в $i−$ ом столбце и $a ≤a ...≤a 1 2 n$ (этого можно достигнуть перестановкой столбцов). Тогда в нижней строке соответственно стоят числа $b1 = 1− a1,...bn = 1− an.$ Легко видеть, что $b1 ≥ b2 ≥...≥bn.$ Если $n+1 a1+ a2+...+an ≤ 4 ,$ то можно вычеркнуть все числа нижней строки. В противном случае найдем наименьшее такое $k,$ что $n+1 a1+a2+ ...+ ak > 4 .$ Вычеркнем из верхней строки все числа $ak,ak+1,...,an,$ а из нижней — числа $b1,b2,...,bk−1.$ Тогда имеем

n+ 1 a1+ a2 +...+ak−1 ≤-4--

Заметим, что $ak ≥ a1+a2+k...+ak-> n4+k1$ (в силу выбора $k).$ Тогда

( ) bk +bk+1+ ...+bn ≤(n+ 1− k)bk = (n +1 − k)(1 − ak)< (n +1− k) 1− n+-1 4k

Заметим, что

( ) (n+ 1− k) 1− n+-1 = 5(n+ 1)− (n-+1)2−-(2k)2-≤ 5(n +1)− 4(n+-1)k = n-+1 4k 4 4k 4 4k 4

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

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

Дано дерево с $n$ вершинами, $n≥ 2.$ В его вершинах расставлены числа $x,x ,...,x , 1 2 n$ а на каждом ребре записано произведение чисел, стоящих в концах этого ребра. Обозначим через $S$ сумму чисел на всех рёбрах. Докажите, что

√---- 2 2 2 n+ 1(x1 +x2+ ...+ xn)≥2S

Источники: Всеросс., 2003, ЗЭ, 10.3(см. math.ru)

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

Рассмотрим ребро $l,$ соединяющее вершины с числами $x i$ и $x . j$ Обозначим через $k(l)$ количество вершин в компоненте связности, содержащей $xi,$ при удалении ребра $l.$ Тогда:

′ k(l)+ k(l)= n

где $k′(l)$ — количество вершин в компоненте, содержащей $x . j$ Для любого ребра $l$ верны неравенства:

′ 1≤ k(l)≤n − 1, 1 ≤k (l)≤ n− 1

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

Заметим, что:

′ (k(l)+-k′(l))2− (k(l)−-k′(l))2 n2−-(n-− 2)2 k(l)k(l)= 4 ≥ 4 = n− 1

Применим неравенство Коши для ребра $l:$

∘----′-- k(l)x2 +k′(l)x2 2xixj ≤ 2⋅ k(l)k-(l)|xixj|≤ ---i√------j- n− 1 n − 1

Суммируя по всем рёбрам дерева, получим:

∑ ∑ S = xixj ≤ √-1-- (k(l)x2i +k′(l)x2j) рёбраl n− 1рёбраl

Заметим, что для каждого $2 xi$ коэффициент при суммировании равен $n− 1,$

√----∑n 2S ≤ n− 1 x2i i=1

Таким образом, требуемое неравенство доказано.

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

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

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

Источники: Всеросс., 2002, ЗЭ, 10.8(см. math.ru)

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

Подсказка 1

Задачи по комбинаторной геометрии часта решаются рассмотрением чего-нибудь крайнего. Найдите в задаче что-нибудь такое.

Подсказка 2

Непонятно что крайнее рассматривать. Предлагается найти конструкцию следующего вида. Треугольник с чевианой, где чевиана и сторона, к которой она проведена, одного цвета, а остальные две стороны - другого.

Подсказка 3

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

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

Предположим противное. Заметим, что через каждую точку пересечения двух прямых проходит красная прямая. Рассмотрим синюю прямую $ℓ;$ пусть $A,B$ — две наиболее удалённые друг от друга точки пересечения $ℓ$ с красными прямыми, $m$ и $n$ — красные прямые, проходящие через $A$ и $B,C$ — точка пересечения $m$ и $n.$ Тогда через $C$ проходит синяя прямая $p,$ которая пересекает $ℓ$ в какой-то точке $D$ отрезка $AB,$ иначе $A$ и $B$ — не наиболее удалённые (cм. рис.).

$PIC$

Рассмотрим все четвёрки прямых $l′,m′,n′,p′,$ расположенных как $l,m,n,p(l′,p′$ — одного цвета; $m′,n′$ — другого; $m′,n′,p′$ пересекаются в одной точке; точка пересечения $p′$ и $l′$ лежит между точками пересечения $l′$ с $m′$ и $n′),$ и рассмотрим среди них такую, в которой прямые $l′,m ′,n′$ образуют треугольник наименьшей площади (cм. рис.). Тогда через точку $D ′$ проходит прямая $q′,$ одноцветная с $m ′.$ Она пересекает либо отрезок $B ′C′,$ либо $A′C′$ (пусть, для определенности, $B′C ′),$ Тогда прямые $n′,l′,p′,q′$ образуют конфигурацию с треугольником меньшей площади. Противоречие.

$PIC$

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

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

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

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

Многочлен $P(x)=x3 +ax2+ bx +c$ имеет три различных действительных корня, а многочлен $P(Q (x)),$ где $Q (x)= x2+ x+ 2001,$ действительных корней не имеет. Докажите, что $P(2001)> 1∕64.$

Источники: Всеросс., 2001, ЗЭ, 10.5(см. math.ru)

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

По условию $P(x)= (x− x)(x− x )(x− x ), 1 2 3$ следовательно,

P(Q (x))= (Q (x)− x1)(Q(x)− x2)(Q(x)− x3)

где $Q (x)− xi ⁄= 0,i= 1,2,3.$

Пусть $D i$ — дискриминанта квадратного трехчлена $Q(x)− x i$ при $i∈ {1,2,3,4}.$ Тогда $D = 1− 4(2001− x)< 0. i i$ Перемножив полученные неравенства $2001 − x > 1, i 4$ получаем $P(2001)= (2001− x )(2001− x )(2001 − x )> 1-. 1 2 3 64$

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

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

Существуют ли квадратные трёхчлены $ax2+bx+ c$ и $(a +1)x2+(b+ 1)x+ (c+1)$ с целыми коэффициентами, каждый из которых имеет по два целых корня?

Источники: Всеросс., 1997, ЗЭ, 10.5(см. math.ru)

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

Подсказка 1

Для начала давайте подумаем, что у нас есть в наличии. Во-первых, у нас есть факт, что все корни целые, во вторых, что все переменные a, b, c - целые. На какую тогда теорему нас могут натолкнуть эти два факта?

Подсказка 2

Верно, на теорему Виета! Ведь, так как корни целые, то и все коэффициенты приведенных квадратных трехчленов(то есть, когда мы поделим на главный коэффициент) должны быть целыми. А что это нам может дать?

Подсказка 3

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

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

Если каждый трёхчлен имеет целые корни, то каждое из выражений $c a$ , $b a$ , $c+1 a+1$ и $b+1 a+1$ должно быть целым, так как каждое из них выражается через соответствующие целые корни по теореме Виета.

Пусть $a$ — нечётное, тогда $a+ 1$ чётно, равно как и $b+ 1$ и $c+1$ . Следовательно, $b$ и $c$ нечётные. В этом случае видно, что если $x$ чётный, то $2 ax +bx+ c$ нечётно, а значит, не может равняться $0$ . Если же $x$ нечётный, то $2 ax +bx+ c$ также нечётно, пришли к противоречию.

Если $a$ — чётное, то мы придём к такому же противоречию, только со вторым трёхчленом.

Ответ: нет

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

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

На бесконечной в обе стороны полосе из клеток, пронумерованных целыми числами, лежит несколько камней (возможно, по нескольку в одной клетке). Разрешается выполнять следующие действия:

Снять по одному камню с клеток $n− 1$ и $n,$ и положить один камень в клетку $n+ 1;$
Снять два камня с клетки $n$ и положить по одному камню в клетки $n+ 1,$ $n− 2.$

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

Источники: Всеросс., 1997, 10.8(см. math.ru)

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

Подсказка 1

Обозначим a(i) — количество камней в i-ой клетке. Будем говорить, что набор всех a(i) образует конфигурацию. Хотелось бы придумать инвариант, который не изменяется при разрешенных операциях. Каким мог бы быть этот инвариант?

Подсказка 2

Пусть x — некоторое число. Тогда назовем весом конфигурации число, равное бесконечной сумме по всем целым i чисел, равных произведению a(i) и i-ой степени x. Можно ли выбрать x так, чтобы вес не менялся при разрешенных операциях?

Подсказка 3

Конечно! Достаточно положить x > 1 таким, чтобы он удовлетворял равенству x² = x + 1. Попробуем теперь доказать, что любая последовательность действий конечна. Наибольший номер непустой клетки не может уменьшаться. А может ли он увеличиваться бесконечно?

Подсказка 4

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

Подсказка 5

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

Подсказка 6

Точно! Можно убрать камни с большими номерами и применить индукцию. Остается показать, что конечная конфигурация от последовательности действий не зависит. Для этого стоит сначала понять, как может выглядить конечная конфигурация!

Подсказка 7

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

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

Обозначим через $a i$ количество камней в клетке с номером $i.$ Тогда последовательность $A= (a) i$ задает конфигурацию — расположение камней по клеткам. Пусть $α$ — корень уравнения $2 x =x +1,$ больший $1.$ Назовем весом конфигурации $A$ число $∑ i w (A)= aiα.$ Покажем, что разрешенные действия не меняют веса. Действительно,

n+1 n n−1 n−1( 2 ) α − α − α =α α − α− 1 = 0

n+1 n n−2 n−2 ( 2 ) α − 2α +α = α (α− 1) α − α− 1 = 0

Докажем индукцией по $k$ — числу камней, что любая последовательность действий завершается. При $k= 1$ это верно. Пусть при числе камней, меньшем $k,$ утверждение верно. Рассмотрим процесс, начинающийся с конфигурации $A =(a) i$ с $∑ a = k. i$ Наибольший номер непустой клетки при разрешенных действиях не уменьшается, но и расти бесконечно он не может — он не может превысить числа $n,$ при котором $n α >w (A ).$ Значит, с какого-то момента наибольший номер непустой клетки перестает изменяться, и с камнями, попавшими в эту клетку, уже ничего не происходит. Выбросим эти камни, и применим предположение индукции к оставшимся.

В конечной конфигурации в каждой клетке не более одного камня, и нет двух непустых клеток подряд. Докажем, что любые две конфигурации $A= (ai)$ и $B = (bi)$ с такими свойствами имеют разные веса. Пусть $n$ — наибольший номер, при котором $ai ⁄= bi;$ пусть, для определенности, $an = 1,bn =0.$ Выбросим из $A$ и $B$ все камни с номерами, большими $n$ (они в $A$ и $B$ совпадают). Для оставшихся конфигураций $′ A$ и $′ B$ имеем:

( ′) n w A ≥ α ; w(B ′)< αn−1+ αn−3+ αn− 5+...=αn−1---1−2 =αn. 1 − α

Таким образом, для любой конфигурации есть только одна конечная с таким же весом; только к ней и может привести процесс.

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

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

Последовательность натуральных чисел $a i$ такова, что

НОД(ai,aj)=H ОД(i,j)

для всех $i⁄= j.$ Докажите, что $a = i i$ для всех $i∈ ℕ.$

Источники: Всеросс., 1995, ЗЭ, 10.5(см. math.ru)

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

Подсказка 1:

Глобально в этой задаче нужно просто поиграться с НОДами. Попробуйте рассмотреть НОДы чисел с какими-то интересными индексами.

Подсказка 2:

Например, если рассмотреть НОД членов с индексами i, 2i, станет ясно, что aᵢ ≥ i.

Подсказка 3:

А теперь, предположив, что aᵢ > i, попробуйте рассмотреть НОД такой пары, который с одной стороны равен одному числу, а с другой стороны - другому.

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

Так как каждое $a i$ делится на НОД $(a,a )= i 2i$ НОД $(i,2i)= i$ , то $a ≥i i$ для всех $i∈ ℕ.$ Предположим, что $a >i i$ при некотором $i.$ Тогда, с одной стороны, НОД $(ai,aai) =$ НОД $(i,ai)= i$ (так как $ai$ делится на $i$ ), а с другой стороны, поскольку $aai$ делится на $ai,$ то НОД $(ai,aai)= ai > i.$ Противоречие.