Let a and b be non-negative integers such that $ab \ge c^{2}$ where $c$ is an integer. Prove that there is a positive integer n and integers $x_{1}$, $x_{2}$, $\cdots$, $x_{n}$, $y_{1}$, $y_{2}$, $\cdots$, $y_{n}$ such that \[{x_{1}}^{2}+\cdots+{x_{n}}^{2}=a,\;{y_{1}}^{2}+\cdots+{y_{n}}^{2}=b,\; x_{1}y_{1}+\cdots+x_{n}y_{n}=c\]
Problem
Source:
Tags: induction, inequalities
19.11.2007 20:31
Sorry, my solution is flawed.. I'll try to fix it. Anyway, the official one still stands: Official Solution: We can easily assume $ c\ge0$ and $ a\ge b$. If $ b\ge c$ then set $ x_i=y_i=1$ for $ i=\overline{1,c}$. $ x_{c+1}=\ldots=x_{a-c}=1$. $ y_{c+1}=\ldots=y_{a-c}=0$. Then $ y_{a-c+1}=\ldots=y_{a+b-2c}=1$, while other $ x$'s are $ 0$. Assume now $ a > c > b$. Induction on $ a + b$. If $ a + b = 1,2$ we are easily done. Assume the statement true for $ a + b\le N$. Let now $ a + b = N + 1$. Assume $ a\neq b\neq c\neq a$, which is trivial. Using the nice identity $ (a + b - 2c)b - (c - b)^2 = ab - c^2$, we see that $ (a + b - 2c,b,c - b)$ satisfies the statement. Since $ a + b - 2c + b = a + 2(b - c)\le N$ and $ a + b - 2c > 0$ (otherwise $ ab < c^2$, or $ a = b = c$), we get $ n$-uples $ x_i$ and $ y_i$ for the triple $ (a + b - 2c,b,c - b)$. Then for the triple $ (a,b,c)$ take $ X_i = x_i + y_i$ and $ Y_i = y_i$. It is easy to see that $ \sum X_i^2 = \sum (x_i + y_i)^2 = \sum x_i^2 + 2\sum x_iy_i + \sum y_i^2$ $ = a + b - 2c + 2(c - b) + b = a$ and $ \sum (x_i + y_i)y_i = (c - b) + b = c$ and we are done.
07.11.2011 09:52
the solution follows directly from cauchy schwarz inequality