Maths Olympiad Prep

Track / Stage 6 / 246 of 400 #1246 of 1964

Problem 1246

National olympiad, first round
Algebra Difficulty 6.4 Prove it

17 Let {An=(an,bn)}\left\{A_{n}=\left(a_{n}, b_{n}\right)\right\} be a sequence of vectors with integer components. Prove: There exists a positive integer NN, such that for any vector AnA_{n}, there are NN integers kn,1,kn,2,k_{n, 1}, k_{n, 2}, \cdots, kn,Nk_{n, N}, such that An=i=1Nkn,iAiA_{n}=\sum_{i=1}^{N} k_{n, i} A_{i}.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Prove that for V={i=1kiAiV=\left\{\sum_{i=1}^{\infty} k_{i} A_{i} \mid\right. the integer sequence {ki}\left\{k_{i}\right\} has only finitely many non-zero terms }\}, it is easy to verify that VV has the following property:
For any x,yV,k,lZ,kx+lyVx, y \in V, k, l \in \mathbf{Z}, k x+l y \in V.
(*)

We need to prove: There must exist x1,x2Vx_{1}, x_{2} \in V, such that
V={k1x1+k2x2k1,k2Z} V=\left\{k_{1} x_{1}+k_{2} x_{2} \mid k_{1}, k_{2} \in \mathbf{Z}\right\}

If V={(0,0)}V=\{(0,0)\}, the conclusion is obviously true.
If V{(0,0)}V \neq\{(0,0)\}, let x1=(a,b)x_{1}=(a, b) be the non-zero vector in VV with the smallest norm, and let L={tx1tR}L=\left\{t x_{1} \mid t \in \mathbf{R}\right\}.

Assume tx1Vt x_{1} \in V, and tt is not an integer. We can set t=m+s,mZ,0<s<1t=m+s, m \in \mathbf{Z}, 0<s<1.
For any xVx \in V, there exist real numbers k1,k2k_{1}, k_{2}, such that
x=k1x1+k2x2 x=k_{1} x_{1}+k_{2} x_{2}

If k2Zk_{2} \notin \mathbf{Z}, set k2=u+v,uZ,0<v<1k_{2}=u+v, u \in \mathbf{Z}, 0<v<1.
By property (*), k1x1+vx2Vk_{1} x_{1}+v x_{2} \in V.
Since k1x1+vx2=(k1a+vc,k1b+vd)k_{1} x_{1}+v x_{2}=\left(k_{1} a+v c, k_{1} b+v d\right), and
0<a(k1b+vd)b(k1a+vc)=vadbc<adbc. 0<\left|a\left(k_{1} b+v d\right)-b\left(k_{1} a+v c\right)\right|=v|a d-b c|<|a d-b c| .

This contradicts the choice of x2x_{2}!
Therefore, k2Zk_{2} \in \mathbf{Z}. Combining this with property (*), we know that k1x1Vk_{1} x_{1} \in V, and thus k1Zk_{1} \in \mathbf{Z}.
So, V={k1x1+k2x2k1,k2Z}V=\left\{k_{1} x_{1}+k_{2} x_{2} \mid k_{1}, k_{2} \in \mathbf{Z}\right\}.
Since x1,x2Vx_{1}, x_{2} \in V, there exist positive integers NN and integers m1,i,m2,i(i=1,2,,N)m_{1, i}, m_{2, i} (i=1, 2, \cdots, N), such that
x1=i=1Nm1,iAi,x2=i=1Nm2,iAi x_{1}=\sum_{i=1}^{N} m_{1, i} A_{i}, x_{2}=\sum_{i=1}^{N} m_{2, i} A_{i}

Thus, for any vector AnA_{n}, there exist integers k1,k2k_{1}, k_{2}, such that
An=k1x1+k2x2=i=1N(k1m1,i+k2m2,i)Ai A_{n}=k_{1} x_{1}+k_{2} x_{2}=\sum_{i=1}^{N}\left(k_{1} m_{1, i}+k_{2} m_{2, i}\right) A_{i}

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.