%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%spring98 final #1 (added by Ivan)
\problem\points{25} Circle True/False.    %F97 Pfinal p4 in part

%FOR THE FUTURE: These questions merit MULTIPLE CHOICE rather than T/F format.

\begin{list}{{\bf T\ \ F\ \ \ }}{\setlength{\leftmargin}{40pt}%
        \setlength{\labelwidth}{\leftmargin}%
        \setlength{\itemsep}{10pt}%
%        \setlength{\itemsep}{20pt}%
}

%\item
%Adding $k$ edges to an undirected graph increases its chromatic number
%(the number of colors needed to color the vertices) by at most $k$.


\item $[\exists x: P(x) \implies \forall x: Q(x)]$ implies $[\forall x:
[P(x) \implies \forall y: Q(y)]]$
\solution{ \true }

\item
The number of distinct simple paths in a tree is bounded by $2^{(l+1)^2}$
where $l$ is the number of leaves.
\solution{ \false:  Consider a chain of length $n$:
it's a tree with only two leaves, so $n$ can't be bounded by any function
of $l$.
}

\item
If every vertex of an $n$ vertex simple graph has degree at least $n/2$,
then the expected distance between a randomly chosen pair of distinct
vertices is strictly less than two.
\solution { \true: If two nodes each are adjacent to $n/2$
nodes, then by Pigeonholing, their adjacency sets must overlap, and so
distance is always $\le 2$.  Since adjacent nodes are distance 1, the
expectation must be strictly less than 2.
}

%\item
%Reversing the directions of all edges in a directed graph leaves the
%number of simple directed cycles unchanged.

%\item
%If an undirected graph has the degree of every vertex divisible by a prime
%$p$, then $p$ must evenly divide the number of edges.

%\item
%Let $f:A\to B$ and $g:B\to C$.  If $g\comp f$ is a surjection, then both
%$f$ and $g$ are surjections.

\item
If there is a surjection from $A$ to $B$ and also a surjection from $B$ to
$A$, then there is a bijection from $A$ to $B$.
\solution{ \true:  This is
the Schr\"oder-Bernstein Theorem from Handout 34.
}

\item In the polynomial expansion of $(x + 1)^{123}$, every
coefficient occurs exactly twice.
\solution{ \true }

\item Assume each Boolean variable is randomly assigned true or false with
equal likelihood and the choices are independent.  Then $\pr{(p_1 \vee p_2
\vee \overline{p_3})\wedge(\overline{q_1} \vee q_2 \vee q_3)\mbox{ is
true}} \le 3/4$.
\solution{ \false: $(7/8)^2 \approx .77 > 3/4$. }


\item The function $f:\reals \rightarrow \reals$ defined by
$ f(x) = x^3$ is a bijection.
\solution{ \true }

%\item The relation $\{(A,B) \mid \mbox{ there is a surjection from $A$ to
%$B$}\}$ is transitive.  \solution{ \true }

\item If $r$ is a real number and not an integer, then the set of infinite
subsequences of the decimal representation of $r$ is uncountable.
\solution{ \false: eg, $r=1/10= 0.100\ldots$ }

\item There is a surjection from the real line onto the plane.
\solution{ \true---this was highlighted in the cardinality Handout 34. }

\item Every countable powerset is finite.
\solution{ \true:
In order for $P(A)$ to be infinite, $A$ must also be
infinite.  But then $\nats \inj A$, so $P(\nats) \inj P(A)$, and since
$P(\nats)$ is not countable, neither is $P(A)$.
}

\item All $n$-vertex simple graphs with chromatic number $n$ (that is,
that require exactly $n$-colors) are isomorphic.
\solution{ \true: Has to be the complete graph $K_n$. }

\item $n!= 2^{f(n)}$ for some $f:\nats \to \reals$ where $f = \Theta(n
\log n)$.
\solution{ \true: By Stirling's formula.  The $\sqrt{2\pi n}$ and $e^{a_n}$
can be absorbed into $f$.
}
\end{list}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%spring98 final #3 (added by Ivan)
\problem \points{25} Short answers.  No need to be rigorous, though
partial credit may be given based on the derivation.

\bparts

\ppart \points{8} %F97 Q1 p9

We'll say an integer $n\ge 2$ is ``good'' providing that in any set of 401
integers, there are three integers, $j$, $k$ and $l$, such that the
pairwise differences, $j-k, j-l, k-l$ are multiples of $n$.  There is a
bound $m \in \naturals$ such that $n$ is good iff $2 \le n \le m$.  What is
$m$?

\solution{
\textbf{Solution:} $m=200$ by a simple Pigeonholing argument.
}

\ppart \points{5} What is the coefficient of $x^{11}$ in the polynomial
$(3x+2)^{50}$?  (Your answer may contain binomial coefficients and integer
powers.)

\medskip
\solution{
\textbf{Solution:} $3^{11}2^{39}\binom{50}{11}$
}


\ppart \points{7} The space shuttle runs 5 identical computers so that if
two goof, the other three will out-vote them with the right answer.  If
each computer goofs independently with probability $g$, what is the
probability of getting the right answer in a given computation?

\medskip
\solution{
\textbf{Solution:}
\[\pr{\mbox{5 correct}} + \pr{\mbox{4 correct}} +
\pr{\mbox{3 correct}} = (1-g)^5 + \binom{5}{4}(1-g)^4 g +
\binom{5}{3}(1-g)^3g^2\]
}

\ppart \points{5} Suppose two 6-sided dice are thrown, and then as many
coins are flipped as the sum of the dice.  The dice and coins are fair.
What is the expected number of coins showing heads?

\solution{
\textbf{Solution:} $\expect{\mbox{sum of two dice}} =
2\expect{\mbox{value of one die}} = 2[1+2+3+4+5+6]/6 = 7$;
$\expect{\mbox{number of heads from one toss}}=1/2$.  By Wald's Thm,
expected number of coins showing heads is $\expect{\mbox{sum of two
dice}}\cdot \expect{\mbox{number of heads from one toss}}= 7(1/2) = 7/2$.
}

\eparts
