%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 3
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{10} \textbf {Bounding Infinite Sums II}

Prove that the sum $$\sum_{i=1}^{\infty} \frac{1-\log i}{i^2}$$ is finite.

\solution{\bigskip
{\bf Solution:}

\begin{eqnarray*}
\sum_{i=1}^n \frac{1-\log i}{i^2} &=& 1 + \sum_{i=2}^n \frac{1-\log i}{i^2}\\
 &\leq& 1 + \int_1^n{\frac{1-\log x}{x^2}}dx\\
 &=& 1 + \int_1^n\left({\frac{1}{x^2} - \frac{\log x}{x^2}}\right)dx\\
 &=& 1 + \int_1^n {\frac{1}{x}d(\log x) + \log x d(\frac{1}{x})}\\
 &=& 1 + \left[ \frac{\log x}{x} \right]_1^n\\
 &=& 1 + \frac{\log n}{n}
\end{eqnarray*}

Thus, $\sum_{i=1}^n \frac{1-\log i}{i^2} \leq 1 + \frac{\log n}{n}$.
Since $\lim_{n \rightarrow \infty} \frac{\log n}{n} = 0$, the sum
converges.  Thus, the sum $\sum_{i=1}^{\infty} \frac{1-\log i}{i^2}$
is finite.
}
\nextproblem



A string is {\em 1-derful} if all the places in which it matches its
reverse are 1 bits.

\problempart {\bf (10 points)}
What is the total number of 1-derful strings of length $2n$?


\solution{\bigskip
{\bf Solution:}

$3^n$.

To build a 1-derful string of length $2n$ we must set each of the
matching pairs of bits, $(a_i, a_{2n-i}).$ There are three choices for
the pair: $(1,0)$, (0,1),$ and $(1,1)$.  $(0,0)$ is not permitted
because then that pair would be a pair of common bits between the
string and its reverse which are not 1s.  

Thus, we make $n$ independent choices, with 3 possibilities each time.
The number of ways we can do this is $3^n$.

}



\smallspace
\problempart {\bf (5 points)} The set of all {\em algebraic numbers},
that is, $\{ \alpha \ | \ \exists n \in \mathbb{N}, a_0, \ldots, a_n
\in \mathbb{Z}$ such that $a_n\alpha^n + \ldots + a_1\alpha + a_0 =
0.\}$

\solution{\bigskip
{\bf Solution:}

Countable.  There are countably many polynomials of each degree,
countably many degrees, and finitely many roots of each polynomial.
}


\mediumspace
\problempart {\bf (10 points)}:
$\sum_{i=0}^n 2\cdot3^i\cdot\binom{n}{i}$

\solution{ \bigskip
{\bf Solution:}

This is just an expanded formula using the binomial theorem.  Rewriting,

\begin{eqnarray*}
\sum_{i=0}^n 2\cdot 3^i \cdot \binom{n}{i} &=& 2 \sum_{i=0}^n 3^i
\cdot \binom{n}{i}\\
&=& 2 \sum_{i=0}^n 3^i 1^{n-i} \binom{n}{i}\\
&=& 2\cdot(3+1)^n\\
&=& 2\cdot4^n\\
&=& 2^{2n+1}
\end{eqnarray*}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 7
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem \pts{12} \textbf {Winning Record}

Suppose that a tennis player's record this year is 31 wins and 5 losses.  
Answer each of the following true/false.  No explanation is needed.

\problempart {\bf (3 points)}  The player must have won 5 games in a row.

\solution{{\bf Solution}: True.  See the solution for part (b).}
\smallspace

\problempart {\bf (3 points)}  The player must have won 6 games in a row.

\solution{{\bf Solution}: True.  We use the pigeonhole principle to
prove this: let each of the losses be a pigeonhole, and let the
matches (numbered chronologically) 1-6 be one pigeon, 7-12 be the
second, and so on.  

Suppose there is a loss in each one of these ``pigeons.''  Then, by
the pigeonhole principle, since there were 5 losses and 6 sets, some
loss must occur in more than one of the sets.  However, the sets are
distinct, so this is not possible.  Therefore, there cannot be at
least one loss in each of the sets, so there must be one such set which
has no losses in it.  Since each of the sets is a set of 6 consecutive
matches, one of them makes up a set of 6 consecutive wins.  
}

\smallspace
\problempart {\bf (3 points)} If the player's record was 30 wins and 5
losses, the player must still have won 5 games in a row.

\solution{{\bf Solution:}  True.  By the same argument in part (b), but
this time with the sets being 1-5, 6-10, 11-15, 16-20, 21-25, and 26-30,
we see that some set of 5 matches must not have a loss.  }

\smallspace
\problempart {\bf (3 points)} If the player's record was 30 wins and 5
losses, the player must still have won 6 games in a row.

\solution{{\bf Solution:}  False.  If the player's record went:

WWWWWLWWWWWLWWWWWLWWWWWLWWWWWLWWWWW,

there would be no sequence of 6 consecutive games the player won, but the
player's record would be 30 and 5.}
\nextproblem




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 7
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{24} \textbf {Counting Binary Strings}

Let $s = s_1s_2\ldots s_{2n}$ be a string of 0s and 1s.  The
{\em reverse} of $s$ is the string $R(s) = s_{2n}s_{2n-1}\ldots s_1$.

\problempart {\bf (8 points)} A string that is equal to its reverse
is called a $palindrome$.  How many palindromes of length $2n$ are
there?

\solution{\bigskip
{\bf Solution:}

$2^n.$

For a string of length $2n$ to be a palindrome, we must have that $s_1
= s_{2n}$, $s_2 = s_{2n-1}, \ldots, s_n = s_{n+1}$.  Thus, if a string
of length $2n$ is a palindrome, it is determined by the first $n$
bits.  Each of the $n$ bits can be either 0 or 1, so the total number
of ways we can set the first $n$ bits is $2^n$.  Once the first $n$
bits are set we can set the last $n$ bits by using the equations
above, so we need not make any more choices.  Thus, there are $2^n$
palindromes of length $2n$.
}

\mediumspace

\problempart {\bf (8 points)} How many strings of length $2n$ have
exactly $2r$ bits in common with their reverse?  (For example, 001010
has 2 bits in common with its reverse, 010100).

\solution{\bigskip
{\bf Solution:}

$2^n\binom{n}{r}$

We create a string of length $2n$ with exactly $2r$ bits in common
with its reverse by first setting each of the first $n$ bits (there
are $2^n$ ways of doing this) and then choosing which $r$ of those $n$
bits will follow the palindrome equations (ie, will $s_i = s_{2n-i+1}$
or not?).  We can now set all the rest of the bits: those that were
chosen to match, we set to be the same as their matching bit, those
that were not chosen to match, we set to be the {\em opposite} of
their matching bit.  Thus, we will have exactly $2r$ bits in common
(since each pair that matches is counted twice).  Since there are
$\frac{n!}{r!(n-r)!}$ ways of choosing the $r$ bits that will match,
there are $\frac{n!2^n}{r!(n-r)!}$ such strings.  
}

\mediumspace


\problempart {\bf (8 points)} A string $s$ is {\em 1-derful} if all
the common bits of $s$ and $R(s)$ are 1 bits.  How many 1-derful strings
are there of length $2n$ which have $2r$ bits in common with their 
reverse?  (For example, 001111 is 1-derful since it has only the two 1s
in the middle in common with its reverse.  However, 001010 is not 1-derful.)

\solution{\bigskip
{\bf Solution:}

$2^{n-r}\binom{n}{r}$

In order to make a 1-derful string which has $2r$ bits in common with
its reverse, we simply take one of the strings we counted in part (b)
and make all the bits that match into 1s.  When we do this, we will
count each 1-derful string $2^r$ times, since there were $2^r$
different ways those bits could be set before we set them to be 1s.
Thus, we just divide our answer from part (b) by $2^r$, which gives
$\frac{n!2^{n-r}}{r!(n-r)!}$ as our final result.
}

\nextproblem

