Difference between revisions of "2010 USAMO Problems/Problem 6"
Thanosaops (talk | contribs) (→Solution) |
|||
| (4 intermediate revisions by 4 users not shown) | |||
| Line 3: | Line 3: | ||
== Solution == | == 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 <math>28 + 5x - {x \choose 2}</math>, which is maximized at x=5 and x=6, and the maximum value is <math>43</math>. 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 <math>1-p^2</math>. 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 <math>Ap + (68-A)(1-p^2)</math>. We want to prove this is larger than 42 at all times for some choice of p. If <math>A < 36</math>, <math>1/2</math> works for p to give this bound. If <math>A > 36</math>, <math>5/8</math> works for p for p to give the desired bound. If <math>A = 36</math>, we can use <math>3/5</math> 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 == | == See Also == | ||
{{USAMO newbox|year=2010|num-b=5|after=Last question}} | {{USAMO newbox|year=2010|num-b=5|after=Last question}} | ||
| + | {{MAA Notice}} | ||
Latest revision as of 16:52, 15 January 2022
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. 
