Zuming's comment on this problem: Golden Ratio. I think an 16/25 blocking set was discovered by ZerAn, so it is not true that in general the answer is ceil(2n/3) if you replace 68 with n. Golden Ratio would make this problem... 42 or 43?

I think the following is an argument that $N$ is at least 43. Let $p$ be $\frac{\sqrt{5} - 1}{2}$, the inverse golden ratio. It satisfies $1 - p^2 = p$, and is between $\frac{1}{2}$ and $1$. By replacing $k$ with $-k$ everywhere if necessary, we may assume that the only pairs of the form $(k, k)$ occur when $k$ is positive. Let $S$ be the set of integers constructed (randomly) in the following way. For every positive integer $k$, place $k$ in $S$ with probability $p$ and otherwise place $-k$ in $S$. Now let's erase every integer in $S$. For a pair of the form $(k, k)$, its integers will be erased with probability $p$. For a pair of the form $(k, -k)$, one of its integers will be erased with probability $1$. For a pair of the form $(x, y)$, where $y \ne \pm x$, the $x$ will be erased with probability at least $1 - p$ and the same for $y$; hence the probability that at least one of them is erased is at least $1 - p^2$, which is equal to $p$. So for every pair, at least one of its integers is erased with probability at least $p$. By linearity of expectation, that means the expected number of pairs with an erasure is at least $68p$. Since $p > \frac{42}{68}$, that means the expected number of pairs with erasure is more than $42$. Hence there is some way to erase more than $42$ pairs. So $N$ is at least $43$. I haven't shown that $43$ is achievable.

That's really nice, Ravi B... Here's what we came up with for 43: 5 copies of (1,1), (2,2), . . ., (8,8) One copy each of (x,y) with 0 > x > y > -9.

This problem has the unfortunate problem that it was ambiguously worded. Based on the people I have talked to, the consensus is that "At most one of A and B" is ambiguous, meaning either that you can have either one A, one B, or neither, or that it could mean that you can have as many As as you want, as long as there are no Bs. Does anyone happen to know whether the other interpretation changes the answer?

The thing I'm still trying to figure out is why they picked 68. Below is the only point in our reasoning that we were able to make it come up, but it's incredibly unsatisfying. In building our solution we made the following assumption (for various experimental reasons): we use only the integers in the range $-n\leq i\leq n$, we take $a$ copies of each $(+k,+k)$, and we take $b$ copies of the complete graph on the negative integers. (So in Richard's explanation, he takes $n=8$, $a=5$, and $b=1$.) We set this system up, mumbled something about linear programming, and decided that we had to have $\frac b{a+b}=\frac{1}{n-2}$. This means that for this specific family of graphs and a given $n$, the nicest solution has $n-3$ copies of each $(+k,+k)$, and one copy of each $(-i,-j)$ for $i\neq j$. The total number of pairs you write on the blackboard for this arrangement is: \[(n-3)n+\binom n2=\frac n2(3n-7).\] (Notice that $n=3$ is a massive failure, which sent us down the wrong path for a long time.) This gives the sequence $10,20,33,49,68,90,\ldots$. Woohoo, there's 68. The winning strategy chooses either $(-1,-2,3,4,5,\ldots)$ or $(-1,-2,-3,4,5,\ldots)$ (that's an appearance of the linear programming intuition) and erases \[(n-1)+(n-2)+(n-2)(n-3)=n^2-3n+3\] edges. The fraction of the pairs which are in the winning set is \[\frac{n^2-3n+3}{\frac n2(3n+7)}.\] Magically, this function is minimized at some $n$ just shy of 8, and minimized along the integers at $n=8$. So for some reason, 68 is the optimal question for which this particular graph is the answer. I am incredibly dissatisfied with this argument and would love to see some more elegant motivation for the fact that they chose 68 when writing the problem.

I was trying to do an induction on then number of nonzero integers in the blackboard and trying to let some numbers be nonzero; I got that the answer was 46 because I had an error... Since I got to this induction by trying to find an induction on the number of "pairs" and the number of "singles" (which are numbers that have the other number as 0, and you basically weight them. With some very simple weighting you can get a lower bound of (2-sqrt(2))*n, and I'm pretty sure that it isn't hard to get 1/phi. How many points would I get for almost getting the lower bound? It seems like my way is essentially equivalent to Ravi B's..

My guess for the reason why $68$ was picked was that it is $55 + 13 = F_{10} + F_7$. The answer in turn is $42 = 34 + 8 = F_9 + F_6$. I haven't worked on the problem enough to see if this generalizes. EDIT: Although it sounds like the source I read that said the answer was 42 is not correct...

One note on where this problem (may have) come from. In computer science there is a famous problem known as MAXSAT which can be described as follows: You have a list of $n$ variables, each of which can be set to either true or false. You are also given a long list of "OR" clauses, meaning clauses like "$x_5$ is true OR $x_3$ is false OR $x_7$ is true" "$x_1$ is true OR $x_8$ is true" or even "$x_5$ is false". A clause is satisfied if any of the conditions in it hold. So in the above example an assignment where every variable is false would satisfy the first and third clause, but not the second. The goal is to find an assignment of the variables satisfying as many of the clauses as possible. This is known to be a very hard problem, and I believe it is also even very hard to approximate, in the following sense: An efficient algorithm that always satisfies significantly more than $7/8$ of the number of clauses satisfied by the best assignment would lead to a solution of the million dollar $P=NP$ problem. In the problem appearing on the USAMO, erasing the number $i$ corresponds to setting variable $i$ to true, and erasing $-i$ corresponds to setting variable $i$ to false. The pairs $(j, k)$ with $j \neq k$ correspond to clauses of length $2$ (like the second of the three clauses above), and the pairs $(k,k)$ correspond to clauses of length $1$ (e.g. $(-5, -5)$ corresponds to "$x_5$ is false"). The problem asked you to show, in the language of MAXSAT, that if there are no contradictory pairs of clauses of length $1$ (if "$x_i$ is true" and "$x_i$ is false" never both appear at once), you can always satisfy at least a $\phi^{-1}$ fraction of the clauses. In this language I had actually seen this result before, with Ravi B's proof. As to why $68$ was chosen, I think it may have been in part because $68$ is an integer for which the bound $68 \phi^{-1}$ is only a tiny bit more than an integer (so the lower bound of $43$ is in a sense a bit stronger for $68$ than for surrounding integers, as you gain more from rounding up).

The wording of the second sentence was slightly ambiguous. In one interpretation, "at most one" is referring to the entire blackboard, meaning no repeats are allowed for any pair that is a double (repeats of other pairs are allowed), and if a double (k,k) exists then (-k,-k) cannot exist. In the other interpretation, "at most one" is referring to one pair out of the choices {(k,k), (-k,-k)} can be found on the blackboard, meaning that as many copies of (k,k) is allowed as long as (-k,-k) does not exist. I think the two interpretations actually give different answers. I could only get it down to N=46 for the first interpretation, while it's possible to achieve N=43 (rrusczyk's example) with the second interpretation. I was also wondering why they picked the number $68$. Then I looked at my student number. Then I realized, "Aha! They want to see what I come up with for this problem!"

Well, we can do many, many, many reductions on this problem to make it far easier. First, if (k,a) exists, and neither (k,k) or (-k,-k) exists, we can replace it with (k,k) and make sure the max score does not increase. If we keep doing this, we get every number k that appears as either (k,k) or (-k,-k). WLOG let (1,1), (2,2),...,(n,n) appear. Then, we note that if (i,-j) appears, we can replace it with (i,i) and make sure that the max score does not increase. Then, we note that if (-i,-j) does not appear, replace all instances of i with j in all pairs and the max score still does not increase. This leaves us with at least one of (1,1), (2,2),...,(n,n) as well as at least one of (-i,-j) for every distinct i,j between 1 and n, and these types of pairs are the only one possible in our new set. This is where I got stuck, but more because of time than a block in the argument. If possible, anyone care to finish it off? Cheers, Rofler

kevinatcausa wrote: The problem asked you to show, in the language of MAXSAT, that if there are no contradictory pairs of clauses of length $1$ (if "$x_i$ is true" and "$x_i$ is false" never both appear at once), you can always satisfy at least a $\phi^{-1}$ fraction of the clauses. In this language I had actually seen this result before, with Ravi B's proof. Kevin, you are right. After your post, I googled to look for related work in computer science. The specific result you mentioned is due to Lieberherr and Specker (1981). Their original proof was messy, but later someone found the nice probabilistic proof. For example, David Williamson gives the argument in Lecture 3 (Section 1.3) on the following page: http://www.cs.princeton.edu/courses/archive/spr03/cs594/dpw/.

ProtestanT wrote: The wording of the second sentence was slightly ambiguous. In one interpretation, "at most one" is referring to the entire blackboard, meaning no repeats are allowed for any pair that is a double (repeats of other pairs are allowed), and if a double (k,k) exists then (-k,-k) cannot exist. In the other interpretation, "at most one" is referring to one pair out of the choices {(k,k), (-k,-k)} can be found on the blackboard, meaning that as many copies of (k,k) is allowed as long as (-k,-k) does not exist. I think the two interpretations actually give different answers. I could only get it down to N=46 for the first interpretation, while it's possible to achieve N=43 (rrusczyk's example) with the second interpretation. I was also wondering why they picked the number $68$. Then I looked at my student number. Then I realized, "Aha! They want to see what I come up with for this problem!" I interpreted it as only one $(k,k)$ is allowed during USAMO and had a solution that shows that $46$ is the answer for my interpretation I hope the grader will accept the other interpretation and give me the points-.- $\vspace{12pt}$ Here is my solution for my interpretation : only one $(k,k)$ is allowed.

Arr, the forum doesn't take html tags anymore-.-

moplam wrote: ProtestanT wrote: The wording of the second sentence was slightly ambiguous. In one interpretation, "at most one" is referring to the entire blackboard, meaning no repeats are allowed for any pair that is a double (repeats of other pairs are allowed), and if a double (k,k) exists then (-k,-k) cannot exist. In the other interpretation, "at most one" is referring to one pair out of the choices {(k,k), (-k,-k)} can be found on the blackboard, meaning that as many copies of (k,k) is allowed as long as (-k,-k) does not exist. I think the two interpretations actually give different answers. I could only get it down to N=46 for the first interpretation, while it's possible to achieve N=43 (rrusczyk's example) with the second interpretation. I was also wondering why they picked the number $68$. Then I looked at my student number. Then I realized, "Aha! They want to see what I come up with for this problem!" I interpreted it as only one $(k,k)$ is allowed during USAMO and had a solution that shows that $46$ is the answer for my interpretation I hope the grader will accept the other interpretation and give me the points-.- $\vspace{12pt}$ Here is my solution for my interpretation : only one $(k,k)$ is allowed.

Arr, the forum doesn't take html tags anymore-.-

Hamster1800 wrote: moplam wrote: ProtestanT wrote: The wording of the second sentence was slightly ambiguous. In one interpretation, "at most one" is referring to the entire blackboard, meaning no repeats are allowed for any pair that is a double (repeats of other pairs are allowed), and if a double (k,k) exists then (-k,-k) cannot exist. In the other interpretation, "at most one" is referring to one pair out of the choices {(k,k), (-k,-k)} can be found on the blackboard, meaning that as many copies of (k,k) is allowed as long as (-k,-k) does not exist. I think the two interpretations actually give different answers. I could only get it down to N=46 for the first interpretation, while it's possible to achieve N=43 (rrusczyk's example) with the second interpretation. I was also wondering why they picked the number $68$. Then I looked at my student number. Then I realized, "Aha! They want to see what I come up with for this problem!" I interpreted it as only one $(k,k)$ is allowed during USAMO and had a solution that shows that $46$ is the answer for my interpretation I hope the grader will accept the other interpretation and give me the points-.- $\vspace{12pt}$ Here is my solution for my interpretation : only one $(k,k)$ is allowed.

Arr, the forum doesn't take html tags anymore-.-

That is why I restricted the student to only erase $1$ number, so that every number he erased will get him points. Let me clarify: $c$ not yet erased that can be erased is more than $-c$ erased

Does anyone solve this completely in the test?

wuyonglin2004 wrote: Does anyone solve this completely in the test? If they take my interpretation (only one (k,k) is allowed), then yes.... If not =.= The solution I had only took me 20 min to come up with, I kind of knew that something was wrong...

Will there be a Math Jam on this problem?

copeland wrote: The thing I'm still trying to figure out is why they picked 68. As far as I can tell, there are only a finite number of values for which your upper bound and my lower bound agree. Namely, I looked at your upper bound construction of picking $a$ copies of $1$ through $n$, and $1$ copy of the complete graph on $-n$ through $-1$. (I didn't consider the more general case of multiple copies of the complete graph. Perhaps that would have found more values?) By trying all $a$ up to $26$ (and all possible $n$), our bounds only seem to agree on the following values: 1, 3, 5, 6, 9, 10, 14, 18, 20, 25, 33, 39, 49, 60, 68, and 81. If my calculations are right, there can't be any other values that work below 1900 (no matter what the values of $a$ and $n$ are). In particular, the only value larger than 68 that I have found is 81. (For 81, we can choose $a = 5$ and $n = 9$.) For larger values up to 1900, the upper bound and lower bound get quite close to each other, but never agree exactly. Using results about how well the golden ratio can be approximated by rational numbers, it's possible we could even prove that there are no values bigger than 1900 for which our bounds agree, but I don't have the energy to prove that. What other folks said, that $68$ divided by the golden ratio should be a little more than an integer, is on the right track. It seems to be a necessary condition, but not sufficient.

Ravi, That's awesome data. You have several sequences sitting on top of one another in your sequence. I propose splitting a strategy by the (minimum) number of negative integers the strategy (winning or not) chooses. In the accepted notation, the solution has $a=5$, $n=8$, and the total number of pairs we can call \[ N=an+\binom{n}2=68. \] Now there are two winning strategies: taking $k=2$ or $k=3$ negative numbers and the rest positive. Ok, so if you ask the question (I'll explain why in a second): which games, $(a,n)$ have the property that the strategies $k=2$ and $k=3$ give the same value, the games you get are $n-a=3$, so $(1,4)$, $(2,5)$, etc. The sequence you get is: \[ N=3,10,20,33,49,68,90,115\ldots. \] If instead you set the switching point at $k=1$, and $k=2$, you get $n-a=2$, and the sequence \[ 1, 6, 14, 25,39,56,76,99,\ldots. \] In general you get $a+k_{\text{max}}=n$, and the sequences are \[ N=an+\binom n2=n\frac{2(n-k)+(n-1)}2=\frac{n(3n-2k-1)}2 \] Now the next one has your max, $(a,n)=(5,9)$. \[ 6,15,27,42,60,81,105,132,162,\ldots. \] I just noticed this is hard to follow when I put it out of order. These are the lists from $k_{\text{max}}=1$ to $k_{\text{max}}=5$, starting at $n=2$ and putting $\star$ where $n-k<1$: \begin{align*} &\bold{\color{red}3,6,9,18},30,45,63,84,108,135,\ldots\\ &\star, \bold{\color{red}6, 14, 25,39},56,76,99,\ldots\\ &\star,\star,\bold{\color{red}10,20,33,49,68},90,115\ldots\\ &\star,\star,\star,15,27,42,\bold{\color{red}60,81},105,132,162,\ldots\\ &\star,\star,\star,\star,21,35,52,72,95,121,150,182,\ldots. \end{align*} I don't know what's up with 5. I think it's $k=0$, $a=n=2$, which is silly, but not an outlier. It's really weird that none of the later strategies work. That makes me more sad, not less. Back to Rofler's awesome observations, I really want to be able to prove that you can reduce to a local extremum which is a bunch of different complete graphs stacked on the negative side and the appropriately weighted loops on the positive side. Your observation tells us that this really does not want to be true, since stacking in this way can't get a better fraction than whichever one of these things is best. Since this is only an approximation to the golden ratio, we get in serious trouble (like you said) for large n. Worse, though, these two philosophies are at a head. Either you can meander down to some nice global minimum and the result is something quantifiable, or you can't. If you can then we've obviously failed to quantify it and we're broken. My guess is that we need to think more about rational values for $a$ (e.g. larger weights on the complete graph) first. Oh and about having two different values of $k$ which make the same score: this is a min/max, or linear programming trick. If you change $a$ just a tiny bit in one direction, one of the strategies gets better and if you change it in the other direction, the other strategy gets better. So setting them equal gives you ``local extrema.''

Sketch: Let $0<p<1$ vary. Let $x$ be the number of pairs with both entries the same, and $68-x$ otherwise. For every positive integer $k$, we erase $k$ with probability $p$, and $-k$ with probability $1-p$. Some messy casework (including if $p$ is at least $\frac{1}{2}$ or not) and quadratic optimizations using LoE on unerased pairs yield that over all $0 \le x \le 68$, there exists some method of erasure that ensures $\le 25$ pairs with both entries unerased. This gives the bound of at least $68-25=\boxed{43}$ guaranteed points. Equality occurs when all $(i, j)$ with $1 \le i < j \le 8$ appears exactly once, and all $(-i, -i)$ with $1 \le i \le 8$ occurs five times. As this structure is symmetric, we verify this easily by casework on number of distinct negative numbers erased.

The answer is 43. For each pair $k$ and $-k$, it doesn't matter which of $(k,k)$ and $(-k,-k)$ show up, so WLOG pairs of the form $(-k,-k)$ never show up. Now, for each $k\geq 1$, we choose whether to pick out all $k$'s with probability $p$ and all $-k$'s with probability $1-p$ for some $p$. We will show that it is possible to pick $p$ so that the expected score is greater than 42. For the next section, assume $a$ and $b$ are distinct positive integers. Pairs of the form $(a,b)$ have a probability $1-(1-p)^2$ of being counted. Pairs of the form $(a,a)$ have probability $p$ of being counted. Pairs of the form $(a,-b)$ and $(a,-a)$ have probability $1-p(1-p)$ of being counted. Pairs of the form $(-a,-b)$ have probability $1-p^2$ of being counted. Pairs of the form $(-a,-a)$ do not exist. In particular, if we select $$p=\frac{\sqrt{5}-1}{2},$$then all four of these probabilities are at least $\frac{\sqrt{5}-1}{2}$. Thus, we can always get a score of at least $$\lceil 68\cdot \frac{\sqrt{5}-1}{2}\rceil=43.$$ This actually motivates the construction in the following way. in the four cases above, only $(a,a)$ and $(-a,-b)$ achieve the equality case. Thus, the construction should consist of only these two types. We can describe one relatively easily. For all $-8\leq i<j\leq -1$, have the pair $(i,j)$, and have five copies of each of $(1,1)$ through $(8,8)$. We can get at most $$7+6+5\cdot 6=43$$from this, since picking further negative numbers after the first 3 will give us less than if we had picked the positive, hence done.

We claim the answer is $43$. For a construction where $43$ is optimal, include all $(i,j)$ for $-8\le i < j\le -1$ and $5$ copies of $(i,i)$ for each $1\le i\le 8$. We now show $43$ is always attainable. Let $p = \frac{1}{\phi} = \frac{\sqrt5 - 1}{2}$. For each $x > 0$ such that $x$ or $-x$ is written on the board, if $(x,x)$ is written on the board then erase all copies of $x$ with probability $p$ and all copies of $-x$ with probability $1-p$. Otherwise, erase all copies of $x$ with probability $1-p$ and all copies of $1-x$ with probability $p$. It is not hard to verify that any pair on the board will have at least one element erased with probability at least $p$. Hence, the expected number of pairs with at least one element erased is at least $64p > 42$, so by PHP it follows that at least $43$ pairs have at least one number erased in at least one of these configurations.

We are given pairs of integers. Assume that no pairs of the form $(-k, -k)$ fails to appear, else swap $k \mapsto -k$ and $-k \mapsto k$. Now for all $k > 0$ we will now take a biased coin, and assign weights of $p$ and $1-p$, to choose only $k$ or $-k$ respectively, from all pairs they are present in. The key idea in this problem is noting we can use linearity of expectation, to determine the expected number of points from the pairs. Take $m \neq n > 0$. Given $(m, m)$ we expect $p$ points. Given $(m, -m)$ we expect $1$ point. Given $(m , n)$ we expect $1 - (1-p)^2 = 2p - p^2$ points. Note $2p - p^2 = p(2-p) > p$. Given $(m, -n)$ we expect $1 - (1-p) \cdot p =1 - p + p^2$ points. Note that $1 - p + p^2 = (1-p)^2 + p > p$. Given $(-m, -n)$ we expect $1 - p^2$ points. Thus we expect a point form all ordered pairs with probability $\text{min}\{p, 1-p^2\}$. As we wish to maximize this probability, after noting that $p + 1- p^2$ has a fixed sum, it suffices to set them equal to each other. Thus $p^2 + p - 1 = 0 \implies p = \frac{\sqrt{5}-1}{2}$. Now using linearity we note that for any given pair $(m, n)$ the expected points we receive is greater that $p$. Then we expect at least $68p \approx 42 + \epsilon$. It then suffices to find a construction where the maximal number of points achievable is $43$. Note if we wish to have a sharp result we require all pairs to be of the form $(m, m)$ and $-m, -n)$. Consider the pairs: $5$ copies of $(k, k)$ for $k \in (1, 2, 3, 4, 5, 6, 7, 8)$. A pair $(-m, -n)$ for $1 \leq m < n \leq 8$. Then consider choosing $\pm k$ at each step for $k \in (1, 2, 3, 4, 5, 6, 7, 8)$. Clearly for $1$, $2$ it is optimal to choose $(-1$, $-2)$ as they contribute $7$ and $6$ points respectively. For the remainder it is optimal to choose $(+3$, $+4$, $+5$, $+6$, $+7$, $+8)$, as each of these contribute $5$ as opposed to $5$, $4$, $3$, $2$ or $1$ points. Thus we have a final total of $7 + 6 + 5 \cdot 6 = 43$, and we are done.

Knew some elements of the solution from a while ago; I'll attempt to explain motivation here along with the solution, since I already went through the "how would/did I motivate this" question during the solve process given that I knew some solution elements already. I originally thought that this problem was made easier by believing that the answer was basically of the form $cn$, except for $cn+d$, but I suppose it's not hard to get both $n/2$ as a lower bound and $2n/3$ as an upper bound (without constants), indicating the answer might be of the form $cn$. Not to mention that the reasoning I had about $cn$ in the first place is maybe wrong. I also thought problem is possibly made easier by knowing it's global, but then I actually figured out the global part and it felt quite natural too. So maybe the problem isn't hard? lol most likely still wrong The answer is $43$. Let $p=\frac{\sqrt{5}-1}{2}$, so $p^2+p=1$ (obviously in the solve process we only figure this out later). View the problem as choosing some set $S$ (allowed to be infinite, which doesn't change anything) of integers not containing $\{k,-k\}$ for any $k$ that intersects a maximal number of pairs. We first make a localized circular optimization: ignoring the condition, it's better to have a pair $(a,a)$ than a pair $(a,b)$ for $b \neq a$, since if a set intersects $(a,a)$ it must intersect $(a,b)$. Thus for all positive integers $k$, if $(k,k)$ is a written pair, then we can replace any pair containing $k$ with $(k,k)$. Otherwise, we can replace every pair containing $-k$ with $(-k,-k)$; this preserves the condition of $(k,k)$ and $(-k,-k)$ not appearing simultaneously and simplifies the problem somewhat. Do this to every positive $k$ such that either $k$ or $-k$ appears. This lets us place color every integer into one of two colors: Red integers $k$, where every pair containing $k$ is $(k,k)$. Blue integers $k$, where no pair containing $k$ is $(k,k)$. Furthermore, $k$ and $-k$ will always end up being different colors if both can be found in pairs. If not, then we can assign colors (since numbers that aren't in any pair can be colored in either way) such that this still holds. In my opinion, this is all fairly straightforward and nothing new. Now for each pair $(k,-k)$, place the red integer in $S$ with probability $p$ and the blue integer in $S$ with probability $1-p$. Then the probability that a pair $(a,a)$ (so $a$ is red) intersects $S$ is $p$, and the probability that a pair $(a,b)$ with $a \neq b$ (so $a,b$ are blue) is $1-p^2=p$. Hence by expectation we can guarantee at least $\lceil 68p \rceil=43$ integers. Where does this idea come from? Once we get the separation into red and blue integers, there are a few ideas. For instance, if we have some $k$ where there are a lot more or lot less pairs containing $k$ than $-k$ then we can delete everything and do induction, but trying to force this to happen seems messy. So local induction approaches seem hard and we don't want that. Simply picking the number in $\{k,-k\}$ with more pairs also doesn't work either—you can construct a simple counterexample where this is bad. So I guess in some sense we should treat $k$ and $-k$ "equally" all the time: for instance, the possibility that $k$ might have some more pairs doesn't really matter. The most obvious way to "implement" equal treatment is to simply pick $k$ and $-k$ with probability $0.5$ each and use expectation. But if all of our pairs end up on red numbers, this is bad and we only get an average of $n/2$ pairs. So there is still a difference between red and blue numbers, but we also still want this equal treatment of $k$ and $-k$. Why is having all our pairs on red numbers bad? Because red pairs are chosen with probability $0.5$, while blue pairs are actually chosen with probability $1-0.5^2=0.75$; we're actually being biased towards blue pairs, so if every pair is red then our expectation is too low. Hence we should replace the probability of picking red with $p$ instead of $0.5$, and choose $p$ such that these probabilities are equal. Even though "equal treatment" isn't really important at this point, we still have some sort of symmetry between $k$ and $-k$, in the sense that pairs containing $k$ and pairs containing $-k$ are equally likely to be chosen. Now for a construction. This takes a while but isn't very hard if you keep in mind that you sort of want equality at some point with the above probabilistic estimate. Trying to have $k$ and $-k$ contained in the same number of pairs doesn't really work so you sort of go with red integers having $p$ times as many pairs as their blue counterparts and this seems to work asymptotically. If you look too closely at this logic it stops making sense pretty quickly but it's a good enough guiding principle. Take $5$ copies of the pair $(a,a)$ for $1 \leq i \leq 8$ and the one copie of each pair $(-i,-j)$ for $1 \leq i<j \leq 8$, for a total of $40+28=68$ pairs. By symmetry, our score is uniquely determined by the number of red numbers in $[1,8]$ we choose. If we choose $n$ such pairs, we lose $\tfrac{n}{2}$ possible scoring opportunities from blue pairs and $5(8-n)$ possible scoring opportunities from red pairs, so we earn $28-\tfrac{n^2-11n}{2}$ points. Since $n$ is an integer this is maximized at $n=5,6$, in which case we earn $43$ points, establishing the upper bound. $\blacksquare$ If you're just here to read the solution without all this waffling here it is. The answer is $43$. Let $p=\frac{\sqrt{5}-1}{2}$, so $p^2+p=1$. View the problem as choosing some set $S$ (allowed to be infinite, which doesn't change anything) of integers not containing $\{k,-k\}$ for any $k$ that intersects a maximal number of pairs. For all positive integers $k$, if $(k,k)$ is a written pair, then we can replace any pair containing $k$ with $(k,k)$. Otherwise, we can replace every pair containing $-k$ with $(-k,-k)$; this preserves the condition of $(k,k)$ and $(-k,-k)$ not appearing simultaneously and cannot increase the score we obtain with any $S$. Do this to every positive $k$ such that either $k$ or $-k$ appears. This lets us place color every integer into one of two colors: Red integers $k$, where every pair containing $k$ is $(k,k)$. Blue integers $k$, where no pair containing $k$ is $(k,k)$. Furthermore, $k$ and $-k$ will always end up being different colors if both can be found in pairs. If not, then we can assign colors (since numbers that aren't in any pair can be colored in either way) such that this still holds. Now for each pair $(k,-k)$, place the red integer in $S$ with probability $p$ and the blue integer in $S$ with probability $1-p$. Then the probability that a pair $(a,a)$ (so $a$ is red) intersects $S$ is $p$, and the probability that a pair $(a,b)$ with $a \neq b$ (so $a,b$ are blue) is $1-p^2=p$. Hence by expectation we can guarantee at least $\lceil 68p \rceil=43$ integers, establishing the upper bound. For the lower bound, take $5$ copies of the pair $(a,a)$ for $1 \leq i \leq 8$ and the one copie of each pair $(-i,-j)$ for $1 \leq i<j \leq 8$, for a total of $40+28=68$ pairs. By symmetry, our score is uniquely determined by the number of red numbers in $[1,8]$ we choose. If we choose $n$ such pairs, we lose $\tfrac{n}{2}$ possible scoring opportunities from blue pairs and $5(8-n)$ possible scoring opportunities from red pairs, so we earn $28-\tfrac{n^2-11n}{2}$ points. Since $n$ is an integer this is maximized at $n=5,6$, in which case we earn $43$ points, establishing the upper bound. $\blacksquare$

Let the probability that some number $k$ selected be $p$, and the probability that $-k$ is selected be $1 - p$. Clearly only one of $k$ and $-k$ can be selected. Let the total number of points the student has, be $S$. Then the pair $(x, x)$ has a $p$ chance of contributing one point to $S$. $\newline$ $(x, y)$ has a $1 - (1- p)^2 = p(2-p)$ chance of contributing a point to $S$. $\newline$ $(x, -x)$ has a chance of $1$ to contribute a point to $S$. $\newline$ $(x, -y)$ has a chance of $1 - p(1 - p) = p^2 - p + 1$. $\newline$ $(-x, -x)$ has a chance of $1 - p^2$. $\newline$ Then the expected value of the highest number of points we get is $68\min(p, 1 - p^2)$, because we're only allowed to have one of $(k, k)$ and $(-k, -k)$. We set both equal to each other to get $p = 1- p^2$, so $p = \phi$, where $\phi = \frac{\sqrt{5} - 1}{2}$, which is greater than $42$(but less than $43$). This then implies that the maximum possible score the student can guarantee is $43$.

It suffices to find the minimum of the maximum scores over all configurations. Observe that the maximum score in a configuration is greater than or equal to the expected score if implementing a probabilistic method of choosing the integers. Define $k$ to be sigma if $(k,k)$ is a pair or if $(k,k), (-k,-k)$ are not pairs but $k > 0.$ So for every $n \in \mathbb{N}$, either $\pm n$ is sigma. For each $n \in \mathbb{N}$, we can either remove $n$'s or $-n$'s. Optimally, we remove all of a type. With this regard, let $p$ ($0 < p < 1$) be the probability of choosing the sigma variant. We compute the expected number of pairs that score. Let the pair be $(a,b),$ \begin{itemize} \item If $a \ne b$, $a,b$ are sigma, the probability of being scored is $1 - (1-p)^2.$ \item If $a \ne -b$, WLOG $a$ is sigma, $b$ is not sigma, and the probability of being scored is $1 - p(1-p).$ \item If $a \ne b$, $a, b$ are not sigma, the probability of being scored is $1 - p^2.$ \item If $a = -b$, the probability of being scored is $1.$ \item If $a = b$, the probability of being scored is $p$. \end{itemize} To generalize, we seek the minimum values of all these probabilities (keeping in mind this minimum should be maximized to have a strong lower bound for the answer). Observe, \begin{align*} 1 - (1-p)^2 - p &> 1 - (1-p) - p = 0 \\ 1 - p(1-p) - p &> 1 - (1 - p) - p = 0. \end{align*}So the minimum is between $p, 1 -p^2$, maximized at their equality. Solving, we get $p = \frac{1}{2}[-1 + \sqrt{5}].$ So the expected score is, $\ge 68p > 42.$ Hence the guaranteed score is $\ge 43.$ We claim that this is the maximum possible score that he can guarantee. Consider the following construction: Five pairs of $(i, i)$ for $1 \le i \le 8$ and $(-i, -j)$ for $1 \le i < j \le 8.$ There are $40 + 28 = 68$ pairs total. Observe that for $i = 1, 2$ it is optimal to choose $-i$ as it will take $7, 6$ pairs respectively over $5$ from the positive variant. For the rest, it is optimal to choose the positive variant. Hence overall, the maximum score is $5 \cdot 6 + 7 + 6 = 43.$ This proves the lower bound above is maximal. How do I itemize in AoPS?

Oh wait, are we required to provide a construction for this problem? Would I lose points if I didn't?

Yes to both. In any combo problem you must prove your bound, else there is no guarantee your bound is correct.

Let $p = \frac{\sqrt{5}-1}{2}$. For any integer $k>0$ on the board, we erase it with probability $p$ and $1-p$ for negative numbers. Call an ordered pair good if we erased at least one of its integers. Consider each ordered pair (+ denotes a positive integer and $-$ a negative one). WLOG no $(-k,-k)$ pairs show up. If the ordered pair is (+,+) then there is a $\ge p$ chance it is a good pair. If the ordered pair is (+,-) then there is $p^2+(1-p)^2+p(1-p) = 1-p+p^2$ chance this pair is good. If the ordered pair is (-,-) then note it can't be $(-k,-k)$. Thus there is a $1-p^2$ chance it is good. Thus, since $p = \frac{\sqrt{5}-1}{2}$, \[1-p+p^2 > 1-p^2 = p\]Thus, for any ordered pair, there is at least a $p$ chance it is good. Therefore, for any $68$ ordered pairs, we are expected to have $68p > 42$ good ordered pairs. Since this is the expected value when choosing with probability $p$, there must be a way we can choose to guarantee a score of $\boxed{43}$. This is maximal by taking the following 68 pairs: \[(-i,-j) \text{ for $1 \le i < j \le 8$} \text{ and } (i,i) \text{ each repeated $5$ times for $1 \le i \le 8$}\]If we erase $x$ positive numbers, then our score is \[5x + {8 \choose 2}-{x \choose 2}\]which has integer maximum at $43$, which means our inequality is sharp as desired.

Rating (MOHs): 40

Suppose that in all pairs $k, k$ have the property $k>0$, now choose an integer $k>0$ with probability $\frac{\sqrt{5}+1}{2}$ and choose $-k$ with probability $1-\frac{\sqrt{5}+1}{2}$, thus each pair has an expected value of at least $\frac{\sqrt{5}+1}{2}$, thus we get that we can always guarantee a score of $43$ by linearity of expectation. Now for the construction consider having $8$ positive values and each positive pair is of the form $k, k$, now for the negative pairs have $28$ pairs which are all unique.

This is one of the best problems I’ve ever done. We will show that the student can guarantee $43$ score. Suppose that we only have pairs $(k,k)$ with $k>0$. Now we delete all the numbers $k>0$ with probability $p$ and delete all the numbers $-k$ with probability $1-p$. We also choose $p$ such that $p=1-p^2$. We look at the probability that we score for a pair $(a,b)$. Suppose that $a,b>0$ and $a\neq b$. $\bullet$ $(a,a)$ is scored with probability $p$; $\bullet$ $(a,-a)$ is scored with probability $1$; $\bullet$ $(a,b)$ is score with probability $1-(1-p)^2$; $\bullet$ $(a,-b)$ is scored with probability $1-p(1-p)$; $\bullet$ $(-a,-b)$ is scored with probability $1-p^2$. One can easily see that, in any case, the probability that we score a pair is at least $p$ so we get at least $68p>42$ score, which suffices. For the construction, pick $(k,k)$ $5$ times for $1\le k\le 8$ and pick every $(-a,-b)$ with $1\le a,b\le 8$. $\blacksquare$

This problem is beautiful. It's also really hard, even though the solution is short: I'll offer some of my own thoughts on it at the end. The answer is $43$. Construction: Take five copies of the pairs $(1, 1), (2, 2), \dots, (8, 8)$, and one each of $(-a, -b)$ for all $1 \leq a < b \leq 8$. Clearly the first number we erase yields a score of at most $7$, the second number erased yields a score at most $6$, and every successive number yields a score at most $5$. Bound: The proof comes in two parts. Assume without loss of generality that all pairs of the form $(a, a)$ are between two negative numbers. First, we have the following claim: Claim: It suffices to show the bound for the case where there are no pairs $(a, b)$ for $b < 0 < a$ or vice versa. Proof: Replace the pair $(a, b)$ with the pair $(b, b)$. Then, any selection $S$ of erased numbers for which $(b, b)$ scores $(a, b)$ also scores, therefore the same selection $S'$ with the pair $(a, b)$ yields at least the same score. $\blacksquare$ Now let $p = \frac{\sqrt 5 - 1}2$. For each positive integer $a$, we erase $a$ with probability $1-p$ and $b$ with probability $p$. Then every pair of the form $(b, b)$ is scored with probability $p$, while every pair of the form $(a, a')$ is scored with probability $1-p^2 = p$. Hence the expected score is at least $68p>42$ and thus at least $43$. Remark: One of the hardest parts of the problem is figuring out the answer: off the bat, based on the construction, there's no reason why $43$ should be optimal. The most natural way to see the solution, in my opinion, is to see the claim first, which reduces the problem to some multigraph on the positive vertices and self-loops on the negative vertices—from here, the construction for $43$ is clearly the most ``balanced". The reduction (and fairly arbitrary value of $43$) suggests that the solution should follow some local path of smoothing to that equality case—say, by contracting vertices, replacing edges, expanding vertices, etc. Unfortunately, this doesn't work, although it seems very promising. Once we get past the hurdle of realizing that the problem is purely global, the value of $p$ derives itself: we want some kind of probability space that treats self-loops and edges equally because they contribute equally to score.

The answer is $43$ In the construction, pick $(k,k)$ $5$ times for $1\le k\le 8$ and pick every $(-a,-b)$ with $1\le a,b\le 8$ For the bound, choose $k$ with probability $\frac{\sqrt{5}+1}{2}$ and $1-\frac{\sqrt{5}+1}{2}$, it’s easy to see this always gives our answer by LoE