Тема Высшая проба

Высшая проба - задания по годам → .09 Высшая проба 2023

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

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

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

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

Подтемы раздела высшая проба

Разделы подтемы Высшая проба - задания по годам

Высшая проба 2015 и ранее

Высшая проба 2016

Высшая проба 2017

Высшая проба 2018

Высшая проба 2019

Высшая проба 2020

Высшая проба 2021

Высшая проба 2022

Высшая проба 2023

Высшая проба 2024

Высшая проба 2025

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

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

Задача 1#67766

Каждое натуральное число покрасили в один из трёх цветов: красный, синий или зелёный, причём все 3 цвета встречаются. Может ли оказаться так, что сумма любых двух чисел разных цветов является числом оставшегося цвета?

Источники: Высшая проба - 2023, 11.1 (см. olymp.hse.ru)

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

Подсказка 1

Если ответ да, то как доказать, что такое возможно? Привести пример раскраски... Вроде как сходу такую раскраску придумать не получается. Может тогда воспользоваться методом от противного...

Подсказка 2

Пускай такая раскраска существует. Разумно было бы посмотреть на подряд идущие числа: ведь если они разного цвета, то их разность обязана быть покрашена в оставшийся цвет. А их разность это всегда 1

Подсказка 3

Возьмем числа 1 и n такие, что их цвета не совпадают. Тогда числа 1, n и n+1 покрашены в три различных цвета. Может попробовать пойти дальше и посмотреть на n+2? Какой же цвет имеет n+2=1+(n+1)? А n+3=1+(n+2)?

Подсказка 4

Получается, что n+2 имеет цвет числа n, а n+3 имеет цвет числа n+1. Похоже, что мы больше никогда не увидим число, цвет которого совпадает с цветом числа 1:( А может ли быть такое?

Подсказка 5

Такого, конечно же, не может быть: достаточно просто посмотреть на цвет числа 2n+1=n+(n+1)

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

Пойдём от противного, предположим, что такое возможно. Без ограничения общности можно считать, что число 1 покрашено в красный. Выберем произвольное число $x,$ покрашенное в синий. Заметим, что тогда $x +1$ должно быть зелёного цвета, $(x +1)+ 1= x+ 2$ — синего, $(x+ 2)+ 1= x+ 3$ — зелёного и т.д. Таким образом, все числа, большие $x,$ покрашены в синий или зелёный цвет. С другой стороны, так как $x$ покрашен в синий цвет, a $x +1$ — в зелёный, то число $(x+ 1)+x =2x+ 1$ должно быть покрашено в красный цвет, противоречие. Значит, такое невозможно.

Ответ: нет

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

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

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

Задача 2#67767

Различные действительные числа $x,y,z$ таковы, что среди трёх чисел

---x+-y--- ---y+-z-- --z-+x---- x2+ xy+ y2 , y2+ yz+z2, z2+zx+ x2

какие-то два равны. Верно ли, что все эти три числа равны?

Источники: УТЮМ - 2016 и Высшая проба - 2023, 11.2

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

Подсказка 1

Эти знаменатели подозрительно напоминают разложение разности кубов... Может, у каждой дроби умножить числитель и знаменатель на что-то и получить заветную разность?

Подсказка 2

Так и сделаем: числитель и знаменатель первой дроби умножим на x-y, второй на y-z, третьей на z-x и получим в числителях разность квадратов, а в знаменателях разность кубов. Но кажется, что это нам пока не сильно помогло...

Подсказка 3

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

Подсказка 4

Перемножив крест-накрест и раскрыв скобки мы видим какой-то ужас. Хотя, если приглядеться, полученное равенство будет симметрично относительно переменных x и y. На какую мысль это наводит?

Подсказка 5

А мысль то проста: произвести все операции в обратном порядке, поменяв при этом местами переменные x и y, и получить равенство второй и третьей дроби!

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

В данных выражениях умножим числители и знаменатели на $x− y,y− z,$ $z− x$ соответственно (согласно условию, эти разности ненулевые). Получим те же числа в другом виде:

x2− y2 y2− z2 z2− x2 x3− y3, y3−-z3, z3− x3

Без ограничения общности будем считать, что первое и третье числа равны. Тогда

2 2 2 2 x3−-y3-= z3− x3-⇔ x − y z − x

x2z3− x5− y2z3+ y2x3 = z2x3− z2y3− x5+ x2y3 ⇔

x3y2+ y3z2+ z3x2 = x3z2+ y3x2 +z3y2

Это симметричное равенство, поэтому теперь можно просто поменять местами две переменные (например, $x$ и $y)$ и проделать те же переходы в обратном порядке, получив равенство третьего и второго чисел:

x3y2+ y3z2+ z3x2 = x3z2+ y3x2 +z3y2 ⇔

x2z3 − x2y3− z5+ z2y3 = z2x3− z5− y2x3+ y2z3 ⇔

x2− z2 z2− y2 x3−-z3-= z3− y3-⇔

2 2 2 2 z3− x3-= y3− z3 z − x y − z

Деления при этом корректны, так как выражения-делители уже фигурировали ранее в знаменателях, и мы знаем, что они не равны нулю.

Ответ: верно

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

Задача 3#67768

Натуральные числа $a,b,c$ таковы, что $1≤ a< b< c≤ 3000.$ Найдите наибольшее возможное значение величины

НОД(a,b)+ НОД (b,c)+ НОД (c,a)

Источники: Высшая проба - 2023, 11.3 (см. olymp.hse.ru)

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

Подсказка 1

Хочется получить какую-то оценку на эти НОДы. Понятно, что НОД(а,b) не больше чем a. Может попробовать что-то поделать с такой оценкой?

Подсказка 2

Если оценить так каждый НОД, получается как-то слишком грубо. Какой алгоритм приходит в голову, когда речь идёт о НОДах? Конечно же, алгоритм Евклида! Может, как-то улучшить оценку для НОД(a,b) с помощью него?

Подсказка 3

Если воспользоваться алгоритмом Евклида получиться, что: НОД(a,b)=НОД(a,b-a). Тогда т.к. НОД(a,b-a) не больше чем b-a, то и НОД(a,b) будет не больше чем b-a. если сделать тоже самое с НОД(b,c), что получится?

Подсказка 4

Итак, мы имеем что НОД(a,b) не больше b-a, а НОД(b,c) не больше c-b. Если их сложить, получится, что их сумма не больше чем (b-a)+(c-b)=с-а. Если оценить, что НОД(а,с) не больше чем a, то окончательно сумма всех НОДов будет не больше с, которое не больше 3000. Осталось только придумать пример...

Подсказка 5

Понятно, что с=3000. Чтобы достигалась оценка, необходимо, чтобы НОД(a,c)=a. Тогда с делится на a. Если мы сделаем так, что b тоже поделится на a, то, возможно, придумаем пример

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

Воспользуемся алгоритмом Евклида для $Н ОД(a,b),$ получим

НОД(a,b)= НО Д(a,b− a)

Заметим, что, так как НОД двух натуральных чисел не превосходит каждое из них,

НОД (a,b− a)≤ b− a⇒ НО Д(a,b)≤b − a

Аналогично получаем, что

НО Д(b,c)≤c− b

А также

Н ОД(c,a)≤ a

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

Н ОД(a,b)+ НОД(b,c)+ НОД(c,a)≤ (b− a)+ (c− b)+a = c≤3000

В качестве примера на $3000$ можно предъявить, например, $a= 1000,b= 2000,c= 3000.$ В этом случае

НО Д(a,b)+Н ОД(b,c)+Н ОД(c,a)= 1000+ 1000 +1000= 3000

Ответ: 3000

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

Задача 4#67770

Дана клетчатая доска $100× 100.$ Каждая клетка доски покрашена в один из двух цветов: белый или чёрный. Назовём раскраску доски уравновешенной, если в каждой строке и в каждом столбце 50 белых и 50 чёрных клеток. За одну операцию разрешается выбрать две строки и два столбца так, чтобы из 4 клеток на их пересечении две были чёрными, а две — белыми, и перекрасить каждую из этих 4 клеток в противоположный цвет. Докажите, что из любой уравновешенной раскраски можно получить любую другую уравновешенную раскраску с помощью указанных операций.

Источники: Высшая проба - 2023, 11.5 (см. olymp.hse.ru)

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

Подсказка 1

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

Подсказка 2

На ум приходит, конечно же, шахматная раскраска. Но переводить доску целиком в шахматную как-то тяжеловато. Может, начать со столбцов?

Подсказка 3

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

Подсказка 4

Пускай для определённости левая клетка нашей доминошки черная:

Подсказка 5

А вывод такой: в какой-то доминошке, которая находится ниже нашей, левая клетка будет белой, а правая чёрной, ведь иначе суммарно чёрных клеток будет больше в первом столбце, чем во втором, а это противоречит тому, что раскраска доски уравновешенная. Тогда мы можем применить к этим двум доминошкам операцию и продолжить спуск вниз. Но что же делать, если в какой-то момент, идя вниз по столбцам, мы найдём одноцветную доминошку?

Подсказка 6

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

Подсказка 7

На самом деле эти строки содержат две клетки, которые находятся в одном столбце, который находится правее наших, и при этом верхняя будет белая, а нижняя черная (Назовем этот столбец S). Это верно в силу того, что левее наших столбцов в этих строках поровну черных и белых клеток. Тогда мы можем выбрать один из наших столбцов, столбец S и поменять цвет клеток в них по этим строкам. Как же завершить решение?

Подсказка 8

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

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

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

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

Объясним, как делать следующий шаг внутри одной пары столбцов $X$ и $Y.$ Пусть в следующей строке $A$ сейчас находятся чёрная и белая клетка, но в неправильном порядке. Например, слева стоит чёрная клетка, а справа белая, а должно быть наоборот. Заметим, что во всех строках выше $A$ в первом столбце суммарно чёрных клеток не меньше, чем во втором, так как они уже покрашены шахматным образом. Значит, в какой-то строке $B$ ниже $A$ должна быть ситуация, когда в левом столбце чёрных клеток меньше, чем в правом, т.е. должна быть строка белая-чёрная (это следует из того, что суммарно в первом столбце столько же чёрных клеток, сколько и во втором). Произведём операцию со строками $A$ и $B$ и текущими столбцами.

$PIC$

Пусть теперь у нас в строке $A$ стоят две одинаковые клетки, например чёрные. Тогда в какой-то строке $B$ должны оказаться две белые клетки (иначе суммарно чёрных клеток в этих двух столбцах будет слишком много). Понятно, что эта строка расположена ниже текущей, т.к. выше неё все строки разноцветные. Теперь заметим, что если посмотреть на эту пару строк во всей таблице, то должен быть столбец $Z$ правее $X$ и $Y,$ в котором в первой строке белая клетка, а во второй — чёрная. Тут мы пользуемся тем, что левее наших столбцов в этих строках поровну чёрных и белых клеток. Теперь осталось лишь выбрать один из столбцов $X$ или $Y$ (в котором неправильный цвет в строке $A)$ и столбец $Z,$ а также строки $A$ и $B$ и произвести операцию с ними.

$PIC$

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

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

Задача 5#67771

Квадратные трёхчлены $P (x)$ и $Q(x)$ с действительными коэффициентами таковы, что в совокупности они имеют 4 различных действительных корня, а также каждый из многочленов $P(Q(x))$ и $Q(P(x))$ имеет 4 различных действительных корня. Какое наименьшее количество различных действительных чисел может быть среди корней многочленов $P(x),Q (x),P(Q (x))$ и $Q (P(x))?$

Источники: Высшая проба - 2023, 11.6 (см. olymp.hse.ru)

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

Подсказка 1

Попробуем подобраться к оценке: какие из многочленов могут иметь общий корень? По условию P(x) и Q(x) в совокупности имеют 4 корня. Тогда у них нет общих корней. Разбираться в общих корнях P(x) и P(Q(x)) не очень хочется, а вот в P(x) и Q(P(x))...

Подсказка 2

Если a- общий корень P(x) и Q(P(x)), то P(a)=0 и Q(P(a))=0, но тогда Q(0)=0. Это значит, что если P(x) и Q(P(x)) имеют общий корень и одновременно с этим Q(x) и P(Q(x)) имеют общий корень, то P(x) и Q(x) имеют общий корень, равный 0, а такое невозможно. Какую оценку мы уже можем дать?

Подсказка 3

Если корней не более 5, то P(x) и Q(P(x)) имеют общий корень и одновременно с этим Q(x) и P(Q(x)) имеют общий корень, что невозможно. Теперь надо придумать пример для 6 и задача убита...

Подсказка 4

Осталось самое сложное- пример. Из оценки видно, что кто-то из P(x) и Q(x) должен иметь корень 0. Пускай это будет P(x). Тогда: P(x)=mx(x-A) и Q(x)=n(x-C)(x-B). D и E-оставшиеся два корня. Ясно, что множество корней P(Q(x)) совпадает с множеством корней совокупности Q(x)=0 и Q(x)=A. Аналогично множество корней Q(P(x)) совпадает с множеством корней совокупности P(x)=B и P(x)=C. Тогда множество корней Q(P(x)) это B, C, D, E. А вот множество корней P(Q(x)) точно содержит B, C и что-то из 0, A, D, E. Попробуйте каким-то образом распределить корни по уравнениям Q(x)=A, P(x)=B и P(x)=C и попытаться решить систему.

Подсказка 5

Если вы еще пытаетесь найти пример, попробуйте положить, что Q(x)=A имеет корни 0 и D, P(x)=B имеет корни C и D, а P(x)=C имеет корни B и E. Тогда мы получим систему из 6 уравнений и 7 неизвестными.

Подсказка 6

Из системы можно получить, что С+D=B+E=A и B+C=D. Теперь можно наугад взять какие-то маленькие целые числа A, B, C, D, E так, чтобы выполнялись предыдущие равенства и надеется, что при этом m и n определятся однозначно. В противном случае, пробовать другие

Подсказка 7

Возьмите B=-1, C=2 и завершите пример

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

Заметим, что если среди корней многочлена $P(Q(x))$ есть корень $Q(x),$ скажем, число $x 0$ , то $P(Q(x))= P(0)=0, 0$ откуда $0$ является корнем $P (x).$ Аналогично если среди корней $Q(P (x))$ есть корень многочлена $P (x),$ то $0$ является корнем $Q(x).$ Но одновременно $P(x)$ и $Q(x)$ не могут иметь корень $0,$ т.к. иначе в совокупности у них было бы менее $4$ корней.

Отсюда можно получить оценку общего числа различных корней. Если их не больше $5,$ то у $P(Q(x))$ и $Q(x)$ есть общий корень, а также у $Q(P(x))$ и $P(x)$ есть общий корень, чего не может быть по вышесказанному.

Теперь построим пример, когда различных корней ровно $6.$ Пусть

1 P(x)= 2x(x− 3)

Q (x)= − 3(x+ 1)(x− 2) 2

Тогда у $P(x)$ корнями будут числа 0 и 3; у $Q(x)$ корнями будут числа -1 и 2; у $P(Q(x))$ корнями будут числа -1, 0, 1, 2; у $Q(P(x))$ корнями будут числа -1, 1, 2, 4. Итого корни всех многочленов в совокупности: -1, 0, 1, 2, 3, 4.

Ответ: 6

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

Задача 6#75129

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

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

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

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

Оценка. Приведём пример ситуации, в которой 4 дней не хватит. Пусть у каждого из 45 людей будет своя, не совпадающая с другими людьми, пара дней, в которые он не может участвовать во встрече. Так как количество способов выбрать пару дней из 10 предложенных равно $2 C10 =45$ , то для любой пары дней найдётся человек, который не может присутствовать ровно в эту пару дней. Предположим, что мы смогли выбрать какие-то 4 дня так, чтобы каждый узнал все новости. Но тогда существует человек $A$ , который не может присутствовать в первые два дня из этих четырёх, а также человек $B$ , который не может присутствовать в последние два из этих четырёх дней. Заметим, что тогда $B$ не сможет узнать новостей $A$ . Противоречие.

Пример. Теперь поймём, что 5 дней всегда точно хватит. Выберем 5 дней произвольным образом. Докажем, что любые два человека будут вместе присутствовать на какой-то встрече. Действительно, среди этих 5 дней есть не более 2 дней, в которые не может присутствовать первый, а также не более 2 дней, в которые не может присутствовать второй. Значит, найдётся день, в который могут присутствовать оба человека. Таким образом, каждая пара людей сможет обменяться новостями, то есть каждый узнает новость каждого.

Ответ:

При $k= 5$

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

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