chap3.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

by first counting the number~$W$ of winners and the number~$L=1000-W$ of losers.
If each number comes up once during 1000 plays,
we win $5W$ dollars and lose $L$ dollars,
so the average winnings will be
\begindisplay
 {5W-L\over 1000}
 = {5W-(1000-W)\over 1000}
	= {6W-1000\over 1000}\,.
\enddisplay
If there are 167~or~more winners, we have the advantage;
otherwise the advantage is with the house.

How can we count the number of winners among $1$~through~$1000$?
It's not hard to spot a pattern.
The numbers from $1$~through $2^3-1=7$ are all winners because
$\lfloor \mskip-2mu \root3\of{n} \rfloor = 1$ for each.
Among the numbers $2^3=8$ through $3^3-1=26$,
only the even numbers are winners.
And among $3^3=27$ through $4^3-1=63$, only those divisible by~$3$ are.
And so on.

The whole setup
can be analyzed systematically if we use the summation techniques
of Chapter~2, taking advantage of
"Iverson's convention" about logical statements
evaluating to $0$ or~$1$:
\begindisplay \openup2pt
W&=\sum_{n=1}^{1000}\[\hbox{$n$ is a winner}]\cr
&=\!\!\!\sum_{1\le n\le1000}\bigi[
 \lfloor \mskip-2mu \root3\of{n} \rfloor \bigm\divides n
  \bigr]
 =\sum_{k,n}\bigi[k=\lfloor\mskip-2mu\root3\of n\rfloor\bigr]
  \[k\divides n]\[1\le n\le1000]\cr
&=\sum_{k,m,n}\bigi[k^3\le n<(k+1)^3\bigr]\[n=km]\[1\le n\le1000]\cr
&=1+\sum_{k,m}\bigi[k^3\le km<(k+1)^3\bigr]\[1\le k<10]\cr
&=1+\sum_{k,m}\bigi[m\in{\bigl[k^2\dts(k+1)^3\!/k\bigr)}\bigr]\[1\le k<10]\cr
&=1+\sum_{1\le k<10}\bigl(\lceil k^2+3k+3+1/k\rceil -\lceil k^2\rceil \bigr)\cr
\noalign{\vskip-2pt}
&=1+\sum_{1\le k<10}(3k+4)=1+{7+31\over2}\cdt9=172\,.\cr
\enddisplay
This derivation merits careful study. Notice that
line~6 uses our formula \eq(|ints-in-interval|)
for the number of integers in a half-open interval.
The only ``difficult'' maneuver is the decision made between
lines 3 and~4 to treat $n=1000$ as a special case. (The inequality
$k^3\le n<(k+1)^3$ does not combine easily with $1\le n\le1000$ when
$k=10$.) In general, "boundary conditions" tend to be the most critical
\g True.\g "!philosophy"
part of $\sum$-manipulations.

The bottom line says that $W=172$; hence our formula for average
winnings per play reduces to
$(6 \cdt 172 - 1000)/1000$ dollars,
which is 3.2 cents.
\g Where did you say this casino is?\g
We can expect to be about \$3.20 richer after making 100~bets of \$1~each.
(Of course, the house may have made
some numbers more equal than others.)

\looseness=-1
The casino problem we just solved
is a dressed-up version of the more mundane question,
``How many integers~$n$, where $1 \leq n \leq 1000$, satisfy the relation
$\lfloor \mskip-2mu \root3\of{n} \rfloor\bigm\divides n$?''
Mathematically the two questions are the same.
But sometimes it's a good idea to dress up a problem.
We get to use
more "vocabulary" (like ``winners'' and ``losers''), which
helps us to understand what's going on.

Let's get general.
Suppose we change $1000$ to $1000000$, or to an even larger number,~$N$.
(We assume that the casino has connections and can get a bigger wheel.)
"!wheel, big"
Now how many winners are there?

The same argument applies, but we need to deal more carefully with
the largest value of~$k$, which we can call $K$ for convenience:
\begindisplay
 K
	= \lfloor \mskip-2mu \root3\of{N} \rfloor\,.
\enddisplay
(Previously $K$ was $10$.) The total number of winners for general $N$ comes to
\begindisplay \openup2pt
W&=\sum_{1\le k<K}(3k+4)+\sum_m\bigi[K^3\le Km\le N\bigr]\cr
&={\textstyle\half (7+3K+1)(K-1)}+\sum_m\bigi[m\in[K^2\dts N/K]\bigr]\cr
&={\textstyle{3\over2}K^2+{5\over2}K-4}
 +\sum_m\bigi[m\in[K^2\dts N/K]\bigr]\,.\cr
\enddisplay
We know that the remaining sum is $\lfloor N/K\rfloor -\lceil K^2\rceil +1=\lfloor N/K\rfloor -K^2+1$; hence
the formula
\begindisplay
W=\textstyle \lfloor N/K\rfloor +\half K^2+{5\over2}K-3\,,\qquad
 K	= \lfloor \mskip-2mu \root3\of{N} \rfloor
\eqno\eqref|wheel-winners|
\enddisplay
gives the general answer for a wheel of size $N$.

The first two terms of this formula are approximately $N^{2/3}+\half N^{2/3}
={3\over2}N^{2/3}$, and the other terms are much smaller in comparison,
when $N$ is large. In Chapter~9 we'll learn how to derive expressions like
\begindisplay
W=\textstyle{3\over2}N^{2/3}+O(N^{1/3})\,,
\enddisplay
where $O(N^{1/3})$ stands for a quantity that is no more than a constant times
"!big O"
$N^{1/3}$. Whatever the constant is, we know that it's independent of~$N$;
so for large~$N$ the contribution of the $O$-term to~$W$ will be quite small
compared with ${3\over2}N^{2/3}$. For example, the following table shows how
close ${3\over2}N^{2/3}$ is to $W$:
\begindisplay \mathcode`,=\hexcode13B\def\preamble{&\strut\hfil$##$\qquad}
N\enspace&{3\over2}N^{2/3}&W\,&\hbox{\% error}\cr
\noalign{\vskip2pt\hrule\vskip4pt}
1,000&		150.0&		172&	12.791\cr 
10,000&		 696.2&		 746&	 6.670\cr
100,000&	 3231.7&	 3343&	 3.331\cr
1,000,000&	 15000.0&	 15247&	 1.620\cr
10,000,000&	 69623.8&	 70158&	 0.761\cr
100,000,000&	323165.2&	 324322&  0.357\cr 
1,000,000,000&	1500000.0&	 1502496& 0.166\cr
\enddisplay
It's a pretty good "approximation".

Approximate formulas are useful because they're simpler than formulas
with floors and ceilings. However, the exact truth is often important, too,
especially for the smaller values of~$N$ that tend to occur in practice.
For example, the casino owner may have falsely assumed that there are only
${3\over2}N^{2/3}=150$ winners when $N=1000$ (in which case there would
be a 10\rlap/c advantage for the house).

\smallbreak
Our last application in this section looks at so-called spectra.
We define the {\it "spectrum"\/} of a real number~$\alpha$
to be an infinite multiset of integers,
\begindisplay
\spec(\alpha)
	= \{ \lfloor \alpha \rfloor,\, \lfloor 2\alpha \rfloor,\,
			\lfloor 3\alpha \rfloor,\, \ldots\, \} \,.
\enddisplay
"!Spec"
(A "multiset" is like a set but it can have repeated elements.)
For example, the spectrum of $1/2$ starts out $\{0,1,1,2,2,3,3,\ldots\,\}$.

It's easy to prove that no two spectra are equal\dash---%
that $\alpha \neq \beta$ implies $\spec(\alpha) \neq \spec(\beta)$.
\g\dots\ without lots\par of generality\thinspace\dots\g
For, assuming without loss of generality that $\alpha < \beta$,
there's a positive integer~$m$ such that $m(\beta-\alpha) \geq 1$.
(In fact, any $m \geq \lceil 1/(\beta-\alpha) \rceil$ will do; but we
needn't show off our knowledge of floors and ceilings all the time.)
Hence $m\beta-m\alpha \geq 1$,
and $\lfloor m\beta \rfloor > \lfloor m\alpha \rfloor$.
Thus $\spec(\beta)$ has fewer than $m$~elements $\le\lfloor m\alpha\rfloor$,
while $\spec(\alpha)$ has at least~$m$.

Spectra have many beautiful properties.
\g \noindent\llap{``}If\/ $x$ be an incommensurable number less than unity, one of the
series of quantities\/ $m/x$, $m/(1-x)$, where\/ $m$~is a whole number,
can be found which shall lie between any given consecutive integers, and
but one such quantity can be found.''\par\hfill\dash---Rayleigh~[|rayleigh|]\g
For example, consider the two multisets
\begindisplay \openup2pt
\spec(\sqrt{2} \,)
	&= \{ 1,2,4,5,7,8,9,11,12,14,15,16,18,19,21,22,24,\ldots\, \} \,,\cr
\spec(2+\sqrt{2} \,)
	&= \{ 3,6,10,13,17,20,23,27,30,34,37,40,44,47,51,\ldots\, \} \,.
\enddisplay
It's easy to calculate $\spec(\sqrt2\,)$ with a pocket calculator, and
the $n$th element of $\spec(2+\sqrt2\,)$ is just $2n$ more than the $n$th element
of $\spec(\sqrt2\,)$, by \eq(|n-in/out|). A closer look shows that these
two spectra are also related in a much more surprising way:
It seems that any number missing from one is in the other,
but that no number is in both!
And it's true:
The positive integers are the disjoint union of
$\spec(\sqrt{2} \,)$ and $\spec(2+\sqrt{2} \,)$. We say that
these spectra form a {\it"partition"\/} of the positive integers.

To prove this assertion, we will count how many of the elements of
$\spec(\sqrt2\,)$ are $\le n$, and how many of the elements of
$\spec(2+\sqrt2\,)$ are $\le n$. If the total is~$n$, for each~$n$,
\g Right, because exactly one of the counts must increase when $n$
increases by~$1$.\g
these two spectra do indeed partition the integers.

Let $\alpha$ be positive.
The number of elements in $\spec(\alpha)$ that are $\le n$ is
\begindisplay \openup1pt
N(\alpha,n)&=\sum_{k>0}\bigi[\lfloor k\alpha\rfloor\le n\bigr]\cr
&=\sum_{k>0}\bigi[\lfloor k\alpha\rfloor<n+1\bigr]\cr
&=\sum_{k>0}\[k\alpha<n+1]\cr
&=\sum_k\bigi[@0<k<(n+1)/\alpha@\bigr]\cr
&=\lceil(n+1)/\alpha\rceil-1\,.
\eqno\eqref|N-alpha-n|
\enddisplay
This derivation has two special points of interest. First, it uses the
law
\begindisplay
m\le n\quad\iff\quad m<n+1\,,\qquad\hbox{integers $m$ and $n$}
\eqno\eqref|le-vs-l|
\enddisplay
to change `$\le$' to `$<$', so that the floor brackets can be
removed by \eq(|f-c-in/out|). Also\dash---and this is more subtle\dash---%
it sums over the range $k>0$ instead of $k\ge1$, because $(n+1)/\alpha$
might be less than~$1$ for certain $n$ and~$\alpha$. If we had tried to
apply
\eq(|ints-in-interval|) to determine the number of integers in
$[1\dts(n+1)/\alpha)$, rather than the number of integers in $(0\dts(n+1)/\alpha)$, we
would have gotten the right answer; but our derivation would have been
faulty because the conditions of applicability wouldn't have been met.

Good, we have a formula for $N(\alpha,n)$. Now we can test whether or not
$\spec(\sqrt2\,)$ and
$\spec(2+\sqrt2\,)$ partition the positive integers, by testing whether
or not $N(\sqrt2,n)+N(2+\sqrt2,n)=n$ for all integers $n>0$, using
\eq(|N-alpha-n|):
\begindisplay \openup4pt \advance\abovedisplayskip-2pt
&\left\lceil n+1\over\sqrt2\right\rceil-1+
 \left\lceil n+1\over2+\sqrt2\right\rceil-1=n\cr
&\iff\enspace\left\lfloor n+1\over\sqrt2\right\rfloor+
	\left\lfloor n+1\over2+\sqrt2\right\rfloor=n\,,
 &\quad\hbox{by \eq(|c-f|);}\cr
&\iff\enspace{n+1\over\sqrt2}-\left\{n+1\over\sqrt2\right\}+
	{n+1\over2+\sqrt2}-\left\{n+1\over2+\sqrt2\right\}=n\,,
 &\quad\hbox{by \eq(|brace|).}\cr
\enddisplay
Everything simplifies now because of the neat identity
\begindisplay
{1\over\sqrt2}+{1\over2+\sqrt2}=1\,;
\enddisplay
our condition reduces to testing whether or not
\begindisplay
\left\{n+1\over\sqrt2\right\}+\left\{n+1\over2+\sqrt2\right\}=1\,,
\enddisplay
for all $n>0$. And we win, because these are the fractional parts of
two noninteger numbers that add up to the integer $n+1$.
A partition it is.

\beginsection 3.3 Floor/Ceiling Recurrences

Floors and ceilings add an interesting new dimension to the
study of "recurrence" relations. Let's look first at the recurrence
\begindisplay
\eqalign{K_0	&=1 \,;\cr
K_{n+1}	&=1 \,+\, \min (2 K_{\lfloor n/2 \rfloor} ,
				3 K_{\lfloor n/3 \rfloor}) \,,
					\qquad\hbox{for $n \geq 0$.}\cr}
\eqno\eqref|knuth-numbers|
\enddisplay
Thus, for example, $K_1$ is $1 + \min (2 K_0, 3 K_0)=3$;
the sequence begins $1$,~$3$, $3$, $4$, $7$, $7$, $7$, $9$, $9$,~$10$,~$13$,
\dots\thinspace.
One of the authors of this book has modestly decided to call these the
"Knuth numbers".

\goodbreak
Exercise |knuth-no-ex| asks for a proof or disproof
that $K_n\ge n$, for all $n\ge0$.
The first few $K$'s just listed do satisfy the inequality,
so there's a good chance that it's true in general.
Let's try an induction proof:
The basis $n=0$ comes directly from the defining recurrence.
For the induction step,
we assume that the inequality holds
for all values up through some fixed nonnegative~$n$,
and we try to show that $K_{n+1} \geq n+1$.
From the recurrence we know that
$K_{n+1} = 1 + \min (2 K_{\lfloor n/2 \rfloor} , 3 K_{\lfloor n/3 \rfloor})$.
The induction hypothesis tells us that
$2K_{\lfloor n/2 \rfloor} \geq 2\lfloor n/2 \rfloor$ and
$3K_{\lfloor n/3 \rfloor} \geq 3\lfloor n/3 \rfloor$.
However, $2\lfloor n/2\rfloor$ can be as small as $n-1$, and
$3 \lfloor n/3 \rfloor$ can be as small as $n-2$. The most we can conclude
from our induction hypothesis is that $K_{n+1} \geq 1 + (n-2)$;
this falls far short of $K_{n+1} \geq n+1$.

We now have reason to worry about the truth of
$K_n\ge n$, so let's try to disprove it. If we can find an $n$ such that
either $2K_{\lfloor n/2\rfloor}<n$ or
$3K_{\lfloor n/3\rfloor}<n$, or in other words such that
\begindisplay
K_{\lfloor n/2\rfloor}<n/2\qquad\hbox{or}\qquad
K_{\lfloor n/3\rfloor}<n/3\,,
\enddisplay
we will have $K_{n+1}<n+1$. Can this be possible? We'd better not give the
answer away here, because that will spoil exercise~|knuth-no-ex|.

Recurrence relations involving floors and/or ceilings arise often in
computer science, because algorithms based on the important
technique of ``"divide
and conquer"'' often reduce a problem of size~$n$ to the solution of
similar problems of integer sizes that are fractions of~$n$. For example,
one way to sort $n$~records, if $n>1$, is to divide them into two
"!halving"
approximately equal parts, one of size $\lceil n/2\rceil$ and the
other of size $\lfloor n/2\rfloor$. (Notice, incidentally, that
\begindisplay
n=\lceil n/2\rceil +\lfloor n/2\rfloor \,;
\eqno\eqref|half-split|
\enddisplay
this formula comes in handy rather often.) After each part has been sorted
separately (by the same method, applied recursively), we can merge the
records into their final order by doing at most $n-1$ further comparisons.
Therefore the total number of comparisons performed is at most $f(n)$, where
\begindisplay
\eqalign{f(1)	&=0 \,;\cr
f(n)	&=f(\lceil n/2\rceil )+f(\lfloor n/2\rfloor )+n-1\,,
					\qquad\hbox{for $n > 1$.}\cr}