%%SOLSET1-PROBS.TEX  6.042 F01

\begin{problems}

\problem Identify \emph{precisely} what the bugs are in each of the False
proofs 1--5 in the False Proofs Handout 4.

\begin{enumerate}

\item \label{sqrt uv}
\begin{eqnarray*}
1 & = & \sqrt{1} \\
& = & \sqrt{(-1)(-1)} \\
& = & \sqrt{-1} \sqrt{-1} \\
& = & \sqrt{-1}^2 \\
& = & -1.\\
\mbox{So, }1 & = & -1!
\end{eqnarray*}
See Lecture 1 notes for an explanation.

\solution{
The step $\sqrt{(-1)(-1)} = \sqrt{-1} \sqrt{-1}$ is invalid.
Generally, $\sqrt{u v} = \sqrt{u} \sqrt{v}$ does not hold over complex
numbers.
}

\item\label{log10}
\begin{align*}
    3 &> 2 \\
    3 \log_{10} (1/2) &> 2 \log_{10}(1/2) \\
    \log_{10} (1/2)^3 &> \log_{10} (1/2)^2 \\
    (1/2)^3 &> (1/2)^2 \\
    \mbox{Therefore, } 1/8 &> 1/4!
\end{align*}

\solution{$\log x < 0$ for $0<x<1$, so since both sides of the inequality
``$3 > 2$'' are being multiplied by the negative quantity
$\log_{10}(1/2)$, the inequality in the second line should have been the
reverse of the first line, that is, $<$ instead of $>$.}


\item\label{cents}
You are richer than you think:
\[1 \cent = \$0.01 = (\$0.1)^2 = (10\cent)^2 = \$1.\]

\solution{$\$0.01 = \$(0.1)^2 \neq (\$0.1)^2$ because the units $\$^2$ and
$\$$ don't match (just as in physics the difference between $sec^2$ and
$sec$ indicates the difference between acceleration and velocity).}

\item\label{millions} Consider the following scheme to make millions.
Obtain a slab of gold $10'' \times 11'' \times 1''$.  Score it diagonally
as shown in the Figure attached.  Then cut out two little one-inch
triangles at the corners.  These triangles are the profit.  Finally, slide
the two slabs together again and note that the rectangle is now $11''
\times 10'' \times 1''$---the same size as it was before we removed the
small triangles.  By repeating the process, we can produce an unlimited
supply of gold!

(This illustrates why ``proof by diagram'' is mathematically suspicious.)

\solution{The picture makes the little triangles look like right
triangles, but they aren't.  So when the two large pieces left after the
little triangles are removed are slid together, they do not form a
rectangle, which means the resulting shape is not the same as the original
figure.}


\item
\textbf{Claim}: Every polynomial $p(x) = ax^2 + bx +c$ over $\complex$
(the complex numbers) has two roots.

\begin{proof}
Using the usual formulas for the roots of a quadratic, let
\begin{eqnarray*}
r_1 & ::= & \frac{-b + \sqrt{D}}{2a}, \mbox{ and} \\
r_2 & ::= & \frac{-b - \sqrt{D}}{2a}, \mbox{ where}\\
D & ::= & b^2-4ac.
\end{eqnarray*}

To verify that $r_1$ is a root, note that
\begin{eqnarray*}
a{r_1}^2 & = &  a({\frac{-b +\sqrt{d}}{2a}})^2\\
& = & a\frac{b^2 -2b\sqrt{D} + D}{4a^2}\\
& = & \frac{b^2 -2b\sqrt{D} + b^2 -4ac}{4a}\\
& = & \frac{2b^2 -2b\sqrt{D} -4ac}{4a}\\
& = & \frac{b^2 -b\sqrt{D} -2ac}{2a}
\end{eqnarray*}
and
\begin{eqnarray*}
br_1 & = & b\frac{-b+\sqrt{D}}{2a}\\
 & = & \frac{-b^2+b\sqrt{D}}{2a}
\end{eqnarray*}
so
\begin{eqnarray*}
p(r_1) &=&{r_1}^2 + br_1 + c\\
& = & \frac{b^2 -b\sqrt{d} -2ac}{2a} + \frac{-b^2+b\sqrt{d}}{2a} +c\\
 & = & \frac{-2ac}{2a} + c = - c + c = 0,
\end{eqnarray*}
as claimed.  A similar calculation confirms that $p(r_2)=0$.
\end{proof}

Sounds good, but the claim is false.  Find the counterexamples and then
restate the claim so it is correct.

\solution{
The polynomial $0x^2 + 0x + 1$ has no roots.  The proof failed for this
case since it divides by $a$, which is unsound  when $a=0$.

The polynomial $x^2 + 2x + 1$ has only one root.  For $a\neq 0$, the
algebra is ok, but the proof assumes that $r_1 \neq r_2$, which will be
false when $D = 0$.

The proof is correct for polynomials with $a\neq 0 \neq D$ (even though
when $D < 0$, the meaning of $\sqrt{D}$ is ambiguous -- see False
proof~\ref{sqrt uv} above).  So these two conditions are required to make
the claim correct.}

\end{enumerate}

\problem Generalize the proof that $\sqrt{2}$ is irrational, e.g., how
about $\sqrt[3]{2}$?

\solution{From S99 Tutorial 1 Notes:

Here's one of many generalizations of the proof from lecture that
$\sqrt{2}$ is irrational.

\begin{lemma}
Let the coefficients of the polynomial $a_0+a_1x+a_2x^2+\ldots+x^n$ be
integers.  Then any real root of the polynomial is either integral or
irrational.
\end{lemma}

Notice that this Lemma directly implies that $\sqrt{2}$ is irrational:
$x^2 - 2$ has no integer root because 2 is not a perfect square, so the
real roots, namely, $\pm\sqrt{2}$, must be irrational.  Similarly, if $m
\in \naturals$ is not the $k$th power of an integer, then $x^k - m$ has no
integer roots, so $\sqrt[k]{m}$ will be irrational.

\begin{proof}

Let $r\in \reals$ be a root of the polynomial, that is,
\[a_0+a_1r+a_2r^2+\ldots+r^n = 0.\]
There are three cases for $r$: it is either integral, irrational, or the
ratio of two integers with no common divisors where the denominator is
greater than one.  We want to eliminate the last case.

Assume that $r = s/t$ for integers $s$ and $t$ which have no common
divisors and such that $t >1$.  So $t$ will have a prime divisor, $p$.

Substituting $s/t$ for $r$ and multiplying both sides of the above
equation by $t^n$ yields:
\[ a_0t^n+a_1st^{n-1}+a_2s^2t^{n-2}+\ldots+st^{n-1}+s^n = 0.\]

\[ a_0t^n+a_1st^{n-1}+a_2s^2t^{n-2}+\ldots+s^{n-1}t = -s^n.\]

Then $p$ divides each term of the lefthand side of the above equation, and
therefore also divides the righthand side, viz., $p \mid -s^n$.  But this
means that $p$ must divide also $s$.  So $p$ is a common divisor of $s$
and $t$, contradicting our choice of $s$ and $t$.

\end{proof}

Note that we are using an ``obvious'' fact about natural numbers: if a
prime $p$  divides $s^n$ for integer $n \geq 0$, then $p$ divides $s$.

\emph{Class exercise}: What's a quick counterexample if $p$ is not prime?
\emph{Answer}: $9 \mid 3^3$ but \emph{not} $9 \mid 3$.

Actually this fact is more ``familiar'' than completely obvious.  How
would you justify this fact to a friend who didn't see why it was true?

\begin{proof}
Write $s$ as a product of prime powers $p_1^{k_1} p_2^{k_2}~ \cdots
~p_t^{k_l}$.  So $s^n ~=~ p_1^{n k_1} p_2^{n k_2}~ \cdots ~p_t^{n k_l}$.
But factorization of a number into primes is unique (this is the
Fundamental Theorem of Arithmetic, which will be examined more fully next
week).  So if $p$ divides $s^n$, it has to equal one of the $p_j$'s, and
therefore, $p$ also divides $s$.
\end{proof}
}

\end{problems}
