We call a permutation $(a_1, a_2,\cdots , a_n)$ of the set $\{ 1,2,\cdots, n\}$ "good" if for any three natural numbers $i <j <k$, $n\nmid a_i+a_k-2a_j$ find all natural numbers $n\ge 3$ such that there exist a "good" permutation of a set $\{1,2,\cdots, n\}$.
Problem
Source: Iranian TST 2015 second exam p5
Tags: number theory, combinatorics
05.06.2015 13:45
This is ridicoulus for a #5 on an Iran TST... The answer is for all $n=2^k$.First,lets prove this for odd $n$. Consider $2a_2-a_1$.It can't be $a_1$ or $a_2$ $modn$ cause $n$ is odd,so it must be some of $a_3,...a_n$ so we are done.Let $m=2^a*n$,where $n$ is odd.Consider numbers $2^a,2^a*2,2^a*3,....2^a*n$ and do the same we did for odd $n$.For $n=2^k$ we construct the permutation inductively.Base case is trivial($1,3,2,4$).Now,for the inductive step divide the numbers $1,2,...2^k$ in two sets,$E$ and $O$($E$ are evens and $O$ are odds).Now,place $E$ on the first $2^(k-1)$ places such that $2$ is in the place of $1$ in the permutation for $2^{k-1}$,$2a$ is in the place of $a$.Similary,next $2^(k-1)$ places for $O$ such that $2a+1$ is on the place of $a+1$,which ends the inductive step(to be clearer,the inductive step for $k=3$ goes like this:$2,6,4,8,1,5,3,9$.This works cause if you pick $i,j$ such that $i<=2^{k-1}$ and $j>2^k$ their sum will be odd and then WLOG both $i,j$ must be less than $2^{k-1}$ so by inductive hypothesis we can easy conclude that they satisfay so done).
05.06.2015 17:25
junioragd wrote: This is ridicoulus for a #5 on an Iran TST... The answer is for all $n=2^k$.First,lets prove this for odd $n$. Consider $2a_2-a_1$.It can't be $a_1$ or $a_2$ cause $n$ is odd,so it must be some of $a3,...an$ so we are done.Let $m=2^a*n$,where $n$ is odd.Consider numbers $2^a,2^a*2,2^a*3,....2^a*n$ and do the same we did for odd $n$.For $n=2^k$ we construct the permutation inductively.Base case is trivial($1,3,2,4$).Now,for the inductive step divide the numbers $1,2,...2^k$ in two sets,$E$ and $O$($E$ are evens and $O$ are odds).Now,place $E$ on the first 2^(k-1) places such that $2$ is in the place of $1$ in the permutation for 2^(k-1),$2a$ is in the place of $a$.Similary,next 2^(k-1) places for $O$ such that $2a+1$ is on the place of $a+1$,which ends the inductive step. Can you explain more about your solution. the first part and ...
17.03.2016 06:18
My solution: For convenience I will operate on the set $\{0, 1, \ldots , n-1\}$ instead. For $3\le k\le n$, $$a_1+a_k\not\equiv 2a_2\pmod{n}\implies a_k\not\equiv 2a_2-a_1\pmod{n}\implies 2a_2-a_1\equiv a_1\text{ or }a_2\pmod{n}$$Clearly $2a_2-a_1\not\equiv a_2$ else $a_1\equiv a_2$ contradiction; thus, $2a_2-a_1\equiv a_1\implies 2a_2\equiv 2a_1$. If $n>1$ is odd then this reduces to $a_2\equiv a_1$ contradiction; thus, $n$ is even. Now consider the two permutations that consist of the subset of even numbers and subset of odd numbers of the original permutation. I claim that if the original permutation is good, then the even subset divided by two and the odd subset subtracted by one and divided by two must also be good. It is easy to prove; if $\{2a_1, 2a_2, \ldots , 2a_{n/2}\}$ is good mod $2n$ then $\{a_1, a_2, \ldots , a_{n/2}\}$ is good mod $n$ (just divide everything in equivalence by two) and if $\{2a_1+1, 2a_2+1, \ldots , 2a_{n/2}+1\}$ is good mod $2n$ then $\{2a_1, 2a_2, \ldots , 2a_{n/2}\}$ is good mod $2n$ because $a_i+a_k-2a_j$ does not change from variable shifts, and it follows that $\{a_1, a_2, \ldots , a_{n/2}\}$ is good mod $n$. Thus, for a size $n$ permutation to be good, a size $n/2$ permutation must also be good. If $n=a\cdot 2^b$ where $a$ is odd, it follows that for a size $n$ permutation to be good, a size $a$ permutation must also be good; however, unless $a=1$, this is impossible as shown above. Thus, $\boxed{n=2^b}$ are the only possibilities. As for the construction, simply notice that if we permutate the numbers in $\{1, 2, \ldots , n\}$ such that one half is exclusively odd and the other exclusively even, then choosing any $i$ in one half and $k$ in the other half will not yield an $a_j$ because $a_i+a_k$ is odd while $2a_j$ is even; thus, we just need to worry about each half individually and this can be resolved with the induction step.