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

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

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

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

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

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

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

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

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

Задача 1#61459

Имеется дробь $1 n$ . Семиклассник Семёнов каждую минуту прибавляет к её числителю и знаменателю по $1$ и смотрит, можно ли сократить полученную дробь. Семёнов утверждает, что первый раз сократимая дробь получилась после $1000$ шагов. Стоит ли ему верить?

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

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

Подсказка 1

Давайте сначала поверим юному математику и посмотрим на дробь через 1000 минут. Какой вывод можно тогда сделать о делимости её знаменателя?

Подсказка 2

Верно, знаменатель кратен какому-то из простых делителей числа 1001. Пусть этот делитель равен p. Если бы мы хотели опровергнуть слова семиклассника, то скорее всего слова о том, что дробь сократилась впервые, верно?

Подсказка 3

Нужно найти такое число, которое выражается через слагаемые n и p и при этом делится на p. Хороша идея взглянуть на знаменатель дроби.

Подсказка 4

Мы обнаружили число n + p - 1, которое делится на р. Это как будто знаменатель дроби через р-1 минуту. А что с её числителем? Найдём противоречие, которое искали в подсказке 2?

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

Предположим, что Семёнов сказал правду, то есть в первый раз числитель и знаменатель $1+k n+k$ имеют общий делитель больше единицы через $k= 1000$ минут.

Получится $-1001- 7⋅11⋅13 n+1000 = n+1000$ , откуда $n +1000$ делится на какое-то число из множества ${7,11,13},$ давайте это число обозначим буквой $p.$

Заметим, что $1001$ делится на $p$ (если непонятно, то посмотрите, что такое $p$ ). Тогда $p+ (n+ 1000)− 1001= n+ p− 1$ тоже делится на $p$ .

Но отсюда сразу следует, что дробь уже через $p− 1$ шагов сократима: $1+p−1- --p-- n−1+p = n+p−1$ . А Семёнов сказал, что первый раз дробь сократима будет через $1000$ шагов. Но $p− 1 <1000$ . Семёнов, ты не прав!

Ответ:

нет

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

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

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

Задача 2#75195

Дан описанный четырехугольник $ABCD,$ у которого радиусы вписанных окружностей треугольников $ABC$ и $ADC$ равны. Найдите угол между диагоналями $AC$ и $BD.$

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

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

Подсказка 1

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

Подсказка 2

Считать отрезки, на которые делит точка касания вписанной окружности сторону, мы умеем) Так посчитаем же их! А для чего дано условие об описанности четырехугольника?

Подсказка 3

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

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

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

$PIC$

В самом деле, обозначим точки касания $TB$ и $TD$ соответственно. Тогда

|ATB|= |AB-|+|AC|−-|BC-||ATD|= |AD|+-|AC-|−-|DC-| 2 2

Критерий описанности четырехугольника

|AB|+ |CD |= |BC |+ |AD |

что равносильно равенству $|ATB|= |ATD |.$

Теперь легко видеть, что картинка однозначно задается радиусом вписанных окружностей треугольников $ABC$ и $ADC$ и расстояниями от точки касания до точек $A$ и $C.$ Значит, картинка переходит в себя при симметрии относительно прямой $AC,$ при этом точки $B$ и $D$ меняются местами. Но это означает, что $BD$ перпендикулярна $AC.$

Ответ:

$90∘$

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

Задача 3#80963

В правильном тетраэдре с ребром, равным $8,$ отмечены $25$ различных точек: $4$ вершины и $21$ произвольная точка внутри тетраэдра. Никакие $4$ отмеченные точки не лежат в одной плоскости. Докажите, что найдется тетраэдр с вершинами в отмеченных точках, объем которого меньше единицы.

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

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

Подсказка 1:

Так... В условии дано ребро тетраэдра и что-то сказано про объём. Так давайте найдём объём исходного тетраэдра! Как, зная объём, можно доказать требуемое?

Подсказка 2:

На сколько фигур надо разбить исходный тетраэдр, чтобы объём одной из них был точно меньше 1?

Подсказка 3:

Да! Поскольку 128√2/3 < 61, то достаточно разбить и на 61 фигуру, но в условии дано, что никакие 4 отмеченные точки не лежат в одной плоскости. В дальнейшем наверняка будет удобно будет пользоваться делимостью на 4. Давайте докажем, что тетраэдр можно разбить на 64 маленьких. Каким методом проще всего доказать это утверждение?

Подсказка 4:

Воспользуемся индукцией по количеству отмеченных точке внутри исходного тетраэдра. Пусть k — количество точек внутри тетраэдра. Покажем, что исходный тетраэдр можно разбить на 3k + 1 с вершинами в отмеченных точках. База очевидна. При переходе k → k+1 посмотрите, куда падает добавленная точка. Как это позволяет точно добавить новые 4 тетраэдра?

Подсказка 5:

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

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

Объем тетраэдра с ребром 8 есть $128√2∕3,$ поскольку этот тетраэдр получается если взять не соединенные ребром вершины куба с ребром $√- 4 2.$ Заметим, что $√- 128 2∕3< 64,$ значит если удастся тетраэдр разрезать на 64 тетраэдра с вершинами в отмеченных точках, то один из тетраэдров разбиения будет иметь объем меньше $1.$

Докажем, что если внутри тетраэдра выбраны $k$ точек, так что если добавить к ним $4$ вершины тетраэдра, то среди полученных $k +4$ точек никакие $4$ не лежат в одной плоскости, тогда тетраэдр можно разрезать на $3k+ 1$ тетраэдр с вершинами в выбранных точках.

Индукция по $k.$ При $k =0$ считаем что тетраэдр разбит на один тетраэдр — самого себя. Пусть для $k$ доказано, докажем для $k+ 1.$ Возьмем любые $k$ из внутренних точек, по предположению индукции разобьем тетраэдр. Теперь добавим последнюю точку, и посмотрим, внутрь какого тетраэдра разбиения она попала. Этот тетраэдр разобьем на четыре, каждый из которых образован новой точкой и гранью разбиваемого тетраэдра. Разбитый тетраэдр заменим в разбиении четырьмя новыми, число тетраэдров в разбиении выросло на $3$ ( $4$ добавили $1$ убрали). Итак, при $k= 21$ имеем разбиение на $64$ тетраэдра, что и требовалось.

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

Задача 4#83203

Точки $P$ и $Q$ лежат соответственно на сторонах $BC$ и $CD$ квадрата $ABCD.$ Прямые $AP$ и $AQ$ пересекают $BD$ в точках $M$ и $N$ соответственно, вторично пересекают описанную около квадрата окружность в точках $X$ и $Y$ соответственно, а прямые $BY$ и $DX$ пересекаются в точке $H.$ Докажите, что $AH ⊥P Q$ тогда и только тогда, когда точки $P,Q,M,N$ лежат на одной окружности.

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

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

Подсказка 1

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

Подсказка 2

Нужно доказать, что четырёхугольник вписанный. Далее попробуйте сначала показать, что если M, N, P, Q лежат на одной окружности, то PQ || AH. Рассмотрите точку пересечения BY и PQ. Быть может, она лежит на какой-то окружности...

Подсказка 3

Для доказательства в обратную сторону стоит вспомнить теорему Паскаля и применить её к DCBYAX.

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

Сначала полезный факт: на одной окружности лежат точки $M,N,Y,X$ , ведь

A˘B + B˘X A˘D + B˘X ∠AY X =----2---= ----2---= ∠AMD.

$PIC$

_________________________________________________________________________________________________________________________________________________________________________________

Если точки $M,N,P,Q$ лежат на одной окружности, то $∠NQP =∠NMA = ∠AYX$ , то есть $PQ || XY$ .

$PIC$

Пусть прямые $PQ$ и $BY$ пересекаются в точке $H′$ . Тогда, в силу параллельности прямых $XY$ и $PQ$ , верно, что $∠Y XA = ∠H′PA$ . C другой стороны, $∠YXA = ∠YBA$ , т.к. данные углы опираются на меньшую дугу $AY$ в окружности, описанной около квадрата $ABCD$ .

Таким образом, $∠H′BA = ∠YBA$ , что влечёт вписанность четырехугольника $H′PBA$ , следовательно, $∠AH ′P = 180∘− 90∘ = 90∘$ , то есть $H′$ является основанием перепендикуляра из точки $A$ на $PQ$ .

$PIC$

Аналогично, $H ′′$ — точка пересечения прямых $DX$ и $PQ$ — является основанием перпендикуляра из точки $A$ на $PQ$ , а значит, точки $H ′$ и $H ′′$ совпадают и лежат на каждой из прямых $BY$ и $DX$ , следовательно, совпадают с точкой $H$ , что доказывает $AH ⊥ PQ$ .

_________________________________________________________________________________________________________________________________________________________________________________

Если $AH ⊥P Q$ , то по теореме Паскаля для шестиугольника $DCBY AX$ точки пересечения противоположных сторон $DC$ и $Y A$ , $CB$ и $AX$ , $BY$ и $XD$ , соответственно точки $Q,P,H$ лежат на одной прямой. Тогда точки $H,P,B,A$ лежат на окружности, построенной на $AP$ как на диаметре, следовательно, $∠HP A =∠HBA = ∠AXY$ . Наконец, в силу того, что точки $X,Y,M, N$ лежат на одной окружности, верно, что $∠AXY = ∠MNA$ , то есть $∠QP M = ∠MNA$ и точки $M, N,P,Q$ лежат на одной окружности.

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

Задача 5#89083

В последовательности чисел Фибоначчи $1,1,2,3,5,8,13,21,...$ каждое следующее число, начиная с третьего, равно сумме двух предыдущих. Докажите, что среди чисел Фибоначчи нет ни одной натуральной степени числа $7.$

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

Подсказка 1

Какое первое число в последовательности чисел Фибоначчи кратно 7? Чему равен его индекс?

Подсказка 2

Первое число Фибоначчи, кратное 7 - это 21, которое является 8 числом Фибоначчи. Продолжив выписывать элементы данной последовательности можно заметить, что первые несколько членов, индексы которых кратны 8, делятся на 7. Докажите, что на 7 делятся те и только те члены последовательности чисел Фибоначчи, индексы которых кратны 8. Как можно доказать, что никакое из данных чисел не является степенью 7?

Подсказка 3

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

Подсказка 4

Да, достаточно показать, что на 3 делятся те и только те числа Фибоначчи, номер которых делится на 4.

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

Для начала докажем, что на $7$ делятся те и только те числа Фибоначчи, номер которых делится на $8.$ Докажем это по индукции. База: Первое число Фибоначчи, кратное $7$ — это $21,$ которое является $8$ числом Фибоначчи.

Переход: Пусть этот факт был верен для всех чисел Фибоначчи с номерами от $1$ до $8k.$ Докажем, что он верен для чисел от $8k+1$ до $8k+ 8.$ Пусть число с номером $8k − 1$ имело остаток $a$ от деления на $7(a ⁄=0).$ Тогда числа с номерами $8k +1,...,8k +8$ будут иметь следующие остатки: $a,a,2a,3a,5a,a,6a,0.$

Теперь докажем, что на $3$ делятся те и только те числа Фибоначчи, номер которых делится на $4.$ Доказательство аналогично.

Следовательно, если число Фибоначчи делится на $7,$ то его номер делится на $8.$ Значит его номер делится на $4,$ а значит, само число обязано делиться на $3.$ Значит оно не может быть равно натуральной степени числа $7.$

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

Задача 6#121815

Даны $m$ подмножеств $n$ -элементного множества: $A ,...,A . 1 m$ Обозначим через $|A| i$ число элементов множества $A . i$ Докажите неравенство

m∑ n2 |Ai∩ Aj ∩Ak|≥ (|A1|+...+|Am|)3 i,j,k=1

в котором индексы $i,j,k$ пробегают все значения от $1$ до $m,$ то есть в сумме всего $m3$ слагаемых.

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

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

Сумма в левой части описывает количество элементов в пересечениях троек множеств. Можно задаться вопросом: в какое количество пересечений троек входит каждый элемент? Посчитаем и ответим на этот вопрос!

Пусть $i−$ й элемент исходного $n−$ элементного множества входит в $ai$ подмножеств $A1,A2,...,Am.$ Тогда он входит ровно в $3 ai$ пересечений троек. Тогда

∑m |Ai ∩Aj ∩ Ak|=a31+ ...+ a3n i,j,k=1

Заметим, что $a1+ a2 +...+ an = |A1|+ |A2|+ ...+ |Am |,$ так как обе суммы подсчитывают двумя способами одну и ту же величину: количество пар (множество; элемент множества). Таким образом, задача свелась к доказательству неравенства

2 3 3 3 3 n (a1+ a2+ ...+an)≥ (a1 +a2+ ...+ an)

А это неравенство эквивалентно неравенству между средним арифметическим и средним кубическим!

∘ -3---3------3- 3a1+-a2+...+an ≥ a1+a2+-...+-an n n

Курсы

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

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

Задача 7#121817

На доске написана система из $12$ различных уравнений с $6$ неизвестными $x ,x ,x,x ,x,x . 1 2 3 4 5 6$ Каждое уравнение имеет вид $xi+ xj +xk =0,$ где $i⁄= j ⁄= k$ (сумма трех различных неизвестных равна нулю). Могло ли оказаться так, что у системы бесконечно много решений?

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

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

Подсказка 1

Эх, вот бы сразу знать ответ, чтобы не пришлось идти не в ту сторону.. Если такого быть не могло, то должно быть красивое доказательство (хотя бы какое-то!), если может, то нужен один пример. С чего легче начать?

Подсказка 2

Давайте попробуем с примера. Если решений бесконечно много, то у них есть какой-то общий вид, причем чем меньше будет различных значений у переменных, тем больше равенств нулю мы сможем составить (если все 6 неизвестных разные, то составить 12 уравнений будет сложнее, чем если у нас будут всего 1-3 различных значений на 6 переменных).

Подсказка 3

Очевидно, что все переменные не могут быть равны между собой (ведь тогда единственным решением будет (0,0,0,0,0,0), а не бесконечное количество, противоречие). Сможем ли составить пример с двумя различными значениями? Получится ли записать такое решение в общем виде?

Подсказка 4

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

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

Да, могло. Приведем пример. Пусть $t$ — произвольное действительное число, положим, чтобы выполнялись равенства:

x1 = x2 = 2t

x = x = x =x =− t 3 4 5 6

Тогда при сложении одного слагаемого, равного $2t,$ и двух слагаемых, равных $− t,$ сумма будет равна нулю. Количество таких сумм составляет:

C1 ⋅C2= 2⋅6= 12 2 4

Выпишем данную систему явно:

(||x + x + x =0 ||||| 1 3 4 |||||x2+ x3+ x4 =0 |||||x1+ x3+ x5 =0 |||||x2+ x3+ x5 =0 |||||x1+ x3+ x6 =0 ||||{ x2+ x3+ x6 =0 |||||x1+ x4+ x5 =0 |||||x2+ x4+ x5 =0 |||||x1+ x4+ x6 =0 ||||| |||||x2+ x4+ x6 =0 |||||x1+ x5+ x6 =0 |(x2+ x5+ x6 =0

Ответ:

Могло

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

Задача 8#121821

Найдите все вещественные $c,$ при которых сумма девятых степеней корней уравнения $x2− x+c =0$ равна нулю, и сумма пятнадцатых степеней тоже равна нулю.

Замечание: Корни могут быть комплексными.

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

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

Подсказка 1

Видим квадратное уравнение, видим сумму (степеней) корней и сразу думаем о ..?

Подсказка 2

Конечно, о теореме Виета🥰. Тогда нам нужно найти возможные произведения корней. Осталось поколдовать с равенствами (например, если умножим нулевое число на что-то, то получим всё ещё ноль, и если из нуля вычтем ноль, всё ещё будет ноль. А потом и поделить на "не ноль" можем!)

Подсказка 3

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

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

Первое решение.

Обозначим корни через $x1$ и $x2.$ Воспользуемся теоремой Виета, тогда задача переформулируется так: известно, что $15 15 9 9 x1 + x2 = x1+ x2 = 0$ и $x1+x2 = 1,$ найти $x1x2$ .

Для начала заметим, что $x1x2 ⁄=0,$ поскольку в противном случае одно из $x1,x2$ равно нулю, тогда $9 9 x1 +x2 = 0$ влечет, что и второе равно нулю, что противоречит $x1+x2 ⁄= 0.$

Выполним следующие преобразования:

x91+ x92 = 0

( 9 9)( 6 6) x1+x2 x1+ x2 = 0

( 9 9)( 6 6) ( 15 15) x1+x2 x1+x2 − x1 + x2 =0

96 6 9 x1x2+ x1x2 = 0

x61x62(x31+ x32)=0

c6(x31+ x32)=0

Поскольку $c⁄= 0$ имеем

x31+ x32 = 0

(1)

С другой стороны

0= x3+ x3= (x1+ x2)((x1 +x2)2− 3x1x2)=1⋅(12− 3c) 1 2

Отсюда $c= 13.$

Второе решение.

Так же как и в первом решении доказываем равенство $(1).$ Далее вместо последнего шага сделаем следующее. Заметим, что если $x1,x2$ — действительные корни, то одновременное выполнение $(1)$ и $x1+x2 ⁄=0$ невозможно из-за монотонности куба.

Если $x1,x2$ не действительные, то они сопряжены, тогда их кубы — тоже. Если сумма двух сопряжённых чисел равна нулю, то их аргументы имеют вид $π +πk, 2$ то есть до возведения в куб аргумент имел вид $1(π +πk), 3 2$ или эквивалентно $πm-, 6$ где $m∈ {1,3,5}.$ Обозначив аргумент через $r,$ имеем для трёх случаев соответственно:

π π 5π- 2cos 6r= 1, 2cos 2r= 1, 2cos 6 r=1

В первом случае $1- r = √3,$ в других невозможно, поскольку аргумент — неотрицательное число.

Получаем $2 1 c =x1x2 = r = 3.$

Ответ:

$c= 1 3$

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

Задача 9#121822

Дано несколько вещественных чисел, по модулю не превосходящих $1.$ Сумма всех чисел равна $S.$ Докажите, что из них можно выбрать несколько чисел так, чтобы при некотором натуральном $n <100$ сумма выбранных чисел отличалась от $nS- 100$ не более чем на $-1- 100.$

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

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

Подсказка 1

Обозначим данные k чисел за x₁, x₂, ... , x_k. Давайте, например, поймем, что нам дает условие на модуль.

Подсказка 2

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

Подсказка 3

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

Подсказка 5

У нас n - натуральное, давайте рассмотрим наименьшие индексы m_1, m_2, ... , m_99, такие, что x₁ + x₂ + ... + xₘ_₁ ≥ S/100, x₁ + x₂ + ... + xₘ_₂ ≥ 2*S/100 и так далее. Как они могут нам помочь в оценке? Может, нам чего-то еще не хватает? Вспомните, что мы хотим доказать.

Подсказка 6

Доопределим разность суммы каждой последовательности и соответствующей ей оценки: aᵢ = x₁ + x₂ + ... + xᵢ - i*S/100. Кстати, все ли они определены? А можем ли мы как-то оценить величину каждой aᵢ?

Подсказка 7

mᵢ и aᵢ определены, так как по крайней мере для k при любом i выполняется x₁ + x₂ + ... + x_k = S ≥ i*S/100. Давайте формально доопределим m₀ = 0 и a₀ = 0. Выбранные нами индексы были первыми для своего условия, а также все xᵢ по модулю не превосходят 1, следовательно, значения aᵢ лежат в отрезке [0;1]. А можем ли мы сжать этот отрезок для удобства и попробовать оценить разницу между какими-нибудь aᵢ и aⱼ, где i ≠ j? Какое неравенство мы хотим получить по условию задачи?

Подсказка 8

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

Подсказка 9

Несколько ранее мы предположили, что отрезок величин aᵢ можно сжать для получения искомой оценки, а если для некоторого i a_i попадает в отрезанный кусок? Какое множество чисел может быть искомым?

Подсказка 10

Подумайте, как доказать, что в таком случае набор чисел x₁, x₂, ... , x_(m_i-1) нам подойдет.

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

Обозначим данные $k$ чисел через $x,x ,...,x . 1 2 k$ Без ограничения общности будем считать, что $S ≥ 0.$ Если это не так, то будем доказывать утверждение задачи для чисел $yi = −xi$ с положительной суммой. Из него будет следовать утверждение исходной задачи.

Докажем, что среди данных чисел существует набор из подряд идущих, удовлетворяющих неравенству из условия. То есть найдутся такие натуральные $s$ и $t$ $(1≤ s≤ t≤k),$ что подмножество $xs,xs+1,...,xt$ — искомое.

Обозначим через $m1$ первый индекс, для которого

S x1+x2+ ...+ xm1 ≥ 100,

через $m2$ — первый индекс, для которого

x1+x2+ ...+ xm2 ≥-2S-, 100

и так далее:

x1+ x2+...+xmi ≥-iS- 100

по всем $i$ от $1$ до $99.$ Рассмотрим также разности

a = x +x +...+ x − -iS- i 1 2 mi 100

Заметим, что $m i$ и $a i$ определены, поскольку по крайней мере для $k$ выполняется неравенство

x1+ x2 +...+ xk = S ≥-iS- 100

для любого $i.$ Формально доопределим: $m0 = 0$ и $a0 = 0.$ Заметим теперь, что так как выбранные нами индексы были первыми для своего условия и так как все числа $xi$ по модулю не превосходят $1,$ то все $ai$ лежат на отрезке $[0;1].$

Предположим, все $ai$ лежат на отрезке $[0;1− 1100].$ Тогда, так как чисел $ai$ всего $100$ (для $i$ от $0$ до $99),$ найдутся два индекса $i$ и $j,$ для которых $|ai− aj|≤ -1. 100$ Без ограничения общности $j >i.$ Тогда $mj ≥ mi$ по определению чисел $mi.$ Получаем:

| | ||(x + x + ...+ x )− (x +x + ...+ x )+ jS-− iS||≤ -1- | 1 2 mi 1 2 mj 100 100| 100

или, что то же самое,

|| (j− i)S|| 1 ||xmi +xmi+1+ ...+ xmj −--100--||≤ 100.

Заметим, что можно взять $n =j− i,$ поскольку $j− i> 0$ и $j− i≤ j <100.$ Тем самым, числа $xmi,xmi+1,...,xmj$ — искомые.

Пусть теперь для некоторого $i$ разность $ai$ попала на полуинтервал $(1 −1100,1].$ Докажем, что в этом случае подмножество $x1,...,xmi−1$ — искомое. Для этого достаточно показать, что

iS-− -1-< x1 +...+xmi−1 ≤-iS-. 100 100 100

Второе неравенство следует из определения $mi;$ ведь $mi$ — это первый индекс, для которого сумма стала не меньше $-iS-. 100$ Первое неравенство равносильно следующему: $x1+...+xmi−1− iS-> −-1. 100 100$ Но

x1+...+xmi−1− -iS-= ai− xmi 100

и это больше $− 1100,$ так как $ai > 1− 1100$ и $xmi ≤ 1.$