This problem is quite difficult for there are almost no motivations. The main technical claim is seemingly unrelated and useless. I would love to see a more motivating and simpler solution , if exist. Remarks: The following solution looks unenlightening, and it is. The main idea is just noticing the reducing (6)/(7) is possible. The first progress is to guess that statements of form (1) is rather important, and are all true. We would then naturally attempt induction. This has to be done through looking for ways to cancel some consecutive points with density 1/2. The hardest step is to notice (6) and (7) are just two ways to do just that. It is not clear that (6) and (7) are enough to handle all cases, but with some (in general useless) hopeful thinking , intuition , and bashing identities, they turn out to suffice. We say two coloured points, a, (a+n) is a n-jump. (1) We will consider statements of form "Colour (200+n) integers of (200+2n) , must exist yummy of at least 199". We use strong induction. The first case, a segment of length 200 with 200 coloured points: We can obviously find the 199-yummy segment. (2) If we colour k points of n , such that no two points are adjacent. Then: k is at most (n/2) if n is even. k is at most (n/2)+(1/2) If n is odd. Proof: If n is even this is obvious, just by considering pairs {1,2},{3,4}....{n-1,n} If n is odd, consider classes {1,2},{3,4}....,.{n-2,n-1},{n}. To have no adjacent coloured points, each class contains at most 1 point, so there are at most (n/2) + (1/2) points. Contradiction. Back to the main proof: Suppose the whole segment of (200+n) isn't yummy. Then we know it is lack of k-jump for some k. Consider the equivalence of integers a~b means $k|(b-a)$. Suppose $200+2n = ak+c$. Then there are c classes of size (a+1) and (k-c) classes of (a). (3) The number of odd sized classes is at least 200. Proof: Suppose not. The total number of red points, using (2) , will be $\leq$ than half number of elements + half number of odd classes, $< (100+n) + (100) = 200+n$. Contradiction. We then establish (4) k is at least 200 Proof: So that there are at least 200 classes. (5) k cannot be both at greater than n and less than (200+n) Proof: Suppose the contrary, we know $k > n $, $k\geq200$. By inspection of the size in equation $200+2n = ak+c$, a is either 1 or 2. If a is 1, then since k< 200+n, c>n. Since the number of odd classes when a=1 is $(k-c)<200$, this violates (3). If a is 2, then (3) implies we need c>= 200. Then $ak+c = 2k+c > 2n+200 = LHS$. Contradiction. After these , the remaining cases are $k \leq n$ and $k \geq (200+n)$. We can offer a reduction to a smaller n in each of these cases. (6) Reduction for $k \leq n$. Construction: The left most 2k points contains at most k coloured points. We can remove all these 2k points. The condition $k \leq n$ is such that there are at least 200 points left after the removal. Notice removing these points, the balance of colouring (200+A) points of (200+2A) is maintained, but with a smaller A. (7) Reduction for $k \geq 200+n$. Construction: Let z=(200+2n)-k. Consider the z points at two ends. Since we lack a k-jump, these 2z points can have at most z coloured points. Therefore, after removing the points, the balance of colouring (200+A) points of (200+2A) is maintained, but with a smaller A. Note that $k \geq 200+n$ is such that there are at least 200 points left after the removal. Since we can always reduce to a smaller case, the proof is complete.

Of course there is a solution with enough motivation Let's say the set of the 600 integers is $ A $, and we will define $ f(X) $ for every interval $ X $ $ f(X)=\left | A\cap X \right |-\left | A^{c}\cap X \right | $ Also, we will define $ X_0 $ as the interval with the smallest $ |X| $ among the $ X $s with the smallest $ f(X) $. Clearly, we can show that $ X_0 $ is a yummy segment, and of course $ |X_0| \geq f(X_0) \geq f ([1,1000])=200 $

Sounds like a clean solution. However, all I can see from the minimising f(X) condition is just maximising the number of points in a particular sense. I cannot see how this would force out existence of each sizes. Can you show me how this could lead to $X_0$ being a yummy segment? (also can you show me where you have seen/found the solution?)

arvindf232 wrote: Sounds like a clean solution. However, all I can see from the minimising f(X) condition is just maximising the number of points in a particular sense. I cannot see how this would force out existence of each sizes. Can you show me how this could lead to $X_0$ being a yummy segment? (also can you show me where you have seen/found the solution?) Well, it's my solution. Thank you. Well, if you say that $ X_0 $ is not a yummy segment, you can see that there exists a $ t $ in the problem statement. Then, you'll see that you can construct a segment $ Y $ that is $ |Y|<|X_0| $ and $ f(Y) \leq f(X_0) $

Ok thanks I see now. I see the main problem of my solution in comparison to yours is that your way didn't need to care about always preserving 200 points. That's where most of my annoyance come from, so I can avoid (3),(4),(5).