### 36th IMO 1995 shortlist

Problem A2

a, b, c are integers such that a ≥ 0, b ≥ 0, ab ≥ c2. Show that for some n we can find integers x1, x2, ... , xn, y1, y2, ... , yn such that x12 + x22 + ... + xn2 = a, y12 + y22 + ... + yn2 = b, x1y1 + x2y2 + ... + xnyn = c.

Solution

If xi, yi is a solution for a, b, c, then -xi, yi is a solution of a, b, -c, so it is sufficient to consider non-negative c. Without loss of generality we may assume a ≥ b. If c ≤ b, then it is easy to give an explicit solution: take xi = yi = 1 for c values of i; xi = 1, yi = 0 for a-c values of i; xi = 0, yi = 0 for b-c values of i. However, there is no obvious explicit solution for c > b (and hence a > b > c). So we use induction on a+b.

If a + b = 0, then a = b = c = 0, so we can take n = 1, x1 = y1 = 0. Suppose it is true for a + b < m. Take a, b, c with a + b = m. As noted above, we may assume a > c > b. Hence a' = a+b-2c, b' = b, c' = c-b is a valid triple with a'+b' < m. So there is a solution xi', yi' for a', b', c'. But now xi = xi' + yi', yi = yi' is a solution for a, b, c.