Maths Olympiad Prep

Library / /2 of 2

Algebra Difficulty 5.8 AIME, harder Prove it United States

Problem:

Given are n+1n+1 real linear equations in nn variables (of the form a1x1+a2x2++anxn=aa_{1} x_{1}+a_{2} x_{2}+\cdots+a_{n} x_{n}=a). Prove that each == sign can be replaced with either \leq or \geq so that the resulting n+1n+1 inequalities have the following property: for every choice of real numbers x1,x2,,xnx_{1}, x_{2}, \ldots, x_{n}, at least one inequality is true.

Solution

Solution:

Henceforth, we assume that every equation has some ai0a_{i} \neq 0, since otherwise it is of the form 0=a0=a, and then we can change it to either 0a0 \leq a or 0a0 \geq a to form an inequality which is always true. We use induction on nn.

If n=1n=1, we have the two equations ax=ba x=b, cx=dc x=d. We can divide out by aa and cc to obtain the two equations x=bx=b', x=dx=d' equivalent to our original equations. Without loss of generality we can assume bdb' \leq d'; then if we form the inequalities equivalent to xbx \geq b', xdx \leq d', at least one of these always holds.

Suppose n>1n>1 and that the statement has been proven for nn equations in n1n-1 variables. Given n+1n+1 equations in nn variables, look at the last equation. By assumption, some coefficient - say the coefficient of xnx_{n} - is nonzero, so we can solve this equation for xnx_{n} in terms of the other variables. Plugging this result into the first nn equations, we obtain nn linear equations in x1,,xn1x_{1}, \ldots, x_{n-1}. By the induction hypothesis, we can replace each of these equalities with a \leq or \geq sign so that, for any choice of x1,,xn1x_{1}, \ldots, x_{n-1}, some one of these nn inequalities is true.

We thus assign either the \leq or the \geq sign for the first nn original equations, and we claim we can choose the sign in our n+1n+1th equation so that this result still holds. Suppose, otherwise, that, either way we choose the sign, some choice of the variables causes all of the inequalities to be violated. If the n+1n+1th equation was a1x1++anxn=aa_{1} x_{1}+\cdots+a_{n} x_{n}=a, then we can choose x1,,xnx_{1}', \ldots, x_{n}' to violate the first nn inequalities so that a1x1++anxn=a<aa_{1} x_{1}'+\cdots+a_{n} x_{n}'=a'<a, and we can also choose x1,,xnx_{1}'', \ldots, x_{n}'' to violate the first nn inequalities so that a1x1++anxn=a>aa_{1} x_{1}''+\cdots+a_{n} x_{n}''=a''>a. Now, consider what happens when we set
xi=[aa]xi+[aa]xiaa. x_{i}=\frac{\left[a''-a\right] x_{i}'+\left[a-a'\right] x_{i}''}{a''-a'}.
The n+1n+1th equation now holds (as an equality), since
i=1nai[aa]xi+[aa]xiaa=[aa]i=1naixi+[aa]i=1naixiaa=[aa]a+[aa]aaa=a. \sum_{i=1}^{n} a_{i}\frac{\left[a''-a\right] x_{i}'+\left[a-a'\right] x_{i}''}{a''-a'}=\frac{\left[a''-a\right] \sum_{i=1}^{n} a_{i} x_{i}'+\left[a-a'\right] \sum_{i=1}^{n} a_{i} x_{i}''}{a''-a'}=\frac{\left[a''-a\right] a'+\left[a-a'\right] a''}{a''-a'}=a.
We claim that each of the first nn inequalities is still violated. Suppose, for example, that the inequality c1x1++cnxncc_{1} x_{1}+\cdots+c_{n} x_{n} \leq c is violated, so that c1x1++cnxn>cc_{1} x_{1}'+\cdots+c_{n} x_{n}'>c and c1x1++cnxn>cc_{1} x_{1}''+\cdots+c_{n} x_{n}''>c. We can multiply the first of these inequalities by aaa''-a and the second by aaa-a' (preserving their signs, since these quantities are positive), add them, and divide by aaa''-a' to obtain
i=1nci[aa]xi+[aa]xiaa>c, \sum_{i=1}^{n} c_{i}\frac{\left[a''-a\right] x_{i}'+\left[a-a'\right] x_{i}''}{a''-a'}>c,
as claimed. The \geq case is, of course, analogous. Thus, we have found values of xix_{i} for which the n+1n+1th equality holds but none of the first nn inequalities hold. But this contradicts the way the first nn signs were chosen. So our assumption was wrong, and it was indeed possible to choose the sign of the n+1n+1th inequality so that there would always be at least one true inequality, completing the induction step and the proof.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.