Can you color every positive integer either black or white such that there are no entirely white or entirely black non-constant infinite arithmetic progressions?

This is not necessarily the coloring (if such a coloring is possible).

How about switching color every power of 2?

1,4,5,6,7,16,...,31,64,...

2,3,8,9,10,11,12,13,14,15,32,...

Any attempt at an AP would eventually get cut off.

  • 6
    All you need to do is to make increasingly large blocks of each color. – lulu Aug 19 at 20:02
  • 8
    It seems like you answer your own question – Clayton Aug 19 at 20:03
up vote 10 down vote accepted

Color the first integer white, the next two integers black, the next three integers white, etc. We will call these sections of successive integers with the same colors, "blocks". Thus we have successively blocks of length 1, 2, 3, 4, etc.

Now consider an arithmetic progression $a_n = a_0 + nd$ for some positive integers $a_0, d$ ($n = 0, 1, 2, \dots$). Let $k$ be a positive integer such that the block of length $kd$ comes after $a_0$. There is at least one element from the progression that lies in this block. Suppose that $a_n$ is the last element from the progression that lies in this block; then $a_{n+1}$ lies in the next block, of length $kd+1$, and therefore has the opposite color. Thus any arithmetic progression contains successive elements $a_n, a_{n+1}$ of opposite color, as we needed to prove.

First, observe that we can enumerate all possible infinite, nonconstant arithmetic sequences. Each one can be described by specifying a pair of positive integers: the first number and the difference between successive terms. (conversely, every pair of positive integers specifies such a sequence)

So you can color the positive integers by the following method:

  • Start by not assigning any colors.
  • For every arithmetic sequence:

    • Pick the two smallest uncolored integers in the sequence
    • Color one black and the other white
  • Pick any color you want for the remaining positive numbers.

With the specific coloring scheme of step 2, step 3 doesn't actually need to do anything and can be omitted. I include it because the argument clearly generalizes to other schemes for deciding which integers to color in step 2 than "color the two smallest uncolored integers", and some schemes will leave some positive integers uncolored.

  • 3
    "with care, you can even identify which numbers will never be colored in the second step" - specifically, every positive integer will be colored by some iteration of step 2, and step 3 doesn't actually do anything. – user2357112 Aug 20 at 6:34
  • 3
    @user2357112: Ah, you're right! I had originally conceived the argument with a less rigid coloring scheme and needed that to fill in any gaps that one happened to leave. – Hurkyl Aug 20 at 6:53

A really easy construction: Colour all the numbers with an odd number of digits white, and colour all the numbers with an even number of digits black. Since the blocks of white and black numbers increase geometrically, whereas an arithmetic progression is increasing arithmetically, there doesn't exist a monochrome arithmetic progression.

  • 2
    What makes an arithmetic progression non constant? – user585308 Aug 19 at 20:45
  • 3
    Common difference is not zero – X X Aug 19 at 20:47

Color naturals randomly (independently for every natural with probability 1/2 of being black). The probability that a given infinite arithmetic progression is entirely black or white is $0$. It remains to note that there are only countably many infinite arithmetic progressions

  • 7
    Probability zero doesn't mean it can't happen. – Hurkyl Aug 19 at 20:02
  • 5
    @Hurkyl It's just a probabilistic argument. This means that with probability 1 all infinite arithmetic progressions involve two different colors. Hence there extsts such coloring. – Sasha Kozachinskiy Aug 19 at 20:04
  • 4
    You need to specify a probabilty measure on the natural numbers for the first part of your construction to make sense. What measure are you proposing? – Rob Arthan Aug 19 at 21:05
  • 4
    @RobArthan I just mean that I toss a symmetric coin for every natural, independently. Formally, possible outcomes are results of tosses. These results can be encoded by infininite binary sequences. To be absolutely formal, you need a probability measure on such sequences with the property that a set of sequences starting with a fixed word $w$ of length $k$ have probability $2^{-k}$. There are several ways to do it, for example by borrowing Lebesgue measure from [0,1] – Sasha Kozachinskiy Aug 19 at 21:31
  • 4
    Sure you can construct a sensible probability measure space for the set of all sequences colouring each natural number black or white. But that isn't what you wrote in your answer and doesn't seem to me to have any bearing on the original question: as Hurkyl says, probability $0$ does not mean impossible in an infinite probability measure space. – Rob Arthan Aug 19 at 21:49

There is a nice constant, called "Thue Morse constant". The idea behind it seems appropriate for your problem. color the first number white, the next number black. So you have -written in symbols- the string "wb".

Now append the inversion of the string to itself, getting "wbbw". Repeat ad infinitum to get "wbbw bwwb bwwb wbbw ... "

There should be no infinite arithmetic progression of one of the simple symbols.

If I Consider the irrational number $z=\sum_{i=1}^{\infty} 10^{-i!}=0,110001000...$ as a representation of natural numbers, where 1 means white and 0 means black. Let $\{a_n\}$ be an arithmetic progression, where $a_{n+1}-a_n=k$: if a similar series existed, it would mean that, in the decimal represntation of z there is the same digit repeating each k digits, but this is impossible because z is irrational. Therefore, this progression doesn't exist.

  • 3
    Repeating digit doesn't mean rational. – Serge Seredenko Aug 19 at 21:25
  • 3
    Yeah, this answer is quite wrong. You're asserting that since $z$ is irrational, its digits after the decimal point have no arithmetic progressions which are all $0$ or all $1$. As a matter of fact, the 3rd, 5th, 7th, 9th, 11th, … digits are all $0$, because there are no factorials which are odd, except for $0! = 1! = 1$. – Tanner Swett Aug 20 at 0:22

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.