Split the Arithmetic Progressions

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.

Found it! I thought I might've posted this one a few years ago. Anyone who wants a free problem, click here .

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.

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.

Consider the irrational number $z=\sum_{i=1}^{\infty} 10^{-i!}=0,1100010000...$ 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.

Can we get this result if we color prime numbers?

Code all the AP's by the pair (a 0, d) and then list these by increasing value of m = a 0 + d (there are only finitely many AP's for each m so this defines a list containing them all). Start from the beginning of the list and colour one entry from the AP under consideration white and another black, and work through the list this way, only writing down numbers bigger than any you have previously written (which avoids multiple assignment of colours to one integer). Colour any smaller number not assigned a colour any way you like. That should do it.

B W BB WW BBB WWW BBBB WWWW...

Colour every power of 2, 3 and 5 black, and all others white. At no point can you get a arithmetic progression. Or, switch colours every power of 2 and 3. At no point can you get an AP.

Each infinite arithmetic progression of positive integers is determined by its first term $a$ and its common difference $d$ , where $a.d \in \mathbb{N}$ . Thus the number of infinite arithmetic sequences of positive integers is countable. Let the collection of arithmetic progressions be $\{\mathcal{S}_n \,:\, n \in \mathbb{N}\}$ . Note that each set $\mathcal{S}_n$ is infinite.

Find distinct elements $x_1,y_1 \in \mathcal{S}_1$ . Now choose distinct elements $x_2,y_2 \in \mathcal{S}_2 \backslash \{x_1,y_1\}$ .

Suppose that, for $m \in \mathbb{N}$ , we have distinct elements $x_1,x_2,...,x_m,y_1,y_2,...,y_m \in \mathbb{N}$ such that $x_j,y_j \in \mathcal{S}_j$ for $1 \le j \le m$ . Since $S_{m+1}$ is infinite, we can find two distinct elements $x_{m+1},y_{m+1} \in \mathcal{S}_{m+1} \backslash \{x_1,...,x_m,y_1,...,y_m\}$ .

By induction, we can find sequences $(x_n)_n$ and $(y_n)_n$ such that:

• $x_m \neq y_n\,,\, x_m \neq x_n\,,\,y_m \neq y_n$ for all $m,n \ge 1$ ,

• $x_n,y_n \in \mathcal{S}_n$ for all $n \ge 1$ ,

If we define $A = \{x_n \,:\, n \in \mathbb{N}\}$ and $B = \mathbb{N} \backslash A$ , then $x_n \in A$ , so that $x_n \not\in B$ , so that $\mathcal{S}_n \not\subseteq B$ . Also $y_n \in B$ , so that $y_n \not\in A$ , so that $\mathcal{S}_n \not\subseteq A$ . This is true for any $n \in \mathbb{N}$ , and hence neither $A$ nor $B$ contain any infinite arithmetic progression.

Take the first block of n numbers and use both colors. For the next block of n numbers, reverse the color scheme of the first block (e.g.if the i th number in the first block of n numbers is white then make the i th element of the second block of n numbers black). Now there are 2n numbers that are colored. Again, color the next block of 2n numbers with the opposite color sequence of the first 2n numbers. Now you have a block of 4n colored numbers and you can repeat the process on the next block of 4n numbers. Any arithmetic sequence with the same color will be reversed in the next block so that the expanded sequence is colored with more than one color.

Just colour the primes black

My solution is to split the number line into sets of n consecutive numbers (n>=2) where (e.g., for n=2, 1-2 3-4 4-6...). for each set r, you take the product of it's elements and multiply it by r! (or some other f(r) that increases at a ridiculous rate), let it be i(r), and colour that in any colour, you should than multiply this product by some integer over 1 but under n, let it be j(r), and colour that in an opposing colour. because i(r)<j(r)<i(r+1)<j(r+1) the values you will colour will always be distinct but because you are colouring in two multiples of multiples of each block in different colours, every arithmetic progression will never be homogeneous in colour. The remaining numbers that are not coloured by this algortithm could be coloured any way.

I also found a solution based on the fair sharing theorem. It works as so: First give a piece of * insert cuttable object here * to A, then to B. But to be fair, the next sequence will be B A. Use the same logic and you get: A B B A B A A B B A A B A B B A...... Replace each A with white (or black) and replace each B with black (or white) and you get one valid answer.

The first thing that came to my mind was Cantor's diagonal argument. Initially, let's say we will color everything white. Now, as the set of all infinite arithmetic progressions is countable, we will pick the first of these progressions and change the first element of the progression to black, and then pick the second one and color its second element to black and so on. In this way, we get all the progressions with non-constant colors. However, I am assuming here that the progressions are ordered lexicographically, so that cases such as the one where the first element of the first progression is same as the $m$ th element of the $n$ th progression, with $m\ne n$ , does not arise. I think this is a valid construction. Please comment if there are loopholes in the construction that I overlooked.

Color them with the following infinite procedure:

• 1) set n to 1

• 2) set p to 1

• 3) color numbers n to n+p-1 black

• 4) color n+p to n+2p-1 white

• 5) change n to n+2p

• 6) change p to p+1

• 7) go to 3

Notice that, with this procedure, numbers get separated in "intervals" of consecutive numbers of the same color. Every black interval is followed by a white interval of the same length, and every white interval is followed by a black interval of length equal to its own length plus one.

Now to prove that this works:

Start with an arithmetic progression with some initial value a1 and some addition value r , and suppose, without loss of generality, that a1 is white. Follow this arithmetic progression until you either find a black number (in which case your work is done) or until you find an element b such that both b and b+r are in the same white "interval". You will necessarily find such a pair, since there is a white interval for all possible lengths.

If they are in the same white interval, that implies that the length of the interval is greater than r . Now, let c be the last element of the arithmetic progression within that same white interval. Note that c+r is black, since the length of the next black interval is necessarily greater than r .

As the other solutions allude to, one trick is to:

1) have finite blocks of numbers of one colour followed by finite blocks of numbers of the other colour; and

2) make sure you increase the size of the blocks so that no matter how large the common difference $d$ , there are adjacent blocks that are both larger than $d$ . Every arithmetic sequence must hit adjacent blocks at some point.

You could tweak this trick to make solutions without blocks of unbounded length. In fact there are colourings where the blocks are either length one or two.

Take Arjen's solution for example. The blocks are length 1, 2, 3, 4, ... Instead of changing block colour, we map Arjen's colouring to different patterns. For Arjen's white blocks, have the pattern that odd numbers are white and even numbers are black. For Arjen's black blocks, have the opposite pattern so odd numbers are black and even numbers white.

Arjen:

w-bb-www-bbbb-wwwww-bbbbbb...

map(Arjen):

w-wb-bwb-bwbw-wbwbw-wbwbwb...

Let's prove this works.

If the common difference $d$ is odd, there will be an Arjen block longer than $2d$ that contains at least two terms of the arithmetic sequence. In map(Arjen), these two terms are differently coloured as they have opposite parity and the alternating pattern is preserved.

If $d$ is even, there will be two adjacent Arjen blocks each of length greater than $d$ that each contain at least one term of the arithmetic sequence. In map(Arjen), these two terms have the same parity but the alternating pattern is different so the two terms are differently coloured.

The Thue-Morse Sequence satisfies this.

Rohit oraon