Difference between revisions of "2010 USAMO Problems/Problem 6"
(→Solution) |
|||
| Line 3: | Line 3: | ||
== Solution == | == Solution == | ||
| − | To find this, assume only the two extremes, that is when the points have the same, with <math> | + | We will prove that the answer is 68 by proving that it is not possible to have 67. |
| + | To find this, assume only the two extremes, that is when the points have the same, with <math>n</math> <math>-n</math> and so on for 67 more times. After I erase all 68 positive or negative for each one, we got 68 points, because there is no way to get less Henceforth we can get at least 68, because quite intuitively, we can erase more if this is not set up this way. | ||
| + | |||
== See Also == | == See Also == | ||
{{USAMO newbox|year=2010|num-b=5|after=Last question}} | {{USAMO newbox|year=2010|num-b=5|after=Last question}} | ||
Revision as of 15:38, 29 March 2012
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
We will prove that the answer is 68 by proving that it is not possible to have 67.
To find this, assume only the two extremes, that is when the points have the same, with 
and so on for 67 more times. After I erase all 68 positive or negative for each one, we got 68 points, because there is no way to get less Henceforth we can get at least 68, because quite intuitively, we can erase more if this is not set up this way.
See Also
| 2010 USAMO (Problems • Resources) | ||
| Preceded by Problem 5 |
Followed by Last question | |
| 1 • 2 • 3 • 4 • 5 • 6 | ||
| All USAMO Problems and Solutions | ||
