Find the number of all $\text{permutations}$ of $\left \{ 1,2,\cdots ,n \right \}$ like $p$ such that there exists a unique $i \in \left \{ 1,2,\cdots ,n \right \}$ that : $$p(p(i)) \geq i$$
Problem
Source: Iran MO 3rd round 2016 mid-terms - Combinatorics P1
Tags: Iran, permutations, combinatorics
Tintarn
09.09.2016 23:36
Since $p(p(1)) \ge 1$ always holds, $i=1$ must be this unique number. So $p(p(2))=1, p(p(3))=2$ and inductively $p(p(k))=k-1$ for all $k \ge 1$ while $p(p(1))=n$.
So $\mod n$, we have $p(p(n)) \equiv n-1$ and hence $p(n-1) \equiv p(n)-1$, so $p(n) \equiv n+c$ for some constant $c$ (everything is $\mod n$). But then $p(p(n)) \equiv n+2c \equiv n-1$, so $n \mid 2c+1$.
So for even $n$, we don't have any such permutations and for odd $n=2k+1$, we have to choose $c=k$. So for odd $n=2k+1$, there is exactly one such permutation which is defined by $p(i) \equiv i+k \mod n$.
Garfield
10.03.2017 18:12
Such a troll problem,for me this is algebra,not combo.
We see $p(p(1))\geq 1$ so $p(p(2))<2$ so $p(p(2))=1$,$p(p(3))<3$ and $p(p(3))\neq 1$ so we conclude $p(p(i))=i-1$ for $i\geq 2$ and $p(p(1))=n$ .
Let's say $p(x)=n$ now we know that $p(p(x))=x-1$ so $p(n)=x-1$ and we know $p(1)=x$.Now from $p(p(n))=n-1$ we deduce $p(x-1)=n-1$,in same fashion we prove $p(x-i)=n-i$ $\forall i\leq x-1$ and we can prove $p(n-(i+1))=x-2$ so for choosen $x$ for every other number $j$ we know $p(j)$ is unique.Now from proven identities $p(x-(x-1))=n-(x-1)$ so $p(1)=n-x+1$ so but $p(1)=x$ so we know $x=n-x+1$ so $x=\frac{n+1}{2}$ so for odd $n$ answer is $1$ and for even we don't have solutions.
SDEIBAR
05.09.2017 11:02
that is evident p(p(1))>=1 if f(1)=c c={1,2,...,n} then we can easly find f(n) and then we can easily find f(n-1) and... f(2) for unique so all permutation is all c and it is n.
H.HAFEZI2000
24.07.2018 02:56
bgn wrote: Find the number of all $\text{permutations}$ of $\left \{ 1,2,\cdots ,n \right \}$ like $p$ such that there exists a unique $i \in \left \{ 1,2,\cdots ,n \right \}$ that : $$p(p(i)) \geq i$$ what does it mean????????
Hopeooooo
04.08.2021 20:31
I think the problem nice by permutation graph