\input style
{ \catcode`\[=\active\def[{\hbox to 0pt{\hss$\lbrack$}}
 \catcode`\]=\active\def]{\hbox to 0pt{$\rbrack$\hss}}
\htable{򀁋��� 2}{"ᛑ���� ����������"}{
$\phantom{[}#\phantom{]}$\bskip&&$\phantom{[}#\phantom{]}$\bskip\cr
    &     &     &    &     &     &    &    &    &     &     &     &    &     &     &     & (l, r) & \hbox{񒅊}\cr
\noalign{\hrule}
[503& 087 & 512 & 061& 908 & 170 & 897& 275& 653& 426 & 154 & 509 & 612& 677 & 765 & 703]& (1,16) & - \cr
[154& 087 & 426 & 061& 275 & 170]& 503&[897& 653& 908 & 512 & 509 & 612& 677 & 765 & 703]& (1,6)  & (8,16)\cr
[061& 087]& 154 &[426& 275 & 170]& 503&[897& 653& 908 & 512 & 509 & 612& 677 & 765 & 703]& (1,2)  & (4,6)(8,16)\cr
 061& 087 & 154 &[426& 275 & 170]& 503&[897& 653& 908 & 512 & 509 & 612& 677 & 765 & 703]& (4,6)  & (8,16)\cr
 061& 087 & 154 &[170& 275]& 426 & 503&[897& 653& 908 & 512 & 509 & 612& 677 & 765 & 703]& (4,5)  & (8, 16)\cr
 061& 087 & 154 & 170& 275 & 426 & 503&[897& 653& 908 & 512 & 509 & 612& 677 & 765 & 703]& (8,16) & - \cr
 061& 087 & 154 & 170& 275 & 426 & 503&[703& 653& 765 & 512 & 509 & 612& 677]& 897 & 908 & (8,14) & - \cr
 061& 087 & 154 & 170& 275 & 426 & 503&[677& 653& 612 & 512 & 509]& 703& 765 & 897 & 908 & (8,12) & - \cr
 061& 087 & 154 & 170& 275 & 426 & 503&[509& 653& 612 & 512]& 677 & 703& 765 & 897 & 908 & (8,11) & - \cr
 061& 087 & 154 & 170& 275 & 426 & 503& 509&[653& 612 & 512]& 677 & 703& 765 & 897 & 908 & (9,11) & - \cr
 061& 087 & 154 & 170& 275 & 426 & 503& 509&[512& 612]& 653 & 677 & 703& 765 & 897 & 908 & (9,10) & - \cr
 061& 087 & 154 & 170& 275 & 426 & 503& 509& 512& 612 & 653 & 677 & 703& 765 & 897 & 908 &    -   & - \cr
\noalign{\hrule}
}}
򎋜�� ��� ��������� ��������� ���������� ����� ������� ��������  
�����������  \emph{�  �����������;} ���  ����������� �.~�.~�.~�����, 
������������� ������ �������� 
[{\sl Comp. J.,\/} {\bf 5} (1962), 10--15]---���� �� �������� ������������� 
�� �����-���� �������������� ��������� �� ���� ������. ���� �������� 
���� ����� "quicksort" ("������� ����������"), � ��� �������� 
������ ������������� ����������������, ��� ���, ��������, ���� ������� 
����������, ���������� � ����.~2, ������� ����� 48~��������� (������ 
������ ������� �������������� ��� ������, �� ����������� �������� �������, 
��������� 47~���������).
\picture{��� ~19.  ����� ���������� � ����������� ("������� ����������").}
� ���� ���������� �� ������ ������ ��������� ���� � ��� �� ����, ��� ��� 
��� ����� ������� � ��������. ꐎ�� ����, ���������� ����������� ������ 
������ ��������: ��� ����������� ����.~2 ����������� ����� $17$~�������, 
������ ����������� �� ���---������ "����������" (������� ���������), ��� ��� ����
%% 143
�� ������ ��� ����� �������� � ��������, � ��� �� ����� ���������� �� 
������ ����� ������.

⑏������������ �������� (��������� ��� ���������� ������ � 
�����������~$i$, $j$) �� ������, �� ��-�� ��� ��������� ������� ���������� 
����������� ���������� �������� � �������� ��� ������� ��������~$N$; 
������� �������� �������� ���������� ����������� ������ �������, ��� ��� 
�������� � ��������� ���������.

\alg Q.(����� ���������� � �����������.) 瀏���~$R_1$,~\dots, $R_N$ 
��������������� �� ��� �� �����; ����� ���������� ���������� �� ����� 
����� �����������: $K_1\le\ldots\le K_N$. 퓆�� ��������������� ���� ��� 
�������� �� ����� ��� $\log_2 N$~���������. ���� �������� ������������� 
��������� "������� ����������" ����������� ����������, ����������� ����, � 
���������� ����������� � ����� ��������� �������������:
{\medskip\narrower
\item{a)}~����������� ������� ������������� ������~$K_0=-\infty$ 
�~$K_{N+1}=+\infty$, �����, ���
$$
K_0\le K_i \le K_{N+1} \rem{���~$1\le i \le N$.}
\eqno (13)
$$
(��������� �����������.)

\item{b)}~�����, ��������� ��~$M$ � ����� ���������, ����������� 
�������� ���������, ���~$M\ge 1$---��������, ������� ����������, ��� ������� ����.

\item{c)}~� ��������� ������� �������� ���� ��� ��� �������������� 
��������� (����������� ���������� ����������~$i$, $j$), ����� �������� 
����� ��������� ����������� ��������� ������, ��������� ��� ��������.

\item{d)}~瀏��� � ����������� ������� �������� �������, ���� ��� �� 
�������� ������ �����������. (��� ����, ������������� �.~�.~񈍃�����, 
������������ ���������� ��������� ����� �������, ���� ������� ������ 
�����; ��.~���.~18.)
\medskip}

\st[퀗������ ���������.] ������� ���� � ����������~$l\asg1$; $r\asg N$.

\st[퀗��� ����� ������.] (퀌 �������� �� ������������� ����~$R_l$,~\dots,
$R_r$; �� ������ �������� ��������� ��������, ���~$r\ge l-1$, 
$K_{l-1}\le K_i \le K_{r+1}$ ���~$l\le i \le r$.) 呋�~$r-l<M$, �� ������� � 
����~\stp{8}. � ��������� ������ ����������~$i\asg l$, $j\asg r$, $K\asg K_l$, 
$R\asg R_l$. (������� ���������� ������~$R$ �~$K$ ��������� ����.)

\st[񐀂����~$K:K_j$.] 呋�~$K<K_j$, �� ���������~$j$ ��~$1$ � ��������� 
���� ���.

\st[������~$R$ �� �����~$R_i$.] (� ����� ������� $K_i$---����~$\ge K$, 
����������� �� �� ����� �����, �~$K\ge K_j$.) 呋�~$j\le i$, �� 
����������~$R_i\asg R$ � ������� � ����~Q7. � ��������� ������ 
����������~$R_i\asg R_j$ � ���������~$i$ ��~1.
%%144
\st[񐀂����~$K_i:K$.] 呋�~$K_i<K$, �� ���������~$i$ ��~$1$ � ��������� 
���� ���.

\st[������~$R$ �� �����~$R_j$.] (� ����� ������� $K_j$---����~$\le K$, 
����������� �� �� ����� �����, �~$K\le K_i$.) 呋�~$j\le i$, �� 
����������~$R_j\asg R$ �~$i\asg j$. � ��������� ������ 
����������~$R_j\asg R_i$,  ���������~$j$ ��~$1$ � ������� � ����~\stp{3}.

\st[������ � ����.] (򅏅�� �������~$R_l\ldots{}R_i\ldots{}R_r$ 
�������� ���, ���~$K_k\le K_i$ ���~$l\le k \le i$ �~$K_i\le K_k$ 
���~$i\le k \le r$ .) 呋�~$r-i\ge i-l$, �� ��������� � ����~$(i+1, r)$ � 
����������~$r\asg i-1$. � ��������� ������ ��������� � ����~$(l, i-1)$ 
� ����������~$l\asg i+1$. (ꀆ��� ������� �����~$(a, b)$---��� ������ �� 
���������� ��������~$R_a\ldots{}R_b$ � ����� �� ����������� ������.) 
⅐������ � ����~\stp{2}.

\st[񎐒������ �������� ���������.] 䋟~$j=l+1$, $l+2$,~\dots{} ��~$j>r$ 
��������� ��������� ��������: ����������~$K\asg K_j$, $R\asg R_j$, $i\asg j-1$; 
����� ����������~$R_{i+1}\asg R_i$, $i\asg i-1$ ���� ��� ����� ��� 
�� ��� ���, ���� �� ���������� �������~$K_i\le K$; ����� 
����������~$R_{i+1}\asg R$. (���, �� ��������, ��������~5.2.1S, 
����������� � �������� ��~$M$ ��� ����� ���������.)

\st[⇟�� �� �����.] 呋� ���� ����, �� ���������� ���������;
� ��������� ������ ����� ������� ������� �����~$(l', r')$,
����������~$l\asg l'$, $r\asg r'$ � ������������ � ����~\stp{2}.
\algend

񎎒����������� \MIX-��������� �������� ������, �� �� ������; �� ����� 
���� ������� ����� ������ ��������� � �ary~Q7, � ������� ���������� ������ 
������� ����������� � �����������.

\prog Q.(����� ���������� � �����������.) 瀏���, ������� ��������� 
�������������, ��������� � ������� $|INPUT|+1$,~\dots, $|INPUT|+N$; 
��������������, ��� � �������~|INPUT| �~$|INPUT|+N+1$ ���������� ��������, 
�������������� ����������, � ����������� ���������� � ������~\MIX. 
񒅊 ������������� � ������� $|STACK|+1$, $|STACK|+2$,~\dots; ������ ����� 
�����, ������� ���������� ������� ��� ����, ����������� � ���.~20. 
獀����� ���������: $|rI1|\equiv l$, $|rI2|\equiv r$, $|rI3|\equiv i$, 
$|rI4|\equiv j$, $|rI6|\equiv \hbox{������ �����}$, $|rA|\equiv K \equiv R$.
\code
A    & EQU  & 2:3       &      & ��� ���������� �������� �����.
�    & EQU  & 4:5       &      & ⒎��� ���������� �������� �����.
START& ENT1 & 1         & 1    & Q1. 퀗������ ���������. $l\asg1$.
     & ENT2 & N         & 1    & $r\asg N$.
     & ENT6 & 0         & 1    & ������� ����.
2H   & ENTX & 0,2       & 2A+1 & Q2. 퀗��� ����� ������.
     & DECX & M,1       & 2A+1 & $|rX|\asg r-l-M$.
%%145
     & JXN  & 8F        & 2A+1 & � ����~Q8, ���� ������ ��������~$\le M$.
     & ENT3 & 0,1       & A    & $i\asg l$.
     & ENT4 & 0,2       & A    & $j\asg r$.
     & LDA  & INPUT,3   & A    & $K\asg K_i$.
     & JMP  & 3F        & A    & � ����~Q3.
0H   & LDX  & INPUT,3   & B
     & STX  & INPUT,4   & B    & $R_j\asg R_i$.
     & DEC4 & 1         & C'-A & $j\asg j-1$.
3H   & CMPA & INPUT,4   & C'   & Q3.~񐀂����~$K:K_j$.
     & JL   & *-2       & C'   & 呋�~$<$, �� ���������~$j$ � ���������.
4H   & ENTX & 0,3       & B+A  & Q4.~������~$R$ �� �����~$R_i$.
     & DECX & 0,4       & B+A
     & JXNN & 7F        & B+A  & � ����~Q7, ����~$i\ge j$.
     & LDX  & INPUT,4   & B+X
     & STX  & INPUT,3   & B+X  & $R_i\asg R_j$.
     & INC3 & 1         & C''  & $i\asg i+1$.
5H   & ���� & INPUT,3   & C''  & Q5.~񐀂����~$K_i:K$.
     & JG   & *-2       & C''  & 呋�~$<$, �� ���������~$i$ � ���������.
6H   & ENTX & 0,3       & B+X  & Q6.~������~$R$ �� �����~$R_i$.
     & DECX & 0,4       & B+X 
     & JXN  & 0B        & B+X  & � ����~Q3, ����~$i<j$.
     & ENT3 & 0,4       & X    & $i\asg j$.
7H   & STA  & INPUT,3   & A    & Q7. ������ � ����. $R_i\asg R$.
     & ENTA & 0,2       & A
     & DECA & 0,3       & A
     & DECA & 0,3       & A
     & INCA & 0,1       & A
     & INC6 & 1         & A    & $|rI6|\asg |rI6|+1$.
     & JANN & 1F        & A    & ����, ����~$r-i\ge i-l$.
     & ST1  & STACK,6(A)& A'
     & DEC3 & 1         & A'
     & ST3  & STACK,6(B)& A'   & $(l, i-1)\Rasg \hbox{����}$.
     & ENT1 & 2,3       & A'   & $l\asg i+1$.
     & JMP  & 2B        & A'   & � ����~Q2.
1H   & INC3 & 1         & A-A'
     & ST3  & STACK,6(A)& A-A'
     & ST2  & STACK,6(B)& A-A' & $(i+1, r)\Rasg\hbox{����}$.
     & ENT2 & -2,3      & A-A' & $r\asg i-1$.
     & JMP  & 2B        & A-A' & � ����~Q2.
8H   & DEC2 & 0,1       & A+1  & Q8. 񎐒������ �������� ���������.
     & J2NP & 9F        & A+1  & � ����~Q9, ����~$r\le l$.
     & ENT4 & 1,1       & A+1-L& $j\asg l+1$.
1H   & LDA  & INPUT,4   & D    & $R\asg R_j$.
     & ENT3 & -1,4      & D    & $i\asg j-1$.
     & JMP  & *+4       & D    & ���� � ����.
     & LDX  & INPUT,3   & E
     & STX  & INPUT+1,3 & E    & $R_{i+1}\asg R_i$.
     & DEC3 & 1         & E    & $i\asg i-1$.
     & ���� & INPUT,3   & D+E
     & JL   & *-4       & D+E  & ����, ����~$K<K_i$.
     & STA  & INPUT+1,3 & D    & $R_{i+1}\asg R$.
%% 146
     & INC4 & 1         & D    & $j\asg j+1$.
     & DEC2 & 1         & D
     & J2P  & 1B        & D    & ������ $r-l$~���.
9H   & LD1  & STACK,6(A)& A+1  & Q9. ⇟�� �� �����.
     & LD2  & STACK,6(B)& A+1  & $(l, r)\Asg\hbox{����}$.
     & DEC6 & 1         & A+1  & $|rI6|\asg|rI6|-1$.
     & J6NN & 2B        & A+1  & � ����~Q2, ���� ���� �� ��� ����.
\endcode
\progend
\section ������ "������� ����������". 荔������� � ������� ����������, 
����������� ������ � ����������~Q, �������� ������� �� ������ ꈐ�����, 
��� ������ ���������� (��.~�.~1.3.3), � �� ���� �����, ��� ��� ���������� 
� ���� � ����� ������ ������ �����������. �� ����� ������ ������� �� 
��������� �������:
$$
\eqalign{
  A&=\hbox{����� ������, �� ������� ������ ������� �������� ����� $M$~���������;}\cr
  B&=\hbox{����� ������������~$R_j\asg R_i$ � ����~Q6;}\cr
 C'&=\hbox{����� ���������� ����~Q3;}\cr
C''&=\hbox{����� ���������� ����~Q5;}\cr
  D&=\hbox{����� ������������~$R\asg R_j$ � ����~Q8;}\cr
  E&=\hbox{����� ������������~$R_{i+1}\asg R_i$ � ����~Q8;}\cr
  L&=\hbox{����� �������, ����� � ����~Q8 $r\le l$;}\cr
  X&=\hbox{����� ��������~$i\asg j$ � ���� Q6.}\cr
}
\eqno(14)
$$
� �� ����� ������������� ��������~$C'$ �~$C''$ ����������, � ���������� ����
$$
C=C'+C''=\hbox{����� ����� ���������},
\eqno(15)
$$
��� ��� ����� ������ ���~$C'$ �~$C''$ ���������. 臓��� ���� �������: 
$A$, $B$, $C$, $D$, $E$, $L$ �~$X$, �� ������ ������� ������� ��������~$M$,
������� ������������ "�����" ����� ����������� �������� ��������� � 
�����������. (呋� �������� �� ���������, �� ����� ���������� ��� ������ 
�� ������~(25).)

ꀊ � ��� ������� ����������� ������ ���������� � ���� �����, �� ����� 
������������, ��� ����������� ����� ��������;. � ���.~18 ��������, ��� 
������� ������ ������ �� ������� ����������� ������������� ���������~Q; 
� ���������������� ����������� ������ ������, ��-��������, ���� 
������������ �� ����������. � ��� ����� ������� ������ �� 
�������������� ������������ ������, �� ����� ������������ �����, ��� 
��� ������ �����~$\set{1, 2,~\ldots, N}$, ������������� � ��������� �������.

ꎃ�� �� ������� ��������� ����~Q2, ���������� �������� � ������� ��������,
����~$N\le M$, � ��� �� ��� �������; ������� �����������, ���~$N>M$. 
텎������� ���� ����������� � �����������, ������� � ������ ��� �������� � ����~Q7;
%% 147
�������� ������, ��� ��� ���������� ������ � ����� 
��������� $R_1\ldots{}R_{i-1}$ �~$R_{i+1}\ldots{}R_N$ ����� ����������� � 
��������� �������, ���� ������ ������ ��������� ����� ���� ����������� � 
��������� �������. 獀���, ����� ����������� ���������� ����� ����������, 
�������� �������� ��~$N$.

��~$s$---�������� ������� �����~$K_1$, � �����������, ��� �����~$t$ �� 
������~$K_1$,~\dots, $K_s$ �����������~$s$. ��
$$
h=\cases{
1, & ����~$K_s<s$; \cr
0, & ����~$K_s\ge s$.
}
\eqno(16)
$$
荀�� ������, $h=1$, ���� ����, ������� ������� ������� �������~$s$ 
(���� ������� ����~$K_1$), ����� ��������� �����. 퀏�����, ��� 
����������� ����� �������� ������ ������� �� ���������~$\set{1, 2,~\ldots, N}$.

呋�~$s=1$, �� �������� ������, ��� ���������� �� ����� ������ ������ 
����������. ���~Q3 ���������� $N$~���, ����� ���� ���~Q4 �������� ��� �~Q7.
򀊈� �������, ������ ������ � ���� ������ ���� ����� ������: $A=1$, 
$B=0$, $C=N$, $X=0$. �����������, �� ��������� ����� ������� ����������� 
��� ������~$s>1$ (��.~���.~21) ����������, ��� �������� ������ ������ � 
��������� ����� ���������� � ����� ������ �����
$$
A=1,\quad B=t, \quad C=N+1-\delta_{s1},\quad X=h \rem{���~$1<s\le N$.}
\eqno(17)
$$
� ����� ���������� �������� ������ ����������� ������, �� ����� ������� 
��������������� �������� �������������� ��~$s-1$ �~$N-S$~���������.

呋� ������������, ��� � �������� ����� ������ ������������� � ��������� 
�������, �� ����� �������� �������, �������� ������������ ������������ 
������� ��� ������������� ������������ �������~$A$, $B$,~\dots, $X$ 
(��.~���.~22). � ��� �������� �� ������ ����� ������ \emph{������� 
��������} ���� �������~$A_N$, $B_N$,~\dots, $X_N$ ��� ������� ��~$N$. 
����������, ��������, ������� ����� ���������~$C_N$, ����������� � 
�������� ����������. 呋�~$N\le M$, ��~$C_N=0$. ~$N>M$, ��� ��� ����� 
������ ��������~$s$ ����������� � ������������~$1/N$,
$$
\eqalignno{
C_N&={1\over N}\sum_{1\le s \le N} (N+1-\delta_{s1}+C_{s-1}+C_{N-s})=\cr
   &=N+1-{1\over N}+{2\over N}\sum_{0\le k < N} C_k. & (18) \cr
}
$$
����������� ������� ����� ����� � ��� ��������� �������~$A_N$, $B_N$,~\dots, 
$X_N$ (��.~���.~23).
%% 148

񓙅������ ������� ������ ������� ������������ ����������� ����
$$
x_n=f_n+{2\over n}\sum_{0\le k < n} x_k \rem{��� $n\ge m$.}
\eqno(19)
$$
� ������ ���� ������������� �� ����� ������������: ���������
$$
\eqalign{
(n+1)x_{n+1}&=(n+1)f_{n+1}+2\sum_{0\le k \le n} x_k, \cr
      n x_n &=nf_n+2\sum_{0\le k<n} x_k,\cr
}
$$
�� ����� ������� ������ ��������� �� �������, �������
$$
(n+1)x_{n+1}-nx_n=g_n+2x_n, \rem{��� $g_n=(n+1)f_{n+1}-nf_n$.}
$$
򅏅�� ������������ ����������� ��������� ������� ����� ������� ���:
$$
(n+1)x_{n+1}=(n+2)x_n+g_n \rem{��� $n\ge m$.}
\eqno(20)
$$
\emph{랁��} ������������ ����������� ������ ����
$$
a_n x_{n+1}=b_n x_n + g_n
\eqno(21)
$$
����� ������ � ������� �����, ���� �������� ��� ����� �� ����������� 
���������~$a_0a_1\ldots{}a_{n-1}/b_0b_1\ldots{}b_n$. �����
$$
y_{n+1}=y_n+c_n, 
\rem{��� $\displaystyle y_n={a_0\ldots a_{n-1}\over b_0\ldots b_{n-1}}x_n$,
$\displaystyle c_n={a_0\ldots a_{n-1}\over b_0\ldots b_n}g_n$.}
\eqno(22)
$$
� ������~(20) ����������� ��������� ����� ������~$n!/(n+2)!=1/(n+1)(n+2)$. 
򀊈� �������, �������, ��� ������� �����������
$$
{x_{n+1}\over n+2}={x_n \over n+1}+{(n+1)f_{n+1}-nf_n \over (n+1)(n+2)},
\rem{$n\ge m$,}
\eqno(23)
$$
�������� ���������� �����������~(19).

呋�, ��������, ��������~$f_n=1/n$, �� ��������� ����������� 
���������~$x_n/(n+1)=x_m/(m+1)$ ��� �����~$n\ge m$. 
呋� ��������~$f_n=n+1$, �� ���������
$$
\eqalign{
x_n/(n+1)&=2/(n+1)+2/n+\cdots+2/(m+2)+x_m/(m+1)=\cr
         &=2(H_{n+1}-H_{m+1})+x_m/(m+1)\cr
}
$$
��� �����~$n\ge m$. ꎌ������� ���� ���� ������� � �����������~$m=M+1$ 
�~$x_n=0$ ���~$n\le M$ ���� �������
$$
\eqalignno{
C_N&=(N+1)\left(2H_{N+1}-2H_{M+2}+1-{1\over (M+1)(M+2)}\right)\approx\cr
&\approx 2(N+1)\ln \left({N+1\over M+2}\right) \rem{���~$N>M$.} &(24)\cr
}
$$
%% 149
� �.~6.2.2 �� �������, ��� ����������� ���������� 
��������~$C_N$ �������������� �����~$\sqrt{(21-2\pi^2)}/3N$; ��� �������� 
���� �� ��������� �~(24).

������ �������� ����� ����� ����������� �������� (��.~���.~23); �����
$$
\eqalign{
A_N&=2(N+1)/(M+2)-1,\cr
B_N&={1\over 6}(N+1)\left(2H_{N+1}-2H_{M+2}+1-{6\over M+2}\right)+{1\over2},\cr
D_N&=(N+1)M(M-1)/(M+2)(M+1),\cr
E_N&={1\over6}(N+1)M(M-1)/(M+2),\cr
L_N&=4(N+1)/(M+2)(M+1),\cr
X_N&=(N+1)/(M+2)-{1\over2} \rem{��� $N>M$.}\cr
}
\eqno(25)
$$

�������� ���� ���������� ����������, ��� ����� ���������� ������ 
������ �������� ������� ���������� ������ ������� ���������, ��������� 
������, ������� �� ����� ��������� ���� � ����� ������� �������.

����� ���������� "���������" ��������~$M$ ��� ���������� ������, ����� 
��������������� ���������~(24) �~(25). ������~Q ��� ������~\MIX{} 
������� $37A+14B+4C+12D+8E-L+8X+15$~������ �������; ��� ����� � �������
${1\over3}(38(N+1)H_N+(N+1)f(M))-19$~������ ���~$N>M$, ���
$$
f(M)=4M+38H_{M+2}+43+{84\over M+2}+{48\over (M+2)(M+1)}.
\eqno(26)
$$
� ����� ������� ����� ��������~$M$, ��� ������� �������~$f(M)$ ��������� 
��������. � ������ ������
$$
f(M)-f(M-1)=4-{38\over M+2}-{84\over (M+2)(M+1)}-{96 \over(M+2)(M+1)M},
$$
� ��������� ����� ����� ��������~$M$, �����~$f(M)-f(M-1)\le 0$,
$f(M+1)-f(M)\ge 0$; �������~$M=9$ ����� ��������. 呋�~$M=9$, �� ��� 
�������~$N$ ������� ����� ���������� ���������~Q ����� 
��������������~$12.67(N+1)\ln N-1.92N-14.59$.

򀊈� �������, ���������~Q �������� � ������� �������� ������; �������, 
����� ����, ������, ��� ��� ������� ����� ���� ������. � ����� 
\emph{���������} ������ ��� ���������~Q? 񓙅������ �� �����-������ 
�������� �����, ������������ ������� ���� ���������� �� ����������? �� 
��������� ��������������: ���� �������� ���� ��� ����������, � 
������~$K_1<K_2<\ldots<K_N$, �� ������ �������� "����������" ���������� 
����� �����������, ��� ��� ������� �������� � ������ ��������! 獀���, � 
���� �������� (������� ������ ���� ����� �������
%% 150
\bye