2010 USAMO Problems/Problem 6

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

Answer: 43

Attainability: Consider 8 distinct positive numbers. Let there be 5 pairs for each of the numbers including 2 clones of that number. Let there also be 28 pairs that include the negatives of those numbers such that each negative associates with another negative once and exactly once (in graph theoretic terms, a K8). Let x be the number of positives chosen out of these 8 (assume the other chosen numbers are negatives) for erasing; then, the number of points the student scores is , which is maximized at x=5 and x=6, and the maximum value is . Choosing the first 5 numbers as positive and the other three as negative attains this. Hence, 43 is a possible maximum possible score.

Bounding: We use expected values. WLOG all the pairs of numbers with both numbers identical have only positive values. Consider flipping a weighted coin whether to choose the positive number or its negation for each positive number; it chooses positive with probability p. The pairs with both numbers same are chosen with probability p, the pairs (k, -k) are chosen with probability 1, and the pairs (x, y) for distinct x and y that sum to a nonzero number are chosen with probability . We are trying to minimize the expected value, so we can assume that no pairs (k, -k) exist. Let A be the number of (k, k) pairs, and 68-A be the number of (x, y) pairs. The expected number of points scored is . We want to prove this is larger than 42 at all times for some choice of p. If , works for p to give this bound. If , works for p for p to give the desired bound. If , we can use for p to get the desired bound. Hence, in any case, the expected value for the number of points scored across all of these weighted processes is larger than 42, so there exists some case that gives a score of 43. Hence, bounding is complete. We are done with both parts. Q.E.D.

-Solution by thanosaops

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.