\documentclass[boldsans]{article}
\usepackage{ccfonts,fullpage,amsmath,amssymb}
\usepackage{hyperref}
\title{CSC165, Winter 2013\\
Assignment 2\\
Due Wednesday March 6th, 11:59 p.m.}
\renewcommand{\today}{~}
\hypersetup{pdfpagemode=Fullscreen,
  colorlinks=true,
  linkfileprefix={}}
\begin{document}
\maketitle

The aim of this assignment is for you to practice structuring and
expressing some proofs.  You may work in groups of no more than three
students, and you should produce a single solution in a PDF file named
\texttt{a2.pdf}, submitted to
\href{https://stanley.cdf.toronto.edu/markus/csc165-2013-01}{MarkUs}.
You must produce \texttt{a2.pdf} by \textbf{typing} your
solutions and processing the typed input into a PDF with your
favourite word processor or typesetting program.  Handwritten and
then scanned PDF files are huge and often illegible.

You will receive 20\% of the marks for any question you either leave
blank, or write ``I cannot answer this.''  You will receive
substantial parts marks if you present the outline of a proof/disproof
with clear indication of the steps you are unable to complete.

You must decide whether each of the statements below is true or
untrue, and then prove or disprove, as appropriate.  Your
proof/disproof should follow the structure used in this course, that
is indentation and justification of steps.  Please feel free to use
either precise English or the logical symbols taught in this course
(or both) in your proofs.

\textbf{NB:} If you cannot decide whether a statement is true or
false, write out the proof structure of \textbf{both} the proof and
disproof, clearly indicating the remaining steps you are unable to
justify.  These outlines will earn you significant part marks, whereas
you will receive \textbf{no credit} (and that's
significantly less than if you leave it blank) if you either ``prove'' a false
statement to be true, or ``disprove'' a true statement.  You have a
couple of weeks to think over whether each statement is true or
false.

\begin{enumerate}
\item \textbf{Prove or disprove:} $\forall x,y\in\mathbb{R}, x<y
  \Rightarrow \left(\exists z\in\mathbb{R}, x<z \wedge z<y\right)$.
\item \textbf{Prove or disprove:} $\forall m,n\in\mathbb{N}, m<n
  \Rightarrow \left(\exists k\in\mathbb{N}, m<k \wedge k<n\right)$
\item \textbf{Prove or disprove:} If $n$ is a natural number that has
  $n^2 \bmod 11 = 3$, then $n\bmod 11 = 5$.  Your proof/disproof must
  use the definition of $a\bmod b$ on page~11 of the
  \href{http://www.cdf.toronto.edu/~heap/165/W13/Notes/notes.pdf}{Course
    Notes}.
\item \textbf{Prove or disprove:} If $n$ is a natural number that has
  $n\bmod 11 = 5$, then $n^2\bmod 11 = 3$.  Your proof/disproof must
  use the definition of $a\bmod b$ on page~11 of the
  \href{http://www.cdf.toronto.edu/~heap/165/W13/Notes/notes.pdf}{Course
    Notes}.
\item \textbf{Prove or disprove:} For all quadruples of positive real
  numbers $w,x,y,z$, If $w/x < y/z$ then:
  \begin{equation*}
  \left( \frac{w}{x} < \frac{w+y}{x+z}\right) \wedge \left(
    \frac{w+y}{x+z} < \frac{y}{z} \right) 
  \end{equation*}
  \textbf{Hint:} The material on inequalities on page 12 of the
  \href{http://www.cdf.toronto.edu/~heap/165/W13/Notes/notes.pdf}{Course
    Notes} may be helpful.
\item \textbf{Prove or disprove:} For every pair of positive natural
  numbers $(m,n)$, if $m\geq n$, then the $\gcd(m,n)$ $=$ $\gcd(n,m-n)$.
  Your proof/disproof must use the definition of the $\gcd$ (Greatest
  Common Divisor) on page 12 of the
  \href{http://www.cdf.toronto.edu/~heap/165/W13/Notes/notes.pdf}{Course
    Notes}.
\end{enumerate}


\end{document}
