28th Putnam 1967 Problem A6 a i and b i are reals such that a 1 b 2 ≠ a 2 b 1 . What is the maximum number of possible 4-tuples (sign x 1 , sign x 2 , sign x 3 , sign x 4 ) for which all x i are non-zero and x i is a simultaneous solution of a 1 x 1 + a 2 x 2 + a 3 x 3 + a 4 x 4 = 0 and b 1 x 1 + b 2 x 2 + b 3 x 3 + b 4 x 4 = 0. Find necessary and sufficient conditions on a i and b i for this maximum to be achieved.
Solving in terms of x 3 , x 4 gives x 1 = s 23 /s 12 x 3 + s 24 /s 12 x 4 , x 2 = s 31 /s 12 x 3 + s 41 /s 12 x 4 , x 3 = x 3 , x 4 = x 4 , where s ij = (a i b j - a j b i ). Plot the 4 lines s 23 /s 12 x 3 + s 24 /s 12 x 4 = 0, x 2 = s 31 /s 12 x 3 + s 41 /s 12 x 4 = 0, x 3 = 0, x 4 = 0 in the x 3 , x 4 plane. We get 4 lines through the origin. Evidently x 1 changes sign if we cross the first, x 2 changes sign if we cross the second, x 3 changes sign if we cross the third and x 4 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 s 23 and s 24 are non-zero (otherwise the first line coincides with one of the last two) and that s 31 and s 41 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 s 31 /s 41 is not equal to s 23 /s 24 . After some slightly tiresome algebra that reduces to s 34 non-zero. So a necessary and sufficient condition to achieve 8 is that all s ij are non-zero. 28th Putnam 1967 © John Scholes jscholes@kalva.demon.co.uk 14 Jan 2002