Департамент образования города Москвы

§1.3 Лемма Штейница. Некоторые оценки константы Штейница

Лемма Штейница. Существует такая константа , что любое сколь угодно большое, но конечное множество векторов в , длина которых не превосходит , а сумма равна 0, можно упорядочить так, чтобы длина суммы первых векторов для любого не превышала .
Аналогичное утверждение верно и в одномерном случае. Более того константу можно считать равной 1.
Действительно, пусть имеется конечный набор ненулевых чисел , сумма которых равна и каждое из которых по модулю не превосходит .
1) На первое место поставим произвольное положительное число при прохождении набора слева на право. Возможны два случая:
а) следующее по счету положительное число в сумме с первым не превосходит . Тогда поставим его вторым слагаемым.
б) в противном случае в качестве второго слагаемого выберем первое по счету отрицательное число и так далее.
Если чисел уже выбраны так, что частичные суммы не превосходят , то следующее число всегда можно выбрать так, чтобы остаться в предела промежутка
Таким образом .
Для доказательства Леммы Штейница для плоскости понадобится доказать еще две леммы.
Лемма 1. Пусть - начало ломаной в с конечным числом звеньев и максимальной длиной звена , а - ее конец (рис.1). Тогда можно так переставить звенья этой ломаной, чтобы расстояние от любой вершины полученной ломаной до прямой не превышало .
Доказательство. Спроектируем ломаную на прямую перпендикулярную прямой . Тогда точки и перейдут в какую-то точку на этой прямой, примем ее за 0. Выберем упорядочение полученной одномерной ломаной как описано в лемме Штейница для одномерного случая. Тогда соответствующая полученной перестановка в и будет искомой. То есть расстояние от любой из вершин ломаной до прямой не будет превышать максимальную длину звена (рис.2).
Лемма 2. Пусть, как и в лемме 1 расстояние от всех вершин ломаной до прямой меньше и дополнительно . Тогда можно так переставить звенья этой ломаной, что некоторый начальный кусок полученной после перестановки ломаной от до некоторой вершины удовлетворяет двум условиям:

1) ;

2) расстояния от вершин ломаной, расположенных между и , до отрезка не превосходят .

Доказательство. Выберем часть исходной ломаной, начинающуюся в вершине и заканчивающуюся в вершине , следующим образом:



Рис.3.

1) расстояние от до и от до не превосходит

2) проекции на прямую всех вершин ломаной между и лежат на отрезке
Занумеруем вершины ломаной в порядке движения от к . Будем считать, что точка лежит "выше" точки на прямой . Выделим множество вершин, проекции которых лежат выше . В нем имеется вершина с наибольшим номером. Проекция следующей за ней вершины будет уже лежать ниже точки . Эта вершина и будет вершиной . При этом расстояние от ее проекции до точки меньше (так как предыдущая вершина лежит выше точки ) и расстояние от до ее проекции меньше . Следовательно, расстояние от до вершины меньше . Аналогично определим точку , выбирая вершину, предыдущую той, которая имеет наименьший номер среди лежащих ниже . Условие гарантирует, что .
Если переставить выделенную часть ломаной в точку , то ее конец будет находиться на расстоянии не больше от вершины . Расстояние до отрезка при такой увеличится не более чем на (рис.4).
Последовательное применение лемм 1 и 2 к некоторой ломаной, расстояние между началом и концом которой превосходит , дает такую перестановку вершин, что в ломаной, полученной в результате перестановки, есть непустая правильная часть - такой начальный кусок ломаной, который удовлетворяет утверждению леммы 2.