%% To students who wish to submit their homework in LaTeX format:
%% On the line that starts ``\newcommand{\student}''
%%   put your name(s) in the appropriate place.
%% Then, uncomment the line further down that starts
%%   ``%% \\[2pt]\student''

\documentclass[11pt]{article}

\usepackage{fullpage}

\newcommand{\solution}{\bigskip\hrule\bigskip}
\newcommand{\problembreak}{\bigskip\hrule\bigskip}

\renewcommand{\theenumi}{\bf\Alph{enumi}}

\newlength{\spread}
\setlength{\spread}{1.0in}

\begin{document}

\begin{center}
{\Large CS5114 Spring 2010\\
Solution to Homework Assignment 1}
\end{center}
\vspace*{0.10in}
\medskip

\textbf{Pledge:
I (we) have not received unauthorized aid on this assignment.
I (we) understand the answers that I (we) have
submitted.
The answers submitted have not been directly copied from another
source, but instead are written in my (our) own words.}

\bigskip
\PutYourNameHere, \PutYourIDNumberHere
%Put second name/ID here if there is one

\paragraph {1.}
Manber 2.13: Prove that, for all $n > 1$,
\[1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} =
\frac{k}{m},\]
where $k$ is an odd number and $m$ is an even number.


\solution
% PUT YOUR SOLUTION HERE

\problembreak

\paragraph {2.}
Manber 2.14: Consider the following series, 1, 2, 3, 4, 5, 10, 20, 40,
..., which starts as an arithmetics series, but after the first 5
terms, becomes a geometric series.
Prove that any positive integer can be written as a sum of distinct
numbers from this series.

% PUT YOUR SOLUTION HERE

\solution

\problembreak

\paragraph {3.}

Manber 2.21: Prove that the regions formed by a planar map all of
whose vertices have even degree can be colored with two colors such
that no two neighboring regions have the same color.
[A planar map is a graph whose edges are straight line
segments, and whose edges may not intersect except where they meet at
a vertex.]

\solution

% PUT YOUR SOLUTION HERE

\problembreak


\end{document}






