% 
% hw2.tex
%
%   This is LaTeX template to get you started
%   making problem-set solutions
%
 
\documentclass[11pt]{article}
\usepackage{amsthm,amsmath, amssymb}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\textheight}{9.0in}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{-0.5in}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{\bf Homework 3: due 1/29/2019\\[2ex]
       \rm\normalsize ECS 20 (Winter 2019)}
\date{}
\author{Patrice Koehl\\koehl@cs.ucdavis.edu}

\begin{document}
\maketitle


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 1 \textbf{\emph{(5 points)}}}  
Let $a$, $b$, and $c$ be three propositions. Show that this implication is a tautology, using a truth table:
\begin{eqnarray*}
(a \lor b) \land (\neg a \lor c) \rightarrow (b \lor c)
\end{eqnarray*}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 2 \textbf{\emph{(5 points)}}} 

Let $p$, $q$, and $r$ be three propositions. 
Show that $(p \lor q) \rightarrow r$ and $(p \rightarrow r) \lor (q \rightarrow r)$ are not logically equivalent.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 3 \textbf{\emph{(5 points each; total 20 points)}}}

Determine the truth values of the following statements; justify your answers:
\begin{itemize}
\item [a)] $\forall n \in \mathbb{N}, n < (n + 2)$
\item [b)] $\exists n \in \mathbb{N}, 4n=7n$
\item [c)] $\forall n \in \mathbb{Z}, 2n \leq 3n$
\item [d)] $\exists x \in \mathbb{R}, x^3 < x^2$
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 4 \textbf{\emph{(5 points each; total 25 points)}}} 

Solve the following proof problems.
\begin{itemize}
\item [a)] Let $x$ be a real number. Prove that if $x^2$ is irrational, then $x$ is irrational.
\item [b)] Let $x$ be a positive real number. Prove that if $x$ is irrational, then $\sqrt{x}$ is irrational.
\item[c)] Prove or disprove that if $a$ and $b$ are two rational numbers, then $a^b$ is also a rational number.
\item [d)] let $n$ be a natural number. Show that $n$ is even if and only if $5n+12$ is even.
\item [e)] Prove that either $4 \times 10^{769}+22$ or $4 \times 10^{769}+23$ is not a perfect square. Is your prove constructive, or non-constructive?
\end{itemize}

Note: for question e), a natural number $n$ is a perfect square if there exists a natural number $q$ such that $n = q^2$. For example, 4, 9, 16, 25, .... are all perfect squares while 2, 3, 5, 6,.... are not.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 5 \textbf{\emph{(10 points)}}} 

Let $n$ be a natural number and let $a_1, a_2, \ldots, a_n$ be a set of $n$ real numbers. Prove that at least one of these numbers is less than, or equal to the average of
these numbers. What kind of proof did you use?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 6 \textbf{\emph{(5 points each; total 10 points)}}} 

Let $n$ be an integer. Show that if $n^3+9$ is even, then $n$ is odd, using:
\begin{itemize}
\item [a)]  a proof by contraposition
\item[b)] a proof by contradiction
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Extra Credit \textbf{\emph{(5 points)}}} 

Use Exercise 5 to show that if the first 12 strictly positive integers are placed around a circle, in any order, then there exist three integers in consecutive locations around the circle that have a sum smaller than or equal to 19.

\vspace{0.5in}

\textbf{\emph{(+ 2 points for submitting online)}}

\end{document}