Olympiad Comninatorics Chapter 2 problem 7

For discussing Olympiad Level Combinatorics problems
User avatar
ahmedittihad
Posts:181
Joined:Mon Mar 28, 2016 6:21 pm
Olympiad Comninatorics Chapter 2 problem 7

Unread post by ahmedittihad » Thu Dec 29, 2016 2:07 am

Given a finite set of points in the plane, each with integer coordinates, is it always possible to color the points red or white so that for any straight line L parallel to one of the coordinate axes the difference (in absolute value) between the numbers of white and red points on L is not greater than 1?
Frankly, my dear, I don't give a damn.

User avatar
ahmedittihad
Posts:181
Joined:Mon Mar 28, 2016 6:21 pm

Re: Olympiad Comninatorics Chapter 2 problem 7

Unread post by ahmedittihad » Sun Jan 01, 2017 1:14 am

This is all I could progress with.

WLoG, let's assume that every point is connectable by a line parallel to the axes. If every point aren't, we can just treat the non connectable set of points as the problem itself. We can also reduce the problem to the points which have other points on their x and y axis (bad points). Otherwise we can color that point to our benefit as it can only be a good influence.

Let us set out reference frame a rectangle having lattice points a vertices and having the set of all connectable and bad points in it.

Now, let $ x_1, x_2, ....x_n $ denote the difference of the number of white and red colored points on the lines parallel to the x axis. Similarly denote $ y_1, y_2, ....y_m $.

Now let us color the points on the line parallel to the x axis keeping in mind the problem condition for all $ x_i $s and ignoring the condition of the $ y_i$s such that, summation of $x_i$ $<2$. This is easily achievable.

Now, it is trivial that summation of $x_i $ $=$ summation of $y_i$. Which is $<2$. So if some $y_i$ doesn't meet the condition, there is another $y_j$ that can help $y_i$ meet the condition. Now we need to show an algorithm that can change the value of two $y_i$ and $y_j$ while keeping all the other values same.
Frankly, my dear, I don't give a damn.

Post Reply