chap3.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

\eqno\eqref|merge-sort-rec|
\enddisplay
A solution to this recurrence appears in exercise~|merge-sol|.

The "Josephus problem" of Chapter 1 has a similar recurrence, which can be
cast in the form
\begindisplay
J(1)&=1\,;\cr
J(n)&=2J(\lfloor n/2\rfloor )-(-1)^n\,,\qquad\hbox{for $n>1$.}
\enddisplay

We've got more tools to work with than we had in Chapter~1, so let's consider
the more authentic Josephus problem in which every third person is eliminated,
instead of every second. If we apply the methods that worked in Chapter~1
to this more difficult problem, we wind up with a recurrence like
\begindisplay
J_3(n)=\textstyle\Bigl\lceil {3\over2}J_3\bigl(\lfloor{2\over3}n\rfloor\bigr)
 +a_n\Bigr\rceil \bmod n+1\,,
\enddisplay
where `mod' is a function that we will be studying shortly, and where we have
$a_n=-2$, $+1$, or~$-\half $ according as $n\bmod3=0$, $1$, or~$2$.
But this recurrence is too horrible to pursue.

There's another approach to the Josephus problem that gives a much better
setup. Whenever a person is passed over, we can assign a new number.
Thus, $1$ and~$2$ become $n+1$ and~$n+2$, then $3$~is executed;
$4$ and~$5$ become $n+3$ and~$n+4$, then $6$~is executed; \dots;
$3k+1$ and~$3k+2$ become $n+2k+1$ and~$n+2k+2$, then $3k+3$~is executed;
\dots~then $3n$~is executed (or left to survive).
For example, when $n=10$ the numbers are
\begindisplay \def\preamble{&$\hfil##\hfil$\kern1.5em}
1&2&3&4&5&6&7&8&9&10\cr
11&12&&13&14&&15&16&&17\cr
18&&&19&20&&&21&&22\cr
&&&23&24&&&&&25\cr
&&&26&&&&&&27\cr
&&&28\cr
&&&29\cr
&&&30\cr
\enddisplay
The $k$th person eliminated ends up with number $3k$. So we can figure out who
the survivor is if we can figure out the original number of person number~$3n$.

If $N>n$, person number $N$ must have had a previous number,
and we can find it as follows: We have $N=n+2k+1$ or $N=n+2k+2$, hence
$k=\lfloor (N-n-1)/2\rfloor $;
 the previous number was $3k+1$ or $3k+2$, respectively.
That is, it was $3k+(N-n-2k)=k+N-n$.
 Hence we can calculate the survivor's number
$J_3(n)$ as follows:
\begindisplay
&N:=3n\,;\cr
&\hbox{{\bf while} \ $N>n$ \ {\bf do} \
 $\displaystyle N:=\left\lfloor N-n-1\over2\right\rfloor+N-n\,$;}\cr
&J_3(n):=N\,.
\enddisplay
\g\vskip-13pt\noindent\llap{``}Not too slow,\par not too fast.''\par
\hfill\dash---L. "Armstrong"\g
This is not a closed form for $J_3(n)$; it's not even a recurrence. But at
least it tells us how to calculate the answer reasonably fast, if $n$~is
large.

Fortunately there's a way to simplify this algorithm if we use the variable
$D=3n+1-N$ in place of~$N$. (This change in notation
 corresponds to assigning numbers from
$3n$ down to~$1$, instead of from $1$ up to~$3n$; it's sort of like a
countdown.) Then the complicated assignment to~$N$ becomes
\begindisplay \openup4pt
D&:=3n+1-\left(\left\lfloor (3n+1-D)-n-1\over2\right\rfloor +(3n+1-D)-n\right)\cr
&\mathrel{\phantom:}=
 n+D-\left\lfloor 2n-D\over2\right\rfloor =D-\left\lfloor -D\over2\right\rfloor 
 =D+\left\lceil D\over2\right\rceil
 =\textstyle\bigl\lceil {3\over2}D\bigr\rceil \,,\cr
\enddisplay
and we can rewrite the algorithm as follows:
\begindisplay
&D:=1\,;\cr
&\hbox{{\bf while} \ $D\le2n$ \ {\bf do} \
 $D:=\bigl\lceil{3\over2}D\bigr\rceil\,$;}\cr
&J_3(n):=3n+1-D\,.
\enddisplay
Aha! This looks much nicer, because $n$ enters the calculation in a very
simple way. In fact, we can show by the same reasoning that the survivor
$J_q(n)$ when every $q$th person is eliminated can be calculated as follows:
\begindisplay
&D:=1\,;\cr
&\hbox{{\bf while} \ $D\le(q-1)n$ \ {\bf do} \
 $D:=\bigl\lceil{q_{\null}\over q-1}D\bigr\rceil\,$;}\eqno\eqref|m-josephus|\cr
&J_q(n):=qn+1-D\,.
\enddisplay
In the case $q=2$ that we know so well,
%\g We're $2$ familiar.\g
 this makes $D$ grow to $2^{m+1}$
when $n=2^m+l$; hence $J_2(n)=2(2^m+l)+1-2^{m+1}=2l+1$. Good.

The recipe in \thiseq\ computes a sequence of integers that can be
defined by the following recurrence:
\begindisplay
\eqalign{D_0^{(q)}&=1\,;\cr
D_n^{(q)}&=\Bigl\lceil {q\over q-1}D_{n-1}^{(q)}\Bigr\rceil \,
 \qquad\hbox{for $n>0$}.\cr}
\eqno\eqref|dm-rec|
\enddisplay
"!Josephus numbers"
These numbers don't seem to relate to any familiar functions in a simple
way, except when $q=2$; hence they probably don't have a nice closed form.
But if we're willing to accept the sequence $D_n^{(q)}$ as ``known,\qback''
\g``Known'' like, say, harmonic numbers.
A.\thinspace M. "Odlyzko" and\par
 H.\thinspace S. "Wilf" have shown [|odl-wilf|] that
\smallskip
$D_n^{(3)}=\lfloor({3\over2})^nC\rfloor$,
\smallskip
 where
\smallskip
$C\approx1.622270503.$\g
then it's easy to describe the solution to the generalized Josephus
problem: The survivor $\smash{J_q(n)}$ is $qn+1-D_k^{(q)}$, where $k$ is as
small as possible such that $D_k^{(q)}>(q-1)n$.

\beginsection 3.4 `mod': The Binary Operation

The "quotient" of $n$ divided by $m$ is $\lfloor n/m\rfloor$, when
$m$ and~$n$ are positive integers. It's handy to have a simple "notation"
also for the "remainder" of this
division, and we call it `$n\bmod m$'.
\tabref|nn:mod|"!mod, binary operation"
The basic formula
\begindisplay
n = m \underbrace{\lfloor n/m \rfloor}_{
					\hbox to0pt{\hss\sevenrm quotient\hss}}
		\;+\; \underbrace{n \bmod m}_{
					\hbox to0pt{\hss\sevenrm remainder\hss}}
\enddisplay
tells us that we can express $n\bmod m$ as $n-m\lfloor n/m\rfloor$. We can
generalize this to negative integers, and in fact to arbitrary real numbers:
\begindisplay
x \bmod y
	= x \,-\, y \lfloor x/y \rfloor \,,
						\qquad\hbox{for $y \neq 0$.}
\eqno\eqref|bmod-def|
\enddisplay
This defines `mod' as a binary operation,
just as addition and subtraction are binary operations.
\g Why do they call it `mod': The Binary Operation?
Stay tuned to find out in the next, exciting, chapter!\g
Mathematicians have used mod this way informally for a long time,
taking various quantities mod~$10$, mod~$2\pi$, and so on,
but only in the last twenty years has it caught on formally.
Old notion, new notation.

We can easily grasp
the intuitive meaning of $x\bmod y$, when $x$ and $y$ are positive real
numbers, if we imagine a circle of circumference~$y$
whose points have been assigned real numbers in the interval $[@0\dts y)$.
If we travel a distance~$x$ around the circle, starting at~$0$,
we end up at $x\bmod y$. (And the number of times we encounter~$0$ as
we go is $\lfloor x/y\rfloor$.)

When $x$ or $y$ is negative, we need to look at the definition carefully
in order to see exactly what it means.
\g Beware of computer languages that use another definition.\g
Here are some integer-valued examples:
\begindisplay
5 \bmod 3	&=5 - 3 \lfloor 5/3 \rfloor		&=2 \,;\cr
5 \bmod -3	&=5 - (-3) \lfloor 5/(-3) \rfloor	&=-1 \,;\cr
-5 \bmod 3	&=-5 - 3 \lfloor -5/3 \rfloor		&=1 \,;\cr
-5 \bmod -3	&=-5 - (-3) \lfloor -5/(-3) \rfloor	&=-2 \,.
\enddisplay
The number after `mod' is called the {\it "modulus"\/}; nobody has
\g How about calling the other number the modumor?\g
yet decided what to call the number before `mod'. In applications,
the modulus is usually
positive, but the definition makes perfect sense when
the modulus is negative.
In both cases the value of $x\bmod y$ is between $0$~and the modulus:
\begindisplay
0 \leq x \bmod y < y\,,	&\qquad \hbox{for $y > 0$;} \cr
0 \geq x \bmod y > y\,,	&\qquad \hbox{for $y < 0$.}
\enddisplay
What about $y=0$? Definition~\eq(|bmod-def|) leaves this case undefined,
in order to avoid division by zero, but to be complete we can define
\begindisplay
x \bmod 0
	= x \,.
\eqno\eqref|mod0|
\enddisplay
This convention preserves the property that $x\bmod y$ always differs from~$x$
by a multiple of~$y$. (It might seem more natural to make the function
continuous at~$0$, by defining
$x\bmod0=\lim_{y\to0}x\bmod y=0$. But we'll see in Chapter~4 that this
"!mod~$0$"
would be much less useful. Continuity is not an important aspect of
the mod operation.)

We've already seen one special case of mod in disguise,
when we wrote $x$ in terms of its integer and fractional parts,
$x = \lfloor x \rfloor + \{x\}$.
The fractional part can also be written $x\bmod1$, because we have
\begindisplay
x	= \lfloor x \rfloor \,+\, x \bmod 1 \,.
\enddisplay
Notice that parentheses aren't needed in this formula; we take
mod to bind more tightly than addition or subtraction.

The floor function has been used to define mod, and the ceiling function
hasn't gotten equal time. We could perhaps
use the ceiling to define a mod analog like
\begindisplay
 x \mathbin{\rm mumble} y
	= y \lceil x/y \rceil - x \,;
\enddisplay
in our circle analogy this represents the distance the traveler needs
\g There was a time in the 70s when `mod' was the fashion.
Maybe the new "mumble" function should be called `punk'?\medskip
No\dash---I \undertext{like} \hbox{`mumble'}.\g
"!notation, need for new"
to continue, after going a distance~$x$, to get back to the starting point~$0$.
But of course we'd need a better name than `mumble'.
If sufficient applications come along, an appropriate name will
probably suggest itself.

The "distributive law" is mod's most important algebraic property: We have
\begindisplay
c(x \bmod y)
	= (cx) \bmod (cy)
\eqno\eqref|mod-dist|
\enddisplay
for all real $c$, $x$, and $y$. (Those
who like mod to bind less tightly than multiplication
may remove the parentheses from the right side here, too.)
It's easy to prove this law from definition~\eq(|bmod-def|), since
\begindisplay
 c(x \bmod y)
	= c(x - y \lfloor x/y \rfloor)
	= cx - cy \lfloor cx/cy \rfloor
	= cx \bmod cy \,,
\enddisplay
if $cy\ne0$; and the zero-modulus cases are trivially true.
Our four examples using $\pm 5$ and $\pm 3$ illustrate this law twice,
with $c=-1$. An identity like \thiseq\ is reassuring, because it gives
us reason to believe that `mod' has not been defined improperly.

In the remainder of this section,
\g The remainder, eh?\g
we'll consider an application in which `mod' turns out to be helpful although
it doesn't play a central role. The problem
arises frequently in a variety of situations: We want to "partition"
$n$~things into $m$~groups as equally as possible.

 Suppose, for example,
that we have $n$~short lines of text that we'd like to arrange in
$m$~columns. For \ae{}sthetic reasons, we want the columns to be
arranged in decreasing order of length (actually nonincreasing order); and the
lengths should be approximately the same\dash---no two columns should differ by
more than one line's worth of text. If 37 lines of text are being divided
into five columns, we would therefore prefer the arrangement on the right:
\begindisplay \def\\{\kern9pt}
\vbox{\baselineskip6pt\halign{&\fiverm line\kern1pt #\hfil\\\cr
\omit\hfil$8$\hfil\\&
\omit\hfil$8$\hfil\\&
\omit\hfil$8$\hfil\\&
\omit\hfil$8$\hfil\\&
\omit\hfil$5$\hfil\\\cr
\noalign{\vskip4pt}
1&9&17&25&33\cr
2&10&18&26&34\cr
3&11&19&27&35\cr
4&12&20&28&36\cr
5&13&21&29&37\cr
6&14&22&30\cr
7&15&23&31\cr
8&16&24&32\cr}}
\qquad\quad
\vbox{\baselineskip6pt\halign{&\fiverm line\kern1pt #\hfil\\\cr
\omit\hfil$8$\hfil\\&
\omit\hfil$8$\hfil\\&
\omit\hfil$7$\hfil\\&
\omit\hfil$7$\hfil\\&
\omit\hfil$7$\hfil\\\cr
\noalign{\vskip4pt}
1&9&17&24&31\cr
2&10&18&25&32\cr
3&11&19&26&33\cr
4&12&20&27&34\cr
5&13&21&28&35\cr
6&14&22&29&36\cr
7&15&23&30&37\cr
8&16\cr}}
\enddisplay
Furthermore we want to distribute the lines of text columnwise\dash---first deciding
how many lines go into the first column and then moving on to the second,
the third, and so on\dash---because that's the way people read.
Distributing row by row would give us the correct number
of lines in each column, but the ordering would be wrong. (We would get
something like the arrangement on the right, but column~1 would contain
lines 1,~6, 11, \dots,~36, instead of lines 1,~2, 3, \dots,~8 as desired.)

A row-by-row distribution strategy can't be used,
but it does tell us how many lines
to put in each column. If $n$ is not a multiple of~$m$,
the row-by-row procedure makes it clear
that the long columns should each contain $\lceil n/m\rceil$
lines, and the short columns should each contain $\lfloor n/m\rfloor$.
There will be exactly $n\bmod m$ long columns (and, as it turns out,
there will be exactly $\mathsurround=1pt n\mathbin{\rm mumble}m$ short ones).

Let's generalize the terminology and talk about `things' and `groups' instead