Ahh... Grids!

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Ahh... Grids!

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: RMO 2023/6

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

450 posts

#1 h Oct 29, 2023, 10:57 AM

Y by

Consider a set of $16$ points arranged in $4 \times 4$ square grid formation. Prove that if any $7$ of these points are coloured blue, then there exists an isosceles right-angled triangle whose vertices are all blue.

This post has been edited 1 time. Last edited by SatisfiedMagma, Jan 5, 2024, 3:59 PM
Reason: more latex?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

14 posts

#2 h Oct 29, 2023, 11:25 AM

Y by

Can we replace $16$ by $n^2$ and $7$ by $2n-1$ here?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1184 posts

L567

#3 h Oct 29, 2023, 5:09 PM • 3 Y

Y by Nuterrow, zhenghua, SatisfiedMagma

Here's a solution by Rohan from his livestream, which avoids casework:

(This is much easier to see with a picture, but until I put one up...)

Suppose not. Note that in any square, at most two points may be marked. Partition grid into the center, the corners and two other squares. This forces that one of the central squares is marked, call it $C$ . Observe that the $3 \times 3$ grid around $C$ can have at most two other marked points. Further, using isosceles right triangles with $C$ as the vertex, we can pair the rest of the squares (excluding the $3 \times 3$ ) into three pairs and one corner, each of which must have a marked square. Therefore the opposite corner must be marked, but this leads to a contradiction as now neither of the squares in one of the pairs can be marked.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1774 posts

#4 h Oct 29, 2023, 5:58 PM

Y by

RMO 2017 P4 seems to be a weird "inverted" version of this problem...anyone know how the solution to that might help in this one?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

64 posts

#5 h Oct 30, 2023, 3:15 PM

Y by

How can someone even casework perfectly? like there are so many cases.. in exam, i just proved for like 3-4 cases and wrote that alone

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

154 posts

#6 h Oct 31, 2023, 6:05 AM

Y by

polynomialian wrote:

How can someone even casework perfectly? like there are so many cases.. in exam, i just proved for like 3-4 cases and wrote that alone

All cases with $4$ colors on one side get rejected (it is easy to prove) and then ig you are left with $4$ cases...

This post has been edited 1 time. Last edited by Jishnu4414l, Oct 31, 2023, 6:05 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

The_Great_Learner

26 posts

The_Great_Learner

#9 h Oct 31, 2023, 7:21 PM • 3 Y

Y by maths_arka, Rijul saini, Pranmoyee

Sol by RG:- For the sake of contradiction assume there exists no isosceles triangle.
Step 1 The Center $2 \times 2$ square must have a blue point.
Proof We partition the the grid into $4$ squares as in the following diagram one of which is the center $2 \times 2$ square. Clearly each square have atmost $2$ blue points so as to avoid isosceles right triangle. This means that the three squares (other than the center $2 \times 2$ square) altogether have atmost $6$ blue points. Since there are $7$ blue points, the Center $2 \times 2$ square must have a blue point.

https://cdn.discordapp.com/attachments/961202142809563140/1168970057683058729/image.png?ex=6553b334&is=65413e34&hm=4ef8f8188314785c12e61e353cd3c9de9f96a7397d37d918ecf651842586776f&

We pick a blue point in the center $2 \times 2$ grid and name it $O$ .Let us consider the $3 \times 3$ grid whose center is $O$ .We name this grid $G$ .

https://cdn.discordapp.com/attachments/961202142809563140/1168973312299380837/image.png?ex=6553b63c&is=6541413c&hm=557c911fb589041d5343d1b57b59b2a48bf857d19463fa617e804f066dfbf3fe&

Step 2 There are atleast $3$ blue points in grid $G$ .
Proof We label the vertices outside grid $G$ as $A,B,C,D$ as in the following diagram such that vertices labelled by same alphabet along with $O$ form an isosceles right triangle. So we have atmost $1A,1B,1C,1D$ blue vertex. Thus there are atmost $4$ blue vertices outside grid $G$ implying that there are atleast $3$ blue vertices in grid $G$ .

https://cdn.discordapp.com/attachments/961202142809563140/1168978319589523476/image.png?ex=6553bae5&is=654145e5&hm=9f3d2bf3b3f3213b09f14f21201c95c5b084323d09a2d3b3045d54b38fb94963&

Step 3 There are atmost $3$ blue vertices in grid $G$ .
Proof Since there are atleast $3$ blue vertices in grid $G$ so there exists blue points in grid $G$ other than $O$ . We partition the points (other than $O$ ) in grid $G$ into $2$ squares (red and green) as in the following diagram.

https://cdn.discordapp.com/attachments/961202142809563140/1168982412995342448/image.png?ex=6553beb5&is=654149b5&hm=a8e16681daa5030020a45c9d11d335f4512b25a08afeee79ddab951577fc2372&

Case 1 There exists a blue point in red square.
We name this blue vertex $P$ .Consider the purple trapezoid in the following diagram.Note that it can't have a blue point other than $O$ since otherwise that point along with $O,P$ would form an isosceles right triangle .Consider the pink square, it contains atmost $1$ blue point other than $O$ so as to avoid isosceles right triangle. Thus we obtain atmost $3$ blue points in grid $G$ .

https://cdn.discordapp.com/attachments/961202142809563140/1168987414568636417/image.png?ex=6553c35e&is=65414e5e&hm=091c8641b2653ca1a5e7e2881dd92e6bd251c89e019729e02177cd8ddf093e7b&

Case 2 There exists a blue point in green square.
We name this blue vertex $Q$ . Consider the purple rectangle in the following diagram. It doesn't contain any blue point other than $O,Q$ since otherwise that vertex along with $O,Q$ would form an isosceles right triangle.Consider the pink segment in the following digram, it can't contain more than $1$ blue point since otherwise those $2$ points along with $O$ would form isosceles right triangle.Thus we obtain atmost $3$ points in Grid $G$ .

https://cdn.discordapp.com/attachments/961202142809563140/1168989174402121828/image.png?ex=6553c501&is=65415001&hm=032af697c5725dc6bb2bd178176f1873757ee2867e8fbc9eebb38ed47e934138&

Step 4 Final contradiction
Since there are atmost $3$ blue squares and atleast $3$ blue squares in grid $G$ ,grid $G$ has exactly $3$ blue squares and there are exactly $4$ squares outside grid $G$ which implies there are exactly $1A,1B,1C,1D$ square (from step $2$ ).But then $OBD$ is isosceles right angled triangle.Contradiction.

https://cdn.discordapp.com/attachments/961202142809563140/1168992529493004378/image.png?ex=6553c821&is=65415321&hm=35659b488a489d487f14b6815992502309a150baef29e450ab7061f5212713aa&

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lifeismathematics

1188 posts

lifeismathematics

#10 h Oct 31, 2023, 8:06 PM • 4 Y

Y by The_Great_Learner, aman_maths, GeoKing, Nightwings

So here I present a solution...

$\mathrm{FTSOC}$ assume that there do not exists such an isosceles right-angled triangle whose vertices are all blue.

Then we start with drawing the $16$ point grid and stretching it's diagonal:

$[asy] size(2cm,2cm); dot((0,0)); dot((0,1)); dot((0,2)); dot((0,3)); dot((1,0)); dot((1,1)); dot((1,2)); dot((1,3)); dot((2,0)); dot((2,1)); dot((2,2)); dot((2,3)); dot((3,0)); dot((3,1)); dot((3,2)); dot((3,3)); draw((0,0)--(3,3)); [/asy]$

We start by casing on the colouring of the diagonal (the blue dot represents the points that are coloured blue and the red dot represents the dots which we can't choose):

$\mathrm{Case1:}$ There are $4$ blue points on the diagonal:

$[asy] size(2cm,2cm); dot((0,0), blue); dot((0,1)); dot((0,2)); dot((0,3)); dot((1,0)); dot((1,1), blue); dot((1,2)); dot((1,3)); dot((2,0)); dot((2,1)); dot((2,2), blue); dot((2,3)); dot((3,0)); dot((3,1)); dot((3,2)); dot((3,3), blue); draw((0,0)--(3,3)); [/asy]$
Since any square we choose in this grid will have at most two blue points as its vertices, we can't have the rest of the points to be blue ( $\dagger$ ) as otherwise clearly there exists an isosceles right-angled triangle then the configuration for this case would be something like this:

$[asy] size(2cm,2cm); dot((0,0), blue); dot((0,1),red); dot((0,2),red); dot((0,3),red); dot((1,0),red); dot((1,1), blue); dot((1,2),red); dot((1,3),red); dot((2,0),red); dot((2,1), red); dot((2,2), blue); dot((2,3), red); dot((3,0), red); dot((3,1), red); dot((3,2), red); dot((3,3), blue); draw((0,0)--(3,3)); [/asy]$

So This case is clearly not possible.
$\mathrm{Case 2:}$ $3$ points are coloured blue on the diagonal.

Now this case has two subcases:
Subcase 1: The coloring of the three points is like this:

$[asy] size(2cm,2cm); dot((0,0), blue); dot((0,1)); dot((0,2)); dot((0,3)); dot((1,0)); dot((1,1),red); dot((1,2)); dot((1,3)); dot((2,0)); dot((2,1)); dot((2,2), blue); dot((2,3)); dot((3,0)); dot((3,1)); dot((3,2)); dot((3,3), blue); draw((0,0)--(3,3)); [/asy]$

In this case first of all, clearly from ( $\dagger$ ) we have the immediate colouring like this:

$[asy] size(2cm,2cm); dot((0,0), blue); dot((0,1)); dot((0,2),red); dot((0,3),red); dot((1,0)); dot((1,1),red); dot((1,2)); dot((1,3)); dot((2,0),red); dot((2,1)); dot((2,2), blue); dot((2,3),red); dot((3,0),red); dot((3,1)); dot((3,2),red); dot((3,3), blue); draw((0,0)--(3,3)); [/asy]$

also colouring of the type:

$[asy] size(2cm,2cm); dot((1,0)); dot((1,1)); dot((2,0)); draw((1,0)--(1,1)--(2,0)--(1,0)); [/asy]$

and

$[asy] size(2cm,2cm); dot((1,0)); dot((2,1)); dot((3,0)); dot((2,0)); draw((2,1)--(3,0)--(1,0)--(2,1)); [/asy]$

are strictly prohibited hence we get the immediate colouring as:

$[asy] size(2cm,2cm); dot((0,0), blue); dot((0,1)); dot((0,2),red); dot((0,3),red); dot((1,0)); dot((1,1),red); dot((1,2)); dot((1,3),red); dot((2,0),red); dot((2,1)); dot((2,2), blue); dot((2,3),red); dot((3,0),red); dot((3,1),red); dot((3,2),red); dot((3,3), blue); draw((0,0)--(3,3)); [/asy]$

Now it is immediate that to complete colouring of $7$ we must choose left $4$ points but they will again form a isosceles triangle so this case is also not true.

Now:
Subcase 2: The coloring of the three points is like this:

$[asy] size(2cm,2cm); dot((0,0),red); dot((0,1)); dot((0,2)); dot((0,3)); dot((1,0)); dot((1,1),blue); dot((1,2)); dot((1,3)); dot((2,0)); dot((2,1)); dot((2,2), blue); dot((2,3)); dot((3,0)); dot((3,1)); dot((3,2)); dot((3,3), blue); draw((0,0)--(3,3)); [/asy]$

Now this case is similar to Subcase 1: from the arguments we above saw clearly the immediate colouring that would follow would be like this:
$[asy] size(2cm,2cm); dot((0,0),red); dot((0,1)); dot((0,2),red); dot((0,3)); dot((1,0)); dot((1,1),blue); dot((1,2),red); dot((1,3),red); dot((2,0),red); dot((2,1),red); dot((2,2), blue); dot((2,3),red); dot((3,0)); dot((3,1),red); dot((3,2), red); dot((3,3), blue); draw((0,0)--(3,3)); [/asy]$
Now clearly these four left points are the only choices to choose from, but then there is again an isosceles right-angled triangle in this configuration, so this case is also impossible.

so in all cases of $3$ points being blue, it's not possible.

Now the cases of $2$ , $1$ , $0$ blue points on the diagonal are very strong , in which we have that at least $3$ points will be blue in the equal $6$ points region divided by the diagonal , also if there are at least $4$ points blue in any of the two $6$ point regions then, in that case, clearly there is always an isosceles right-angled triangle.

so clearly case of $0$ point being blue coloured in the diagonal forces that at least $4$ points would be in any of $1$ region forming an isosceles right-angled triangle,so this case is also not possible.

so to proceed we just need to show that for $2$ point blue case $3$ and $2$ point splitting of blue coloured dot is not possible similarly for $1$ point blue case we need to show that $3$ and $3$ point splitting of the blue coloured dot is not possible and

$\mathrm{Case \hspace{0.1cm} of \hspace{0.1cm} 2 \hspace{0.1cm} points:}$ for this case clearly the only possible colourings are like this as rest will be get obtained by rotation:

$[asy] size(2cm,2cm); dot((0,0),blue); dot((0,1),red); dot((0,2),red); dot((0,3),red); dot((1,0),red); dot((1,1),blue); dot((1,2),red); dot((1,3),red); dot((2,0),red); dot((2,1),red); dot((2,2), red); dot((2,3)); dot((3,0),blue); dot((3,1),blue); dot((3,2), blue); dot((3,3), red); [/asy]$

$[asy] size(2cm,2cm); dot((0,0),red); dot((0,1),red); dot((0,2)); dot((0,3)); dot((1,0),red); dot((1,1),blue); dot((1,2),red); dot((1,3),red); dot((2,0),blue); dot((2,1),red); dot((2,2), red); dot((2,3),red); dot((3,0),blue); dot((3,1),red); dot((3,2), blue); dot((3,3), blue); [/asy]$
which clearly shows it's always possible to form a right-angled isosceles triangle in this case.
$\mathrm{Case \hspace{0.1cm} of \hspace{0.1cm} 1 \hspace{0.1cm} points:}$ for this case clearly the only possible colourings are like this (as others are same upto rotation):

$[asy] size(2cm,2cm); dot((0,0),red); dot((0,1),red); dot((0,2),red); dot((0,3),red); dot((1,0),red); dot((1,1),blue); dot((1,2),red); dot((1,3),red); dot((2,0),blue); dot((2,1),red); dot((2,2), red); dot((2,3),red); dot((3,0),blue); dot((3,1),blue); dot((3,2), blue); dot((3,3),red); draw((2,3)--(3,0)--(1,1)--(2,3),green); [/asy]$

giving us that there is no right-angled isosceles triangle in this case also

This exhausts all cases and hence we found that there must exist a right angled isosceles triangle with such colouring. $\blacksquare$

This post has been edited 2 times. Last edited by lifeismathematics, Oct 31, 2023, 8:17 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

147 posts

#11 h Oct 23, 2024, 9:18 AM

Y by

I have discussed this question in my RMO 2023 video on my channel "little fermat". Here is the Video

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a