Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $n \in \mathbb N$, $n \ge 2$ and let $S_n$ be the symmetric group on $n$ elements.

I will call for shortness $I_n := \{1 , \ldots , n\} \subset \mathbb {N}$. Fix $i_0 \in I_n$ and consider the following statement:

$\forall \sigma \in S_n, \quad \exists i \in I_n, \quad i \ge i_0 \quad \mathrm{ s.t.} \quad \sigma(i)\le i_0$

I think it is true, it seems like an application of pigeonhole but I don't manage to write a formal and clear proof. I also tried with reductio ad absurdum, unsuccessfully.

What would you suggest? Do you think the statement is true? Thanks.

share|cite|improve this question
up vote 2 down vote accepted

If $i_0=n$ then this is immediate. If $i_0\lt n$, then there are $n-i_0+1$ indices greater than $i_0$, and only $n-i_0$ indices strictly greater than $i_0$, so $\sigma$ cannot map $\{i_0,i_0+1,\ldots,n\}$ to $\{i_0+1,\ldots,n\}$ (pigeonhole principle, using the fact that $\sigma$ is one-to-one); hence there exists $i\in \{i_0,i_0+1,\ldots,n\}$ such that $\sigma(i)\notin \{i_0+1,\ldots,n\}$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.