Permutation Identity

Jumbler · Riemann Hypothesis Offline Joined: 30 Aug 2006 Posts: 319

Suppose that a permutation $(a_1,a_2,...,a_n)$ of $(1,2,...,n)$ satisfies
$\frac{a_k^2}{a_{k+1}}\leq k+2$

for $k=1,2,...,n-1$ .

Prove that it must be the identity permutation.

**Posted:** Sun Nov 01, 2009 12:58 pm

darij grinberg

I don't really see the point of this problem. If $a_k = n$ for some $k < n$ , then $a_{k + 1}\leq n - 1$ and $k + 2\leq n - 1$ , so that $\frac {a_k^2}{a_{k + 1}}\leq k + 2$ is impossible (since $\frac {a_k^2}{a_{k + 1}}\geq\frac {n^2}{n - 1} > n + 1\geq k + 2$ ). Hence, we must have $a_n = n$ . Now proceed by induction over $n$ .

darij

**Posted:** Fri Nov 06, 2009 4:26 pm

_________________
Now the die is cast, the first step taken, a glimmer of hope lights up our lives
Visions of the past, dreams forsaken forming right under our eyes
We are alive...