%\magnification=\magstephalf
%\nopagenumbers
%\hsize 18true cm
\input mymacros
\input amssym.def
\def\mathcal#1{{\cal #1}}
\def\lto{\longrightarrow}
\def\iff{\longleftrightarrow}
\def\rr{{\Bbb R}}
\def\nn{{\Bbb N}}
\def\zz{{\Bbb Z}}
\def\rrr{{\mymagtwobf R}}
\def\nnn{{\mymagtwobf N}}
\xdef\startexpage{
\eject
\null
\vskip 1cm
\centerline{\hbox to 6cm{\hrulefill}\ \ \ \hbox to 6cm{\hrulefill}}
\centerline{\hbox to 6cm{\hfill Student's name\hfill}\ \ \ \hbox to
6cm{\hfill Student's I.D. number\hfill}}

\vskip 0.5cm
}
\def\boxoto{\enspace\lower5pt\vbox{\hrule height2.6pt depth-2pt\hbox{\vrule width0.6pt\kern1pt\vbox{\kern1pt\phantom{O}\kern1pt}\kern1.5pt\vrule width0.6pt}\hrule height2.6pt depth-2pt}}
\def\plttr#1{\hbox to 9cm{#1\enspace\hrulefill} \boxoto\ True \ \boxoto\  False\ }
\def\tra{\vskip 0.05cm Translation:
\vskip 1.5cm}
\def\pltt#1{\hbox to 8cm{#1\hfill\enspace is$\,\,\,$a$\,\,\,$}
\boxoto$\,$Tautology \boxoto$\,$Contradiction\ \boxoto$\,$Contingency.}
\def\lr{\leftrightarrow}
\def\plcor{\boxoto\ Correct \ \ \ \boxoto\  Incorrect.}
\def\plhas{\boxoto\ Has a solution \ \ \ \boxoto\  Does not have a solution.}
\raggedbottom
\null
\vskip 1.6cm
\centerline{{\mymagtwobf MATHEMATICS 300}}

\bigbreak
\centerline{{\mymagtwoit INSTRUCTOR: H\'ector J.  Sussmann}}

\bigbreak
\centerline{{\mymagonebf INTRODUCTION TO MATHEMATICAL REASONING --- FALL 2002}}

\bigbreak
\centerline{{\mymagonebf  SOLUTIONS TO THE PROBLEMS OF THE
FIRST MIDTERM EXAM.}}

\vskip 0.1in

{{\bf 1.}} \ i.  Define ``prime number.''

\medbreak
\itemitem{}  {\bf ANSWER.} A {\it prime number}  is an integer $p$
such that $p>1$ and there do not exist integers $x$, $y$ such that $x>1$,
$y>1$, and $p=x.y$. (Other ways to say it: (a)~A {\it prime number} is an
integer $p$ such that $p>1$ and there does not exist an integer $x$ such
that $1<x<p$ and $x$ divides $p$; (b)~A {\it prime number} is an integer
$p$ such that $p>1$ and the only positive divisors of $p$ are $1$ and $p$;
(c)~A {\it prime number} is a positive integer $p$ that has exactly two
positive divisors; (d)~Let $p$ be an integer. We say that $p$ is {\it
prime} if $p>1$ and there does not exist an integer $x$ such that $1<x<p$
and $x$ divides $p$; (e)~Let $p$ be an integer. We say that $p$ is {\it
prime} if $p>1$ and the only positive divisors of $p$ are $1$ and $p$.)

\medbreak
\itemitem{ii.}  Define ``tautology.''

\medbreak
\itemitem{}  {\bf ANSWER.} A {\it tautology}  is a Boolean expression 
$E$ that has the value True for all possible choices of truth values of
the propositional variables that occur in $E$. (Note: you could have said 
``propositional form,'' or ``sentence form,'' or ``statement form,''
instead of ``Boolean expression,'' and that would still have been O.K. 
But if you said something like ``A {\it tautology}  is a true statement,''
then that is wrong.) 

\medbreak
\itemitem{iii.}  Define ``contradiction.''

\medbreak
\itemitem{}  {\bf ANSWER.} A {\it contradiction}  is a Boolean expression 
$E$ that has the value False for all possible choices of truth values of
the propositional variables that occur in $E$. 

\itemitem{iv.}  Define ``greatest common divisor.''

\medbreak
\itemitem{}  {\bf ANSWER.} Let $a$, $b$ be integers. 
A {\it greatest common divisor} of $a$ and $b$ is a positive integer
$g$ such that (a)~$g$ divides $a$, (b)~$g$ divides $b$, and (c)~if 
$g'$ is any integer that divides $a$ and $b$, then $g'\le g$.

\bigbreak

\item{{\bf 2.}} Prove each of the following:

\medbreak 
\itemitem{(i)} For every $n\in\nn$,
$1+3+3^2+\cdots+3^n={3^{n+1}-1\over 2}\,.$

\medbreak
\itemitem{}  {\bf PROOF.} Let $p(n)$ be the sentence
``$1+3+3^2+\cdots+3^n={3^{n+1}-1\over 2}\,\,$''.  We want to prove that
$\forall n\in\nn,p(n)$. Suppose this was not true. Then there 
would exist an $n\in\nn$ such that $\neg\,p(n)$. The Well Ordering
Principle then implies that there 
exists  a smallest  $n\in\nn$ such that $\neg\,p(n)$. Pick such an $n$
and call it $\nu$. Then we know the following things about 
$\nu$: (a)~$\nu\in\nn$, (b)~the sentence
``$1+3+3^2+\cdots+3^\nu={3^{\nu}-1\over 2}\,\,$''
is false, (b)~the sentence $p(n)$ (that is, 
``$1+3+3^2+\cdots+3^n={3^{n+1}-1\over 2}\,\,$'')
is true for all $n\in\nn$ such that $n<\nu$. 

\itemitem{}
It follows that $\nu\neq 0$, since the formula $p(0)$ is true. 
So $\nu>0$, and then $\nu-1\in\nn$. But then $p(n)$ is true
if we plug in  $\nu-1$ for $n$. That is,
$1+3+3^2+\cdots+3^{\nu-1}={3^{\nu}-1\over 2}\,.$
Let us add $3^{\nu}$ to both sides. We get 
$1+3+3^2+\cdots+3^{\nu-1}+3^{\nu}=
{3^{\nu}-1\over 2}+3^{\nu}\,.$
But 
$$
{3^{\nu}-1\over 2}+3^{\nu}=
{3^{\nu}-1\over 2}+{2.3^{\nu}\over 2}=
{3^{\nu}-1+2.3^{\nu}\over 2}=
{3.3^{\nu}-1\over 2}={3^{\nu+1}-1\over 2}\,.
$$
Therefore $1+3+3^2+\cdots+3^{\nu}=
{3^{\nu+1}-1\over 2}\,.$
So we have shown that $p(\nu)$ is true. This contradicts the fact 
that $p(\nu)$ is false. So the assumption that $\forall n\in\nn,p(n)$
is false has led us to a contradiction. So $\forall n\in\nn,p(n)$ is 
true.\  \ {\bf END OF PROOF.} 


\medbreak 
\itemitem{(ii)} For every $n\in\nn$ and every $a\in\rr$ such that 
$a\ge 0$, 
$$
(1+a)^n\ge 1+na\,.
$$

\medbreak
\itemitem{}  {\bf PROOF.} Let $a$ be an arbitrary real number such 
$a\ge 0$. Let $p(n)$ be the sentence
``$(1+a)^n\ge 1+na\,\,$''.    We want to prove that
$\forall n\in\nn,p(n)$. Suppose this was not true. Then there 
would exist an $n\in\nn$ such that $\neg\,p(n)$. The Well Ordering
Principle then implies that there 
exists  a smallest  $n\in\nn$ such that $\neg\,p(n)$. Pick such an $n$
and call it $\omega$. Then we know the following things about 
$\omega$: (a)~$\omega\in\nn$, (b)~the sentence
``$(1+a)^\omega\ge 1+\omega.a\,\,$''
is false, (b)~the sentence $p(n)$ (that is, 
``$(1+a)^n\ge 1+na\,\,$'')
is true for all $n\in\nn$ such that $n<\omega$. 

\itemitem{}
It follows that $\omega\neq 0$, since the formula $p(0)$ is true. 
So $\omega>0$, and then $\omega-1\in\nn$. But then $p(n)$ is true
if we plug in  $\omega-1$ for $n$. That is,
$$
(1+a)^{\omega-1}\ge 1+(\omega-1).a\,\,\,.
$$
Let us multiply both sides by $1+a$. We get 
$$
(1+a)^{\omega}\ge(1+(\omega-1).a).(1+a)\,\,\,.
$$
But 
$$
(1+(\omega-1).a).(1+a)=1+(\omega-1).a+a+(\omega-1).a^2=
1+\omega.a+(\omega-1).a^2\ge 1+\omega.a\,.
$$
Therefore 
$$
(1+a)^{\omega}\ge 1+\omega.a\,.
$$
So we have shown that $p(\omega)$ is true. This contradicts the fact 
that $p(\omega	)$ is false. So the assumption that $\forall n\in\nn,p(n)$
is false has led us to a contradiction. So $\forall n\in\nn,p(n)$ is 
true.\  \ {\bf END OF PROOF.} 

\bigbreak
{\bf 3.}\ (i) Prove: 
$\Big((\exists x, x{\rm\,\,is\,\,a\,\,borogove})\wedge 
(\exists x,x{\rm \,\,is\,\,mimsy})\Big)
\lto\Big(\exists x, (x{\rm\,\,is\,\,a\,\,borogove}\wedge 
x{\rm \,\,is\,\,mimsy})\Big)\,.$

\medbreak
\itemitem{}  {\bf ANSWER.} This statement cannot be proved, because
it does not have to be true. For example, if the universe of discourse
consists of all U.S. senators, ``is a borogove'' stands for
``is a Republican'', and ``is mimsy'' stands for
``is a Democrat'', then the premiss 
$(\exists x, x{\rm\,\,is\,\,a\,\,borogove})\wedge 
(\exists x,x{\rm \,\,is\,\,mimsy})$ says ``some Senators
are Republicans and some senators are Democrats'', and the 
conclusion says ``some senators are both Republican and Democrat''.
So the premiss is true but the conclusion is not. Therefore
the implication is false. 

\medbreak
\itemitem{(ii)} Prove: 
$\Big((\exists x, x{\rm\,\,is\,\,a\,\,borogove})\vee 
(\exists x,x{\rm \,\,is\,\,mimsy})\Big)
\lto\Big(\exists x, (x{\rm\,\,is\,\,a\,\,borogove}\vee 
x{\rm \,\,is\,\,mimsy})\Big)\,.$

\medbreak
\itemitem{}  {\bf PROOF.} Assume 
$(\exists x, x{\rm\,\,is\,\,a\,\,borogove})\vee 
(\exists x,x{\rm \,\,is\,\,mimsy})$. We want to prove the statement that
$\exists x, (x{\rm\,\,is\,\,a\,\,borogove}\vee 
x{\rm \,\,is\,\,mimsy})$. 

\itemitem{} Since $(\exists x, x{\rm\,\,is\,\,a\,\,borogove})\vee 
(\exists x,x{\rm \,\,is\,\,mimsy})$, we will consider separately two cases:
Case 1 is when $\exists x, x{\rm\,\,is\,\,a\,\,borogove})$, and 
Case 2 is when $\exists x, x{\rm\,\,is\,\,mimsy})$.  

\itemitem{} In Case 1, since
there exists a borogove, we can pick one and call it anyway we like, 
e.g. ``Boris''. So Boris is a Borogove. Therefore Boris is a 
borogove$\vee$Boris is mimsy. So 
$\exists x, (x{\rm\,\,is\,\,a\,\,borogove}\vee 
x{\rm \,\,is\,\,mimsy})$. 

\itemitem{} In Case 2, since
there exists something that is mimsy, we can pick one such thing and call
it anyway we like, e.g. ``Mimi''. So Mimi is mimsy. Therefore Mimi
is a borogove$\vee$ Mimi is mimsy. So 
$\exists x, (x{\rm\,\,is\,\,a\,\,borogove}\vee 
x{\rm \,\,is\,\,mimsy})$. 

\itemitem{} We have therefore established the desired conclusion,
that $\exists x, (x{\rm\,\,is\,\,a\,\,borogove}\vee 
x{\rm \,\,is\,\,mimsy})$, in both cases. true.\  \ {\bf END OF PROOF.} 

\medbreak
\itemitem{(iii)} Prove: $\Big((\forall x, x{\rm\,\,is\,\,a\,\,borogove})\lto
(\forall x,x{\rm \,\,is\,\,mimsy})\Big)
\lto\Big(\forall x, (x{\rm\,\,is\,\,a\,\,borogove}\lto 
x{\rm \,\,is\,\,mimsy})\Big)\,.$

\medbreak
\itemitem{}  {\bf ANSWER.} This statement cannot be proved, because
it does not have to be true. For example, if the universe of discourse
consists of all U.S. Senators, ``is a borogove'' stands for
``is a Republican'', and ``is mimsy'' stands for
``is a Democrat'', then the premiss 
$\forall x, x{\rm\,\,is\,\,a\,\,borogove})\lto
(\forall x,x{\rm \,\,is\,\,mimsy})$ says  ``if all senators are 
Republicans then all senators are Democrats'', which is clearly true
because it is an implication whose premiss (``all senators are 
Republicans'') is false. On the other hand, the 
conclusion says ``every senator who is a Republican 
is a Democrat'', which is clearly false since, for example,
Senator Lott is a Republican and is not a Democrat.
So the premiss is true but the conclusion is not. Therefore
the implication is false. 

\bigbreak
\item{{\bf 4.}} A {\it telephone number} is a sequence of ten digits
such that the first digit is neither a $0$ nor a $1$. (Recall
that a {\it digit} is a member of the set $\{0,1,2,3,4,5,6,7,8,9\}$.) 


\medbreak
\itemitem{I.} How many telephone numbers are there that 
contain exactly one even digit (and, of course, nine odd digits)?

\medbreak
\itemitem{}  {\bf ANSWER.} To produce a telephone number of the desired
kind, we can use the following sequence of steps, each one of which
involves a choice: in Step 1, we choose which of the ten locations
for our digits will be the one where we will put the even digit;
then in Step 2 we choose which digit to put in the leftmost 
location, 
then in Step 3 we choose which digit to put in the second 
location from the left, and so on until in Step 11 
we choose which digit to put in the rightmost 
location. For Step 1 we have ten choices; for Step 2 we have four, 
and for each of the remaining nine steps we have five choices.

\itemitem{}  
So the total number of phone numbers of the desired kind is
$$
N=10\times 4\times 5^9\,.
$$
We can rewrite this as 
$$
N={4\over 5}\times(10\times 5^{10}=
{{4\over 5}\times 10^{11}\over 2^{10}} 
={{4\over 5}\times 10^{11}\over 1024} 
={{4\over 5}\times 10^{8}\over 1.024}={{8\over 10}\times 10^{8}\over 1.024}=
{8\times 10^{7}\over 1.024}={80,000,000\over 1.024}\,.
$$
So $N$ is approximately $80,000,000$, but is in fact a little smaller.


\itemitem{II.} Is the number of part I larger or smaller that $80$ million
(that is, than $80,000,000$)$\,$?

\medbreak
\itemitem{}  {\bf ANSWER.} As explained in the answer to part I, the number
is smaller than $80$ million. 

\bigbreak
\item{{\bf 5.}} Let $S=\{ 1,3,5,6,8,10\}\,.$
\medbreak
\itemitem{(i)} Prove: $\forall x\in S,\exists y\in S,x+y=11$.

\medbreak
\itemitem{}  {\bf PROOF.} We will show that 
``$\exists y\in S,x+y=11$'' is true for every $x\in S$. If $x=1$, then
``$\exists y\in S,x+y=11$'' is true because we can take $y=10$.  If $x=3$,
then ``$\exists y\in S,x+y=11$'' is true because we can take $y=8$.  If
$x=5$, then ``$\exists y\in S,x+y=11$'' is true because we can take $y=6$.
If $x=6$, then ``$\exists y\in S,x+y=11$'' is true because we can take
$y=5$.  If $x=8$, then ``$\exists y\in S,x+y=11$'' is true because we can
take $y=3$.  If $x=10$, then ``$\exists y\in S,x+y=11$'' is true because we
can take $y=3$.\ \ {\bf END OF PROOF.} 

\medbreak
\itemitem{(ii)} Prove: $\exists y\in S,\forall x\in S,x+y=11$.

\medbreak
\itemitem{}  {\bf ANSWER.} This cannot be proved because it is false. 
To prove that the statement is false, we show that there exists no $y\in S$
for which $\forall x\in S,x+y=11$.  To prove this, we show that no matter
what $y$ might be, the statetent 
``$\forall x\in S,x+y=11$'' is false. Let $y$ be an arbitrary member 
of $S$. Suppose 
``$\forall x\in S,x+y=11$'' was true. Then we can plug in $x=1$ and
conclude that $1+y=11$, and also $x=3$ and conclude that 
$3+y=11$. Subtracting, we get $2=0$, which is false. So the assumption 
that $\forall x\in S,x+y=11$ has led us to a false conclusion.
Therefore $\forall x\in S,x+y=11$ is false. 

\itemitem{(iii)} Prove: $\forall x\in S,(x>12\lto x=x+1)$.

\medbreak
\itemitem{}  {\bf PROOF.} Let $x\in S$ be arbitrary. Then 
``$x>12$'' is false. So $x>12\lto x=x+1$ is true.\ \ {\bf END OF PROOF.} 

\bigbreak
\item{{\bf 6.}} Find the gratest common divisor of 
$72$ and $114$
and express it as an integer linear combination of  $72$ and $114$.

\medbreak
\itemitem{}  {\bf SOLUTION.} The greatest common divisor (gcd) 
of $72$ and $114$ is $6$. Indeed, $6$ divides $72$ and $114$. Furthermore,
it can easily be proved that every integer $n$ that divides $72$ and $114$ must
divide $6$, from which it follows that $n\le 6$. This can be shown in
various ways, e.g. using prime factorization, but it also follows 
immediately from the fact, to be established below, that $6$ is an integer 
linear combination (ILC) of $72$ and $114$.

\itemitem{}  Let us express $6$ as an ILC of $72$ and $114$. We have
$$
114=72+42\qquad{\rm (i.e.,}\quad 114=1\times 72+42{\rm )}\,,
$$
so 
$$
42=114-72\,.
$$
Next, 
$$
72=42+30\,,
$$
so
$$
30=72-42=72-(114-72)=(-1)\times 114+2\times 72\,.
$$
Now,
$$
72=2\times 30+12\,,
$$
so 
$$
12=72-2\times 30=72-2\times((-1)\times 114+2\times 72)
=2\times 114+(-3)\times 72\,.
$$
Now $72$ is divisible by $12$, but $114$ is not. So we write
$$
114=9\times 12+6\,,
$$
and then 
$$
6=114-9\times 12=114-9\times(2\times 114+(-3)\times 72)
=(-17)\times 114+27\times 72\,.
$$
VERIFICATION: $17\times 114=1140+798=1938$, and
$27\times 72=1440+504=1944$, so
$27\times 72-17\times 114=1944-1938=6$.

\medbreak
\itemitem{}  Therefore {\bf the gcd of 72 and 114 is 6, and
6=(-17)$\times$114+27$\times$72$\,$.}

\bigbreak
\item{{\bf 7.}} 
Prove that the product of four consecutive integers
is divisible by 24.

\medbreak
\itemitem{}  {\bf PROOF.} Let $a,b,c,d$ be four consecutive integers.
Then at least one of them has to be divisible by 3. Furthermore,
two of them must be even, and one of those two even 
integers must be divisble by 4. So the product 
$a\cdot b\cdot c\cdot d$ is divisible by 8 and by 3. Hence 
$a\cdot b\cdot c\cdot d$ is divisible by 24. \ \ {\bf END OF PROOF.} 

\bigbreak
\item{{\bf 8.}} In each of the
following cases, check the appropriate box.

\medbreak
\item{1.} $P\lto(Q\lto (R\lto (S\lto (P\wedge Q\wedge R\wedge S))))$ 
is a {\bf tautology}.

\medbreak
\item{2.} $(P\wedge(\neg P))\lto Q$ is a {\bf tautology}.

\medbreak
\item{3.} $P\lto(\neg P)$ is a {\bf contingency}.

\medbreak
\item{4.} $(P\wedge (\neg Q))\lto(P\lto Q)$  is a {\bf contingency}.

\medbreak
\item{5.} $((\neg P)\vee(\neg Q))\lto(P\lto(Q\lto R))$ is a {\bf tautology}.

\medbreak
\item{6.} $((\neg P)\wedge(\neg Q))\wedge(P\vee Q)$
is a {\bf contradiction}.

\end

