\input style \chapno=6\subchno=3\chapnotrue %%601 \subchap{ÈÅÛÉÒÏ×ÁÎÉÅ} % 6.4 Äï óéè ðïò íù òáóóíáôòé÷áìé íåôïäù ðïéóëá, ïóîï÷áîîùå îá óòá÷îåîéé äáîîïçï áòçõíåîôá~$K$ ó éíåàýéíéóñ ÷ ôáâìéãå ëìàþáíé éìé îá éóðïìøúï÷áîéé åçï ãéæò äìñ õðòá÷ìåîéñ ðòïãåóóïí òáú÷åô÷ìåîéñ. Îï åóôø é ôòåôéê ðõôø: îå òùóëáôø ÷ïëòõç äá ïëïìï, á ðòïéú÷åóôé îáä~$K$ îåëïôïòïå áòéæíåôéþåóëïå ÷ùþéóìåîéå é ðïìõþéôø æõîëãéà~$f(K)$, õëáúù÷áàýõà áäòåó ÷ ôáâìéãå, çäå èòáîéôóñ~$K$ é áóóïãééòï÷áîîáñ ó îéí éîæïòíáãéñ. Îáðòéíåò, òáóóíïôòéí ÷îï÷ø íîïöåóô÷ï éú 31~áîçìéêóëïçï óìï÷á, ëïôïòïå íù ðïä÷åòçáìé ÷ïúäåêóô÷éà òáúìéþîùè óôòáôåçéé ðïéóëá ÷ ð.~6.2.2 é \S~6.3. Ôáâìéãá~1 óïäåòöéô ëïòïôëõà ðòïçòáííõ äìñ \MIX, ðòåïâòáúõàýõà ëáöäùê éú 31~ëìàþá ÷ õîéëáìøîïå þéóìï~$f(K)$ íåöäõ~$-10$ é~$30$. Åóìé íù óòá÷îéí üôïô íåôïä ó \MIX-ðòïçòáííáíé äìñ õöå éúõþåîîùè îáíé íåôïäï÷ (îáðòéíåò, ó âéîáòîùí ðïéóëïí, ïðôéíáìøîùí ðïéóëïí ðï äåòå÷õ, âïòï÷ïê ðáíñôøà, ãéæòï÷ùí ðïéóëïí ðï äåòå÷õ), ôï õ÷éäéí, þôï ïî ìõþûå ëáë ó ôïþëé úòåîéñ ðòïóôòáîóô÷á, ôáë é ó ôïþëé úòåîéñ óëïòïóôé; ôïìøëï âéîáòîùê ðïéóë éóðïìøúõåô îåóëïìøëï íåîøûå ðòïóôòáîóô÷á. × óáíïí äåìå, ðòé éóðïìøúï÷áîéé ðòïçòáííù éú ôáâì.~1 óòåäîåå ÷òåíñ ðïéóëá óïóôá÷ìñåô ìéûø ïëïìï~$17.8u$ (äáîîùå ï þáóôïôå ÷úñôù éú òéó.~12), é äìñ èòáîåîéñ 31~ëìàþá ôòåâõåôóñ ôáâìéãá ÷óåçï äìñ 41~üìåíåîôá. Ë óïöáìåîéà, îáèïäéôø ðïäïâîùå æõîëãéé~$f(K)$ äï÷ïìøîï óìïöîï. Óõýåóô÷õåô $41^{31}\approx10^{50}$~òáúìéþîùè ïôïâòáöåîéê íîïöåóô÷á éú 31~üìåíåîôá ÷ íîïöåóô÷ï éú 41~üìåíåîôá, é ôïìøëï $41\cdot40\cdot\ldots\cdot11=41!/10!\approx10^{43}$ éú îéè äáàô òáúìéþîùå úîáþåîéñ äìñ ëáöäïçï áòçõíåîôá; ôáëéí ïâòáúïí, ìéûø ïäîá éú ëáöäùè 10~íéììéïîï÷ æõîëãéê ïëáúù÷áåôóñ ðïäèïäñýåê. Æõîëãéé, äáàýéå îåðï÷ôïòñàýéåóñ úîáþåîéñ, îåïöéäáîîï òåäëé äáöå ÷ óìõþáå äï÷ïìøîï âïìøûïê ôáâìéãù. Îáðòéíåò, úîáíåîéôùê ðáòáäïëó äîåê òïöäåîéñ õô÷åòöäáåô, þôï, åóìé ÷ ëïíîáôå ðòéóõôóô÷õåô îå íåîåå 23~þåìï÷åë, éíååôóñ èïòïûéê ûáîó îá ôï, þôï õ ä÷õè éú îéè óï÷ðáäåô äåîø òïöäåîéñ! Éîùíé óìï÷áíé, åóìé íù ÷ùâéòáåí óìõþáêîõà æõîëãéà, ïôïâòáöáàýõà 23~ëìàþá ÷ 365-üìåíåîôîõà ôáâìéãõ, ôï ó ÷åòïñôîïóôøà~$0.4927$ (íåîåå ðïìï÷éîù) ÷óå ëìàþé ðïðáäõô ÷ òáúîùå íåóôá. Óëåðôéëé, óïíîå÷áàýéåóñ ÷ üôïí, íïçõô ðïðùôáôøóñ îáêôé óï÷ðáäåîéå äîåê òïöäåîéñ îá âìéöáêûåê âïìøûïê ÷åþåòéîëå. [Ðáòáäïëó äîåê òïöäåîéñ ÷ðåò÷ùå õðïíñîõô ÷ òáâïôáè æïî~Íéúåóá ({\sl Istanbul %%602 \"Universitesi Fen Fak\"ultesi Mecmuasi,\/} {\bf 4} (1939), 145--163) é~Õ.~Æåììåòá (×÷åäåîéå ÷ ôåïòéà ÷åòïñôîïóôåê é åå ðòéìïöåîéñ, Í., "Íéò", 1964, çì.~2, \S~3).] Ó äòõçïê óôïòïîù, ðïäèïä, éóðïìøúï÷áîîùê ÷ ôáâì.~1, äï÷ïìøîï çéâëéê [óò.~ó~Í.~Çòåîå÷óëé é~×.~Ôõòóëé, {\sl CACM,\/} {\bf 6} (1963), 322--323], é äìñ ôáâìéãù óòåäîåçï òáúíåòá ðïäèïäñýõà æõîëãéà íïöîï îáêôé ðòéíåòîï úá äåîø. × óáíïí äåìå, ïþåîø úáîñôîï òåûáôø ðïäïâîùå çïìï÷ïìïíëé. Òáúõíååôóñ, ôáëïê íåôïä éíååô óõýåóô÷åîîùê îåäïóôáôïë, éâï óïäåòöéíïå ôáâìéãù äïìöîï âùôø éú÷åóôîï úáòáîåå; äïâá÷ìåîéå èïôñ âù ïäîïçï ëìàþá íïöåô ÷óå éóðïòôéôø, é îáí ðòéäåôóñ îáþéîáôø æáëôéþåóëé îá ðõóôïí íåóôå. Íïöîï ðïìõþéôø çïòáúäï âïìåå çéâëéê íåôïä, åóìé ïôâòïóéôø éäåà ïäîïúîáþîïóôé, äïðõóëáñ óï÷ðáäåîéñ úîáþåîéê~$f(K)$ äìñ òáúìéþîùè áòçõíåîôï÷, é éóðïìøúï÷áôø ïóïâùê íåôïä òáúòåûåîéñ îåïðòåäåìåîîïóôé ðïóìå ÷ùþéóìåîéñ~$f(K)$. Îáûé òáóóíïôòåîéñ ðòé÷ïäñô ë ûéòïëï éú÷åóôîïíõ ëìáóóõ íåôïäï÷, ïâùþîï îáúù÷áåíùè \dfn{èåûéòï÷áîéåí} éìé \dfn{òáóóåñîîïê ðáíñôøà.} Áîçìéêóëéê çìáçïì "to hash" éíååô óíùóì îáòåúáôø, òáóëòïûéôø þôï-ìéâï éìé óäåìáôø éú üôïçï íåóé÷ï; éäåñ èåûéòï÷áîéñ óïóôïéô ÷ ôïí, þôïâù ÷úñôø îåëïôïòùå èáòáëôåòéóôéëé ëìàþá é éóðïìøúï÷áôø ðïìõþåîîõà þáóôéþîõà éîæïòíáãéà ÷ ëáþåóô÷å ïóîï÷ù ðïéóëá. Íù ÷ùþéóìñåí \dfn{èåû-æõîëãéà $h(K)$} é âåòåí üôï úîáþåîéå ÷ ëáþåóô÷å áäòåóá îáþáìá ðïéóëá. Ðáòáäïëó äîåê òïöäåîéñ óìõöéô äìñ îáó ðòåäïóôåòåöåîéåí, þôï, ÷åòïñôîï, îáêäõôóñ òáúìéþîùå ëìàþé~$K_i\ne K_j$, äìñ ëïôïòùè %%603 $h(K_i)=h(K_j)$. Ðïäïâîïå óïâùôéå îáúù÷áåôóñ \dfn{ëïììéúéåê;} äìñ òáúòåûåîéñ ëïììéúéê âùìé òáúòáâïôáîù éîôåòåóîùå ðïäèïäù. Þôïâù éóðïìøúï÷áôø òáóóåñîîõà ôáâìéãõ, ðòïçòáííéóô äïìöåî ðòéîñôø ä÷á ðïþôé îåúá÷éóéíùè òåûåîéñ: ïî äïìöåî ÷ùâòáôø èåû-æõîëãéà~$h(K)$ é íåôïä òáúòåûåîéñ ëïììéúéê. Üôé ä÷á áóðåëôá úáäáþé ðïéóëá íù é òáóóíïôòéí ðï ïþåòåäé. \section Èåû-æõîëãéé. Äìñ ïðòåäåìåîîïóôé îá ðòïôñöåîéé üôïçï ðõîëôá âõäåô ðòåäðïìáçáôøóñ, þôï èåû-æõîëãéñ~$h$ éíååô îå âïìåå $M$~òáúìéþîùè úîáþåîéê é þôï üôé úîáþåîéñ õäï÷ìåô÷ïòñàô õóìï÷éà $$ 0\le h(K)M$, ôáë þôï ðåòåðïìîåîéå îå ðòåäóôá÷ìñåô óåòøåúîïê ðòïâìåíù. Åóìé éóðïìøúõàôóñ òáúäåìøîùå óðéóëé, æïòíõìù~(18) é~(19) óðòá÷åäìé÷ù äìñ~$\alpha>1$. Ëïçäá öå óðéóëé óòáóôáàôóñ, ëáë ÷ áìçïòéôíå~C, íïöîï ðïíåýáôø ðåòåðïìîñàýéå üìåíåîôù ÷ï ÷óðïíïçáôåìøîùê ðõì ðáíñôé. Ëáë äïëáúáì Ì.~Çàéâá, ÷ üôïí óìõþáå óòåäîåå þéóìï ðòïâ ðòé ÷óôá÷ëå $(M+L+1)\hbox{-çï}$~üìåíåîôá óïóôá÷ìñåô~$\left(L/2M+{1\over4}\right)((1+2/M)^M-1)+{1\over2}$. \section Òáúòåûåîéå ëïììéúéê "ïôëòùôïê áäòåóáãéåê". Äòõçïê óðïóïâ òåûåîéñ ðòïâìåíù ëïììéúéê óïóôïéô ÷ ôïí, þôïâù ðïìîïóôøà ïôëáúáôøóñ ïô óóùìïë é ðòïóôï ðòïóíáôòé÷áôø ïäéî úá äòõçéí òáúìéþîùå üìåíåîôù ôáâìéãù, ðïëá îå âõäõô îáêäåîù ëìàþ~$K$ éìé ó÷ïâïäîáñ ðïúéãéñ. Îå ðìïèï âùìï âù éíåôø ðòá÷éìï, óïçìáóîï ëïôïòïíõ ëáöäùê ëìàþ~$K$ ïðòåäåìñåô ðïóìåäï÷áôåìøîïóôø %%616 ðòïâ, ô.~å.~ðïóìåäï÷áôåìøîïóôø ðïúéãéê ÷ ôáâìéãå, ëïôïòùå îõöîï ðòïóíáôòé÷áôø ÷óñëéê òáú ðòé ÷óôá÷ëå éìé ðïéóëå~$K$. Åóìé íù, éóðïìøúõñ ïðòåäåìñåíõà~$K$ ðïóìåäï÷áôåìøîïóôø ðòïâ, îáôïìëîåíóñ îá ó÷ïâïäîõà ðïúéãéà, ôï íïöîï óäåìáôø ÷ù÷ïä, þôï $K$~îåô ÷ ôáâìéãå, ôáë ëáë ôá öå ðïóìåäï÷áôåìøîïóôø ðòïâ ÷ùðïìîñåôóñ ëáöäùê òáú ðòé ïâòáâïôëå äáîîïçï ëìàþá. Üôïô ïâýéê ëìáóó íåôïäï÷ Õ.~Ðåôåòóïî îáú÷áì \dfn{ïôëòùôïê áäòåóáãéåê} [{\sl IBM J.~Research \& Development,\/} {\bf 1} (1957), 130--146]. Ðòïóôåêûáñ óèåíá ïôëòùôïê áäòåóáãéé, éú÷åóôîáñ ëáë \dfn{ìéîåêîïå ïðòïâï÷áîéå,} éóðïìøúõåô ãéëìéþåóëõà ðïóìåäï÷áôåìøîïóôø $$ h(K), h(K)-1, \ldots, 0, M-1, M-2, \ldots, h(K)+1 \eqno(20) $$ é ïðéóù÷áåôóñ óìåäõàýéí ïâòáúïí. \alg L.(Ðïéóë ó ÷óôá÷ëïê ðï ïôëòùôïê òáóóåñîîïê ôáâìéãå.) Áìçïòéôí ðïú÷ïìñåô òáúùóëáôø äáîîùê ëìàþ~$K$ ÷ ôáâìéãå éú $M$~õúìï÷. Åóìé $K$~îåô ÷ ôáâìéãå é ïîá îå ðïìîá, ëìàþ~$K$ ÷óôá÷ìñåôóñ. Õúìù ôáâìéãù ïâïúîáþáàôóñ þåòåú~$|TABLE|[i]$, $0\le i0$.\cr } \eqno(25) $$ Üôïô íåôïä âùóôòåå ðï÷ôïòîïçï äåìåîéñ, îï ïî ÷óå öå ðòé÷ïäéô ë \emph{÷ôïòéþîïíõ ïëõþé÷áîéà,} ôòåâõñ îåóëïìøëï âïìøûå ðòïâ éú-úá õ÷åìéþåîéñ ÷åòïñôîïóôé ôïçï, þôï ä÷á éìé âïìåå ëìàþåê ðïóìåäõàô ïäîéí é ôåí öå ðõôåí. Æïòíõìù, ÷ù÷åäåîîùå îéöå, íïöîï éóðïìøúï÷áôø, þôïâù ïðòåäåìéôø, ðåòå÷åûé÷áåô ìé ÷ùéçòùû ÷ï ÷òåíåîé èåûéòï÷áîéñ ðïôåòé îá ðòïâáè. %% 621 Áìçïòéôíù~L é~D ïþåîø ðïèïöé, îï éíåàô é äïóôáôïþîï òáúìéþéê, ðïüôïíõ ðïìåúîï óòá÷îéôø ÷òåíåîá òáâïôù óïïô÷åôóô÷õàýéè ðòïçòáíí äìñ~\MIX. \prog D.(Ïôëòùôáñ áäòåóáãéñ ó ä÷ïêîùí èåûéòï÷áîéåí.) Ôáë ëáë üôá ðòïçòáííá ÷åóøíá îáðïíéîáåô ðòïçòáííõ~L, ïîá ðòé÷ïäéôóñ âåú ëïííåîôáòéå÷. Úäåóø~$|rI2|\equiv c-1$. \code START&LDX &K &1 &ENTA&0 &1 &DIV &=M= &1 &STX &*+1(0:2) &1 &ENT1&* &1 &LDX &TABLE,1 &1 &ÓÍÒÈ&K &1 &JE &SUCCESS &1 &JXZ &4F &1-S1 &SRAX&5 &A-S1 &DIV &=M-2= &A-S1 &STX &*+1(0:2) &A-S1 &ENT2&* &A-S1 &LDA &K &A-S1 3H &DEC1&1,2 &C-1 &J1NN&*+2 &C-1 &INC1&M &B &CMPA&TABLE,1 &C-1 &JE &SUCCESS &C-1 &LDX &TABLE,1 &C-1-S2 &JXNZ&3B &C-1-S2 4H &LDX &VACANCIES&1-S &JXZ &OVERFLOW &1-S &DECX&1 &1-S &STX &VACANCIES&1-S &LDA &K &1-S &STA &TABLE,1 &1-S \endcode \progend Óþåôþéëé þáóôïô~$A$, $C$, $S1$, $S2$ éíåàô ôïô öå óíùóì, þôï é ÷ ðòïçòáííå~C. Óòåäîåå úîáþåîéå ðåòåíåîîïê~$B$ ðòéíåòîï òá÷îï~$(C-1)/2$. (Åóìé óõúéôø äéáðáúïî~$h_2(K)$, óëáöåí, äï~$1\le h_2(K)\le {1\over2} M$, úîáþåîéå~$B$ óïóôá÷éìï âù ìéûø~$(C-1)/4$, ÷åòïñôîï, õ÷åìéþåîéå þéóìá ðòïâ îå ó÷åäåô îá îåô üôï õ÷åìéþåîéå óëïòïóôé.) Åóìé ÷ ôáâìéãå $N=\alpha M$~ëìàþåê, óòåäîåå úîáþåîéå~$A$, òáúõíååôóñ, òá÷îï~$\alpha$ äìñ îåõäáþîïçï ðïéóëá é~1 äìñ õäáþîïçï. Ëáë é ÷ áìçïòéôíå~C, óòåäîåå úîáþåîéå~$S1$ äìñ îåõäáþîïçï ðïéóëá óïóôá÷ìñåô~$1-{1\over2}((N-1)/M)\approx 1-{1\over2}\alpha$. Ôòõäîï ôïþîï ïðòåäåìéôø óòåäîåå þéóìï ðòïâ, ïäîáëï üíðéòéþåóëéå ðòï÷åòëé ðïëáúù÷áàô èïòïûåå óïçìáóéå ó ÷ù÷åäåîîùíé îéöå æïòíõìáíé äìñ "òá÷îïíåòîïçï ïðòïâï÷áîéñ": $$ \eqalignno{ C'_N&={M+1\over M+1-N}\approx(1-\alpha)^{-1} \rem{(îåõäáþîùê ðïéóë)};&(26)\cr C_N&={M+1\over N}(H_{M+1}-H_{M+1-N}) \approx-\alpha^{-1}\ln (1-\alpha) \rem{(õäáþîùê ðïéóë)},&(27)\cr } $$ åóìé~$h_1(K)$ é~$h_2(K)$ îåúá÷éóéíù. Ëïçäá öå $h_2(K)$~úá÷éóéô ïô~$h_1(K)$, ëáë ÷~(25), ÷ôïòéþîïå ïëõþé÷áîéå ÷ùúù÷áåô õ÷åìéþåîéå óòåäîéè %%622 úîáþåîéê äï $$ \eqalignno{ C'_N &={M+1\over M+1-N}-{N\over M+1}+H_{M+1}-H_{M+1-N}+O(M)^{-1}\approx\cr &\approx(1-\alpha)^{-1}-\alpha-\ln(1-\alpha);&(28)\cr C_N&=1+H_{M+1}-H_{M+1-N}-{N\over 2(M+1)} -(H_{M+1}-H_{M+1-N})/N+O(N^{-1})\approx\cr &\approx 1-\ln(1-\alpha)-{1\over2}\alpha. &(29) \cr } $$ (Óí.~õðò.~44.) Úáíåôéí, þôï, ëïçäá ôáâìéãá úáðïìîñåôóñ, ô.~å.~ëïçäá $N $~óôòåíéôóñ ë~$M$, úîáþåîéå~$C_N$ ðòéâìéöáåôóñ ë~$H_{M+1}-1$, á~$C'_N$---ë~$H_{M+1}-{1\over2}$; üôï íîïçï ìõþûå, þåí ÷ óìõþáå áìçïòéôíá~L, îï îå óôïìø èïòïûï, ëáë ÷ íåôïäáè ãåðïþåë. Ðïóëïìøëõ ÷ áìçïòéôíå~L ðòïâù úáîéíáàô îåóëïìøëï íåîøûå ÷òåíåîé, ä÷ïêîïå èåûéòï÷áîéå ðòåäðïþôéôåìøîï ìéûø ðòé úáðïìîåîîïê ôáâìéãå. Îá òéó.~42 óòá÷îé÷áàôóñ óòåäîéå ÷òåíåîá òáâïôù ðòïçòáíí~L, D é íïäéæéãéòï÷áîîïê ðòïçòáííù~D (ðòéþåí üôá íïäéæéëáãéñ ÷ìåþåô úá óïâïê ÷ôïòéþîïå óëõþé÷áîéå): íù úáíåîñåí äï÷ïìøîï íåäìåîîïå ÷ùþéóìåîéå~$h_2(K)$ ÷ óôòïëáè~10--13 îá ôòé ëïíáîäù $$ \mixcode ENN2 & -M-1, 1 & $c\asg M-i$. J1NZ & *+2 ENT2 & 0 & Åóìé $i=0$, $c\asg 1$. \endmixcode \eqno(30) $$ \picture{Òéó. 42. ×òåíñ õäáþîïçï ðïéóëá äìñ ôòåè óèåí ïôëòùôïê áäòåóáãéé.} %%623 × äáîîïí óìõþáå ÷ôïòéþîïå óëõþé÷áîéå ìõþûå îåúá÷éóéíïçï ðï÷ôïòîïçï èåûéòï÷áîéñ. Îá ä÷ïéþîïê Ü×Í íù íïçìé âù éîùí óðïóïâïí õóëïòéôø ÷ùþéóìåîéå~$h_2(K)$, úáíåîé÷ óôòïëé~10--13, óëáöåí, îá $$ \mixcode AND & =511= & $|rA|\asg |rA| \bmod 512$. STA & *+1(0:2) ENT2 & * & $c\asg |rA|+1$. \endmixcode \eqno(31) $$ åóìé $M$---ðòïóôïå þéóìï, âïìøûåå~512. Üôá éäåñ, ðòåäìïöåîîáñ Âåììïí é Ëáí\'á [{\sl CACM,\/} {\bf 13} (1970), 675--677], îåúá÷éóéíï ðòéäõíá÷ûéíé áìçïòéôí~D, ðïú÷ïìñåô éúâåöáôø ÷ôïòéþîïçï óëõþé÷áîéñ âåú úáôòáô îá ðï÷ôïòîïå äåìåîéå. Âùìï ðòåäìïöåîï íîïçï äòõçéè ðïóìåäï÷áôåìøîïóôåê ðòïâ ÷ ëáþåóô÷å õìõþûåîéê áìçïòéôíá~L, îï, ðï-÷éäéíïíõ, îé ïäîá éú îéè îå ìõþûå áìçïòéôíá~D. (Âùôø íïöåô, éóëìàþåîéå óïóôá÷ìñåô íåôïä, ïðéóáîîùê ÷ õðò.~20.) \picture{ Òéó. 43. Óëïìøëï òáú ëïíðéìñôïò éýåô éíåîá ðåòåíåîîùè ÷ ôéðéþîïí óìõþáå. Éíåîá ÷ùðéóáîù óìå÷á îáðòá÷ï ÷ ðïòñäëå éè ðåò÷ïçï ðïñ÷ìåîéñ.} \section Éúíåîåîéå, ðòåäìïöåîîïå Âòåîôïí. Òéþáòä Âòåîô îáûåì ôáëïê óðïóïâ éúíåîåîéñ áìçïòéôíá~D, þôïâù óòåäîåå ÷òåíñ õäáþîïçï ðïéóëá ïóôá÷áìïóø ïçòáîéþåîîùí ðï íåòå úáðïìîåîéñ ôáâìéãù. Åçï íåôïä ïóîï÷áî îá ôïí æáëôå, þôï ÷ï íîïçéè ðòéìïöåîéñè %%624 õäáþîùê ðïéóë ðòïéú÷ïäéôóñ çïòáúäï þáýå ÷óôá÷ïë; ðïüôïíõ ïî ðòåäìáçáåô äåìáôø âïìøûå òáâïôù ðòé ÷óôá÷ëå üìåíåîôá, nepeíåýáñ úáðéóé, þôïâù õíåîøûéôø ïöéäáåíïå ÷òåíñ ÷ùâïòëé. [{\sl CACM,\/} {\bf 16} (1973), 105--109.] Îáðòéíåò, îá òéó.~43 ðïëáúáîï, óëïìøëï òáú ôïô éìé éîïê éäåîôéæéëáôïò ÷óôòåþáìóñ ÷ ôéðéþîïê ðòïãåäõòå îá~PL/1. Óõäñ ðï üôéí äáîîùí, ëïíðéìñôïò ó~PL/1, éóðïìøúõàýéê òáóóåñîîõà ôáâìéãõ äìñ èòáîåîéñ éíåî ðåòåíåîîùè, âõäåô éóëáôø íîïçéå éíåîá ðñôø éìé âïìåå òáú, á ÷óôá÷ìñôø éè ìéûø ïäîáöäù. Áîáìïçéþîï Âåìì é~Ëáí\'á ïâîáòõöéìé, þôï ëïíðéìñôïò ó~Ëïâïìá éóðïìøúï÷áì ó÷ïê áìçïòéôí ôáâìéã óéí÷ïìï÷ $10988$~òáú ÷ï ÷òåíñ ëïíðéìñãéé ðòïçòáííù é óï÷åòûéì ìéûø $735$~÷óôá÷ïë, ô.~å.~îá ïäéî îåõäáþîùê ðïéóë ðòéèïäéìïóø ðòéíåòîï 14~õäáþîùè. Éîïçäá ôáâìéãá óïúäáåôóñ ôïìøëï ïäéî òáú (îáðòéíåò, ôáâìéãá óéí÷ïìéþåóëéè ëïäï÷ ïðåòáãéê ÷ á÷ôïëïäå) é éóðïìøúõåôóñ ðïóìå üôïçï éóëìàþéôåìøîï äìñ ÷ùâïòëé. Âòåîô ðòåäìïöéì óìåäõàýéí ïâòáúïí éúíåîéôø ðòïãåóó ÷óôá÷ëé ÷ áìçïòéôíå~D. Ðòåäðïìïöéí, þôï ðòé îåõäáþîïí ðïéóëå âùìé ïðòïâï÷áîù ñþåêëé $$ p_0, p_1,~\ldots, p_{t-1}, p_t, $$ çäå~$p_j=(h_1(K)-jh_2(K))\bmod M$ é õúåì~$|TABLE|[p_t]$ ðõóô. Åóìé~$t\le 1$, íù, ëáë ïâùþîï, ÷óôá÷ìñåí~$K$ ÷ ðïúéãéà~$p_t$, îï åóìé~$t\ge2$, ÷ùþéóìñåí~$c_0=h_2(K_0)$, çäå~$K_0=|KEY|[p_0]$, é óíïôòéí, ó÷ïâïäîï ìé ÷~$|TABLE| [(p_0-c_0)\bmod M$]. Åóìé õóìï÷éå ÷ùðïìîåîï, ðïíåýáåí ÷ äáîîùê õúåì óïäåòöéíïå ñþåêëé~$|TABLE|[p_0]$ é ÷óôá÷ìñåí~$K$ ÷ ðïúéãéà~$p_0$. Üôï õ÷åìéþé÷áåô ÷òåíñ ÷ùâïòëé $K_0$ îá ïäéî ûáç, îï õíåîøûáåô ÷òåíñ ÷ùâïòëé~$K$ îá $t\ge2$~ûáçï÷. ×ùéçòùû îáìéãï. Áîáìïçéþîï, åóìé ÷~$|TABLE|[(p_0-c_0)\bmod M]$ úáîñôï é~$t\ge3$, íù ðòïâõåí ñþåêëõ~$|TABLE| [(p_0-2c_0)\bmod M]$; åóìé é ôáí úáîñôï, ÷ùþéóìñåí~$c_1=h_2(|KEY|[p_1])$ é ðòïâõåí $|TABLE|[(p_1-c_1)\bmod M]$ é~ô.~ä. ×ïïâýå, ðõóôø~$c_j=h_2(|KEY|[p_j])$ é~$p_{j,k}=(p_j-kc_j)\bmod M$; åóìé ðïúéãéé~$|TABLE|[p_{j,k}]$ ïëáúáìéóø úáîñôùíé ðòé ÷óåè~$j, k$, ôáëéè, þôï~$j+k (M+1)/(M+1-n)$; îåìøúñ ÷óå ÷òåíñ ðïâåöäáôø òá÷îïíåòîïå èåûéòï÷áîéå. × äåêóô÷éôåìøîïóôé ÷ ëáþåóô÷å íåòù ìõþûå ðïäèïäéô îå~$C'_N$, á þéóìï ðòïâ ðòé \emph{õäáþîïí} ðïéóëå~$C_N$. Ðåòåóôáîï÷ëé~(52) îå äáàô õìõþûåîéñ~$C_N$ îé ðòé ëáëïí~$N$, é ëáöåôóñ ÷åóøíá òáúõíîùí ðòåäðïìïöéôø, þôï îéëáëïå ðòéðéóù÷áîéå ðåòåóôáîï÷ëáí ÷åòïñôîïóôåê îå íïöåô óäåìáôø~$C_N$ íåîøûå "òá÷îïíåòîïçï" úîáþåîéñ~$((M+1)/N) (H_{M+1}-H_{M+1-N})$. Ëáë ïëáúù÷áåôóñ, üôï õô÷åòöäåîéå ïþåîø ôòõäîï äïëáúáôø çìá÷îùí ïâòáúïí ðïôïíõ, þôï ðïìõþéôø üææåëô òá÷îïíåòîïçï èåûéòï÷áîéñ íïöîï íîïçéíé óðïóïâáíé; íù îå ïâñúáîù ðòéðéóù÷áôø ëáöäïê ðåòåóôáîï÷ëå ÷åòïñôîïóôø~$1/M!$. Îáðòéíåò, óìåäõàýåå òáóðòåäåìåîéå ðòé~$M=4$ üë÷é÷áìåîôîï òá÷îïíåòîïíõ èåûéòï÷áîéà: $$ \matrix{ \hbox{Ðåòåóôáîï÷ëá} & \hbox{×åòïñôîïóôø} & \hbox{Ðåòåóôáîï÷ëá} & \hbox{×åòïñôîïóôø}\cr 0\ 1\ 2\ 3 & 1/6 &0\ 2\ 1\ 3 & 1/12\cr 1\ 2\ 3\ 0 & 1/6 &1\ 3\ 2\ 0 & 1/12\cr 2\ 3\ 0\ 1 & 1/6 &2\ 0\ 3\ 1 & 1/12\cr } \eqno(53) $$ (ïóôáìøîùí 16~ðåòåóôáîï÷ëáí ðòéðéóù÷áåôóñ îõìå÷áñ ÷åòïñôîïóôø). Óìåäõàýáñ ôåïòåíá èáòáëôåòéúõåô \emph{÷óå} òáóðòåäåìåîéñ ÷åòïñôîïóôåê, ëïôïòùå äáàô ðï÷åäåîéå òá÷îïíåòîïçï èåûéòï÷áîéñ: \proclaim Ôåïòåíá~U. Ðòéðéóù÷áîéå ðåòåóôáîï÷ëáí ÷åòïñôîïóôåê óäåìáåô ÷óå $\perm{M}{N}$~ëïîæéçõòáãéê úáîñôùè é ó÷ïâïäîùè ñþååë ðïóìå N~÷óôá÷ïë òá÷îï÷åòïñôîùíé äìñ~$0{1\over2}$ îáûìéóø \emph{ôòïå,} éíåàýéå ïäéî é ôïô öå äåîø òïöäåîéñ? \ex[15] Íéóôåò Ôõðéãá ðéóáì ëïíðéìñôïò ó ÆÏÒÔÒÁÎá, éóðïìøúõñ äåóñôéþîõà íáûéîõ \MIX, é ðåòåä îéí ÷óôáìá úáäáþá óïúäáîéñ ôáâìéãù óéí÷ïìï÷ äìñ èòáîåîéñ éíåî ðåòåíåîîùè ëïíðéìéòõåíïê ðòïçòáííù. Äìéîá üôéè éíåî ïçòáîéþåîá äåóñôøà ìéôåòáíé. Ïî òåûéì éóðïìøúï÷áôø òáóóåñîîõà ôáâìéãõ ó~$M=100$ é âùóôòõà èåû-æõîëãéà~$h(K)=\hbox{ëòáêîîê ìå÷ùê âáêô~$K$}$. Èïòïûï ìé üôï? \ex[15] Òáúõíîï ìé úáíåîéôø ðåò÷ùå ä÷å éîóôòõëãéé ÷~(3) îá~|LDA K|; |ENTX 0|? \ex[×Í30] \exhead(Ðïìéîïíéáìøîïå èåûéòï÷áîéå.) Ãåìø îáóôïñýåçï õðòáöîåîéñ---òáóóíïôòåôø ðïóôòïåîéå íîïçïþìåîï÷~$P(x)$ ôéðá~(10), ëïôïòùå ðòåïâòáúõàô $n\hbox{-âéôï÷ùå}$ ëìàþé ÷ $m\hbox{-âéôï÷ùå}$ áäòåóá é ðòé üôïí òáúîùå ëìàþé, ïôìéþáàýéåóñ îå âïìåå þåí $t$~âéôáíé, ðïìõþáô òáúîùå áäòåóá. Ðï úáäáîîùí úîáþåîéñí~$n$, $t\le n$, é ãåìïíõ þéóìõ~$k$, ôáëïíõ, þôï~$n$ äåìéô~$2^k-1$, íù ðïóôòïéí íîïçïþìåî, óôåðåîø ïô ëïôïòïçï ñ÷ìñåôóñ æõîëãéåê~$n$, $t$ é~$k$. (Ïâùþîï, åóìé üôï îåïâèïäéíï, $n$~õ÷åìéþé÷áåôóñ, ðïüôïíõ $k$~íïöîï ÷ùâòáôø äïóôáôïþîï íáìùí.) Ðõóôø $S$---íéîéíáìøîïå íîïöåóô÷ï ãåìùè þéóåì, ôáëïå, þôï~$\set{1,2,~\ldots, t}\subseteq S$ é~$(2j) \bmod n \in S$ äìñ ÷óåè~$j\in S$. Îáðòéíåò, åóìé~$n=15$, $k=4$, $t=6$, éíååí~$S=\set{1, 2, 3, 4, 5, 6, 8, 10, 12, 9}$. Ïðòåäåìéí ôåðåòø íîïçïþìåî~$P(x)= \prod_{j\in S} (x-\alpha^j)$, çäå $\alpha$~åóôø üìåíåîô ðïòñäëá~$n$ ëïîåþîïçï ðïìñ~$GF(2^k)$, á ëïüææéãéåîôù~$P(x)$ ÷ùþéóìñàôóñ ÷ üôïí ðïìå. Óôåðåîø~$m$ íîïçïþìåîá~$P(x)$ òá÷îá þéóìõ üìåíåîôï÷ ÷~$S$. Åóìé~$\alpha^j$---ëïòåîø~$P(x)$, ôï é~$\alpha^2j$---ëïòåîø; ïôóàäá óìåäõåô, þôï ëïüææéãéåîôù~$P(x)$ õäï÷ìåô÷ïòñàô óïïôîïûåîéà~$p^2_i=p_i$, ô.~å.~ïîé òá÷îù~0 éìé~1. Äïëáöéôå, þôï åóìé~$R(x)=r_{n-1}x^{n-1}+\cdots+r_1x+r_0$---îåîõìå÷ïê íîïçïþìåî ðï íïäõìà~2 ó îå âïìåå þåí $t$~îåîõìå÷ùíé ëïüææéãéåîôáíé, ôï~$R(x)$ îå ëòáôåî~$P(x)$ ðï íïäõìà~2. [Ïôóàäá óìåäõåô, þôï óïïô÷åôóô÷õàýáñ èåû-æõîëãéñ ÷åäåô óåâñ ïâåýáîîùí ïâòáúïí.] \ex[Í34] \exhead(Ôåïòåíá ï ôòåè äìéîáè.) Ðõóôø~$\theta$---éòòáãéïîáìøîïå þéóìï, ìåöáýåå íåöäõ~0 é~1, ðòåäóôá÷ìåîéå ëïôïòïçï ÷ ÷éäå ðòá÷éìøîïê îåðòåòù÷îïê äòïâé (ïâïúîáþåîéñ ð.~4.5.3) åóôø~$\theta=/a_1, a_2, a_3, ~\ldots/$. Ðõóôø~$q_0=0$, $p_0=1$, $q_1=1$, $p_1=0$ é~$q_{k+1}=a_kq_k+q_{k-1}$, $p_{k+1}=a_kp_k+p_{k-1}$ ðòé~$k\ge1$. Ïâïúîáþéí~$x \bmod 1=x-\floor{x}$ þåòåú~$\{x\}$, á~$x-\ceil{x}+1$ þåòåú~$\{x\}^+$. Âõäåí îõíåòï÷áôø ïôòåúëé ÷ ôïí ðïòñäëå, ëáë ïîé ðïìõþáàôóñ ðòé ðïóìåäï÷áôåìøîùè ÷óôá÷ëáè ÷ éîôåò÷áì~$[0, 1]$ ôïþåë~$\{\theta\}$, $\{2\theta\}$, $\{3\theta\}$,~\dots, ôáë þôï ðåò÷ùê ïôòåúïë äáîîïê äìéîù éíååô îïíåò~0, ÷ôïòïê---îïíåò~1 é~ô.~ä. Äïëáöéôå, þôï ÷óå óìåäõàýéå õô÷åòöäåîéñ ÷åòîù. Ìå÷ùí ëïîãïí éîôåò÷áìá îïíåò~$s$ äìéîù~$\{t\theta\}$, çäå~$t=rq_k+q_{k-1}$, $0\le r2(c-b)$ éìé~$c-b>2(b-a)$. Äïëáöéôå, þôï åóìé~$\theta\ne \phi^{-1}$ éìé~$\theta\ne\phi^{-2}$, ôï ðòé îåëïôïòïí~$n$ ôïþëá~$\{n\theta\}$ äáåô ðìïèïå òáúâéåîéå; åóìé öå~$\theta=\phi^{-1}$ éìé~$\theta=\phi^{-2}$, ôï ðìïèéè òáúâéåîéê îå ðïìõþáåôóñ. \ex[Í43] (Ò.~Çòüèåí.) Äïëáöéôå éìé ïðòï÷åòçîéôå óìåäõàýåå \emph{ðòåäðïìïöåîéå ï $3d$~äìéîáè:} åóìé~$\theta$, $\alpha_1$,~\dots, $\alpha_d$--- ÷åýåóô÷åîîùå þéóìá, ðòéþåí~$\alpha_1=0$, åóìé~$n_1$,~\dots, $n_d$---îáôõòáìøîùå þéóìá é åóìé ôïþëé~$\{n\theta+\alpha_i\}$ ÷óôá÷ìñàôóñ ÷ éîôåò÷áì~$[0, 1]$ ðòé~$0\le n < n_i$, $1\le i\le d$, ôï $n_1+\cdots+n_d$~ðïìõþáàýéèóñ éîôåò÷áìï÷ (÷ïúíïöîï, ðõóôùè) éíåàô îå âïìåå $3d$~òáúìéþîùè äìéî. \ex[16] Ïâùþîï õäáþîùå ðïéóëé ðòïéú÷ïäñôóñ þáýå îåõäáþîùè Òáúõíîï ìé óôòïëé~12--13 ðòïçòáííù~C ðïíåîñôø íåóôáíé óï óôòïëáíé~10--11? \rex[21] Ðïëáöéôå, þôï íïöîï ôáë ðåòåðéóáôø ðòïçòáííõ~C, þôï ÷ï ÷îõôòåîîåí ãéëìå ïóôáîåôóñ ìéûø ïäîá éîóôòõëãéñ õóìï÷îïçï ðåòåèïäá. Óòá÷îéôå ÷òåíåîá òáâïôù íïäéæéãéòï÷áîîïê é ðåò÷ïîáþáìøîïê ðòïçòáíí. \ex[24] \exhead(Óïëòáýåîîùå ëìàþé.) Ðõóôø $h(K)$---èåû-æõîëãéñ, a $g(K)$---ôáëáñ æõîëãéñ ïô~$K$, þôï, úîáñ~$h(K)$ é~$g(K)$, íïöîï îáêôé~$K$. Îáðòéíåò, ðòé èåûéòï÷áîéé äåìåîéåí íïöîï ðïìïöéôø~$h(K)=K \bmod M$ é~$g(K)=\floor{K/M}$; ÷ íõìøôéðìéëáôé÷îïí èåûéòï÷áîéé ÷ ëáþåóô÷å~$h(K)$ íïöîï ÷úñôø óôáòûéå òáúòñäù~$(AK/w)\bmod 1$, á ÷ ëáþåóô÷å~$g(K)$---ïóôáìøîùå òáúòñäù. Ðïëáöéôå, þôï ðòé éóðïìøúï÷áîéé íåôïäá ãåðïþåë âåú îáìïöåîéñ ÷ ëáöäïê úáðéóé ÷íåóôï~$K$ äïóôáôïþîï èòáîéôø~$g(K)$. (Üôï éîïçäá üëïîïíéô ðòïóôòáîóô÷ï, îåïâèïäéíïå äìñ ðïìåê óóùìïë.) Éúíåîéôå áìçïòéôí~C, þôïâù ïî íïç òáâïôáôø ó ôáëéíé óïëòáýåîîùíé ëìàþáíé, õóôòáîé÷ îáìïöåîéå óðéóëï÷, îï îå éóðïìøúõñ ÷óðïíïçáôåìøîùè ñþååë ðáíñôé äìñ "ðåòåðïìîñàýéè" úáðéóåê. \ex[24] (Ü.~Üìøëïë.) Ðïëáöéôå, þôï âïìøûáñ òáóóåñîîáñ ôáâìéãá íïöåô éóðïìøúï÷áôø ïâýõà ó äòõçéíé ó÷ñúáîîùíé óðéóëáíé ðáíñôø. Ðõóôø ëáöäïå óìï÷ï óðéóïþîïê ðáíñôé óïäåòöéô ä÷õèâéôï÷ïå ðïìå~|TAG|, éíåàýåå óìåäõàýéê óíùóì: {\medskip\narrower \item{$|TAG|(|P|)=0$} ïâïúîáþáåô óìï÷ï ÷ óðéóëå ó÷ïâïäîïçï ðòïóôòáîóô÷á; $|LINK|(|P|)$~õëáúù÷áåô îá óìåäõàýåå ó÷ïâïäîïå óìï÷ï. % \item{$|TAG|(|P|)=1$} ïâïúîáþáåô éóðïìøúõåíïå óìï÷ï, îå ñ÷ìñàýååóñ þáóôøà òáóóåñîîïê ôáâìéãù; æïòíáô ïóôáìøîùè ðïìåê üôïçï óìï÷á ðòïéú÷ïìåî. % \item{$|TAG|(|P|)=2$} ïâïúîáþáåô óìï÷ï ÷ òáóóåñîîïê ôáâìéãå; $|LINK|(|P|)$~õëáúù÷áåô îá äòõçïå óìï÷ï. ×óñëéê òáú, ëïçäá ðòé ïâòáâïôëå óðéóëá, îå ñ÷ìñàýåçïóñ þáóôøà òáóóåñîîïê ôáâìéãù, íù äïóôéçáåí óìï÷á ó~$|TAG|(|P|)=2$, îõöîï õóôáîï÷éôø~$P\asg|LINK|(|P|)$ äï ðïìõþåîéñ óìï÷á ó~$|TAG|(|P|)\le 1$. (Äìñ üææåëôé÷îïóôé íïöîï éúíåîéôø ïäîõ éú ðòåäûåóô÷õàýéè óóùìïë; ôïçäá îå ðòéäåôóñ óîï÷á é óîï÷á ðåòåóëáëé÷áôø þåòåú ïäîé é ôå öå üìåíåîôù òáóóåñîîïê ôáâìéãù.) \medskip} Ðïëáöéôå, ëáë ïðòåäåìéôø ðïäèïäñýéå áìçïòéôíù äìñ ÷óôá÷ëé é ÷ùâïòëé ëìàþåê éú ôáëïê ëïíâéîéòï÷áîîïê ôáâìéãù, ðòåäðïìáçáñ, þôï ÷ óìï÷å ó~$|TAG|(|P|)=2$ éíååôóñ åýå ïäîï ðïìå óóùìëé~$|AUX|(|P|)$. \ex[16] Ðïþåíõ ÷ áìçïòéôíáè~L é~D òáúõíîï æéëóéòï÷áôø ðåòåðïìîåîéå ðòé~$N=M-1$, á îå ðòé~$N=M$? %%646 \ex[10] × ðòïçòáííå~L çï÷ïòéôóñ, þôï $K$~îå äïìöîï òá÷îñôøóñ~0. Á ÷äòõç îá óáíïí äåìå ïîá òáâïôáåô äáöå ðòé~$K=0$? \ex[15] Ðïþåíõ îå ðïìïöéôø ðòïóôï~$h_2(K)=h_1(K)$ ÷~(25), åóìé~$h_1(K)\ne0$? \rex[21] Äåêóô÷éôåìøîï ìé~(31) ðòåäðïþôéôåìøîåå~(30) ÷ ëáþåóô÷å úáíåîù óôòïë~10--13 ðòïçòáííù~D? Äáêôå ïô÷åô, éóèïäñ éú óòåäîéè úîáþåîéê~$A$, $S1$ é~$C$. \ex[40] Ðòï÷åòøôå üíðéòéþåóëé ÷ïúäåêóô÷éå ïçòáîéþåîéñ ïâìáóôé úîáþåîéê~$h_2(K)$ ÷ áìçïòéôíå~D ôáë, þôï: (a)~$1\le h_2(K)\le r$ ðòé~$r=1$, 2, 3,~\dots, 10; (b)~$1\le h_2(K)\le\rho M$ ðòé $\rho={1\over10}$, ${2\over10}$, ${3\over10}$,~\dots, ${9\over10}$. \ex[Í25] (Ò.~Ëòõôáò.) Éúíåîéôå áìçïòéôí~D óìåäõàýéí ïâòáúïí, õóôòáîññ èåû-æõîëãéà~$h_2(K)$: ÷ ûáçå~D3 õóôáîï÷éôø~$c\asg 0$, á ÷ îáþáìå ûáçá~D4 õóôáîï÷éôø~$c\asg c+1$. Äïëáöéôå, þôï, åóìé~$M=2^m$, óïïô÷åôóô÷õàýáñ ðïóìåäï÷áôåìøîïóôø ðòïâ~$h_1(K)$, $(h_1(K)-1)\bmod M$, ~\dots, $\left(h_1(K)-\perm{M}{2}\right)\bmod M$ âõäåô ðåòåóôáîï÷ëïê íîïöåóô÷á~$\set{0, 1,~\dots, M-1}$. Ëáë üôïô íåôïä, âõäõþé úáðòïçòáííéòï÷áîîùí äìñ íáûéîù~\MIX, ÷ùçìñäéô ðï óòá÷îåîéà ó ôòåíñ ðòïçòáííáíé, òáóóíáôòé÷áåíùíé îá òéó.~42, åóìé ðï÷åäåîéå áîáìïçéþîï óìõþáêîïíõ ïðòïâï÷áîéà óï ÷ôïòéþîùí ïëõþé÷áîéåí? \rex[20] Ðòåäðïìïöéí, þôï íù èïôåìé âù õäáìéôø úáðéóø éú ôáâìéãù, ðïóôòïåîîïê ó ðïíïýøà áìçïòéôíá~D, ðïíåþáñ óïïô÷åôóô÷õàýõà ðïúéãéà ëáë õäáìåîîõà. Óìåäõåô ìé ðòé üôïí õíåîøûáôø úîáþåîéå ðåòåíåîîïê~$N$, õðòá÷ìñàýåê áìçïòéôíïí~D? \ex[27] Äïëáöéôå, þôï áìçïòéôí~R ïóôá÷ìñåô ôáâìéãõ ôïþîï ÷ ôáëïí öå ÷éäå, ëáë åóìé âù $|KEY|[i]$ îå âùì óðåò÷á ÷óôá÷ìåî. \rex[23] Ðòéäõíáêôå áìçïòéôí, áîáìïçéþîùê áìçïòéôíõ~R, äìñ õäáìåîéñ üìåíåîôï÷ éú òáóóåñîîïê ôáâìéãù ãåðïþåë, ðïóôòïåîîïê ó ðïíïýøà áìçïòéôíá~C. \ex[Í20] Ðòåäðïìïöéí, þôï íîïöåóô÷ï ÷óåè ÷ïúíïöîùè ëìàþåê óïóôïéô éú $MP$~üìåíåîôï÷, ðòéþåí òï÷îï $P$~ëìàþåê éíåàô äáîîùê èåû-áäòåó. (× òåáìøîùè óìõþáñè $P$~ïþåîø ÷åìéëï; îáðòéíåò, åóìé ëìàþáíé ñ÷ìñàôóñ ðòïéú÷ïìøîùå äåóñôéúîáþîùå þéóìá, á~$M=10^3$, ôï~$P=10^7$.) Ðòåäðïìïöéí, þôï~$M\ge7$ é~$N=7$. Ðõóôø éú íîïöåóô÷á ÷óåè ÷ïúíïöîùè ëìàþåê óìõþáêîùí ïâòáúïí ÷ùâéòáàôóñ óåíø òáúìéþîùè üìåíåîôï÷. ×ùòáúéôå þåòåú~$M$ é~$P$ ôïþîõà ÷åòïñôîïóôø ðïìõþåîéñ èåû-ðïóìåäï÷áôåìøîïóôé 1~2~6~2~1~6~1 (ô.~å.~$h(K_1)=1$, $h(K_2)=2$,~\dots, $h(K_7)=1$). \ex[M19] Ïâ®ñóîéôå, ðïþåíõ ÷åòîá æïòíõìá~(39). \ex[M20] Óëïìøëï èåû-ðïóìåäï÷áôåìøîïóôåê $a_1\ a_2~\ldots a_9$ ðòé éóðïìøúï÷áîéé ìéîåêîïçï ïðòïâï÷áîéñ äáäõô ëáòôéîõ úáîñôùè ñþååë~(21)? \ex[Í27] Úá÷åòûéôå äïëáúáôåìøóô÷ï ôåïòåíù~K. [\emph{Õëáúáîéå:} ðõóôø $$ s(n,x,y)=\sum_{k\ge0}\perm{n}{k}(x+k)^{k+1}(y-k)^{n-k-1}(y-n); $$ éóðïìøúõêôå âéîïíéáìøîõà ôåïòåíõ Áâåìñ [æïòíõìá~(1.2.6-16)] äìñ äïëáúáôåìøóô÷á ôïçï, þôï~$s(n, x, y)=x(x+y)^n+ns(n-1, x+1, y-1)$] \ex[M30] × ôå äá÷îéå ÷òåíåîá, ëïçäá Ü×Í âùìé çïòáúäï íåäìåîîåå îùîåûîéè, ðï íéçáîéà ìáíðïþåë íïöîï âùìï óõäéôø, ó ëáëïê óëïòïóôøà òáâïôáåô áìçïòéôí~L. Ëïçäá ôáâìéãá óôáîï÷éìáóø ðïþôé ðïìîïê, ïäîé üìåíåîôù ïâòáâáôù÷áìéóø ïþåîø âùóôòï, á äòõçéå ÷åóøíá íåäìåîîï. Üôé îáâìàäåîéñ îá÷ïäñô îá íùóìø ï ôïí, þôï, åóìé éóðïìøúõåôóñ ìéîåêîïå ïðòïâï÷áîéå, óòåäîåë÷áäòáôéþîïå ïôëìïîåîéå ÷åìéþéîù~$C'_N$ äï÷ïìøîï ÷åìéëï. Îáêäéôå æïòíõìõ, ÷ùòáöáàýõà äéóðåòóéà þåòåú æõîëãéé~$Q_r$, ïðòåäåìåîîùå ÷ ôåïòåíå~K, é ïãåîéôå åå ðòé~$N=\alpha M$ é~$M\to\infty$. \ex[M21] \exhead(Úáäáþá ï óôïñîëå.) Îá îåëïê õìéãå ó ïäîïóôïòïîîéí ä÷éöåîéåí éíååôóñ $m$~íåóô äìñ óôïñîëé, òáóðïìïöåîîùè ÷ òñä é ðåòåîõíåòï÷áîîùè ïô~1 äï~$m$. Íõö ÷åúåô ÷ á÷ôïíïâéìå ó÷ïà äòåíìàýõà öåîõ. ×îåúáðîï öåîá ðòïóùðáåôóñ é ôòåâõåô îåíåäìåîîï ïóôáîï÷éôøóñ. Ïî ðïóìõûîï ïóôáîá÷ìé÷áåôóñ %%647 îá ðåò÷ïí ó÷ïâïäîïí íåóôå, îï åóìé îåô ó÷ïâïäîùè íåóô, ë ëïôïòùí íïöîï ðïä®åèáôø, îå ðï÷ïòáþé÷áñ ïâòáôîï (ô.~å.~åóìé öåîá ðòïóîõìáóø, ëïçäá íáûéîá äïóôéçìá $k\hbox{-çï}$~íåóôá äìñ óôïñîëé, îï ÷óå "ðïúéãéé"~$k$, $k+1$,~\dots, $m$ úáîñôù), íõö ðòéîïóéô ó÷ïé éú÷éîåîéñ é åäåô äáìøûå Ðòåäðïìïöéí, þôï üôï ðòïéóèïäéô ó $n$~òáúìéþîùíé íáûéîáíé, ðòéþåí $j-\hbox{ñ}$~öåîá ðòïóùðáåôóñ ÷ íïíåîô, ëïçäá íáûéîá îáèïäéôóñ ðåòåä íåóôïí~$a_j$. Óëïìøëï éíååôóñ ôáëéè ðïóìåäï÷áôåìøîïóôåê~$a_1$~\dots{}$a_n$, ðòé ëïôïòùè ÷óå íáûéîù õäáþîï ðòéðáòëõàôóñ, ðòåäðïìáçáñ, þôï ðåò÷ïîáþáìøîï õìéãá ðõóôá é îéëôï óï óôïñîëé îå õåúöáåô? Îáðòéíåò, åóìé~$m=n=9$ é~$a_1\ldots{}a_9=3\ 1\ 4\ 1\ 5\ 9\ 2\ 6\ 5$, á÷ôïíïâéìé òáóðïìïöáôóñ óìåäõàýéí ïâòáúïí: \picture{Òéó. óôò. 647} [Õëáúáîéå: ÷ïóðïìøúõêôåóø áîáìéúïí ìéîåêîïçï ïðòïâï÷áîéñ.] \ex[Í28] (Äöïî~Òéïòäáî.) Ðïëáöéôå, þôï ÷ úáäáþå ï óôïñîëå éú õðò.~29 ðòé~$n=m$ ÷óå íáûéîù ðòéðáòëõàôóñ ôïçäá é ôïìøëï ôïçäá, ëïçäá óõýåóô÷õåô ðåòåóôáîï÷ëá~$p_1$ $p_2$~\dots{} $p_n$ íîïöåóô÷á~$\set{1, 2, ~\ldots, ð}$, ôáëáñ, þôï~$a_j\le p_j$ äìñ ÷óåè~$j$. \ex[Í40] Åóìé ÷ úáäáþå ï óôïñîëå (õðò.~29) $n=m$, þéóìï òåûåîéê ïëáúù÷áåôóñ òá÷îùí~$(n+1)^{n-1}$, á éú õðò.~2.3.4.4-22 íù úîáåí, þôï üôï åóôø þéóìï ó÷ïâïäîùè, äåòå÷øå÷ îáä~$n+1$~òáúìéþîùíé ÷åòûéîáíé! Îáêäéôå éîôåòåóîõà úá÷éóéíïóôø íåöäõ ðïóìåäï÷áôåìøîïóôñíé ïóôáîï÷ïë é äåòå÷øñíé. \ex[Í26] Äïëáöéôå, þôï óéóôåíá õòá÷îåîéê~(44) éíååô åäéîóô÷åîîïå òåûåîéå~$(C_0, C_1,~\ldots, C_{M-1})$ ðòé ìàâùè ãåìùè îåïôòéãáôåìøîùè~$b_0$, $b_1$,~\dots, $b_{M-1}$, óõííá ëïôïòùè íåîøûå~$M$. Ðïóôòïêôå áìçïòéôí äìñ îáèïöäåîéñ üôïçï òåûåîéñ. \ex[Í23] Ïâ®ñóîéôå, ðïþåíõ~(51) ÷óåçï ìéûø ðòéâìéöåîéå ë éóôéîîïíõ óòåäîåíõ þéóìõ ðòïâ, ðòïéú÷ïäéíùè áìçïòéôíïí~L. [Ëáëéå îåóôòïçïóôé âùìé äïðõýåîù ðòé ÷ù÷ïäå~(51)?] \ex[Í22] Ãåìø üôïçï õðòáöîåîéñ---éóóìåäï÷áôø óòåäîåå, þéóìï ðòïâ ÷ òáóóåñîîïê ôáâìéãå ãåðïþåë, ëïçäá óðéóëé ïóôáàôóñ òáúäåìøîùíé, ëáë îá òéó~38. (a)~Þåíõ òá÷îá ÷åòïñôîïóôø~$P_{Nk}$ ôïçï, þôï äáîîùê óðéóïë éíååô äìéîõ~$k$, åóìé $M^N$~èåû-ðïóìåäï÷áôåìøîïóôåê~(35) òá÷îï÷åòïñôîù? (b)~Îáêäéôå ðòïéú÷ïäñýõà æõîëãéà~$P_N(z)\sum_{k\ge0} P_{Nk} z^k$. (c)~×ùòáúéôå þåòåú üôõ ðòïéú÷ïäñýõà æõîëãéà óòåäîåå þéóìï ðòïâ ðòé õäáþîïí é îåõäáþîïí ðïéóëå. (Ðòåäðïìáçáåôóñ, þôï îåõäáþîùê ðïéóë ÷ óðéóëå äìéîù~$k$ ôòåâõåô $k+\delta_{k0}$~ðòïâ.) \ex[Í21] (Ðòïäïìöåîéå õðò.~34.) Îáêäéôå óòåäîåå þéóìï ðòïâ ðòé îåõäáþîïí ðïéóëå, åóìé ïôäåìøîùå óðéóëé õðïòñäïþåîù ðï úîáþåîéñí ëìàþåê. \ex[Í22] Îáêäéôå äéóðåòóéà þéóìá ðòïâ äìñ íåôïäá òáúäåìøîùè ãåðïþåë, åóìé ðïéóë âùì îåõäáþîùí. (Óí.~(18).) \rex[Í29] Îáêäéôå äéóðåòóéà þéóìá ðòïâ äìñ íåôïäá òáúäåìøîùè ãåðïþåë, åóìé ðïéóë âùì õäáþîùí. (Óí.~(19).) \ex[Í32] \exhead(Éóðïìøúï÷áîéå äåòå÷øå÷ ðòé èåûéòï÷áîéé.) Éóëõóîùê ðòïçòáííéóô íïç âù ðïðùôáôøóñ éóðïìøúï÷áôø ÷ íåôïäå ãåðïþåë âéîáòîùå äåòå÷øñ ðïéóëá ÷íåóôï ìéîåêîùè óðéóëï÷, ëïíâéîéòõñ ôáëéí ïâòáúïí áìçïòéôí~6.2.2Ô ó èåûéòï÷áîéåí. Ðòïáîáìéúéòõêôå óòåäîåå þéóìï ðòïâ, îõöîùè üôïíõ ëïíâéîéòï÷áîîïíõ áìçïòéôíõ é ÷ óìõþáå õäáþîïçï, é ÷ óìõþáå îåõäáþîïçï ðïéóëá. [\emph{Õëáúáîéå:} óò.~ó æïòíõìïê~(5.2.1-11).] \ex[M30] Ãåìø üôïçï õðòáöîåîéñ---ðòïáîáìéúéòï÷áôø óòåäîåå þéóìï ðòïâ ÷ áìçïòéôíå~C (óòáóôáàýéåóñ ãåðïþëé). Ïâïúîáþéí þåòåú~$c(k_1, k_2, k_3, ~\dots)$ ëïìéþåóô÷ï èåû-ðïóìåäï÷áôåìøîïóôåê~(35), úáóôá÷ìñàýéè áìçïòéôí~C ïâòáúï÷áôø òï÷îï $k_1$~óðéóëï÷ äìéîù~1, $k_2$~óðéóëï÷ äìéîù~2 é ô.~ä.; $k_1+2k_2+3k_3+\ldots=N$. Îáêäéôå òåëõòòåîôîïå óïïôîïûåîéå, ïðòåäåìñàýåå üôé þéóìá, é éóðïìøúõêôå %%648 åçï ðòé ÷ù÷ïäå ðòïóôïê æïòíõìù äìñ óõííù $$ S_N=\sum_{\scriptstyle j\ge 1\atop \scriptstyle k_1+k_2+\ldots=N}k_jc(k_1, k_2, \ldots). $$ Ëáë ó÷ñúáîá ÷åìéþéîá $S_N$ ó þéóìïí ðòïâ ÷ï ÷òåíñ îåõäáþîïçï ðïéóëá ó éóðïìøúï÷áîéåí áìçïòéôíá~C? \ex[M33] Îáêäéôå äéóðåòóéà þéóìá ðòïâ, ðòïéú÷ïäéíùè ÷ áìçïòéôíå~C, åóìé ðïéóë âùì îåõäáþîùí (óí.~(15).) \ex[Í40] Ðòïáîáìéúéòõêôå, óëïìøëï òáú ÷ óòåäîåí |R|~õíåîøûáåôóñ îá~1 ðòé ÷óôá÷ëå $(N+1)\hbox{-çï}$~üìåíåîôá ó ðïíïýøà áìçïòéôíá~C. (Ïâïúîáþéí üôï þéóìï þåòåú~$T_N$.) \ex[Í20] ×ù÷åäéôå~(17). \ex[Í42] Ðòïáîáìéúéòõêôå íïäéæéëáãéà áìçïòéôíá~C, éóðïìøúõàýõà ôáâìéãõ òáúíåòá~$M'\ge M$. Äìñ èåûéòï÷áîéñ éóðïìøúõàôóñ ìéûø ðåò÷ùå~$M$ ðïúéãéê, ôáë þôï ðåò÷ùå $M'-M$~ó÷ïâïäîùè õúìï÷, îáêäåîîùè ÷ ûáçå~C5, òáóðïìïöáôóñ ÷ äïðïìîéôåìøîïê þáóôé ôáâìéãù. Ëáëïê ÷ùâïò~$M$ ðòé æéëóéòï÷áîîïí~$M'$, $1\le M \le M'$, äáåô îáéìõþûéå èáòáëôåòéóôéëé? \ex[Í43] \exhead(Óìõþáêîïå ïðòïâï÷áîéå ó ÷ôïòéþîùí óëõþé÷áîéåí.) Ãåìø üôïçï õðòáöîåîéñ---ïðòåäåìéôø óòåäîåå þéóìï ðòïâ ÷ óèåíå ïôëòùôïê áäòåóáãéê ó ðïóìåäï÷áôåìøîïóôøà ïðòïâï÷áîéê $$ h(K), (h(K)+p_1)\bmod M, (h(K)+p_2)\bmod M, \ldots, (h(K)+p_{M-1})\bmod M, $$ çäå $p_1$ $p_2$~\dots $p_{M-1}$---óìõþáêîï-÷ùâòáîîáñ ðåòåóôáîï÷ëá íîïöåóô÷á~$\set{1, 2,~\ldots, M-1}$, úá÷éóñýáñ ïô~$h(K)$. Éîùíé óìï÷áíé, õ ÷óåè ëìàþåê ó ïäéîáëï÷ùí úîáþåîéåí~$h(K)$ ïäîá é ôá öå ðïóìåäï÷áôåìøîïóôø ïðòïâï÷áîéê, á $(M-1)!^M$~÷ïúíïöîùè ÷ùâïòï÷ $M$~ðïóìåäï÷áôåìøîïóôåê ðòïâ ó üôéí ó÷ïêóô÷ïí òá÷îï÷åòïñôîù. Íïöîï ôïþîï óíïäåìéòï÷áôø óéôõáãéà, åóìé îáä ðåò÷ïîáþáìøîï ðõóôùí ìéîåêîùí íáóóé÷ïí òáúíåòá~$m$ ÷ùðïìîéôø óìåäõàýõà ðòïãåäõòõ. Äåìáåí $n$~òáú ôáëõà ïðåòáãéà: {\medskip\narrower Ó ÷åòïñôîïóôøà~$p$ úáêíåí ëòáêîàà ìå÷õà ó÷ïâïäîõà ðïúéãéà. × ðòïôé÷îïí óìõþáå (ô.~å.\ ó~÷åòïñôîïóôøà~$q=1-p$) ÷ùâåòåí ìàâõà ðïúéãéà ôáâìéãù, ëòïíå ëòáêîåê ìå÷ïê, ðòéþåí ÷óå $m-1$~ðïúéãéê òá÷îï÷åòïñôîù. Åóìé ÷ùâòáîîáñ ðïúéãéñ ó÷ïâïäîá, úáêíåí åå; ÷ ðòïôé÷îïí óìõþáå ÷ùâåòåí \emph{ìàâõà} ó÷ïâïäîõà ðïúéãéà (÷ëìàþáñ óáíõà ìå÷õà) é úáêíåí åå, óþéôáñ, þôï ÷óå ó÷ïâïäîùå ðïúéãéé òá÷îï÷åòïñôîù. \medskip} Îáðòéíåò, åóìé~$m=5$ é~$n=3$, ôï ðïóìå ÷ùðïìîåîéñ ïðéóáîîïê ðòïãåäõòù ëïîæéçõòáãéñ (úáîñôï, úáîñôï, ó÷ïâïäîï, úáîñôï, ó÷ïâïäîï) ðïìõþáåôóñ ó ÷åòïñôîïóôøà $$ {7\over 192}qqq+{1\over6}pqq+{1\over6}qpq+{11\over64}qqp+{1\over3}ppq+{1\over4}pqp+{1\over4}qpp. $$ (Üôá ðòïãåäõòá óïïô÷åôóô÷õåô óìõþáêîïíõ ïðòïâï÷áîéà ó ÷ôïòéþîùí óëõþé÷áîéåí, ëïçäá~$p=1/m$, éâï íïöîï ðåòåîõíåòï÷áôø üìåíåîôù ôáâìéãù ôáë, þôï îåëïôïòáñ ðïóìåäï÷áôåìøîïóôø ðòïâ óï÷ðáäåô ó~0, 1, 2,~\dots, á ÷óå ïóôáìøîùå âõäõô óìõþáêîùíé.) Îáêäéôå æïòíõìõ äìñ óòåäîåçï þéóìá úáîñôùè ðïúéãéê ÷ ìå÷ïí ëïîãå íáóóé÷á (ä÷å ÷ ðòé÷åäåîîïí ðòéíåòå). Ïðòåäåìéôå ôáëöå áóéíðôïôéþåóëïå úîáþåîéå üôïê ÷åìéþéîù ðòé~$p=1/m$, $n=\alpha(m+1)$, $m\to\infty$. \ex[Í43] Òåûéôå áîáìïç õðò.~44 ó \emph{ôòåôéþîùí óëõþé÷áîéåí,} ëïçäá ðïóìåäï÷áôåìøîïóôø ðòïâ îáþéîáåôóñ ó~$h_1(K)$, $(h_1(K)+h_2(K))\bmod M$; ÷ùâïò äáìøîåêûéè ðòïâ óìõþáåî é úá÷éóéô ìéûø ïô~$h_1(K)$ é~$h_2(K)$ (ô.~å.~$(M-2)!^{M(M-1)}$ ÷ïúíïöîùè ÷ùâïòï÷ ðïóìåäï÷áôåìøîïóôåê ðòïâ ó üôéí ó÷ïêóô÷ïí óþéôáàôóñ %%649 òá÷îï÷åòïñôîùíé). Ñ÷ìñåôóñ ìé ðòåäìáçáåíáñ ðòïãåäõòá áóéíðôïôéþåóëé üë÷é÷áìåîôîïê òá÷îïíåòîïíõ ïðòïâï÷áîéà? \ex[M42] Îáêäéôå~$C'_N$ é~$C_N$ äìñ íåôïäá ïôëòùôïê áäòåóáãéé, éóðïìøúõàýåçï ðïóìåäï÷áôåìøîïóôø ðòïâ $$ h(K), 0, 1, \ldots, h(K-1), h(K)+1, \ldots, M-1. $$ \ex[M25] Ëáëïå óòåäîåå þéóìï ðòïâ ðïôòåâõåôóñ äìñ ïôëòùôïê áäòåóáãéé ó ðïóìåäï÷áôåìøîïóôøà ðòïâ $$ h(K), h(K)-1, h(K)+1, h(K)-2, h(K)+2,\ldots\,? $$ Üôá ðïóìåäï÷áôåìøîïóôø âùìá ïäîáöäù ðòåäìïöåîá éú-úá ôïçï, þôï ÷óå òáóóôïñîéñ íåöäõ ðïóìåäï÷áôåìøîùíé ðòïâáíé ðòé þåôîïí~$M$ òáúìéþîù [\emph{Õëáúáîéå: îåâïìøûáñ èéôòïóôø óõýåóô÷åîîï ïâìåçþéô úáäáþõ.}] \rex[M21] Äáîá âåóëïîåþîáñ ðïóìåäï÷áôåìøîïóôø ÷úáéíîï îåúá÷éóéíùè óìõþáêîùè èåû-æõîëãéê~$h_n(K)$. Ðòïáîáìéúéòõêôå íåôïä ïôëòùôïê áäòåóáãéé, ÷ ëïôïòïí ðòïâõàôóñ ðïúéãéé~$h_1(K)$, $h_2(K)$, $h_3(K)$,~$\ldots\,$. Úáíåôøôå, þôï ÷ïúíïöîï ðï÷ôïòîïå ïðòïâï÷áîéå ïäîïê é ôïê öå ðïúéãéé, îáðòéíåò åóìé~$h_1(K)=h_2(K)$, îï üôï ÷åóøíá íáìï÷åòïñôîï. \ex[×Í24] Ïâïâýé÷ õðò.~34 îá óìõþáê $b$~úáðéóåê ÷ âìïëå, ïðòåäåìéôå óòåäîåå þéóìï ðòïâ (ô.~å.~ïâòáýåîéê ë æáêìõ) $C_N$ é~$C'_N$ ðòé éóðïìøúï÷áîéé òáúäåìøîùè ãåðïþåë, ðòåäðïìáçáñ, þôï îåõäáþîùê ðïéóë ÷ óðéóëå éú $k$~üìåíåîôï÷ ôòåâõåô~$\min(1, k-b+1)$~ðòïâ. ×íåóôï ôïþîùè ÷åòïñôîïóôåê~$P_{Nk}$ éú õðò.~34 ÷ïóðïìøúõêôåóø \dfn{ðòéâìéöåîéåí Ðõáóóïîá} $$ \eqalign{ \perm{N}{k}\left({1\over M}\right)^k \left(1-{1\over M}\right)^{N-k} &={N\over M}{N-1\over M}\ldots{N-k+1\over M}\left(1-{1\over M}\right)^N \left(1-{1\over M}\right)^{-k}{1\over k!}=\cr &=e^{-\rho}\rho^k/k!+O(M^{-1}),\cr } $$ óðòá÷åäìé÷ùí ðòé~$N=\rho M$, $M\to\infty$. \ex[M20] Ðïëáöéôå, þôï ÷ ïâïúîáþåîéñè~(42) $Q_1(M, N)=M-(M-N-1)Q_0(M, N)$. [\emph{Õëáúáîéå:} äïëáöéôå óîáþáìá, þôï $Q_1(M, N)=(N+1)Q_0(M, N)-NQ_0(M, N-1)$.] \ex[BM16] ×ùòáúéôå æõîëãéà~$R(\alpha, n)$, ïðòåäåìåîîõà ÷~(55), þåòåú æõîëãéà~$Q_0$, ïðòåäåìåîîõà ÷~(42). \ex[×Í20] Äïëáöéôå, þôï~$Q_0(M,N)=\int_0^\infty e^{-t}(1+t/M)^N\,dt.$ \ex[×Í20] Äïëáöéôå, þôï æõîëãéà~$R(\alpha, n)$ íïöîï ÷ùòáúéôø þåòåú îåðïìîõà çáííá-æõîëãéà, é éóðïìøúõêôå òåúõìøôáô õðò.~1.2.11.3-9 äìñ îáèïöäåîéñ áóéíðôïôéþåóëïçï úîáþåîéñ~$R(\alpha, n)$ ó ôïþîïóôøà äï~$O(n^{-2})$) ðòé~$n\to\infty$ é æéëóéòï÷áîîïí~$\alpha<1$. \ex[40] Éóóìåäõêôå ðï÷åäåîéå áìçïòéôíá~C, åóìé åçï ðòéóðïóïâéôø ë ÷îåûîåíõ ðïéóëõ ôáë, ëáë üôï ïðéóáîï ÷ ôåëóôå. \ex[×Í43] Ïâïâýéôå íïäåìø Ûáñ---Óðòõôá, ïâóõöäá÷ûõàóñ ðïóìå ôåïòåíù~P, îá óìõþáê $M$~âìïëï÷ òáúíåòá~$b$. Äïëáöéôå, þôï~$C(z)=Q(z)/(B(z)-z^b)$, çäå $Q(z)$---íîïçïþìåî óôåðåîé~$b$ é~$Q(1)=0$. Ðïëáöéôå, þôï óòåäîåå þéóìï ðòïâ òá÷îï $$ 1+{M\over N}C'(1)=1+{1\over b}\left({1\over 1-q_1}+\cdots++{1\over 1-q_{b-1}}-{1\over2}{B''(1)-b(b-1)\over B'(1)-b}\right), $$ çäå~$q_1$~\dots$q_{b-1}$ óõôø ëïòîé íîïçïþìåîá~$Q(z)/(z-1)$. Úáíåîé÷ âéîïíéáìøîïå òáóðòåäåìåîéå ÷åòïñôîïóôåê~$B(z)$ ðòéâìéöåîéåí Ðõáóóïîá~$P(z)=e^{b\alpha(z-1)}$, çäå $\alpha=N/Mb$, é éóðïìøúï÷á÷ ìáçòáîöå÷õ æïòíõìõ ïâòáýåîéñ (óò. ó æïòíõìïê~(2.3.4.4-9) é õðò.~4.7-8), ðòé÷åäéôå ïô÷åô ë ÷éäõ~(61). \ex[M48] Ïâïâýéôå ôåïòåíõ~K, ðïìõþé÷ ôïþîùê áîáìéú ìéîåêîïçï ïðòïâï÷áîéñ ðòé éóðïìøúï÷áîéé âìïëï÷ òáúíåòá~$b$. %%650 \ex[Í47] Äáåô ìé ðòéðéóù÷áîéå ðïóìåäï÷áôåìøîïóôñí ðòïâ ïäéîáëï÷ùè ÷åòïñôîïóôåê íéîéíáìøîïå úîáþåîéå~$C_N$ óòåäé ÷óåè íåôïäï÷ ïôëòùôïê áäòåóáãéé? \ex[M21] (Ó.~Äöïîóïî.) Îáêäéôå äåóñôø ðåòåóôáîï÷ïë íîïöåóô÷á~$\set{0, 1, 2, 3, 4}$, üë÷é÷áìåîôîùè òá÷îïíåòîïíõ èåûéòï÷áîéà ÷ óíùóìå ôåïòåíù~U. \ex[Í25] Äïëáöéôå, þôï åóìé ðòéðéóù÷áîéå ÷åòïñôîïóôåê ðåòåóôáîï÷ëáí üë÷é÷áìåîôîï òá÷îïíåòîïíõ èåûéòï÷áîéà (÷ óíùóìå ôåïòåíù~U), ôï þéóìï ðåòåóôáîï÷ïë ó îåîõìå÷ùíé ÷åòïñôîïóôñíé ðòå÷úïêäåô~$M^a$ ðòé ìàâïí æéëóéòï÷áîîïí ðïëáúáôåìå~$a$, åóìé $M$~äïóôáôïþîï ÷åìéëï. \ex[M48] Âõäåí çï÷ïòéôø, þôï óèåíá ïôëòùôïê áäòåóáãéé ÷ëìàþáåô \emph{åäéîóô÷åîîïå èåûéòï÷áîéå,} åóìé éóðïìøúõåôóñ òï÷îï $M$~ðïóìåäï÷áôåìøîïóôåê ðòïâ, îáþéîáàýéèóñ óï ÷óåè ÷ïúíïöîùè úîáþåîéê~$h(K)$ é ÷óôòåþáàýéèóñ ó ÷åòïñôîïóôøà~$1/M$. Þôï áóéíðôïôéþåóëé ìõþûå (÷ óíùóìå íéîéíáìøîïóôé~$C_N$): îáéìõþûáñ óèåíá ó åäéîóô÷åîîùí èåûéòï÷áîéåí éìé óìõþáêîùå óèåíù, áîáìéúéòï÷á÷ûéåóñ ÷ õðò.~44? \ex[Í46] Ñ÷ìñåôóñ ìé íåôïä, áîáìéúéòï÷á÷ûéêóñ ÷ õðò.~46, îáéèõäûåê ÷ïúíïöîïê óèåíïê ó åäéîóô÷åîîùí èåûéòï÷áîéåí? (Óò.~ó~õðò.~60.) \ex[Í49] Îáóëïìøëï èïòïûá íïöåô âùôø óèåíá ó åäéîóô÷åîîùí èåûéòï÷áîéåí, åóìé ûáçé~$p_1$ $p_2$~\dots $p_{M-1}$ (ïâïúîáþåîéñ õðò.~44) æéëóéòï÷áîù é îå úá÷éóñô ïô~$K$? (Ðòéíåòáíé ôáëéè íåôïäï÷ óìõöáô ìéîåêîïå ïðòïâï÷áîéå é ðïóìåäï÷áôåìøîïóôé, òáóóíáôòé÷á÷ûéåóñ ÷ õðò.~20 é~47.) \ex[Í25] Åóìé ÷ òáóóåñîîïê ôáâìéãå ðòïéú÷ïäñôóñ óìõþáêîùå ÷óôá÷ëé é õäáìåîéñ, ôï óëïìøëï îõöîï ÷ óòåäîåí îåúá÷éóéíùè ÷óôá÷ïë, þôïâù ÷óå $M$~ðïúéãéê ðïâù÷áìé ÷ úáîñôïí óïóôïñîéé? \ex[M46] Ðòïáîáìéúéòõêôå ïöéäáåíïå ðï÷åäåîéå áìçïòéôíá~R. Óëïìøëï òáú ÷ óòåäîåí âõäåô ÷ùðïìîñôøóñ ûáç~R4? \rex[20] \exhead(Ëìàþé ðåòåíåîîïê äìéîù.) ×ï íîïçéè ðòéìïöåîéñè òáóóåñîîùè ôáâìéã ëìàþé íïçõô óïóôïñôø éú ðòïéú÷ïìøîïçï þéóìá ìéôåò. × ôáëïí óìõþáå îåìøúñ ðòïóôï úáðïíîéôø ëìàþ ÷ ôáâìéãå, ëáë üôï äåìáìïóø ÷ ðòïçòáííáè äáîîïçï ðáòáçòáæá. Ðòéäõíáêôå èïòïûéê óðïóïâ éóðïìøúï÷áîéñ òáóóåñîîùè ôáâìéã äìñ èòáîåîéñ ëìàþåê ðåòåíåîîïê äìéîù, åóìé òáâïôá ÷åäåôóñ îá íáûéîå~\MIX. %% 651 \bye