Avoiding Arithmetic Sequences

I was looking through some open problems in arithmetic combinatorics earlier this week and thought some of the problems that revolve around avoiding arithmetic sequences might make nice puzzles. We'll look at a few variants.

Setup

For this activity, you'll want a grid strip and counters. If you print this document, you can cut out and tape some strips from the first page together to a long grid strip. I'd imagine \(30\) squares is more than enough for most explorations. The squares are a little over \(1" \times 1"\), so should accommodate most counters you'd want to use. Having counters of several colors or types can be useful, but not necessary. For some extensions, you'll also want a gridded board, as in the second page of the linked grid strip document or a checkerboard.

The sorts of problems we'll be tackling will be related to the one below:

Example

You have a strip of length \(10\). How many counters can you place (at most one per square) so that no counter is exactly halfway between two others?

There are many ways to do it, but it turns out that \(5\) counters is the best we can do. Here is one solution:

Challenges

As before, for each of the following puzzles, a solution will involve placing counters on a strip so that no counter lies exactly halfway between any two others.

1. Can you find a solution for \(4\) counters on a strip of length \(8\)?

2. Could you have solved it on a strip of length \(7\)? \(6\)? Shorter?

3. We've seen a solution for \(5\) counters on a strip of length \(10\). Can you find a solution on a strip of length \(9\)? Shorter?

4. Find a solution for \(6\) counters on a strip as long as you like. How long was your strip?

5. What's the shortest strip that can fit a solution with \(6\) counters?

6. What's the shortest strip that can fit a solution with \(7\) counters?

7. What's the shortest strip that can fit a solution with \(9\) counters?

8. What's the shortest strip that can fit a solution with \(12\) counters?

9. Can you find a method for always producing a solution for \(m\) counters on a strip? (The strip can be as long as you need it to be.)

10. Can you find a method for always producing a solution for \(m\) counters that uses a relatively short strip? (You can decide what it means for a strip to be relatively short.)

Notes

• If we number the counters by their positions, as we have above, then we can conveniently think about the position exactly halfway between two counters as being their average.

• A more general framework is to think in terms of arithmetic sequences. More specifically, we are trying to choose \(n\) numbers from \(\{1,2,3,...,m\}\) so that no three of them are consecutive terms in an arithmetic progression.

• For each \(n\), there is a shortest strip that can support a solution for \(n\) counters. Typically there will be more than one solution, but here are shortest solutions for \(4 \leq n \leq 12\) counters, written as subsets of the positions on the strip:

  • \(n = 4:\quad\) \(\{1, 2, 4, 5\}\)
  • \(n = 5:\quad\) \(\{1, 2, 4, 8, 9\}\)
  • \(n = 6:\quad\) \(\{1, 2, 4, 5, 10, 11\}\)
  • \(n = 7:\quad\) \(\{1, 2, 4, 5, 10, 11, 13\}\)
  • \(n = 8:\quad\) \(\{1, 2, 4, 5, 10, 11, 13, 14\}\)
  • \(n = 9:\quad\) \(\{1, 2, 6, 7, 9, 14, 15, 18, 20\}\)
  • \(n = 10:\quad\) \(\{1, 2, 5, 7, 11, 16, 18, 19, 23, 24\}\)
  • \(n = 11:\quad\) \(\{1, 2, 5, 7, 11, 16, 18, 19, 23, 24, 26\}\)
  • \(n = 12:\quad\) \(\{1, 3, 4, 8, 9, 11, 20, 22, 23, 27, 28, 30\}\)

  We can see a sequence \(\{a_n\}\) emerging, where \(a_n = m\) if \(m\) is the least value such that \(n\) terms can be chosen from \(\{1,2,3,...,m\}\) so they do not contain a \(3\)-term arithmetic sequence. The first thirty terms of this sequence are

  \[ 1, 2, 4, 5, 9, 11, 13, 14, 20, 24, 26, 30, 32, 36, 40, 41, 51, 54, 58, 63, 71, 74, 82, 84, 92, 95, 100, 104, 111, 114, ... \]

• One way to produce an arbitrarily long sequence free of \(3\)-term arithmetic sequences goes as follows: Start with a set that has no such sequences. (Any of the above examples will work.) Choose the next number to be bigger than all of the previous values so that it does not form a three-term arithmetic sequence with any two terms before it.

  If our numbers are all positive, we can choose the next number to be twice the last one, for example. The powers of \(2\) are such a sequence that is free of \(3\)-term arithmetic sequences:

  \[ \{1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, ...\} \]

  The sequence above grows pretty quickly. We've seen that if we want a subset of \(\{1,2,3,...,m\}\) with \(8\) terms that are free of \(3\)-term arithmetic sequences, we can do it with \(m = 14\) (e.g., \(\{1, 2, 4, 5, 10, 11, 13, 14\}\)), whereas the powers of \(2\) lead us to a solution for \(m = 128\) (i.e., \(\{1, 2, 4, 8, 16, 32, 64, 128\}\)).

  We can do better if we choose greedily. Instead of choosing a next number that works at each stage, we'll choose the next smallest number that works. If we do this starting with \(\{1\}\), the sequence we end up generating is

  \[ \{1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 32, 37, 38, 40, 41, 82, 83, 85, 86, 91, 92, 94, 95, 109, ...\} \]

  While taking the first \(n\) numbers from this sequence doesn't always generate the optimal solution, it does much better than powers of \(2\). For \(n=8\), we get an optimal arrangement \(\{1, 2, 4, 5, 10, 11, 13, 14\}\). For \(n=11\), the sequence suggests the solution \(\{1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31\}\), which is worse than the optimal \(\{1, 2, 5, 7, 11, 16, 18, 19, 23, 24, 26\}\). Sequences generated greedily to avoid arithmetic progressions in this way are called Stanley sequences.

  If we subtract \(1\) from every element in the sequence above, we get the binary-ternary sequence

  \[ \{0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40, 81, 82, 84, 85, 90, 91, 93, 94, 108, ...\} \]

  of numbers whose representations base-\(3\) contain no \(2\)'s -- i.e., numbers expressible as sums of distinct powers of \(3\).

• It is an open problem how large \(m\) must be so that \(\{1,2,3,...,m\}\) contains an \(n\)-element subset free of \(3\)-term arithmetic sequences. (Such subsets are called Salem-Spencer sets.) It is known that as \(n\) increases, \(m\) increases at a rate that is greater-than-linear. More details can be found here. (The current known bounds were improved in February of this year!)

Extra Challenges

• If you want to present it more like the initial example, one way to go about it is the place two counters on the strip and see how much of the strip between them you can fill without introducing a \(3\)-term arithmetic sequence. This is a subtly different problem than the one initially stated, although you might not notice until you have a strip of length \(33\) or longer! The difference is that given a strip of length \(n\), it's always advantageous to put a counter in position \(1\) or \(n\), but not necessarily in both, as this setup requires. However, this does give a nice way to put bounds on some segment of a large strip without having to fold or cover it.

• A natural extension is to graduate from avoiding \(3\)-term arithmetic sequences to instead avoiding \(k\)-term arithmetic sequences. This allows for the subsets to be more dense, since in avoiding \(3\)-term arithmetic sequences, you avoid arithmetic sequences of length \(k\) for all \(k \geq 3\). If we look to avoid \(k\)-term arithmetic sequences in \(\{1,2,3,...,20\}\), here are some optimal subsets for different values of \(k\):

  • \(k = 3:\quad\) \(\{1, 2, 6, 7, 9, 14, 15, 18, 20\}\)
  • \(k = 4:\quad\) \(\{1, 2, 3, 5, 6, 8, 9, 10, 15, 16, 17, 19\}\)
  • \(k = 5:\quad\) \(\{1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19\}\)
  • \(k = 6:\quad\) \(\{1, 2, 3, 4, 5, 7, 8, 9, 10, 12, 13, 14, 15, 17, 18, 19, 20\}\)

• For a colorful extension based on van der Waerden's theorem, take the numbers \(\{1,2,3,...,n\}\) and try to color them so that no subset that shares a color contains a \(3\)-term arithmetic sequence. How many colors do you need for a given \(n\) and what does the coloring look like? Below is a nice \(2\)-coloring of \(\{1,2,3,4,5,6,7,8\}\)

  

  To color \(\{1,2,3,4,5,6,7,8,9\}\), we would need \(3\) colors, however.

• A classic puzzle due to Dudeney asks for the maximum number of points one can place on an \(n \times n\) grid without any three being collinear. (Here we mean lines of any slope, not just the horizontal, vertical, and diagonals.) This problem has a rich history, but I'm not sure if any work has been done on the following variation:

  How many points can be placed on an \(m \times n\) grid so that none is the midpoint of any other two?

  More broadly, if the above question is a 2D analogue of avoiding \(3\)-term arithmetic sequences, we could ask how many points can be placed so that no line contains \(k\) equally-spaced points for different values of \(k\).

This post was sponsored by the Julia Robinson Mathematics Festival