Saudi Arabia Mathematical Competitions 2012

We claim that Alice can draw up to $K=\frac{2012^3}{2}$ segments. Since there are $2012^3$ points, conditions (a) and (b) guarantee that Alice can draw at most $K$ segments. We will prove that she can do so.

Let $T=\{1,2,\dots ,2012\}$. We will define a bijection $f:T\to T$ such that for all distinct $i,j\in T$, the inequality $$|f(i)-i|\ne |f(j)-j|$$ holds. We let $$\begin{array}{rl}& (f(1),f(2),\dots ,f(2012))\\ =& (2012,2011,\dots ,1510,504,1509,1508,\dots ,1008,1006,\\ & 1005,\dots ,505,503,502,\dots ,1,1007).\end{array}$$ It is not hard to verify that $f$ satisfies the desired inequality condition.

For each point $(x,y,z)\in S$ such that $z\le 1006$, Alice draws a segment between it and the point $(f(x),f(y),2013-z)$. The $K$ segments she has drawn are easily seen to satisfy (a) and (b). To verify that they satisfy (c), suppose that two segments have the same distance triplets. Assume that the first segment has $(x_1,y_1,z_1)$ where $z_1\le 1006$ as an endpoint, and the second segment has $(x_2,y_2,z_2)$ where $z_2\le 1006$ as an endpoint. The distance triplets of the two segments are $$(|f(x_1)-x_1|,|f(y_1)-y_1|,|2013-2z_1|)$$ and $$(|f(x_2)-x_2|,|f(y_2)-y_2|,|2013-2z_2|)$$ respectively. For them to coincide, we must have that $$(x_1,y_1,z_1)=(x_2,y_2,z_2),$$ a contradiction.

---

Alternative solution.

We will use the following auxiliary result:

Lemma. If $n\equiv 0(\mathrm{mod}4)$, then there exists a permutation $\sigma \in S_n$ such that $$\{|\sigma (i)-i|:i=1,\dots ,n\}=\{0,1,\dots ,n-1\}.(1)$$ Proof of Lemma. Consider the cycle defined by $$\sigma =(1,n,2,n-1,\dots ,\frac{n}{4},\frac{3n}{4}+1,\frac{n}{4}+1,\frac{3n}{4}-1,\dots ,\frac{n}{2}-1,\frac{n}{2}+1,\frac{n}{2}).$$ If $n=4k$, then we have $$|\sigma (1)-1|=4k-1|\sigma (2k+1)-(2k+1)|=1$$ $$|\sigma (2)-2|=4k-3|\sigma (2k+2)-(2k+2)|=3$$ $$|\sigma (k)-k|=2k+1|\sigma (3k-1)-(3k-1)|=2k-3$$ $$|\sigma (k+1)-(k+1)|=2k-2|\sigma (3k)-3k|=0$$ $$|\sigma (k+2)-(k+2)|=2k-4|\sigma (3k+1)-(3k+1)|=2k+2$$ $$|\sigma (2k-1)-(2k-1)|=2|\sigma (4k-1)-(4k-1)|=4k-4$$ $$|\sigma (2k)-2k|=2k-1|\sigma (4k)-4k|=4k-2.$$ Remark. Such a permutation exists if and only if $$n\equiv 0(\mathrm{mod}4)\text{ or }n\equiv 1(\mathrm{mod}4).$$ To see the condition is necessary, notice that those $n$ distinct differences must be, in some order, the numbers $0,1,\dots ,n-1$, as $0\le |\sigma (k)-k|\le n-1,k=1,\dots ,n$. We must have $$\frac{n(n-1)}{2}=\sum _{k=1}^n|\sigma (k)-k|\equiv \sum _{k=1}^n(\sigma (k)-k)\equiv 0(\mathrm{mod}2).$$ In our problem, clearly $2012\equiv 0(\mathrm{mod}4)$. We connect the point $(x,y,z)$ with $(\sigma (x),\sigma (y),2013-z)$, where $z\le 1006$, $x,y\le 2012$, and $\sigma \in S_{2012}$ is the permutation in Lemma. The "distance" of a such segment is $(|x-\sigma (x)|,|y-\sigma (y)|,2013-2z)$. Moreover, for two pairs $(x_1,y_1,z_1),(x_2,y_2,z_2),z_1,z_2\le 1006$, we have $$\{\begin{array}{l}|x_1-\sigma (x_1)|=|x_2-\sigma (x_2)|\\ |y_1-\sigma (y_1)|=|y_2-\sigma (y_2)|\\ 2013-2z_1=2013-2z_2\end{array}$$ so all the "distances" are different and every point lies in some segment. It follows that we have $\frac{2012^3}{2}$ segments.