\documentclass{article}
\usepackage{amsthm, amssymb, amsmath,verbatim}
\usepackage[margin=1in]{geometry}
\usepackage{enumerate}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\N}{\mathbb{N}}
\newtheorem*{claim}{Claim}
\newtheorem{ques}{Question}
\title{Math 184 Homework 2}
\date{Fall 2022}
\begin{document}
\maketitle
This homework is due on gradescope Friday October 7th at 11:59pm pacific time. Remember to justify your work even if the problem does not explicitly say so. Writing your solutions in \LaTeX is recommend though not required.
\begin{ques}[Other Pigeonhole Principle Generalizations, 30 points]
Suppose that each of $n$ pigeons are assigned to one of $m$ holes. For which values of $m$ and $n$ can each of the following be guaranteed?
\begin{enumerate}[(a)]
\item There are at least $n$ (possibly overlapping) pairs of pigeons that share the same hole. [10 points]
\item There are at least $n/2$ pigeons that share a hole with some other pigeon. [10 points]
\item There are at least $2$ holes each with at least $2$ pigeons. [10 points]
\end{enumerate}
\end{ques}
\begin{ques}[Bishop Packing, 20 points]
In chess a bishop can move diagonally any number of squares. Prove that if $15$ bishops are placed on an $8\times 8$ chessboard that at least two will be attacking each other.
Hint: Try to divide the board into $14$ regions so that any two bishops in the same region would attack each other.
\end{ques}
\begin{ques}[Counting Subsets, 50 points]
In the following $[n]$ will be used to denote the set $\{1,2,3,\ldots,n\}$. For each of the following, give a formula for the number of sets of the type specified along with the actual number.
\begin{enumerate}[(a)]
\item How many subsets of $[10]$ are there? [5 points]
\item How many subsets of $[10]$ are there of size exactly $5$? [5 points]
\item How many subsets of $[12]$ consist of exactly $4$ even numbers and $3$ odd numbers? [5 points]
\item How many subsets of $[12]$ have the same number of even and odd numbers in them? [5 points]
\item How many subsets of $[20]$ contain exactly one element with each last digit? [5 points]
\item How many subsets of $[20]$ contain at least one element with each last digit? [5 points]
\item How many subsets of $[10]$ contain exactly one multiple of $3$ and no other elements within $1$ of that multiple of $3$? [5 points]
\item How many subsets of $[20]$ have largest and smallest elements that differ by at most $5$? [5 points]
\item How many subsets of $[10]$ contain no pair of consecutive numbers? Hint: Figure out the number of such subsets of $[n]$ for smaller values of $n$ as well. [5 points]
\item How many subsets of $[12]$ contain no pair of elements where one is exactly twice the other? [5 points]
\end{enumerate}
\end{ques}
\begin{ques}[Extra credit, 1 point]
Approximately how much time did you spend working on this homework?
\end{ques}
\end{document}