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

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

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

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

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

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

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

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

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

Задача 1#121751

Дан выпуклый многогранник. Разделим длину каждого ребра на сумму длин остальных ребер и вычислим сумму полученных дробей. Докажите, что полученная сумма меньше $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

Многочлен $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

Дан шестиугольник $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

В комплекте для сборки игрушечного поезда есть один локомотив (который всегда расположен спереди), $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

Саша и Гоша поставили $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

При каких $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

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

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

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

Пусть чётные числа $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

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

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

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

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

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

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

$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

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

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

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

Пример $1.$

$PIC$

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

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

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

Пример $4.$

$PIC$

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

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

Ответ:

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

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

Задача 10#128830

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

$PIC$

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

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

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

$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

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

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

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

Занумеруем камни от $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,$ что и требовалось.