# 2020-16 A convex function of matrices

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.

GD Star Rating

# Solution: 2020-15 The number of cycles of fixed lengths in random permutations

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.

The best solution was submitted by 이준호 (수리과학과 2016학번). Congratulations!

Here is his solution of problem 2020-15.

GD Star Rating

# 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.

GD Star Rating

# Solution: 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?

The best solution was submitted by 채지석 (수리과학과 2016학번). Congratulations!

Here is his solution of problem 2020-14.

Other solutions were submitted by 강한필 (전산학부 2016학번, +3), 김건우 (수리과학과 2017학번, +3), 이준호 (수리과학과 2016학번, +3), 김유일 (2020학번, +3).

GD Star Rating

# 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?

GD Star Rating

# Notice on POW 2020-13

POW 2020-13 is still open and anyone who first submits a correct solution will get the full credit.

GD Star Rating
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.