What's the size of the biggest set of numbers from 1 to 100 so that no number is the average of any other two?

Question

John wants to build a set of numbers, from the range of 1 to 100. The only rule is that in that set no number can be the average of any other two. For example, if the set contains the numbers 1 and 3, then 2 cannot be present. What’s the size of the biggest set that John can build?

More precisely, if L is "John's set", then $$ \forall x,y,z \in L : z \ne \frac{x+y}{2} $$ and $$ \forall x \in L : 1 \leq x \leq 100$$

We want to find the cardinality of L.

---

PS: This problem appeared on a Sunday newspaper many years ago. On the following week they published a solution that was wrong. I was able to solve it computationally but never mathematically.

Answer 1

You can solve the problem via integer linear programming as follows. Let $n=100$. For $i\in\{1,\dots,n\}$, let binary decision variable $x_i$ indicate whether $i\in L$. The problem is to maximize $\sum_{i=1}^n x_i$ subject to $$x_i + x_{i+d} + x_{i+2d} \le 2 \quad \text{for $i\in\{1,\dots,n-2\}$ and $d\in\{1,\dots,\lfloor(n-i)/2\rfloor\}$}.$$ The optimal objective value turns out to be $27$, attained by $$L=\{1,5,7,10,11,14,16,24,26,29,30,33,35,39,66,70,72,75,76,79,81,89,91,94,95,98,100\}.$$

See https://oeis.org/A003002 for more terms. Such a set is called a Salem-Spencer set, and asymptotic bounds are known for the largest cardinality.

Answer 2

A greedy algorithm would hive an answer of $24$, as given by the "Erdos-Szekeres" sequence here: http://oeis.org/A003278 .

But, as demonstrated by RobPratt, and as often happens in analysis, the greedy algorithm is ultimately not the optimal one. It's as if you overuse an initially fertile soil, exhaust its nutrients and then you find you can't grow crops until you give time for rains to fall and the soil to replenish itself. Let's explore why greed turned out not good in this case.

Welcome to the desert

Suppose you have a list of whole numbers, with a minimum of $1$ and a maximum of $n$, such that there is not a group of three in arithmetic sequence. Then the arithmetic third of any pair of numbers from this list cannot be larger than $2n-1$, and so you can always insert the number $2n$ and be sure there is still no three-term arithmetic sequence.

If, in fact, you do need to resort to $2n$ to continue your list -- that is, no smaller number will do -- then you have in effect created a "desert". The presence of such deserts can make you fall behind a more carefully tended, more optimal sequence. And that is what happened here.

Upon further review, the Erdos-Szekeres sequence, constructed to take as small a number as possible at any step, is equally optimal at producing deserts. A number $k$ enters this sequence iff the ternary representation of $k-1$ has no elements of $2$, for instance eleven minus one is ten, which is $101$ in base $3$, so ten is in the sequence. But once we get to fourteen in this case, where one less is $111$ base $3$, we are forced to accept a $2$ somewhere in the ternary representation until we have passed the next power of $3$, in this case at $28$, where we can introduce a new ternary "digit". We build in a desert from $n=(3^m+1)/2$ all the way up to $2n=3^m+1$ for every whole number $m$. In this problem the desert from $41$ to $82$ ($m=4$) renders the greedy algorithm inferior.

Finding an oasis

Of course, we can change the rules of our game to make the greedy algorithm look good. If, instead of an upper bound of $100$, we were to choose an upper bound of $(3^m+1)/2$ for some whole number $m$ -- stopping just at the threshold of the desert -- then the Erdos-Szekeres method really does work. For instance, with a maximum of $(3^5+1)/2=122$ the Erdos-Szekeres method gives $32$ terms and that is indeed the optimum for a max element of $122$. See https://oeis.org/A065825.