3
$\begingroup$

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.

1 Answers 1

2

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