Suppose that each point on a plane is colored with one of the colors red or yellow. Show that exist a convex pentagon with three right angles and all vertices are with same color.
Problem
Source: Kosovo MO 2019 Grade 12, Problem 2
Tags: combinatorics
03.03.2019 11:10
dangerousliri wrote: Suppose that each point on a plane is colored with one of the colors red or yellow. Show that exist a convex pentagon with three right angles and all vertices are with same color. Solution. Consider the plane as a cartesian grid. For the sake of contradiction, suppose there are no such pentagon exists. Claim 1. We can find a monochromatic rectangle. (Proof): Suppose there is no monochromatic rectangle. We can find three monochromatic collinear points, say $R_1 = (0,0),R_2=(a,0),R_3=(b,0)$ and all are red (WLOG). Now draw perpendicular lines $\ell_i$ through $R_i$ perpendicular to $\overline{R_1R_2R_3}$ for $i=1,2,3$. If $\ell_1$ contains at least two red points say $R_4 = (0,c)$ and $R_5=(0,d)$, then as there are no monochromatic rectangle, $(a,c),(b,c),(a,d),(b,d)$ are yellow which gives a monochromatic rectangle. Therefore each line $\ell_i$ contains at most one red point which clearly gives us a yellow rectangle. $\square$ Now we have a monochromatic rectangle, say red and the points are $R_1R_2R_3R_4$. Claim 2. All points between $R_1,R_2;R_3,R_4$ are yellow or all points between $R_1,R_4;R_2,R_3$ are yellow. (Proof): If there is no red point on any side of the rectangle, it anyways satisfies the condition. Therefore suppose there is a red point on any side of the rectangle, say $R_5$ and it lies on $R_1R_2$. If there is a red point on $R_1R_4$, say $R_6$ then the pentagon $R_2R_3R_4R_6R_5$ satisfies the condition. Therefore $R_1R_4$ is yellow and similarly $R_2R_3$ is yellow. $\square$ Now, we have a monochromatic red rectangle $R_1R_2R_3R_4$ rectangle and all points between $R_1,R_2$ and $R_3,R_4$ are yellow (WLOG). Now consider a yellow rectangle $Y_1Y_2Y_3Y_4$ such that $Y_1,Y_2\in R_1R_2$ and $Y_3,Y_4\in R_3R_4$. If there is any yellow point on $Y_1Y_4$ or $Y_2Y_3$ then we get a desired pentagon, therefore all points between $Y_1,Y_4$ and $Y_2,Y_3$ are red. Varying $Y_1,Y_2$ on $\overline{R_1R_2}$ gives that all points inside the rectangle $R_1R_2R_3R_4$ are red which clearly gives us a desired pentagon and we are done. $\blacksquare$
03.03.2019 11:42
The statement is true for any number $n$ of colors. It is an immediate corollary of van der Waerden, but here is an elementary solution. Let $N = (2n+1)^n$ and consider an $(2n+1) \times (2N+1)$ grid of points. By pigeonhole, three of the columns are the same; by pigeonhole again, in these columns, three of the points are the same color. This implies there exists a monochromatic $3 \times 3$ rectangular grid, which implies the desired statement.