The even positive integers. If $ n$ is good then there exists a permutation $ \sigma$ with the desired property. Consider the graph of $ \sigma$ that is the bipartite graph whose sets of vertices are the positive integers from $ 1$ to $ n$, two being connected, say $ a$ and $ b$, iff $ \sigma (a) = b$. The edges connecting two integers with the same parities use as many even (resp. odd) integers in both sets. This there are the same number of even integers $ x$ such that $ \sigma (x)$ is odd than odd integers $ x$ such that $ \sigma (x)$ is even. It follows that the numebr of $ x$ such that $ x$ and $ \sigma (x)$ have opposite parities is even. Thus, the sum of all the $ |\sigma(x) -x|$ is even, so that $ n$ is even. In the other hand, if $ n=2p$ then consider the permutation $ \sigma$ such that $ \sigma(1)=p+1$ and $ \sigma(p+1)=1$ and $ \sigma(x) =x$ in all the other cases. It is easy to verify that $ \sigma$ has the desired property so that $ n$ is a solution of the problem. Pierre.

Ooops... I think I misread the problem, I tought there was a sum.... Pierre.

pohoatza wrote: Let $ n$ be a nonzero positive integer. Find $ n$ such that there exists a permutation $ \sigma \in S_{n}$ such that \[ \left| \{ |\sigma(k) - k| \ : \ k \in \overline{1, n} \}\right | = n.\] \] just an idea, not the complete solution. if $ n$ is solution then $ 3n+1$ is solution so $ 3^{p}n+\frac{3^p-1}{2}$ is solution. $ \exists f\in S_{n}: \ \{ |f(k) - k| \ : \ k \in \overline{1, n} \}=\{0,1,2,...,n-1\}$ we take $ F\in S_{3n+1}$ such that $ \forall x\in\{n+2,n+3,...,2n+1\}: \ F(x)=f(x-n-1)$ and $ F(x)=x$ in all the other cases we take $ g=Foh\in S_{3n+1}$ such that $ \forall x\in\{n+1,n+2,...,2n+1\}: h(x)=x$ and: $ h(x)=(3n+1)-x+1$ if $ x\le n$ $ h(x)=(3n+1)-x+2$ if $ x\ge 2n+2$ $ h(n+1)=1$ $ \{ |g(k) - k| \ : \ k \le n+2 \}=\{n,n+2+2k: \ k=0...n-1\}$ $ \{ |g(k) - k| \ : \ k \ge 2n+1 \}=\{n+1+2k: \ k=0...n-1\}$ $ \{ |g(k) - k| \ : \ k \in\{n+2,...,2n+1\} \}=\{0,1,2,...,n-1\}$ then $ |\{ |g(k) - k| \ : \ k \in\{1,2,...,3n+1\} \}|=|\{0,1,2,...,3n\}|=3n+1$ for exemple $ n=4$ is solution for $ f=(1\ 4\ 2)$ then $ n=3^{n}4+\frac{3^n-1}{2} is solution$

I hope I do not misread again... More precisely, we must have $ n = 0,1 \mod[4]$. First, let $ \sigma$ be a permutation with the desired property. Let $ d_i = |\sigma (i) - i |$ for each $ i$. Note that $ 0 \leq d_i \leq n-1$, thus the $ d_i$'s give exactly the values $ 0,\cdots, n-1.$ It follows that $ \sum_i d_i = \frac{n(n-1)}2$. We want to prove that this sum is even. - If $ n$ is even, there are $ \frac n 2$ even integers and $ \frac n 2$ odd integers in $ \{1,\cdots , n \}$. Let $ p$ be such that there are $ \frac n 2 - p$ even integers $ i$ such that $ \sigma(i)$ is odd. Since there are $ \frac n 2$ odd integers $ \sigma(i)$, it remains $ p$ odd integers $ i$ such that $ \sigma(i)$ is also odd. It follows that there are $ \frac n 2 - p$ odd integers $ i$ such that $ \sigma(i)$ is even and $ p$ even integers $ i$ such that $ \sigma(i)$ is even. It follows that $ \sum_i d_i = n-2p = 0 \mod[2].$ - If $ n$ is odd, there are $ \frac {n-1} 2$ even integers and $ \frac {n+1} 2$ odd integers in $ \{1,\cdots , n \}$. As above, let $ p$ be such that there are $ \frac {n-1} 2 - p$ even integers $ i$ such that $ \sigma(i)$ is odd. Then there are $ p+1$ odd integers $ i$ such that $ \sigma(i)$ is also odd. It follows that there are $ \frac {n+1} 2 - (p+1)$ odd integers $ i$ such that $ \sigma(i)$ is even. It follows that $ \sum_i d_i = (\frac {n-1}2-p ) + (\frac{n+1}2 -(p+1))=n-1-2p= 0 \mod[2].$ Now, for $ n=4$ we may consider the permutation $ 4,1,3,2$. And for $ n=5$, we have the 'good' permutation $ 5,2,4,1,3$. I think, we may probably construct good permutations in each cases by induction, as done by aviateurpilot... Pierre.

hi pbornsztein, you konw that $ x\equiv |x|(mod\ 2)$ so $ \frac{n(n-1)}{2}=\sum_{i}d_i\equiv \sum_{i} f(i)-i (mod\ 2)\equiv \sum_if(i)-\sum_ii(mod\ 2)\equiv 0(mod\ 2)$

pbornsztein wrote: I hope I do not misread again... I think, we may probably construct good permutations in each cases by induction, as done by aviateurpilot... Pierre. Can you complete your proof？ I don't think the left is easy.

shfdfzhjj wrote: pbornsztein wrote: I hope I do not misread again... I think, we may probably construct good permutations in each cases by induction, as done by aviateurpilot... Pierre. Can you complete your proof？ I don't think the left is easy. yes , I think so .

http://mathcentral.uregina.ca/mp/previous2001/aug02sol.html

This link redirects here, which is locked. This was the problem of RMO 2011, which held today only ( 4 december according to indian time) The user solo1729 is a cheater...

Sorry for reviving, but does anyone has a inductive construction? I‘ve tried but found it hard to accomplish.