АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ ТЕОРИИ ГРУПП И ПОЛУГРУПП 2001 г.

не более С\ дисков, следовательно в ее поддиаграмме не более С/ диско* Итак, в поддиаграмме Kn\K t 1 не более С\ дисков. К ° 2 SC ,2, < - - С] . И т.д. По условию - 0. Поэтому АТГ»-' < с { . с ( > К ^ ' К f *-2 - c t => к**-1 <2 C f K ° h' 2 K°h-) -С,2, С,2> к?*-2 -с .Н к ^ - 3 - 2 С,2,=> к ° н ъ < 3 С\ и т.д. В итоге получаем К ° й йИС?. Лемма доказана. Следствие 7. 1. Пусть К\ - диск как в лемме 6 . Тогда, если К , 0 =Ni, то 5 = I КЛ>С _ Щ 2С\ 2 • Доказательство. S —Ni +N 2 + . . . + Я*. 1 >N t +N 2 + . . . +Nh.i 2 2 N, N. N. N 1 2C f 2C f - С. Здесь элементы N\, N 2 , ■. ., Мм со­ ставляют арифметическую прогрессию с первым членом Nu разность этой про­ грессии равна -С] и необходимо просто вычислить сумму ее первых п членов, Ч . Следствие доказано. Предположим, что диаграмма Мо такова, что сняв менее чем Ew слоев с каждою из дисков К< получим поддиаграмму Я0, содержащую только короткие диски. Лемма 8. Пусть Мо - диаграмма, как описано выше. Пусть К / - диск в Мо- Тогда К°° iC ; p +Ew С2 . Доказательство. Пусть А ,0 = К, \ = А ’,0 \ К *1, . . . , К[=К\ Ч К " ' , /<£w- 1 . Поддиаграммы состоят из дисков, позво­ ляющих строить элементы из V.(и») (из дисков длины оснований которых боль- 1 ше 2lw |). Но уже в диаграмме К {+1 = К[ \К ^п1 все диски короткие. Из дока- 134