Question	Answer
a. How many strings of length eight can be made by using eight of the ten letters RRR GGG BBBB? b. How many 3-digit strings with distinct letters contain at least one vowel? c. How many 7-letter words are in alphabetical order (can repeat)?	a. $3\frac{8!}{3! 3! 2!}+2\frac{8!}{3! 1! 4!}+\frac{8!}{2! 2! 4!}$. b. $P(26,3)-P(21,3)$. c. $\binom{26+7-1}{7}$
Oski tosses a fair coin repeatedly until either two tails in a row have come up (TT) or the sequence heads-tails (HT) has come up. What is the probability that HT (rather than TT) is the sequence that stops Oski's tossing?	$P(\text{HT before TT}) = \frac{1}{2}(1)+\frac{1}{2}(\frac{1}{2})$. Once we see H $(1/2)$, guaranteed to get HT before TT $(1)$. Once we see T $(1/2)$, ether we get H or T $(1/2)$.
a. No hearts or clubs. b. At most two of the four suits. c. At least one Ace and at least one King. d. At least two face cards. e. One heart, two diamonds, two clubs. f. One ace, no king, at least one heart.	a. $\binom{26}{5}$ b. $\binom{4}{1}\binom{13}{5} + \binom{4}{2} \left[ \binom{26}{5} - 2\binom{13}{5} \right]$. c. $\binom{52}{5} - \binom{48}{5} - \binom{48}{5} + \binom{44}{5}$. d. $\binom{52}{5} - \binom{40}{5} - \binom{12}{1}\binom{40}{4}$. e. $\binom{13}{1}\binom{13}{2}\binom{13}{2}$. f. $\binom{4}{1}\binom{44}{4}-\binom{3}{1}\binom{32}{4}$
a. # of 13-card hands that have 4 cards from each of two suits, 3 cards from the third suit, and 2 cards from the remaining suit. b. # of 5-card hands that contain at most two of the four suits. c. # of 5-card hands that have at least one card from each of the four suits.	a. $\frac{4!}{2!}\times \binom{13}{4}\binom{13}{4}\binom{13}{3}\binom{13}{2}$. b. $4\binom{13}{5}+(4\times3)[\binom{13}{4}\binom{13}{1}+\binom{13}{3}\binom{13}{2}]$. c. $4\times\binom{13}{2}\times\binom{13}{1}^3$ (4 ways to choose which suit gets 2 card, $\binom{13}{2}$ ways to choose 2 cards from that suit, and for the other 3 suits, $\binom{13}{1}$ ways to choose 1 card from 13 cards)
a. # of ways to place $n$ distinguishable balls into $k$ distinguishable bins is... b. # place $n$ indistinguishable balls into $k$ distinguishable bins is... b. place $n$ indistinguishable balls into $k$ indistinguishable bins is... d. place $n$ indistinguishable balls into $k$ distinguishable bins such that no bin is empty is...	a. $k^n$. b. $\binom{n+k-1}{k-1}$. c. $\binom{n}{k}$. d. $\binom{n-1}{k-1}$.
Suppose we throw 10 balls into 5 bins. a. Expected number of bins containing exactly 2 balls is... b. Probability that there exists a bin containing at least two balls is... c. Probability that every bin has exactly two balls is...	a. $5\times\binom{10}{2}\frac{4}{5}^8\frac{1}{5}^2$. b. $1 - 0 = 1$ (Pigeonhole Principle). c. $\frac{10!}{2!2!2!2!2!} / 5^{10}$ (# of ways to make every bin have 2 balls BB BB BB BB BB / # of ways to arrange 10 balls in 5 bins)
A group of $n$ students $S_1, \dots, S_n$ leave their hats in a cloakroom. a. What is the probability that student $S_1$ gets their own hat back? b. What is the expected number of students who get their own hat back?	a. $1/n$. b. $1$.
I roll three fair 6-sided dice: $R, B, W$. a. If the blue die comes up 1, what is the probability that all three dice come up 1? b. If at least one of the dice comes up 1, what is the probability that all three dice come up 1?	a. $1/36$. b. $\frac{1/216}{1 - 125/216} = 1/91$.
In a discussion section with 26 students, a GSI randomly distributes one letter (A-Z) to each student. What is the expected number of students who receive a plastic version of the letter that begins their family names?	$E = 1$.
Find a simple formula for each of the following sums: a. $\sum_{k=0}^{2n} \binom{2n}{k}$ b. $\sum_{k=0}^{2n} (-1)^k \binom{2n}{k}$ c. $\sum_{k \text{ even}} \binom{2n}{k}$	a. $2^{2n}$. b. $0$. c. $2^{2n-1}$.
Find the number of 7-letter words (A-Z): a. No letter occurs more than once. b. The word contains exactly two distinct letters.	a. $P(26, 7) = \frac{26!}{19!}$. b. $\binom{26}{2}(2^7 - 2)$.
Prove the identity $\sum_{i=k}^n \binom{i}{k} = \binom{n+1}{k+1}$ for all integers $n \ge k \ge 0$.	Use Pascal's Identity $\binom{i+1}{k+1} - \binom{i}{k+1} = \binom{i}{k}$ and note the sum telescopes.
A die is rolled repeatedly until two different faces have come up. Find expected number of rolls.	$E = 1 + \sum_{i=1}^6 \frac{1}{P(\text{new face})} = 1 + \sum_{k=1}^5 \frac{1}{k/6} = 1 + 6/5$.
a. The expansion of $(x+y+z+w)^{100}$. How many terms are there after like terms are collected? b. How many solutions to the equation $x_1 + x_2 + x_3 + x_4 = 15$? c. How many solutions to the inequality $x_1+x_2+x_3 \le 11$?	a. $\binom{100+4-1}{4-1}$. b. $\binom{15+4-1}{4-1}$. c. $\binom{11+4-1}{4-1}$.
a. Five flavors (types). Ways to choose a dozen (items)? b. Two dozen with at least two of each flavor. c. Two dozen with no more than two broccoli flavor.	a. $\binom{5+12-1}{12}$ b. 2 donuts per type: $2\times 6=12$ donuts, $24-12=12$ donuts to distribute freely, $\binom{5+12-1}{12}$. c. $\binom{5+24-1}{24}+\binom{5+23-1}{23}+\binom{5+22-1}{22}$, 0 broccoli + 1 + 2.
Find the number of positive integers $\lt100000$ with one digit being 9 and the sum of digits = 13.	$\binom{6}{1}\times \binom{5+4-1}{4}$. Choose 1 position out of 6 for the digit 9, remaining 5 digits must sum to 4.
Prove that if S is a 15 element subset of ${1, 2, \dots, 50}$, then there are four distinct elements $a, b, c, d \in S$ such that $a+b=c+d$.	Pigeonholes are the 97 possible sums ($3$ to $99$). There are $\binom{15}{2}=105$ pairs (pigeons). $105 > 97$, so two pairs have the same sum, $a+b=c'+d'$.
Let X be the number (from 1 to 6) that comes up when a fair six-sided die is rolled once. a. Calculate $E(X)$. b. Calculate $V(X)$.	a. $1/6 * ( 1 + 2 + 3 + 4 + 5 +6)=7/2$. b. $1/6 * ( 1^2 + 2^2 + 3^2 + 4^2 + 5^2 +6^2)-(7/2)^2=35/12$.
Suppose I roll a standard 6-faced die 7 times. Let X be a random variable equal to the number of distinct faces that appear. a. What is the expectation of X? b. What is the variance of X?	a. $E(X) = 6 \cdot [1 - (5/6)^7]$. b. $V(X) = 6 \left[ (5/6)^7 - (5/6)^{14} \right] + 30 \left[ (4/6)^7 - (5/6)^{14} \right]$.
A spinner has a dial that is equally likely to point to each of $n$ regions numbered $1, 2, \dots, n$. If I spin the dial 3 times, what is the probability that the sum of the selected numbers is exactly $n$?	$P(\text{sum}=n) = \frac{\binom{n-1}{2}}{n^3}$ for $n \ge 3$.
What is the largest number of elements that a set of integers can have if it does not contain three distinct elements $a, b, c$ such that $a \equiv b \equiv c \pmod{10}$?	$2 \cdot 10 = 20$.
Show that if a fair 6-sided die is rolled 30 times, the probability is greater than 0.5 that the number of times it comes up 1 is between 3 and 7 (inclusive).	Let $X \sim \text{Binomial}(30, 1/6)$. Then $E(X) = 5$ and $V(X) = 30 \cdot \frac{1}{6} \cdot \frac{5}{6} = \frac{25}{6}$. By Chebyshev: $P(|X - 5| \ge 2) \le \frac{25/6}{4} = \frac{25}{24} < 1$, so $P(3 \le X \le 7) = P(|X - 5| \le 2) > 1 - \frac{25}{24} \cdot \frac{1}{2} > 0.5$.
Let Y be the total when the die is rolled 12 times. a. Find $E(Y)$ and $V(Y)$. b. Use the values of $E(Y)$ and $V(Y)$ to find a lower bound on the probability that $33 \le Y \le 51$.	a. $E(Y) = 12 \cdot \frac{7}{2} = 42$ and $V(Y) = 12 \cdot \frac{35}{12} = 35$. b. By Chebyshev: $P(|Y - 42| \le 9) \ge 1 - \frac{35}{81} = \frac{46}{81}$.
Let X be a random variable on a sample space S such that $X(s) \ge 0$ for all $s \in S$. If $a$ is a positive real number, show that $P(X \ge a) \le E(X)/a$.	$E(X) \ge \sum_{s: X(s) \ge a} X(s) P(s) \ge \sum_{s: X(s) \ge a} a P(s) = a P(X \ge a)$.
(22 Spring) Let $p$ be a prime number $\ge3$ and let $n$ be a positive integer. Prove that if $x$ is an integer such that $x^2-1$ is divisible by $p^n$, then either $x-1$ or $x+1$ is divisible by $p^n$. Is the analogous statement true if $p=2$?

Given that $p^n \mid (x^2 - 1)$. Factoring the difference of squares, we have $p^n \mid (x - 1)(x + 1)$. Since $p$ is a prime factor of $p^n$, $p$ must divide the product $(x-1)(x+1)$. By Euclid's Lemma (if a prime divides a product, it divides at least one factor), we know that either $p \mid (x-1)$ or $p \mid (x+1)$. Case 1: Assume $p \mid (x-1)$. We can express $x+1$ as $(x-1) + 2$. Since $p \mid (x-1)$, if $p$ were to also divide $(x+1)$, then $p$ would have to divide their difference: $(x+1) - (x-1) = 2$. However, we are given that $p \ge 3$, so $p$ cannot divide 2. Therefore, $p \nmid (x+1)$. Since $p$ is the only prime factor of $p^n$ and $p$ does not divide $x+1$, we have $\gcd(p^n, x+1) = 1$. We now apply the generalized Euclid's Lemma: If $a \mid bc$ and $\gcd(a, c) = 1$, then $a \mid b$. With $a=p^n$, $b=(x-1)$, and $c=(x+1)$, we have $p^n \mid (x-1)(x+1)$ and $\gcd(p^n, x+1)=1$. Therefore, $p^n \mid (x-1)$. Case 2: Assume $p \mid (x+1)$. Similarly, write $x-1 = (x+1) - 2$. Since $p \nmid 2$, $p$ cannot divide $x-1$. Thus, $\gcd(p^n, x-1) = 1$. By the generalized Euclid's Lemma, since $p^n \mid (x-1)(x+1)$ and $\gcd(p^n, x-1) = 1$, it follows that $p^n \mid (x+1)$. In either case, one of the factors must be divisible by $p^n$. Is it true for $p=2$? No. Counterexample: Let $p=2$, $n=3$, and $x=3$. $x^2 - 1 = 8$, which is divisible by $p^n = 2^3 = 8$. However, $x-1 = 2$ (not divisible by 8) and $x+1 = 4$ (not divisible by 8). The proof fails because $p=2$ does divide the difference between the factors (which is 2), so $p$ can (and does) divide both $x-1$ and $x+1$, splitting the factors of $p^n$ between them.

(22 Fall) Prove or disprove: if $x$ is a rational number and $x^2$ is an integer, then $x$ must be an integer.

Let $x \in \mathbb{Q}$. We can write $x = \frac{a}{b}$ where $a, b \in \mathbb{Z}, b \ne 0$, and $\gcd(a, b) = 1$ (lowest terms). We are given $x^2 = k$ where $k \in \mathbb{Z}$. $\frac{a^2}{b^2} = k \implies a^2 = k b^2$. Suppose $b > 1$. Then by the Fundamental Theorem of Arithmetic, there exists a prime $p$ such that $p \mid b$. If $p \mid b$, then $p \mid b^2$, and since $a^2 = k b^2$, $p \mid a^2$. If a prime divides a square, it must divide the root, so $p \mid a$. However, we stated that $\gcd(a, b) = 1$. It is a contradiction for $p$ to divide both $a$ and $b$. Therefore, $b$ cannot be greater than 1. Since $b$ must be a positive integer (standard representation of rationals), $b=1$. Thus $x = \frac{a}{1} = a$, which is an integer.

(21 Spring) Prove that if $r$, $s$, and $n$ are positive integers, and $r^2=s^2 n$, then $n$ is a perfect square. Then, use your result to prove that if $n$ is a positive integer and not a perfect square, then $\sqrt{n}$ is irrational.

Part 1: Given $r^2 = s^2 n$, we can rearrange to $n = \frac{r^2}{s^2} = \left(\frac{r}{s}\right)^2$. Since $n$ is an integer, $\left(\frac{r}{s}\right)^2$ is an integer. Let $x = \frac{r}{s}$. Since $x$ is rational and $x^2$ is an integer, by the proof in the previous question (22 Fall), $x$ must be an integer. Let $k = \frac{r}{s}$ where $k \in \mathbb{Z}$. Then $n = k^2$. Thus, $n$ is a perfect square. Part 2: Assume $\sqrt{n}$ is rational. Then $\sqrt{n} = \frac{r}{s}$ for integers $r, s$. Squaring both sides: $n = \frac{r^2}{s^2} \implies r^2 = s^2 n$. By the result in Part 1, this implies $n$ is a perfect square. Therefore, if $n$ is not a perfect square, $\sqrt{n}$ cannot be rational (it must be irrational).

(19 Spring) If $A$, $B$, and $C$ are sets such that $A\cap C=B\cap C$ and $A\cup C=B\cup C$, does it follow that $A=B$?

We will show that $A \subseteq B$ and $B \subseteq A$. Let $x$ be an arbitrary element of $A$. Case 1: $x \in C$. If $x \in A$ and $x \in C$, then $x \in A \cap C$. Since $A \cap C = B \cap C$, then $x \in B \cap C$, which implies $x \in B$. Case 2: $x \notin C$. If $x \in A$, then clearly $x \in A \cup C$. Since $A \cup C = B \cup C$, then $x \in B \cup C$. Because $x \in B \cup C$ but $x \notin C$, it must be that $x \in B$. In both cases, $x \in A \implies x \in B$, so $A \subseteq B$. The argument is symmetric for $B \subseteq A$. Thus, $A=B$.

(16 Spring) Prove that $A$ and its power set $\mathcal{P}{(A)}$ cannot have the same cardinality.

We assume for the sake of contradiction that $|A| = |\mathcal{P}(A)|$. This implies there exists a bijection $f: A \to \mathcal{P}(A)$. Consider the set $S = {x \in A : x \notin f(x)}$. Since $S$ is a subset of $A$, $S \in \mathcal{P}(A)$. Because $f$ is a bijection (specifically surjective), there must exist some element $c \in A$ such that $f(c) = S$. If $c \in S$, by the definition of $S$, $c \notin f(c)$. Since $f(c) = S$, this means $c \notin S$. (Contradiction). If $c \notin S$, by the definition of $S$, $c \in f(c)$. Since $f(c) = S$, this means $c \in S$. (Contradiction). Both cases lead to a contradiction. Therefore, no such bijection $f$ exists. Since $|\mathcal{P}(A)| > |A|$ (trivial for finite sets, true for infinite), they cannot have the same cardinality.

(14 Spring) Suppose that $f:A\rightarrow \mathcal{P}{(A)}$ is a function from a set to its power set. Let $B={x\in A:x\notin f(x)}$, and let $c$ be an element of $A$. Show that $f(c)\ne B$ by deriving a contradiction from the assumption $f(c)=B$.

Let $B = {x \in A : x \notin f(x)}$. Assume there exists $c \in A$ such that $f(c) = B$. We check if $c$ is in $B$: $c \in B \iff c \in {x \in A : x \notin f(x)} \iff c \notin f(c)$. Substitute $f(c) = B$ gives us $c \in B \iff c \notin B$. This is a contradiction ($P \iff \neg P$ is always false). Therefore, the assumption $f(c) = B$ must be false.

(21 Spring) Let $G$ be a graph constructed by arranging $n$ vertices around a circle and connecting every pair by an edge, except for pairs of vertices that are next to each other on the circle. For which values of $n$ does this graph have an Euler circuit?

$n$ must be odd (and $n \ge 5$). The graph described is the Complete Graph $K_n$ with the edges of the Cycle Graph $C_n$ removed. The degree of every vertex in $K_n$ is $n-1$. The degree of every vertex in $C_n$ is 2. The degree of every vertex in $G$ is $(n-1) - 2 = n-3$. For a graph to have an Euler circuit, every vertex must have an even degree (and the graph must be connected). Therefore, $n-3 \text{ is even} \iff n \text{ is odd}$.

(19 Spring) For which values of $n$ does the complete graph on $n$ vertices have an Euler circuit?

$n$ is odd. In a complete graph $K_n$, every vertex is connected to every other vertex. The degree of every vertex is $n-1$. For an Euler circuit to exist, the degree of every vertex must be even. Therefore, $n-1 \text{ is even} \implies n \text{ is odd}$.