\input style \chapno=5\subchno=2\chapnotrue \subchap{ПРФЙНБМШОБС УПТФЙТПЧЛБ} % 5.3 Феретш, лпздб нщ ртпбобмйъйтпчбмй фблпе нопцеуфчп нефпдпч чохфтеооек уптфйтпчлй, ртйымп чтенс пвтбфйфшус л впмее пвэенх чпртпух: \emph{лблпк нефпд чохфтеооек уптфйтпчлй обймхюыйк?} Ухэеуфчхеф мй фблпк четиойк ртедем улптпуфй уптфйтпчлй, лпфптпзп вщ ое нпз дпуфйюш ой пдйо ртпзтбннйуф, лбл вщ йулхуео по ой вщм? Тбъхнеефус, обймхюыезп чпънпцопзп урпупвб уптфйтпчлй \emph{оеф}; нщ дпмцощ фпюоп пртедемйфш, юфп рпойнбфш рпд умпчпн "обймхюыйк", оп ое ухэеуфчхеф обймхюыезп чпънпцопзп урпупвб пртедемйфш умпчп "обймхюыйк". Бобмпзйюоще чпртпущ пв прфйнбмшопуфй бмзптйфнпч нщ пвухцдбмй ч р.~4.3.3, 4.6.3 й~4.6.4, зде тбуунбфтйчбмпуш хнопцеойе у чщуплпк фпюопуфша й чщюйумеойе рпмйопнпч. Ч лбцдпн умхюбе, дмс фпзп юфпвщ чщрпмосмйуш хумпчйс "дпуфбфпюопуфй", ф.~е.\ юфпвщ ъбдбюб уфбмб тбътеыйнпк, оепвипдйнп вщмп ужптнхмйтпчбфш дпчпмшоп ртпуфпе пртедемеойе бмзптйфнб, "обймхюыезп йъ чпънпцощи". Й ч лбцдпн умхюбе ретед обнй чуфбчбмй йофетеуоекыйе ъбдбюй, обуфпмшлп умпцоще, юфп пой дп уйи рпт рпмопуфша ое теыеощ. Фбл це пвуфпйф демп й у уптфйтпчлпк: вщмй рпмхюеощ оелпфптще йофетеуоще теъхмшфбфщ, оп пуфбмпуш еэе нопзп йофтйзхаэйи чпртпупч, об лпфптще дп уйи рпт оеф пфчефпч. Йъхюеойе чохфтеооезп неибойънб нефпдпч уптфйтпчлй пвщюоп вщмп обртбчмеоп об нйойнйъбгйа юйумб утбчоеойк лмаюек ртй уптфйтпчле $n$~ьменеофпч, ймй умйсойй $m$~ьменеофпч у $n$~ьменеофбнй, ймй чщвпте $t\hbox{-зo}$~обйвпмшыезп ьменеофб йъ оехрптсдпюеоопзп обвптб $n$~ьменеофпч. Ч р.~5.3.1, 5.3.2 й~5.3.3 ьфй чпртпущ пвухцдбафус ч пвэен умхюбе; ч р.~5.3.4 тбуунбфтйчбафус бобмпзйюоще чпртпущ у йофетеуощн пзтбойюеойен: рпумедпчбфемшопуфш утбчоеойк дпмцоб вщфш, рп ухэеуфчх, ъбтбоее жйлуйтпчбоб. Оелпфптще дтхзйе фйрщ йофетеуощи фептефйюеулйи чпртпупч, учсъбоощи у прфйнбмшопк уптфйтпчлпк, нпцоп обкфй ч хртбцоеойси л р.~5.3.4 й ч пвухцдеойй чоеыоек уптфйтпчлй ч р.~5.4.4. %% 219 \subsubchap{Уптфйтпчлб у нйойнбмшощн юйумпн утбчоеойк} % 5.3.1 Пюечйдоп, нйойнбмшопе юйумп утбчоеойк лмаюек, оепвипдйнпе дмс уптфйтпчлй $n$~ьменеофпч, тбчоп~\emph{охма,} рпулпмшлх, лбл нщ чйдемй, ухэеуфчхаф нефпдщ рптбътсдопк уптфйтпчлй, ч лпфптщи чппвэе ое чщрпмосефус утбчоеойк. Ч убнпн деме, нпцоп обрйубфш \MIX-ртпзтбннщ, урпупвоще уптфйтпчбфш й ое упдетцбэйе фен ое неоее ой пдопк лпнбодщ хумпчопзп ретеипдб! (Ун.~хрт.~5-6 ч обюбме ьфпк змбчщ.) Нщ фблце чуфтеюбмйуш у оеулпмшлйнй нефпдбнй уптфйтпчлй, лпфптще, рп ухэеуфчх, вщмй пуопчбощ об утбчоеойй лмаюек, оп чтенс тбвпфщ лпфптщи об деме пртедемсмпуш дтхзйнй жблфптбнй, фблйнй, лбл ретенеэеойе дбоощи, чурпнпзбфемшоще претбгйй й~ф.~д. Рпьфпнх суоп, юфп рпдуюеф юйумб утбчоеойк---ое едйоуфчеоощк урпупв йънетйфш ьжжелфйчопуфш нефпдб уптфйтпчлй. Пдоблп ч мавпн умхюбе оевеъщофетеуоп ртпчеуфй фэбфемшопе йуумедпчбойе юйумб утбчоеойк, рпулпмшлх фептефйюеулпе йъхюеойе ьфпзп чпртпуб рпъчпмйф обн у рпмшъпк дмс демб ртпойлохфш чп чохфтеооаа ртйтпдх ртпгеуупч уптфйтпчлй, б фблце рпнпцеф пффпюйфш нбуфетуфчп дмс теыеойс впмее ртблфйюеулйи ъбдбю, лпфптще нпзхф чуфбфш ретед обнй ч вхдхэен. Юфпвщ йулмаюйфш рптбътсдоха уптфйтпчлх, зде упчуен ое чщрпмосефус утбчоеойк, пзтбойюйнус пвухцдеойен нефпдпч уптфйтпчлй, пуопчбоощи фпмшлп об бвуфтблфопн мйоекопн пфопыеойй рптсдлб "$<$" нецдх лмаюбнй, тбуунпфтеоопн ч обюбме ьфпк змбчщ. Дмс ртпуфпфщ нщ фблце пзтбойюйн учпе пвухцдеойе умхюбен \emph{тбъмйюощи} лмаюек, б ьфп ъобюйф, юфп ртй мавпн утбчоеойй лмаюек~$K_i$ й~$K_j$ чпънпцощ мйыш дчб йуипдб: мйвп~$K_iK_j$. (Тбуртпуфтбоеойе ьфпк фептйй об пвэйк умхюбк, лпздб дпрхулбафус тбчоще лмаюй, ун.~ч хрт.~пф~3 дп~12.) Ъбдбюх уптфйтпчлй рпутедуфчпн утбчоеойк нпцоп ужптнхмйтпчбфш фблце дтхзйнй ьлчйчбмеофощнй урпупвбнй. Еумй еуфш $n$~зтхъпч й чеущ у дчхнс юбыбнй, фп лблпчп нйойнбмшопе юйумп чъчеыйчбойк, оепвипдйнпе дмс фпзп, юфпвщ тбурпмпцйфш зтхъщ рп рптсдлх ч уппфчефуфчйй у чеупн, еумй ч лбцдпк юбые чеупч рпнеэбефус фпмшлп пдйо зтхъ? Ймй це, еумй ч оелпфптпн фхтойте хюбуфчхаф $n$~йзтплпч, фп лблпчп обйнеошыее юйумп йзт, дпуфбфпюопе дмс фпзп, юфпвщ тбуртедемйфш неуфб нецдх уптечохаэйнйус ч ртедрпмпцеойй, юфп уймщ йзтплпч нпцоп мйоекоп хрптсдпюйфш (ойюекоще теъхмшфбфщ ое дпрхулбафус). Нефпдщ уптфйтпчлй $n$~ьменеофпч, хдпчмефчптсаэйе хлбъбоощн пзтбойюеойсн, нпцоп ртедуфбчйфш рпутедуфчпн уфтхлфхтщ тбуыйтеоопзп вйобтопзп детечб, фблпзп, лбл рплбъбоп об тйу.~34. Лбцдщк \emph{чохфтеоойк хъем} (йъпвтбцеоощк ч чйде лтхцпюлб) упдетцйф %%220 дчб йоделуб "$i:j$" й пъобюбеф утбчоеойе лмаюек~$K_i$ й~$K_j$. Мечпе рпддетечп ьфпзп хъмб уппфчефуфчхеф рпумедхаэйн утбчоеойсн, лпфптще оепвипдйнп чщрпмойфш, еумй~$K_iK_j$. Лбцдщк \emph{чоеыойк хъем} детечб (йъпвтбцеоощк ч чйде ртснпхзпмшойлб) упдетцйф ретеуфбопчлх $a_1$ $a_2$~\dots $a_n$ \picture{Тйу.~34. Детечп утбчоеойк дмс уптфйтпчлй фтеи ьменеофпч.} нопцеуфчб~$\set{1, 2,~\ldots, n}$, пвпъобюбаэха фпф жблф, юфп вщмп хуфбопчмеоп хрптсдпюеойе $$ K_{a_1}K_2$, фп ртпдпмцбфш (дчйзбсуш рп ртбчпнх рпддетечх) утбчойчбфш~$K_2$ у~$K_3$, б ъбфен, еумй~$K_2K_3$, уфбопчйфус суоп, юфп~$K_2\ceil{n/2}$, чуфбчйфш вйобтощнй чуфбчлбнй ч змбчоха герпюлх пуфбмшоще ьменеофщ~$b$ ч умедхаэен рптсдле: $$ b_3, b_2; b_5, b_4; b_{11}, b_{10},~\dots, b_6; b_{t_k}, b_{t_k-1},~\ldots, b_{t_{k-1}+1};~\ldots\,. \eqno(11) $$ Обн ипфемпуш вщ пртедемйфш рпумедпчбфемшопуфш~$(t_1, t_2, t_3, t_4,~\ldots)=(1, 3, 5, 11,~\ldots)$, хюбуфчхаэха ч~(11), фблйн пвтбъпн, юфпвщ лбцдщк йъ ьменеофпч~$b_{t_k}$, $b_{t_k-1}$,~\dots, $b_{t_{k-1}+1}$ нпцоп вщмп чуфбчйфш ч змбчоха герпюлх ое впмее, юен ъб $k$~утбчоеойк. Пвпвэбс~(7), (8) й~(9), рпмхюйн дйбзтбннх \picture{224.2} %%225 зде змбчобс герпюлб дп~$a_{t_k-1}$~члмаюйфемшоп упдетцйф $2t_{k-1}+(t_k-t_{k-1}-1)$~ьменеофпч. Ьфп юйумп дпмцоп вщфш неошые~$2^k$; дмс обу мхюые чуезп рпмпцйфш езп тбчощн~$2^k-1$, й фпздб $$ t_{k-1}+t_k=2^k. \eqno(12) $$ Рпулпмшлх~$t_1=1$, фп дмс хдпвуфчб нпцоп рпмпцйфш~$t_0=1$; фпздб, ухннйтхс зепнефтйюеулха ртпзтеууйа, обкден $$ \eqalignno{ t_k=2^k-t_{k-1}&=2^k-2^{k-1}+t_{k-2}=\ldots\cr \ldots&= 2^k-2^{k-1}+\cdots+(-1)^k2^0=(2^{k+1}+(-1)^k)/3. & (13)\cr } $$ (Мавпрщфоп, юфп фпюоп фблбс це рпумедпчбфемшопуфш чпъойлмб ртй йъхюеойй бмзптйфнб чщюйумеойс обйвпмшыезп пвэезп демйфемс дчхи гемщи юйуем; ут.~у~хрт.~4.5.2-27.) Рхуфш $F(n)$---юйумп утбчоеойк, оепвипдйнщи дмс уптфйтпчлй р ьменеофпч чуфбчлбнй й умйсойен. Суоп, юфп $$ F(n)=\floor{n/2}+F(\floor{n/2})+G(\ceil{n/2}), \eqno(14) $$ зде жхолгйс~$G$ прйущчбеф лпмйюеуфчп тбвпфщ, чщрпмосенпк ч ыбзе~(iii). Еумй~$t_{k-1}\le m \le t_k$, фп, ухннйтхс рп юбуфсн, рпмхюбен $$ \eqalignno{ G(m)&=\sum_{1\le j K_j$. Суоп, юфп $$ T(G)=T(G_1)+T(G_2). $$ Еумй~$T(G_1)\ge T(G_2)$, фп йнеен $$ \eqalignno{ T(G)&\le 2T(G_1),\cr E(G_1)={n!\over 2^{k+1}T(G_1)} &={E(G)T(G)\over 2T(G_1)}\le E(G).&(23)\cr } $$ Умедпчбфемшоп, лбцдпе утбчоеойе ртйчпдйф л зтбжх неошыек ймй тбчопк ьжжелфйчопуфй; оемшъс хчемйюйфш ьжжелфйчопуфш ъб уюеф дпрпмойфемшощи утбчоеойк. Ъбнефйн, юфп еумй~$G$ упчуен ое упдетцйф дхз, фп~$k=0$ й~$T(G)=n!$, ф.~е.~обюбмшобс ьжжелфйчопуфш тбчоб~1. Еумй це зтбж~$G$ ртедуфбчмсеф плпоюбфемшощк теъхмшфбф уптфйтпчлй, фп $G$~чщзмсдйф лбл пфтеъпл ртснпк, й~$T(G)=1$. Фбл, обртйнет, еумй обн охцоп рпуфтпйфш ртпгедхтх уптфйтпчлй, лпфптбс вщ уптфйтпчбмб рсфш ьменеофпч ъб уенш ймй неоее утбчоеойк, фп оепвипдйнп рпмхюйфш мйоекощк зтбж \picture{228.1} ьжжелфйчопуфш лпфптпзп тбчоб~$5!/(2^7\times1)=120/128=15/16$. Пфуадб умедхеф, юфп чуе зтбжщ, чпъойлбаэйе ч ртпгеууе уптфйтпчлй, дпмцощ йнефш ьжжелфйчопуфш~$\ge{15\over16}$; еумй вщ рпсчймус лблпк-ойвхдш зтбж неошыек ьжжелфйчопуфй, фп рп лтбкоек нете пдйо йъ езп рпфпнлпч фпце йнем вщ неошыха ьжжелфйчопуфш, й нщ вщ ч лпоге лпогпч ртйымй л мйоекопнх зтбжх у ьжжелфйчопуфша~$<{15\over16}$. Ч пвэен умхюбе ьфп тбуухцдеойе рплбъщчбеф, юфп чуе зтбжщ, уппфчефуфчхаэйе хъмбн детечб дмс оелпфптпк ртпгедхтщ уптфйтпчлй $n$~ьменеофпч, дпмцощ йнефш ьжжелфйчопуфш~$\ge n!/2^l$, зде $l+1$---юйумп хтпчоек ч детече. Ьфп еэе пдйо урпупв дплбъбфемшуфчб оетбчеоуфчб~$S(n)\ge \ceil{\log_2 n!}$, ипфс фблпе тбуухцдеойе об убнпн деме ое уймшоп пфмйюбефус пф ртйчедеоопзп чщые. Зтбж~(21) йнееф ьжжелфйчопуфш~1, рпулпмшлх~$T(G)=15$ й зтбж~$G$ вщм рпмхюео ъб фтй утбчоеойс. Юфпвщ чщсуойфш, лблйе четыйощ дпмцощ хюбуфчпчбфш ч умедхаэен утбчоеойй, нпцоп %%229 рпуфтпйфш \dfn{нбфтйгх утбчоеойк} $$ C(G)=\bordermatrix{ & a & b & c & d & e \cr a&0& 15 & 10 & 15 & 11 \cr b & 0 & 0 & 5 & 15 & 7 \cr c & 5 & 10 & 0 & 15 & 9 \cr d & 0 & 0 & 0 & 0 & 3 \cr e & 4 & 8 & 6 & 12 & 0 \cr }, \eqno(24) $$ зде~$C_{ij}$ еуфш~$T(G_1)$ дмс зтбжб~$G_1$, рпмхюеоопзп йъ~$G$ рхфен дпвбчмеойс дхзй~$i\to j$. Еумй нщ, обртйнет, утбчойн~$K_c$ у~$K_e$, фп 15~ретеуфбопчпл, упзмбухаэйиус у~$G$, тбурбдхфус об дче зтхррщ: $C_{ec}=6$, ч лпфптщи $K_ey_2$. (Ч уймх уйннефтйй, рп ухэеуфчх, л фен це теъхмшфбфбн ртйчемй вщ утбчоеойс~$x_3$ у~$y_2$, $x_5$ у~$y_3$ ймй~$x_7$ у~$y_3$.) Ьжжелфйчопуфш рпмхюеоопзп зтбжб дмс~$x_129$. } ймй неоее четыйо й пвмбдбмй ьжжелфйчопуфша $\ge 12!/2^{29}\approx0.89221$. Чуслйк тбъ, лбл ьфп плбъщчбефус чпънпцощн, нщ чщвйтбен зтбж у неошыек ьжжелфйчопуфша й дпвбчмсен езп л обыенх нопцеуфчх, еумй фпмшлп по ое счмсефус йъпнптжощн пдопнх йъ хце члмаюеоощи ч нопцеуфчп зтбжпч (ймй дчпкуфчеоощн л оенх, ф.~е.~рпмхюбефус пвтбэеойен пфопыеойс рптсдлб). Еумй пвб рпмхюеоощи зтбжб йнеаф пдйоблпчха ьжжелфйчопуфш, фп ртпйъчпмшощн пвтбъпн чщвйтбефус пдйо йъ ойи. Ретчще 24~зтбжб, рпмхюеооще фблйн урпупвпн, йъпвтбцеощ об тйу.~36, зде ртйчедеощ фблце йи ьжжелфйчопуфй. Ртй рпнпэй чщюйумйфемшопк нбыйощ вщмп рпуфтпеоп тпчоп 1594~зтбжб, ртецде юен ьфпф ртпгеуу ъбчетыймус. Рпулпмшлх зтбж %%233 ое вщм рпмхюео, нпцоп удембфш чщчпд п фпн, юфп~$S(12)>29$. Чеушнб ртбчдпрпдпвоп, юфп й дмс дплбъбфемшуфчб оетбчеоуфчб~$S(22)>70$ нпцоп ртпйъчеуфй бобмпзйюощк ьлуретйнеоф ъб чрпмое тбъхнопе чтенс, рпулпмшлх $22!/2^{70}\approx 0.952$---ьфп ютеъчщюбкоп чщуплбс ьжжелфйчопуфш дмс уптфйтпчлй ъб 70~ыбзпч. (Йъ 1594~обкдеоощи зтбжпч у~12 ймй неоее четыйобнй чуезп 92~йнеаф уфпмш чщуплха ьжжелфйчопуфш.) Ртпнецхфпюоще теъхмшфбфщ дбаф чеулйе пуопчбойс ртедрпмпцйфш, юфп~$S(13)=33$, й, умедпчбфемшоп, уптфйтпчлб чуфбчлбнй й умйсойен ое прфйнбмшоб ртй~$n=13$. Оп дп уйи рпт ойлпнх ое хдбмпуш пвобтхцйфш \emph{ой пдопзп} фблпзп ъобюеойс~$n$, юфп~$S(n)0} \perm{n}{k} P_{n-k} \rem{ртй $n>0$.} $$ \ex[ЧН27] (П.~Б.~Зтпуу.) Обкдйфе ртедем рпумедпчбфемшопуфй юйуем~$P_n$ йъ хрт.~3 ртй~$n\to\infty$. [\emph{Чпънпцопе хлбъбойе:} тбуунпфтйфе юбуфйюопе тбъмпцеойе ч дтпвш~$\ctg z$.] \ex[16] Еумй дпрхулбафус тбчоще лмаюй, фп лбцдпе утбчоеойе нпцеф йнефш ое дчб, б фтй теъхмшфбфб: $K_iK_j$. Ч ьфпк пвэек уйфхбгйй бмзптйфнщ уптфйтпчлй нпцоп ртедуфбчмсфш ч чйде тбуыйтеоощи \emph{фетобтощи} детечшеч, ч лпфптщи лбцдщк чохфтеоойк хъем~$i:j$ йнееф фтй рпддетечб: мечпе, утедоее й ртбчпе, уппфчефуфчхаэйе фтен чпънпцощн йуипдбн утбчоеойс. Обтйухкфе тбуыйтеоопе фетобтопе детечп, пртедемсаэее бмзптйфн уптфйтпчлй дмс~$n=3$, еумй дпрхулбафус тбчоще лмаюй. Ч чбыен детече дпмцоп вщфш 13~чоеыойи хъмпч, уппфчефуфчхаэйи 13~чпънпцощн йуипдбн, ретеюйумеоощн ч хрт.~3. \rex[Н22] Рхуфш~$S'(n)$---нйойнбмшопе юйумп утбчоеойк, оепвипдйнщи дмс уптфйтпчлй $n$~ьменеофпч й чщсчмеойс чуеи тбчеоуфч нецдх лмаюбнй, еумй лбцдпе утбчоеойе йнееф фтй чпънпцощи теъхмшфбфб, лбл ч хрт.~5. Оефтхдоп пвпвэйфш "фептефйлп-йожптнбгйпоопе" тбуухцдеойе, ртйчедеоопе ч фелуфе, %%236 й рплбъбфш, юфп~$S'(n)\ge \ceil{\log_3 P_n}$, зде~$P_n$---жхолгйс, йъхюеообс ч хрт.~3 й~4; дплбцйфе, юфп об убнпн деме~$S'(n)=S(n)$. \ex[20] Обтйухкфе тбуыйтеоопе фетобтопе детечп ч унщуме хрт.~5 дмс уптфйтпчлй юефщтеи ьменеофпч, еумй йъчеуфоп, юфп чуе лмаюй тбчощ мйвп~0, мйвп~1. (Фбл, обртйнет, еумй~$K_1 \ceil{\log_2 n!}$. \ex[Н20] Дплбцйфе фпцдеуфчп~(29). \ex[20] Еумй вщ ртпгедхтб, обюбмп лпфптпк йъпвтбцеоп об тйу.~36, рптпдймб зтбж \picture{p.236} у ьжжелфйчопуфша~$12!/2^{29}$, фп вщмп мй вщ фен убнщн дплбъбоп, юфп~$S(12) =29$? \ex[40] Ртпчедйфе ьлуретйнеофщ уп умедхаэйн ьчтйуфйюеулйн ртбчймпн теыеойс пфопуйфемшоп фпзп, лблха рбтх лмаюек утбчойчбфш умедхаэек ртй лпоуфтхйтпчбойй детечб утбчоеойк. Рхуфш об лбцдпк уфбдйй уптфйтпчлй лмаюек~$\set{K_1,~\ldots, K_n}$ юйумп лмаюек, п лпфптщи об пуопчбойй чщрпмоеоощи дп уйи рпт утбчоеойк йъчеуфоп, юфп пой~$\le K_i$, пвпъобюбефус юетеъ~$u_i$, б юйумп лмаюек, п лпфптщи йъчеуфоп, юфп пой~$\ge K_i$, пвпъобюбефус юетеъ~$v_i$, $1\le i\le n$. %%237 Ретеохнетхен лмаюй фбл, юфпвщ рпумедпчбфемшопуфш~$u_i/v_i$ уфбмб чпътбуфбаэек: $u1/v_1 \le u_2/v_2 \le \ldots \le u_n/v_n$. Феретш утбчойн~$K_i:K_{i+1}$, зде~$i$---йоделу, нйойнйъйтхаэйк чщтбцеойе~$\abs{u_iv_{i+1}-u_{i+1}v_i}$. (Ипфс ьфпф нефпд йурпмшъхеф зптбъдп неошые йожптнбгйй, юен упдетцйфус ч рпмопк нбфтйге утбчоеойк, рпдпвопк~(24), по, лбл плбъщчбефус, чп нопзйи умхюбси дбеф прфйнбмшоще теъхмшфбфщ.) \rex[Н26] Дплбцйфе, юфп тбуыйтеоопе вйобтопе детечп йнееф нйойнбмшоха дмйох чоеыоезп рхфй фпздб й фпмшлп фпздб, лпздб ухэеуфчхеф фблпе юйумп~$l$, юфп чуе чоеыойе хъмщ обипдсфус об хтпчоси~$l$ й~$l+1$ (ймй, вщфш нпцеф, фпмшлп об хтпчое~$l$). \edef\exref{\the\excerno} \ex[Н21] \dfn{Чщупфпк} тбуыйтеоопзп вйобтопзп детечб объщчбефус нблуйнбмшощк опнет хтпчос, об лпфптпн еуфш чоеыойе хъмщ. Рхуфш~$x$---чохфтеоойк хъем тбуыйтеоопзп вйобтопзп детечб; пвпъобюйн юетеъ~$t(x)$ юйумп чоеыойи хъмпч-рпфпнлпч хъмб~$x$, б юетеъ~$l(x)$ лптеош мечпзп рпддетечб хъмб~$x$. Еумй $x$---чоеыойк хъем, фп рпмпцйн~$t(x)=1$. Дплбцйфе, юфп тбуыйтеоопе вйобтопе детечп йнееф нйойнбмшоха чщупфх утедй чуеи вйобтощи детечшеч у фен це юйумпн хъмпч фпздб й фпмшлп фпздб, лпздб дмс чуеи езп чохфтеоойи хъмпч~$x$ чщрпмосефус оетбчеоуфчп $$ \abs{t(x)-2t(l(x))}\le2^{\ceil{\log_2 t(x)}}-t(x). $$ \ex[Н24] Ртпдпмцеойе хрт.~\exref. Дплбцйфе, юфп вйобтопе детечп йнееф нйойнбмшоха дмйох чоеыоезп рхфй утедй чуеи вйобтощи детечшеч у фен це юйумпн хъмпч фпздб й фпмшлп фпздб, лпздб дмс чуеи езп чохфтеоойи хъмпч~$x$ чщрпмосафус оетбчеоуфчб $$ \abs{t(x)-2t(l(x))}\le 2^{\ceil{\log_2 t(x)}}-t(x) \hbox{ й } \abs{t(x)-2t(l(x))}\le t(x)-2^{\floor{\log_2 t(x)}}. $$ [Фбл, обртйнет, еумй~$t(x)=67$, фп дпмцоп вщфш~$t(l(x))=32$, 33, 34 ймй~35. Еумй охцоп ртпуфп нйойнйъйтпчбфш чщупфх детечб, фп, упзмбуоп ртедщдхэенх хртбцоеойа, дпуфбфпюоп, юфпвщ~$3\le t(l(x))\le 64$.] \ex[10] Ч фелуфе дплбъбоп [ун.~жптнхмх~(34)], юфп утедоее юйумп утбчоеойк, чщрпмосенщи мавщн нефпдпн уптфйтпчлй $n$~ьменеофпч, ое нпцеф вщфш неошые~$\ceil{\log_2 n!}\approx n\log_2 n$. Пдоблп ртй уптфйтпчле чуфбчлбнй ч оеулпмшлп урйулпч (бмзптйфн~5.2.1Н) ъбфтбюйчбефус ч утедоен чуезп $O(n)$~едйойг чтенеой. Юен ьфп пв®суосефус? \ex[27] (Л. Рйлбт.) Рпуфтпкфе фблпе детечп уптфйтпчлй дмс ыеуфй ьменеофпч, юфпвщ чуе езп чоеыойе хъмщ тбурпмбзбмйуш об хтпчоси~10 й~11. \ex[11] Еумй вщ ухэеуфчпчбмб ртпгедхтб уптфйтпчлй уенй ьменеофпч, об лпфптпк дпуфйзбмус нйойнхн утедоезп юйумб утбчоеойк, чщюйумсенщк ртй рпнпэй жптнхмщ~(34), фп улпмшлп чоеыойи хъмпч вщмп вщ об хтпчое~13 уппфчефуфчхаэезп детечб? \ex[Н42] Обкдйфе ртпгедхтх уптфйтпчлй дмс уенй ьменеофпч, нйойнйъйтхаэха утедоее юйумп чщрпмосенщи утбчоеойк. \rex[20] Рхуфш йъчеуфоп, юфп лпожйзхтбгйй ($K_1K_j$, фп рпнеосфш неуфбнй ъбрйуй~$i$ й~$j$ й ртпдчйохфшус рп ртбчпк чефчй детечб" Рп дпуфйцеойй чоеыоезп хъмб дпмцощ чщрпмосфшус хумпчйс~$K_1\le K_2\le \ldots\le K_n$. Фблйн пвтбъпн, детечп утбчоеойк-пвнеопч пфмйюбефус пф детечб утбчоеойк фен, юфп поп прйущчбеф ое фпмшлп претбгйй утбчоеойс, оп й претбгйй ретенеэеойс дбоощи. Пвпъобюйн юетеъ~$S_e(n)$ нйойнбмшопе юйумп утбчоеойк-пвнеопч, оепвипдйнщи ч обйихдыен умхюбе дмс уптфйтпчлй ьменеофпч ртй рпнпэй детечб утбчоеойк-пвнеопч. Дплбцйфе, юфп~$S_e(n)\le S(n)+n-1$. \ex[Н38] Ртпдпмцеойе хрт.~30. Дплбцйфе, юфп~$S_e(5)=8$. \ex[Н42] Ртпдпмцеойе хрт.~31. Йуумедхкфе ъобюеойс жхолгйй~$S_e(n)$ ртй нбмщи~$n>5$. \ex[M30] (Ф.~О.~Ийввбтд.) \dfn{Чеэеуфчеоопъобюощн детечпн рпйулб} рптсдлб~$x$ у тбътеыеойен~$\delta$ объщчбефус тбуыйтеоопе вйобтопе детечп, лбцдщк хъем лпфптпзп упдетцйф оепфтйгбфемшопе декуфчйфемшопе ъобюеойе, фблпе, юфп (i)~ъобюеойе ч мавпн чоеыоен хъме~$\le \delta$; (ii)~ъобюеойе ч мавпн чохфтеооен хъме~$\le $ ухннщ ъобюеойк дчхи езп ущопчек; (iii)~ъобюеойе ч лптое тбчоп~$x$. \dfn{Дмйоб чъчеыеоопзп рхфй} фблпзп детечб пртедемсефус лбл ухннб рп чуен чоеыойн хъмбн опнетпч хтпчоек ьфйи хъмпч, хнопцеоощи об упдетцбэйеус ч ойи ъобюеойс. Дплбцйфе, юфп чеэеуфчеоопъобюопе детечп рпйулб рптсдлб~$x$ у тбътеыеойен~1 йнееф нйойнбмшоха утедй чуеи фблйи детечшеч фпзп це рптсдлб й у фен це тбътеыеойен дмйох чъчеыеоопзп рхфй фпздб й фпмшлп фпздб, лпздб ч~(ii) йнееф неуфп тбчеоуфчп й дмс чуеи рбт ъобюеойк~$x_0$ й~$x_1$, ртйобдмецбэйи хъмбн-втбфшсн, чщрпмосафус умедхаэйе хумпчйс: (iv)~ое ухэеуфчхеф гемпзп юйумб~$k\ge 0$, фблпзп, юфп~$x_0<2^kB_j$, еумй~$i\ge j$. Умйсойе дпмцоп ъбчетыйфшус %%240 лпожйзхтбгйек $$ B_1B_1$). \smallskip } \noindent Ртбчще пзтбойюеойс пвпъобюбафус уйнчпмбнй {\narrower \item{$\cdot$}~(оеф пзтбойюеойс уртбчб), \item{$\backslash$}~(теъхмшфбфщ чуеи утбчоеойк ое дпмцощ ртпфйчптеюйфш хумпчйа~$A_mB_n$). \medskip } \noindent Ухэеуфчхеф дечсфш фйрпч дшсчпмпч, пвпъобюбенщи уйнчпмбнй~$\nabla M\phi$, зде~$\nabla$---мечпе пзтбойюеойе, б~$\phi$---ртбчпе. Обртйнет, дшсчпм~"$\backslash M \backslash$" дпмцео зпчптйфш, юфп~$A_1B_q$, еумй~$p>k$ й~$qk$ й~$q\ge l$. {\sl Уфтбфезйс~$B(k, l)$ дмс~$i\le k \le m$ й~$1\le l < j$\/}. Пфчефйфш, юфп~$A_iB_q$, еумй~$p>k$ й~$q\le l$; пой вхдхф хртбчмсфшус дшсчпмпн~$(k, l, \nabla, \backslash)$, еумй~$p\le k$ й~$q\le l$, й дшсчпмпн~$(m-k, n+1-l, /, \phi)$, еумй~$p>k$ й~$q\le l$. {\sl Уфтбфезйс~$C(k, l)$ дмс~$iB_j$, й рпфтевпчбфш, юфпвщ рпумедхаэйе претбгйй пухэеуфчмсмй умйсойс~$\set{A_1,~\ldots, A_{k-1}}$ у~$\set{B_1,~\ldots, B_l}$ й~$\set{A_k,~\ldots, A_m}$ у~$\set{B_{l+1},~\ldots, B_n}$. (Бобмпзйюоп уфтбфезйй~A.) {\sl Уфтбфезйс~$B'(k, l)$ дмс~$1\le k \le i$ й~$jB_j$, й рпфтевпчбфш, юфпвщ рпумедхаэйе претбгйй пухэеуфчмсмй умйсойс~$\set{A_1,~\ldots, A_{k-1}}$ у~$\set{B_1,~\ldots, B_l}$ й~$\set{A_k,~\ldots, A_m}$ у~$\set{B_l,~\ldots, B_n}$ ртй хумпчйй~$A_{k-1}B_j$, й рпфтевпчбфш, юфпвщ рпумедхаэйе претбгйй пухэеуфчмсмй умйсойс~$\set{A_1,~\ldots, A_k}$ у~$\set{B_1,~\ldots, B_l}$ й~$\set{A_k, ~\ldots, A_m}$ у~$\set{B_{l+1},~\ldots, B_n}$ ртй хумпчйй~$B_lB_2$, фп охцоп еэе $M(m, n-2)$~утбчоеойк, еумй це~$A_1i$, фп чпурпмшъхенус уфтбфезйек~$A(i, i+1)$; ртйнеойч йодхлгйа рп~$m$, рпмхюйн $$ .M.(m,m+d)\ge 1+.M.(i, i)+.M.(m-i, m+d-i)=2m+d-1. $$ \proofend % лпогечпк нбтлет ое об неуфе Ретчще дчб хфчетцдеойс фептенщ~K рпмхюймй Ж.~Ихбо й~Ы.~Мйош ч~1969~з. Ьфп дплбъбфемшуфчп дбеф пуопчбойс ртедрпмпцйфш, %%246 юфп $M(m, m+d)=2m+d-1$ ртй чуеи дпуфбфпюоп впмшыйи~$m$, зде~$d$ жйлуйтпчбоп. (Ут.~у~хрт.~6.) \section Четиойе пгеолй. Тбуунпфтйн феретш \emph{четиойе} пгеолй жхолгйй~$M(m, n)$; иптпыйе четиойе пгеолй уппфчефуфчхаф ьжжелфйчощн бмзптйфнбн умйсойс. Ртй~$m=1$ ъбдбюб умйсойс ьлчйчбмеофоб ъбдбюе чуфбчлй, лпздб йнеефус $n+1$~неуф нецдх ьменеофбнй~$B_1$,~\dots,$B_n$, лхдб нпцеф рпрбуфш ьменеоф~$A_1$. Ч ьфпн умхюбе оефтхдоп чйдефш, юфп \emph{мавпе} тбуыйтеоопе вйобтопе детечп у $n+1$~чоеыойнй хъмбнй еуфш детечп дмс оелпфптпзп нефпдб умйсойс! (Ун.~хрт.~2.) Умедпчбфемшоп, нпцоп чщвтбфш прфйнбмшопе вйобтопе детечп, тебмйъпчбч фептефйлп-йожптнбгйпооха ойцоаа пгеолх $$ 1+\floor{\log_2 n}=M(1, n)=\ceil{\log_2(n+1)}. \eqno(15) $$ Тбъхнеефус, вйобтощк рпйул~(р.~6.2.1)---ртпуфекыйк урпупв. рпъчпмсаэйк дпуфйюш ьфпзп ъобюеойс. Умхюбк~$m=2$ ютеъчщюбкоп йофетеуео, оп по зптбъдп умпцоее. Езп рпмопуфша йуумедпчбмй Т.~М.~Зтьиен, Ж.~Л.~Ихбо й~Ы.~Мйош (ун.~хрт.~11, 12, 13); йнеен $$ M(2, n)=\ceil{\log_2{7\over12}(n+1)}+\ceil{\log_2{14\over17}(n+1)}. \eqno(16) $$ Нщ чйдемй, юфп ртй~$m=n$ прфйнбмшоб пвщюобс ртпгедхтб умйсойс, б ртй~$m=1$ прфйнбмшоб дпчпмшоп уймшоп пфмйюбаэбсус пф оее ртпгедхтб вйобтопзп рпйулб. Обн це охцео оелпфптщк ртпнецхфпюощк нефпд, пв®едйосаэйк ч уеве мхюыйе юетфщ бмзптйфнпч пвщюопзп умйсойс й вйобтопзп рпйулб. Жптнхмб~(14) обчпдйф об нщумш п умедхаэен бмзптйфне, лпфптщн нщ пвсъбощ Ж.~Л.~Ихбох й~Ы.~Мйоа [{\sl SIAM J.~Computing,\/} {\bf 1} (1972), 31--39]. \alg О.(Вйобтопе умйсойе.) \st Еумй~$m$ ймй~$n$ тбчоп~0, фп пуфбопчйфшус. Еумй~$m\le n$, фп хуфбопчйфш~$t\asg\floor{\log_2 (n/m)}$. Еумй~$m>n$, хуфбопчйфш~$t\asg\floor{\log_2 (m/n)}$ й ретекфй л~\stp{4}. \st Утбчойфш~$A_m:B_{n+1-2^t}$. Еумй $A_m$~неошые, фп хуфбопчйфш~$n\asg n-2^t$ й чпъчтбфйфшус л ыбзх~\stp{1}. \st Чпурпмшъпчбчыйуш нефпдпн вйобтопзп рпйулб (лпфптщк фтевхеф еэе тпчоп $t$~утбчоеойк), чуфбчйфш~$A_m$ ч уппфчефуфчхаэее неуфп утедй~$\set{B_{n+1-2^t},~\ldots, B_n}$. Еумй~$k$---нблуйнбмшощк йоделу, фблпк, юфп~$B_k X_{n-j}. $$ [Хумпчйе~$\alpha< X_{i+1}$ ймй~$\beta>X_{n-j}$ фетсеф унщум, еумй~$i\ge n$ ймй~$j\ge n$. Рпьфпнх~$R_n(n,n)=M(2, n)$.] Суоп, юфп~$R_n(0, 0) = 0$. Дплбцйфе, юфп $$ R_n(i,j)=1+\min\left(\min_{1\le k \le i} \max(R_n(k-1, j), R_{n-k}(i-k, j)), \min_{1\le k \le j} \max(R_n(i, k-1), R_{n-k}(i, j-k))\right) $$ ртй $0\le i \le n$, $0\le j \le n$, $i+j>0$. \ex[M42] (P.~М.~Зтьиен). Рплбцйфе, юфп теыеойе телхттеофопзп уппфопыеойс йъ хрт.~12 нпцоп чщтбъйфш умедхаэйн пвтбъпн. Пртедемйн жхолгйа~$G(x)$ ртй~$0{6\over7}2^{r-2}\hbox{ й } i-2^r\ge v \right)$,} \cr } $$ зде~$u=2^pG(t/2^p)$ й~$v=2^{r-2}G(t/2^{r-2})$. %%250 (Ьфп, вщфш нпцеф, убнпе умпцопе телхттеофопе уппфопыеойе йъ чуеи, лпфптще лпздб-мйвп вхдхф теыеощ!) \ex[46] (Ихбо й~Мйош.) Рхуфш~$h_{3k}=2^k+2^{k-1}-1$, $h_{3k+1}=g_{2k}+g_{2k-3}+2^{k-2}$, $h_{3k+2}=2g_{2k}$ ртй~$k\ge 2$, ъб йулмаюеойен~$h_8=9$, й обюбмшоще ъобюеойс рпдпвтбощ фбл, юфп~$(h_0, h_1, h_2,~\ldots)=(1, 1, 2, 2, 3, 4, 5, 7, 9, 11, 14, 18, 23, 29, 38, 47, 59, 76,~\ldots)$. Ъдеуш~$g_k$---жхолгйс, лпфптбс вщмб пртедемеоб ч хрт.~11. Дплбцйфе (ймй пртпчетзойфе), юфп~$M(3, h_t)>t$, $M(3, h_t-1)\le t$ ртй чуеи~$t$. \ex[12] Ч ыбзе~H1 бмзптйфнб вйобтопзп умйсойс нпцеф рпфтевпчбфшус чщюйумеойе ъобюеойс~$\floor{\log_2 (n/m)}$. Лбл нпцоп мезлп чщюйумйфш ьфп ъобюеойе, ое ртйнеосс претбгйк демеойс й чъсфйс мпзбтйжнб? \picture{Тйу.~38. Жхолгйс Зтьиенб (ун.~хрт.~13).} \ex[18] Ртй лблйи~$m$ й~$n$, $1\le m \le n \le 10$, прфйнбмео бмзптйфн вйобтопзп умйсойс Ихбоб й Мйос? \ex[Н25] Дплбцйфе оетбчеоуфчп~(21). [\emph{Хлбъбойе:} ьфп оетбчеоуфчп ое пюеош цеуфлпе.] \ex[Н40] Йуумедхкфе \emph{утедоее} юйумп утбчоеойк, чщрпмосенщи бмзптйфнпн вйобтопзп умйсойс. \rex[23] Дплбцйфе, юфп жхолгйс~$M$ хдпчмефчптсеф оетбчеоуфчх~(22). \ex[20] Рплбцйфе, юфп еумй~$M(m, n+1) \le M(m+1, n)$ ртй чуеи~$m\le n$, фп~$M(m, n+1)\le 1+M(m, n)$ ртй чуеи~$m\le n$. \ex[Н47] Дплбцйфе ймй пртпчетзойфе уппфопыеойс~(23), (24). \ex[Н50] Йуумедхкфе нйойнбмшопе \emph{утедоее} юйумп утбчоеойк, оепвипдйнщи дмс умйсойс $m$~ьменеофпч у $n$~ьменеофбнй. \ex[ЧН30] (Ь.~Текозпмшд.) Рхуфш~$\set{A_1,~\ldots, A_n}$ й~$\set{B_1,~\ldots, B_n}$---нопцеуфчб, упдетцбэйе рп $n$~ьменеофпч лбцдпе. Тбуунпфтйфе бмзптйфн, лпфптщк рщфбефус ртпчетйфш обмйюйе тбчеоуфчб нецдх нопцеуфчбнй йулмаюйфемшоп рхфен утбчоеойк об тбчеоуфчп ьменеофпч ьфйи нопцеуфч. Фблйн пвтбъпн, бмзптйфн ъбдбеф чпртпущ фйрб~"$A_i=B_j$?" ртй оелпфптщи~$i$ й~$j$ й чщвйтбеф дбмшоекыйк рхфш чщюйумеойк ч ъбчйуйнпуфй пф фпзп, вщм мй пфчеф рпмпцйфемшощн ймй пфтйгбфемшощн. Пртедемйч рпдипдсэезп дшсчпмб, дплбцйфе, юфп мавпк фблпк бмзптйфн ч обйихдыен дмс уевс умхюбе чщохцдео чщрпмойфш ое неоее ${1\over2}n (n+1)$~утбчоеойк. %%250 \subsubchap{* Чщвпт у нйойнбмшощн юйумпн утбчоеойк} % 5.3.3 Ртй рпйуле обймхюыйи чпънпцощи ртпгедхт дмс чщвптб $t\hbox{-зп}$~ьменеофб ч рптсдле хвщчбойс йъ $n$~ьменеофпч нщ чуфтеюбенус у лмбуупн ъбдбю, рпдпвощи тбуунпфтеоощн ч ртедщдхэен рхолфе. Йуфптйс ьфпзп чпртпуб чпуипдйф л ъбойнбфемшопнх (ипфс й уетшеъопнх) пюетлх ртерпдпвопзп Ю.~М.~Дпдцупоб п фхтойтби рп феоойух, рпсчйчыенхус ч St.~James's Gazette 1~бчзхуфб 1883~з. (уфт.~5--6). Дпдцупо, лпфптщк, тбъхнеефус, впмее йъчеуфео лбл Мшайу Льттпм, тбуунбфтйчбм оеуртбчедмйчще ртбчймб, рп лпфптщн ртйухцдбмйуш (й дп уйи рпт ртйухцдбафус) ртйъщ ч фхтойтби рп феоойух. Тбуунпфтйн, обртйнет, тйу.~39, зде рплбъбо фйрйюощк фхтойт "у чщвщчбойен" нецдх 32~йзтплбнй, рпнеюеоощнй $01$, $02$,~\dots, $32$. Ч жйобме йзтпл~$01$ пдетцйчбеф рпведх обд йзтплпн~$05$, рпьфпнх суоп, юфп йзтпл~$01$---юенрйпо й ъбумхцйм ретчщк ртйъ. Оеуртбчедмйчпуфш ртпсчмсефус ч фпн, юфп йзтпл~$05$ пвщюоп рпмхюбеф чфптпк ртйъ, ипфс по нпцеф й ое вщфш чфптщн йзтплпн. Чщйзтбфш чфптпк ртйъ нпцоп, дбце еумй йзтбеыш ихце рпмпчйощ йзтплпч фхтойтб. Ч убнпн деме, лбл ъбнефйм Дпдцупо, чфптпк йзтпл чщйзтщчбеф чфптпк ртйъ ч фпн й фпмшлп фпн умхюбе, еумй ретчпобюбмшоп по й юенрйпо обипдймйуш ч ртпфйчпрпмпцощи рпмпчйоби фхтойтб; дмс $2^n$~йзтплпч ьфп ртпйуипдйф у четпсфопуфша~$2^{n-1}/(2^n-1)$, фбл юфп рпюфй ч рпмпчйое умхюбеч чфптпк ртйъ рпмхюбеф ое фпф йзтпл! Еумй ртпйзтбчыйе ч рпмхжйобме (йзтплй~$25$ й~$17$ об тйу.~39) уптечохафус ъб фтефйк ртйъ, фп чеушнб нбмпчетпсфоп, юфп фтефйк йзтпл рпмхюйф фтефйк ртйъ. Рпьфпнх Дпдцупо теыйм обкфй фблпк фхтойт, лпфптщк ртбчймшоп пртедемсеф чфптпзп й фтефшезп йзтплпч ч ртедрпмпцеойй фтбоъйфйчопуфй. (Йобюе зпчптс, еумй йзтпл~$A$ рпвецдбеф йзтплб~$B$, б~$B$ рпвецдбеф~$C$, фп нпцоп уюйфбфш, юфп йзтпл~$A$ рпведйф~$C$). По ртйдхнбм ртпгедхтх, ч лпфптпк ртпйзтбчыйн дбаф ущзтбфш еэе оеулпмшлп йзт, рплб ое уфбоеф пртедемеооп йъчеуфоп, юфп пой ихце дтхзйи фтеи йзтплпч. Ртйнет уиенщ Дпдцупоб ртйчпдйфус об тйу.~40, йъпвтбцбаэен дпрпмойфемшощк фхтойт, лпфптщк умедхеф ртпчеуфй чнеуфе у фхтойтпн, рплбъбоощн об тйу.~39. Дембефус рпрщфлб птзбойъпчбфш чуфтеюй йзтплпч, х лпфптщи дп уйи рпт вщмй тбчоще теъхмшфбфщ, й йулмаюйфш нбфюй нецдх йзтплбнй, рпвецдеоощнй пдойн й фен це юемпчелпн. Обртйнет, йзтпл~$16$ ртпйзтщчбеф~$11$, б йзтпл~$13$ ртпйзтщчбеф~$12$ ч ретчпн фхте; рпуме фпзп лбл йзтпл~$16$ ртпйзтщчбеф~$13$ чп чфптпн фхте, $16$~йулмаюбефус, фбл лбл феретш йъчеуфоп, юфп по ихце, юен~$11$, $12$ й~$13$. Ч фтефшен фхте нщ ое рпъчпмсен опнетх~$19$ йзтбфш у~$21$, фбл лбл пой пвб вщмй рпвецдеощ %%252 \picture{Тйу. 39. Фхтойт 32~йзтплпч у чщвщчбойен.} %%253 \picture{Тйу. 40. Феоойуощк фхтойт Мшайуб Льттпмб (ч дпрпмоеойе л фхтойтх тйу.~39).} %% 254 йзтплпн~$18$ й нщ ое нпзмй вщ бчфпнбфйюеулй йулмаюйфш ртпйзтбчыезп чп чуфтеюе~$19$ у~$21$. Вщмп вщ ртйсфоп уппвэйфш, юфп фхтойт Мшайуб Льттпмб плбъбмус прфйнбмшощн, оп, л упцбмеойа, ьфп ое фбл. Йъ ъбрйуй ч езп доечойле пф 23~йамс 1883~з. счуфчхеф, юфп по упуфбчйм ьфпф пюетл ртйнетоп ъб ыеуфш юбупч, й юхчуфчпчбм, юфп, "рпулпмшлх феоойуощк уеъпо ртйвмйцбефус л лпогх, пюетл умедхеф обрйубфш рпвщуфтее, ое умйылпн хчмелбсуш лбюеуфчпн". Ч езп ртпгедхте дембефус впмшые утбчоеойк, юен оепвипдйнп, й поб ое ужптнхмйтпчбоб дпуфбфпюоп юефлп, юфпвщ лчбмйжйгйтпчбфш ее лбл бмзптйфн. У дтхзпк уфптпощ, ч оек йнеафус оелпфптще пюеош йофетеуоще бурелфщ, еумй ухдйфш у фпюлй ътеойс рбтбммемшощи чщюйумеойк. Поб фблце ртедуфбчмсефус пфмйюощн тбурйубойен феоойуопзп фхтойтб, рпулпмшлх Льттпм члмаюйм ч оее оеулпмшлп дтбнбфйюеулйи ьжжелфпч; обртйнет, по пртедемйм, юфп дчб жйобмйуфб дпмцощ ртпрхуфйфш рсфщк фхт й ущзтбфш "дмйоощк" нбфю ч фхтби~6 й~7. Пдоблп птзбойъбфптщ фхтойтпч, рп-чйдйнпнх, упюмй ьфп ртедмпцеойе йъмйыое мпзйюощн, й рпфпнх уйуфенб Льттпмб, улптее чуезп, ойлпздб ое йурщфщчбмбуш. Чнеуфп ьфпзп ртблфйлхефус нефпд "тбууейчбойс" впмее уймшощи йзтплпч, юфпвщ пой рпрбмй ч тбъоще юбуфй детечб. Об нбфенбфйюеулпн уенйобте ч~1929--1930~з. Зхзп Ыфекозбхъ рпуфбчйм ъбдбюх обипцдеойс нйойнбмшопзп юйумб феоойуощи нбфюек, фтевхенщи дмс пртедемеойс ретчпзп й чфптпзп йзтплпч ч фхтойте, еумй йнеефус $n >2$~йзтплпч. А.~Ытекет [{\sl Mathesis Polska,\/} {\bf 7} (1932), 154--160] ртйчем ртпгедхтх, фтевхаэха убнпе впмшыее $n-2+\ceil{\log_2 n}$~нбфюек, йурпмшъпчбч, рп ухэеуфчх, фпф це нефпд, юфп й ретчще дче уфбдйй ртпгеууб, лпфптщк нщ объчбмй уптфйтпчлпк рпутедуфчпн чщвптб йъ детечб (ун.~р.~5.2.3, тйу.~23), пдоблп ое чщрпмосс дпрпмойфемшощи утбчоеойк, упдетцбэйи~$-\infty$. Ытекет фблце хфчетцдбм, юфп $n-2+\ceil{\log_2 n}$---обймхюыее чпънпцопе ъобюеойе; оп езп дплбъбфемшуфчп вщмп пыйвпюощн, лбл й еэе пдоб рпрщфлб дплбъбфемшуфчб, ртедртйосфбс Е.~Умхреглй [{\sl Colloquium Mathematician,\/} {\bf 2} (1951), 286--290]. Ртпымп 32~зпдб, ртецде юен У.~У.~Лйумйгщощн вщмп прхвмйлпчбоп ртбчймшопе, ипфс й пюеош умпцопе дплбъбфемшуфчп [{\sl Уйвйтулйк нбфенбфйюеулйк цхтобм,\/} {\bf 5} (1964), 557--564]. Рхуфш~$V_t(n)$ дмс~$1\le t \le n$ пвпъобюбеф нйойнбмшопе юйумп утбчоеойк, фтевхенщи дмс пртедемеойс $t\hbox{-зп}$ ч рптсдле хвщчбойс ьменеофб йъ $n$~ьменеофпч, й рхуфш $W_t(n)$~тбчоп обйнеошыенх юйумх утбчоеойк, оепвипдйнщи дмс пртедемеойс обйвпмшыезп, чфптпзп,~\dots, $t\hbox{-зп}$ ьменеофпч чуеи утбъх. Йъ уппвтбцеойк уйннефтйй йнеен $$ V_t(n)=V_{n+1-t}(n); \eqno(1) $$ %%255 пюечйдоп фблце, юфп $$ \eqalignno{ V_1(n)&=W_1(n), & (2) \cr V_t(n)&\le W_t(n), & (3) \cr W_n(n)&=W_{n-1}(n)=S(n). & (4) \cr } $$ Ч р.~5.2.3 нщ чйдемй, юфп $$ V_1(n)=n-1. \eqno(5) $$ Еуфш хдйчйфемшоп ртпуфпе дплбъбфемшуфчп ьфпзп жблфб, рпулпмшлх лбцдщк хюбуфойл фхтойтб, лтпне юенрйпоб, дпмцео ртпйзтбфш рп лтбкоек нете пдох йзтх! Пвпвэбс ьфх йдеа й йурпмшъхс "дшсчпмб", нщ нпцен веъ пупвпзп фтхдб дплбъбфш фептенх Ытекетб---Лйумйгщоб. \proclaim Фептенб~S. Ртй~$n\ge 2$ уртбчедмйчп тбчеоуфчп~$V_2(n)=W_2(n)=n-2+\ceil{\log_2 n}$. \proof Ртедрпмпцйн, юфп ч фхтойте, зде у рпнпэша оелпфптпк дбоопк ртпгедхтщ дпмцео пртедемйфшус чфптпк йзтпл, хюбуфчхаф $n$~йзтплпч, й рхуфш~$a_j$---юйумп йзтплпч, ртпйзтбчыйи~$j$ ймй впмшые нбфюек. Пвэее юйумп ущзтбоощи нбфюек вхдеф фпздб тбчоп~$a_1+a_2+a_3+\ldots\,$. Нщ ое нпцен пртедемйфш чфптпзп йзтплб, ое чщсчйч ъбпдоп й юенрйпоб (ун.~хрт.~2), рпьфпнх йъ ртедщдхэйи тбуухцдеойк~$a_1=n-1$. Дмс ъбчетыеойс дплбъбфемшуфчб рплбцен, юфп чуездб ухэеуфчхеф рпумедпчбфемшопуфш теъхмшфбфпч нбфюек, лпфптбс ртйчпдйф л~$a_2\ge \ceil{\log_2 n}-1$. Ртедрпмпцйн, юфп л лпогх фхтойтб юенрйпо ущзтбм $p$~йзт й рпведйм $p$~йзтплпч; пдойн йъ ойи вщм чфптпк йзтпл, б пуфбмшоще дпмцощ ртпйзтбфш рп лтбкоек нете еэе рп пдопнх тбъх, рпьфпнх~$a_2\ge p-1$. Йфбл, нщ нпцен ъблпоюйфш дплбъбфемшуфчп, рпуфтпйч дшсчпмб, ртедпртедемсаэезп теъхмшфбфщ йзт фблйн пвтбъпн, юфпвщ юенрйпох ртйымпуш ущзтбфш рп лтбкоек нете еэе у~$\ceil{\log_2 n}$~дтхзйнй хюбуфойлбнй фхтойтб. Рхуфш дшсчпм уюйфбеф, юфп йзтпл~$A$ мхюые, юен~$B$, еумй~$A$ тбоее ое ртпйзтщчбм, б~$B$ ипфс вщ пдобцдщ ртпйзтбм, ймй еумй пвб ое ртпйзтщчбмй, оп $B$~чщйзтбм л ьфпнх нпнеофх неошые нбфюек, юен~$A$. Ртй дтхзйи пвуфпсфемшуфчби дшсчпм нпцеф ртйойнбфш ртпйъчпмшопе теыеойе, ое ртпфйчптеюбэее оелпфптпнх юбуфйюопнх хрптсдпюеойа. Тбуунпфтйн теъхмшфбфщ ъбчетыеоопзп фхтойтб, нбфюй лпфптпзп ртедпртедемсмйуш фблйн дшсчпмпн. Нщ улбцен, юфп "$A$ ртечпуипдйф $B$" фпздб й фпмшлп фпздб, лпздб~$A=B$ ймй $A$~ртечпуипдйф йзтплб, лпфптщк ретчщн рпведйм~$B$. (Фпмшлп ретчпе рптбцеойе йзтплб ухэеуфчеооп ч ьфпн пфопыеойй, рпумедхаэйе езп йзтщ йзоптйтхафус. Ч уппфчефуфчйй у хуфтпкуфчпн дшсчпмб мавпк йзтпл, \emph{ретчщн} рпведйчыйк лблпзп-фп, ой ч пдопк йъ ртедщдхэйи чуфтею ое дпмцео йнефш рптбцеойк. Пфуадб умедхеф, юфп %%256 йзтпл, лпфптщк чщйзтбм учпй ретчще $p$~нбфюек, ртечпуипдйф об пуопчбойй ьфйи $p$~йзт ое впмее $2^p$~йзтплпч. (Еумй~$p=0$, ьфп пюечйдоп, еумй це $p>0$, фп $p\hbox{-к}$~нбфю вщм ущзтбо ртпфйч йзтплб, лпфптщк мйвп тбоее рпфетрем рптбцеойе, мйвп ртечпуипдйф ое впмее~$2^{p-1}$~йзтплпч.) Юенрйпо ртечпуипдйф чуеи, рпьфпнх по дпмцео вщм ущзтбфш ое неоее $\ceil{\log_2 n}$~нбфюек. \proofend Фблйн пвтбъпн, ъбдбюб обипцдеойс чфптпзп ч рптсдле хвщчбойс ьменеофб рпмопуфша теыеоб ч нйойнблуопн унщуме. Ч хрт.~6 рплбъбоп, юфп нпцоп дбфш ртпуфха жптнхмх дмс нйойнбмшопзп юйумб утбчоеойк, оепвипдйнщи дмс чщсчмеойс чфптпзп ьменеофб нопцеуфчб, еумй йъчеуфоп ртпйъчпмшопе юбуфйюопе хрптсдпюеойе ьменеофпч. \qsection Б еумй $t>2$? Ч хрпнсохфпк уфбфше Лйумйгщо рпыем дбмшые. По тбуунпфтем впмшыйе ъобюеойс~$t$, дплбъбч, юфп $$ W_t(n)\le n-t+\sum_{n+1-tX_3$, $X_5X_7$, ъбфен утбчойн~$X_2:X_6$; ч уймх уйннефтйй рпмпцйн~$X<2n+t-3+\sum_{0\le j\le t-2}\ceil{\log_2((n+2-t)/(t+j))}, \rem{$n\ge 2t-1$.} \eqno(12) $$ Лйтлрбфтйл фпюоп хуфбопчйм рпчедеойе жхолгйй~$V_t(n)$ ртй~$t=3$, дплбъбч, юфп~$V_3(n)=n+\ceil{\log_2 ((n-1)/2.5)}+\ceil{\log_2((n-1)/4)}$ ртй чуеи~$n\ge 50$ (ут.~у~хрт.~22). \section Мйоекощк нефпд. Еумй $n$~оеюефоп й~$t=\ceil{n/2}$, фп~$t\hbox{-к}$ ч рптсдле хвщчбойс (й~$t\hbox{-к}$ ч рптсдле чпътбуфбойс) ьменеоф объщчбефус недйбопк. Ч уппфчефуфчйй у~(11) нщ нпцен обкфй недйбох~$n$ %%260 {\catcode`\!=\active\def!{\hbox to 0 pt{${}^*$\hss}} \htable{Фбвмйгб 1}% {Обймхюыйе йъ йъчеуфощи четиойи пгеопл дмс $V_t(n)$}% {\strut\bskip\hfill$#$\bskip&&\bskip\hfill$#$\bskip\cr n & V_1(n) & V_2(n) & V_3(n) & V_4(n) & V_5(n) & V_6(n) & V_7(n) & V_8(n) & V_9(n) & V_{10}(n)\cr \noalign{\hrule} 1 & 0 \cr 2 & 1 & 1 \cr 3 & 2 & 3 & 2 \cr 4 & 3 & 4 & 4 & 3 \cr 5 & 4 & 6 & 6 & 6 & 4 \cr 6 & 5 & 7 & 8 & 8 & 7 & 5 \cr 7 & 6 & 8 & 10 & 10!& 10 & 8 & 6\cr 8 & 7 & 9 & 11 & 12 & 12 & 11 & 9 & 7\cr 9 & 8 & 11 & 12 & 14 & 15!& 14 & 12 & 11 & 8\cr 10 & 9 & 12 & 14!& 15 & 17 & 17 & 15 & 14! & 12 & 9 \cr \noalign{\hrule} \multispan{11}\hbox{$*$)~Ч ьфйи умхюбси хрт.~10--12 дбаф рпуфтпеойс, рпъчпмсаэйе хмхюыйфш~(11).}\cr }}% ьменеофпч ъб $\approx {1\over2}n\log_2 n$~утбчоеойк, оп ьфп мйыш ртйвмйъйфемшоп чдчпе вщуфтее уптфйтпчлй, ипфс обн охцоб ъобюйфемшоп неошыбс йожптнбгйс. Ч феюеойе оеулпмшлйи меф пв®едйоеооще хуймйс тсдб йуумедпчбфемек вщмй обртбчмеощ об хмхюыеойе жптнхмщ~(11) дмс впмшыйи ъобюеойк~$t$ й~$n$; облпоег, ч 1971~з. Нбохьмш Вмхн пфлтщм нефпд, фтевхаэйк фпмшлп $O(n \log \log n)$~ыбзпч. Рпдипд Вмхнб л ьфпк ъбдбюе дбм фпмюпл л тбъчйфйа опчпзп лмбууб нефпдпч, лпфптщк ртйчем л умедхаэенх рпуфтпеойа, ртйобдмецбэенх Т.~Тбкчеуфх й~Т.~Фбтшсох. \proclaim Фептенб~L. Еумй~$n>32$, фп~$V_t(n)\le 15n-163$ ртй~$1\le t\le n$. \proof Лпздб $n$~нбмп, фептенб фтйчйбмшоб, фбл лбл~$V_t(n)\le S(n)\le 10n\le 15n-163$ дмс~$32r+1$, фп обн охцоп обкфй $(t-1-r)\hbox{-к}$~ьменеоф ч рптсдле хвщчбойс йъ $n-1-r$~неошыйи ьменеофпч. Ухфш демб ч фпн, юфп~$r$ й~$n-1-r$ пвб неошые ймй тбчощ~$10q+3$ (тбънет пвмбуфек~Б й~D рмау~Ч ймй~У). Йодхлгйек рп~$q$ чщчпдйн, юфп ьфпф ыбз фтевхеф ое впмее $15(10q+3)-163$~утбчоеойк. \medskip Пвэее юйумп утбчоеойк плбъщчбефус ое впмшые $$ 13(2q+1)+30q-148+4q+15(10q+3)-163=15(14q-6)-163. $$ Фбл лбл нщ обюбмй у ое неоее $14q-6$~ьменеофпч, дплбъбфемшуфчп ъбчетыеоп. \proofend Нефпд, йурпмшъпчбоощк ч ьфпн дплбъбфемшуфче, ое чрпмое упчетыеоощк, рпулпмшлх об ыбзе~4 фетсефус ъобюйфемшобс йожптнбгйс. Фэбфемшоще хмхюыеойс, ртпдембооще Ч.~Ртбффпн, %%262 Т.~Тбкчеуфпн й~Т.~Фбтшсопн, рплбъщчбаф, юфп лпоуфбофх~15 нпцоп хнеошыйфш дп~$5.43$. \section Утедоее юйумп. Чнеуфп нйойнйъбгйй \emph{нблуйнбмшопзп} юйумб утбчоеойк нпцоп йулбфш бмзптйфн, лпфптщк нйойнйъйтхеф \emph{утедоее} юйумп утбчоеойк, ртедрпмбзбс, юфп рптсдпл умхюбео. Лбл пвщюоп, ьфб ъбдбюб ъобюйфемшоп фтхдоее, й поб чуе еэе ое теыеоб дбце ч умхюбе~$t=2$. Лмпд Рйлбт хрпнсохм ьфх ъбдбюх ч учпек \picture{ Тйу.~42. Ртпгедхтб, лпфптбс чщвйтбеф чфптпк ьменеоф йъ~$\set{X_1, X_2, X_3, X_4, X_5, X_6}$, йурпмшъхс ч утедоен $6{1\over2}$~утбчоеойк. Лбцдбс "уйннефтйюобс" чефчш йдеофйюоб учпенх втбфх, пдоблп йнеоб ретеуфбчмеощ уппфчефуфчхаэйн пвтбъпн. Чп чоеыойи хъмби ъбрйубоп~$j\ k$, еумй йъчеуфоп, юфп $X_j$---чфптпк, a $X_k$---обйвпмшыйк ьменеоф; юйумп ретеуфбопчпл, ртйчпдсэйи л ьфпнх хъмх, ъбрйубоп оерпутедуфчеооп рпд ойн. } лойзе Th\'eorie des Questionnaires (1965), ыйтплпе йуумедпчбойе вщмп ртедртйосфп Нймфпопн Упвемен [Univ.~of Minnesota, Dept.~of Statistics, report~113 (November, 1968)]. Упвемш рпуфтпйм ртпгедхтх, йъпвтбцеооха об тйу.~42, лпфптбс обипдйф чфптпк ч рптсдле хвщчбойс ьменеоф йъ ыеуфй ьменеофпч, ч утедоен йурпмшъхс фпмшлп $6{1\over2}$~утбчоеойк. Ч ихдыен %%263 умхюбе фтевхефус 8~утбчоеойк, й ьфп ихце, юен~$V_2(6)=7$; оп чуе йъчеуфоще ртпгедхтщ дмс ьфпк ъбдбюй, фтевхаэйе ое впмее 7~утбчоеойк, йурпмшъхаф ч утедоен рп лтбкоек нете $6{2\over3}$~утбчоеойк. Фблйн пвтбъпн, четпсфоп, ойлблбс ртпгедхтб обипцдеойс чфптпзп йъ ыеуфй ьменеофпч ое вхдеф прфйнбмшопк пдопчтенеооп й лбл нйойнблуобс, й лбл нйойнйъйтхаэбс утедоее юйумп утбчоеойк. Рхуфш $\bar V(n)$~пвпъобюбеф нйойнбмшопе утедоее юйумп утбчоеойк, оепвипдйнщи дмс пртедемеойс $t\hbox{-зп}$~ьменеофб ч рптсдле хвщчбойс йъ $n$~ьменеофпч. Ч умедхаэек фбвмйге рплбъбощ обймхюыйе йъчеуфоще четиойе пгеолй дмс~$\bar V_2(n)$, чщюйумеооще Упвемен: {\catcode`\!=\active\def!#1,#2/#3.{#1{#2\over#2}} $$ \vbox{ \halign{ \hfill$#$\bskip&&\bskip$#$\hfill\bskip\cr n=2& 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \cr \bar V_2(n)\le 1& !2,2/3. & 4 & !5,4/15. & !6,1/2. & !7,17/21. & 9 & !10, 1/15. & !11,4/135.\cr }} \eqno(13) $$ } Упвемш ртедрпмпцйм, юфп $$ \bar V_2(n)\ge n-2+\floor{2\log_2 n}/2. \eqno(14) $$ Т.~Х.~Жмпкд ч 1970~з.\ пвобтхцйм, юфп недйбоб $n$~ьменеофпч ч утедоен нпцеф вщфш обкдеоб чуезп ъб ${3\over2}n+O\left(n^{2\over3}\log n\right)$~утбчоеойк. (Ун.~хрт.~13.) Жблфйюеулй по дплбъбм, юфп $$ \bar V_t(n)\le n+t+f(n), \rem{зде $\lim_{n\to\infty} f(n)/n=0$.} \eqno(15) $$ Ртедрпмбзбефус, юфп ьфпф теъхмшфбф счмсефус обймхюыек буйнрфпфйюеулпк жптнхмпк, пдоблп ойлблпк хдпчмефчптйфемшопк ойцоек пгеолй чуе еэе ое обкдеоп. \excercises \ex[15] Рпюенх ч фхтойте Мшайуб Льттпмб (тйу.~39 й~40) йзтпл~$13$ чщвщчбеф, оеунпфтс об фп юфп по чщйзтбм учпк нбфю ч фтефшен фхте? \rex[Н25] Дплбцйфе, юфп рпуме фпзп, лбл нщ обымй у рпнпэша рпумедпчбфемшопуфй утбчоеойк $t\hbox{-к}$ ьменеоф ч рптсдле хвщчбойс йъ $n$~ьменеофпч, нщ фблце ъобен, лблйе $t-1$~ьменеофпч впмшые оезп й лблйе $n-t$~ьменеофпч неошые. \ex[M21] Дплбцйфе, юфп~$V_t(n)\ge V_t(n-1)+1$ ртй~$1\le t \le n$. \ex[Н20] Дплбцйфе, юфп~$W_t(n)\ge\ceil{\log_2 n^{t\atop -}}$, зде~$n^{t\atop -}=n(n-1) \ldots (n+1-t)$. \ex[10] Дплбцйфе, юфп~$W_3(n)\le V_3(n)+1$. \rex[Н26] (Т.~Х.~Жмпкд.) Дбоп $n$~тбъмйюощи ьменеофпч~$\set{X_1,~\ldots, X_n}$ й пфопыеойс~$X_iK_j$, пдоблп~$i$ й~$j$ неосафус тпмснй. Об тйу.~43(б) йъпвтбцеоп детечп утбчоеойк, ч лпфптпн ьфп хумпчйе чщрпмоеоп. (Ъбнефйн, юфп об лбцдпн хтпчое ртпйъчпдйфус пдйоблпчпе юйумп утбчоеойк, рпьфпнх рпуме $m$~утбчоеойк йнеефус $2^m$~теъхмшфбфпч; фбл лбл~$n!$ ое счмсефус уфереоша~2, фп оелпфптще утбчоеойс вхдхф йъмйыойнй ч фпн унщуме, юфп пдоп йъ йи рпддетечшеч ойлпздб ое чуфтеюбефус об ртблфйле. Йощнй умпчбнй, об оелпфптщи чефчси детечб ртйипдйфус чщрпмосфш впмшые утбчоеойк, юен оепвипдйнп, юфпвщ уптфйтпчлб вщмб ртбчймшопк об чуеи уппфчефуфчхаэйи чефчси.) Фбл лбл лбцдщк рхфш фблпзп детечб учетих дпойъх пртедемсеф чуе детечп, фп рпдпвоха уиенх уптфйтпчлй ртпэе йъпвтбцбфш ч чйде \dfn{уефй,} лбл об тйу.~43(b). Ртснпхзпмшойлй ч фблпк уефй ртедуфбчмсаф "лпнрбтбфптоще нпдхмй", йнеаэйе дчб чипдб (йъпвтбцеооще мйойснй, чипдсэйнй ч нпдхмш учетих) %%266 \picture{Тйу. 43. Детечп утбчоеойк, ч лпфптпн ое хюйфщчбефус ртедщуфптйс, (a) й уппфчефуфчхаэбс уефш~(b).} %%267 й дчб чщипдб (йъпвтбцеооще мйойснй, чщипдсэйнй чойъ); мечщк чщипд еуфш неошыйк йъ дчхи чипдпч, б ртбчщк чщипд---впмшыйк йъ ойи. Ьменеоф~$K'_1$ ч ойцоек юбуфй уефй еуфш обйнеошыйк йъ~$\set{K_1, K_2, K_3, K_4}$, $K'_2$---чфптпк ч рптсдле чпътбуфбойс й~ф.~д. Оефтхдоп дплбъбфш, юфп мавбс уефш уптфйтпчлй уппфчефуфчхеф детечх утбчоеойк, пвмбдбаэенх учпкуфчпн оеъбчйуйнпуфй пф ртедщуфптйй (ч хлбъбоопн чщые унщуме), й юфп мавпе фблпе детечп уппфчефуфчхеф уефй лпнрбтбфптощи нпдхмек. Нецдх ртпюйн ъбнефйн, юфп у йоцеоетопк фпюлй ътеойс лпнрбтбфптощк нпдхмш дпчпмшоп мезлп йъзпфпчйфш. Ртедрпмпцйн, обртйнет, юфп рп мйойсн учсъй ч нпдхмш рпуфхрбаф дчпйюоще юйумб рп пдопнх вйфх ч едйойгх чтенеой, обюйобс уп уфбтыезп. Лбцдщк лпнрбтбфптощк нпдхмш йнееф фтй упуфпсойс й жхолгйпойтхеф умедхаэйн пвтбъпн: $$ \matrix{ \multispan{3}\hfill\hbox{Нпнеоф $t$}\hfill &\multispan{3}\hfill \hbox{Нпнеоф $(t+1)$}\hfill\cr \hbox{Упуфпсойе} & \hbox{Чипдщ}\hfill\span & \hbox{Упуфпсойе} &\hbox{Чщипдщ}\hfill\span\cr 0 & 0 & 0 & 0 & 0 & 0\cr 0 & 0 & 1 & 1 & 0 & 1\cr 0 & 1 & 0 & 2 & 0 & 1\cr 0 & 1 & 1 & 0 & 1 & 1\cr 1 & x & y & 1 & x & y\cr 2 & x & y & 2 & y & x\cr } $$ Ретчпобюбмшоп чуе нпдхмй обипдсфус ч упуфпсойй~0 й чщдбаф~$00$. Нпдхмш ретеипдйф ч упуфпсойе~1 ймй~2, лбл фпмшлп езп чипдщ уфбохф тбъмйюощнй. Юйумб, лпфптще ч нпнеоф чтенеой~$t$ обюбмй рпуфхрбфш учетих ч уефш, уппфчефуфчхаэха тйу.~43(b), обюохф ч нпнеоф~$t+3$ чщчпдйфшус уойъх ч пфуптфйтпчбоопн \picture{Тйу.~44. Еэе пдйо урпупв ртедуфбчмеойс уптфйтпчлй рпумедпчбфемшопуфй $\langle 4, 1, 3, 2\rangle$ рпутедуфчпн уефй, йъпвтбцеоопк об тйу.~43.} рптсдле, еумй члмаюйфш уппфчефуфчхаэйк ъбдетцйчбаэйк ьменеоф ч мйойси~$K'_1$ й~$K'_4$. Дмс тбътбвпфлй фептйй уефек уптфйтпчлй хдпвоп йъпвтбцбфш йи оеулпмшлп йощн урпупвпн (тйу.~44). Об ьфпн тйухоле юйумб рпуфхрбаф умечб, б лпнрбтбфптоще нпдхмй йъпвтбцеощ четфйлбмшощнй упедйоеойснй нецдх дчхнс ртснщнй; лбцдщк %%268 лпнрбтбфпт чщъщчбеф, еумй оепвипдйнп, ретеуфбопчлх учпйи чипдпч фблйн пвтбъпн, юфп рпуме ртпипцдеойс лпнрбтбфптб впмшыее юйумп плбъщчбефус об ойцоек мйойй. Ч ртбчпк юбуфй дйбзтбннщ чуе юйумб хрптсдпюеощ учетих чойъ. Тбоее, йъхюбс прфйнбмшоха уптфйтпчлх, нщ хдемсмй пуопчопе чойнбойе нйойнйъбгйй юйумб утбчоеойк, рпюфй (ймй упчуен) \picture{Тйу.~45. Рпмхюеойе $(n+1)$-ьменеофопзп уптфйтпчэйлб йъ $n$-ьменеофопзп: (a)---чуфбчлб; (b)---чщвпт.} ое хюйфщчбс ретенеэеойе дбоощи ймй умпцопуфш уфтхлфхтщ теыеойк нефпдб уптфйтпчлй. Ч ьфпн пфопыеойй уефй уптфйтпчлй йнеаф оелпфптпе ртейнхэеуфчп, фбл лбл дбооще нпзхф итбойфшус ч $n$~сюеклби, б уфтхлфхтб теыеойк "ртснпмйоекоб"; оеф оепвипдйнпуфй ъбрпнйобфш теъхмшфбфщ ртедщдхэйи утбчоеойк---рмбо оейънеоео й жйлуйтпчбо ъбтбоее. Еэе пдойн чбцощн \picture{Тйу.~46. Уефечще бобмпзй ьменеофбтощи уиен чохфтеооек уптфйтпчлй, рпмхюеооще нопзплтбфощн ртйнеоеойен претбгйй, ртедуфбчмеоопк об тйу.~45: (a)---ртпуфбс чуфбчлб; (b)---нефпд рхъщтшлб.} ртейнхэеуфчпн уефек уптфйтпчлй счмсефус фп, юфп юбуфш претбгйк нпцоп упчнеуфйфш, еумй чщрпмосфш йи пдопчтенеооп (об рпдипдсэек нбыйое). Обртйнет, рсфш ыбзпч об тйу.~43 й~44 уплтбэбафус дп фтеи, еумй дпрхуфйфш пдопчтенеооще оеретелтщчбаэйеус утбчоеойс, фбл лбл нпцоп пв®едйойфш ретчще дчб й умедхаэйе дчб ыбзб; рпъдоее ч дбоопн рхолфе нщ йурпмшъхен %%269 ьфп учпкуфчп уефек уптфйтпчлй. Фблйн пвтбъпн, уефй уптфйтпчлй нпзхф вщфш пюеош рпмеъощ, ипфс чпънпцопуфш рпуфтпеойс ьжжелфйчопк уефй уптфйтпчлй $n$~ьменеофпч ртй впмшыйи~$n$ чпчуе ое пюечйдоб; чпънпцоп, нщ пвобтхцйн, юфп дмс рпддетцбойс пдоптпдопк уфтхлфхтщ теыеойк фтевхефус нопзп дпрпмойфемшощи утбчоеойк. Йнеефус дчб ртпуфщи урпупвб рпуфтпеойс уефй уптфйтпчлй. дмс $n+1$~ьменеофпч, еумй дбоб уефш дмс $n$~ьменеофпч: у йурпмшъпчбойен мйвп ртйогйрб \emph{чуфбчлй,} мйвп ртйогйрб \emph{чщвптб.} Об \picture{Тйу.~47. Ртй рбтбммемшопн чщрпмоеойй претбгйк ртпуфбс чуфбчлб упчрбдбеф у нефпдпн рхъщтшлб!} тйу.~45(a) рплбъбоп, лбл $(n+1)\hbox{-к}$~ьменеоф нпцеф вщфш чуфбчмео об охцопе неуфп рпуме фпзп, лбл ретчще $n$~ьменеофпч пфуптфйтпчбощ, б об тйу.~45(b) рплбъбоп, лбл нпцоп чщвтбфш обйвпмшыйк ьменеоф, ртецде юен ретекфй л уптфйтпчле пуфбмшощи. Нопзплтбфопе ртйнеоеойе тйу.~45(a) дбеф уефечпк бобмпз ртпуфщи чуфбчпл (бмзптйфн~5.2.1S), б нопзплтбфопе ртйнеоеойе тйу.~45(b) ртйчпдйф л уефечпнх бобмпзх нефпдб рхъщтшлб (бмзптйфн~5.2.2B). Об тйу.~46 йъпвтбцеощ уппфчефуфчхаэйе уефй дмс ыеуфй ьменеофпч. Йофетеуоп ъбнефйфш, юфп еумй уцбфш лбцдха уефш, юфпвщ пвеуреюйфш пдопчтенеооще претбгйй, фп пвб нефпдб учедхфус л пдопк й фпк це "фтехзпмшопк" ртпгедхте у $(2n-3)$~уфбдйснй (тйу.~47). Мезлп дплбъбфш, юфп уефй, ртедуфбчмеооще об тйу.~43 й~44, вхдхф уптфйтпчбфш мавпе нопцеуфчп йъ юефщтеи юйуем, рпулпмшлх ретчще юефщте лпнрбтбфптб обртбчмсаф обйнеошыйк й обйвпмшыйк ьменеофщ об рпмпцеооще йн неуфб, б рпумедойк лпнрбтбфпт тбурпмбзбеф ч фтевхенпн рптсдле пуфбмшоще дчб ьменеофб. Пдоблп ое чуездб фбл мезлп улбъбфш, вхдеф мй дбообс уефш уптфйтпчбфш чуе чпънпцоще чипдоще рпумедпчбфемшопуфй; обртйнет, уефй \picture{p.269} счмсафус ртбчймшощнй юефщтеиьменеофйщнй уефснй уптфйтпчлй, оп дплбъбфемшуфчп йи ртбчймшопуфй оефтйчйбмшоп. Вщмп вщ %%270 дпуфбфпюоп ртпчетйфш лбцдха $n$-ьменеофоха уефш об чуеи $n!$~ретеуфбопчлби $n$~тбъмйюощи юйуем, оп жблфйюеулй нщ нпцен пвпкфйуш ъобюйфемшоп неошыйн лпмйюеуфчпн ртпчетпл. \proclaim Фептенб~Z. (Ртйогйр охмек й едйойг.) Еумй уефш у $n$~чипдбнй уптфйтхеф ч оехвщчбаэен рптсдле чуе $2^n$~рпумедпчбфемшопуфек йъ~0 й~1, фп поб вхдеф уптфйтпчбфш ч оехвщчбаэен рптсдле мавха рпумедпчбфемшопуфш $n$~юйуем. \proof (Ьфп юбуфощк умхюбк фептенщ Вхтйуйхуб, хрт.~5.3.1-12.) Еумй~$f(x)$---мавбс нпопфпообс жхолгйс, дмс лпфптпк~$f(x)\le f(y)$ ртй~$x\le y$, й еумй дбообс уефш ртепвтбъхеф~$\< x_1,~\ldots, x_n>$ ч~$\$, фп, лбл оефтхдоп чйдефш, ьфб уефш ртепвтбъхеф~$\$ ч~$\$. Еумй~$y_i>y_{i+1}$ ртй оелпфптпн~$i$, фп тбуунпфтйн нпопфпооха жхолгйа~$f$, лпфптбс дмс чуеи юйуем $$, лпфптбс ое уптфйтхефус дбоопк уефша. Умедпчбфемшоп, еумй чуе рпумедпчбфемшопуфй~0 й~1 рпддбафус уптфйтпчле, фп вхден йнефш~$y_i\le y_{i+1}$ дмс чуеи~$1\le i < n$. \proofend Ртйогйр охмек й едйойг дпчпмшоп рпмеъео дмс рпуфтпеойс уефек уптфйтпчлй. Ч лбюеуфче оефтйчйбмшопзп ртйнетб рпмхюйн пвпвэеоощк чбтйбоф "пвнеоопк уптфйтпчлй уп умйсойен" Вьфюетб (бмзптйфн~5.2.2Н). Йдес упуфпйф ч фпн, юфпвщ уптфйтпчбфш $m+n$~ьменеофпч, "уптфйтхс ретчще~$m$ й рпумедойе~$n$ ьменеофпч оеъбчйуйнп й ъбфен ртйнеосс л теъхмшфбфх \dfn{$(m, n)$-уефш умйсойс.} Рпуфтпйфш $(m, n)$-уефш умйсойс нпцоп рп йодхлгйй: {\medskip\narrower \item{a)}~Еумй~$m=0$ ймй~$n=0$, фп уефш рхуфбс. Еумй~$m=n=1$, фп уефш упуфпйф йъ едйоуфчеоопзп лпнрбтбфптопзп нпдхмс. \item{b)}~Еумй~$mn>1$, фп пвпъобюйн умйчбенще рпумедпчбфемшопуфй $\$ й~$\$. Упмшен "оеюефоще рпумедпчбфемшопуфй"~$\$ й~$\$ й рпмхюйн пфуптфйтпчбоощк теъхмшфбф~$\$; упмшен "юефоще рпумедпчбфемшопуфй"~$\$ й~$\$ й рпмхюйн пфуптфйтпчбоощк теъхмшфбф~$\$. Й облпоег, ртйнеойн претбгйй утбчоеойс-пвнеоб $$ w_1:v_2, w_2:v_3, w_3:v_4, w_{\floor{m/2}+\floor{n/2}}:v^* \eqno(1) $$ л рпумедпчбфемшопуфй $$ \; \eqno(2) $$ теъхмшфбф вхдеф пфуптфйтпчбо. (!) (Ъдеуш~$v^*=v_{\floor{m/2}+\floor{n/2}+1}$ ое ухэеуфчхеф, еумй~$m$ й~$n$ пвб юефоще, й~$v^{**}=v_{\floor{m/2}+\floor{n/2}+2}$ %% 271 ухэеуфчхеф, мйыш еумй~$m$ й~$n$ пвб оеюефоще; пвэее юйумп лпнрбтбфптощи нпдхмек, хлбъбоощи ч~(1), тбчоп~$\floor{(m+n)-1)/2}$.) \medskip} \noindent Объпчен $(m, n)$-уефш умйсойс Вьфюетб \dfn{юефоп-оеюефощн умйсойен.} Рпуфтпеоопе ч уппфчефуфчйй у ьфйнй ртйогйрбнй $(4, 7)$-умйсойе рплбъбоп об тйу.~48. \picture{Тйу. 48. Юефоп-оеюефопе умйсойе дмс~$m=4$ й~$n=7$.} Юфпвщ дплбъбфш, юфп ьфб пюеош уфтбообс ртпгедхтб декуфчйфемшоп тбвпфбеф ртй~$mn>1$, чпурпмшъхенус ртйогйрпн охмек й едйойг й ртпчетйн ее об чуеи рпумедпчбфемшопуфси~0 й~1. Рпуме обюбмшощи $m$-уптфйтпчлй й $n$-уптфйтпчлй рпумедпчбфемшопуфш~$\$ вхдеф упуфпсфш йъ $k$~охмек, ъб лпфптщнй умедхаф $m-k$~едйойг, б рпумедпчбфемшопуфш~$\$---йъ $l$~охмек у рпумедхаэйнй $n-l$~едйойгбнй ртй оелпфптщи~$k$ й~$l$. Умедпчбфемшоп, рпумедпчбфемшопуфш~$\$ вхдеф упуфпсфш йъ~$\ceil{k/2}+\ceil{l/2}$~охмек у рпумедхаэйнй едйойгбнй, б $\$---йъ $\floor{k/2}+\floor{l/2}$~охмек у рпумедхаэйнй едйойгбнй. Теыбаэйн нпнеофпн дплбъбфемшуфчб счмсефус фп, юфп $$ (\ceil{k/2}+\ceil{l/2})-(\floor{k/2}+\floor{l/2})=0, 1 \hbox{ ймй } 2. \eqno(3) $$ Еумй ьфб тбъопуфш тбчоб~0 ймй~1, фп рпумедпчбфемшопуфш~(2) хце хрптсдпюеоб, б еумй поб тбчоб~2, фп пдоб йъ претбгйк утбчоеойс-пвнеоб ч~(1) уфбчйф чуе об учпй неуфб. Дплбъбфемшуфчп ъбчетыеоп. (Ъбнефйн, юфп ртйогйр охмек й едйойг учпдйф $\perm{m+n}{m}$~умхюбеч ч ъбдбюе умйсойс чуезп мйыш л~$(m+1)(n+1)$, лбцдщк йъ лпфптщи йъпвтбцбефус дчхнс рбтбнефтбнй~$k$ й~$l$.) Рхуфш~$C(m, n)$---юйумп лпнрбтбфптощи нпдхмек, йурпмшъхенщи ртй юефоп-оеюефопн умйсойй $m$ й $n$~ьменеофпч, ое уюйфбс %%272 обюбмшощи $m$- й~$n$-уптфйтпчпл; йнеен $$ C(m,n)=\cases{ mn, & еумй $mn\le 1$;\cr C(\ceil{m/2}, \ceil{n/2})+C(\floor{m/2}, \floor{n/2})+ \floor{(m+n-1)/2}, & еумй $mn>1$.\cr } \eqno(4) $$ Ч пвэен умхюбе ьфп ое умйылпн ртпуфбс жхолгйс пф~$m$ й~$n$, пдоблп, ъбнефйч, юфп~$C(1, n)=n$ й юфп $$ C(m+1, n+1)-C(m,n)= =1+C(\floor{m/2}+1, \floor{n/2}+1)-C(\floor{m/2}, \floor{n/2}), \rem{еумй $mn\ge 1$}, $$ нщ нпцен чщчеуфй уппфопыеойе $$ C(m+1, n+1)-C(m,n)=t+2+\floor{n/2^{t+1}}, \rem{еумй~$n\ge m \ge 1$ й~$t=\floor{\log_2 m}$.} \eqno(5) $$ Умедпчбфемшоп, $$ C(m, m+r)=B(m)+m+R_m(r) \rem{ртй $m\ge0$, $r\ge0$,} \eqno (6) $$ зде $B(m)$~еуфш жхолгйс "вйобтопк чуфбчлй"~$\sum_{1\le k\le m}\ceil{\log_2 k}$ йъ уппфопыеойс~(5.3.1-3), б $R_m(r)$~пвпъобюбеф ухннх ретчщи пф юмеопч тсдб $$ \floor{{r+0\over1}}+\floor{{r+1\over2}}+\floor{{r+2\over4}}+ \floor{{r+3\over4}}+\floor{{r+4\over8}}+\cdots+ \floor{{r+j\over2^{\floor{\log_2 j}+1}}}+\ldots\,. \eqno(7) $$ Еумй це~$r=0$, рпмхюбен чбцощк юбуфощк умхюбк $$ C(m,m)=B(m)+m. \eqno(8) $$ Лтпне фпзп, еумй~$t=\ceil{\log_2 m}$, фп $$ \eqalign{ R_m(r+2^t) &= R_m(r)+1\cdot 2^{t-1}+2\cdot 2^{t-2}+\cdots+2^{t-1}\cdot2^0+m=\cr &= R_m(r)+m+t\cdot 2^{t-1}. } $$ Умедпчбфемшоп, $C(m, n+2^t)-C(m, n)$~йнееф ртпуфпк чйд й $$ C(m, n)=\left({t\over2}+{m\over 2^t}\right) n+O(1)\rem{ ртй жйлуйтпчбоопн~$m$, $n\to\infty$, $t=\ceil{\log_2 m}$;} \eqno (9) $$ юмео~$O(1)$ уфбопчйфус ч лпоге лпогпч ретйпдйюеулпк жхолгйек пф~$n$ у дмйопк ретйпдб~$2^t$. Буйнрфпфйюеулй ртй~$n\to\infty$ чемйюйоб~$C(n, n)$ тбчоб~$n \log_2 n$ йъ~(8) й хрт.~5.3.1-15. \section Уефй у нйойнбмшощн юйумпн утбчоеойк. Рхуфш~$\hat S(n)$---нйойнбмшопе юйумп утбчоеойк, фтевхенщи ч уефй уптфйтпчлй дмс $n$~ьменеофпч; суоп, юфп~$\hat S(n)\ge S(n)$, зде~$S(n)$---нйойнбмшопе юйумп утбчоеойк, %%273 оепвипдйнпе дмс уптфйтпчлй веъ чуслйи пзтбойюеойк (ун.~р.~5.3.1). Нщ чйдемй, юфп~$\hat S(4)=5=S(4)$, рпьфпнх опчпе пзтбойюеойе ое чщъщчбеф рпфетй ьжжелфйчопуфй ртй~$n=4$; оп хце ртй~$n=5$ плбъщчбефус, юфп~$\hat S(5)=9$, ч фп чтенс лбл~$S(5)=7$. Ъбдбюб пртедемеойс~$\hat S(n)$ лбцефус еэе впмее фтхдопк, юен ъбдбюб пртедемеойс~$S(n)$; дп уйи рпт оейъчеуфоп дбце буйнрфпфйюеулпе рпчедеойе~$\hat S(n)$. Йофетеуоп ртпумедйфш йуфптйа ьфпк ъбдбюй, фбл лбл об лбцдщк опчщк ыбз ртйипдймпуш ъбфтбюйчбфш пртедемеооще хуймйс. Уефй уптфйтпчлй вщмй чретчще йуумедпчбощ Р.~О.~Бтнуфтпозпн, Т.~Дц.~Оемшупопн й Д.~Дц.~П'Лпооптпн плпмп 1954~з. [ун.~U.~S.~Patent 3029413]; пой рплбъбмй, юфп~$\hat S(n+1)\le \hat S(n)+n$. Лбл улбъбоп ч йи рбфеофопк ъбсчле, "ртймпцйч уфбтбойс, нпцоп улпоуфтхйтпчбфш ьлпопнйюоще $n$-чипдоще уптфйтхаэйе ретелмаюбфемй, йурпмшъхс хнеошыеоопе юйумп дчхичипдощи уптфйтхаэйи ретелмаюбфемек"; пой ртйчемй ртйнетщ лпоуфтхлгйк дмс~$4\le n \le 8$, йурпмшъпчбч уппфчефуфчеооп 5, 9, 12, 18 й 19~лпнрбтбфптпч. Тбвпфбс дбмее обд ьфпк ъбдбюек, Оемшупо упчнеуфоп у Т.~Ю.~Впъе еэе дп~1960~з. тбътбвпфбмй пвэха ртпгедхтх дмс рпуфтпеойс уефек уптфйтпчлй, рплбъщчбаэха, юфп~$\hat S(2^n)\le3^n-2^n$ ртй чуеи~$n$, рпьфпнх~$\hat S(n)=O(n^{\log_2 3})=O(n^{1.585})$. Впъе й~Оемшупо прхвмйлпчбмй учпк йофетеуощк нефпд ч {\sl JACM,\/} {\bf 9} (1962), 282--296, чщулбъбч ртедрпмпцеойе, юфп ьфп обймхюыйк чпънпцощк теъхмшфбф; Ф.~О.~Ийввбтд [{\sl JACM,\/} {\bf 10} (1963), 142--150] обыем бобмпзйюощк, оп оеулпмшлп впмее ртпуфпк нефпд, ч лпфптпн йурпмшъхефус фблпе це юйумп утбчоеойк, рпдлтерйч фен убнщн ьфп ртедрпмпцеойе. Ч 1964~з.\ Т.~Х.~Жмпкд й~Д.~Ь.~Лохф йурпмшъпчбмй опчщк рпдипд л ьфпк ъбдбюе, ртйчедыйк йи л буйнрфпфйюеулпк пгеоле чйдб~$\hat S(n)=O(n^{1+c/\sqrt{\log n}})$. Тбвпфбс оеъбчйуйнп, Л.~Ь.~Вьфюет пфлтщм прйубооха чщые пвэха уфтбфезйа умйсойс; йурпмшъхс юйумп лпнрбтбфптпч, пртедемсенпе лбл $$ c(1)=0, c(n)=c(\ceil{n/2})+c(\floor{n/2})+C(\ceil{n/2}, \floor{n/2}) \rem{ртй $n\ge2$,} \eqno (10) $$ по дплбъбм, юфп (ун.~хрт.~5.2.2-14) $$ c(2^t)=(t^2-t+4)2^{t-2}-1, $$ й пфуадб чщчем, юфп~$\hat S(n)=O(n(\log n)^2)$. Лбл Вьфюет, фбл й Жмпкд у Лохфпн прхвмйлпчбмй учпй лпоуфтхлгйй мйыш юетеъ оелпфптпе чтенс [{\sl Notices of the Amer.\ Math.\ Soc.,\/} {\bf 14} (1967), 283; Proc.\ AFIPS Spring Joint Computer Conference, {\bf 32} (1968), 307--314]. %%274 Лпе-лпнх хдбмпуш уплтбфйфш юйумп лпнрбтбфптпч, йурпмшъхенщи ч лпоуфтхлгйй умйсойс у пвнеобнй, ртедмпцеоопк Вьфюетпн; ч умедхаэек фбвмйге рплбъбощ дбймхюыйе йъ йъчеуфощи ч обуфпсэее чтенс четиойи пгеопл дмс~$\hat S(n)$: $$ \matrix{ \hfill n=1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \cr \hfill c(n)=0 & 1 & 3 & 5 & 9 & 12 & 16 & 19 & 26 & 31 & 37 & 41 & 48 & 53 & 59 & 63 \cr \hfill \hat S(n)\le 0 & 1 & 3 & 5 & 9 & 12 & 16 & 19 & 25 & 29 & 35 & 39 & 46 & 51 & 56 & 60\cr } \eqno(11) $$ Фбл лбл~$\hat S(n)8$. Еумй~$n\le 8$, фп фблбс уптфйтпчлб ьлчйчбмеофоб рп лпмйюеуфчх лпнрбтбфптпч лпоуфтхлгйй Впъе й~Оемшупоб. Жмпкд й~Лохф дплбъбмй ч 1964--1966~зз., юфп хлбъбооще ъобюеойс~$\hat S(n)$ \emph{фпюощ} ртй~$n<8$ [ун.\ A Survey of Combinatorial Theory (North-Holland, 1973), 163--172]; ъобюеойс~$\hat S(n)$ ртй~$n>8$ дп уйи рпт оейъчеуфощ. Лпоуфтхлгйй, ртйчпдсэйе л хлбъбоощн чщые ъобюеойсн дмс~$\hat S(n)$, йъпвтбцеощ об тйу.~49. Уефш ртй~$n=9$, пуопчбообс об йофетеуопн фтеирхфечпн умйсойй, вщмб обкдеоб Т.~Х.~Жмпкдпн ч 1964~з.; хуфбопчйфш ее уртбчедмйчпуфш нпцоп ртй рпнпэй пвэезп ртйогйрб, прйубоопзп ч хрт.~27. Уефш ртй~$n=10$ ч~1969~з.\ рпуфтпйм Б.~Чблунбо; по тбуунбфтйчбм чипдщ лбл ретеуфбопчлй нопцеуфчб~$\set{1, 2,~\ldots, 10}$ й рщфбмус, упитбосс оелпфптха уйннефтйа, обулпмшлп чпънпцоп хнеошыйфш юйумп ъобюеойк, лпфптще нпзхф рпсчмсфшус ч лбцдпк уфтпле об дбоопк уфбдйй. Ч 1969~з. З.~Ыбрйтп обыем уефш уптфйтпчлй 16~ьменеофпч у 62~лпнрбтбфптбнй, й ьфп вщмп чеушнб оепцйдбооп, рпулпмшлх нефпд Вьфюетб (63~утбчоеойс), лбъбмпуш, йурпмшъхеф чуе чпънпцопуфй, еумй $n$~счмсефус уфереоша~2. Н.~Х.~Зтйо чулпте рпуме фпзп, лбл по пъоблпнймус у лпоуфтхлгйек Ыбрйтп, рпчетз чуеи ч еэе впмшыее йъхнмеойе, обкдс уптфйтпчлх у 60~утбчоеойснй, рплбъбооха об тйу.~49. Ретчбс юбуфш лпоуфтхлгйй Зтйоб дпчпмшоп ртпуфб дмс рпойнбойс; рпуме фпзп лбл чщрпмоеощ 32~претбгйй утбчоеойс-пвнеоб умечб пф рхолфйтопк мйойй, чуе ртснще нпцоп фбл рпнефйфш 16~рпднопцеуфчбнй~$\set{a, b, c, d}$, юфпвщ ртп ртснха, рпнеюеооха~$s$, вщмп йъчеуфоп, юфп поб упдетцйф юйумб, неошыйе ймй тбчоще упдетцйнпнх ртснпк, рпнеюеоопк~$t$, чуслйк тбъ, лпздб $s$~еуфш рпднопцеуфчп~$t$. Упуфпсойе уптфйтпчлй ч ьфпф нпнеоф пвухцдбефус впмее рпдтпвоп ч хрт.~32. Пдоблп утбчоеойс, чщрпмосенще об рпумедхаэйи хтпчоси, уфбопчсфус упчетыеооп ъбзбдпюощнй, й дп уйи рпт ойлфп ое ъобеф, лбл пвпвэйфш ьфх лпоуфтхлгйа, юфпвщ рпмхюйфш уфпмш це ьжжелфйчоще уефй дмс впмшыйи ъобюеойк~$n$. %%275 Ыбрйтп й Зтйо пфлтщмй фблце йъпвтбцеооха об тйу.~49 уефш дмс~$n=12$. Иптпыйе уефй дмс~$n=11$, 13, 14 й~15 нпцоп рпмхюйфш, хдбмйч ойцоаа ртснха уефй дмс~$n+1$ чнеуфе уп чуенй лпнрбтбфптбнй, рпдупедйоеоощнй л ьфпк мйойй. \picture{Тйу. 49. Ьжжелфйчоще уефй уптфйтпчлй.} Обймхюыйе йъчеуфоще л обуфпсэенх нпнеофх уефй дмс~$n\to\infty$ ун.~ч дплфптулпк дйууетфбгйй Д.~Чбо~Чптйуб (Stanford University, 1971); езп уефй фтевхаф буйнрфпфйюеулй %% 276 ${1\over 4}n(\log_2 n)^2-\alpha n \log_2 n$~лпнрбтбфптпч, зде~$\alpha={1\over4}+{1\over6}\sum_{k\ge0}2^{-2^k-k}\approx0.356~852$. \section Уефй у нйойнбмшощн чтенеоен. Ч жйъйюеулйи тебмйъбгйси уефек уптфйтпчлй й об рбтбммемшощи ЬЧН нпцоп чщрпмосфш оеретеуелбаэйеус претбгйй утбчоеойс-пвнеоб пдопчтенеооп, рпьфпнх лбцефус еуфеуфчеоощн рпрщфбфшус нйойнйъйтпчбфш чтенс ъбдетцлй. Рп оелпфптпн тбънщымеойй ъблмаюбен, юфп чтенс ъбдетцлй уефй уптфйтпчлй тбчоп нблуйнбмшопнх юйумх лпнрбтбфптпч, ртймезбаэйи л лблпнх-мйвп "рхфй" юетеъ уефш, еумй пртедемйфш рхфш лбл фтбелфптйа мавпзп дчйцеойс умечб обртбчп, \picture{Тйу.~50. Чщрпмоеойе лбцдпзп утбчоеойс ч обйвпмее тбоойк йъ чпънпцощи нпнеофпч.} чпънпцоп, у ретеипдпн у пдопк ртснпк об дтхзха юетеъ лпнрбтбфптщ. Х лбцдпзп лпнрбтбфптб нщ нпцен рпуфбчйфш рптсдлпчщк опнет, хлбъщчбаэйк убнщк тбоойк нпнеоф, лпздб нпцеф вщфш чщрпмоеоп утбчоеойе; ьфпф опнет об едйойгх впмшые, юен нблуйнбмшощк опнет х лпнрбтбфптпч, ртедыеуфчхаэйи дбоопнх. (Ун.~тйу.~50(a); ч юбуфй~(b) ьфпзп тйухолб рплбъбоб фб це уефш, рететйупчбообс фбл, юфпвщ лбцдпе утбчоеойе чщрпмосмпуш ч обйвпмее тбоойк чпънпцощк нпнеоф.) Ч прйубоопк чщые уефй Вьфюетб дмс юефоп-оеюефопзп умйсойс ъбфтбюйчбефус $T_b(m,n)$~едйойг чтенеой, зде~$T_b(m,0)=T_b(0, n)=0$, $T_B(1,1)=1$ й $$ T_B(m, n)=1+\max(T_B(\floor{m/2}, \floor{n/2}), T_B(\ceil{m/2}, \ceil{n/2})) \rem{дмс~$mn\ge 2$.} $$ Йурпмшъхс ьфй уппфопыеойс, нпцоп дплбъбфш рп йодхлгйй, юфп~$T_B(m, n+1)\ge T_B(m,n)$; умедпчбфемшоп, $T_B(m, n)=1+T_B(\ceil{m/2}, \ceil{n/2})$ дмс~$mn\ge2$, б пфуадб ъблмаюбен, юфп $$ T_B(m,n)=1+\ceil{\log_2 \max (m,n)} \rem{дмс $mn\ge1$.} \eqno (12) $$ Фблйн пвтбъпн, лбл рплбъбоп ч хрт.~5, нефпд уптфйтпчлй Вьфюетб йнееф чтенс ъбдетцлй $$ \perm{1+\ceil{\log_2 n}}{2}. \eqno(13) $$ %%277 Рхуфш $\hat T(n)$---нйойнбмшопе чтенс ъбдетцлй, дпуфйцйнпе ч мавпк уефй уптфйтпчлй $n$~ьменеофпч. Оелпфптще йъ прйубоощи чщые уефек нпцоп хмхюыйфш, ое йурпмшъпчбч дпрпмойфемшощи лпнрбтбфптпч, фбл, юфпвщ пой йнемй неошыее чтенс ъбдетцлй, лбл \picture{Тйу.~51. Уефй уптфйтпчлй, лпфптще оепвщлопчеооп вщуфтщ, еумй утбчоеойс чщрпмосафус рбтбммемшоп.} рплбъбоп об тйу.~51 дмс~$n=6$ й~$n=9$, б ч хрт.~7---дмс~$n=10$. Нпцоп рпмхюйфш еэе неошыее чтенс ъбдетцлй, еумй дпвбчйфш пдйо ймй дчб дпрпмойфемшощи нпдхмс, лбл рплбъщчбаф уефй дмс~$n=10$, 12 й~16 об тйу.~51. Ьфй рпуфтпеойс ртйчпдсф л умедха- %%378 эйн четиойн пгеолбн дмс~$T(n)$ ртй хнетеоощи ъобюеойси~$n$: $$ \matrix{ \hfill n=1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16\cr \hfill \hat T(n)\le 0 & 1 & 3 & 3 & 5 & 5 & 6 & 6 & 7 & 7 & 8 & 8 & 9 & 9 & 9 & 9\cr } \eqno(14) $$ Йъчеуфоп, юфп ртйчедеооще ъдеуш ъобюеойс фпюощ ртй~$n\le 8$ (ун.~хрт.~4). Уефй об тйу.~51 ъбумхцйчбаф фэбфемшопзп йъхюеойс, рпулпмшлх чпчуе ое пюечйдоп, юфп пой зпдсфус дмс уптфйтпчлй; ьфй уефй вщмй пфлтщфщ ч~1969--1971~зз. З.~Ыбрйтп ($n=6$, 9, 12) й~Д.~Чбо~Чптйупн ($n=10$, 16). \section Уефй умйсойс. Рхуфш $\hat M(m, n)$~пвпъобюбеф нйойнбмшопе юйумп лпнрбтбфптпч, оепвипдйнщи дмс уефй, лпфптбс умйчбеф $m$~ьменеофпч~$x_1~\le~\ldots \le x_m$ у~$n$~ьменеофбнй~$y_1\le\ldots \le y_n$, пвтбъхс пфуптфйтпчбооха рпумедпчбфемшопуфш~$z_1\le \ldots \le z_{m+n}$. Л обуфпсэенх чтенеой ое пфлтщфп ой пдопк уефй умйсойс, лпфптбс вщмб вщ мхюые юефоп-оеюефопзп умйсойс, прйубоопзп чщые; умедпчбфемшоп, жхолгйс~$C(m, n)$ ч~(6) ртедуфбчмсеф обймхюыха йъчеуфоха четиоаа пгеолх дмс~$\hat M(m, n)$. Т.~Х.~Жмпкд пвобтхцйм йофетеуощк урпупв, рпъчпмсаэйк пртедемйфш \emph{ойцойе} пгеолй ч ьфпк ъбдбюе умйсойс. \proclaim Фептенб~F. Ртй чуеи~$n\ge 1$ уртбчедмйчп оетбчеоуфчп~$\hat M (2n, 2n)\ge 2\hat M(n, n)+n$. \proof Тбуунпфтйн уефш у~$\hat M(2n, 2n)$~лпнрбтбфптощнй нпдхмснй, урпупвоха уптфйтпчбфш чуе чипдоще рпумедпчбфемшопуфй~$\$, фблйе, юфп~$z_1\le z_3\le\ldots \le z_{4n-1}$ й~$z_2\le z_4\le\ldots\le z_{4n}$. Нщ нпцен уюйфбфш, юфп лбцдщк нпдхмш ъбнеосеф~$(z_i, z_j)$ об~$(\min(z_i, z_j, \max(z_i, z_j))$ ртй оелпфптщи~$i2n$ й~$j>2n$; \item{c)}~$i\le 2n$ й~$j>2n$. \medskip} Лмбуу~(a) дпмцео упдетцбфш рп лтбкоек нете $\hat M(n, n)$~лпнрбтбфптпч, фбл лбл $z_{2n+1}$, $z_{2n+2}$,~\dots, $z_{4n}$ нпзхф хце обипдйфшус об учпйи неуфби, лпздб умйсойе обюйобефус; бобмпзйюоп ч лмбууе~(b) дпмцоп вщфш рп лтбкоек нете $\hat M(n, n)$~лпнрбтбфптпч. Лтпне фпзп, лбл рплбъщчбеф чипдобс рпумедпчбфемшопуфш~$\<0, 1, 0, 1,~\ldots, 0, 1>$, лмбуу~(c) упдетцйф ое неоее $n$~лпнрбтбфптпч, фбл лбл $n$~охмек дпмцощ ретенеуфйфшус йъ~$\set{z_{2n+1},~\ldots, z_{4n}}$ ч~$\set{z_1,~\ldots, z_{2n}}$. \proofend Нопзплтбфопе ртйнеоеойе фептенщ~F дплбъщчбеф, юфп~$\hat M(2^m, 2^m)\ge{1\over2}(m+2) 2^m$; умедпчбфемшоп, $\hat M(n, n) \ge {1\over2}n \log_2 n+O(n)$. %%279 Умйсойе \emph{веъ} уефечпзп пзтбойюеойс фтевхеф мйыш $M(n,n)=2n-1$~утбчоеойк; фблйн пвтбъпн, нщ дплбъбмй, юфп уефечпе умйсойе умпцоее рп ухэеуфчх, юен умйсойе чппвэе. Юефоп-оеюефопе умйсойе рплбъщчбеф, юфп~$\hat M(n,n)\le C(n, n)= n\log_2 n+O(n)$, рпьфпнх буйнрфпфйюеулпе рпчедеойе~$\hat M(n, n)$ йъчеуфоп у фпюопуфша дп нопцйфемс~2. (Фпюоще ъобюеойс~$\hat M(n, n)$ йъчеуфощ дмс~$n\le 5$; ун.~хрт.~9.) Б.~Л.~Сп й~Ж.~Ж.~Сп дплбъбмй, юфп~$\hat M(2,n)=C(2, n)=\ceil{{3\over2}n}$ й~$\hat M(m, n)\ge{1\over2}n\log_2(m+1)$ ртй~$m$ йъ $p$~юйуем вхден объщчбфш \dfn{вйфпоопк,} еумй~$z_1\ge\ldots\ge z_k\le\ldots\le z_p$ дмс оелпфптпзп~$k$, $1\le k \le p$ (утбчойфе ьфп у пвщюощн пртедемеойен "нпопфпоощи" рпумедпчбфемшопуфек). Вйфпоощк уптфйтпчэйл рптсдлб~$p$---ьфп лпнрбтбфптобс уефш, урпупвобс уптфйтпчбфш ч оехвщчбаэен рптсдле мавха вйфпооха рпумедпчбфемшопуфш дмйощ~$p$. Ъбдбюб умйсойс~$x_1\le\ldots\le x_m$ у~$y_1\le\ldots\le y_n$ счмсефус юбуфощн умхюбен ъбдбюй вйфпоопк уптфйтпчлй, фбл лбл умйсойе нпцоп пухэеуфчйфш, ртйнеойч л рпумедпчбфемшопуфй~$\$ вйфпоощк уптфйтпчэйл рптсдлб~$m+n$. Ъбнефйн, юфп еумй рпумедпчбфемшопуфш~$\$ вйфпообс, фп фблпчщнй це счмсафус й чуе ее рпдрпумедпчбфемшопуфй. Чулпте рпуме фпзп, лбл Вьфюет пфлтщм уефй юефоп-оеюефопзп умйсойс, по пвобтхцйм, юфп бобмпзйюощн пвтбъпн нпцоп рпуфтпйфш вйфпоощк уптфйтпчэйл рптсдлб~$p$, уобюбмб оеъбчйуйнп уптфйтхс вйфпооще рпдрпумедпчбфемшопуфй~$\$ й~$\$, б ъбфен чщрпмосс утбчоеойс-пвнеощ~$z_1:z_2$, $z_3:z_4$,~$\ldots\,$. (Дплбъбфемшуфчп ун.~ч~хрт.~10.) Еумй уппфчефуфчхаэее юйумп лпнрбтбфптощи нпдхмек пвпъобюйфш юетеъ~$C'(p)$, фп вхден йнефш $$ C'(p)=C'(\ceil{p/2})+C'(\floor{p/2})+\floor{p/2} \rem{ртй $p\ge2$.} \eqno (15) $$ б чтенс ъбдетцлй, пюечйдоп, тбчоп~$\ceil{\log_2 p}$. Об~тйу.~52 рплбъбо вйфпоощк уптфйтпчэйл рптсдлб~7, рпуфтпеоощк ьфйн урпупвпн; по нпцеф вщфш йурпмшъпчбо й лбл~$(3, 4)$, й лбл $(2, 5)\hbox{-уефш}$ умйсойс у ъбдетцлпк ч фтй едйойгщ; юефоп-оеюефопе умйсойе дмс~$m=2$ й~$n=5$ йнееф об пдйо лпнрбтбфпт неошые, оп об пдйо хтпчеош ъбдетцлй впмшые. %%280 Вйфпоощк уптфйтпчэйл Вьфюетб рптсдлб~$2^k$ пупвеооп йофетеуео; по упуфпйф йъ $k$~хтпчоек рп $2^{k-1}$~лпнрбтбфптпч ч лбцдпн. Ъбохнетхен чипдоще ртснще~$z_0$, $z_1$,~\dots, $z_{2^k-1}$; ртй ьфпн ьменеоф~2, утбчойчбефус у~$z_j$ об хтпчое~$l$ фпздб й фпмшлп фпздб, лпздб дчпйюоще ртедуфбчмеойс~$i$ й~$j$ тбъмйюбафус фпмшлп ч $l\hbox{-н}$~вйфе умечб. Ьфб ртпуфбс уфтхлфхтб ртйчпдйф л рбтбммемшопк уефй уптфйтпчлй, лпфптбс фбл це вщуфтб, лбл пвнеообс уптфйтпчлб \picture{Тйу.~52. Вйфпоощк уптфйтпчэйл Вьфюетб рптсдлб~7.} уп умйсойен (бмзптйфн~5.2.2M), оп ъобюйфемшоп ртпэе дмс тебмйъбгйй. (Ун.~хрт.~11 й~13.) Еумй~$m=n$, фп оефтхдоп чйдефш, юфп й юефоп-оеюефопе умйсойе, й вйфпоощк уптфйтпчэйл Вьфюетб пвеуреюйчбаф бвупмафощк нйойнхн чтенеой ъбдетцлй, дпуфйцйнпзп ч мавпк уефй умйсойс. \picture{Тйу.~53. Пдйо ьменеоф умйчбефус у ыеуфша дтхзйнй у тбъчефчмеойен, юфпвщ дпуфйюш нйойнбмшоп чпънпцопзп чтенеой ъбдетцлй.} Ч $(n, n)$-уефй умйсойс $n\hbox{-к}$ рп чемйюйое чщипд (уюйфбс пф обйнеошыезп) дпмцео ъбчйуефш пф чуеи $2n$~чипдпч, й еумй езп нпцоп чщюйумйфш ъб $l$~ыбзпч, фп по вхдеф ъбчйуефш ое впмее, юен пф $2^l$~чипдпч; рпьфпнх~$2^l\ge 2n$, $l\ge \ceil{\log_2 (2n)}$. Еумй~$m$ й нщ ипфйн чщвтбфш $t$~обйвпмшыйи; Ч.~Е.~Бмелуееч [{\sl Лйветоефйлб,\/} {\bf 5}, 5 (1969), 99--103] ъбнефйм, юфп ьфп нпцеф вщфш чщрпмоеоп, еумй уобюбмб пфуптфйтпчбфш~$\$ й~$\$, б ъбфен утбчойфш й рпнеосфш неуфбнй $$ x_1:x_{2t}, x_2:x_{2t-1},~\ldots, x_t:x_{t+1}. \eqno(17) $$ Фбл лбл ой ч пдопк йъ ьфйи рбт ое нпцеф упдетцбфшус впмее пдопзп йъ обйвпмшыйи $t$~ьменеофпч (рпюенх?), фп ртпгедхтб Бмелуеечб дпмцоб чщвтбфш $t$~обйвпмшыйи ьменеофпч. Еумй обн охцоп чщвтбфш $t$~обйвпмшыйи йъ $nt$~ьменеофпч, фп нщ нпцен ртйнеойфш ьфх ртпгедхтх $n-1$~тбъ (йулмаюбс лбцдщк тбъ $t$~ьменеофпч); умедпчбфемшоп, $$ \hat U_t(nt)\le (n-1)(2\hat S(t)+t). \eqno(18) $$ Бмелуееч фблце рпмхюйм йофетеуоха \emph{ойцоаа} пгеолх дмс ъбдбюй чщвптб. %%282 \proclaim Фептенб~A. $\hat U_t (n) \ge (n-t)\ceil{\log_2 (t+1)}$. \proof Хдпвоее тбуунбфтйчбфш ьлчйчбмеофоха ъбдбюх чщвптб \emph{обйнеошыйи} $t$~ьменеофпч. Плпмп лбцдпк ртснпк лпнрбтбфптопк уефй нпцоп чщрйубфш юйумб~$(l, u)$, лбл рплбъбоп об тйу.~54, зде~$l$ й~$u$ пвпъобюбаф уппфчефуфчеооп нйойнбмшопе й \picture{Тйу.~54. Пфдемеойе юефщтеи обйвпмшыйи пф юефщтеи обйнеошыйи. (Юйумб обд ртснщнй йурпмшъхафус ч дплбъбфемшуфче фептенщ~A.)} нблуйнбмшопе ъобюеойс, лпфптще нпзхф рпсчйфшус ч ьфпн неуфе, еумй чипдпн умхцйф ретеуфбопчлб~$\set{1, 2,~\ldots, n}$. Рхуфш~$l_i$ й~$l_j$---ойцойе пгеолй об ртснщи~$i$ й~$j$ ретед утбчоеойен~$x_i:x_j$, й рхуфш~$l'_i$ й~$l'_j$---уппфчефуфчхаэйе ойцойе пгеолй рпуме ьфпзп \picture{Тйу.~55. Йобс йофетртефбгйс уефй, йъпвтбцеоопк об тйу.~54.} утбчоеойс. Пюечйдоп, юфп~$l'_i=\min(l_i, l_j)$, б ч хрт.~24 дплбъщчбефус (оепюечйдопе) уппфопыеойе $$ l'_j\le l_i+l_j. \eqno (19) $$ Феретш дбдйн дтхзха йофетртефбгйа декуфчйс уефй (тйу.~55); ртедрпмпцйн, юфп об чуеи чипдощи ртснщи упдетцйфус охмш, %%283 б лбцдщк "лпнрбтбфпт" рпнеэбеф феретш об четиоаа ртснха неошыйк йъ езп чипдпч, б об ойцоаа ртснха---впмшыйк чипд \emph{рмау пдйо.} Рпмхюбаэйеус юйумб~$\$ пвмбдбаф учпкуфчпн $$ 2^{m_i}\ge l_i \eqno(20) $$ ч мавпн неуфе уефй, фбл лбл ьфп учпкуфчп ретчпобюбмшоп уртбчедмйчп й упитбосефус лбцдщн лпнрбтбфптпн ч уймх~(19). Лтпне фпзп, плпоюбфемшопе ъобюеойе $$ m_1+m_2+\cdots+m_n $$ тбчоп пвэенх юйумх лпнрбтбфптпч ч уефй, фбл лбл лбцдщк лпнрбтбфпт дпвбчмсеф л ьфпк ухнне едйойгх. Еумй уефш чщвйтбеф обйнеошыйе $t$~юйуем, фп~$n-t$ йъ юйуем~$l_i$ впмшые ймй тбчощ~$t+1$; умедпчбфемшоп, $n-t$ йъ юйуем~$m_i$ дпмцощ вщфш~$\ge \ceil{\log_2 (t+1)}$. \proofend Ойцосс пгеолб ч фептене~A плбъщчбефус фпюопк, еумй~$t=1$ ймй~$t=2$ (ун.~хрт.~19). Ч фбвм.~1 дбощ ъобюеойс~$\hat U_t(n)$, $\hat V_t(n)$ й~$\hat W_t(n)$ дмс оевпмшыйи~$t$ й~$n$. \htable{Фбвмйгб~1}% {Утбчоеойс, оепвипдйнще дмс уефек чщвптб ($\hat U_t(n)$, $\hat V_t(n)$, $\hat W_t(n)$)}% {\strut\hfill$#$\hfill&&\bskip\hfill$#$\hfill\bskip\cr & t=1 & t=2 & t=3 & t=4 & t=5 & t=6 \cr \noalign{\hrule} n=1 & (0,0,0)\cr n=2 & (1,1,1)& (0,1,1)\cr n=3 & (2,2,2)& (2,3,3)& (0,2,3) \cr n=4 & (3,3,3)& (4,5,5)& (3,5,5) & (0,3,5) \cr n=5 & (4,4,4)& (6,7,7)& (6,7,8) & (4,7,9) & (0,4,9) \cr n=6 & (5,5,5)& (8,9,9)& (8,10,10)& (8,10,12) & (5,9,12) & (0,5,12) \cr \noalign{\hrule} } \excercises (РЕТЧБС ЮБУФШ) Дбмее ч оеулпмшлйи хртбцоеойси дбоп впмее змхвплпе тбъчйфйе фептйй уефек уптфйтпчлй, рпьфпнх вхдеф хдпвоп ччеуфй оелпфптще пвпъобюеойс. Чнеуфп нпдхмс утбчоеойс-пвнеоб вхден рйубфш~$[i:j]$. Уефш у $n$~чипдбнй й $r$~лпнрбтбфптощнй нпдхмснй ъбрйыен лбл~$[i_1:j_1]\,[i_2:j_2]\ldots[i_r:j_r]$, зде чуе~$i$ й~$j$ неошые ймй тбчощ~$n$; дмс лтбфлпуфй вхден объщчбфш ее $n\hbox{-уефша}$. Уефш объщчбефус \dfn{уфбодбтфопк,} еумй~$i_q$ еуфш $n\hbox{-челфпт}$, б $\alpha$~еуфш $n\hbox{-уефш}$, фп йурпмшъхен пвпъобюеойе~$x\alpha$ дмс челфптб юйуем~$\<(x\alpha)_1,~\ldots, (x\alpha)_n>$, рптпцдеоощи уефша. Рпмпцйн фблце дмс лтбфлпуфй~$a\lor b=\max(a, b)$, %%284 $a\land b=\min(a, b)$, $\bar a=1-a$; фпздб~$(x[i:j])_i=x_i\land x_j$, $(x[i:j])_j=x_i\lor x_j$ й~$(x[i:j])_k=x_k$ дмс~$i\ne k \ne j$. Вхден зпчптйфш, юфп $\alpha$~счмсефус \emph{уефша уптфйтпчлй,} фпздб й фпмшлп фпздб, лпздб~$(x\alpha)_i\le(x\alpha)_{i+1}$ дмс~$1\le i < n$ й чуеи~$x$. Уйнчпм~$e^{(i)}$ пвпъобюбеф челфпт, х лпфптпзп ч рпъйгйй~$i$ обипдйфус~1, б ч пуфбмшощи неуфби~0; фблйн пвтбъпн, $(e^{(i)})_j=\delta_{ij}$. Уйнчпм~$D_n$ пвпъобюбеф нопцеуфчп чуеи $2^n$~$n\hbox{-неуфощи}$ челфптпч йъ~0 й~1, б $P_n$~пвпъобюбеф нопцеуфчп чуеи $n!$~челфптпч, счмсаэйиус ретеуфбопчлбнй~$\set{1, 2,~\ldots, n}$. Нщ вхден йурпмшъпчбфш пвпъобюеойс~$x\land y$ й~$x\lor y$ дмс челфптпч~$\$ й~$\$ й вхден рйубфш~$x\le y$, еумй~$x_i\le y_i$ ртй чуеи~$i$. Фблйн пвтбъпн, $x\le y$~фпздб й фпмшлп фпздб, лпздб~$x\lor y= y$, й фпздб й фпмшлп фпздб, лпздб \picture{Тйу.~56. Оеуфбодбтфобс уефш, пуопчбообс об вйфпоопк уптфйтпчле.} $x\land y=x$. Еумй~$x$ й~$y$ мецбф ч~$D_n$, фп вхден зпчптйфш, юфп \dfn{$x$~рплтщчбеф~$y$,} еумй~$x=y\lor e^{(i)}\ne y$ ртй оелпфптпн~$i$. Облпоег, дмс чуеи~$x$ ч~$D_n$ рхуфш~$\nu(x)$ вхдеф юйумпн едйойг ч $x$, a~$\zeta(x)$---юйумпн охмек; фблйн пвтбъпн, $\nu(x)+\zeta(x)=n$. \ex[20] Обтйухкфе уефш юефоп-оеюефопзп умйсойс дмс~$m=3$ й~$n=5$. \ex[22] Рплбцйфе, юфп бмзптйфнх уптфйтпчлй Ч.~Ртбффб (ун.~хрт.~5.2.1-30) уппфчефуфчхеф уефш уптфйтпчлй $n$~ьменеофпч, йнеаэбс ртйвмйъйфемшоп $(\log_2 n) \times (\log_3 n)$~хтпчоек ъбдетцлй. Обтйухкфе фблха уефш дмс~$n=12$. \ex[M20] (Л.~Ь.~Вьфюет.) Обкдйфе ртпуфпе уппфопыеойе нецдх~$C(m, m-1)$ й~$C(m,m)$. \rex[Н23] Дплбцйфе, юфп~$\hat T(6) =5$. \ex[Н21] Дплбцйфе, юфп чщтбцеойе~(13) декуфчйфемшоп пртедемсеф чтенс ъбдетцлй дмс уефй уптфйтпчлй, прйубоопк уппфопыеойснй~(10). \ex[28] Рхуфш~$T(n)$ вхдеф нйойнбмшощн юйумпн уфбдйк, фтевхенщи дмс уптфйтпчлй у \emph{пдопчтенеоощн чщрпмоеойен оеретеуелбаэйиус утбчоеойк} (веъ уефечпзп пзтбойюеойс); лбцдпе фблпе нопцеуфчп утбчоеойк нпцеф вщфш ртедуфбчмеоп хъмпн, упдетцбэйн нопцеуфчп рбт~$i_1:j_1$, $i_2:j_2$,~\dots, $i_r:j_r$, зде чуе~$i_1$, $j_1$, $i_2$, $j_2$,~\dots, $i_r$, $j_r$ тбъмйюощ; пф ьфпзп хъмб пфипдйф чойъ $2^r$~чефчек, %%285 уппфчефуфчхаэйи умхюбсн $$ \eqalign{ &\<{K_{i_1};\cr &\<{K_{i_1}>K_{j_1}, K_{i_2} \hbox{й~ф.~д.}\cr } $$ Дплбцйфе, юфп~$T(5) =T (6) = 5$. \ex[25] Рплбцйфе, юфп еумй рпумедойк лпнрбтбфпт уефй дмс~$n=10$ об~тйу.~49 рпнеуфйфш оерпутедуфчеооп ретед чфптщн й фтефшйн у лпогб лпнрбтбфптбнй, фп уефш рп-ртецоенх вхдеф уптфйтпчбфш. \ex[Н20] Дплбцйфе, юфп~$\hat M(m_1+m_2, n_1+n_2)\ge \hat M(m_1, n_1)+ \hat M(m_2, n_2)+\min(m_1, n_2)$ ртй~$m_1, m_2, n_1, n2\ge 0$. \ex[Н25] (Т.~Х.~Жмпкд.) Дплбцйфе, юфп~$\hat M(3,3)=6$, $\hat M(4,4)=9$, $\hat M(5,5)=13$. \ex[Н22] Дплбцйфе, юфп вйфпоощк уптфйтпчэйл Вьфюетб, лбл по пртедемео ч фелуфе ретед~(15), декуфчйфемшоп тбвпфбеф. [\emph{Хлбъбойе.} Дпуфбфпюоп дплбъбфш, юфп вхдхф уптфйтпчбфшус чуе рпумедпчбфемшопуфй, упуфпсэйе йъ $k$~едйойг, ъб лпфптщнй умедхаф $l$~охмек, ъб лпфптщнй умедхаф $n-k-l$~едйойг.] \ex[Н23] Дплбцйфе, юфп вйфпоощк уптфйтпчэйл Вьфюетб рптсдлб~$2^p$ вхдеф уптфйтпчбфш ое фпмшлп рпумедпчбфемшопуфй~$\$, дмс лпфптщи $z_0 \ge \ldots\ge z_k \le \ldots\le z_{2^p-1}$, оп фблце й чуе рпумедпчбфемшопуфй, дмс лпфптщи $z_0\le \ldots \le z_k \ge \ldots \ge z_{2^p-1}$. [Лбл умедуфчйе ьфпзп, уефш об тйу.~56 вхдеф уптфйтпчбфш 16~ьменеофпч, фбл лбл лбцдбс уфбдйс упуфпйф йъ вйфпоощи уптфйтпчэйлпч ймй пвтбэеоощи вйфпоощи уптфйтпчэйлпч, ртйнеосенщи л рпумедпчбфемшопуфсн, лпфптще вщмй пфуптфйтпчбощ ч ртпфйчпрпмпцощи обртбчмеойси.] \ex[Н20] Дплбцйфе ймй пртпчетзойфе умедхаэее хфчетцдеойе: еумй~$x$ й~$y$---вйфпооще рпумедпчбфемшопуфй тбчопк дмйощ, фп рпумедпчбфемшопуфй~$x\lor y$ й~$x\land y$ фблце вйфпооще. \rex[24] (X.~У.~Уфпхо). Рплбцйфе, юфп уефш уптфйтпчлй дмс $2^t$~ьменеофпч нпцоп рпуфтпйфш рп уиене, ртпйммауфтйтпчбоопк дмс~$t=4$ об тйу.~57. Лбцдщк йъ $t^2$~ыбзпч ьфпк уиенщ упуфпйф йъ "йдебмшопзп фбупчбойс" ретчщи $2^{t-1}$~ьменеофпч у рпумедойнй~$2^{t-1}$, ъб лпфптщн умедхаф претбгйй, чщрпмосенще пдопчтенеооп обд $2^{t-1}$~рбтбнй упуедойи ьменеофпч. Лбцдбс йъ ьфйи претбгйк пвпъобюеоб мйвп~"$0$" (оеф претбгйй), мйвп~"$+$" (уфбодбтфощк лпнрбтбфптощк нпдхмш), мйвп~"$-$" (пвтбэеоощк лпнрбтбфптощк нпдхмш). Уптфйтпчлб ртпфелбеф ч $t$~уфбдйк рп $t$~ыбзпч лбцдбс; об рпумедоек уфбдйй чуе претбгйй ухфш~"$+$". Ч феюеойе уфбдйй~$s$ ртй~$sj_q$. Еумй фблйи йоделупч оеф, фп пуфбопчйфшус. \item{T2.}~Ъбнеойфш чуе чипцдеойс~$i_q$ об~$j_q$ й чуе чипцдеойс~$j_q$ об~$i_q$ чп чуеи лпнрбтбфптби~$[i_s:j_s]$ дмс~$q\le s \le r$. Четохфшус л ыбзх~T1.\endmark \medskip} \noindent Обртйнет, уефш~$[4:1]\,[3:2]\,[1:3]\,[2:4]\,[1:2]\,[3:4]$ ртепвтбъхефус уобюбмб ч~$[1:4]\,[3:2]\,[4:3]\,[2:1]\,[4:2]\,[3:1]$, ъбфен ч~$[1:4]\,[2:3]\,[4:2]\,[3:1]\,[4:3]\,[2:1]$, ъбфен %%286 \picture{Тйу.~57.~Уптфйтпчлб 16 ьменеофпч у "йдебмшощн фбупчбойен".} %%287 ч~$[1:4]\,[2:3]\,[2:4]\,[3:1]\,[2:3]\,[4:1]$ й~ф.~д., рплб ое рпмхюйфус уфбодбтфобс уефш~$[1:4]\,[2:3]\,[2:4]\,[1:3]\,[1:2]\,[3:4]$. \ex[Н25] Рхуфш~$D_{tn}$ вхдеф нопцеуфчпн чуеи $\perm{n}{t}$~рпумедпчбфемшопуфек $\$ йъ охмек й едйойг, йнеаэйи тпчоп $t$~едйойг. Дплбцйфе, юфп $\hat U_t(n)$~тбчоп нйойнбмшопнх юйумх лпнрбтбфптпч, лпфптще оепвипдйнщ ч уефй, уптфйтхаэек чуе ьменеофщ~$D_{tn}$; юфп $\hat V_t (n)$~тбчоп нйойнбмшопнх юйумх лпнрбтбфптпч, охцощи дмс уптфйтпчлй~$D_{tn}\cup D_{(t-1)n}$; й юфп $\hat W_t(n)$~тбчоп нйойнбмшопнх юйумх лпнрбтбфптпч, охцощи дмс уптфйтпчлй~$\bigcup_{0\le k \le t} D_{kn}$. \rex[Н20] Дплбцйфе, юфп уефш, лпфптбс пртедемсеф недйбох $2t-1$~ьменеофпч, фтевхеф ое неоее~$(t-1)\ceil{\log_2(t+1)}+\ceil{\log_2 t}$ лпнрбтбфптощи нпдхмек. [\emph{Хлбъбойе:} ун. дплбъбфемшуфчп фептенщ~A.] \ex[Н22] Дплбцйфе, юфп~$\hat U_2(n)=2n-4$ й~$\hat V_2(n)=2n-3$ дмс чуеи~$n\ge2$. \ex[24] Дплбцйфе, юфп~$\hat V_3(5)=7$. \ex[M15] Рхуфш~$\alpha$---мавбс $n\hbox{-уефш}$, б~$x$ й~$y$---дчб $n\hbox{-челфптб}$. Дплбцйфе, юфп йъ~$x\le y$ умедхеф~$x\alpha \le y\alpha$. \ex[Н15] Дплбцйфе, юфп еумй~$x$ й~$y$ ухфш $n\hbox{-челфптщ}$ декуфчйфемшощи юйуем, фп~$x\cdots y \le (x\alpha)\cdot(y\alpha)$. (Ъдеуш~$x\cdot y$---улбмстопе ртпйъчедеойе $x_1y_1+\cdots+x_ny_n$.) \ex[Н17]. Рхуфш~$\alpha$ еуфш~$n\hbox{-уефш}$. Дплбцйфе, юфп ухэеуфчхеф ретеуфбопчлб~$p\in P_n$, фблбс, юфп $(p\alpha)_i=j$ фпздб й фпмшлп фпздб, лпздб ч~$D_n$~обкдхфус челфптщ~$x$, $y$, фблйе, юфп~$x$ рплтщчбеф~$y$, $(x\alpha)_i=1$, $(y\alpha)_i=0$ й~$\zeta(y)=j$. \rex[M21] (Ч.~Е.~Бмелуееч.) Рхуфш~$\alpha$ еуфш~$n\hbox{-уефш}$; ччеден пвпъобюеойс $l_k=\min\set{ (p\alpha)_k \mid p\in P_n}$, $u_k=\max\set{(p\alpha)_k\mid p\in P_n}$ ртй~$1\le k \le n$ дмс ойцоек й четиоек зтбойг дйбрбъпоб ъобюеойк, лпфптще нпзхф рпсчмсфшус об ртснпк~$k$ чщипдб. Рхуфш~$l'_k$ й~$u'_k$---бобмпзйюоп пртедемеооще чемйюйощ дмс уефй~$\alpha'=\alpha[i:j]$. Дплбцйфе, юфп~$l'_i=l_i\land l_j$, $l'_j\le l_i+l_j$, $u'_i\ge u_+u_j-(n+1)$, $u'_j=u_i\lor u_j$. [\emph{Хлбъбойе:} дмс дбоощи челфптпч~$x$ й~$y$ йъ~$D_n$, фблйи, юфп~$(x\alpha)_i=(y\alpha)_j=0$, $\zeta(x)=l_i$, $\zeta(y)=l_j$, обкдйфе челфпт~$z$ йъ~$D_n$, фблпк, юфп~$(z\alpha')_j=0$, $\zeta(z)\le l_i+l_j$.] \ex[M30] Рхуфш~$l_k$ й~$u_k$ пртедемеощ, лбл ч хрт.~24. Дплбцйфе, юфп нопцеуфчп~$\set{(p\alpha)_k \mid p\in P_n}$ упдетцйф чуе гемще юйумб нецдх~$l_k$ й~$u_k$ члмаюйфемшоп. \ex[M24] (Т.~Х.~Жмпкд.) Рхуфш~$\alpha$ еуфш $n\hbox{-уефш}$. Дплбцйфе, юфп нопцеуфчп~$D_n\alpha=\set{x\alpha \mid x\in D_n}$ нпцеф вщфш пртедемеоп, йъ нопцеуфчб~$P_n\alpha=\set{p\alpha \mid p\in P_n}$ й, пвтбфоп, $P_n\alpha$~нпцеф вщфш пртедемеоп йъ~$D_n\alpha$. \rex[M20] Рхуфш~$x$ й~$y$---челфптщ, й рхуфш~$x\alpha$ й~$y\alpha$---пфуптфйтпчбооще челфптщ. Дплбцйфе, юфп~$(x\alpha)_i\le (y\alpha)_j$ фпздб й фпмшлп фпздб, лпздб дмс мавпк упчплхропуфй $j$~ьменеофпч йъ~$y$ нпцоп обкфй упчплхропуфш $i$~ьменеофпч йъ~$x$, фблха, юфп мавпк ьменеоф, чъсфщк йъ~$x$, неошые оелпфптпзп ьменеофб, чъсфпзп йъ~$y$, ймй тбчео енх. Йурпмшъхкфе ьфпф ртйогйр дмс дплбъбфемшуфчб фпзп, юфп \emph{еумй пфуптфйтпчбфш уфтплй мавпк нбфтйгщ, б ъбфен пфуптфйтпчбфш уфпмвгщ, фп уфтплй пуфбохфус хрптсдпюеоощнй.} \rex[Н20] Умедхаэбс дйбзтбннб рплбъщчбеф, лбл ъбрйубфш жптнхмщ дмс упдетцйнпзп чуеи мйойк уефй уптфйтпчлй юетеъ ее чипдщ: \picture{p.287} Йурпмшъхс ъблпощ лпннхфбфйчопуфй~$x\land y =y \land x$, $x\lor y = y \lor x$, ъблпощ буупгйбфйчопуфй~$x\land (y\land z)=(x\land y) \land z$, $x \lor (y \lor z) = (x \lor y) \lor z$, ъблпощ дйуфтйвхфйчопуфй $x\land (y\lor z)=(x\land y)\lor (x\land z)$, $x\lor(y\land z)=(x\lor y)\land (x\lor z)$, ъблпощ рпзмпэеойс $x\land (x\lor y)=x\lor(x\land y)=x$ й ъблпощ йденрпфеофопуфй $x\land x=x\lor x = x$, нщ нпцен учеуфй жптнхмщ ч ртбчпк юбуфй ьфпк уефй уппфчефуфчеооп л~$(a \land b \land c \land d)$, $(a\land b \land c) \lor (a\land b \land d) \lor (a\land c\land d) \lor (b \land c \land d)$, $(a\land b) \lor (a \land c) \lor (a \land d) \lor (b \land c) \lor (b \land d) \lor (c \land d)$, $a \lor b \lor c \lor d$. Дплбцйфе, %%288 юфп ч пвэен умхюбе $t\hbox{-к}$ ч рптсдле хвщчбойс ьменеоф йъ~$\set{x_1,~\ldots, x_n}$ дбефус "ьменеофбтопк уйннефтйюеулпк жхолгйек" $$ \sigma_t(x_1,~\ldots, x_n)= \bigvee \set{x_{i_1}\land x_{i_2}\land\ldots\land x_{i_t} \mid 1\le i_1 < i_2 < \ldots < i_t \le n}. $$ [Ъдеуш $\perm{n}{t}$~юмеопч пв®едйосафус претбгйек~$\vee$ чнеуфе. Фблйн пвтбъпн, ъбдбюб обипцдеойс уефй уптфйтпчлй нйойнбмшопк уфпйнпуфй ьлчйчбмеофоб ъбдбюе чщюйумеойс ьменеофбтощи уйннефтйюеулйи жхолгйк у нйойнбмшощн юйумпн уиен "й/ймй", зде об лбцдпн ыбзе дче чемйюйощ~$\phi$ й~$\psi$ ъбнеосафус об~$\phi\land\psi$ й~$\phi\lor\psi$.] \ex[M20] Дбоп, юфп~$x_1\le x_2 \le x_3$ й~$y_1\le y_2 \le y_3 \le y_4 \le y_5$ й юфп~$z_1\le z_2 \le \ldots \le z_8$---теъхмшфбф умйсойс~$x$ у~$y$. Обкдйфе чщтбцеойс дмс лбцдпзп~$z$ юетеъ~$x$ й~$y$, йурпмшъхс претбфптщ~$\land$ й~$\lor$. \ex[ЧН24] Дплбцйфе, юфп мавбс жптнхмб, упдетцбэбс~$\land$, $\lor$ й оеъбчйуйнще ретенеооще~$\set{x_1,~\ldots, x_n}$, нпцеф вщфш ртйчедеоб у йурпмшъпчбойен фпцдеуфч йъ хрт.~28 л "лбопойюеулпк" жптне~$\tau_1\lor\tau_2\lor\ldots\lor\tau_k$, ъдеуш~$k\ge1$ й лбцдщк~$\tau_i$ йнееф чйд~$\land \set{x_j \mid j \in S_i}$, зде~$S_i$---рпднопцеуфчп~$\set{1,2,~\ldots, n}$ й ойлблпе нопцеуфчп~$S_i$ ое члмаюбефус ч~$S_j$, еумй~$i\ne j$. Дплбцйфе фблце, юфп дче фблйе лбопойюеулйе жптнщ тбчощ дмс чуеи~$x_1$,~\dots, $x_n$ фпздб й фпмшлп фпздб, лпздб пой йдеофйюощ (у фпюопуфша дп рптсдлб). \ex[Н24] (Т.~Деделйод, 1897.) Рхуфш~$\delta_n$---юйумп тбъмйюощи лбопойюеулйи жптн пф~$x_1$,~\dots, $x_n$ ч унщуме хрт.~30 Фбл, $\delta_1=l$, $\delta_2=4$ й~$\delta_3=18$. Юенх тбчоп~$\delta_4$? \ex[Н28] (Н.~Х.~Зтйо.) Рхуфш~$G_1=\set{00, 01, 11}$; пртедемйн~$G_{n+1}$ лбл нопцеуфчп чуеи герпюел~$\theta\phi\psi\omega$, фблйи, юфп~$\theta$, $\phi$, $\psi$, $\omega$ йнеаф дмйох~$2^{n+1}$ й~$\theta\phi$, $\psi\omega$, $\theta\psi$ й~$\phi\omega$ ртйобдмецбф~$G_n$. Рхуфш~$\alpha$---уефш, упуфпсэбс йъ юефщтеи ретчщи хтпчоек 16-уптфйтпчэйлб, йъпвтбцеоопзп об тйу.~48. Рплбцйфе, юфп~$D_{16}\alpha=G_4$, й дплбцйфе, юфп ьфп нопцеуфчп йнееф ч фпюопуфй $\delta_4+2$~ьменеофпч. (Ун.~хрт.~31.) \rex[Н22] Ое чуе $\delta_n$~жхолгйк пф~$\$ йъ хрт.~31 нпзхф чуфтефйфшус ч лпнрбтбфптощи уефси. Б йнеооп дплбцйфе, юфп жхолгйс~$(x_1\land x_2) \lor (x_2\land x_3) \lor (x_3\land x_4)$ ое нпцеф вщфш теъхмшфбфпн ойлблпк лпнрбтбфптопк уефй пф~$\$. \ex[23] Счмсефус мй умедхаэбс уефш уефша уптфйтпчлй? \picture{p.288} \ex[20] Дплбцйфе, юфп ч мавпк \emph{уфбодбтфопк уефй} уптфйтпчлй дпмцео рп лтбкоек нете пдйо тбъ чуфтефйфшус лбцдщк йъ лпнрбтбфптпч~$[i:i+1]$ ртй~$1\le i < n$. \rex[22] Уефш об тйу.~47 упдетцйф фпмшлп \emph{лтбфюбкыйе} утбчоеойс~$[i:i+1]$; вхден объщчбфш фблйе уефй \dfn{ртйнйфйчощнй,} (a)~Дплбцйфе, юфп ртйнйфйчббс уефш уптфйтпчлй дмс $n$~ьменеофпч дпмцоб йнефш ое неоее $\perm{n}{2}$~лпнрбтбфптпч. [\emph{Хлбъбойе:} тбуунпфтйфе йочетуйй ретеуфбопчлй.] (b)~(Т.~Х.~Жмпкд, 1964.) Рхуфш~$\alpha$---ртйнйфйчобс уефш дмс $n$~ьменеофпч, б~$x$---челфпт, фблпк, юфп~$(x\alpha)_i >(x\alpha)_j$ ртй оелпфптщи~$i(y\alpha)_j$, зде~$y$---челфпт~$\$. (у)~Ч лбюеуфче умедуфчйс~(b) дплбцйфе, юфп ртйнйфйчобс %%288 уефш счмсефус уефша уптфйтпчлй фпздб й фпмшлп фпздб, лпздб поб уптфйтхеф едйоуфчеоощк челфпт~$\$! \ex[Н22] \dfn{Юефоп-оеюефобс уптфйтпчлб у фтбоурпъйгйснй} дмс $n$~юйуем, $n\ge 3$, ьфп $n\hbox{-хтпчоечбс}$ уефш у ${1\over2}n(n-1)$~лпнрбтбфптбнй, обрпнйобаэбс лйтрйюоха лмбдлх (тйу.~58). (Еумй $n$~юефоп, йнеафус дче чпънпцопуфй.) Фблха уптфйтпчлх пупвеооп мезлп тебмйъпчбфш бррбтбфхтоп, фбл лбл рпретенеооп чщрпмосафус фпмшлп дчб чйдб декуфчйк. Дплбцйфе, юфп фблбс уефш декуфчйфемшоп вхдеф ртбчймшопк уефша уптфйтпчлй. [\emph{Хлбъбойе:} ун.~хрт.~36.] \picture{Тйу.~58. Юефоп-оеюефобс уптфйтпчлб у фтбоурпъйгйснй.} \ex[29] Нпцоп дбфш дтхзха йофетртефбгйа уефсн уптфйтпчлй, уюйфбс, юфп об лбцдпк мйойй обипдйфус нхмшфйнопцеуфчп йъ $m$~юйуем, б ое пдоп юйумп; ртй ьфпк йофетртефбгйй претбгйс~$[i:j]$ ъбнеосеф~$x_i$ й~$x_j$ уппфчефуфчеооп об~$x_i \upup x_j$ й~$x_i\dndn x_j$---обйнеошыйе~$m$ й обйвпмшыйе~$m$ йъ~$2m$ юйуем~$x_i\uplus x_j$. (Тйу.~59 йммауфтйтхеф ьфп ртй~$m=2$.) Еумй~$a$ й~$b$ ухфш нхмшфйнопцеуфчб, упдетцбэйе $m$~юйуем лбцдпе, фп вхден зпчптйфе, юфп~$a \lflf b$ фпздб \picture{Тйу.~59. Дтхзбс йофетртефбгйс уефй уптфйтпчлй, ртедуфбчмеоопк об тйу.~44: лбцдщк лпнрбтбфптощк нпдхмш чщрпмосеф претбгйа умйсойс.} й фпмшлп фпздб, лпздб~$a \upup b=a$ (ймй, ьлчйчбмеофоп, $a \dndn b=b$; обйвпмшыйк ьменеоф~$a$ неошые ймй тбчео обйнеошыенх ьменеофх~$b$). Фблйн пвтбъпн, $a \upup b \lflf a \dndn b$. Рхуфш~$\alpha$ еуфш $n\hbox{-уефш}$, a~$x=\$---челфпт, ч лпфптпн лбцдбс лпнрпоеофб~$x_i$---нхмшфйнопцеуфчп йъ $m$~ьменеофпч. Дплбцйфе, юфп еумй~$(x\alpha)_i$ ое $\lflf (x\alpha)_j$ ч прйубоопк йофетртефбгйй, фп ч~$D_n$ обкдефус челфпт~$y$, фблпк, юфп $(y\alpha)_i=1$ й~$(y\alpha)_j=0$. [Умедпчбфемшоп, уефш уптфйтпчлй $n$~ьменеофпч ртечтбэбефус ч уефш уптфйтпчлй $mn$~ьменеофпч, еумй ъбнеойфш утбчоеойс $m$-рхфечщнй умйсойснй. Об тйу.~60 йъпвтбцео чпушнйьменеофощк уптфйтпчэйл, рпуфтпеоощк йъ юефщтеиьменеофопзп у йурпмшъпчбойен ьфпзп обвмадеойс.] \rex[Н23] Рплбцйфе, юфп ч пвпъобюеойси хрт.~38 $(x\upup y)\upup z=x\upup (y\upup z)$ й~$(x\dndn y)\dndn z=x\dndn(y\dndn z)$, пдоблп $(x\dndn y)\upup z)$ \emph{ое} чуездб тбчоп~$(x\upup z)\dndn (y\upup z)$ й~$(x\upup y)\dndn (x\upup z)\dndn (y\upup z)$ \emph{ое} чуездб тбчоп утедойн $m$~ьменеофбн~$x\uplus y \uplus z$. Обкдйфе ртбчймшоха жптнхмх дмс ьфйи утедойи ьменеофпч, йурпмшъпчбч ч оек $x$, $y$, $z$, б фблце претбгйй~$\upup$ й~$\dndn$. %%290 \ex[M25] (Т.~М.~Зтьиен.) Лпнрбтбфпт~$[i:j]$ объщчбефус йъвщфпюощн ч уефй~$\alpha_1[i:j]\alpha_2$, еумй мйвп~$(x\alpha_1)_i \le (x\alpha_1)_j$ дмс чуеи челфптпч~$x$, мйвп~$(x\alpha_1)_i\ge (x\alpha_1)_j$ дмс чуеи челфптпч~$x$. Дплбцйфе, юфп еумй $\alpha$~счмсефус уефша у $r$~оейъвщфпюощнй лпнрбтбфптбнй, фп обкдхфус рп лтбкоек нете $r$~тбъмйюощи хрптсдпюеоощи \picture{Тйу.~60. 8-уптфйтпчэйл, рпуфтпеоощк йъ 4-уптфйтпчэйлб у йурпмшъпчбойен умйсойс.} рбт~$(i, j)$ тбъмйюощи йоделупч, фблйи, юфп~$(x\alpha)_i\le (x\alpha)_j$ дмс чуеи челфптпч~$x$. (Умедпчбфемшоп, уефш веъ йъвщфпюощи лпнрбтбфптпч упдетцйф ое впмее $\perm{n}{2}$~нпдхмек.) \rex[M27] (Ч.~Е.~Бмелуееч.) Рхуфш~$\alpha=[i_1:j_1]\ldots[i_r:j_r]$ еуфш~$n\hbox{-уефш}$; дмс~$1\le s \le r$ пртедемйн~$\alpha^s=[i'_1:j'_1]\ldots[i'_{s-1}:j'_{s-1}]\, [i_s:j_s]\ldots[i_r:j_r]$, зде~$i'_k$ й~$j'_k$ рпмхюеощ йъ~$i_k$ й~$j_k$ ъбнеопк~$i_s$ об~$j_s$ й~$j_s$ об~$i_s$ чеъде, зде пой чуфтеюбафус. Обртйнет, еумй~$\alpha=[1:2]\,[3:4]\,[1:3]\,[2:4]\,[2:3]$, фп~$\alpha^4=[1:4]\, [3:2]\,[1:3]\,[2:4]\,[2:3]$. {\medskip\narrower \item{a)}~Дплбцйфе, юфп~$D_n\alpha=D_n(\alpha^s)$. \item{b)}~Дплбцйфе, юфп~$(\alpha^s)^t=(\alpha^t)^s$. \item{c)}~\dfn{Упртсцеойен~$\alpha$} счмсефус мавбс уефш чйдб~$(\ldots((\alpha^{s_1})^{s_2})\ldots)^{s_k}$. Дплбцйфе, юфп $\alpha$~йнееф ое впмее $2^{r-1}$~упртсцеойк. \item{d)}~Рхуфш~$g_\alpha(x)=1$, еумй~$x\in D_n\alpha$, й~$g_\alpha(x)=0$, еумй~$x\notin D_n\alpha$, й рхуфш $$ f_\alpha(x)=(\bar x_{i_1}\lor x_{j_1})\land\ldots\land(\bar x_{i_r}\lor x_{j_r}). $$ Дплбцйфе, юфп~$g_\alpha(x)=\bigvee\set{f_{\alpha'}(x)\mid \hbox{$\alpha'$ еуфш упртсцеойе~$\alpha$}}$. \item{e)}~Рхуфш~$G_\alpha$---обртбчмеоощк зтбж у четыйобнй~$\set{1,~\ldots, n}$ й дхзбнй~$i_s\to j_s$ дмс~$1\le s \le r$. Дплбцйфе, юфп б счмсефус уефша уптфйтпчлй фпздб й фпмшлп фпздб, лпздб дмс чуеи ее упртсцеойк~$\alpha'$ ч~$G_{\alpha'}$ йнеефус птйеофйтпчбоощк рхфш пф~$i$ дп~$i+1$ дмс~$1\le i < n$. [Ьфп дпчпмшоп йофетеуопе хумпчйе, рпулпмшлх~$G_\alpha$ ое ъбчйуйф пф рптсдлб лпнрбтбфптпч ч~$\alpha$.] \medskip} \rex[25] (Д.~Чбо Чптйу.) Дплбцйфе, юфп~$\hat S(n)\ge \hat S(n-1)+\ceil{\log_2 n}$. \ex[23] \dfn{Ретеуфбопчпюопк уефша} объщчбефус рпумедпчбфемшопуфш нпдхмек~$[i_1:j_1]\ldots[i_r:j_r]$, зде лбцдщк нпдхмш~$[i:j]$ нпцеф хуфбобчмйчбфшус йъчое ч пдоп йъ дчхи упуфпсойк: мйвп по ретедбеф учпй чипдщ веъ йънеоеойк, мйвп неосеф неуфбнй~$x_i$ й~$x_j$ (оеъбчйуйнп пф ъобюеойк~$x_i$ й~$x_j$), й рпумедпчбфемшопуфш нпдхмек дпмцоб вщфш фблпк, юфп об чщипде нпцоп рпмхюйфш мавха ретеуфбопчлх чипдпч ртй уппфчефуфчхаэек хуфбопчле нпдхмек. Мавбс уефш уптфйтпчлй счмсефус, пюечйдоп, ретеуфбопчпюопк уефша, оп пвтбфопе оечетоп. Обкдйфе ретеуфбопчпюоха уефш дмс рсфй ьменеофпч, йнеаэха фпмшлп чпуенш нпдхмек. %%291 \ex[46] Йъхюйфе учпкуфчб уефек уптфйтпчлй, рпуфтпеоощи йъ $m$-уптфйтпчэйлпч чнеуфп 2-уптфйтпчэйлпч. (Обртйнет, З.~Ыбрйтп рпуфтпйм уефш дмс уптфйтпчлй 16~ьменеофпч, йурпмшъпчбч юефщтобдгбфш 4-уптфйтпчэйлпч. Обймхюыее мй ьфп теыеойе? Ухэеуфчхеф мй дмс чуеи $m$~ьжжелфйчощк урпупв уптфйтпчлй $m^2$~ьменеофпч у рпнпэша нпдхмек, чщрпмосаэйи $m$-уптфйтпчлх?) \ex[48] Обкдйфе, $(m, n)\hbox{-уефш}$ умйсойс у юйумпн лпнрбтбфптпч, неошыйн~$C(m,n)$, ймй дплбцйфе, юфп фблпк уефй ое ухэеуфчхеф. \ex[48] Обкдйфе $(m, n)\hbox{-уефш}$ умйсойс неошые, юен у $\ceil{\log_2 (m+n)}$~хтпчоснй ъбдетцлй, ймй дплбцйфе, юфп ее ое ухэеуфчхеф. \ex[48] Йъхюйфе лмбуу уиен уптфйтпчлй, лпфптще нпзхф вщфш тебмйъпчбощ ч чйде уиен у йдебмшощн фбупчбойен, лбл об тйу.~57, оп у дтхзйн тбурпмпцеойен претбгйк~"$0$", "$+$" й~"$-$". \ex[ЧН49] Йуумедхкфе учпкуфчб претбгйк~$\upup$ й~$\dndn$, пртедемеоощи ч хрт.~38. Нпцоп мй пибтблфетйъпчбфш чуе фпцдеуфчб ч ьфпк бмзевте лблйн-мйвп йъсэощн урпупвпн ймй чщчеуфй чуе йи йъ лпоеюопзп обвптб фпцдеуфч? Ч ьфпн пфопыеойй фблйе фпцдеуфчб, лбл $$ x\upup x \upup x = x \upup x \hbox{ ймй } x\upup (x\dndn (x\upup (x\dndn y)))=x\upup(x\dndn y), $$ лпфптще йнеаф неуфп фпмшлп дмс~$m\le 2$, ртедуфбчмсаф пфопуйфемшоп оевпмшыпк йофетеу; тбуунбфтйчбкфе мйыш фпцдеуфчб, уртбчедмйчще ртй \emph{чуеи}~$m$. \ex[M49] Лблпчп буйнрфпфйюеулпе рпчедеойе жхолгйй~$T(n)$, пртедемеоопк ч хрт.~в? Нпцеф мй вщфш $T(n)<\hat T(n)$ ртй лблпн-ойвхдш~$n$? \ex[50] Обкдйфе фпюопе ъобюеойе~$\hat S(n)$ дмс лблпзп-мйвп~$n>8$. \ex[Н50] Дплбцйфе, юфп буйнрфпфйюеулпе ъобюеойе~$\hat S(n)$ ое еуфш~$O(n\log n)$. \centerline{{\bf ХРТБЦОЕОЙС, (ЧФПТБС ЮБУФШ)}} Умедхаэйе хртбцоеойс йнеаф демп у тбъмйюощнй фйрбнй прфйнбмшощи ъбдбю, лбубаэйиус уптфйтпчлй. Ретчще оеулпмшлп ъбдбю пуопчбощ об "йофетеуопн "нопзпзпмпчпюопн" пвпвэеойй нефпдб рхъщтшлб, ртедмпцеоопн Ж.~О.~Бтнуфтпозпн й~Т.~Дц.~Оемшупопн еэе ч~1954~з. [Ун.~U.~S.~Patents 3029413, 3034102.] Рхуфш~$1=h_1N$, фп ъбрйуш~$R_{j+h[k]}$ ое тбуунбфтйчбефус, йобюе зпчптс, %%292 лмаюй~$K_0$, $K_{-1}$, $K_{-2}$,~\dots{} уюйфбафус тбчощнй~$-\infty$, a~$K_{N+1}$, $K_{N+2}$,~\dots{}---тбчощнй~$+\infty$. Рпьфпнх ртй~$j\le -h[m-1]$ ймй~$j>N-h[2]$ ыбз~$j$ фтйчйбмео.) Обртйнет, ч умедхаэек фбвмйге рплбъбо пдйо ртпипд уптфйтпчлй ртй~$m=3$, $N=9$ й~$h_1=1$, $h_2=2$, $h_3=4$: {\def\ul#1{\underline{#1}}\def\emp{\phantom{0}} \ctable{ $#$\hfill && \bskip\hfill$#$\hfill\bskip\cr & K_{-2} & K_{-1} & K_0 & K_1 & K_2 & K_3 & K_4 & K_5 & K_6 & K_7 & K_8 & K_9 & K_{10} & K_{11} & K_{12}\cr j=-3 & \ul{\emp} & \ul{\emp} & & \ul{3} & 1 & 4 & 5 & 9 & 2 & 6 & 8 & 7 \cr j=-2 & & \ul{\emp}& \ul{\emp}& 3 & \ul{1} & 4 & 5 & 9 & 2 & 6 & 8 & 7 \cr j=-1 & & & \ul{\emp}&\ul{3} & 1 & \ul{4} & 5 & 9 & 2 & 6 & 8 & 7\cr j=0 & & & &\ul{1} & \ul{3} & 4 & \ul{5} & 9 & 2 & 6 & 8 & 7 \cr j=1 & & & & 1 & \ul{3} & \ul{4} & 5 & \ul{9} & 2 & 6 & 8 & 7 \cr j=2 & & & & 1 & 3 & \ul{2} & \ul{4} & 9 & \ul{5} & 6 & 8 & 7 \cr j=3 & & & & 1 & 3 & 2 & \ul{4} & \ul{6} & 5 &\ul{9} & 8 & 7 \cr j=4 & & & & 1 & 3 & 2 & 4 & \ul{5} & \ul{6} & 9 & \ul{8} & 7 \cr j=5 & & & & 1 & 3 & 2 & 4 & 5 & \ul{6} & \ul{7} & 8 & \ul{9}\cr j=6 & & & & 1 & 3 & 2 & 4 & 5 & 6 & \ul{7} & \ul{8} & 9 & \ul{\emp} \cr j=7 & & & & 1 & 3 & 2 & 4 & 5 & 6 & 7 & \ul{8} & \ul{9} & & \ul{\emp}\cr j=8 & & & & 1 & 3 & 2 & 4 & 5 & 6 & 7 & 8 & \ul{9} & \ul{\emp}& & \ul{\emp} \cr } } Ъбнефйн, юфп, еумй~$m=2$, $h_1=1$ й~$h_2=2$, ьфпф "нопзпзпмпчпюощк" нефпд учпдйфус л нефпдх рхъщтшлб (бмзптйфн~5.2.2B). \ex[21] (Дцекну Дхзходй.) Дплбцйфе, юфп еумй~$h[k+1]=h[k]+1$ ртй оелпфптпн~$k$, $1\le k < m$, фп нопзпзпмпчпюощк уптфйтпчэйл, пртедемеоощк чщые, пфуптфйтхеф мавпк чипдопк жбкм ъб лпоеюопе юйумп ртпипдпч. Оп еумй~$h[k+1]\ge h[k]+2$ ртй~$1\le k < m$, фп нпцеф умхюйфшус, юфп чипдобс рпумедпчбфемшопуфш \emph{ойлпздб} ое уфбоеф хрптсдпюеоопк. \edef\exref{\the\excerno} \rex[50] (Бтнуфтпоз й~Оемшупо.) Рхуфш~$h[k+1]\le h[k]+k$ ртй~$1\le k\le m$ й~$N\ge n-1$. Дплбцйфе, юфп ч феюеойе ретчпзп ртпипдб обйвпмшыйе $n-1$~ьменеофпч чуездб ъбкнхф учпй плпоюбфемшоще неуфб. [\emph{Хлбъбойе:} йурпмшъхкфе ртйогйр охмек й едйойг; дплбцйфе, юфп еумй уптфйтхефус рпумедпчбфемшопуфш йъ охмек й едйойг, ртйюен едйойг неошые~$n$, фп чуе зпмпчлй нпзхф юйфбфш~1 мйыш ч фпн умхюбе, лпздб чуе охмй мецбф умечб пф зпмпчпл.] Дплбцйфе, юфп еумй зпмпчлй хдпчмефчптсаф ужптнхмйтпчбоощн хумпчйсн, фп уптфйтпчлб вхдеф ъблпоюеоб ое впмее, юен ъб $\ceil{(N-1)/(n-1)}$~ртпипдпч. Ухэеуфчхеф мй чипдопк жбкм, дмс лпфптпзп оепвипдйнп тпчоп уфпмшлп ртпипдпч? \ex[26] Дплбцйфе, юфп ртй~$n=N$ ретчщк ртпипд рпнеуфйф обйнеошыйк лмаю ч рпъйгйа~$R_1$ фпздб й фпмшлп фпздб, лпздб~$h[k+1]\le 2h[k]$, $1\le k=\<1, 2, 4, 7,~\ldots, 1+\perm{m}{2}>. $$ пвтбъхеф упчетыеоощк уптфйтпчэйл дмс $N=\perm{m}{2}$~ьменеофпч, йурпмшъхс $m=(\sqrt{8N-7}+l)/2$~зпмпчпл. Обртйнет, рпумедпчбфемшопуфш зпмпчпл~$\<1, 2, 4, 7, 11, 16, 22>$ счмсефус упчетыеоощн уптфйтпчэйлпн дмс 22~ьменеофпч. Дплбцйфе, юфп рпумедпчбфемшопуфш зпмпчпл~$\<1, 2, 4, 7, 11, 16, 23>$ об убнпн деме вхдеф упчетыеоощн уптфйтпчэйлпн дмс 23~ьменеофпч. \ex[49] Пртедемйфе ртй ъбдбоопн~$m$ обйвпмшыее~$N$, дмс лпфптпзп ухэеуфчхеф упчетыеоощк уптфйтпчэйл у $m$~зпмпчлбнй. Четоп мй, юфп~$N=O(m^2)$? %%293 \ex[23] (Ч.~Ртбфф.) Еумй лбцдбс зпмпчлб~$h_k$ обипдйфус ч рпмпцеойй~$2^{k-1}$ дмс~$1\le k \le m$, фп улпмшлп ртпипдпч рпфтевхефус дмс уптфйтпчлй рпумедпчбфемшопуфй охмек й едйойг~$z_1$ $z_2$~\dots{} $z_{2^{m-1}}$, зде $z_j=0$ фпздб й фпмшлп фпздб, лпздб $j$~счмсефус уфереоша~2? \ex[24] (Пдоптпдобс уптфйтпчлб.) Ч детече об тйу.~34 ч р.~5.3.1 утбчоеойе~$2:3$ чщрпмосефус ч пвпйи чефчси хтпчос~1; б ч лбцдпк чефчй хтпчос~2 чщрпмосефус утбчоеойе~$1:3$, еумй фпмшлп поп ое счмсефус йъвщфпюощн. Ч пвэен умхюбе нщ нпцен тбуунпфтефш лмбуу бмзптйфнпч уптфйтпчлй, пдоптпдощи йнеооп ч ьфпн унщуме, ртедрпмбзбс, юфп~$M=\perm{N}{2}$ рбт~$\set{(a,b) \mid 1\le aK_{b_i}$, фп дпвбчйфш дхзх~$b_i\to a_i$. \medskip Обу йофетеухеф змбчощн пвтбъпн юйумп утбчоеойк лмаюек, чщрпмосенщи бмзптйфнпн пдоптпдопк уптфйтпчлй, б ое неибойън, у рпнпэша лпфптпзп декуфчйфемшоп хуфтбосафус йъвщфпюоще утбчоеойс; зтбж~$G$ ое пвсъбфемшоп уфтпйфш ч счопн чйде---ъдеуш по йурпмшъхефус фпмшлп дмс пртедемеойс пдоптпдопк уптфйтпчлй. Вхден фблце тбуунбфтйчбфш \dfn{пзтбойюеооха пдоптпдоха уптфйтпчлх,} ртй лпфптпк ч хлбъбоощи чщые умхюбси 1--3 хюйфщчбафус фпмшлп рхфй дмйощ~2. (Бмзптйфн пзтбойюеоопк уптфйтпчлй нпцеф чщрпмосфш оелпфптще йъвщфпюоще утбчоеойс, оп, лбл рплбъщчбеф хрт.~59, бобмйъ пзтбойюеоопзп умхюбс оеулпмшлп ртпэе.) Дплбцйфе, юфп бмзптйфн пзтбойюеоопк пдоптпдопк уптфйтпчлй упчрбдбеф у бмзптйфнпн пдоптпдопк уптфйтпчлй, лпздб рпумедпчбфемшопуфш рбт мелуйлпзтбжйюеулй хрптсдпюеоб: $$ (1, 2)\, (1, 3)\, (1, 4)\ldots(1, N)\, (2, 3)\, (2, 4)\ldots(2, N)\ldots (N-1, N). $$ Рплбцйфе, юфп об убнпн деме пвб бмзптйфнб ьлчйчбмеофощ "вщуфтпк уптфйтпчле" (бмзптйфн~5.2.2Q), еумй чуе лмаюй тбъмйюощ й йъвщфпюоще утбчоеойс вщуфтпк уптфйтпчлй хуфтбоеощ, лбл ч хрт.~5.2.2-24. (Ое пвтбэбкфе чойнбойс об рптсдпл, ч лпфптпн декуфчйфемшоп чщрпмосафус утбчоеойс ч вщуфтпк уптфйтпчле; хюйфщчбкфе фпмшлп, лблйе рбтщ лмаюек утбчойчбафус.) \ex[Н38] Дмс ъбдбоопк, лбл ч хрт.~58, рпумедпчбфемшопуфй рбт~$(a_1, b_1)$~\dots{}$(a_M, b_M)$ рхуфш~$c_i$ вхдеф юйумпн рбт~$(j, k)$, фблйи, юфп~$jR_i$, дпуфйзбефус нйойнбмшопе юйумп ртпипдпч. %% 295 \bye