uniolympiads Ελληνικά

IMC 2006, Day 2, Problem 4

Let v0v_0 be the zero vector in Rn\mathbb{R}^n and let v1,v2,…,vn+1∈Rnv_1, v_2, \dots, v_{n+1} \in \mathbb{R}^n be such that the Euclidean norm ∣vi−vj∣|v_i - v_j| is rational for every 0≤i,j≤n+10 \le i, j \le n + 1. Prove that v1,…,vn+1v_1, \dots, v_{n+1} are linearly dependent over the rationals.

Original from the official PDFLet v 0 be the zero vector in R n and let v 1 , v 2 , . . . , v n+1 ∈ R n be such that the Euclidean norm |v i − v j | is rational for every 0 ≤ i, j ≤ n + 1. Prove that v 1 , . . . , v n+1 are linearly dependent over the rationals. (20 points)

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

Solution. By passing to a subspace we can assume that v1,…,vnv_1,\ldots,v_n are linearly independent over the reals. Then there exist λ1,…,λn∈R\lambda_1,\ldots,\lambda_n\in\mathbb{R} satisfying

vn+1=∑j=1nλjvjv_{n+1}=\sum_{j=1}^n\lambda_jv_j
We shall prove that λj\lambda_j is rational for all jj. From
−2⟨vi,vj⟩=∣vi−vj∣2−∣vi∣2−∣vj∣2-2\left\langle v_i,v_j\right\rangle=|v_i-v_j|^2-|v_i|^2-|v_j|^2
we get that ⟨vi,vj⟩\left\langle v_i,v_j\right\rangle is rational for all i,ji,j. Define AA to be the rational n×nn\times n-matrix Aij=⟨vi,vj⟩A_{ij}=\left\langle v_i,v_j\right\rangle, w∈Qnw\in\mathbb{Q}^n to be the vector wi=⟨vi,vn+1⟩w_i=\left\langle v_i,v_{n+1}\right\rangle, and λ∈Rn\lambda\in\mathbb{R}^n to be the vector (λi)i(\lambda_i)_i. Then,
⟨vi,vn+1⟩=∑j=1nλj⟨vi,vj⟩\left\langle v_i,v_{n+1}\right\rangle=\sum_{j=1}^n\lambda_j\left\langle v_i,v_j\right\rangle
gives Aλ=wA\lambda=w. Since v1,…,vnv_1,\ldots,v_n are linearly independent, AA is invertible. The entries of A−1A^{-1} are rationals, therefore λ=A−1w∈Qn\lambda=A^{-1}w\in\mathbb{Q}^n, and we are done.

Transcribed from the official solutions, pages 2–3. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?