Let $n$ and $a \leq n$ be two positive integers. There's $2n$ people sitting around a circle reqularly. Two people are friend iff one of their distance in the circle is $a$(that is , $a-1$ people are between them). Find all integers $a$ in terms of $n$ st we can choose $n$ of these people , no two of them positioned in front of each other(means they're not antipodes of each other in the circle) and the total friendship between them is an odd number.
Problem
Source: Iran MO 2023 3rd round , Combinatorics exam P1
Tags: combinatorics
01.09.2023 14:07
The answer is all $a$ s.t. $n-a$ is odd. Mark these people with $1 \sim 2n$ in order. If we choose $1 \sim n$, there are exaclty $n-a$ pairs of friends because for all $1\leq k\leq n-a$, $(k,k+a)$ are friends and that's all. Now we prove that $n-a$ must be odd if the condition is satisfied. Assume we choose $a_1,a_2,\dots,a_n$. Because no two of them are positioned in front of each other, for all $1\leq k \leq n$, at most one person is chosen between $k$ and $k+n$. Therefore, WLOG we can assume $a_k = k + b_k n$, where $b_k\in\{0,1\}$. Consider $a_i,a_j (1\leq i<j\leq n)$. If they are friends, we have $a_j-a_i=(j-i)+(b_j-b_i)n \equiv \pm a \pmod{2n}.$ -- If $b_i = b_j$, we have $a_j - a_i = j-i = a$. -- If $b_i \neq b_j$, we have $a_j-a_i = j+n-i = 2n-a$ or $a_i-a_j = i+n-j=a$, both implies $j-i = n-a$. As a result, all possible friendship among $a_1 \sim a_n$ can be divided into two groups: -- $(a_k,a_{k+a}) (1\leq k\leq n-a)$. They are friends iff $b_k=b_{k+a} \iff b_k+b_{k+a}+1$ is odd. -- $(a_k,a_{k+n-a}) (1\leq k\leq a)$. They are friends iff $b_k \neq b_{k+n-a} \iff b_k+b_{k+n-a}$ is odd. Therefore, the total friendship among $a_1\sim a_n$ is an odd number is equivalent to the value below is an odd number: $$ \sum_{k=1}^{n-a} (b_k+b_{k+a}+1) + \sum_{k=1}^a (b_k+b_{k+n-a}) = 2\sum_{k=1}^n b_k + (n-a). $$This implies $n-a$ is odd.
13.09.2023 11:40
first , number people in clockwise order from $0$ to $ 2n-1$ . imagine those who we choose have red shirt and those who we do not choose have blue shirt. we want to prove a more powerful thing : the number of friendships has same paity with $n-a$ we whould prove that the number of pairs k,l wuch that k-l=a and k,l both have red shirt has same parity with $n-a$ 1)) for $a=1$ . 1) if $1$ and $n+1$ both have same colour , the number of consecutive numbers from $1$ to$ n$ with diffrent shirt is even $n,n+1$ have diffrent shirts and 1,2n have diffrent shirts . so , the number of diffrent consecutive shirts is 2*odd note that $k,k+1$ are red iff people in front of them are blue . which means the number of consecutive red shirts is $(2n-2*odd)/2=n-odd$ which hase same parity with $n-1$ 2)) if $1$ and $n+1$ have diffrent colour we can use the same approach and solve the problem when $a=1$ now let's solve problem for n>1: 1) the problem when 2n|[n,a] : $A(i)={i+ak mod 2n|0<k<=n/gcd(n,a)} $for $ 0<i<=2gcd(n,a)$ if $k,l$ are friends , k,l are in a same set . we can place $i+a,...,i+[n,a]$ on a circle . the number of cosecutive diffrent shirts is even . so , the number of consecutive red shirts is $gcd(n,a)*(n/gcd(n,a))=n$ $v_2(n)<max{v_2(n),v_2(a)} $-->$ v_2(n)<v_2(a)$ -> a is even --> friendships have same parity with n-a 2) problem when [n,a]/n is odd : $A_i={i+ak mod 2n | 0<k<=2n/gcd(a,n)} 0<i<=gcd(n,a)$ for each $A_i$ , number of friendships is $n/gcd(a,n) -1 $ --> number of fiendships have same parity with $n-gcd(a,n)$ if a is even --> n is even --> friendships are even if a is odd --> friendships have same parity with$ n-1$ or$ n-a$
29.06.2024 21:10
Answer: All $a$ of different parity then $n$ Construction: Choose $n$ consecutive people along the circle. There will be $n-a$ friends amongst them, as desired. Bound: Notice that one person must be chosen out of every two that face each other. Define a swap as unselecting a chosen person and choosing the person that he faces. We claim that a swap preserves the parity of the number of chosen friends, which is sufficient. Assume we are to swap $A$ with $B$. Let $A_R$ be the friend of $A$ to the right and $A_L$ be the friend of $A$ to the left. Define $B_R$ and $B_L$ similarly. Notice the $A_L$ and $B_L$ and $A_R$ and $B_R$ are both antipodes so one of each of them has to have been chosen. The case $a=n$ and $a=\frac{n}{2}$ can be easily resolved, otherwise a swap preserves parity by a quick casework.