функции у, чем на У'*, что противоречит минимальности У*. Таким образом, в Т* не может существовать последовательность отрезков, включающая не более Х2п/2 отрезков и содержащая два отрезка, длины которых отличались бы более, чем на 1 .
Свойство 7. Существует такое «о, что для любых я>По кратные точки любого минимального разбиения Т* не могут находиться внутри отрезка [0, v + 1].
Допустим противное. Предположим, что каким бы ни задать число по, всегда найдутся число п > п 0 и минимальное разбиение Т* такое, что кратные точки этого разбиения будут находиться внутри
отрезка {0, v+1]. Возьмем число |
|
п , ™ max | 2 l0B |
{г О [У 2 (а Р) + 1 ] ) |
, 2 ь Д |
*
где
г = 1 + 2 ( У 2 ( . - р ) + 1)/(1 - У 2 (« — р).
Согласно сделанному предположению существуют п*>п0 и разбие ние Т* такие, что кратные точки разбиения Т* лежат внутри отрезка
[О, |
v + 1]. Рассмотрим |
это |
число п* и соответствующее ему |
разбие |
ние Т*. |
|
|
|
входящие в Т*, на группы |
|
|
|
|
Разобьем |
все отрезки |
Д, |
последова |
тельных отрезков, включающие по Х2п*12— 1 отрезков каждая |
(А. = |
= |
1 — V 2(a‘ |
— Р) — 2 |
~ |
). |
Группы строятся так, что |
две |
из них |
начинаются с отрезков, |
граничных с кратными точками, и все группы, |
не пересекаясь друг с другом, |
расходятся в обе стороны |
от |
кратных |
точек (рис, 6); при этом группы, лежащие на концах отрезка [0 , v + 1 ],
могут насчитывать и меньшее, чем А.2п*!2— 1, |
число |
отрезков. |
На |
основании свойства 2 |
количество отрезков |
в разбиении |
Т* не превос |
ходит величины />+ |
1 = |
V 2 (а — Р) 2л*/2+ |
1 и число групп не более, |
чем г —- 1 + 2 ( V 2 (а — Р) + |
1)/(1 — Y 2 (а — Р). Действительно, |
|
р + 1____________ У 2 (а — Р) + 2~п*!2 |
|
|
\2п*12— 1 |
— |
1 — Y2 (а — Р) — 2-2~п*>2 |
^ |
|
|
< |
У 2 ( а - Р ) |
+ 1 |
|
|
|
|
1_ У2 (а -Р) |
|
|
|
|
|
|
|
|
|
так как п* > 2 1 о2 [4/(1- У |
2 ( а - р ) ] . |
|
|
|
|
Рассмотрим две соседних группы. Длина первого отрезка по |
следующей группы |
на |
основании свойства 6 |
не может более, |
чем |
на 1 , отличаться от длины любого другого отрезка предыдущей группы; с другой стороны, на основании того же свойства 6, длина этого отрезка не может более, чем на 1 , отличаться от длины любого
другого отрезка его собственной группы. Поэтому длина любого
Группы поМ 0,5п*~ 1отреэко8
Рис. 6.
отрезка последующей группы отличается от длины любого отрезка предыдущей группы не более, чем на 2. Так как первый отрезок первой группы (для любой из двух последовательностей групп, идущих вправо и влево от кратных точек) является по построению групп граничным с кратной точкой, то в соответствии со свойством 4 (или свойством 5) его длина равна 1.
Согласно только что отмеченной закономерности длина любого отрезка второй группы не может превышать 3, длина любого отрез ка третьей группы не может превышать 5 и т. д. Так как общее
число групп М ^ г , |
то максимальная длина отрезка в разбиении Т* |
не может быть больше (2г—1 ). |
Следовательно, |
сумма длин всех отрезков разбиения Т* не превы |
шает величины (2г — 1 ) [ 1^ 2 (<х— Р) 2 ”*^2 + l ] , что |
меньше величины |
V - f 1 = Р2"* + 1, так как п* > 2 log {(2г — 1) |
[ V 2 (а—Р)+1 ]/|3} . |
Таким образом, разбиение Т* не является разбиением типа Т, что |
противоречит предположению о минимальности Т*. |
Свойство 8. Существует по такое, что при любом я>яо, если
только одна из кратных точек любого разбиения Т* совпадает с од ним из концов отрезка (0, v + l], Т* содержит лишь одну кратную точку.
Доказательство свойства 8 проведем в предположении, что крат
ная точка |
совпадает |
с левым |
концом |
отрезка |
(0, v + l], |
так как |
в случае |
совпадения |
кратной |
точки с |
правым |
концом |
отрезка |
[О, v + 1] ход доказательства остается прежним.
Предположим противное. Пусть для любого я0 существуют я*> > я 0 и соответствующее этому п* минимальное разбиение такое, что
одна из кратных точек разбиения Т* совпадает с левым концом от
резка |
(0, |
v + l ] и разбиение Т* содержит две кратные точки. В |
ка |
честве |
«о |
возьмем число, использовавшееся при выводе свойства |
7, |
и рассмотрим соответствующее этому «о число л* и минимальное разбиение Т*, существующее по сделанному предположению. Так как по предположению Т* содержит две кратные точки, то гранич ный с кратными точками справа отрезок имеет единичную длину — это можно доказать так же, как при выводе свойства 4. Далее точно так же, как при выводе свойства 7, можно показать, что сумма длин всех отрезков разбиения Т* не может равняться требуемой величине v +1 и, следовательно, разбиение Т* не является разбиением типа Т, что противоречит предположению о минимальности разбиения Т*.
Свойство 9. Существует яо такое, что для любого я>Яо, если только некоторое разбиение Т* содержит одну кратную точку, эта точка не может совпадать с правым концом отрезка (0, v + l].
Предположим противное. Пусть для любого Яо найдутся я*>Яо и соответствующее этому я* разбиение Т*, такое что Т* содержит одну кратную точку и эта точка совпадает с правым концом отрезка [О, v+1]. Возьмем в качестве я0 число
По = 2 log {«/р [1 V 2 (а — Р)]>.
Тогда по сделанному предположению найдутся я* и соответствую щее ему Т* такие, что Т* содержит одну кратную точку и эта точка совпадает с правым концом отрезка [0, v + l]; рассмотрим это раз
биение Т*. Для него сумма длин отрезков, соответствующих одним только кратным точкам (их число, согласно свойству 2 , превышает
[1 |
— V2 (а — р)]2 п*/2 — 1 ) |
24* |
371 |
не меньше, чем
{ [1 - К2 (« — Р)] 2 ^ 2 - 1 } ( v + 1) =
= { [ 1 - |
V2 (ос - р )] 2п'12 - 1 } ($2п*+ 1), |
что при выбранном |
п0 превышает требуемое значение s— ( v +l ) = |
= (а—<$)2п*—1. Следовательно, Т* не является разбиением типа Т; это приводит к противоречию, что я доказывает свойство 9.
Из свойств 2—9 становится ясным вид минимального разбиения Т* при достаточно больших п: для любого п > п а (где «о выбирается наибольшим из всех значений, необходимых для доказательства свойств 2—9) (Ь—р—1) точек разбиения совпадают с левым концом отрезка (0, v+1]. Остальные р точек разбиения заполняют отрезок [О, v+1], причем среди этих р точек уже нет совпадающих. Соот ветственно сказанному / , = /г= ■• • = /ь - р - 1= 0 , остальные отрезки jb-p, j b - p+i, . . jb отличны от нуля.
Обозначим j b- p = A о, / ь_ р+1=|Дь ..., / ь = Д Р,
Ьр
тогда g (п) = |
min |
]\\ = |
min Д Д„! |
Здесь |
область 2 определяется |
|
р |
*=1 |
п |
*=о |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
соотношениями |
Afc=v + |
1, |
(р + |
1) Д0 + |
/?Д, + |
... + Д Р = |
s. Вос- |
|
*=0 |
|
|
|
|
|
|
|
|
пользовавшись формулой Стирлинга |
m\ — V2р.т |
е ^ 12т , спра |
ведливой для любого целого т > |
0 , |
можем записать: |
|
8(п) = min 1 / |
(2«)к+*П ‘ |
|
|
|
|
|
|
й |
г |
|
|
|
|
|
|
|
|
|
* = 0 |
|
|
|
|
|
|
> е —(v + <) min Д |
= |
е -(»+ !) exp < min |
Дк 1пД„ |
( П ) |
|
|
k=o |
|
|
|
|
I й |
*=о |
|
|
В формуле (11) минимум определяется по множеству целых поло жительных чисел Ak, этот минимум может только уменьшиться, если его вычислить по множеству любых положительных чисел Ak, поэтому
g ( r t ) > e - ( v + , ) exp j m i n £ ' д к 1п д к| . |
(12) |
Здесь штрих у знака суммы означает, что минимум берется по лю бым положительным Ah
р
Найдем минимум Д^ In при условиях
k=0
р |
|
2 Ai = v + 1 , |
(13) |
i= 0 |
|
(P + О До + P&i + •••+ Лр = s. |
(14) |
Воспользуемся методом неопределенных множителей Лагранжа и будем искать безусловный минимум функции
О (Д0, Ai, .... Др) = ^ j |
Aft In Ajt -f- p-j |
X Ah •—(v + 1) + |
ft=o |
, ft= 0 |
p |
|
|
+ 1^2 2 |
( P + 1— A) Afc |
s , |
ft=o |
|
|
где |xb p.2 —множители Лагранжа.
Условие экстремума состоит в равенстве нулю частных произ
водных |
dG |
|
|
|
|
|
|
1ч Ah + |
1-f- |
— Р-2^ = О, |
(15) |
|
dAh |
дЮ |
ft — 0 , 1 .......... р |
|
|
|
__ |
1 |
то имеет |
место экстремум-минимум. |
Поскольку ■^2— |
----- д— > 0 , |
Из системы равенств (15) получаем: |
|
|
|
|
|
Ah=Aoqht k = 0, |
1 , |
.. •. Р, |
(16) |
где приняты обозначения: |
|
|
|
|
|
|
Д„ = |
е -< 1+Ч |
|
|
(17) |
|
|
q = е^2. |
|
|
(18) |
Итак, минимум достигается в том случае, когда длины отрезков разбиения Ah распределены по геометрической прогрессии со знаме нателем q, который, как это следует из (18), может принимать толь ко положительные значения. Неизвестные параметры геометрической прогрессии Ао и q выбираются так, чтобы выполнялись условия (13), (14), что приводит к следующим уравнениям для Д0 и q:
До 2 Я* = v + 1 ■ Д0 2 ( Р + I — k) qh = s, ft= 0 ft= 0
или, если провести несложные преобразования и ввести обозначения
A= Ao/(v+l), / = s / ( v+l ) ,
р
А 2 Як = |
1. |
(19) |
ft= 0 |
|
|
р |
|
|
А 2 kq* = р + |
1 — I. |
(20) |
ft=o
Для значений я ф \ уравнения (19), (20) можно переписать в виде
А(‘7р +1— 1)1(Я— 1) = ,1. |
(21) |
Aq[pqv+i—(p+l)qv + l\l( q—1)2= р +1 —/. |
(22) |
