There are 68 ordered pairs (not necessarily distinct) of nonzero integers on a blackboard. It's known that for no integer $k$ does both $(k, k)$ and $(-k,-k)$ appear. A student erases some of the 136 integers such that no two erased integers have sum zero, and scores one point for each ordered pair with at least one erased integer. What is the maximum possible score the student can guarantee?
The answer is 43 .
The structure of this problem is better understood as follows: we construct a multigraph whose vertices are the entries, and the edges are the 68 ordered pairs on the blackboard. To be precise, construct a multigraph $G$ with vertices $a_{1}, b_{1}, \ldots, a_{n}, b_{n}$, with $a_{i}=-b_{i}$ for each $i$. The ordered pairs then correspond to 68 edges in $G$, with self-loops allowed (WLOG) only for vertices $a_{i}$. The student may then choose one of $\left\{a_{i}, b_{i}\right\}$ for each $i$ and wishes to maximize the number of edges adjacent to the set of chosen vertices.

First we use the probabilistic method to show $N \geq 43$. We select the real number $p=\frac{\sqrt{5}-1}{2} \approx 0.618$ satisfying $p=1-p^{2}$. For each $i$ we then select $a_{i}$ with probability $p$ and $b_{i}$ with probability $1-p$. Then
- Every self-loop $\left(a_{i}, a_{i}\right)$ is chosen with probability $p$.
- Any edge $\left(b_{i}, b_{j}\right)$ is chosen with probability $1-p^{2}$.

All other edges are selected with probability at least $p$, so in expectation we have $68 p \approx 42.024$ edges scored. Hence $N \geq 43$.

For a construction showing 43 is optimal, we let $n=8$, and put five self-loops on each $a_{i}$, while taking a single $K_{8}$ on the $b_{i}$ 's. The score achieved for selecting $m$ of the $a_{i}$ 's and $8-m$ of the $b_{i}$ 's is
$$
5 m+\left(\binom{8}{2}-\binom{m}{2}\right) \leq 43
$$
with equality when either $m=5$ and $m=6$.
Remark (Colin Tang). Here is one possible motivation for finding the construction. In equality case we probably want all the edges to either be $a_{i}$ loops or $b_{i} b_{j}$ edges. Now if $b_{i}$ and $b_{j}$ are not joined by an edge, one can "merge them together", also combining the corresponding $a_{i}$ 's, to get another multigraph with 68 edges whose optimal score is at most the original ones. So by using this smoothing algorithm, we can reduce to a situation where the $b_{i}$ and $b_{j}$ are all connected to each other.

It's not unnatural to assume it's a clique then, at which point fiddling with parameters gives the construction. Also, there is a construction for $\lceil 2 / 3 n\rceil$ which is not too difficult to find, and applying this smoothing operation to this construction could suggest a clique of at least 8 vertices too.

Remark (David Lee). One could consider changing the probability $p(n)$ to be a function of the number $n$ of non-loops (hence there are $68-n$ loops); we would then have
$$
\mathbb{E}[\text { points }] \geq(68-n) p(n)+n\left(1-p(n)^{2}\right) .
$$

The optimal value of $p(n)$ is then
$$
p(n)=\left\{\begin{array}{ll}
\frac{68-n}{2 n}=\frac{34}{n}-\frac{1}{2} & n \geq 23 \\
1 & n23$ we then have
$$
\begin{aligned}
E(n)= & (68-n)\left(\frac{34}{n}-\frac{1}{2}\right)+n\left(1-\left(\frac{34}{n}-\frac{1}{2}\right)^{2}\right) \\
& =\frac{5 n}{4}+\frac{34^{2}}{n}-34
\end{aligned}
$$
which has its worst case at around $5 n^{2}=68^{2}$, so at $n=30$ and $n=31$. Indeed, one can find
$$
\begin{array}{l}
E(30)=42.033 \\
E(31)=42.040 .
\end{array}
$$

This gives another way to get the lower bound 43 , and gives a hint about approximately how many non-loops one would want in order to achieve such a bound.