\input style
\chapno=5\subchno=2\chapnotrue
\subchap{��⨬��쭠� ���஢��} % 5.3

⅏���, ����� �� ���������������� ����� ��������� ������� ����������
����������, ������ ����� ���������� � ����� ������ �������: \emph{�����
����� ���������� ���������� ���������?} ᓙ������� �� ����� ������� ������
�������� ����������, �������� �� �� ��� ������� �� ���� �����������, ���
�� ������� �� �� ���?

����������, ���������� ���������� ������� ���������� \emph{���}; �� ������
����� ����������, ��� �������� ��� ������ "���������", �� �� ����������
���������� ���������� ������� ���������� ����� "���������". �����������
������� �� ������������� ���������� �� ��������� � �.~4.3.3, 4.6.3
�~4.6.4, ��� ��������������� ��������� � ������� ��������� � ����������
���������. � ������ ������, ��� ���� ����� ����������� �������
"�������������", �.~�.\ ����� ������ ����� ����������, ���������� ����
�������������� �������� ������� ����������� ���������, "���������� ��
���������". � � ������ ������ ����� ���� �������� ������������� ������,
��������� �������, ��� ��� �� ��� ��� ��������� �� ������.   �� �������
���� � � �����������: ���� �������� ��������� ���������� ����������, ��
�������� ��� ����� ����������� ��������, �� ������� �� ��� ��� ��� �������.

�������� ����������� ��������� ������� ���������� ������ ���� ����������
�� ����������� ����� ��������� ������ ��� ���������� $n$~���������, ���
������� $m$~��������� � $n$~����������, ��� ������
$t\hbox{-�o}$~����������� �������� �� ���������������� ������
$n$~���������. � �.~5.3.1, 5.3.2 �~5.3.3 ��� ������� ����������� � �����
������; � �.~5.3.4 ��������������� ����������� ������� � ����������
������������: ������������������ ��������� ������ ����, �� ��������,
������� �����������. ��������� ������ ���� ���������� �������������
��������, ��������� � ����������� �����������, ����� ����� � �����������
� �.~5.3.4 � � ���������� ������� ���������� � �.~5.4.4.

%% 219

\subsubchap{᎐������� � ����������� ������ ���������} % 5.3.1

��������, ����������� ����� ��������� ������, ����������� ��� ����������
$n$~���������, �����~\emph{����,} ���������, ��� �� ������, ����������
������ ����������� ����������, � ������� ������ �� ����������� ���������.
 � ����� ����, ����� �������� \MIX-���������, ��������� ����������� � ��
���������� ��� �� ����� �� ����� ������� ���������
��������! (�.~���.~5-6 � ������ ���� �����.) �� ����� ����������� �
����������� �������� ����������, �������, �� ��������, ���� �������� ��
��������� ������, �� ����� ������ ������� �� ���� ������������ �������
���������, ������, ��� ����������� ������, ��������������� �������� �~�.~�.

������� ����, ��� ������� ����� ���������---�� ������������ ������
�������� ������������� ������ ����������. ������ � ����� ������
�������������� �������� ���������� ������������ ����� ���������,
��������� ������������� �������� ����� ������� �������� ��� � ������� ���
���� ���������� �� ���������� ������� ��������� ����������, � �����
������� �������� ���������� ��� ������� ����� ������������ �����,
������� ����� ������ ����� ���� � �������.

璎�� ��������� ����������� ����������, ��� ������ �� �����������
���������, ����������� ����������� ������� ����������, ���������� ������
�� ����������� �������� ��������� ������� "$<$" ����� �������,
������������� � ������ ���� �����. ��� �������� �� ����� ��������� ����
���������� ������� \emph{���������} ������, � ��� ������, ��� ��� �����
��������� ������~$K_i$ �~$K_j$ �������� ���� ��� ������: ����~$K_i<K_j$,
����~$K_i>K_j$. (��������������� ���� ������ �� ����� ������, �����
����������� ������ �����, ��.~� ���.~��~3 ��~12.)

������ ���������� ����������� ��������� ����� �������������� �����
������� �������������� ���������. ���� ���� $n$~������ � ���� � �����
������, �� ������ ����������� ����� �����������, ����������� ��� ����,
����� ����������� ����� �� ������� � ������������ � �����, ���� � ������
���� ����� ���������� ������ ���� ����? ��� ��, ���� � ��������� �������
��������� $n$~�������, �� ������ ���������� ����� ���, ����������� ���
����, ����� ������������ ����� ����� �������������� � �������������, ���
���� ������� ����� ������� ����������� (�������� ���������� �� �����������).

������ ���������� $n$~���������, ��������������� ��������� ������������,
����� ����������� ����������� ��������� ������������ ��������� ������,
������, ��� �������� �� ���.~34. ������ \emph{���������� ����}
(������������ � ���� ��������) ��������
%%220
��� ������� "$i:j$" � �������� ��������� ������~$K_i$
�~$K_j$. ����� ��������� ����� ���� ������������� ����������� ����������,
������� ���������� ���������, ����~$K_i<K_j$, � ������ ���������---���
���������, ������� ���������� ����������� � ������~$K_i>K_j$. ������
\emph{������� ����} ������ (������������ � ���� ��������������) ��������
������������ $a_1$ $a_2$~\dots $a_n$
\picture{���.~34. ������ ��������� ��� ���������� ���� ���������.}
���������~$\set{1, 2,~\ldots, n}$, ������������ ��� ����, ���
���� ����������� ������������
$$
K_{a_1}<K_{a_2}<\ldots<K_{a_n}.
$$
(���� ��������� �� ���� �� ����� � ����� �������� ����, �� ������ ��
$n-1$~����������� $K_{a_i}<K_{a_{i+1}}$, ���~$1\le i < n$, �����
����������� ���������� ���������~$a_i:a_{i+1}$ ���~$a_{i+1}:a_i$ �� ���� ����.)

 , �� ���.~34 ����������� ����� ����������, �������� �������� �����
������� ��������~$K_1$ �~$K_2$; ����~$K_1>K_2$, �� ���������� (��������
�� ������� ���������) ����������~$K_2$ �~$K_3$, � �����, ����~$K_2<K_3$,
��������~$K_1$ �~$K_3$; �������, ����~$K_1>K_3$, ���������� ����,
���~$K_2<K_3<K_1$. �������� �������� ���������� ������ ����� �����
���������� ����� �� �����, �� ��� ���������� ������ ���������, ������� ��
���������� ��� ����������� ������. ��� ���������~$K_i$ �~$K_j$ � ����
������ ������ ������� � ���� \emph{��������} �����~$K_i$ �~$K_j$, � �� ��
�����, ������� ����� ������~$i\hbox{-�}$ �~$j\hbox{-�}$ ������� � �����
� ���������� ����������� �������.

�������� � ���������� ���������; ��������, �� ���.~35 ��� �������������
����������~$3:1$, ��������� �� ����������~$K_1<K_2$ �~$K_2<K_3$
�������~$K_1<K_3$. ������� ������������ �� ����� ��������������� ������
��������� ����~$\elnode{3:1}$ �� ���.~35, ��� ��� ��� ����� ���������
������� �� ����� �����������! ��������� ��� ���������� ����������� �����
���������, �� ����� �������, ��� ���������� ��������� �� ������������;
� ����� ������� �� ����� ����� ���� �� ���������� ������������
%%221
��������� ������, � ������� ������� �������� ���� �������������
��������� ������������. ��� ������������ �������� ������ ��������, �
������ ������������ ���������� ������������ ���� �� ����� � ��������
����; ������ ��������, ��� \emph{� ������ ��������� ��� ����������
$n$~��������� ��� ���������� ��������� ������� ����� $n!$~������� �����.}

\picture{���. 35.            ������ ����������� ���������.}

\section ����������� � ��������� ������. ������ ������������
������� ����������� ������---����� ������� ���������, ��������������
\emph{������������} ����� ����������� ���������. (����� �� ����������
\emph{�������} ����� ���������.)

����� $S(n)$---����������� ����� ���������, ����������� ��� ����������
$n$~���������. ���� ��� ���������� ���� � ������ ��������� ������������� ��
������� $<k$, �� ��������, ��� � ������ �� ����� ���� ����� $2^k$~�����.
ዅ����������, �������~$k=S(n)$, �����
$$
n!\le 2^{S(n)}.
$$
��������� $S(n)$---����� �����, �� ����� �������� ��� �������  �����,
������� ������ ������:
$$
S(n)\ge \ceil{\log_2 n!}.
\eqno(1)
$$
�������, ��� �� ������� ᒈ������
$$
\ceil{\log_2 n!}=n\log_2 n-n/(\ln 2)+{1\over2}\log_2 n+O(1);
\eqno(2)
$$
�������������, ���������� ��������� ����� $n\log_2 n$~���������.

ᎎ��������~(1) ����� �������� "���������-�������������� ������ �������",
��������� ���������� � ������� ������ ���������� ������ ��, ��� � ��������
���������� ����������� $(\log_2 n!)$~"����� ����������"; ������ ���������
���� �� �����  ������ "���� ����������".  �� �������, ��� �� ���.~34,
�������� ����� "������������" ("questionnaires"), � �� ��������������
�������� ����������� � ����� ����� ������ Th\'eorie des questionnaires
(Paris: Gauthier-Villars, 1965).
%%222
�� ���� ������������� ���� ������� ���������� ��� ������ ������� ������
����� ���������: �������� ������� (��.~�~�.~5.2.1), ����� �� ������
(��.~�~�.~5.2.3) � ������� ����������� �������, ��� ��� ������� �
���������~5.2.4L. �������� ������, ��� ������������ ����� ��������� ���
������ �������� ������� �����
$$
B(n)=\sum_{1\le k\le n} \ceil{\log_2 k}=n\ceil{\log_2 n}-2^{\ceil{\log_2 n}}+1
\eqno(3)
$$
(��.~�~���.~1.2.4-42), � ������������ ����� ��������� ���
���������~5.2.4L ��������� � ���.~5.2.4-14. ����������� (��.~�.~5.3.3),
 ��� ��� ������ �� ������ ������� ������ ����� ��������� ���� ����� ��,
��� ��� �������� �������, ���� ����� ��, ��� ��� ������������ �������, �
����������� �� ����, ��� �������� ������. �� ���� ���� ������� �����
��������������� ��������~$n\log_2 n$; ��������� ������� � ������ ������
���~$S(n)$, �������, ���
$$
\lim_{n\to\infty} {S(n)\over n\log_2 n}=1.
\eqno(4)
$$
 �� �������, �� �������� ������������ ������� ���~$S(n)$, ������
���������� ����� ����� ������ ����������. � ��������� ������� ���������
�������� ��������� ���� ������� ��� �����~$n$:
\ctable{
\hfill$#$\bskip && \hfill$#$\bskip\cr
               n=1 & 2 & 3 & 4 & 5 &  6 &  7 &  8 &  9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17\cr
\ceil{\log_2 n!}=0 & 1 & 3 & 5 & 7 & 10 & 13 & 16 & 19 & 22 & 26 & 29 & 33 & 37 & 41 & 45 & 49\cr
            B(n)=0 & 1 & 3 & 6 & 8 & 11 & 14 & 17 & 21 & 25 & 29 & 33 & 37 & 41 & 45 & 49 & 54\cr
            L(n)=0 & 1 & 3 & 5 & 9 & 11 & 14 & 17 & 25 & 27 & 30 & 33 & 38 & 41 & 45 & 49 & 65\cr
}
�����~$B(n)$ �~$L(n)$ ��������� �������������� � �������� �������� �
������� �������. ����� ��������, ���~$B(n)\le L(n)$ ��� �����~$n$ (��.~���.~2).

��� ����� �� ����������� ���� �������, $S(4)=5$, ��~$S(5)$ ����� ���������
����~7, ����~8. � ���������� ����� �������� � ������, ������������ �
������~\S~5.2. ����� ��������� ������ ���������� ���� ���������? ��������
�� ���������� ���� ��������� ��� ������ ����� ���� ���������?

 �� ���������� ��������, �� ��� ������ ����� �� ��� ������. �������� ���
��, ��� ��� ���������� ������� ��������� ����������� �������, ���������
������~$K_1:K_2$, �����~$K_3:K_4$, � ����� ���������� �������� ����� ���.
품 ��������� ��������� ������������, ������� ����� ���������� ����������
\picture{���. ���. 222}
%%223
������������, ���~$a<b<d$ �~$c<d$. (��� ������������� ���������
��������� ������� ����� ���������� ������ ��������������� �������������
�������, ������, ��� ����, ��� �����������~$x<y$ ��������� ���������
����� � ������ �����, ����� �� ����� ���� ���� ��~$x$ �~$y$.) ⅏���
��������� ����� �������~$K_5=e$ � ��������������� ����� �����~$\set{a, b, d}$;
��� ����� ��������� ����� ��� ���������, ��������� ����� ��������
��� ������� �~$b$, � ����� �~$a$ ���~$d$.  �� �������, �������� ���� ��
������� ������������:
\picture{p.223}
� � ������ ������ ���������� ��� ���� ���������, ����� ��������~$c$ �
������� ��������� ���������, �������~$d$.  �� ������ ���������� ����
��������� ������� ��������� �.~�.~����� [Ph.~D.~thesis, Stanford
University (Oct., 1956). 41--43].

\section ᎐������� ��������� � ��������. ������� ��������� �����������
���� ������ ����������� ������� 䎐��~��.\ �~ᅋ����~�.~��������.
��������� ��� ���������� ��������� ����������� ���� �������� ����������:
����������� ������� � ����������� �������, �� �� ������� ���� �����
\dfn{����������� ��������� � ��������.} ����������, ��������, ������
���������� 21~��������. ������ ����� �� ��������� ������ ���
������~$K_1:K_2$, $K_3:K_4$,~\dots, $K_{19}:K_{20}$, ����� �������
������������� ��������� � �������� ������� �������� ���. � ����������
������� ������������
\picture{223.2}
�����������~(5). ዅ������ ��� ������� � ���, ����� ��������
�������~$b_3$ � ������������������~$\set{b_1, a_1, a_2}$, � �����~$b_2$---�
������������������ ��������� ���������, �������~$a_2$, �������� � ������������
\picture{223.3}
������� ������� �������� \dfn{������� ��������.} 틅����~$b_5$
����� �������� � ������� ������� �� ��� ��������� (������� ��� �������
�~$c_4$, ����� �~$c_2$ ���~$c_6$ �~�.~�.); ����� ��� �� ��� ���������
����� ����������� � ������� �������~$b_4$, ��� ��������
%%224
� ������������
\picture{224.1}
ዅ������ ��� ��������; ���� �� ���, ��� ������ ������? ��� ������ �����
������� ��������� ���������~$b_{11}$ (� \emph{��}~$b_7$) � ������� �������.
 ����� ����� ��������~$b_{10}$, $b_9$, $b_8$, $b_7$, $b_6$ (������ � �����
�������) ����� �������� � ������ ����� � ������� ������� �� ����� ��� ��
������ ��������� ������.

���������� ������� ����� ��������� ��������� ����������, ��� 21~�������
����� ������������� �� ����� ��� �� $10+22+2+2+3+3+4+4+4+4+4+4=66$~�����.
���������
$$
2^{65}<21!<2^{66},
$$
���� �����, ��� � � ����� ������ ������ ���������� �� ����� 66~���������;
�������������,
$$
S(21)=66.
\eqno(10)
$$
(��� ���������� ��������� ��������� ������������ �� 74~���������.)

� ����� ������ ���������� ��������� � �������� ��� $n$~���������
�������� ��������� �������:
\medskip
\item{i)}~���������� ��������� $\floor{n/2}$~����������������
��� ���������. (���� $n$~�������, �� ���� ������� �� ��������� � ����������.)

\item{ii)}~������������� $\floor{n/2}$~�\'������ ��������� ���,
��������� � ����~(i), ��������� � ��������.

\item{iii)}~��� ��������� ������ ����������� $a_1$, $a-2$,~\dots,
$a_{\floor{n/2}}$, $b_1$, $b_2$,~\dots, $b_{\ceil{n/2}}$, ��� �~(7),
���~$a_1\le a_2 \le\ldots\le a_{\floor{n/2}}$ �~$b_i\le a_i$
���~$1\le i \le \floor{n/2}$; �������~$b_1$ � ��� ��������~$a$ "�������
��������". �� ������ ���������~$b_j$ ���~$j>\ceil{n/2}$, ��������
��������� ��������� � ������� ������� ��������� ��������~$b$ � ���������
�������:
$$
b_3, b_2; b_5, b_4; b_{11}, b_{10},~\dots, b_6; b_{t_k}, b_{t_k-1},~\ldots,
b_{t_{k-1}+1};~\ldots\,.
\eqno(11)
$$
��� �������� �� ����������
������������������~$(t_1, t_2, t_3, t_4,~\ldots)=(1, 3, 5, 11,~\ldots)$,
����������� �~(11), ����� �������, ����� ������ �� ���������~$b_{t_k}$,
$b_{t_k-1}$,~\dots, $b_{t_{k-1}+1}$ ����� ���� �������� � ������� �������
�� �����, ��� �� $k$~���������. �������~(7), (8) �~(9), ������� ���������
\picture{224.2}
%%225
��� ������� ������� ��~$a_{t_k-1}$~������������ ��������
$2t_{k-1}+(t_k-t_{k-1}-1)$~���������. 풎 ����� ������ ���� ������~$2^k$;
��� ��� ����� ����� �������� ��� ������~$2^k-1$, � �����
$$
t_{k-1}+t_k=2^k.
\eqno(12)
$$
���������~$t_1=1$, �� ��� �������� ����� ��������~$t_0=1$; �����, ��������
�������������� ����������, ������
$$
\eqalignno{
t_k=2^k-t_{k-1}&=2^k-2^{k-1}+t_{k-2}=\ldots\cr
\ldots&= 2^k-2^{k-1}+\cdots+(-1)^k2^0=(2^{k+1}+(-1)^k)/3. & (13)\cr
}
$$
(���������, ��� ����� ����� �� ������������������ �������� ��� ��������
��������� ���������� ����������� ������ �������� ���� ����� �����; ��.~�~���.~4.5.2-27.)


����� $F(n)$---����� ���������, ����������� ��� ���������� � ���������
��������� � ��������. �, ���
$$
F(n)=\floor{n/2}+F(\floor{n/2})+G(\ceil{n/2}),
\eqno(14)
$$
��� �������~$G$ ��������� ���������� ������, ����������� � ����~(iii).
����~$t_{k-1}\le m \le t_k$, ��, �������� �� ������, ��������
$$
\eqalignno{
G(m)&=\sum_{1\le j <k} j(t_j-t_{j-1})+k(m-t_{k-1})=\cr
&=km-(t_0+t_1+\cdots+t_{k-1}). & (15)\cr
}
$$
�������
$$
w_k=t_0+t_1+\cdots+t_{k-1}=\floor{2^{k+1}/3},
\eqno(16)
$$
� ����� $(w_0, w_1, w_2, w_3, w_4,~\ldots)=(0, 1, 2, 5, 10, 21,~\ldots)$.
� ���.~13 ��������, ���
$$
F(n)-F(n-1)=k \rem{����� � ������ �����, ����� $w-k<n\le w_{k+1}$},
\eqno(17)
$$
� ��������� ������� ������������ ������������
$$
\displaylines{
{2^{k+1}\over 3} < n \le {2^{k+2}\over 3},\cr
k+1<\log_2 (3n)\le k+2;\cr
}
$$
�������������,
$$
F(n)-F(n-1)=\ceil{\log_2\left({3\over4}n\right)}.
\eqno(18)
$$
(풎� �������� �� ������� �.~������ [Ph.~D.~thesis, Univ.~of~Minnesota
(1969), 38--42].) ������ ��������, ��� �������~$F$ ���������� �����������
������� ��������:
$$
F(n)=\sum_{1\le k\le n} \ceil{\log_2\left({3\over4}k\right)},
\eqno(19)
$$
%%226
������� ����� ������ �� ��������������� �������~(3) ��� �������� �������.
� "��������� ����" ��� ����� ����� ����� � ���.~14.

����������������~(19), �������� ��������� ������� ��������
�������~$F(n)$; �����
\ctable{
\hfill$#$&$\hbox{}#$\hfill\bskip && \hfill$#$\bskip\cr
               n&=1 &  2 &  3 &  4 &  5 &  6 &  7 &  8 &  9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17\cr
 \ceil{\log_2n!}&=0 &  1 &  3 &  5 &  7 & 10 & 13 & 16 & 19 & 22 & 26 & 29 & 33 & 37 & 41 & 45 & 49\cr
            F(n)&=0 &  1 &  3 &  5 &  7 & 10 & 13 & 16 & 19 & 22 & 26 & 30 & 34 & 38 & 42 & 46 & 50\cr
\noalign{\smallskip}
              n&=18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30 & 31 & 32 & 33\cr
\ceil{\log_2n!}&=53 & 57 & 62 & 66 & 70 & 75 & 80 & 84 & 89 & 94 & 98 &103 &108 &113 &118 &123\cr
           F(n)&=54 & 58 & 62 & 66 & 71 & 76 & 81 & 86 & 91 & 96 &101 &106 &111 &116 &121 &126\cr
}
�������, ��� ���~$1\le n\le 11$ �~���~$20 \le n \le 21$ $F(n)=\ceil{\log_2n!}$;
����� �������, ��� ���� ��������� ���������� ��������� � �������� ����������:
$$
S(n)=\ceil{\log_2 n!}=F(n) \rem{��� $1\le n \le 11$ �~$20\le n \le 21$}.
\eqno (20)
$$

������ ���������� �������~$S(n)$ �������� ���� 蒅������ �� ������ �������
����� ������������ ����� Mathematical Snapshots   (Oxford   University
Press,   1950),   38--39\note{1}%
{���� ������� ������� ������� ���� �����: �������������� �����������, �.,
�����������, 1949.---{\sl ����. �����.\/}
}). �� ������ �������� �������, ������� �������� ��������� ��������
���������� $n$~��������� ��� �������, ��� $n\hbox{-�}$~������� ��
��������������� �� ��� ���, ���� �� ������������� ������ $n-1$~���������;
� �� ������ ������������� � ���, ��� ����� �������� ������� ��������� � �
����� ������. ��������� ��� ������ [{\sl Calcutta Math.~Soc.\ Golden
Jubilee Commemoration,\/} 2 (1959), 323--327] �� �������, ��� ���� ���
������, �.~␈���� � �.~���, "�������" ���������� ��� ������������� �
����� ��������~$S(n)$ ���~$n\le11$. ��������, ␈���� � ��� ����������
������ � ���������� ��������� � ��������, �� ������� ������ ���������
���������� �.~�.~䎐�� �~�.~�.~�������� [{\sl AMM,\/} {\bf 66} (1950), 387--389].

����� ����������� ���������� ��������� � �������� ������ �����������
��������� �������~$S(n)$ �����~$S(12)$. �� ����.~1 �����, ��� �����~$12!$
�������� ������ �~$2^29$, ������� ������������� 29-������� ���������
���������� 12~��������� ������ ������������. ��� ������� ����� �������
������ 㝋��� ��� ���������� ������������� ����� (�������� ��
�������������� ������ ������~II �����~60~�.), ������� �������,
���~$S(12)=30$
[Proc. IFIP Congress 65, 2 (1965), 497--498]. ����, ��������� ������� �
������� ����������� ����������� � ���~$n=12$.

%%227

\htable{ ���� 1}%
{�������� ����������� � �������� ������� ���������}%
{\hfill$#$&$\hbox{}=#$\cr
1 & 1!\cr
10 &2!\cr
110 & 3!\cr
11000 & 4!\cr
1111000 & 5!\cr
1011010000 & 6!\cr
1001110110000 & 7!\cr
1001110110000000 & 8!\cr
1011000100110000000 & 9!\cr
1101110101111100000000 & 10!\cr
10011000010001010100000000 & 11!\cr
11100100011001111110000000000 & 12!\cr
101110011001010001100110000000000 & 13!\cr
1010001001101111110110010100000000000 & 14!\cr
10011000001110111011101110101100000000000 & 15!\cr
100110000011101110111011101011000000000000000 & 16!\cr
}

\section *����� ��������� ������. 璎�� ����� ���������
����������� �������~$S(n)$, ����������� ������ ���������
���������� ������������, �����, ���~(5). ���������� �����
���������� ��������� �������� ����� ����������� � ���� ������������� �����.
 풎� ������������ ���� � ���� �������������� ���������~$<$ �� ��������
������; �������������, ��� ������ ����� ���������� ����� �������, �����
��� ���� ��� ����� �������;
������� ������� ������� �� ��������� �������. � ���������� ���������~(5)
������������� �
\picture{p.227}
����� $G$---����� ������������ ����; ��������� ����� $T(G)$~�����
������������, ������������� �~$G$, �.~�.~����� �������� �������� �������
�����~$G$ ������ �������~$\set{1, 2,~\ldots, n}$ ���, ����� ����� �
�������~$x$ ���� ������ ����� � �������~$y$, ���� ����~$x\to y$
�����������~$G$. ������ ������������, ������������� �~(21): $a=1$, $b=4$,
 $c=2$, $d=5$, $e=3$. �� ������� �������~$T(G)$ ��� ���������~$G$ �
�.~5.1.4, ��� ���� ��������, ��� $T(G)$~���� ����� �������� "�������������
�������������" ����~$G$.

����� $G$---���� �� $n$~���������, ������� ����� �������� �����
$k$~���������; ��������� \emph{�������������} �����~$G$ ��������
$$
E(G)={n!\over 2^k T(G)}.
\eqno(22)
$$
%%228
(풀 ���� ����������� 䐀��� 哀�� �~腍� ����.) ᒐ��� ������,
������������� �� ���� ������� ���� ������ �����~$G$---��� ������� �� ����
����, ������� �� ������ �~$G$ � �������� ����������, ������ ��� ������
��������� ��� ��������� ����������. �������� ��� ���� ��������� ���
����������~$i$ �~$j$, ������� ��� �����~$G_1$, �~$G_2$: ����---���
������~$K_i<K_j$ � ������---��� ������~$K_i>K_j$. �, ���
$$
T(G)=T(G_1)+T(G_2).
$$
����~$T(G_1)\ge T(G_2)$, �� �����
$$
\eqalignno{
T(G)&\le 2T(G_1),\cr
E(G_1)={n!\over 2^{k+1}T(G_1)} &={E(G)T(G)\over 2T(G_1)}\le E(G).&(23)\cr
}
$$
ዅ����������, ������ ��������� �������� � ����� ������� ��� ������
�������������; ������ ��������� ������������� �� ���� �������������� ���������.

�������, ��� ����~$G$ ������ �� �������� ���, ��~$k=0$ �~$T(G)=n!$,
�.~�.~��������� ������������� �����~1. ���� �� ����~$G$ ������������
������������� ��������� ����������, �� $G$~�������� ��� ������� ������,
�~$T(G)=1$.  , ��������, ���� ��� ����� ��������� ��������� ����������,
������� �� ����������� ���� ��������� �� ���� ��� ����� ���������,
�� ���������� �������� �������� ����
\picture{228.1}
������������� �������� �����~$5!/(2^7\times1)=120/128=15/16$. ������
�������, ��� ��� �����, ����������� � �������� ����������, ������ �����
�������������~$\ge{15\over16}$; ���� �� ��������
�����-������ ���� ������� �������������, �� �� ������� ���� ���� �� ���
�������� ���� ���� �� ������� �������������, � �� �� � ����� ������ ������
� ��������� ����� � ��������������~$<{15\over16}$. � ����� ������ ���
����������� ����������, ���
��� �����, ��������������� ����� ������ ��� ��������� ���������
���������� $n$~���������, ������ ����� �������������~$\ge n!/2^l$, ���
$l+1$---����� ������� � ������. 풎 ��� ���� ������ ��������������
�����������~$S(n)\ge \ceil{\log_2 n!}$, ���� ����� ����������� �� �����
���� �� ������ ���������� �� ������������ ����.

����~(21) ����� �������������~1, ���������~$T(G)=15$ � ����~$G$ ���
������� �� ��� ���������. 璎�� ��������, ����� ������� ������ �����������
� ��������� ���������, �����
%%229
��������� \dfn{������� ���������}
$$
C(G)=\bordermatrix{
  & a & b & c & d & e \cr
a&0& 15 & 10 & 15 & 11 \cr
b & 0 & 0 & 5 & 15 & 7 \cr
c & 5 & 10 & 0 & 15 & 9 \cr
d & 0 & 0 & 0 & 0 & 3 \cr
e & 4 & 8 & 6 & 12 & 0 \cr
},
\eqno(24)
$$
���~$C_{ij}$ ����~$T(G_1)$ ��� �����~$G_1$, ����������� ��~$G$ �����
���������� ����~$i\to j$. ���� ��, ��������, �������~$K_c$ �~$K_e$, ��
15~������������, ������������� �~$G$, ���������� �� ��� ������: $C_{ec}=6$,
 � ������� $K_e<K_c$, �~$C_{ce}=9$, � �������~$K_c<K_e$. ��������� ����
���� ��
�������������~$15/(2 \times 9)={5\over6}<{15\over16}$, ��� ��� ���
��������� �� ����� �������� � ����������� ��������� ����������.
ዅ������ ����������, ��� ���� ����� ���������
�������������~$\ge{15\over16}$, \emph{�������} ����~$K_b:K_e$.

������� "�������������" �������� ������� ��� ������������ "�������
���������" ������. �������, ��������, ����
\picture{p.229.1}
�� ������� �� ���� ���������
\picture{p.229.2}
��� �� ���� ���� �� ���������~$G'$ �~$G''$; �������������, ��
��� ��������� ����� ���������� ��������� ������ ������~$G'$ � ����������
���������� ��������� ������ ������~$G''$. � ����� ������ �����������, ���
����~$G=G'+G''$ �� �������� ���, �����������~$G'$ �~$G''$, ���~$G'$
�~$G''$ ����� ��������������~$n'$ �~$n''$ ������; ����� ������, ���
$$
T(G)=\perm{n'+n''}{n'}T(G')T(G''),
\eqno(25)
$$
��������� ������ ������������, ������������� �~$G$, ���������� �����
������ $n'$~���������, ������� ��������� �������������� �����~$G'$, �
������������ ����������� ������������, ������������� �~$G'$, � ����������,
������������, ������������� �~$G''$. ����� ������~$G'$ ���������~$k'$
���������, � ������ $G''$---%
%%230
�������������� $k''$~���������; �������� �������� ���������
$$
E(G)={(n'+n'')!\over 2^{k'+k''}T(G)}
={n'!\over 2^{k'}T(G')}\cdot{n''!\over 2^{k''}T(G'')}=E(G')E(G''),
\eqno(26)
$$
������������, ��� ����� �������������� ����� � ��������������� ���
��������� ���������� ������� �����. ������� �� ����� ���������� ����
������������ �������, �������� ������ ���� ����������.

⅏��� �����������, ���~$G'$ �~$G''$---���������������� �����, � �� �����
������� �� ������, ������� �������~$x$ �����~$G'$ � ��������~$y$
�����~$G''$. ����� ��������, ��������� ����������� ��������� ����. ���
���� ���� ��� ���������� �������, ������� ����� ���������� �����
$$
\left({p\atop m}<{q\atop n}\right),
\eqno(27)
$$
������ �� ����������� ����� ������������, ������������� � ������
\picture{p.230}
 �� �������, $\left({p\atop m}<{q\atop n}\right)$ ����
������������~$\perm{m+n}{m}$ �� ����������� ����, ���
$p\hbox{-�}$~���������� ������� �� ��������� $m$~����� ������
$q\hbox{-��}$~����������� �������� �� ���������� ����������
��������� $n$~�����. � ���.~17 ��������, ���
�������~$\left({p\atop m}<{q\atop n}\right)$ ����� �������� �����
������������ ������������ ����� ���������:
$$
\eqalignno{
\left({p\atop m}<{q\atop n}\right)&=\sum_{0\le k <q}
\perm{m-p+n-k}{m-p}\perm{p-1+1}{p-1}=\cr
&=\sum_{p\le j \le m}\perm{n-q+m-j}{n-q}\perm{q-1+j}{q-1}.&(29)\cr
}
$$
(����� ������, ������������� ������ ������� �� ��������, ��� ��� ��� �����
������������ ������������ ������������� ������ ���� �����.) ����� ����� �������
$$
\eqalignno{
\left({p\atop m}<{q\atop n}\right)+\left({q\atop n}<{p\atop m}\right) &=\perm{m+n}{m}, &(30)\cr
\left({q\atop n}<{p\atop m}\right)&=\left({m+1-p\atop m}<{n+1-q\atop n}\right). &(31)\cr
}
$$

%%231
��� ������� ���������� ��� �����
\picture{p.231}
�������� �������� ������� �������������, ���~$T(G')=42$ �~$T(G'')=5$; ���
��� ����~$G$---���� �~11~���������, ����������~$G'$ �~$G''$ � �������� �����
���������, �� �� �������~(25)
$T(G)=\perm{11}{4}\cdot 42 \cdot 5=69~300$. 풎 ����� ������������
������� �����������, ����� �� ����� ���� �������� �, ����� �������,
 ��������, � �������� �� ��� $x_i < y_j$ ��� ����~$i$ �~$j$. ������ ���
���������� ����� ��� �� ��� ����� ��������� ������� ��������� �������.
�������� �������~$A(G')$ �~$A(G'')$, ���~$A_{ik}$---����� ������������,
������������� �~$G'$ (���~$G''$), � �������~$x_i$ (���~$y_i$) �����~$k$.
⎃�� ����� ������������, ������������� �~$G$, � �������~$x_i$
������~$y_j$, ���� ����� �� ����~$p$ �~$q$, $1\le p \le 7$, $1\le q \le 4$,
 ������������ $(ip)\hbox{-��}$~�������� �������~$A(G')$ ��~$\left({p\atop
7}<{q\atop 4}\right)$ � �� $(jq)\hbox{-�}$~������� �������~$A(G'')$. �����
������, ����� ��������� ������������ ������~$A(G')\cdot L \cdot A(G'')^T$,
 ���~$L_{pq}=\left({p\atop 7}<{q\atop 4}\right)$. ��� �����
{\def\pmatrix#1{\left(\vcenter{
\halign{
\hfill$\scriptstyle ##$&&\hfill$\quad\scriptstyle ##$\cr
#1
}}
\right)}
$$
\pmatrix{
21 & 16 &  5 &  0 &  0 &  0 &  0 \cr
 0 &  5 & 10 & 12 & 10 &  5 &  0 \cr
21 & 16 &  5 &  0 &  0 &  0 &  0 \cr
0  &  0 & 12 & 18 & 12 &  0 &  0 \cr
0  &  0 &  0 &  0 &  5 & 16 & 21 \cr
0  &  5 & 10 & 12 & 10 &  5 &  0 \cr
0  &  0 &  0 &  0 &  5 & 16 & 21 \cr
}
\pmatrix{
210 & 294 & 322 & 329 \cr
126 & 238 & 301 & 325 \cr
 70 & 175 & 265 & 315 \cr
 35 & 115 & 215 & 295 \cr
 15 &  65 & 155 & 260 \cr
  5 &  29 &  92 & 204 \cr
  1 &   8 &  36 & 120 \cr
}
\pmatrix{
2 & 3 & 0 & 0 \cr
2 & 2 & 0 & 1 \cr
1 & 0 & 2 & 2 \cr
0 & 0 & 3 & 2 \cr
}
=\pmatrix{
48169 & 42042 & 66858 & 64031 \cr
22825 & 16005 & 53295 & 46475 \cr
48169 & 42042 & 66858 & 64031 \cr
22110 & 14850 & 54450 & 47190 \cr
 5269 & 2442 & 27258 & 21131 \cr
22825 & 16005 & 53295 & 46475 \cr
 5269 & 2442 & 27258 & 21131 \cr
}.
$$
}
 �� �������, "���������" ������ ���������~$G'$
�~$G''$---��� ��������~$x_1$ �~$y_2$; � 42~042~������� �������~$x_1<y_2$ �
�~$69~300-42~042=27~258$~�������---$x_1>y_2$. (� ���� ���������, ��
��������, � ��� �� ����������� ������� �� ���������~$x_3$ �~$y_2$, $x_5$
�~$y_3$ ���~$x_7$ �~$y_3$.) 픔���������� ����������� ����� ���~$x_1<y_2$ �����
$$
{69~300\over 84~084}E(G')E(G''),
$$
�.~�.~�� �������� ������; �������������, ��-��������, ������ �� ����� �� �
����� ������ ���������� ��������� ����������~$G'$ �~$G''$! ጛ�� �����
������� � ���, ��� �� ������ ������� ����� �������, �� ��������� ���������
������� ����������.
%%232
품�� ������ ����� ��������������� ����� ��� ������������ �������������
�������������� ����� 㝋�� �������������� ����, ���~$S(12)=30$. ����� �
�����, ����������� ���� �������, �� ����� ��������� ������� ����������
��������� � ������ �� ����� ������~$G$ ��� � ���� ���������
�����~$G'$ �~$G''$ � ����� ��������, ����� ��� ���������� ����� ���������~12
\picture{���.~36.                ��������� ����� � �� �������������,
���������� � ������ �������� �������������� �����������~$S(12)>29$.
}
��� ����� ������ � �������� �������������� $\ge 12!/2^{29}\approx0.89221$.
������ ���, ��� ��� ����������� ���������, �� �������� ���� � �������
�������������� � ��������� ��� � ������ ���������, ���� ������ �� ��
�������� ���������� ������ �� ��� ���������� � ��������� ������ (���
������������ � ����, �.~�.~���������� ���������� ��������� �������).
���� ��� ���������� ����� ����� ���������� �������������, ��
������������ ������� ���������� ���� �� ���. ������ 24~�����, ����������
����� ��������, ���������� �� ���.~36, ��� ��������� ����� �� �������������.

��� ������ �������������� ������ ���� ��������� ����� 1594~�����, ������
��� ���� ������� ����������. ��������� ����
%%233
�� ��� �������, ����� ������� ����� � ���, ���~$S(12)>29$. ������
�������������, ��� � ��� �������������� �����������~$S(22)>70$ �����
���������� ����������� ����������� �� ������ �������� �����, ���������
$22!/2^{70}\approx 0.952$---��� ����������� ������� ������������� ���
���������� �� 70~�����. (�� 1594~��������� ������ �~12 ��� ����� ���������
����� 92~����� ����� ������� �������������.)

������������� ���������� ���� ������ ��������� ������������,
���~$S(13)=33$, �, �������������, ���������� ��������� � �������� ��
���������� ���~$n=13$. �� �� ��� ��� ������ �� ������� ���������� \emph{��
������} ������ ��������~$n$, ���~$S(n)<F(n)$.

��������� ����� ��������, ���~$S(16)<F(16)$, ���������~$F(16)$---��� ��� ���
����� ����� ���������, ����� ���������, ����� ������� �������������
10~��������� �� $S(10)$~�����, � ����� ����������� �������� �������
�������� �� ������ ��������� ����� ���������. ���������� ������
������������ ����� ������� ������!

\section ᐅ���� ����� ���������. �� ��� ��� �� ������������� ���������,
��������� � ��� ������, ��� ��� �� ����� � ��������� ������; �� ������
"�����������" ���������, �������������� \emph{������������} �����
���������. ������ ������ "�����������" ���������, ��������������
\emph{�������} ����� ��������� � �������������, ��� ������� ������
��������, �.~�.~��� ������������ �������������.

���������� ��� ��� ������������ �� ���.~34 ������������� ���������
���������� � ���� ������. ᐅ���� ����� ��������� �� ���� �������������
��� ����� ������ �����
$$
{2+3+3+3+3+2\over 6}=2{2\over3}.
$$
� ����� ������ ������� ����� ��������� ��� ������ ���������� ����
\emph{����� �������� ���� ������,} �������� ��~$n$. (��������, ��� �����
�������� ����---��� ����� ���� ���������� �� ����� �� ������� �� �������
�����; ��.~�.~2.3.4.5.) �� ���������� � �.~2.3.4.5 ����� ������, ���
������� ����� �������� ���� ����������� �� ����� �������� ������ �
$N$~�������� ������, � �������� ������� $2^q-N$~������� ����� ��
������~$q-1$ �~$2N-2^q$ �� ������~$q$, ���~$q=\ceil{\log_2 N}$. (������
��������� �� ������� ������.)  �� �������, ����������� �����
�������� ���� �����
$$
(q-1)(2^q-N)+q(2N-2^q)=(q+1)N-2^q.
\eqno(33)
$$

������� ��� ���� ���������� ������ ���������������� ����������� �����
����: \dfn{����������� �������� ������ ����� �����������
%%234
����� �������� ���� ����� � ������ �����, ����� ���������� �����
�����~$l$, ��� ��� ������� ���� ��������� �� �������~$l$ �~$l+1$.}
(�.~���.~20.)

���� ��������~$q=\log_2 N+\theta$, ���~$0\le \theta < 1$, ��
������� ����������� ����� �������� ���� ������ ���
$$
N(\log_2 N+1+\theta-2^\theta).
\eqno(34)
$$
������ �������~$1+\theta-2^\theta$ ��������� �� ���.~37;
���~$0<\theta<1$ ��� ��������� �������������, �� ����� ����� ��������, ��
�����������
$$
1-(1+\ln\ln 2)/(\ln 2)=0.08607~13320~55934+.
\eqno(35)
$$
\picture{���.~37.  䓍���� $1+\theta-2^\theta$.}
 �� �������, ����������� ��������� ������� ����� ����, �������
���������� � ���������� �������~(34) ��~$N$, �� ����� ���� ������~$\log_2 N$
� ������~$\log_2 N+0.0861$. (풎� ��������� ������� ������� �.~������ �
���������������� ������� (1956).)

���� ������ �������~$N=n!$, �� ������� ������ ������ �������� �����
��������� �� ���� ������ ����������. �������, ��� ������ �����~$\log_2
n!+O(1)=n\log_2 n-n/(\ln 2)+O(\log n)$.

�����~$\bar F(n)$---������� ����� ���������, ����������� ����������
���������� ��������� � ��������; �����
$$
\matrix{
\hfill n=1 & 2 & 3  &  4 & 5 & 6 & 7 & 8 \cr
{\hbox{\sl ������ ������\/}}(33)=0 & 2 & 16 & 112 & 832 & 6896 & 62368 & 619904\cr
            \hfill n! \bar F(n) = 0& 2 & 16 & 112 & 832 & 6912 & 62784 & 623232\cr
}
$$
����, ���������� ��������� � �������� ���������� � ����� ������� ���~$n
\ge 5$, ������ ���~$n=6$ ��� ����� ������ ����������� �
�������~$6912/720=9.6$~��������� ������ ���������, �������� ������ ������,
$6896/720=9.577777\ldots$~���������. ������� �������, �������� ������,
������ ��� ���: ��������� "�������" ������������ ����� ���������
����������� ������� ������� � ������� ����� �� ������ ���������, � �����
������ ��������� ����� ������� ���� �� ����, � �� �� ���� �������. ��-��
����� ������������� ��������� ����� ����. � ���.~24 ��������, ��� �����
��������� ��������� ���������� ����� ���������, ��������� ������ ������
��� ������ ���������; �������������,
%%235
���� ����� ����������� ����� ������� � ������� � ������� � ��
���� ���� � ������ ������.

�.~ᅇ��� [thesis (Paris, 1968), �.~37] �������, ��� ���~$n=7$ ��
���������� ������ ����������, ��� ������� �� ����������� ������
������~62368 ����� �������� ����. (��������� ��������� ���.~22, ����
���� ����� �������� �������.) � ������ �������, �� �������� ���������,
��� ������� ����������� ������ ������~(33) ���~$n=9$ ���~10. ������ ��
������ ����������� �������� ����� ��������� ������� ������� ����������
�������~$S(n)$. ������ ���� ��������, ��� ��� ���������~$n$ ��� ������,
�������������� \emph{�������} ����� ���������, � ������ ������ �������
\emph{�����}~$S(n)$ ���������.

\excercises
\ex[20] ��������� ������� ��������� ��� ���������� �������
��������� �������� (a)~�������� �������; (b)~�������� ������������ �������.
 ������ ����� ������� ����� ��� ���� ��������?

\ex[�24] ��������, ���~$B(n)\le L(n)$, � ������� ��� ��������~$n$,
��� ������� ����� ����� ���������.

\ex[�22] ���� ����������� ������ �����, �� ��� ���������� ���� ���������
�������� 13~�������:
$$
\displaylines{
\matrix{
K_1=K_2=K_3, & K_1=K_2<K_3, & K_1=K_3<K_2, \cr
K_2=K_3<K_1, & K_1<K_2=K_3, & K_2<K_1=K_3, \cr
K_3<K_1=K_2, & K_1<K_2<K_3, & K_1<K_3<K_2, \cr
}\cr
\matrix{
K_2<K_1<K_3, & K_2<K_3<K_1, & K_3<K_1<K_2, & K_3<K_2<K_1.\cr
}\cr
}
$$
��������� �����~$P_n$ ����� ��������� ������� ��� ���������� $n$~���������,
 ���� ����������� ������ �����, ��� ���
$(P_0, P_1, P_2, P_3, P_4, P_5,~\ldots)=(1, 1, 3, 13, 75, 541,~\dots)$.
��������, ��� ������������ �������~$P(z)=\sum_{n\ge 0} P_n z^n/n!$
�����~$1/(2-e^z)$. \emph{㊀�����:} ��������, ���
$$
P_n=\sum_{k>0} \perm{n}{k} P_{n-k} \rem{��� $n>0$.}
$$

\ex[��27] (�.~�.~�����.) ������� ������ ������������������ �����~$P_n$ ��
���.~3 ���~$n\to\infty$. [\emph{��������� ��������:} ����������� ���������
���������� � �����~$\ctg z$.]

\ex[16] ���� ����������� ������ �����, �� ������ ��������� ����� ����� ��
���, � ��� ����������: $K_i<K_j$, $K_i=K_j$, $K_i>K_j$. � ����
����� �������� ��������� ���������� ����� ������������ � ����
����������� \emph{���������} ��������, � ������� ������ ����������
����~$i:j$ ����� ��� ���������: �����, ������� � ������, ���������������
���� ��������� ������� ���������.

��������� ����������� ��������� ������, ������������ �������� ����������
���~$n=3$, ���� ����������� ������ �����. � ����� ������ ������ ����
13~������� �����, ��������������� 13~��������� �������, ������������� � ���.~3.

\rex[�22] �����~$S'(n)$---����������� ����� ���������, �����������
��� ���������� $n$~��������� � ��������� ���� �������� ����� �������,
���� ������ ��������� ����� ��� ��������� ����������, ��� � ���.~5.
�������� �������� "���������-��������������" �����������, ����������� �
������,
%%236
� ��������, ���~$S'(n)\ge \ceil{\log_3 P_n}$, ���~$P_n$---�������, ���������
� ���.~3 �~4; ��������, ��� �� ����� ����~$S'(n)=S(n)$.

\ex[20] ��������� ����������� ��������� ������ � ������ ���.~5
��� ���������� ������� ���������, ���� ��������, ��� ��� ����� �����
����~0, ����~1. ( , ��������, ����~$K_1<K_2$ �~$K_3<K_4$, �� �������,
���~$K_1=K_3$ �~$K_2=K_4$!) ��������� ������������ ����� ��������� �
�������, ������, ��� ��� $2^4$~��������� �������� ������ �������������.

\ex[26] ��������� ����������� ��������� ������, ��� � ���.~7, ���
���������� ������� ���������, ���� ��������, ��� ��� ����� �����
����~$-1$, ����~0, ����~$+1$. ��������� ������������ ����� ��������� �
�������, ������, ��� ��� $3^4$~��������� �������� ������ �������������.

\ex[�20] ������ ����������� ����� ��������� � ��������� ������
��� ���������� $n$~���������, ��� � ���.~7, ����� ��������, ��� ���
�������� ����� ����~0, ����~1?

\rex[�25] ������ ����������� \emph{�������} ����� ��������� ��� ����������
$n$~���������, ��� � ���.~7, ����� ��������, ��� ��� ����� ����� ����~0,
����~1? ��������� ����������� � ���� ������� ��~$n$.

\ex[��25] �����~$S_m(n)$---����������� ����� ���������, ����������� �
��������� ������ ��� ���������� $n$~���������, ��� � ���.~5, ���� ��������,
 ��� ��� ����� ����������� ���������~$\set{1, 2,~\ldots, m}$. [ ��
�������, �������� ���.~6,  $S_n(n)=S(n)$.] ��������, ���~$S_m(n)$
��������� �~$n\log_2 m$ ��� �������������~$m$ � $n\to\infty$.

\rex[�25] (�.~�.~��������, ����� 1954~�.) �����������, ��� ������
����� ����� �����������, �� �� ����� ������ �������������
��������~$\set{K_1, K_2,~\ldots, K_n}$  ���, ����� ����������
������������~$a_1\ a_2~\ldots a_n$, �����,
���~$K_{a_1}\le K_{a_2} \le \ldots \le K_{a_n}$; ��� �� �����, ����� ��
����� ��������� ����� ����������~$K_{a_i}$ �~$K_{a_{i+1}}$.

����� ��������, ��� ������ ��������� \emph{������} ���������
������������������ ������, ���� ��� ��������� ��� ������������������ �
������������� ������, ���������� �� ����, ����� ���� �������� �
�����~$i:j$, ��� �������~$K_i=K_j$. (������ ��������, � �� ���������.)

\medskip
\item{a)}~��������, ��� ������, �� ���������� ���������� ���������,
������ ��������� ����� ������������������ ������ ����� � ������ �����,
����� ��� ��������� ����� ������������������ ��������� ������.

\item{b)}~��������, ��� ������ ��������� ������ ��������� �����
������������������ ������ ����� � ������ �����, ����� ��� ������
��������� ����� ������������������ ����� � ������.
\medskip

\ex[�28] �������� �����������~(17).

\ex[�24] �������� �����~(19) � "��������� ����".

\ex[�21] ���������� ��������������� ��������� �������~$B(n)$ �~$F(n)$ �
��������� ��~$O(\log n)$. [\emph{㊀�����:} ��������, ��� � ����� �������
����������� ���~$n$ �������� �������, ������������ �� ���.~37.]

\ex[��26] (�.~哀� � �.~����.) ��������, ��� ���~$n\ge22$
����������� �����������~$F (n) > \ceil{\log_2 n!}$.

\ex[�20] �������� ���������~(29).

\ex[20] ���� �� ���������, ������ ������� ���������� �� ���.~36,
�������� ����
\picture{p.236}
� ��������������~$12!/2^{29}$, �� ���� �� �� ��� ����� ��������,
���~$S(12) =29$?

\ex[40] ��������� ������������ �� ��������� ������������� �������� �������
������������ ����, ����� ���� ������ ���������� ���������
��� ��������������� ������ ���������. ����� �� ������ ������ ����������
������~$\set{K_1,~\ldots, K_n}$ ����� ������, � ������� �� ���������
����������� �� ��� ��� ��������� ��������, ��� ���~$\le K_i$, ������������
�����~$u_i$, � ����� ������, � ������� ��������, ��� ���~$\ge K_i$,
������������ �����~$v_i$, $1\le i\le n$.

%%237
������������ ����� ���, ����� ������������������~$u_i/v_i$ ����� ������������:
$u1/v_1 \le u_2/v_2 \le \ldots \le u_n/v_n$. ⅏��� �������~$K_i:K_{i+1}$,
���~$i$---������, �������������� ���������~$\abs{u_iv_{i+1}-u_{i+1}v_i}$.
(厒� ���� ����� ���������� ������� ������ ����������, ��� ���������� �
������ ������� ���������, ��������~(24), ��, ��� �����������, �� ������
������� ���� ����������� ����������.)

\rex[�26] ��������, ��� ����������� �������� ������ ����� �����������
����� �������� ���� ����� � ������ �����, ����� ���������� ����� �����~$l$,
 ��� ��� ������� ���� ��������� �� �������~$l$ �~$l+1$ (���, ���� �����,
������ �� ������~$l$).

\edef\exref{\the\excerno}
\ex[�21] \dfn{�������} ������������ ��������� ������ ����������
������������ ����� ������, �� ������� ���� ������� ����.
�����~$x$---���������� ���� ������������ ��������� ������; ���������
�����~$t(x)$ ����� ������� �����-�������� ����~$x$, � �����~$l(x)$ ������
������ ��������� ����~$x$. ���� $x$---������� ����, �� �������~$t(x)=1$.
��������, ��� ����������� �������� ������ ����� ����������� ������ �����
���� �������� �������� � ��� �� ������ ����� ����� � ������ �����, �����
��� ���� ��� ���������� �����~$x$  ����������� �����������
$$
\abs{t(x)-2t(l(x))}\le2^{\ceil{\log_2 t(x)}}-t(x).
$$

\ex[�24] ����������� ���.~\exref. ��������, ��� �������� ������
����� ����������� ����� �������� ���� ����� ���� �������� �������� � ���
�� ������ ����� ����� � ������ �����, ����� ��� ���� ��� ����������
�����~$x$ ����������� �����������
$$
\abs{t(x)-2t(l(x))}\le 2^{\ceil{\log_2 t(x)}}-t(x) \hbox{ � }
\abs{t(x)-2t(l(x))}\le t(x)-2^{\floor{\log_2 t(x)}}.
$$
[ , ��������, ����~$t(x)=67$, �� ������ ����~$t(l(x))=32$, 33, 34
���~35. ���� ����� ������ �������������� ������ ������, ��, ��������
����������� ����������, ����������, �����~$3\le t(l(x))\le 64$.]

\ex[10] � ������ �������� [��.~�������~(34)], ��� ������� �����
���������, ����������� ����� ������� ���������� $n$~���������, �� �����
���� ������~$\ceil{\log_2 n!}\approx n\log_2 n$. ������ ��� ����������
��������� � ��������� ������� (��������~5.2.1�) ������������� � �������
����� $O(n)$~������ �������. 煌 ��� �����������?

\ex[27] (�. �����.) ��������� ����� ������ ���������� ��� �����
���������, ����� ��� ��� ������� ���� ������������� �� �������~10 �~11.

\ex[11] ���� �� ������������ ��������� ���������� ���� ���������,
�� ������� ���������� ������� �������� ����� ���������, ����������� ���
������ �������~(34), �� ������� ������� ����� ���� �� �� ������~13
���������������� ������?

\ex[�42] ������� ��������� ���������� ��� ���� ���������, ��������������
������� ����� ����������� ���������.

\rex[20] ����� ��������, ��� ������������ ($K_1<K_2<K_3$, $K_1<K_3<K_2$,
 $K_2<K_1<K_3$,  $K_2<K_3<K_1$,   $K_3<K_1<K_2$,  $K_3<K_2<K_1$)
����������� � ������������� �������������� ($.01$, $.25$, $.01$, $.24$,
$.25$, $.24$). ������� ������ ���������, ������� �� ����������� ����� ���
�������� � ���������� ������� ������ ���������.

\ex[40] �������� MIX-���������, ������� ��������� 5~����������� ������ ��
���������� ��������� �����, ����� ���� ���������������. (�.~��������
������� � ������~\S~5.2.)

\ex[�25] (�.~�.~睉�.) ����� $a_1$ $a_2$~\dots $a_n$---������������
���������~$\set{1, 2,~\ldots, n}$. ��������, ��� ����� ��������, �������
����������, �������� �� ������ ������������ ������ ��� ��������
(�.~�.~�������� �� ��� ������ ��� �������� ����� ��������), � ����������
������������� �� ���������� ���������~$a$, ������ ��������� �� �����
$n\log_2 n$~���������, ���� �� ����� ����� ��� ��������� ������.
%%238

\ex[�23] \exhead(����������� �������� ����������.) ����� ��������
�������� ���������� � ������ �����������, ������� � �.~5.2.2, �����
����������� � ���� \dfn{������ ���������-�������,} � ������ � ����
��������� ��������� ������, ���������� ���� �������� �����
���~$\elnode{i:j}$, ���~$i<j$, � ���������������� ��������� �������:
"����~$K_i\le K_j$, �� ������������ �� ����� ����� ������; ����~$K_i>K_j$,
�� �������� ������� ������~$i$ �~$j$ � ������������ �� ������
����� ������"   �� ���������� �������� ���� ������ �����������
�������~$K_1\le K_2\le \ldots\le K_n$.  �� �������, ������
���������-������� ���������� �� ������ ��������� ���, ��� ��� ��������� ��
������ �������� ���������, �� � �������� ����������� ������.

��������� �����~$S_e(n)$ ����������� ����� ���������-�������,
����������� � ��������� ������ ��� ���������� ��������� ��� ������
������ ���������-�������. ��������, ���~$S_e(n)\le S(n)+n-1$.

\ex[�38] ����������� ���.~30. ��������, ���~$S_e(5)=8$.

\ex[�42] ����������� ���.~31. ���������� �������� �������~$S_e(n)$ ���
�����~$n>5$.

\ex[M30] (�.~�.~刁����.) \dfn{������������������ ������� ������}
�������~$x$ � �����������~$\delta$ ���������� ����������� �������� ������,
������ ���� �������� �������� ��������������� �������������� ��������,
�����, ��� (i)~�������� � ����� ������� ����~$\le \delta$; (ii)~��������
� ����� ���������� ����~$\le $ ����� �������� ���� ��� �������;
(iii)~�������� � ����� �����~$x$. \dfn{����� ����������� ����} ������
������ ������������ ��� ����� �� ���� ������� ����� ������� ������� ����
�����, ���������� �� ������������ � ��� ��������.

��������, ��� ������������������ ������ ������ �������~$x$ �
�����������~1 ����� ����������� ����� ���� ����� �������� ���� ��
������� � � ��� �� ����������� ����� ����������� ���� ����� � ������ �����,
 ����� �~(ii) ����� ����� ��������� � ��� ���� ��� ��������~$x_0$ �~$x_1$,
������������� �����-�������, ����������� ��������� �������: (iv)~��
���������� ������ �����~$k\ge 0$, ������, ���~$x_0<2^k<x_1$
���~$x_1 < 2^k < x_0$; (v)~$\ceil{x_0}-x_0+\ceil{x_1}-x_1<1$.
(� ���������, ����
$x$---����� �����, �� �� �������~(v) �������, ��� ��� �������� �
������---�����, � �������~(iv) ������������ ���������� ���.~22.)

�������� �����, ��� ��������������� ����� ����������� ����
�����~$x\ceil{\log_2 x}+\ceil{x}-2^{\ceil{\log_2 x}}$.

\ex[�50] ���������� ������ �������� �������~$S(n)$ ���
������������ ��������� ����������~$n$.

\subsubchap{*ወ���� � ����������� ������ ���������}%%5.3.2
���������� ������ ������, ������� ��������� � ����������� ������: �����
��������� ������ ������� �������������� ��������� $m$~��������� �
������������� ���������� $n$~���������? ��������� �������� ���������
�������� �����
$$
\eqalignno{
A_1 &< A_2 < \ldots < A_m, \cr
B_1 &< B_2 < \ldots < B_n. & (1) \cr
}
$$
��� � � �.~5.3.1, ����� ������������, ��� ��� $m+n$~��������� ��������.
틅�����~$A$ ����� ���������~$B$ ����� �������������
$\perm{m+n}{m}$~���������; ����� �������, �� �����������, ������� �� %%239
��������������� � ������ � ����������, �������, ��� ���������� ���������
�� ������� ����
$$
\ceil{\log_2 \perm{m+n}{m}}
\eqno(2)
$$
���������. ���� ��������~$m=\alpha n$ � ���������~$n$ �~$\infty$,
�������~$\alpha$ ����������, �� �� ������� ᒈ������
$$
\log_2 \perm{\alpha n+n}{\alpha n}= n \left((1+\alpha)\log_2 (1+\alpha)
-\alpha\log_2\alpha\right)-{1\over2}\log_2 n+O(1).
\eqno(3)
$$
������� ��������� ������� (��������~5.2.4�) ��������� � ������ ������ $m+n-1$~���������.

��������� �����~$M(m, n)$ �������, �����������~$S(n)$, � ������
����������� ����� ���������, �������� ����������� ��� �������
$m$~��������� � $n$~����������. �� ������ ��� ���������� ����������
�������, ���
$$
\ceil{\log_2\perm{m+n}{m}}\le M(m,n)\le m+n-1  \rem{��� ���� $m, n\ge1$.}
\eqno(4)
$$
䎐����~(3) ����������, ��������� ������ ����� �������� ���� �� �����
������ � ������� ������. ���~$\alpha=1$ (�.~�.~$m=n$)
������ ������ �����~$2n-{1\over 2}\log_2 n+O(1)$, ��� ��� ���
������---�������� ������ �������, �� �������� ����� ���� ����� ���� �����
������ ������. ���~$\alpha=0.5$ $\left(\hbox{�.~�.~$m={1\over2}n$}\right)$
������ ������ �����
$$
{3\over2}n \left(\log_2 3 -{2\over3}\right)+O(\log n),
$$
��� ���������� ��������~$\log_2 3-{2\over3}\approx 0.918$ �� ������� ������.
� ���������~$\alpha$ ������� ����� ������� � ������ ��������
��� �������������, ��������� ����������� �������� ������� ����������
������� ������� ��� ������ �~$m\approx n$.

���~$m=n$ ������ � ������� ����� ������ ������� �������;
�������� ����������� �� �������, � \emph{������} ������~(4). ዅ������
������� ���������� �������� �.~�.~������ �~�.~�.~���� �������� � 1968~�.

\proclaim ⅎ����~M. ���~$m\ge 1$ ����������� ���������~$M(m,m)=2m-1$.

\proof ���������� �����-������ ��������, ������� ������������ �������
���������~$A_1<\ldots<A_m$ �~$B_1<\ldots<B_m$. ��� ���������
���������~$A_i:B_j$ ������� �����~$A_i<B_j$, ����~$i<j$, � �����~$A_i>B_j$,
 ����~$i\ge j$. ወ���� ������ �����������
%%240
�������������
$$
B_1<A_1<B_2<A_2<\ldots<B_m<A_m,
\eqno(5)
$$
��������� ��� ����������� �� ����� ���������� �������. � ������ ��
$2m-1$~��������� $B_1:A_1$, $A_1:B_2$, $B_2:A_2$,~\dots, $B_m:A_m$ ������
���� ��������� ����, ����� ������� �� �� ������� ���� ��� ������������, ��
�������������� ��������� ������. ���� �� ��, ��������, �� ��������~$A_1$
�~$B_2$, �� ������������
$$
B_1<B_2<A_1<A_2<\ldots<B_m<A_m
$$
���� �� ���������� ��~(5).
\proofend

������� ����������� ����� �������������� ���� ����������� �������
$$
M(m, m+1)=2m \rem{��� $m\ge 0$.}
\eqno  (6)
$$

\section ���������� ������ ������. ⅎ����~M ����������, ���
"���������-��������������" ������ ������~(2) ����� ����� ������ ������
�������� �� �������� ������ �������; ����� �������, ����� ��������������
�������~M ���� ��� ��� ���� ������ ���������� ������ ������.  �� �����
�������������� ����� ��������������� ��� ���������� \dfn{�������,} �������
����� ����, ������� �������� ��������� �������� �������� ��� �����
���������. ����� �������� ������� ������ �������� ��������~$A_i:B_j$,
������ ��� ���������� ������ ���������, ��� ��������� �������� �������
�������� ������� ����. ���� �� �� ������ ��������� ����������� �������, ��
������ �� ��������� � ���, ��� ������ ���������� �������� ������� ������
��������� �������� ����� ���������. (��������� �������� ��� �� ��������,
� "��������" ��� "�������"; ������ ���������� �������� ����� �������� �
���� ���������, ��������� ����� "������" ����� ������ ������ �������� �
������ ����������� �������, � ����� "�����" ������������� � ������ ������
� ������������, ��������� � ������������� �����������.)

�� ����� ������������ \dfn{�������� � ������������� �������������,}
�������� ������� ����������� ������� ��������� ������������ ���������
���������. � ������ �������, ����������� ��� ������������ ������� �
������������� �������������, ����������� ��������� ������������ � �������
����������� ��� ����������� ��������� ���� � ��� ������, ����� ��
���������� ��������������. ��������, � �������������� �������~M ��
���������� ��� ���������� ��������� ��������~(5), ��� �� ����� � ���������
������� ������ ��������������� ���� ���������������, ����� �������� ����
�� ������ ���������.

�����������, ������� �� ����� ������������ � ��������� ����������,
��������� � ������ � ������� ������ ������. ����� ����������� ������������
���������
%%241
{\narrower
\item{$\cdot$}~(��� ����������� �����),

\item{$\backslash$}~(���������� ���� ��������� �� ������ �������������
�������~$A_1< B_1$),

\item{$/$}~(���������� ���� ��������� �� ������ ������������� �������~$A_1>B_1$).
\smallskip
}
\noindent ������ ����������� ������������ ���������

{\narrower
\item{$\cdot$}~(��� ����������� ������),

\item{$\backslash$}~(���������� ���� ��������� �� ������ �������������
�������~$A_m<B_n$),

\item{$/$}~(���������� ���� ��������� �� ������ �������������
�������~$A_m>B_n$).
\medskip
}

\noindent ᓙ������� ������ ����� ��������, ������������
���������~$\nabla M\phi$, ���~$\nabla$---����� �����������, �~$\phi$---������.
��������, ������~"$\backslash M \backslash$" ������ ��������,
���~$A_1<B_j$ �~$A_i<B_n$; ������~"$.M.$" �� ����������� �������
������������. ��� ��������� ����� ���������~$m$ �~$n$ ������� �
������������� ������������� ��������� ����� ����� �� ������������;
���~$m=1$, ��������, �� ����� ���� �������~"$\backslash M /$".

�������� ������ ����������� ������ ��������, �� ����������� ���������
������� ��� �������. �� �� ������ ��������� ����������� ����������, ��
���� ������ ������, ������� ���������� ��������� ���������� �������.
�����������, ������~$m$ �~$n$, � ����� ����� � ������ �����������~$\nabla$
�~$\phi$, � ����� ������� ����������, ������� �� ���� ���������~$A_i$
�~$B_j$ ������. ������ �����, ������ ������, ��������� ����� ���������
�������� ������ � ������ �������� ��������~$m+n$:

{\medskip\narrower
{\sl ᒐ������~$A(k, l)$ ���~$i\le k \le m$ �~$1\le l \le j$.\/} ��������,
���~$A_i<B_j$, � �����������, ����� ����������� �������� ������������
�������~$\set{A_1,~\ldots, A_k}$ �~$\set{B_1,~\ldots, B_{l-1}}$
�~$\set{A_{k+1},~\ldots, A_m}$ �~$\set{B_l,~\ldots, B_n}$. ⎃��
����������� ���������~$A_p:B_q$ ����� ����������: $A_p<B_q$, ����~$p\le k$
�~$q\ge l$, �~$A_p>B_q$, ����~$p>k$ �~$q<l$; ��� ����� �����������
��������~$(k, l-1, \nabla, .)$, ����~$p\le k$ �~$q<l$, �
��������~$(m-k, n+1-l,., \phi)$, ����~$p>k$ �~$q\ge l$.

{\sl ᒐ������~$B(k, l)$ ���~$i\le k \le m$ �~$1\le l < j$\/}. ��������,
���~$A_i<B_j$, � �����������, ����� ����������� �������� ������������
�������~$\set{A_1,~\ldots, A_k}$ �~$\set{B_1,~\ldots, B_l}$
�~$\set{A_{k+1},~\ldots, A_m}$ �~$\set{B_l,~\ldots, B_n}$ ���
�������~$A_k<B_l<A_{k+1}$. (�������, ���~$B_l$ ��������� � ����� �������,
���������� �������. 㑋����~$A_k<B_l<A_{k+1}$ ������������ ����� ���������,
 ��� ������� ������� ����� ���� ������ �� ����� ���� ������� ����������,
������� �� ������� ��� ������� ������ ����.) ⎃�� �����������
���������~$A_p:B_q$ ����� ����������: $A_p<B_q$,
����~$p\le k$
%%242
�~$q\ge l$, �~$A_p>B_q$, ����~$p>k$ �~$q\le l$; ��� �����
����������� ��������~$(k, l, \nabla, \backslash)$, ����~$p\le k$ �~$q\le
l$, �
��������~$(m-k, n+1-l, /, \phi)$, ����~$p>k$ �~$q\le l$.

{\sl ᒐ������~$C(k, l)$ ���~$i<k\le m$ �~$1\le l \le j$.\/} ��������,
���~$A_i<B_j$, � �����������, ����� ����������� �������� ������������
�������~$\set{A_1,~\ldots, A_k}$ �~$\set{B_1,~\ldots, B_{l-1}}$
�~$\set{A_k,~\ldots, A_m}$ �~$\set{B_l,~\ldots, B_n}$ ���
�������~$B_{l-1}<A_k<B_l$. (���������� ���������~B, �� �����~$A$ �~$B$
�������� ������.)

{\sl ᒐ������~$A'(k, l)$ ���~$1\le k \le i$ �~$j\le l \le n$.\/} ��������,
 ���~$A_i>B_j$, � �����������, ����� ����������� �������� ������������
�������~$\set{A_1,~\ldots, A_{k-1}}$ �~$\set{B_1,~\ldots, B_l}$
�~$\set{A_k,~\ldots, A_m}$ �~$\set{B_{l+1},~\ldots, B_n}$.
(���������� ���������~A.)

{\sl ᒐ������~$B'(k, l)$ ���~$1\le k \le i$ �~$j<l\le n$.\/} ��������,
���~$A_i>B_j$, � �����������, ����� ����������� �������� ������������
�������~$\set{A_1,~\ldots, A_{k-1}}$ �~$\set{B_1,~\ldots, B_l}$
�~$\set{A_k,~\ldots, A_m}$ �~$\set{B_l,~\ldots, B_n}$ ���
�������~$A_{k-1}<B_l<A_k$. (���������� ���������~B.)

{\sl ᒐ������~$C'(k, l)$ ���~$1\le k \le i$ �~$j\le l \le n$.\/} ��������,
 ���~$A_i>B_j$, � �����������, ����� ����������� �������� ������������
�������~$\set{A_1,~\ldots, A_k}$ �~$\set{B_1,~\ldots, B_l}$
�~$\set{A_k, ~\ldots, A_m}$ �~$\set{B_{l+1},~\ldots, B_n}$ ���
�������~$B_l<A_k<B_{l+1}$. (���������� ���������~C.)
\medskip}

��-�� ���������� ����������� ����������� ���� ��������� �� �����
����������� � ��������� �������, ������� �� ����� ��������:
\ctable{
\bskip\hfill$#$\hfill\bskip&\bskip\hfill$#$\hfill\bskip\cr
\hbox{ᒐ������} & \hbox{�� ������ �����������, ����}\cr
A(k, 1), B(k, 1), C(k, 1) &     \nabla=/ \cr
A'(1,l), B'(1,l), C'(1,l) &  \nabla=\backslash \cr
A(m, l), B(m, l), C(m, l) &\phi=/ \cr
A'(k, n), B'(k, n), C'(k, n) & \phi= \backslash \cr
}

��������� �����~$\nabla M \phi(m, n)$ ������������ ������ ������, �������
����� �������� ��� ������ ������� �� ���������� ���� ������. ���� ������
��������� ����~$A_i:B_j$, �� ������  ���������, ���� ��� ���������, ����
�����������, �����������
%%243
��� ������ �������, � ������
$$
\eqalign{
A(k, l): & \;\nabla M\phi(m,n)\ge1+\nabla M.(k, l-1) +.M\phi(m-k, n+1-l);\cr
B(k, l): & \;\nabla M\phi(m,n)\ge1+\nabla M\backslash(k, l)+/M\phi(m-k, n+1-l);\cr
C(k, l): & \;\nabla M\phi(m,n)\ge1+\nabla M/(k,l-1)+\backslash M\phi(m+1-k, n+1-l);\cr
A'(k, l):& \;\nabla M\phi(m,n)\ge1+\nabla M.(k-1, l)+.M\phi(m+1-k, n-l);\cr
B'(k, l):& \;\nabla M\phi(m,n)\ge1+\nabla M\backslash(k-1, l)+/M\phi(m+1-k,n+1-l);\cr
C'(k, l):& \;\nabla M\phi(m,n)\ge1+\nabla M/(k, l)+\backslash M\phi(m+1-k, n-l).\cr
}
$$
��� �������������~$i$ �~$j$ ������ ������ �� ���������,
������� ������������� ������ ������, ���������� �������
������� ����������; ����� �������, $\nabla M_\phi(m, n)$~���� ������� ����
������ ������ �� ����~$1\le i\le m$ �~$1\le j \le n$. ����~$m$ ���~$n$
����� ����, �� � �������� �������~$\nabla M_\phi(m, n)$ �����~0.

�����, ��������, $m=2$ �~$n=3$, � ��� ������ �� ���������. ���� ������
����������� ���������~$A_1:B_1$, �� ������ ����� ������� ���������~$A'(1,
1)$, � ���������� ���� ����������� ��� $.M.(0, 1)+.M.(2, 2)=3$~���������.
���� ������ ����������� ���������~$A_1:B_3$, �� �� ����� �������
���������~$B(1, 2)$, ����� ����������� ���~$.M\backslash(1, 2)+/M.(1,
2)=4$~���������. ���������� �� ����, ������ ���� ������ ���������,
������ ����������� ���������� ��� �� ������� ���� 3~���������.
ዅ����������, $.M.(2, 3)=4$.

�� ��� ������ ��������� ��� ���������� �������, �� ��� ������ ��� �����
�������� ������ �������� ������� �������~$\nabla M\phi$. 품 �������
�������� ���������� ���������� ���������� ���������
$$
/M.(m, n)=.M\backslash(m, n)=\backslash M.(n, m)=.M/(n, m),
\eqno (7)
$$
������������ ������ ���� ������ ������� ����� ���� � �������:
$$
.M.(m, n), \quad  /M.(m, n), \quad  /M\backslash (m, n)\hbox{ � }/M/(m, n).
$$
� ����.~1 ��������� �������� ��� ����~$m, n \le 10$. ��� ������ ���
������� ��������� ����� �������, ���
$$
.M.(m, n)\le M(m, n)\rem{ ��� ���� $m, n\ge 0$.}
\eqno  (8)
$$
풎 ����������� �������� � �������� �������� ������ �������~M, ���������
���~$\abs{m-n}\le 1$ ��� ������ ������� ������� ��������� ���� �������.

%%244
\htable{ ���� 1}%
{������ ������ ��� �������, ����������� ��� ������� "�������"}
{\strut\hfill$#$&&\bskip\hfill$#$\bskip\cr
  &\multispan{10}\hfill$.M.(m,n)$\hfill     &   & \multispan{10}\hfill$/M.(m,n)$\hfill\cr
  & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\cr
\noalign{\hrule}
 1& 1 & 2 & 2 & 3 & 3 & 3 & 3 & 4 & 4 & 4 & & 1 & 2 & 2 & 3 & 3 & 3 & 3 & 4 & 4 & 4 & 1\cr
 2& 2 & 3 & 4 & 5 & 5 & 6 & 6 & 6 & 7 & 7 & & 1 & 3 & 4 & 4 & 5 & 5 & 6 & 6 & 7 & 7 & 2\cr
 3& 2 & 4 & 5 & 6 & 7 & 7 & 8 & 8 & 9 & 9 & & 1 & 3 & 5 & 6 & 7 & 7 & 8 & 8 & 9 & 9 & 3\cr
 4& 3 & 5 & 6 & 7 & 8 & 9 &10 &10 &11 &11 & & 1 & 4 & 5 & 7 & 8 & 9 & 9 &10 &10 &11 & 4\cr
 5& 3 & 5 & 7 & 8 & 9 &10 &11 &12 &12 &13 & & 1 & 4 & 6 & 8 & 9 &10 &11 &12 &12 &13 & 5\cr
 6& 3 & 6 & 7 & 9 &10 &11 &12 &13 &14 &15 & & 1 & 4 & 6 & 8 &10 &11 &12 &13 &14 &14 & 6\cr
 7& 3 & 6 & 8 &10 &11 &12 &13 &14 &15 &16 & & 1 & 4 & 7 & 9 &10 &12 &13 &14 &15 &16 & 7\cr
 8& 4 & 6 & 8 &10 &12 &13 &14 &15 &16 &17 & & 1 & 5 & 7 & 9 &11 &13 &14 &15 &16 &17 & 8\cr
 9& 4 & 7 & 9 &11 &12 &14 &15 &16 &17 &18 & & 1 & 5 & 8 &10 &11 &13 &15 &16 &17 &18 & 9\cr
10& 4 & 7 & 9 &11 &13 &15 &16 &17 &18 &19 & & 1 & 5 & 8 &10 &12 &14 &15 &17 &18 &19 &10\cr
\noalign{\smallskip}
m &   &   &   &   &   &   &   &   &   &   & &   &   &   &   &   &   &   &   &   &   &m \cr
\noalign{\smallskip}
&\multispan{10}\hfill$/M\backslash(m,n)$\hfill& &\multispan{10}\hfill$/M/(m,n)$\hfill\cr
 1&-\infty& 2& 2& 3& 3& 3& 3& 4& 4& 4& & 1 & 1 & 1& 1& 1& 1& 1& 1& 1& 1& 1\cr
 2&-\infty& 2& 4& 4& 5& 5& 6& 6& 7& 7& & 1 & 3 & 3& 4& 4& 4& 4& 5& 5  5& 2\cr
 3&-\infty& 2& 4& 6& 6& 7& 8& 8& 8& 9& & 1 & 3 & 5& 5& 6& 6& 7& 7& 8& 8& 3\cr
 4&-\infty& 2& 5& 6& 8& 8& 9&10&10&11& & 1 & 4 & 5& 7& 7& 8& 9& 9& 9&10& 4\cr
 5&-\infty& 2& 5& 7& 8&10&10&11&12&13& & 1 & 4 & 6& 7& 9& 9&10&11&11&12& 5\cr
 6&-\infty& 2& 5& 7& 9&10&12&13&14&14& & 1 & 4 & 6& 8& 9&11&11&12&13&14& 6\cr
 7&-\infty& 2& 5& 8&10&11&12&14&15&16& & 1 & 4 & 7& 9&10&11&13&14&15&15& 7\cr
 8&-\infty& 2& 6& 8&10&12&13&15&16&17& & 1 & 5 & 7& 9&11&12&14&15&16&17& 8\cr
 9&-\infty& 2& 6& 9&10&12&14&16&17&18& & 1 & 5 & 8& 9&11&13&15&16&17&18& 9\cr
10&-\infty& 2& 6& 9&11&13&15&16&18&19& & 1 & 5 & 8&10&12&14&15&17&18&19&10\cr
\noalign{\hrule}
  &      1& 2& 3& 4& 5& 6& 7& 8& 9&10&n& 1 & 2 & 3& 4& 5& 6& 7& 8& 9&10\cr
}

���������� ������ ��������� ������� �����������, ������� ������������� �������~$M$:
$$
\eqalignno{
M(m, n) &=   M(n,m), &  (9)\cr
M(m, n) &\le M(m, n+1),& (10)\cr
M(k+m,n)&\le M(k,n)+M(m, n), & (11)\cr
M(m, n) &\le \max(M(m,n-1)+1, M(m-1, n)+1),& (12)\cr
M(m, ni)&\le \max(M(m, n-2)+1, M(m-1, n)+2) \rem{��� $m\ge1$, $n\le2$.} & (13)\cr
}
$$
ᎎ��������~(12) ������� �� ������� ��������� �������, ���� ������ ��
��������� ���������~$A_1:B_1$. ᎎ��������~(13) ��������� ����������,
������ � ������ ������� ������������~$A_1:B_2$; ����~$A_1>B_2$, �� �����
��� $M(m, n-2)$~���������, ���� ��~$A_1<B_2$, �� ����� ��������~$A_1$ �
��������������� ����� �
�����~$\set{A_2,~\ldots, A_m}$ �~$\set{B_1,~\ldots, B_n}$. �������� ������,
 ��� ����������� ~(12) �~(13) ����� ��������:
$$
M(m,n)\le\max(M(m,n-k)+1,\quad M(m-1, n)+1+\ceil{\log_2 k})
\rem{��� $m\ge 1$, $n\ge k$,}
\eqno(14)
$$
%% 245
�������� ������� ���������~$A_1:B_k$, � �������� �������� ����� �
������~$A_1<B_k$.

�����������, $M(m, n)=.M.(m, n)$ ��� ����~$m, n \le 10$, ��� ��� � ����.~1
� ���������������� ��������� ����������� �������� ��� �������. 풎 �����
��������, �������� �����������~(9)--(14), � ����� ����������� ����������
���~$(m, n)= (2, 8)$, $(3, 6)$ �~$(5, 9)$, ������� ���������� � ���.~8, 9 �~10.

� ������ �������, ����� ������ �� ������ ���� ��������� ��������� ������
������; ���������� ������: $m=3$, $n=11$, �����~$.M.(3, 11)=9$,
�~$M(3, 11)=10$. 璎�� ������, ��� �� � ���� ������ ��� ������ "�����������",
����� ������� ������, �� ������� �������� ��� �������; ��� ����������
���������� ������������ ��������������, ��� ����~$(i, j)\ne (2, 6)$, ��
������ ����� �������� ���������, ��������� 10~���������;
���� ��~$(i, j)=(2, 6)$, �� �� ���� ��������� ��
����������� ���������~$A(2, 4)$, �������  �������� � ������
������~$1+.M.(2, 3)+.M.(1, 8)=9$. ����������, �� �� ����������, �����
������� ������������ ��������~$\set{A_1, A_2}$
�~$\set{B_1, B_2, B_3}$ �~$\set{A_3}$ �~$\set{B_4,~\ldots, B_{11}}$; �����
�������, ������ ������ � ���� ������ ����������� �� ������.

���������� ����� ��������, ���~$.M.(2, 38)=10$, � �� ����� ���~$M(2, 38)=11$;
������, ��� ������ �� ���������� �������, ����� ���������� ��
�������~$m=2$. ������ ���������� ����������� ����� ��������, ��� �������
�� �������� ����������.

\proclaim ⅎ����~K.
$$
\eqalign{
M(m, m+2)&=2m+1  \rem{��� $m\ge2$,}\cr
M(m, m+3)&=2m+2  \rem{��� $m\ge4$,}\cr
M(m, m+4)&=2m+3 \rem{��� $m\ge6$.}\cr
}
$$

\proof �� ����� ���� �� ����� ���������� ��� �����������, �������~$M$
��~$.M.$; ��� ����� �� ��� ���������� ���� �������� � ������� ���, �������
����� ������������, ���~$m$ ���������� ������. ����� ����� �������, ���
������ ��������� ����~$A_i:B_j$, ���~$i\le \ceil{m/2}$. ����~$j\le i$, ��
������������� ����������~$A'(i,i)$; ����� �������
$$
.M.(m, m+d)\ge1+.M.(i-1, i)+.M.(m+1-i, m+d-i)=2m+d-1,
$$
�������� �������� ��~$d$, $d\le 4$. ����~$j>i$, ��
������������� ����������~$A(i, i+1)$; �������� �������� ��~$m$, �������
$$
.M.(m,m+d)\ge 1+.M.(i, i)+.M.(m-i, m+d-i)=2m+d-1.
$$
\proofend % �������� ������ �� �� �����

������ ��� ����������� �������~K �������� �.~哀� �~�.~���� �~1969~�. 풎
�������������� ���� ��������� ������������,
%%246
��� $M(m, m+d)=2m+d-1$ ��� ���� ���������� �������~$m$, ���~$d$
�����������. (�.~�~���.~6.)

\section ������� ������. ���������� ������ \emph{�������} ������
�������~$M(m, n)$; ������� ������� ������ �������������
����������� ���������� �������.

���~$m=1$ ������ ������� ������������ ������ �������, ����� �������
$n+1$~���� ����� ����������~$B_1$,~\dots,$B_n$, ���� ����� �������
�������~$A_1$. � ���� ������ �������� ������, ��� \emph{�����} �����������
�������� ������ � $n+1$~�������� ������ ���� ������ ��� ���������� ������
�������! (�.~���.~2.) ዅ����������, ����� ������� ����������� ��������
������, ���������� ���������-�������������� ������ ������
$$
1+\floor{\log_2 n}=M(1, n)=\ceil{\log_2(n+1)}.
\eqno(15)
$$
����������, �������� �����~(�.~6.2.1)---���������� ������. �����������
������� ����� ��������.

ዓ���~$m=2$ ����������� ���������, �� �� ������� �������. ��� ���������
����������� �.~�.~������, �.~�.~哀� �~�.~���� (��.~���.~11, 12, 13); �����
$$
M(2, n)=\ceil{\log_2{7\over12}(n+1)}+\ceil{\log_2{14\over17}(n+1)}.
\eqno(16)
$$

�� ������, ��� ���~$m=n$ ���������� ������� ��������� �������, � ���~$m=1$
���������� �������� ������ ������������ �� ��� ��������� ��������� ������.
��� �� ����� ��������� ������������� �����, ������������ � ���� ������
����� ���������� �������� ������� � ��������� ������. 䎐����~(14) �������
�� ����� � ��������� ���������, ������� �� ������� �.~�.~哀�� �~�.~����
[{\sl SIAM J.~Computing,\/} {\bf 1} (1972), 31--39].

\alg �.(�������� �������.)
\st ����~$m$ ���~$n$ �����~0, �� ������������.

����~$m\le n$, �� ����������~$t\asg\floor{\log_2 (n/m)}$.

����~$m>n$, ����������~$t\asg\floor{\log_2 (m/n)}$ � ������� �~\stp{4}.

\st ᐀�����~$A_m:B_{n+1-2^t}$. ���� $A_m$~������, �� ����������~$n\asg
n-2^t$ � ������������ � ����~\stp{1}.

\st ���������������� ������� ��������� ������ (������� ������� ��� �����
$t$~���������), ��������~$A_m$ � ��������������� �����
�����~$\set{B_{n+1-2^t},~\ldots, B_n}$.  ����~$k$---������������ ������,
�����, ���~$B_k<A_m$, �� ����������~$m\asg m-1$ �~$n\asg k$. ������������
�~\stp{1}.

\st (考�~\stp{4} �~\stp{5} ������� �����~\stp{2} �~\stp{3}, ��
����������~$m$, $n$, $A$, $B$ �������� ������.).
����~$B_n<A_{m+1-2^t}$, �� ����������~$m\asg m-2^t$ � ������������ �
����~\stp{1}.

%%247
\st ��������~$B_n$ � ��������������� ����� �����
���������~$A$. ����~$k$---������������ ������, �����, ���~$A_k<B_n$, ��
����������~$m\asg k$ �~$n\asg n-1$. ������������ � ����~\stp{1}.
\algend

� �������� ������� ������ ����� ��������� � ����.~2 ������� �������,
������� ���� ������~$\set{087, 503, 512}$ � ����������� �������~$\set{061,
154,~\ldots, 908}$; � ���� ������� ����������� ������ ���������.

{\catcode`\[=\active\def[{\hbox to 0pt{\hss$\{$}}
\catcode`\]=\active\def]{\hbox to 0pt{$\}$\hss}}
\catcode`\!=\active\def!#1 {\bf#1}
\htable{ ����~2}%
{������ ���������� ������ ��������� �������}%
{$\scriptstyle\phantom{\{}#\phantom{\}}$\bskip&&$\scriptstyle\phantom{\{}#\phantom{\}}$\bskip\cr
\multispan{9}\hbox{� (������������ ���������� ��������)} &\omit\span\hfill\hbox{�}\hfill &\multispan{8}\hfill\hbox{�����}\cr
[087   & 503   & !512 ]&[061 & 154 & 170 & 275 & 426 & 509 & 612 &  653 & 677 &!703 & 765 & 897 & 908]\cr
[087   & 603   & !512 ]&[061 & 151 & 170 & 275 & 426 & 509 & 612 & !653 & 677]&     &     &     & [703 & 765 & 897 & 908]\cr
[087   & 503   & !512 ]&[061 & 154 & 170 & 275 & 426 &!509 & 612]&    &     &     &[653 & 677 & 703 & 765 & 897 & 908]\cr
[087   & 503   & !512 ]&[061 & 154 & 170 & 275 & 426 & 509 &!612 ]&    &     &[653 & 677 & 703 & 765 & 897 & 908]\cr
[087   & !503]&       &[061 & 154 & 170 & 275 & !426 & 509]&     &    &[512 & 612 & 653 & 677 & 703 & 765 & 897 & 908]\cr
[087   & !503]&       &[061 & 154 & 170 & 275 & 426 & !509 ]&     &    &[512 & 612 & 653 & 677 & 793 & 765 & 897 & 908]\cr
[!087 ]&       &       &[061 & !154 & 170 & 275 & 426]&     &[503 & 509 & 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908]\cr
[!087 ]&       &       &[!061 ]&     &[154 & 170 & 275 & 426 & 503 & 509 & 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908]\cr
       &       &       &[061 & 087 & 154 & 170 & 275 & 426 & 503 & 509 & 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908]\cr
}
}

�����~$H(m,n)$---������������ ����� ���������, ����������� ���������� 哀��
�~����. 璎�� ���������~$H(m, n)$, ����� ������������, ���~$k=n$ � ����~H3
�~$k=m$ � ����~H5, ��������� ��� ������ �������� ��~$n$ ��������
��������,
���~$H(m, n)\le H(m, n+1)$ ��� ����~$n\ge m$.  �� �������, ���~$m\le n$ �����
$$
H(m, n)=\max(H(m,n-2^t)+1,  H(m-1, n)+t+1) \rem{���~$2^t m \le n < 2^{t+1}m$.}
\eqno  (17)
$$
�������~$n$ ��~$2n+\varepsilon$ ($\varepsilon=0$ ���~1) � �������
$$
H(m, 2n+\varepsilon)=
 \max(H(m, 2n+\varepsilon-2^{t+1})+1, H(m-1, 2n+\varepsilon)+t+2)
\rem{���~$2^t m \le n < 2^{t+1} m$.}
$$
������ ��������, ���� ��������� �������� ��~$n$, ���
$$
H(m, 2n+\varepsilon)=H(m, n)+m \rem{���~$m\le n$,  $\varepsilon=0$ ���~1.}
\eqno (18)
$$
����� ������ �����, ���~$H(m, n)=m+n-1$, ����~$m\le n < 2m$. ዅ����������,
 ������������ ���������� �������~(18) ���� ��� ����� �������
$$
H(m, n)=m+\ceil{n/2^t}-1+tm \rem{���~$m\le n$, $t=\ceil{\log_2(n/m)}$.}
\eqno (19)
$$
%%248

�������~$m=\alpha n$ �~$\theta=\log_2 (n/m)-t$, ������
$$
H(\alpha n, n)=\alpha n(1+2^\theta-\theta-\log_2 \alpha)+O(1)
\eqno (20)
$$
���~$n\to\infty$. �� ������~(5.3.1-35) ��������,
���~$1.9139<1+2^\theta-\theta\le2$. ዅ����������, (20)~����� �������� �
���������-�������������� ������ �������~(3). 哀� � ����
�������� (��.~���.~17), ���
$$
H(m, n) < \ceil{\log_2\perm{m+n}{m}}+\min(m, n).
\eqno(21)
$$
�������� ������� 哀��---����, ������� ����� ���� �� ������� ����������
"��������� �������", �� ������ ���������, �� �������� ��� ����������
������������, ��� ��� �������� ����� �����������������. �� �������� �
"����������������� ��������� ������" ���~$m=1$ � � ������� ���������
������� ���~$m\approx n$, ��� ��� ��� ������� �������� ����� �����
���������� ��������. ����� ����, �� ������ ������� �� \emph{��������}
����������� (��.~���.~16).

䎐����~(18) ������� �� ����� � ���, ��� � ���� �������~$M$, ���� �����,
������������� �����������
$$
M(m, n)\le M(m, \floor{n/2})+m.
\eqno (22)
$$
풎 � � ����� ���� ��� (��.~���.~19).  ���� �������� �������~$M(m, n)$
��������� ������������, ���, ��������, ����� ����� � ������ �����������,
�����, ���
$$
\displaylines{
\hfill M(m+1, n)\ge 1+M(m, n)\ge M(m, n+1) \rem{��� $m\le n$;} \hfill\llap{(23)}\cr
\hfill M(m+1, n+1)\ge 2+M(m, n).            \hfill\llap{(24)}\cr
}
$$
�� � ��������� ����� �� �������� ������� ������������� ���� ����������.

\excercises
\ex[15] ������� ���� ���������� �����������, ������� ���������
�������~$M(m, n)$ � �������~$S$, ������������ � �.~5.3.1.
[\emph{㊀�����:} �����������~$S(m+n)$.]

\rex[22] ���~$m=l$ ����� �������� �������, �� ���������� ����������
���������, ���������� ����������� �������� ������ �
$\perm{m+n}{m}=n+1$~�������� ������. ��������, ��� ����� � ��������,
�.~�.~������� ������������  ��������� ������ ������������� ���������
�������� ������� �~$m=1$.

\ex[�24] ��������, ���~$.M.(1, n)=M(1, n)$ ��� ����~$n$.

\ex[�44] Ꮠ�������� �� �����������~$.M.(m, n)\ge
\ceil{\log_2\perm{m+n}{m}}$ ���
����~$m$ �~$n$?

\ex[�30] ��������, ��� $.M.(m, n)\le .M\backslash (m, n+1)$.

\ex[�26] ᔎ������������� ���� �������������� �������~K ������� ��������
�������� ����� ������� � ������������ ���. ����� ������� ����� �����
��������� ����� ����� �������?

%%249
\ex[21] �������� �����������~(11).

\rex[24] ��������, ���~$M(2,8)\le 6$. ��� ����� ���������� �����
�������� ������� ���� ��������� � ������� �������, ������� �� ��������
�� ����� ����� ���������.

\ex[27] ��������, ��� ��� �������� ����� ����� � ������ ���������� ��
����� ��� �� ���� �����.

\ex[33] ��������, ��� ���� ��������� ����� ����� � ������� �� ����� ��� ��
���������� �����. [\emph{㊀�����:} ���� �������� ������� ������������,
��� ������ ����� �� ���������~$A_1:B_2$, �����, ����~$A_1<B_2$, ����������
��������~$A_5:B_8$.]

\ex[�40] (�.~哀�, �.~����.) �����~$g_{2k}=\floor{2^k\cdot{17\over14}}$,
$g_{2k+1}=\floor{2^k\cdot{12\over 7}}$ ���~$k\ge 0$, ���
���~$(g_0, g_1, g_2,~\ldots)=(1, 1, 2, 3, 4, 6, 9, 13, 19, 27, 38, 54, 77,~\ldots)$.
��������, ��� ��� ������� ���� ��������� �~$g_t$~����������
��������� � ������ ������ ����� ��� $t$~���������, ������ ����� ���
�������� �~$g_t-1$ ����� �� ����� ��� �� $t$~�����. [\emph{㊀�����:}
��������, ��� ����~$n\ge g_{t-1}$, � ����� �����~$\set{A_1, A_2}$
�~$\set{B_1, B_2,~\ldots, B_n}$ �� $t$~���������, �� ��������� ������
���������---���~$A_2:B_{g_{t-1}}$.]

\ex[�21] �����~$R_n(i,j)$---���������� ����� ���������, �����������
��� ���������� ��������� ��������~$\set{\alpha, \beta, X_1, X_2,~\ldots, X_n}$,
���� ������ �����������
$$
\alpha<\beta, \quad X_1<X_2<\ldots<X_n, \quad \alpha<X_{i+1}, \quad \beta > X_{n-j}.
$$
[㑋����~$\alpha< X_{i+1}$ ���~$\beta>X_{n-j}$ ������ �����, ����~$i\ge n$
���~$j\ge n$. �������~$R_n(n,n)=M(2, n)$.]

�, ���~$R_n(0, 0) = 0$. ��������, ���
$$
R_n(i,j)=1+\min\left(\min_{1\le k \le i} \max(R_n(k-1, j), R_{n-k}(i-k, j)),
\min_{1\le k \le j} \max(R_n(i, k-1), R_{n-k}(i, j-k))\right)
$$
��� $0\le i \le n$, $0\le j \le n$, $i+j>0$.

\ex[M42] (P.~�.~������). ��������, ��� ������� ������������� �����������
�� ���.~12 ����� �������� ��������� �������. ��������� �������~$G(x)$
���~$0<x<\infty$ ������ ���������:
$$
G(x)=\cases{
\mathstrut 1,  & $0<x\le {5\over 7}$;\cr
\mathstrut {1\over2}+{1\over8}G(8x-5), & ${5\over 7} < x \le {3\over 4}$;\cr
\mathstrut {1\over2}G(2x-1), & ${3\over4}<x\le 1$;\cr
\mathstrut 0, & $1\le x \le \infty$.
}
$$
(�.~���.~38.) ���������~$R_n(i,j)=R_n(j,i)$ � ��� ���~$R_n(0, j)=M(1, j)$,
 �� ����� �������, ���~$1\le i \le j \le n$. �����~$p=\floor{\log_2 i}$,
$q=\floor{\log_2 j}$, $r=\floor{\log_2 n}$ �~$t=n-2^r+1$. ⎃��
$$
R_n(i,j)=p+q+S_n(i,j)+T_n(i,j),
$$
��� �������~$S_n$ �~$T_n$ ��������� ��������~0 ���~1:
$$
\eqalign{
S_n(i,j)&=1 \hbox{ ����� � ������ �����, ����� $q<r$ ���~$(i-2^p\ge u$ �~$j-2^r\ge u$);}\cr
T_n(i,j)&=1 \hbox{ ����� � ������ �����, ����� $p<r$ ���~$\left(t>{6\over7}2^{r-2}\hbox{ � } i-2^r\ge v \right)$,} \cr
}
$$
���~$u=2^pG(t/2^p)$ �~$v=2^{r-2}G(t/2^{r-2})$.
%%250

(풎, ���� �����, ����� ������� ������������ ����������� �� ����, �������
�����-���� ����� ������!)

\ex[46] (哀� �~����.) �����~$h_{3k}=2^k+2^{k-1}-1$,
$h_{3k+1}=g_{2k}+g_{2k-3}+2^{k-2}$, $h_{3k+2}=2g_{2k}$ ���~$k\ge 2$, ��
�����������~$h_8=9$, � ��������� �������� ��������� ���, ���~$(h_0, h_1,
h_2,~\ldots)=(1, 1, 2, 2, 3, 4, 5, 7, 9, 11, 14, 18, 23, 29, 38, 47, 59,
76,~\ldots)$.
�����~$g_k$---�������, ������� ���� ���������� � ���.~11. �������� (���
������������), ���~$M(3, h_t)>t$, $M(3, h_t-1)\le t$ ��� ����~$t$.

\ex[12] � ����~H1 ��������� ��������� ������� �����
������������� ���������� ��������~$\floor{\log_2 (n/m)}$. ��� ����� �����
��������� ��� ��������, �� �������� �������� ������� � ������ ���������?

\picture{���.~38. 䓍���� ������� (��.~���.~13).}

\ex[18] ��� �����~$m$ �~$n$, $1\le m \le n \le 10$, ��������� ��������
��������� ������� 哀�� � ����?

\ex[�25] �������� �����������~(21). [\emph{㊀�����:} ��� ����������� ��
����� �������.]

\ex[�40] ���������� \emph{�������} ����� ���������, �����������
���������� ��������� �������.

\rex[23] ��������, ��� �������~$M$ ������������� �����������~(22).

\ex[20] ��������, ��� ����~$M(m, n+1) \le M(m+1, n)$ ��� ����~$m\le n$,
 ��~$M(m, n+1)\le 1+M(m, n)$ ��� ����~$m\le n$.

\ex[�47] �������� ��� ������������ �����������~(23), (24).

\ex[�50] ���������� ����������� \emph{�������} ����� ���������,
����������� ��� ������� $m$~��������� � $n$~����������.

\ex[��30] (�.~���������.)
�����~$\set{A_1,~\ldots, A_n}$ �~$\set{B_1,~\ldots, B_n}$---���������,
���������� �� $n$~��������� ������. ����������� ��������, ������� ��������
��������� ������� ��������� ����� ����������� ������������� �����
��������� �� ��������� ��������� ���� ��������.  �� �������, ��������
������ ������� ����~"$A_i=B_j$?" ��� ���������~$i$ �~$j$ � ��������
���������� ���� ���������� � ����������� �� ����, ��� �� �����
������������� ��� �������������.

��������� ����������� �������, ��������, ��� ����� ����� ��������
� ��������� ��� ���� ������ �������� ��������� �� �����
${1\over2}n (n+1)$~���������.

%%250
\subsubchap{* ����� � ����������� ������ ���������} % 5.3.3
��� ������ ��������� ��������� �������� ��� ������ $t\hbox{-��}$~��������
� ������� �������� �� $n$~��������� �� ����������� � ������� �����,
�������� ������������� � ���������� ������. ������� ����� �������
�������� � �������������� (���� � ����������) ������ ������������
�.~�.~�������� � �������� �� �������, ������������ � St.~James's Gazette
1~������� 1883~�. (���.~5--6). �������, �������, ����������, �����
�������� ��� ����� ������, ������������ �������������� �������, ��
������� ������������ (� �� ��� ��� ������������) ����� � �������� ��
�������. ����������, ��������, ���.~39, ��� ������� �������� ������
"� ����������" ����� 32~��������, ����������� $01$, $02$,~\dots, $32$. �
������ �����~$01$ ���������� ������ ��� �������~$05$, ������� ����, ���
�����~$01$---������� � �������� ������ ����. ���������������� ����������� �
���, ��� �����~$05$ ������ �������� ������ ����, ���� �� ����� � �� ����
������ �������. �������� ������ ���� �����, ���� ���� ������� ����
�������� ������� �������. � ����� ����, ��� ������� �������, ������ �����
���������� ������ ���� � ��� � ������ ��� ������, ���� ������������� �� �
������� ���������� � ��������������� ��������� �������; ���
$2^n$~������� ��� ���������� � ������������~$2^{n-1}/(2^n-1)$, ���
��� ����� � �������� ������� ������ ���� �������� �� ��� �����! ����
����������� � ���������� (������~$25$ �~$17$ �� ���.~39) ����������� ��
������ ����, �� ������ ������������, ��� ������ ����� ������� ������ ����.

������� ������� ����� ����� ����� ������, ������� ��������� ����������
������� � �������� ������� � ������������� ��������������. (����� ������,
 ���� �����~$A$ ��������� ������~$B$, �~$B$ ���������~$C$, �� �����
�������, ��� �����~$A$ �������~$C$). �� �������� ���������, � �������
����������� ���� ������� ��� ��������� ���, ���� �� ������
����������� ��������, ��� ��� ���� ������ ���� �������. ������
����� �������� ���������� �� ���.~40, ������������ �������������� ������,
 ������� ������� �������� ������ � ��������, ���������� �� ���.~39.
�������� ������� ������������ ������� �������, � ������� �� ��� ��� ����
������ ����������, � ��������� ����� ����� ��������, ������������ ����� �
��� �� ���������. ��������, �����~$16$ �����������~$11$, �
�����~$13$ �����������~$12$ � ������ ����; ����� ���� ��� �����~$16$
�����������~$13$ �� ������ ����, $16$~�����������, ��� ���
������ ��������, ��� �� ����, ���~$11$, $12$ �~$13$. � ������� ���� ��
�� ��������� ������~$19$ ������ �~$21$, ��� ��� ��� ��� ���� ���������
%%252
\picture{���. 39. ⓐ��� 32~������� � ����������.}
%%253
\picture{���. 40. ⅍������ ������ ������ ������� (� ���������� � �������
���.~39).}
%% 254
�������~$18$ � �� �� ����� �� ������������� ��������� ������������
�� �������~$19$ �~$21$.

���� �� ������� ��������, ��� ������ ������ ������� �������� �����������,
��, � ���������, ��� �� ���. �� ������ � ��� �������� �� 23~���� 1883~�.
��������, ��� �� �������� ���� ����� �������� �� ����� �����, �
����������, ���, "��������� ��������� ����� ������������ � �����, �����
������� �������� ���������, �� ������� ��������� ���������". � ���
��������� �������� ������ ���������, ��� ����������, � ��� ��
�������������� ���������� �����, ����� ��������������� �� ��� ��������.
� ������ �������, � ��� ������� ��������� ����� ���������� �������, ����
������ � ����� ������ ������������ ����������. ��� ����� ��������������
�������� ����������� ���������� �������, ��������� ������ ������� � ���
��������� ������������� ��������; ��������, �� ���������, ��� ���
��������� ������ ���������� ����� ��� � ������� "�������" ���� � �����~6
�~7. ������ ������������ ��������, ��-��������, ����� ��� �����������
������� ��������, � ������ ������� �������, ������ �����, ������� ��
������������. ������ ����� ������������ ����� "�����������" �����
������� �������, ����� ��� ������ � ������ ����� ������.

�� �������������� �������� �~1929--1930~�. ���� 蒅������ �������� ������
���������� ������������ ����� ��������� ������, ��������� ��� �����������
������� � ������� ������� � �������, ���� �������
$n >2$~�������. �.~萅��� [{\sl Mathesis Polska,\/} {\bf 7} (1932),
154--160] ������ ���������, ��������� ����� �������
$n-2+\ceil{\log_2 n}$~������, �����������, �� ��������, ��� �� �����, ���
� ������ ��� ������ ��������, ������� �� ������� ����������� �����������
������ �� ������ (��.~�.~5.2.3, ���.~23), ������ �� ��������
�������������� ���������, ����������~$-\infty$. 萅��� ����� ���������,
��� $n-2+\ceil{\log_2 n}$---��������� ��������� ��������; �� ���
�������������� ���� ���������, ��� � ��� ���� ������� ��������������,
������������ �.~ዓ�����
[{\sl Colloquium Mathematician,\/} {\bf 2} (1951), 286--290].
������ 32~����, ������ ��� �.~�.~���������� ���� ������������ ����������,
 ���� � ����� ������� ��������������
[{\sl ሁ������ �������������� ������,\/} {\bf 5} (1964), 557--564].
�����~$V_t(n)$ ���~$1\le t \le n$ ���������� ����������� ����� ���������,
��������� ��� ����������� $t\hbox{-��}$ � ������� �������� �������� ��
$n$~���������, � ����� $W_t(n)$~����� ����������� ����� ���������,
 ����������� ��� ����������� �����������, �������,~\dots,
$t\hbox{-��}$ ��������� ���� �����. �� ����������� ��������� �����
$$
V_t(n)=V_{n+1-t}(n);
\eqno(1)
$$
%%255
�������� �����, ���
$$
\eqalignno{
V_1(n)&=W_1(n), & (2) \cr
V_t(n)&\le W_t(n), & (3) \cr
W_n(n)&=W_{n-1}(n)=S(n). & (4) \cr
}
$$

� �.~5.2.3 �� ������, ���
$$
V_1(n)=n-1.
\eqno(5)
$$
���� ����������� ������� �������������� ����� �����, ��������� ������
�������� �������, ����� ��������, ������ ��������� �� ������� ���� ����
����! ������� ��� ���� � ��������� "�������", �� ����� ��� ������� �����
�������� ������� 萅����---���������.

\proclaim ⅎ����~S. ���~$n\ge 2$ �����������
���������~$V_2(n)=W_2(n)=n-2+\ceil{\log_2 n}$.

\proof �����������, ��� � �������, ��� � ������� ��������� ������
��������� ������ ������������ ������ �����, ��������� $n$~�������, �
�����~$a_j$---����� �������, �����������~$j$ ��� ������ ������. �����
����� ��������� ������ ����� ����� �����~$a_1+a_2+a_3+\ldots\,$. �� ��
����� ���������� ������� ������, �� ������ ������ � �������� (��.~���.~2),
 ������� �� ���������� �����������~$a_1=n-1$. ��� ����������
�������������� �������, ��� ������ ���������� ������������������
����������� ������, ������� �������� �~$a_2\ge \ceil{\log_2 n}-1$.

�����������, ��� � ����� ������� ������� ������ $p$~��� � �������
$p$~�������; ����� �� ��� ��� ������ �����, � ��������� ������ ���������
�� ������� ���� ��� �� ������ ����, �������~$a_2\ge p-1$. ����, �� �����
��������� ��������������, �������� �������, ����������������� ����������
��� ����� �������, ����� �������� �������� ������� �� ������� ���� ���
�~$\ceil{\log_2 n}$~������� ����������� �������.

����� ������ �������, ��� �����~$A$ �����, ���~$B$, ����~$A$ ����� ��
����������, �~$B$ ���� �� ������� ��������, ��� ���� ��� �� �����������,
�� $B$~������� � ����� ������� ������ ������, ���~$A$. ��� ������
��������������� ������ ����� ��������� ������������ �������, ��
�������������� ���������� ���������� ������������.

���������� ���������� ������������ �������, �����
�������� ���������������� ����� ��������. �� ������, ��� "$A$
����������� $B$" ����� � ������ �����, �����~$A=B$ ���
$A$~����������� ������, ������� ������ �������~$B$. (⎋��� ������
��������� ������ ����������� � ���� ���������, ����������� ���
���� ������������. � ������������ � ����������� ������� ����� �����,
\emph{������} ���������� ������-��, �� � ����� �� ���������� ������ ��
������ ����� ���������. ������ �������, ���
%%256
�����, ������� ������� ���� ������ $p$~������, ����������� �� ���������
���� $p$~��� �� ����� $2^p$~�������. (����~$p=0$, ��� ��������, ���� ��
$p>0$, �� $p\hbox{-�}$~���� ��� ������ ������ ������, ������� ���� �����
�������� ���������, ���� ����������� �� �����~$2^{p-1}$~�������.) 煌����
����������� ����, ������� �� ������ ��� ������� �� �����
$\ceil{\log_2 n}$~������.
\proofend

 �� �������, ������ ���������� ������� � ������� �������� ��������
��������� ������ � ����������� ������. � ���.~6 ��������, ��� ����� ����
������� ������� ��� ������������ ����� ���������, ����������� ���
��������� ������� �������� ���������, ���� �������� ������������
��������� ������������ ���������.

\qsection � ���� $t>2$? � ���������� ������ �������� ����� ������. ��
���������� ������� ��������~$t$, �������, ���
$$
W_t(n)\le n-t+\sum_{n+1-t<j\le n} \ceil{\log_2 j} \rem{���~$n\ge t$.}
\eqno  (6)
$$

�� ������, ��� ���~$t=1$ �~$t=2$ ��� ������� ������������ ����� ���������;
���~$t=3$ ��� ����� ���� ������ �������� (��.~���.~21).

�� ������� ������� ���������, �������, ��� ������ $t$~������ \emph{������
�� ������} ������� �� �����~$n-t+\sum_{n+1-t<j\le n}\ceil{\log_2 j}$
��������� (�������� ��� ���������, ����������~$-\infty$). ���������, ���
������ �����~(6) �����~$B(n)$, �����~$t=n-1$
�~$t=n$ [��.~�������~(5.3.1-3)]; �������������, ����� �� ������ �
�������� ������� �������� � ����� � ��� �� ������� ������ ��� ������
����������, ���� ��� ���������� ��������� ������.

�����~$\alpha$---����������� �������� ������ � $n$~�������� ������
�~$\pi$---������������ ���������~$\set{1,2,~\ldots, n}$. �������� ��������
������������~$\pi$ �� ������� ���� ����� ������� � ������������ ������� �
�������� ���������� ���� � ������������ � ��������� ������� � ����������
��� ��� ������ �� ������. ��������� ���������� �������� ������ �
��������������� ������ ���������� ������������������~$c_{n-1}
c_{n-2}~\ldots c_1$, ��� $c_j$~���� ����� ���������, ���������, �����.
��������� �������~$j$ � ������ ������, ����� ���� ��� �������~$j+1$ ���
������� ��~$-\infty$. ��������, ���� $\alpha$---������
\picture{p.256}
%%257
�~$\pi=5\ 3\ 1\ 4\ 2$,�� �� �������� ���������������� �������
\picture{p. 257.1}
���� �� $\pi=3\ 1\ 5\ 4\ 2$, �� ������������������~$c_4c_3c_2c_1$
����� ����, ������~$2\ 1\ 1\ 0$. ����� ������, ��� $c_1$~������ ����~0.

�����~$\mu(\alpha, \pi)$---���������������~$\set{c_{n-1}, c_{n-2},~\ldots,
c_1}$, ������������~$\alpha$ �~$\pi$. ����
\picture{p.257.2}
� ���� ��������~1 �~2 �� ���������� ��� ���� �~$\alpha'$, ����
�~$\alpha''$, �� ����� ������, ���
$$
\mu(\alpha, \pi)=(\mu(\alpha', \pi')+1)\uplus (\mu(\alpha'', \pi'')+1)\uplus\set{0}
\eqno(8)
$$
��� ���������� ������������~$\pi'$ �~$\pi''$, ���
$(\mu+1)$~���������� ���������������, ���������� ������������~1 � �������
��������~$\mu$. � ������ �������, ���� � �������~1, � �������~2
��������� �~$\alpha'$, �����
$$
\mu(\alpha, \pi)=(\mu(\alpha', \pi')+\varepsilon)\uplus(\mu(\alpha'', \pi'')+1)\uplus\set{0},
$$
��� $(\mu+\varepsilon)$~���������� �����-������ ���������������,
���������� ������������~1 � ��������� ���������~$\mu$ �~0 � ���������.
����������� ������� �����������, ���� ��������~1 �~2 ���������
�~$\alpha''$. ����� ��������, ��� ���������������~$\mu_1$
����������~$\mu_2$, ����~$\mu_1$ �~$\mu_2$ �������� ������ �����
��������� � $k\hbox{-�}$ � ������� �������� �������~$\mu_1$ ������ ���
�����~$k\hbox{-��}$ � ������� �������� ��������~$\mu_2$ ��� ����~$k$.
���������~$\mu(\alpha)$ ��� ���������~$\mu(\alpha, \pi)$ �� ����
�������������~$\pi$ � ��� ������, ���~$\mu(\alpha)$
����������~$\mu(\alpha,\pi)$ ��� ����~$\pi$ �~$\mu(\alpha)=\mu(\alpha, \pi)$
��� ���������~$\pi$. ����������� ���� ������� ����������, ���
\picture{p.257.3}
�������������, \dfn{$\mu(\alpha)$ ���� ��������������� ���� ����������
�� ����� �� ���������� �����~$\alpha$.}

%% 258

���� �������� ������� �� ����� ����� �����������, ��� ������ ���� ����,
��� ������ �� ������ �������� ������� ���������~(6), ���������
$W_t(n)$~������ ��� ����� $n-1$~����~$t-1$ ����������
���������~$\mu(\alpha)$, ��� $\alpha$---����� ������, ������������ ���
���������� ����������� ������ �� ������. ����� ������� � ��������~$\alpha$
������ �������� ������ � $n$~�������� ������ (��.~�.~2.3.4.5); � ���� ������
$$
\eqalignno{
\mu(\alpha) &=\set{\floor{\log_2 1}, \floor{\log_2 2}, \ldots, \floor{\log_2(n-1)}}=\cr
&=\set{\ceil{\log_2 2}-1, \ceil{\log_2 3}-1, \ldots, \ceil{\log_2 n}-1}.
&(10) \cr
}
$$
�� ������� �������~(6), ���� ���������� $t-1$~���������� ��������� �����
���������������.

ⅎ���� ��������� ���� ������� ������� ������ ���~$W_t(n)$; ��������
�������, ���~$V_3(5)=6 < W_3(5)=7$, �� �� ���� ����� � ����� ������ ������
������ ���~$V_t(n)$. 풎 ���� ������� �.~������� �~�.~ᎁ����, �������
������������ \emph{����� � ����������} ������ ������ �� ������
(��.~�.~5.4.1). ���������� ��� ������� [Univ.\ of~Minnesota,
Dept.~of~statistics, report~121 (May, 1969)]
$$
V_t(n)\le n-t+(t-1)\ceil{\log_2 (n+2-t)}, \rem{$n\ge t$,}
\eqno(11)
$$
���������� ��~(6) ���, ��� ������ ������� ����� �~(6) ������� ��
���������� �������.

ⅎ���� ������ �~ᎁ��� ����� ��������, ���������������� ���������
�����������. ፀ���� �������� �������� ������ ��� ������� � ����������
$n-t+2$~���������. (풎 ������� $n-t+1$~���������.) ���������� �������
����������� $n-t+1$~������ ���������, ������� �� �� �����
����~$t\hbox{-�}$ � ������� ��������. ������� ��� �� ������� ���� ������
�� ���� �� $t-2$~���������, ���������� � �������, � ������ ���������� ��
������������ $n-t+2$~���������; ��� ������� �� ����� $\ceil{\log_2
(n+2-t)}$~���������, ��������� �������� ������ ��������� ������ ����
���� � ������. �������� ��� �������� ����� $t-2$~���, �� ������ ���� ���
������� �������� �� �������. �������, ������� ������� ���������� �������
��~$-\infty$ � ��������� ���������� �� ���������� $n+1-t$~���������;
��� ����� ����������� �� ����� $\ceil{\log_2 (n+2-t)}-1$~���������,
�~$t\hbox{-�}$ � ������� �������� ������� ��������� ��������� ������� �
������ ������. ᓌ��������� ��������� ����~(11).

����������, �� ������ ��������~$t$ ��~$n+1-t$ � ������ �����
�����������~(11), ���� $n+1-t$~���� ������ �������� (��� ���~$n=6$, $t=3$).
 ��� �� �������, �� ��� ������� ���� ���~$V_7(13)$ ������� ������, ���
���~$V_6(13)$. ������� ������ �~(11) ����� ���~$n\le 6$, �� �����~$n$
�~$t$ ���������� ��������, ����� �������� ����������� ������ ������
���~$V_t(n)$.

%%259

��������, ����� ������������ ��������� ������� ����� (������������� ������
������), ����� ��������, ���~$V_4(8)\le12$. ��������� �������� �����~$X_1,
~\ldots, X_8$; ������� �������~$X_1:X_2$, $X_3:X_4$ � ���� �����������,
��������� �� �� ���~$X_5:X_6$, $X_7:X_8$, � �� �����������. �����������
�������� ���, ����� ��������~$X_1<X_2<X_4>X_3$, $X_5<X_6<X_8>X_7$, �����
�������~$X_2:X_6$;
� ���� ��������� �������~$X<2<X_6$, ������� ����� ������������
\picture{p.259.1}
(⅏���~$X_1$ �~$X_8$ ����� �� ����, � �� ������ ����� ������ � �������
�������� ������� ��~$\set{X_2,~\ldots, X_7}$.) ᐀����~$X_2:X_7$, �
�������� �������; � ������ ������ �������~$X_2<X_7$, � ��� ���� �����
������ � ������� �������� ������� ��
\picture{p.259.2}
풎 ����� ������� ��� �� $V_3(5)-2=4$~����, ��� ��� ��������� ���~$t=3$
�~$n=5$ �~(11) ���������� �� ��������� ���� ���������������� ��� ���������.

����� ������������ ������ ����� ��������� ����, ����� �������� ����������,
���������� � ����.~1; �� ��� ��� �� ����� �������� ������ ������, �
�������� � ������� ���~$n\ge8$ ����� ���������� ���������. �������,
���~$V_3(10)\le 14$, ������� (11)~�� ������ ���� ��������� ���~$t=3$. ⎒
����, ���~$V_4(7)=10$, ����������, ��� �����������~(11) �������� � ������
��~2 ��� ���~$n=7$.

�������� ������ ������ � ������ ������ ������� ����� ����������
(Ph.~D.~thesis, Univ.\ of~Toronto, 1974]. ����������� �� ������
����������, ���
$$
V_t(n)>n+t-3+\sum_{0\le j\le t-2}\ceil{\log_2((n+2-t)/(t+j))},
\rem{$n\ge 2t-1$.}
\eqno(12)
$$
���������� ����� ��������� ��������� �������~$V_t(n)$ ���~$t=3$, �������,
���~$V_3(n)=n+\ceil{\log_2 ((n-1)/2.5)}+\ceil{\log_2((n-1)/4)}$ ���
����~$n\ge 50$ (��.~�~���.~22).

\section �������� �����. ���� $n$~������� �~$t=\ceil{n/2}$,
��~$t\hbox{-�}$ � ������� �������� (�~$t\hbox{-�}$ � ������� �����������)
������� ���������� ��������. � ������������ �~(11) �� ����� ����� �������~$n$
%%260
{\catcode`\!=\active\def!{\hbox to 0 pt{${}^*$\hss}}
\htable{ ���� 1}%
{��������� �� ��������� ������� ������ ��� $V_t(n)$}%
{\strut\bskip\hfill$#$\bskip&&\bskip\hfill$#$\bskip\cr
n  & V_1(n) & V_2(n) & V_3(n) & V_4(n) &  V_5(n) & V_6(n) & V_7(n) & V_8(n) & V_9(n) & V_{10}(n)\cr
\noalign{\hrule}
 1 & 0 \cr
 2 & 1 &  1 \cr
 3 & 2 &  3 & 2  \cr
 4 & 3 &  4 & 4  &  3 \cr
 5 & 4 &  6 & 6  &  6 &  4 \cr
 6 & 5 &  7 & 8  &  8 &  7 &  5 \cr
 7 & 6 &  8 & 10 & 10!& 10 &  8 &  6\cr
 8 & 7 &  9 & 11 & 12 & 12 & 11 &  9 & 7\cr
 9 & 8 & 11 & 12 & 14 & 15!& 14 & 12 & 11  &  8\cr
10 & 9 & 12 & 14!& 15 & 17 & 17 & 15 & 14! & 12 & 9 \cr
\noalign{\hrule}
\multispan{11}\hbox{$*$)~� ���� ������� ���.~10--12 ���� ����������, ����������� ��������~(11).}\cr
}}%
��������� �� $\approx {1\over2}n\log_2 n$~���������, �� ��� ���� ��������������
����� ������� ����������, ���� ��� ����� ����������� ������� ����������.
� ������� ���������� ��� ������������ ������ ���� �������������� ����
���������� �� ��������� �������~(11) ��� ������� ��������~$t$ �~$n$;
�������, � 1971~�. ������� ���� ������ �����, ��������� ������
$O(n \log \log n)$~�����. ������ ����� � ���� ������ ��� ������ � ��������
������ ������ �������, ������� ������ � ���������� ����������, ��������������
�.~�������� �~�.~‐����.

\proclaim ⅎ����~L. ����~$n>32$, ��~$V_t(n)\le 15n-163$ ���~$1\le t\le n$.

\proof ����� $n$~����, ������� ����������, ���
���~$V_t(n)\le S(n)\le 10n\le 15n-163$  ���~$32<n\le 2^{10}$. �������
����� ������� 13~��������� ���������~"$-\infty$", ����� �������,
���~$n=7(2q+1)$ ��� ��������� �����~$q\ge 73$. ⅏��� ���
������ $t\hbox{-��}$ � ������� �������� �������� ������������� ���������
�������.
\medskip
{\sl 考~1.\/}~�������� �������� �� $2q+1$~����� �� 7~��������� � ������ �
����������� ������ ������. 풎 ��������� �� ����� $13(2q+ 1)$~���������.

\smallskip
{\sl 考~2.\/}~������ ������� �� $2q+1$~������, ���������� �� ����~1, �
��������� ��~$x$. ������� �������� ��~$q$, ��������, ��� ��� ������� ��
����� $V_{q+1}(2q+1)\le 30q-148$~���������.

\smallskip
{\sl 考~3.\/}~⅏��� $n-1$~���������, �������� ��~$x$, ����������� �� ���
��������� (���.~41):
%%261
\medskip
$4q+3$~���������, � ������� ��������, ��� ��� ������~$x$ (������� �);

$4q+3$~���������, � ������� ��������, ��� ��� ������~$x$ (������� �);

$6q$~���������, ��������� ������� �~$x$ ���������� (������� A, D).
\medskip

\noindent �������� ������������� $4q$~���������, �� ����� �
�������� �������, ����� �������� �� ��������~� �~D ������~$x$. (ፀ���� ��
����������~$x$ �� ������� ��������� ������ ������.)
\picture{���. 41.           �������� ������ �������� � ‐���� ($q=4$).}
\smallskip
{\sl 考~4.\/}~⅏��� ��� ���������~$r$ �� ����� $r$~���������,
�������~$x$, �~$n-1-r$~���������, �������~$x$. ����~$t=r+1$, ��~$x$ �
����� �������; ����~$t<r+1$, �� ��� ����� ����� $t\hbox{-�}$~������� �
������� �������� �� $r$~�\'������ ���������; � ����~$t>r+1$, �� ��� �����
����� $(t-1-r)\hbox{-�}$~������� � ������� �������� �� $n-1-r$~�������
���������. ᓒ� ���� � ���, ���~$r$ �~$n-1-r$ ��� ������ ��� �����~$10q+3$
(������ ��������~� �~D ����~� ���~�). ��������� ��~$q$ �������, ��� ����
��� ������� �� ����� $15(10q+3)-163$~���������.
\medskip

����� ����� ��������� ����������� �� ������
$$
13(2q+1)+30q-148+4q+15(10q+3)-163=15(14q-6)-163.
$$
  ��� �� ������ � �� ����� $14q-6$~���������, �������������� ���������.
\proofend

�����, �������������� � ���� ��������������, �� ������ �����������,
��������� �� ����~4 �������� ������������ ����������. ♀�������
���������, ����������� �.~�������,
%%262
�.~��������� �~�.~‐�����, ����������, ��� ���������~15 ����� ���������
��~$5.43$.

\section ᐅ���� �����. ������ ����������� \emph{�������������} �����
��������� ����� ������ ��������, ������� ������������
\emph{�������} ����� ���������, �����������, ��� ������� �������. ���
������, ��� ������ ����������� �������, � ��� ��� ��� �� ������ ���� �
������~$t=2$. ���� ����� �������� ��� ������ � �����
\picture{
  ���.~42. ���������, ������� �������� ������ �������
  ��~$\set{X_1, X_2, X_3, X_4, X_5, X_6}$, ��������� � �������
  $6{1\over2}$~���������.
������ "������������" ����� ��������� ������ �����, ������ �����
������������ ��������������� �������. �� ������� ����� ��������~$j\ k$,
���� ��������, ��� $X_j$---������, a $X_k$---���������� �������; �����
������������, ���������� � ����� ����, �������� ��������������� ��� ���.
}
����� Th\'eorie des Questionnaires (1965), ������� ������������ ����
����������� �������� ᎁ���� [Univ.~of Minnesota, Dept.~of Statistics,
report~113 (November, 1968)].

ᎁ��� �������� ���������, ������������ �� ���.~42, ������� �������
������ � ������� �������� ������� �� �����  ���������, � ������� ���������
������ $6{1\over2}$~���������. � ������
%%263
������ ��������� 8~���������, � ��� ����, ���~$V_2(6)=7$;
�� ��� ��������� ��������� ��� ���� ������, ��������� ��
����� 7~���������, ���������� � ������� �� ������� ����
$6{2\over3}$~���������.  �� �������, ��������, ������� ���������
���������� ������� �� ����� ��������� �� ����� ����������� ������������
� ��� �����������, � ��� �������������� ������� ����� ���������.

����� $\bar V(n)$~���������� ����������� ������� ����� ���������,
����������� ��� ����������� $t\hbox{-��}$~�������� � ������� �������� ��
$n$~���������. � ��������� ������� �������� ��������� ��������� �������
������ ���~$\bar V_2(n)$, ����������� ᎁ����:
{\catcode`\!=\active\def!#1,#2/#3.{#1{#2\over#2}}
$$
\vbox{
\halign{
\hfill$#$\bskip&&\bskip$#$\hfill\bskip\cr
n=2& 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \cr
\bar V_2(n)\le 1& !2,2/3. & 4 & !5,4/15. & !6,1/2. & !7,17/21. & 9 & !10,
1/15. & !11,4/135.\cr
}}
\eqno(13)
$$
}
ᎁ��� �����������, ���
$$
\bar V_2(n)\ge n-2+\floor{2\log_2 n}/2.
\eqno(14)
$$

�.~�.~䋎�� � 1970~�.\ ���������, ��� ������� $n$~���������
� ������� ����� ���� ������� ����� �� ${3\over2}n+O\left(n^{2\over3}\log
n\right)$~���������. (�.~���.~13.) 䀊������� �� �������, ���
$$
\bar V_t(n)\le n+t+f(n), \rem{��� $\lim_{n\to\infty} f(n)/n=0$.}
\eqno(15)
$$

��������������, ��� ���� ��������� �������� ��������� ���������������
��������, ������ ������� ������������������ ������ ������ ��� ��� �� �������.

\excercises
\ex[15] ������ � ������� ������ ������� (���.~39 �~40) �����~$13$
��������, �������� �� �� ��� �� ������� ���� ���� � ������� ����?

\rex[�25] ��������, ��� ����� ����, ��� �� ����� � �������
������������������ ��������� $t\hbox{-�}$ ������� � ������� �������� ��
$n$~���������, �� ����� �����, ����� $t-1$~��������� ������ ���� � �����
$n-t$~��������� ������.

\ex[M21] ��������, ���~$V_t(n)\ge V_t(n-1)+1$ ���~$1\le t \le n$.

\ex[�20] ��������, ���~$W_t(n)\ge\ceil{\log_2 n^{t\atop -}}$,
���~$n^{t\atop -}=n(n-1) \ldots (n+1-t)$.

\ex[10] ��������, ���~$W_3(n)\le V_3(n)+1$.

\rex[�26] (�.~�.~䋎��.) ���� $n$~��������� ���������~$\set{X_1,~\ldots,
X_n}$ � ���������~$X_i<X_j$ ��� ��������� ���~$(i, j)$. �� ����� �����
������ � ������� �������� �������. ���� ��������, ���~$X_i<X_j$
�~$X_i<X_k$ ���~$j\ne k$, ��~$X_i$ �� ����� ���� ������ ���������, �������
��� ����� ���������. � ����������
%%264
��������� ����� ����� ���
\picture{p.264}
� ������ ���������� $m$~����� ���������, ������� ����� �����������
��������~$(l_1, l_2,~\ldots, l_m)$; $j\hbox{-�}$~������ ��������
$l_j+1$~���������, ��� ���� �� ������� ��������, ��� �� ������ ���������.
 ��������, ������������ ������������ ����� ���� ������� ��������~$(3, 2,
4, 0, 1)$; ���� �� ������ ��������� �� ��������, �� ����� ������ �� $n$~�����.

�����~$f(l_1, l_2,~\ldots, l_m)$---����������� ����� ���������, ������
��� ����������� ������� �������� ������ �������� ��������������
���������. ��������, ���
$$
f(l_1, l_2,~\ldots, l_m)=m-2+\ceil{\log_2(2^{l_1}+2^{l_2}+\cdots+2^{l_m})}.
$$
[\emph{㊀�����.} ��������, ��� ��������� ��������� ������ ������� � ���,
�����  ���������� ���������� �������� ���� ����� ��������� �����, ���� ��
������ �� � �������; ����������� �������� �o~$l_1+l_2+\cdots+l_m+2m$.]

\ex[�20] ��������~(8).

\ex[�21] 䎐���� ���������~(6) �������� �� ���������� ����������� ������
�� ������, ������������ ������ �������� ������ � $n$~�������� ������.
����� �� ����� �� ������, ���������� �� ��������� \emph{������} ������,
 ���� ������ ������ ��� �����-������ $t$ u~$n$?

\rex[20] ��������� ������ ��������� ��� ���������� ������� ����
��������� �� ����� ��� �� ����� �����, ��������� ����� ������ �
���������� ������ �~ᎁ��� [��.~(11)].

\ex[35] ��������, ��� ������� ���� ��������� ����� ���� ������� �� �����
��� �� 10~�����.

\ex[28] (����� �~ᎁ���.) �������� ����� ������, ���������������� � ������,
��������, ��� ������� ������ ��������� ����� ���� ������� �� ����� ��� ��
15~�����.

\ex[21] (����� �~ᎁ���.) ��������, ���~$V_3(n)\le V_3(n-1)+2$.
[\emph{㊀�����:} ������� � �������� ����������� ��~$\set{X_1, X_2, X_3, X_4}$.]

\rex[��28] (�.~�.~䋎��.) ��������, ��� ���� ������ � ����������
�������~$\set{X_1,~\ldots, X_{n^{2/3}}}$, ��������� ����������
������������ �����, �� �����
����� �������~$\set{X_1,~\ldots, X_n}$, �������� � �������
${3\over2}n+O(n^{2/3}\log n)$~���������.

\rex[20] (�.~ᎁ���.) ��������, ���, ����������� �� ����� ���� ���������,
 ����� ����� ��� ���������� �������� ��~$\set{X_1, X_2, X_3, X_4, X_5}$,
���� �� ����� �� �������� �������.

\ex[22] (�.~���.) �����������, ��� ��� ���������� �����������
������������, � �� �������. ����� ����������� ����� ���� ������
��������� ��� ����������~$t\hbox{-��}$ �� $n$~���������, ���� ������
������� �������� ���� ����� � �������� �������� � ������ ������� �� ������?

\rex[25] (�.~���.) ��������, ��� �� ����� ����� ������������ �������� �
������� ��������� �� $n$~���������, ����������� �� �����
$\ceil{{3\over2}n}-2$~���������, � ��� ����� �� ����� ���� ���������.
[\emph{㊀�����.} ����� ������ ������ ��������� ����� ���� ������������
���������~$(a, b, c, d)$, ��� $a$~��������� ������ �� ������������,
$b$~��������� ����������, �� ������� �� �����������,
%%265
$c$~�����������, �� ������� �� ����������, $d$~��� ����������,
��� � �����������. ��������� ����������� �������.]

\ex[20] (�.~�.~䋎��.) ��������, ��� ����� ������� $k$~����������
�~$l$~���������� ��������� ��������� �� $n$~���������, ����������� �� �����
$\ceil{{3\over2}n}-k-l+\sum_{n+1-k<j\le n}\ceil{\log_2 j}+\sum_{n+1-l<j\le n}\ceil{\log_2j}$~���������.

\ex[�20] ���� �� � �������������� �������~L ���� ������������
������ �������~5, � ��~7, �� ����� �� ���������� �������?

\ex[�44] ������� ������ ��������~$\bar V_2(6)$. ����� �� ��� ����������� �
���������, ������� �� ����������� ����� ���� ���������?

\ex[�47] �������� (��� ������������) ������������� ᎁ���~(13).

\ex[25] (�.~���.) ��������, ���~$W_3(2^k+2)\le 2^k+2k$, ����~$k\ge3$.

\ex[24] (����� �.~����������.) ��������, ��� �
������~$4\cdot2^k<n-1<5\cdot2^k$ ������� ������~(11) ���~$V_3(n)$ �����
���� ��������� ������� ��������� ��~1: (i)~��������� ������ "������ �
����������" �������~$2^k$. (ii)~������� ����������� �� ������� ����������
� ������� ��� $2^k$~��������� ���������������� ������. (iii)~���������
����������� ����������, ��������� ���� ������ � ����������
�������~$n-1-2^k$. (iv)~�����������, ��� ��� ��������������~(11).

\ex[�49] ������ ��������������� ��������~$V_{\ceil{n/2}}(n)$ ���~$n\to\infty$?

\ex[�48] ������ ��������������� ��������~$\bar V_{\ceil{n/2}}(n)$
���~$n\to\infty$?

\subsubchap{ᅒ� ����������} %5.3.4
� ��������� ������ �� ����� ������� ����� ������� ����������,
��������������� ���������� �����������. ������� � ����� �������
����������� � �������� ������������ � �������� ������������� �������.
풎 ����� ����������� �������, ����� \emph{������������������ ��������� ��
�������� �� �����������}%
\note{1}%
{� ������ �������� ����� ����� ������� ����� ������������������
����������.---{\sl ����. ���.\/}}
� ��� ������, ��� ���� �� ����������~$K_i$ �~$K_j$, �� �����������
��������� ��� ������~$K_i<K_j$ � �������� �� ��, ��� �
��� ������~$K_i>K_j$, ������~$i$ �~$j$ �������� ������. ��
���.~43(�) ���������� ������ ���������, � ������� ��� �������
���������. (�������, ��� �� ������ ������ ������������ ����������
����� ���������, ������� ����� $m$~��������� ������� $2^m$~�����������;
��� ���~$n!$ �� �������� ��������~2, �� ��������� ��������� �����
��������� � ��� ������, ��� ���� �� �� ����������� ������� �� �����������
�� ��������. ����� �������, �� ��������� ������ ������ ����������
��������� ������ ���������, ��� ����������, ����� ���������� ����
���������� �� ���� ��������������� ������.)

  ��� ������ ���� ������ ������ ������ ������ ���������� ��� ������,
�� �������� ����� ���������� ����� ���������� � ���� \dfn{����,} ��� ��
���.~43(b). �������������� � ����� ���� ������������ "�������������
������", ������� ��� ����� (������������ �������, ��������� � ������ ������)
%%266
\picture{���. 43. ������ ���������, � ������� �� ����������� �����������,
(a) � ��������������� ����~(b).}
%%267
� ��� ������ (������������ �������, ���������� ����); ����� ����� ����
������� �� ���� ������, � ������ �����---������� �� ���. 틅����~$K'_1$ �
������ ����� ���� ���� ���������� ��~$\set{K_1, K_2, K_3, K_4}$,
$K'_2$---������ � ������� ����������� �~�.~�. �������� ��������, ��� �����
���� ���������� ������������� ������ ���������, ����������� ���������
������������� �� ����������� (� ��������� ���� ������), � ��� �����
����� ������ ������������� ���� ������������� �������.

����� ������ �������, ��� � ���������� ����� ������ ������������� ������
�������� ����� ����������. �����������, ��������, ��� �� ������ ����� �
������ ��������� �������� ����� �� ������ ���� � ������� �������, �������
�� ��������. ������ ������������� ������ ����� ��� ��������� �
������������� ��������� �������:
$$
\matrix{
\multispan{3}\hfill\hbox{������ $t$}\hfill &\multispan{3}\hfill \hbox{������ $(t+1)$}\hfill\cr
\hbox{᎑������} & \hbox{�����}\hfill\span & \hbox{᎑������} &\hbox{������}\hfill\span\cr
0                & 0 & 0                   & 0                & 0 & 0\cr
0                & 0 & 1                   & 1                & 0 & 1\cr
0                & 1 & 0                   & 2                & 0 & 1\cr
0                & 1 & 1                   & 0                & 1 & 1\cr
1                & x & y                   & 1                & x & y\cr
2                & x & y                   & 2                & y & x\cr
}
$$
������������� ��� ������ ��������� � ���������~0 � ������~$00$. ������
��������� � ���������~1 ���~2, ��� ������ ��� ����� ������ ����������.
爑��, ������� � ������ �������~$t$ ������ ��������� ������ � ����,
��������������� ���.~43(b), ������ � ������~$t+3$ ���������� ����� �
���������������
\picture{���.~44. ��� ���� ������ ������������� ����������
������������������ $\langle 4, 1, 3, 2\rangle$ ����������� ����,
������������ �� ���.~43.}
�������, ���� �������� ��������������� ������������� ������� �
������~$K'_1$ �~$K'_4$.

��� ���������� ������ ����� ���������� ������ ���������� �� ���������
���� �������� (���.~44). �� ���� ������� ����� ��������� �����, �
������������� ������ ���������� ������������� ������������ ����� �����
�������; ������
%%268
���������� ��������, ���� ����������, ������������ ����� ������ �����
�������, ��� ����� ����������� ����������� ������� ����� ����������� ��
������ �����. � ������ ����� ��������� ��� ����� ����������� ������ ����.

�����, ������ ����������� ����������, �� ������� �������� ��������
����������� ����� ���������, ����� (��� ������)
\picture{���.~45. ��������� $(n+1)$-����������� ������������ ��
$n$-�����������: (a)---�������; (b)---�����.}
�� �������� ����������� ������ ��� ��������� ��������� ������� ������
����������. � ���� ��������� ���� ���������� ����� ��������� ������������,
��� ��� ������ ����� ��������� � $n$~�������, � ��������� �������
"������������"; ��� ������������� ���������� ���������� ����������
���������---���� ��������� � ���������� �������. ��� ����� ������
\picture{���.~46. ᅒ���� ������� ������������ ����
���������� ����������, ���������� ������������ ����������� ��������,
�������������� �� ���.~45: (a)---������� �������; (b)---����� ��������.}
������������� ����� ���������� �������� ��, ��� ����� �������� �����
����������, ���� ��������� �� ������������ (�� ���������� ������).
��������, ���� ����� �� ���.~43 �~44 ����������� �� ����, ���� ���������
������������� ����������������� ���������, ��� ��� ����� ����������
������ ��� � ��������� ��� ����; ������� � ������ ������ �� ����������
%%269
��� �������� ����� ����������.  �� �������, ���� ���������� ����� ����
����� �������, ���� ����������� ���������� ����������� ���� ����������
$n$~��������� ��� �������~$n$ ����� �� ��������; ��������, �� ���������,
��� ��� ����������� ���������� ��������� ������� ��������� �����
�������������� ���������.

������� ��� ������� ������� ���������� ���� ����������. ���
$n+1$~���������, ���� ���� ���� ��� $n$~���������: � �������������� ����
�������� \emph{�������,} ���� �������� \emph{������.} ��
\picture{���.~47. ��� ������������ ���������� �������� ������� �������
��������� � ������� ��������!}
���.~45(a) ��������, ��� $(n+1)\hbox{-�}$~������� ����� ���� �������� ��
������ ����� ����� ����, ��� ������ $n$~��������� �������������, � ��
���.~45(b) ��������, ��� ����� ������� ���������� �������, ������ ���
������� � ���������� ���������. ������������ ���������� ���.~45(a) ����
������� ������ ������� ������� (��������~5.2.1S), � ������������
���������� ���.~45(b) �������� � �������� ������� ������ ��������
(��������~5.2.2B). �� ���.~46 ���������� ��������������� ���� ��� �����
���������. ��������� ��������, ��� ���� ����� ������ ����, �����
���������� ������������� ��������, �� ��� ������ �������� � ����� � ��� ��
"�����������" ��������� � $(2n-3)$~�������� (���.~47).

����� ��������, ��� ����, �������������� �� ���.~43 �~44, �����
����������� ����� ��������� �� ������� �����, ��������� ������ ������
����������� ���������� ���������� � ���������� �������� �� ���������� ��
�����, � ��������� ���������� ����������� � ��������� ������� ���������
��� ��������. ������ �� ������ ��� ����� �������, ����� �� ������ ����
����������� ��� ��������� ������� ������������������; ��������, ����
\picture{p.269}
�������� ����������� ������������������ ������ ����������, ��
�������������� �� ������������ ������������. ���� ��
%%270
���������� ��������� ������ $n$-���������� ���� �� ���� $n!$~�������������
$n$~��������� �����, �� ���������� �� ����� �������� ����������� �������
����������� ��������.

\proclaim ⅎ����~Z. (������� ����� � ������.) ���� ���� � $n$~�������
��������� � ����������� ������� ��� $2^n$~������������������� ��~0 �~1, ��
��� ����� ����������� � ����������� ������� ����� ������������������ $n$~�����.

\proof (풎 ������� ������ ������� ���������, ���.~5.3.1-12.)
����~$f(x)$---����� ���������� �������, ��� �������~$f(x)\le f(y)$
���~$x\le y$, � ���� ������ ���� �����������~$\< x_1,~\ldots, x_n>$
�~$\<y_1,~\ldots, y_n>$, ��, ��� �������� ������, ��� ����
�����������~$\<f(x_1),~\ldots, f(x_n)>$ �~$\<f(y_1),~\ldots, f(y_n)>$.
����~$y_i>y_{i+1}$ ��� ���������~$i$, �� ���������� ���������� �������~$f$,
 ������� ��� ���� ����� $<y_i$ ��������� ��������~0, � ��� ����
�����~$\le y_1$---��������~1. 풀 ������� ���������� ������������������ �����
� ������~$\<f(x_1),~\ldots, f(x_n)>$, ������� �� ����������� ������ �����.
ዅ����������, ���� ��� ������������������~0 �~1 ��������� ����������,
�� ����� �����~$y_i\le y_{i+1}$ ��� ����~$1\le i < n$.
\proofend

������� ����� � ������ �������� ������� ��� ���������� ����� ����������. �
�������� �������������� ������� ������� ���������� ������� "��������
���������� �� ��������" ������� (��������~5.2.2�). ���� ������� � ���,
����� ����������� $m+n$~���������, "�������� ������~$m$ � ���������~$n$
��������� ���������� � ����� �������� � ���������� \dfn{$(m, n)$-����
�������.} ��������� $(m, n)$-���� ������� ����� �� ��������:
{\medskip\narrower
\item{a)}~����~$m=0$ ���~$n=0$, �� ���� ������. ����~$m=n=1$, �� ����
������� �� ������������� �������������� ������.

\item{b)}~����~$mn>1$, �� ��������� ��������� ������������������ $\<x_1,
~\ldots, x_m>$ �~$\<y_1,~\ldots, y_n>$. ᎋ��� "��������
������������������"~$\<x_1, x_3,~\ldots, x_{2\ceil{m/2}-1}>$
�~$\<y_1, y_3,~\ldots, y_{2\ceil{n/2}-1}>$ � ������� ���������������
���������~$\<v_1, v_2,~\ldots, v_{\ceil{m/2}+\ceil{n/2}}>$;
������ "������ ������������������"~$\<x_2, x_4,~\ldots, x_{2\floor{m/2}}>$
�~$\<y_2, y_4,~\ldots, y_{2\floor{n/2}}>$ � ������� ���������������
���������~$\<w_1, w_2,~\ldots, w_{\floor{m/2}+\floor{n/2}}>$. � �������,
�������� �������� ���������-������
$$
w_1:v_2, w_2:v_3, w_3:v_4, w_{\floor{m/2}+\floor{n/2}}:v^*
\eqno(1)
$$
� ������������������
$$
\<v_1, w_1, v_2, w_2, v_3, w_3,~\ldots, v_{\floor{m/2}+\floor{n/2}},
w_{\floor{m/2}+\floor{n/2}}, v^*, v^{**}>;
\eqno(2)
$$
��������� ����� ������������. (!)
(�����~$v^*=v_{\floor{m/2}+\floor{n/2}+1}$ �� ����������, ����~$m$ �~$n$
��� ������, �~$v^{**}=v_{\floor{m/2}+\floor{n/2}+2}$
%% 271
����������, ���� ����~$m$ �~$n$ ��� ��������; ����� ����� �������������
�������,   ���������   �~(1),   �����~$\floor{(m+n)-1)/2}$.)
\medskip}
\noindent ������� $(m, n)$-���� ������� ������� \dfn{�����-��������
��������.} ����������� � ������������ � ����� ���������� $(4,
7)$-������� �������� �� ���.~48.

\picture{���. 48.         煒��-�������� ������� ���~$m=4$ �~$n=7$.}

璎�� ��������, ��� ��� ����� �������� ��������� ������������� ��������
���~$mn>1$, ������������� ��������� ����� � ������ � �������� �� �� ����
�������������������~0 �~1. ����� ��������� $m$-���������� � $n$-����������
������������������~$\<x_1,~\ldots, x_m>$ ����� �������� �� $k$~�����, ��
�������� ������� $m-k$~������, �
������������������~$\<y_1,~\ldots, y_n>$---�� $l$~����� �
������������ $n-l$~��������� ��� ���������~$k$ �~$l$.
ዅ����������, ������������������~$\<v_1, v_2,~\ldots>$ �����
�������� ��~$\ceil{k/2}+\ceil{l/2}$~����� � ������������ ���������,
� $\<w_1, w_2,~\ldots>$---�� $\floor{k/2}+\floor{l/2}$~����� � ������������
���������. �������� �������� �������������� �������� ��, ���
$$
(\ceil{k/2}+\ceil{l/2})-(\floor{k/2}+\floor{l/2})=0, 1 \hbox{ ��� } 2.
\eqno(3)
$$
���� ��� �������� �����~0 ���~1, �� ������������������~(2) ��� �����������,
 � ���� ��� �����~2, �� ���� �� �������� ���������-������ �~(1) ������ ���
�� ���� �����. �������������� ���������. (�������, ��� ������� ����� �
������ ������
$\perm{m+n}{m}$~������� � ������ ������� ����� ���� �~$(m+1)(n+1)$,
������ �� ������� ������������ ����� �����������~$k$ �~$l$.)
�����~$C(m, n)$---����� ������������� �������, ������������ ���
�����-�������� ������� $m$ � $n$~���������, �� ������
%%272
��������� $m$- �~$n$-����������; �����
$$
C(m,n)=\cases{
mn, & ���� $mn\le 1$;\cr
C(\ceil{m/2}, \ceil{n/2})+C(\floor{m/2}, \floor{n/2})+ \floor{(m+n-1)/2},
& ���� $mn>1$.\cr
}
\eqno(4)
$$

� ����� ������ ��� �� ������� ������� ������� ��~$m$ �~$n$, ������,
�������, ���~$C(1, n)=n$ � ���
$$
C(m+1, n+1)-C(m,n)=
=1+C(\floor{m/2}+1, \floor{n/2}+1)-C(\floor{m/2}, \floor{n/2}),
\rem{���� $mn\ge 1$},
$$
�� ����� ������� �����������
$$
C(m+1, n+1)-C(m,n)=t+2+\floor{n/2^{t+1}},
\rem{����~$n\ge m \ge 1$ �~$t=\floor{\log_2 m}$.}
\eqno(5)
$$
ዅ����������,
$$
C(m, m+r)=B(m)+m+R_m(r) \rem{��� $m\ge0$, $r\ge0$,}
\eqno (6)
$$
��� $B(m)$~���� �������
"�������� �������"~$\sum_{1\le k\le m}\ceil{\log_2 k}$  ��
�����������~(5.3.1-3), � $R_m(r)$~���������� ����� ������ �� ������ ����
$$
\floor{{r+0\over1}}+\floor{{r+1\over2}}+\floor{{r+2\over4}}+
\floor{{r+3\over4}}+\floor{{r+4\over8}}+\cdots+
\floor{{r+j\over2^{\floor{\log_2 j}+1}}}+\ldots\,.
\eqno(7)
$$
���� ��~$r=0$, �������� ������ ������� ������
$$
C(m,m)=B(m)+m.
\eqno(8)
$$
����� ����, ����~$t=\ceil{\log_2 m}$, ��
$$
\eqalign{
R_m(r+2^t) &= R_m(r)+1\cdot 2^{t-1}+2\cdot 2^{t-2}+\cdots+2^{t-1}\cdot2^0+m=\cr
&= R_m(r)+m+t\cdot 2^{t-1}.
}
$$
ዅ����������, $C(m, n+2^t)-C(m, n)$~����� ������� ���
�
$$
C(m, n)=\left({t\over2}+{m\over 2^t}\right) n+O(1)\rem{ ���
�������������~$m$, $n\to\infty$,  $t=\ceil{\log_2 m}$;}
\eqno (9)
$$
����~$O(1)$ ���������� � ����� ������ ������������� �������� ��~$n$ �
������ �������~$2^t$. �������������� ���~$n\to\infty$ ��������~$C(n, n)$
�����~$n \log_2 n$ ��~(8) � ���.~5.3.1-15.

\section ᅒ� � ����������� ������ ���������.
�����~$\hat S(n)$---����������� ����� ���������, ��������� � ���� ����������
��� $n$~���������; ����, ���~$\hat S(n)\ge S(n)$, ���~$S(n)$---�����������
����� ���������,
%%273
����������� ��� ���������� ��� ������ ����������� (��.~�.~5.3.1).
�� ������, ���~$\hat S(4)=5=S(4)$, ������� ����� ����������� �� ��������
������ ������������� ���~$n=4$;
�� ��� ���~$n=5$ �����������, ���~$\hat S(5)=9$, � �� ����� ���~$S(5)=7$.
������ �����������~$\hat S(n)$ ������� ��� ����� �������, ��� ������
�����������~$S(n)$; �� ��� ��� ���������� ���� ���������������
���������~$\hat S(n)$.

��������� ���������� ������� ���� ������, ��� ��� �� ������ ����� ���
����������� ����������� ������������ ������. ᅒ� ���������� ���� �������
����������� �.~�.~�����������, �.~��.~��������� � �.~��.~�'�������� �����
1954~�. [��.~U.~S.~Patent 3029413]; ��� ��������, ���~$\hat S(n+1)\le \hat
S(n)+n$. ��� ������� � �� ��������� ������, "�������� ��������, �����
��������������� ����������� $n$-������� ����������� �������������,
��������� ����������� ����� ����������� ����������� ��������������"; ���
������� ������� ����������� ���~$4\le n \le 8$, �����������
�������������� 5, 9, 12, 18 � 19~������������. ������� ����� ��� ����
�������, ������� ��������� � �.~�.~���� ��� ��~1960~�. ����������� �����
��������� ��� ���������� ����� ����������, ������������,
���~$\hat S(2^n)\le3^n-2^n$ ��� ����~$n$,
�������~$\hat S(n)=O(n^{\log_2 3})=O(n^{1.585})$. ���� �~������� ������������
���� ���������� ����� �
{\sl JACM,\/} {\bf 9} (1962), 282--296, �������� �������������, ��� ���
��������� ��������� ���������; �.~�.~刁���� [{\sl JACM,\/} {\bf 10}
(1963), 142--150] ����� �����������, �� ��������� ����� ������� �����, �
������� ������������ ����� �� ����� ���������, ��������� ��� ����� ���
�������������.

� 1964~�.\ �.~�.~䋎�� �~�.~�.~���� ������������ ����� ������ � ����
������, ��������� �� � ��������������� ������
����~$\hat S(n)=O(n^{1+c/\sqrt{\log n}})$. ������� ����������, �.~�.~������
������ ��������� ���� ����� ��������� �������; ��������� �����
������������, ������������ ���
$$
c(1)=0, c(n)=c(\ceil{n/2})+c(\floor{n/2})+C(\ceil{n/2}, \floor{n/2})
\rem{��� $n\ge2$,}
\eqno (10)
$$
�� �������, ��� (��.~���.~5.2.2-14)
$$
c(2^t)=(t^2-t+4)2^{t-2}-1,
$$
� ������ �����, ���~$\hat S(n)=O(n(\log n)^2)$. ��� ������, ��� � 䋎�� �
������ ������������ ���� ����������� ���� ����� ��������� ����� [{\sl
Notices of the Amer.\ Math.\ Soc.,\/} {\bf 14} (1967), 283; Proc.\ AFIPS
Spring Joint Computer Conference, {\bf 32} (1968), 307--314].

%%274

���-���� ������� ��������� ����� ������������, ������������ �
����������� ������� � ��������, ������������ ��������; � ��������� �������
�������� ��������� �� ��������� � ��������� ����� ������� ������
���~$\hat S(n)$:
$$
\matrix{
\hfill n=1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 &
16 \cr
\hfill c(n)=0 & 1 & 3 & 5 & 9 & 12 & 16 & 19 & 26 & 31 & 37 & 41 & 48 & 53
& 59 & 63 \cr
\hfill \hat S(n)\le 0 & 1 & 3 & 5 & 9 & 12 & 16 & 19 & 25 & 29 & 35 & 39 &
46 & 51 & 56 & 60\cr
}
\eqno(11)
$$
  ���~$\hat S(n)<c(n)$ ���~$8<n\le 16$, �� �������� ���������� ��
�������� ������������ ��� ����~$n>8$. ����~$n\le 8$, �� ����� ����������
������������ �� ���������� ������������ ����������� ���� �~��������.
䋎�� �~���� �������� � 1964--1966~��., ��� ��������� ��������~$\hat S(n)$
\emph{�����} ���~$n<8$ [��.\ A Survey of Combinatorial Theory
(North-Holland, 1973), 163--172]; ��������~$\hat S(n)$ ���~$n>8$ �� ���
��� ����������.

�����������, ���������� � ��������� ���� ��������� ���~$\hat S(n)$,
���������� �� ���.~49. ᅒ� ���~$n=9$, ���������� �� ����������
����������� �������, ���� ������� �.~�.~䋎���� � 1964~�.; ���������� ��
�������������� ����� ��� ������ ������ ��������, ���������� � ���.~27.
ᅒ� ���~$n=10$ �~1969~�.\ �������� �.~�������; �� ������������ �����
��� ������������ ���������~$\set{1, 2,~\ldots, 10}$ � �������,
�������� ��������� ���������, ��������� �������� ��������� ����� ��������,
������� ����� ���������� � ������ ������ �� ������ ������.

� 1969~�. �.~耏��� ����� ���� ���������� 16~��������� � 62~�������������,
� ��� ���� ������ ����������, ��������� ����� ������� (63~���������),
��������, ���������� ��� �����������, ���� $n$~�������� ��������~2.
�.~�.~���� ������ ����� ����, ��� �� ����������� � ������������ 耏���,
������ ���� � ��� ������� ���������, ����� ���������� � 60~�����������,
���������� �� ���.~49. ������ ����� ����������� ����� �������� ������ ���
���������; ����� ���� ��� ��������� 32~�������� ���������-������ �����
�� ���������� �����, ��� ������ ����� ��� ��������
16~��������������~$\set{a, b, c, d}$, ����� ��� ������, ����������~$s$,
���� ��������, ��� ��� �������� �����, ������� ��� ������ �����������
������, ����������~$t$, ������ ���, ����� $s$~���� ������������~$t$.
᎑������ ���������� � ���� ������ ����������� ����� �������� �
���.~32. ������ ���������, ����������� �� ����������� �������, ����������
���������� �����������, � �� ��� ��� ����� �� �����, ��� �������� ���
�����������, ����� �������� ����� �� ����������� ���� ��� ������� ��������~$n$.

%%275

耏��� � ���� ������� ����� ������������ �� ���.~49 ���� ���~$n=12$.
厐���� ���� ���~$n=11$, 13, 14 �~15 ����� ��������, ������ ������ ������
���� ���~$n+1$ ������ �� ����� �������������, ��������������� � ���� �����.
\picture{���. 49.   픔�������� ���� ����������.}

��������� ��������� � ���������� ������� ���� ���~$n\to\infty$ ��.~�
���������� ����������� �.~���~������ (Stanford University, 1971); ���
���� ������� ��������������
%% 276
${1\over 4}n(\log_2 n)^2-\alpha n \log_2 n$~������������,
���~$\alpha={1\over4}+{1\over6}\sum_{k\ge0}2^{-2^k-k}\approx0.356~852$.

\section ᅒ� � ����������� ��������. � ���������� �����������
����� ���������� � �� ������������ ��� ����� ��������� ����������������
�������� ���������-������ ������������, ������� ������� ������������
���������� �������������� ����� ��������. �� ��������� �����������
���������, ��� ����� �������� ���� ���������� ����� ������������� �����
������������, ����������� � ������-���� "����" ����� ����,
���� ���������� ���� ��� ���������� ������ �������� ����� �������,
\picture{���.~50.  ���������� ������� ��������� � �������� ������ ��
��������� ��������.}
��������, � ��������� � ����� ������ �� ������ ����� �����������. �
������� ����������� �� ����� ��������� ���������� �����, �����������
����� ������ ������, ����� ����� ���� ��������� ���������; ���� ����� ��
������� ������, ��� ������������ ����� � ������������, ��������������
�������. (�.~���.~50(a); � �����~(b) ����� ������� �������� �� �� ����,
 �������������� ���, ����� ������ ��������� ����������� � �������� ������
��������� ������.)

� ��������� ���� ���� ������� ��� �����-��������� ������� �������������
$T_b(m,n)$~������ �������, ���~$T_b(m,0)=T_b(0, n)=0$, $T_B(1,1)=1$ �
$$
T_B(m, n)=1+\max(T_B(\floor{m/2}, \floor{n/2}),  T_B(\ceil{m/2}, \ceil{n/2}))
\rem{���~$mn\ge 2$.}
$$
��������� ��� �����������, ����� �������� �� ��������,
���~$T_B(m, n+1)\ge T_B(m,n)$;    �������������,    $T_B(m,
n)=1+T_B(\ceil{m/2}, \ceil{n/2})$ ���~$mn\ge2$, � ������ ���������, ���
$$
T_B(m,n)=1+\ceil{\log_2 \max (m,n)} \rem{��� $mn\ge1$.}
\eqno  (12)
$$
 �� �������, ��� �������� � ���.~5, ����� ���������� ������� ����� �����
��������
$$
\perm{1+\ceil{\log_2 n}}{2}.
\eqno(13)
$$
%%277

����� $\hat T(n)$---����������� ����� ��������, ���������� � ����� ����
���������� $n$~���������. ��������� �� ��������� ���� ����� ����� ��������,
 �� ����������� �������������� ������������, ���, ����� ��� �����
������� ����� ��������, ���
\picture{���.~51. ᅒ� ����������, ������� ������������� ������,  ����
��������� ����������� �����������.}
�������� �� ���.~51 ���~$n=6$ �~$n=9$, � � ���.~7---���~$n=10$. �����
�������� ��� ������� ����� ��������, ���� �������� ���� ��� ���
�������������� ������, ��� ���������� ���� ���~$n=10$, 12 �~16 �� ���.~51.
품 ���������� �������� � ������-
%%378
��� ������� ������� ���~$T(n)$ ��� ��������� ���������~$n$:
$$
\matrix{
           \hfill n=1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16\cr
\hfill \hat T(n)\le 0 & 1 & 3 & 3 & 5 & 5 & 6 & 6 & 7 &  7 &  8 &  8 &  9 &  9 &  9 &  9\cr
}
\eqno(14)
$$

��������, ��� ����������� ����� �������� ����� ���~$n\le 8$ (��.~���.~4).
ᅒ� �� ���.~51 ����������� ����������� ��������, ��������� ����� ��
��������, ��� ��� ������� ��� ����������; ��� ���� ���� �������
�~1969--1971~��. �.~耏���  ($n=6$, 9, 12) �~�.~���~������� ($n=10$, 16).

\section ᅒ� �������. ����� $\hat M(m, n)$~���������� �����������
����� ������������, ����������� ��� ����, ������� �������
$m$~���������~$x_1~\le~\ldots \le x_m$ �~$n$~����������~$y_1\le\ldots \le y_n$,
������� ��������������� ������������������~$z_1\le \ldots \le z_{m+n}$.
� ���������� ������� �� ������� �� ����� ���� �������,
������� ���� �� ����� �����-��������� �������, ���������� ����;
�������������, �������~$C(m, n)$ �~(6) ������������ ��������� ���������
������� ������ ���~$\hat M(m, n)$.

�.~�.~䋎�� ��������� ���������� ������, ����������� ����������
\emph{������} ������ � ���� ������ �������.

\proclaim ⅎ����~F. ��� ����~$n\ge 1$ �����������
�����������~$\hat M (2n, 2n)\ge 2\hat M(n, n)+n$.

\proof ���������� ���� �~$\hat M(2n, 2n)$~�������������� ��������,
��������� ����������� ��� �������
������������������~$\<z_1,~\ldots, z_{4n}>$, �����,
���~$z_1\le z_3\le\ldots \le z_{4n-1}$  �~$z_2\le z_4\le\ldots\le z_{4n}$.
�� ����� �������, ��� ������ ������
��������~$(z_i, z_j)$ ��~$(\min(z_i, z_j, \max(z_i, z_j))$ ���
���������~$i<j$ (���.~16). ����, ����������� ����� ��������� �� ��� ������:
{\medskip\narrower
\item{a)}~$i\le 2n$  �~$j\le 2n$;
\item{b)}~$i>2n$ �~$j>2n$;
\item{c)}~$i\le 2n$  �~$j>2n$.
\medskip}
�����~(a) ������ ��������� �� ������� ���� $\hat M(n, n)$~������������,
��� ��� $z_{2n+1}$, $z_{2n+2}$,~\dots, $z_{4n}$ ����� ��� ����������
�� ����� ������, ����� ������� ����������; ���������� � ������~(b) ������
���� �� ������� ���� $\hat M(n, n)$~������������. ����� ����, ���
���������� ������� ������������������~$\<0, 1, 0, 1,~\ldots, 0, 1>$,
�����~(c) �������� �� ����� $n$~������������, ��� ��� $n$~����� ������
������������� ��~$\set{z_{2n+1},~\ldots, z_{4n}}$ �~$\set{z_1,~\ldots, z_{2n}}$.
\proofend

������������ ���������� �������~F ����������,
���~$\hat M(2^m, 2^m)\ge{1\over2}(m+2) 2^m$; �������������,
$\hat M(n, n) \ge {1\over2}n \log_2 n+O(n)$.
%%279
ወ���� \emph{���} �������� ����������� ������� ���� $M(n,n)=2n-1$~���������;
����� �������, �� ��������, ��� ������� �������
������� �� ��������, ��� ������� ������. 煒��-�������� �������
����������, ���~$\hat M(n,n)\le C(n, n)= n\log_2 n+O(n)$, �������
��������������� ���������~$\hat M(n, n)$ �������� � ��������� ��
���������~2. (⎗��� ��������~$\hat M(n, n)$ �������� ���~$n\le 5$;
��.~���.~9.) �.~�.~� �~�.~�.~� ��������,
���~$\hat M(2,n)=C(2, n)=\ceil{{3\over2}n}$
�~$\hat M(m, n)\ge{1\over2}n\log_2(m+1)$ ���~$m<n$
[{\sl JACM,\/} ����� ������������].

\section �������� ����������. ���� ��������� ������������� ���������, ��,
 ��� ����� �� �������~12, ��� �����-�������� ������� ���~$1\le m \le n$
��������� �������� ��~$\ceil{\log_2 (2n)}$~������ �������. ������ �����
������ ��� ���� �������, ����������
\dfn{�������� �������������,} ��� �������� ����� �������� ���������
��~$\ceil{\log_2(m+n)}$, �� �� ������� ������ ������������� �������.

������������������~$\<z_1,~\ldots, z_p>$ �� $p$~����� �����
�������� \dfn{��������,} ����~$z_1\ge\ldots\ge z_k\le\ldots\le z_p$ ���
����������~$k$, $1\le k \le p$ (�������� ��� � ������� ������������
"����������" �������������������). �������� ����������� �������~$p$---���
������������� ����, ��������� ����������� � ����������� ������� �����
�������� ������������������ �����~$p$. ������ �������~$x_1\le\ldots\le
x_m$ �~$y_1\le\ldots\le y_n$ �������� ������� ������� ������ ��������
����������, ��� ��� ������� ����� �����������, �������� �
������������������~$\<x_m,~\ldots, x_1, y_1,~\ldots,~y_n>$ ��������
����������� �������~$m+n$.

�������, ��� ���� ������������������~$\<z_1,~\ldots, z_p>$ ��������, ��
�������� �� �������� � ��� �� ���������������������. ������ ����� ����,
��� ������ ������ ���� �����-��������� �������, �� ���������, ���
����������� ������� ����� ��������� �������� ����������� �������~$p$,
������� ���������� �������� ��������
���������������������~$\<z_1, z_3, z_5,~\ldots>$
�~$\<z_2, z_4, z_6,~\ldots>$, � ����� ��������
���������-������~$z_1:z_2$, $z_3:z_4$,~$\ldots\,$.
(�������������� ��.~�~���.~10.) ���� ��������������� ����� �������������
������� ���������� �����~$C'(p)$, �� ����� �����
$$
C'(p)=C'(\ceil{p/2})+C'(\floor{p/2})+\floor{p/2} \rem{��� $p\ge2$.}
\eqno (15)
$$
� ����� ��������, ��������, �����~$\ceil{\log_2 p}$. ��~���.~52 �������
�������� ����������� �������~7, ����������� ���� ��������; �� ����� ����
����������� � ���~$(3, 4)$, � ��� $(2, 5)\hbox{-����}$ ������� � ���������
� ��� �������; �����-�������� ������� ���~$m=2$ �~$n=5$ ����� �� ����
���������� ������, �� �� ���� ������� �������� ������.

%%280

�������� ����������� ������� �������~$2^k$ �������� ���������; ��
������� �� $k$~������� �� $2^{k-1}$~������������ � ������. ����������
������� ������~$z_0$, $z_1$,~\dots, $z_{2^k-1}$; ��� ���� �������~2,
������������ �~$z_j$ �� ������~$l$ ����� � ������ �����, ����� ��������
�������������~$i$ �~$j$ ����������� ������ � $l\hbox{-�}$~���� �����. 풀
������� ��������� �������� � ������������ ���� ����������, ������� ��� ��
������, ��� �������� ����������
\picture{���.~52.   �������� ����������� ������� �������~7.}
�� �������� (��������~5.2.2M), �� ����������� ����� ��� ����������.
(�.~���.~11 �~13.)

����~$m=n$, �� �������� ������, ��� � �����-�������� �������, � ��������
����������� ������� ������������ ���������� ������� ������� ��������,
����������� � ����� ���� �������.
\picture{���.~53. ���� ������� ��������� � ������ ������� �
�������������, ����� ������� ���������� ���������� ������� ��������.}
� $(n, n)$-���� ������� $n\hbox{-�}$ �� �������� ����� (������ ��
�����������) ������ �������� �� ���� $2n$~������, � ���� ���
����� ��������� �� $l$~�����, �� �� ����� �������� �� �����, ��� ��
$2^l$~������; �������~$2^l\ge 2n$, $l\ge \ceil{\log_2 (2n)}$.

����~$m<n$, �� $n\hbox{-�}$~����� $(m, n)$-���� ������� �������
�� $2m+1$~������ (��.~�~���.~29), ������� �� �� ����������� ����
%%281
� ���� ������ ����������� ����� �������� ��� �������~$\ceil{\log_2(2m+l)}$.
 ������ ������� [Report GER-14122 (Akron, Ohio: Goodyear Aerospace
Corporation, 1968)], ��� ��� ����������� ����� �������� �����������,
���� � ���� ����������� ������������, �.~�.~����� ��������� �����, ���
���� � �� �� ����� � ���� � �� �� ����� ������������ �����������
��������. � �������� ������� �� ���.~53 ���������� (���~$n=6$) ����,
 ������� ������� ���� ������� � $n$~������� ����� � ����� ��������
��������. �������, ���� � ������������� �� ������������� �����
�����������; �������� ����� ������, ��� ����� $(1, n)\hbox{-����}$ �������
��� ������������ ������ ����� ����� ��������~$\log_2(n+1)$ ��� �����.
(�.~���.~14.)

\section ᅒ� ������. ᅒ� ����� ��������� ����� � � ������
�.~5.3.3. ����� $\hat U_t(n)$~���������� ����������� ����� ������������,
����������� � ����, ������� ���������� $t$~���������� �� $n$~���������
������ �� $t$~������������ �������� ������, ��� ����� ������������� ��
���� �������� ������ � ������������ �������. ����� $\hat
V_t(n)$~���������� ����������� ���������� ������������, ������ ���
����������� $t-\hbox{��}$ � ������� �������� �� $n$~��������� ������ ��
������������ �������� ������, � ����� $\hat W_t(n)$~���������� �����������
����� ������������, ��������� ��� ����������� $t$~���������� ��
$n$~��������� ������ �� ������������ $t$~�������� ������ � �����������
�������. �������� ������ (��.~���.~17), ���
$$
\hat U_t(n)\le \hat V_t(n) \le \hat W_t(n).
\eqno(16)
$$

ፀ���� �����������, ��� ������� $2t$~���������
$\<x_1,~\ldots, x_{2t}>$ � �� ����� ������� $t$~����������; �.~�.~��������
[{\sl �����������,\/} {\bf 5}, 5 (1969), 99--103] �������, ��� ��� �����
���� ���������, ���� ������� �������������~$\<x_1,~\ldots, x_t>$
�~$\<x_{t+1},~\ldots, x_{2t}>$, � ����� �������� � �������� �������
$$
x_1:x_{2t}, x_2:x_{2t-1},~\ldots, x_t:x_{t+1}.
\eqno(17)
$$
  ��� �� � ����� �� ���� ��� �� ����� ����������� ����� ������ ��
���������� $t$~��������� (������?), �� ��������� ��������� ������ �������
$t$~���������� ���������.

���� ��� ����� ������� $t$~���������� �� $nt$~���������, �� �� �����
��������� ��� ��������� $n-1$~��� (�������� ������ ��� $t$~���������);
�������������,
$$
\hat U_t(nt)\le (n-1)(2\hat S(t)+t).
\eqno(18)
$$

�������� ����� ������� ���������� \emph{������} ������ ��� ������ ������.

%%282
\proclaim ⅎ����~A. $\hat U_t (n) \ge (n-t)\ceil{\log_2 (t+1)}$.

\proof ㄎ���� ������������� ������������� ������ ������
\emph{����������} $t$~���������. ����� ������ ������ ������������� ����
����� �������� �����~$(l, u)$, ��� �������� �� ���.~54, ���~$l$ �~$u$
���������� �������������� ����������� �
\picture{���.~54. ��������� ������� ���������� �� �������
����������. (爑�� ��� ������� ������������ � �������������� �������~A.)}
������������ ��������, ������� ����� ��������� � ���� �����, ���� ������
������ ������������~$\set{1, 2,~\ldots, n}$. �����~$l_i$ �~$l_j$---������
������ �� ������~$i$ �~$j$ ����� ����������~$x_i:x_j$, � �����~$l'_i$
�~$l'_j$---��������������� ������ ������ ����� �����
\picture{���.~55. ���� ������������� ����, ������������ �� ���.~54.}
���������. ��������, ���~$l'_i=\min(l_i, l_j)$, � � ���.~24 ������������
(�����������) �����������
$$
l'_j\le l_i+l_j.
\eqno  (19)
$$

⅏��� ����� ������ ������������� �������� ���� (���.~55);
�����������, ��� �� ���� ������� ������ ���������� ����,
%%283
� ������ "����������" �������� ������ �� ������� ������ ������� �� ���
������, � �� ������ ������---������� ���� \emph{���� ����.} ������������
�����~$\<m_1, m_2,~\ldots, m_n>$ �������� ���������
$$
2^{m_i}\ge l_i
\eqno(20)
$$
� ����� ����� ����, ��� ��� ��� �������� ������������� ����������� �
����������� ������ ������������ � ����~(19). ����� ����, �������������
��������
$$
m_1+m_2+\cdots+m_n
$$
����� ������ ����� ������������ � ����, ��� ��� ������ ����������
��������� � ���� ����� �������.

���� ���� �������� ���������� $t$~�����, ��~$n-t$ �� �����~$l_i$ ������
��� �����~$t+1$; �������������, $n-t$ �� �����~$m_i$ ������ ����~$\ge
\ceil{\log_2 (t+1)}$.
\proofend

������ ������ � �������~A ����������� ������, ����~$t=1$ ���~$t=2$
(��.~���.~19). � ����.~1 ���� ��������~$\hat U_t(n)$, $\hat
V_t(n)$ �~$\hat W_t(n)$ ��� ���������~$t$ �~$n$.

\htable{ ����~1}%
{᐀������, ����������� ��� ����� ������ ($\hat U_t(n)$, $\hat V_t(n)$, $\hat W_t(n)$)}%
{\strut\hfill$#$\hfill&&\bskip\hfill$#$\hfill\bskip\cr
 & t=1 & t=2 &  t=3 & t=4 & t=5 & t=6 \cr
\noalign{\hrule}
n=1 & (0,0,0)\cr
n=2 & (1,1,1)& (0,1,1)\cr
n=3 & (2,2,2)& (2,3,3)& (0,2,3)  \cr
n=4 & (3,3,3)& (4,5,5)& (3,5,5)  & (0,3,5)   \cr
n=5 & (4,4,4)& (6,7,7)& (6,7,8)  & (4,7,9)   & (0,4,9) \cr
n=6 & (5,5,5)& (8,9,9)& (8,10,10)& (8,10,12) & (5,9,12) & (0,5,12) \cr
\noalign{\hrule}
}

\excercises  (��ࢠ� ����)
����� � ���������� ����������� ���� ����� �������� �������� ������ �����
����������, ������� ����� ������ ������ ��������� �����������. ������
������ ���������-������ ����� ������~$[i:j]$. ᅒ� � $n$~������� �
$r$~�������������� �������� ������� ���~$[i_1:j_1]\,[i_2:j_2]\ldots[i_r:j_r]$,
��� ���~$i$ �~$j$ ������ ��� �����~$n$; ��� ��������� �����
�������� �� $n\hbox{-�����}$. ᅒ� ���������� \dfn{�����������,}
����~$i_q<j_q$ ���~$1\le q \le r$.  , ��������, ���.~44 ���������
����������� 4-����, ������������ �������������������
������������~$[1:2]\, [3:4]\, [1:3]\, [2:4]\, [2:3]$.

���� ���������� � ������ �� ����������� �������� ����� ��������� ��������
������ ����������� ����; ��� �����������~$[i:j]$ ������������ ������
��~$i$ �~$j$, ���~$i<j$. ���� ����� ���������� ������������� ����, ��
����� ������������ \emph{�������} ��~$i$ �~$j$, �����������, ��� �������
����� ������������ � ������ �������. ��������, �� ���.~56 ����������
������������� ���� ��� 16~��������� � �������������~$[1:2]\,[4:3]\,[5:6]\,
[8:7]$ �~�.~�. � ���.~11 ������������, ��� ��� ���� ����������.
����~$x=\<x_1,~\ldots, x_n>$ ���� $n\hbox{-������}$, � $\alpha$~����
$n\hbox{-����}$, �� ���������� �����������~$x\alpha$ ��� �������
�����~$\<(x\alpha)_1,~\ldots,  (x\alpha)_n>$, ����������� �����. �������
����� ��� ���������~$a\lor b=\max(a, b)$,
%%284
$a\land b=\min(a, b)$, $\bar a=1-a$;
�����~$(x[i:j])_i=x_i\land x_j$,
$(x[i:j])_j=x_i\lor x_j$ �~$(x[i:j])_k=x_k$ ���~$i\ne k \ne j$. �����
��������, ��� $\alpha$~�������� \emph{����� ����������,} ����� � ������
�����, �����~$(x\alpha)_i\le(x\alpha)_{i+1}$ ���~$1\le i < n$ � ����~$x$.

ሌ���~$e^{(i)}$ ���������� ������, � �������� � �������~$i$ ���������~1,
� � ��������� ������~0; ����� �������, $(e^{(i)})_j=\delta_{ij}$.
ሌ���~$D_n$ ���������� ��������� ���� $2^n$~$n\hbox{-�������}$ ��������
��~0 �~1, � $P_n$~���������� ��������� ���� $n!$~��������, ����������
��������������~$\set{1, 2,~\ldots, n}$. �� ����� ������������
�����������~$x\land y$ �~$x\lor y$ ���
��������~$\<x_1\land y_1,~\ldots, x_n\land y_n>$
�~$\<x_1\lor y_1,~\ldots, x_n\lor y_n>$  � ����� ������~$x\le y$,
����~$x_i\le y_i$ ��� ����~$i$.
 �� �������, $x\le y$~����� � ������ �����, �����~$x\lor y= y$, � �����
� ������ �����, �����
\picture{���.~56. ������������� ����, ���������� �� �������� ����������.}
$x\land y=x$. ����~$x$ �~$y$ ����� �~$D_n$, �� ����� ��������, ���
\dfn{$x$~���������~$y$,} ����~$x=y\lor e^{(i)}\ne y$ ��� ���������~$i$.
�������, ��� ����~$x$ �~$D_n$ �����~$\nu(x)$ ����� ������ ������ � $x$,
a~$\zeta(x)$---������ �����; ����� �������, $\nu(x)+\zeta(x)=n$.

\ex[20] ��������� ���� �����-��������� ������� ���~$m=3$ �~$n=5$.

\ex[22] ��������, ��� ��������� ���������� �.~������
(��.~���.~5.2.1-30) ������������� ���� ���������� $n$~���������, �������
��������������
$(\log_2 n) \times (\log_3 n)$~������� ��������. ��������� ����� ����
���~$n=12$.

\ex[M20] (�.~�.~������.) ������� ������� ����������� �����~$C(m,
m-1)$ �~$C(m,m)$.

\rex[�23] ��������, ���~$\hat T(6) =5$.

\ex[�21] ��������, ��� ���������~(13) ������������� ����������
����� �������� ��� ���� ����������, ��������� �������������~(10).

\ex[28] �����~$T(n)$ ����� ����������� ������ ������, ���������
��� ���������� � \emph{������������� ����������� ����������������
���������} (��� �������� �����������); ������ ����� ��������� ���������
����� ���� ������������ �����, ���������� ��������� ���~$i_1:j_1$,
$i_2:j_2$,~\dots, $i_r:j_r$, ��� ���~$i_1$, $j_1$, $i_2$, $j_2$,~\dots,
$i_r$, $j_r$ ��������; �� ����� ���� ������� ���� $2^r$~������,
%%285
��������������� �������
$$
\eqalign{
&\<{K_{i_1}<K_{j_1}, K_{i_2}<K_{j_2},\ldots, K_{i_r}<K_{j_r}}>;\cr
&\<{K_{i_1}>K_{j_1}, K_{i_2}<K_{j_2},\ldots, K_{i_r}<K_{j_r}}> \hbox{�~�.~�.}\cr
}
$$
��������, ���~$T(5) =T (6) = 5$.

\ex[25] ��������, ��� ���� ��������� ���������� ���� ���~$n=10$ ��~���.~49
��������� ��������������� ����� ������ � ������� � ����� �������������, ��
���� ��-�������� ����� �����������.

\ex[�20] ��������, ���~$\hat M(m_1+m_2, n_1+n_2)\ge \hat M(m_1, n_1)+
\hat M(m_2, n_2)+\min(m_1, n_2)$ ���~$m_1, m_2, n_1, n2\ge 0$.

\ex[�25] (�.~�.~䋎��.) ��������, ���~$\hat M(3,3)=6$, $\hat M(4,4)=9$,
$\hat M(5,5)=13$.

\ex[�22] ��������, ��� �������� ����������� �������, ��� �� ��������� �
������ �����~(15), ������������� ��������. [\emph{㊀�����.} ����������
��������, ��� ����� ������������� ��� ������������������, ��������� ��
$k$~������, �� �������� ������� $l$~�����, �� �������� ������� $n-k-l$~������.]

\ex[�23] ��������, ��� �������� ����������� ������� �������~$2^p$
����� ����������� �� ������ ������������������~$\<z_0, z_1,~\ldots,
z_{2^p-1}>$, ��� ������� $z_0 \ge \ldots\ge z_k \le \ldots\le z_{2^p-1}$,
�� ����� � ��� ������������������, ��� ������� $z_0\le \ldots \le z_k \ge
\ldots \ge z_{2^p-1}$. [��� ��������� �����, ���� �� ���.~56 �����
����������� 16~���������, ��� ��� ������ ������ ������� �� ��������
������������� ��� ���������� �������� �������������, ����������� �
�������������������, ������� ���� ������������� � ��������������� ������������.]

\ex[�20] �������� ��� ������������ ��������� �����������:
����~$x$ �~$y$---�������� ������������������ ������ �����, ��
������������������~$x\lor y$ �~$x\land y$ ����� ��������.

\rex[24] (X.~�.~ᒎ��). ��������, ��� ���� ���������� ���
$2^t$~��������� ����� ��������� �� �����, ������������������� ���~$t=4$ ��
���.~57. ������ �� $t^2$~����� ���� ����� ������� �� "����������
���������" ������ $2^{t-1}$~��������� � ����������~$2^{t-1}$, �� �������
������� ��������, ����������� ������������ ��� $2^{t-1}$~������ ��������
���������. ������ �� ���� �������� ���������� ����~"$0$" (��� ��������),
����~"$+$" (����������� ������������� ������), ����~"$-$" (����������
������������� ������). ᎐������� ��������� � $t$~������ �� $t$~�����
������; �� ��������� ������ ��� �������� ����~"$+$". � �������
������~$s$ ���~$s<t$ �� ��������� $t-s$~�����, ��� ��� �������� ����~"$0$",
 � ����� ��������� $s$~�����, ��� �� ������ $q-\hbox{�}$~���� ����������
����������� $2^{q-1}$~��������~"$+$" � ����� $2^{q-1}$~��������~"$-$"
���~$q=1$, 2,~\dots, $s$.

[�������, ��� ��� ����� ���������� ����� ���� ��������� ������
������� �����������, ����������� ���� ��� "��������� � ��������" �
���������� ����� ������� �� ����. ������ ��� ���� �� ���.~57 �����,
�������, ���������, ��� ���������, ���� ����� ������� ����� ��������.
ᒎ�� ��������, ��� ��� �� ������� "���������/��������" ����������� �
��������� ������ ����������, �����, ��� ������� �������������� 䓐��
(��.~�.~4.6.4).]

\ex[�20] ��������, ��� ����� $(1, n)\hbox{-����}$ ������� ���
������������ ������ ����� �� ����� $\ceil{\log_2(n+1)}$~������� ��������.

\ex[20] ������� ������������� ���� ���������� ������� ���������,
���������� ������ ���� ������������� �������.

\ex[M22] ��������, ��� ��������� �������� ����������� �����
���� ����������~$[i_1:j_1]\cdots[i_r:j_r]$ � ����������� ���� ����������:
%% !!! ���������� �����, ��������� � ����������
{\medskip\narrower
 \item{T1.}~�����~$q$--- ���������� ������, �����, ���~$i_q>j_q$. ���� �����
�������� ���, �� ������������.
\item{T2.}~�������� ��� ���������~$i_q$ ��~$j_q$ � ��� ���������~$j_q$
��~$i_q$ �� ���� ������������~$[i_s:j_s]$ ���~$q\le s \le r$. ��������� �
����~T1.\endmark
\medskip}

\noindent ��������, ����~$[4:1]\,[3:2]\,[1:3]\,[2:4]\,[1:2]\,[3:4]$
������������� ������� �~$[1:4]\,[3:2]\,[4:3]\,[2:1]\,[4:2]\,[3:1]$, �����
�~$[1:4]\,[2:3]\,[4:2]\,[3:1]\,[4:3]\,[2:1]$, �����
%%286
\picture{���.~57.~᎐������� 16 ��������� � "��������� ����������".}
%%287
�~$[1:4]\,[2:3]\,[2:4]\,[3:1]\,[2:3]\,[4:1]$ �~�.~�., ���� �� ���������
����������� ����~$[1:4]\,[2:3]\,[2:4]\,[1:3]\,[1:2]\,[3:4]$.

\ex[�25] �����~$D_{tn}$ ����� ���������� ����
$\perm{n}{t}$~������������������� $\<x_1,~\ldots, x_n>$ �� ����� � ������,
������� ����� $t$~������. ��������, ��� $\hat U_t(n)$~����� ������������
����� ������������, ������� ���������� � ����, ����������� ���
��������~$D_{tn}$; ��� $\hat V_t (n)$~����� ������������ �����
������������, ������ ��� ����������~$D_{tn}\cup D_{(t-1)n}$; � ��� $\hat
W_t(n)$~����� ������������ ����� ������������, ������ ���
����������~$\bigcup_{0\le k \le t} D_{kn}$.

\rex[�20] ��������, ��� ����, ������� ���������� ������� $2t-1$~���������,
������� �� �����~$(t-1)\ceil{\log_2(t+1)}+\ceil{\log_2 t}$
������������� �������. [\emph{㊀�����:} ��. �������������� �������~A.]

\ex[�22] ��������, ���~$\hat U_2(n)=2n-4$ �~$\hat V_2(n)=2n-3$ ��� ����~$n\ge2$.

\ex[24] ��������, ���~$\hat V_3(5)=7$.

\ex[M15] �����~$\alpha$---����� $n\hbox{-����}$, �~$x$ �~$y$---���
$n\hbox{-�������}$. ��������, ��� ��~$x\le y$ �������~$x\alpha \le y\alpha$.

\ex[�15] ��������, ��� ����~$x$ �~$y$ ���� $n\hbox{-�������}$
�������������� �����, ��~$x\cdots y \le (x\alpha)\cdot(y\alpha)$.
(�����~$x\cdot y$---��������� ������������ $x_1y_1+\cdots+x_ny_n$.)

\ex[�17]. �����~$\alpha$ ����~$n\hbox{-����}$. ��������, ��� ����������
������������~$p\in P_n$, �����, ��� $(p\alpha)_i=j$ ����� � ������ �����,
����� �~$D_n$~�������� �������~$x$, $y$, �����, ���~$x$ ���������~$y$,
$(x\alpha)_i=1$,
$(y\alpha)_i=0$ �~$\zeta(y)=j$.

\rex[M21] (�.~�.~��������.) �����~$\alpha$ ����~$n\hbox{-����}$; ������
����������� $l_k=\min\set{ (p\alpha)_k \mid p\in P_n}$,
$u_k=\max\set{(p\alpha)_k\mid p\in P_n}$ ���~$1\le k \le n$ ��� ������ �
������� ������ ��������� ��������, ������� ����� ���������� �� ������~$k$
������. �����~$l'_k$ �~$u'_k$---���������� ������������ �������� ���
����~$\alpha'=\alpha[i:j]$. ��������, ���~$l'_i=l_i\land l_j$,
$l'_j\le l_i+l_j$,
$u'_i\ge u_+u_j-(n+1)$, $u'_j=u_i\lor u_j$.  [\emph{㊀�����:} ��� ������
��������~$x$ �~$y$ ��~$D_n$, �����,
���~$(x\alpha)_i=(y\alpha)_j=0$, $\zeta(x)=l_i$, $\zeta(y)=l_j$, �������
������~$z$ ��~$D_n$, �����, ���~$(z\alpha')_j=0$, $\zeta(z)\le l_i+l_j$.]

\ex[M30] �����~$l_k$ �~$u_k$ ����������, ��� � ���.~24. ��������, ���
���������~$\set{(p\alpha)_k \mid  p\in P_n}$ �������� ��� ����� �����
�����~$l_k$ �~$u_k$ ������������.

\ex[M24] (�.~�.~䋎��.) �����~$\alpha$ ���� $n\hbox{-����}$. ��������, ���
���������~$D_n\alpha=\set{x\alpha \mid x\in D_n}$ ����� ���� ����������,
�� ���������~$P_n\alpha=\set{p\alpha \mid p\in P_n}$ �, �������,
$P_n\alpha$~����� ���� ���������� ��~$D_n\alpha$.

\rex[M20] �����~$x$ �~$y$---�������, � �����~$x\alpha$
�~$y\alpha$---��������������� �������. ��������, ���~$(x\alpha)_i\le
(y\alpha)_j$ ����� � ������ �����, ����� ��� ����� ������������
$j$~��������� ��~$y$ ����� ����� ������������ $i$~��������� ��~$x$, �����,
��� ����� �������, ������ ��~$x$, ������ ���������� ��������,
������� ��~$y$, ��� ����� ���. ����������� ���� ������� ��� ��������������
����, ��� \emph{���� ������������� ������ ����� �������, � �����
������������� �������, �� ������ ��������� ��������������.}

\rex[�20] ዅ������ ��������� ����������, ��� �������� ������� ���
����������� ���� ����� ���� ���������� ����� �� �����:
\picture{p.287}
��������� ������ ���������������~$x\land y =y \land x$, $x\lor y = y \lor x$,
������ ���������������~$x\land (y\land z)=(x\land y) \land z$,
$x \lor (y \lor z) = (x \lor y) \lor z$, ������ ����������������
$x\land (y\lor z)=(x\land y)\lor (x\land z)$,
$x\lor(y\land z)=(x\lor y)\land (x\lor z)$, ������ ����������
$x\land (x\lor y)=x\lor(x\land y)=x$ � ������ ���������������
$x\land x=x\lor x = x$, �� ����� ������ ������� � ������ ����� ���� ����
�������������� �~$(a \land b \land c \land d)$,
$(a\land b \land c) \lor (a\land b \land d) \lor (a\land c\land d) \lor (b \land c \land d)$,
$(a\land b) \lor (a \land c) \lor (a \land d) \lor (b \land c) \lor (b \land d) \lor (c \land d)$,
$a \lor b \lor c \lor d$. ��������,
%%288
��� � ����� ������ $t\hbox{-�}$ � ������� �������� �������
��~$\set{x_1,~\ldots, x_n}$ ������ "������������ �������������� ��������"
$$
\sigma_t(x_1,~\ldots, x_n)=
\bigvee \set{x_{i_1}\land x_{i_2}\land\ldots\land x_{i_t} \mid
1\le i_1 < i_2 < \ldots < i_t \le n}.
$$
[����� $\perm{n}{t}$~������ ������������ ���������~$\vee$ ������.  ��
�������, ������
���������� ���� ���������� ����������� ��������� ������������ ������
���������� ������������ �������������� ������� � ����������� ������
���� "�/���", ��� �� ������ ���� ��� ��������~$\phi$ �~$\psi$ ����������
��~$\phi\land\psi$ �~$\phi\lor\psi$.]

\ex[M20] ����, ���~$x_1\le x_2 \le x_3$ �~$y_1\le y_2 \le y_3 \le y_4 \le
y_5$ � ���~$z_1\le z_2 \le \ldots \le z_8$---��������� �������~$x$ �~$y$.
������� ��������� ��� �������~$z$ �����~$x$ �~$y$, ���������
���������~$\land$ �~$\lor$.

\ex[��24] ��������, ��� ����� �������, ����������~$\land$, $\lor$ �
����������� ����������~$\set{x_1,~\ldots, x_n}$, ����� ���� ��������� �
�������������� �������� �� ���.~28 � "������������"
�����~$\tau_1\lor\tau_2\lor\ldots\lor\tau_k$, �����~$k\ge1$ �
������~$\tau_i$ ����� ���~$\land \set{x_j \mid j \in S_i}$,
���~$S_i$---������������~$\set{1,2,~\ldots, n}$ � ������� ���������~$S_i$ ��
���������� �~$S_j$, ����~$i\ne j$. �������� �����, ��� ��� �����
������������ ����� ����� ��� ����~$x_1$,~\dots, $x_n$ ����� � ������ �����,
 ����� ��� ��������� (� ��������� �� �������).

\ex[�24] (�.~��������, 1897.) �����~$\delta_n$---����� ���������
������������ ���� ��~$x_1$,~\dots, $x_n$ � ������ ���.~30  ,
$\delta_1=l$, $\delta_2=4$ �~$\delta_3=18$. 煌� �����~$\delta_4$?

\ex[�28] (�.~�.~����.) �����~$G_1=\set{00, 01, 11}$; ���������~$G_{n+1}$
��� ��������� ���� �������~$\theta\phi\psi\omega$, �����, ���~$\theta$,
$\phi$, $\psi$, $\omega$ ����� �����~$2^{n+1}$ �~$\theta\phi$,
$\psi\omega$, $\theta\psi$ �~$\phi\omega$ �����������~$G_n$.
�����~$\alpha$---����, ��������� �� ������� ������ ������� 16-������������,
������������� �� ���.~48. ��������, ���~$D_{16}\alpha=G_4$, � ��������,
��� ��� ��������� ����� � �������� $\delta_4+2$~���������. (�.~���.~31.)

\rex[�22] �� ��� $\delta_n$~������� ��~$\<x_1,~\ldots, x_n>$ �� ���.~31
����� ����������� � ������������� �����. � ������ ��������, ���
�������~$(x_1\land x_2) \lor (x_2\land x_3) \lor (x_3\land x_4)$ �� �����
���� ����������� ������� ������������� ���� ��~$\<x_1,~\ldots, x_n>$.

\ex[23] ����� �� ��������� ���� ����� ����������?
\picture{p.288}
\ex[20] ��������, ��� � ����� \emph{����������� ����} ���������� ������ ��
������� ���� ���� ��� ����������� ������ �� ������������~$[i:i+1]$
���~$1\le i < n$.

\rex[22] ᅒ� �� ���.~47 �������� ������ \emph{����������}
���������~$[i:i+1]$; ����� �������� ����� ���� \dfn{������������,}
(a)~��������, ��� ����������� ���� ���������� ��� $n$~��������� ������
����� �� ����� $\perm{n}{2}$~������������. [\emph{㊀�����:} �����������
�������� ������������.] (b)~(�.~�.~䋎��, 1964.)
�����~$\alpha$---����������� ���� ��� $n$~���������, �~$x$---������, �����,
���~$(x\alpha)_i >(x\alpha)_j$ ��� ���������~$i<j$. ��������,
���~$(y\alpha)_i>(y\alpha)_j$,
���~$y$---������~$\<n, n-1,~\ldots, 1>$. (�)~� �������� ���������~(b)
��������, ��� �����������
%%288
���� �������� ����� ���������� ����� � ������ �����, ����� ���
��������� ������������ ������~$\<n, n-1,~\ldots, 1>$!

\ex[�22] \dfn{煒��-�������� ���������� � ��������������} ��� $n$~�����,
$n\ge 3$, ��� $n\hbox{-���������}$ ���� � ${1\over2}n(n-1)$~�������������,
������������ ��������� ������ (���.~58). (���� $n$~�����, ������� ���
�����������.)  �� ���������� �������� ����� ����������� �����������, ���
��� ����������� ����������� ������ ��� ���� ��������. ��������, ��� �����
���� ������������� ����� ���������� ����� ����������. [\emph{㊀�����:} ��.~���.~36.]
\picture{���.~58.  煒��-�������� ���������� � ��������������.}

\ex[29] ����� ���� ������ ������������� ����� ����������, ������, ��� ��
������ ����� ��������� ��������������� �� $m$~�����, � �� ���� �����; ���
���� ������������� ��������~$[i:j]$ ��������~$x_i$ �~$x_j$
�������������� ��~$x_i \upup x_j$ �~$x_i\dndn x_j$---����������~$m$ �
����������~$m$ ��~$2m$ �����~$x_i\uplus x_j$. (���.~59 ������������ ���
���~$m=2$.) ����~$a$ �~$b$ ���� ���������������, ���������� $m$~�����
������, �� ����� ��������, ���~$a \lflf b$ �����
\picture{���.~59.  ������ ������������� ���� ����������, �������������� ��
���.~44: ������ ������������� ������ ��������� �������� �������.}
� ������ �����, �����~$a \upup b=a$ (���, ������������, $a \dndn b=b$;
���������� �������~$a$ ������ ��� ����� ����������� ��������~$b$).  ��
�������,
$a \upup b \lflf a \dndn b$.

�����~$\alpha$ ���� $n\hbox{-����}$, a~$x=\<x_1,~\ldots, x_n>$---������, �
������� ������ ����������~$x_i$---��������������� �� $m$~���������. ��������,
��� ����~$(x\alpha)_i$ �� $\lflf (x\alpha)_j$ � ��������� �������������,
�� �~$D_n$ �������� ������~$y$, �����, ��� $(y\alpha)_i=1$
�~$(y\alpha)_j=0$. [ዅ����������, ���� ���������� $n$~���������
������������ � ���� ���������� $mn$~���������, ���� �������� ���������
$m$-�������� ���������. �� ���.~60 ��������� ����������������
�����������, ����������� �� ������������������ � �������������� �����
����������.]

\rex[�23] ��������, ��� � ������������ ���.~38
$(x\upup y)\upup z=x\upup (y\upup z)$ �~$(x\dndn y)\dndn z=x\dndn(y\dndn
z)$, ������ $(x\dndn y)\upup z)$ \emph{��}  ������ �����~$(x\upup z)\dndn
(y\upup z)$ �~$(x\upup y)\dndn (x\upup z)\dndn (y\upup z)$ \emph{��}
������ ����� ������� $m$~���������~$x\uplus y \uplus z$. �������
���������� ������� ��� ���� ������� ���������, ����������� � ��� $x$, $y$,
$z$, � ����� ��������~$\upup$ �~$\dndn$.
%%290

\ex[M25] (�.~�.~������.) ����������~$[i:j]$ ���������� ���������� �
����~$\alpha_1[i:j]\alpha_2$, ���� ����~$(x\alpha_1)_i \le (x\alpha_1)_j$
��� ���� ��������~$x$, ����~$(x\alpha_1)_i\ge (x\alpha_1)_j$ ��� ����
��������~$x$. ��������, ��� ���� $\alpha$~�������� ����� �
$r$~������������� �������������, �� �������� �� ������� ����
$r$~��������� �������������
\picture{���.~60.   8-�����������, ����������� �� 4-������������ �
�������������� �������.}
���~$(i, j)$ ��������� ��������, �����, ���~$(x\alpha)_i\le (x\alpha)_j$
��� ���� ��������~$x$. (ዅ����������, ���� ��� ���������� ������������
�������� �� ����� $\perm{n}{2}$~�������.)

\rex[M27] (�.~�.~��������.) �����~$\alpha=[i_1:j_1]\ldots[i_r:j_r]$ ����~$n\hbox{-����}$;
���~$1\le s \le r$
���������~$\alpha^s=[i'_1:j'_1]\ldots[i'_{s-1}:j'_{s-1}]\,
[i_s:j_s]\ldots[i_r:j_r]$, ���~$i'_k$ �~$j'_k$ �������� ��~$i_k$ �~$j_k$
�������~$i_s$ ��~$j_s$ �~$j_s$ ��~$i_s$ �����, ��� ��� �����������.
��������,
����~$\alpha=[1:2]\,[3:4]\,[1:3]\,[2:4]\,[2:3]$, ��~$\alpha^4=[1:4]\,
[3:2]\,[1:3]\,[2:4]\,[2:3]$.
{\medskip\narrower
\item{a)}~��������, ���~$D_n\alpha=D_n(\alpha^s)$.
\item{b)}~��������, ���~$(\alpha^s)^t=(\alpha^t)^s$.
\item{c)}~\dfn{ᎏ��������~$\alpha$} �������� ����� ����
����~$(\ldots((\alpha^{s_1})^{s_2})\ldots)^{s_k}$. ��������, ���
$\alpha$~����� �� ����� $2^{r-1}$~����������.
\item{d)}~�����~$g_\alpha(x)=1$, ����~$x\in D_n\alpha$, �~$g_\alpha(x)=0$,
����~$x\notin D_n\alpha$, � �����
$$
f_\alpha(x)=(\bar x_{i_1}\lor x_{j_1})\land\ldots\land(\bar x_{i_r}\lor x_{j_r}).
$$
��������,
���~$g_\alpha(x)=\bigvee\set{f_{\alpha'}(x)\mid \hbox{$\alpha'$ ���� ����������~$\alpha$}}$.
\item{e)}~�����~$G_\alpha$---������������ ���� � ���������~$\set{1,~\ldots,
n}$ � ������~$i_s\to j_s$ ���~$1\le s \le r$. ��������, ��� � ��������
����� ���������� ����� � ������ �����, ����� ��� ���� ��
����������~$\alpha'$ �~$G_{\alpha'}$ ������� ��������������� ���� ��~$i$
��~$i+1$ ���~$1\le i < n$. [풎 �������� ���������� �������,
���������~$G_\alpha$ �� ������� �� ������� ������������ �~$\alpha$.]
\medskip}

\rex[25] (�.~��� �����.) ��������, ���~$\hat S(n)\ge \hat
S(n-1)+\ceil{\log_2 n}$.

\ex[23] \dfn{��������������� �����} ���������� ������������������
�������~$[i_1:j_1]\ldots[i_r:j_r]$, ��� ������ ������~$[i:j]$ �����
��������������� ����� � ���� �� ���� ���������: ���� �� �������� ����
����� ��� ���������, ���� ������ �������~$x_i$ �~$x_j$ (���������� ��
��������~$x_i$ �~$x_j$), � ������������������ ������� ������ ���� �����,
��� �� ������ ����� �������� ����� ������������ ������ ��� ���������������
��������� �������. ����� ���� ���������� ��������, ��������,
��������������� �����, �� �������� �������. ������� ��������������� ����
��� ���� ���������, ������� ������ ������ �������.
%%291

\ex[46] ������� �������� ����� ����������, ����������� ��
$m$-������������� ������ 2-�������������. (��������, �.~耏��� �������� ����
��� ���������� 16~���������, ����������� ������������
4-�������������. ��������� �� ��� �������? ᓙ������� �� ��� ����
$m$~����������� ������ ����������  $m^2$~��������� � ������� �������,
����������� $m$-����������?)

\ex[48] �������, $(m, n)\hbox{-����}$ ������� � ������ ������������,
�������~$C(m,n)$, ��� ��������, ��� ����� ���� �� ����������.

\ex[48] ������� $(m, n)\hbox{-����}$ ������� ������, ��� �
$\ceil{\log_2 (m+n)}$~�������� ��������, ��� ��������, ��� �� �� ����������.

\ex[48] ������� ����� ���� ����������, ������� ����� ���� ����������� �
���� ���� � ��������� ����������, ��� �� ���.~57, �� �
������ ������������� ��������~"$0$", "$+$" �~"$-$".

\ex[��49] ���������� �������� ��������~$\upup$ �~$\dndn$, ������������ �
���.~38. ����� �� ���������������� ��� ��������� � ���� ������� �����-����
������� �������� ��� ������� ��� �� �� ��������� ������ ��������? �
���� ��������� ����� ���������, ���
$$
x\upup x \upup x = x \upup x \hbox{ ��� } x\upup (x\dndn (x\upup (x\dndn
y)))=x\upup(x\dndn y),
$$
������� ����� ����� ������ ���~$m\le 2$, ������������ ������������
��������� �������; �������������� ���� ���������, ������������ ��� \emph{����}~$m$.

\ex[M49] ������ ��������������� ��������� �������~$T(n)$, ������������ �
���.~�? ����� �� ���� $T(n)<\hat T(n)$ ��� �����-������~$n$?

\ex[50] ������� ������ ��������~$\hat S(n)$ ��� ������-����~$n>8$.

\ex[�50] ��������, ��� ��������������� ��������~$\hat S(n)$ ��
����~$O(n\log n)$.

\centerline{{\bf  �ࠦ�����, (���� ����)}}

ዅ������ ���������� ����� ���� � ���������� ������ ����������� �����,
���������� ����������. ������ ��������� ����� �������� �� "����������
"���������������" ��������� ������ ��������,
������������ �.~�.~����������� �~�.~��.~��������� ��� �~1954~�.
[�.~U.~S.~Patents 3029413, 3034102.]
�����~$1=h_1<h_2<\ldots<h_m=n$---������������ ������������������ �����
�����; ����� �������� �� "������������������� �������" �����~$m$ �
����������~$n$. ��� ����� �������������� ��� ����������� �������
���������� ������������ ����. ᎐������� �������~$R_1$~\dots{}$R_N$
�������������� �� ��������� ��������, � ������ ������ ������� ��
$N+n-1$~�����. �� ����~$j$ ���~$j=1-n$, $2-n$,~\dots,.$N-1$
��������������� ������~$R_{j+h[1]}$, $R_{j+h[2]}$,~\dots, $R_{j+h[m]}$,
������� � ������ ������������� �������������� ���, ����� �� �����
��������� ��������������. (�� �������, ���~$R_{j+h[1]}\ldots{}R_{j+h[m]}$
��������� "��� ��������� ������-������". ����~$j+h[k]$ ����~$<1$,
����~$>N$, �� ������~$R_{j+h[k]}$ �� ���������������, ����� ������,
%%292
�����~$K_0$, $K_{-1}$, $K_{-2}$,~\dots{} ��������� �������~$-\infty$,
a~$K_{N+1}$, $K_{N+2}$,~\dots{}---�������~$+\infty$. ������� ���~$j\le
-h[m-1]$ ���~$j>N-h[2]$ ���~$j$ ���������.)

��������, � ��������� ������� ������� ���� ������ ���������� ���~$m=3$,
$N=9$ �~$h_1=1$, $h_2=2$, $h_3=4$:
{\def\ul#1{\underline{#1}}\def\emp{\phantom{0}}
\ctable{
$#$\hfill && \bskip\hfill$#$\hfill\bskip\cr
& K_{-2} & K_{-1} & K_0 & K_1 & K_2 & K_3 & K_4 & K_5 & K_6 & K_7 & K_8 &
K_9 & K_{10} & K_{11} & K_{12}\cr
j=-3 &  \ul{\emp} & \ul{\emp} &               & \ul{3} & 1 & 4 & 5 & 9 & 2
& 6 & 8 & 7 \cr
j=-2 &                  & \ul{\emp}& \ul{\emp}& 3 & \ul{1} & 4 & 5 & 9 & 2
& 6 & 8 & 7 \cr
j=-1 &                  &               & \ul{\emp}&\ul{3} & 1 & \ul{4} &
5 & 9 & 2 & 6 & 8 & 7\cr
j=0  &                  &               &                &\ul{1} & \ul{3}
& 4 & \ul{5} &  9 & 2 & 6 & 8 & 7 \cr
j=1  &                  &                &                & 1 & \ul{3} &
\ul{4} & 5 & \ul{9} & 2 & 6 & 8 & 7 \cr
j=2  &                  &                 &                & 1  & 3 &
\ul{2} & \ul{4} & 9 & \ul{5} & 6 & 8 & 7 \cr
j=3  &                  &                  &                & 1  & 3 & 2 &
\ul{4} & \ul{6} & 5 &\ul{9} & 8 & 7 \cr
j=4  &                  &                  &                 & 1 & 3 & 2 &
4 & \ul{5} & \ul{6} & 9 & \ul{8} & 7 \cr
j=5  &                  &                  &                  & 1 & 3 & 2
& 4 & 5 & \ul{6} & \ul{7} & 8 & \ul{9}\cr
j=6  &                   &                 &                   & 1 & 3 & 2
& 4 & 5 & 6 & \ul{7} & \ul{8} & 9 & \ul{\emp} \cr
j=7  &                   &                  &                  & 1 & 3 & 2
& 4 & 5 & 6 & 7 & \ul{8} & \ul{9} & & \ul{\emp}\cr
j=8  &                   &                   &                 & 1 & 3 & 2
& 4 & 5 & 6 & 7 & 8 & \ul{9} & \ul{\emp}&  & \ul{\emp} \cr
}
}


�������, ���, ����~$m=2$, $h_1=1$ �~$h_2=2$, ���� "���������������"
����� �������� � ������ �������� (��������~5.2.2B).

\ex[21] (������ �������.) ��������, ��� ����~$h[k+1]=h[k]+1$
��� ���������~$k$, $1\le k < m$, �� ��������������� �����������,
������������ ����, ����������� ����� ������� ���� �� �������� �����
��������. ��
����~$h[k+1]\ge h[k]+2$ ���~$1\le k < m$, �� ����� ���������, ��� �������
������������������ \emph{�������} �� ������ �������������.

\edef\exref{\the\excerno}
\rex[50] (��������� �~�������.) �����~$h[k+1]\le h[k]+k$ ���~$1\le k\le m$
�~$N\ge n-1$. ��������, ��� � ������� ������� �������
���������� $n-1$~��������� ������ ������ ���� ������������� �����.
[\emph{㊀�����:} ����������� ������� ����� � ������; ��������, ��� ����
����������� ������������������ �� ����� � ������, ������ ������
������~$n$, �� ��� ������� ����� ������~1 ���� � ��� ������, ����� ���
���� ����� ����� �� �������.]

��������, ��� ���� ������� ������������� ���������������� ��������, ��
���������� ����� ��������� �� �����, ��� ��
$\ceil{(N-1)/(n-1)}$~��������. ᓙ������� �� ������� ����, ��� ��������
���������� ����� ������� ��������?

\ex[26] ��������, ��� ���~$n=N$ ������ ������ �������� ����������  ���� �
�������~$R_1$ ����� � ������ �����, �����~$h[k+1]\le 2h[k]$, $1\le k<m$.

\ex[34] (��.~厏�����.) "ᎂ�������� �������������"
$N$~��������� ���������� ��������������� �����������, ������� ������
����������� ������ �� ���� ������. ㏐�������~\exref{} ����������, ���
������������������
$$
\<h_1, h_2, h_3, h_4,~\ldots, h_m>=\<1, 2, 4, 7,~\ldots, 1+\perm{m}{2}>.
$$
�������� ����������� ����������� ��� $N=\perm{m}{2}$~���������, ���������
$m=(\sqrt{8N-7}+l)/2$~�������. ��������, ������������������
�������~$\<1, 2, 4, 7, 11, 16, 22>$ �������� ����������� ������������� ���
22~���������.

��������, ��� ������������������ �������~$\<1, 2, 4, 7, 11, 16, 23>$
�� ����� ���� ����� ����������� ������������� ��� 23~���������.

\ex[49] ���������� ��� ��������~$m$ ����������~$N$, ��� ��������
���������� ����������� ����������� � $m$~���������. ����� ��, ���~$N=O(m^2)$?
%%293

\ex[23] (�.~�����.) ���� ������ �������~$h_k$ ��������� �
���������~$2^{k-1}$  ���~$1\le k \le m$, �� ������� �������� �����������
��� ���������� ������������������ ����� �
������~$z_1$ $z_2$~\dots{} $z_{2^{m-1}}$,
��� $z_j=0$ ����� � ������ �����, ����� $j$~�������� ��������~2?

\ex[24] (���������� ����������.) � ������ �� ���.~34 � �.~5.3.1
���������~$2:3$ ����������� � ����� ������ ������~1; � � ������ �����
������~2 ����������� ���������~$1:3$, ���� ������ ��� �� ��������
����������. � ����� ������ �� ����� ����������� ����� ����������
����������, ����������
������ � ���� ������, �����������, ���~$M=\perm{N}{2}$
���~$\set{(a,b) \mid 1\le a<b\le N}$ ��������� � ������������������
$$
(a_1, b_2)\, (a_2, b_2)\ldots(a_M, b_M);
$$
�� ����� ��������������� ��������� �� �� ���������~$K_{a_1}:K_{b_1}$,
$K_{a_2}:K_{b_2}$,~\dots, ��������� ������� ��� �� ��������. ������ ��
$M!$~����������� ���~$(a,b)$ ���������� �������� ���������� ����������.
���� ���������� ���������� ����������� X.~�.~����� [{\sl JACM,\/}{\bf 17}
(1970), 482--495], � ������ �������� ���� ���������� ��������� ���������
����������.

��� ����������� ����������� ���������� ���������� ������ ���������������
������� ������. �����~$G$---������������ ���� � ���������~$\set{1, 2,~\ldots, N}$
� ��� ���. ���~$i=1$, 2,~\dots, $M$ �� ��������� ���� �~$G$ ��������� �������:
\medskip
{\sl ዓ���~1.\/}~�~$G$ ������� ���� ��~$a_i$ �~$b_i$.
�������� �~$G$ ����~$a_i\to b_i$.

{\sl ዓ���~2.\/}~�~$G$ ������� ���� ��~$b_i$ �~$a_i$.
�������� �~$G$ ����~$b_i\to a_i$.

{\sl ዓ���~3.\/}~�~$G$ ��� ���� �� ��~$a_i$ �~$b_i$, �� ��~$b_i$ �~$a_i$.
᐀�����~$K_{a_i}:K_{b_i}$; �����, ����~$K_{a_i}\le K_{b_i}$, ��������
�~$G$ ����~$a_i\to b_i$, ���� ��~$K_{a_i}>K_{b_i}$, �� ��������
����~$b_i\to a_i$.
\medskip

��� ���������� ������� ������� ����� ��������� ������,
����������� ���������� ���������� ����������, � �� ��������, � �������
�������� ������������� ����������� ���������� ���������; ����~$G$ ��
����������� ������� � ����� ����---����� �� ������������ ������ ���
����������� ���������� ����������.

����� ����� ������������� \dfn{������������ ���������� ����������,}
��� ������� � ��������� ���� ������� 1--3 ����������� ������ ����
�����~2. (�������� ������������ ���������� ����� ��������� ���������
���������� ���������, ��, ��� ���������� ���.~59, ������ �������������
������ ��������� �����.)

��������, ��� �������� ������������ ���������� ���������� ��������� �
���������� ���������� ����������, ����� ������������������ ���
����������������� �����������:
$$
(1, 2)\, (1, 3)\, (1, 4)\ldots(1, N)\, (2, 3)\, (2, 4)\ldots(2, N)\ldots
(N-1, N).
$$
��������, ��� �� ����� ���� ��� ��������� ������������ "�������
����������" (��������~5.2.2Q), ���� ��� ����� �������� � ����������
��������� ������� ���������� ���������, ��� � ���.~5.2.2-24. (�� ���������
�������� �� �������, � ������� ������������� ����������� ��������� �
������� ����������; ���������� ������, ����� ���� ������ ������������.)

\ex[�38] ��� ��������, ��� � ���.~58, ������������������ ���~$(a_1,
b_1)$~\dots{}$(a_M, b_M)$ �����~$c_i$ ����� ������ ���~$(j, k)$, �����,
���~$j<k<i$
�~$(a_i,  b_i)$, $(a_j, b_j)$, $(a_k, b_k)$ �������� �����������.
(a)~��������, ��� ������� ����� ���������, ����������� ����������
������������ ���������� ����������, �����~$\sum_{1\le i\le M} 2/(c_i+2)$.
(b)~����������� ���������~(a) � ���.~58, ����� ���������� ������� �����
������������ ���������, ����������� ������� �����������.
%%294
(c)~ዅ������ ������������������ ��� ������� ����������� �������� (��
�� ������������ ��):
$$
(1, 2)\,(3, 4)\,(5, 6)\ldots (1, 3)\,(1, 4)\,(2, 3)\,(2, 4)\,(5, 7)\ldots
(1, 5)\,(1,6)\,(1, 7)\,(1, 8)\, (2, 5)~\ldots
$$
��� ���������� ������, ���������� �� ���� ������������������, �����
����������� � ������� ������ ��� ������ ���������, ��� ��� ������� ����������?

\ex[�29] ������� ���������� ���������� � ��������� ������
$\perm{N}{2}$~���������. ����� ��, ��� ��� ��������� ������������
���������� ���������� (� ������ ���.~57) ��������� $\perm{N}{2}$~���������
� ��������� ������?
\picture{���.~61. 㑒�������, ��� �������� ��������� ������ ��������
�������� �����������.}

\ex[�48] (X.~�.~����.) ����� ��, ��� ������� ���������� �����
����������� ������� ����� ��������� ����� ���� ���������� (������������)
���������� ����������?

\ex[25] ���������� ����������� ������� �.~������ "Electronic Data Sorting"
(Stanford University: October 1956) ����, ��������, ������ �������, �
������� �������-������ �������� ��������������� ������� ���������
����������. ����� ���������� ��������� ����������� ������� ���������
��� ���������� � ����� ������ � ������� ������ �������� � �������������
������� ����������, ����������� � ������ ������. ���������� ���
������---"����������� ������������� ������" (���.~61)---������ ����� ����� ����������.

���������� ������, ������� ���������~$R_1$ $R_2$~\dots{} $R_N$  �� ���
��������, ��� ������ ������ ������� �� ��������� $N +1$~�����:
\medskip
{\sl 考~1.\/}~㑒������� $R\asg R_1$i. ($R$---��� ���������� ������� ������.)

{\sl 考~$i$.\/}~($1<i\le N$):
���� (a)~����������~$R_{i-1}\asg R$, $R\asg R_i$;

���� (b)~���������� $R_{i-1}\asg R_i$, ��������~$R$ ����������.

{\sl 考~$N+1$.\/} 㑒�������~$R_N\asg R$.
\medskip

������ ������� � ���, ����� ����� ����� ����� ������ �����
��������������~(a) �~(b), ����� �������������� ����� ��������, ������
��� ����������.

��������, ��� ����� "��������" ��������� ��� ���� ������. ������� �������,
��������, ��� ��� ���������, ������� �������� ������������~(a), ����~$R\le
R_i$, � ������������~(b), ����~$R>R_i$, ����������� ����������� ����� ��������.

%% 295
\bye
