\documentclass[11pt]{article}
\usepackage{calc,fancyhdr,lastpage}
\usepackage[hmargin=.75in,vmargin=1in,
            footskip=.5in,headsep=.5in-\headheight]{geometry}
\usepackage{amsmath,amssymb}
\usepackage{graphicx}

% Page layout.
\flushbottom  % stretch text to fill up page
\reversemarginpar  % margin notes on the left

% Common symbols and macros.
\input{macros-236}

% Headings.
\pagestyle{fancy}
\let\headrule\empty
\let\footrule\empty
\lhead{{\bfseries CSC\,236\,H1F}}
\chead{{\bfseries\large Homework Assignment \#\,1}}
\rhead{{\bfseries Fall 2009}}
\lfoot{{Dept.\ of Computer Science,
    University of Toronto (St.~George Campus)}}
\cfoot{{}}
\rfoot{{Page \thepage\ of \pageref{LastPage}}}


\begin{document}

\vspace*{-5ex}

\noindent
\strong{Worth:}  8\%
\hfill
\strong{Due:}  By 6pm on Wednesday 30 September

\vspace{2.5ex}% when not using \begin{enumerate} immediately

\noindent
For each question, please write up detailed answers carefully.
Make sure that you use notation and terminology correctly, and
that you explain and justify what you are doing.
Marks \strong{will} be deducted for
incorrect or ambiguous use of notation and terminology, and
for making incorrect, unjustified, ambiguous, or vague claims
in your solutions.
\begin{enumerate}


\item
    Suppose $c \in \R^+$.
    In this question,
    you will investigate the existence of a value $d \in \R$ such that
    \begin{equation}\label{ineq}
        \frac{(1-a_1)}{(1+a_1)} \frac{(1-a_2)}{(1+a_2)} \dotsm
        \frac{(1-a_n)}{(1+a_n)} \ge d.
    \end{equation}
    for all natural numbers $n \ge 1$ and
    all $a_1,a_2,\dotsc,a_n \in \R^+$ such that
    \(\sum_{i=1}^n a_i = c\).
    \begin{enumerate}

    \item
        Consider a specific value of $c$ before tackling
        the general case:
        pick a value for $c$ and
        make up appropriate values for each $a_i$
        for the cases $n = 1,2,\dotsc,5$.
        For example, if $c = 1$ and $n = 3$, then
        $a_1 = \frac{1}{2}$,
        $a_2 = \frac{1}{3}$, and
        $a_3 = \frac{1}{6}$
        would be appropriate values.

        For your choice of $c$,
        what might be a good value for $d$?

    \item
        Prove that $\forall\, x,y \in \R^+$,
        \[  \frac{(1-x)}{(1+x)} \frac{(1-y)}{(1+y)} \ge
            \frac{1-x-y}{1+x+y}.  \]
        You should use the proof method that results in the most elegant
        solution.

    \item
        Based on your experiments and results from the previous parts,
        choose an appropriate value for $d$
        (\ie, the largest possible value) and
        prove Equation~\ref{ineq} for all natural numbers $n \ge 1$ and
        all $a_1,a_2,\dotsc,a_n \in \R^+$ such that
        \(\sum_{i=1}^n a_i = c\).

    \end{enumerate}


\item
    Prove that every rational number $0 < \frac{p}{q} < 1$
    can be written as a finite sum
    $\frac{1}{a_1} + \frac{1}{a_2} + \dotsb + \frac{1}{a_k}$,
    where $0 < a_1 < a_2 < \dotsb < a_k$ are all natural numbers.

    For example, $\frac{3}{10} = \frac{1}{4} + \frac{1}{20}$.


\item
    \altemph{Restricted Arithmetic Expressions} (``RAE's'' for short)
    are defined recursively as follows:
    \begin{points}
    \item  $2,3,4,\dotsc$ are ``atomic'' RAE's,
    \item  if $x,y$ are RAE's, then so are $(x + y)$ and $(x \times y)$,
    \item  nothing else is a RAE.
    \end{points}
    Prove that $\forall\, n \in \N$,
    every RAE that contains $n$ atomic sub-expressions
    has value at least $2n$.


\item
    Use the Principle of Well Ordering to prove that
    $\forall\, n \in \N$, it is possible to tile a triangular grid
    with $2^n$ triangles on a side and one corner missing,
    using tiles that consist of three small triangles in a line.
    For example, for $n = 2$,
    the picture on the right shows one possible way to tile
    the grid on the left.
    \begin{center}
        \includegraphics{triangle}
    \end{center}


\item
    Consider the following description of a game.
    \begin{points}
    \item
        There are $n$ people playing, one of whom leads the game.
        They are playing on a playing field with no obstacles.
        Everyone carries one water balloon.
    \item
        Everyone walks around the playing field until
        the game leader yells ``stop''.
        Assume that the leader will yell stop only when
        everyone is in a position where
        they have a \altemph{unique} closest neighbour.
    \item
        Next, the leader yells ``throw'' and
        everyone throws their water balloon at their nearest neighbour
        (there is exactly one, by the assumption in the previous point).
    \item
        A \altemph{survivor} is anyone
        who is still dry at the end of the game
        (assuming everyone has perfect aim and
        the water balloons are designed so that
        they get only their intended target wet).
    \end{points}
    Prove that for all odd natural numbers $n$,
    there will always be at least one survivor
    when the game is played with $n$ people.

    (For your own amusement, what can you prove about
    the minimum and maximum number of survivors possible for
    arbitrary values of $n$---odd or even?
    What other properties can you prove?
    For example,
    think about how many balloons someone could be hit with,
    how many pairs of players could throw balloons at each other, \etc.)


\end{enumerate}

\end{document}