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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Подсказка 1

В плоскости мы умеем давать оценки на какие-то суммы длин. Но сейчас мы работаем в пространстве, значит, нужно найти плоскости!

Подсказка 2

Рассмотрите многоугольники, в которые входит конкретное ребро. Какие оценки на длину этого ребра можно в них сделать?

Подсказка 3

Воспользуйтесь неравенством многоугольника для каждого ребра!

Подсказка 4

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

Подсказка 5

Длина ребра многогранника всегда меньше, чем L/3, где L — сумма длин рёбер многогранника.

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

Обозначим за $l,l,...,l 1 2 n$ длины ребер многогранника, а за $L$ — сумму длин всех ребер многогранника. Каждое ребро многогранника входит в две грани, которые являются многоугольниками. Отсюда следует, что для каждого ребра имеется как минимум два непересекающихся набора других ребер, длины которых в сумме больше, чем длина этого ребра (по неравенству многоугольника). Это значит, что длина каждого ребра многогранника всегда меньше, чем $L∕3,$ а значит, сумма длин всех ребер, кроме одного, всегда больше, чем $2L∕3.$ Теперь запишем сумму дробей из условия и заменим в каждой дроби знаменатель на $2L∕3$ — от этого сумма строго увеличится, но станет равной

l1 l2 ln L 3 2L∕3 + 2L∕3 + ⋅⋅⋅+ 2L∕3 = 2L∕3 = 2

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

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

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

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

Многочлен $P(x)$ со старшим коэффициентом $1$ имеет только целые коэффициенты, среди которых есть отрицательные. Обязательно ли многочлен $2025 (P(x))$ имеет хотя бы один отрицательный коэффициент?

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

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

Подсказка 1

Это задача — конструктив. Значит, ответ — необязательно, и нужно лишь привести пример многочлена.

Подсказка 2

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

Подсказка 3

Вероятно, вы попытались придумать такой многочлен 1, 2, 3 степени и потерпели неудачу. Как насчёт того, чтобы попробовать придумать многочлен 4 степени?

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

Покажем несколько примеров приведенных многочленов с целыми коэффициентами, среди которых есть отрицательные, у которых $2025$ -я степень не имеет отрицательных коэффициентов.

Пример 1. Рассмотрим многочлен

4 3 x2 Q(x)=x +x − a-+ x+ 1,

где $a$ — достаточно большое натуральное число (на самом деле, достаточно взять $a≥ 3).$ Проверим, что $(Q(x))2$ и $(Q(x))3$ имеют только положительные коэффициенты:

( ) ( ) ( ) ( ) ( ) (Q(x))2 =x8+ 2x7+ 1− 2a x6+ 2− 2a x5+ 1a2 + 4 x4+ 2− 2a x3+ 1− 2a x2+2x+ 1.

( ) ( ) ( ) ( ) ( ) (Q(x))3 = x12 +3x11+ 3− 3 x10+ 4− 6 x9+ 9+ -3− 3 x8+ 9+ 3-− 6 x7+ 6− -1 + 12 x6+ a a a2 a a2 a a3 a2

( 3- 6) 5 ( 3- 3) 4 ( 6) 3 ( 3) 2 + 9+ a2 − a x + 9+ a2 − a x + 4− a x + 3 − a x + 3x+1.

Теперь положим $P(x)= x5+ aQ(x).$ Этот многочлен приведённый, имеет только целые коэффициенты и один отрицательный. Покажем, что $(P(x))2$ и $(P (x))3$ тоже имеют только неотрицательные коэффициенты:

2 10 5 2 2 P(x)) = x +2ax Q(x)+ a (Q (x))

Единственный отрицательный коэффициент в этой сумме есть только у $2ax5Q(x)$ при $x7,$ он равен $− 2,$ но коэффициент при $x7$ у $a2(Q(x))2$ равен $2a2 >2,$ поэтому вся сумма не имеет отрицательных коэффициентов.

3 15 10 25 2 3 3 (P(x)) = x +3ax Q (x)+ 3ax (Q(x)) +a (Q(x))

Единственный отрицательный коэффициент в этой сумме есть только у $3ax10Q(x)$ при $x12,$ и он равен $− 3,$ но коэффициент при $x12$ уже в $a3(Q (x))3$ равен $a3 >3,$ поэтому вся сумма гарантированно не имеет отрицательных коэффициентов.

Поэтому $(P(x))2$ и $(P(x))3$ не имеют отрицательных коэффициентов, а значит, и $(P (x))n$ для всех больших $n$ не имеет отрицательных коэффициентов, так как любое число, большее $3,$ представимо в виде суммы двоек и троек.

Идея этого примера такова: рассмотрим многочлен $x4+ x3+ x+ 1.$ Его любая степень имеет положительные коэффициенты (нет нулевых). “Пошевелив” (на данный момент нулевой) коэффициент при $x2$ в отрицательную сторону мы получим многочлен, коэффициенты степеней которого «мало» отличаются от коэффициентов тех же степеней многочлена $x4+ x3+ x+1,$ так как коэффициенты его степеней $(x4+ x3 − tx2+ x+1)n$ являются непрерывными функциями от параметра $t,$ поэтому при малом $t= 1 a$ степени многочлена $4 3 x2 x + x − a + x+1$ будут иметь только положительные коэффициенты. На основе этого легко построить приведенный целочисленный многочлен, у которого все степени имеют только положительные коэффициенты. Аналогично подходит многочлен $k k−1 l x + x + ...+0 ∗x +...+ x+ 1$ и его шевеления $k k−1 xl- x + x +...− a + ...+ x+ 1$ для всех $2≤ l≤ k− 2$ при $k ≥4,$ тогда

( xl ) P(x)=xk+1+ a xk+ xk−1+ ...− a-+...+x +1

дает нам нужный пример многочлена $P (x),$ имеющий произвольную степень $k +1 ≥5.$

______________________________________________________________________________________________________________________________________________________

Пример 2. Рассмотрим

P (x)= x4+ 3x3− x2+ 3x+2.

Тогда многочлены $(P(x))2$ и $(P(x))3$ тоже имеют только положительные коэффициенты, а значит, и для всех $n > 3$ многочлен $(P(x))n$ будет иметь только положительные коэффициенты. Аналогичные примеры можно построить для любой степени, не меньшей $4 :P (x)= xd+ 3xd−1+ ...− xl+...+3x+ 2$ (почти все коэффициенты равны $3,2≤ l≤ d− 2).$ В этом примере минимальная степень многочлена равна $4.$

______________________________________________________________________________________________________________________________________________________

Пример 3. Пусть $d ≥6.$ Рассмотрим

P(x)=xd+ xd−1+ ...+x4 − x3+ x2+x +1

(все коэффициенты, кроме одного, равны $1).$ Тогда $(P(x))2$ и $(P(x))5$ не имеют отрицательных коэффициентов, а значит, и для всех $n >5$ многочлен $(P(x))n$ не будет иметь отрицательных коэффициентов. В этом примере модули коэффициентов не превосходят $1.$

______________________________________________________________________________________________________________________________________________________

Замечание 1. Данные примеры показывают, что для любого $d≥ 4$ существует приведённый целочисленный многочлен степени $d$ с отрицательным коэффициентом, старшие степени которого не имеют отрицательных коэффициентов. Можно доказать, что если квадратичный или кубический многочлен имеет отрицательные коэффициенты, то его степени тоже будут иметь отрицательные коэффициенты.

_________________________________________________________________________________________________________________________________________________________________________________

Замечание 2. Для всякого $n > 3$ можно построить целочисленный приведенный многочлен $P(x),$ степени которого вплоть до $n − 1$ имеют отрицательные коэффициенты, а начиная с $n$ не имеют отрицательных коэффициентов.

Ответ:

Не обязательно

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

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

Дан шестиугольник $ABCDEF,$ в котором $AF = CD,BC = EF,∠A +∠D = ∠B +∠E = 180∘.$ Докажите, что $2CF ≥ AB +DE.$

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

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

Подсказка 1

Вспомним условие на сумму углов в n-угольнике. Чем нам это может помочь? Для каких углов получается выразить величины?

Подсказка 2

Обратим внимание на четырёхугольник, образованный точками A, B, D, E. Какие свойства есть у вписанного четырёхугольника? Что ещё можно сказать про этот четырёхугольник?

Подсказка 3

Попробуем применить симметрию относительно середины отрезков BD и AE – какие новые точки и фигуры при этом получаются?

Подсказка 4

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

Подсказка 5

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

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

$PIC$

Так как сумма любого $n$ -угольника равна $180∘(n− 2),$ то сумма углов любого шестиугольника, не обязательно выпуклого, равна $720∘.$ Поэтому из условия $180∘ = ∠A +∠D = ∠B +∠E$ следует, что $∠C +∠F = 360∘,$ что, в свою очередь, влечет равенство треугольников $AF E$ и $DCB$ по двум сторонам и углу между ними. Так как углы $∠BDC$ и $∠EAF$ равны, а $180∘ = ∠BAE + ∠BDE,$ четырехугольник $ABDE$ — вписанный. Хорды $AE$ и $BD$ его описанной окружности равны, поэтому $ABDE$ является равнобокой трапецией.

Пусть, без ограничения общности, $AF = CD ≥ BC = EF.$ Отразим точки $F$ и $C$ относительно середин $P$ и $Q$ отрезков $AE$ и $BD$ соответственно, получим точки $F′$ и $C′.$ Параллелограммы $AF EF′$ и $BCDC ′$ равны, поэтому

∠BQC = ∠C′QD = ∠FPE = ∠F′PA

Отсюда делаем вывод, что $∠PQC ′ = ∠FPQ = α.$ Расстояние от точки $C′$ до прямой $PQ$ равно $C′Qsin α= FP sinα,$ что равно расстоянию от точки $F$ до прямой $PQ.$ На то же расстояние удалены точки $F′$ и $C′$ от прямой $PQ,$ поэтому четырехугольник $CC ′F F′$ является равнобокой трапецией с основаниями $C ′F$ и $F ′C,$ параллельными прямой $PQ$ (и, соответственно, $AB$ и $DE$ ). Кроме того, отрезок $PQ$ является общей средней линией для трапеций $CC′FF′$ и $ABDE,$ и его длина равна $(AB+ DE )∕2.$ Но в $CC ′F F′$ отрезок $CF$ является диагональю, которая всегда длиннее, чем средняя линия, если трапеция невырождена. Равенство $CF = (AB+ DE )∕2$ возможно только если $F$ и $C$ обе попали на прямую $PQ$ и $CC′FF′$ является вырожденной трапецией.

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

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

В комплекте для сборки игрушечного поезда есть один локомотив (который всегда расположен спереди), $2n$ одинаковых красных вагонов и $3n$ одинаковых желтых вагонов. Назовем поезд длинным, если в нем есть хотя бы $n$ вагонов (не считая локомотива). Сколько различных длинных поездов можно собрать, используя этот комплект? (Ответ должен быть дан в замкнутом виде: в ответе не должно быть сумм с переменным числом слагаемых, многоточий и т.д.)

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

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

Подсказка 1

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

Подсказка 2

В общем виде, для длины x, и, допустим, количества красных вагонов y, получаем, что количество поездов будет равно C из x по y (так как вагоны считаются одинаковыми, и нас интересует только расположение цветов). Теперь зафиксируем количество красных вагонов и просуммируем по всевозможным длинам поезда. Получаем какую-то неприятную сумму "цешек", которую, однако, можно упростить, если применить тождество Паскаля. Как нам это помогло?

Подсказка 3

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

Подсказка 4

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

Подсказка 5

Можем просто считать, что для каждой позиции имеем 2 варианта: красный или жёлтый. Суммируем по всевозможным длинам (от 0 до n не включительно), вычитаем из ранее найденного и получаем ответ.

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

Посчитаем количество всех поездов, которые можно собрать в данном наборе, и потом вычтем количество поездов, в которых не более $n − 1$ вагонов.

Зафиксируем число $k$ $(0≤ k≤ 2n)$ и посчитаем, сколько всего поездов с ровно $k$ красными вагонами. Жёлтых вагонов может быть от $0$ до $3n,$ и для каждого числа $l$ жёлтых вагонов от $0$ до $3n$ мы выбираем $k$ мест в строке длины $k+l.$ Таким образом, искомое количество поездов с $k$ красными вагонами равно сумме

Ckk +Ckk+1 +⋅⋅⋅+ Ckk+3n

Докажем, что эта сумма равна $k+1 Ck+3n+1.$

Распишем каждое слагаемое, пользуясь следующим тождеством Паскаля:

b+1 Cba = Ca+1− Cb+a1

Мы получим:

( k+1 k+1) ( k+1 k+1) ( k+1 k+1) ( k+1 k+1 ) ( k+1 k+1) Ck+1 − Ck + C k+2 − Ck+1 + Ck+3 − Ck+2 + ⋅⋅⋅ + Ck+3n− Ck+3n−1 + Ck+3n+1− Ck+3n

В каждой скобке вычитаемое равно уменьшаемому из предыдущей скобки. Нетронутым останется лишь уменьшаемое в последней скобке, равное $k+1 Ck+3n+1,$ — это и есть искомый результат сложения.

Заметим, что в силу симметрии биномиальных коэффициентов этот результат можно переписать как

k+1 3n Ck+3n+1 = Ck+3n+1

Теперь нужно сложить эти числа по всем $k$ от $0$ до $2n.$ Получим сумму

3n 3n 3n C3n+1 +C3n+2+ ⋅⋅⋅+ C5n+1

которая суммируется аналогичным образом через тождество Паскаля, и результат этого суммирования равен

3n+1 3n 2n+1 C5n+2 − C3n = C5n+2 − 1

Мы посчитали количество всех поездов. Осталось лишь вычесть количество поездов, в которых не более $n − 1$ вагонов, но для каждого $l≤ n− 1$ количество поездов длины $l$ очевидно равно $2l,$ а всего в сумме таких поездов $2n− 1.$ Таким образом, длинных поездов $C2n+1− 2n. 5n+2$

Ответ:

$C2n+1− 2n 5n+2$

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

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

Саша и Гоша поставили $2025$ фишек в клетки доски $1000× 1000$ и по очереди ходят. Саша своим ходом может взять две фишки, стоящие в левом верхнем и правом нижнем углу некоторого клетчатого прямоугольника (со сторонами больше $1),$ и поместить их по одной в две другие угловые клетки того же прямоугольника. Гоша своим ходом может передвинуть любую фишку либо вправо вниз, либо влево вверх по диагонали на любое число клеток. Они заканчивают ходить, когда кто-то не может сделать ход. Могут ли они ходить бесконечно?

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

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

Подсказка 1

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

Подсказка 2

Рассмотрите диагонали, параллельные побочной.

Подсказка 3

Докажите, что общее количество фишек на каждой из указанных диагоналей либо не меняется, либо строго увеличивается.

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

Запишем в клетки доски $n ×n$ положительные целые числа $a ,a ,...,a 1 2 2n−1$ так: число $a i$ записано в каждой клетке $i−$ й диагонали, параллельной главной диагонали, идущей слева сверху вправо вниз (ниже приведен пример для доски $5× 5).$

|---|---|--|---|---| |a5-|a4-|a3|a2-|a1-| |a6-|a5-|a4|a3-|a2-| |a7-|a6-|a5|a4-|a3-| |a8-|a7-|a6|a5-|a4-| -a9--a8--a7-a6--a5-|

Сопоставим каждой конфигурации фишек целочисленную величину $S,$ которая равна сумме чисел в клетках, занятых фишками. Тогда $S$ не меняется при действиях Гоши. Пусть последовательность ${ai}$ быстро растет как функция от $i,$ например, $i ai = 2.$ Покажем, что в этом случае $S$ строго увеличивается с каждым действием Саши.

Пусть Саша выбрал прямоугольник, у которого левая верхняя и правая нижняя клетки имели числа $ak$ и $al.$ Заметим, что в нашей расстановке для всякого числа $am$ числа, находящиеся строго ниже и левее него, имеют большие номера. Поэтому после хода Саши числа изменятся с $ak$ и $al$ на $ak+h$ и $al−h$ , где $h+ 1$ — высота выбранного прямоугольника, измеренная в клетках $(h≥ 1).$ Тогда

ak+h+ al−h =2k+h+ 2l−h >2k+ 2l = ak +al

Значит, $S$ станет строго больше. При этом $S$ все время остается целочисленным. Так как $S$ ограничено сверху (как минимум, оно меньше, чем $2025a2n−1),$ игра не может продолжаться бесконечно.

Ответ:

Не могут

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

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

При каких $n≥ 2025$ существует такой набор из $n$ прямоугольников, что из них можно собрать прямоугольник (без пустот и наложений), а из любого меньшего их подмножества, состоящего из хотя бы двух прямоугольников, — нельзя?

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

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

Подсказка 1

Попробуйте определить некоторое разбиение (в дальнейшем будем называть его спиральным) клетчатого прямоугольника [(n+1)/2]×[(n+1)/2].

Подсказка 2

Нарисуем спираль, начиная двигаться из угла вдоль короткой стороны прямоугольника, если они не равны. Затем расположим в центре спирали квадратик 1×1, за ним — прямоугольник 1×2, а затем будем накрывать все непокрытые клетки частично покрытого отрезка спирали прямоугольником ширины 1 и соответствующей длины. Что еще нужно сделать в этом разбиении?

Подсказка 3

Нужно построить спиральное разбиение клетчатого прямоугольника со столбцами и строками неравной ширины.

Подсказка 4

Определим ширину столбца i как wᵢ = (n+1)ⁱ⁻¹, а ширину строки j как hⱼ = C ⋅ (n+1)ʲ⁻¹, где С = (n+1)ⁿ⁺³. Теперь разбейте неравномерный клетчатый прямоугольник на меньшие. Какие прямоугольники можно из них сложить?

Подсказка 5

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

Подсказка 6

Что, если в прямоугольнике, сложенном из малых прямоугольников, два прямоугольника ориентированы по-разному?

Подсказка 7

Можно получить противоречие с величиной его площади.

Подсказка 8

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

Подсказка 9

Оцените для любого i количества прямоугольников ширины не более wᵢ и высоты не более hᵢ.

Подсказка 10

Предположим, что мы сложили из подмножества малых прямоугольников некоторый прямоугольник. Заметим, что верхняя сторона этого прямоугольника состоит из сторон малых прямоугольников. Как тогда можно представить ее длину? А длину высоты?

Подсказка 11

Пусть некоторая горизонтальная прямая пересекает прямоугольник и не содержит сторон малых прямоугольников. Чему тогда равна суммарная ширина всех малых прямоугольников, которые пересекает эта прямая?

Подсказка 12

Вычислите, сколько четырёхугольников ширины wᵢ пересекает любая такая прямая.

Подсказка 13

Сколько тогда из них можно сложить прямоугольников, и какого они будут размера?

Подсказка 14

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

Подсказка 15

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

Подсказка 16

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

Подсказка 17

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

Подсказка 18

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

Подсказка 19

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

Подсказка 20

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

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

Для начала определим разбиение клетчатого прямоугольника

⌊n-+1⌋ ⌊n-+1⌋ 2 × 2 ,

которое в дальнейшем будем называть спиральным. Нарисуем спираль, начиная двигаться из угла вдоль короткой стороны прямоугольника, если они не равны. Затем расположим в центре спирали квадратик $1× 1,$ за ним — прямоугольник $1× 2,$ а затем будем накрывать все непокрытые клетки частично покрытого отрезка спирали прямоугольником ширины 1 и соответствующей длины.

Для того, чтобы получить искомое разбиение, построим спиральное разбиение клетчатого прямоугольника со столбцами и строками неравной ширины. Положим ширину столбца $i$ равной

wi =(n+ 1)i−1,

а ширину строки $j$ равной

hj = C ⋅(n +1)j−1,

где $C = (n +1)n+3.$

Далее разобьем неравномерный клетчатый прямоугольник на

⌊ n+ 1⌋ ⌊ n+ 1⌋ -2-- × -2--

прямоугольников (назовем их $малыми$ ) по линиям сетки. Выясним, какие прямоугольники можно сложить из подмножества множества малых прямоугольников.

Заметим, что суммарная площадь малых прямоугольников равна

( ⌈n+1⌉) ( ⌊n+1⌋) 1+ (n+ 1)+...+ (n+ 1) 2 C +C ⋅(n +1)+ ...+ C⋅(n+ 1) 2 <

( ⌈n+1⌉)( ⌊n+1⌋) < C ⋅n2⋅ 1+ (n+ 1)+ ...+(n+ 1)-2- 1 +(n+ 1)+...+(n+ 1)-2- =

( ⌈ ⌉ ) ( ⌊ ⌋ ) = C⋅ (n+ 1)n+21 +1− 1 (n+ 1) n+21+1 − 1 <

⌈n+1⌉+1 ⌊n+1⌋+1 ⌈n+1⌉+⌊n+1⌋+2 n+3 2 < C(n+ 1) 2 (n+ 1) 2 = C(n+1) 2 2 = C(n+ 1) = C

Заметим также, что если в прямоугольнике, сложенном из малых прямоугольников, два прямоугольника ориентированы по-разному, обе его стороны имеют длину не менее $C,$ а значит, его площадь будет не меньше $C2,$ что, как мы увидели выше, невозможно.

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

_________________________________________________________________________________________________________________________________________________________________________________

Утверждение 1. Пусть даны некоторые целые неотрицательные числа, не превышающие $n$

′ ′ a1,...,a⌈n+21⌉ и a1,...,a⌈n+21⌉

Тогда если

a1w1+ ...+a⌈n+21⌉w⌈n+21 ⌉ =a′1w1+ ...+ a′⌈n+1⌉w⌈n+21⌉, 2

то $ai =a′i$ для всех $i.$

Предположим, что для некоторых различных наборов $ai$ и $a′i$ оказалось, что

a1w1+ ...+ an+1 w n+1 = a′1w1 +...+ a′n+1w n+1 ⌈2 ⌉ ⌈ 2 ⌉ ⌈ 2 ⌉ ⌈ 2 ⌉

Пусть $k$ — наибольшее число, при котором

′ ak ⁄=ak.

Не умаляя общности положим, что $ak >a′k.$ Тогда

( ) ( ) a1w1+ ...+a⌈n+1⌉w⌈n+1⌉ − a′w1 +...+a′⌈ ⌉w⌈n+1⌉ = -2- -2- 1 n+21 -2-

( ) = (a1− a′1)w1+ ...+ a⌈n+1⌉− a′⌈n+1⌉ w⌈n+1⌉ = (a1− a′1)w1+ ...+(ak− a′k)w⌈n+1⌉ > 2 2 2 2

( k−2) k−1 > (− n)⋅(w1+ ...+ wk−1)+wk = (−n)⋅ 1+ (n+ 1)+ ...+ (n +1) +(n+ 1) =

( k−1 ) k−1 = − (n+ 1) − 1 +(n+ 1) =1 >0

_________________________________________________________________________________________________________________________________________________________________________________

Утверждение 2. Пусть даны некоторые целые неотрицательные числа, не превышающие $n$

′ ′ b1,...,b⌊n+21⌋ и b1,...,b⌊n+21⌋

Тогда если

b1h1+ ...+ b⌊n+21⌋h⌊n+21 ⌋ =b′1h1+ ...+b′⌊n+21⌋h⌊n+21⌋,

то $bi = b′i$ для всех $i.$

Доказывается аналогично утверждению 1.

_________________________________________________________________________________________________________________________________________________________________________________

По построению для любого $i$ малых прямоугольников ширины $wi$ не больше

⌈ ⌉ n+-1 ≤ n, 2

а малых прямоугольников высоты $hi$ не более

⌊n+-1⌋ 2 ≤ n

Предположим, что мы сложили из подмножества малых прямоугольников некоторый прямоугольник. Заметим, что верхняя сторона этого прямоугольника состоит из сторон малых прямоугольников, а значит, ее длина представима в виде

a1w1+ ...+ a⌈n+21⌉w⌈n+21⌉,

где $ai$ — целые неотрицательные числа, не превышающие $n.$ Аналогично, высота прямоугольника представима в виде

b1h1+ ...+ b⌊n+21⌋h⌊n+21⌋,

где $bi$ — целые неотрицательные числа, не превышающие $n.$

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

a1w1+ ...+ a⌈n+1⌉w⌈n+1⌉ 2 2

Из утверждения 1 следует, что любая такая прямая пересекает ровно $ai$ прямоугольников ширины $wi.$ Значит, из всех прямоугольников ширины $wi$ можно сложить $ai$ прямоугольников размера

wi× (b1h1+ ...+ bn+1 h n+1-) ⌊ 2 ⌋ ⌊2 ⌋

Из утверждения 2 следует, что для каждого такого прямоугольника нам нужно использовать $bi$ малых прямоугольников высоты $hi.$ Получается, для построения нашего прямоугольника нам понадобится не менее $ai⋅bj$ малых прямоугольников размера $wi× hj.$ С другой стороны, все малые прямоугольники различны, а значит, все $ai$ и $bi$ равны либо 0, либо 1.

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

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

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

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

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

Наконец, если центральный прямоугольник не входит в $A,$ ни один прямоугольник, содержащий клетку на пересечении строк, содержащих клетки ключевого прямоугольника, и столбца, в котором лежит центральный прямоугольник, не может содержаться в $A.$ Из этого следует, что ни один прямоугольник, кроме ключевого, не может входить в $A.$

Получается, $A$ состоит из всех прямоугольников разбиения, что и требовалось.

Ответ:

При всех $n ≥ 2025$

Курсы

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

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

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

Даны многочлены $P (x)$ и $Q(x),$ оба степени $n$ со старшими коэффициентами $1.$ У каждого из них ровно $n$ различных целых корней. Известно, что все корни многочлена $P(x)$ четны, а все корни многочлена $Q (x)$ нечетны. Докажите, что у многочлена $P (x)+ Q(x)$ не может быть целых корней.

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

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

Подсказка 1

Как можно преобразовать многочлены, зная их корни?

Подсказка 2

Например, x² + 3x + 2 = (x + 2)(x + 1).

Подсказка 3

Подставьте вместо x некоторое число k. Каким оно может быть?

Подсказка 4

Что, если k — чётно?

Подсказка 5

Воспользуйтесь тем, что корни P(x) — чётные, а корни Q(x) — нечётные. Может ли их сумма обращаться в 0?

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

Пусть чётные числа $a ,a ,...,a 1 2 n$ — корни многочлена $P (x),$ а нечётные числа $b,b,...,b 1 2 n$ — корни многочлена $Q(x).$ Тогда:

P(x)+Q (x)= (x− a1)(x− a2)⋅⋅⋅(x− an)+(x− b1)(x− b2)⋅⋅⋅(x− bn)

Подставим в $P(x)+ Q(x)$ целое число $k.$ Возможны два случая: $k$ чётно и $k$ нечётно. В первом случае

P(k)= (k− a1)(k− a2)⋅⋅⋅(k− an)

чётно как произведение чётных чисел, а

Q(k)=(k− b)(k− b)⋅⋅⋅(k− b) 1 2 n

нечётно как произведение нечётных чисел, поэтому, $P(k)+Q (k)$ нечётно.

Аналогично в случае нечётного $k,$ тогда $P(k)$ нечётно как произведение нечётных чисел, а $Q(k)$ чётно как произведение чётных чисел, и $P(k)+ Q(k)$ опять нечётно. Таким образом, $P(k)+ Q(k)$ нечётно при любом целом $k,$ и поэтому не может быть равно нулю, т.к. ноль — четное число. Значит, $P(x)+Q (x)$ не имеет целых корней.

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

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

Дана двусторонняя линейка без делений. Этот инструмент позволяет делать две операции:

1) провести прямую через две данные точки;

2) провести прямую, параллельную данной, на расстоянии 1 от нее.

Постройте с ее помощью (и не используя никакие другие инструменты) правильный треугольник.

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

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

Подсказка 1

Попробуйте получить равносторонний треугольник из иных фигур.

Подсказка 2

Мы можем строить параллельные прямые, какие фигуры они могут нам дать?

Подсказка 3

Рассмотрите пересечение двух пар параллельных прямых.

Подсказка 4

Они образуют параллелограмм, а чему будут равны его высоты, если между параллельными прямыми расстояние равно единице?

Подсказка 5

Как раз единице высоты и будут равны. А чем тогда является наш параллелограмм?

Подсказка 6

Это ромб! Рассмотрите его диагонали.

Подсказка 7

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

Подсказка 8

Проводя прямые, параллельные данным, мы построим клетчатую сетку из квадратов со стороной 1.

Подсказка 9

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

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

$PIC$

Для начала построим две пары параллельных прямых. На их пересечении образуется параллелограмм с одинаковыми высотами, равными $1,$ а значит, являющийся ромбом. Проведем его диагонали, как известно, являющиеся перпендикулярными. Заметим, что с помощью двух этих перпендикулярных прямых и построения параллельных прямых на расстоянии $1$ мы можем построить клетчатую сетку любого конечного размера, состоящую из квадратиков со стороной $1.$

Введем систему координат с центром в одном из узлов сетки и с осями, параллельными сторонам клеток. Проведем прямую $l$ через точки $(0,0)$ и $(1,1).$ Теперь проведем снизу от нее параллельную прямую $l′$ на расстоянии $1.$ Заметим, что на пересечении пар прямых $x= 0,x =1$ и $l,l′$ образуется ромб со стороной длины $√12+-12-=√2,$ а значит, $l′$ проходит через точку $(0,− √2).$

Теперь проведем прямую $m$ через пару точек $(0,−√2 )$ и $(1,0),$ а также параллельную ей прямую $m′$ на расстоянии $1$ сверху от нее. На пересечении пар прямых $x= 0,x =1$ и $m,m ′$ образуется ромб со стороной длины $∘ -------- 12+(√2)2 = √3,$ а значит, $m ′$ проходит через точку $(1,√3).$

Осталось лишь соединить точки $(0,0),(1,√3)$ и $(2,0),$ чтобы получить искомый равносторонний треугольник.

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

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

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

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

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

Подсказка 1

Нам надо либо предъявить данный треугольник для любого возможного типа графа, либо придумать антипример. Что проще?

Подсказка 2

Конечно же, второй вариант. А как удобнее будет строить такой граф?

Подсказка 3

Попробуйте разделить точки на несколько уровней/групп. Хотелось бы как-то сократить перебор возможных вершин синего треугольника...

Подсказка 4

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

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

Пример $1.$

$PIC$

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

Докажем, что синего треугольника не найдется. Для этого разделим точки на три уровня: точки $1,$ $2$ и $3$ будут принадлежать внешнему уровню, точки $4,$ $5$ и $6$ — среднему, а $7$ и $8$ — внутреннему. Заметим, что на каждом уровне все точки соединены между собой красными отрезками, а значит, если синий треугольник существует, все его вершины находятся на разных уровнях.

Вершина $7$ соединена со всеми вершинами среднего уровня, а значит, не может быть вершиной синего треугольника. Аналогично, вершина $5$ соединена со всеми вершинами внешнего уровня, а значит, не может быть вершиной синего треугольника. Тогда вершина $8$ соединена со всеми вершинами среднего уровня, кроме $5,$ и не может быть вершиной синего треугольника. Значит, ни одна вершина внутреннего уровня не является вершиной треугольника с синими сторонами, а значит, такого треугольника не найдется.

_________________________________________________________________________________________________________________________________________________________________________________

Пример $2.$

$PIC$

Возьмем два графа $K4$ с красными ребрами. Тогда синие отрезки образуют граф $K4,4,$ то есть двудольный граф, в котором могут быть только циклы четной длины, а треугольник — это цикл нечётной длины, следовательно треугольников нет.

_________________________________________________________________________________________________________________________________________________________________________________

Замечание. Если точек $9$ или более, то синий треугольник обязательно найдется. Другими словами, граф, дополнительный к планарному на $9$ и более вершинах, всегда содержит граф-треугольник в качестве подграфа.

Ответ:

Не обязательно

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

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

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

$PIC$

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

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

Подсказка 1

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

Подсказка 2

А что, если "прикладывать" к картинке треугольник?

Подсказка 3

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

Подсказка 4

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

Подсказка 5

Например, можно разрезать фигуру по прямым CB и BK.

Подсказка 6

Рассмотрите точку пересечения прямых FD и BK.

Подсказка 7

Докажите, что на прямой, содержащей эту точку и точку G, будет лежать одна из сторон треугольника.

Подсказка 8

Перейдите к счёту углов.

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

Решение представлено на рисунке.

$PIC$

Покажем, что это действительно требуемое разрезание. Изначально был семиугольник $ABCDEF G.$ Точка $L$ получена отражением точки $B$ относительно точки $K$ — середины стороны $CD,$ в результате чего получен треугольник $DKL,$ равный треугольнику $CKB.$ При этом, $FL = 3= AB,$ откуда следует, что треугольники $ABG$ и $FLG$ равны по двум сторонам ( $FL = AB$ и $FG = GA$ ) и углу между ними $∘ ∠LGF = ∠BAG = 120.$

Таким образом, треугольники $ABG$ и $FLG$ совместятся после разрезания и указанного перекладывания. Получится равносторонний треугольник $BGL,$ длины сторон которого равны длине большей диагонали параллелограмма со сторонами $2$ и $3$ и тупым углом $120∘.$

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

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

По кругу стоит несколько коробок. В одной из них 2025 камней, а остальные пусты. Разрешается взять два камня (возможно, из разных коробок) и переложить один в соседнюю коробку по часовой стрелке, а другой — в соседнюю против часовой стрелки. Через некоторое время все камни оказались в одной и той же коробке, соседней с начальной. Докажите, что один из камней побывал во всех коробках.

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

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

Подсказка 1

Занумеруем коробки от 0 до n-1. Скажем, что сначала камни были в нулевой коробке, а в конце — в первой.

Подсказка 2

А как именно мы будем вычислять номер коробки, в которой будет находиться камень, при перекладывании?

Подсказка 3

Если мы переложим камень по часовой стрелке из коробки k, то он окажется в коробке (k + 1) mod n. А давайте избавимся от взятия остатков.

Подсказка 4

Можно задать это отдельно: скажем, что у нас есть бесконечное количество кувшинов, в самом начале в кувшине с номером 0 будет 2025 шаров. При перекладывании камня i из коробки с номером k в коробку (k + 1) mod n, мы также переложим шар с номером i из кувшина k' в кувшин k' + 1.

Подсказка 5

В каких кувшинах окажутся шары в конце?

Подсказка 6

Их номера будут сравнимы с 1 по модулю n. А что можно сказать про сумму их номеров?

Подсказка 7

А как мы перекладываем камни?

Подсказка 8

Сумма номеров кувшинов всегда будет равно 0, при том за каждое перекладывание одно из слагаемых увеличивается на 1, а другое — уменьшается на 1. В кувшинах с какими номерами могут находиться шары в конце?

Подсказка 9

В кувшине с номером 0 не может быть шаров. Пусть шар с номером i оказался в кувшине с отрицательным номером. Посмотрите на остатки.

Подсказка 10

Как может меняться номер кувшина для i-го шара за одно перекладывание?

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

Занумеруем камни от $1$ до $2025.$ Занумеруем коробки от $0$ до $n − 1$ по или против часовой стрелки так, чтобы все камни в начале были в $0$ -й коробке, а в конце оказались в $1$ -й.

Расставим бесконечное количество кувшинов в ряд (у каждого кувшина будет номер целое число). Положим в кувшин с нулевым номером $2025$ шаров, занумерованных от $1$ до $2025.$ Каждый ход, когда камень с номером $i$ перекладывают из коробки номер $k$ в коробку номер $(k +1)mod n,$ будем перекладывать шар номер $i$ из кувшина $′ k,$ где он находился на момент перекладывания камня, в кувшин номер $′ k + 1.$

Аналогично, когда камень с номером $i$ перекладывают из коробки номер $k$ в коробку номер $(k − 1)mod n,$ будем перекладывать шар номер $i$ из кувшина $′ k,$ где он находился на момент перекладывания камня, в кувшин номер $′ k − 1.$ Таким образом, одновременно с перекладыванием двух камней мы будем перекладывать два шара. Заметим, что остаток по модулю $n$ от номера кувшина, в котором находится $i$ -й шар, будет всегда равен номеру коробки, в котором находится $i$ -й камень.

Обозначим номер кувшина, в котором находится $i$ -й шар в данный момент, за $Q(i).$ Мы только что выяснили, что тогда номер коробки, в котором находится $i$ -й камень, равен $Q(i)mod n.$ Теперь ясно, что в конце все шары оказались в кувшинах, номера которых сравнимы с $1$ по модулю $n.$ Заметим, что сумма

Q (1)+ Q(2)+ ...+ Q(n)

в любой момент времени равна нулю: в начале она равна нулю, так как все шары были в кувшине с номером $0,$ и каждый ход одно из слагаемых увеличивается на $1,$ а другое — уменьшается.

Поскольку ни один из шаров в конце не находится в кувшине номер $0,$ один из шаров, допустим $i$ -й, оказался в конце в кувшине с отрицательным номером. Поскольку этот номер сравним с $1$ по модулю $n,$ номер кувшина $i$ -го шара в конце концов оказался меньше либо равен $1− n.$

Итого, номер кувшина $i$ -го шара каждый ход менялся не более, чем на $1,$ и в конце стал меньше либо равен $1− n.$ Но это значит, что остатки от деления на $n$ номера кувшина $i$ -го шара пробежали все возможные значения от $0$ (в начале) до $n− 1.$ То есть номер коробки $i$ -го камня пробежал все возможные значения от $0$ до $n− 1,$ что и требовалось.

Интенсивы

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

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

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

Существует ли функция $f,$ определенная на всей числовой прямой, такая, что для любого $x$ выполнено равенство

2 f(f(x))= x − x− 1

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

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

Подсказка 1

Хм, функция от функции... При подстановке каких-то иксов мы не получим ничего интересного, ведь нам не сильно помогает знание, например, f(f(0))=-1. Тогда какие ещё интересные точки можно попробовать поискать?

Подсказка 2

Давайте найдём неподвижные точки функции g(x)=f(f(x)), то есть решим уравнение g(x)=x.

Подсказка 3

Используя знание о неподвижных точках g(x), найдём неподвижные точки g(g(x)).

Подсказка 4

Попробуем найти g(g(f(1))). Распишем каждую g(x) как f(f(x)), а потом обратно соберём f(f(...)) в g(..), но в другом порядке. Что интересного можно сказать про единицу?

Подсказка 5

Предыдущее выражение можно преобразовать в f(g(g(1))), а единица — одна из неподвижных точек g(g(x)), значит, это просто f(1). Как это использовать?

Подсказка 6

Ага, получается g(g(f(1)))=f(1), значит, f(1) — неподвижная точка g(g(x)). Но мы ранее их находили, следовательно, мы теперь точно знаем, какие значения может принимать f(1).

Подсказка 7

Давайте посмотрим, чему может быть равно f(1), и в каждом случае поищем противоречие.

Подсказка 8

Скорее всего, оно будет связано с переходом в преобразованиях g(x)=f(f(x)), ведь мы знаем f(1) по рассматриваемому случаю и умеем напрямую считать g(x), потому что она задана в явном виде.

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

Предположим, что такая функция $f$ существует. Положим

2 g(x)= x − x − 1= f(f(x))

Заметим, что

2 g(x)=x ⇐ ⇒ x − 2x− 1= 0 ⇐ ⇒

⇐ ⇒ x∈ {1− √2,√2-+ 1}

Также заметим, что

g(g(x))= (x2 − x− 1)2− (x2− x− 1)− 1= x ⇐⇒

⇐⇒ x4 − 2x3− 2x2 − 2x− 1= 0

Два корня этого уравнения мы уже знаем, так как

g(x)= x

g(g(x))= g(x) =x

Отсюда

4 3 2 (2 )(2 ) x − 2x − 2x − 2x− 1= x − 2x− 1 x − 1 = 0

Значит,

g(g(x))= x

x∈ {− 1,1− √2,1,√2-+ 1}

Заметим, что

g(g(1))= 1

g(g(f(1)))= f(f(f(f(f(1)))))= f(g(g(1)))=f(1)

Отсюда

√- √ - f(1)∈ {−1,1− 2,1, 2+ 1}

Проверим все случаи:

1) $f(1)= 1$

1= f(1)=f(f(1))= g(1)= −1

2) $f(1)= −1$

1= g(− 1) =f(f(− 1))= f(f(f(1)))=

=f(g(1))=f(−1)= f(f(1))=g(1)=− 1

3) $√- √- f(1)∈ {1− 2, 2 +1}$

1= g(g(1))= f(f(f(f(1)))= f(g(f(1)))= f(f(1))= g(1)= −1

В любом случае приходим к противоречию, а значит, искомой функции не существует.

Ответ:

Не существует

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

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

Многие учащиеся математического кружка остаются в нём преподавать после выпуска. Будем говорить, что Ваня является последователем Саши, если Ваня учился у Саши или если Ваня учился у ученика Саши, ученика ученика Саши и так далее. Преподаватель кружка называется народным, если у него есть последователи, и не менее половины из них — победители международной олимпиады IMO. Известно, что всего в кружке училось 100 победителей IMO. Какое наибольшее количество народных преподавателей может быть в этом кружке, если у каждого человека не более одного учителя и никто не является собственным последователем?

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

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

Подсказка 1

У нас есть люди, причём некоторые из них связаны каким-то отношением... Всё это очень похоже на граф! Рассмотрим ориентированный граф, где вершины — это ученики и преподаватели кружка, а ребра ведут от учителя к его ученику. Каким будет этот граф?

Подсказка 2

Верно, это будет набор непересекающихся деревьев! Рассмотрим какого-нибудь народного учителя, не являющегося последователем другого народного учителя. Если среди его последователей k победителей IMO, то сколько среди них может быть народных учителей?

Подсказка 3

Общее число последователей не может быть больше 2k+1, значит, учителей среди них не больше 2k. Получается, в одном таком поддереве количество народных учителей не более, чем удвоенное количество победителей IMO. А верна ли эта оценка для всего графа?

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

Рассмотрим ориентированный граф, где вершины ученики и преподаватели кружка, а ребра ведут от учителя к его ученику. По условию этот граф — лес. Оценка. Выберем какого-нибудь народного учителя $A,$ который не является последователем другого народного учителя. Пусть у вершины $A$ $k$ последователей победителей IMO. Тогда не победителей IMO, у $A$ не более чем $k,$ так как $A$ — народный. А, значит, всего вершин в поддереве $A$ не более $2k+ 1,$ из которых только $2k$ учителей могут будут народными, так хотя бы один человек никого не учил. Осталось заметить, что поддеревья соответствующие разным выбранным народным учителям, не пересекаются. Поэтому число народных преподавателей кружка не больше чем удвоенное число победителей IMO. Получили оценку на $200.$ Пример. Возьмём ориентированный путь из $201$ вершины. Победители IMO — это $100$ нижних учеников. Тогда все преподаватели, кроме самого нижнего в этом пути — народные.

Ответ: 200

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

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

Окружность $ω$ описана около треугольника $ABC.$ Биссектриса $AL$ пересекает $ω$ в точке $S ⁄= A.$ Докажите, что длина проекции отрезка $AS$ на прямую $AB$ больше длины отрезка $AL.$

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

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

Подсказка 1

Какую еще проекцию можно рассмотреть?

Подсказка 2

Пусть точки K и M — проекции S на AB и BC соответственно. Будем считать без потери общности AB > AC. Что можно сказать о точках K и M?

Подсказка 3

Например, точка M будет являться серединой BC.

Подсказка 4

Попробуйте заметить точки, лежащие на окружности.

Подсказка 5

Это точки K, M, B, S. Рассмотрите треугольник AKL. Как он связан с вопросом задачи?

Подсказка 6

Какой вывод можно будет сделать, если мы докажем, что ∠ALK — тупой?

Подсказка 7

Тогда AK > AL! Попробуйте оценить сумму ∠LAK + ∠AKL.

Подсказка 8

При получении неравенства Вам может пригодиться взаимное расположение точек L и M.

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

Длины проекции на $AB$ и на $AC$ совпадают, поэтому без потери общности $AB >AC.$

Пусть точки $K,$ $M$ — проекции $S$ на $AB$ и $BC$ соответственно. Заметим, что точка $K$ — попала на отрезок $AB,$ а $M$ — середина $BC,$ а, значит, лежит на $BL.$ Так же, точки $K,$ $M,$ $B,$ $S$ лежат на одной окружности.

$PIC$

Докажем, что в $△AKL$ угол $∠ALK$ тупой, из этого сразу будет следовать, что $AK > AL.$ Для этого оценим $∠LAK + ∠AKL.$ Пользуемся описанной окружностью треугольника и вписанностью $KMSB$

∠LAK = ∠SAC = ∠SBC = ∠SBM = ∠SKM < 90∘− ∠LKA

В последнем неравенстве воспользовались расположением точек $L$ и $M.$ Это неравенство даёт нам $∘ ∠LAK + ∠LKA < 90 ,$ а из этого следует, что $∠ALK$ — тупой.

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