For each $n$ find the number of ways one can put the numbers $\{1,2,3,...,n\}$ numbers on the circle, such that if for any $4$ numbers $a,b,c,d$ where $n|a+b-c-d$. The segments joining $a,b$ and $c,d$ do not meet inside the circle. (Two ways are said to be identical , if one can be obtained from rotaiting the other)
Problem
Source: Iranian Third Round 2020 Combinatorics exam Problem2
Tags: combinatorics, circle, modulo, identical
19.11.2020 20:13
what are "these" n numbers?
20.11.2020 17:15
I am not sure if this works for special cases but at least for large enugh $n$ it should work.First assume that the permutation is cylic Lemma:For any integer $i$ we have: $$2a_i \equiv a_{i-1}+a_{i+1} \pmod n$$Proof:Note that there is some integer $x \neq a_{i-1},x \neq a_{i+1},x \equiv a_{i+1}+a_{i-1}-a_i \pmod n$ if $x$ is not $a_i$ we will get contradiction considering segments $xa_{i},a_{i+1}a_{i-1}$ Hence the result. The lemma is same as$a_{i+1}-a_i \equiv a_i-a_{i-1} \pmod n$ and numbers are of form $a_i=(a_1+(i-1)*c) \pmod n$.It is easy to see that all such sequences work iff $\gcd(c,n)=1$(just consider a particular sum all arces with that sum are paralell.) Now we have to count such sequences.Noting that changing the value of $a_1$ won't change the sequence(all such permutations are cyclic shifts of each other) and changing $c$ between numbers co_prime to $n$ and less than it will give a different sequence (just look at the number after $0$ in clock_wise order).We deduce that the answer is $\phi (n)$.
22.11.2020 17:38
There were two crucial lemmas for solving this problem Lemma $1$: If you consider three adjacent numbers on the circle such as $(a,b,c)$ then $a+c=2b\ (mod\ n)$ Proof: If the lemma is false then there is a number $d$ distinct from $a,b,c$ such that $d+b=a+c\ (mod\ n)$ and we know $(b,d)$ intersects $(a,c)$, a contradiction. So the Lemma is correct! Lemma 2: If for any 3 adjacent numbers $(a,b,c)$ on the circle we have $a+c=2b\ (mod\ n)$ then this sitting of numbers has the problem condition. Proof: Consider the number $1$ and the number adjacent to it (say $a$ for example), then the number adjacent to $a$ is $2a-1\ (mod\ n)$ and the number adjacent to that is $3a-2\ (mod\ n)$ and so on... (If we call the number which has $i-1$ numbers between it and $1$ clockwise $a_i$ then $a_i=ia-i+1$) So now if $(a_i,a_j)$ intersects $(a_k,a_l)$ Without loss of generality we can assume $i<k<j<l<i+n$ and so $$a_k+a_l=(k+l)a-k-l+2=(k+l)(a-1)+2\ne(i+j)(a-1)+2=a_i+a_j\ (mod\ n)$$we are done. now we just need to see when all the $a_i$ are all distinct $mod\ n$ and this is the really easy part and we can see the answer is $\phi(n)$