Вводя новые обозначения |
i\ = %b-u |
t.2= Л |
....... |
£ь—1= Xi, |
получим |
следующее выражение: |
|
|
|
|
|
|
|
|
|
= я |
|
о |
Г 'Ь-2 |
С)> СЬ = |
|
|
|
'гV +ь1- 1' ‘ь- 1 |
Iз |
|
|
|
|
|
|
(v + 1)! |
|
|
(6) |
((2 |
ч)! |
•• • |
|
(Ч>-1 |
Ч - 2 )! (v + 1— h - \ ) l |
|
|
Каждому слагаемому |
этой |
суммы |
соответствует |
набор |
чисел Ч, |
/2, . • ., it.—1, подчиняющихся условиям |
|
|
|
|
6-1 |
|
|
|
|
|
|
|
2 |
/ , |
= |
S - ( v + l ) |
|
|
(7) |
6=1 |
|
|
|
|
|
|
|
0 < i i < i 2< . .. s £ iV is £ v + l |
|
(8) |
или, что то же самое, некоторое разбиение (назовем его разбиением типа Т) отрезка ,[0, -v+1], подчиняющееся тем же условиям (рис. 1). Поэтому количество слагаемых в сумме (6) равно числу различных
разбиений типа Т отрезка [0, v+1]. Последнее заведомо меньше, чем число всевозможных произвольных разбиений отрезка [0, v + 1] b— 1 точками (Ч, г2, ..., ib-1) без учета дополнительного условия (7).
Найдем это число.
|
|
■ |
|
|
^ |
-У* ^ |
|
Л ^ |
Л»/* |
if-.- |
|
it-г |
|
1 |
У*? |
|
|
Рис. 1. |
|
|
|
|
|
|
Представим себе, что у |
нас имеется v + b |
элементов |
со |
следую |
щими надписями: на первых |
v + 2 элементах |
нанесены |
цифры 0, 1 , |
2 , ... , v + 1 , на оставшихся |
b—2 элементах |
сделаны надписи «г2 со |
впадает с Ч», «(з совпадает |
с |
г2», • • •, |
«*ь—i |
совпадает с г'г,-2» и про |
изводится выборка b—1 элементов из этих |
v + b |
элементов. Число |
таких различных выборок равноС’*“ ^ . |
Нетрудно заметить, |
что каж |
дой выборке соответствует единственное разбиение отрезка (О, v+1]. Действительно, пусть выбраны какие-то b—1 элементов; поскольку число элементов с надписями типа «(2 совпадает с Ч» равно b—2 , то
влюбой выборке присутствует элемент с цифровой надписью. Упорядочим множество чисел, нанесенных на элементы выборки,
впорядке возрастания. В качестве точки разбиения Ч выберем пер
вое |
из этих чисел и нанесем Ч на отрезок [0, |
v + 1], |
затем |
проверим, |
нет |
ли в выборке элемента с надписью «£2 |
совпадает с |
Ч». |
Если |
такой элемент имеется, то наносится вторая |
точка |
разбиения |
i2= iь |
если же такой элемент отсутствует, то в качестве i2 берется следую
щее по величине число. Далее проверяется, нет ли в разбиении
элемента с надписью «Ч совпадает с г2» и т. |
д.; таким образом, по |
выборке осуществляется |
однозначное разбиение отрезка [0 , |
v + 1]. |
Справедливо и обратное: по конкретному |
разбиению однозначно |
образуется |
выборка из |
указанных |
v + b элементов. |
Значит, |
число |
различных |
произвольных |
разбиений |
отрезка |
[0, v + 1] |
равно |
С^+1 |
и, следовательно, число разбиений типа Т отрезка [0, v+1], подчи-
няющихся условиям (7), (3) (и число слагаемых в сумме ( 6 ) ) , не
превышает величины |
|
откуда получим, |
что |
|
|
|
|
|
|
Q?b,v |
|
|
|
|
|
|
1)! |
|
|
|
|
|
. |
(9) |
min [tj! (i2— г,)!... (г'ь_ 1 — ib_ 2)! (v + |
1 |
|
h - \ ) V |
|
|
т |
|
|
|
|
|
|
|
типа Т отрезка |
Здесь минимум |
берется |
по |
различным |
разбиениям |
[О, v+1]. Если |
теперь обозначить |
интервалы |
разбиения |
через |
/i = i‘i, |
/2— 1*2—h, ■■■, |
jb- 1 —ib-i—h - 2. j b = v + 1—1ь -1, то |
|
|
|
|
|
|
|
|
|
|
|
|
min [/x! /2! ... /b!j |
’ |
|
|
|
|
|
( 10) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
т |
|
|
|
|
|
|
|
|
|
причем |
разбиение |
T определяется |
соотношениями |
(5,а), |
что |
и тре |
бовалось доказать. |
|
|
|
что для любого п > п 0 |
|
|
Лемма 3. Существует па такое, |
|
|
|
|
ь |
|
________ (у + |
1 )!________ o- 0/ 12(v+ l) |
|
|
|
|
|
|
|
|
|
|
|
m in П W > (2/ _ 1)У+У2л(у + Г) 6 |
|
|
|
|
|
|
|
к=\ |
|
|
|
|
|
|
|
|
|
|
|
|
|
где 0 < 0 < 1 , |
s = a2n, v = p2n, |
b= 2n/2, / = s / ( v + l ) , |
а |
и |
(3 — постоян |
ные, подчиняющиеся соотношению 1/2> !а ^ |3 ^ 0 . |
у = |
h H h —hV- |
Д о к а з а т е л ь с т в о . |
Рассмотрим |
функцию |
|
|
|
|
|
|
ь |
|
|
|
|
|
|
|
|
|
. .. (tb- i |
— г'ь-2)(у + |
! — |
|
|
и |
оцеинм |
величину |
g (п) = |
|
|
|
|
|
|
к = \ |
|
|
|
|
|
|
|
|
|
= min у, |
когда |
y = |
p2 n, s = |
a.2n, |
b — 2 " /2 ; |
а |
и |
р — постоянные, |
т |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
подчиняющиеся |
соотношению |
|
|
[см. |
неравенства |
|
(7.3), |
(7.4)]. При выбранных нами значениях s, v, b всегда существует разбиение типа Т. Среди разбиений типа Т всегда найдется разбие ние Т*, обращающее функцию y(ii, 12, ... ib-i) в минимум; назовем
такие разбиения минимальными. Выясним некоторые свойства и вид
минимальных разбиений Т*. |
|
|
число п0, |
|
|
|
|
|
Свойство |
2. |
Существует такое |
что при произвольном |
п > п0 любое |
разбиение |
типа |
Т содержит |
не менее |
[1 — V 2 (а—(S) — |
—2~ п/2] 2п!2 |
совпадающих точек. |
Пусть |
некоторое |
разбиение |
Р |
(не |
обязательно |
типа |
Т) |
содержит р |
различных точек |
разбиения. |
Оче- |
|
|
|
|
|
|
|
|
|
|
|
6 - 1 |
|
|
|
|
|
|
видно, |
наименьшее |
значение суммы |
Д при |
этом |
достигается при |
|
|
|
|
|
|
|
|
|
|
|
k= 1 |
|
|
|
|
|
|
разбиении |
П = |
h = |
••• = k - p - 1 |
— 0 , |
ib- v — \, |
гь_ р+1 = |
2 , ... |
1 ъ - \ ~ |
p |
(рис. |
2); |
оно |
равно |
р ( р - \ - \)/2 . В \разбиении |
типа |
Т \ |
|
|
|
|
|
|
|
|
|
р { р + |
1 ) |
6-1 |
|
|
|
|
|
содержащем р различных точек, |
ЧП |
|
— (v + |
1). Уси- |
------^------ < |
7 , /h< s |
к = 1
ливая неравенство, получим, что в разбиении типа Т
4 г < ( * — Р)2"- P < V 2(а — р) .2"/2,
Поскольку 7 г > а^ |
Р > 0 , |
то, начиная с п0 = 2 log Г1 — V 2 (а—В)]-< |
р < . Ь — 1 для всех |
п ^ |
п0. |
|
Следовательно, начиная с «0, разбиение типа Т обязательно со |
держит совпадающие (кратные) |
точки разбиения. Число таких точек |
не меньше, чем |
|
|
|
Ь— 1 — р — Х2п>2, где |
X = 1 — У 2 (а — р)— 2~"/2. |
Свойство 3. Минимальным |
является разбиение Т*, в котором |
вес совпадающие точки сосредоточены не более, чем в двух смежных точках.
^Ь-р-1
I |
LЬ-р |
^b-p+1 |
lb-p+i |
h -т |
/ |
2 |
J |
|
о |
Р > |
|
|
|
Рис. |
2. |
В подтверждение этого свойства рассмотрим минимальное раз биение Т* и на (0, v + l ] выделим отрезок, ограниченный крайними кратными точками А, В (рис. 3). Пусть в точке А находится кА совпадающих точек, а количество совпадающих точек в точке В равно кв и пусть для определенности kA^ .kn. Перейдем от Т* к но вому разбиению Тр, которое получается из исходного, если кА—I точек переместить из Л в Л + I и одновременно кА— 1 точку пере нести из В в В— 1.
Разбиение Т*, |
является разбиением |
типа |
Т, так как при сделан- |
|
|
ft- 1 |
|
|
ных преобразованиях'сумма |
/h осталась прежней. Более того, если |
|
|
*=1 |
|
|
исходное разбиение |
было минимальным, |
то и |
полученное разбиение |
Т1* также является минимальным, поскольку сделанные преобразо
вания не увеличили длины ни одного отрезка.
Операцию сближения крайних совпадающих точек можно про должить, причем на каждом шаге преобразований получатся разбие ния Т*, а расстояние между крайними совпадающими точками будет уменьшаться. Не позднее, чем после (В—А—1)-го преобразования возникнет минимальное разбиение Т*в -А- и содержащее либо одну кратную точку, либо две смежных кратных точки (рис. 3). В даль нейшем процесс сближения кратных точек ни к чему не приводит, так как смежные кратные точки (если их две) начинают переходить друг в друга. В доказательстве ничего не изменится, если kB< k A. На основании этого свойства в качестве минимального разбиения Т* можно рассматривать такое разбиение, при котором все совпадаю щие точки сосредоточены либо в одной какой-либо точке, либо
в двух смежных точках. Будем обозначать такие минимальные раз биения через Т*.
Свойство 4. Если минимальное разбиение Т* содержит лишь
одну |
кратную точку и эта точка не |
принадлежит концам отрезка |
[О, v + |
1], то граничный с ней отрезок |
разбиения Т* равен 1. |
|
Предположим противное. Пусть все совпадающие точки (рис. 4) |
разбиения Т* |
находятся |
в точке /1 (0 < /I< v ) и пусть |
соседний (для |
определенности правый) |
отрезок / разбиения Т* имеет длину / боль- |
|
кА точек |
|
|
Т* |
квточек |
|
_ L . |
-V — |
« ------Ф |
|
V - _1_ |
О |
А |
|
|
|
|
в |
0+ 1 |
|
|
|
|
|
(Ке-кА+1)точка |
-1--------- . — @— .——@------ |
-«—W—— I— |
О |
А |
АН |
|
|
8-1 |
В |
0*1 |
|
|
|
|
|
Т* |
|
|
|
|
|
|
|
I В - А - 1 |
|
|
О |
|
—'— @— ©■— •--------------•— |
|
0 +1 |
|
|
|
|
|
|
|
|
|
|
Рис. 3. |
|
|
|
|
|
— L— |
J |
|
|
_1_ |
О |
|
А +1 |
------------------------ |
|
|
8-1 |
А |
|
|
0+ 1 |
JL |
|
|
|
|
|
|
|
О |
|
8 —1 |
А |
А + 1 |
|
|
9 +1 |
|
|
|
|
Рис. 4. |
|
|
|
ше I. Рассмотрим новое разбиение Ту, получающееся из Т*, если |
одну |
из совпадающих точек |
перенести из точки А |
в точку |
Л + 1 , |
а еще одну совпадающую точку перенести в точку А— 1, что |
всегда |
можно осуществить, так как по предположению точка А находится
внутри |
отрезка [0, v + 1] (рис. 4). |
При этом Тi является снова раз- |
|
|
6 - 1 |
|
биением |
типа Т, так как сумма |
2 |
осталась прежней. Вместо |
|
|
6=1 |
|
отрезка / в разбиение Ту входят два отрезка длиной |
1 и /— 1, а дли |
ны остальных отрезков разбиения не увеличиваются, |
следовательно, |
в функции y(ju |
j b) = /i! /2! .. . /ь! множитель |
/! |
заменяется на |
два сомножителя |
1! (/—1) 1< /! (поскольку / > 1). |
Величины осталь |
ных сомножителей не увеличатся, и, следовательно, значение функ ции у на разбиении Ту будет меньше ее значения на разбиении Т*, что противоречит минимальности Т*. Следовательно, соседние с крат ной точкой отрезки должны обязательно иметь единичную длину.
Свойство S. Если минимальное разбиение Т* содержит две крат ные смежные точки и ни одна из них не совпадает е концами от резка (0, v + 1], то граничные с кратными точками отрезки разбиения
Т* равны 1.
Это свойство доказывается так же, как и свойство 4. |
в любой |
Свойство 6. Существует по такое, что для любых п>по |
последовательности отрезков разбиения Т*, |
включающей |
не более |
Я2 тг/2 отрезков (Х,= 1— \/Г2(а—'Р)—2 - "/2), не |
может быть |
двух от |
резков, отличающихся по длине более, чем на 1, если только ни одна
из кратных |
точек разбиения Т* не |
принадлежит |
концам отрезка |
[О, v+ 1]. |
|
|
|
|
|
Допустим противоположное. Пусть в Т* существует последо |
вательность отрезков, |
включающая не более Я2 ЭТ/ 2 |
отрезков и содер |
жащая два |
отрезка, |
длины |
которых |
отличаются |
более, чем на 1. |
|
|
J k |
J k t t |
Jk+ p -1 |
Jk+p |
|
|
Рис. 5. |
|
|
|
Выделим |
из этой |
последовательности |
подпоследовательность jk, |
Д + 1....... |
jk+p-u jk+p, начинающуюся |
в одном |
из таких |
отрезков |
jk и кончающуюся |
в другом отрезке jk+p, при |
этом |
2"/2. Для |
определенности будем считать jk+p^jk + 2.
Рассмотрим новое разбиение Т\, получающееся из Т* смеще нием всех точек разбиения (за исключением крайних) внутри под последовательности jk,..., jk+p на единицу вправо и смещением р—1 совпадающей точки из кратных точек на 1 влево (рис. 5). Это всегда можно осуществить, так как общее количество совпадающих точек, согласно свойству 2, не менее Х2п/2 и по предположению крат ные точки находятся внутри отрезка (0, v+1]. Получается новое раз биение Т1, являющееся разбиением типа Т, поскольку проведенные
преобразования не изменили 2
*=1
Вместо подпоследовательности jk, jk+1, • • •, jk+p - |
i , jk+p |
разбие |
ния T* |
в разбиение |
войдет |
подпоследовательность |
/*+ 1, |
jk+ь . •., |
jk+p-> |
jk+p—1 и остальные |
отрезки не увеличат своей длины. По |
этому в функции у |
вместо сомножителей Д! Д +i! ... |
Д+р! |
появятся |
сомножители |
|
|
|
|
(Д + 1)! Д-ц! • • • Д + p - i U /m -p — 1)! =
=[(ih+m(jh+p)]ih\jk +^ ■■• Д + р !<
<Д ! Д +i! ■■• Д+р!,
поскольку Д + р > Д + 2, а остальные сомножители не возрастут. Сле довательно, на разбиении Г, будет достигаться меньшее значение
