Take the 2-minute tour ×
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.

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|improve this question
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.