\input style \chapnotrue\chapno=5\subchno=4\subsubchno=2 фбл лбл ч ыбзби~A3 й~A5 чщрпмосефус фпмшлп "рпмпчйоб ртпипдб", ф.~е.\ уьлпопнмеоп плпмп 25\% чтенеой. Ч декуфчйфемшопуфй нпцоп дбце рпмопуфша хуфтбойфш лпрйтпчбойе, еумй обюбфш у $F_n$~пфтеълпч об меофе~T1 й у $F_{n-1}$~пфтеълпч об~T2, зде~$F_n$ й~$F_{n-1}$---рпумедпчбфемшоще юйумб Жйвпобююй. Тбуунпфтйн, обртйнет, умхюбк~$n=7$, $S=F_n+F_{n-1}=13+8=21$: {\def\cm{\hfil$-$\hfil}\def\hd#1{\multispan{3}\hfil#1\hfil}\let\f=\hfil\ctable{ #\bskip& #&#&#\bskip&\bskip#&#&#\bskip&\bskip#&#&#&#\hfil\cr &\hd{Упдетцйнпе~Ф1} & \hd{Упдетцйнпе~Ф2} & \hd{Упдетцйнпе~T3} & Ртйнеюбойс \cr Жбъб~1.& 1, 1, 1, 1, &1, 1, 1, 1, &1, 1, 1, 1, 1& 1, 1, &1, 1, 1, 1, & 1, 1 & & & & Обюбмшопе тбуртедемеойе\cr Жбъб~2.& & &1, 1, 1, 1, 1& &\cm & & 2, 2, 2, & 2,2, & 2,2,2 & Умйсойе 8~пфтеълпч об~T3\cr Жбъб~3.& &\cm & & &3, 3, 3, 3, & 3 & & & 2,2,2 & Умйсойе 5~пфтеълпч об~T3\cr Жбъб~4.& &\f 5, 5, 5 & & &\f 3, & 3 & & \cm & & Умйсойе 3~пфтеълпч об~T1\cr Жбъб~5.& &\f 5 & & &\cm & & &\f 8,8 & & Умйсойе 2~пфтеълпч об~T3\cr Жбъб~6.& &\cm & & &\f 13 \f & & &\f 8 & & Умйсойе 1~пфтеълб об~T2\cr Жбъб~7.& &\f 21 \f & & &\cm & & &\cm & & Умйсойе 1~пфтеълб об~T1\cr }}% Ъдеуш "2, 2, 2, 2, 2, 2, 2, 2", обртйнет, пвпъобюбеф чпуенш пфтеълпч пфопуйфемшопк дмйощ~2, еумй уюйфбфш пфопуйфемшоха дмйох лбцдпзп обюбмшопзп пфтеълб тбчопк~1. Чуадх ч ьфпк фбвмйге юйумб Жйвпобююй! Рпмощк ртпипд рп дбоощн пухэеуфчмсаф фпмшлп жбъщ~1 й~7; жбъб~2 пвтбвбфщчбеф мйыш $16/21$~пвэезп юйумб обюбмшощи пфтеълпч, жбъб~3---мйыш~$15/21$ й~ф. д.; фблйн пвтбъпн, ухннбтопе юйумп "ртпипдпч" тбчоп~$(21+16+15+15+16+13+21)/21=5{4\over7}$, еумй ртедрпмпцйфш, юфп обюбмшоще пфтеълй йнеаф ртйнетоп тбчоха дмйох. Дмс утбчоеойс ъбнефйн, юфп тбуунпфтеообс чщые дчхижбъобс ртпгедхтб ъбфтбфймб вщ 8~ртпипдпч об уптфйтпчлх ьфйи це обюбмшощи пфтеълпч. Нщ хчйдйн, юфп ч пвэен умхюбе ьфб уиенб Жйвпобююй фтевхеф ртйвмйъйфемшоп $1.04\log_2 S+0.99$~ртпипдпч, юфп дембеф ее утбчойнпк у \emph{юефщтеимеофпюощн} увбмбоуйтпчбоощн умйсойен, ипфс поб йурпмшъхеф фпмшлп фтй меофщ. Ьфх йдеа нпцоп пвпвэйфш об умхюбк $T$~меоф ртй мавпн~$T\ge 3$, йурпмшъхс $(T-1)\hbox{-рхфечпе}$~умйсойе. Нщ хчйдйн, обртйнет, юфп ч умхюбе юефщтеи меоф фтевхефус фпмшлп плпмп $0.703\log_2 S+0.96$~ртпипдпч рп дбоощн. Пвпвэеообс уиенб йурпмшъхеф пвпвэеооще юйумб Жйвпобююй. Тбуунпфтйн умедхаэйк ртйнет у ыеуфша меофбнй: \ctable{ #\hfil\bskip&$#$\hfil\bskip&$#$\hfil\bskip&$#$\hfil\bskip&$#$\hfil\bskip&$#$\hfil\bskip&$#$\hfil\bskip&\hfil$#$&\hfil$\hbox{}#$\cr & & & & & & & \hbox{Юйумп пвтбвбфщчбенщи обюбмшощи пфтеълпч}\cr & T1 & T2 & T3 & T4 & T5 & T6 & \cr Жбъб~1.& 1^{31}& 1^{30}& 1^{28}& 1^{24}& 1^{16}& - & 31+30+28+24+16 =&129\cr Жбъб~2.& 1^{15}& 1^{14}& 1^{12}& 1^8 & - & 5^{16}& 16\times 5 =& 80\cr Жбъб~3.& 1^7 & 1^6 & 1^4 & - & 9^8 & 5^8 & 8\times 9 =& 72\cr Жбъб~4.& 1^3 & 1^2 & - & 17^4 & 9^4 & 5^4 & 4\times 17 =& 68\cr Жбъб~5.& 1^1 & - & 33^2 & 17^2 & 9^2 & 5^2 & 2\times 33 =& 66\cr Жбъб~6.& - & 65^1 & 33^1 & 17^1 & 9^1 & 5^1 & 1\times 65 =& 65\cr Жбъб~7.& 129^1 & - & - & - & - & - & 1\times 129=&129\cr } %%320 Ъдеуш $1^{31}$~пвпъобюбеф 31~пфтеъпл пфопуйфемшопк дмйощ~1 й~ф.д.; чеъде йурпмшъхефус рсфйрхфечпе умйсойе. Ьфб пвэбс уиенб вщмб тбътбвпфбоб Т.~М.~Зймуфьдпн [Proc.\ AFIPS Eastern Jt.\ Computer Conf., 18 (1960), 143--148], лпфптщк объчбм ее нопзпжбъощн умйсойен. Умхюбк фтеи меоф вщм тбоее пфлтщф В.~Л.~Вефген [оепрхвмйлпчбообс ъбнефлб, Minneapolis-Honeywell Regulator Co.\ (1956)]. Юфпвщ ъбуфбчйфш нопзпжбъопе умйсойе тбвпфбфш, лбл ч ртедщдхэен ртйнете, оепвипдйнп рпуме лбцдпк жбъщ йнефш "фпюопе жйвпобююйечп тбуртедемеойе" пфтеълпч рп меофбн. Юйфбс ртйчедеооха чщые фбвмйгх уойъх ччети, нпцоп ъбнефйфш, юфп ретчще уенш фпюощи жйвпобююйечщи тбуртедемеойк ртй~$T=6$ ухфш $\set{1, 0, 0, 0, 0}$, $\set{1, 1, 1, 1, 1}$, $\set{2, 2, 2, 2, 1}$, $\set{4, 4, 4, 3, 2}$, $\set{8, 8, 7, 6, 4}$, $\set{16, 15, 14, 12, 8}$ й~$\set{31, 30, 28, 24, 16}$. Феретш ретед обнй уфпсф умедхаэйе чбцоще чпртпущ: \enumerate \li Лблпе ртбчймп ултщфп ъб ьфйнй фпюощнй жйвпобююйечщнй тбуртедемеойснй? \li Юфп дембфш, еумй~$S$ ое уппфчефуфчхеф фпюопнх жйвпобююйечпнх тбуртедемеойа? \li Лбл рпуфтпйфш обюбмшощк ртпипд тбуртедемеойс, юфпвщ по рптпцдбм охцопе тбурпмпцеойе пфтеълпч об меофби? \li Улпмшлп "ртпипдпч" рп дбоощн рпфтевхеф $T\hbox{-меофпюопе}$ нопзпжбъопе умйсойе (лбл жхолгйс пф~$S$---юйумб обюбмшощи пфтеълпч)? \enumend Нщ пвухдйн ьфй юефщте чпртпуб рп пюетедй, ртй ьфпн уобюбмб дбдйн "ртпуфще пфчефщ", б ъбфен ъбкненус впмее змхвплйн бобмйъпн. Фпюоще жйвпобююйечщ тбуртедемеойс нпцоп рпмхюйфш, "ртплтхюйчбс" тбуунпфтеооха уиенх ч пвтбфоха уфптпох, гйлмйюеулй ретеуфбчмсс упдетцйнпе меоф. Обртйнет, ртй~$T=6$ йнеен умедхаэее тбуртедемеойе пфтеълпч: $$ \vcenter{\halign{ \hfil # \hfil &\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\hfil$#$\hfil\cr Хтпчеош & T1 & T2 & T3 & T4& T5 & \hbox{Ухннб} & \hbox{Меофб у плпоюбфемшощн теъхмшфбфпн}\cr 0 & 1 & 0& 0& 0 & 0& 1& T1\cr 1 & 1 & 1& 1& 1 & 1& 5& T6\cr 2 & 2 & 2& 2& 2 & 1& 9& T5\cr 3 & 4 & 4& 4& 3 & 2& 17& T4\cr 4 & 8 & 8& 7& 6 & 4& 33& T3\cr 5 & 16 & 15& 14& 12 & 8& 65& T2\cr 6 & 31 & 30& 28& 24 & 16& 129& T1\cr 7 & 61 & 59& 55& 47 & 31& 253& T6\cr 8 & 120 & 116& 108& 92 & 61& 497& T5\cr \multispan{8}\dotfill\cr n & a_n & b_n & c_n & d_n & e_n & t_n & T(k) \cr n+1 & a_n+b_n & a_n+c_n & a_n+d_n & a_n+e_n & a_n & t_n+4a_n & T(k-1)\cr \multispan{8}\dotfill\cr }} \eqno(1) $$ %%321 (Рпуме обюбмшопзп тбуртедемеойс меофб~T6 чуездб вхдеф рхуфпк.) Йъ ртбчймб ретеипдб пф хтпчос~$n$ л хтпчоа~$n+1$ суоп, юфп хумпчйс $$ a_n \ge b_n \ge c_n \ge d_n \ge e_n \eqno (2) $$ чщрпмосафус об мавпн хтпчое. Ч убнпн деме, мезлп чйдефш йъ~(1), юфп $$ \eqalign{ e_n &= a_{n-1},\cr d_n &= a_{n-1}+e_{n-1}=a_{n-1}+a_{n-2},\cr c_n &= a_{n-1}+d_{n-1}=a_{n-1}+a_{n-2}+a_{n-3},\cr b_n &= a_{n-1}+c_{n-1}=a_{n-1}+a_{n-2}+a_{n-3}+a_{n-4},\cr a_n &= a_{n-1}+b_{n-1}=a_{n-1}+a_{n-2}+a_{n-3}+a_{n-4}+a_{n-5},\cr } \eqno (3) $$ зде~$a_0=1$ й зде нщ рпмбзбен~$a_n=0$ ртй~$n=-1$, $-2$, $-3$, $-4$. \def\Fib#1,#2.{F^{(#1)}_{#2}} \dfn{Юйумб Жйвпобююй $p\hbox{-зп}$~рптсдлб~$\Fib p, n.$} пртедемсафус ртбчймбнй $$ \eqalign{ \Fib p, n. &=\Fib p, n-1.+\Fib p, n-2.+\cdots+\Fib p, n-p. \rem{ртй $n\ge p$;}\cr \Fib p, n. &=0 \rem{ртй $0\le n \le p-2$;}\cr \Fib p, p-1. &=1.\cr } \eqno (4) $$ Дтхзйнй умпчбнй, нщ обюйобен у $p-1$~охмек, ъбфен рйыен~1, б лбцдпе умедхаэее юйумп счмсефус ухннпк $p$~ртедщдхэйи юйуем. Ртй~$p=2$ ьфп пвщюобс рпумедпчбфемшопуфш Жйвпобююй; дмс впмшыйи ъобюеойк~$p$ ьфх рпумедпчбфемшопуфш чретчще йъхюйм, рп-чйдйнпнх, Ч.~Ымеземш ч [{\sl El Progreso Matematico,\/} {\bf 4} (1894), 173--174]. Ымеземш чщчем ртпйъчпдсэха жхолгйа $$ \sum_{n\ge 0}\Fib p, n. z^n= {z^{p-1}\over 1-z-z^2-\cdots-z^p}= {z^{p-1}-z^p \over 1-2z+z^{p+1}}. \eqno (5) $$ Жптнхмб~(3) рплбъщчбеф, юфп юйумп пфтеълпч об~T1 ч ртпгеууе ыеуфймеофпюопзп нопзпжбъопзп умйсойс счмсефус юйумпн Жйвпобююй рсфпзп рптсдлб~$a_n=\Fib 5, n+4.$. Ч пвэен умхюбе, еумй рпмпцйфш~$P=T-1$, тбуртедемеойс ч нопзпжбъопн умйсойй дмс $T$~меоф вхдхф бобмпзйюощн пвтбъпн уппфчефуфчпчбфш юйумбн Жйвпобююй $P\hbox{-зп}$~рптсдлб. Ч фпюопн тбуртедемеойй $n\hbox{-зп}$~хтпчос об $k\hbox{-к}$~меофе вхдеф $$ \Fib P, n+P-2. + \Fib P, n+P-3. +\cdots+ \Fib P, n+k-2. $$ %% 322 обюбмшощи пфтеълпч дмс~$1\le k \le P$, б пвэее лпмйюеуфчп обюбмшощи пфтеълпч об чуеи меофби вхдеф, умедпчбфемшоп, тбчоп $$ t_n=P\Fib P, n+P-2. + (P-1)\Fib P, n+P-3. + \cdots + \Fib P, n-1. . \eqno(6) $$ Ьфп теыбеф чпртпу п "фпюопн жйвпобююйечпн тбуртедемеойй". Оп юфп нщ дпмцощ дембфш, еумй~$S$ ое тбчоп ч фпюопуфй~$t_n$ ой ртй лблпн~$n$? Лбл ретчпобюбмшоп рпнеуфйфш пфтеълй об меофщ? Еумй~$S$ ое счмсефус фпюощн юйумпн Жйвпобююй (б юйуем Жйвпобююй ое фбл хц нопзп), фп нпцоп декуфчпчбфш, лбл ч увбмбоуйтпчбоопн $P\hbox{-рхфечпн}$ умйсойй, дпвбчмсс "жйлфйчоще \picture{Тйу.~68. Уптфйтпчлб нопзпжбъощн умйсойен.} пфтеълй"; рпьфпнх нпцоп уюйфбфш, юфп~$S$, ч лпоге лпогпч, вхдеф фпюощн. Еуфш оеулпмшлп урпупвпч дпвбчмеойс жйлфйчощи пфтеълпч; нщ еэе ое ъобен, лбл ьфп удембфш "обймхюыйн" урпупвпн. Ч ретчха пюетедш тбуунпфтйн нефпд тбуртедемеойс пфтеълпч й ртйрйущчбойс жйлфйчощи пфтеълпч, лпфптщк ипфс й ое убнщк прфйнбмшощк, оп ъбфп дпуфбфпюоп ртпуфпк й, рп-чйдйнпнх, мхюые чуеи дтхзйи нефпдпч фблпк це уфереой умпцопуфй. \alg D.(Уптфйтпчлб нопзпжбъощн умйсойен у йурпмшъпчбойен "зптйъпофбмшопзп" тбуртедемеойс.) Ьфпф бмзптйфн ветеф обюбмшоще пфтеълй й тбуртедемсеф йи пдйо ъб дтхзйн рп меофбн, рплб ъбрбу обюбмшощи пфтеълпч ое йуюетрбефус. Ъбфен по пртедемсеф, лбл обдп умйчбфш меофщ, йурпмшъхс $P\hbox{-рхфечпе}$ умйсойе, ч ртедрпмпцеойй, юфп йнеафус $T=P+1\ge 3$~меофпртпфсцощи хуфтпкуфч. Меофх~$T$ нпцоп йурпмшъпчбфш дмс итбоеойс ччпдб, фбл лбл об оее ое ъбрйущчбефус ой пдопзп обюбмшопзп пфтеълб. Ч рбнсфй итбосфус умедхаэйе фбвмйгщ: %%323 \descrtable{ $|A|[j]$, $1 \le j \le T$: & Фпюопе жйвпобююйечпе тбуртедемеойе, л лпфптпнх нщ уфтенйнус. \cr $|D|[j]$, $1 \le j \le T$: & Юйумп жйлфйчощи пфтеълпч, лпфптще уюйфбафус ртйухфуфчхаэйнй ч обюбме меофщ об мпзйюеулпн хуфтпкуфче у опнетпн~$j$.\cr $|TAPE|[j]$, $1 \le j \le T$: & Опнет жйъйюеулпзп меофпртпфсцопзп хуфтпкуфчб, уппфчефуфчхаэезп мпзйюеулпнх хуфтпкуфчх у опнетпн~$j$.\cr } (Плбъбмпуш, юфп хдпвоп тбвпфбфш у "опнетбнй мпзйюеулйи меофпртпфсцощи хуфтпкуфч", уппфчефуфчйе лпфптщи жйъйюеулйн хуфтпкуфчбн неосефус ч ртпгеууе чщрпмоеойс бмзптйфнб.) \st[Обюбмшобс хуфбопчлб.] Хуфбопчйфш~$|A|[j]\asg |D|[j]\asg 1$ й~$|TAPE|[j]\asg j$ ртй~$1\le j < T$. Хуфбопчйфш~$|A|[T]\asg |D|[T]\asg 0$ й~$|TAPE|[T]\asg T$. Ъбфен хуфбопчйфш~$l\asg 1$, $j\asg 1$. \st[Ччпд об меофх~$j$.] Ъбрйубфш пдйо пфтеъпл об меофх~$j$ й хнеошыйфш~$|D|[j]$ об~1. Ъбфен, еумй ччпд йуюетрбо, ретенпфбфш чуе меофщ й ретекфй л ыбзх~\stp{5}. \st[Ртпдчйцеойе~$j$.] Еумй~$|D|[j]<|D|[j+1]$, фп хчемйюйфш~$j$ об~1 й четохфшус л ыбзх~\stp{2}. Ч ртпфйчопн умхюбе, еумй~$|D|[j]=0$, ретекфй л ыбзх~\stp{4}, б еумй~$|D|[j]\ne 0$, хуфбопчйфш~$j\asg 1$ й четохфшус л ыбзх~\stp{2}. \st[Рпдосфшус об пдйо хтпчеош.] Хуфбопчйфш~$l\asg l+1$, $a\asg |A|[1]$, ъбфен дмс~$j=1$, 2,~\dots, $P$ (йнеооп ч ьфпн рптсдле) хуфбопчйфш~$|D|[j]\asg a+|A|[j+1]-|A|[j]$ й~$|A|[j]\asg a+|A|[j+1]$. (Ун.~(1). Пфнефйн, юфп~$|A|[P+1]$ чуездб~0. Ч ьфпн неуфе вхден йнефш~$|D|[1]>|D|[2]>\ldots>|D|[T]$.) Феретш хуфбопчйфш~$j\asg 1$ й четохфшус л ыбзх~\stp{2}. \st[Умйсойе.] Еумй~$l=0$, фп уптфйтпчлб ъбчетыеоб, теъхмшфбф обипдйфус об~$|TAPE|[1]$. Ч ртпфйчопн умхюбе умйчбфш пфтеълй у меоф~$|TAPE|[1]$,~\dots, $|TAPE|[P]$ об~$|TAPE|[T]$ дп феи рпт, рплб~$|TAPE|[P]$ ое уфбоеф рхуфпк й~$|D|[P]$ ое пвтбфйфус ч~$0$. Ртпгеуу умйсойс дмс лбцдпзп умйчбенпзп пфтеълб дпмцео ртпфелбфш умедхаэйн пвтбъпн. Еумй~$|D|[j]>0$ дмс чуеи~$j$, $1\le j \le P$, фп хчемйюйфш~$|D|[T]$ об~1 й хнеошыйфш лбцдпе~$|D|[j]$ об~1 дмс~$1\le j \le P$; ч ртпфйчопн умхюбе умйчбфш рп пдопнх пфтеълх у лбцдпк меофщ~$|TAPE|[j]$, фблпк, юфп~$|D|[j]=0$, й хнеошыйфш~$|D|[j]$ об~1 дмс пуфбмшощи~$j$. (Фблйн пвтбъпн, уюйфбефус, юфп жйлфйчоще пфтеълй обипдсфус ч \emph{обюбме} меофщ, б ое ч лпоге.) \st[Прхуфйфшус об пдйо хтпчеош.] Хуфбопчйфш~$l\asg l-1$. Ретенпфбфш меофщ~$|TAPE|[P]$ й~$|TAPE|[T]$. (Ч декуфчйфемшопуфй ретенпфлб~$|TAPE|[P]$ нпзмб вщфш обюбфб об ыбзе~\stp{5} рпуме ччпдб у оее рпумедоезп вмплб.) Ъбфен хуфбопчйфш~$(|TAPE|[1], %%324 |TAPE|[2],~\ldots, |TAPE|[T])\asg (|TAPE|[T], |TAPE|[1],~\ldots, |TAPE|[T-1])$, $(|D|[1], |D|[2],~\ldots, |D|[T])\asg(|D|[T], |D|[1],~\ldots, |D|[T-1])$ й четохфшус л ыбзх~\stp{5}. \algend Ртбчймп тбуртедемеойс, лпфптпе фбл мблпойюоп ужптнхмйтпчбоп ч ыбзе~D3 ьфпзп бмзптйфнб, уфтенйфус рп чпънпцопуфй хтбчосфш юйумб жйлфйчощи пфтеълпч об лбцдпк меофе. Тйухопл~69 йммауфтйтхеф рптсдпл тбуртедемеойс, лпздб нщ ретеипдйн пф хтпчос~4 (33~пфтеълб) л хтпчоа~5 (65~пфтеълпч) ч уптфйтпчле у ыеуфша меофбнй; еумй вщмп вщ, улбцен, фпмшлп 53~обюбмшощи \picture{ Тйу.~69. Рптсдпл, ч лпфптпн пфтеълй у~34-зп рп~65-к тбуртедемсафус об меофщ ртй ретеипде у хтпчос~4 об хтпчеош~5. (Ун.~фбвмйгх фпюощи тбуртедемеойк об уфт.~320.) Ъбыфтйипчбооще пвмбуфй уппфчефуфчхаф ретчщн 33~пфтеълбн, лпфптще вщмй тбуртедемеощ л нпнеофх дпуфйцеойс хтпчос~4. } пфтеълб, фп чуе пфтеълй у опнетбнй~54 й чщые тбуунбфтйчбмйуш вщ лбл жйлфйчоще. (Об убнпн деме пфтеълй ъбрйущчбафус ч лпоег меофщ, оп хдпвоее уюйфбфш, юфп пой ъбрйущчбафус ч обюбмп, фбл лбл ртедрпмбзбефус, юфп жйлфйчоще пфтеълй обипдсфус ч обюбме меофщ.) Нщ хце тбуунпфтемй ретчще фтй йъ рпуфбчмеоощи чщые чпртпупч, пуфбмпуш чщсуойфш юйумп "ртпипдпч" рп дбоощн. Утбчойчбс обы ыеуфймеофпюощк ртйнет у фбвмйгек~(1), нщ чйдйн, юфп ухннбтопе лпмйюеуфчп пвтбвпфбоощи обюбмшощи пфтеълпч ртй~$S=t_6$ еуфш~$a_5t_1+a_4t_2+a_3t_3+a_2t_4+a_1t_5+a_0t_6$, еумй йулмаюйфш обюбмшощк ртпипд тбуртедемеойс. Ч хрт.~4 чщчпдсфус %%325 ртпйъчпдсэйе жхолгйй $$ \eqalign{ a(z)&=\sum_{n\ge0}a_nz^n={1\over 1-z-z^2-z^3-z^4-z^5},\cr t(z)&=\sum_{n\ge1} t_nz^n={5z+4z^2+3z^3+2z^4+z^5\over 1-z-z^2-z^3-z^4-z^5}.\cr } \eqno(7) $$ Пфуадб умедхеф, юфп ч пвэен умхюбе юйумп пвтбвбфщчбенщи обюбмшощи пфтеълпч ртй~$S=t_n$ тбчоп лпьжжйгйеофх ртй~$z^n$ ч ртпйъчедеойй~$a(z)\cdot t(z)$ рмау~$t_n$ (ьфп дбеф обюбмшощк ртпипд тбуртедемеойс). Феретш нщ нпцен чщюйумйфш буйнрфпфйюеулпе рпчедеойе нопзпжбъопзп умйсойс, лбл рплбъбоп ч хрт.~5--7, й рпмхюбен теъхмшфбфщ, ртйчедеооще ч фбвм.~1. Ч фбвм.~1 "пфопыеойе тпуфб" еуфш ртедем~$\lim_{n\to\infty} t_{n+1}t_n$, рплбъщчбаэйк, чп улпмшлп ртйвмйъйфемшоп тбъ чпътбуфбеф юйумп \htable{Фбвмйгб~1}% {Брртплуйнбгйс рпчедеойс уптфйтпчлй нопзпжбъощн умйсойен}% {\hfill$#$\bskip&&\bskip\hfill$#$\hfill\bskip\cr \hbox{Меофщ} & \hbox{Жбъщ} & \hbox{Ртпипдщ} & \hbox{Ртпипдщ/жбъщ,} & \hbox{Пфопыеойе}\cr & & & & \hbox{ч ртпгеофби тпуфб}\cr \noalign{\hrule} 3 & 2.078 \ln S+0.678 & 1.504 \ln S+0.992 & 72 & 1.6180340\cr 4 & 1.641 \ln S+0.364 & 1.015 \ln S+0.965 & 62 & 1.8392868\cr 5 & 1.524 \ln S+0.078 & 0.863 \ln S+0.921 & 57 & 1.9275620\cr 6 & 1.479 \ln S-0.185 & 0.795 \ln S+0.864 & 54 & 1.9659482\cr 7 & 1.460 \ln S-0.424 & 0.762 \ln S+0.797 & 52 & 1.9835826\cr 8 & 1.451 \ln S-0.642 & 0.744 \ln S+0.723 & 51 & 1.9919642\cr 9 & 1.447 \ln S-0.838 & 0.734 \ln S+0.646 & 51 & 1.9960312\cr 10 & 1.445 \ln S-1.017 & 0.728 \ln S+0.568 & 50 & 1.9980295\cr 20 & 1.443 \ln S-2.170 & 0.721 \ln S-0.030 & 50 & 1.9999981\cr \noalign{\hrule} } пфтеълпч об лбцдпн хтпчое. "Ртпипдщ" пвпъобюбаф утедоее лпмйюеуфчп пвтбвпфпл лбцдпк ъбрйуй, б йнеооп~$(1/S)$, хнопцеоопе об пвэее юйумп обюбмшощи пфтеълпч, пвтбвбфщчбенщи ч феюеойе жбъ тбуртедемеойс й умйсойс. Хуфбопчмеооще юйумб ртпипдпч й жбъ уртбчедмйчщ ч лбцдпн умхюбе у фпюопуфша дп~$O(S^{-\varepsilon})$ ртй оелпфптпн~$\varepsilon>0$ дмс фпюопзп тбуртедемеойс ртй~$S\to\infty$. Об тйу.~70 йъпвтбцеощ ч чйде жхолгйк пф~$S$ утедойе лпмйюеуфчб умйсойк лбцдпк ъбрйуй ртй йурпмшъпчбойй бмзптйфнб~D ч умхюбе оефпюощи юйуем. Ъбнефйн, юфп ртй йурпмшъпчбойй фтеи меоф лбл тбъ рпуме фпюощи тбуртедемеойк рпсчмсафус "рйлй" пфопуйфемшопк оеьжжелфйчопуфй, оп ьфп счмеойе ч ъобюйфемшопк уфереой йуюеъбеф ртй юефщтеи ймй впмшыен юйуме меоф. Йурпмшъпчбойе %%326 чпушнй ймй впмее меоф дбеф утбчойфемшоп нбмпе хмхюыеойе рп утбчоеойа у ыеуфша ймй уенша меофбнй. \section *Впмее дефбмшопе тбуунпфтеойе. Ч увбмбоуйтпчбоопн умйсойй, фтевхаэен $k$~ртпипдпч, лбцдбс ъбрйуш пвтбвбфщчбефус ч ипде уптфйтпчлй тпчоп $k$~тбъ. Оп нопзпжбъобс ртпгедхтб ое счмсефус фблпк веуртйуфтбуфопк: оелпфптще ъбрйуй нпзхф пвтбвбфщчбфшус \picture{Тйу.~70. Ьжжелфйчопуфш нопзпжбъопзп умйсойс, йурпмшъхаэезп бмзптйфн~D.} нопзп впмшыее юйумп тбъ, юен дтхзйе, й нщ нпцен хчемйюйфш улптпуфш, еумй хумпчйнус рпнеэбфш жйлфйчоще пфтеълй ч юбуфп пвтбвбфщчбенще рпъйгйй. Рп ьфпк ртйюйое йъхюйн впмее рпдтпвоп нопзпжбъопе тбуртедемеойе. Чнеуфп фпзп юфпвщ йофетеупчбфшус фпмшлп юйумпн пфтеълпч об лбцдпк меофе, лбл ч~(1), ртйрйыен лбцдпнх пфтеълх езп \emph{юйумп умйсойк}---улпмшлп тбъ по пвтбвбфщчбефус ч феюеойе чуезп ртпгеууб уптфйтпчлй. Чнеуфп~(1) рпмхюйн умедхаэха фбвмйгх: %%327 $$ \matrix{ \hbox{Хтпчеош} & T1 & T2 & T3 & T4 & T5 \cr 0 & 0 & - & - & - & - \cr 1 & 1 & 1 & 1 & 1 & 1 \cr 2 & 21 & 21 & 21 & 21 & 2\cr 3 & 3221 & 3221 & 3221 & 322 & 32 \cr 4 & 43323221 & 43323221 & 4332322 & 433232 & 4332 \cr 5 & 5443433243323221 & 544343324332322 & 54434332433232 & 544343324332 & 54434332 \cr \multispan{6}{\dotfill}\cr n & A_n & B_n & C_n & D_n & E_n \cr n+1& (A_n+1)B_n & (A_n+1)C_n & (A_n+1)D_n & (A_n+1)E_n & A_n+1\cr \multispan{6}{\dotfill}\cr } \eqno(8) $$ Ъдеуш $A_n$~еуфш герпюлб йъ $a_n$~ъобюеойк, ртедуфбчмсаэйи юйумб умйсойк лбцдпзп пфтеълб об~$T1$, еумй нщ обюйобен у тбуртедемеойс $n\hbox{-зп}$~хтпчос; $B_n$~еуфш уппфчефуфчхаэбс герпюлб дмс~T2 й~ф.~д.\ Пвпъобюеойе~"$(A_n+1)B_n$" юйфбефус: "$A_n$, чуе ъобюеойс лпфптпк хчемйюеощ об~1, б ъб оеа~$B_n$". Тйухопл~71~(б), об лпфптпн "уойъх ччети" йъпвтбцеощ~$A_5$, $B_5$, $C_5$, $D_5$, $E_5$, денпоуфтйтхеф, лблйн пвтбъпн юйумб умйсойк дмс лбцдпзп пфтеълб рпсчмсафус об меофе; ъбнефйн, юфп пфтеъпл ч обюбме мавпк меофщ вхдеф пвтбвбфщчбфшус 5~тбъ, ч фп чтенс лбл пфтеъпл ч лпоге~T1 вхдеф пвтбвбфщчбфшус мйыш пдобцдщ. \picture{Тйу.~71. Бобмйъ нопзпжбъопзп тбуртедемеойс рсфпзп хтпчос об ыеуфй меофби: (a)---юйумб умйсойк; (b)---прфйнбмшощк рптсдпл тбуртедемеойс.} Ьфб "дйултйнйобгйс" ртй нопзпжбъопн умйсойй ртйчпдйф л фпнх, юфп жйлфйчоще пфтеълй мхюые рпнеэбфш ч обюбмп меофщ, б ое ч лпоег. Об тйу.~71~(b) ртедуфбчмео прфйнбмшощк рптсдпл тбуртедемеойс пфтеълпч дмс умхюбс рсфйхтпчоечпзп нопзпжбъопзп умйсойс; лбцдщк опчщк пфтеъпл рпнеэбефус ч рпъйгйа у обйнеошыйн йъ пуфбчыйиус юйумпн умйсойк. Ъбнефйн, юфп бмзптйфн~D %%328 (тйу.~69) оеулпмшлп ихце, фбл лбл по ъбрпмосеф оелпфптще рпъйгйй~"4" дп фпзп, лбл ъбрпмоеощ чуе рпъйгйй~"3". Телхттеофоще уппфопыеойс~(8) рплбъщчбаф, юфп чуе~$B_n$, $C_n$, $D_n$, $E_n$ счмсафус обюбмшощнй рпдгерпюлбнй~$A_n$. Ч декуфчйфемшопуфй, йурпмшъхс~(8), нпцоп чщчеуфй жптнхмщ $$ \eqalign{ E_n&=(A_{n-1})+1,\cr D_n&=(A_{n-1}A_{n-2})+1,\cr C_n&=(A_{n-1}A_{n-2}A_{n-3})+1,\cr B_n&=(A_{n-1}A_{n-2}A_{n-3}A_{n-4})+1,\cr A_n&=(A_{n-1}A_{n-2}A_{n-3}A_{n-4}A_{n-5})+1,\cr } \eqno(9) $$ пвпвэбаэйе уппфопыеойс~(3), лпфптще йнеаф демп фпмшлп у дмйобнй ьфйи герпюел. Лтпне фпзп, йъ ртбчйм, пртедемсаэйи герпюлй~$A$, умедхеф, юфп уфтхлфхтб ч обюбме лбцдпзп хтпчос, ч ухэопуфй, пдоб й фб це; йнеен $$ A_n=n-Q_n, \eqno(10) $$ зде $Q_n$~еуфш герпюлб йъ $a_n$~ъобюеойк, пртедемсенбс ъблпопн $$ \displaynarrow{ Q_n=Q_{n-1}(Q_{n-2}+1)(Q_{n-3}+2)(Q_{n-4}+3)(Q_{n-5}+4) \rem{ртй $n\ge 1$},\cr Q_0=\hbox{'0'}; Q_n=\hbox{(рхуфп)} \rem{ртй $n<0$.}\cr } \eqno(11) $$ Фбл лбл~$Q_n$ обюйобефус у~$Q_{n-1}$, фп нпцоп тбуунпфтефш \emph{веулпоеюоха} герпюлх~$Q_\infty$, ретчще $a_n$~ьменеофпч лпфптпк упчрбдбаф у~$Q_n$; ьфб герпюлб, рп ухэеуфчх, прйущчбеф чуе юйумб умйсойк ч нопзпжбъопн тбуртедемеойй. Ч умхюбе ыеуфй меоф йнеен $$ Q_\infty=011212231223233412232334233434412232334233434452334344534454512232\ldots\,. \eqno (12) $$ Ч хрт.~11 упдетцйфус йофетеуобс йофетртефбгйс ьфпк герпюлй. Ртй хумпчйй юфп~$A_n$ еуфш герпюлб~$m_1m_2\ldots m_{a_n}$, пвпъобюйн юетеъ~$A_n(x)=x^{m_1}+x^{m_2}+\cdots+x^{m_{a_n}}$ уппфчефуфчхаэха ртпйъчпдсэха жхолгйа, прйущчбаэха, улпмшлп тбъ рпсчмсефус лбцдпе юйумп умйсойк; бобмпзйюоп ччеден~$B_n(x)$, $C_n(x)$, $D_n(x)$, $E_n(x)$. Обртйнет, $A_4(x)=x^4+x^3+x^3+x^2+x^3+x^2+x^2+x=x^4+3x^3+3x^2+x$. Ч уймх уппфопыеойк~(9) йнеен ртй~$n\ge1$ $$ \eqalign{ E_n(x)&=x(A_{n-1}(x)),\cr D_n(x)&=x(A_{n-1}(x)+A_{n-2}(x)),\cr C_n(x)&=x(A_{n-1}(x)+A_{n-2}(x)+A_{n-3}(x)),\cr B_n(x)&=x(A_{n-1}(x)+A_{n-2}(x)+A_{n-3}(x)+A_{n-4}(x)),\cr A_n(x)&=x(A_{n-1}(x)+A_{n-2}(x)+A_{n-3}(x)+A_{n-4}(x)+A_{n-5}(x)),\cr } \eqno(13) $$ %%329 зде~$A_0(x)=1$ й~$A_n(x)=0$ ртй~$n=-1$, $-2$, $-3$, $-4$. Умедпчбфемшоп, $$ \sum_{n\ge 0} A_n(x)z^n={1\over 1-x(z+z^2+z^3+z^4+z^5)}= \sum_{k\ge 0} x^k(z+z^2+z^3+z^4+z^5)^k. \eqno(14) $$ Тбуунбфтйчбс пфтеълй об чуеи меофби, рпмпцйн $$ T_n(x)=A_n(x)+B_n(x)+C_n(x)+D_n(x)+E_n(x), \qquad n\ge 1; \eqno (15) $$ йъ~(13) оенедмеооп рпмхюбен $$ T_n(x)=5A_{n-1}(x)+4A_{n-2}(x)+3A_{n-3}(x)+2A_{n-4}(x)+A_{n-5}(x), $$ б ъобюйф, й $$ \sum_{n\ge 1} T_n(x)z^n= {x(5z+4z^2+3z^3+2z^4+z^5)\over 1-x(z+z^2+z^3+z^4+z^5)}. \eqno(16) $$ Уппфопыеойе~(16) рплбъщчбеф, юфп мезлп чщюйумйфш лпьжжйгйеофщ~$T_n(x)$: $$ \matrix{ & z &z^2 & z^3 & z^4 & z^5 & z^6 & z^7 & z^8 & z^9 & z^{10} & z^{11} & z^{12} & z^{13} & z^{14} \cr x & 5 & 4 & 3 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \cr x^2 & 0 & 5 & 9 & 12 & 14 & 15 & 10 & 6 & 3 & 1 & 0 & 0 & 0 & 0 \cr x^3 & 0 & 0 & 5 & 14 & 26 & 40 & 55 & 60 & 57 & 48 & 35 & 20 & 10 & 4 \cr x^4 & 0 & 0 & 0 & 5 & 19 & 45 & 85 & 140 & 195 & 238 & 260 & 255 & 220 & 170\cr x^5 & 0 & 0 & 0 & 0 & 5 & 24 & 69 & 154 & 294 & 484 & 703 & 918 & 1088 & 1168 \cr } \eqno(17) $$ Уфпмвгщ ьфпк фбвмйгщ дбаф~$T_n(x)$; обртйнет, $T_4(x)=2x+12x^2+14x^3+5x^4$. Лбцдщк ьменеоф ьфпк фбвмйгщ (лтпне ьменеофпч ретчпк уфтплй) счмсефус ухннпк рсфй ьменеофпч, тбурпмпцеоощи ч ртедщдхэек уфтпле оерпутедуфчеооп мечее оезп. Юйумп пфтеълпч ч фпюопн тбуртедемеойй $n\hbox{-зп}$~хтпчос тбчоп~$T_n(1)$, б пвэее лпмйюеуфчп пвтбвбфщчбенщи пфтеълпч ч ртпгеууе йи умйсойс тбчоп ртпйъчпдопк~$T'_n(1)$. Дбмее, $$ \sum_{n\ge 1} T'_n(x)z^n= {5z+4z^2+3z^3+2z^4+z^5\over (1-x(z+z^2+z^3+z^4+z^5))^2}; \eqno(18) $$ рпмбзбс~$x=1$ ч~(16) й~(18), рпмхюбен, юфп юйумп умйсойк дмс фпюопзп тбуртедемеойс р-зп хтпчос еуфш лпьжжйгйеоф ртй~$z^n$ ч~$a(z)t(z)$ [ут.~(7)]. Ьфп упзмбухефус у обыйнй ртедщдхэйнй тбуухцдеойснй. Жхолгйй~$T_n(x)$ нпцоп йурпмшъпчбфш дмс пртедемеойс упчетыбенпк тбвпфщ, лпздб жйлфйчоще пфтеълй дпвбчмсафус прфйнбмшощн пвтбъпн. Рхуфш~$\sum_n (m)$ еуфш ухннб обйнеошыйи $m$~юйуем умйсойк ч тбуртедемеойй $n\hbox{-зп}$~хтпчос. Рпунпфтеч об уфпмвгщ~(17), %%330 нщ веъ фтхдб чщюйумйн ьфй ухннщ~$\sum_n(m)$: {\let\i=\infty $$\vcenter{\halign{ $#$\bskip&&\bskip\hfill$#$\bskip\cr \span m=1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 \cr n=1 & 1 & 2 & 3 & 4 & 5 & \i & \i & \i & \i & \i & \i & \i & \i & \i & \i& \i & \i & \i & \i & \i & \i \cr n=2 & 1 & 2 & 3 & 4 & в & 8 & 10 & 12 & 14 & \i & \i & \i & \i & \i & \i & \i & \i & \i & \i & \i & \i \cr n=3 & 1 & 2 & 3 & 5 & 7 & 9 & 11 & 13 & 15 & 17 & 19 & 21 & 24 & 27 & 30 &33 & 36 & \i & \i & \i & \i \cr n=4 & 1 & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & 20 & 22 & 24 & 26 & 29& 32 & 35 & 38 & 41 & 44 & 47 \cr n=5 & 1 & 3 & 5 & 7 & 9 & 11 & 13 & 15 & 17 & 19 & 21 & 23 & 25 & 27 & 29& 32 & 35 & 38 & 41 & 44 & 47 \cr n=6 & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & 20 & 22 & 24 & 26 & 28 & 30 & 33 & 36 & 38 & 42 & 45 & 48 \cr n=7 & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & 20 & 23 & 26 & 29 & 32 & 35 & 38 & 41 & 44 & 47 & 50 & 53 \cr }} \eqno(19) $$}% Обртйнет, еумй нщ ипфйн пфуптфйтпчбфш 17~пфтеълпч, йурпмшъхс тбуртедемеойе 3-зп~хтпчос, фп пвэее лпмйюеуфчп претбгйк еуфш~$\sum_3 (17)=36$, оп еумй йурпмшъпчбфш тбуртедемеойе~4-зп ймй 5-зп~хтпчос, фп пвэее лпмйюеуфчп претбгйк ч ртпгеууе умйсойс вхдеф фпмшлп~$\sum_4(17)=\sum_5 (17)=35$. Чщзпдоее йурпмшъпчбфш хтпчеош~4, ипфс юйумп~17 уппфчефуфчхеф фпюопнх тбуртедемеойа 3-зп~хтпчос! Ч убнпн деме, рп. нете чпътбуфбойс~$S$ прфйнбмшощк опнет хтпчос плбъщчбефус ъобюйфемшоп впмшые, юен йурпмшъхенщк ч бмзптйфне~D. Хртбцоеойе~14 рплбъщчбеф, юфп ухэеуфчхеф оехвщчбаэбс рпумедпчбфемшопуфш юйуем~$M_n$, фблбс, юфп хтпчеош~$n$ прфйнбмео дмс~$M_n\le S < M_{n+1}$, оп ое дмс~$S\ge M_{n+1}$. Ч умхюбе ыеуфй меоф фпмшлп юфп чщюйумеообс фбвмйгб~$\sum_n (m)$ дбеф $$ M_0=0,\quad M_1=2,\quad M_2=6,\quad M_3=10,\quad M_4=14. $$ Чщые нщ йнемй демп фпмшлп уп умхюбен ыеуфй меоф, пдоблп суоп, юфп фе це йдей ртйнеойнщ л нопзпжбъопк уптфйтпчле у~$T$~меофбнй дмс мавпзп~$T\ge3$; ртпуфп ч уппфчефуфчхаэйи неуфби обдп ъбнеойфш~5 об~$P=T-1$. Ч фбвм.~2 йъпвтбцеощ рпумедпчбфемшопуфй~$M_n$, рпмхюеооще дмс тбъмйюощи ъобюеойк~$T$. Фбвмйгб~3 й тйу.~72 дбаф ртедуфбчмеойе пв пвэен лпмйюеуфче пвтбвбфщчбенщи обюбмшощи пфтеълпч рпуме чщрпмоеойс прфйнбмшопзп тбуртедемеойс жйлфйчощи пфтеълпч. (Жптнхмщ чойъх фбвм.~3 умедхеф ртйойнбфш у пуфптпцопуфша, фбл лбл ьфп ртйвмйцеойе рп нефпдх обйнеошыйи лчбдтбфпч об пвмбуфй~$1\le S \le 5000$ ($1\le S \le 10\, 000$ ртй~$T=3$), юфп ртйчпдйф л оелпфптпнх пфлмпоеойа, рпулпмшлх дбообс пвмбуфш ъобюеойк~$S$ ое счмсефус пдйоблпчп рпдипдсэек дмс чуеи~$T$. Ртй~$S\to\infty$ юйумп пвтбвбфщчбенщи обюбмшощи пфтеълпч рпуме прфйнбмшопзп нопзпжбъопзп тбуртедемеойс буйнрфпфйюеулй тбчоп~$S\log_p S$, оп уипдйнпуфш л ьфпнх буйнрфпфйюеулпнх ртедемх лтбкое недмеообс.) Ртй рпнпэй фбвм.~4 нпцоп утбчойфш нефпд тбуртедемеойс бмзптйфнб~D у теъхмшфбфбнй прфйнбмшопзп тбуртедемеойс, ртйчедеоощнй ч фбвм.~3. Суоп, юфп бмзптйфн~D ое пюеош вмйъпл л прфйнбмшопнх ртй впмшыйи~$S$ й~$T$; пдоблп оерпосфоп, нпцоп мй рпуфхрйфш ч ьфйи умхюбси ухэеуфчеооп мхюые бмзптйфнб~D, ое ртйвезбс л ъобюйфемшощн хумпцоеойсн, пупвеооп еумй нщ ое %%331 ъобен~$S$ ъбтбоее. Л уюбуфша, ъбвпфйфшус п впмшыйи~$S$ ртйипдйфус дпчпмшоп тедлп (ун.~р.~5.4.6), фбл юфп бмзптйфн~D об ртблфйле ое фбл хц рмпи, об убнпн деме---дбце чеушнб оермпи. Нбфенбфйюеулй нопзпжбъобс уптфйтпчлб чретчще вщмб ртпбобмйъйтпчбоб Х.~Л.~Лбтфетпн [Тзпу.\ IFIP Congress (1962), 62--66]. \picture{Тйу.~72. Ьжжелфйчопуфш нопзпжбъопзп умйсойс у прфйнбмшощн обюбмшощн тбуртедемеойен (ут.~у~тйу.~70).} Нопзйе йъ ртйчедеоощи теъхмшфбфпч пфопуйфемшоп прфйнбмшопзп тбънеэеойс жйлфйчощи пфтеълпч ртйобдмецбф В.~Уьлнбох й~Ф.~Уйозметх [A vector model for merge sort analisis, оепрхвмйлпчбоощк дплмбд, ртедуфбчмеоощк об уйнрпъйхн~ACM рп уптфйтпчле (опсвтш 1962), уфт.~21]. Рпъдоее Уьлнбо ртедмпцйм зптйъпофбмшощк нефпд тбуртедемеойс, йурпмшъхенщк ч бмзптйфне~D; Дпобмшд Ыемм [{\sl CACM,\/} {\bf 14} (1971), 713--719; {\bf 15} (1972), 28], оеъбчйуйнп тбъчйч ьфх фептйа, хлбъбм об уппфопыеойе~(10) й рпдтпвоп йъхюйм оеулпмшлп тбъмйюощи бмзптйфнпч тбуртедемеойс. Дбмшоекыйе рпмеъоще хупчетыеоуфчпчбойс й хртпэеойс вщмй рпмхюеощ Детелпн~Ь.~Ъькчпн [{\sl JACM,\/} вхдеф прхвмйлпчбоп]. %%332 \htable{Фбвмйгб 2}% {Юйумп пфтеълпч, ртй лпфптпн дбоощк хтпчеош прфйнбмео} { \hfill$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\bskip$#$\hfill\cr \hbox{Хтпчеош}& T=3 & T=4 & T=5 & T=6 & T=7 & T=8 & T=9 & T=10\cr \noalign{\hrule} 1 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & M_1 \cr 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & M_2 \cr 3 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & M_3 \cr 4 & 6 & 10 & 14 & 14 & 17 & 20 & 23 & 26 & M_4 \cr 5 & 9 & 18 & 23 & 29 & 20 & 24 & 28 & 32 & M_5 \cr 6 & 14 & 32 & 35 & 43 & 53 & 27 & 32 & 37 & M_6 \cr 7 & 22 & 55 & 76 & 61 & 73 & 88 & 35 & 41 & M_7 \cr 8 & 35 & 96 &109 &194 & 98 &115 &136 & 44 & M_8 \cr 9 & 56 &173 &244 &216 &283 &148 &171 &199 & M_9 \cr 10 & 90 &280 &359 &269 &386 &168 &213 &243 & M_{10}\cr 11 &145 &535 &456 &779 &481 &640 &240 &295 & M_{11}\cr 12 &234 &820 &1197&1034&555 &792 &1002&330 & M_{12}\cr 13 &378 &1635&1563&1249&1996&922 &1228&1499& M_{13}\cr 14 &611 &2401&4034&3910&2486&1017&1432&1818& M_{14}\cr 15 &988 &4959&5379&4970&2901&4397&1598&2116& M_{15}\cr 16 &1598&7029&6456&5841&10578&5251&1713&2374&M_{16}\cr 17 &2574&14953&18561&19409&13097&5979&8683&2576&M_{17}\cr 18 &3955&20583&22876&23918&15336&6499&10069&2709&M_{18}\cr 19 &6528&44899&64189&27557&17029&30164&11259&15787& M_{19}\cr \noalign{\hrule} } {\def\m#1#2{\matrix{\hfill #1\cr\hfill #2\cr}} \htable{Фбвмйгб~3}% {Юйумп обюбмшощи пфтеълпч, пвтбвбфщчбенщи ртй прфйнбмшопн \nl нопзпжбъопн умйсойй}% {\hfill$#$\bskip&&\hfill\bskip$#$\bskip\cr S& T=3 & T=4 & T=5 & T=6 & T=7 & T=8 & T=9 & T=10\cr \noalign{\hrule} 10& 36& 24& 19& 17& 15& 14& 13& 12\cr 20& 90& 60& 49& 44& 38& 36& 34& 33\cr 50& 294& 194& 158& 135& 128& 121& 113& 104\cr 100& 702& 454& 362& 325& 285& 271& 263& 254\cr 1000& 10371& 6680& 5430& 4672& 4347& 3872& 3739& 3632\cr 5000& 63578& 41286& 32905& 28620& 26426& 23880& 23114& 22073\cr \multispan{2} \hfil$ \displaystyle S\left\{\matrix{ \hfill (1.51\cr \hfill +(-.11\cr }\right. $ & \m{0.951}{+.14} & \m{0.761}{+.16} & \m{0.656}{+.19} & \m{0.589}{+.21} & \m{0.548}{+.20} & \m{0.539}{+.02} & \multispan{2} \hfill\bskip$\displaystyle\vcenter{\halign{\hfil$#$&$\hbox{}#$\hfil\cr 0.488)&\cdot S \ln S \cr +.18)&\cdot S \cr }}$ \cr \noalign{\hrule} }} Ртпйъчпдсэбс жхолгйс~(16) вщмб чретчще йуумедпчбоб Х.~Вхтцен [Тзпу. IFIP Congress (1971), I, 454--459]. \qsection Б лбл пвуфпйф демп у чтенеоен ретенпфлй? Дп уйи рпт нщ йурпмшъпчбмй "пвтбвбфщчбенще обюбмшоще пфтеълй" лбл едйоуфчеооха нетх ьжжелфйчопуфй дмс утбчоеойс уфтбфезйк меофпюопзп умйсойс. Оп рпуме лбцдпк йъ жбъ~2--6 ч ртйнетби ч обюбме ьфпзп рхолфб ЬЧН дпмцоб пцйдбфш ретенпфлй дчхи меоф; лбл ртедщдхэбс чщчпдобс меофб, фбл й опчбс фелхэбс чщчпдобс %%333 \htable{Фбвмйгб~4}% {Юйумп обюбмшощи пфтеълпч, пвтбвбфщчбенщи ртй уфбодбтфопн \nl нопзпжбъопн умйсойй}% {\hfill$#$\bskip&&\hfill\bskip$#$\bskip\cr S& T=3 & T=4 & T=5 & T=6 & T=7 & T=8 & T=9 & T=10\cr \noalign{\hrule} 10& 36& 24& 19& 17& 15& 14& 13& 12\cr 20& 90& 62& 49& 44& 41& 37& 34& 33\cr 50& 294& 194& 167& 143& 134& 131& 120& 114\cr 100& 714& 459& 393& 339& 319& 312& 292& 277\cr 1000& 10730& 6920& 5774& 5370& 4913& 4716& 4597& 4552\cr 5000& 64740& 43210& 36497& 32781& 31442& 29533& 28817& 28080\cr \noalign{\hrule} } меофб дпмцощ вщфш ретенпфбощ ч обюбмп, ртецде юен унпцеф чщрпмосфшус умедхаэбс жбъб. Ьфп нпцеф чщъчбфш ухэеуфчеооха ъбдетцлх, фбл лбл ч пвэен умхюбе ртедщдхэбс чщчпдобс меофб упдетцйф ъобюйфемшощк ртпгеоф уптфйтхенщи ъбрйуек (ун. уфпмвег "ртпипдщ/жбъщ" ч фбвм.~1). Дпубдоп, лпздб ЬЧН ртпуфбйчбеф чп чтенс претбгйк ретенпфлй, фпздб лбл нпцоп вщмп вщ, йурпмшъхс йоха уиенх умйсойс, чщрпмойфш рпмеъоха тбвпфх у пуфбмшощнй меофбнй. Ьфх ъбдбюх теыбеф ртпуфбс нпдйжйлбгйс нопзпжбъопк ртпгедхтщ, ипфс поб фтевхеф ое неоее рсфй меоф [ун.~дйууетфбгйа Й.~Уеъбтй (Univ.~of~Paris (1968), 25--27), зде ьфб йдес ртйрйущчбефус Дц.~Льктпох]. Лбцдбс жбъб уиенщ Льктпоб умйчбеф пфтеълй у $(T-3)$~меоф об оелпфптха дтхзха меофх, ч фп чтенс лбл пуфбаэйеус дче меофщ ретенбфщчбафус. Тбуунпфтйн, обртйнет, умхюбк ыеуфй меоф й 49~обюбмшощи пфтеълпч. Ч умедхаэек фбвмйге вхлчпк~$R$ рпнеюеощ меофщ, ретенбфщчбаэйеус чп чтенс дбоопк жбъщ; ртедрпмбзбефус, юфп $T5$~упдетцйф ретчпобюбмшоще пфтеълй: \ctable{ \hfill$#$\bskip&&\bskip\hfill$#$\hfill\bskip\cr \omit\hfill Жбъб\hfill & T1 & T2 & T3 & T4 & T5 & T6 & \omit\hfill Чтенс ъбрйуй \hfill & \omit\hfill Чтенс ретенпфлй \hfill \cr 1&1^{11}&1^{17}&1^{13}& 1^8& - & (R) & 49 & 17\cr 2& (R)& 1^9& 1^5& -& R & 3^8 & 8\times 3=24& 49-17=32\cr 3& 1^6& 1^4& - & R& 3^5 & R & 5\times 3=15& \max(8,24)\cr 4& 1^2& -& R & 5^4& R & 3^4 & 4\times 5=20& \max(13,15)\cr 5& - & R& 7^2& R& 3^3 & 3^2 & 2\times 7=14& \max(17,20)\cr 6& R & 11^2& R& 5^2& 3^1 & - & 2\times 11=22& \max(11,14)\cr 7& 15^1& R& 7^1& 5^1& - & R & 1\times 15=15& \max(22,24)\cr 8& R & 11^1& 7^0& -& R & 23^1 & 1\times 23=23& \max(15,16)\cr 9& 15^1 & 11^1& -& R& 33^0& R & 0\times 33= 0& \max(20,23)\cr 10&(15^0)& -& R&49^1& (R) & (23^0)& 1\times 49=49& 14\cr } Ъдеуш чуе ретенпфлй, рп ухэеуфчх, упчнеэеощ; ъб йулмаюеойен жбъщ~9 ("жйлфйчобс жбъб", лпфптбс рпдзпфбчмйчбеф плпоюбфемшопе умйсойе) й ретенпфлй рпуме обюбмшопк жбъщ тбуртедемеойс (лпздб ретенбфщчбафус чуе меофщ). Еумй $t$~еуфш чтенс, оепвипдйнпе %%334 дмс умйсойс фблпзп лпмйюеуфчб ъбрйуек, лблпе упдетцйфус ч пдопн обюбмшопн пфтеъле, б $r$---чтенс ретенпфлй об пдйо обюбмшощк пфтеъпл, фп ьфпф ртпгеуу фтбфйф плпмп~$182t+40r$ рмау чтенс обюбмшопзп тбуртедемеойс й ъбчетыбаэек ретенпфлй. Уппфчефуфчхаэйе чщтбцеойс дмс уфбодбтфопзп нопзпжбъопзп нефпдб, йурпмшъхаэезп бмзптйфн~D, еуфш~$140t+104r$, юфп оеулпмшлп ихце, еумй~$r={3\over 4}t$, й оеулпмшлп мхюые, еумй~$r={1\over2}t$. Чуе улбъбоопе п уфбодбтфопн нопзпжбъопн нефпде ртймпцйнп л нопзпжбъопнх нефпдх Льктпоб; обртйнет, рпумедпчбфемшопуфш~$a_n$ феретш хдпчмефчптсеф телхттеофопнх уппфопыеойа $$ a_n=a_{n-2}+a_{n-3}+a_{n-4} \eqno (20) $$ чнеуфп~(3). Юйфбфема вхдеф рпмеъоп ртпбобмйъйтпчбфш ьфпф нефпд фблйн це пвтбъпн, лбл нщ бобмйъйтпчбмй уфбодбтфощк нопзпжбъощк, фбл лбл ьфп хмхюыйф рпойнбойе пвпйи нефпдпч (ун., обртйнет, хрт.~19 й~20). Ч фбвм.~5 учедеощ жблфщ п нопзпжбъопн нефпде Льктпоб, бобмпзйюоще жблфбн пв пвщюопн нопзпжбъопн нефпде, ртйчедеоощн ч фбвм.~1. Ъбнефйн, юфп. об убнпн деме ртй чпушнй й впмее. меофби нефпд Льктпоб уфбопчйфус \emph{мхюые} нопзпжбъопзп лбл рп юйумх пвтбвбфщчбенщи пфтеълпч, фбл й рп чтенеой ретенпфлй, оеунпфтс об фп юфп по чщрпмосеф $(T-3)\hbox{-рхфечпе}$ умйсойе чнеуфп $(T-1)\hbox{-рхфечпзп}$! Ьфп нпцеф лбъбфшус, рбтбдплубмшощн, рплб нщ ое рпкнен, юфп \emph{чщуплйк рптсдпл умйсойс ое пвсъбфемшоп пъобюбеф ьжжелфйчоха уптфйтпчлх.} Ч лбюеуфче лтбкоезп тбуунпфтйн умхюбк, лпздб об меофх~T1 рпнеэбефус 1~пфтеъпл й $n$~пфтеълпч---об~T2, T3, \htable{Фбвмйгб 5}% {Ртйвмйъйфемшопе рпчедеойе нопзпжбъопзп умйсойс Льктпоб}% { \hfill$#$\bskip&&\bskip\hfill$#$\hfill\bskip\cr \hbox{Меофщ} & \hbox{Жбъщ} & \hbox{Ртпипдщ} & \hbox{Ртпипдщ/жбъщ,} & \hbox{Пфопыеойе}\cr & & & \hbox{ч ртпгеофби} & \hbox{тпуфб} \cr \noalign{\hrule} 5& 3.566 \ln S +0.158 & 1.463 \ln S + 1.016 & 41 & 1.3247180\cr 6& 2.616 \ln S -0.166 & 0.951 \ln S + 1.014 & 36 & 1.4655712\cr 7& 2.337 \ln S -0.472 & 0.781 \ln S + 1.001 & 33 & 1.5341577\cr 8& 2.216 \ln S -0.762 & 0.699 \ln S + 0.980 & 32 & 1.5701473\cr 9& 2.156 \ln S -1.034 & 0.654 \ln S + 0.954 & 30 & 1.5900054\cr 10& 2.124 \ln S -1.290 & 0.626 \ln S + 0.922 & 29 & 1.6013473\cr 20& 2.078 \ln S -3.093 & 0.575 \ln S + 0.524 & 28 & 1.6179086\cr \noalign{\hrule} } T4, T5; еумй нщ вхден рппюетедоп чщрпмосфш умйсойс об~T6 й~T1, рплб T2, T3, T4, T5 ое уфбохф рхуфщнй, фп чтенс пвтбвпфлй вхдеф тбчоп $(2n^2+3n)$~дмйобн обюбмшощи пфтеълпч, ф.~е., рп ухэеуфчх, ртпрптгйпобмшоп~$S^2$, б ое~$S\log S$, ипфс чуе чтенс ртпйъчпдйфус рсфйрхфечпе умйсойе. %%335 \section Тбуэермеойе меоф. Ьжжелфйчопе упчнеэеойе чтенеой ретенпфлй счмсефус ртпвменпк, чпъойлбаэек чп нопзйи ртймпцеойси, б ое фпмшлп ч уптфйтпчле; ухэеуфчхеф пвэйк рпдипд, лпфптщк юбуфп нпцеф вщфш йурпмшъпчбо. Тбуунпфтйн йфетбфйчощк ртпгеуу, лпфптщк йурпмшъхеф меофщ умедхаэйн пвтбъпн: \ctable{ #\bskip\hfill&&\bskip#\bskip\hfill\cr &\omit\hfill T1 \hfill&\omit\hfill T2 \hfill\cr Жбъб~1& Чщчпд~1 & \omit\hfill $-$ \hfill \cr & Ретенпфлб & \omit\hfill $-$ \hfill \cr Жбъб~2& Ччпд~1 & Чщчпд~2\cr & Ретенпфлб & Ретенпфлб\cr Жбъб~3& Чщчпд~3 & Ччпд~2\cr & Ретенпфлб & Ретенпфлб\cr Жбъб~4& Ччпд~3 & Чщчпд~4\cr & Ретенпфлб & Ретенпфлб\cr } й ф. д., зде "чщчпд~$k$" пъобюбеф ъбрйуш ч $k$-к чщчпдопк жбкм, б "ччпд~$k$" пъобюбеф езп юфеойе. Нпцоп хуфтбойфш чтенс ретенпфлй, еумй йурпмшъпчбфш фтй меофщ, лбл вщмп ртедмпцеоп Л.~Чекуетфпн [{\sl CACM,\/} {\bf 5} (1962), 102]: \ctable{ #\bskip\hfill&&\bskip#\bskip\hfill\cr &\omit\hfill T1 \hfill&\omit\hfill T2 \hfill& \omit\hfill T3 \hfill\cr Жбъб~1 & Чщчпд~1.1 & \omit\hfill $-$ \hfill & \omit\hfill $-$ \hfill\cr & Чщчпд~1.2 & \omit\hfill $-$ \hfill & \omit\hfill $-$ \hfill\cr & Ретенпфлб & Чщчпд~1.3 & \omit\hfill $-$ \hfill\cr Жбъб~2 & Ччпд~1.1 & Чщчпд~2.1 & \omit\hfill $-$ \hfill\cr & Ччпд~1.2 & Ретенпфлб & Чщчпд~2.2\cr & Ретенпфлб & Ччпд~1.3 & Чщчпд~2.3\cr Жбъб~3 & Чщчпд~3.1 & Ччпд~2.1 & Ретенпфлб\cr & Чщчпд~3.2 & Ретенпфлб & Ччпд~2.2\cr & Ретенпфлб & Чщчпд~3.3 & Ччпд~2.3\cr Жбъб~4 & Ччпд~3.1 & Чщчпд~4.1 & Ретенпфлб\cr & Ччпд~3.2 & Ретенпфлб & Чщчпд~4.2\cr & Ретенпфлб & Ччпд~3.3 & Чщчпд~4.3\cr } й~ф.~д. Ъдеуш "чщчпд~$k.j$" пъобюбеф ъбрйуш $j\hbox{-к}$~фтефй $k\hbox{-зп}$~чщчпдопзп жбкмб, б "ччпд~$k.j$" пъобюбеф ее юфеойе. Ч лпоге лпогпч вхдеф йулмаюеоп чуе чтенс ретенпфлй, еумй ретенпфлб рп лтбкоек нете чдчпе вщуфтее юфеойс/ъбрйуй. Рпдпвобс ртпгедхтб, ч лпфптпк чщчпд ч лбцдпк жбъе тбъдемсефус нецдх меофбнй, объщчбефус "тбуэермеойен меоф". М.~Нбл-Бммеуфет [{\sl CACM\/}, {\bf 7} (1964), 158--159] рплбъбм, юфп тбуэермеойе меоф ртйчпдйф л ьжжелфйчопнх нефпдх упчнеэеойс чтенеой ретенпфлй ч нопзпжбъопн умйсойй. Езп нефпд нпцоп йурпмшъпчбфш у юефщтшнс ймй впмшыйн лпмйюеуфчпн меоф, й по пухэеуфчмсеф $(T-2)\hbox{-рхфечпе}$~умйсойе. %%336 Ртедрпмпцйн уопчб, юфп х обу еуфш ыеуфш меоф й рпрщфбенус рпуфтпйфш уиенх умйсойс, лпфптбс тбвпфбеф умедхаэйн пвтбъпн, тбуэермсс чщчпд об лбцдпн хтпчое (вхлчщ~I, П й~R пвпъобюбаф уппфчефуфчеооп ччпд, чщчпд й ретенпфлх): $$ \vcenter{\halign{ \hfil$#$\hfil&\bskip\hfill # \hfill\bskip&\bskip\hfill # \hfill\bskip&\bskip\hfill # \hfill\bskip&\bskip\hfill # \hfill\bskip&\bskip\hfill # \hfill\bskip&\bskip\hfill # \hfill\bskip&\bskip\hfill$#$\hfill\bskip\cr & & & & & & & \hbox{Юйумп чщчпдйнщи}\cr Хтпчеош & T1 & T2 & T3 & T4 & T5 & T6 & \hbox{пфтеълпч}\cr 7 & I & I & I & I & R & O & u_7 \cr & I & I & I & I & O & R & v_7 \cr 6 & I & I & I & R & O & I & u_6 \cr & I & I & I & O & R & I & v_6 \cr 5 & I & I & R & O & I & I & u_5 \cr & I & I & O & R & I & I & v_5 \cr 4 & I & R & O & I & I & I & u_4 \cr & I & O & R & I & I & I & v_4 \cr 3 & R & O & I & I & I & I & u_3 \cr & O & R & I & I & I & I & v_3 \cr 2 & O & I & I & I & I & R & u_2 \cr & R & I & I & I & I & O & v_2 \cr 1 & I & I & I & I & R & O & u_1 \cr & I & I & I & I & O & R & v_1 \cr 0 & I & I & I & R & O & I & u_0 \cr & I & I & I & O & R & I & \cr }} \eqno (21) $$ Юфпвщ ъблпоюйфш тбвпфх у пдойн пфтеълпн об Ф4 й рхуфщнй пуфбмшощнй меофбнй, нщ дпмцощ йнефш $$ \eqalign{ v_0 &= 1,\cr u_0+v_1&= 0,\cr u_1+v_2 &= u_0+v_0,\cr u_2+v_3 &= u_1+v_1+u_0+v_0,\cr u_3+v_4 &= u_2+v_2+u_1+v_1+u_0+v_0,\cr u_4+v_5 &= u_3+v_3+u_2+v_2+u_1+v_1+u_0+v_0,\cr u_5+v_6 &= u_4+v_4u_3+v_3+u_2+v_2+u_1+v_1,\cr } $$ й~ф.~д.; ч пвэен умхюбе фтевхефус, юфпвщ $$ u _n+v_{n+1}=u_{n-1}+v_{n-1}+u_{n-2}+v_{n-2}+u_{n-3}+v_{n-3}+u_{n-4}+v_{n-4} \eqno (22) $$ ртй чуеи~$n\ge 0$, еумй уюйфбфш~$u_j=v_j=0$ ртй чуеи~$j<0$. Х ьфйи хтбчоеойк оеф едйоуфчеоопзп теыеойс; ч убнпн деме, еумй рпмпцйфш чуе~$u$ тбчощнй охма, фп рпмхюйн пвщюопе нопзпжбъопе, умйсойе, ртйюен пдоб меофб вхдеф мйыоек! Оп еумй %%337 чщвтбфш~$u_n\approx v_{n+1}$, фп чтенс ретенпфлй вхдеф хдпчмефчптйфемшоп упчнеэеоп. Нбл-Бммеуфет ртедмпцйм чъсфш~$u_n=v_{n-1}+v_{n-2}+v_{n-3}+v_{n-4}$, $v_{n+1}=u_{n-1}+u_{n-2}+u_{n-3}+u_{n-4}$, фбл юфп рпумедпчбфемшопуфш $$ \ = \ $$ хдпчмефчптсеф пдоптпдопнх телхттеофопнх уппфопыеойа $$ x_n=x_{n-3}+x_{n-5}+x_{n-7}+x_{n-9}. $$ Плбъбмпуш, пдоблп, юфп мхюые рпмпцйфш $$ \eqalign{ v_{n+1} &= u_{n-1}+v_{n-1}+u_{n-2}+v_{n-2},\cr u_n &= u_{n-3}+v_{n-3}+u_{n-4}+v_{n-4}.\cr } $$ Ьфб рпумедпчбфемшопуфш ое фпмшлп оенопзп мхюые рп чтенеой умйсойс, ее впмшыпе ртейнхэеуфчп ч фпн, юфп уппфчефуфчхаэее чтенс умйсойс нпцоп ртпбобмйъйтпчбфш нбфенбфйюеулй. [Чбтйбоф Нбл-Бммеуфетб дмс бобмйъб лтбкое фтхдео, рпфпнх юфп ч пдопк жбъе нпзхф чуфтеюбфшус пфтеълй тбъопк дмйощ; нщ хчйдйн, юфп фблпзп ое нпцеф умхюйфшус ртй~(23).] Нпцоп чщчеуфй юйумп пфтеълпч об лбцдпк меофе об лбцдпн хтпчое, дчйзбсуш объбд рп уиене~(21); нщ рпмхюбен умедхаэха уиенх уптфйтпчлй: {\def\m#1{\displaystyle\matrix{#1}}\ctable{ \hfil#\hfil&\bskip\hfil$#$\hfil\bskip&\bskip\hfil$#$\hfil\bskip&\bskip\hfil$#$\hfil\bskip&\bskip\hfil$#$\hfil\bskip&\bskip\hfil$#$\hfil\bskip&\bskip\hfil$#$\hfil\bskip&\bskip$#$\hfil\bskip&\bskip\hfil$#$\hfil\bskip\cr Хтпчеош & T1 & T2 & T3 & T4 & T5 & T6 & \hbox{Чтенс ъбрйуй} & \hbox{Чтенс ретенпфлй}\cr & 1^{23} & 1^{21} & 1^{17} & 1^{10} & - & 1^{11} & 82 & 23\cr 7 & 1^{19} & 1^{17} & 1^{13} & 1^6 & R & 1^{11}4^4 & 4\times 4=16 & 82-23\cr & 1^{13} & 1^{11} & 1^7 & - & 4^6& R & 6\times 4=24 & 25 \cr 6 & 1^{10} & 1^8 & 1^4 & R & 4^9& 1^84^4 & 3\times 4=12 & 10 \cr & 1^6 & 1^4 & - & 4^4 & R & 1^44^4 & 4\times 4=16 & 36 \cr 5 & 1^5 & 1^3 & R & 4^47^1 & 4^8& 1^34^4 & 1\times 7=7 & 17 \cr & 1^2 & - & 7^3 & R & 4^5& 4^4 & 3\times 7=21 & 23 \cr 4 & 1^1 & R &7^3 13^1& 4^37^1 & 4^4& 4^3 & 1\times 13=13 & 21 \cr & - & 13^1 & R & 4^27^1 & 4^3& 4^2 & 1\times 13=13 & 34 \cr 3 & R & 13^1 19^1& 7^2 13^1 & 4^1 7^1 & 4^2 & 4^1 & 1\times 19=19 & 23 \cr & 19^1 & R & 7^1 13^1 & 7^1 & 4^1& - & 1\times 19=19 & 32 \cr 2 & 19^1 31^0& 13^1 19^1 & 7^1 13^1 & 7^1 & 4^1 & R & 0\times 31=0 & 25 \cr & R & 19^1 & 13^1 & 7^0 & - & 31^1 & 1\times 31=31 & 19 \cr $\m{ 1\cr \cr 0\cr}$ & \m{ 19^1 31^0 \cr 19^1 31^0 \cr 19^1 31^0 \cr}& \m{ 19^1 \cr 19^1 \cr 19^1 \cr } & \m{13^1 \cr 13^1 \cr 13^1 \cr } & \m{ 7^0 \cr - \cr R \cr } & \m{ R \cr 52^0 \cr 52^0 82^0 \cr } & \m{ 31^1 52^0 \cr R \cr 31^1 52^0 \cr } & \left.\m{ 0\times 52 = 0 \cr 0\times 52 = 0 \cr 0\times 82 = 0 \cr } \right\} \max(36, 31, 23)\span\cr & (31^0) & (19^0) & - & 82^1 & (R) & (52^0) & 1\times 82 = 82 & 0\cr }} Оеупчнеэеообс ретенпфлб чуфтеюбефус фпмшлп ртй ретенпфле ччпдопк меофщ~T5 (82~едйойгщ), ч феюеойе ретчпк рпмпчйощ жбъщ чфптпзп хтпчос (25~едйойг) й ч феюеойе плпоюбфемшощи жбъ "жйлфйчопзп умйсойс" об хтпчоси~1 й~0 (36 едйойг). Фблйн %% 338 пвтбъпн, чтенс тбвпфщ нпцоп пгеойфш чемйюйопк~$273t+143r$; дмс бмзптйфнб~D уппфчефуфчхаэбс чемйюйоб~$268t+208r$ рпюфй чуездб ихце. Оефтхдоп чйдефш (ун.~хрт.~23), юфп дмйощ пфтеълпч, чщчпдйнщи чп чтенс лбцдпк жбъщ, ухфш рпумедпчбфемшоп $$ 4, 4, 7, 13, 19, 31, 52, 82, 133, \ldots \eqno(24) $$ ртй ьфпн рпумедпчбфемшопуфш~$\< t_1, t_2, t_3,~\ldots>$ хдпчмефчптсеф ъблпох $$ t_n=t_{n-2}+2t_{n-3}+t_{n-4}, \eqno(25) $$ еумй уюйфбфш~$t_n=1$ ртй~$n \le 0$. Нпцоп фблце ртпбобмйъйтпчбфш прфйнбмшопе тбънеэеойе жйлфйчощи пфтеълпч, тбуунпфтеч уфтплй юйуем умйсойк, лбл нщ дембмй дмс уфбодбтфопзп нопзпжбъопзп нефпдб [ут.~у~(8)]: $$ \vcenter{\halign{ \hfill$#$\hfill&&\bskip\hfill$#$\hfill\bskip\cr & & & & & & \hbox{Плпоюбфемшощк} \cr \hbox{Хтпчеош} & T1 & T2 & T3 & T4 & T6 & \hbox{чщчпд об меофе}\cr 1 & 1 & 1 & 1 & 1 & - & T5 \cr 2 & 1 & 1 & 1 & - & 1 & T4 \cr 3 & 21 & 21 & 2 & 2 & 1 & T3 \cr 4 & 2221 & 222 & 222 & 22 & 2 & T2 \cr 5 & 23222 & 23222 & 2322 & 23 & 222 & T1 \cr 6 & 333323222 & 33332322 & 333323 & 3333 & 2322 & T6 \cr \multispan{7}\dotfill\cr n & A_n & B_n & C_n & D_n & E_n & T(k) \cr n+1 & (A''_n E_n+1)B_n & (A''_nE_n+1)C_n & (A''_n E_n+1)D_n & A''_nE_n+1 & A'_n & T(k-1)\cr \multispan{7}\dotfill\cr }} \eqno(26) $$ зде~$A_n=A'nA''_n$ й~$A''_n$ упуфпйф йъ рпумедойи $u_n$~юйуем умйсойк~$A_n$. Ртйчедеоопе чщые ртбчймп ретеипдб у хтпчос~$n$ об хтпчеош~$n+1$ уртбчедмйчп дмс \emph{мавпк} уиенщ, хдпчмефчптсаэек~(22). Еумй нщ пртедемсен~$u$ й~$v$ рпутедуфчпн~(23), фп уфтплй~$A_n$,~\dots, $E_n$ нпцоп чщтбъйфш ч умедхаэен, дпчпмшоп ртпуфпн чйде [ут.~у~(9)]: $$ \eqalign{ A_n &= (W_{n-1}W_{n-2}W_{n-3}W_{n-4})+1,\cr B_n &= (W_{n-1}W_{n-2}W_{n-3})+1,\cr C_n &= (W_{n-1}W_{n-2})+1,\cr D_n &= (W_{n-1})+1,\cr E_n &= (W_{n-2}W_{n-3})+1,\cr } \eqno(27) $$ зде $$ \eqalign{ W_n &= (W_{n-3}W_{n-4}W_{n-2}W_{n-3})+1 \rem{ртй $n>0$;}\cr W_0 &=\hbox{'0'}\hbox{ й } W_n = \hbox{(рхуфп)} \rem{ ртй $n<0$.}\cr } \eqno(28) $$ %%339 Йуипдс йъ ьфйи уппфопыеойк, мезлп рпдтпвоп ртпбобмйъйтпчбфш умхюбк ыеуфй меоф. Ч пвэен умхюбе, еумй йнеефус $T\ge 5$~меоф, фп рпмпцйн~$P=T-2$ й пртедемйн рпумедпчбфемшопуфй~$\$, $\$ рп ртбчймбн $$ \eqalign{ v_{n+1}&= u_{n-1}+v_{n-1}+\cdots+u_{n-r}+v_{n-r};\cr u_n &= u_{n-r-1}+v_{n-r-1}+\cdots+u_{n-P}+v_{n-P} \rem{ртй $n\ge 0$,}\cr } \eqno(29) $$ зде~$r=\floor{P/2}$, $v_0=1$ й~$u_n=v_n=0$ ртй~$n<0$. Еумй~$w_n=u_n+v_n$, фп йнеен $$ \eqalign{ w_n &= w_{n-2}+\cdots+w_{n-r}+2w_{n-r-1}+w_{n-r-2}+\cdots+w_{n-P}, \rem{$n>0$,}\cr w_0&=1 \hbox{ й } w_n=0 \rem{ртй $n<0$.}\cr } \eqno(30) $$ Ртй обюбмшопн тбуртедемеойй дмс хтпчос~$n+1$ об меофх~$k$ рпнеэбефус $w_n+w_{n-1}+\cdots+w_{n-P+k}$~пфтеълпч ртй~$1\le k \le P$ й~$w_{n-1}+\cdots+w_{n-r}$--- об меофх~$T$; меофб~$T-1$ йурпмшъхефус дмс ччпдб. Ъбфен $u_n$~пфтеълпч умйчбафус об меофх~$T$, ч фп чтенс лбл меофб~$T-1$ ретенбфщчбефус; $v_n$~пфтеълпч умйчбафус об~$T-1$, рплб~$T$ ретенбфщчбефус; $u_{n-1}$~пфтеълпч---об~$T-1$, рплб $T-2$~ретенбфщчбефус, й~ф.~д. \htable{Фбвмйгб~6} {Ртйвмйъйфемшопе рпчедеойе нопзпжбъопзп умйсойс у тбуэермеойен меоф}% {\hfill$#$\hfill&&\hfill\bskip$#$\bskip\hfill\cr \hbox{Меофщ} & \hbox{жбъщ} & \hbox{Ртпипдщ} & \hbox{Ртпипдщ/жбъщ} & \hbox{Пфопыеойе}\cr & & & \hbox{ч ртпгеофби} & \hbox{тпуфб}\cr \noalign{\hrule} 4 & 2.885\ln S+0.000 & 1.443\ln S+1.000 & 50 & 1.4142136\cr 5 & 2.078\ln S+0.232 & 0.929\ln S+1.022 & 45 & 1.6180340\cr 6 & 2.078\ln S-0.170 & 0.752\ln S+1.024 & 34 & 1.6180340\cr 7 & 1.958\ln S-0.408 & 0.670\ln S+1.007 & 34 & 1.6663019\cr 8 & 2.008\ln S-0.762 & 0.624\ln S+0.994 & 31 & 1.6454116\cr 9 & 1.972\ln S-0.987 & 0.595\ln S+0.967 & 30 & 1.6604077\cr 10 & 2.013\ln S-1.300 & 0.580\ln S+0.94l & 29 & 1.6433803\cr 20 & 2.069\ln S-3.164 & 0.566\ln S+0.536 & 27 & 1.6214947\cr \noalign{\hrule} } Фбвмйгб~6 рплбъщчбеф ртйвмйъйфемшопе рпчедеойе ьфпк ртпгедхтщ, лпздб~$S$ ое умйылпн нбмп. Уфпмвег "ртпипдщ/жбъщ" ртйнетоп хлбъщчбеф, лблбс юбуфш чуезп жбкмб ретенбфщчбефус чп чтенс лбцдпк рпмпчйощ жбъщ й лблбс юбуфш жбкмб ъбрйущчбефус ъб чтенс лбцдпк рпмопк жбъщ. \emph{Нефпд тбуэермеойс меоф ртечпуипдйф уфбодбтфощк нопзпжбъощк об ыеуфй ймй впмее меофби} й, четпсфоп; фблце об рсфй меофби, рп лтбкоек нете дмс впмшыйи~$S$. Еумй~$T=4$, фп хлбъбообс ртпгедхтб уфбмб вщ, рп ухэеуфчх, ьлчйчбмеофопк увбмбоуйтпчбоопнх дчхирхфечпнх умйсойа \emph{веъ} упчнеэеойс чтенеой ретенпфлй, фбл лбл~$w_{2n+1}$ вщмп вщ тбчоп~$0$ %$390 ртй чуеи~$n$. Рпьфпнх ьменеофщ фбвм.~6 ртй~$T=4$ вщмй рпмхюеощ рпутедуфчпн оевпмшыпк нпдйжйлбгйй, упуфпсэек ч фпн, юфп рпмбзбмпуш $$ \displaylines{ v_2=0, u_1=1, v_1=0, u_0=0, v_0=1\hbox{ й } v_{n+1}=u_{n-1}+v_{n-1},\cr u_n=u_{n-2}+v_{n-2}\rem{ртй $n \ge 2$.}\cr } $$ Ьфп ртйчпдйф л пюеош йофетеуопк уиене уптфйтпчлй (ун.~хрт.~25 й~26). \excercises \ex[16] Об тйу.~69 хлбъбо рптсдпл, ч лпфптпн бмзптйфн~D тбуртедемсеф рп рсфй меофбн пфтеълй у~34-зп рп~65-к; ч лблпн рптсдле тбуртедемсафус пфтеълй у~1-зп рп~33-к? \rex[21] Четоп мй, юфп рпуме дчхи жбъ умйсойс ч бмзптйфне~D, ф.~е.~лпздб нщ чп чфптпк тбъ дпуфйзоен ыбзб~D6, чуе жйлфйчоще пфтеълй йуюеъбаф? \rex[22] Дплбцйфе, юфп рп плпоюбойй ыбзб~D4 чуездб чщрпмоеоп хумпчйе $|D|[1]\ge |D|[2] \ge \ldots \ge |D|[T]$. ПвRсуойфе, чбцопуфш ьфпзп хумпчйс дмс ртбчймшопк тбвпфщ неибойънб ыбзпч~D2 й~D3. \ex[Н20] Чщчедйфе ртпйъчпдсэйе жхолгйй~(7). \ex[ЧН26] (Ь.~Р.~Нбкму~нм., 1960.) Дплбцйфе, юфп ртй чуеи~$p\ge 2$ нопзпюмео~$f_p(z)=z^p-z^{p-1}-\cdots-z-1$ йнееф $p$~тбъмйюощи лптоек, йъ лпфптщи тпчоп пдйо ртечпуипдйф~1 рп бвупмафопк чемйюйое. [\emph{Хлбъбойе:} тбуунпфтйфе нопзпюмео~$z^{p+1}-2z^p+1$.] \ex[ЧН24] Гемш ьфпзп хртбцоеойс---тбуунпфтефш урпупв упуфбчмеойс фбвм.~1, 5 й~6. Ртедрпмпцйн, юфп йнеефус уиенб умйсойс, учпкуфчб лпфптпк умедхаэйн пвтбъпн ибтблфетйъхафус нопзпюмеобнй~$p(z)$ й~$q(z)$: (1)~Юйумп обюбмшощи пфтеълпч ч "фпюопн тбуртедемеойй", фтевхаэен $n$~жбъ умйсойс, тбчоп лпьжжйгйеофх ртй~$z^n$ ч~$p(z)/q(z)$. (2)~Юйумп обюбмшощи пфтеълпч, пвтбвбфщчбенщи ч феюеойе ьфйи $n$~жбъ умйсойс, тбчоп лпьжжйгйеофх ртй~$z^n$ ч~$p(z)/q(z)^2$. (3)~Х нопзпюмеоб~$q(z^{-1})$ еуфш "змбчощк лптеош"~$\alpha$, фблпк, юфп~$q(\alpha^{-1})=0$, $q'(\alpha^{-1}) \ne 0$, $p(\alpha^{-1})\ne 0$, й йъ~$q(\beta^{-1})=0$ умедхеф, юфп~$\beta=\alpha$ ймй~$\abs{\beta}<\abs{\alpha}$. Дплбцйфе, юфп ухэеуфчхеф~$\varepsilon > 0$, фблпе, юфп еумй $S$~тбчоп юйумх пфтеълпч ч фпюопн тбуртедемеойй, фтевхаэен $n$~жбъ умйсойс, б чп чтенс ьфйи жбъ пвтбвбфщчбефус $\rho S$~пфтеълпч, фп~$n=a\ln S+b+O(S^\varepsilon)$, $\rho=c\ln S+d+O(S^{-\varepsilon})$, зде $$ \displaylines{ a=(\ln \alpha)^{-1},\quad b= -a\ln\left({p(\alpha^{-1})\over -q'(\alpha^{-1})}\right)-1, \quad c=a{\alpha\over -q'(\alpha^{-1})},\cr d={(b+1)\alpha-p'(\alpha^{-1})/p(\alpha^{-1})+q''(\alpha^{-1})/q'\alpha^{-1} \over -q'(\alpha^{-1})}.\cr } $$ \ex[ЧН22] Рхуфш~$\alpha_p$---змбчощк лптеош нопзпюмеоб~$f_p(z)$ йъ хрт.~5. Лблпчп буйнрфпфйюеулпе рпчедеойе~$\alpha_p$ ртй~$p\to\infty$? \ex[Н20] (Ь.~Оеффп, 1901.) Рхуфш~$N^{(p)}_m$ еуфш юйумп урпупвпч чщтбъйфш~$m$ ч чйде хрптсдпюеоопк ухннщ гемщи юйуем~$\set{1, 2,~\ldots, p}$. Обртйнет, еумй~$p=3$ й~$m=5$, фп йнеефус 13~урпупвпч: $1+1+1+1+1=1+1+1+2=1+1+2+1=1+1+3=1+2+1+1 =1+2+2= 1+3+1=2+1+1+1=2+1+2=2+2+1=2+3=3+1+1=3+2$. Рплбцйфе, юфп $N^{(p)}_m$~счмсафус пвпвэеоощнй юйумбнй Жйвпобююй. \ex[Н20] Рхуфш~$K^{(p)}_m$---юйумп рпумедпчбфемшопуфек йъ охмек й едйойг, фблйи, юфп ч ойи оеф $p$~рпумедпчбфемшощи едйойг. Обртйнет, еумй~$p=3$ й~$m=5$, йнеефус 24~чбтйбофб: $00000$, $00001$, $00010$, $00011$, $00100$, $00101$, $00110$, $01000$, $01001$,~\dots, $11011$. Рплбцйфе, юфп $K^{(p)}_m$~счмсафус пвпвэеоощнй юйумбнй Жйвпобююй. %%341 \ex[Н27]\exhead(Уйуфенб уюйумеойс у пвпвэеоощнй юйумбнй Жйвпобююй.) Дплбцйфе, юфп лбцдпе оепфтйгбфемшопе гемпе~$n$ йнееф едйоуфчеоопе ртедуфбчмеойе ч чйде ухннщ тбъмйюощи юйуем Жйвпобююй $p\hbox{-зп}$~рптсдлб~$F^{(p)}_j$ ртй~$j\ge p$, хдпчмефчптсаэее хумпчйа, юфп ое йурпмшъхафус ойлблйе $p$~рпумедпчбфемшоще юйумб Жйвпобююй. \ex[Н24] Дплбцйфе, юфп $n\hbox{-к}$~ьменеоф герпюлй~$Q_\infty$ ч~(12) тбчео лпмйюеуфчх тбъмйюощи юйуем Жйвпобююй ч ртедуфбчмеойй ьменеофб $n-1$~юйумбнй Жйвпобююй рсфпзп рптсдлб (ун.~хрт.~10). \rex[M20] Обкдйфе ъбчйуйнпуфш нецдх уфереоснй нбфтйгщ $$ \pmatrix{ 0 & 1 & 0 & 0 & 0 \cr 0 & 0 & 1 & 0 & 0 \cr 0 & 0 & 0 & 1 & 0 \cr 0 & 0 & 0 & 0 & 1 \cr 1 & 1 & 1 & 1 & 1 \cr } $$ й фпюощн жйвпобююйечщн тбуртедемеойен ч~(1). \rex[22] Дплбцйфе умедхаэее йофетеуопе учпкуфчп фпюощи жйвпобююйечщи тбуртедемеойк: еумй плпоюбфемшощк чщчпд плбъщчбефус об меофе опнет~$T$, фп юйумп пфтеълпч об чуеи дтхзйи меофби \emph{оеюефопе,} еумй плпоюбфемшощк чщчпд плбъщчбефус об оелпфптпк меофе, пфмйюопк пф~$T$, фп юйумп пфтеълпч вхдеф \emph{оеюефощн} об ьфпк меофе й \emph{юефощн} об пуфбмшощи [ун.~(1)]. \ex[Н35] Рхуфш~$T_n(x)=\sum_{k\ge0} T_{nk}x^k$, зде $T_n(x)$---нопзпюмеощ, пртедемеооще ч~(16). (a)~Рплбцйфе, юфп дмс лбцдпзп~$k$ ухэеуфчхеф юйумп~$n(k)$, фблпе, юфп~$T_{1k}\le T_{2k} \le \ldots \le T_{n(k)k} > T_{n(k)+1,k}\ge\ldots\,$.. (b)~Ртй хумпчйй юфп~$T_{n'k'}$, фблбс, юфп~$\sum_n(S) =\min_{j\ge 1} \sum_j (S)$ ртй~$M_n\le S < M_{n+1}$, оп~$\sum_n(S)>\min_{j\ge 1}\sum_j(S)$ ртй~$S\ge M_{n+1}$. [Ун.~(19).] \ex[Н43] Четоп мй, юфп~$\sum_{n-1}(m) < \sum_n (m)$ чмеюеф~$\sum_n(m)\le\sum_{n+1}(m)\le \sum_{n+2}(m) \le \ldots?$ (Фблпк теъхмшфбф уймшоп хртпуфйм вщ чщюйумеойе фбвм.~2.) \ex[M43] Пртедемйфе буйнрфпфйюеулпе рпчедеойе нопзпжбъопзп умйсойс у прфйнбмшощн тбуртедемеойен жйлфйчощи пфтеълпч. \ex[32] Четоп мй, юфп пфтеълй дмс прфйнбмшопзп нопзпжбъопзп тбуртедемеойс нпцоп тбънеуфйфш фблйн пвтбъпн, юфп тбуртедемеойе $S+1$~обюбмшощи пфтеълпч рпмхюбефус рхфен дпвбчмеойс пдопзп пфтеълб (об уппфчефуфчхаэха меофх) л тбуртедемеойа $S$~обюбмшощи пфтеълпч? \ex[30] Четоп мй, юфп прфйнбмшопе нопзпжбъопе тбуртедемеойе дбеф обймхюыха чпънпцоха уиенх умйсойс ч фпн унщуме, юфп ухннбтопе лпмйюеуфчп пвтбвбфщчбенщи обюбмшощи пфтеълпч нйойнбмшоп, еумй фтевхефус, юфпвщ обюбмшоще пфтеълй тбънеэбмйуш ое впмее, юен об $T-1$~меофби? (Чтенеоен ретенпфлй ртеоевтеюш.) \ex[21] Упуфбчшфе фбвмйгх, бобмпзйюоха~(1), дмс нопзпжбъопзп нефпдб уптфйтпчлй Льктпоб дмс ыеуфй меоф. \ex[Н24] Лблбс ртпйъчпдсэбс жхолгйс дмс льктпопчулпк нопзпжбъопк уптфйтпчлй об ыеуфй меофби уппфчефуфчхеф~(7) й~(16)? Лблйе уппфопыеойс, бобмпзйюоще~(9) й~(27), пртедемсаф уфтплй юйуем умйсойк? \ex[11] Юфп дпмцоп рпсчйфшус об хтпчое~7 ч~(26)? \ex[M21] Лбцдщк юмео рпумедпчбфемшопуфй~(24) ртйвмйъйфемшоп тбчео ухнне дчхи ртедщдхэйи. Обвмадбефус мй ьфп счмеойе дмс пуфбмшощи юмеопч рпумедпчбфемшопуфй? Ужптнхмйтхкфе й дплбцйфе фептенх п~$t_n-t_{n-1}-t_{n-2}$. \rex[29] Лблйе йънеоеойс обдп вщмп вщ удембфш ч~(25), (27) й (28), еумй вщ (23)~ъбнеоймпуш об~$v_{n+1}=u_{n-1}+v_{n-1}+u_{n-2}$, $u_n=v_{n-2}+u_{n-3}+v_{n-3}+u_{n-4}+v_{n-4}$? %%342 \ex[ЧН41] Чщюйумйфе буйнрфпфйюеулпе рпчедеойе нопзпжбъопк ртпгедхтщ у тбуэермеойен меоф, еумй ьменеоф~$v_{n+1}$ пртедемео лбл ухннб ретчщи$q$ юмеопч~$u_{n-1}+v_{n-1}+\cdots+u_{n-P}+v_{n-P}$ ртй тбъмйюощи~$P=T-2$ й~$0\le q \le 2P$. (Ч фелуфе тбуунбфтйчбефус фпмшлп умхюбк~$q=2\floor{P/2}$; ут.~у~хрт.~23.) \ex[19] Ртпденпоуфтйтхкфе, лбл нопзпжбъопе умйсойе у тбуэермеойен меоф, хрпнсохфпе ч лпоге ьфпзп рхолфб, уптфйтпчбмп вщ 32~обюбмшощи пфтеълб. (Дбкфе бобмйъ жбъб ъб жбъпк, лбл ьфп удембоп ч фелуфе ч ртйнете у 82~пфтеълбнй й 6~меофбнй.) \ex[Н21] Ртпбобмйъйтхкфе рпчедеойе нопзпжбъопзп умйсойс у тбуэермеойен меоф об юефщтеи меофби ртй~$S=2^n$ й ртй~$S=2^n+2^{n-1}$ (ун.~хрт.~25). \ex[23] Еумй обюбмшоще пфтеълй тбуртедемеощ об меофби ч уппфчефуфчйй у фпюощн тбуртедемеойен, фп нопзпжбъобс уфтбфезйс ртечтбэбефус ртпуфп ч "умйчбфш дп прхуфпыеойс". Нщ умйчбен пфтеълй уп чуеи оерхуфщи чипдощи меоф, рплб пдоб йъ ойи ое уфбоеф рхуфпк, ъбфен нщ йурпмшъхен ьфх меофх лбл умедхаэха чщчпдоха, б ртедщдхэха чщчпдоха меофх йурпмшъхен лбл ччпдоха. Четоп мй, юфп ьфб уфтбфезйс "умйчбфш дп прхуфпыеойс" чуездб чщрпмосеф уптфйтпчлх оеъбчйуйнп пф фпзп, лбл тбуртедемеощ обюбмшоще пфтеълй, ртй хумпчйй юфп нщ тбуртедемсен йи рп лтбкоек нете об дче меофщ (пдоб меофб, лпоеюоп, вхдеф пуфбчмеоб рхуфпк, юфпвщ поб нпзмб умхцйфш ретчпк чщчпдопк меофпк). \edef\exref{\the\excerno} \ex[Н26] Ртедщдхэее хртбцоеойе пртедемсеф чеушнб впмшыпе уенекуфчб уиен умйсойс. Рплбцйфе, юфп нопзпжбъобс уиенб \emph{обймхюыбс} йъ ойи ч умедхаэен унщуме: еумй йнеефус ыеуфш меоф й нщ тбуунбфтйчбен лмбуу чуеи обюбмшощи тбуртедемеойк~$(a, b, c, d, e)$, фблйи, юфп уфтбфезйс "умйчбфш дп прхуфпыеойс" фтевхеф~$n$ ймй неошые жбъ дмс уптфйтпчлй, фп~$a+b+c+d+e\le t_n$, зде~$t_n$---уппфчефуфчхаэее юйумп дмс нопзпжбъопк уптфйтпчлй~(1). \ex[Н47] Хрт.~\exref{} рплбъщчбеф, юфп нопзпжбъопе тбуртедемеойе прфйнбмшоп утедй чуеи уиен "умйчбфш дп прхуфпыеойс" ч унщуме нйойнбмшопуфй юйумб жбъ. Оп счмсефус мй поп прфйнбмшощн фблце ч унщуме нйойнбмшопуфй юйумб ртпипдпч? Рхуфш юйумб~$a$ й~$b$ чъбйноп ртпуфще, й ртедрпмпцйн, юфп $a+b$~еуфш юйумп Жйвпобююй~$F_n$. Четоп мй умедхаэее ртедрпмпцеойе, чщулбъбоопе Т.~Н.~Лбтрпн: юйумп обюбмшощи пфтеълпч, пвтбвбфщчбенщи уиенпк "умйчбфш дп прхуфпыеойс", обюйобаэекус у тбуртедемеойс~$(a, b)$, впмшые ймй тбчоп~$((n-5)F_{n+1}+(2n+2)F_n)/5$? (Хлбъбоопе ъобюеойе дпуфйзбефус, лпздб~$a=F_{n+1}$, $b=F_{n-2}$.) \ex[42] Упуфбчшфе фбвмйгх, бобмпзйюоха фбвм.~2, дмс нопзпжбъопзп умйсойс у тбуэермеойен меоф. \subsubchap{Лбулбдопе умйсойе}%5.4.3 Дтхзбс пуопчобс уиенб, объщчбенбс "лбулбдощн умйсойен", об убнпн деме вщмб пфлтщфб тбошые нопзпжбъопк [В.~Л.~Вефг й~Х.~Л.~Лбтфет, ACM Nat'1 Conference, {\bf 14} (1959), Paper~14]. Ойце ч фбвмйге ьфпф рпдипд йммауфтйтхефус дмс 6~меоф й~190~обюбмшощи пфтеълпч у йурпмшъпчбойен пвпъобюеойк йъ р.~5.4.2: \ctable{ #\hfil\bskip&\bskip\hfil$#$\bskip\hfil&\bskip\hfil$#$\bskip\hfil &\bskip\hfil$#$\bskip\hfil&\bskip\hfil$#$\bskip\hfil &\bskip\hfil$#$\bskip\hfil&\bskip\hfil$#$\bskip\hfil&#\hfil\cr & T1 & T2 & T3 & T4 & T5 & T6 & Лпмйюеуфчп пвтбвпфбоощи обюбмшощи пфтеълпч\cr Ртпипд~1. & 1^{55} & 1^{50} & 1^{41} & 1^{29} & 1^{15} & - & 190 \cr Ртпипд~2. & - & {1^5}_* & 2^9 & 3^{12} & 4^{14} & 5^{15}& 190 \cr Ртпипд~3. & 15^5 & 14^4 & 12^3 & 9^2 & {5^1}_*& - & 190 \cr Ртпипд~4. & - & {15^1}_*& 29^1 & 41^1 & 50^1 & 55^1 & 190 \cr Ртпипд~5. & 190^1 & - & - & - & - & - & 190 \cr } %%343 \bye