Тема Региональный этап ВсОШ и олимпиада им. Эйлера

Регион 10 класс

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

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

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

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

Подтемы раздела региональный этап всош и олимпиада им. эйлера

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

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

Задача 1#74875

Последовательность чисел $a ,a ,... 1 2$ задана условиями $a =1 1$ , $a = 143 2$ и

a1+a2-+...+-an an+1 = 5⋅ n

при всех $n ≥2.$ Докажите, что все члены последовательности — целые числа.

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

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

Положим $S = a + a +...+a , n 1 2 n$ тогда $a =S − S . n+1 n+1 n$ Достаточно показать, что все числа $S n$ – целые. Заметим, что $S1 = 1,S2 = 144,$ и $5Sn- Sn+1 − Sn = n ,$ то есть $n+5 Sn+1 = n Sn.$ Значит, при $n≥ 2$

(n+ 5)(n+ 4)...⋅7 (n+ 5)(n+ 4)(n+ 3)(n+ 2)(n+ 1) Sn+1 =--n(n−-1)...⋅2--⋅S2 =--------6⋅5⋅4⋅3⋅2---------⋅144=

= (n-+5)(n-+4)(n-+3)(n-+2)(n+1)- 5

Так как одно из чисел $n+ 5,n +4,n+ 3,n +2,n+ 1$ делится на $5,$ то при $n ≥2$ число $Sn+1$ – целое.

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

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

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

Задача 2#31258

В окружность $Ω$ вписан шестиугольник $AECDBF$ . Известно, что точка $D$ делит дугу $BC$ пополам, а треугольники $ABC$ и $DEF$ имеют общую вписанную окружность. Прямая $BC$ пересекает отрезки $DF$ и $DE$ в точках $X$ и $Y$ , а прямая $EF$ пересекает отрезки $AB$ и $AC$ в точках $Z$ и $T$ соответственно. Докажите, что точки $X,Y,T,Z$ лежат на одной окружности.

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

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

Подсказка 1

Из-за общей вписанной окружности добываем ещё одну биссектрису и, соответственно, середину дуги

Подсказка 2

Раз проведены из середин дуг отрезки, то поможет лемма, что всегда получается добыть ещё вписанность (посчитайте угол между хордами и вписанный угол)

Подсказка 3

Явно же не хочется в XYTZ проводить что-то такое и считать углы, значит, надо будет считать отрезки. А счёт отрезков для вписанных четырёхугольников это степень точки писать

Подсказка 4

Рассмотрите случай, когда стороны XYTZ параллельны, а в ином случае можно пересечь и реализовать план пункта 2

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

$PIC$

Пусть $I$ — центр вписанной окружности $ABC$ и $DEF$ , тогда $A,I,D$ образуют прямую, поскольку $D$ — середина дуги $BC$ , кроме того, тогда $A$ — середина дуги $FE$ . Заметим, что $⌢ ⌢ ⌢ ⌢ 2∠FED = FB + BD =F B+ CD = 2∠FXB$ , откуда $EF XY$ вписан. Аналогично $∠ACB =∠F ZB$ и вписан $BCZT$ . Далее если $FE||BC$ , то картинка симметрична и $ZTXY$ образуют прямоугольник, иначе $S =EF ∩ BC$ , запишем степень точки $S$

SX⋅SY = SF ⋅SE = SB⋅SC = SZ⋅ST

Пользуемся вписанностью $FEYX$ , $BF EC$ и $BZT C$ , в итоге $ZTY X$ вписан из равенства первого и последнего.

Ответ:

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

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

Задача 3#79752

Пусть $P(x)= a xn+ a xn−1+ ...+ ax +a , n n−1 1 0$ где $n$ — натуральное число. Известно, что числа $a,a ,...,a 0 1 n$ — целые, при этом $an ⁄=0,an−k = ak$ при всех $k= 0,1,...,n,$ и $an+ an−1+ ...+a1 +a0 = 0.$ Докажите, что число $P(2022)$ делится на квадрат некоторого натурального числа, большего $1.$

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

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

Достаточно доказать утверждение: многочлен $P (x)$ делится на $(x − 1)2.$ Действительно, после деления (например, столбиком), в частном получится многочлен $Q(x)$ с целыми коэффициентами, и тогда равенство многочленов $2 P(x)= (x− 1)Q (x)$ влечет равенство $2 P (2022)= 2021 ⋅Q (2022),$ из которого следует утверждение задачи, поскольку $Q(2022)$ — целое число.

Для доказательства утверждения сделаем замену $t= x− 1,$ положим $n n−1 R(t)= P(t+1)= an(t+ 1) +an−1(t+1) + ...+a1(t+1)+ a0$ и докажем, что $R(t)$ делится на $2 t ,$ т.е. что последние два коэффициента многочлена $R(t)$ равны $0.$

Свободный член многочлена $R$ равен $R(0) =an+ an−1+ ...+ a0 =0.$ Поскольку в многочлене $k (t+ 1)$ коэффициент при $t$ равен $k,$ коэффициент при $t$ многочлена $R$ равен $nan+ (n − 1)an−1 +...+ a1.$ Из условий $an−k = ak$ следует, что удвоенный коэффициент при $t$ равен $(nan+ (n − 1)an−1 +...+a1)+(na0+ (n − 1)a1+...+an−1)= n(an+ an−1+ ...+a0)= 0.$ Тем самым, задача решена.

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

Задача 4#88689

Дан квадратный трехчлен $P (x)$ . Докажите, что существуют попарно различные числа $a$ , $b$ и $c$ такие, что выполняются равенства

P(b+c)= P(a),P(c+ a)= P(b),P (a +b)= P(c).

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

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

Подсказка 1

Очень полезно уметь представлять такие задачи. Мы знаем, что Р(х) --- это трёхчлен. Как выглядит его график?

Подсказка 2

Это парабола! Вспомним, что парабола симметрична относительно некоторой вертикальной прямой. А если значения в двух различных точках параболы равны, то что можно сказать про эти точки?

Подсказка 3

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

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

Пусть $d$ — абсцисса вершины параболы $y =P(x)$ , так что прямая $x= d$ — ось симметрии параболы. Тогда для любых чисел $t$ и $s$ с суммой $2d$ (т.е. таких, что точки $t$ и $s$ симметричны относительно $d)$ выполнено $P(t)= P(s)$ .

Таким образом, любая тройка попарно различных чисел $a,b,c$ с суммой $2d$ будет удовлетворять условию задачи. Можно взять, скажем,

2d 2d 2d a =-3 − 1,b= 3-,c= 3-+1.

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

Задача 5#75240

Пусть $p$ — простое число, большее $3.$ Докажите, что найдется натуральное число $y,$ меньшее $p∕2$ и такое, что число $py+ 1$ невозможно представить в виде произведения двух целых чисел, каждое из которых больше $y.$

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

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

Положим $p= 2k+ 1.$ Предположим противное: для каждого из чисел $y = 1,2,...,k$ существует разложение $py +1= a b, y y$ где $ay > y,by >y.$ Заметим, что каждое из чисел $ay$ и $by$ строго больше $1,$ а также что $ay < p,by < p,$ иначе $ayby ≥ p(y +1)> py+ 1.$ Значит, каждое из $p− 1$ чисел набора $a1,b1,a2,b2,...ak,bk$ лежит в множестве из $p− 2$ чисел ${2,3,...,p− 1}.$ Таким образом, в этом наборе найдутся два равных числа. Пусть каждое из этих двух чисел равно $d.$

Пусть эти равные числа имеют равные индексы в наборе, то есть $ay = by =d$ при некотором $y.$ Тогда $2 py+ 1= d,$ поэтому число $2 d − 1= (d − 1)(d +1)= py$ делится на простое $p.$ Так как $1≤d − 1< d+ 1≤ p,$ это может быть лишь при $d+ 1= p.$ Тогда соответствующее значение $y$ равно $d− 1= p− 2 =2k− 1,$ что при $p >3$ больше, чем $k.$ Противоречие (так как $y ≤k$ ).

В противном случае существуют индексы $y1 < y2$ такие, что $1≤ y1 < y2 < d,$ для которых числа $py1+ 1$ и $py2+ 1$ делятся на $d.$ Тогда и $p(y2− y1) =(py2 +1)− (py1+ 1)$ также делится на $d.$ Из взаимной простоты чисел $d$ и $p$ получаем, что $y2− y1$ делится на $d,$ а это невозможно, так как $0< y2− y1 < y2 < d.$

Таким образом, в каждом случае получено противоречие и, следовательно, указанное в условии задачи число $y$ всегда найдётся.

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

Задача 6#79694

На сторонах выпуклого четырёхугольника $ABCD$ во внешнюю сторону построены прямоугольники. Оказалось, что все вершины этих прямоугольников, отличные от точек $A,B,C,D,$ лежат на одной окружности. Докажите, что четырехугольник $ABCD$ — вписанный.

Источники: Всеросс., 2020, РЭ, 10.7(см. olympiads.mccme.ru)

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

$PIC$

Пусть $ABXY$ — один из данных прямоугольников, а $O$ — центр окружности, на которой лежат восемь вершин из условия задачи. Тогда $O$ лежит на серединном перпендикуляре к отрезку $XY.$ Но он совпадает с серединным перпендикуляром к отрезку $AB.$ Поскольку $O$ лежит на нём, имеем $OA =OB.$ Аналогично доказываем, что $OB = OC$ и $OC =OD.$ Тогда $O$ равноудалена от всех вершин четырехугольника $ABCD,$ значит, $ABCD$ вписан в окружность с центром $O,$ что и требовалось доказать.

Курсы

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

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

Задача 7#79750

На доске пишут $n$ квадратных трёхчленов вида $⋆x2+ ⋆x +⋆$ (вместо коэффициентов написаны звёздочки). Можно ли при каком-либо $n >100$ поставить вместо $3n$ звёздочек некоторые $3n$ последовательных натуральных чисел (в каком-то порядке) так, чтобы каждый из $n$ данных трёхчленов имел два различных целых корня?

Источники: Всеросс., 2020, РЭ, 10.8(см. olympiads.mccme.ru)

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

Решение будет состоять из трёх шагов $(A,B,C).$

$A)$ Докажем следующую лемму. Лемма. Пусть при некоторых натуральных $a,b,c$ квадратный трёхчлен $2 ax +bx+ c$ имеет целые корни. Тогда $b$ и $c$ делятся на $a.$

Доказательство. По теореме Виета $b a =− (x1+ x2)$ и $c a = x1x2$ являются целыми числами. Лемма доказана.

$B)$ Предположим, что натуральные числа $k+1,k+ 2,...,k+ 3n$ (при некотором целом неотрицательном k) нужным образом расставлены в качестве коэффициентов данных квадратных трёхчленов $2 aix + bix +ci(i= 1,2,...,n).$ Для определённости пусть $a1 < a2 < ...< an.$ Тогда $a1 ≥k +1,$ откуда $a2 ≥k +2,$ и т.д., $an ≥ k+ n.$ Тогда из леммы следует, что минимальное из чисел $bn,cn$ не меньше, чем $2an,$ а максимальное (назовём его $M$ ) — не меньше, чем $3an.$ Но $M$ должно быть среди чисел $k+1,k+ 2,...,k+ 3n.$ Получаем $3(k+n)≤ 3an ≤ M ≤ k+3n.$ Отсюда $k≤ 0,$ и, значит, $k= 0.$ Кроме того, $an =n,$ откуда сразу следует, что $ai = i$ при $i= 1,2,...,n.$

$C)$ Среди $3n$ подряд идущих чисел менее $3n2 + 1$ чётных. С другой стороны, зная, что $ai$ пробегают числа ${1,2,...,n},$ получим оценку снизу на количество $C$ чётных чисел среди всех коэффициентов. Заметим, что в каждой из $n$ троек $(ai,bi,ci)$ хотя бы одно чётное число, иначе значение трёхчлена $aix2+ bix+ ci$ в любой целой точке будет нечётно, в частности, такой трёхчлен не может иметь целых корней. Если же $ai$ чётно (количество соответствующих троек $(ai,bi,ci)$ равно $[n2]$ ), то $bi$ и $ci,$ в силу леммы, тоже чётные, значит, в такой тройке $(ai,bi,ci)$ все три коэффициента чётные. Итого $C ≥ n+ 2[n2]≥ 2n− 1.$ Сравнивая верхнюю и нижнюю оценки, имеем $3n2-+1 >C ≥ 2n − 1,$ откуда $n< 4.$ Противоречие.

Ответ:

Нет

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

Задача 8#79754

Петя задумал два многочлена $f(x)$ и $g(x),$ каждый вида $ax2+bx+ c$ (т. е. степень каждого многочлена не превышает $2$ ). За ход Вася называет Пете число $t,$ а Петя сообщает ему (по своему усмотрению) одно из значений $f(t)$ или $g(t)$ (не уточняя, какое именно он сообщил). После $n$ ходов Вася должен определить один из петиных многочленов. При каком наименьшем $n$ у Васи есть стратегия, позволяющая гарантированно этого добиться?

Источники: Всеросс., 2020, РЭ, 10.10(см. olympiads.mccme.ru)

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

Мы будем называть многочлен вида $ax2+bx+ c$ просто многочленом, а график такого многочлена — просто графиком. Мы будем пользоваться следующей известной леммой.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Через любые три точки $(ai,bi)(i=1,2,3)$ с разными абсциссами проходит ровно один график.

Доказательство. Один график, проходящий через эти точки, найдётся всегда. С другой стороны, если через три точки проходят графики двух разных многочленов $f(x)$ и $g(x),$ то разность $f(x)− g(x)$ имеет три корня $a1,a2,a3,$ что невозможно.

_________________________________________________________________________________________________________________________________________________________________________________

Из леммы следует, что через любые две точки с разными абсциссами проходит бесконечно много графиков, и любые два из них пересекаются только по этим двум точкам. Перейдём к решению. Будем считать, что Петя задумал два графика, за ход Вася называет Пете число $t,$ а Петя отмечает точку с абсциссой $t$ на одном из графиков. Можно считать, что на разных ходах Вася называет разные $t$ (иначе Петя повторит ответ).

Рассмотрим ситуацию после $k$ ходов. Назовём пару графиков подходящей, если объединение этих графиков содержит все отмеченные Петей точки.

$1)$ Покажем, что $k≥8.$ Мы будем считать, что Петя изначально не рисует никаких графиков, а просто отмечает некоторые точки с данными абсциссами. Покажем, как ему действовать, чтобы после $7$ ходов нашлись две подходящих пары графиков такие, что все $4$ графика различны; это и будет означать, что Вася не смог добиться требуемого, ибо Петя мог нарисовать любую из этих пар.

Будем обозначать точку, появляющуюся после $i$ -го хода, через $Ai = (ai,bi).$ На первых двух ходах Петя выбирает $b1 =b2 = 0.$ На следующих $4$ ходах Петя отметит точки $A3$ и $A4$ на графике $F+$ многочлена $f+(x)= (x − a1)(x− a2)$ и точки $A5$ и $A6$ — на графике $F−$ многочлена $f−(x)= −(x− a1)(x− a2).$ Седьмым ходом Петя выбирает точку $A7$ , не лежащую ни на одном из графиков, проходящем через какие-то три точки из $A1,A2,A3,A4,A5$ и $A6.$ Тогда существуют графики $G+$ и $G,$ проходящие через тройки точек $A5,A6,A7$ и $A3,A4,A7;$ согласно нашему выбору, эти графики различны и отличаются от $F+$ и $F −.$ Значит, пары $(F+,G+ )$ и $(F−,G−)$ — подходящие, и все эти четыре графика различны, то есть Вася не сможет добиться требуемого.

$2)$ Покажем, как Васе добиться требуемого за $8$ ходов. На первых $7$ ходах он называет $7$ произвольных различных чисел.

Назовём график подозрительным, если он проходит хотя бы через три точки, отмеченных Петей на этих ходах. Назовём число $a$ плохим, если два различных подозрительных графика имеют общую точку с абсциссой $a.$ Существует лишь конечное количество подозрительных графиков и, следовательно, лишь конечное количество плохих чисел.

На восьмом ходу Вася называет любое неплохое число $a8.$ После того, как Петя отметит восьмую точку, возможны два случая.

Случай $1.$ Существует график $G$ многочлена $f(x),$ содержащий пять из восьми отмеченных точек. Три из этих точек лежат на одном из Петиных графиков; по лемме, этот график совпадает с $G.$ Значит, Васе достаточно назвать многочлен $f(x).$

Случай $2.$ Такого графика нет. Это значит, что на каждом из Петиных графиков лежит ровно по $4$ отмеченных точки; поэтому оба этих графика подозрительны. Докажем, что существует единственная пара подозрительных графиков, содержащих в совокупности все $8$ отмеченных точек; тогда Васе достаточно назвать любой из соответствующих многочленов. Пусть $(G1,H1)$ и $(G2,H2)$ — две таких пары, причём $H1$ и $H2$ содержат $A8.$ Согласно выбору числа $a8,$ это может произойти лишь при $H1 = H2.$ Но тогда каждый из графиков $G1$ и $G2$ проходит через $4$ отмеченных точки, не лежащих на $H1,$ и они совпадают согласно лемме. Значит, и наши пары совпадают.

Ответ:

$8$

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

Задача 9#79753

Бесконечная последовательность ненулевых чисел $a ,a,a ,... 1 2 3$ такова, что при всех натуральных $n >2024$ число $a n+1$ является наименьшим корнем многочлена

2n 2n−2 2n−4 Pn(x)=x + a1x + a2x + ...+ an

Докажите, что существует такое $N,$ что в бесконечной последовательности $a ,a ,a ,..., N N+1 N+2$ каждый член меньше предыдущего.

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

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

Пусть $n ≥2018.$ Заметим, что $P (a) =P (−a) n n$ при всех $a.$ Значит, поскольку $P (x) n$ имеет ненулевой корень, он имеет и отрицательный корень, откуда $an+1 < 0.$

Далее, поскольку $2 Pn+1(x)= x Pn(x)+ an+1,$ имеем

2 Pn+1(an+1)= an+1Pn(an+1)+ an+1 =0+ an+1 < 0

Так как степень многочлена $P (x) n+1$ чётна, а старший коэффициент положителен, при достаточно больших по модулю отрицательных $x$ он принимает положительные значения. Теперь из полученного выше соотношения следует, что у этого многочлена есть корень на интервале $(−∞ ),an+1).$ Значит, и $an+2 < an+1.$

Итак, мы получили, что $an+2 < an+1$ при всех $n ≥2018.$ Это означает, что последовательность $(a2019,a2020,a2021,...)$ — убывающая.

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

Задача 10#81692

Даны действительные числа $a$ и $b,$ причём $b>a >1.$ Пусть

n( 2n√ - 2n√-) xn =2 b− a

Докажите, что последовательность $x1,x2,...$ убывает.

Источники: Всеросс., 2019, РЭ, 10.7(см. olympiads.mccme.ru)

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

Нас просят доказать неравенство $x > x n n+1$ для всех натуральных $n.$ По условию $b> a> 1.$ Перепишем корни в степени и приступим к доказательству:

n -1 -1 n+1 -1-- -1-- 2 (b2n − a2n)> 2 (b2n+1 − a2n+1)

Сократим на $2n :$

1n 1n- -n1+1 -1n+1- b2 − a2 > 2(b2 − a2 )

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

21n 21n 2n1+1- 2n1+1 21n+1- 2n1+1- b − a = (b − a )(b + a )

Сократим на величину $b21n+1 − a2n1+1,$ которая является положительной, поскольку $b >a >1 :$

b2n1+1 + a21n+1-> 2

Осталось заметить, что $1 b2n+1->1$ и $1 a2n+1 > 1,$ потому что $b>1$ и $a >1.$ Следовательно, их сумма больше $2.$

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

Задача 11#73548

Петя и Вася по очереди выписывают на доску натуральные числа, не превосходящие $2018$ (выписывать уже имеющееся число запрещено); начинает Петя. Если после хода игрока на доске оказываются три числа, образующих арифметическую прогрессию, этот игрок выигрывает. У кого из игроков есть стратегия, позволяющая ему гарантированно выиграть?

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

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

Рассмотрим момент после третьего хода (когда выписаны три числа). Если к этому моменту никто еще не выиграл, то следующим ходом Вася выигрывает — ему достаточно найти два выписанных числа одной чётности и выписать своим ходом их среднее арифметическое (оно является целым числом).

Кроме того, заметим, что если три целых числа из множества $1,2,3,...,2018$ образуют арифметическую прогрессию, то её разность не больше $1008$ (иначе разность между наибольшим и наименьшим числами будет не менее $2⋅1009= 2018,$ что невозможно).

Теперь опишем выигрышную стратегию Васи.

Пусть первым ходом Петя выписал число $a$ . Предположим, что $a≤ 1009.$ Тогда Вася выписывает то из чисел $2017$ или $2018$ , чётность которого отлична от чётности числа $a$ (обозначим это число через $b$ ). После этого хода выписано два числа разной чётности; значит, они не могут быть первым и третьим членом прогрессии из целых чисел. А поскольку $b− a> 1009,$ они также не могут быть соседними членами прогрессии. Тем самым, Петя не сможет выиграть третьим ходом. Но в этом случае, как мы видели ранее, следующим ходом Вася выиграет.

Если же $a >1010,$ то Вася отвечает, выписывая то из чисел $1$ и $2,$ которое по чётности отличается от $a.$ Дальнейшие рассуждения аналогичны первому случаю.

Ответ:

У Васи

Интенсивы

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

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

Задача 12#79857

Дана клетчатая доска $1000×1000.$ Фигура гепард из произвольной клетки $x$ бьёт все клетки квадрата $19 ×19$ с центральной клеткой $x,$ за исключением клеток, находящихся с $x$ в одном столбце или одной строке. Какое наибольшее количество гепардов, не бьющих друг друга, можно расставить на доске?

Источники: Всеросс., 2018, РЭ, 10.8(см. olympiads.mccme.ru)

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

Подсказка 1

Так как здесь у нас речь идёт про фигуру, бьющую определённым образом поля, то давайте попробуем для оценки разбить доску на части. Доска у нас 1000 на 1000. И гепард бьёт клетки в определённом квадрате. Тогда на какие части хорошо бы разбить доску? К тому же они должны быть удобными для работы и оценки.

Подсказка 2

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

Подсказка 3

Да, такого не может произойти, так как в таком случае они будут бить друг друга, даже если будут стоять на одной вертикали и горизонтали с исходным. Значит, всех гепардов в квадрате 10 на 10 мы ставим в один ряд, откуда их не более 10. Остался пример. Так как мы всю задачу как-то работали с числом 10, то как лучше всего их расположить в таком случае?

Подсказка 4

Верно, мы можем расположить их в один столбец с интервалом в 10 клеток. Тогда несложно увидеть, что всё сработает. Победа!

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

Разобьём доску на $1002$ квадратов $10× 10.$ Покажем, что в каждом квадрате может стоять не более $10$ гепардов, не бьющих друг друга — отсюда будет следовать, что общее число гепардов не может превосходить $2 100 ⋅10= 100000.$

Рассмотрим произвольный квадрат $Q$ размера $10×10$ и произвольного гепарда $g$ в нём. Гепард $g$ бьёт все клетки квадрата, кроме клеток, лежащих с ним в одной строке или в одном столбце. Если один из остальных гепардов $′ g$ в квадрате $Q$ стоит в одной строке с $g,$ а ещё один, $′′ g ,$ — в одном столбце с $g,$ то $′ g$ и $′′ g$ стоят в разных строках и столбцах и, следовательно, бьют друг друга; это невозможно. В противном случае, без ограничения общности, все гепарды в квадрате $Q$ стоят в одной строке с $g,$ то есть их не больше $10.$

Таким образом, мы доказали, что общее число гепардов не может превосходить $100000;$ осталось привести пример, когда эта оценка достигается. Пронумеруем столбцы доски подряд числами $1,2,...,1000.$ Расставим гепардов на все клетки столбцов, номера которых делятся на $10.$ Этих гепардов будет $1000⋅100= 100000,$ и они не будут бить друг друга.

Ответ:

$100000$

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

Задача 13#73209

Изначально на доске записаны несколько натуральных чисел (больше одного). Затем каждую минуту на доску дописывается число, равное сумме квадратов всех уже записанных на ней чисел (так, если бы на доске изначально были записаны числа $1,2,2,$ то на первой минуте было бы дописано число $2 2 2 1 + 2 +2$ ). Докажите, что сотое дописанное число имеет хотя бы $100$ различных простых делителей.

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

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

Заменим в условии сто на $n$ и докажем утверждение индукцией по $n.$ Обозначим число, записанное на $n$ -й минуте через $S . n$ Так как $S1 > 1,$ оно имеет хотя бы один простой делитель, то есть база доказана.

Переход. Заметим, что $2 2 2 2 Sn+1 = Sn+ Sn−1+ ...+S1 =Sn +Sn = Sn(Sn+ 1).$ То есть $Sn+1$ делится на все простые делители $Sn$ (по предположению их хотя бы $n$ ), а также оно делится на простой делитель $Sn+ 1,$ отличный от простых делителей $Sn,$ поскольку $(Sn+ 1,Sn)= 1.$ Получили требуемое.

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

Задача 14#81579

Паша выбрал $2017$ (не обязательно различных) натуральных чисел $a ,a ,...,a 1 2 2017$ и играет сам с собой в следующую игру. Изначально у него есть неограниченный запас камней и $2017$ больших пустых коробок. За один ход Паша добавляет в любую коробку (по своему выбору) $a1$ камней, в любую из оставшихся коробок (по своему выбору) — $a2$ камней, $...,$ наконец, в оставшуюся коробку — $a2017$ камней. Пашина цель — добиться того, чтобы после некоторого хода во всех коробках стало поровну камней. Мог ли он выбрать числа так, чтобы цели можно было добиться за $43$ хода, но нельзя — за меньшее ненулевое число ходов?

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

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

Заметим, что $2017= 43⋅46+39.$ Приведём пример Пашиных чисел, при которых требуемое выполняется. Пусть среди его чисел $39$ двоек, $46$ чисел, равных $44,$ а остальные — единицы.

Чтобы добиться требуемого за $43$ хода, Паша выбирает $39$ коробок, в которые он всегда кладёт по два камня — через $43$ хода в них окажется $2⋅43 =86$ камней. Остальные коробки он разбивает на $43$ группы по $46$ коробок; на $i$ -м ходу он положит по $44$ камня во все коробки $i$ -й группы и по одному камню — в коробки остальных групп. Тогда через $43$ хода в каждой коробке каждой группы будет по $44+42⋅1= 86$ камней, то есть во всех коробках будет поровну камней.

Осталось доказать, что за меньшее число ходов требуемое невыполнимо. Пусть Паша сделал $k< 43$ ходов. Тогда в какую-то коробку $A$ попало $44$ камня на одном ходу и в ней будет не меньше, чем $44+ (k− 1)= 43+ k$ камней. С другой стороны, поскольку $46k <2017,$ в какую-то коробку $B$ ни на одном из ходов не попадёт $44$ камня, то есть в ней будет не больше $2k$ камней. Поскольку $k <43,$ имеем $2k< k+ 43,$ а значит, в коробке $B$ меньше камней, чем в $A.$ Таким образом, Паша ещё не добился требуемого.

Ответ:

Да, мог

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

Задача 15#73365

Известно, что свободный член $α 0$ многочлена $P(x)$ с целыми коэффициентами по модулю меньше 100, а $P(20)= P(16)=2016.$ Найдите $α0.$

Источники: Отборочный этап олимпиады БИБН - 2016 (адаптация задачи 10.6 с Регионального этапа ВсОШ - 1994)

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

Подсказка 1

Есть смысл рассматривать не многочлен P(x), а многочлен P(x) - 2016, ведь у него мы знаем два корня.

Подсказка 2

Понятно, что мы можем записать многочлен P(x) - 2016, как (x - 20)(x - 16)Q(x). Попробуйте выразить P(0).

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

Из условия следует, что

P(x)− 2016 =(x− 20)(x− 16)Q(x)

где $Q (x)$ — некоторый целочисленный многочлен.

Как известно, свободный член многочлена равен его значению в нуле. Тогда

P(0)= 2016+ 320Q (0)

Из условия

−100≤ 2016+ 320Q (0)≤ 100

получаем, что $Q(0)= −6,$ а свободный член равен $96.$

Ответ:

$96$

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

Задача 16#75449

Коэффициенты $a,b,c$ квадратного трёхчлена $f(x)= ax2 +bx+ c$ — натуральные числа, сумма которых равна $2000.$ Паша может изменить любой коэффициент на $1,$ заплатив $1$ рубль. Докажите, что он может получить квадратный трёхчлен, имеющий хотя бы один целый корень, заплатив не более $1050$ рублей.

Источники: Всеросс., 2015, РЭ, 10.7(см. olympiads.mccme.ru)

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

Подсказка 1

Во-первых, что мы можем делать, чтобы при каком-то условии точно был корень? Мы можем уменьшать c до 0, ведь тогда у нас будет корень 0. Но что, если c > 1050?

Подсказка 2

Тогда a + b <= 949. Что еще нам выгодно сделать? Коль скоро мы уже зануляли последний коэффициент, то надо пробовать занулить средний (ведь в дискриминанте первый и последний почти никак не отличаются, так как они равноправны). Что мы вообще хотим, если предполагаем занулять средний? Мы хотим, чтобы -4ac было квадратом, значит, a < 0. Ну и поскольку а никак не зависит от с, не считая суммы, то стоит попробовать взять а = -1, и тогда останется только сделать c - точным квадратом. Почему все это можно реализовать за 1050 действий?

Подсказка 3

Верно, чтобы сделать a = -1, b = 0 надо не более 950 действий. У нас остается 100 действий, но при этом, понятно, что в силу того, что с < 2000, так как изначально числа натуральные, то расстояние до ближайшего квадрата точно не больше чем 45^2 - 44^2(чем больше квадрат, тем больше расстояние от него до следующего) = 89 < 100. Значит, 100 действий, чтобы довести до квадрата, хватит!!

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

Если $c ≤1050,$ то просто сделаем $c =0$ и получим корень $x = 0.$ Пусть теперь $c≥ 1051,$ тогда $a +b≤ 949.$ Сделаем $a =− 1$ и $b =0,$ на это уйдёт не более $950$ рублей. В нашем распоряжении осталось хотя бы $100$ рублей, покажем, что их достаточно, чтобы увеличить или уменьшить $c$ до ближайшего квадрата. $c< 2000,$ а значит оно располагается между квадратами, расстояние между которыми не превосходит $2 2 45 − 44 = 89< 100.$ Таким образом, нам хватит $100$ рублей, чтобы сделать $c$ квадратом и получить трёхчлен $2 2 − x + n ,$ который имеет целые корни, что и требовалось.

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

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

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

Задача 17#90112

Положительные числа $a,b,c$ удовлетворяют соотношению $ab+ bc+ ca= 1.$ Докажите, что

∘----1 ∘---1 ∘ ---1 √ - √ - √ - a + a + b+ b + c+ c ≥ 2( a+ b+ c)

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

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

Подсказка 1:

Есть условие ab + bc + ca = 1. Оно довольно непростое, подумайте, что с ним можно сделать.

Подсказка 2:

Его нужно куда-то подставить вместо 1. Но как понять куда, ведь единицу можно найти везде, даже a = a*1.

Подсказка 3:

Подставьте вместо числителя в дробях 1/a, 1/b, 1/c. Что теперь там хорошего получается? Теперь можно уже и вспомнить классические неравенства, попробовать применить их.

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

Заметим, что

∘---1- ∘---ab+-bc-+ac ∘ ---bc------ ∘-√------- ∘-√---√--- a+ a = a+ ----a----= a+ a-+b+ c≥ 2 bc+ b+ c= ( b+ c)2

√ - = b+√c

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

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

Задача 18#99946

В языке племени АУ две буквы — $a$ и $y.$ Некоторые последовательности этих букв являются словами, причём в каждом слове не больше $13$ букв. Известно, что если написать подряд любые два слова, то полученная последовательность букв не будет словом. Найдите максимальное возможное количество слов в таком языке.

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

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

Подсказка 1

Сколько существует слов длины n, которые состоят только из буквы a и у?

Подсказка 2

Верно, 2^n. Может ли в искомом множестве слов не быть слов длины 13?

Подсказка 3

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

Подсказка 4

Давайте возьмем в множество все слова длины хотя бы 7. Чему равно количество слов? Почему нельзя больше?

Подсказка 5

Количество слов равно 2¹⁴ - 2⁷ . Может ли в искомом множестве не быть слов длины 7?

Подсказка 6

Нет, не может. Пусть так же в языке есть k слов длины не больше 6. Докажите, что тогда количество не превосходит 2¹⁴ - 2⁷ - k.

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

Если все последовательности, количество букв в которых не меньше $7$ и не больше $13,$ являются словами, то, очевидно, условие задачи соблюдается; при этом количество таких слов равно $7 13 14 7 2 +...+2 = 2 − 2 .$ Осталось показать, что это количество — наибольшее возможное.

Общее количество последовательностей длины, не превосходящей $13,$ равно $2 13 14 2+2 + ...+ 2 =2 − 2.$ Если среди слов в языке нет ни одного $7$ -буквенного, то общее количество слов не превосходит $14 7 14 7 2 − 2− 2 <2 − 2.$ Пусть, напротив, в языке существует $7$ -буквенное слово $s.$ Тогда для каждого слова $t,$ состоящего из $6$ или менее букв, последовательность букв $st$ не может являться словом, и все последовательности вида $st,$ очевидно, различны. Значит, если в языке есть $k$ слов из $6$ или менее букв, то количество слов из хотя бы $7$ букв не превосходит $(7 13) 14 7 2 + ...+ 2 − k= 2 − 2 − k.$ Значит, общее количество слов не превосходит $(14 7 ) 14 7 k+ 2 − 2 − k =2 − 2,$ что и требовалось доказать.

Ответ:

$214− 27 =16056$

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

Задача 19#81750

Натуральные числа $a,b$ и $c,$ где $c≥2,$ таковы, что $1+ 1 = 1. a b c$ Докажите, что хотя бы одно из чисел $a+c, b+ c$ – составное.

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

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

Достаточно показать, что хотя бы одно из двух чисел $d = (a,c) a$ и $d = (b,c) b$ больше $1.$ Действительно, если, например, $d > 1, a$ то $a+ c$ делится на $da$ и $a+c >$ $da,$ значит, $a+ c$ – составное число. Из условия следует, что $c(a +b)= ab;$ значит, $ab$ делится на $c.$ Но тогда, если $da = db =1,$ то и $c= 1,$ что противоречит условию.

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

Задача 20#96366

Ненулевые числа $a,$ $b,$ $c$ таковы, что $ax2+ bx +c> cx$ при любом $x.$ Докажите, что $cx2− bx+ a> cx − b$ при любом $x.$

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

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

Подсказка 1

Посмотрите на выражения в неравенствах как на квадратные трëхчлены относительно x.

Подсказка 2

Осталось вспомнить, в каких случаях квадратный трëхчлен может целиком лежать выше оси абсцисс.

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

Если квадратный трёхчлен $ax2+ (b− c)x+ c> 0$ при всех $x,$ то это значит, что его дискриминант $(b− c)2− 4ac< 0.$ Ещё мы можем понять, что $c >0,$ подставив $x =0.$ Нас же просят доказать, что дискриминант трёхчлена $2 (b+ c) − 4c(a+ b)$ также меньше $0.$ Если заметить, что $2 2 (b+c) − 4bc= (b− c),$ то становится ясно, что второе неравенство идентично первому. Тогда получаем, что у графика трёхчлена ветви направлены вверх и его дискриминант отрицательный. Значит, неравенство верно.

Предыдущий раздел

Следующий раздел