\documentclass[11pt]{article}
\usepackage{latexsym,amsmath,amsthm,amssymb,fullpage,enumerate}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\degree}{\operatorname{degree}}
\begin{document}
\section*{CS 70 homework 8 submission}
Your full name: PUT YOUR NAME HERE
\\
Your login name: PUT YOUR LOGIN NAME HERE
\\
Homework 8
\\
Your section number: PUT YOUR SECTION NUMBER HERE
\\
Your list of partners: LIST THE PEOPLE YOU WORKED WITH HERE (OR ``none'')
\begin{enumerate}
\item
\begin{enumerate}[{(}a{)}]
\item How many 10-bit strings are there that contain exactly 4 ones?
YOUR ANSWER GOES HERE
\item How many different 13-card bridge hands are there?
YOUR ANSWER GOES HERE
\item How many different 13-card bridge hands are there that contain no aces?
YOUR ANSWER GOES HERE
\item How many different 13-card bridge hands are there that contain all
four aces?
YOUR ANSWER GOES HERE
\item How many different 13-card bridge hands are there that contain
exactly 6 spades?
YOUR ANSWER GOES HERE
\item How many 99-bit strings are there that contain more ones than
zeros?
YOUR ANSWER GOES HERE
\item If we have a standard 52-card deck,
how many ways are there to order these 52 cards?
YOUR ANSWER GOES HERE
\item Two identical decks of 52 cards are mixed together,
yielding a stack of 104 cards. How many different ways are there to order
this stack of 104 cards?
YOUR ANSWER GOES HERE
\item How many different anagrams of FLORIDA are there?
YOUR ANSWER GOES HERE
\item How many different anagrams of ALASKA are there?
YOUR ANSWER GOES HERE
\item How many different anagrams of ALABAMA are there?
YOUR ANSWER GOES HERE
\item How many different anagrams of MONTANA are there?
YOUR ANSWER GOES HERE
\item We have 9 balls, numbered 1 through 9, and 27 bins.
How many different ways are there to distribute these 9 balls among
the 27 bins?
YOUR ANSWER GOES HERE
\item We throw 9 identical balls into 7 bins.
How many different ways are there to distribute these 9 balls among
the 7 bins such that no bin is empty?
YOUR ANSWER GOES HERE
\item How many different ways are there to throw 9 identical balls
into 27 bins?
YOUR ANSWER GOES HERE
\item There are exactly 130 students currently enrolled in CS70.
How many different ways are there to pair up the 130 CS70 students,
so that each student is paired with one other student?
YOUR ANSWER GOES HERE
\end{enumerate}
\item
\begin{enumerate}[{(}a{)}]
\item
Describe a bijection $f:S\to T$.
YOUR ANSWER GOES HERE
\item
How many ways are there to place the seven bluebirds into some seven
of these bird boxes, so that no two blue birds end up in adjacent bird boxes?
YOUR ANSWER GOES HERE
\end{enumerate}
\item
Explain how the Dean's staff can use this coloring to assign an exam date
to each course, using only $k$ different dates.
YOUR ANSWER GOES HERE
\item
%Let $G$ be a bipartite graph, with a set $L$ of vertices on
%the left and a set $R$ of vertices on the right and a non-empty set of edges
%$E \subseteq L \times R$.
\begin{enumerate}[{(}a{)}]
\item Prove that $\sum_{v \in L} \degree(v) = \sum_{v \in R} \degree(v)$.
YOUR ANSWER GOES HERE
\item
%Let $s$ denote the average degree of vertices in $L$
%and $t$ the average degree of vertices in $R$, i.e.,
%\[ s = \frac{1}{|L|} \sum_{v \in L} \degree(v), \quad
%t = \frac{1}{|R|} \sum_{v \in R} \degree(v). \]
Prove that $s/t = |R|/|L|$.
YOUR ANSWER GOES HERE
\item
%In 1992, the University of Chicago interviewed a random sample
%of 2500 people in the U.S. about the number of opposite-gender sex partners
%they've had. They reported that on average men have 74\%
%more opposite-gender partners than women.
%At around the same time, the U.S. Census Bureau reported that female
%population of the U.S. was about 140 million and the male population
%about 134 million.
Explain why the University of Chicago and the U.S. Census Bureau
can't both be right.
YOUR ANSWER GOES HERE
\end{enumerate}
\item
%In the following parts, let $p$ be a prime number and
%let $k$ be a positive integer.
\begin{enumerate}[{(}a{)}]
\item
How many different ways are there construct such a sequence of beads?
YOUR ANSWER GOES HERE
\item
Count how many non-equivalent necklaces there are, if the $p$
beads must not all have the same color.
YOUR ANSWER GOES HERE
\item Use your answer to part (b) to prove Fermat's little theorem.
(Recall that Fermat's little theorem says that if $p$ is prime and
$a \not\equiv 0 \pmod p$, then $a^{p-1} \equiv 1 \pmod p$.)
YOUR ANSWER GOES HERE
\end{enumerate}
\item
Assign a grade of A (correct) or F (failure) to
the following proof.
{\bf Theorem:}
Let $G=(V,E)$ be a connected, undirected graph
and $f:V\to \R$ be a function that labels
each vertex with a real number. Suppose that for every vertex $v \in V$,
$f(v)$ is the median of the values of $f$ on the vertices adjacent to $v$
(choosing the smaller of the two possible medians, if there are
an even number of vertices adjacent to $v$)---in which case we say
that $f$ is \emph{unwrinkled}.
Then $f$ is a constant function, i.e., $f$ assigns the same
real number to every vertex.
\begin{proof}
We use induction on the number of vertices.
Let $P(n)$ be the proposition that the theorem is true for every
graph with $n$ vertices.
\emph{Base case:} If $n=1$, then the graph has only one vertex, so
the function $f$ obviously assigns the same real number to every vertex.
Therefore $P(1)$ is true.
\emph{Induction hypothesis:} Assume $P(n)$ is true for some $n\ge 1$.
\emph{Inductive step:} We must prove that $P(n+1)$ is true.
Consider any $n$-vertex graph $G$ that is connected and any
unwrinkled function $f:V \to \R$. By the induction
hypothesis, $f$ is a constant function, say $f(v)=c$ for every $v \in V$.
Now we add one more vertex
$w$ to obtain a graph $G'=(V',E')$ with $n+1$ vertices, and we extend
$f$ to a function $f':V' \to \R$ by labeling $w$ with some real number.
(Here $V' = V \cup \{w\}$, $f'(v)=f(v)$ for all $v \in V$,
and $E'$ differs from $E$ only in that it
may contain some extra edges incident on $w$.)
Suppose $G'$ is connected and $f'$ is unwrinkled (otherwise
there is nothing to prove).
Since $G'$ is connected, $w$ must have an edge to at least one
vertex in $V$ (possibly more), say to the vertices $v_1,\dots,v_k$.
Since $f'$ is unwrinkled, $f'(w)$ must be equal to the median of
the values $f'(v_1),\dots,f'(v_k)$ (choosing the smaller of the two
possible medians in case $k$ is even), which in turn is equal to
the median of the values $f(v_1),\dots,f(v_k)$ (again, choosing the
smaller of the two possible medians if $k$ is even).
But we said earlier that $f(v)=c$ for every $v \in V$, so
$f'(w)$ must be the median of $c,c,\dots,c$.
This means that $f'(w)=c$.
Also we know that $f'(v) = f(v) = c$ for every $v \in V$.
Therefore $f'(x)=c$ for every $x \in V'$, i.e., $f'$ is a constant function.
This proves that for every connected graph $G'$ with $n+1$ vertices
and every unwrinkled function $f'$ on $G'$, $f'$ is a constant
function.
In other words, $P(n+1)$ is true.
The theorem follows by induction.
\end{proof}
YOUR ANSWER GOES HERE
\end{enumerate}
\end{document}