, 2010

(By Zuming Feng and Paul Zeitz). The answer is 43.

We first show that we can always get 43 points. Without loss of generality, we assume that the value of $x$ is positive for every pair of the form $(x, x)$ (otherwise, replace every occurrence of $x$ on the blackboard by $-x$, and every occurrence of $-x$ by $x$). Consider the ordered $n$-tuple $(a_1, a_2, \dots, a_n)$ where $a_1, a_2, \dots, a_n$ denote all the distinct absolute values of the integers written on the board.

Let $\phi = \frac{\sqrt{5}-1}{2}$, which is the positive root of $\phi^2 + \phi = 1$. We consider $2^n$ possible erasing strategies. Every strategy corresponds to an ordered $n$-tuple $s = (s_1, \dots, s_n)$ with $s_i = \phi$ or $s_i = 1-\phi$ ($1 \le i \le n$). If $s_i = \phi$, then we erase all occurrences of $a_i$ on the blackboard. If $s_i = 1-\phi$, then we erase all occurrences of $-a_i$ on the blackboard. The weight $w(s)$ of strategy $s$ equals the product $\prod_{i=1}^n s_i$. It is easy to see that the sum of weights of all $2^n$ strategies is equal to $\sum_s w(s) = \prod_{i=1}^n [\phi + (1-\phi)] = 1$.

For every pair $p$ on the blackboard and every strategy $s$, we define a corresponding cost coefficient $c(p, s)$: If $s$ scores a point on $p$, then $c(p, s)$ equals the weight $w(s)$. If $s$ does not score on $p$, then $c(p, s)$ equals 0. Let $c(p)$ denote the sum of coefficients $c(p, s)$ taken over all $s$. Now consider a fixed pair $p = (x, y)$. We claim that $c(p) \ge \phi$, for which we consider two cases.

(a) First, suppose that $x = y = a_j$. Then, every strategy that erases $a_j$ scores a point on this pair. Therefore, we have $c(p) = \phi \prod_{i \neq j} [\phi + (1-\phi)] = \phi$.

(b) Now, suppose that $x \neq y$. We have
$$c(p) = \begin{cases} \phi^2 + \phi(1-\phi) + (1-\phi)\phi = 3\phi - 1, & (x, y) = (a_k, a_\ell); \\ \phi(1-\phi) + (1-\phi)\phi + (1-\phi)^2 = \phi, & (x, y) = (-a_k, -a_\ell); \\ \phi^2 + \phi(1-\phi) + (1-\phi)^2 = 2 - 2\phi, & (x, y) = (\pm a_k, \mp a_\ell). \end{cases}$$
The bound $c(p) \ge \phi$ follows in each case by noting that $\phi \approx 0.618$ satisfies $\frac{1}{2} < \phi < \frac{2}{3}$.

Let $C$ denote the sum of the coefficients $c(p, s)$ taken over all $p$ and $s$. Our bound then yields that
$$C = \sum_{p,s} c(p,s) = \sum_{p} c(p) \ge \sum_{p} \phi = 68 \phi > 42.$$
Suppose for the sake of contradiction that every strategy $s$ scores at most 42 points. Then every $s$ contributes at most $42w(s)$ to $C$, and we get $C \le 42 \sum_s w(s) = 42$, which contradicts $C > 42$. Therefore, there is always some strategy which will score at least 43 points.

To complete our proof, we now show that we cannot always get 44 points. Consider the blackboard containing the following 68 pairs: for each of $m = 1, \dots, 8$, five copies of $(m, m)$ (for a total of 40 pairs of type (a)); for every $1 \le m < n \le 8$, one copy of $(-m, -n)$ (for a total of $\binom{8}{2} = 28$ pairs of type (b)). We claim that we cannot get 44 points from this initial stage. Indeed, assume that exactly $k$ of the integers $1, 2, \dots, 8$ are underlined. Then we get at most $5k$ points from the pairs of type (a) and at most $28 - \binom{k}{2}$ points from the pairs of type (b), for a total of at most $5k + 28 - \binom{k}{2}$ points. The quadratic function $5k + 28 - \binom{k}{2} = -\frac{k^2}{2} + \frac{11k}{2} + 28$ is maximized for integer $k$ at $k = 5$ or $k = 6$ and has a maximum value of 43. Thus, we can get at most 43 points with this initial blackboard, completing the solution.