# 2020-18 A way of shuffling cards

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.

GD Star Rating
loading...

# 2020-17 Endomorphisms of abelian groups

Prove or disprove that a surjective homomorphism from a finitely generated abelian group to itself is an isomorphism.

GD Star Rating
loading...

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

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

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

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

GD Star Rating
loading...

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

GD Star Rating
loading...

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

GD Star Rating
loading...

# 2020-10 An inequality with sin and log

Prove that
$\frac{x+\sin x}{2} \geq \log (1+x)$
for $$x > -1$$.

GD Star Rating
loading...

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

GD Star Rating
loading...