Problem:
A blackboard contains 68 pairs of nonzero integers. Suppose that for each positive integer at most one of the pairs and is written on the blackboard. A student erases some of the 136 integers, subject to the condition that no two erased integers may add to 0 . The student then scores one point for each of the 68 pairs in which at least one integer is erased. Determine, with proof, the largest number of points that the student can guarantee to score regardless of which 68 pairs have been written on the board.
Solution:
Solution by Zuming Feng and Paul Zeitz: The answer is 43 .
We first show that we can always get 43 points. Without loss of generality, we assume that the value of is positive for every pair of the form (otherwise, replace every occurrence of on the blackboard by , and every occurrence of by ). Consider the ordered -tuple where denote all the distinct absolute values of the integers written on the board.
Let , which is the positive root of . We consider possible underlining strategies: Every strategy corresponds to an ordered -tuple with \
or . If , then we underline all occurrences of on the blackboard. If , then we underline all occurrences of on the blackboard. The weight of strategy equals the product . It is easy to see that the sum of weights of all strategies is equal to .
For every pair on the blackboard and every strategy , we define a corresponding cost coefficient : If scores a point on , then equals the weight . If does not score on , then equals 0 . Let denote the the sum of of coefficients taken over all . Now consider a fixed pair :
In this case, we assume that . Then every strategy that underlines scores a point on this pair. Then .
In this case, we assume that . We have
By noting that , we can easily conclude that .
We let denote the sum of the coefficients taken over all and . These observations yield that
Suppose for the sake of contradiction that every strategy scores at most 42 points. Then every contributes at most to , and we get , which contradicts .
To complete our proof, we now show that we cannot always get 44 points. Consider the blackboard contains the following 68 pairs: For each of , five pairs of (for a total of 40 pairs of type (a)); For every , one pair of (for a total of pairs of type (b)). We claim that we cannot get 44 points from this initial stage. Indeed, assume that exactly of the integers are underlined. Then we get at most points on the pairs of type (a), and at most points on the pairs of type (b). We can get at most points. Note that the quadratic function obtains its maximum 43 (for integers ) at or . Thus, we can get at most 43 points with this initial distribution, establishing our claim and completing our solution.
This problem was suggested by Zuming Feng.
The problems on this page are the property of the MAA's American Mathematics Competitions