Let $E$ denote the set of $25$ points $(m,n)$ in the $\text{xy}$-plane, where $m,n$ are natural numbers, $1\leq m\leq5,1\leq n\leq5$. Suppose the points of $E$ are arbitrarily coloured using two colours, red and blue. SHow that there always exist four points in the set $E$ of the form $(a,b),(a+k,b),(a+k,b+k),(a,b+k)$ for some positive integer $k$ such that at least three of these four points have the same colour. (That is, there always exist four points in the set $E$ which form the vertices of a square with sides parallel to the axes and having at least three points of the same colour.)
Problem
Source: RMO 2018 P4
Tags: combinatorics
07.10.2018 14:58
Assume not, then every square with sides parallel to the axes must have two red and two blue points. Start with the top left point. WLOG let it be blue. Then consider two cases: the adjacent squares can be R-R or R-B. Keep constructing and we reach a contradiction.
07.10.2018 14:59
I did it like this: Let us assume that the condition does not hold, that is, there exists no square with more than $2$ vertices of one colour. Then each square must have $2$ red and $2$ blue vertices. This implies that the total number of red and blue vertices is equal, which is impossible, as $25$ is odd.
07.10.2018 15:03
DynamoBlaze wrote: I did it like this: Let us assume that the condition does not hold, that is, there exists no square with more than $2$ vertices of one colour. Then each square must have $2$ red and $2$ blue vertices. This implies that the total number of red and blue vertices is equal, which is impossible, as $25$ is odd. Its' wrong. Consider the following counter example for a 3x3 square: RBR RBR BRB
07.10.2018 15:14
DynamoBlaze wrote: I did it like this: Let us assume that the condition does not hold, that is, there exists no square with more than $2$ vertices of one colour. Then each square must have $2$ red and $2$ blue vertices. This implies that the total number of red and blue vertices is equal, which is impossible, as $25$ is odd. It's trivial that you're wrong. But, even if we consider that you're correct, can you explain a little bit more ?
07.10.2018 16:04
This one is long and boring. For the sake of contradiction, assume that any square of the lattice board has $2$ red and $2$ blue. Lemma: Consider a $3\times 2$ box. First row and third row have same number of red. Case 1: The two red squares on the corner squares are adjacent. \begin{align*} B--&-B\\ ---&--\\ ---&--\\ ---&--\\ R--&-R\\\\ \end{align*} Now consider the point $(2,5)$. If it is blue then our lemma is contradicted (then first two and last two points of the $2\times 5$ box have different reds). Thus we have (WLOG, the center square is red), \begin{align*} BR-&RB\\ R--&-R\\ --R&--\\ B--&-B\\ RB-&BR\\ \end{align*} We get a lot of stuff which is fixed now (consider $2\times 2$ squares). \begin{align*} BR-&RB\\ RB-&BR\\ --R&--\\ BR-&RB\\ RB-&BR\\ \end{align*} Now the remain four pairs of unfilled squares have two contain exactly one red and one blue. Consider $(4,3)$ and $(2,3)$ they must blue. Thus now we have \begin{align*} BRR&RB\\ RBB&BR\\ RBR&BR\\ BRB&RB\\ RBR&BR\\ \end{align*} But we can find the square $(1,1),(3,1),(1,3),(3,3)$ and we have contradiction. Case 2: The reds are in opposite corners. We have something like this: \begin{align*} B--&-R\\ ---&--\\ B--&-R\\ ---&--\\ R--&-B\\ \end{align*} Thus consider $(3,3)$ if it's red then we get contradiction with top right square and if its left then we get contradiction with top left square.
07.10.2018 16:36
Wlog assume that the maximum number of points are blue then no. of blue points >=13 Now no. of distinct squares such that all the points belong to atmost one square <= n= gif(25/4)=6 For the sake of contradiction assume that each square contain atmost 2 blue points Then no. of blue points <= 2*n = 12 But this contradicts the first inequality hence there exists at least one square which has three blue points, which is the required square.
07.10.2018 16:44
MathKnight16 wrote: DynamoBlaze wrote: I did it like this: Let us assume that the condition does not hold, that is, there exists no square with more than $2$ vertices of one colour. Then each square must have $2$ red and $2$ blue vertices. This implies that the total number of red and blue vertices is equal, which is impossible, as $25$ is odd. Its' wrong. Consider the following counter example for a 3x3 square: RBR RBR BRB In a $3\times3$ grid this would be wrong, because there is a total of $5$ squares. But in a $5\times 5$ grid there are $30$ squares, so this should be correct.
07.10.2018 16:48
Can anyone check if this is correct (ive never solved a problem of this type): Claim:If there is any $3\times 3$ grid of points/square with diagonal points of same colour, the result follows. Proof: WLOG let center point be red- $$B - R$$$$ - R - $$$$R - B$$ Now, considering $1 \times 1$ grid in top-right and bottom left corners, we get remaining points are blue. The $1 \times 1$ square in top left corner has 3 blue points, thus proving our claim. $\square$ We try to show that there is no case where each square has 2 red and 2 blue. Now, for the $5 \times 5$ square, assume center is red. Applying our claim on square with corners $(1,1), (1,3), (3,1), (3,3)$, we get that $(1,1)$ must be blue. And similarly $(5,5)$ is blue. Thus, $(1,5)$ and $(5,1)$ are red. $$R---B$$$$-----$$$$--R--$$$$-----$$$$B---R$$ Now consider the $3\times 3$ grid in top left corner. By our claim, we get the desired result. $\square$
07.10.2018 17:46
MathKnight16 wrote: Assume not, then every square with sides parallel to the axes must have two red and two blue points. Start with the top left point. WLOG let it be blue. Then consider two cases: the adjacent squares can be R-R or R-B. Keep constructing and we reach a contradiction. I did it this way and concluded that it is the same for every $n*n$ square if $n$ is odd.
07.10.2018 18:06
Here's my solution: Assume to the contrary that such a square doesn't exist. By PHP, atleast three of the five points in the first row must be colored with the same color. WLOG assume this color is blue. CASE-1 $(1,1),(2,1),(4,1)$ are colored blue. \begin{align*} -----\\ R--R-\\ -R-R-\\ RR---\\ BB-B-\\ \end{align*}Then the square formed by points $(1,2),(2,2),(2,3),(1,3)$ has 3 red vertices; i.e. a contradiction. A similar argument is valid when $(1,1),(3,1),(4,1)$ or $(2,1),(3,1),(5,1)$ or $(2,1),(4,1),(5,1)$ are colored blue. CASE-2 $(1,1),(2,1),(3,1)$ are colored blue. \begin{align*} -----\\ -----\\ R-R--\\ RRR--\\ BBB--\\ \end{align*}Then the square formed by points $(1,2),(2,2),(2,3),(1,3)$ has 3 red vertices; i.e. a contradiction. A similar argument is valid when $(2,1),(3,1),(4,1)$ or $(3,1),(4,1),(5,1)$ are colored blue. CASE-3 $(1,1),(3,1),(5,1)$ are colored blue. \begin{align*} R---R\\ -----\\ R-R-R\\ -----\\ B-B-B\\ \end{align*}Then the square formed by points $(1,3),(3,3),(3,5),(1,5)$ has 3 red vertices; i.e. a contradiction. CASE-4 $(1,1),(2,1),(5,1)$ are colored blue. \begin{align*} R-RBR\\ -RRBR\\ -----\\ RR-B-\\ BB--B\\ \end{align*}Then the square formed by points $(2,4),(3,4),(3,5),(2,5)$ has 3 red vertices; i.e. a contradiction. A similar argument is valid when $(1,1),(4,1),(1,1)$ are colored blue. Thus, we arrive at a contradiction for all 10 possibilities, and so the required square always exists.
07.10.2018 18:07
Well this was a long case bashy problem
07.10.2018 20:22
TheDarkPrince wrote: This one is nice. TheDarkPrince wrote: Well this was a long case bashy problem You are very indecisive
08.10.2018 10:03
CASE WORK Assume the contrary. Consider the four corner squares. We have two cases: First case: \begin{align*} &B---B\\ &-----\\ &-----\\ &-----\\ &R---R\\\\ \end{align*} In this case, again, we may assume WLOG that the centre square is red. Then we can fill up more squares: \begin{align*} &B-R-B\\ &-----\\ &B-R-B\\ &-----\\ &R-B-R\\\\ \end{align*} and blah, I give up writing.
08.10.2018 10:25
Here's a pretty clean approach similar to some of the other solutions on the thread. We $\{\pm 1\}$-label the points instead, suppose that every axis-aligned square has sum 0, and aim for a contradiction. Consider a $3 \times 3$ grid and the following global sum: \[\begin{bmatrix} 1 & 1 & \\ 1 & 1 & \\ & & \end{bmatrix} - \begin{bmatrix} & 1 & 1\\ & 1 & 1\\ & & \end{bmatrix} - \begin{bmatrix} & &\\ 1 & 1 & \\ 1 & 1 & \\ \end{bmatrix} + \begin{bmatrix} & &\\ & 1 & 1\\ & 1 & 1 \end{bmatrix} + \begin{bmatrix} 1 & & 1\\ & &\\ 1 & & 1 \end{bmatrix} = 2 \begin{bmatrix} 1 & &\\ & &\\ & & 1 \end{bmatrix}. \]Thus opposite corners of any $3 \times 3$ grid bear opposite values. Similar reasoning applies to the opposite corners of the whole $5 \times 5$ grid (simply dilate the matrices above by a factor of two). Now the points $(1, 1)$, $(3, 3)$, $(5, 5)$ must be assigned different values, contradiction.
08.10.2018 10:29
CantonMathGuy wrote: We $\{\pm 1\}$-label the points instead I started writing my probable solution using this exact same thing, but couldn't end up.
08.10.2018 10:32
^^ I wanted to do something similar, but I was like whatever. Nice
19.05.2019 20:18
Non case-bashy proof( different from the case-base I did in the exam): By PHP, there must be 13 points of one color, say blue. Now let the 5 rows be A,B,C,D,E, and there be A',B',C',D',E' blues in each respective row. Calculate the number of pairs of blue color which one can take on any particular row( if 1st ,3rd, 5the cell of 1st row is blue then we have 3C2=3 pairs for the first row). Take the sum of all such pairs, i.e. $\binom{A'}{2}+\binom{B'}{2}+...\binom{E'}{2}$. Now $A'+B'+C'+D'+E' \geq 13$. Use the fact that if $A>B>C>D$ and $A+D=B+$, then $\binom{A}{2}+\binom{D}{2}>\binom{C}{2}+\binom{B}{2}$ to get that the minimum of this sum is at $11>\binom{5}{2}=10$. Now by PHP, there are some two numbers k,l between 1 and 5 and some two rows such that both rows have their $k^{th}$ and $l^{th}$ cells blue, forming a rectangle.
07.05.2020 12:03
Represent each of the 25 points as elements of the matrix $[A_{ij}]_{5\times5}$, with elements either $(+1)$ or $(-1)$, depending upon the colour of the point. Let $N_1$ represent the number of points with colour $(+1)$. Similarly, let $N_2$ represent the number of points with colour $(-1)$. Let $S_1$ represent the sum of all the elements of this matrix. $S_1 = \sum_{i=1}^{5} \sum_{j=1}^{5}A_{ij}$ Let $S_2$ represent the sum of all the elements of the inner $3\times 3$ matrix (i.e. without $1st$ row and column, and without $5th$ row and column). $S_2 = \sum_{i=2}^{4} \sum_{j=2}^{4}A_{ij}$ For each square having vertices among the $25$ points, associate a number that is the sum of all the vertices of that square. Let $S_0$ be the sum of all such numbers for all squares. $S_0 = 4\times(A_{11}+A_{15}+A_{51}+A_{55}) + 4\times(A_{12}+A_{21}+A_{14}+A_{41}+A_{25}+A_{52}+A_{45}+A_{54}) + 4\times (A_{13}+A_{31}+A_{35}+A_{53}) + 6\times(A_{22}+A_{24}+A_{42}+A_{44}) + 6\times(A_{23}+A_{32}+A_{34}+A_{43}) + 8\times(A_{33})$ [$A_{11}$ comes in four squares, it is counted four times. $A_{21}$ comes in four squares. Similarly, for other elements in the matrix] $S_0 = 4\times S_1 + 2\times S_2 +2\times A_{33} $ Similarly, let $S_3$ denote the same sum but with the inner $3\times 3$ matrix. $S_3 = 2\times(A_{22}+A_{24}+A_{42}+A_{44}) + 2\times(A_{23}+A_{32}+A_{34}+A_{43}) + 4\times(A_{33})$ $S_3 = 2\times S_2 + 2\times A_{33} $ Hence, $S_0 = 4\times S_1 + S_3 $ Since there are an odd number of total points (i.e. 25 points), parity of $N_1$ and $N_2$ are different. Hence, one of $N_1$ or $N_2$ is odd and the other is even. $S_1 = N_1\times(+1) + N_2\times(-1)$ Hence, $S_1$ is not equal to zero. Now, assume on the contrary that there doesn't exist a square with at least 3 vertices of the same colour. This implies there are two $(+1)$ and two $(-1)$ vertices associated with each square. So, the sum of all the vertices of each square is zero. Each individual sum equal to zero implies $S_0=0$, by definition. Similarly, $S_3=0$, by definition. This gives $4\times S_1 = 0$, which is a contradiction. $\qquad\blacksquare$
31.03.2023 09:47
Actually this problem is equivalent to there exist a right angle triangle whose three vertex coloured with same colour and This can be easily prove using PHP.