chap1.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

newnumber$(J(n))$,\kern-3.1pt\smallskip
where\newline newnumber$(k)=$\newline$2k-1$.\g
That is,
\begindisplay
 J(2n)	= 2\mkern1muJ(n) - 1 \,, \qquad\hbox{for $n \geq 1$.}
\enddisplay
We can now go quickly to large $n$.
For example, we know that $J(10) = 5$, so
\begindisplay
 J(20)	= 2\mkern1mu J(10) - 1	= 2 \cdt 5 - 1	= 9 \,.
\enddisplay
Similarly $J(40)=17$, and we can deduce that $J(5\cdt 2^m)=2^{m+1}+1$.

\looseness=-1
But what about the odd case?
\g Odd case? Hey, leave my brother out of it.\g
With $2n+1$~people, it turns out that person number~$1$ is wiped out just after
person number $2n$, and we're left with
\begindisplay
\unitlength=2pt
\beginpicture(48,31)(-28,-15)
\put(0,0){\circle{20}}
\put(0,0){\vector(0,1){9}}
\put(0,14.5){\cnum3}
\put(8.52,11.73){\cnum5}
\put(13.79,4.48){\cnum7}
\put(13.79,-4.48){\cnum9}
\put(0,-14.5){\cnum{\ldots}}
\put(-13.79,4.48){\cnum{2n-1}}
\put(-8.52,11.73){\cnum{2n+1}}
\endpicture
\enddisplay
Again we almost have the original situation with $n$ people,
but this time their numbers are
doubled and {\it increased\/} by~$1$.
Thus
\begindisplay
 J(2n+1)= 2\mkern1muJ(n) + 1 \,, \qquad\hbox{for $n \geq 1$.}
\enddisplay
Combining these equations with~$J(1)=1$ gives us a recurrence
that defines $J$ in all cases:
\begindisplay
\eqalign{J(1)&=1 \,;\cr
   J(2n)&= 2\mkern1muJ(n) - 1 \,, \qquad\hbox{for $n\ge1$;}\cr
   J(2n+1)&= 2\mkern1muJ(n) + 1 \,, \qquad\hbox{for $n\ge1$.}\cr
}\eqno\eqref|josephus-rec|
\enddisplay
Instead of getting $J(n)$ from $J(n-1)$, this recurrence is much more
``efficient,\qback'' because it reduces $n$ by a factor of~$2$ or more each
time it's applied. We could compute $J(1000000)$, say, with only 19~applications
of \thiseq. But still, we seek a closed form, because that will be
even quicker and more informative. After all, this is a matter of life
or death.

Our recurrence makes it possible to build a table of small values very
quickly. Perhaps we'll be able to spot a pattern and guess the answer.
\begindisplay \let\ =\enspace
\vbox{\halign{\bigstrut\hfil$#$\hfil&
 \ \vrule#&
 \ \hfil$\hss#\hss$&
 \ \vrule#&
 \ \hfil$\hss#\hss$&
 \ \hfil$\hss#\hss$&
 \ \vrule#&
 \ \hfil$\hss#\hss$&
 \ \hfil$\hss#\hss$&
 \ \hfil$\hss#\hss$&
 \ \hfil$\hss#\hss$&&
 \ \vrule#&
 \ \hfil$\hss#\hss$&
 \ \hfil$\hss#\hss$&
 \ \hfil$\hss#\hss$&
 \ \hfil$\hss#\hss$&
 \ \hfil$\hss#\hss$&
 \ \hfil$\hss#\hss$&
 \ \hfil$\hss#\hss$&
 \ \hfil$\hss#\hss$\cr
n&&1&&2&3&&4&5&6&7&&8&9&10&11&12&13&14&15&&16\cr
\noalign{\hrule}
J(n)&&1&&1&3&&1&3&5&7&&1&3&5&7&9&11&13&15&&1\cr}}
\enddisplay
\kern-1pt{\it Voil\`a!\/} It seems we can group by powers of~$2$
(marked by vertical lines in the table);
$J(n)$~is always~$1$ at the beginning of a group
and it increases by~$2$ within a group.
So if we write~$n$ in the form $n = 2^m+l$, where
$2^m$~is the largest power of~$2$ not exceeding~$n$
and where $l$~is what's left,
the solution to our recurrence seems to be
\begindisplay
J(2^m+l)= 2l+1 \,, \qquad\hbox{for $m \geq 0$ and $0\le l<2^m$.}
\eqno\eqref|josephus-sol|
\enddisplay
(Notice that if $2^m\le n<2^{m+1}$, the remainder $l=n-2^m$
satisfies $0\le l<2^{m+1}-2^m=2^m$.)

We must now prove \thiseq.
As in the past we use "induction",
but this time the induction is on~$m$.
When $m=0$ we must have $l=0$; thus the basis of \thiseq\ reduces to
$J(1)=1$, which is true.
\g But there's a simpler way! The key fact is that $J(2^m)=1$ for
all~$m$, and this follows immediately from our first equation,
\smallskip $J(2n)=2\mkern1muJ(n)-1.$\smallskip
Hence we know that the first person will survive
whenever $n$~is a power of~$2$.\par
And in the general case, when $n=2^m+l$, the number of people
is reduced to a power of~$2$ after there have been $l$~executions.
The~first remaining person at this point, the survivor, is number~$2l+1$.\g
The induction step has two parts, depending on whether $l$ is even or odd.
If $m>0$ and $2^m+l=2n$, then $l$ is even and
\begindisplay
J(2^m+l)=2\mkern1muJ(2^{m-1}+l/2)-1= 2(2l/2+1)-1=2l+1\,,
\enddisplay
by \eq(|josephus-rec|) and the induction hypothesis;
this is exactly what we want. A similar proof works in the odd case,
 when $2^m+l=2n+1$.
We might also note that \eq(|josephus-rec|) implies the relation
\begindisplay
J(2n+1)-J(2n)=2.
\enddisplay
Either way, the induction is complete and \eq(|josephus-sol|) is established.

To illustrate solution~\eq(|josephus-sol|), let's compute $J(100)$.
In this case we have $100 = 2^6 + 36$,
so $J(100) = 2\cdt36+ 1 = 73$.

Now that we've done the hard stuff (solved the problem)
we seek the soft:
"!philosophy"
Every solution to a problem can be generalized so that it applies to
a wider class of problems. Once we've learned a technique, it's instructive
to look at it closely and see how far we can go with it.
Hence, for the rest of this section,
we will examine the solution~\eq(|josephus-sol|) and
explore some "generalization"s of the recurrence~\eq(|josephus-rec|).
These explorations will uncover the structure that underlies all
such problems.

Powers of~$2$ played an important role in our finding the solution,
so it's natural to look at the "radix~$2$ representation"s of~$n$ and~$J(n)$.
Suppose~$n$'s "binary expansion" is
\tabref|nn:radix|%
\begindisplay
 n= (b_m\, b_{m-1} \ldots b_1\, b_0)_2\,;
\enddisplay
that is,
\begindisplay
 n = b_m 2^m \,+\, b_{m-1} 2^{m-1} \,+\, \cdots \,+\, b_1 2 \,+\, b_0 \,,
\enddisplay
where each $b_i$ is either $0$~or~$1$ and where the leading bit $b_m$ is~$1$.
Recalling that $n = 2^m+l$, we have, successively,
\begindisplay
n	&= (1\,b_{m-1}\, b_{m-2} \ldots b_1\, b_0)_2 \,,\cr
l	&= (0\,b_{m-1}\, b_{m-2} \ldots b_1\, b_0)_2 \,,\cr
2l	&= (b_{m-1}\, b_{m-2} \ldots b_1\, b_0\, 0)_2 \,,\cr
2l+1	&= (b_{m-1}\, b_{m-2} \ldots b_1\, b_0\, 1)_2 \,,\cr
J(n)	&= (b_{m-1}\, b_{m-2} \ldots b_1\, b_0\, b_m)_2 \,.
\enddisplay
(The last step follows because $J(n) = 2l+1$ and because $b_m=1$.)
We have proved that
\begindisplay
J\bigl((b_m\, b_{m-1} \ldots b_1\, b_0)_2\bigr)
	= (b_{m-1} \ldots b_1\, b_0\, b_m)_2 \,;
\eqno
\enddisplay
that is, in the lingo of computer programming,
we get~$J(n)$ from~$n$ by doing a one-bit "cyclic shift" left!
Magic.
For example, if $n = 100 = (1100100)_2$ then
$J(n) = J\bigl((1100100)_2\bigr) = (1001001)_2$, which is $64+8+1=73$.
If we had been working all along in binary notation, we probably would
have spotted this pattern immediately.

If we start with~$n$
and iterate the $J$ function $m+1$~times,
\g (``Iteration'' here means applying a function to~itself.)\g
we're doing $m+1$ one-bit cyclic shifts;
so, since $n$~is an $(m{+}1)$-bit number,
we might expect to end up with~$n$ again.
But this doesn't quite work.
For instance if $n=13$ we have $J\bigl((1101)_2\bigr) = (1011)_2$,
but then $J\bigl((1011)_2\bigr) = (111)_2$ and the process breaks down;
the $0$ disappears when it becomes the leading bit.
In fact, $J(n)$ must always be $\le n$ by definition, since $J(n)$ is
the survivor's number; hence if
$J(n)<n$ we can never get back up to $n$ by continuing to iterate.

Repeated application of $J$ produces a sequence of decreasing
values that eventually reach a ``"fixed point",\qback''
where $J(n)=n$. The cyclic shift property makes it easy
to see what that fixed point
will be: Iterating the function enough times
will always produce a pattern of all $1$'s
whose value is $2^{\nu(n)}-1$,
where $\nu(n)$ is the number of $1$~bits
"!sideways addition" "!nu function"
in the binary representation of~$n$.
Thus, since $\nu(13) = 3$, we have
\begindisplay
 \overbrace{J(J( \ldots J}^
  {\hbox to0pt{\hss
   \the\scriptfont0$\scriptstyle 2$ or more $\scriptstyle J$'s\hss}}
 (13)\ldots\, )) \,=\, 2^3 - 1 \,=\, 7 \,;
\enddisplay
\g Curiously enough, if $M$ is a compact $C^\infty$ $n$-manifold
($n>1$), there exists a differentiable immersion of $M$ into
$\hbox{\runhead R}^{2n-\nu(n)}$ but not necessarily into
 $\hbox{\bf\runhead R}^{2n-\nu(n)-1}$. I~wonder
if Josephus was secretly a~topologist?\g
similarly
\begindisplay
 \overbrace{J(J( \ldots J}^
  {\hbox to0pt{\hss\the\scriptfont0$\hss\scriptstyle 8$ or more\hss}}
 ((101101101101011)_2) \ldots\, )) = 2^{10} - 1 = 1023 \,.
\enddisplay
Curious, but true.

Let's return briefly to our first guess,
that $J(n)=n/2$ when $n$~is even.
This is obviously not true in general, but
we can now determine exactly when it {\it is\/} true:
\begindisplay \openup3pt
J(n)	&= n/2 \,, \cr
2l+1	&= (2^m+l)/2 \,, \cr
l	&= \textstyle{1\over3}(2^m-2) \,.
\enddisplay
If this number
$l={1\over3}(2^m-2)$ is an integer, then
$n=2^m+l$ will be a solution, because
$l$ will be less than~$2^m$.
It's not hard to verify that $2^m-2$ is a multiple of~$3$
when $m$ is odd, but not when $m$ is even.
(We will study such things in Chapter~4.) Therefore there are
infinitely many solutions to the equation $J(n)=n/2$, beginning as follows:
\begindisplay
\vbox{\offinterlineskip\halign{\strut\ $\hfil#\hfil$&&\qquad$\hfil#\hfil$\cr
m	& \;\,l	& n = 2^m + l	& J(n) = 2l+1 = n/2	&\hbox{$n$ (binary)} \cr
\noalign{\kern2pt\hrule\kern4pt}
1 &\nullnum 0	& \twonullnum 2	& \nullnum 1	& \phantom{000000}10 \cr
3 &\nullnum 2	& \nullnum 10	& \nullnum 5	& \phantom{0000}1010 \cr
5	& 10	& \nullnum 42	& 21		& \twonullnum 101010 \cr
7	& 42	& 170		& 85		& 10101010\cr}}
\enddisplay
Notice the pattern in the rightmost column. These are the binary numbers
for which cyclic-shifting one place left produces the same result
as ordinary-shifting one place right (halving).

OK, we understand the $J$ function pretty well; the next step is to
"generalize" it. "!Josephus recurrence, generalized"
What would have happened if our problem had produced a recurrence that
was something like \eq(|josephus-rec|), but with different constants?
Then we might not have been lucky enough to guess the solution, because
the solution might have been really weird. Let's investigate this by
introducing constants $\alpha$,~$\beta$,
\g Looks like Greek to~me.\g
 and~$\gamma$ and trying to
find a closed form for the more general recurrence
\begindisplay
\eqalign{f(1)&=\alpha\,;\cr
   f(2n)&= 2f(n) +\beta \,, \qquad\hbox{for $n\ge1$;}\cr
   f(2n+1)&= 2f(n) + \gamma \,, \qquad\hbox{for $n\ge1$.}\cr
}\eqno\eqref|gen-jos-rec|
\enddisplay
(Our original recurrence had $\alpha=1$, $\beta=-1$, and $\gamma=1$.)
Starting with $f(1)=\alpha$ and working our way up,
we can construct the following general table for small values of~$n$:
\begindisplay
\def\hline{\omit&height2pt\cr\noalign{\hrule}\omit&height2pt\cr}
\vcenter{\offinterlineskip\halign{\strut\hfill$#$\ &\vrule#\ &&\ \hfil$#$\cr
n	&&		&&\hidewidth f(n)\cr
\hline
1	&& \alpha\cr
\hline
2	&& 2\alpha	&+& \beta \cr
3	&& 2\alpha	&&		&+& \gamma \cr
\hline
4	&& 4\alpha	&+& 3\beta \cr
5	&& 4\alpha	&+& 2\beta	&+& \gamma \cr
6	&& 4\alpha	&+& \beta	&+& 2\gamma \cr
7	&& 4\alpha	&&		&+& 3\gamma \cr
\hline
8	&& 8\alpha	&+& 7\beta \cr
9	&& 8\alpha	&+& 6\beta	&+& \gamma\cr}}
\eqno\eqref|alpha-beta-gamma|
\enddisplay
It seems that $\alpha$'s coefficient is $n$'s~largest power of~$2$.
Furthermore, between powers of~$2$,
$\beta$'s coefficient decreases by~$1$ down to~$0$
and $\gamma$'s increases by~$1$ up from~$0$.
Therefore if we express $f(n)$ in the form
\begindisplay
f(n)	= A(n) \mskip2mu \alpha \,+\, B(n) \mskip2mu \beta
					\,+\, C(n) \mskip2mu \gamma \,,
\eqno\eqref|gen-jos-form|
\enddisplay
by separating out its dependence on
$\alpha$,~$\beta$, and~$\gamma$, it seems that
\begindisplay
A(n)	&= 2^m \,; \cr
B(n)	&= 2^m - 1 - l \,;\eqno\eqref|gen-jos-sol| \cr
C(n)	&= l \,.
\enddisplay
Here, as usual, $n = 2^m+l$ and $0 \leq l < 2^m \bex$, for~$n \geq 1$.

It's not terribly hard to prove \eq(|gen-jos-form|) and \eq(|gen-jos-sol|)
\g Hold onto your hats, this next part is new stuff.\g
by induction, but the calculations are messy and uninformative.
Fortunately there's a better way to proceed, by choosing particular
values and then combining them. Let's illustrate this by considering
the special case $\alpha=1$, $\beta=\gamma=0$, when $f(n)$ is
supposed to be equal to~$A(n)$: Recurrence \eq(|gen-jos-rec|) becomes
\begindisplay
A(1)&=1\,;\cr
   A(2n)&= 2A(n)\,,&\qquad\hbox{for $n\ge1$;}\cr
   A(2n+1)&= 2A(n)\,,&\qquad\hbox{for $n\ge1$.}\cr
\enddisplay
Sure enough, it's true (by induction on~$m$) that $A(2^m+l)=2^m$.

Next, let's use recurrence \eq(|gen-jos-rec|) and solution
\eq(|gen-jos-form|) {\it in reverse}, by
starting with a simple function $f(n)$ and seeing if there are
any constants $(\alpha,\beta,\gamma)$ that will define it.
\g A neat idea!\g