Bariz - Problem

Source: Kürchák 2018 P2

Tags: vector, analytic geometry, number theory, prime numbers

ThE-dArK-lOrD

08.10.2018 09:01

Given a prime number $p$ and let $\overline{v_1},\overline{v_2},\dotsc ,\overline{v_n}$ be $n$ distinct vectors of length $p$ with integer coordinates in an $\mathbb{R}^3$ Cartesian coordinate system. Suppose that for any $1\leqslant j<k\leqslant n$, there exists an integer $0<\ell <p$ such that all three coordinates of $\overline{v_j} -\ell \cdot \overline{v_k} $ is divisible by $p$. Prove that $n\leqslant 6$.

nice problem, It's easy to see that the result is true for $p=2$ See that $p^2| |\overline{v_j} -\ell \cdot \overline{v_k}|^2=> p^2|<v_j,v_k> $ Now , $-p^2 = -|v_j|.|v_k|\le <v_j,v_k> < |v_j|.|v_k|=p^2$ $=> <v_j,v_k> = \{-p^2,0\} => v_j = -v_k $ or $v_j \perp v_k$. Now , consider a graph $G(V,E)$ with $V =\{v_1,v_2,\cdots,v_n\}$ and $E=\{(v_j,v_k):v_j\perp v_k\}$ See that for each vertex in $G$ there are atleast $n-2$ edges.So $|E| \ge \frac{n(n-2)}{2}$ As $Dim(\mathbb{R}^3) =3 => G$ is $K_4$ free .By turan's theorem $|E| \le \frac{n^2}{3}$ $=>\frac{n(n-2)}{2} \le \frac{n^2}{3} => n \le 6$