\documentstyle[12pt,twoside,macpsfig,amssymb]{article}
\input{macros-course}

\begin{document}

\pset{2}{September 13, 1994}{Tuesday, September 20}

{\bf Reading:\ }Maurer \& Ralston: Chapter 2.

\bigskip

Some of the problems ask you to ``verify or falsify'' a proof.  For these
problems, you must either justify the correctness of each step of the
proof, or else locate and explain the error.  It is not sufficient to
merely show that an incorrect proof is indeed wrong.  You must explain
where the bug is.

When you are asked for a proof, you may assume the facts on
Handout~\ref{symbols}, as well as any theorems proved in class.  Do
not assume facts that we have not proved, such as, for example, that
every rational number is representable by a fraction in lowest terms.

Read Handout~\ref{course-information} for the policy on problem sets.

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Prove that every nonempty decreasing sequence of natural numbers is
finite.  That is, show that if $\ang{b_0, b_1, \ldots}$ is a sequence
of natural numbers with $b_0 > b_1 > \cdots$, then the sequence
must have a ``last'' element.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Prove that $\gcd(F_n,F_{n+2})=1$ for all $n\in\naturals$,
where $F_n$ is the $n$th Fibonacci number.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem
Verify or falsify the following proof that for
all real $x\neq 0$, and all natural numbers $n$, we have $x^n=1$.
\begin{quotation}
We use induction on~$n$.  For the base step, observe that if $x \neq
0$, we have $x^0 = 1$.  We now assume that for all $k\leq n$, we have $x^k=1$.
We shall show that $x^{n+1}=1$.  By the induction hypothesis, we have
$x^n = x^{n-1} = 1$.  Hence, it follows that 
\begin{eqnarray*}
x^{n+1} & = & \frac{x^nx^n}{x^{n-1}}\\
& = &\frac{1\times 1}{1}\\
& = & 1\ . 
\end{eqnarray*}
\end{quotation}

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\remove{
\problem 
Verify or falsify the following proof that $\sum_{i=1}^n i$
is less than or equal to some positive constant times~$n$.
\begin{quotation}
The proof is by induction on $n$. 

If $n=1$, then the summation evaluates to $1$, which can be bounded
above by $c$ times~$1$, where $c$ is any constant greater than or
equal to~$1$.

Assume that the statement is true for $n=k$, that is, that
\begin{eqnarray*}
\sum_{i=1}^k i \le ck
\end{eqnarray*}
for some constant~$c\geq 1$.  Adding $k+1$ to both sides, we obtain
\begin{eqnarray*}
\sum_{i=1}^{k+1} i & \le & ck + (k+1)\\
& \le & (c+1)(k+1)\ .
\end{eqnarray*}
Since $c$ is a constant greater than or equal to 1, so is~$c+1$.  For
$n=k+1$, therefore, the sum $\sum_{i=1}^{n} i$ is also bounded above
by a constant times~$n$.  Consequently, by induction this property
holds for every natural number $n\geq 1$.
\end{quotation}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Verify or falsify the following proof that there exists a
natural number $x\leq 1000$ such that $91\divides (x-1)$
and $143\divides (x+1)$.  
\begin{quotation}
Define
\[
S = \set{n\in\naturals : 91\divides (n-1) \mbox{ and } 143\divides (n+1)}\ ,
\]
and let $x = \min(S)$.  Suppose for the purpose of contradiction that
$x\geq 1001$.  Then, consider $y=x-1001$.  We have $91\divides (x-1)$
and $91\divides 1001$, which implies that $91\divides (y-1)$.
Similarly, $143\divides (y+1)$.  Consequently, we must have $y\in S$,
contradicting the minimality of~$x$, and thus, $x\leq 1000$.

\end{quotation}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem You are given an unlimited supply of 4-cent stamps and 7-cent
stamps.  Obviously, with these two denominations, you cannot make
certain amounts of postage, such as 10 cents.  Prove, nevertheless,
that for some $n_0>0$, every amount $n$ of postage such that $n\geq
n_0$ can be made up from 4- and 7-cent stamps.  What is the minimum
value for $n_0$ such that this theorem holds?


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem
Prove that $k! \divides n(n+1)(n+2)\cdots(n+k-1)$ for all $k,n\in\nat$.
(\hint Do a ``double'' induction.)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Consider a thermometer marked in both Centigrade and
Fahrenheit, from $0^\circ {\rm C} = 32^\circ {\rm F}$ to $100^\circ
{\rm C} = 212^\circ {\rm F}$.  What is the closest nonzero distance in
Centigrade and in Fahrenheit between any two degree markings on the
thermometer?  What is the lowest pair of degree markings at which this
closest distance occurs?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem A farmer spent \$100 to buy 100 animals of three different
kinds.  Each cow cost \$4, each pig cost \$2, and sheep cost \$1 for 3
of them.  Assuming that he bought at least one of each kind of animal,
how many of each animal did the farmer buy?  Find all solutions.

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem {\bf The monkey and the coconuts.} This famous problem first
appeared in {\it The Saturday Evening Post} in 1926, in a short story
by Ben Ames Williams, which we paraphrase here:

\begin{quotation}
Five men and a monkey were shipwrecked on a desert island, and they
spent the first day gathering coconuts for food.  They piled them all
up together and went to sleep for the night.  But while they were
asleep, one man woke up, and he thought there might be a row about
dividing the coconuts in the morning, so he decided to take his share
right then.  He divided the coconuts into five piles of equal size
with one coconut left over, which he gave to the monkey.  He hid his
pile and put the other four piles back together into one pile.

By and by through the night, each of the other four men woke up and
did the same thing.  Each man divided the pile he found into five
equal piles with one coconut left over.  He gave the leftover coconut
to the monkey, took one of the piles for himself, and merged the other
four piles back into one pile.  

In the morning, they divided the remaining coconuts, which came out in
five equal shares.  Of course each man must have noticed that there
were coconuts missing, but each man was as guilty as the others, and
so they didn't say anything.  How many coconuts were there in the
beginning?
\end{quotation}

Williams neglected to include the answer in his story, and the 
offices of {\it Post} were subsequently showered
with some 2,000 letters asking about the solution. 
The editor-in-chief of the {\it Post} sent Williams the following 
historic wire, which we now put to you:

\begin{center}
{\sc for the love of mike, how many coconuts?  hell popping around here.}
\end{center}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\end{problems}

\end{document}


