%% 428 \input style \subsubchap{Дйулй й вбтбвбощ} Дп уйи рпт нщ тбуунбфтйчбмй меофщ лбл едйоуфчеоопе утедуфчп дмс чоеыоек уптфйтпчлй, пдоблп оетедлп ч обыен тбурптсцеойй плбъщчбафус й дтхзйе фйрщ хуфтпкуфч нбуупчпк рбнсфй у впмее зйвлйнй чпънпцопуфснй. Ипфс фблйе ъбрпнйобаэйе .хуфтпкуфчб "впмшыпзп пвRенб" ймй "ъбрпнйобаэйе хуфтпкуфчб у ртснщн дпуфхрпн" чеушнб нопзппвтбъощ, нпцоп чщдемйфш умедхаэйе пвэйе учпкуфчб: \medskip \item{i)} Дмс дпуфхрб л мавпк пртедемеоопк юбуфй итбойнпк йожптнбгйй ое фтевхефус пюеош нопзп чтенеой. \item{ii)} Вмплй, упдетцбэйе рпумедпчбфемшоще умпчб, нпзхф вщуфтп ретедбчбфшус нецдх чохфтеооек (претбфйчопк) й чоеыоек рбнсфша. \medskip \noindent Нбзойфобс меофб хдпчмефчптсеф (ii), оп ое (i), рпулпмшлх ретеипд меофщ пф пдопзп лпогб л дтхзпнх ъбойнбеф нопзп чтенеой. Оелпфптще хуфтпкуфчб хдпчмефчптсаф (i), оп ое (ii); ртйнетпн нпцеф умхцйфш рбнсфш впмшыпзп пвRенб об жеттйфпчщи уетдеюойлби, \picture{Тйу. 89. Рблеф дйулпч} ч лпфптпк чтенс дпуфхрб л лбцдпнх умпчх ртйнетоп ч деусфш тбъ ртечщыбеф чтенс дпуфхрб л чохфтеооек рбнсфй. Лбцдпе чоеыоее ъбрпнйобаэее хуфтпкуфчп йнееф учпй ибтблфетоще пупвеоопуфй, лпфптще умедхеф фэбфемшоп йъхюйфш, ртецде юен рйубфш дмс оезп впмшыйе ртпзтбннщ; пдоблп феиопмпзйс неосефус фбл вщуфтп, юфп ъдеуш ое хдбуфус улпмшлп-ойвхдш рпдтпвоп пвухдйфш чуе ухэеуфчхаэйе тбъопчйдопуфй пвптхдпчбойс. Рпьфпнх нщ тбуунпфтйн мйыш оелпфптще фйрйюоще ъбрпнйобаэйе хуфтпкуфчб й об .ойи ртпйммауфтйтхен ртпдхлфйчоще рпдипдщ л ъбдбюе уптфйтпчлй. Пдойн йъ обйвпмее тбуртпуфтбоеоощи фйрпч чоеыойи ъбрпнйобаэйи хуфтпкуфч, хдпчмефчптсаэйи (i) й (ii), счмсефус дйулпчщк %% 429 жбкм ймй нпдхмш у рблефпн дйулпч (тйу. 89). Дбооще итбосфус об оеулпмшлйи вщуфтп чтбэбаэйиус лтхзмщи дйулби, рплтщфщи нбзойфощн нбфетйбмпн; дмс ъбрйуй ймй чщвптлй йожптнбгйй йурпмшъхефус детцбфемш зпмпчпл ч чйде зтевеылб. упдетцбэйк пдох ймй оеулпмшлп "зпмпчпл юфеойс/ъбрйуй" дмс лбцдпк рпчетиопуфй дйулб. Лбцдбс рпчетиопуфш демйфус об лпогеофтйюеулйе лпмшгб, объщчбенще \emph{дптпцлбнй} ймй \emph{фтелбнй}, фбл юфп ъб чтенс пдопзп пвптпфб дйулб рпд зпмпчлбнй юфеойс/ъбрйуй ртпипдйф гембс дптпцлб. Детцбфемш зпмпчпл нпцеф ретенеэбфшус ч дчхи обртбчмеойси---чохфтш ймй обтхцх, ретедчйзбс зпмпчлй юфеойс/ъбрйуй пф дптпцлй л дптпцле, оп ьфп дчйцеойе фтевхеф чтенеой. Нопцеуфчп дптпцел, лпфптще нпзхф вщфш ртпюйфбощ ймй ъбрйубощ веъ ретенеэеойс детцбфемс зпмпчпл, объщчбефус \emph{гймйодтпн}. Обртйнет, об тйу.~89 рплбъбо дйулпчщк жбкм, лпфптщк йнееф рп пдопк зпмпчле юфеойс/ъбрйуй об лбцдха рпчетиопуфш; рхолфйтощнй мйойснй пвпъобюео пдйо йъ гймйодтпч, упуфпсэйк йъ чуеи дптпцел, ртпунбфтйчбенщи ч обуфпсэйк нпнеоф зпмпчлбнй. Юфпвщ удембфш обый тбуухцдеойс впмее лполтефощнй, тбуунпфтйн зйрпфефйюеулпе дйулпчпе хуфтпкуфчп |MIXTEC|, дмс лпфптпзп $$ \eqalign{ \hbox{1 дптпцлб}& =\hbox{5000 мйфет,}\cr \hbox{1 гймйодт}& =\hbox{20 дптпцел,}\cr \hbox{1 дйулпчпе хуфтпкуфчп}&= \hbox{200 гймйодтпч.}\cr } $$ Фблпе дйулпчпе хуфтпкуфчп упдетцйф 20 нйммйпопч мйфет, ф. е. юхфш неошые фпзп пвRенб дбоощи, лпфптщк нпцоп ъбрйубфш об пдох нбзойфоха меофх. Об оелпфптщи нбыйоби дптпцлй чвмйъй геофтб упдетцбф неошые мйфет, юен дптпцлй вмйце л лтба. Пф ьфпзп ртпзтбннйтпчбойе ъобюйфемшоп хумпцосефус, оп |MIXTEC|, л уюбуфша, ое упъдбеф фблйи ртпвмен. Чтенс, оепвипдйнпе дмс юфеойс ймй ъбрйуй об дйулпчщк жбкм, ртедуфбчмсеф, рп ухэеуфчх, ухннх фтеи чемйюйо: \itemize \li Чтенс рпйулб (чтенс, ъбфтбюйчбенпе об ретенеэеойе детцбфемс зпмпчпл л охцопнх гймйодтх). \li Чтенс пцйдбойс (ъбдетцлб, учсъбообс у чтбэеойен дйулб, рплб зпмпчлб юфеойс/ъбрйуй ое дпуфйзоеф охцопзп неуфб). \li Чтенс ретедбюй (ъбдетцлб, учсъбообс у чтбэеойен дйулб, рплб дбооще ртпипдсф рпд зпмпчлбнй). \itemend Об хуфтпкуфчби |MIXTEC| чтенс рпйулб дмс ретеипдб пф гймйодтб $i$ л гймйодтх $j$ тбчоп $25+{1\over2}\vert i-j \vert$ ну. Еумй $i$ й $j$---умхюбкоп чщвтбооще гемще юйумб нецдх 1 й 200, фп утедоее ъобюеойе %%430 $\vert i-j\vert$ тбчоп $2 \left( {201\atop 3}\right)/200^2\approx 66.7$, ф. е. утедоее чтенс рпйулб упуфбчмсеф ртйвмйъйфемшоп 60~ну. Дйулй |MIXTEC| упчетыбаф пдйо пвптпф ъб 25 ну, фбл юфп чтенс пцйдбойс тбчоп ч утедоен 12.5 ну. Чтенс ретедбюй $n$ мйфет еуфш $(n/5000)\times25\hbox{ ну}=5n\hbox{ нлу}$. (Ьфп ртйнетоп ч $3{1\over3}$ тбъб вщуфтее, юен улптпуфш ретедбюй дмс меоф |MIXT|, йурпмшъпчбоощи ч ртйнетби р.~5.4.6.) Фблйн пвтбъпн, пуопчоще тбъмйюйс нецдх дйулбнй |MIXTEC| й меофбнй |MIXT|, лбубаэйеус уптфйтпчлй, умедхаэйе: \medskip \item{a)} Об меофби чпънпцео фпмшлп рпумедпчбфемшощк дпуфхр л дбоощн. \item{b)} Пфдемшобс претбгйс у дйулпн, лбл ртбчймп, упртсцеоб уп ъобюйфемшоп впмшыйнй облмбдощнй тбуипдбнй (чтенс рпйулб + чтенс пцйдбойс ч утбчоеойй уп уфбтфуфпрощн чтенеоен). \item{c)} Улптпуфш ретедбюй х дйулб впмшые. \medskip Йурпмшъхс дмс меоф тбъхноще уиенщ умйсойс, нщ нпзмй дп оелпфптпк уфереой улпнреоуйтпчбфш оедпуфбфпл (a). Феретш х обу йобс гемш---обн охцоп обкфй фблйе тбгйпобмшоще бмзптйфнщ уптфйтпчлй об дйулби, ч лпфптщи лпнреоуйтхефус оедпуфбфпл (b). \qsection Лбл уплтбфйфш чтенс пцйдбойс? Тбуунпфтйн .уобюбмб ъбдбюх нйойнйъбгйй ъбдетцел, чщъщчбенщи фен, юфп ч фпф нпнеоф, лпздб нщ ипфйн обюбфш лпнбодх ччпдб/чщчпдб, дйул ое чуездб обипдйфус ч рпдипдсэек рпъйгйй. Оемшъс ъбуфбчйфш дйул чтбэбфшус вщуфтее, оп чуе-фблй нпцоп ртйвезохфш л тбъощн хмпчлбн, лпфптще хнеошыбф ймй дбце рпмопуфша хуфтбосф чтенс пцйдбойс. Оеупноеооп, рпнпцеф дпвбчмеойе еэе оеулпмшлйи детцбфемек зпмпчпл, оп ьфп чеушнб дптпзпуфпсэбс нпдйжйлбгйс пвптхдпчбойс. Чпф оеулпмшлп "ртпзтбннйуфулйи" йдек. \enumerate \li Еумй нщ юйфбен ймй ъбрйущчбен ъб пдйо тбъ оеулпмшлп дптпцел пдопзп гймйодтб, фп фен убнщн хуфтбосен чтенс пцйдбойс (й чтенс рпйулб) дмс чуеи дптпцел, лтпне ретчпк. Чппвэе ъбюбуфха нпцоп фблйн пвтбъпн уйоитпойъпчбфш чщюйумеойс у чтбэеойен дйулб, юфп ртй чщрпмоеойй рпумедпчбфемшопуфй лпнбод ччпдб/чщчпдб ое вхдеф ъбдетцел йъ-ъб пцйдбойс. \li Тбуунпфтйн ъбдбюх юфеойс рпмпчйощ дптпцлй дбоощи (тйу.~90): еумй лпнбодб юфеойс чщдбефус, лпздб зпмпчлб обипдйфус ч фпюле $A$, фп ъбдетцлб об пцйдбойе пфухфуфчхеф, й пвэее чтенс юфеойс тбчоп чтенеой ретедбюй, ф.е. ${1\over2}\times25$ ну. Еумй лпнбодб обюйобефус, лпздб зпмпчлб обипдйфус ч фпюле $B$, фп фтевхефус ${1\over 4}$ пвптпфб дмс пцйдбойс й $1\over2$ дмс ретедбюй; ч йфпзе йнеен %%431 ${3\over4}\times25$ ну. Обйвпмее йофетеуео умхюбк, лпздб зпмпчлб ретчпобюбмшоп обипдйфус ч фпюле $C$: йнес уппфчефуфчхаэее пвптхдпчбойе й ртпзтбннопе пвеуреюеойе, обн \emph{ое} ртйдефус фетсфш $3\over4$ пвптпфб об пцйдбойе. Нпцоп оенедмеооп обюбфш юфеойе чп чфптха рпмпчйох вхжетб ччпдб, ъбфен рпуме рбхъщ ч ${1\over2}\times25$ ну .нпцоп чпъпвопчйфш юфеойе ч ретчха рпмпчйох вхжетб, фбл юфп лпнбодб . вхдеф ъбчетыеоб, лпздб нщ уопчб рпрбден ч фпюлх $C$. Рпуфхрбс \picture{Тйу. 90. Бобмйъ чтенеой пцйдбойс ртй юфеойй рпмпчйощ дптпцлй} фблйн пвтбъпн, нпцоп збтбофйтпчбфш, юфп пвэее чтенс об пцйдбойе+ретедбюх ойлпздб ое ртечъпкдеф чтенеой пдопзп пвптпфб оеъбчйуйнп пф обюбмшопзп рпмпцеойс дйулб. Утедоее чтенс пцйдбойс хнеошыбефус ьфпк уиенпк у рпмпчйощ пвптпфб дп ${1\over2}(1-x^2)$ пвптпфб, еумй юйфбефус ймй ъбрйущчбефус дпмс $x$ дптпцлй ($0оеюефопе юйумп тбъ, оп ч умхюбе пдопзп вбтбвбоб нпцоп йурпмшъпчбфш впмее пвэйе уиенщ умйсойс. Нщ чйдемй ч р.~5.4.4, юфп уиенщ умйсойс нпцоп йъпвтбцбфш у рпнпэша детечшеч й юфп чтенс ретедбюй, уппфчефуфчхаэее уиене умйсойс, ртпрптгйпобмшоп дмйое чоеыоезп рхфй детечб. Ч лбюеуфче уиен ьжжелфйчопзп умйсойс об меофби нпцоп йурпмшъпчбфш мйыш чрпмое пртедемеооще детечшс ("$T$-lifo" ймй "уймшоще $T$-fifo"), рпфпнх юфп ч ртпгеууе умйсойс оелпфптще пфтеълй плбъщчбафус "уртсфбоощнй" ч уетедйое меофщ. Оп \emph{ртй йурпмшъпчбойй дйулпч ймй вбтбвбопч ртйзпдощ мавще детечшс}, еумй фпмшлп уфереой йи чохфтеоойи хъмпч ое умйылпн чемйлй (ф. е. упзмбухафус у обмйюощн пвRенпн чохфтеооек рбнсфй). Умедпчбфемшоп, чтенс ретедбюй нпцоп нйойнйъйтпчбфш, еумй чщвтбфш детечп у нйойнбмшопк дмйопк чоеыоезп рхфй, фблпе, лбл рпмопе $P$-бтопе детечп, зде $P$---убнпе впмшыпе, лблпе чпънпцоп. Рп жптнхме (5.4.4--9) дмйоб чоеыоезп рхфй фблпзп детечб %% 434 у $S$ чоеыойнй хъмбнй (мйуфшснй) тбчоб $$ qS-\lfloor(P^q-S)/(P-1)\rfloor, \qquad q=\lceil\log_P S\rceil. \eqno(1) $$ Пупвеооп ртпуфп уфтпйфус бмзптйфн, лпфптщк пухэеуфчмсеф умйсойе ч уппфчефуфчйй уп уиенпк рпмопзп $P$-бтопзп детечб. (Ун., обртйнет, тйу.~91, об лпфптпн рплбъбо умхюбк $P=3$, $S=6$.) Уобюбмб нщ дпвбчмсен, еумй оепвипдйнп, "жйлфйчоще пфтеълй", юфпвщ удембфш $S\equiv1 \pmod{P-1}$; ъбфен пвRедйосен пфтеълй ч уппфчефуфчйй у дйугйрмйопк "ретчщн члмаюбефус --- \picture{Тйу. 92. Рпмопе фетобтопе детечп у ыеуфша мйуфшснй...} ретчщн йулмаюбефус", умйчбс об лбцдпн ьфбре $P$ убнщи "уфбтщи" пфтеълпч ч обюбме пюетедй ч пдйо пфтеъпл, рпнеэбенщк ч лпоег. Рпмоще $P$-бтоще детечшс дбаф прфйнбмшоха уиенх, еумй чуе пфтеълй йнеаф тбчоха дмйох, оп юбуфп теъхмшфбф нпцеф вщфш еэе мхюые, еумй оелпфптще пфтеълй дмйооее дтхзйи. Прфйнбмшоха уиенх дмс ьфпк пвэек уйфхбгйй нпцоп веъ фтхдб рпуфтпйфш у рпнпэша нефпдб Ибжжньоб (хрт. 2.3.4.5--10), лпфптщк об същле умйсойс жптнхмйтхефус фбл: "уобюбмб дпвбчшфе $(1-S)\bmod(P-1)$ жйлфйчощи пфтеълпч дмйощ 0, ъбфен нопзплтбфоп умйчбкфе $P$ \emph{лтбфюбкыйи} йъ йнеаэйиус пфтеълпч, рплб ое пуфбоефус пдйо пфтеъпл". Еумй чуе обюбмшоще пфтеълй йнеаф пдйоблпчха дмйох, фп ьфпф нефпд учпдйфус л прйубоопк чщые дйугйрмйое. Ч обыен ртйнете уп 100000, ъбрйуек нщ нпцен чщрпмосфш 9-рхфечпе умйсойе, фбл лбл ч рбнсфй рпнеуфсфус 18 вхжетпч ччпдб й дчб вхжетб чщчпдб, й ч бмзптйфне 5.4.6F вхдеф дпуфйзохфп рпмопе упчнеэеойе чщюйумеойк. Рпмопе 9-бтопе детечп у 60 мйуфшснй уппфчефуфчхеф уиене умйсойс у $1{29\over30}$ ртпипдб, еумй. чуе обюбмшоще пфтеълй йнеаф пдйоблпчха дмйох. Пвэее чтенс уптфйтпчлй у пдойн вбтбвбопн й у йурпмшъпчбойен "лпофтпмшопзп юфеойс" рпуме лбцдпк ъбрйуй уфбопчйфус, фблйн пвтбъпн, тбчощн 7.4 нйо. Хчемйюйчбс $P$, нпцоп оенопзп хнеошыйфш ьфп чтенс, оп уйфхбгйс чеушнб ъбрхфбообс, рпулпмшлх ое йулмаюбефус ъбдетцлб юфеойс, фбл лбл вхжетщ нпзхф плбъбфшус умйылпн рпмощнй ймй умйылпн рхуфщнй. %%435 \section Чмйсойе чтенеой рпйулб. Ртедщдхэее пвухцдеойе рплбъщчбеф, юфп дмс вбтбвбопч пфопуйфемшоп мезлп улпоуфтхйтпчбфш "прфйнбмшоха" уиенх умйсойс, рпулпмшлх чтенс рпйулб й чтенс пцйдбойс нпцоп учеуфй об оеф. Оп еумй йурпмшъхафус дйулй, фп рпйул йожптнбгйй ъбойнбеф впмшые чтенеой, юен ее юфеойе. Рпьфпнх чтенс рпйулб плбъщчбеф ъобюйфемшопе чмйсойе об уфтбфезйа уптфйтпчлй. Хнеошыеойе рптсдлб умйсойс $P$ дбеф чпънпцопуфш . йурпмшъпчбфш впмшыйе рп тбънетх вхжетщ, фбл юфп теце фтевхефус рпйул; ъб уюеф ьфпзп юбуфп лпнреоуйтхефус дпрпмойфемшопе чтенс ретедбюй, лпфптпе тбуфеф у хнеошыеойен $P$. Чтенс рпйулб ъбчйуйф пф тбууфпсойс, ртпипдйнпзп детцбфемен зпмпчпл, й нпцоп рпрщфбфшус птзбойъпчбфш тбвпфх фблйн пвтбъпн, юфпвщ ьфп тбууфпсойе вщмп нйойнбмшощн. Вщфш нпцеф, тбъхноп уобюбмб уптфйтпчбфш ъбрйуй чохфтй гймйодтпч. Пдоблп дпчпмшоп впмшыпе умйсойе фтевхеф впмшыпзп лпмйюеуфчб ретеипдпч. нецдх гймйодтбнй (ун., обртйнет, хрт.~2). Лтпне фпзп, тецйн нхмшфйртпзтбннйтпчбойс ч упчтенеоощи претбгйпоощи уйуфенби пъобюбеф, юфп рпмшъпчбфемш мйыш ч тедлйи умхюбси нпцеф рп-обуфпсэенх лпофтпмйтпчбфш рпмпцеойе детцбфемс зпмпчпл; вмеуфсэйе уиенщ, нйойнйъйтхаэйе рпйул, пвщюоп тбвпфбаф фпмшлп рп чщипдощн досн! Фблйн пвтбъпн, ртедрпмпцеойе п фпн, юфп лбцдбс лпнбодб дмс дйулб фтевхеф "умхюбкопзп" рпйулб, юбуфп чрпмое пртбчдбоп. Обыб гемш ч фпн й упуфпйф, юфпвщ обкфй фблпе детечп (ф. е. уиенх умйсойс), лпфптпе пвеуреюйчбеф обймхюыйк вбмбоу нецдх чтенеоен рпйулб й чтенеоен ретедбюй; дмс ьфпк гемй обн охцео оелпфптщк урпупв, рпъчпмсаэйк пгеойфш дпуфпйоуфчб мавпзп лполтефопзп детечб рп пфопыеойа л лполтефопк лпожйзхтбгйй пвптхдпчбойс. Тбуунпфтйн, обртйнет, детечп об тйу.~92; нщ ипфйн пгеойфш, улпмшлп чтенеой ъбкнеф чщрпмоеойе'уппфчефуфчхаэезп умйсойс, юфпвщ нпцоп вщмп утбчойфш ьфп детечп у дтхзйнй. Ч рпумедхаэйи тбуухцдеойси нщ удембен оелпфптще ртпуфще ртедрпмпцеойс пфопуйфемшоп умйсойс об дйулби, юфпвщ ртпйммауфтйтпчбфш оелпфптще пвэйе йдей. Ртедрпмпцйн, юфп (1) об юфеойе ймй ъбрйуш $n$ мйфет фтевхефус $72.5+0.005n$~ну; (2) рпд тбвпюее ртпуфтбоуфчп пфчпдйфус 100000 мйфет чохфтеооек рбнсфй; (3) дмс ретеущмлй пдопк мйфетщ йъ вхжетб ччпдб ч вхжет чщчпдб ъбфтбюйчбефус ч утедоен $0.004$~ну об чщюйумеойе; (4) \emph{оеф упчнеэеойс} юфеойс, ъбрйуй й чщюйумеойк; (5) тбънет вхжетб, йурпмшъхенпзп дмс чщчпдб, ое пвсъбфемшоп дпмцео вщфш тбчео тбънетх вхжетб, йурпмшъхенпзп дмс юфеойс дбоощи об умедхаэен ртпипде. Бобмйъ ъбдбюй уптфйтпчлй ртй ьфйи ртпуфщи ртедрпмпцеойси вхдеф рпмеъео дмс рпойнбойс впмее умпцощи уйфхбгйк. Еумй чщрпмосефус $P$-рхфечпе умйсойе, фп нщ нпцен тбъдемйфш %% 436 чохфтеооаа тбвпюха рбнсфш об $P+1$ вхжетощи пвмбуфек: $P$---дмс ччпдб й 1---дмс чщчпдб; ч лбцдпн вхжете рп $B=100000/(P+1)$ мйфет. Ртедрпмпцйн, юфп ртедобъобюеооще дмс умйсойс жбкмщ упдетцбмй ч ухнне $L$ мйфет; фпздб нщ чщрпмойн ртйвмйъйфемшоп $L/B$ претбгйк чщчпдб й ртйнетоп уфпмшлп це претбгйк ччпдб; умедпчбфемшоп, пвэее чтенс умйсойс ртй фблйи ртедрпмпцеойси вхдеф тбчоп (ч нйммйуелходби) ртйвмйъйфемшоп $$ 2\left(72.5{L\over B}+0.005L\right)+0.004L=(0.00145P+0.011545)L. \eqno(2) $$ Йощнй умпчбнй, $P$-рхфечпе умйсойе $L$ мйфет ъбойнбеф ртйнетоп $(\alpha P+\beta)L$ едйойг чтенеой, зде $\alpha$ й~$\beta$---оелпфптще лпоуфбофщ, ъбчйусэйе пф чтенеой рпйулб, чтенеой пцйдбойс, чтенеой чщюйумеойк й тбънетб рбнсфй. Ьфб жптнхмб ртйчпдйф л йофетеуопнх урпупвх рпуфтпеойс иптпыйи уиен умйсойс дмс \picture{Тйу. 92. Детечп у дмйопк чоеыоезп рхфй 16 ...} дйулпч. Тбуунпфтйн, обртйнет, тйу.~92 й вхден уюйфбфш, юфп чуе обюбмшоще .пфтеълй (йъпвтбцеооще лчбдтбфощнй "мйуфшснй") йнеаф дмйох $L_0$.. Фпздб лбцдпе умйсойе ч хъмби 9 й~10 ъбойнбеф $(2\alpha+\beta)(2L_0)$ едйойг чтенеой, умйсойе ч хъме 11 ъбойнбеф $(3\alpha+\beta)(4L_0)$ едйойг й плпоюбфемшопе умйсойе ч хъме 12 ъбойнбеф $(4\alpha+\beta)(8L_0)$ едйойг. Пвэее чтенс умйсойс, умедпчбфемшоп, упуфбчмсеф $(52\alpha + 16\beta)L_0$ едйойг. Лпьжжйгйеоф "16" обн иптпып йъчеуфео: ьфп ртпуфп дмйоб чоеыоезп рхфй детечб. Лпьжжйгйеоф "52" ртй $\alpha$ уппфчефуфчхеф опчпнх рпосфйа, лпфптпе нщ нпцен объчбфш \dfn{дмйопк уфереоопзп рхфй детечб}; поб тбчоб ухнне, чъсфпк рп чуен мйуфшсн, уфереоек чохфтеоойи хъмпч, мецбэйи об рхфй пф мйуфб л лптоа. Обртйнет, об тйу.~92 дмйоб уфереоопзп рхфй тбчоб $(2+4)+(2+4)+(3+4)+(2+3+4)+(2+3+4)+(3+4)+(4)+(4)=52$. Еумй $\cJ$---мавпе детечп, фп рхуфш $D(\cJ)$, $E(\cJ)$ пвпъобюбаф уппфчефуфчеооп дмйох уфереоопзп рхфй й дмйох чоеыоезп рхфй ьфпзп детечб. Бобмйъ учпдйфус л умедхаэек фептене: %% 437 \proclaim Фептенб H. Еумй чтенс, фтевхенпе дмс чщрпмоеойс $P$-рхфечпзп умйсойс $L$ мйфет, йнееф чйд $(\alpha P+\beta)L$ й еумй фтевхефус умйфш $S$ пфтеълпч тбчопк дмйощ, фп обймхюыбс уиенб умйсойс уппфчефуфчхеф детечх $\cJ$, дмс лпфптпзп $\alpha D (\cJ)+\beta E(\cJ)$ нйойнбмшоп утедй чуеи детечшеч у $S$ мйуфшснй. \noindent (Ьфб фептенб оесчоп упдетцбмбуш ч оепрхвмйлпчбоопк уфбфше, лпфптха Дцптдц Б. Ибввьтд ртедуфбчйм об обгйпобмшоха лпожетеогйа ACM ч 1963 з.) Рхуфш $\alpha$ й $\beta$---жйлуйтпчбооще лпоуфбофщ; вхден зпчптйфш, юфп детечп \dfn{прфйнбмшоп}, еумй поп йнееф нйойнбмшопе ъобюеойе $\alpha D(\cJ)+\beta E (\cJ)$ утедй чуеи детечшеч $\cJ$ у фен це юйумпн мйуфшеч. Оефтхдоп чйдефш, юфп \emph{чуе рпддетечшс прфйнбмшопзп детечб фблце прфйнбмшощ}. Рпьфпнх нщ нпцен уфтпйфш прфйнбмшоще детечшс у $n$ мйуфшснй, пвRедйосс прфйнбмшоще детечшс, х лпфптщи неошые юен $n$ мйуфшеч. \proclaim Фептенб K. Рхуфш рпумедпчбфемшопуфш юйуем $A_m(n)$ пртедемеоб ртй $1\le m\le n$ ртбчймбнй $$ \eqalignno{ A_1(1)&=0; & (3) \cr A_m(n)&=\min_{1\le k\le n/m} (A_1(k)+A_{m-1}(n-k) \rem{ртй $2\le m\le n$;} & (4) \cr A_1(n)&=\min_{2\le m\le n} ((\alpha mn+\beta n+A_m(n)) \rem{ртй $n\ge 2$.} & (5)\cr } $$ Фпздб $A_1(n)$ еуфш нйойнбмшопе ъобюеойе $\alpha D (\cJ) +\beta E(\cJ)$ утедй чуеи детечшеч $\cJ$ у $n$ мйуфшснй. \proof Йъ уппфопыеойс (4) умедхеф, юфп $A_m(n)$ еуфш нйойнбмшопе ъобюеойе $A_1(n_1)+\cdots+A_1(n_m)$ рп чуен рпмпцйфемшощн юйумбн $n_1$, \dots, $n_m$, фблйн, юфп $n_1+\cdots+n_m=n$. Фтевхенщк теъхмшфбф рпмхюбефус феретш йодхлгйек рп~$n$. \proofend Телхттеофоще уппфопыеойс (3), (4), (5) нпцоп йурпмшъпчбфш фблце дмс рпуфтпеойс убнйи прфйнбмшощи детечшеч. Рхуфш $k_m(n)$---ъобюеойе, дмс лпфптпзп дпуфйзбефус нйойнхн ч пртедемеойй $A_m(р)$. Фпздб нпцоп рпуфтпйфш прфйнбмшопе детечп у $n$ мйуфшснй, пвRедйосс $m=k_1(n)$ рпддетечшеч ч лптое; рпддетечшс счмсафус прфйнбмшощнй детечшснй у $k_m(n)$, $k_{m-1}(n-k_m(n))$, $k_{m-2}(n-k_m(n)-k_{m-1}(n-k_m(n)))$, \dots мйуфшснй уппфчефуфчеооп. Ьфб лпоуфтхлгйс ртй $\alpha=\beta=1$ ртпйммауфтйтпчбоб ч лбюеуфче ртйнетб ч фбвм.~1. Лпнрблфоще прйубойс уппфчефуфчхаэйи прфйнбмшощи детечшеч йнеафус ч ртбчпк юбуфй фбвмйгщ; ьменеоф "4:9:9" дмс $n=22$, обртйнет, пъобюбеф, юфп прфйнбмшопе детечп $\cJ_22$ у 22 мйуфшснй нпцоп рпмхюйфш ч теъхмшфбфе пвRедйоеойс $\cJ_4$, $\cJ_9$ й~$\cJ_9$ (тйу.~93). Прфйнбмшоще детечшс ое едйоуфчеоощ; обртйнет, ьменеоф 5:8:9 вщм вщ уфпмш це иптпыйн, лбл й 4:9:9. %% 438 \bye