Category Archives: problem

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-06 A binary maze

A binary maze consists of \(n\) separate rooms. Each room has a teleportation machine but no doors. The numbers \( a_{i,j}\in [n] \) are given for all \( (i,j)\in [n]\times \{0,1\} \). If you shout a number \( j\in \{0,1\} \) while you are in the room \( i \), then the teleportation machine will teleport you to the room \(a_{i,j}\).

You don’t know the numbers \(a_{i,j}\), but it is given that for any \(i\neq i’ \), there exists a way to reach room \( i’ \) from room \( i \) by shouting numbers \( 0 \) and \( 1 \) in some order.

At the beginning, your enemy will teleport you into one of the rooms while your eyes are closed. Your goal is to visit all rooms at least once with your eyes closed. As your eyes are closed, you don’t know which rooms you have visited before and you don’t know which room you are currently at.

So, you decide to pick a sequence \( b=(b_1,\dots, b_s) \in \{0,1\}^s \) before entering the binary maze and decide to shout the numbers \( b_1,\dots, b_s \) in order. Find a lower bound \( \ell(n) \) and an upper bound \( u(n) \) on the minimum length of a sequence which guarantees that you can visit all \( n \) rooms. If your \( \frac{u(n)}{\ell(n)} \) is smaller than some polynomial of \( n \) for all \( n\in\mathbb{N} \) , then you will get full points.

2020-04 Convergence at all but one point

Let \( f_n : [-1, 1] \to \mathbb{R} \) be a continuous function for \( n = 1, 2, 3, \dots \). Define
\[
g_n(y) := \log \int_{-1}^1 e^{y f_n(x)} dx.
\]
Suppose there exists a continuous function \( g: \mathbb{R} \to \mathbb{R} \) and \( y_0 \in \mathbb{R} \) such that \( \lim_{n \to \infty} g_n(y) = g(y) \) for all \( y \neq y_0 \). Prove or disprove that \( \lim_{n \to \infty} g_n(y_0) = g(y_0) \).

2020-03 Graceful permutations

A permutation \( \pi : [n]\rightarrow [n] \) is graceful if \( |\pi(i+1) – \pi(i)| \neq |\pi(j+1)-\pi(j)| \) for all \(i\neq j \in [n-1]\). For a graceful permutation \( \pi :[2k+1] \rightarrow [2k+1] \) with \( \pi(\{2,4,\dots,2k\}) = [k] \), prove that \(\pi(1)+ \pi(2k+1) = 3k+2 \).

2020-01 Another singular matrix

For a given positive integer \( n \), find all non-negative integers \( r \) such that the following statement holds:

For any real \( n \times n \) matrix \( A \) with rank \( r \), there exists a real \( n \times n \) matrix \( B \) such that \( \det (AB+BA) \neq 0 \).

2019-22 Prime divisors of polynomial iterates

Let \(f = X^n + a_{n-1}X^{n-1} + \dots + a_0\in \mathbb{Z}[X]\) be a polynomial with integer coefficients, and let \(m\in \mathbb{Z}\).

Consider the sequence \[f_0,f_1,f_2,\dots \]

where \(f_0:=m\), and \(f_i:=f(f_{i-1})\) for all \(i\ge 1\).

Let \(S:=\{p\in \mathbb{P}: p \text{ divides } f_i \text{ for some } i\ge 0\}\) be the set of prime divisors of the sequence \(f_0,f_1,f_2,\dots\). 

Assume that \(S\) is finite, but \(\{f_i\mid i\ge 0\}\) is infinite. Show that \(f=X^n\).