chap3.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

Incidentally, when we're faced with a ``prove or disprove,\qback''
we're usually better off trying first to disprove with a counterexample,
\g "Skepticism" is healthy only to a limited extent. Being skeptical
"!philosophy"
about proofs and programs (particularly your own) will probably keep
your grades healthy and your job fairly secure. But applying that much
skepticism will probably also keep you shut away working all the time,
instead of letting you get out for exercise and relaxation.\par
Too much skepticism is an open invitation to the
state of rigor mortis, where you become so worried about being
correct and rigorous that you never get anything finished.\par
\hfill\dash---A skeptic\g
for two reasons: A disproof is
potentially easier (we need just one counterexample); and
nit-picking arouses our creative juices.
Even if the given assertion is true, our
search for a counterexample
often leads us to a proof, as soon as we see why a counterexample
is impossible. Besides, it's healthy to be skeptical.

If we try to prove that
$\bigl\lfloor \mskip-1mu\sqrt{\lfloor x \rfloor} \bigr\rfloor
	= \lfloor \sqrt{x} \rfloor$ with the help of calculus, we
might start by decomposing~$x$
into its integer and fractional parts $\lfloor x \rfloor + \{x\}
=n+\theta$
and then expanding the square root using the binomial theorem:
$(n + \theta)^{1/2} =
	n^{1/2} + n^{-1/2} \theta / 2
	- n^{-3/2} \theta^2 \!/ 8 + \cdots\,$.
But this approach gets pretty messy.

It's much easier to use the tools we've developed.
Here's a possible strategy:
Somehow strip off the outer floor and square root of
$\bigl\lfloor \mskip-1mu \sqrt{\lfloor x \rfloor} \bigr\rfloor$,
then remove the inner floor,
then add back the outer stuff to get
$\lfloor \sqrt{x} \rfloor$.
OK\null. We let $m =
\smash{\bigl\lfloor \mskip-1mu \sqrt{\lfloor x \rfloor} \bigr\rfloor}$
and invoke~\eq(|alt-f-c-def|\rm(a)),
giving $m \leq \smash{\sqrt{\lfloor x \rfloor}} < m+1$.
That removes the outer floor bracket without losing any information.
Squaring, since all three expressions are nonnegative,
we have $m^2 \leq \lfloor x \rfloor < (m+1)^2 \bex$.
That gets rid of the square root.
Next we remove the floor,
using~\eq(|f-c-in/out|\rm(d)) for the left inequality
and~\eq(|f-c-in/out|\rm(a)) for the right:
$m^2 \leq x < (m+1)^2 \bex$.
It's now a simple matter to retrace our steps,
taking square roots to get $m \leq \sqrt{x} < m+1$
and invoking~\eq(|alt-f-c-def|\rm(a))
 to get $m = \lfloor \sqrt{x} \rfloor$.
Thus $\bigl\lfloor \mskip-1mu \sqrt{\lfloor x \rfloor} \bigr\rfloor = m
= \lfloor \sqrt{x} \rfloor$; the assertion is true. Similarly, we can
prove that
\begindisplay
 \bigl\lceil \mskip-1mu\sqrt{\lceil x \rceil}@ \bigr\rceil
	= \lceil \sqrt{x}\, \rceil \,, \qquad\hbox{real $x \geq 0$.}
\enddisplay

The proof we just found
doesn't rely heavily on the properties of square roots.
A closer look shows that we can generalize the ideas and prove much more:
Let $f(x)$ be any continuous,
monotonically increasing function with the property that
\begindisplay
f(x)={\rm integer}\qquad\Longrightarrow\qquad x={\rm integer}\,.
\enddisplay
(The symbol `$\Longrightarrow$' means ``"implies".\qback'')
"!$\Longrightarrow$ (alphabetize at the end)"
Then we have
\begindisplay
\lfloor f(x)\rfloor =\lfloor f(\lfloor x\rfloor )\rfloor \qquad\hbox{and}\qquad
 \lceil f(x)\rceil =\lceil f(\lceil x\rceil )\rceil ,\,
\eqno
\enddisplay
whenever $f(x)$, $f(\lfloor x\rfloor )$, and $f(\lceil x\rceil )$ are defined.
\g\vskip-35pt(This observation
 was made by R.~J. "McEliece" when he was an undergrad.)\g
Let's prove this general property for ceilings, since we did floors
earlier and since the proof for floors is almost the same. If $x=\lceil
x\rceil $, there's nothing to prove. Otherwise $x<\lceil x\rceil $, and
$f(x)<f(\lceil x\rceil )$ since $f$~is increasing.  Hence $\lceil
f(x)\rceil \le\lceil f(\lceil x\rceil )\rceil $,
since $\lceil \,\rceil$~is nondecreasing.
If $\lceil f(x)\rceil <\lceil f(\lceil x\rceil )\rceil $,
 there must be a number~$y$ such that $x\le y<\lceil x\rceil $
and $f(y)=\lceil f(x)\rceil $,
 since $f$~is continuous. This~$y$ is an integer, because of $f@$'s
special property. But there cannot be an integer strictly between
$x$ and~$\lceil x\rceil $. This contradiction implies that we must have
$\lceil f(x)\rceil =\lceil f(\lceil x\rceil )\rceil $.

An important special case of this theorem is worth noting explicitly:
\begindisplay
\left\lfloor  x+m\over n\right\rfloor =\left\lfloor \lfloor x\rfloor +m\over n\right\rfloor \qquad\hbox{and}\qquad
\left\lceil x+m\over n\right\rceil =\left\lceil \lceil x\rceil
 +m\over n\right\rceil \,,
\eqno\eqref|rational-in/out|
\enddisplay
\looseness=-1
if $m$ and $n$ are integers and the denominator $n$ is positive.
For example, let $m=0$; we have
$\bigl\lfloor \bigl\lfloor \lfloor x/10\rfloor /10
\bigr\rfloor /10\bigr\rfloor =\lfloor x/1000\rfloor $.
Dividing thrice by~$10$ and throwing off digits is the same as
dividing by~$1000$ and tossing the remainder.

Let's try now to prove or disprove another statement:
\begindisplay
 \bigl\lceil \mskip-1mu\sqrt{\lfloor x \rfloor}\mskip2mu \bigr\rceil
	\buildrel?\over= \lceil \sqrt{x}\, \rceil \,, \qquad\hbox{real $x \geq 0$.}
\enddisplay
This works when $x=\pi$ and $x=e$, but it fails when $x=\phi$; so we know
that it isn't true in general.

Before going any further, let's digress a minute to discuss different
"levels" of problems that might appear in books about mathematics:
"!philosophy" "!problems, levels of" "!exercises, levels of"

\def\level#1. {\smallbreak\noindent\hbox{\subsubtitle Level #1. }}
\level 1. Given an explicit object $x$ and an explicit property~$P(x)$,
{\it prove\/} that $P(x)$ is true. For example, ``Prove that
$\lfloor \pi\rfloor =3$.'' Here the problem involves finding a proof of some
purported fact.

\level 2. Given an explicit set $X$ and an explicit property~$P(x)$,
prove that $P(x)$ is true {\it for all\/} $x\in X$. For example,
``Prove that $\lfloor x\rfloor \le x$ for all real $x$.''
Again the problem involves
finding a proof, but the proof this time must be general. We're doing
algebra, not just arithmetic.

\level 3. Given an explicit set $X$ and an explicit property~$P(x)$,
prove {\it or disprove\/} that $P(x)$ is true for all $x\in X$.
\g In my other texts ``prove or disprove''
seems to mean the same as ``prove,\qback'' about
99.44\% of the time; but not in~this~book.\g
For example, ``Prove or disprove that
$\bigl\lceil \mskip-1mu\sqrt{\lfloor x \rfloor}\mskip2mu \bigr\rceil
	= \lceil \sqrt{x}\,\rceil$ for all real $x \geq 0$.''
Here there's an additional level of uncertainty;
the outcome might go either way. This is closer to the real situation a
mathematician constantly faces: Assertions that get into
books tend to be true, but
new things have to be looked at with a jaundiced eye. If the statement
is false, our job is to find a counterexample. If the statement is true,
we must find a proof as in level~2.

\level 4. Given an explicit set $X$ and an explicit property~$P(x)$,
find a {\it "necessary and sufficient condition"\/} $Q(x)$ that $P(x)$
is true.
 For example, ``Find a necessary and sufficient condition
that $\lfloor x\rfloor \ge\lceil x\rceil $.''
The problem is to find $Q$ such that $P(x)\iff Q(x)$.
 Of course, there's always a trivial answer;
we can take $Q(x)=P(x)$. But the implied requirement is to find a condition
that's as simple as possible.
\g But no simpler.\par\hfill\dash---A. "Einstein"\g
Creativity is required to discover a simple condition that will work.
(For example, in this case, ``$\lfloor x\rfloor \ge\lceil x\rceil \iff x$
 is an integer.'')
The extra element of discovery needed to find $Q(x)$ makes this sort of
problem more difficult, but it's more typical of what mathematicians must do
in the ``real world.\qback'' Finally, of course, a proof must be given
that $P(x)$ is true if and only if $Q(x)$ is true.

\level 5. Given an explicit set $X$, find {\it an interesting property\/}
$P(x)$ of its elements. Now we're in the scary domain of pure research,
where students might think that total chaos reigns. This is real
mathematics. Authors of textbooks rarely dare to pose level 5 problems.

\smallbreak
End of digression. But let's convert the last question we looked at
 from level~3 to
level~4: What is a necessary and sufficient condition that
$\bigl\lceil \mskip-1mu\sqrt{\lfloor x \rfloor}\mskip2mu \bigr\rceil
	= \lceil \sqrt{x}\,\rceil$?
We have observed that equality holds when $x=3.142$ but not when $x=1.618$;
further experimentation shows that it fails also when $x$ is between $9$
and~$10$. Oho.
\g Home of the Toledo~Mudhens.\g "!baseball"
 Yes. We see that bad cases occur whenever $m^2<x<m^2+1$,
since this gives $m$ on the left and $m+1$ on the right.
In all other cases where $\sqrt x$ is defined, namely when $x=0$ or
$m^2+1\le x\le(m+1)^2$, we get equality.
The following statement is therefore necessary and sufficient
for equality: Either $x$ is an integer or $\sqrt{\lfloor x\rfloor}$~isn't.

\smallbreak
For our next problem let's consider a handy new notation, suggested by
C.\thinspace A.\thinspace R. "Hoare" and
Lyle "Ramshaw", for "intervals" of the real line:
\tabref|nn:interval|
$[\alpha\dts \beta ]$ denotes the set of real numbers~$x$ such that
$\alpha \leq x \leq \beta$.
This set is called a {\it "closed interval"\/} because
it contains both endpoints $\alpha$~and~$\beta$.
The interval containing neither endpoint, denoted by $(\alpha\dts \beta)$,
consists of all~$x$ such that $\alpha < x < \beta$; this
is called an {\it "open interval"}.
And the intervals $[\alpha\dts \beta)$ and $(\alpha\dts \beta ]$,
which contain just one endpoint, are defined similarly and called
{\it "half-open"}. \g(Or, by pessimists, half-closed.)\g

How many integers are contained in such intervals?
The half-open intervals are easier, so we start with them.
In fact half-open intervals are almost always
nicer than open or closed intervals.
For example, they're additive\dash---we can combine the half-open intervals
$[\alpha\dts\beta)$ and $[\beta\dts\gamma)$ to form
the half-open interval $[\alpha\dts\gamma)$.
This wouldn't work with open intervals
because the point~$\beta$ would be excluded,
and it could cause problems with closed intervals
because $\beta$~would be included twice.

Back to our problem. The answer
is easy if $\alpha$ and~$\beta$ are integers: Then
$[\alpha\dts\beta)$ contains the $\beta - \alpha$ integers
$\alpha$,~$\alpha+1$, \dots,~$\beta-1$, assuming that $\alpha \leq \beta$.
Similarly $(\alpha\dts\beta@]$
 contains $\beta - \alpha$ integers in such a case.
But our problem is harder, because $\alpha$~and~$\beta$ are arbitrary
reals.
We can convert it to the easier problem, though,
since
\begindisplay
&\alpha \leq n < \beta\qquad\iff\qquad
\lceil \alpha\rceil \leq n < \lceil\beta\rceil \,,\cr
&\alpha < n \leq \beta\qquad\iff\qquad
	 \lfloor\alpha\rfloor < n \leq \lfloor\beta\rfloor \,,\cr
\enddisplay
when $n$ is an integer, according to~\eq(|f-c-in/out|).
The intervals on the right have integer endpoints and contain the
same number of integers as those on the left, which have real endpoints.
So the interval $[\alpha\dts\beta)$ contains exactly
$\lceil\beta\rceil - \lceil\alpha\rceil$ integers,
and $(\alpha\dts\beta@]$ contains
$\lfloor\beta\rfloor - \lfloor\alpha\rfloor$.
This is a case where we actually want to introduce floor or ceiling brackets,
instead of getting rid of them.

By the way, there's a mnemonic for remembering
which case uses floors and which uses ceilings:
Half-open intervals that include the left endpoint but not the right
(such as $0 \leq \theta < 1$) are slightly more common than those that include
the right endpoint but not the left;
\g Just like we can remember the date of "Columbus"'s departure by
singing, ``In fourteen hundred and ninety-three/ Columbus sailed the
deep blue sea.''\g
and floors are slightly more common than ceilings.
So by "Murphy's Law", the correct rule is
the opposite of what we'd expect\dash---ceilings for
$[\alpha\dts\beta)$ and floors for $(\alpha\dts\beta@]$.

Similar analyses show that the closed interval $[\alpha\dts\beta@]$ contains
exactly $\lfloor\beta\rfloor - \lceil\alpha\rceil + 1$ integers
and that the open interval $(\alpha\dts\beta)$ contains
$\lceil\beta\rceil - \lfloor\alpha\rfloor - 1$;
but we place the additional restriction $\alpha \neq \beta$
on the latter so that the formula won't ever embarrass us
by claiming that an empty interval $(\alpha\dts\alpha)$ contains
a total of $-1$~integers.
To summarize, we've deduced the following facts:
\begindisplay
\vcenter{\halign{\hfil$#$\hfil\quad&&\quad\hfil$#$\hfil\quad\cr
\hidewidth\hbox{interval}\hidewidth
 & \hbox{integers contained} & \hbox{restrictions} \cr
\noalign{\vskip2pt}
[\alpha\dts\beta@] & \lfloor\beta\rfloor - \lceil\alpha\rceil + 1 &
						\alpha \leq \beta \,, \cr
[\alpha\dts\beta) & \lceil\beta\rceil - \lceil\alpha\rceil	&
						\alpha \leq \beta \,, \cr
(\alpha\dts\beta@] & \lfloor\beta\rfloor - \lfloor\alpha\rfloor	&
						\alpha \leq \beta \,, \cr
(\alpha\dts\beta) & \lceil\beta\rceil - \lfloor\alpha\rfloor - 1	&
						\alpha < \beta \,. \cr}}
\eqno\eqref|ints-in-interval|
\enddisplay

Now here's a problem we can't refuse.
The "Concrete Math Club" has a casino (open only to purchasers of this book)
"!greed"
in which there's a "roulette" "wheel" with one thousand slots,
 numbered $1$~to~$1000$.
If the number~$n$ that comes up on a spin
is divisible by the floor of its cube root,
that is, if
\begindisplay
 \lfloor \mskip-2mu \root3\of{n} \rfloor \bigm\divides n \,,
\enddisplay
then it's a winner and the house pays us \$5;
otherwise it's a loser and we must pay~\$1.
(The notation $a\divides b$, read ``$a$~divides~$b$,\qback''
means that $b$~is an exact multiple of~$a$; Chapter~4 investigates
this relation carefully.)
\g (A poll of the class at this point showed that 28~students thought it was a
bad idea to play, 13~wanted to gamble, and the rest were too confused
to answer.)\smallskip
(So we hit them with the Concrete Math Club.)\g
Can we expect to make money if we play this game?

We can compute the average winnings\dash---%
that is, the amount we'll win (or lose) per play\dash---%