Let \( A \) be an \( n \times n \) Hermitian matrix and \( \lambda_1 (A) \geq \lambda_2 (A) \geq \dots \geq \lambda_n (A) \) the eigenvalues of \( A \). Prove that for any \( 1 \leq k \leq n \)
\[
A \mapsto \lambda_1 (A) + \lambda_2 (A) + \dots + \lambda_k (A)
\]
is a convex function.
Category Archives: problem
2020-15 The number of cycles of fixed lengths in random permutations (modified)
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.
2020-14 Connecting dots probabilistically
Say there are n points. For each pair of points, we add an edge with probability 1/3. Let \(P_n\) be the probability of the resulting graph to be connected (meaning any two vertices can be joined by an edge path). What can you say about the limit of \(P_n\) as n tends to infinity?
2020-13 An integral sequence
Let \( a_n \) be a sequence defined recursively by \( a_0 = a_1 = \dots = a_5 = 1 \) and
\[
a_n = \frac{a_{n-1} a_{n-5} + a_{n-2} a_{n-4} + a_{n-3}^2}{a_{n-6}}
\]
for \( n \geq 6 \). Prove or disprove that every \( a_n \) is an integer.
2020-12 Draws on a chess tournament
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.
2020-11 Free group of rank 2
Show that there is a subgroup of a free group of ran 2 that is not finitely generated.
2020-10 An inequality with sin and log
Prove that
\[
\frac{x+\sin x}{2} \geq \log (1+x)
\]
for \( x > -1 \).
2020-09 Displacement of permutations
For a permutation \(\pi: [n]\rightarrow [n]\), we define the displacement of \(\pi\) to be \(\sum_{i\in [n]} |i-\pi(i)|\).
For given \(k\), prove that the number of even permutations of \([n]\) with displacement \(2k\) minus the number of odd permutations of \([n]\) with displacement \(2k\) is \((-1)^{k}\binom{n-1}{k}\).
2020-08 Geometric action revisited
In the problem 2019-08 (https://mathsci.kaist.ac.kr/pow/2019/2019-08-group-action/), we considered a group G acting by isometries on a proper geodesic metric space X properly discontinuously and cocompactly. Such an action is called a geometric action. The conclusion was that a geometric action leads to that G is finitely generated.
Would this conclusion still hold in the case the space X is not necessarily proper?
2020-07 Perfect square
Suppose that \( x, y, z \) are positive integers satisfying
\[
0 \leq x^2 + y^2 – xyz \leq z+1.
\]
Prove that \( x^2 + y^2 – xyz \) is a perfect square.