Given a positive integer $n$, show that for no set of integers modulo $n$, whose size exceeds $1+\sqrt{n+4}$, is it possible that the pairwise sums of unordered pairs be all distinct.
Problem
Source: Romania TST 2016 Day 3 P3
Tags: combinatorics
02.11.2017 18:34
EDIT: The following argument is flawed. The statement in red is false. Sorry. We will prove that for $n\geq 5$ and for any set of $m$ integers modulo $n$, where $m \geq 1+\sqrt{n}$, the pairwise sums of unordered pairs cannot be all distinct. It boils down to consider a circumference $C$ with length $n$ and a set $A$ of $m$ integer points on it. We want to prove that under some integer rotation $\rho$ , there exist $a_1, a'_1, a_2, a'_2\in A$, pairwise distinct, such that $\rho(a_1)=a'_1\,,\,\rho(a_2) = a'_2$. Suppose fore the sake of contradiction, it's not true. Let $A = \{a_0,a_1,\dots,a_{m-1}\}$, where the points $a_i$ are enumerated starting from $a_0$ and going through $C$ on the positive direction. Let $\rho_i\,,\,i=1,2,\dots,m-1$ be corresponding rotations on positive direction for which $\rho_i(a_0) = a_i\,,\,i=1,2,\dots,m-1 $. For each rotation $\rho_i$ , let $A_i$ be the following set of points. First, we set $A'_i := \rho_i(A)\setminus \{a_i\}$. Then, if $\rho(a_i)\in A $ we set $A_i := A'_i\setminus \rho_i(a_i) $,and if $\rho_i^{-1}(a_0)\in A$ , we set $A_i := A'_i\setminus a_0$. It is not possible to hold both $\rho(a_i)\in A$ and $\rho_i^{-1}(a_0)\in A$ , since $m\geq 4$ (because $n\geq 5$) and because of our assumption. Hence $|A_i|\geq m-2$. Now, it is easy to check that the sets $A, A_1,A_2,\dots,A_{m-1}$ are disjoint. It means $|A|+\sum_{i=1}^{m-1}|A_i|\leq n$. Hence: \[m + (m-1)(m-2)\leq n \implies 1+\sqrt{n}+\sqrt{n}(\sqrt{n}-1)\leq n\]which is a contradiction.
03.11.2017 12:25
I don’t understand why $A,A_1,\dots,A_{m-1}$ are disjoint.
10.11.2017 16:44
Indeed, they are not. $A_i$ and $A_j$ have (only) one common point, since $\rho_i(a_j)=\rho_j(a_i)$. Very sorry, it's my bad. Here is another approach, but the most I can do is to prove the claim for $m\geq 2+\sqrt{n+4}$. Map any two points of $A$ to the length of the shortest arc these points divide the circumference. All unordered pairs of points of $A$ are $m(m-1)/2=(m-2+2)(m-2+1)/2\geq (n+4)/2 +3(m-2)/2 +1=n/2+3(m-2)/2+3$, while the possible distinct lengths of the arcs are at most $n/2$. Hence, we have at least $3(m-2)/2 +3$ pairs of unordered pairs, each of them mapped to the same number. If any of those pairs $(a,b)\,,\, (c,d)$ with $b-a=d-c$, is such that $a,b,c,d$ are all distinct, we are done, so suppose such pairs are like $(a,b)\,,\,(b,c)\,,\,b-a=c-b$. The only possibility three pairs to have equal arc's length, namely $(a,b),(b,c),(c,a)$, is when $a,b,c$ divide the circle into three equal arcs. (if there exists other such triple, we are done). To each pair $(a,b)\,,\,(b,c)\,,\,b-a=c-b$ assign the point they meet at, i.e. $b$ (which is a points of the set $A$). Thus, we have at least $3(m-2)/2+2$ pairs and $m$ points of $A$. Since $3(m-2)/2+2>m$ for $m>2$, there exists 2 pairs like $(a,b),(b,c)$ and $(a',b),(b,c')$. But then $(a,a'), (c,c')$ satisfies $a'-a=c'-c$ and $a',a,c',c$ are distinct, that's, we are done.