%Theodore Ian Martiny
%Summer 2017 Homework 2

\documentclass[addpoints]{exam}
\newcommand{\naturals}{\mathbb{N}}
\newcommand{\reals}{\mathbb{R}}
\renewcommand{\baselinestretch}{1.5}
%\setlength{\textwidth}{16cm}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{color}
\usepackage{colortbl}
\usepackage{fullpage}
\usepackage[utf8]{inputenc}
\usepackage{listings}
\usepackage{multicol}
\usepackage{setspace}
\usepackage{xcolor}
 
\definecolor{codegreen}{rgb}{0,0.6,0}
\definecolor{codegray}{rgb}{0.5,0.5,0.5}
\definecolor{codepurple}{rgb}{0.58,0,0.82}
\definecolor{backcolour}{rgb}{0.95,0.95,0.92}
\definecolor{Gray}{gray}{0.85}
 
\lstdefinestyle{mystyle}{
    backgroundcolor=\color{backcolour},   
    commentstyle=\color{codegreen},
    keywordstyle=\color{magenta},
    numberstyle=\tiny\color{codegray},
    stringstyle=\color{codepurple},
    basicstyle=\footnotesize,
    breakatwhitespace=false,         
    breaklines=true,                 
    captionpos=b,                    
    keepspaces=true,                 
    numbers=left,                    
    numbersep=5pt,                  
    showspaces=false,                
    showstringspaces=false,
    showtabs=false,                  
    tabsize=2
}
\newcolumntype{a}{>{\columncolor{Gray}}c} 
\lstset{style=mystyle}
\begin{document}
\singlespacing

\begin{center}
  {\large\textbf{CSCI 2824 - Discrete Structures}}

  {\large\textbf{Homework 2}}
\end{center}

You MUST show your work. If you only present answers you will receive minimal credit. This homework is worth \numpoints pts.

\textbf{Due: Wednesday June 21}

\begin{questions}
  %% Question 1
  \question[2]\label{qn:1} Prove that the sum of two odd integers is an even
  integer.
    \vspace*{\fill}
    \begin{solution}
      Let $m,n$ be odd integers. Then we can write $m = 2k+1$, $n= 2j+1$ for
      integers $k,j$. Then:
      \begin{align*}
        m + n &= 2k+1 + 2j+1\\
        &= 2k + 2j + 1 + 1\\
        &= 2(k+j + 1)\\
        &= 2p
      \end{align*}
      where $p$ is an integer.

      Thus $m + n$ is even.

      \qed
    \end{solution}

  %% Question 2
  \question[4] Prove that for all real numbers $x$ and $y$, if $xy \leq 2$, then either $x\leq \sqrt{2}$ or $y \leq \sqrt{2}$.
    \vspace*{\fill}

    \begin{solution}
      Proof by contrapositive. That is we prove that if $x > \sqrt{2}$ \textbf{and} $y > \sqrt{2}$ then $xy > 2$. Simply multiply the numbers: Since $x,y > \sqrt{2}$ we have that $xy>\sqrt{2}\cdot\sqrt{2}$. Or more simply, $xy > 2$. This proves the original claim that $xy \leq 2$ implies that $x \leq \sqrt{2}$ or $y\leq \sqrt{2}$

      This can also be proved by contradiction, but you'll probably just contradict the assumption that $xy \leq 2$, meaning you're really doing a contrapositive argument.

      \qed
    \end{solution}

  %% Question 3
  \question[10] Prove that the real numbers have the Archimedean Property. That
  is given any positive real numbers $x$ and $y$ prove that there is an integer
  $n$ such that $xn > y$.
  \vspace*{\fill}

  \begin{solution}
    Proof by contradiciton. Assume this is not true, and that there are two real
    numbers $x,y$ such that for any integer $n$, $xn \leq y$. Equivalently we
    can write, $n \leq \frac{y}{x}$ for every integer $n$. This provides an
    upper bound on all integers, which we know is false. This is our
    contradiction, thus the Archimedean Property is true.
  \end{solution}

  %% Question 4
  \question[6] Suppose $a,b$ and $c$ are integers. If $a^2$ divides $b$ and
  $b^3$ divides $c$, then $a^6$ divides $c$. [Divides, is a formal statement in
  math, $x$ divides $y$ means that $y$ is a multiple of $x$. For example $5$
  divides $10$, but $4$ does not divide $2$. This is often written $5|10$,
  $x|y$, $4\not|\ 2$ etc. For this problem it may help to think in terms of
  multiples, $x|y$ means that $y= kx$ for some integer $k$.]

  \begin{solution}
    Since $a^2$ divides $b$ means that we can write $b = na^2$ for some integer
    $n$. Similarly, since $b^3$ divides $c$ we can write $c = mb^3$ for some
    integer $m$. Combining:

    \begin{align*}
      c &= mb^3\\
      &= m(na^2)^3\\
      &= m\cdot n^3 \cdot (a^2)^3\\
      &= p \cdot a^6
    \end{align*}
    where $p$ is an integer. Thus $c$ is a multiple of $a^6$, or $a^6$ divides
    $c$.
    
    \qed
  \end{solution}

  \question[7] Prove that for all \emph{positive} integers $m,n$: $2m + 5n^2 = 20$ has no solution.
  \vspace*{\fill}
  \begin{solution}
    This solutions is more long than difficult. In order to use positive integers to satisfy the equation we must have that $1\leq m \leq 10$. Note that 0 is NOT positive.

    Similarly to satisfy the equation we must have that $1 \leq n \leq 2$. 

    However note that when $n=2$ then $5n^2 = 20$ so $m =0$, this is not allowed so the ONLY possible option for $n$ is 1. Thus we must have $2m = 15$ (after reducing our equation). This is not possible for integral $m$. So no solution exists, with positive integers.

    \qed
  \end{solution}

  %\question[8] Exhaustively prove (prove by cases) that $|xy| = |x||y|$. (\textbf{Hint:} There are 4 cases)
  %\vspace*{\fill}
  %\begin{solution}
  %\end{solution}

  %\question[6] Prove the following:
  %\begin{parts}
    %\part If $x^3-1$ is even then $x$ is odd.

    %\part If $x+y$ is even then $x$ and $y$ have different parity (that is one is even and the other is odd).
  %\end{parts}
  %\vspace*{\fill}
  %\begin{solution}
  %\end{solution}

  \question[5] Prove that that the difference between an irrational number $x$ and a rational number $y$ is irrational.
  \vspace*{\fill}
  \begin{solution}
    Proof by contradiction. That is suppose the difference between an irrational number $x$ and a rational number $y$ is rational. Then we have the following circumstance:

    Let $y = \frac pq$ for integers $p,q$, we can't write $x$ like this but by our assumption we can write $x-y = \frac ab$ for some integers $a,b$, or :
    \begin{align*}
      x - y &= \frac ab\\
      x - \frac pq &= \frac ab\\
      x &= \frac ab + \frac pq\\
    \end{align*}

    And by the proof of Question~\ref{qn:1}, the sum of two rationals is rational, so that $x$ is rational. This is a contradiction to our assumption, so it must be the case that the difference $x-y$ is NOT rational, i.e., irrational.

    \qed
  \end{solution}

  \question[4] Prove that for all integers $n$ if $n^3 + 5$ is odd then $n$ is even.
  \vspace*{\fill}
  \begin{solution}
    We prove this by contrapostive. That is we prove that if $n$ is odd then $n^3 + 5$ is even. If $n$ is odd then we can write $n = 2k+1$ for some integer $k$. Then we compute:
    \begin{align*}
      n^3 + 5 &= (2k+1)^3 + 5\\
      &= 8k^3 + 12k^2 + 6k + 1 + 5\\
      &= 8k^3 + 12k^2 + 6k + 6\\
      &= 2(4k^3 + 6k^2 + 3k + 3)
    \end{align*}
    Thus $n^3 + 5$ is even. This proves the original claim that if $n^3+5$ is odd then $n$ is even.

    \qed
  \end{solution}

  \question[8] Verify the following equation:
    \[
      1^2 - 2^2 + 3^2 - \cdots + (-1)^{n+1}n^2 = \frac{(-1)^{n+1} n (n+1)}{2}
    \]
    \vspace*{\fill}
    \begin{solution}
      We prove this by Induction: \textbf{Base case:} $n = 1$, $1^2 = \frac{1(2)}2 = 1$ $\checkmark$.

      \textbf{IH:} If $1^2 - 2^2 + \cdots + (-1)^{n+1}n^2 = \frac{(-1)^{n+1}n (n+1)}2$ then we show $1^2 - 2^2 + \cdots + (-1)^{n+2}(n+1)^2 = \frac{(-1)^{n+2}(n+1)(n+2)}2$.

      For simplicity: We're trying to show that 
      \[
        \sum_{j=1}^n (-1)^{j+1}j^2 = \frac{(-1)^{n+1} n (n+1)}{2} \implies \sum_{j=1}^{n+1} (-1)^{j+1}j^2 = \frac{(-1)^{n+2} (n+1)(n+2)}{2}
      \]

      Lets begin:
      \begin{align*}
        \sum_{j=1}^{n+1} (-1)^{j+1}j^2 &= \sum_{j=1}^{n} (-1)^{j+1}j^2 + (-1)^{n+2}(n+1)^2\\
        \text{(by \textbf{IH:})\hspace{1cm}} &= \frac{(-1)^{n+1} n (n+1)}{2} + (-1)^{n+2}(n+1)^2\\
        &= \frac{(-1)^{n+1} n (n+1)}{2} + \frac{2(-1)^{n+2}(n+1)^2}{2}\\
        &= \frac{(-1)^{n+1} (n^2 + n) + (n^2 + 2n + 1) (2) (-1)^{n+2}}2\\
        \intertext{Re-grouping terms:}
        &= \frac{(-1)^{n+1} n^2 + (-1)^{n+1}(2)n^2 + (-1)^{n+1}n + (-1)^{n+2}(2)(2n) + (-1)^{n+2}(2)(1)}{2}\\
        \intertext{The next step is kind of involved. We're using that $(-1)^{n} + (-1)^{n+1} = 0$ for all $n$, since one is $-1$ and the other is $1$. However in our case one of each term (the one with $(-1)^{n+2}$) has a factor of 2 in front, so it takes over and replaces the zero.}
        &= \frac{(-1)^{n+2}n^2 + (-1)^{n+2} 3n + (-1)^{n+2} 2}{2}\\
        &= \frac{(-1)^{n+2}(n+1)(n+2)}2
      \end{align*}

      \qed
    \end{solution}
  %\end{parts}
  
  \question[6] Prove that $7^n -1$ is divisible by 6 for all integers $n\geq 1$.
  \vspace*{\fill}
  \begin{solution}
    We prove this by induction. \textbf{Base case:} $n=1$ gives $7-1 = 6$ clearly $6\mid 6$.

    \textbf{IH:} If $7^n -1$ is divisible by 6 we show that $7^{n+1} - 1$ is divisible by 6.

    Thus:
    \begin{align*}
      7^{n+1} - 1 &= 7^n\cdot 7 - 1\\
      &= 7^n\cdot (1 + 6) - 1\\
      &= 7^n - 1 + 6\cdot 7^n\\
      \intertext{By \textbf{IH} we have that $7^n -1 = 6k$ for some integer $k$.}
      &= 6k + 6\cdot 7^n\\
      &= 6(k+7^n)\\
    \end{align*}
    we see that $7^{n+1}-1 = 6p$ for an integer $p$. This proves our inductions hypothesis, and closes our induction.

    \qed
  \end{solution}

  \question[8] Prove the following by cases:
  \begin{parts}
    \part 
    \[
      \max\{x,y\} = \frac{x+y+|x-y|}{2}
    \]
    for all real numbers $x$ and $y$.
    \vspace*{\fill}
    \begin{solution}
      We prove this by cases.

      \textbf{Case 1:} $x\geq y$. Then $\max\{x,y\} = x$, and $x-y >0 \implies |x-y| = x-y$. So:
      \begin{align*}
        \frac{x + y + |x-y|}{2} &= \frac{x + y + x - y}{2}\\
        &= \frac{2x}{2}\\
        &= x
      \end{align*}

      \textbf{Case 2:} $x\leq y$. Then $\max\{x,y\} = y$ and $x-y < 0 \implies |x-y| = -(x-y)$. So:
      \begin{align*}
        \frac{x + y + |x-y|}{2} &= \frac{x + y - (x-y)}2\\
        &= \frac{x + y - x + y}{2}\\
        &= \frac{2y}{2}\\
        &= y
      \end{align*}

      In either case we get that 
    \[
      \max\{x,y\} = \frac{x+y+|x-y|}{2}
    \]
    proving our claim.

    \qed
    \end{solution}

    \part 
    \[
      \min\{x,y\} = \frac{x+y-|x-y|}{2}
    \]
    for all real numbers $x$ and $y$.
    \vspace*{\fill}
    \begin{solution}
      We prove this by cases.

      \textbf{Case 1:} $x\geq y$. Then $\min\{x,y\} = y$, and $x-y >0 \implies |x-y| = x-y$. So:
      \begin{align*}
        \frac{x + y - |x-y|}{2}  &= \frac{x + y - (x-y)}{2}\\
        &= \frac{x + y - x + y}{2}\\
        &= \frac{2y}{2}\\
        &= y
      \end{align*}

      \textbf{Case 2:} $x\leq y$. Then $\min\{x,y\} = x$ and $x-y < 0 \implies |x-y| = -(x-y)$. So:
      \begin{align*}
        \frac{x + y - |x-y|}{2} &= \frac{x + y + (x-y)}2\\
        &= \frac{x + y + x - y}{2}\\
        &= \frac{2x}{2}\\
        &= x
      \end{align*}

      In either case we get that 
    \[
      \min\{x,y\} = \frac{x+y-|x-y|}{2}
    \]
    proving our claim.

    \qed
    \end{solution}
  \end{parts}

  \question[10] Verify the inequality:
  \[
    2n + 1\leq 2^n, \, n\geq 3
  \]

  \begin{solution}
    Proof by induction, base case, $n=3$: $2\cdot 3 + 1 = 7 < 8$ $\checkmark$.

    \textbf{IH:} Assume that the inequality holds for some $k\geq 1$ then we
    show it holds for $k+1$:

    \begin{align*}
      2(k+1) + 1 &= 2k + 2 + 1\\
      &= 2k+1 + 2\\
      \text{(by \textbf{IH})} &< 2^k + 2\\
      &< 2^{k+1} \text{  since $k>1$}
    \end{align*}
    This closes the induction.

    \qed.
  \end{solution}

  \question[10] Show that postage of 24 cents or more can be achieved by using
  only 5-cent and 7-cent stamps.

  \begin{solution}
    Proof by (Strong) induction, base cases:
    \begin{align*}
      n = 24&: \text{ choose 2 5-cent and 2 7-cent stamps}\\
      n = 25&: \text{ choose 5 5-cent stamps}\\
      n = 26&: \text{ choose 1 5-cent and 3 7-cent stamps}\\
      n = 27&: \text{ choose 4 5-cent and 1 7-cent stamps}\\
      n = 28&: \text{ choose 4 7-cent stamps}\\
    \end{align*}

    \textbf{IH:} Assume that $n\geq 29$ and for each $k$ such that $24 \leq k <
    n$ we have shown we can make postage using only 5-cent and 7-cent stamps. We
    show that we can make $n$-cent postage.

    By \textbf{IH} we can make $(n-5)$-cent postage, now add one more 5-cent
    stamp.

    \qed
  \end{solution}

  \question[20] Suppose we have two piles of cards containing $n$ cards each.
  Two players play the following game. Each player, in turn, chooses one pile
  and then removes any number of cards from the chosen pile. The player who
  removes   the last card on the table wins the game. Show the second player can
  always   win the game. [Note: You need to PROVE the second player can always
  win.   Coming up with a strategy is a necessary step, but then you'll need to
  prove   that strategy will always work. Hint: Induction]

  \begin{solution}
    The strategy is for the second player to mimic the move of the first player
    but in the other pile. This means the second player will never eliminate a
    pile before the first, forcing the first player to eliminate one pile first,
    so the second can clear the table.

    Proof this works (by Induction), base case, $n=1$. There are two piles each
    with one card, when the first player chooses one pile and removes the only
    card, the second player will remove the card from the remaining pile,
    winning the game.

    \textbf{IH:} Assume $n\geq 1$ and for any $k$ with $1\leq k < n$ there is a
    strategy for the second player to win the game when there are two piles of
    $k$ cards.

    We show that the second player can also win when there are $n$ cards in each
    pile: The first player will choose one pile, and remove $c$ cards from it.
    The second player will now choose the \emph{other} pile and also remove $c$
    cards from that. 

    This is now a game with $n-c$ cards in each pile, by \textbf{IH} the second
    player now has a winning strategy and will win.

    This closes the induction.

    \qed
  \end{solution}
\end{questions}
\end{document}
