Key Concepts & Formulas
- $$V - E + F = 2 \text{ (planar graphs)}$$
- $$\sum \deg(v) = 2|E|$$
- $$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$
- $$|A \cup B \cup C| = \sum|A_i| - \sum|A_i \cap A_j| + \ldots$$
- Pigeonhole Principle & its generalizations
- $$\text{Generating function: } \sum a_n x^n$$
- $$\text{Chromatic polynomial } \chi(G, k)$$
- $$C_n = \frac{1}{n+1}\binom{2n}{n}$$
- Stirling numbers of the second kind
- Boolean algebra identities & De Morgan's laws
1Medium
Prove that in any group of 6 people, there exist either 3 mutual acquaintances or 3 mutual strangers. (This is \(R(3,3) = 6\).)
Show Hint
Fix one person. By the pigeonhole principle, they either know at least 3 of the other 5 or don't know at least 3. Then examine the relationships among those 3 people.
2Easy
How many ways can you distribute 15 identical balls into 4 distinct boxes such that each box has at least 2 balls?
Show Hint
First place 2 balls in each box (using 8 balls). Then distribute the remaining 7 balls freely: \(\binom{7 + 4 - 1}{4 - 1} = \binom{10}{3}\).
3Hard
Solve the recurrence \(a_n = 5a_{n-1} - 6a_{n-2} + 2^n\) with \(a_0 = 1\), \(a_1 = 2\). Find a closed-form expression for \(a_n\).
Show Hint
Solve the homogeneous part (roots 2 and 3). For the particular solution, since 2 is a root of the homogeneous equation, try \(a_n^{(p)} = cn \cdot 2^n\). Then combine and use initial conditions.
4Medium
Find the number of onto functions from a set of 5 elements to a set of 3 elements using inclusion-exclusion.
Show Hint
Total functions: \(3^5\). Subtract those missing at least one element: \(\binom{3}{1} \cdot 2^5 - \binom{3}{2} \cdot 1^5 + \binom{3}{3} \cdot 0^5\). This gives \(3^5 - 3 \cdot 2^5 + 3 \cdot 1 = 243 - 96 + 3 = 150\).
5Hard
Find the ordinary generating function for the sequence \(a_n\) = the number of ways to tile a \(2 \times n\) rectangle with \(1 \times 2\) dominoes. Use it to derive a closed form for \(a_n\).
Show Hint
The sequence satisfies \(a_n = a_{n-1} + a_{n-2}\) (Fibonacci numbers). The generating function is \(A(x) = \frac{1}{1 - x - x^2}\). Factor the denominator and use partial fractions.
6Medium
Prove that every tree with \(n \geq 2\) vertices has at least 2 leaves (vertices of degree 1). Then show that a tree on \(n\) vertices has exactly \(n - 1\) edges.
Show Hint
For leaves: consider the longest path in the tree; its endpoints must be leaves (why?). For edges: use induction. Removing a leaf gives a tree on \(n-1\) vertices.
7Hard
Find the chromatic polynomial of the Petersen graph. Determine its chromatic number.
Show Hint
The chromatic number of the Petersen graph is 3. Use the deletion-contraction method, but note the Petersen graph is vertex-transitive. Consider using known results about its structure (it is 3-regular, has girth 5, 10 vertices, 15 edges).
8Easy
Using Boolean algebra, simplify the expression \(F(A,B,C) = A'BC + AB'C + ABC' + ABC\) to a minimal sum-of-products form.
Show Hint
Note that \(ABC\) appears in all terms as a potential absorption. Group: \(ABC + ABC' = AB\), \(ABC + AB'C = AC\), \(ABC + A'BC = BC\). So \(F = AB + AC + BC\).
9Medium
How many permutations of \(\{1, 2, \ldots, 8\}\) have no fixed points (derangements)? Express your answer using the inclusion-exclusion formula and compute the exact value.
Show Hint
$$D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$$ For \(n = 8\): \(D_8 = 8!\left(1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24} - \frac{1}{120} + \frac{1}{720} - \frac{1}{5040} + \frac{1}{40320}\right) = 14833\).
10Hard
Prove that the number of labeled forests on \(n\) vertices (collections of labeled trees) equals \((n+1)^{n-1}\), using a connection to Cayley's formula.
Show Hint
Add a new vertex labeled 0 and connect each tree's root to vertex 0. This creates a labeled tree on \(\{0, 1, \ldots, n\}\). By Cayley's formula, the number of labeled trees on \(n+1\) vertices is \((n+1)^{n-1}\).
11Medium
Prove that among any 52 integers, there exist two whose difference is divisible by 51. Can you strengthen this to find two whose sum or difference is divisible by 100, if you pick 52 integers from \(\{1, \ldots, 100\}\)?
Show Hint
For the first part: consider residues mod 51 (51 pigeonholes, 52 integers). For the second part: pair up numbers that sum to 101: \(\{1,100\}, \{2,99\}, \ldots, \{50,51\}\). These 50 pairs plus the number 101 (not available) — think carefully about what happens.
12Hard
Let \(G\) be a simple graph on \(n\) vertices with more than \(\frac{n^2}{4}\) edges. Prove that \(G\) contains a triangle. (This is the Mantel/Turán theorem for \(r=2\).)
Show Hint
Consider a vertex \(v\) of maximum degree \(d\). Among its \(d\) neighbors, if any two are adjacent, we have a triangle. If not, the \(d\) neighbors form an independent set, and each of the remaining \(n - d - 1\) vertices has degree at most \(n - d\). Count edges and derive a contradiction.