8
$\begingroup$

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.

$\endgroup$
0

2 Answers 2

8
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ Very nice. Just out of curiosity, did you just write the program on the fly? When I look at the constraint, my first thought is that $2^{(100)} \approx 10^{(30)}$ is too many cases. My pc balks at more than $(10)^8$ cases. Did you find a way to streamline the code? For example, did you experiment with $V = $ value and increment $V$ by $(+1)$, checking each value, and discovering that $V = 27$ is attainable and $V = 28$ is not? $\endgroup$ May 25 at 23:26
  • 1
    $\begingroup$ @asinomás can you undelete your answer? I think including it makes for an interesting comparison getween the greedy and optimal algorithms. $\endgroup$ May 25 at 23:30
  • 2
    $\begingroup$ @user2661923 I used a generic ILP solver that uses the branch-and-cut algorithm, not brute force. $\endgroup$
    – RobPratt
    May 25 at 23:53
  • $\begingroup$ @OscarLanzi I agree with you and just voted to undelete the answer. asinomas was not flagged by your comment because he has not been registered for RobPratt's answer. One alternative is for you to track down any posting/answer that asinomas is registered for, and leave your comment request, addressed to him, there. Naturally, you will need to include a link back to this posting. $\endgroup$ May 25 at 23:57
  • $\begingroup$ Very nice. The answer is indeed 27 (for N=100). In my case, I had used dynamic programming to find the sets. The reason I keep looking at this problem after all these years is that although I was able to prove a few properties/theorems about the cardinality of L, I was never able to solve it in a more "mathematical" way. I.e., for a certain size of N, is there an expression for #L? $\endgroup$
    – Paulo
    May 26 at 9:26
2
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ The description of the sequence seems to say that this is the result of the greedy approach (build a sequence from $1, 2, \ldots$ by choosing the next smallest valid number), which might not be optimal as RobPratt's answer suggests. $\endgroup$
    – angryavian
    May 25 at 23:15
  • $\begingroup$ @angryavian Nice catch, I missed that. I deleted my comment. $\endgroup$ May 25 at 23:15
  • $\begingroup$ I was k-c-u-f-ed (read it backwards) by Autocorrect. Forced to rephrase that passage. Please try again. $\endgroup$ May 26 at 0:59
  • $\begingroup$ @OscarLanzi This time, when you reply, please include the AT:user2661923, so that I will be flagged. Perhaps I am being dense here. I don't understand this sentence: "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." In this sentence, what is $n$, and what pair of numbers are you referring to? Are you, for example saying that if you take an optimal list, and append the number $(200)$ to it, that no constraint has been violated? $\endgroup$ May 26 at 1:08
  • 1
    $\begingroup$ @OscarLanzi Okay. I skimmed your analysis. I am going t have to study it further, which will take at least a few days. I have bookmarked this posting, for reference. For what it's worth, I was also intrigued by Rob Pratt's reference to a branch and cut algorithm, re integer linear programming. $\endgroup$ May 26 at 1:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.