\documentclass{article}
\input{../notes/preamble.tex}
\usepackage{url}
\title{Assignment 8}
\date{Wednesday June 27, 2012}
\newcommand{\df}{\textbf}
\begin{document}
\maketitle
\section{Be My Grader!}
The following section is intended to be completed Friday June 22. It will get us better at checking whether something is counting correctly, as well as practice counting!
\begin{prob}
Consider the following counting arguements. Determine if they count things twice, miss counting things, or both. Justify your answer with specific objects that are counted twice or not counted.
\begin{quote}
\begin{enumerate}
\item Count the number of four decimal digit positive integers with at least two distinct digit. (eg. 1111 is bad, for instance, but 2324 is good. 0011 is also good.)
\begin{soln*} \mbox{}
\begin{tabular}{>{\bfseries}r p{3in} l}
Step 1& Choose the first digit. & $10$ ways. \\
Step 2& Of the remaining three spots, choose one to have a different digit. & $3$ ways. \\
Step 3& Pick a digit to go on that spot which is different than the first & $9$ ways. \\
Step 4& Pick digits for the other two spots. They can be anything as we already gaurenteed there are two distinct. & $10^2$ ways. \\
Total & $10\cdot 3 \cdot 9 \cdot 10^2$
\end{tabular}
\end{soln*}
\item At a restarant, there are 10 different kind of appetizers, and a group of friends wants to order 4, not necessarily different. Count the number of ways they can do this.
\begin{soln*}\mbox{}
\begin{tabular}{>{\bfseries}r p{3in} l}
Step 1& They choose the first appetizer & 10 ways \\
Step 2& They choose the second appetizer & 10 ways \\
Step 3& They choose the third appetizer & 10 ways \\
Step 4& They choose the fourth appetizer & 10 ways \\
Total& $10^4$
\end{tabular}
\end{soln*}
\item Count the number of strings of A,B,C,D,E of length 5 with exactly 3 distinct letters.
\begin{soln*}\mbox{}
\begin{tabular}{>{\bfseries}r p{3in} l}
Step 1& Choose the first letter in string & 5 ways \\
Step 2& Choose the second letterin string & 4 ways \\
Step 3& Choose the third letter in string & 3 ways \\
Step 4& Choose the fourth letter in string (only 3 ways since we already have used 3 distinct digits) & 3 ways \\
Step 5& Choose the fifth letter in string & 3 ways\\
Total & $5\cdot 4\cdot 3^3$
\end{tabular}
\end{soln*}
\end{enumerate}
\end{quote}
\end{prob}
\section{Pigeonhole}
The following section is intended to be completed Friday June 22.
\begin{prob}
Consider the set $[3n]$. Prove that any subset of size $2n+1$ will have $3$ consecutive numbers. Is it true for $2n$ numbers?
\end{prob}
\begin{prob}
Prove that for any arrangement of numbers from $[10]$ around a circle there are three neighbors on the circle whose sum is at least 17. Is it true for 18?
\end{prob}
\begin{prob}
Prove that for any coloring of the squares of a 3 by 7 board white and black that there is a rectangle of at least 4 squares whose corner squares are the same color. Is it true for a 3 by 6 board?
\end{prob}
\section{Inclusion-Exclusion}
The following section is intended to be completed Monday June 25.
\begin{prob}
How many numbers less than $360$ are relatively prime with 360 (ie. they share no factors)?
\end{prob}
\begin{prob}
How many ways are there to rearrange the numbers in $[n]$ that leave no points in their usual position (ie. 1 is not first, 2 not second, etc)?
\end{prob}
\begin{prob}
How many ways are there to sit $n$ couples around a merry-go-round so that no one is next to their partner?
\end{prob}
\section{Graphs}
The following section is intended to be completed Tuesday June 26.
\begin{prob}
Prove every graph has an even number of vertices of odd degree.
\end{prob}
\begin{prob}
Define a graph $G$ with vertex set $V=[15]$ and say $xEy$ if and only if $x\sim y$ if and only if $x$ and $y$ are relatively prime. Count the number of edges of the graph.
\end{prob}
\end{document}