
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 2000 Final exam
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 1
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{33} \textbf {Miscellaneous}

\problempart {\bf (6 points)} Circle the numbers of ALL of the
following which are logical tautologies:

1.  $(P \wedge \neg P) \vee (Q \vee \neg Q)$\\
2.  $(P \Leftrightarrow Q) \vee (\neg P \vee Q)$\\
3.  $\forall x \forall y (P(x) \wedge \neg P(x)) \Rightarrow Q(y)$

\solution{\bigskip{\bf Solution:}
1 and 3 are tautologies and 2 is not.  

In 1, $(Q \vee \neg Q)$ is always true.  Since it is one part of an or
expression, the law of domination tells us the expression is always
true.

In 2, the expression is false if $P$ is true and $Q$ is false.

In 3, the expression $P(x) \wedge \neg P(x)$ is always false.  Since
an implication is always true if its antecedent is false, the expression
$(P(x) \wedge \neg P(x)) \Rightarrow Q(y)$ is true for all $x$ and $y$.
}

\problempart {\bf (3 points)} Define the relation $R$ such that $nRm$
whenever $n$ and $m$ are natural numbers such that $|n-m|$ is the
square of a nonnegative integer.
Circle the numbers of ALL of the following which apply to $R$:

1.  A reflexive relation\\
2.  A symmetric relation\\
3.  An equivalence relation

\solution{\bigskip{\bf Solution:} 
1 and 2 apply to $R$ but 3 does not.

Since $0$ is a nonnegative integer, 0 is the square of a nonnegative
integer.  Thus, if $n = m$, then $|n-m| = 0$ so $nRm$.  Thus, 1
applies.

If $|n-m| = a$ where $a$ is the square of a nonnegative integer, then
$|m-n| = |(-1)(n-m)| = a$, so $mRn$.  Thus, 2 applies.

However, $0R1$ and $1R5$ but $\neg 0R5$, so $R$ is not transitive.
Thus, 3 does not apply.
}

\problempart {\bf (10 points)} Circle the numbers of ALL of the
following statements that are true for all $m, n > 0 \in N$.  Let $G$
be an $m$ by $n$ grid graph.

1.  There is an Euler circuit in $G$.\\
2.  There is a Hamiltonian path in $G$.\\
3.  If $m$ and $n$ are even, there is a Hamiltonian circuit in $G$.\\
4.  If $m$ and $n$ are odd, there is a Hamiltonian circuit in $G$.\\
5.  If there is a Hamiltonian circuit in $G$ then $m$ and $n$ are even.

\solution{\bigskip{\bf Solution:} 
2 and 3 are true; the others are false.

1 is not true if either $m$ or $n$ is not equal to 2.  Thus is it not
true for ALL $m$ and $n$, though it is true for some.

2 is true.  The Hamiltonian path simply goes row by row and snakes back 
and forth.

3 is true.  We proved a less general version of this on the first exam;
the proof is analagous.

4 is false.  Grid graphs are 2-colorable; however, a Hamiltonian
circuit contains every node once.  Thus, since $mn$ is odd, the
Hamiltonian circuit is a circuit of odd length that is 2-colorable.
This is not possible, so there could be no Hamiltonian circuit.

5 is false.  Actually, the accurate statement is that if there is
a Hamiltonian circuit in $G$ then either $m$ or $n$ is even.  The 
2 by 3 grid graph gives a counterexample to 5.
}

\problempart {\bf (8 points)} Circle the numbers of ALL of the
following functions which are $\theta(n)$:

1.  $f(n) = 8000 \sqrt{n} + .00034 n$\\
2.  $g(n) = \frac{n^2 + 3n - 4}{-4n^2 + 9n + 9}$\\
3.  $h(n) = \log (n!/n)$\\
4.  $l(n) = n^{1 + \frac{1}{n}}$

\solution{\bigskip{\bf Solution:} 
1 and 4 are $\theta(n)$.

1: $f(n)$ is clearly $\theta(n)$ since the growth of $n$ outstrips
that of $\sqrt{n}$.

2: $g(n)$ is $O(n)$ but not $\Omega(n)$ since $\lim_{n \to \infty}
g(n) = -\frac14$.

3: $h(n)$ is $\Omega(n)$ but not $O(n)$.  By Stirling's approximation,
$\log(n!) = \theta(n \log n)$.  Thus, $h(n) = \theta (n \log n - n)$ which
is still $\theta(n \log n)$.

4: $l(n)$ is clearly greater than $n$, so it is $\Omega(n)$.  However, the
other direction is harder.  The question becomes whether there is a constant
$c$ such that for sufficiently large $n$,

$$n^{1 + \frac1n} < cn$$
$$n^{\frac1n} < c$$
$$\frac1n \log n < \log c$$

which is true for (say) $c = e$ since $\lim_{n \to \infty} \frac1n \log n = 0$.
Thus, $l(n) = O(n)$, so $l(n) = \theta(n)$.
}

\problempart {\bf (6 points)} Circle the numbers of ALL of the
following which are uncountably infinite sets:

1.  The set of all even natural numbers\\
2.  The set of all subsets of the even natural numbers\\
3.  The set of all real numbers with only even digits in their 
decimal representations

\solution{\bigskip{\bf Solution:} 
2 and 3 are uncountably infinite, but 1 is not.

1 is clearly countable.  $0, 2, 4, \ldots$ is the way to count it.

2 is uncountable by the standard diagonalization argument.  It is just
like $\mathcal{P}(\mathbb{N})$.

3 is uncountable.  The diagonalization argument for the uncountability
of the real numbers works even better here, since we don't run into the
$.9999\ldots = 1$ issue.
}