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

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

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

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

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

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

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

Разделы подтемы Регион 11 класс

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

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

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

Даны неотрицательные числа $a,b,c,d$ такие, что $a+b+ c+ d= 8.$ Докажите, что

---a3--- ---b3-- ---c3---- ---d3--- a2+ b+c +b2+ c+ d + c2+d +a +d2+ a+ b ≥ 4.

Источники: ВСОШ, РЭ, 2022, 11.10 (см. olympiads.mccme.ru)

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

Первое решение. Заметим, что

a3 a(b+ c) a(b+ c) √b-+c- a2-+b+-c = a− a2+-b+c-≥a −2a√b+-c = a−-2--.

Здесь мы оценили знаменатель по неравенству о средних:

a2 +b+ c≥ 2a√b-+c.

Сложим полученное неравенство с тремя аналогичными. Теперь нам достаточно доказать, что

√---- √ ---- √ ---- √---- a+ b+c+ d− -a+-b− --b+c −--c+d − -d+-a≥ 4. 2 2 2 2

Поскольку

a+ b+ c+d =8,

это равносильно неравенству

√ ---- √---- √---- √ ---- --a+-b+ -b+-c+ -c+-d+ --d+a-≤ 4. 2 2 2 2

Но из неравенства между средним арифметическим и средним квадратичным мы получаем, что

√a-+-b √c+-d ∘ (√a+-b)2-+(√c+-d)2- --2-- + --2--≤ ⋅-------2------- =2,

и, аналогично,

√---- √---- -b+-c+ -d+-a-≤2. 2 2

Складывая эти два неравенства, получаем требуемое.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. По неравенству Коши-Буняковского-Шварца в форме Энгеля

---a3---- ---b3-- ---c3---- ---d3--- a2+ b+c + b2+ c+d + c2 +d+ a + d2+ a+ b ≥

2 2 2 22 ≥ --2----------2(a-+b-+-c-+2d-)-------2------. a(a + b+ c)+ b(b + c+d)+ c(c + d+ a)+ d(d + a+ b)

Таким образом, достаточно доказать, что

(a2+ b2+c2+ d2)2 ≥ 4(a3+ b3+c3+ d3+ ab+ bc+cd+ da+ 2ac+ 2bd).

Заметим, что

32= (a-+b+-c+-d)2-=ab+ bc +cd+ da+ac+ bd+ a2-+c2+ b2+-d2-≥ 2 2 2

≥ ab+bc+ cd+da+ 2ac+2bd

поэтому достаточно проверить, что

2 2 2 2 2 3 3 3 3 (a + b+ c + d) ≥ 4(a + b +c + d +32). (∗)

Сделаем замену

a= 2+ x, b =2+ y, c= 2+ z, d =2 +t.

Тогда

x +y+ z+ t=a +b+ c+ d− 8 =0,

a2 +b2+ c2 +d2 = 4⋅22+2 ⋅2(x+ y+ z+t)+ x2+y2+ z2+ t2 = 16+ x2+y2+ z2+ t2,

a3+ b3 +c3+ d3 =4 ⋅23+ 3⋅22(x+ y+ z+ t)+ 3⋅2(x2+ y2+ z2 +t2)+x3+ y3+z3+ t3.

Неравенство $(∗)$ примет вид

((x2+ y2+ z2 +t2)+16)2 ≥4 (x3+ y3+ z3 +t3+ 6(x2+ y2+z2+ t2)+ 64).

После раскрытия и сокращения остаётся доказать, что

(x2+ y2+ z2 +t2)2+ 8(x2 +y2+ z2+t2)≥4(x3+ y3 +z3+ t3).

Остаётся заметить, что

(x2+ y2+ z2+t2)2+ 8(x2 +y2+ z2+t2)≥ x4 +y4+ z4+t4+ 4x2 +4y2+ 4z2+ 4t2 ≥4(x3+ y3 +z3+ t3).

Первое неравенство получается раскрытием скобок: после сокращения в левой его части остаются лишь неотрицательные слагаемые. Второе получается сложением четырёх неравенств о средних вида $4 2 3 x + 4x ≥ 4x.$

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

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

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

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

На доску записали три рациональных положительных числа. Каждую минуту числа на доске $x,y,z$ стираются, а вместо них выписываются числа $1- -1 1- x + yz,y+ zx,z+ xy.$ Докажите, что начиная с некоторого момента на доске не будет появляться целых чисел.

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

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

Заметим сразу, что все числа, появляющиеся на доске, положительны и рациональны. Пусть $x ,y ,z n n n$ — числа на доске после $n$ минут, а $a =x0,b= y0,c= z0$ — исходные числа.

Положим $--1--- Fn =1+ xnynzn .$ Тогда $xn+1 =xnFn,yn+1 = ynFn$ и $zn+1 = znFn.$ В частности, $yn+1 yn b xn+1 = xn =...= a$ и, аналогично, $-zn+1 -c xn+1 =a.$

Положим $Pn =xnynzn,$ и пусть $Pn = pqnn$ — представление этого числа в виде несократимой дроби. Тогда $Fn = pn+pqnn,$ и потому

3 Pn+1 =PnFn3= (pn-+2qn)- pnqn

где последняя дробь также несократима (ибо $pn$ и $qn$ взаимно просты). Итак, $pn+1 = (pn +qn)3$ и $qn+1 =p2qn.$ В частности, $pn = (pn−1+qn−1)3 ≥(1+ 1)3 =8$ при $n≥ 1,$ и потому $qn ≥ 82qn−1 > qn−1$ при $n ≥ 2.$ Иными словами, последовательность $q1,q2,q3,...$ строго возрастает.

Обозначим через $D$ произведение всех числителей и знаменателей чисел $a,b$ и $c.$ Тогда при некотором $N$ имеем $qN >D2.$

Докажем, что с $N$ -й минуты все числа на доске нецелые. Действительно, пусть, скажем, $xn$ — целое при $n> N.$ Тогда $y = x ⋅-b,z = x ⋅ c, n n a x n a$ и потому

∏ 3 bc n = xn⋅a2

Знаменатель этого числа в несократимой записи делит $D2;$ но это невозможно, ибо $qn >qN >D2.$ Противоречие.

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

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

Многочлен $P(x)∈ℝ[x]$ имеет степень $105$ , а его старший коэффициент равен $1.$ Найдите наименьшую возможную степень многочлена

1000 1000 R(x)= P(x +1)− P(x)

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

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

Подсказка 1

Пусть n = 1000 и k = 100. Тогда рассматривается многочлен P степени nk. Для начала попробуем показать, что существует только один многочлен P со старшим коэффициентом 1, для которого степень многочлена R будет меньше, чем nk(n-1). Как это можно сделать?

Подсказка 2

Для начала запишем P(x) в виде суммы степеней x с nk + 1 коэффициентом (старший равен 1). Обозначим первый из многочленов в выражении R через F(x), а второй G(x). Можно ли понять, в членах какой степени участвует конкретный коэффициент многочлена F(x)?

Подсказка 3

Верно! В членах степени, не превосходящей n(nk-j), для j-го коэффициента. Тогда коэффициенты для достаточно больших степеней членов в F(x) зависят далеко не от всех коэффициентов многочлена P. От каких зависят?

Подсказка 4

Точно! Коэффициенты при степени члена, равной n²k - i, зависят только от коэффициентов P при степени j для j ≤ i/n < i. В многочлене G при этой же степени есть коэффициент np + A, причем A зависит только от коэффициентов при степенях, меньших i, а p — коэффициент P при степени i. Как тогда уменьшить степени разности F(x) - G(x)?

Подсказка 5

Конечно, коэффициенты при одинаковых степенях нужно сделать равными. Очевидно, что, благодаря этим равенствам, коэффициенты P можно определить однозначно. Как теперь предъявить многочлен P такой, что степень R окажется меньше nk(n-1)?

Подсказка 6

Попробуем положить P(x) равным k-ой степени многочлена, равного сумме n-ой степени x и 1. Почему он подходит?

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

Первое решение. Обозначим $n= 1000,k= 100,$ то есть степени рассматриваемых многочленов $P$ равны $nk.$

Лемма. Существует единственный многочлен $P$ степени $nk$ (со старшим коэффициентам $1$ ) такой, что степень полученного многочлена $R$ будет меньше, чем $nk(n− 1).$

Доказательство. Запишем наш многочлен как

nk nk− 1 nk−2 P(x)= x +p1x +p2x +...+pnk

Обозначим $F (x)= P(xn+ 1)$ и $G (x)= P(x)n;$ это — многочлены степени $n2k$ со старшим коэффициентом $1.$

В многочлене $F(x)$ коэффициент $p j$ участвует лишь в членах степени, не большей $n(nk − j).$ Значит, для любого $i=1,2,...,nk$ коэффициент при $n2k−i x$ в многочлене $F(x)$ зависит лишь от коэффициентов $pj$ при $j ≤ i∕n < i.$ С другой стороны, коэффициент при этой же степени в $G(x)$ есть $npi+ A,$ где $A$ зависит лишь от коэффициентов $pj$ при $j <i.$ Если мы хотим, чтобы степень $R$ была меньше, чем $nk(n − 1),$ то эти коэффициенты должны быть равны; это равенство даёт однозначное выражение $pi$ через $p1,p2,...,pi−1$ (в частности, $p1$ находится единственным образом). Значит, из этих равенств по очереди находятся все коэффициенты многочлена $P (x).$

Теперь достаточно предъявить многочлен $P (x)$ такой, что степень $R$ окажется меньше, чем $nk(n − 1)$ — по лемме, он единственный, и он и даст минимальную степень $R.$ Положим $n k P(x) =(x + 1).$ Тогда многочлен

n n k n nk R(x)=((x + 1) + 1) − (x + 1) = = k⋅(xn +1)n(k−1)+C2k (xn+ 1)n(k−2)+...

имеет степень всего лишь $n2(k− 1)< nk(n− 1).$ Значит, наименьшая возможная степень $R$ и есть $n2(k− 1)=99⋅106.$

______________________________________________________________________________________________________________________________________________________

Второе решение. Используем те же обозначение $n$ и $k,$ что и в первом решении. Мы будем считать, что

degR <n2k− nk (∗)

(впоследствии мы увидим, что это возможно; поэтому для многочлена $R$ минимальной степени так считать можно).

Предположим, что в многочлене $P (x)$ есть одночлен степени, не кратной $n;$ пусть $s asx$ — такой одночлен наибольшей степени. Тогда коэффициент многочлена $R$ при $xnk(n−1)+s$ равен $− nas,$ что противоречит неравенству.

Таким образом, в предположении, степени всех одночленов в $P(x)$ кратны $n;$ иначе говоря, существует такой многочлен $Q,$ что $P (x)= Q(xn).$ Тогда

R(x)= P(xn+ 1)− P(x)n = Q((xn +1)n)− Q (xn)n

то есть $R (x)= R1(xn),$ где

R1(y)= Q ((y+ 1)n)− Q(y)n

при этом $degQ= k< n,$ а предположение $(∗)$ означает, что $degR1 < nk− k.$

Рассмотрим многочлен $n n R2(x)= R1(x− 1)= Q(x )− Q (x − 1) ,$ тогда $degR2 =degR1.$ Аналогично рассуждению выше, предположим, что $Q (x− 1)⁄= xk,$ то есть в многочлене $Q (x − 1)$ есть одночлены, кроме $xk;$ пусть $btxt$ — такой одночлен наибольшей степени. Тогда в многочлене $R2(x)$ есть одночлен $− nbtxnk−k+t,$ что противоречит неравенству $deg R2 < nk− k.$ Таким образом, $Q(x− 1)= xk,$ а тогда $Q (x)= (x +1)k$ и $P(x) =$ $= (xn+ 1)k.$ Мы приходим к тому же примеру, что и в первом решении (и видим, что в этом случае степень $R$ действительно удовлетворяет (*)).

Ответ:

$99⋅106$

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

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

Пусть $I$ — центр вписанной окружности остроугольного треугольника $ABC, M$ и $N$ — точки касания вписанной окружности сторон $AB$ и $BC$ соответственно. Через точку $I$ проведена прямая $ℓ,$ параллельная стороне $AC,$ и на неё опущены перпендикуляры $AP$ и $CQ.$ Докажите, что точки $M,N,P$ и $Q$ лежат на одной окружности.

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

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

Подсказка 1

Давайте посмотрим на рисунок и поймëм, что у нас не особо много способов, через которые можно доказать, что PMNQ вписанный. Единственный способ - доказать, что сумма противолежащих углов равна 180 градусов.

Подсказка 2

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

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

$PIC$

Пусть углы $BAC$ и $BCA$ треугольника $ABC$ равны, соответственно $2α$ и $2γ.$ Углы $AP I$ и $AMI$ — прямые, поэтому точки $A,P,M,I$ лежат на одной окружности с диаметром $AI.$ Тогда $∠AMP = ∠AIP =$ (в силу параллельности) $= ∠IAC =α.$ Аналогично $∠QNC = γ.$ Из равнобедренного треугольника $MBN$ находим: $∠BMN = 180∘−-∠M2BN--= α+ γ.$ Тогда $∠P MN = ∠PMA +(180∘− ∠BMN )=180∘− γ.$ Но $∠P QN =∠ICN = γ,$ значит, сумма углов $PMN$ и $PQN$ равна $180∘,$ то есть точки $M, N,P$ и $Q$ лежат на одной окружности.

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

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

На оси $Ox$ отметили точки $0,1,2,...,100$ и нарисовали графики $200$ различных квадратичных функций, каждый из которых проходит через две из отмеченных точек и касается прямой $y = −1.$ Для каждой пары графиков Олег написал на доске число, равное количеству общих точек этих графиков. После чего он сложил все $19900$ чисел, написанных на доске. Мог ли он получить число $39699?$

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

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

Подсказка 1

Почти всегда две параболы пересекаются в 2 точках. Но при каких условиях параболы имеют ровно одну точку пересечения?

Подсказка 2

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

Подсказка 3

Оцените количество многочленов, имеющие общую ось симметрии, а также имеющие одинаковые расстояния между корнями. В первом случае просто посчитайте, сколько у вас может быть различных осей. Во втором же предположим, что x_i - количество многочленов с расстоянием между корнями, равным i.

Подсказка 4

Если у вас получилась оценка на 39699, то вспомним, что x_100 не более 1.

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

Каждому из наших $200$ многочленов соответствует две целых точки $a$ и $b$ на оси $Ox.$ Не умаляя общности будем считать, что $a< b.$ Назовем шириной многочлена $f$ натуральное число $b− a,$ а осью многочлена — $a+b- 2 .$

Пусть многочлен $f$ имеет ширину $w > 0$ и ось $c,$ тогда он записывается в виде $-4 2 f(x)= w2(x− c)− 1.$

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

Действительно, $4- 2 -4 2 w21(x − c1) − 1= w22(x− c2) − 1$ равносильно $(x− c1)w2 = ±(x− c2)w1.$ Если $w1 ⁄= w2,$ то каждое из двух линейных уравнений имеет корни, и они совпадают только если $c1 =c2.$ Если же $w1 = w2,$ то $c1 ⁄=c2$ (трехчлены разные) и одно из двух линейных уравнений корней не имеет, а второе имеет.

Заметим, что ширина многочлена может принимать значение от 1 до 100, при этом найдется не более одного многочлена с шириной $100.$ Обозначим $xi$ количество многочленов с шириной $i.$ Оценим количество пар многочленов с одинаковой шириной:

100 100 ∑ xi(xi−-1)= ∑ (x2i −-4xi+4)+-3xi−-4= i=1 2 i=1 2

100 2 =∑ (xi− 2)-+ 3⋅200− 4-⋅100≥ 1+ 100 i=1 2 2

В последнем неравенстве мы воспользовались следующим соображением: так как сумма ста чисел $xi$ равна 200 и $x100 ⁄= 2,$ то найдется еще хотя бы одно $xi ⁄= 2,$ следовательно, $∑100 2 i=1(xi− 2) ≥ 2.$

Осью многочлена может быть любое целое или полуцелое число от $1 2$ до $1 992,$ таких чисел $199,$ следовательно, найдется как минимум одна пара многочленов с общей осью. Это будет ранее не учтенная пара, так как трехчлены с общими шириной и осью совпадают. Чтобы найти количество точек пересечения графиков надо из удвоенного количества пар многочленов вычесть количество пар с одинаковой шириной или осью. Таким образом, точек пересечения не более, чем $200⋅199 2⋅--2-- − 101− 1= 39698,$ что меньше, чем $39699.$

Ответ:

не мог

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

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

В алфавите $n> 1$ букв; словом является каждая конечная последовательность букв, в которой любые две соседние буквы различны. Слово называется хорошим, если из него нельзя вычеркнуть все буквы, кроме четырех, так, чтобы осталась последовательность вида $aabb,$ где $a$ и $b$ — различные буквы. Найдите наибольшее возможное количество букв в хорошем слове.

Источники: ВСОШ, РЭ, 2021, 9.9 и 11.8 (см. olympiads.mccme.ru)

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

Первое решение. Назовём длиной слова количество букв в нём. Пусть $a ,a ,...,a 1 2 n$ — буквы алфавита. Тогда нетрудно проверить, что хорошим является слово

anan−1...a2a1a2a1a2a3...an.

Осталось показать, что нет хороших слов большей длины.

Предположим, что в $n$ -буквенном алфавите существует хорошее слово длины $2n+ 2.$ Тогда какая-то буква (скажем, $a ) 1$ встречается в нём хотя бы три раза. Отметим её второе $(V)$ и предпоследнее $(P)$ вхождение в слово (тогда $V$ стоит не правее, чем $P ).$

Любая другая буква встречается не более одного раза перед $P,$ а также не более одного раза после $V,$ иначе вычёркиванием можно получить запрещённую последовательность. Значит, каждая из букв $a2,...,an$ встречается не более двух раз. Более того, если такая буква и встречается дважды, то одно из её вхождений стоит до $V,$ а другое — после $P.$

Пусть $a1$ встречается $k≥ 3$ раз. Тогда между $V$ и $P$ стоят хотя бы $k − 3$ буквы, отличных от $a1$ (по одной между соседними вхождениями $a1),$ и все такие буквы встречаются ровно по разу. Выделим $k − 3$ таких буквы. Остальные $n− k+ 2$ буквы могут встречаться максимум по два раза. Поэтому длина слова не превосходит

k+ (k− 3)⋅1+ (n − k +2)⋅2= 2n+ 1,

что противоречит нашему предположению.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Приведём другое доказательство того, что длина хорошего слова не превосходит $2n+1.$ Индукция по $n ≥2.$ В базовом случае $n= 2$ буквы в слове чередуются, и слово длины хотя бы $6$ содержит фрагмент вида $ababab,$ из которого вычёркиванием букв можно получить $aabb.$ Для перехода предположим, что в $n$ -буквенном алфавите есть хорошее слово длины, не меньшей $2n+ 2.$ Тогда какая-то буква $a$ встречается в этом слове хотя бы три раза. Предположим, что букв, встречающихся хотя бы $3$ раза, две — $a$ и $b.$ Пусть, без ограничения общности, второе вхождение $a$ стоит раньше второго вхождения $b;$ тогда вычёркиванием букв можно получить слово $aabb,$ что невозможно. Значит, буква $a$ встречается в слове $k≥3$ раз, а все остальные — максимум по два раза. Тогда длина слова не меньше, чем $2n+ 2,$ и не больше, чем $k+ 2(n − 1),$ откуда $k ≥4.$ Между вторым и третьим вхождением буквы $a$ есть какая-то буква $c.$ Эта буква не может встречаться в других местах: если она встречается после второго вхождения $a,$ то вычёркиванием букв можно получить $aacc,$ а если до него — то $ccau$ (поскольку $k ≥4).$ Пусть соседи буквы $c$ различны. Тогда, удалив её из слова, мы получим хорошее слово в $(n− 1)$ -буквенном алфавите (без буквы $c).$ Длина этого слова будет не меньше $2n+ 1= 2(n − 1)+ 3,$ что противоречит индукционному предположению. Если же соседи буквы $c$ одинаковы, удалим из слова $c$ и букву перед ней; тогда на этом «стыке» останутся различные буквы. Поэтому мы опять получим хорошее слово в $(n− 1)$ -буквенном алфавите, длина которого не меньше, чем $2(n− 1)+2;$ это опять же невозможно по индукционному предположению.

Ответ:

$2n+ 1$

Курсы

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

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

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

Натуральное число, большее 1000000, даёт одинаковые остатки при делении на 40 и на 625. Какая цифра может стоять у этого числа в разряде тысяч?

Источники: ВСОШ, РЭ, 2021, 11.1 (см. olympiads.mccme.ru)

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

Пусть $n$ — данное число, $t$ — его остаток от деления на $40$ и от деления на $625.$ Тогда число $n− t$ делится на $40$ и на $625,$ то есть делится на

(40;625)= 5000.

Значит, разность $n− t$ оканчивается либо на $5000,$ либо на $0000.$ А остаток $t<40.$ Поэтому цифра в разряде тысяч может быть $0$ или $5.$ Обе ситуации возможны, такие цифры имеют, например числа $20210000$ и $20215000$ (оба этих числа имеют остатки $0$ при делении на $40$ и на $625$ ).

Ответ:

0 или 5

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

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

Ненулевые числа $x$ и $y$ удовлетворяют неравенствам $x4− y4 > x$ и $y4− x4 > y.$ Какой знак может иметь произведение $xy$ (укажите все возможности)?

Источники: ВСОШ, РЭ, 2021, 11.2 (см. olympiads.mccme.ru)

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

Первое решение. Сложив данные неравенства, мы получим: $x+ y < 0.$ Преобразуем данные неравенства к виду:

4 4 x − x> y

4 4 y − y > x

и перемножим (это можно делать, так как их правые части положительны). Имеем:

xy(1− x3− y3)>0.

Так как $x< −y,$ то $x3 < −y3,$ то есть $x3+ y3 < 0.$ Поэтому

1− x3− y3 > 1>0.

Значит, $xy$ — положительно.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Докажем, что $xy >0.$ Предположим противное:

xy < 0

( $xy ⁄= 0$ по условию). Не умоляя общности, $x> 0,$ $y < 0.$ Сложив данные неравенства, получим $x+y <0,$ т.е. $0< x< −y.$ Следовательно, $x4 < y4.$ Но тогда $x< x4− y4 < 0$ — противоречие.

Ответ:

знак плюс

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

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

В Цветочном городе живёт $992$ коротышек. Некоторые из коротышек рыцари (всегда говорят правду), а остальные — лжецы (всегда лгут). Дома в городе расположены в клетках квадрата $99× 99$ (всего $2 99$ домов, расположенных в $99$ вертикальных и в $99$ горизонтальных улицах). В каждом доме живет ровно один коротышка. Номер дома обозначается парой чисел $(x;y),$ где $1≤ x≤ 99$ — номер вертикальной улицы (номера возрастают слева направо), а $1≤ y ≤ 99$ — номер горизонтальной улицы (номера возрастают снизу вверх). Цветочным расстоянием между двумя домами с номерами $(x1;y1)$ и $(x2;y2)$ называется число $ρ =|x1− x2|+ |y1− y2|.$ Известно, что на каждой улице — вертикальной или горизонтальной — проживает не менее $k$ рыцарей. Кроме того, все коротышки знают, в каком доме живет рыцарь Знайка. Вы хотите найти его дом, но не знаете, как выглядит Знайка. Вы можете подходить к любому дому и спрашивать живущего в нем коротышку: «Каково цветочное расстояние от вашего дома до дома Знайки?». При каком наименьшем $k$ вы можете гарантированно найти дом Знайки?

Источники: ВСОШ, РЭ, 2021, 11.5 (см. olympiads.mccme.ru)

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

Пример. Покажем, что если $k= 74,$ то мы не сможем гарантированно найти дом Знайки. Разместим Знайку и лжеца Незнайку в дома с номерами $(50;49)$ и $(49;50)$ соответственно. Покажем, что может оказаться так, что по ответам жителей нельзя однозначно определить, в каком из этих двух домов живёт Знайка.

В нижний левый квадрат $49× 49$ поселим рыцарей. Их расстояния до Знайки и Незнайки одинаковые. В верхний правый квадрат $50× 50$ тоже поселим рыцарей, их расстояния тоже одинаковы. В нижний правый прямоугольник (из $49$ строк и $50$ столбцов) поселим рыцарей так, чтобы в каждой строке было ровно $25$ рыцарей и $25$ лжецов, а в каждом столбце хотя бы $24$ рыцаря и $24$ лжеца. В верхний левый прямоугольник поселим коротышек диагонально-симметрично правому верхнему, причём рыцарей и лжецов поменяем местами. В нём в каждом столбце будет по $25$ рыцарей и $25$ лжецов, а в каждой строке хотя бы $24$ рыцаря и $24$ лжеца. Для каждого коротышки из этих прямоугольников расстояния до Знайки и Незнайки разные. Пусть все лжецы в них говорят расстояние не до Знайки, а до Незнайки. Тогда при замене местами рыцарей и лжецов в этих прямоугольниках (в частности, при замене местами Знайки и Незнайки) все будут говорить то же самое, но Знайка будет жить в другом доме.

Оценка. Покажем, что если $k≥ 75,$ то мы сможем гарантированно найти дом Знайки. Пусть есть два подозрительных дома с номерами $(x;y)$ и $(u;v).$ Можно считать, что $x ≤u,$ $y ≤ v,$ т.к. можно повернуть квадрат требуемым образом. Так как оба неравенства одновременно не могут быть равенствами, без ограничения общности будем считать, что $y <v.$ Рассмотрим столбцы $(x,...)$ и $(u,...)$ (возможно, это один и тот же столбец).

Если $u− x> v− y$ или $(u − x)+ (v − y)$ — нечётно, то в этих столбцах нет ни одного коротышки, расстояния от которого до двух выделенных домов одинаковы.

Если $x= u,$ а $v− y$ чётно, то в столбце $(x,...)$ находится один коротышка, расстояния от которого до двух домов одинаковы.

Если $u− x< v− y,$ а $(u− x)+(v− y)$ чётно, то в столбцах $(x,...)$ и $(u,...)$ находятся по одному коротышке, расстояния от которого до двух домов одинаковы.

Если же $u − x =v− y,$ то в столбце $(x,...)$ места, от которых расстояния до $(x;y)$ и $(u;v)$ одинаковы, имеют вид $(x;V),$ где $V ≥ v,$ и таких мест ровно $100 − v.$ Аналогично, в столбце $(u,...)$ места, от которых расстояния до $(x;y)$ и $(u;v)$ одинаковы, имеют вид $(u;Y),$ где $Y ≤y,$ и таких мест ровно $y.$

Заметим, что

y+ (100− v) ≤99.

Значит, какое-то из чисел $y,100− v$ не больше $49.$

Таким образом, во всех случаях найдется столбец, в котором не более $49$ рыцарей указывают на оба места, при этом на неправильное место указывают не более, чем эти рыцари и все лжецы (их не больше $99− 75= 24$ ), т.е. не более, чем $49 +24= 73$ коротышек. В то же время, на правильное место в любом столбце указывают хотя бы все рыцари, т.е. не менее $75$ коротышек. Таким образом, из двух подозрительных мест всегда можно исключить одно (т.к. строка или столбец, на который мы ориентируемся, зависит только от положения мест, а не от расположения рыцарей/лжецов). Значит, всегда можно найти единственное правильное место.

Ответ:

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

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

На доске написаны функции: $x+1,x2+ 1,x3+ 1,x4+ 1.$ Разрешается дописывать на доску новые функции, получаемые из написанных на доске с помощью операций вычитания и умножения. Покажите, как получить ненулевую функцию, которая при положительных значениях аргумента принимает неотрицательные значения, а при отрицательных значениях аргумента — неположительные значения.

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

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

Например, подходит $(x4+1)(x+1)− (x4 +1)= x(x4+ 1).$

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

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

Известно, что для некоторых $x$ и $y$ суммы $sinx+ cosy$ и $sin y+cosx$ — положительные рациональные числа. Докажите, что найдутся такие натуральные числа $m$ и $n,$ что $m sinx +n cosx$ — натуральное число.

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

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

Пусть $sinx+ cosy = a$ и $sin y+cosx= b.$ Тогда $cosy =a − sin x$ и $siny = b− cosx.$ Возведём эти равенства в квадрат и сложим их. Тогда в силу основного тригонометрического тождества получим: $2 2 1= a +b − 2a sinx− 2bcosx+ 1,$ то есть $2 2 2asinx +2bcosx= a +b .$ Пусть $N$ — НОК знаменателей чисел $a$ и $b;$ тогда, умножив полученное равенство на $2 N ,$ получим требуемое.

Интенсивы

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

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

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

Известно, что каждый из трёхчленов $x2 +ax+ b$ и $x2+ax+ b+ 1$ имеет хотя бы по одному корню, и все корни этих трёхчленов целые. Докажите, что трёхчлен $2 x + ax+ b+2$ корней не имеет.

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

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

Подсказка 1

Если корни целые, то что можно сказать по теореме Виета? Верно, что коэффициенты также целые. А что можно сказать про дискриминант, если корни являются целыми?

Подсказка 2

Что он точный квадрат! Ну тогда пусть дискриминант первого - n^2, тогда, если дискриминант второго - m^2, то m^2 - n^2 = 4. А при каких натуральных m и n такое может быть?
(то, что они целые - понятно, а натуральными мы их можем взять, так как даже если целые, то мы их в формуле корней отберем)

Подсказка 3

Верно, только при n = 0, m = 2. Теперь явно запишем первый дискриминант через a и b. a^2 - 4b = 4. А чему равен тогда дискриминант третьего трехчлена?

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

Понятно, что $a$ и $b$ целые, так как выражаются через целые корни по теореме Виета. Для того, чтобы квадратный трёхчлен с целыми коэффициентами имел целые корни, необходимо, чтобы его дискриминант был точным квадратом. Таким образом, $2 2 2 2 a − 4b= m ,a − 4b− 4= n,$ откуда $2 2 m − n = 4,$ то есть $(m − n)(m +n) =4.$ Последнее равенство равносильно двум случаям $m − n= 1$ и $m+ n= 4,m − n =2$ и $m + n= 2.$ Первый случай целых решений не даёт, а второй — $n = 0,m = 2.$ Таким образом, $2 a − 4b= 4.$ Заметим, что дискриминант трёхчлена $2 x + ax+b+ 2$ равен $2 a − 4b− 8 =− 4<0,$ а значит он действительно не имеет корней, что и требовалось.

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

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

В классе $m$ учеников. В течение сентября каждый из них несколько раз ходил в бассейн; никто не ходил дважды в один день. Первого октября выяснилось, что все количества посещений бассейна у учеников различны. Более того, для любых двух из них обязательно был день, когда первый из них был в бассейне, а второй — нет, и день, когда, наоборот, второй из них был в бассейне, а первый — нет. Найдите наибольшее возможное значение $m.$ В сентябре $30$ дней.

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

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

Подсказка 1

Переформулируем задачу на языке теории множеств: у нас есть m подмножеств 30-элементного множества, причём все разного размера, и никакие не вложены друг в друга.

Подсказка 2

Очевидно, 30-элементного подмножества быть не может. Также одновременно не может быть 29-элементного и 1-элементного подмножества при наличии ещё каких-то. Это позволяет доказать, что m не может быть слишком большим.

Подсказка 3

Тогда будем строить пример для m=28 по индукции, добавляя по 2 элемента в множество. Одно новое подмножество можно сделать большим, а другое маленьким.

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

Для каждого натурального $n$ обозначим $X ={1,2,...,n}. n$ Каждому ученику сопоставим множество всех дней, когда он ходил в бассейн (это будет подмножество в $X30$ ). Итого, мы получили набор из $m$ (согласно условию, непустых) подмножеств в $X30.$ Условие равносильно тому, что во всех подмножествах разные количества элементов, и ни одно из них не содержится в другом; назовём такой набор подмножеств хорошим. Таким образом, нам нужно найти максимальное число множеств в хорошем семействе подмножеств в $X30.$

Докажем сначала, что такой набор не может содержать больше $28$ множеств. Это очевидно, если в наборе есть $30$ -элементное подмножество, так как оно содержит любое другое. Значит, можно считать, что множества в наборе могут состоять лишь из $1,2,...,29$ элементов (и их не больше $29$ ). Пусть в хорошем наборе есть $29$ -элементное множество $A$ и $1$ -элементное множество $B.$ Так как $B$ не содержится в $A,$ они не пересекаются. Тогда любое другое подмножество в $X30$ либо содержит $B,$ либо содержится в $A.$ Значит, в этом случае хороший набор состоит лишь из двух подмножеств. Наконец, если в наборе нет $1$ или $29$ -элементного подмножества, то в нём уже не более $28$ множеств, что и требовалось.

Осталось предъявить пример хорошего набора из $28$ подмножеств в $X30.$ Для этого покажем индукцией по $k ≥2,$ что существует хороший набор $A1,A2,...,A2k−2$ подмножеств в $X2k,$ причём $Ai$ содержит $i+ 1$ элемент. В базовом случае $k = 2$ годятся подмножества $A1 = {1,2}$ и $A2 = {1,3,4}.$

Пусть для некоторого $k$ уже построен требуемый хороший набор $B1,...,B2k−2$ подмножеств в $X2k.$ Тогда требуемый хороший набор подмножеств в $X2k+2$ можно построить так. Положим $Ai+1 =Bi ∪{2k+ 2}$ при $i= 1,2,...,2k − 2;$ эти множества содержат $3,4,...,2k$ элементов соответственно. Наконец, положим $A1 = {2k+ 1,2k+ 2}$ и $A2k ={1,2,...,2k+ 1}.$ Нетрудно проверить, что они образуют требуемый хороший набор. Тем самым переход индукции доказан.

Ответ:

$m = 28$

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

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

Назовём расстоянием между двумя клетками клетчатой доски наименьшее количество ходов, за которое шахматный король может добраться от одной из них до другой. Найдите наибольшее количество клеток, которое можно отметить на доске $100× 100$ так, чтобы среди них не нашлось двух клеток, расстояние между которыми равно $15.$

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

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

Разобьём доску на $9$ квадратов $30× 30,6$ прямоугольников $10×30$ и один квадрат $10× 10$ (см. рис. слева). В каждом квадрате $30× 30$ клетки разбиваются на $2 15$ четвёрок так, что расстояние между любыми клетками в одной четвёрке равно $15$ (каждая четвёрка состоит из клеток с координатами $(a,b),(a,b+ 15),(a +15,b),(a +15,b+15)$ ). Тогда в любой четвёрке может быть отмечено не более одной клетки, то есть общее число отмеченных клеток в таком квадрате не превосходит $2 15.$

$PIC$

Аналогично, каждый прямоугольник $10×30$ (скажем, с длинной горизонтальной стороной) разбивается на пары клеток, отстоящих друг от друга на $15$ (с координатами $(a,b)$ и $(a+15,b)$ ) — поэтому в нём не более $15⋅10$ отмеченных клеток. Наконец, в квадрате $10× 10$ всего $102$ клеток. Итого, отмеченных клеток не больше, чем $9⋅152+ 6⋅15⋅10+102 = (3 ⋅15+ 10)2 =552.$

Пример с таким количеством отмеченных клеток показан на рис. справа.

Ответ:

$552 = 3025$ клеток

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

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

В каждую клетку таблицы $1001× 1001$ поставили $0$ или $1.$ Оказалось, что в любом столбце нулей больше, чем единиц. Обязательно ли найдутся два столбца таких, что число строк, в пересечениях которых с этими двумя столбцами стоят только нули, больше числа строк, в пересечениях которых с этими двумя столбцами стоят только единицы?

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

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

Покажем, что требуемому условию удовлетворяют любые два столбца таблицы. Выкинем из таблицы все столбцы, кроме двух рассматриваемых. Общее число нулей в этих столбцах больше общего числа единиц; это значит, что нулей в них не меньше $1002.$ Если в полученной таблице $k$ строк с двумя нулями, то есть ещё хотя бы $1002 − 2k$ строк с одним нулём — и, следовательно, не более $1001− k− (1002− 2k)= k− 1$ столбцов с двумя единицами. Осталось заметить, что $k− 1< k.$

Ответ:

Да

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

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

Внутри выпуклого пятиугольника отметили точку и соединили её со всеми вершинами. Какое наибольшее число из десяти проведенных отрезков (пяти сторон и пяти отрезков, соединяющих отмеченную точку с вершинами пятиугольника) может иметь длину $1?$

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

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

$PIC$

Сначала докажем, что все $10$ отрезков не могут иметь длину $1.$ Предположим противное. Пусть $ABCDE$ — пятиугольник, $O$ — точка внутри него, и все $10$ проведенных отрезков имеют длину $1$ (см. рис. выше). Тогда треугольники $OAB, OBC,OCD, ODE$ и $OEA$ — правильные, поэтому $∠AOB = ∠BOC = ∠COD = ∠DOE = ∠AOE = 60∘.$ Сумма же этих углов должна быть равна $360∘,$ однако $5⋅60∘ = 300∘$ — противоречие.

$PIC$

Осталось привести пример, когда $9$ отрезков имеют длину $1$ (см. рис. выше). Отметим на плоскости точки $A$ и $O$ на расстоянии $1.$ выберем последовательно точки $B,C,D$ и $E$ так, чтобы треугольники $AOB, BOC,COD$ и $DOE$ были равносторонними. Тогда точка $O$ лежит внутри пятиугольника $ABCDE,$ и из $10$ проведенных отрезков все, кроме $AE,$ имеют длину $1.$

Ответ:

$9$ отрезков

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

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

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

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

Функция $f(x),$ заданная на всей числовой оси, при всех действительных $x$ и $y$ удовлетворяет условию

x-+y x−-y f(x)+ f(y)= 2f( 2 )f( 2 )

Верно ли, что функция $f(x)$ обязательно чётная?

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

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

Подставим в данное равенство $− y$ вместо $y.$ Получим

x−-y x-+y f(x)+ f(−y)=2f( 2 )f( 2 )

Итак, $f(x)+f(y)= f(x)+ f(− y),$ откуда для всех действительных $y$ получим $f(y)=f(−y).$ Это и означает, что функция $f(x)$ чётная.

Ответ:

Верно

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

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

Дан неравнобедренный треугольник $ABC,$ в котором $∠B = 135∘.$ Пусть $M$ — середина отрезка $AC.$ Точка $O$ — центр окружности $Ω,$ описанной около треугольника $ABC.$ Луч $BM$ вторично пересекает окружность $Ω$ в точке $D.$ Докажите, что центр окружности $Γ ,$ описанной около треугольника $BOD,$ лежит на прямой $AC.$

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

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

Так как $∠ABC = 135∘,$ то $∠AOC =90∘.$ Так как $OM$ — медиана в прямоугольном треугольнике $AOC,$ имеем $OM = AM = MC.$ На продолжении отрезка $OM$ за точку $M$ отметим точку $E$ так, что $OM =ME.$ Поскольку четырёхугольник $ABCD$ вписанный,

BM ⋅MD = AM ⋅MC = OM ⋅ME.

Следовательно, точка $E$ лежит на окружности $Γ .$

$PIC$

Точка $O$ лежит на серединном перпендикуляре к отрезку $AC,$ поэтому $AC ⊥ OM.$ Значит, прямая $AC$ является серединным перпендикуляром к отрезку $OE.$ Поскольку отрезок $OE$ является хордой окружности $Γ ,$ её центр лежит на прямой $AC.$

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

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

В пространстве расположены $2016$ сфер, никакие две из них не совпадают. Некоторые из сфер — красного цвета, а остальные зеленого. Каждую точку касания красной и зеленой сферы покрасили в синий цвет. Найдите наибольшее возможное количество синих точек.

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

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

Подсказка 1

Оценка в этой задаче делается совсем не сложным образом. Вам нужно лишь вспомнить, что две сферы могут касаться только в 1 точке. Что же делать с примером? Нужно как-то удачно расположить сферы между собой. Подумайте, как это можно сделать.

Подсказка 2

Для начала убедимся, что оценка на 1008² у нас с вами совпала. Как можно в теории получить это число? Нужно, чтобы одна сфера зелёного цвета, например, касалась остальных 1008 красных(отсюда понятно, что радиусы у них можно взять одинаковый). Тогда, учитывая все 1008 зелёных сфер, получим требуемое. Теперь подумайте в этом направлении.

Подсказка 3

Самый простой способ располагать красные сферы - это разместить их на какой-нибудь удобной окружности. Осталось только понять, как расположить зелёные сферы(и немного, технически описать радиусы всех сфер), и победа!

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

Пусть среди сфер есть $r$ красных и $2016− r$ зелёных. Так как у любых двух сфер максимум одна точка касания, количество синих точек не превосходит $2 2 2 r(2016− r) =1008 − (1008− r) ≤1008.$

Предъявим пример с таким количеством синих точек. Пусть $ℓ$ — некоторая прямая, $α$ — плоскость, перпендикулярная $ℓ$ и пересекающая её в точке $O,$ а $ω$ — окружность с центром $O$ и радиусом $1,$ лежащая в $α.$ Построим $1008$ красных сфер одинакового радиуса $r< 1$ с различными центрами $R1,R2,...,R1008,$ лежащими на $ω.$

$PIC$

Пусть $G1,G2,...,G1008$ — различные точки на $ℓ,$ удалённые от $O$ на расстояния $d1,d2,...,d1008.$ Тогда расстояние между $Gi$ и любой точкой $Rj$ равно $∘ ----- 1+ d2i.$ Значит, если мы построим зелёную сферу с центром $Gi$ и радиусом $∘ ----- 1+ d2i − r,$ она будет касаться всех красных сфер. При этом все точки касания будут попарно различными, поскольку они лежат на отрезках вида $RjGi,$ которые не имеют общих точек, кроме концов. Значит, в нашей конструкции действительно будут отмечены $10082$ синих точек.

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

Ответ:

$10082 =1016064$ точек

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

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

В зоопарк прибыли несколько пар особей, у каждой из которых от 1 до 10 детёнышей. Ветеринар выбирал одного детёныша, одну самку и самца из трёх разных семей и проводил осмотр. У него было 3630 способов выбрать нужную тройку животных. Сколько всего детёнышей могло прибыть в зоопарк?

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

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

Пусть в зоопарк было $p$ пар особей и $d$ детёнышей. Тогда каждый детёныш состоял в $(p − 1)(p− 2)$ тройках: самку можно было выбрать из одной из $p − 1$ пар особей, а после её выбора самца можно было выбрать из одной $p− 2$ оставшихся пар. Значит, общее количество троек равно

d(p− 1)(p− 2)= 3630.

Поскольку $d≤ 10p,$ получаем $3630 ≤10p3,$ то есть $p3 ≥ 363> 73.$ Значит, $p ≥8.$

Число $3630= 2⋅3⋅5⋅112$ имеет два делителя $p− 1$ и $p− 2,$ отличающиеся на $1.$ Если один из этих делителей делится на $11,$ то другой даёт остаток $1$ или $10$ при делении на $11.$ Тогда он взаимно прост с $11,$ а значит, делит $2⋅3⋅5= 30$ и при этом не меньше $10.$ Нетрудно видеть, что этим делителем может быть только $10;$ тогда $p − 2 =10,p− 1 =11 и d= 3630 :110= 33.$