% 
% hw1.tex
%
%   This is a LaTeX template to get you started
%   making problem-set solutions
%
 
\documentclass[11pt]{article}

\usepackage{amssymb,amsmath,pstricks,framed}
\usepackage{color}

\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\textheight}{9.0in}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{-0.5in}

% *** GRAPHICS RELATED PACKAGES ***
%

\usepackage[pdftex]{graphicx}
 \graphicspath{{./}}
 \DeclareGraphicsExtensions{.pdf,.jpeg,.png}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{\bf Data, Logic, and Computing\\[2ex] 
       \rm\normalsize ECS 17 (Winter 2025)}
\date{\today}
\author{Patrice Koehl\\koehl@cs.ucdavis.edu}

\begin{document}
\maketitle
\section*{\underline{Midterm 2: solutions}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 1 \emph{(1 question, 10 points)}}

\textcolor{blue}{\emph{Let $a, b$, and $c$ be 3 integers. Using the method of proof of your choice, show that if $abc$ is even, then at least one of $a, b,$ or $c$ must be even.}}

\vspace{0.1in}
We want to prove an implication of the form $p \rightarrow q$ is true, with:
\begin{table}[!h]
\begin{tabular}{l l} 
$p$:  $abc$ is even & $\lnot p$: $abc$ is odd \\
$q$:  $a$ is even or $b$ is even or $c$ is even & $\lnot q$:  $a$ and $b$ and $c$ are odd. \\
\end{tabular}
\end{table}

We use an indirect proof: we show that $\lnot q \rightarrow \lnot p$ is true.

Let us assume that $\lnot q$ is true, namely that $a$, $b$, and $c$ are odd. There exists three integers $l$, $m$, and $n$ such that:
\begin{eqnarray*}
a &=& 2l + 1 \\
b &=& 2m + 1 \\
c &=& 2n + 1.
\end{eqnarray*}
Then,
\begin{eqnarray*}
abc & = & (2l+1) (2m+1) (2n+1) \\
&=& (4lm + 2l + 2m + 1) (2n + 1) \\
&=& 8lmn + 4lm + 4ln + 2l + 4mn + 2m + 2n + 1 \\
&=& 2( 4lmn + 2lm + 2ln + 2mn + l + m + n) +1.
\end{eqnarray*}

As $l$, $m$, and $n$ are integers, $4lmn + 2lm + 2ln + 2mn + l + m + n$ is an integer. Therefore $abc$ is odd.

 Therefore $\lnot p$ is true when $\lnot q$ is true. the proposition $\lnot q \rightarrow \lnot p$ is true and, by equivalence, $p\rightarrow q$ is true.
 
 \newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 2 \emph{(1 question, 10 points)}}

\textcolor{blue}{\emph{Let $n$ be an integer. Give an indirect proof of the proposition, if $n^2+8n$ is odd then $5n$ is odd.}}

\vspace{0.1in}
We want to prove an implication of the form $p \rightarrow q$ is true, with:
\begin{table}[!h]
\begin{tabular}{l l} 
$p$:  $n^2+8n$ is odd & $\lnot p$:  $n^2+8n$ is even \\
$q$:  $5n$ is odd & $\lnot q$: $5n$ is even \\
\end{tabular}
\end{table}

We use an indirect proof, i.e. we show $\lnot q \rightarrow \lnot p$ is true.

Let us assume that $\lnot q$ is true, i.e. that $5n$ is even. There exists and integer $k$ such that $5n=2k$. Therefore,
\begin{eqnarray*}
n^2 + 8n &=& n^2 + n + 5n + 2n \\
&=& n(n+1) + 2k + 2n
\end{eqnarray*}
We have shown in class that $n(n+1)$ is always even, when $n$ is an integer. Therefore there exists an integer $l$ such that $n(n+1)=2l$. Therefore,
\begin{eqnarray*}
n^2 + 8n &=& 2l+2k +2n\\
&=& 2(k+l+n)
\end{eqnarray*}

As $k$, $n$, and $l$ are integers, $k+l+n$ is an integer. Therefore $n^2+8n$ is even.

We have shown that $\lnot p$ is true when $\lnot q$ is true: the proposition $\lnot q \rightarrow \lnot p$ is true and, by equivalence, $p\rightarrow q$ is true.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 3 \emph{(1 question, 10 points)}}

\textcolor{blue}{\emph{Let $n$ be an integer. Use a proof by contradiction to show that $\frac{n^3+n^2+3}{2n^2+6}$ is not an integer.}}

\vspace{0.1in}
Let:

$P$: $\frac{n^3+n^2+3}{2n^2+6}$  is not an integer

We use a proof by contradiction. We \textbf{assume} that $P$ is false, i.e. we assume that $\frac{n^3+n^2+3}{2n^2+6}$ is an integer. Let us name this integer as $k$. We have:
\begin{eqnarray*}
\frac{n^3+n^2+3}{2n^2+6} = k
\end{eqnarray*}
which we rewrite as:
\begin{eqnarray*}
n^3+n^2+3= k(2n^2+6)
\end{eqnarray*}
Let $LHS=n^3+n^2+3$ and $RHS=k(2n^2+6)$. Notice that:
\begin{eqnarray*}
LHS &=& n (n(n+1)) + 3 \\
&=& 2ln + 2 + 1 \\
&=& 2(ln+1) + 1
\end{eqnarray*}
where we have used that $n(n+1)$ is even, i.e. there exists an integer $l$ such that $n(n+1)=2l$.
Since $ln+1$ is an integer, $LHS$ is odd. Conversely,
\begin{eqnarray*}
RHS = 2(k(n^2+3))
\end{eqnarray*}
As $k$ and $n$ are integers, $k(n^2+3)$ is an integer and therefore $RHS$ is even.

Under the assumption that $P$ is false, we find that $LHS=RHS$ with $LHS$ odd and $RHS$ even. Since an even number cannot be equal to an odd number, we have reached a contradiction.
Therefore the assumption that $P$ is false, is false, i.e. $P$ is true.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 4 \emph{(1 question, 10 points)}}

\textcolor{blue}{\emph{Let $n$ be an integer. Use a direct proof to show that if $n$ is odd, then there exists an integer $m$ such that $n^2=8m+1$.}}

\vspace{0.1in}
We want to prove an implication of the form $p \rightarrow q$ is true, with:
\begin{itemize}
\item[$p$: ] $n$ is odd
\item[$q$: ] There exists an integer $m$ such that $n^2 = 8m+1$.
\end{itemize}

We use a direct proof. We assume that $p$ is true.

Since $p$ is true, $n$ is odd: there exists an integer $k$ such that $n=2k+1$.
Therefore,
\begin{eqnarray*}
n^2 &=& 4 k^2 + 4k + 1 \\
&=& 4k(k+1) + 1.
\end{eqnarray*}
As $k$ is an integer, $k(k+1)$ is even. Therefore there exists an integer $l$ such that $k(k+1)=2l$. Therefore
\begin{eqnarray*}
n^2 &=& 8l+1.
\end{eqnarray*}
We have found an integer $m$ ($m = l$) such that $n^2 = 8m+1$: q is true.

We have shown that $q$ is true when $p$ is true: the proposition $p\rightarrow q$ is true.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 5 \emph{(1 question, 10 points)}}

\textcolor{blue}{\emph{Let $n$ be an integer. Show that $4n+3$ is not a perfect square. (An integer $a$ is a perfect square if and only if there exists an integer $b$ such that $a=b^2$).}}

\vspace{0.1in}
Let:

$P$: $4n+3$  is not a perfect square.

We use a proof by contradiction. We \textbf{assume} that $P$ is false, i.e. we assume that $4n+3$ is a perfect square. Then
there exists an integer $k$ such that:
\begin{eqnarray*}
4n+3 = k^2
\end{eqnarray*}
Since $4n+3$ is odd, $k^2$ is odd and therefore $k$ is odd. We write it at $k=2l+1$ where $l$ is an integer. Then,
\begin{eqnarray*}
4n+3 &=& (2l+1)^2 \\
&=& 4k^2 + 4k + 1
\end{eqnarray*}
We rewrite it as:
\begin{eqnarray*}
2 &=& 4k^2 + 4k -4n \\
\end{eqnarray*}
After dividing by 2,
\begin{eqnarray*}
1 &=& 2k^2 + 2k -2n \\
1 &=& 2(k^2+k-n).
\end{eqnarray*}
As $k$ and $n$ are integers, $k^2+k-n$ is an integer and therefore $2(k^2+k-n)$ is even. But 1 is odd. Since an even number cannot be equal to an odd number, we have reached a contradiction.
Therefore the assumption that $P$ is false, is false, i.e. $P$ is true.



\end{document}