% LaTex2e
\documentclass[12pt]{article}
\usepackage{amssymb,latexsym}

\usepackage{anysize}
%\marginsize{left}{right}{top}{bottom}
%\marginsize{1.25cm}{1.25cm}{1.75cm}{2.5cm} % this cuts off page numbers
\marginsize{2cm}{2cm}{1cm}{3cm}

\pagestyle{myheadings}
\def\header{{\hfill Exam 2 \hfill A. Miller \hfill Spring 2005
                                       \hfill Math 240\hfill}}
\markboth\header\header
\newcount\probno
\newcount\total
\newwrite\examTBLFile

\probno=0

\def\prob#1{\advance\probno by 1 \par  \vfill \newpage
    \noindent\the\probno . (#1 pts)\advance\total by #1
    \immediate\write\examTBLFile{\the\probno
       \string& #1 \string&
       \string\qquad \string\\ \string\hline}}

\def\finishtbl{
    \immediate\write\examTBLFile{Total \string& \the\total
    \string& \qquad \string\\ \string\hline}
     }

\newwrite\ans
\immediate\openout\ans=answers
\outer\def\answer{\par\medbreak
  \immediate\write\ans{}
  \immediate\write\ans{\string\bigskip \the\probno . }
  \copytoblankline}
\outer\def\answerx{\par\medbreak
  \immediate\write\ans{}
  \immediate\write\ans{\string\bigskip \the\probno . }
  \copytoblankline}
\outer\def\putanswer{\par\medbreak
  \immediate\write\ans{}
  \copytoblankline}
\def\copytoblankline{\begingroup\setupcopy\copyans}
\def\setupcopy{\def\do##1{\catcode`##1=12}\dospecials
     \catcode`\|=12\obeylines}
{\obeylines \gdef\copyans#1
  {\def\next{#1}%
  \ifx\next\empty\let\next=\endgroup%
  \else\immediate\write\ans{\next}\let\next=\copyans\fi\next}}
\def\printanswers{\newpage\begin{center} Answers \end{center}
    \immediate\closeout\ans\input answers}

% \def\answer{\par\bigskip\bigskip\bigskip\noindent Answer: \par}
% \outer\def\answer{ {\par\bigskip Circle your answer.} \par\medbreak

\begin{document}

\bigskip

Show all work.

% Simplify your answers.

% Circle your answer.

\bigskip

No notes, no books, no calculators, no cell phones, no pagers, no
electronic devices of any kind.


\par\vskip .25in
\begin{center}
Name\makebox[3in]{\hrulefill} \\
\end{center}

\bigskip
Circle your Discussion Section:
\begin{verbatim}

    DIS 303 12:05p T B235 VAN VLECK
    DIS 304 12:05p R B235 VAN VLECK
    DIS 307  2:25p T B139 VAN VLECK
    DIS 308  2:25p R B309 VAN VLECK

\end{verbatim}
\bigskip

\begin{center} \Large
 \begin{tabular}{||c|c|c||} \hline\hline
  Problem & Points & Score \\  \hline\hline
   \input{exam.tbl}
  \hline \hline
 \end{tabular}
\end{center}

\immediate\openout\examTBLFile=exam.tbl

\bigskip

Solutions will be posted shortly after the exam:
www.math.wisc.edu/$\sim$miller/m240

 \setcounter{page}{0}

\newpage

\prob{10} % 3.1-21
Let $p$ be a prime. Prove that for any integers $a$ and $b$ that
$$a^2\equiv_p b^2 \;\;\;\;\mbox{ if and only if }\;\;\;\;
 a\equiv_p b  \mbox { or }
a\equiv_p -b. $$
$a\equiv_p b$ stands for $a=b$ mod $p$, or equivalently,
$a-b$ is divisible by $p$.

\answer The main point is that for a prime $p$ if
$p$ divides $(a-b)(a+b)$, then either $p$ divides $a-b$
or $p$ divides $a+b$.

\def\nat{{\mathbb N}}

\prob{10} % 3.2-37,41
$\nat=\{1,2,3, \ldots\}$ is the set of
positive integers.  A nonempty set $X$ is countable iff
there exists a function
$f:\nat\to X$ which is onto.  
Equivalently, a nonempty set $X$ is countable iff it can be
enumerated:
$$X=\{x_1,x_2,x_3,\ldots\}$$

(a) Prove that the set $E$ of even integers
is countable. (Note: we include in $E$ the negative even integers.)

(b) Prove exactly one of the following.  If you choose to prove (2)
you may assume (1) without proof.
\begin{enumerate}
  \item The set of ordered pairs of natural numbers, $\nat \times \nat$,
  is countable.
  \item  The union of a countable family of
  countable sets is countable, i.e., if $\{X_n:n\in\nat\}$ is a family
  of sets where each $X_n$ is countable, then $X$ is countable:
  $$X=\bigcup\{X_n:n\in\nat\}$$
\end{enumerate}

\answer \par (a) $\{0,2,-2,4,-4,\ldots\}$
\par (b) (1) See figure 2 on page 235.
\par (b) (2) Let $g:\nat\to\nat\times\nat$ 
be an onto function.  Suppose $f_n:\nat\to X_n$ is onto for each $n\in\nat$.
Define the function $h:\nat\to X$ by $h(n)=x$ where
$x=f_i(j)$ and $g(n)=(i,j)$. It is not hard to see that $h$ is onto.

\prob{10} % 3.5-25
Consider a sequence defined by $a_0=0,a_1=1$ and
$a_n=2a_{n-1}+3a_{n-2}+n^2$ for $n\geq 2$.
Write pseudocode for an iterative algorithm to compute $f(n)=a_n$.  Iterative
means that the algorithm may use loops
(for-next, repeat-until, do-while, etc) but may not call itself
recursively.  Do not use an array to store the values of $a_i$ for $i<n$.

\answer The inner code of the loop might look like this:
\par\bigskip $savey=y$
\par $y=2y+3x+z^2$
\par $x=savey$
\par $z=z+1$
\bigskip
\par\bigskip\noindent Each iteration of the loop has the effect of `shifting'
\par\bigskip
\par $y=a_n,$ $x=a_{n-1},$ $z=n$
\par to
\par $y=a_{n+1},$ $x=a_{n},$ $z=n+1$.


\prob{10} % 4.2-9
What is the minimum number of people each of whom comes from one
of 25 cities
which guarantees there are at least 9 from the same city?

\answer $201$

\prob{10} % 4.3-9
How many possible ways are there for first, second, third, and
last place finishes in a car race with 20 cars?  Assume no ties.

\answer $20\cdot 19\cdot 18\cdot 17$.

\prob{10} % 4.4-9
What is the coefficient of $x^3$ in the expansion of
$(x-1)^{8}$?
\answer $-56$

\prob{10} % 4.5-45
How many ways can $10$ cans of soup be put onto $4$ distinguishable shelves

\par (a) If the cans are indistinguishable?  For example, each can
contains the same brand of chicken
noodle soup.

\par (b) If each of the ten cans is a different kind of soup and
the position of the cans on the shelves matter?

\def\comb(#1,#2){ \left(\begin{array}{c} #1\\ #2 \end{array}\right) }

\answer (a) $\comb(13,3)$ (b) $10!\comb(13,3)$


\prob{10} % 5.1-39  Monty-Hall problem not really close.
Suppose that there are 10 sections in a discrete math book and
10 assigned exercises from each section.  An instructor randomly chooses 10
of the 100 assigned exercises to base his test on.
\par (a) What is the probability that all 10 chosen exercises
come from the same section in the book?
\par (b) What is the probability that each chosen exercise is from
a different section in the book?

\answer $$(a) \;\;\;{10\over {\comb(100,10)}}$$
$$(b) \;\;\;{{10^{10}}\over {\comb(100,10)}}$$

\prob{10} % 6.2-13
Find the general solution to
$$a_{n+1}-5a_{n}+6a_{n-1}=2n+5$$
(Hint: There should be two arbitrary constants in your solution.)

\answer $a_n=C2^n+D3^n+n+5$

\prob{10} % 6.3-11

\par (a) Suppose that $f(n)=7f(n/2)+n^2$ whenever $n$ is divisible by $2$.
Find the general solution for the recurrence relation satisfied
by $a_k=f(2^k)$.

\par (b) Suppose that $f$ of part (a) is an increasing function positive
function. Estimate the size of $f(n)$ using the big-O notation.

\answer \par (a) $a_k=C(7^k)+ (-{1\over 3})4^k$ for an arbitrary constant $C$.
\par (b) $f(n)$ is $O(n^c)$ where $c=\log_2(7)\approx 2.8$.

\finishtbl

\newpage

The following program was used to pick the problems on the test.
I combined a couple and changed the probability problem completely.

\begin{verbatim}

#! /usr/ucb/python

import string
import sys
import random

f=open("hmwk2",'r')    # input file
lines=f.readlines()

random.seed("Moe, Larry, and Curly")

linenumb=0
problems=[]
for line in lines:
  if linenumb > 30:
    s=string.split(line)
    if len(s)>0:
      section=s.pop(0)
      for prob in s:
        problems.append(section+"-"+prob.rjust(2))
  linenumb=linenumb+1
random.shuffle(problems)
problems=problems[0:12]
problems.sort()
for prob in problems:
  print prob


\end{verbatim}




\printanswers

\end{document}



