Colouring of $mathbbN$ that avoids all non-constant infinite arithmetic progressions?

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?

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 Answers
6

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:

For every arithmetic sequence:

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.

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.

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

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.

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.

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.