Доказательство теоремы 2.
Рассмотрим еще один (третий) спо-
соб вложения, обобщающий рассмотренный ранее вспомогательный
способ. Он состоит в следующем.
1. Разбиваем отрезок
x
n
на отрезки
˜
x
r
i
= [
x
r
i
−
1
+1
, . . . , x
r
i
]
, i
= 1
, . . .
. . . , k, r
0
= 0
.
2. Если отрезок
˜
x
r
1
может быть вложен с допуском
d
в нач ало
последовательности
y
, то выбираем из всех возможных способов тот,
в котором знак
x
r
1
“вставлен” наиболее близко к началу последова-
тельности
y
. Если отрезок
˜
x
r
1
не может быть вложен с допуском
d
в
начало последовательности
y
, то считаем, что последовательность
x
n
не вкладывается третьим способом в
y
.
3. Далее используем рекурсию. Пусть отрезок
[
x
1
, . . .
. . . , x
r
1
+
...
+
r
j
]
, j
1
,
уже вложен третьим способом в начало последо-
вательности
y
, причем знак
x
r
1
+
...
+
r
j
“вставлен” в последовательность
y
на
t
x
r
1 +
...
+
r j
-м месте. Если отрезок
˜
x
r
j
+1
может быть вложен с допус-
ком
d
в начало последовательности
[
y
t
x r
1 +
...
+
r j
+1
, y
t
x r
1 +
...
+
r j
+2
, . . .
]
, то
выбираем из всех возможных способов тот, в котором знак
x
r
1
+
...
+
r
j
+
r
j
+1
“вставляется” наиболее близко к началу последовательности
[
y
t
x r
1 +
...
+
r j
+1
, y
t
x r
1 +
...
+
r j
+2
, . . .
]
. Присоединим результат вложения от-
резка
˜
x
r
j
+1
к результату вложения по третьему способу отрезка
[
x
1
, . . . , x
r
1
+
...
+
r
j
]
и получим вложение по третьему способу отрез-
ка
[
x
1
, . . . , x
r
1
+
...
+
r
j
+1
]
.
Если отрезок
˜
x
r
j
+1
не может быть вложен с допуском
d
в нач а-
ло последовательности
[
y
t
x r
1 +
...
+
r j
+1
, y
t
x r
1 +
...
+
r j
+2
, . . .
]
, то сч итаем, ч то
отрезок последовательности
x
n
не вкладывается третьим способом в
начало последовательности
y
.
Отметим несколько важных свойств третьего способа вложения.
1. Если отрезок последовательности
x
n
вкладывается в начало по-
следовательности
y
с допуском
d
вспомогательным третьим способом,
то он вкладывается в ее начало и основным способом вложения с до-
пуском
d
.
2. Если вкладываемый отрезок
x
n
= [
a, . . . , a
]
состоит из одинако-
вых знаков и вкладывается в начало последовательности
y
с допуском
d
, то он вкладывается в ее начало и третьим способом. Действительно,
множество
{
1
i
(
d
+ 1)
n
:
y
i
=
a
}
состоит не менее, чем из
n
элементов, причем первые
n
из них удовлетворяют условию вложения
с допуском
d
. Следовательно, отрезок
x
n
может быть вставлен именно
на эти первые места. Это означает, что
x
n
вкладывается в
y
третьим
способом.
8
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2012. № 2
