For a natural number \(n\), let \(a_n\) be the number of congruence classes of triangles whose all three sides have integer length and its perimeter is \(n\). Obtain a formula for \(a_n\).

In a graduation ceremony, \(n\) graduating students form a circle and their diplomas are distributed uniformly at random. Students who have their own diploma leave, and each of the remaining students passes the diploma she has to the student on her right, and this is one round. Again, each student with her own diploma leave and each of the remaining students passes the diploma to the student on her right and repeat this until everyone leaves. What is the probability that this process takes exactly \(k \) rounds until everyone leaves.

For given \(k\in \mathbb{N}\), determine the minimum natural number \(n\) satisfying the following: no matter how one colors each number in \(\{1,2,\dots, n\}\) red or blue, there always exists (not necessarily distinct) numbers \(x_0, x_1,\dots, x_k \in [n]\) with the same color satisfying \(x_1+\dots + x_k = x_0\).

Let \(\mathcal{A}_n\) be the collection of all sequences \( \mathbf{a}= (a_1,\dots, a_n) \) with \(a_i \in [i]\) for all \(i\in [n]=\{1,2,\dots, n\}\). A nondecreasing \(k\)-subsequence of \(\mathbf{a}\) is a subsequence \( (a_{i_1}, a_{i_2},\dots, a_{i_k}) \) such that \(i_1< i_2< \dots < i_k\) and \(a_{i_1}\leq a_{i_2}\leq \dots \leq a_{i_k}\). For given \(k\), determine the smallest \(n\) such that any sequence \(\mathbf{a}\in \mathcal{A}_n\) has a nondecreasing \(k\)-subsequence.

Consider an \(n\) by \(n\) chessboard with white/black squares alternating on every row and every column. In how many ways can one choose \(k\) white squares and \(n-k\) black squares from this chessboard with no two squares in a row or column.

For each \( i \in \mathbb{N}\), let \(F_i\) be the \(i\)-th Fibonacci number where \(F_0=0, F_1=1\) and \(F_{i+1}=F_{i}+F_{i-1}\) for each \(i\geq 1\).
For \(n>m\), we divide \(F_n\) by \(F_m\) to obtain the remainder \(R\). Prove that either \(R\) or \(F_m-R\) is a Fibonacci number.

Alice and Bob play the following game with \( S=\{1,\dots, 777\} \).

Alice picks a number \(x \in S\) without telling anyone and Bob will guess what the number is at the end of the game. Alice is malicious so that she can always change her number \(x\) at any time until the end of the game.

In each round, Bob picks a subset \(T\subseteq S\) and asks a following question to Alice: “is your \(x\) belong to \(T\)?” Alice must say either Yes or No. At the end of the game, Bob guesses her \(x\) first and then Alice reveals her number \(x\) (Alice can still change her number after she listen to Bob’s guess and before revealing her number). According to her final number \(x\), each of her previous answers are determined to be either a truth or a lie.

Bob wins if Alice end up lying more than three times or his answer is correct. Alice wins if Bob’s answer is wrong and at most three of her answers are lies. Prove that if a game consists of twenty rounds, then no matter what Bob does Alice can always win.

Consider the cards with labels \( 1,\dots, n \) in some order. If the top card has label \(m \), we reverse the order of the top \( m \) cards. The process stops only when the card with label \( 1\) is on the top. Prove that the process must stop in at most \( (1.7)^n \) steps.

Let \( m_0=n \). For each \( i\geq 0 \), choose a number \( x_i \) in \( \{1,\dots, m_i\} \) uniformly at random and let \( m_{i+1}= m_i – x_i\). This gives a random vector \( \mathbf{x}=(x_1,x_2, \dots) \). For each \( 1\leq k\leq n\), let \( X_k \) be the number of occurrences of \( k \) in the vector \( \mathbf{x} \).

For each \(1\leq k\leq n\), let \(Y_k\) be the number of cycles of length \(k\) in a permutation of \( \{1,\dots, n\} \) chosen uniformly at random. Prove that \( X_k \) and \(Y_k\) have the same distribution.

There are \(n\) people participating to a chess tournament and every two players play exactly one game against each other. The winner receives \(1\) point and the loser gets \(0\) point and if the game is a draw, each player receives \(0.5\) points. Prove that if at least \(3/4\) of the games are draws, then there are two players with the same total scores.