28th Putnam 1967

Problem A6

ai and bi are reals such that a1b2 ≠ a2b1. What is the maximum number of possible 4-tuples (sign x1, sign x2, sign x3, sign x4) for which all xi are non-zero and xi is a simultaneous solution of a1x1 + a2x2 + a3x3 + a4x4 = 0 and b1x1 + b2x2 + b3x3 + b4x4 = 0. Find necessary and sufficient conditions on ai and bi for this maximum to be achieved.



Solving in terms of x3, x4 gives x1 = s23/s12 x3 + s24/s12 x4, x2 = s31/s12 x3 + s41/s12 x4, x3 = x3, x4 = x4, where sij = (aibj - ajbi). Plot the 4 lines s23/s12 x3 + s24/s12 x4 = 0, x2 = s31/s12 x3 + s41/s12 x4 = 0, x3 = 0, x4 = 0 in the x3, x4 plane. We get 4 lines through the origin. Evidently x1 changes sign if we cross the first, x2 changes sign if we cross the second, x3 changes sign if we cross the third and x4 changes sign if we cross the fourth. So we have a different combination of signs in each sector, but the same combination throughout any given sector.

Thus the maximum is achieved when the four lines are distinct, giving 8 sectors (and hence 8 combinations). This requires that s23 and s24 are non-zero (otherwise the first line coincides with one of the last two) and that s31 and s41 are non-zero (otherwise the second line coincides with one of the last two). Finally, the first two lines must not coincide with each other. That requires that s31/s41 is not equal to s23/s24. After some slightly tiresome algebra that reduces to s34 non-zero. So a necessary and sufficient condition to achieve 8 is that all sij are non-zero.



28th Putnam 1967

© John Scholes
14 Jan 2002