%% 428
\input style
\subsubchap{����� � ��������}
�� ��� ��� �� ������������� ����� ��� ������������ �������� ��� �������
����������, ������ ������� � ����� ������������ ����������� � ������
���� ��������� �������� ������ � ����� ������� �������������. 厒� �����
������������ .���������� "�������� ������" ��� "������������ ���������� �
������ ��������" ������ ������������, ����� �������� ��������� ����� ��������:
\medskip
\item{i)} ��� ������� � ����� ������������ ����� �������� ���������� ��
��������� ����� ����� �������.

\item{ii)} �����, ���������� ���������������� �����, �����
������ ������������ ����� ���������� (�����������) � ������� �������.
\medskip
\noindent ��������� ����� ������������� (ii), �� �� (i), ���������
������� ����� �� ������ ����� � ������� �������� ����� �������. ���������
���������� ������������� (i), �� �� (ii); �������� ����� ������� ������
�������� ������ �� ���������� �����������,
\picture{���. 89. ����� ������}
� ������� ����� ������� � ������� ����� �������� � ������ ��� ���������
����� ������� � ���������� ������.

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

����� �� �������� ���������������� ����� ������� ������������ ���������,
��������������� (i) � (ii), �������� ��������
%% 429
���� ��� ������ � ������� ������ (���. 89). ������ �������� ��
���������� ������ ����������� ������� ������, �������� ���������
����������; ��� ������ ��� ������� ���������� ������������ ���������
������� � ���� ��������. ���������� ���� ��� ��������� "�������
������/������" ��� ������ ����������� �����. ������ ����������� ������� ��
��������������� ������, ���������� \emph{���������} ��� \emph{�������},
��� ��� �� ����� ������ ������� ����� ��� ��������� ������/������ ��������
����� �������. ��������� ������� ����� ������������ � ����
������������---������ ��� ������, ���������� ������� ������/������ ��
������� � �������, �� ��� �������� ������� �������. ��������� �������,
������� ����� ���� ��������� ��� �������� ��� ����������� ���������
�������, ���������� \emph{���������}. ��������, �� ���.~89 �������
�������� ����, ������� ����� �� ����� ������� ������/������ �� ������
�����������; ����������� ������� ��������� ���� �� ���������, ���������
�� ���� �������, ��������������� � ��������� ������ ���������.

璎�� ������� ���� ����������� ����� �����������, ����������
�������������� �������� ���������� |MIXTEC|, ��� ��������
$$
\eqalign{
\hbox{1 �������}& =\hbox{5000 �����,}\cr
\hbox{1 �������}& =\hbox{20 �������,}\cr
\hbox{1 �������� ����������}&= \hbox{200 ���������.}\cr
}
$$
 �� �������� ���������� �������� 20 ��������� �����, �. �. ���� ������
���� ������ ������, ������� ����� �������� �� ���� ��������� �����. ��
��������� ������� ������� ������ ������ �������� ������ �����, ��� �������
����� � ����. �� ����� ���������������� ����������� �����������, ��
|MIXTEC|, � �������, �� ������� ����� �������.

�����, ����������� ��� ������ ��� ������ �� �������� ����, ������������,
�� ��������, ����� ���� �������:
\itemize
\li ����� ������ (�����, ������������� �� ����������� ��������� �������
� ������� ��������).
\li ����� �������� (��������, ��������� � ��������� �����, ���� �������
������/������ �� ��������� ������� �����).
\li ����� �������� (��������, ��������� � ��������� �����, ���� ������
�������� ��� ���������).
\itemend

�� ����������� |MIXTEC| ����� ������ ��� �������� �� �������� $i$ �
�������� $j$ ����� $25+{1\over2}\vert i-j \vert$ ��. ���� $i$ �
$j$---�������� ��������� ����� ����� ����� 1 � 200, �� ������� ��������
%%430
$\vert i-j\vert$ ����� $2 \left( {201\atop 3}\right)/200^2\approx 66.7$,
�. �. ������� ����� ������
���������� �������������� 60~��. ����� |MIXTEC| ��������� ���� ������ ��
25 ��, ��� ��� ����� �������� ����� � ������� 12.5 ��. ����� �������� $n$
����� ����
$(n/5000)\times25\hbox{ ��}=5n\hbox{ ���}$.
(풎 �������� � $3{1\over3}$ ���� �������, ��� �������� �������� ��� ����
|MIXT|, �������������� � �������� �.~5.4.6.)

 �� �������, �������� �������� ����� ������� |MIXTEC| � ������� |MIXT|,
���������� ����������, ���������:
\medskip
\item{a)} �� ������ �������� ������ ���������������� ������ � ������.

\item{b)} ��������� �������� � ������, ��� �������, ��������� ��
����������� �������� ���������� ��������� (����� ������ + ����� ��������
� ��������� �� ������������ ��������).
\item{c)} ኎����� �������� � ����� ������.
\medskip

��������� ��� ���� �������� ����� �������, �� ����� �� ��������� �������
��������������� ���������� (a). ⅏��� � ��� ���� ����---��� ����� �����
����� ������������ ��������� ���������� �� ������, � �������
�������������� ���������� (b).
\qsection ��� ��������� ����� ��������? ���������� .�������
������ ����������� ��������, ���������� ���, ��� � ��� ������, ����� ��
����� ������ ������� �����/������, ���� �� ������ ��������� � ����������
�������. ������ ��������� ���� ��������� �������, �� ���-���� �����
���������� � ������ �������, ������� �������� ��� ���� ���������
�������� ����� ��������. ����������, ������� ���������� ��� ����������
���������� �������, �� ��� ������ ������������� ����������� ������������.
 ��� ��������� "���������������" ����.
\enumerate
\li ���� �� ������ ��� ���������� �� ���� ��� ��������� ������� ������
��������, �� ��� ����� ��������� ����� �������� (� ����� ������) ���
���� �������, ����� ������. ������ �������� ����� ����� �������
�������������� ���������� � ��������� �����, ��� ��� ����������
������������������ ������ �����/������ �� ����� �������� ��-�� ��������.

\li ���������� ������ ������ �������� ������� ������ (���.~90): ����
������� ������ ��������, ����� ������� ��������� � ����� $A$, �� ��������
�� �������� �����������, � ����� �����
������ ����� ������� ��������, �.�. ${1\over2}\times25$ ��. ����
������� ����������, ����� ������� ��������� � ����� $B$, ��
��������� ${1\over 4}$ ������� ��� �������� � $1\over2$ ��� ��������; �
����� �����
%%431
${3\over4}\times25$ ��. �������� ��������� ������, ����� �������
������������� ��������� � ����� $C$: ���� ��������������� ������������ �
����������� �����������, ��� \emph{��} �������� ������ $3\over4$ �������
�� ��������. ����� ���������� ������ ������ �� ������ �������� ������
�����, ����� ����� ����� � ${1\over2}\times25$ �� .�����
����������� ������ � ������ �������� ������, ��� ��� ������� . �����
���������, ����� �� ����� ������� � ����� $C$. ��������
\picture{���. 90. ������ ������� �������� ��� ������ �������� �������}
����� �������, ����� �������������, ��� ����� ����� ��
��������+�������� ������� �� ���������� ������� ������ ������� ���������� ��
���������� ��������� �����. ᐅ���� ����� �������� ����������� ����
������ � �������� ������� �� ${1\over2}(1-x^2)$
�������, ���� �������� ��� ������������ ���� $x$ ������� ($0<x\le 1$).
���� �������� ��� ������������ ����� ������� ($x=1$), �� ���� �����
��������� ��������� ��������� ��������.

\section ��������: ������, ����� ����� �� �����. �� ���������
����������� ������� ������ ����������� �� ����� ������� ������/������
��� ������ �������, � ������� ����� ������ ��������� ���������. ���� ��
����� ���������� ������������ �����, �������������������� �� ���.~90, ��
��� ����� ������, ��� � ����� �������� ������� � ����, ��� ������� ��� ��
������ ������ ��� ���������� ��� ������� �������. � ���� ���������
�������� ����� �������� �������� ������������ ��������������� ��������.

���������� ����� ������ �� �.~5.4.6, � ������� ����������� 100000 �������
�� 100 ����� ������ � ���������� ������� � 100000 �����. ���� �����
����������� ������ �������� �������� ����� |MIXTEC|. ������ ����������
������������ ������ � ������ �� ����� �������� ����������; �������
�����������, ��� ������� ��� �����, ��� ��� ������ � ������ ����� ����������.
%%432
 ���� ����� �������, ��� "�����"---��� ���������� \emph{��������},
���������� 4000 ������� �� 5000 ����� ������, � �������� �������
������ �� ���������.

����� �������� ���������� ������� ������������? ����������� �������
����� �������; ������ ������ ���������� ���������� �� ����� ������ �
���������� � ������, �� �����������. ��������, ����������� �������, ��
����������� � �.~5.4.7 ����������, ��� ����������� ���������� ������
���� �������, ���� ���� ���� �� � �����-������ ������� �����������.
(�������� ������, ���. ������� ��������������, ���������������� � ����
������, ��������� � ������ ����� ��� ��, ��� � � ������.)

璎�� ������ ���������� ��������, ����� ������������ ����� � ���������� �
����� �������� ����� �� 5000 ����� � ����� �������� ������ �� 5000 �����,
���������� ����� ������ �� � \emph{����} ������� �� 5000 �����, ����
�������� ������ � ������� ������ ����� �� ������, ��������� �� ������
������. �������� ��� 85000 ����� (850 �������) ��� ������ ������, ��� ���
���� ������ �� ������ ������ ������� �������� ������������ ����� 60
��������� �������� (��. ������� (5.4.6--3)). 풎� ������ �������� ����
����� 50~�, ���� ������������, ��� �������� ���������� ���������
���������� ������, ����� ������ �� ������/������� (������ 500~��� � �����
������ ������ ������������ ������). ���� �� ����������� ��������
������ ��������� �� ����� |MIXT|, � �� �� ��������, �� ���� ������
����� ����������� ���������, � .����� ����� �������� �� �������� �����.

�������� ������, ��� � ������ ���� ��������� � ��� ������/������ �������
��������� ����� ����� �������� ��� $P$-�������� ������� ����������� �
����������� $P$. � ���������, �� �� ����� ��������� ���� ������ 60-�������
������� ���� ��������� ��������, ��� ��� � ������ ��� ����� ��� 60
�������. (���� ������ ������� ����� ������ 5000 �����, ��
�������� .������������� ����� ��������.) ���� �� ���������
$P$-������� �������, ����������� ��� ������ � ������ �������� ��
������ ����� �������, ��� ������ � ������ ���������, �� ����� ��������
������� ����� $\lceil \log_P 60\rceil$; �������������, �� ����� ���������
������ �� ��� �������, ���� $8\le P \le 59$. � ����������� $P$
����������� ����� ���������� ����������, ������� ������� $P=8$; ���� �����
���������� 65 ��������� ��������, �� ������� $P=9$. ���� ����� ����������
82 ��� ������ ��������� ��������, �� ����� ����� $P=10$, �� ��� ���
������� ����� ������ ��� 18 ������� ����� � ���� ������� ������, ��
�������� ����������� �������� ��� ������� (��. ��������~5.4.6F); � �����
������, ��������, ����� ��������� ��� ��������� ������� ��� ���������
����� ������, �������� ����� ��������� �������� �� 81 ��� ������.
%%433
��� ����� �������������� ������ ������ ������� ������ ����� 50~�, ��� ���
��� ���������� � ���� ��������� ��������
����� ��������� �� $2{1\over2}$~��� (���� ��������� ������ ��
������������� � ������ ��������������� ��������). 풎 � �����
��� �������, ��� ��������� �� ���������� � ������ �������, �������������
� �.~5.4.6. ��������� ����� ��������� �������� ����������� ��������
�������� ������ ����� ������� � ���������� ������� (��� � $3{1\over2}$
���� ����) , ����� ������� ������� ������� (�� �� ����� �����������
������������� �������
�� ������ �� ���� ������ ��� �������� ����� ����) � ��, ��� ��������
������ �������� �� ����� (��� ������������� � �������������� ��������� �
�. �.). ���� ���������, ����� �������� ������ � ��������������� ���������
���� �� ������ |MIXT|, � �������� ������������ ������ ��� �������, ��
����� ���������� ������ ����� 8.2 ���.

���� ������ ���� ��������� ������� ������ ����, �� ����� �����/������
���������� �����, ��������� ������/������ �������� ��������� ��
�����������. (�� ����� ���� �������� �����/������ ������ � \emph{��� ����}
������ �������, ���������
������ �����-���� ������ �������� ������; � ����� ������� ������������� ��
������ ��������� ������ ��������� �������� ������������ ������, ����� ��
�������� ���������� �����-������ �������� ������, ���� ������
������������ �� ������������ �������������� �������� ����������
����������.) ������ ����� ����� ��������������� ������� ����� ����������,
��������� �� ����� ������������ ��������� �������, ��� ������� ���� ������
�������������� ���� ������. � ������ ���� ��������� ���������, ����� ���
������ �������������� ������ ���>�������� ����� ���, �� � ������ ������
�������� ����� ������������ ����� ����� ����� �������.

�� ������ � �.~5.4.4, ��� ����� ������� ����� ���������� � �������
�������� � ��� ����� ��������, ��������������� ����� �������,
��������������� ����� �������� ���� ������. � �������� ���� ������������
������� �� ������ ����� ������������ ���� ������ ������������ �������
("$T$-lifo" ��� "������� $T$-fifo"), ������ ��� � �������� �������
��������� ������� ����������� "�����������" � �������� �����. �� \emph{���
������������� ������ ��� ��������� �������� ����� �������}, ����
������ ������� �� ���������� ����� �� ������� ������ (�. �. �����������
� �������� ������� ���������� ������).

ዅ����������, ����� �������� ����� ��������������, ���� ������� ������ �
����������� ������ �������� ����, �����, ��� ������ $P$-����� ������, ���
$P$---����� �������, ����� ��������. �� ������� (5.4.4--9) ����� ��������
���� ������ ������
%% 434
� $S$ �������� ������ (��������) �����
$$
qS-\lfloor(P^q-S)/(P-1)\rfloor, \qquad q=\lceil\log_P S\rceil.
\eqno(1)
$$

�������� ������ �������� ��������, ������� ������������ ������� �
������������ �� ������ ������� $P$-������ ������. (�., ��������, ���.~91,
�� ������� ������� ������ $P=3$, $S=6$.) ፀ���� �� ���������, ����
����������, "��������� �������", ����� ������� $S\equiv1 \pmod{P-1}$;
����� ���������� ������� � ������������ � ����������� "������ ���������� ---
\picture{���. 92. ������ ��������� ������ � ������ ��������...}
������ �����������", ������ �� ������ ����� $P$ ����� "������" �������� �
������ ������� � ���� �������, ���������� � �����.

������ $P$-����� ������� ���� ����������� �����, ���� ��� ������� �����
������ �����, �� ����� ��������� ����� ���� ��� �����, ���� ���������
������� ������� ������. ����������� ����� ��� ���� ����� �������� �����
��� ����� ��������� � ������� ������ 倔����� (���. 2.3.4.5--10), �������
�� ����� ������� ������������� ���: "������� ��������
$(1-S)\bmod(P-1)$ ��������� �������� ����� 0, ����� ����������� ��������
$P$ \emph{����������} �� ��������� ��������, ���� �� ���������
���� �������". ���� ��� ��������� ������� ����� ���������� �����, �� ����
����� �������� � ��������� ���� ����������.

� ����� ������� �� 100000, ������� �� ����� ��������� 9-������� �������,
��� ��� � ������ ���������� 18 ������� ����� � ��� ������ ������, � �
��������� 5.4.6F ����� ���������� ������ ���������� ����������. ������
9-����� ������
� 60 �������� ������������� ����� ������� � $1{29\over30}$ �������, ����.
��� ��������� ������� ����� ���������� �����. ����� ����� ���������� �
����� ��������� � � �������������� "������������ ������" ����� ������
������ ����������, ����� �������, ������ 7.4 ���. ゅ������� $P$, �����
������� ��������� ��� �����, �� �������� ������ ����������, ��������� ��
����������� �������� ������, ��� ��� ������ ����� ��������� �������
������� ��� ������� �������.

%%435
\section ������� ������� ������. ���������� ���������� ����������, ��� ���
��������� ������������ ����� ��������������� "�����������" ����� �������,
 ��������� ����� ������ � ����� �������� ����� ������ �� ���. �� ����
������������ �����, �� ����� ���������� �������� ������ �������, ��� ��
������. ������� ����� ������ ��������� ������������ ������� �� ���������
����������. ㌅������� ������� ������� $P$ ���� ����������� .
������������ ������� �� ������� ������, ��� ��� ���� ��������� �����; ��
���� ����� ����� �������������� �������������� ����� ��������, �������
������ � ����������� $P$.

����� ������ ������� �� ����������, ����������� ���������� �������, �
����� ���������� ������������ ������ ����� �������, ����� ��� ����������
���� �����������. ���� �����, ������� ������� ����������� ������ ������
���������. ������ �������� ������� ������� ������� �������� ����������
���������. ����� ���������� (��., ��������, ���.~2). ����� ����, �����
���������������������� � ����������� ������������ �������� ��������, ���
������������ ���� � ������ ������� ����� ��-���������� ��������������
��������� ��������� �������; ��������� �����, �������������� �����,
������ �������� ������ �� �������� ����!  �� �������, ������������� �
���, ��� ������ ������� ��� ����� ������� "����������" ������, �����
������ ���������.

���� ���� � ��� � �������, ����� ����� ����� ������ (�. �. ����� �������),
������� ������������ ��������� ������ ����� �������� ������ � ��������
��������; ��� ���� ���� ��� ����� ��������� ������, ����������� �������
����������� ������ ����������� ������ �� ��������� � ����������
������������ ������������. ����������, ��������, ������ �� ���.~92;
�� ����� �������, ������� ������� ������ ����������'����������������
�������, ����� ����� ���� �������� ��� ������ � �������.

� ����������� ������������ �� ������� ��������� ������� �������������
������������ ������� �� ������, ����� ����������������� ��������� �����
����. �����������, ��� (1) �� ������ ��� ������ $n$ ����� ���������
$72.5+0.005n$~��; (2) ��� ������� ������������ ��������� 100000 �����
���������� ������; (3) ��� ��������� ����� ������ �� ������ ����� �
����� ������ ������������� � ������� $0.004$~�� �� ����������; (4)
\emph{��� ����������} ������, ������ � ����������; (5) ������ ������,
 ������������� ��� ������, �� ����������� ������ ���� ����� ������� ������,
 ������������� ��� ������ ������ �� ��������� �������. ������ ������
���������� ��� ���� ������� �������������� ����� ������� ��� ���������
����� ������� ��������.

���� ����������� $P$-������� �������, �� �� ����� ���������
%% 436
���������� ������� ������ �� $P+1$ �������� ��������: $P$---��� ����� �
1---��� ������; � ������ ������ �� $B=100000/(P+1)$ �����. �����������, ���
��������������� ��� ������� ����� ��������� � ����� $L$ �����; ����� ��
�������� �������������� $L/B$ �������� ������ � �������� ������� ��
�������� �����;
�������������, ����� ����� ������� ��� ����� �������������� ����� �����
(� �������������) ��������������
$$
2\left(72.5{L\over B}+0.005L\right)+0.004L=(0.00145P+0.011545)L.
\eqno(2)
$$

����� �������, $P$-������� ������� $L$ ����� �������� ��������
$(\alpha P+\beta)L$ ������ �������, ��� $\alpha$ �~$\beta$---���������
���������,
��������� �� ������� ������, ������� ��������, ������� ���������� �
������� ������. 풀 ������� �������� � ����������� ������� ����������
������� ���� ������� ���
\picture{���. 92. ������ � ������ �������� ���� 16 ...}
������. ����������, ��������, ���.~92 � ����� �������, ��� ��� ���������
.������� (������������ ����������� "��������") ����� ����� $L_0$.. ⎃��
������ ������� � ����� 9 �~10 �������� $(2\alpha+\beta)(2L_0)$ ������
�������, ������� � ���� 11 �������� $(3\alpha+\beta)(4L_0)$ ������ �
������������� ������� � ���� 12 �������� $(4\alpha+\beta)(8L_0)$ ������.
����� ����� �������, �������������, ���������� $(52\alpha + 16\beta)L_0$
������. ����������� "16" ��� ������ ��������: ��� ������ ����� ��������
���� ������. ����������� "52" ��� $\alpha$ ������������� ������ �������,
������� �� ����� ������� \dfn{������ ���������� ���� ������}; ��� �����
�����, ������ �� ���� �������, �������� ���������� �����, ������� ��
���� �� ����� � �����. ��������, �� ���.~92 ����� ���������� ���� �����
$(2+4)+(2+4)+(3+4)+(2+3+4)+(2+3+4)+(3+4)+(4)+(4)=52$.

���� $\cJ$---����� ������, �� ����� $D(\cJ)$, $E(\cJ)$
���������� �������������� ����� ���������� ���� � ����� ��������
���� ����� ������. ������ �������� � ��������� �������:

%% 437
\proclaim ⅎ���� H. ���� �����, ��������� ��� ����������
$P$-�������� ������� $L$ �����, ����� ��� $(\alpha P+\beta)L$ � ����
��������� ����� $S$ �������� ������ �����, �� ��������� ����� �������
������������� ������ $\cJ$, ��� �������� $\alpha D (\cJ)+\beta E(\cJ)$
���������� ����� ���� �������� � $S$ ��������.

\noindent (풀 ������� ������ ����������� � ���������������� ������,
 ������� ������ �. 倁���� ���������� �� ������������ ����������� ACM �
1963 �.)

����� $\alpha$ � $\beta$---������������� ���������; ����� ��������, ���
������ \dfn{����������}, ���� ��� ����� ����������� �������� $\alpha
D(\cJ)+\beta E (\cJ)$ ����� ���� �������� $\cJ$ � ��� �� ������
�������. �������� ������, ��� \emph{��� ���������� ������������ ������
����� ����������}. ������� �� ����� ������� ����������� ������� � $n$
��������, ��������� ����������� �������, � ������� ������ ��� $n$ �������.

\proclaim ⅎ���� K. ����� ������������������ ����� $A_m(n)$ ����������
��� $1\le m\le n$ ���������
$$
\eqalignno{
A_1(1)&=0; & (3) \cr
A_m(n)&=\min_{1\le k\le n/m} (A_1(k)+A_{m-1}(n-k)
\rem{��� $2\le m\le n$;} & (4) \cr
A_1(n)&=\min_{2\le m\le n} ((\alpha mn+\beta n+A_m(n))
\rem{��� $n\ge 2$.} & (5)\cr
}
$$
⎃��  $A_1(n)$ ���� ����������� ��������
$\alpha D (\cJ) +\beta E(\cJ)$ ����� ���� �������� $\cJ$ � $n$ ��������.

\proof �� ����������� (4) �������, ��� $A_m(n)$ ���� ����������� ��������
$A_1(n_1)+\cdots+A_1(n_m)$ �� ���� ������������� ������
$n_1$, \dots, $n_m$, �����, ���
$n_1+\cdots+n_m=n$. ␅������ ��������� ���������� ������ ���������
��~$n$.
\proofend

������������ ����������� (3), (4), (5) ����� ������������ ����� ���
���������� ����� ����������� ��������. ����� $k_m(n)$---��������, ���
�������� ����������� ������� � ����������� $A_m(�)$. ⎃�� �����
��������� ����������� ������ � $n$ ��������, ��������� $m=k_1(n)$
����������� � �����; ���������� �������� ������������ ��������� � $k_m(n)$,
 $k_{m-1}(n-k_m(n))$, $k_{m-2}(n-k_m(n)-k_{m-1}(n-k_m(n)))$, \dots
�������� ��������������.

풀 ����������� ��� $\alpha=\beta=1$ ����������������� � �������� �������
� ����.~1. ���������� �������� ��������������� ����������� ��������
������� � ������ ����� �������; ������� "4:9:9" ��� $n=22$, ��������,
��������, ��� ����������� ������ $\cJ_22$ � 22 �������� ����� �������� �
���������� ����������� $\cJ_4$, $\cJ_9$ �~$\cJ_9$ (���.~93). �����������
������� �� �����������;
��������, ������� 5:8:9 ��� �� ����� �� �������, ��� � 4:9:9.
%% 438
\bye
