Arithmetically progressive

If we color the integers in $S$ red and those not in $S$ blue, we get a certain case of a famous problem, solved by Van der Waerden . We can simply pull out the number $W(2,3) = \boxed{9}$ , but that's not very interesting is it? ;)

First, note that $N = 8$ is not valid: We can do the coloring RBBRRBBR to avoid a monochromatic 3-term arithmetic progression (hereby called MAP for Monochromatic (3-term) Arithmetic Progression). Also, $N < 8$ aren't valid either; just truncate the above coloring to $N$ terms and we still lack a MAP. We will now prove that $N = 9$ suffices. The proof also exists on the net , but what follows is my own solution when I first saw this problem several years ago.

Suppose there exists a coloring that doesn't make a MAP. WLOG let 1 be colored red, otherwise swap red and blue.

• Case 1: 2 is red

Then 3 is blue, otherwise (1,2,3) forms a red MAP.

• Case 1.1: 4 is red

Then 6,7 are blue, otherwise (2,4,6) or (1,4,7) forms a red MAP. Then 5,8 are red, otherwise (5,6,7) or (6,7,8) forms a blue MAP. But (2,5,8) forms a red MAP.

• Case 1.2: 4 is blue

Then 5 is red, otherwise (3,4,5) forms a blue MAP. Then 8,9 are blue, otherwise (2,5,8) or (1,5,9) forms a red MAP. Then 6,7 are red, otherwise (4,6,8), (7,8,9) forms a blue MAP. But (5,6,7) forms a red MAP.

• Case 2: 2 is blue

• Case 2.1: 3 is red

Then 5 is blue, otherwise (1,3,5) forms a red MAP. Then 8 is red, otherwise (2,5,8) forms a blue MAP.

• Case 2.1.1: 4 is red

Then 7 is blue, otherwise (1,4,7) forms a red MAP. Then 6 is red, otherwise (5,6,7) forms a blue MAP. But (4,6,8) forms a red MAP.

• Case 2.1.2: 4 is blue

Then 6 is red, otherwise (4,5,6) forms a blue MAP. Then 7,9 is blue, otherwise (6,7,8) or (3,6,9) forms a red MAP. But (5,7,9) forms a blue MAP.

• Case 2.2: 3 is blue

Then 4 is red, otherwise (2,3,4) forms a blue MAP. Then 7 is blue, otherwise (1,4,7) forms a red MAP. Then 5 is red, otherwise (3,5,7) forms a blue MAP. Then 6,9 are blue, otherwise (4,5,6) or (1,5,9) forms a red MAP. But (3,6,9) forms a blue MAP.

The above covers all cases, so it's impossible to have a coloring of 9 numbers without making a MAP. So all colorings of 9 numbers always make a MAP, and so the minimum value of $N$ is $\boxed{9}$ .

(Note: The solution can be better understood if you keep drawing the things as you read)

We want to find the smallest $N$ for which the property holds good. Instead, we will find the largest $N$ for which the property doesn't hold good.

Suppose we have the set $\{1,2,3,4,5...,N\}$ and you choose a random element. Let the elements be $\{ i-n , i-n+1 , ... i-3 , i-2 , i-1, i , i+1 , i+2 , i+3, i+4 , ... i+n\}$ If you choose the element $i$ there arise some cases. We will do this case by case.

_ Case 1 _ : After selecting $i$ , you select $i+1$ , so now your next selection cannot be $i+2$ or $i-1$ as the three elements will form an A.P. Now again there are sub-cases after selecting $i+1$ $$ SUB- CASE 1 : (You select $(i+2)$ ) Now after selecting $i+2$ , we are bound to have the selection of elements lying between $(i)$ and $(i+3)$ otherwise we will get an A.P. So we see that we are limited to a $5$ element selection. $$ SUB-CASE 2 : ( You select $(i+3)$ ) By similar arguments, we are now bound to select the elements lying between $(i-2)$ and $(i+5)$ , a $8$ -element selection. Since we want the worst case scenario, we observe that for the selection $\{ i-2 , i , i+3 , i+5 \}$ , there exists no such A.P. satisfying the conditions in the question.

Now with similar arguments used above we can explore the cases when $$ Case 2 After selecting After selecting $i$ , you select $i+2$ , and $$ Case 3 After selecting $i$ , you select $i+3$ . $$ We have to keep in mind that more cases will not arise, like we cannot select $i+4$ since then $(i+1) , (i+2) , (i+3)$ will form an A.P. After combining the results of all the cases, we find that $N=8$ is the largest $N$ so that the conditions in the questions do not hold good. Thus we conclude that the smallest value of $N$ is $\boxed{N=9}$

8 doesn't work since the subset {2,4,5,7} allows no progression. I like to visualize it as

_ O _ O O _ O _

Where the O's are in $S$ and the _'s are not. Every number below 8 can be shown not to work by removing spots from the right of my visualization.

Now, I will show 9 works. WLOG, say 5 is in $S$ . If it isn't, we can simply flip which elements are in $S$ . Notice that if (1,2,3,4) is in $S$ , then the corresponding element of (9,8,7,6) isn't.

? ? ? ? O ? ? ? ?

Now, we have two cases: Neither of 1 and 3 are in $S$ , or exactly one is (or we are done).

If neither are in, then 7 and 9 both are in, and we are done since 5,7,9 are in $S$ .

If one, say 3, is in, then we have

_ ? O ? O ? _ ? O

Now we see this is symmetrical to the case when 1 is in $S$ (reflect horizontally). Now, 4 cannot be in $S$ .

_ ? O _ O O _ ? O

Now we have 3,6,9 in $S$ , and so the answer is $\boxed{9}$ .