\input style

\proof �����������, ��� � ������ ������� ������������� $b$~�������; 
������������� ��� ��������� � �����, � ���� �� ���������� ������������ 
���������� �������. ���� ����� ��������������� � ������������ �� ��������� 
����������, ������� �~$k$ (������� ����), �������~$1$.
\picture{���. 87.  �������� ����� ��� �����.}
% !!! � ����� ��� ���������
\alg K.(�������� ����� ��� �����)
\st[�������� �����.] �� $b+c$~�����, ����������� � ������ ������ � ����� � 
�� �����~$k$, ������~$b$, ������� ����� ������� ����� ����������, 
�������� � ����, ��������� �������� �� �����~$k$.

����� ������ � ����� ��������� $u$~������� � �����������~$>k$ �~$d$ � 
�����������~$\le k$. (��������, ���~$u=\min (b, u_k)$;
����~$u_k<b$, �� �����, �������������, ������� ��������� ����� �� �� ����� 
����������. 풎---�� ������ ��� ����� ������). ㌅������~$u_k$ ��~$u$, 
���������~$d_{k+1}$ ��~$d$ � ����� ���������~$k$ ��~$1$.

\st[���������� �������� �����?] ����~$u_k>0$, ��������� � ����~\stp{1}.

\st[�������� ����.] �� $b+c$~�����, ����������� � ������ ������ � ����� 
��� �� �����~$k$, ������~$b$, ������� ����� ������ ����� ����������, 
�������� � ����, ��������� �������� �� �����~$k$. ����� ������ � ����� 
��������� $u$~������� � �����������~$\ge k$ �~$d$ � �����������~$<k$. 
(������ �����������, ���~$u=0$, a~$d=b$, �� �������� ����������� 
����� ������������� � �����~$u$ �~$d$, ����� ������� �������������� 
��������� ����������.) ㌅������~$d_k$ ��~$d$, ���������~$u_{k-1}$ ��~$u$ 
� ����� ���������~$k$ ��~$1$.

\st[���������� �������� ����?] ����~$k>1$ �~$u_{k-1}>0$, ��������� � 
����~\stp{3}. ����~$k=1$ �~$u_1=0$, ��������� �������� (��� ���� 
���������� �� ���� ����� ����������, � $b$~"��������������" ����� ����� 
��������� � �����). � ��������� ������ ��������� � ����~\stp{2}
\algend

�� ���.~88 ������� ������ ������ ����� ��������� ��� ������ � ������� 
������� �~$b=3$, $c=2$. �������, ��� ���� �� �������� �������� 
������������ �� ������ ����� ����������, �������� �� �� ��� ���� �������� 
���������� ��������� 
%%426
����������. ��������~$u_{k-1}$ �� ����~K4 ��������, ��� �� ������,
�������� �������� ��� ���������� ������ ���������.

璎�� ��������� ������������ ����� ���������, �������, ��� ����~K1 �~K3 
������ ������������ �������~$u$ �~$d$ � ������������ � ������� 
����������, ���� ������� ����� � ����� ������������ �� ������� �����~$k$. 
⅏��� ����� �������� ��
\picture{���.~88. ����������� ������ ����������������� ����� ��� ������ 
  ���������� ���������� �����. (������ ������� ����������� ������� �����, 
  �� ������� �� ������������.)
}
��������, ��� � ������ ������� ���� ����� ����� ��������� ��������:
$$
\displaylinesno{
u_l=d_{l+1}  \rem{��� $k\le l < n$;} & (6) \cr
u_l=d_{l+1}-b \rem{��� $1\le l < k$;} & (7) \cr
\hbox{���� } u_l=0 \hbox{ � } k\le l < n, \hbox{ �� } u_{l+1}=0. & (8) \cr
}
$$
����� ����, � ������ ����~K1 � ����� ��� �� �����~$k$ ��������� 
$\min(u_k, b)$~������� � ���������� ������������ ����� ���� ����� �� 
������~$\le k$ � ������������~$>k$. � ������ ����~K3 � ����� ��� �� 
�����~$k$ ��������� $\min(d_k, b)$~������� � ���������� ������������ 
����� ���� ����� �� ������~$\ge k$ � ������������~$<k$. 품 ������� 
����� ����� ��������� ����������, ���� ����������, ��� �� �������� � 
����~K1 ���~K3 (��.~���.~5).

�� ���� ������� �������, ��� ��������� � ������� �� �����~K1 �~K3 
�����������. ������ ���������� ����~K1, �������������, 
���������~$\ceil{u_k/b}$ ��~1 � ���������~$\ceil{d_{k+1}/b}$ ��� ���������.
������ ���������� ����~K3 ���������~$\ceil{d_k/b}$ ��~$1$ �
%% 427
��������� ����������~$\ceil{u_{k-1}/b}$. ��������, �������������, ������ 
����������� �� �������� ����� �����, � ����� ����� � ����~(6) �~(8) ������ 
������� ������ ��������� �� ����� �����.
\proofend

����~$u_k=0$, a~$u_{k+1}>0$, �� ����� "���������" ��������;
���� ������ ��������� �� �����~$k+1$, ����� ����������� ����� �����, ���� 
������ �� ����� ���������� � ������~$\le k$ �� �����~$\ge k+1$. He 
���������� ���������, ����� �������~$u_{n-1}>0$; ����� ����� ���������� 
������ ������ �������� �� ������� ����
$$
2 \sum_{1\le k < n} \max (1, \ceil{u_k/b})
\eqno (9)
$$
��������, ��� ��� �� �������, ����� ���� �������� �� ������ ����. ������, 
��� �������� ����������� ��� ������ �������, ����� ��������� (���.~4).

\excercises
\ex[17] � ������ �������� $P\hbox{-��}$~�������, ������������� � ������, 
������������ ������ ������ ������ � ���������. ����� �� �������������� 
�������� ���, ����� ������� ������������ �� \emph{���������} ������?

\ex[�26] ������� ����� ��������� � ��������� ���� ��� �����~$X_n$, $Y_n$,
 ������������ �~(3). [\emph{㊀�����:} ������� ������� ���������~(5.2.2-19).]

\ex[38] ᓙ������� �� ����� ���������� � ����� �������, ���������� ������ 
�� ��������� ������ (� �� �� ��������� ����), ��� �������� � ��������� 
������ ��� ���������� $N$~������� ����������� ���� ����������~$O(N\log N)$?  
[��� ������� ���������� ��� �������� ����������� � �������, �� �� � 
��������� ������, � � ������ 免�� �~ᒈ���� (���.~86) ��� 
���������~$O(N(\log N)^2)$.]

\ex[�23] � ������ � ����� �����������, ��� ������� �������~$p$, $q$, 
������~$q\ge p+2$, $u_p>0$, $u_q>0$ �~$u_{p+1}=\cdots=u_{q-1}=0$. 
���������, ��� ��������� ������, ��������� �� ����� (9)~������ �������.

\rex[�23] ����� �� ��������� �����������? ����� ����~K1 
��������� �������~� ����� � ����� �� ��������� ������� �� ����� ������ 
����, ��� ����� �� ���������� �� ������~$<k$.

\ex[�30] (�.~�.~����.) �������� ������ � ����� (���.~87) �� ������, 
����� �� �����~$j$ ������������� ��������� $c_j$~���������� � ����~$j$ 
������ ����������� ��� $c'_j$~���������� ���~$1\le j \le n$. ��������, 
��� ���������� ������ ������, ������������ �� 
$2\sum_{1\le k < n} \max (1, \ceil{u_k/b}, \ceil{d_{k+1}/b})$~������ 
�������, ������ �� �����~$j$ 
������� �� ����������� ������������ ����� $\max (c_j, c'_j)$~����������. 
[\emph{㊀�����:} �������, ���� ����������, ��������� �����, 
����� �������~$c_j=c'_j$ ��� ����~$j$.]

\ex[�40] (�.~�.~����.) �������� ������ �� ���.~6, ������� �������� ����, 
���������� ������, �� ���� �����, �� ������� ����� ������ �� ��������, 
��� �������, ��� ���� �������� ����� \emph{��������� ������.} ������� 
����� �������� �������, � ���������� ��������� ���������� � �� ������ 
���������� ���, ����� ������� ������ ����������� ����������. 

\ex[�32] ����� � ������ � �����, ����������� � ������, $c=1$. 
኎���� ������������ �� $n$~������� �� $n$~������ ����� �~(4) $u_k \le 1$ 
���~$1 \le k \le n$? [��������, $3\,1\,4\,5\,9\,2\,6\,8\,7$---����� ������������.]

\rex[�25] ������� ������ ����� ����� ������-�����������, ��������� � 
�.~5.2.2 (���.~16), � �������~$u_1$, $u_2$,~\dots, $u_n$ �~(4) � ������~$c=1$.

\ex[20] ��� �� �� ����������� ����� �� ���������� �������, ���� ������ ��� 
�������������� ����������?

%% 428
\bye