\documentclass{article}
\input{../notes/preamble.tex}
\title{Exam 3 - Technique Questions}
\date{June 29, 2012}
\begin{document}
\maketitle
The following are Exam 3 technique questions. Of this list, you will be asked to prove a specific few of them on the exam. This will constitute the majority of the points on Exam 3. Therefore, it is highly advised that you know these questions very well. It is not advised that you simply memorize the proof, as there are too many problems here to make that feasible.
You are welcome to study these problems with each other, and use any resources as per the Homework Resource Policy on the syllabus. You may not ask me any questions about them specifically except if you think there is an error or poor phrasing. However, as always, if you feel like you are having difficulties with a concept, you should come to me for help.
\begin{enumerate}
\item Consider 5 digits numbers. (Note: numbers less than ten thousand are read with preceeding $0$'s. For example, $431$ is read $00431$, which as 4 distinct digits: $0$, $4$, $3$, and $1$).
\begin{enumerate}
\item Count how many said digits have exactly $3$ distinct digits.
\item Count how many said digits have exactly $4$ distinct digits.
\item Count how many said sigits have exactly $4$ distinct digits and are even.
\end{enumerate}
\item Supposed you were setting up a tennis tourtament.
\begin{enumerate}
\item Count the number of ways to set up $n$ tennis matches with $2n$ total people (A match is different only if different people are player).
\item Count the number of ways to assign $n$ matches to courts if there are $n$ distinguishable courts.
\item Count the number of ways to assign $n$ matches to courts if there are clay, grass, and hard courts and courts of the same type are indistiguishable.
\end{enumerate}
\item Suppose there are $12$ people, two of them are Alice and Bob.
\begin{enumerate}
\item Count the number of ways to line them up so that Alice and Bob are standing next to each other.
\item Count the number of ways to line them up so that Alice and Bob are not standing next to each other.
\item Count the number of ways to line them up so there is exactly $i$ people between Alice and Bob, where $0\leq i \leq 10$
\end{enumerate}
\item Consider functions from $[m]$ to $[n]$.
\begin{enumerate}
\item Count the number of said bijections.
\item Count the number of said injections.
\item Count the number of said surjections.
\end{enumerate}
\item You have twenty books and you will place them on a bookshelf with 5 shelves. Each shelf is capable of holding twenty books.
\begin{enumerate}
\item Count the number of ways if all you care about is how many books are on each shelf.
\item Count the number of ways if all you care about is which book is on which shelf.
\item Count the number of ways if you care about which books are on which shelf, and the order they are in on that shelf.
\end{enumerate}
\item $\sum_{i=0}^k {n\choose i}{m\choose k-i} = {{m+n}\choose k}$
\item ${{n+1}\choose m} = {n\choose{m-1}} + {{n-1}\choose m} + {{n-1}\choose{m-1}}$
\item Let $A = \s{ 1,4,7,\ldots, 1+3i,\ldots 100}$. Prove that for any $19$ elements chosen from these set, there is two distinct integers chosen whose sum is $104$.
\item Let $n\geq 3$ be odd. Prove there is a number in $\s{ 2^1 -1, 2^2-1,\ldots,2^{n-1}-1}$ which is divisble by $n$. {\it Hint: if $n\mid ab$, $n$ odd, and $a$ is a power of two, then $n$ divides $b$. You may use this without proof.}
\item A bag contains 100 quarters, dimes, nickels, and pennies. Every minute, a coin is drawn from the bag. Determine and prove how long it will take to ensure that you have a dozen of one kind of object. {\it Note: You need to show the result is best possible as well}
\item Prove that if for any choice of $2^{n-1}+1$ subsets of $[n]$ then there are two sets that are disjoint. Prove this result is best possible by finding $2^{n-1}$ subsets of $[n]$ which are all, pairwise, have an element in common.
\item Suppose there are $100$ gold bars, and $3$ pirates. Determine the nunber of ways to divide the gold among the pirates so that no one recieves more than half of the tresure.
\item Count the number of positive integers less than $1000$ are not divisible by $2$, $3$, or $5$.
\item Suppose there are $n$ different classes, which will be taught in the spring and the fall. Count the number of ways to assign $n$ professors to teach the courses, ensuring that a professor doesn't teach the same course in both semesters.
\item Prove the following are equivalent:
\begin{enumerate}
\item $T$ is a tree (ie. $T$ is minmally connected).
\item $T$ for any two points on the tree $a$ and $b$, there is a unique path connecting $a$ and $b$
\item $T$ is connected and acyclic.
\item $T$ is connected with $n-1$ vertices.
\end{enumerate}
\item Prove the chromatic number of any tree with more than one vertex is $2$.
\item Prove a graph is Eulerian if and only if every vertex has even degree.
\end{enumerate}
\end{document}