\input style
\chapno=6\subchno=4\chapnotrue

\subchap{�롮ઠ �� ����� ���砬} %%6.5
�� ��������� �������� ������ �� "��������� ������", �.~�.
�� ������, ���������� ������������ ������ � �����. �� ������
���������� ����� �����, ����������� �� �� ��������� ������, � �� ���������
������ ����� ������, ������� ����� ���������� "���������� �������" ���
"����������" ������. ��������, � ��������������� �����, ����������
���������� � ��������� ������������, ����� ������������ ����� ����
���������-�������������� �� �����, �� ������������������ ��
���������� ��� ����������, ��� ����� ������������ ����� ���� ����������
����������, ��������� ��-����������, � �.~�.

������ �����������, ��� ������ ������ ����� ��������� ��������� � �� �����
����� ��� ������ � ������������� ���������� ������������ ���������.
Ꮕ��������� ������� ������� ���������� \dfn{��������}. ������ �����������
�� ����� ���� ��������� ����� ��������.
\medskip
\item{a)}~\dfn{������� ������}, ����� ������������� ��������
�������� ���������� ��������, �������� $|ᯥ樠�쭮���|=|��⥬�⨪�|$ ���
$|���⮦�⥫��⢮|.|���| = |�����|$.

\item{b)}~\dfn{������ �� ������� ��������}, ����� ���
������������� �������� �������� ���������� ������� ��������, ��������
$|業�|<18.00\$$; ��� $21 \le |������| \le 23$.

\item{c)}~\dfn{����� ������} ������� �� �������� ���� ������ �����,
 ����������� ���������� |�|, |���|, |��|; ��������,
$$
\displaylines{
(|����|=|��ப��᭨�|) \mathbin{|�|} (|���⮦�⥫��⢮.���|=|�����|) \cr
\mathbin{|�|} \mathop{|��|}\nolimits
((|ᯥ樠�쭮���|=|��⥬�⨪�|)\mathbin{|���|} (|ᯥ樠�쭮���|=|����⨪�|)).\cr
}
$$

������ ���������� ����������� ������� ������ ���������� ������ ��� ���
���� ���� ����� ��������, ������� ������� ����� ������� ����� ������ ��
���������������. ��������, ��������������� �������� ����� �� ����� ����,
����������� ������� ��������� ���� ������������� �� ��������
�������. ������ ���� "����� ��� ��������� ������-������������ � ��������
500~���� �� ም���" � ����� ���� ��� �� ����������, ���� �� "���������� ��
ም���" ���� �� ��������� ������ ������, � ������� �������� ����������
���������. ������������� �� ���������� ��������� � ���������� � |�|,
|���| �~|��| ����� � ���������� �����������, ������� ������� ����������
%% 652
���� ��������� ������ �������. ��������, ���� ���� �����������
����������, �� ����� �� ��������� ������ � ����� ������� ����� �������
������ � �������� �����. 품 ������� ������, �� �� ��� ��� �� �����
��������, �������� ���� ������ �� ������� ������� ��������������� �����.
���� � ��� ����� ������� �������; ��������, ����� ��� ���� �������,
������� ���������� �������� ���� ��� ����� ��������� (��� �����������
����, ����� ������ �������� ������ ���������). �������� ������� �����
������������� ��� ����� ������ ����������������, ��������� �� �����
������ ������, ���� ����� �� ����� ������� �� ��������� ���������������
���� �����.

������ ��� ���������� � �������� ��������� ������� ������� �� ���������
������, ������� ����������� ������������� ������� �������. 厒� ��������
�������� ������� ���������� �������� � ������� ����� ���� ����� ��������,
������� ������, ������� �� ����� �������, ������ �� ������
�������� �������������������; ���� ������ ����� ������� ������� �������!
��� ��������� �������� ������� ���������� �������������� �
$10^7$--$10^8$~���; ��������� �� ������������� � ���� ����������
����������� ���������� ������. ��� ��������� � ������� ����������� ������
����������� ��� �������� ��� ��� � ������������� (� �� ������������)
����������, �������, ������� ������ ������� �� ���, �� �� �������� �������
��������� ������������� �� ������� ������. �� ������� ������� �� ���
������� ������� ������ ������, ��� ��� ������� ������ ��������� ������\dots

���� �������� 킅���� "������, ��� �� ����������", � ������, ��� ����
������� ������������, ��������� ����������� ���������; ����� ��� ��,
������������ � ����� ����������, ���� ���������� ������������ ��� ���
������� �� ����� ������� �������� � ���������� ������� � �����������
������ � �������� �������� �������, �� �������� ������� ������� ���������
������. ␅������ ���������� ��������, �� ������� ������ ��� �������������
�������������.

����������, ��������, ��������� ������� ������ ������� �� ���������
������: ����� "\emph{�����������}" ���� �������� ����� ����������
���������������� ����� �� ���� �����, ������� ��� ������ ������.
("�����������" ��������, ��� �� ����������� �������, ������ ��� ������
�� ���������.) 풎� ����� ������ ����������������, ���� ���� �� �������
�����, � �� ������� �� ���� �������� ����������. �� ������� ����
��� ������ �� ������ � ���� ����� �� ������� ������� �������� ���, ���
������ ��� ����� ����������� � ������ ��������� ������������. ����� ����,
������������ ������ �������� ���� ��� ��������� �������������� ��������
���� "���������� �� ም���".

%%653

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

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

���� ��������� ������ ������� ���� ��� ������� ���� ������, �� (���
�������� ��������� ��� ���������) ��� ��������� ��������� ����������
���� ��������� ���������� ������� �� ��������� ������. ����������
�������� ������������ ������ � ���������� �� �� ������ ����
�������������� ���������� ���� ��������� ������������, ��� � ��
������ ���������������� ��������� ������� ��������� � �������� ��������. �
��������� ��������� ���������� ���� �������� �� �������������� ��������;
���� �������� ������, ����� ���������� ������� ������ ����� �������� �
������ ���������� ������.

\section ��������������� �����. ������ ������ ����� ������� ������� ��
��������� ������ ������� �� ���� "���������������� �����". 풎� ������ ��
��������, ��� ���� ���������� ����� ����, �� ��������, ��� ������ �
�������� ���������� ������. ������ ������������ ��������� ������ ������
������������� ������, ������� ������ �������� ��������.

� ������������ ����� �� �������� ����� (������, ��� ������� �������)
������������ � ���������������� �������. ��������, ��������������� ������,
��������������� ������-����������� �������, �������� �����-�������
�������. ��������������� ������, ��������������� ���� �����,
�������� ���������, ���������� �� ��������� ���������.
���������� ����������� ���������� "������� �����������", ����� ���
������� ���������� �������������� ��� � ����� �����, ��� � � �����
�������, ��� ��������� ����� �������������� �������� ����� ����� � ����
�������.

������ ��������������� ���� ������ �� ���������� ��� �� ����, ��� �����
������������ ������ � ��������������, ����������������� ������ ���
��������� ������ � ������� ������������
%%654
� ��� ���������� ����������. ���������� ���������������� �����,
�.~�.~������ ���� �������, ������� ������ �������� ���������� ��������,
���������� \dfn{���������������� ��������}.

��� � ��� ������ ������, ��������������� ������ ����� ������������ �
������ ��� ���������� ���������, � ��� ������ ���������� �������� ������
�������������. ��������� ���� ��������� ������ ����� ����� ���� ���
�������� (��������, ������� "���"), � ���������������
��������������� ������ ����� ������, �� ������ ���� ������ ����� �����
����� �������� � ������� ������������ (��������, ������� "����� ��������").

���������� ����, ��� �� ����� ������� ���������� � ���������� �����
����� �������, ����� ��� �������� ����� ���� �������� ���� �� �����, ����
�� ������ ��������, ���� �� ����� ����������. ���� �� ������� ������� �
���, ����� ������ ����� ��� ��������� �����, ��������������� �� ������
��� ������. ������ ���� ����������� � ����������� ���� ������, ��������, �
������� ���������� ���� ���������� ������, �������� � ������ �������
��������� ������ �������. � ���� ��������� ����� ������ ������ ������ ����
��������� ���� ������� � ������ ������� ��������� ��� ���� ������; �����
����� ���������� \dfn{��������������} � ����������� ����. ��� ����
�����������---���������� ��� ����� � ���� ��������� �� �������� �
������������ ���������, � ������� �������� � ��������� �������, �������� �
���������� ���� � �������� � ������ ���� ��� ������ ����������� �� ��������.

�������� �������, ��������������� � ���������� � ������ �����, �����������
�� ������ ���� � ������������� ��������������� �������. ����
������������� �������� �������� ������������� ����� ���� ���������,
����� ������������ ������� ���������������� ������ ������� �������
(���������� ������� ������� � ��������� � �����), ������� ������ ��������
���������� �����. ���� ��������������� ������
������������� ���������������, ����� ���� �������� ��������
��������� (��������, �� ��������~200 ��~214). ���� ��������, ���
������ ����� �������� ����� ������������, ������ ������� ������� �
��������������� �����, �������, ����� ������������ ��������� �����;
����� ��� ����� ������� ������� �� ����� ����� ����������� �������
���������. ��������, ��� ������� �� ������ ������ ����������� ����� � ����,
 � ��������� � ��������� ������ �������� �� �� ��������� �������, � �� ������� ����������.

������ ������������ ���� �� ����� �������� ��� ������ �������� � �����
���������� ����������, ���� �������� "|���|". � ����� �������� ����� ����
���� ��������������� ������,
%%655
��� �� ������� ���� ������� � �������. ���� ������ �������� �������������
�������� �������� ��������� �����, ��������������� ������ ����� ������
��������, ������ �� �������� ��� ��� ��������� ����� ��������� ������
������, ��������� ������������� � ���� ������� �����, ��� ������
��� ���������� �������� �������� ������������ ������.  , �������
�����~$01001011101\ldots$ ����� �� ��������, ��� ������ ������
����� ��������� �������, ������---�������, ��������� ���---������ � �.~�.
(�.~����� � ����������� ������������� ������� ����� � �����~\S~6.1.)

����������� ������ ����������������� ��� ��������� �������� ��
���������� ��������� ���������. ��������� ��������� ���� �������
�������� ������������ ������� �� ������� ��������. ��� ���� ������
����������� ����� ������������ ����� ������, ���������� �� ���������� (\S~6.2).

��� ������� �������� ����
"$(|ᯥ樠�쭮���| = |��⥬�⨪�|) \mathbin{|�|}
(|���⮦�⥫��⢮|.|���|= |�����|)$"
 ����� �������� ��� ��������������� ������. 풎 ����� �������
����������� ���������; ��������, ���� ��� ������ �����������, ����
������ �� ������� �� ��� ��������� ������� ��� ����� ��������. ��� ��
����� ����� \emph{����������} ������ � ������������� ��� ��������,
�������� �������� ������ ���������;
������ ����� ����� �������� � ��������~|�| � �� �������� � ��������~|���|.
����� ����, �� �� ������� ��� ������� ������, ��� ����� � �������� �����
��������� � �������, �� ��������������� �������.

����������� ����������� ����������, ��� ���������� ���� ��������������
����������� ������������ ��� ������� ��������, ���� ���� �������,
��������� ��� ������� ����� �������� ���������. ���������� ����, ��������,
��� ����������, ���� ��������� � ���� ����� ������������ ��������������
�������. ������ ������� ��������� ����� ��������� ���� �� ��������� �� ���
�������, ��� ������������� ����������� ������; �� ������ �������� ���
������� ������� ������ ������� ������ �� ����� ��� ����������� ���������.
� ����� ������ �������� ����������� ����� �������, ����� ����� ����
��������, ����������� � ���� "[������ ����������] � [(������� ����������)
��� (���������� ����������)]". � ������ �������, ��� �� ������
����� ����������, �������� ����� �� ��� �������� �������� ��������� �
��������� ��������� �������� ��� ���������������� �������� ���
���������� ���������� ������������ �������, ��������������� �������.

���� ��������������� ������ ����������� � ���� ������� �����, ��
���������� �������� ����� ��������� ������ ���������� ��������,
��������� ��� ����� �������������� ��������� ����� �� ������������
������� ���������. � ������ ���������
%%656
��������, ����� ��������� �������� ������������ �����������
���������������� ������� ������� �������, � ������ ����������� �������
�����, �������� ������������� ���������������� ������ � ������� ����� �
���������� ��� ���� ������ ��������.

� ���� ����� ������� �������� �������������� ������ ���������������
����������. �����������, ������� 1000000~������� �� 40~����� � ������, �
����� ���� �������� �� ������ \MIXTEC (��.~�.~5.4.9). ဌ ���� ��������
��� �������� ������;
��������������� ������ ������, ��������, ��������� ������ �����. ������
������� ��������
$5000\hbox{~�����}=30\ 000\hbox{~�����}$, ������� ��������������� ������
��� ���������� �������� ������ �� ����� 34~�������. (������������ �����
������� ������������� ������, ����� ������������� � ���� ������� �����
�������� ��������.) �����������, ������� �������� ������� ������,
��������� �� ������� ���������� 10~��������������� �������; �
������ ������ ��� �������� �������� 340~������� ���������� ��
���������������� �����. ������ ����� ������ ��������
$340\times 25\hbox{~��} =8.5\hbox{~�.}$
ᐅ���� ����� �������� ����� �������������� �������� ����� ����������, ��
���� ������� ��������� ���������, �������� ����� ���������. ���� �������
������ ������� ������� �� ����� ��������, ������ �� ��������� � �.~�., ��
����� ������ ����� �������
���������~$34\times26\hbox{~��}\approx0.9\hbox{~�}$ (��� 1.8~�, ����
������ ������������ � ���� ������). �������, ���� ������� �������������
$k$~�������, �� �����������
$k\times (60\hbox{~�� (�����)}+12.5\hbox{~��(��������)}+0.2\hbox{~�� (������)})$
��������������� �������, ����� ������� �� ��� �����������
���������.  �� �������, ��������������� ������ ������� ������� ���������
����� �������� �������� ������� ���� �����~$(10+0.073kt)\hbox{~�}$.
���������� ��������� ����� ����������� � 210~�, ������� �� ������
����� ����� � ������������ ���������.

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

�� ��� ��� � ������� ��� ������� ������� ��������������, ��� � ��������
��������� ������� ���� �� ������ � �� �����������; �� ��� ������, ����
���������� ������ ���������? �� ������ ����������� ���������� ������������
��� ��������� ��������� � ������������ � ��� � ��������� ������, �����
�� ����� �������� �� �������. ���� �� ��������� ����� ����� �������
���������, ������������� ������������� $B\hbox{-��������}$ (�.~6.2.4). ���
��������� ��������������� ������� ����� ���� �� ��������� � ����
���������� $B\hbox{-������}$, ������ �������������� ���� ������
��������� �������� ������, � ������---� �����, � ������ ���������� �� ������.

%%657
%% 657

� ���������� ���������� �� �������� ��� �� ����� ������� �������---� ������
������� ���������� �������� �� ������� ��������. �����������, ��������,
��� ������ ����� ��������� ������ ᅂ����� ������� � ��� �������������
�������� ���� ������� � ������������
$$
(21.49^\circ<|���|\le 37.41^\circ)\mathbin{|�|} (70.34^\circ\le
|������| \le  75.72^\circ).
$$
኎��� �����, �� ���� ��������� ������ ��-���������� �� ������� ���
�������� "�������� �� ������������� ������� ��������". (�������� ��
�����, �� �����, ��� ������ ������ ������������� ����������� �� ������,
������---�� �������, �� ���� �� �������� �����, ��������������� �����
������������.) �������, ��������� ������ ������� � ��������
������ ����������� ��������� ���� ��������� �������� |����| � |�������|,
����� �� ������ ������� ����������� ���� ��������� ������� (��������,
����� ��������� � ����������� �� �����, ��������~$5^\circ$), � �
����������� ���������� ���������������� ������ ��� �������
���������������� $(|���|, |������|)$~������. 풎 ��� �����, ��� �����
�����, ��� ��� ������� ���������� ������ �������� ��������� ��������.
��� ������������� ���������� �~$5^\circ$ � ������� ����� ��������� ������
�������, � ������ $(20^\circ, 70^\circ)$, $(25^\circ, 70^\circ)$,~\dots,
$(35^\circ, 75^\circ)$. ������ ���������� ���������� ��� ������ �� ���,
���� ��������� ����� ������ ����������� ������ ��������, ����
��������������� ��������� � ������� � ����������� �� ����� �������,
��������������� ���� ��������. �� ��������, ���������� ��������� ������ �
���������� �������������� �� ���������� �����.

������ ������ � �������� �� ������������� �������, ����� ���������� ��
��������� ������, ��������� ���� ���-����. �����, ��������, �����
���������� ������ ���� "����� ����� ����� ����� � �����~$x$?", ���� ����
��������~$x$. ������ ���� ������������� ���-������ ��������� ������ ������
������������� ������~$y$ � "������������ �������"~$r$; �����
��������� ����� ���� ������������� ���� �������~$z$, ������� ����������� �
������, ������ ���������� ��~$y$ ��~$z$ ������ ���� $\le r+\delta$;
���������� ������ ��������� ������������� ��� ���������� $\ge r-\delta$.
����� $\delta$---������ ������; ������, ��������� ��~$y$ ������, ���
��~$r+\delta$, � ������, ��� ��~$r-\delta$, ������ ������� � ��� ���������.
 ����� � ����� "�������� ������" ��������� ������� ��� ������, ���������
�� ������ ����� �����, ��� ��~$\delta$. (�.~���.~45.)

� 1972~�. ���-���� � 턂��� �����, ����������� �� ���� ����, �������
��������� �������������. � �������� ���� ������ ��� ������������
231~�������� ���������� ����� ���������������
%% 658
\picture{��� 45. ������� ������ "��������� ������". 璎�� ����� ��� ������,
 ������������� ������ ������ �����~$x$, ������ � �����: ���� $x$ �� �����
1800 ���� �� ���-������, ���� �����, � ��������� ������--- ������; �����
��������� ���� �������, ���� �� ��������� ��������� ����. ����� ����������
������ �����������, ��� � �������� ������ �� ��������� ���� �������,
��������� ��~$x$ �� ����� ��� �� 20~����.
}
%%659
ᎅ�������� 蒀���, ������ � ��������� �������. �����������
������~$r$ ���������� ���������� �������: ��� ���� ����� $r$~��������
��~$0.67r$, � ��� ���� ������---��~$0.57r$. ���� �� ���������� ������ ��
���� ���������������� ������ ������, ������ ��������� ����������. �
���������� ����������, ��� ��� $\delta = 20\hbox{~����}$ � ������ ����
610~�����, � ��� $\delta=35\hbox{~����}$---1600~�����. �� ���.~45 ����������
������� ������ �������� ������. (� ���������� ������� ������� (����
䋎����) ���������� � ���� �����������, � ���� ������. ��������� ������
����������� �������� �����; ���, 17~����� ������������� ��� ��������
(���� �����������)!)

\section ᎑������ ��������. ����� �������������� ��� ��� ����� ���������
� ���� ������������. ��������, �������
"$(|����|, |ᯥ樠�쭮���|)$" � ��������������� ��������������� �����
����� �������, ���������� ���� |����| �~|ᯥ樠�쭮���|. ��� ����� �������
�� ������ ����� ����� �������� � ������� ����������� ���������� ��������
�������, � �� � ������� ����������� ����� ������� �������.

���� ���������� ��������� ������ �.~��� [{\sl CACM,\/} {\bf 13} (1970),
660--665]. �� ��������� ������������� ��������������� ������,
 ��������������� ��������� ���������, ����������������� ����� ������� �
����������� ��������� �����, � ������� ��������� �������� ������������
���������� �������. �����������, ��������, ��� ������� ��� �������� |A|,
|B|, |C|; ����� ���������� ��� ��������������� ��������
$$
(|A|, |B|, |C|),   (|B|, |C|, |A|),   (|C|, |A|, |B|)
\eqno (1)
$$
� ��� ������� �� ��� ��������� ������������� ��������������� ������.
( , � ������ ������ ������ ����������� �� �������� ����~|A|; ���
������ � ����� � ��� �� ���������~|A| ����������� ��~|B|, � ����� �
��~|C|.) �������� ����������� ��������� �������� �� �������, ��������� ��
����� ���������� ���� ���� ���������; ��������, ��� ������, �������
������������ ��������~|A| �~|C|, ����������� � ������� ������ ���� �� ������.

���������� �� ������� ��������� |A|, |B|, |C|, |D| ����� ����������
����� ��������������� ���������
$$
\matrix{
(|A|,  |B|, |C|, |D|), &  (|B|, |C|, |D|, |A|), & (|B|, |D|, |A|, |C|), \cr
(|C|, |A|, |D|, |B|), &(|C|, |D|, |A|, |B|), &(|D|, |A|, |B|, |C|),\cr
}
\eqno(2)
$$
��� ��������� �������� �� ��� ���������� ������� ��������, � �������
�����������, �������� ������, ����, ���� ��� ������� ���������.
ᓙ������� ����� ��������� ���������� $\perm{n}{k}$~���������������
��������� �� $n$~���������, ��� $k\le{1\over2}n$; ��� ���� ��� ������,
������� ������������ ���������� $\le k$ ���
%% 660
$\ge n-k$~�������� ���������, ������������ ��������������� � ����� ��
��������������� ������� (��.~���.~1). ��� �� �����  �������� �������
������ ����������, ���� ��������� �������� ����� ������������ ����������
��������. ��������, ����  �������~$|D|$ ����� ��������� ���� ��� ��������,
�� ��� ����������
$$
\matrix{
(|D|, |A|, |B|, |C|),& (|D|, |B|, |C|, |A|),& (|D|, |C|, |A|, |B|),\cr
}
\eqno(3)
$$
���������� ��~(1) ���������~$|D|$ � ������, ����� ����� ����� �� ������,
��� �~(2), ��� ��� ������� �� �������, �� ��������� ��~|D|, ���� ��
������� ���������� ����������� ����� � ���� ������. ������������ ��
���������� ����������� �����.

\section �������� ��������. ������� ����������� ������� ������, ����� ���
�������� ����� ��������� ���� ��� ��������. �� ��������, �� �����
\emph{������ �����������������} �������������� ���������, ��� ��� �����
����������� ����� �������� � ���� ��������� ����� � ������������� ����
����� ����� ��� ��������� ��������. � ����.~1 (��.~McCall, Cook Book (New
York: Random House (1963), Ch.~9) �������� �������� ����, ����������
�������� "��-���"; � ������ ������ ������ ��������� ��������� �������
�������, � �������� ����������, ����� ����������� ������������. ��������,
��� ������������� ����������  ������ � ����� ����� �����, ����, ������,
����� � ��������
�����. ���� ���������� ����.~1 ��� ������� �� ����� � ������, ��
����������������� ������� ���� ��������������� ���� � ���� ������� �����.

� ������ ������� ����.~1 ������� ������, ����� ������������� �������� ��
����� ���� �� ������������ ����� ����������, �� ������ ������� �� �������;
�� �� �����������  � ��� ������� "�������� �������". ����� ���� ��
����������� ������������ ������� "����", ��� ���� ������ �� ��� �����,
 ����� �������. ᅉ���, ������, ������� ������� � ������� ��� �����������
� ������ ������������� ������� "������ �����������".

��������� \emph{������� ������} � ����� � ��������� ����������, ��� ������
�� ��� ������, ������� ���� � ������������ ��������, �������---� ���������
������ � ������������ ��������---� ���������� ��������. ��������� "$*$" ���
����������� ������������� ��������, ����� ������� ������ �����
����������� � ���� ������������������ �����, ������ � ���������.
���������� ���� ��������, �������� ����� ����� ���������� ������� �
���������� �������, ����� ��� ������� �������� � ���� ��������, ���� �� ��
������, � �������� � ���� ���. �� ����� �������������� ����� ������:
$$
0 * * 0 * * * 1 * * * * * * * * * * * * * * * * * * * 0 * *
\eqno(4)
$$
%% 661
\picture{ ���� 1 䀉� � ��������� ����������}
%% 662
 ����~1 �������, ��� �� ����� ���� ��� ������� ������� ��������� �
�����������.

������ ��� ����������� ����� ������ ����������� �����  ��� ���������
������� ��������, ����� ������� ������� ������, ����� ������ �������
������ �� ������ � ���������.  ��
������ ����� ������� \emph{����������}, ��� �� ����������� ���;
������, ���������� � ���� ��������� ��������� ��������� (�����������
�������, ��� ������� ���������� ��������� �������, � ����---�������������).
 ��������, �� �������� ����.~1
\picture{���. 46.  ����� � ������� �����������.}
������ ������������� �������� ������� � ��������� �������� �������
�������� � �������� �������, � ������� ����.

��� ��������� ���������� ���������� ���������� ���� ������ �� ����������
�������. 풎 �����������, ��������, ��� ������ �������� ������ "�� ������
� ������� �����������" ��� "�������� ���������". ሑ���� �� ������ �
������� �����������, ��������������� ����.~1, ��������� �� �� ����� ��
������ ������, ��� ������� ����������� ������������� �����. (�.~���.~46.)
��� ��������� ����������� ������� ����� ���������� � ���������� ������ �
������ ����� � �������, ��������������� ��������� ���������. ����� �����
��������� � �����, ������� ������ ��������, ��������.

"��������� ���������" ���������� �������� � ��������������� ������. �
���� ������ ������� �� ����� �� ������ �������. ��� ������ ������ ��
������ ��������� ������������ �������, � ���� ������ �������� ���������
���������, �� � ��������������� ����� �������� ��������. ዅ����������,
������� $80\hbox{-��������}$ ���������� ����� ��������� ���������� �
$12\times80=960\hbox{~�������}$. ��� ��������� �����������
������� �������� ����� ������ ���������, ������ �� ������ � ������������;
%%663
\htable{ ���� 2}%
{������ ����������� ����������}%
{
#\bskip\hfill&\bskip$#$\bskip&#\bskip\hfill&\bskip$#$\bskip\cr
\noalign{\hbox{���� ��������� ������}}
��������           & 1000010000 & �������� ���      & 1000100000\cr
���������          & 0100000100 & ���               & 0000000011\cr
���������� �����   & 0000000101 & �������           & 1001000000\cr
������             & 0000100010 & ��������� ����    & 0000010010\cr
�������            & 0000001001 & ��������� "����"  & 0000010100\cr
�������� �����     & 0000100001 & �����             & 0000100100\cr
������������ ����� & 0000101000 & �����             & 0010000100\cr
����� �����        & 0000011000 & ጎ��������� ���� & 0010000001\cr
����               & 0101000000 & 䈍���            & 1000000100\cr
������             & 0000110000 & 戒���            & 0100000010\cr
��������           & 1000000001 & 煐������         & 0010000010\cr
��������� �����    & 0001010000 & 煑���            & 0001100000\cr
������             & 1000000010 & 莊����           & 0010001000\cr
����               & 0001000100 & 튑����� �������  & 0100000001\cr
�������� �����     & 0011000000 & ����� ����     & 0010010000\cr
\noalign{\hbox{���������� ����}}
��������-������� �������       &\span\span 1000111111\cr
��������-�������� ���������    &\span\span 0000101101\cr
��������� �������              &\span\span 0000001001\cr
������������� �������� ������� &\span\span 1001110010\cr
����������� �������            &\span\span 0010101101\cr
����� � ��������               &\span\span 0010101100\cr
������                         &\span\span 0010111101\cr
��������� ��������             &\span\span 1011100101\cr
������� �������                &\span\span 1011110111\cr
�������                        &\span\span 1000101100\cr
���������� ������� � ��������  &\span\span 0001111101\cr
���������� ����� � �����       &\span\span 0000100100\cr
��������� ������� �� ��������  &\span\span 1001110011\cr
������� ������� � ��������     &\span\span 1000100100\cr
������� ��������� � �����������&\span\span 0111110110\cr
������� � ���������� ������    &\span\span 0010001101\cr
������� � �������              &\span\span 1101010110\cr
������� � ������               &\span\span 1111111111\cr
������� � �������� ������      &\span\span 1111111111\cr
������� �� ��������� �����     &\span\span 0010001001\cr
����������� ����� � ��������   &\span\span 1011101101\cr
��������                       &\span\span 1000001011\cr
������� �������                &\span\span 0001111101\cr
�������������� �������� �������&\span\span 0011011000\cr
ᒀ������ �������� �������     &\span\span 0000011011\cr
䈃����� �������� �������      &\span\span 0000000000\cr
䈍���� �����                  &\span\span 0100100101\cr
%% 664
肅����� ��������                       &\span\span 0000000000\cr
肅�������� ��������� ������� � ������� &\span\span 1000000010\cr
莊������� �������                      &\span\span 0010101101\cr
莒�������� ������� �������             &\span\span 0000001001\cr
���                                  &\span\span 0000001001\cr
}%
���� ����� ������� ����� ��� �������, ��������������� �������
������� 풀 �������� ���������� ��������� ������� �������� �����
����������� ��������������� ������� �����.

\section ����������� ����������. ������� ������ ������� �������� � ������
���������� ������� � ���, ��� ���� ��������� ����� ���������� ��������
�������� ����� �� ������ � ������� �����������; ��� �� ������ �������� �
������������� ������ � ������ ���. ����������� ���������� ����������
�����������; � ���������������� ��� �������� �� ��������� ���
�� �������� �����������. ���� ������� � ���, ����� ���������� �������� �
��������� $k\hbox{-�������}$ ���� � $n\hbox{-�������}$ ����� � ��������
���� ��������� � ������ ���������. ���������� ������ � ��������� ���������
��������� ����� ������������� �� ���������� ������ � ���������������
���������� �������� �����. 풎�� ������� ����� ������������� ���������
������ �������, �� ���������� ����� "������ ���������"
����� ������������� ������. [�. � Calvin N.~Mooers,
{\sl Amer.~Chem.~Soc.~Meeting\/}, {\bf 112} (September, 1947), 14E--15E;
{\sl American Documentation,\/} {\bf 2} (1951), 20--32.]
� �������� ������� ����������� ���������� ����� ���������� ����.~1, ��
�� ���, � ������ �����, ���������� ������. � ����.~2 ��������, ���
���������, ���� ��������� ��������� ������ ��������� ����������� ���� �
������������� ���� � �������� ��. ��������, ������� "����������
�������" ���������� ���������� ����� ��� ��������, ������ � ��������:
$$
0010001000 \vee 0000100100 \vee 0000001001 = 0010101101.
$$
��������� ����� ��������� ����� ��������� ������ ���������, � ������
������ ��� �������� �����, ������������ �����, ������������ ����,
��������� ����� � �����, ��� �������� � "������ ����������" ��� ������� ��
��������� ������� (����� ����, � ��� �������� ����� ������---������� �������!)
�� ����� ���� ����������� ���������� �� ����� ������ �������� ��� ����.~2,
���������� ��������� �������� �� ���-
%%665
���� ����������. �������������, ������� � �������� ������ ����� ��������
��� \emph{������} �������, ��� ��� ������ �������� ���������� ���� �����,
����������� ��� ������ �������; ��� ���� ������� ���� � �������� � ������,
���������� ����������" ���������� �����! � ������ �������, � ���������
������� ����.~2 �������� ����������� ������; ��������, � ����� �� ������
� �������� ��� ������� ���� ������� � ������.

����� ���������� �������� ������, ����� � ��� ����, ������, 32-�������
���� � ��������� �� $\perm{32}{3}=4960$ ��������� ���������. ������ ������
����� ����� �� ����� ���������, � ������ ������� ���������� �������������
3-� �� 32-� �����. ���� �� �����������, ��� ������ ������ ����� �����
�������� ��������� ���������, �� ����������� ������� ��������� ���
���������� ������� ������:
$$
\matrix{
\hbox{�� ������ ��������:}\hfill   & 0.07948358; \cr
\hbox{�� ���� ���������:} \hfill   & 0.00708659;\cr
\hbox{�� ���� ���������:} \hfill   & 0.00067094;\cr
\hbox{�� ������� ���������:}\hfill & 0.00006786;\cr
\hbox{�� ���� ���������:} \hfill   & 0.00000728;\cr
\hbox{�� ����� ���������:}\hfill   & 0.00000082.\cr
}
\eqno(5)
$$
 �� �������, ���� ���� $M$~�������, �� ��������������� ������� �� ����
���������, �� �������������� $0.007M$ ����� ���������� ����, �����������
��� ���� ���� ���� ���������. (����������� ���������� � ���.~4.) ���
������������� ���������������� ����� ����������� $32\times
\hbox{(���������� �������)}$~�����, ��� ���������� ����� �������� �� �����
�����, ����������� ��� �������� ���������� ��������� � �������� �����.

���������~�.~倐����� [{\sl CACM,\/} {\bf 14} (1971), 777--779] �������,
��� ����������� ���������� ����� ������������ ��� ��������� ������ ������.
�����������, ��� ��� ����� ���������� ��� ��������� ��������� �������
����� � ������� ����� ��� ���������� ����������� ������ ��������.
�����������, ����� ����, ��� ����� ������� �� ������ $c_1$ $c_2$~\dots
$c_{50}$  �� 50~����� � ������. 倐����� ���������� ���������� ������ ��
49~��� $c_1$~$c_2$, $c_2$~$c_3$,~\dots, $c_{49}~c_{50}$ ����� �����������
�� � ����� ��~0 ��, ������,~127. ����� ���������� "���������" ������ $c_1$
$c_2$~\dots $c_{50}$---������� �� 128 ����� $b_0$ $b_1$~\dots $b_{127}$, ���
$b_i=1$ ����� � ������ �����, ����� $h(c_j, c_{j+1})=i$ ��� ���������~$j$.


���� ��� ����� ����� ��� ��������� ����� |������| � ������� ��������� ����
|�⮣ᥭ�|, �� ������ ���������� ��� ������, ��������� ������� ��������~1
� �������� $h(|��|)$, $h(|��|)$, $h(|��|)$, $h(|��|)$, $h(|KA|)$. ���
��������� ���-������� ����������� ����, ��� ��������� ��������� ������
�������� �
%%666
��������� ��� ��� �������, ����� ����� ���� 0.00341 (��.~�~���.~4);
�������������, ����������� ���� ��������������� ������� ������� �����
�������� ������ ����� ��� ������, ���������� ����� |������| (����,
��������, ����� � ��������� ������ ���������).

� ������ ���������� �������� � ����������� �� ����� ���� �������������,
��������� ������� ������ ����� � ���� ������� ���������� ����������
����������; ������������� ������������� ���������� � ������ ������
������������. ��������, ������� ��������� ��� ����~$c_j$~$c_{j+1}$,
���������� ������ "������", ��� ��� ������ ������� ����������� �������
���� ������ �����.

������ ���������� ���������� ����������� ���������� � ������� ������ �����
������ ���� [{\sl CACM,\/} {\bf 13} (1970), 422--426]; �� ����� ���� ���
����� ������������ ��� ������� �� \emph{���������} ������, �� ��� ������
�������� ��� � ���� ���������. ���������� ����, ��� ������������ ����� �
������� ������������ ������, ������, ���� �� �������� ���������, �������
�������� ��������� �� �����. ��������, �� ����� ��������� ���-���� �����
�������� ��� ����� ����������� ������� � �.~�.; � ���� � ����� ���
��������������� ����� ���� ������, �� ����������� ������������ ��
���������. ���������� ��� ���������� ��� ��� ������������� ������ �������
����� ��������� ������� ��������, ������� �������� ��������� ������
�������� ��� ����������� ����, �� ����� ���������� �
50000~������-�����������. ���� �����-���� ����� �� ������� ����� � �����
����������, ����� ������������ ���� ������� ��������.

� �������� �������� ����� ������� �� ���������� ������ ������� �����, ���
��� � ����������� ������� ���������� ����� ����� �������� ��� ���������
� ������� ������. ��� ��� ��� ��������. ��������� ���������� ������� �����
����� $b_0$~$b_1$~\dots~$b_{M-1}$, ��� $M$ ������ ������. ��� �������
�����~$K_j$ ����� �������� $k$ ����������� ���-������� $h_1(K_j)$,~\dots,
$h_k(K_j)$ � ��������� ��������������� $k$~����� �������~1. (품
$k$~�������� �� ������� ���� ����������.)  �� �������, $b_i=1$ ����� �
������ �����, ����� $h_l(K_j)=i$ ��� ���������~$j$ �~$l$. ⅏��� ��� ����,
����� ����������, ���������� �� �������� ������~$K$ �� ������� �����,
����� ������� ���������, ����������� �� ����������� $b_{h_l(K)}=1$ ���
$1\le l\le k$: ���� ���, �� ������� ���������� � ������� ������, ���� ��
��, �� ��� ���������� ������~$K$ �~$M$ �������� �������� ������ ���
������ ����� ������� �����~$K$. ����������� ������� ��������� ��� ����� ��
$N$~������� ����������� �����~$(1-e^{-kN/M})^k$. �� ��������, �
������ ����� ���� ���� ��������������� ��� ���� ������, ���������
%%667
����� ���������� ��� ��������� ��������, � ����������� ����������
������������ � �������� $M\hbox{-�������}$ ����.

��� ���� ������� ����������� ���������� � ����� ���������� �����������
���������� ������ ��������� (Univ. South Carolina, 1969). �����������,
������� $N$~������� � ������ �� ��� ��������~6 �� 10000~���������
���������. ��������, ������ ����� �� ��������� ����������� ������, �
��������---��������� � ��� �������� �����. ����� $h$---���-�������,
������������ ������ ������� � ����� �����~0 �~15. ���� ������
�������� ���������� $a_1$, $a_2$,~\dots, $a_6$, �� �� ������ ����������
��� ������������ � 16-������� ����� $b_0$~$b_1$\dots$b_{15}$, ��� $b_i=1$
����� � ������ �����, ����� $h(a_j)=i$ ��� ���������~$j$; �����, ���� ����
$k$~����� ����� ����������, $k<6$, �� ������ $6-k$~������ �����������
����� ��������� ������� (�� ����������� ��������� ��
����� �������). ������� $\perm{16}{9}=8008$ 16-������� �����, ����������
����� ����� ������; ��� ��������� ���� ������� ��������������
$N/8008$~������� ����������� � ������ ��������. ����� �������
8008~������� �������, � ������� ���������� ������� �������� �����,
��������������� ���� $b_0$~$b_1$\dots$b_{15}$. � ����� ����, ���� �������
����������� � �������� $0\le p_1<p_2<\ldots<p_6$, �������
$$
\perm{p_1}{1}+\perm{p_2}{2}+\cdots+\perm{p_6}{6}
$$
����������� ������ ������� $b_0$~$b_1$\dots$b_{15}$ � ����� �����~0 �~8007,
������ ������ ������� ��������� ������ ������. (�.~���.~1.2.6-56 �~2.2.6-7.)

���� ������ �� ����� ����� ��� ������, ������� ��� ������������ ��������
$A_1$, $A_2$, $A_3$, �� ������� ��������� $h(A_1)$, $h(A_2)$ �~$h(A_3)$;
���� ��� �������� ��������, ��� �������� ����������� ������, ���������� �
$\perm{13}{3}=286$~�������, ���� ������� $b_0$~$b_1$\dots$b_{15}$ ��������
������� � �������� $h(A_1)$, $h(A_2)$ �~$h(A_3)$. ����� �������,
������������ ������������ ���� $286\times100/8008\approx 3.5$\%~�������.

\section ������������� �����������. �������� ���� ������ ��� ����������
������ ���������� ������� � ���, ����� ����� ����� ������ �����������
������� � ������ ������, ����� ���� ��������� ���������� ������� ����
������� � ������������ ��������. ������ ���� ����� �������� ���� �
���������� ��������, ����� ��������� ������ �������� ����� ������
���������. ������ ��� �����������, ��������������� ��� ���������
������������ ������� �������� ����~(4), ��������� �� �����, ������ �
���������, ������ � 1971~�. ������� �������.

����������� �������, ��� ������� 1000000~������� � ������ �� ���
�������� 10 ��������� ������, ������ ������ ���������
%%668
���� ����� ��������� �������� ����� ��������� ��������. ������ ��
���������� ������� ($K_1$, $K_2$,~\dots, $K_{10}$) ����� ���������� �
20-������� �����
$$
h(K_1) h(K_2) \ldots h(K_{10}),
\eqno(6)
$$
��� $h$---���-�������, ������������� ��������� ���� � 2-������� �����, �
(6) ���������� ���������������� ������������ ���� ������ ��� �����. ���
����� ����� 1000000~������� ������������ � ��������� ��
$2^{20}=1048576$~��������; ��� ����������� ����� ������������� ���
���-������� �~$M=2^{20}$. ��� ���������� �������� ������������� �������
�������. ���� �� ����� ������� ��� ������, ������� ������������
�������� ���� ��������� ������, ��� �������� ����������� ����
$2^{10}$~������� [��������������� ���� ������������������� ����� � (6)],
�.~�.~� ������� ����� ��������� ����� $1000=\sqrt{N}$~�������.
[����������� ������ ��������� �������, {\sl J.~Inf.~Proc.~Soc.~Japan,\/}
{\bf 12} (1971), 163--167.]

������� ������ ��� ���� ������, ��� ��� �� ������ ������� �� �����
��������� ��������. �����������, ���������� $N\approx2^n$~������� � ������
�� ��� �������� $m$~��������� ������. ������ ������������ �
$n\hbox{-�������}$ ���-������ ����� �������, ��� ������, ��
��������������� �������� $k$~������, ����������� ��������
$N^{k/m}$~�������. ��� ��������� ������������� � ���� ��������� ������
(����� ������ ����������) ������� ��� ������� ���������� ������� $N$~�����
(������, ����������� ������������������ �������); ��� ����������
�������~$N$ ����� �������� �������� ����� �������, � ���� �� �� ��
������� �������������� ������.

��, ������ ��� ��������� ����� ������, ����� ���������� ����������
�����������. ���������� ������ � ���������� ���������� ����������, �����
$m=4$ �~$n=3$, � ��� ��������� ����� ����� ��������� ���� ��� ��������;
��������� 4-������� ������ � ������ ������� ��������� �������:
$$
\matrix{
*&0&0&0&\to& 1\cr
*&1&1&1&\to& 2\cr
0&*&0&1&\to& 3\cr
1&*&1&0&\to& 4\cr
}
\qquad
\matrix{
0&1&*&0&\to& 5\cr
1&0&*&1&\to& 6\cr
0&0&1&*&\to& 7\cr
1&1&0&*&\to& 8\cr
}
\eqno(7)
$$
������������ ���� ������� ����������, ��� ��� ������, ���������������
�������~$0***$, ������������ � ���� ������� 1, 2, 3, 5 �~7; � ������
\emph{�����} ������� ������ � ����� ����������� ����������� ����� ����
�������. ������� ������ � ����� ����������� ����������� ��� ������, �,
�������, ������� ������ � ����� ���������� ����������� ���� ����, ����
���, � � ������� $(8\times1+24\times2)/32=1.75$~������.  �� �������, �����
%%669
{\def\hdr#1{\vbox{\dimen255=\hsize\divide\dimen255 by 3\hsize=\dimen255\leftskip=0pt plus 1fill\rightskip=0pt plus 1fill\noindent #1\par}}
$$
\matrix{
\hdr{���������� ������������������� \goodbreak ����� � �������} & \hdr{���������� ������������� \goodbreak �������}\cr
4 & 8 = 8^{4/4}\cr
3& 5\approx 8^{3/4}\cr
2& 3\approx 8^{2/4}\cr
1& 1.75\approx 8^{1/4}\cr
0& 1= 8^{0/4}\cr
}
\eqno(8)
$$
}

����������, ��� ���� ��������� ������; ������� ��������� ������� �����
������������ ��� ������ ���������. �� �� ������� � ��� �������������
����������, ����� $m=4r$ �~$n=3r$, ���� $4r\hbox{-�������}$ ������ �����
���������� �
$2^{3r}\approx N$~�������, �������� ��������� ����� �� $r$~����� �� ������
���� � ������ � ��������~(7) � ������ ������. ������������ �����������
�������� ��������� ���������: \dfn{������, ����������� $k$ �� $m$~�����
��������������������, �������� �������� $N^{k/m}$~�������}. (�.~���.~6.)

��������� ������ �����������, ��������� ���������, ���������� � ���.~7;
�� ����� ������������ ������ �~(7) ��� ��������� ������� ��������������
����������� � ������ $1\le m/n \le 2$. �� ����� ���� ����� ���� ��
������������ ����� �������~$b$ � ��������~$N \approx 2^n b$; �� �����
$b=1$ ��� �������� ���������.

\section *၀������������� �������� �������. ������ ������������� ������ �
������ ������� ����������, ���������� �� "�������� ����������������
�������� �����", ������ ��������� �������������� ������������. 厒� ��
����� ��������� � �������������� ����� ������, ����� ������������
�������� ���� �����, � ���������, ��� �� �������. 璎�� ���� ��������
����������� ������������� ��������� �����������, �� ��� �� �������
����� ������� �������� � ������, �� ����� �������, ��� ���-������ ������
�� ������������ ����������.

\emph{蒅���������� �������� �����} ���������� ����� �������������
$v$~�������� � ��������������� ������, ����� ������ ���� ��������
����������� ����� � ����� ������. ��������, ���� $v=7$, �������, ��
��������, ���� ������������� ������� �����, � ������
$$
\matrix{
\hbox{␎���} & \hbox{ᎄ��������� � ��� ����}\span \span \span\cr
\set{1,2,4} & \set{1,2}, & \set{1,4}, & \set{2,4}\cr
\set{2,3,5} & \set{2,3}, & \set{2,5}, & \set{3,6}\cr
\set{3,4,6} & \set{3,4}, & \set{3,6}, & \set{4,6}\cr
\set{4,5,0} & \set{0,4}, & \set{0,5}, & \set{4,5}\cr
\set{5,6,1} & \set{1,5}, & \set{1,6}, & \set{5,6}\cr
\set{6,0,2} & \set{0,2}, & \set{0,6}, & \set{2,6}\cr
\set{0,1,3}  & \set{0,1}, & \set{0,3}, & \set{1,8}\cr
}
$$
%%670
��������� ���������� ${1\over2}v(v-1)$~��� ��������, � � ������---���
����, ����� ����� ����� �����~${1\over6}v(v-1)$; ��������� ������ ������
����� ���������� ���� ����� � $v-1$ ������� ���������, �� ������
�������������� ����� � ${1\over2}(v-1)$~�������. �� ���� �����������
�������, ��� ������� 蒅����� ���������� ���� �����, ����� �����
${1\over6}v(v-1)$ �~${1\over2}(v-1)$ �����. ������,
$v$ ������ ���� �������� � ��� ������� ��~3 �� ������ � ������� 2, �.~�.
$$
v \bmod 6 =1\hbox{ ��� } 3.
\eqno(10)
$$
�������, � 1847~�.~������� �������, ���, ���� $v\ge1$ � ���������
�������~(10), ������������� ������� ����� ������������� ����������. ���
���������� ����������� ��������� � ���.~10.

蒅���������� ������� ����� ����� ������������ ��� ���������� ������������
� ��������������� ��������������� ������. ���������� ����� ���� ��������
������� (����.~1) � ����������� ������ ������� � 31-�~�������, �������
�����~1, ���� ��������� ����������� ����������, �~0 � ���������
������. �����������, �� ����� �������� �� ��� ���������� ������� � �����
���������, �������� �� ������ "� ����� �������� ������������ � ���������
�����, � ����?" ����� ���� �� ��������� ��������������� ������ ��� �������
�� $\perm{31}{2}=465$~��������� ��������. ������ ��� ������ ������ �����
�����, ���������, ��������, ������� � ������ ����� ����������� �
$\perm{17}{2}=136$ �� ���, � ������, ���������� ����� ����������,
������ � ������ ������! ������������� ������� ����� 蒅����� ���������
�������� ��������. ��� 31~������� ���������� ������� 蒅����� ��
155~�����, ������ ������ ���� �������� ������ ����� � ���� ������. ������
������~$\set{a, b, c}$ ����� ����������� ������ ������: ���� ������---���
�������, ���������� ���������� $a$, $b$, $\bar c$ (�.~�.~��~$c$);
������---��� $a$, $\bar b$, $c$; ������---��� $\bar a$, $b$, $c$;
���������---��� $a$, $b$, $c$.  �� ����������� �����������, ��� �������
������ �� ������� ����� ��� � 155~��������������� �������, � ��������
������������, ���� ������ ����� ��� ��������, ��������������� ������ �������.

ሑ���� ����� �������� ������� ������� ������ �����, ��������� �� ����
��� ����� ��������. ��������, 31~������ ����� ��� ������������ ��
��������������� ���������, ��� ������ ���� �������� ������� ����� � ���� ��������:
%%671
{\def\sset#1{\scriptstyle\set{#1}\hfill}
$$\matrix{
\sset{1,  5, 17, 22, 23, 25} &\sset{ 7, 11, 23, 28, 29, 0} &\sset{13, 17, 26, 3,  4,  6} &\sset{20, 24,  5, 10, 11, 13} &\sset{26, 30, 11, 16, 17, 19}\cr
\sset{2,  6, 18, 23, 24, 26} &\sset{ 8, 12, 24, 29, 30, 1} &\sset{14, 18, 30, 4,  5,  7} &\sset{21, 25,  6, 11, 12, 14} &\sset{27,  0, 12, 17, 18, 20}\cr
\sset{3,  7, 19, 24, 25, 27} &\sset{ 9, 13, 25, 30,  0, 2} &\sset{15, 19,  0, 5,  6,  8} &\sset{22, 26,  7, 12, 13, 15} &\sset{28,  1, 13, 18, 19, 21}\cr
\sset{4,  8, 20, 25, 26, 28} &\sset{10, 14, 26,  0,  1, 3} &\sset{16, 20,  1, 6,  7,  9} &\sset{23, 27,  8, 13, 14, 16} &\sset{29,  2, 14, 19, 20, 22}\cr
\sset{5,  9, 21, 26, 27, 29} &\sset{11, 15, 27,  1,  2, 4} &\sset{17, 21,  2, 7,  8, 10} &\sset{24, 28,  9, 14, 15, 17} &\sset{30,  3, 15, 20, 21, 23}\cr
\sset{6, 10, 22, 27, 28, 30} &\sset{12, 16, 28,  2,  3, 5} &\sset{18, 22,  3, 8,  9, 11} &\sset{25, 29, 10, 15, 16, 18} &\sset{ 0,  4, 16, 21, 22, 24}\cr
                             &                             &\sset{19, 23,  4, 9, 10, 12} \cr
}
$$
}
[풀 ������� ���������� �� ������ ������ ����� �������� �� ������~31. ���
�������� ����, ��� ��� �������� ��������� ���������, �������, ���
30~��������~$(a_i-a_j)\bmod 31$, $i\ne j$, ��������, ����
$(a_1, a_2, ~\ldots, a_6)=(1, 5, 17, 22, 23, 25)$. 璎�� ����� ��������,
���������� ������ ����~$(x, y)$, ������� $i$ �~$j$ ���, ���
$a_i-a_j\equiv x-y \pmod{31}$; ���� $k=(x-a_i) \bmod 31$, ��
$(a_i+k) \bmod31=x$ �~$(a_j+k)\bmod31=y$.]

ሑ����~(11) ����� ������������ ��� �������� ��������������� �������,
������ �� ���� ������ �� �������� ����� 31~����. ������
��������~$\set{a, b, c, d, e, f}$ ������������ 57~�������,
��������������� ��� �������,
������� ��� ��� ����� �������� $a$, $b$, $c$, $d$, $e$ ���~$f$,
�.~�.~������� �������� $(a, b, \bar c, \bar d, \bar e, \bar f)$,
$(a, \bar b, c, \bar d, \bar e, f)$,~\dots,
$(a, b, c, d, e, f)$; ������� �� ����� ���������� ������ �� ���� ���������
�������� ����������� ��� ����������� 16~���������� ������� ����������
��������. ������� � ������ ������ �~29 �� 31~������ ���� �������,
��������� ��������� ����� ����� ��� �� ����� ��������� �� ���� ���������,
 ����� $\set{19, 23, 4, 9, 10, 12}$
�~$\set{13, 17, 29, 3, 4, 6}$ (���� �� ���������� ������� ������� ��~0 ��~30).

����������� ���� ��������� ��� ���������� ������������ � ���������
��������������� �������, ����� �� ����� �������� �� �������, � �� ��
���������� �������. �����������, ��������, ��� ������ �������� ����
��������� ������ $K_1$, $K_2$, $K_3$, $K_4$, $K_5$, ������ �� �������
����� ��������� ���� �� ������� ��������~0, 1, 2 ���~3. 璎�� ��������
�� ������ � �������, ��� ������� $K_i=a$ �~$K_j=b$ ��� ������ $a$, $b$
�~$i\ne j$, �� ����� �� ���������� ��������������� ������ ��� ����
160~�������� ��������; � ����� ������ ������ ������ �������������� ��
� ������ ��������������� �������. ������������� �������� �������������
��������� ������� ������������� �������, ���������� �� �������������
�����, ������� ���������� "������� ������������� ��������� ��������":
$$
\matrix{
(0, 0, 0, 0, 0) & (1, 0, 1, 2, 3) & (2, 0, 2, 3, 1) & (3, 0, 3, 1, 2) \cr
(0,1,1,1,1) & (1,1,0,3,2) & (2,1,3,2,0) & (3,1,2,0,3)\cr
(0,2,2,2,2) & (1,2,3,0,1) & (2,2,0,1,3) & (3,2,1,3,0)\cr
(0,3,3,3,3) & (1,3,2,1,0) & (2, 3,1,0,2) & (3,3,0,2,1)\cr
}
$$
���� �� ������ ��������� �� ����� ��� �� ���� ���������, �� ������, ���
��� 16~��������� ������������� ��� ��������
%%672
����������� � ���� �������� ����� ���� ���. ������ ($a$, $b$, $c$, $d$,
$e$) ���� ������� ����� ����������� ������, ��������������� �� �������
���� ���� �� ������� $K_1=a$, $K_2=b$,~\dots, $K_5=e$.  �� �������,
������ �� 16~����� ����� ������������ 376 ��~1024 ��������� �������,
������� ������� ������������
����������� �~ 0 ��~$16\times 376/1024 =5{7\over8}$.

ⅎ��� ������ ����� ����� � ��������� ��������� �������� ����������� �
"����� Marshall Hall, Jr., Combinatorial Theory (Waltham; Mass.: Blaisdell,
 1967). �������� �� ��� ������� ����� ����� ����, � ������� �������
���������� �� ������� ������������ ���� ��� ���������� ������������ ���
���������� ��������� ��������������� �������; ����� 熎� [{\sl
Information and Control,\/} {\bf 15} (1969), 377--396] �������, ��� ����
�� ���������� ����� ������� � ��� ������������� ������.

\section ������� ������� � ������������. ������ �������������� ������ �
������� ������� �� ��������� ������ �������� �. ��������� [{\sl CACM,\/}
{\bf 4} (1961), 218--222]. �������������� ������� �������� � ���� � �� ��
����� ���������� ����������� ��� ������, X.~����, �.~��������, �.~��������
� �.~������; ��.~� [{\sl IEEE Trans.~on Communication and Electronics,\/}
{\bf 68} (1963), 488--492]. ������ �������� ������ ����������,
��������� ������� �� ����������� ������, ����������� �.~�.~������ �
�.~�.~���� [{\sl CACM,\/} {\bf 8} (1965), 243--246].

� �������� ����������, ����������� � ��� ��� �� ����� �������, ��������
�������� ��������� �������������� � �������������� � ������
����������������, �� ���� ��� ��� ����� ����� �� ��������. � ����������
� ��� ������������� ������� ����� ��������������� ���������
�������������� ������, ��������� ������ ���������� ������
���-��������� ����� ���������: Jack Minker, Jerome Sable, {\sl
Ann.~Rev.~of Information Science and Technology,\/} {\sl 2} (1967),
123--160; Robert E.~Bleier, Proc.~ACM~Nat.~Conf., {\bf 22} (1967), 41--49;
Jerome A.~Feldman, Paul D.~Rovner, {\sl CACM,\/} {\bf 12} (1969),
439--449; Burton H.~Bloom, Proc.~ACM~Nat.~Conf., {\bf 24} (1969), 83--95;
H.~S.~Heaps, L.~H.~Thiel, {\sl Information Storage and Retrieval,\/} {\bf
6} (1970), 137--153;
Vincent Y.~Lum, Huei Ling, Proc.~ACM~Nat.~Conf., {\bf 26} (1971), 349--356.
 厐���� ����� ������ �������� ������ � ��.~5 ����� ����� Methods of
Information Handling (New York: Wiley, 1963). "၀������������� ��������
�������" ������� ����������� �������, �.~���� � �.~���-玓����� � 1965~�.;
�������, ������ ������ ���� ������ � ������������ �������� ������
���� �.~���� � ���� ��� [{\sl SIAM, J.~Appl.~Math.,\/} {\bf 17} (1969), 1203--1214].

� ��������� ��������� �� �������� �������� ����� ���������� ����,
�������� � ����� ������ ���������. ���������
%% 673
������ �� ���� ������� ��������� ��������� �� ��������� �������
���������, �� ����� ������, ��������, �� �������� ���� �����.

��������� ��������, ��� ������������ ���� ��������� ������� �� ���������
������ ������� �����, ��� ���; � ����� ����, �� �������� ����� ����������
���� ��� ������� �~�.~�.\ �� ���������� ����������, � �� ����� ��� ������,
�������, ������ �� � ��������� ������� ���. � ��� ������ ������������ �
���, ��� ������� ����� ������ ������������� ����� ������ � ���������������
�����, ������� ��� � �������� ����� ������ ������� �� ��������� ������,
������ ��� ����� ���� ���� �������� ��������.

\excercises
\rex[�27] ����� $0\le k \le {1\over2}n$. ��������, ��� ���������
���������� ����
$\perm{n}{k}$~������������ �����~$\set{1, 2,~\ldots, n}$, �����, ���
������ $t\hbox{-����������}$ ������������ ���������~$\set{1, 2,~\dots, n}$
��� $t\le k$ ���~$t\ge n-k$ ����������� �� ������� ���� ���� ��� �
�������� ������ $t$~��������� ������������. ���������� ���� �� ���������
�� �����~$(0, 0)$ �~$(n, r)$, ��� $r\ge n-2k$, � ������� $i\hbox{-�}$~���
������������ �� �����~$(i-1, j$) �~$(i, j+1)$ ��� �~$(i, j-1)$;
��������� ����������� ������� ���� ���~$j\ge 1$, ������� ���� ������� �� ����������
���� ���~$x$. ᓙ������� ����� $\perm{n}{k}$ ����� �����. ������������,
��������������� ��������� ����, �������� � �������������� ����
������������� ������ ������� ��������� �������: ���� $i\hbox{-�}$~���
�������� �����, $i=1$, 2,~\dots, $n$, �� �����~$i$ ���������� �
������~$B$; ���� �� ����, �� $i$~���������� � ������~$A$, � ������������
�� ������ ������ ������� ������~$B$ ��������� �� ���� � ����������� �
������~$C$. ����� ����� �������� ���� �� ������ �������� �������~$A$, $B$
(� ������������ �������) �~$C$ (����� � ������������ �������). ����������
������������ ���������.

��������, ��� $n=4$ �~$k=2$ ���������� ����� ����� � ��������������� ��
������������
\picture{���. ���. 673}
(������������ ����� ��������� ������~$A$, $B$ �~$C$. 품 �����
������������ ������������� ��������� ��������� �~(2).)

[\emph{㊀�����.} ����������� ������ $t\hbox{-����������}$
������������~$S$ � ������� ���� ��~$(0, 0)$ �~$ (n, n-2t)$,
$i\hbox{-�}$~��� �������� ����������� ��~$(i-1, j)$ �
$(i, j+1)$, ���� $i\notin S$, � �~$(i, j-1)$, ���� $i\in S$. ������������
������ ����� ���� � ���� ���������� ���� ����.]

\ex[�25] (ည�� ����.) ������� ���������� ��������� �����~$l$ ������ $r_1$
$r_2$~\dots $r_l$ ������ �� ������, ����������� ��� ���������, ��� ���
������ �� ����� �� ���������� �������� $* * 1$, $* 1 *$, $1* *$, $* 1 1$,
$1*1$, $11*$, $1 1 1$ �� ���� ������ � ����� ���������� ����������
�������� � ����������������
���������~$r_i~\ldots r_j$.
%%674

\ex[19] ���������� ����.~2. ����� ���������� ������� �������
������ ���������: (a)~���������� ��������� �������; (b)~������� �������
� ��������?

\ex[M30] ������� ������ ������� ��� ������������~(5), �����������, ���
������ ������ ����� � ��������� ���������, �������� ����������
��~$\perm{n}{k}$ $k\hbox{-�������}$ ����� � $n\hbox{-�������}$ ����, � ���
������ �������� $q$~���������, � � ��������� ��������� ���������. (��
���������, ���� ������� �� ����� ����������!)

\ex[40] ������������������� � ���������� ��������� ����������
������������ � �������, ���� ��� ������ ���������� ������������ �����
倐������.

\rex[�20] ����� ����� $m\hbox{-�������}$ �������� � $k$~������������������
������ ����� $s=\perm{m}{k}2^k$. ���� ������������� ���-�������,
��������~(7), ����������� ��� ������� � ������ $l_1$, $l_2$,~\dots, $l_s$
��������������, �� $L(k)=(l_1+l_2+\cdots+l_s)/s$ ���� ������� �����
�������, ������������ �� ������. [��������, �~(7) ����� $L(3)=1.75$.]

���������� ������ ��������� ���-������� ��� $(m_1+m_2)\hbox{-�������}$
�����, ������������ ������������ ������ $m_1$~����� � ������� �����
���-�������, � ���������� $m_2$~�����---� ������� ������. ����� $L_1(k)$
�~$L_2(k)$---��������������� ������� ���������� �������, ������������ ��
������. ������� �������, ����������~$L(k)$ (������� ��� ��������� �������)
�����~$L_1$ �~$L_2$.

\ex[M24] (�.~�������.) ������� �������� �������~$L(k)$, ������������ �
���������� ����������, ��� ��������� ������� �������������� �����������:
$$
{\hbox{(a) $m=3$, $n=2$}
\atop
\matrix{
0&0&*&\to&1\cr
1&*&0&\to&2\cr
*&1&1&\to&3\cr
1&0&1&\to&4\cr
0&1&0&\to&4\cr
}
}
\qquad
{\hbox{(a) $m=4$, $n=2$}
\atop
\matrix{
0&0&*&*\to&1\cr
*&1&*&0\to&2\cr
*&1&1&1\to&3\cr
1&0&1&*\to&3\cr
*&1&0&1\to&4\cr
1&0&0&*\to&4\cr
}
}
$$

\ex[�47] ���������� ����� �������� ������ �������
�������������� �����������, �����������~(7).

\ex[�20] ��������, ��� ��� $v=3^n$ ��������� ���� ����� ����
$$
\set{ (a_1\ldots a_{k-1} 0 b_1\ldots b_{n-k})_3, (a_1\ldots
a_{k-1}1c_1\ldots c_{n-k})_3,
(a_1\ldots a_{k-1} 2 d_1\ldots d_{n-k})_3}, 1\le k\le n,
$$
�������� ������������� ������� �����. ��������������, ��� $a_i$, $b_i$,
$c_i$ �~$d_i$ ����� 0, 1 ���~2 �~$b_i+c_i+d_i\equiv 0 \pmod{3}$.

\ex[�32] (⎌�� ������� [{\sl Cambridge and Dublin Math~ Journal,\/}
{\bf 2} (1847), 191--204].) ������� �������� ����� �������� �������~$v$ �����
����������� $v+1$~�������� $\set{x_0, x_1,~\ldots, x_v}$ � ������, ���
������ ����~$\set{x_i, x_j}$, $i\ne j$, ����������� ����� � ����� ������;
���������� ���������� $v$~��� $\set{ x_i, x_{(i+1)\bmod v}}$, $0\le i<v$,
�� ������������� �� � ����� ������. ��������,
$$
\set{x_0, x_2, x_4}, \set{x_1, x_3, x_4}
$$
�������� �������� ����� �������� �������~4.

\item{a)}~��������, ��� ������� ����� �������� ����� ������������
������ ���~$v\bmod 6= 0$ ���~4.
%%675
\item{b)}~���� ������������� ������� �����~$S$ ��� $v$~���������
$\set{x_1,~\ldots, x_v}$.
��������, ��� ��������� ���������� �������� � �������������
������� �����~$S'$ ��� $2v+1$~��������� � ������������� ������� �����~$K'$
������� $2v-2$: � $S'$ ������ ��� ������ �� $S$ ����
\itemitem{i)} $\set{x_i, y_j, y_k}$, ��� $j+k\equiv i \pmod{v}$ �~$j<k$,
$1\le i, j, k\le v$;
\itemitem{ii)} $\set{x_i, y_j, z}$, ��� $2j\equiv i \pmod{v}$, $1\le i,
j\le v$.
� �������~$K'$ ������ ��� ������~$S'$, �� ���������� $y_1$ �/���~$y_v$.

\item{c)} ���� ������������� ������� �����~$K$ ��� ���������
$\set{x_0, x_1,~\ldots, x_v}$, ���~$v=2u$. ��������, ��� ���������
���������� �������� � ������������� ������� �����~$S'$ ���
$2v+1$~��������� � ������������� ������� �����~$K'$ �������~$2v-2$: � $S'$
������ ��� ������ �� $K$ ����
\itemitem{i)}~$\set{x_i, x_{(i+1)\bmod v}, y_{i+1}}$, $ 0\le i <v$;
\itemitem{ii)}~$\set{x_i, y_j, y_k}$,.$j+k\equiv 2i+1 \pmod{v-1}$, $1\le j <k-1 \le v-2$, $1\le i \le v-2$;
\itemitem{iii)}~$\set{x_i, y_j, y_v}$, $2j\equiv 2i+1 \pmod{v-1}$, $1\le j \le v-1$, $1\le i \le v-2$;
\itemitem{iv)}~$\set{x_0, y_{2j}, y_{2j+1}}$, $\set{x_{v-1}, y_{2j-1}, y_{2j}}$, $\set{x_v, y_j, y_{v-j}}$, $1\le j <u$;
\itemitem{v)}~$\set{x_v, y_u, y_v}$.
� $K'$ ������ ��� ������ �� $S'$, �� ���������� $y_1$ �/��� $y_{v-1}$.

\item{d)}~����������� ���������� ���������� ��� �������������� ����,
��� ������������� ������� ����� �������~$v$ ���������� ��� ����� $v\ge0$,
������� ��� $6k$ ���~$6k+4$, � ������������� ������� ����� ���
$v$~��������� ���������� ��� ����� $v\ge1$, ������� ���~$6k+1$ ���~$6k+3$.

\ex[�25] � ������ ������� ������������� ������������� ������� ����� �
����� � ����������� ���������; ����� ������������ �� � ���
������� ��������, ����������� ������ ��������� �������. \dfn{�����������
�������� �����} �������~$v$ ���������� ����� ����������� $2v$~��������
$\set{x_1,~\ldots, x_v, \bar x_1,~\ldots., \bar x_v}$ � ������, ��� ������
���� �������� ����������� ����� � ����� ������; ���������� ���������� ����
�������������� ���������~$\set{x_i, \bar x_i}$, �� �������� �� � ����
������. ��������,
$$
\set{x_1, x_2, x_3},\quad, \set{x_1, \bar x_2, \bar x_3},\quad
\set{\bar x_1, x_2, \bar x_3}, \quad \set{\bar x_1, \bar x_2, x_3}
$$
���� ����������� ������� ����� �������~3.

��������, ��� ����������� ������� ����� �������~$v$ ���������� ���
������~$v\ge0$, �� �������� ����~$3k+2$.

\ex[�23] � ����������� ���.~11 ��������� ����������� �������
\emph{��������} �������~7.

\ex[�25] ��������� ������� ��������, ���������� $v=4^n$~���������,
 ����������� ������� ����� �� ���.~9.

\ex[25] �������� ������ �������� ����� �� �������� ��������, ��������
������������� �� ���.~45.

%%676

\bye
