Algebra
Let \(a, b, c\) be positive real numbers such that \(abc = 1\). Prove that
$$\left(a^3 + b^3 + c^3\right) + \left(\frac{1}{a^3} + \frac{1}{b^3} + \frac{1}{c^3}\right) \ge 2(a + b + c).$$
Hint
Apply AM-GM to each pair \(\left(x^3 + \frac{1}{x^3}\right) \ge 2\). Then show that a stronger bound holds by using the constraint \(abc = 1\) and the power mean inequality.
Find all functions \(f : \mathbb{Q} \to \mathbb{Q}\) such that for all \(x, y \in \mathbb{Q}\):
$$f(x + f(y)) = f(x) \cdot f(y).$$
Hint
Set \(x = 0\) to find \(f(f(y)) = f(0) \cdot f(y)\). Then set \(y = 0\) to find \(f(x + f(0)) = f(x) \cdot f(0)\). Consider what \(f(0)\) must be. Show that \(f\) is either identically zero or an exponential-type function.
Let \(P(x)\) be a polynomial with integer coefficients such that \(P(n)\) divides \(n!\) for every positive integer \(n\). Prove that \(P\) is the zero polynomial or \(\deg(P) \ge 1\) and the leading coefficient of \(P\) is \(\pm 1\).
Hint
Consider the growth rate of \(P(n)\) versus \(n!\). If \(\deg(P) = d\) with leading coefficient \(a\), then \(P(n) \sim a \cdot n^d\). Compare this with the prime factorization of \(n!\) using Legendre's formula. For large primes \(p\), analyze \(p \mid P(p)\).
Let \(a, b, c\) be non-negative reals with \(a + b + c = 3\). Prove that
$$a^2 b + b^2 c + c^2 a + ab^2 + bc^2 + ca^2 \le 6 + abc.$$
Hint
Rewrite the LHS as \((a+b+c)(ab+bc+ca) - 2abc\). Use the constraint \(a+b+c = 3\) to get \(3(ab+bc+ca) - 2abc \le 6 + abc\), i.e., \(3(ab+bc+ca) \le 6 + 3abc\). Now apply Schur's inequality: \(a^3 + b^3 + c^3 + abc \ge ab(a+b) + bc(b+c) + ca(c+a)\), and use Newton's inequalities.
Combinatorics
An \(8 \times 8\) chessboard has its squares colored with 4 colors such that no \(2 \times 2\) square contains all four colors. What is the maximum number of distinct colorings of the board? Prove your answer.
Hint
Consider what the \(2 \times 2\) restriction means locally. In any \(2 \times 2\) sub-square, at most 3 colors appear. Try to characterize valid colorings row by row. Use the transfer matrix method or a direct combinatorial argument.
In a tournament with \(n\) players (every pair plays exactly once, no draws), prove that there exists a player who can reach every other player in at most 2 steps (i.e., either beats them directly or beats someone who beats them).
Hint
Consider the player with the maximum number of wins (out-degree). Let this player be \(v\) with out-neighborhood \(N^+(v)\). For any player \(u\) not beaten by \(v\), \(u\) beat \(v\). But \(u\) must have lost to some player in \(N^+(v)\), otherwise \(u\) beats everyone \(v\) beats plus \(v\), contradicting maximality. Formalize this.
Let \(S = \{1, 2, \ldots, 2n\}\). Find the maximum size of a collection \(\mathcal{F}\) of subsets of \(S\), each of size \(n\), such that any two sets in \(\mathcal{F}\) share at least one element. Prove your answer.
Hint
This is the Erdős-Ko-Rado type problem. Note that for any \(n\)-element subset \(A\), exactly one of \(A\) and its complement \(S \setminus A\) is in the collection (they share no elements). The maximum is \(\binom{2n-1}{n-1}\). To prove the upper bound, pair each set with its complement.
Geometry
Let \(\omega_1, \omega_2, \omega_3\) be three circles such that no two are concentric. Prove that the three radical axes of pairs \((\omega_1, \omega_2)\), \((\omega_2, \omega_3)\), \((\omega_3, \omega_1)\) are concurrent or all parallel.
Hint
Let the power of a point \(P\) with respect to circle \(\omega_i\) be \(d_i(P)\). The radical axis of \(\omega_i\) and \(\omega_j\) is \(\{P : d_i(P) = d_j(P)\}\). If \(P\) lies on two radical axes, then \(d_1(P) = d_2(P) = d_3(P)\), so \(P\) lies on the third. If two radical axes are parallel (same slope), show the third must be parallel too.
In triangle \(ABC\), let \(D, E, F\) be points on sides \(BC, CA, AB\) respectively. Lines \(AD, BE, CF\) are concurrent at point \(P\). Let \(X = EF \cap BC\), \(Y = FD \cap CA\), \(Z = DE \cap AB\). Prove that \(X, Y, Z\) are collinear.
Hint
This is a consequence of Desargues' theorem applied to triangles \(DEF\) and \(ABC\) (which are in perspective from point \(P\)). Alternatively, use trigonometric Ceva + Menelaus. By Ceva's theorem on the concurrency, deduce the Menelaus ratio product for \(X, Y, Z\) equals \(-1\).
Four circles \(\omega_1, \omega_2, \omega_3, \omega_4\) are pairwise externally tangent. Let \(t_{ij}\) denote the common external tangent length between \(\omega_i\) and \(\omega_j\). Prove that
$$t_{12} \cdot t_{34} = t_{13} \cdot t_{24} = t_{14} \cdot t_{23}.$$
Hint
If two circles with radii \(r\) and \(R\) are externally tangent, the external tangent length is \(2\sqrt{rR}\). So \(t_{ij} = 2\sqrt{r_i r_j}\). Then \(t_{12} \cdot t_{34} = 4\sqrt{r_1 r_2 r_3 r_4} = t_{13} \cdot t_{24} = t_{14} \cdot t_{23}\). Alternatively, perform an inversion centered at one tangency point.
Let \(P\) be a point on the circumcircle of triangle \(ABC\). The projections of \(P\) onto lines \(AB, BC, CA\) are \(X, Y, Z\) respectively (forming the Simson line). Prove that the Simson line of \(P\) bisects the segment \(PH\), where \(H\) is the orthocenter of \(ABC\).
Hint
Use the fact that the midpoint of \(PH\) lies on the nine-point circle. Show that the Simson line passes through this midpoint by establishing that the Simson line is the locus of midpoints of \(PQ\) where \(Q\) ranges over a specific set related to the orthocenter. Use complex coordinates with the circumcircle as the unit circle.
Number Theory
Let \(p\) be an odd prime and \(a, b\) be integers with \(p \mid (a + b)\) but \(p \nmid a\) and \(p \nmid b\). Prove that
$$v_p(a^n + b^n) = v_p(a + b) + v_p(n)$$
where \(n\) is odd and \(v_p\) denotes the \(p\)-adic valuation.
Hint
This is the Lifting the Exponent Lemma (LTE). Factor \(a^n + b^n = (a+b)(a^{n-1} - a^{n-2}b + \cdots + b^{n-1})\). The second factor has \(n\) terms. Modulo \(p\), since \(a \equiv -b \pmod{p}\), each term equals \(a^{n-1} \pmod{p}\), so the sum is \(n \cdot a^{n-1} \pmod{p}\). Formalize the valuation computation.
Find all pairs of positive integers \((m, n)\) such that
$$2^m + 3^n = k^2$$
for some positive integer \(k\).
Hint
Check small cases: \(m=4, n=2\) gives \(16+9=25=5^2\). For systematic analysis, work modulo 4: \(3^n \equiv k^2 - 2^m \pmod{4}\). If \(m \ge 2\), then \(k^2 \equiv 3^n \pmod{4}\). Since \(k^2 \equiv 0\) or \(1 \pmod{4}\), and \(3^n \equiv 3\) or \(1 \pmod{4}\), we need \(n\) even. Set \(n = 2j\) and factor \(k^2 - 3^{2j} = 2^m\).
Prove that for every prime \(p > 3\), the sum
$$1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{p-1} \equiv 0 \pmod{p^2}$$
where fractions are interpreted modulo \(p^2\) (using modular inverses).
Hint
This is Wolstenholme's theorem. Pair up terms: \(\frac{1}{k} + \frac{1}{p-k} = \frac{p}{k(p-k)}\). The sum becomes \(p \cdot \sum \frac{1}{k(p-k)}\) for \(k=1\) to \(\frac{p-1}{2}\). Now show that \(\sum \frac{1}{k(p-k)} \equiv 0 \pmod{p}\) by analyzing the sum modulo \(p\) using properties of modular inverses.
Let \(a > b \ge 1\) be coprime integers. Prove that for every integer \(n \ge 3\) (with the exception \((a,b,n) = (2,1,6)\)), there exists a prime \(p\) that divides \(a^n - b^n\) but does not divide \(a^k - b^k\) for any positive integer \(k < n\).
Hint
This is Zsygmondy's theorem. Such a prime is called a primitive prime divisor. Consider the cyclotomic polynomial \(\Phi_n(a/b)\) after clearing denominators. Show that \(\Phi_n(a,b) = \prod_{d \mid n} (a^d - b^d)^{\mu(n/d)}\) has a prime factor not dividing any \(a^k - b^k\) for \(k < n\), using properties of the order of \(a/b\) modulo primes.