Consider a convex \((n+2)\)-gon. Let \(a_n\)​ denote the number of ways to add non-crossing chords to this polygon, including the case where no chords are added (i.e., \(a_0=a_1=1\) and \(a_2=3\)).

Find a recurrence relation for the sequence \(a_n​\) and determine its generating function.

There are \(n+1\) hats, each labeled with a number from \(1\) to \(n+1\), and \(n\) people. Each person is randomly assigned exactly one hat, and each hat is assigned to at most one person (i.e., the assignment is injective). A person can see all other assigned hats but cannot see their own hat and the unassigned hat. Each person must independently guess the number on their own hat.

If everyone correctly guesses their own hat’s number, they win; otherwise, they lose. They may discuss a strategy before the hats are assigned, but no communication is allowed afterward.

Determine a strategy that maximizes their probability of winning.

Consider any sequence \( a_1,\dots, a_n \) of non-negative integers in \(\{0,1,\dots, m\}\). Prove that \[|\{ a_i+ a_j + (j-i): 1\leq i < j \leq n \}|\geq m \] when \(m= \lfloor \frac{1}{4} n^{2/3} \rfloor \).

A bonus problem: Can you find a function \(f(n)=\omega(n^{2/3})\) such that the above statement is true when \(m = f(n) \)? Is there such a function with \(f(n)= \Omega(n)\)? (You would still get full points without answering the bonus question.)

Consider a function \(f: \{1,2,\dots, n\}\rightarrow \mathbb{R}\) satisfying the following for all \(1\leq a,b,c \leq n-2\) with \(a+b+c\leq n\).

\[ f(a+b)+f(a+c)+f(b+c) – f(a)-f(b)-f(c)-f(a+b+c) \geq 0 \text{ and } f(1)=f(n)=0.\]

Prove or disprove this: all such functions \(f\) always have only nonnegative values on its domain.

Acknowledgement: This problem arises during a research discussion between June Huh, Jaehoon Kim and Matt Larson.

Let \(p\) be a prime number at least three and let \(k\) be a positive integer smaller than \(p\). Given \(a_1,\dots, a_k\in \mathbb{F}_p\) and distinct elements \(b_1,\dots, b_k\in \mathbb{F}_p\), prove that there exists a permutation \(\sigma\) of \([k]\) such that the values of \(a_i + b_{\sigma(i)}\) are distinct modulo \(p\).

Let \(\mathbb{S}_n\) be the set of all permutations of \([n]=\{1,\dots, n\}\). For positive real numbers \(d_1,\dots, d_n\), prove \[ \sum_{\sigma\in \mathbb{S}_n} \frac{1}{ d_{\sigma(1)}(d_{\sigma(1)}+d_{\sigma(2)}) \dots (d_{\sigma(1)}+\dots + d_{\sigma(n)}) } = \frac{1}{d_1\dots d_n}.\]

Let \(\phi = \frac{1+\sqrt{5}}{2}\). Let \(f(1)=1\) and for \(n\geq 1\), let
\[ f(n+1) = \left\{\begin{array}{ll}
f(n)+2 & \text{ if } f(f(n)-n+1)=n \\
f(n)+1 & \text{ otherwise}.
\end{array}\right.\]
Prove that \(f(n) = \lfloor \phi n \rfloor\), and determine when \(f(f(n)-n+1)\neq n\) holds.

Determine the minimum number of hyperplanes in \(\mathbb{R}^n\) that do not contain the origin but they together cover all points in \(\{0,1\}^n\) except the origin.

There are light bulbs \(\ell_1,\dots, \ell_n\) controlled by the switches \(s_1, \dots, s_n\). The \(i\)th switch flips the status of the \(i\)th light and possibly others as well. If \(s_i\) flips the status of \(\ell_j\), then \(s_j\) flips the status of \(\ell_i\). All lights are initially off. Prove that it is possible to turn all the lights on.

Let \(\varphi(x)\) be the Euler’s totient function. Let \(S = \{a_1,\dots, a_n\}\) be a set of positive integers such that for any \(a_i\), all of its positive divisors are also in \(S\). Let \(A\) be the matrix with entries \(A_{i,j} = gcd(a_i,a_j)\) being the greatest common divisors of \(a_i\) and \(a_j\). Prove that \(\det(A) = \prod_{i=1}^{n} \varphi(a_i)\).