\input style
������� �������� �������������� ���������� � ����������� ������.) 
�������������� ������������ �����, ��-��������, �������������� ��������� 
�������, ���� ������� ��� ��� ���� �����, ��� � ������ ������� � ������. � 
���� �� �������� ������������� �������� ��������� ������� ��� ����� � ������;
��� �������� ����� ��������� � ����� � ��� �� ������� ������.

�������� ����---��� �������� ����� ������� � ������, ����� ����������� �� 
����� �������, � \emph{�����������.} ������ ������ �������� ����� �� 
������������� ���������. �� ������ ������ ������������� � ���, ��� ����� 
������������ �������� ���������� � �� "������������" ���������� � 
�����-�� ����������. ��������� ���� ��������� �������� ������ ����������� 
�� $M$~�������� � ��������������, ��� ������ ���� �������� � ������ 
������� � ������������~$1/M$. ������� �������������� ������ ��� ������ 
$M$~�������, � ������ ������ ������, ��� ��� ������� �������� � ������.

��� ������������� ��������� ����� ���� �������� �� ����� �������������. 
���������� ������� ���������� ��� ������ ������� �������~$\NULL$, � ��� 
������� ����� ������������ �������� �������������� ������, � ����� �� 
$M$~�������� �� ��������, ����� ���� �������� ��� � ��������������� ������,
��� � ���������~L.

璎�� ����������������� ���� ����� � ��������, �����������, ��� ���� 
16~������ ��������� �� $M=4$~��������� $0$--$249$, $250$--$499$, 
$500$--$749$, $750$--$999$. � �������� ���������� ���������� ��������� 
������������:
\ctable{
#\hfil\bskip&&\bskip#\hfil\bskip\cr
Ꮘ��� & ������~4     & ������~8            & ������~12                  & �������� \cr
       & ��������     & ���������           & ���������                  & ���������\cr
1:     & $061$, $087$ & $061$, $087$, $170$ & $061$, $087$, $154$, $170$ & $061$, $087$, $154$, $170$\cr
2:     &              & $275$               & $275$, $426$               & $275$, $426$ \cr
3:     & $503$, $512$ & $503$, $512$        & $503$, $509$, $512$, $653$ & $503$, $509$, $512$, $612$\cr
       &              &                     &                            & $653$, $677$, $703$ \cr
4:     &              & $897$, $908$        & $897$, $908$               & $765$, $897$, $908$\cr
}
��������� ���������� ��������� ������ �� ��������� �������� ������������� 
������ ��� ������������� ������� ���������� �����.

\prog M.(������� � ��������� �������.) � ���� ��������� �������� �� �� 
�������������, ��� � � ���������~L, �� ����� ������ ���� 
\emph{����������������;} ��� ���
$$
0\le|KEY|<(|BYTESIZE|)^3.
$$
풎� �������� ������� � ��������� �� |M|~������ ������ ����� ��������� 
������� ����� �� ���������� ���������. ������ ������� �������� � 
�������~$|HEAD|+1$,~\dots, $|HEAD|+|M|$.
%%125
\code
KEY   & EQU  & 1:3
LINK  & EQU  & 4:5
START & ENT2 & �            & 1
      & STZ  & HEAD,2       & M     & $|HEAD|[p]\asg\NULL$.
      & DEC2 & 1            & M
      & J2P  & *-2          & M     & $M\ge p \ge 1$.
      & ENT1 & N            & 1     & $j\asg N$.
2H    & LDA  & INPUT.l(KEY) & N
      & MUL  & =M(1:3)=     & N     & $|rA|\asg\floor{M\times K_j/|BYTESIZE|^3}$. 
      & STA  & *+1(1:2)     & N
      & ENT3 & 0            & N     & $q\asg |rA|$.
      & INC3 & HEAD+1-INPUT & N     & $q\asg |LOC|(|HEAD|[q])$.
      & LDA  & INPUT, 1     & N     & $K\asg K_j$.
      & JMP  & 4F           & N     & 㑒�������~$p$.
3H    & CMPA & INPUT,2(KEY) & B+N-A 
      & JLE  & 5F           & B+N-A & ��������, ����~$K\le K_p$.
      & ENT3 & 0,2          & B     & $q\asg p$.
4H    & LD2  & INPUT,3(LINK)& B+N   & $p\asg |LINK|(q)$.
      & J2P  & 3B           & B+N   & �������, ���� �� ����� ������.
5�    & ST1  & INPUT,3(LINK)& N     & $|LINK|(q)\asg|LOC|(R_j)$.
      & ST2  & INPUT,1(LINK)& N     & $|LINK|(|LOC|(R_j))\asg p$.
6H    & DEC1 & 1            & N
      & J1P  & 2B           & N     & $N\ge j \ge 1$.
\endcode
\algend

풀 ��������� �������� ��� ������������� ��������~$M$, �� ����� 
�������������~$M$, ������� ��� ������ ���������� �������� ��������; 
�����, ��������, ��������~$M=|BYTESIZE|$, ����� ������ ������� ����� 
���������� �����-������������ ��������~|MOVE|, � ������������������ 
������~08--11, ����������� ���������, �������� ��������~|LD3 INPUT,1(1:1)|. 
�������� �������� ������� ���������~M �� ���������~L ������� � 
���, ��� � ���������~M ����� ������������� ������ ������� ������, ����� �� 
���� ������ ���������.

኎���� �� ������� �� ��������, ���� $M$~������� ������ ������? ����� 
����� ������ ���������~M ����� $7B+31N-3A+4M+2$~������, ���~$M$---����� 
�������, $N$---����� ����������� �������, $A$ �~$B$ ����� �������������� 
����� �������������� ���������� � ����� �������� ����� ������, 
������������� ������� ������. (��� ������� ����� ��������� � ������� �� 
���� ������ �������� � ������ ������ �� ������� ������� ������ ������� 
�������� ������������ �������������� ����������, � �� ���������� ���.) �� 
��� ������� ��������~$A$ �~$B$ ���~$M=1$, ����� �� ������� �������� ����� 
��������������~$H_N$ �~${1\over2}\perm{N}{2}$. ᎃ����� ������������� � 
������������� ������, ����������� ����, ��� ������ ������ � ����� 
���������� ����� ��������� ����� $n$~���������, ���� "������������" �����������
$$
\perm{N}{n}\left({1\over M}\right)^n\left(1-{1\over M}\right)^{N-n}.
\eqno(10)
$$
%%126
������� ������� �������� �������~$A$ �~$B$ � ����� ������� �����
$$
\eqalignno{
A_{ave}&= M\sum_n\perm{N}{n}\left({1\over M}\right)^n
\left(1-{1\over M}\right)^{N-n}H_n; & (11) \cr
B_{ave}&= M\sum_n\perm{N}{n}\left({1\over M}\right)^n
\left(1-{1\over M}\right)^{N-n}\perm{n}{2}. & (12) \cr
}
$$
�� �������~1.2.7A
$$
\sum_n\perm{N}{n}(M-1)^{-n}H_n=\left(1-{1\over M}\right)^{-N}(H_N-\ln M)+\varepsilon,
\qquad 
0<\varepsilon=\sum_{n>N}{1\over n}\left(1-{1\over M}\right)^{n-N}<{M-1\over N+1};
$$
�������������,
$$
A_{ave}=M(H_N-\ln M)+\delta, 
\qquad 
0<\delta<{M^2\over N+1}\left(1-{1\over M}\right)^{N+1}.
\eqno(13)
$$
(풀 ������� ����������� ����������, ����~$M\approx N$. ����� �������� 
��������������� ��������� ��������~$A_{ave}$ ���~$M=N/\alpha$  ����������� 
� ���.~5.2.2-57.) ᓌ��~(12) ����� ��������� � ������� ���������
$$
\perm{N}{n}\perm{n}{2}=\perm{N}{2}\perm{N-2}{n-2},
$$
������� ������������ ����� ������� ������ ���������~(1.2.6-20); ��������
$$
B_{ave}={1\over 2M}\perm{N}{2}.
\eqno(14)
$$
(ᒀ�������� ���������� ��� ��������~$B$ ��.\ � ���.~37.) ዅ����������, 
����� ����� ������ ���������~M ��� �������������~$M$ �~$N\to\infty$ �����
$$
\eqalign{
\min\qquad& 31N+M+2,\cr
\ave\qquad& 1.75N^2/M+31N-3MH_N+3M\ln M+4M-3-1.75N/M+2,\cr 
\max\qquad& 3.50N^2+24.5N+4M+2.\cr
}
\eqno(15)
$$
�������, ��� ����~$M$ �� ������� ������, \emph{�� ������� ����� ������ 
����������� � $M$~���.} ���~$M=10$ ���������� ����� �������� � 10~��� 
�������, ��� ���~$M=1$! ������ ������������ ����� ������ ������� ������ 
��������.  �� �������, �������������� ������������� ���������� 
������������� � ������������� ������������� ������, ��� ��� ��������� 
������ ����� �����, ����� ��� ����� �������� � ���� ������.

%%127

���� ��������~$M=N$, �� ������� ����� ������ ����� ��������~$34.36N$, 
���~$M={1\over2}N$ ��� ��������� ������, ����� ��������������~$34.52N$, 
� ���~$M=N/10$ ��� ����� ��������������~$48.04N$. (�������, ���~$10N$ �� 
���� ������ ������� ������ \MIX{} �������� �� ���� ���� ������� 
���������!) \emph{�� �������� ����� ���������� � �������� ������ 
�������~$N$ ��� �������, ��� ����� �������� ���������� ������������ � 
������� ���������.}

\excercises
\ex[10] ����� �� ��������~S ���������� "����������" ����������?

\ex[11] ����� �� ��������~S ��������� ����������� �����, ���� � ����~S3 
���������~"$K\ge K_i$" �������� ��~"$K>K_i$"?

\rex[30] ����� �� ���������~S ����� �������� ���������� ���������� 
��� ������ \MIX, ��� ����� �������� ����� �������� ���������, ������� �� 
������ ��� �� ���������?

\rex[�20] ������� ����������� � ������������ ����� ������ ���������~S ��� 
������� ��~$N$.

\rex[�27] ������� ������������ �������~$g_N(z)=\sum_{k\ge0} p_{Nk} z^k$ 
��� ������ ������� ������ ���������~S, ���~$p_{Nk}$---����������� ����, ��� 
�� ���������� ���������~S ����� ����� $k$~������ ������� ��� �������� 
�������� ��������� ������������ ���������~$\set{1, 2,~\ldots, N}$. 
��������� ����� ����������� ���������� ������� ������ ��� ������� ��������~$N$.

\ex[33] ��� ����������� �������, ������������������� � ����.~2,
��-��������, ����������, ������ ������� �����, ���������� $N$~�������,
����� ������� ������, � ������� ����� ��������� $2N+1$~�������. ��������,
��� ����� ��������� ����������� �������, ���� ��� ��� �����, ��� � 
��� ������ ������������, ����������� ��� �������� ����� $N+1$~�������.

\ex[�20] �����~$a_1\,a_2\,\ldots\,a_n$---��������� ������������  
���������~$\set{1, 2,~\ldots, n}$; ������ ������� �������� 
��������~$\abs{a_1-1}+\abs{a_2-2}+\cdots+\abs{a_n-n}$? (��� ����� 
������������~$n$ �� ������� ������ ����������, �� ������� ������������ 
������ � �������� ����������.)

\ex[10] ����� �� ��������~D ���������� "����������" ����������?

\ex[20] ����� ��������~$A$ �~$B$ � ����� ����� ����� ������ 
���������~D ������������� ����.~3 �~4? ��������������� ����������� ������ 
腋�� �� ��������� � �������� ��������� � ���� ������.

\rex[22] � ������, �����~$K_j\ge K_{j-h}$, � ����~D3 ��������~D 
������������ ���������� ��������� �������� ��������. ��������, ��� ����� 
�������� ���������~D, ����� �������� ���� ���������� ����������, � 
�������� ������������ ������ ���������.

\ex[�10] ����� ���� �� ������� (����������� �������������� �� ���.~11) 
������������� ������������ $1\,2\,5\,3\,7\,4\,8\,6\,9\,11\,10\,12$?

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

\rex[�22] ��������, ��� ����� ��������� ���� \emph{��������������} 
�������� ������ ������������, ����� ����� �������������� ����� ���� �� 
������� ��������� ����� �������� � ��������������� 2-������������� ������������.

\ex[�24] (a)~��������, ��� ��� ����, ������������ ����������~(2),
$A_{2n+1}=2A_{2n}$. (b)~���� ��������~$r=-s-1$, $t=1$, �� ����� ��������� 
�� ���.~1.2.6-26 ���������� ��
$$
\sum_k\perm{2k+s}{k}z^k={1\over\sqrt{1-4z}}\left({1-\sqrt{1-4z}\over 2z}\right)^s.
$$
%%128
���������� �����~$\sum_n A_{2n} z^n$ ��������, ���
$$
A_{2n}=n\cdot 4^{n-1}.
$$

\rex[��33] �����~$g_n(z)$, $\bar g_n(z)$, $h(z)$, $\bar h_n(z)$ 
�����~$\sum z^{\hbox{����� ��� ����}}$, ��� ����� ������� �� ���� ����� 
�����~$2n$ �� ������� ��~$(0, 0)$ �~$(n, n)$, ��������������� ��������� 
������������ �� �������, ����� ������� ��� ���� ��������: ���~$h_n(z)$ ��� 
�����������, ���~$g_n(z)$ ���� �� ������ ��������� ����� �������~$(i, j)$, 
�����, ���~$i>j$; $\bar h_n(z)$ �~$\bar g_n(z)$ ������������ ����������, 
�� �� ����������� ����� � �������~$(i, i)$ ���~$0<i < n$.  �� �������,
$$
\displaylines{
g_0(z)=1, \quad g_1(z)=z, \quad g_2(z)=z^3+z^2; \quad \bar g_1(z)=z, \quad \bar g_2(z)=z^3;\cr
h_0(z)=1,\quad   h_1(z)=z+1, \quad h_2(z)=z^3+z^2+3z+1;\cr
\bar h_1(z)=z+1, \quad \bar h_2(z)=z^3+z.\cr
}
$$
������� ������������ �����������, ������������ ��� �������, � 
�������������� ����� ������������� ������������� ��� �������������� ���������
$$
h''_n(1)+h'_n(1)={7n^3+4n^2+4n\over 30}\perm{2n}{n}.
$$
(������ ����� ��������� ������ ������� ��������� ����� �������� � 
��������� 2-������������� ������������ ���������~$\set{1, 2,~\ldots, 2n}$; 
��� �������������� ������������ �~$\left({7\over 30}-{\pi\over 16}\right) n^3$.)

\ex[�24] ������� ������� ������������� ����� �������� � $h$-������������� 
������������ ���������~$\set{1, 2,~\ldots, n}$. ������ ����������� 
��������� ����� �����������, ����������� ����������~D, ���� ���� 
���������� ������������� ������� ���������~(5)?

\ex[M21] ��������, ��� ����~$N=2^t$ �~$h_s=2^{s-1}$ ���~$t\ge s\ge 1$, 
�� ���������� ������������ ������������ ���������~$\set{1, 2,~\ldots, N}$, 
��������������� ����� �����������, ����������� ����������~D. ������� 
������� ������ �������� ���� ������������.

\ex[��24] ��� ������� ���������~$N$ �����~(6) ����� ������� ���������
$$
{1\over 4}{N^2\over h_t}+{\sqrt{\pi}\over 8}
\left({N^{3/2}h_t^{1/2}\over h_{t-1}}+\cdots+{N^{3/2}h_2^{1/2}\over h_1}\right).
$$
������ �������������� �����~$h_t$,~\dots, $h_1$, �������������� ��� 
���������, ����~$N$ �~$t$ �����������, a~$h_1=1$?

\rex[�25] ������ ������� �������� ��������~$A$ � ������� ������� ������
���������~D, ���� ���� ���������� ������������� ������� ���������~(5)?

\ex[�20] ��������, ��� �������~K ������� �� �����~L.

\ex[�25] �����~$h$ �~$k$---������� ������� ����� ������������� 
�����. ��������, ��� ���������� ����� �����, ������� ������ ����������� � 
����~$ah+bk$, ���~$a$ �~$b$---\emph{���������������} ����� �����, 
�����~$hk-h-k$. ዅ����������, ���� ���� �������� ������������ 
$h$-������������� �~$k$-�������������, ��~$K_i\le K_j$ ���~$j-i\ge(h-1)(k-1)$.

\ex[M30] ��������, ��� ����� ����� �����~$\ge 2^h(2^h-1)$ ����� 
����������� � ����~$a_0(2^h-1)+a_1(2^{h+1}-1)+a_2(2^{h+2}-1)+\ldots$, 
���~$a_j$---��������������� ����� �����; �� �����~$2^h(2^h-1)-1$ ������ 
����������� � ����� ����. ����� ����, ���������� ����� $2^{h-1}(2^h+h-3)$ 
����� ������������� �����, ������� ������ ����������� � ����� ����.

������� ����������� ������� ��� ������, ����� � ���� 
������������� ���������~$2^k-1$ �������� ��~$2^k+1$.

\rex[�22] ��������, ��� ����~$h_{s+2}$ �~$h_{s+1}$ ������� ������, �� 
����� �����������, ����������� ����������~D ��� ��������� � �����~$h_s$, 
����~$O(Nh_{s+2}h_{s+1}/h_s)$. (\emph{㊀�����:} ��.~���.~21.)
%% 129

\ex[�42] ��������, ��� �������~P---��������� �� ��������� ������ � ��� 
������, ��� ����������~$3/2$ ������ ���������.

\rex[M22] ኎���� ���������� ������������ ���������~$\set{1, 2,~\ldots, n}$, 
���������� ������������ 3-�������������� � 2-��������������? 
������ ������������ ����� �������� � ����� ������������? 煌� ����� 
��������� ����� �������� �� ���� ����� �������������?

\ex[�35] ����� �� 3-, 5- � 7-������������� ���� �� $N$~��������� ��������� 
����� $N$~��������?

\ex[�50] ���������� ����������� �������� ���������� ������������, ������� 
������� ������������� ����� �������� ����������� � ���������~D ��� 
��������~$N$, $h_t$, $h_{t-1}$,~\dots, $h_1$.

\ex[15] ����� �� ������������������� �����, ��������� � ����.~6, ��������� 
��� ���������~D � ����� ������ ���������� ������� ������?

\ex[�42] ������� ���~$N=1000$ � ��������� ��������~$t$ 
������������ ��������~$h_t$,~\dots, $h_1$, �������, ���� �����, 
������������ ������� ����� �������� ����������� � ���������~D � ��� 
������, ��� ���� �������� ���� �� �������~$h$, �� ����� ���������, �� 
������� ����� ����������� ���������.

\ex[�23] (�.~�����.) ��������, ��� ���� ��������� ����� 
����~$\set{2^p3^q \mid 2^p3^q<N}$, �� ����� ���������� ����� 
��������~${1\over2}(\log_2 N)(\log_3 N)$ � �� ������ �������� ���������� 
�� ����� $N/2$~�������� �����������. � ���������������� ��� ����� 
���������, ����~$K_{j-h}>K_j$, �� ������~$K_{j-3h}$, 
$K_{j-2h}>\le K_j<K_{j-h}\le K_{j+h}$, $K_{j+2h}$, ��� ��� ����� ������ 
�������� �������~$K_{j-h}$ �~$K_j$ � ���������~$j$ ��~$2h$, ��������� � 
���������~D 2~���������. (\emph{㊀�����:} c�.~���.~25.)

\rex[25] �������� \MIX-��������� ��� ��������� ����������, ������������� 
�.~������� (���.~30). �������� �� ����� ������ ����� ��������~$A$, $B$, 
$S$, $T$, $N$, ����������� ��������������� ��������� � ���������~D.

\ex[10] ������ ����� ������������� ���������� 
������~$L_0L_1\ldots{}L_{16}$, ���� �������� �� ����� ���������� ������ 
��������� � ����.~8?

\rex[25] ������� ������ ����������������� ���������~L, ����� �� 
����� ������ ������������ ���������~$5B$, � ��~$7B$, ���~$B$---����� ��������.

\ex[�10] ��������� �������~(10).

\ex[18] �����������, ��� ������ ����� ������~\MIX{} �����~100 � 
����������� ������ � ����.~8 ����� �� ����� ����~$503\,000$, $087\,000$, 
$512\,000$,~\dots, $703\,000$. ���������� ����� ������ ��������~M �~L � 
����� ������� ���~$M=4$.

\ex[��16] ���� ��������� ����������� �������������� �� $A/M+B$~������ 
������� � ���������� $C+M$~����� ������, �� ��� ����� 
������~$M$ ����������� ����������� �������� ������������ ������������ �� �����?

\ex[�25] �����~$g_n(z)$---������������ ������� ��� ����� �������� � 
��������� ������������ $n$~��������� (��.\ � ��������~(5.1.1-11)). 
�����~$g_{NM}(z)$---��������������� ������������ ������� ��� ��������~$B$ � 
���������~$M$. ��������, ���
$$
\sum_{N\ge0} g_{NM}(z) M^N w^N/N!=\left(\sum_{n\ge0} g_n(z)w^n/n!\right)^M,
$$
� �������������� ���� �������� ��� ������ ��������� ��������~$B$.

\ex[��23] (�.~�.~����.) �����~$F(x)$---��������� ������� 
������������� ������������, ������~$F(0)=0$ �~$F(1)=1$. ��������, ��� ���� 
�����~$K_1$, $K_2$,~\dots, $K_N$ ���������� ���������� ��������� ������� 
�� ����� ������������� �~$M=cN$, ���~$c$---���������, �~$N\to\infty$, �� 
����� ������ ���������~M ����~$O(N)$, ���� ������~$F$---���������� ������� 
�������. (����~$K$ ����������� � ������~$j$, ����~$\floor{MK}=j-1$; ��� 
��������� � ������������~$F(j/M)-F((j-1)/M)$. � ������ �������������� ���� 
������~$F(x)=x$, $0\le x \le 1$.)

%%130
\bye
