% CHANGES TO VOLUME 4B OF THE ART OF COMPUTER PROGRAMMING
%
% Copyright (C) 2022, 2023, 2024 by Donald E. Knuth
% This file may be freely copied provided that no modifications are made.
% All other rights are reserved.
%
% Three levels of changes to the books are distinguished here:
%
% "\bugonpage" introduces the correction of an error;
% "\amendpage" introduces new material for future editions;
% "\improvepage" introduces ameliorations of lesser importance.
%
% (Changes introduced by \improvepage do not appear in the hardcopy listing.)
%
% Also, "\planforpage" introduces some of the author's half-baked intentions.
%
% NOTE: TO PUT THE INDEX ON A SEPARATE PAGE, RUN THIS WITH THE COMMAND LINE
% tex "\let\indexeject+ \input err4b"
\newif\ifall % \alltrue means show the trivial items too
\relax % hook
\def\vertical{|}
\def\inref#1 #{\expandafter\def\csname\vertical#1\endcsname}
\catcode`|=\active
\let|\inref \input \jobname.ref
\catcode`|=12
\input taocpmac % use the format for TAOCP, with modifications below
\def\becomes{\ifmmode\ \hbox\fi{\manfnt y}\ } % wiggly arrow indicates a change
\def\bugonpage#1.#2 #3 (#4) {
\medbreak\defaultpointsize
\line{\kern-5pt\llap{\manfnt x}% print a black triangle in left margin
{\bf Page #2}\enspace #3
\leaders\hrule\hfill\ \eightrm\date#4.}
\nobreak\smallskip\iftrue\noindent}
\def\amendpage#1.#2 #3 (#4) {
\medbreak\defaultpointsize
\line{\kern-5pt{\bf Page #2}\enspace #3
\leaders\hrule\hfill\ \eightrm\date#4.}
\nobreak\smallskip\iftrue\noindent}
\def\improvepage#1.#2 #3 (#4) {\ifall
\medbreak\ninepoint
\line{\kern-6pt{\sl Page #2\enspace #3\/}
\leaders\hrule\hfill\ \eightrm\date#4.}
\nobreak\smallskip\noindent}
\def\planforpage#1.#2 #3 (#4) {
\medbreak\defaultpointsize
\line{\kern-5pt{\bf Page #2}\enspace #3
\leaders\hbox to 5pt{\hss.\hss}\hfill\ \eightrm\date#4.}
\nobreak\smallskip\begingroup\let\endchange=\endgroup\sl\noindent}
\let\endchange=\fi
\def\nl{\par\noindent}
\def\nlh{\par\noindent\hangit}
\def\hangit{\hangindent2em}
\def\cutpar{{\parfillskip=0pt\par}}
\def\date#1.#2.#3.{% convert "yy.mm.dd." to "dd Mon 19yy"
#3
\ifcase#2\or Jan\or Feb\or Mar\or Apr\or May\or Jun\or
Jul\or Aug\or Sep\or Oct\or Nov\or Dec\fi
\ \ifnum #1<97 \hundred#1\else19#1\fi}
\def\hundred{20} % the "century" for dates before '97
\def\ex #1. [#2]{\ninepoint
\textindent{\bf#1.}[{\it#2\/}]\kern6pt}
\def\EX #1. [#2]{\ninepoint
\textindent{\llap{\manfnt x}\bf#1.}[{\it#2\/}]\kern6pt}
\def\foottext#1{\medskip
\hrule height\ruleht width5pc \kern-\ruleht \kern3pt \eightpoint
\smallskip\textindent{#1}}
\def\volheadline#1{\line{\cleaders\hbox{\raise3pt\hbox{\manfnt\char'36}}\hfill
\titlefont\ #1\ \cleaders\hbox{\raise3pt\hbox{\manfnt\char'36}}\hfill}}
\def\refin#1 {\let|\inref \input #1.ref \let|\crossref}
\let\defaultpointsize=\tenpoint
%%%%%%%%%%%%%% opening remarks %%%%%%%%%%%%%%%%%%%%%%%%
\def\lhead{INTRODUCTION}
\let\rhead=\lhead
\titlepage
\volheadline{THE ART OF COMPUTER PROGRAMMING}
\bigskip
\volheadline{ERRATA TO VOLUME 4B}
\bigskip
\noindent This document is a transcript of the notes that I have been making
in my personal copy of {\sl The Art of Computer Programming}, Volume~4B
since it was first printed in 2022.
\ifall Four levels of updates\dash---``errors,'' ``amendments,'' ``plans,''
and ``improvements''\dash---appear, indicated by four
\else Three levels of updates\dash---``errors,'' ``amendments,'' and
``plans''\dash---appear, indicated by three \fi
different typographic conventions:
\begingroup\def\hundred{17}
\bugonpage 0.666 line 1 (76.07.04)
Technical or typographical errors (aka bugs) are the most critical items, so
they are flagged with a `\thinspace{\manfnt x}\thinspace' preceding the page
number. The date on which I first was told about the bug is shown; this is the
effective date on which I paid the finder's fee. The necessary
corrections are indicated in
a straightforward way. If,~for example, the book says
`$n$' where it should have said `$n+1$', the change is shown thus:
\smallskip
$n$ \becomes $n+1$
\endchange
\amendpage 0.666 line 2 (89.07.14)
Amendments to the text appear in the same format as bugs, but without
the~`\thinspace{\manfnt x}\thinspace'. These are things I wish I had known
about or thought of when I wrote the original text, so I added them later.
The date is the date I drafted the new text.
\endchange
\def\hundred{19}
\planforpage 0.666 line 3 (17.11.20)
Plans for the future represent a third kind of item. In such notes I~sketched
my intentions about things that I wasn't ready to flesh out further when
I~wrote them down. You can identify these items because they're written in
slanted type, and preceded by a bunch of dots
`\hbox to 6em{\leaders\hbox to 5pt{\hss.\hss}\hfill}' leading to the date on
which I recorded the plan in my files.
\endchange
\improvepage 0.666 line 4 (38.01.10)
The fourth and final category\dash---indicated by page and line number in
smaller, slanted type\dash---consists of minor corrections or improvements
that most readers don't want to know about, because they are so trivial.
You wouldn't even
be seeing these items if you hadn't specifically chosen to print the complete
errata list in all its gory details.
Are you sure you wanted to do that?
\endchange
\endgroup
\ifall\else\medskip\ninepoint
My personal file of updates also includes a fourth category of items, not
shown in this list. They are miscellaneous minor corrections or improvements
that most readers don't want to know about, because they are so trivial.
If you really want to see all of the gory details,
you can download the full list from Internet webpage
$$\.{http://www-cs-faculty.stanford.edu/\char`\~knuth/taocp.html}$$
by selecting the ``long form'' of the errata.
\fi
\medskip
\tenpoint
\beginconstruction
The ultimate, glorious, future editions of {\sl The Art of Computer
Programming\/} are works in progress.
Please let me know of any improvements that you think I ought to make.
Send your comments either by snail mail to D.~E. Knuth, Computer
Science, Gates Building 1B, Stanford University, Stanford CA~94305-9015,
or by email to
{\tt taocp{\char`\@}cs.stanford.edu}. (Use email for book suggestions
only, please\dash---all
other correspondence is returned unread to the sender, or discarded,
because I have no time to
read ordinary email.) Although I'm working full time on
Volume~4C these days, I~will try to reply to all such messages
within a year of receipt. Current news is posted on
$$\.{http://www-cs-faculty.stanford.edu/\char`~knuth/taocp.html}$$
and updated regularly.
\par\endconstruction
\rightline{\dash---Don Knuth, July 2022}
\bigskip
\bigskip
{\quoteformat
Next to the promulgation of new truth,
the best thing, I conceive, that a man can do,
is the recantation of published error.
\author JOSEPH LISTER (1878)
% Trans. Pathol. Soc. Lond. 29 (1878), 425--467;
% I saw it in Notes&Records 67(2013)228 in note 23 by R Richardson
\bigskip\bigskip
\vfill\eject
}
\def\today{\number\day\space\ifcase\month\or
January\or February\or March\or April\or May\or June\or
July\or August\or September\or October\or November\or December\fi
\space\number\year}
%%%%%%%%%%%%%%% CHANGES FOR VOLUME 4B %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\lhead{CHANGES TO VOLUME 4B: COMBINATORIAL ALGORITHMS, PART 2}
\let\rhead=\lhead
\titlepage
\volheadline{COMBINATORIAL ALGORITHMS, PART 2}
\bigskip
\rightline{Copyright \copyright\ 2022, 2023, 2024
Addison\with Wesley}
\rightline{Last updated \today}
\bigskip
\rightline{\sl Most of these corrections have already been made in
recent printings.}
\smallskip
\let\defaultpointsize=\tenpoint
\def\bland{@\land@} % \land as wide as \xor
\def\blor{@\lor@}
\def\nbool#1{\mathbin{\mkern1.5mu\overline{\mkern-1.5mu#1\mkern-1.5mu}\mkern1.5mu}}
\def\nimp{\?\nbool\supset\?}
\bugonpage 4b.ix lines 10 and 11 (23.01.06)
Mar-ijn \becomes Ma-rijn
\endchange
\improvepage 4b.x line $-3$ (23.11.24)
For example, $\nu@10=2$, $\lambda@10=3$, $\rho@10=1$. \becomes\nl
For example, $\nu@18=2$, $\lambda@18=4$, $\rho@18=1$.
\endchange
\improvepage 4b.xiv running head (23.04.09)
[delete this page number and running head; put `xiv' at bottom, centered]
\endchange
\amendpage 4b.xv replacement for lines 11--13 (22.11.26)
\ninepoint\smallskip
\def\0 #1 |#2|{\line{{#1}\leaders\hbox to
1em{\hfil.\hfil}\hfil\hbox to 5.7em{\hfil#2}}}%
\def\1 #1 #2 |#3|{\line{\hbox to 2.25em{#1\hfil}{#2}\leaders\hbox to
1em{\hfil.\hfil}\hfil\hbox to 5.7em{\hfil#3}}}%
\def\2 #1 #2 |#3|{\line{\hskip2.25em \hbox to
2.95em{#1\hfil}{#2}\leaders \hbox to 1em{\hfil.\hfil}\hfil\hbox to 5.7em{\hfil#3}}}%
\0 {\tenssbx Chapter 7\dash---Combinatorial Searching} |[4A.1\rlap]|
\smallskip
\1 7.2. Generating All Possibilities |[4A.281\rlap]|
\2 7.2.1. Generating Basic Combinatorial Patterns |[4A.281\rlap]|
\endchange
\amendpage 4b.2 in {\eq(9)} (22.12.25)
$(\E XY)$ \becomes $\E(XY)$
\endchange
\amendpage 4b.27 lines 3 and 4 of exercise 135 (22.12.05)
\ninepoint
either ($p_kl$ and $q_l>k$ and $q_{l+1}l$ and $p_l>k$ and $p_{l+1}k$ and $p_{l+1}l$) or
($q_{k+1}k$ and $q_k>l$).
\endchange
\improvepage 4b.33 in step W4 (22.11.27)
[Append `(Otherwise stop.)', to match steps B5 and B5*.]
\endchange
\bugonpage 4b.37 line 17 (23.02.15)
to run though \becomes to run through
\endchange
\bugonpage 4b.42 in the caption to Table 1 (22.11.27)
\ninepoint \.{0000} \becomes \.{000}\nl
\.{150f} \becomes \.{15f}\nl
\.{MEM[40d]} \becomes \.{MEM[4d]}
\endchange
\bugonpage 4b.43 line 2 after Table 2 (22.11.27)
\.{200} through \.{204} \becomes \.{20} through \.{24}
\endchange
\amendpage 4b.49 first line of step E5 (24.01.28)
If $d=0$, terminate.
Otherwise set $D\gets D\cdot d$ and $X_{@l}\gets y_I$, \becomes\nl
Set $D\gets D\cdot d$, and terminate if $d=0$.
Otherwise set $X_{@l}\gets y_I$,
\endchange
\amendpage 4b.49 replacement for the final six lines (24.01.28)
\noindent know roughly how many there are;
Algorithm E will tell us the approximate number.
Indeed, the expected final value of~$D$ is exactly the
total number of solutions, because every solution $X_1\ldots
X_{@l}$ constructed by the algorithm is obtained with probability $1/D$,
in a case where $D>0$.
Note that there may be another criterion for successful termination
in step~E2, even though $l$~might still be $\le n$.
\endchange
\bugonpage 4b.50 line $-2$ (23.11.11)
they defend \becomes they defined
\endchange
\amendpage 4b.55 new rating for exercise 15 (23.06.14)
\ninepoint [{\it\HM42\/}] \becomes [{\it\HM44\/}]
\endchange
\bugonpage 4b.58 exercises 41 and 42 (22.11.27)
\ninepoint
\.{MEM[40d]} \becomes \.{MEM[4d]}\nl
\.{MEM[904]} \becomes \.{MEM[94]}\nl
\.{MEM[a0d]} \becomes \.{MEM[ad]}
\endchange
\improvepage a4b.68 line 2 after Table 1 (22.12.16)
to cover a given item~$i$: \becomes
to cover the item whose number is~$i$:
\endchange
\improvepage 4b.90 near the top (22.09.30)
line 2: like cover$(i)$ \becomes like cover$(i)$ in \eq(12)\nl
line 3: like hide$(p)$ \becomes like hide$(p)$ in \eq(13)
\endchange
\bugonpage 4b.91 line $-6$ (22.12.17)
only 5.2 G$\mu$ \becomes only 4.5 G$\mu$
\endchange
\bugonpage 4b.102 in {\eq(86)} (23.01.19)
$60741+$ \becomes $60742-$
\endchange
\amendpage 4b.102 four lines after {\eq(86)} (23.08.03)
average length $n$ \becomes average length $n/2$
\endchange
\bugonpage 4b.110 line 1 of step P5 (23.01.02)
of its option, go \becomes
of its option, or if $\.{COLOR($x$)}\ne0$, go
\endchange
\bugonpage 4b.111 line 11 (22.12.14)
30,286,432 solutions \becomes 30,258,432 solutions
\endchange
\improvepage 4b.112 the line before {\eq(108)} (23.07.03)
remarkable pairing \becomes remarkable Langford pairing
\endchange
\improvepage 4b.135 lines 8 and 9 of exercise 103 (23.01.03)
\ninepoint twelve-tone row \becomes {\it twelve-tone row}
\endchange
\amendpage 4b.136 append a sentence to exercise 111 (23.03.30)
\ninepoint (Crossword puzzle diagrams
are black-and-white grids such as those in exercise 1.3.2--23.)
\endchange
\bugonpage 4b.138 line 8 of exercise 121 (23.01.07)
\ninepoint (2, 3, 3, 57) \becomes (2, 2, 3, 57)
\endchange
\improvepage 4b.142 line 7 (23.02.13)
\ninepoint the boundary of \becomes the boundary path of
\endchange
\improvepage 4b.145 line 3 of exercise 162 (23.11.04)
eight of the possible \becomes eight of the ten possible
\endchange
\amendpage 4b.145 new rating for exercise 171 (23.11.14)
\ninepoint [{\it 25\/}] \becomes [{\it 35\/}]
\endchange
\amendpage 4b.145 and 146 in exercise 172 (23.01.03)
\ninepoint [change `snake-in-the-box' to simply `snake', in five places]
\endchange
\amendpage 4b.146 new rating for exercise 175 (24.03.27)
\ninepoint [{\it 21\/}] \becomes [{\it 22\/}]
\endchange
\bugonpage 4b.146 lines 2 and 4 of exercise 175 (24.03.27)
\ninepoint $a_i$ \becomes $r_i$
\endchange
\amendpage 4b.159 new rating for exercise 300 (23.10.27)
\ninepoint [{\it 23\/}] \becomes [{\it 24\/}]
\endchange
\amendpage 4b.160 new rating for exercise 305 (23.02.03)
\ninepoint [{\it 25\/}] \becomes [{\it 28\/}]
\endchange
\amendpage 4b.161 new rating for exercise 306 (23.02.04)
\ninepoint [{\it 30\/}] \becomes [{\it 32\/}]
\endchange
\amendpage 4b.161 in exercise 306 (23.01.03)
\ninepoint [change `snake-in-the-box' to simply `snake', in two places]
\endchange
\amendpage 4b.172 new first paragraph for exercise 372{(b)} (22.12.06)
\begingroup\advance\parindent by 4pt\advance\thickmuskip-1mu
\ninepoint\item{b)} A {\it twintree\/} is a data structure whose nodes~$x$
have four pointer fields, \.{L0($x$)}, \.{R0($x$)},
\.{L1($x$)}, \.{R1($x$)}. It defines
two binary trees $T_0$ and $T_1$ on the nodes, where
$T_\theta$ is rooted at \.{ROOT$\theta$} and has child links
$(\.{L$\theta$},\.{R$\theta$})$.
These two trees satisfy inorder$(T_0)={\rm inorder}(T_1)=
x_1\ldots x_n$;
$\.{L0($x_k$)}=\Lambda$ $\iff$ $\.{L1($x_k$)}\ne\Lambda$,
for $10$ and $k=j+1$, or $i'>0$ and $l=j'+1$,
in order to force `\.{123456789}' on the top row.\par
With that top row and with $\alpha={}$transposition, Algorithm C produces
30,258,432 solutions in 171~gigamems. (These solutions were first enumerated
in 2005 by E.~Russell; see {\tt
www.afjarvis.org.uk/sudoku/sudgroup.html}.)
\endchange
\amendpage 4b.444 line 1 of answer 115 (23.01.02)
$b'_{yk}$ and $B'_{y'l}$ \becomes $b'_{yk}$
\endchange
\bugonpage 4b.446 new solution for answer {121(c)} (23.01.08)
\indent(c) With $\delta RU$ in the middle, another solution has
$C_{k-1}$, $D_{k-1}$, $A_{k-1}$, $B_{k-1}$ at the corners. With $\delta LD$,
another solution has corners $B_{k-1}$, $A_{k-1}$, $D_{k-1}$, $C_{k-1}$.
Both of those solutions work with $\delta LU$ and $\delta SU\?$;
and $\delta SU$ also has 54 additional solutions, with $C_{k-2}$ in the
upper left corner. They use
$\delta\{\{L,P,S,T\}\{J,U\},RU\}$ in the middle of row $2^{k-2}$,
and independently $\delta\{L,K,P,R,S,T\}U$ in the middle of row
$3\cdot2^{k-2}$.
\endchange
\bugonpage 4b.450 lines 4 and 5 of answer 133 (23.01.16)
We save a factor \dots\ another factor \becomes
Remove options with non-\.a on the border; also
limit \.{aaaa} to four border positions; and save another factor
\endchange
\bugonpage 4b.455 line 11 (22.12.20)
$q\equiv x$ (modulo~2) \becomes $q\equiv x/q$ (modulo~2)
\endchange
\amendpage 4b.457 line 22 (23.06.19)
8-cube \becomes eight-cube
\endchange
\amendpage 4b.459 line 13 of answer 151 (22.11.05)
with Algorithm X \becomes with Algorithm X and exercise 413
\endchange
\bugonpage 4b.462 line 3 of answer 162 (23.10.13)
$r_{j+1}$ $c_{k+3}$ $a_{j+k+3}$ $b_{j-k-3}$ \becomes
$r_{j+1}$ $c_{k+3}$ $a_{j+k+4}$ $b_{j-k-2}$
\endchange
\bugonpage 4b.462 in answer 162 (23.10.13)
line 5: multiplicity. \becomes multiplcity, and we'll use the
sharp preference heuristic.\nl
line 8: 1.2 teramems. \becomes 150 megamems.\nl
line 10: Only 35 G$\mu$ \becomes Less than 200 M$\mu$\nl
line 13: 6 teramems \becomes 180 megamems\nl
and in the largest displayed solution, put shading on the $\cal Q_5$.
\endchange
\bugonpage 4b.463 replacement for answer 171 (23.11.14)
\ans171. Let there be ten primary items $v$, for $0\le v<10$; also fifteen
primary items $\#uv$, for each edge $u\adj v$,
where the edges are
$0\adj1\adj2\adj3\adj4\adj0$,
$0\adj5$,
$1\adj6$,
$2\adj7$,
$3\adj8$,
$4\adj9$, and
$5\adj7\adj9\adj6\adj8\adj5$. Let there be $26\cdot10$ secondary items
$\.a_v$ through~$\.z_v$, for $0\le v<10$; also $26\cdot30$ secondary items
$\.a_{uv}$ through~$\.z_{uv}$, for $u\nadj v$; also a secondary item~$w$
for each word in, say, \.{WORDS}(1000). There are 26 options,
`$\#uv$ $\.a_u{:}1$ $\.a_v{:}1$' through
`$\#uv$ $\.z_u{:}1$ $\.z_v{:}1$', for each edge.
And there are 10 options for each
word; for example, the options for \.{added} at vertex~0 are
`0 $\.a_v{:}1$
$\.b_v{:}0$
$\.c_v{:}0$
$\.d_v{:}1$
$\.e_v{:}1$
$\.f_v{:}0$ \dots\
$\.z_v{:}0$
$\.a_{02}$
$\.a_{03}$
$\.a_{06}$
$\.a_{07}$
$\.a_{08}$
$\.a_{09}$
$\.d_{02}$ \dots\
$\.e_{09}$
\.{added}'.\tighten\par
Every solution will be obtained at least 120 times,
because the Petersen graph has 120 automorphisms, and the \#$uv$ options
might apply more than once. But symmetry can be
broken by introducing additional secondary items for pairwise
ordering, or by modifying Algorithm C to choose the labels of 0, 1,
and 3 first (see exercise 122).\tighten\par
There are two solutions in \.{WORDS}(834), namely
\.{muddy}, \.{thumb}, \.{books}, \.{knock}, \.{ended}, \.{apply},
\.{fifth}, \.{grass}, \.{civil}, (\.{refer} or \.{fewer}).
\endchange
\amendpage 4b.464 lines 5 and 6 of answer 172 (23.02.02)
${}=2$. For the path \dots\ $=1$ \becomes
${}=2$. We can safely omit options where
$v_i\adj v_j$ and $a_i=a_j=1$; they force a triangle.
For the path problem, the starting vertex should have $d$ options,
with $a_1+\cdots+a_d=1$
\endchange
\amendpage 4b.464 line 4 of answer 172{(a)} (23.01.03)
snake-in-the-box \becomes snake
\endchange
\amendpage 4b.464 in answer 172{(a)} (23.02.02)
line 5: 6 T$\mu$ \becomes 270 G$\mu$\nl
line 12: 13 M$\mu$ \becomes 54 M$\mu$\nl
line 16: (Algorithm M \dots\ 625 G$\mu$ \becomes
(If we force the first step downward,
Algorithm~M finds the $7!^2=25401600$ solutions in 365~G$\mu$\nl
line 21: in 17~G$\mu$, despite having 16788 options of total
length 454380(!). \becomes
in 9.4~G$\mu$, despite having 10422 options of total
length 281934(!).
\endchange
\bugonpage 4b.464 replacement for most of the last paragraph (23.02.02)
\indent
Now let's \dots\ dual transposition. \becomes\nl\indent
Now let's consider paths that start in cell $(0,1)$ and do not end in a corner.
(i)~No such solutions have 32 kings (proved in 166 G$\mu$).
(ii)~Knights, however, yield a big surprise:
There's a unique path of length~33, doubly counted! (Found
in 43~G$\mu$.) (iii)~Bishop paths can't have length~12 unless they start or
end in a corner. (iv)~There are $N=(n-1)!^2-2(n-2)!^2$ solutions where the
rook first moves down, and $N$ where it first moves sideways. Of these,
$2(n-2)!^2$ end at $(1,n-1)$ and are equivalent to those ending at $(n-2,0)$;
$(n-2)!^2$ end at $(n-1,n-2)$ and are double-counted by central symmetry;
$(n-2)!^2-(n-2)!$ end at $(1,0)$ and are double-counted by transposition;
$(n-2)!^2-(n-2)!$ end at $(n-2,n-1)$ and are double-counted by dual
transposition.
\endchange
\bugonpage 4b.465 line 1 (23.02.02)
So there are \dots\ 47691936 \becomes
So there are $2(n-1)!^2-9(n-2)!^2+2(n-2)!=46139040$
\endchange
\amendpage 4b.465 line 6 (23.02.02)
fast, except that the kings need 6.3 T$\mu$. \becomes
fast; kings need the max time (170~G$\mu$).
\endchange
\bugonpage 4b.465 line 5 of answer 172{(b)} (23.3.16)
bishop has 36 \becomes bishop has 72
\endchange
\bugonpage 4b.465 lines 7 and 8 of answer 172{(b)} (23.01.03)
under both horizontal and vertical reflection. Every rook snake-in-the-box
\becomes
under reflection about either diagonal. Every rook snake
\endchange
\amendpage 4b.465 and 466, replacement for final paragraphs of answer 172 (23.09.08)
Nikolai \dots\ [To appear.] \becomes\nl
\indent The maximum length of an $n\times n$ snake king path when $n=100$
was the topic
of a math olympiad problem in 2008, posed by A. and M.~Chapovalov.
Nikolai Beluhov has shown that such maximum
paths can be characterized completely; they're related to spirals when $n$ is
even, and to stamp-folding when $n$ is odd(!). When $n\ge6$ is even,
exactly $2n+(n\mod4)/2$ such paths are distinct
under symmetry, and they all start in a corner.
Furthermore there are exactly six distinct
snake king {\it cycles\/} of length $n^2\!/2-1$, when $n\ge8$
is a multiple of~4.
Beluhov has also proved that the longest
snake paths and cycles of a {\it knight}, on an $m\times n$ board,
have length $mn/2-O(m+n)$.
[See {\sl Enumerative Combinatorics and Applications\/ \bf3:2} (2023),
\#S2R16, 1--23.]
\endchange
\amendpage 4b.466 replacement for Fig.\ A--3 and the three previous lines (23.10.12)
\indent
(b,\thinspace c,\thinspace d) See Fig.\ \fig A--3/. The knight puzzles with
labels $\ge6$, and the bishop puzzles with labels 0, 10, and 12,
are due to N.~Beluhov; the others are mostly due to F.~Stappers
(and are minimum if they have $<5$ clues).
Solutions can be found in Appendix~E.\par
$$\def\epsfsize#1#2{.3#1}
\def\\#1#2{\epsfbox{\figdir/v4b.21#1#2}}
\centerline{\\51\enspace\\52\enspace\\53\enspace\\54\enspace\\55\quad\\57}$$
$$\def\epsfsize#1#2{.32#1}
\def\\#1#2{\epsfbox{\figdir/v4b.21#1#2}}
\centerline{\\31\enspace\\32\enspace\\33\enspace\\34\enspace\\35}$$
$$\def\epsfsize#1#2{.32#1}
\def\\#1#2{\epsfbox{\figdir/v4b.21#1#2}}
\centerline{\\36\enspace\\37\enspace\\38\enspace\\39\enspace\\59}$$
\endchange
\amendpage 4b.467 in answer 175 (24.03.27)
line 5: $a_i=a+1$ \becomes $r_i=r+1$\nl
line 5: $2a+1$ \becomes $2r+1$\nl
line 6: `$\#_{ai}$ $x_{ai}$', `$\#_{ai}$ $\alpha$' \becomes
`$\#_{ri}$ $x_{ri}$', `$\#_{ri}$ $\alpha$'
\endchange
\amendpage 4b.468 append to answer 185 (23.08.10)
(See OEIS sequence A113547 for other interpretations of these numbers.)
\endchange
\bugonpage 4b.485 line 12 (23.11.01)
essentially unity \becomes essential unity
\endchange
\amendpage 4b.482 line $-4$ (22.11.25)
44 pages \becomes 46 pages
\endchange
\bugonpage 4b.497 replacement for answer 305{(a)} (23.02.04)
\indent (a) Two cases: We can use a $5\times5$ box, and require that
the small squares of each option are either
$\{\.{34},\.{45}\}$,
$\{\.{47},\.{56}\}$,
$\{\.{76},\.{65}\}$, or
$\{\.{63},\.{54}\}$; or a $6\times6$ box, with those small-square coordinates
shifted by~\.{11}.
For example, if we call the leftmost piece `\.0', its $5\times5$ options are
`\.0 \.{35} \.{37} \.{34} \.{45}',
`\.0 \.{57} \.{77} \.{47} \.{56}',
`\.0 \.{53} \.{33} \.{63} \.{54}',
`\.0 \.{75} \.{73} \.{76} \.{65}'.
The $5\times5$ problem has $4\cdot183$ solutions, in groups of four that are
related by $90^\circ$ rotation; the $6\times6$ problem, similarly, has
$4\cdot209$ solutions. Reflection gives $4\cdot183+4\cdot209$ more.
Here are some of the $8+5$ classes of
equivalent solutions whose large squares form a symmetric shape; the
last two of these look the same, but use different pieces(!):
$$\def\\#1{\vcenter{\epsfbox{\figdir/v4b.331#1}}}
\def\|#1{\vcenter{\epsfbox{\figdir/v4b.334#1}}}
\def\epsfsize#1#2{.7#1}
\kern-20pt\\0\quad\\1\!\!\quad\\2\quad\\4\quad\\5\quad\|6\ \|7\ \|8\kern-20pt$$
\endchange
\amendpage 4b.498 and 499 in answer 306 (23.01.03)
[change `snake-in-the-box' to simply `snake', in two places]
\endchange
\bugonpage 4b.498 and 499 in answer 306 (23.01.22)
line 2: both even, and $00$. It's currently unknown whether or not
exactly {\it five\/} loops are possible.]
\endchange
\improvepage 4b.536 line $-5$ of answer 413 (23.08.31)
we unclose the loop (and set $\.E\gets0$) if $i=\.E$;
otherwise we zero the mates and set \becomes
we set $\.E\gets0$ (to unclose the loop), if $i=\.E$; but if $i\ne\.E$,
we set $\.{MATE($u$)}\gets\.{MATE($v$)}\gets0$ and
\endchange
\bugonpage 4b.539 in answer 422 (22.12.31)
line 1: $2m-2$ \becomes $2m-1$ \quad and\quad $2n-2$ \becomes $2n-1$\nl
lines 9 and 10: $N(i,j)=C(1,j)-10$, \dots\ Edges \becomes
$N(i,j)=C(i,j)-21$,
$NN(i,j)=C(i,j)-41$,
$W(i,j)=C(i,j)-12$,
$WW(i,j)=C(i,j)-14$; $N(i,j)$ is the edge between cells $(i,j)$ and
$(i-1,j)$. Edges
\endchange
\amendpage 4b.540 last lines of answer 425 (22.11.10)
solutions for $k=5$ \dots\ 9, 10. \becomes
solutions for $5\le k\le 10$, due to G.~J.~H. Goh, are also known.
(See (xviii)--(xxiv) in Fig.~\fig A--5/;
{\tt https://boonsuan.github.io/masyu.pdf}.)
\endchange
\amendpage 4b.548 replacement for copy after the display in answer 449 (23.10.22)
\noindent
Literary hitori nuggets longer than 80 characters were first reported by
Gary McDonald in 2023:
($7\times12=84$) ``he stood and carefully examined the sky, to ascertain the
time of night from the altitudes of the stars.'' [Thomas Hardy,
{\sl Far from the Madding Crowd\/} (1874)].
($11\times8=88$) ``\thinspace`\dots But talk to me of poverty and wealth, and
there indeed we touch upon realities.'
`My De-ar, this is becoming Awful\dash---'\thinspace''
[Charles Dickens, {\sl Our Mutual Friend\/} (1864)].
($10\times10=100$) ``shall never forget his flying Henry's kite for him that
very windy day last Easter\dash---and ever since his particular kindness''
[Jane Austen, {\sl Emma\/} (1816)].
\endchange
\amendpage 4b.549 new answer (23.06.18)
\ans5. The upper bound $W(3,k)=e^{O(\log k)^{11}}$ follows from (surprising)
results of Z.~Kelley and R.~Meka, \arXiv:2302.05537 [math.NT], 79~pages.
The (surprising) superpolynomial lower bound
$W(3,k)=k^{\Omega(\log k/\log\log k)}$ was proved by B.~Green and
Z.~Hunter in
{\sl Forum of Mathematics, Pi\/ \bf10} (2022), e18:1--51;
{\sl Combinatorica\/ \bf42} (2022), 1231--1252.
\endchange
\amendpage 4b.565 at end of answer 84 (24.01.10)
There's no known way \dots\ for all $j\ge0$.] \becomes
There's no known way to prove even the special cases that, say, $f^*(j,2j)=6j$
for all $j\ge0$. There has, however, been a recent spectacular breakthrough:
As of February 2024, Tomas Rokicki has verified equality for all
cells $(i,j)$ with $i\le6$ or $j\le6$.]
\endchange
\bugonpage 4b.611 line 6 of answer 318 (24.02.02)
$g_n-g_{n+1}=p/g_n^t-p/g_{n+1}^t>0$ when $g_{n+1}0$ when $g_n%% Unicode char "845b
\\\GC75:65:-3:60% G3302
<00000003e0000000000000000001f8000000000000000001fe000000000000000000ff00%
00000000000000007f0000000000000000007f8000000000000000003f80000000000000%
00001fc000000000000000001fc000000000000000000fc000000000000000000fc00000%
0000000000000fc0000780000000000007c0000fc000000000000400001fe00000000000%
0000003ff0000ffffffffffffffff80003fffffffffffffffc0001fffffffffffffffc00%
000000000000000000000000000000000000000000000000000000000000000000000000%
380000000000000000003e0000000000000000003f0000000000000000007fc000000000%
700000007fe000000000380000007fc0000000003c0000007f80000000001e0000007f80%
000000001f0000007f00000000000f0000007f00000000000f8000007e000000000007c0%
0000fe000000000007e00000fc000000000007f00000fc000000000003f80000fc000000%
000003f80000f8000000000001fc0001f8000000000001fc0001f0000000000001fe0001%
f0000000000000fe0003f0000000000000ff0003e0000000000000ff0003e00000000000%
007f8003c00000000000007f8007c00000000000007f8007c00000000000007f80078000%
00000000003f800f800000000000003f800f000000000000003f800f000000000000003f%
801f000000000000003f801e000000000000003f003e000000000000001f003c00000000%
0000001e007c00000000000000180078000000000000001000f8000000000000000000f0%
000000000000000001e000001c000000000001e000003e000000000003c000007f000000%
000003c00000ff80ffffffffffffffffffc07fffffffffffffffffe03fffffffffffffff%
ffe0>%% Unicode char "7acb
\JC48:48:0:40% J5581
<00fc0000000000f80000000000f00000006000f0000000f000f0fffffff800f07ffffffc%
00f003c0000000f003c0000000f003c0000000f003c0000004f003c0000004f003c00000%
04fc03c006000cf603c00f000cf703ffff800cf383ffffc018f383c00f8018f3c3c00f00%
18f3c3c00f0038f183c00f0038f003cc0f0070f003c70f0070f003c38f00f0f003c1cf00%
f0f003c1cf00e0f003c0cf0000f003c00f0000f003c00f0000f003cc0f0000f003c70f00%
00f003c38f0000f003c1cf0000f003c1cf0000f003c0cf0000f003c00f0000f003c00f00%
00f003c00f0000f001800f0000f000000f0000f000000f0000f000000f0000f000000f00%
00f000000f1800f000000f3c00f0fffffffe00f07fffffff00f000000000006000000000%
>%% Unicode char "6046
), 370, 395, 520, 523, 680.
Green, Ben Joseph, 549. % 3rd
Gr{\=\i}nbergs (= Grinberg), Emanuels Donats Fr{\=\i}drihs J\=anis, 582. % 3rd
Guibert, Olivier Patrick Serge, 395, 523. % 3rd
Hardy, Thomas, 548. % 3rd
Head of a list, \see List heads. % 3rd
Hexadecimal digits, extended past \.f, 73, 80, 484. % 3rd
Hunter, Zachary William Saunders, 549. % 3rd
Induced subgraphs, 63, 114, 145--146, 153, 183, 265, 436, 626. % 3rd
$k$-clauses: $k$-ary clauses, 187, 231. % 3rd
Keller, Michael, 132, 432, 494, 505. % 3rd
Kelley, Alexander (= Zander) Wilson, 549. % 3rd
Kint-Bruynseels, Ronald Odilon Bondewijn, 509. % 3rd
Knightley, Henry, 548. % 3rd
Knuth, Donald Ervin (\GC75:75:-3:62% G2463
<0000001f0000000000000000001ff8000000000000000007ff000000000000000003ff80%
00000000000000007f8000000000000000007f8000000000000000003f8000003c000000%
00003f8000007e00000000001f800000ff00000000000f800001ff00ffffffffffffffff%
ff80ffffffffffffffffffc07fffffffffffffffffe03800000000000000000000000000%
00000000000000000000000070000000000078000000f800000000007f000001fc000000%
00007ffffffffe00000000007fffffffff00000000003ffffffffe00000000003f000000%
fc00000000003f000000fc00000000003f000000fc00000000003f000000fc0000000000%
3f000000fc00000000003f000000fc00000000003f000000fc00000000003f000000fc00%
000000003ffffffffc00000000003ffffffffc00000000003ffffffffc00000000003f00%
0000fc00000000003f000000fc00000000003f000000fc00000001c03e0000000003c000%
01e03e0000000007e00001f800000000000ff00001fffffffffffffff00001ffffffffff%
fffff80001f8000000000007f80001f8000000000007e00001f8000000000007e00001f8%
000000000007e00001f801c000078007e00001f801e00007e007e00001f801f8000ff007%
e00001f801fffffff007e00001f801fffffff007e00001f801ffffffc007e00001f801f8%
000fc007e00001f801f8000fc007e00001f801f8000fc007e00001f801f8000fc007e000%
01f801f8000fc007e00001f801f8000fc007e00001f801f8000fc007e00001f801f8000f%
c007e00001f801f8000fc007e00001f801ffffffc007e00001f801ffffffc007e00001f8%
01ffffffc007e00001f801f8000fc007e00001f801f0000fc007e00001f801f0000f0007%
e00001f801f000000007e00001f8000000000007e00001f800000000ffcfe00001f80000%
00007fffc00001f8000000000fffc00001f80000000000ffc00001f800000000007f8000%
01f800000000003f800001f000000000001f000001f00000000000100000>%% Unicode char "9ad8
\GC73:74:-4:61% G2134
<00006000001c000000000000f000001f000000000000f800001fc00000000001fc00001f%
e00000000001fe00001fe00000000003fe00001fc00000000003f800001fc00000000007%
f000001f800070000007e000003f0000f800000fc000003f0001fc00001f8000007e0003%
fe00001f07ffffffffffff00003e03ffffffffffff80007c0100007c0000000000f80000%
00780000000000f0000000780000000001e0000000700000000003c03838007000070000%
07807c3c00f0000f80001f007f3f00e0001f80003e00ffbfffffffffc0007c00ffbfffff%
ffffe000f801ff1fffffffffe000c001fe1f03e0780f80000003fe1f03e0780f80000003%
fc1f03e0780f80000007f81f03e0780f80000007f01f03e0780f8000000fe01f03e0780f%
8000000fc01f03e0780fc000001f801f03e0780fc000003f001f03e0780fc000003fe01f%
03e0780fc000007fe01f03e0780fc00000ffe01f03e0780fc00000ffc01fffffffffc000%
01ffc01fffffffffc00001ff803fffffffffc00001ff803f0000000f800003df803f0000%
000f8000079f803f0000000038000f9f803f000000007c001f1f800000000000fe003e1f%
800000000001ff007c1fbfffffffffffff80f81f9fffffffffffff80e01f880000000000%
0000801f8000003000000000001f8000001c00000000001f8000f01e00000000001f8000%
fc0f001e0000001f8000ff0f801f0000001f8060ff07c00f8000001f8060ff07e00fe000%
001f8060fe03e007f000001f8060fc03e003f800001f8060fc03f003fc00001f80e0fc03%
f0c1fe00001f81e0fc03f0c0ff00001f81e0fc03e0e0ff00001f83e0fc01e0e07f00001f%
83e0fc0000e07f00001f87e0fc0000e03f00001f9fe0fc0001f03f00001fbfe0fc0001f0%
1f00001fbfe0fc0003f01f00001f9fe0fe0003f81800001f9fc0fffffff80000001f8380%
fffffff80000001f80007ffffff80000001f80003ffffff00000001f80001ffffff00000%
001f8000000000000000001f0000000000000000>%% Unicode char "5fb7
\GC71:74:-3:61% G3641
<000000000003800000000000000003f00000000300000003fc00000003c0000003fc0000%
0003e0000003f800000007f0000003f800000007f0000003f000000007e0000003f00000%
0007e0000003f000000007c0000003f00000000fc0000003f00000000f80000003f00000%
001f00000003e00000001f00000003e000e0003e00038003e001f0003e00c3e003e001f8%
007c00e1f803e003fc007800f1fffffffffe00f801f9fffffffffe00f001fdf003e003fc%
01e003fff003e003f801e007fff003e003f001c007fdf003e003f003800ff9f003e003f0%
03001ff1f003e003f00f003fe1f003e003f01e01ffc1f003e003f0ffffff81f003e003f0%
ffffff01f003e003f07ffcfe01f007e003f07ff0fc01f007c003f03fc1f801f007c003f0%
3c01f001f007e003f00003e001f00ff003f00003c001f00ff803f00007c001f00ffc03f0%
000f8001f00f9e03f0001f0001f01f9f83f0001e0001f01f0fc3f0003e0001f01f07e3f0%
007c0001f03e07e3f000f80001f03e03f3f001f00001f03c03f3f007e00ff9f07c03fbf0%
0fc3fff9f07803fbf01fffffc1f0f801fbf01fffff01f0f001fbf00ffff001f1f001fbf0%
0ffc0001f1e001fbf007f00001f3c000fbf007c00001f30000fbf002000001f600007bf0%
00000001f4000003f000000001f4000003f000000001f0000003f000000001f0000003f0%
000003fff0000003f00001fffff0000003f000fffff1f0000003f07fffffe1f0000003f0%
7ffffc01f0000003f07fffe001f0000003f03fff8001f0000003f03ff00001f0000003f0%
3f800001f0000007f01e000001f0003c07f010000001f0000ffff000000001f00003fff0%
00000001f000007ff000000001f000003ff000000001f000001ff000000001f000001fc0%
00000003f000000f80000000000000000e00>%% Unicode char "7eb3
), ii, iv, vi, viii, ix, xvii, 46, 54, 55, 63, 73, 77--79, 100, 118, 123, 185, 198, 200, 203, 235--236, 256, 258, 277, 278, 302, 309--311, 384, 389, 397, 401, 406, 412, 413, 419, 420, 424--425, 427, 429, 431--432, 440, 446, 459, 460, 463, 473, 475--478, 480, 481, 484, 485, 501--503, 508, 511, 514, 523, 527, 532, 533, 538, 540, 541, 544, 548, 556, 557, 559, 561, 566, 574, 576, 577, 580, 583, 584, 591, 599--601, 604, 606, 613, 624, 628--631, 638, 639, 642, 643, 646, 650, 654, 80, 686, 714. % 3rd
List heads, 65--68, 89, 124, 212, 480. % 3rd
Lubiw, Anna, 648. % 3rd
Meka, Raghu Vardhan Reddy ({\tl \|0128|\C103\\1\|0128|\C74\C135\ \|1128|\C107\\2\|0128|\raise.1ex\hbox{\|0167|}\C103\\1\|1148|\C90\ \|0141|\C103\\2\raise.1ex\hbox{\|2161|}\|3131|\C83\ \|0142|\C101\|0128|\C71}), 549. % 3rd
Model RB, 333--334. % 2nd
Modifications of Algorithm 7\period2\period2\period1C and related algorithms, 126, 127, 132, 133, 138, 183, 422, 442, 445, 463, 542. % 3rd
Multiple covering with colors, \see {\mc MCC} problem. % 3rd
Oak, Gabriel, 548. % 3rd
Octabytes, 534. % 3rd [because of reformatting pages 534--535]
OEIS\regtm: The On-Line Encyclopedia of Integer Sequences\regtm\ ({\tt oeis\period org}), 422, 423, 455, 468, 469, 504, 516, 556, 647. % 3rd
Online resources, \see Downloadable programs, Internet. % 3rd
{\mc OR} operation, bitwise ($x\bor y$), 17, 128, 227, 410, 560, 605, 622--623.
Pairwise ordering trick, 72, 126, 174, 420, 430, 463. % 3rd
Pi day puzzle, 60, 411, 439. % 3rd
Proof logging, \see Certificates of unsatisfiability. % 3rd
Progress, display of, 73, 126, 214, 329, 339. % 3rd
Propagation algorithm, 412. % 3rd
Purcell, Michael, 370. % 3rd
${\cal Q}_n$ configuration, 145. % 3rd
Ramakrishnan, Kajamalai Gopalaswamy\indexbreak
({\tm\\170\\127\\173\\127\\203\\126\\207\ \\125\\170\\127\\202\\127\\207\\302\\210\\127\\233\ \\205\\127\\203\\220\\315\\161\\176\\150}), 199. % 3rd
RB random instances, 333--334. % 2nd
Representation of sets, 534. % 3rd [because of reformatting pages 534--535]
Reversible memory technique, 44, 59, 222. % 3rd
Rodr{\'\i}guez Carbonell (= Rodr{\'\i}guez-Carbonell), Enric, 631. % 3rd
Rokicki, Tomas\sic/ Gerhard, ix, 564, 565. % 3rd
Rows of musical tones, 135. % 3rd
Search trees, 31, 32, 35, 37--39, 46--48, 52, 54, 73, 98--100, 104--107, 126, 147, 212--213, 216--218, 239, 308, 336, 399, 406, 407, 412, 434. % 3rd
Self-equivalent sudoku solutions, 111, 137. % 3rd
Sequential lists, 39--43, 220--221, 328, 534. % 3rd [because of reformatting pages 534--535]
Signature of a subproblem, 120--122, 154, 484. % 3rd
Slack options, 71, 478. % 3rd
Slack variables, 71. % 3rd
Snake cycles, 146, 161, 465. % 3rd
Snake paths, 145. % 3rd
Stamp folding, 465. % 3rd
Stappers, Filip Jan Jos, ix, 426, 431, 466, 533. % 3rd
Stirling, partition numbers, 138, 234, 333, 423, 424, 468, 584, 590. % 3rd
Sudoku, symmetries of, 74, 111, 137. % 3rd
\sub with knights and bishops, 146. % 3rd
Tagged vertices, 414. % 3rd
Tetraboloes, 163. % 3rd
Twintree structure, 172. % 3rd
Two stacks, 534. % 3rd [because of reformatting pages 534--535]
Unique solutions, 59, 75, 85, 128, 130--132, 140, 144, 146, 157, 160, 164, 173--183, 413, 453, 490--491, 502, 513, 514, 517, 519, 522, 535, 640. % 3rd
Unmatchable (blank) color, 88--89, 463. % 3rd
Utility fields in SGB format, 414. % 3rd
Weigel, Peter Heinrich, 444, 509, 532. % 3rd
Wilfer, Bella, 548. % 3rd
Woodhouse, Emma, 548. % 3rd
\vfill
\enddoublecolumns
\endchange
\bugonpage 4b.714 line $-6$ (22.11.14)
\eightpoint on an Dell Precision \becomes on a Dell Precision
\endchange
\bye
[The next printing will be the 3rd.]
not listed above:
pages iv and viii, http: -> https:
page 40, just before (22), (19) is in wrong font
page 54, line 17, hyphenate Carnegie-Mellon
page 54, line -18, add "in"
page 59, add a period following display in exercise 64
page 176, line 1, I adjusted the spacing in `9\times'
page 418, lines -7 to -4, (ref) -> [ref]
page 463, line 12, inactivated -> deactivated
page 528 changes to accommodate the change to page 529
page 533, similar spacing adjustments as on page 176
page 540, line -3 when -> when we have
page 572 and 573, bigger asterisks in Algorithm 7.2.2.2 A*
page 589, line -3 of answer 214, Probability and Computing
page 666, asterisk in Algorithm 7.2.2.2A*
page 674, adjusted spacing slightly in the epsilon entries
Bloom, Thomas Frederick, leaves the index
L-cube puzzle leaves the index
Solid bent trominoes leaves the index
The change to page 411 affects also pages 412, 413, 414, 415
The change to page 432 affects also pages 433, 434, 435
The change to page 497 affects also page 496
Shlyakhter leaves the index
ARTICLES "TO APPEAR" THAT ARE STILL PENDING:
Simkin arXiv 2107.13460 [ans 7.2.2--15]
Green in Forum of Math (ans 7.2.2.2--5)
Hunter in Combinatorica (ans 7.2.2.2--5)
Kelley and Meka (ans 7.2.2.2--5) surely will also be published