INTRODUCING 5 - days-a-week problem solving session for Math Olympiad and ISI Entrance. Learn More

# Understand the problem

[/et_pb_text][et_pb_text _builder_version="3.22.4" text_font="Raleway||||||||" background_color="#f4f4f4" box_shadow_style="preset2" custom_margin="10px||10px" custom_padding="10px|20px|10px|20px"]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, there exists an integer $0<\ell  such that all three coordinates of $\overline{v_j} -\ell \cdot \overline{v_k}$ is divisible by $p$. Prove that $n\leqslant 6$.

[/et_pb_text][/et_pb_column][/et_pb_row][et_pb_row _builder_version="3.25"][et_pb_column type="4_4" _builder_version="3.25" custom_padding="|||" custom_padding__hover="|||"][et_pb_accordion open_toggle_text_color="#0c71c3" _builder_version="3.26.6" toggle_font="||||||||" body_font="Raleway||||||||" text_orientation="center" custom_margin="10px||10px"][et_pb_accordion_item title="Source of the problem" open="on" _builder_version="3.26.6"]

Kürschák Competition 2018[/et_pb_accordion_item][et_pb_accordion_item title="Topic" _builder_version="3.26.6" open="off"]Number Theory[/et_pb_accordion_item][et_pb_accordion_item title="Difficulty Level" _builder_version="3.26.6" open="off"]Hard[/et_pb_accordion_item][et_pb_accordion_item title="Suggested Book" _builder_version="3.22.7" open="off"][/et_pb_accordion_item][/et_pb_accordion][et_pb_text _builder_version="3.22.4" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3" custom_margin="48px||48px" custom_padding="20px|20px|20px|20px"]

[/et_pb_text][et_pb_tabs active_tab_background_color="#0c71c3" inactive_tab_background_color="#000000" _builder_version="3.26.6" tab_text_color="#ffffff" tab_font="||||||||" background_color="#ffffff"][et_pb_tab title="Hint 0" _builder_version="3.22.4"]Do you really need a hint? Try it first!

[/et_pb_tab][et_pb_tab title="Hint 1" _builder_version="3.26.6"]Prove that any two vectors are either perpendicular or colinear.[/et_pb_tab][et_pb_tab title="Hint 2" _builder_version="3.26.6"]

Note that $p^2| |\overline{v_j}-\ell\cdot\overline{v_k}|^2$. This implies that $p^2|\langle \overline{v_j},\overline{v_k}\rangle$. Also, from the Cauchy-Schwarz inequality we get $|\overline{v_j}|\cdot |\overline{v_k}|\ge |\langle\overline{v_j}.\overline{v_k}\rangle|$ hence $-|\overline{v_j}|\cdot |\overline{v_k}|\le\langle\overline{v_j}.\overline{v_k}\rangle\le |\overline{v_j}|\cdot |\overline{v_k}|$. Also, $latex | \overline{v_j}|\cdot |\overline{v_k}|=p^2$. As the dot product is also divisible by $p^2$, it has to be equal to $\pm p^2$ or 0. It cannot be $p^2$ because the vectors are distinct, hence it is either $-p^2$ or 0. Thus the two vectors are either perpendicular or colinear (adding to 0).

[/et_pb_tab][et_pb_tab title="Hint 3" _builder_version="3.26.6"]

Let us plot the vectors in $\mathbb{R}^3$ and identify them with their tips (as the tails are at the origin). We join two tips by a straight line segment if they correspond to perpendicular vectors. Show that the number of straight lines is at least $\frac{n(n-2)}{2}$. Also prove that, there do not exist 4 vectors such that every possible pair of tips is joined by a line segment.

[/et_pb_tab][et_pb_tab title="Hint 4" _builder_version="3.26.6"]From the last assertion, show that the number of straight line segments in the figure is at most $\frac{n^2}{3}$ (this is a special case of a result called Turan's theorem). Thus, $\frac{n^2}{3}\ge \frac{n(n-2)}{2}$. Hence $n\le 6$. [/et_pb_tab][/et_pb_tabs][et_pb_text _builder_version="3.26.4" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3" custom_margin="48px||48px" custom_padding="20px|20px|20px|20px"]

# Watch video

[/et_pb_text][et_pb_code _builder_version="3.26.4"]