Marking vertices in splitted triangle

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

Marking vertices in splitted triangle

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Mexico

The post below has been deleted. Click to close.

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

647 posts

#1 h Feb 7, 2022, 1:51 PM

Y by

Let $n$ be a positive integer. Consider a figure of a equilateral triangle of side $n$ and splitted in $n^2$ small equilateral triangles of side $1$ . One will mark some of the $1+2+\dots+(n+1)$ vertices of the small triangles, such that for every integer $k\geq 1$ , there is not any trapezoid(trapezium), whose the sides are $(1,k,1,k+1)$ , with all the vertices marked. Furthermore, there are no small triangle(side $1$ ) have your three vertices marked. Determine the greatest quantity of marked vertices.

This post has been edited 1 time. Last edited by mathisreal, Feb 7, 2022, 1:54 PM

Z K Y

The post below has been deleted. Click to close.

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

30653 posts

#2 h Sep 17, 2022, 7:12 PM

Y by

Let $n$ be a positive integer. Consider a figure of a equilateral triangle of side $n$ and splitted in $n^2$ small equilateral triangles of side $1$ . One will mark some of the $1+2+\dots+(n+1)$ vertices of the small triangles, such that for every integer $k\geq 1$ , there is not any trapezoid(trapezium), whose the sides are $(1,k,1,k+1)$ , with all the vertices marked. Furthermore, there are no small triangle(side $1$ ) have your three vertices marked. Determine the greatest quantity of marked vertices.

https://cdn.artofproblemsolving.com/attachments/7/d/a31dd041fcafa9c90b451b16efe3592ec9d721.png

Note: The figure shows an example of a board when $n = 4$ . and an example of one of the mentioned trapezoids, with three of its vertices marked and with $k = 2$ .

This post has been edited 3 times. Last edited by parmenides51, Sep 17, 2022, 8:25 PM

Z K Y

The post below has been deleted. Click to close.

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

19 posts

#3 h May 18, 2025, 1:37 AM • 1 Y

Y by plagueis

The answer is $(k+1)^2$ if $n=2k$ or $(k+1)(k+2)$ if $n=2k+1$ .

First, we are going to prove for $n\geq 2$ that if $f(n)$ is the answer for $n$ , then
$f(n) \leq f(n-2)+n+1$
To prove this.

https://cdn.artofproblemsolving.com/attachments/2/2/416721cf806f2f8f5f00066f9986ee61558929.png

In the pink triangle of length $n-2$ we have maximum $f(n-2)$ marked vertices, and we have $2n+1$ more points, we consider these points in a path (the red path in the picture).

We cannot have 3 consecutive marked points because that implies a short triangle with their three vertices marked.

A packet of marked points is the maximum consecutive marked points.
Let's say we have $a$ packets of size 2, and $b$ packets of size 1.
Now, between two packets of size 2, it should be an even distance otherwise it will form a trapezoid with all the vertices marked.

Then between two packets of size 2 it's at least one extra not marked vertex, otherwise the distance is $2k+1$ where $k$ is the number of packets of size 1 between the packets of size 2.

Then we use at least
$2a+b+ (a+b-1)+(a-1) = 2(2a+b)-2 \leq 2n+1$ The marked points, the spaces between each packet and the "extra" not marked point between the packets of size 2.

Then $2a+b \leq \frac{2n+3}{2}$ but $2a+b$ is integer then $2a+b \leq n+1$ , then the marked points in the path are maximum $n+1$ , and the total points are maximum $f(n-2)+n+1$ .

We have $f(0)=1, f(1)=2$ and then if $n=2k+1$ is odd the maximum is
$2+4+\ldots+(2k+2) = 2 \left(1+2+\ldots+k+1\right)=(k+1)(k+2)$ and if $n=2k$ even the maximum is
$1+3+\ldots+ 2k+1 = (k+1)^2$
And both are possible, if you enumerate the rows from 1 to $n+1$ and taking the rows with the same parity as $n+1$ (It takes just the sums $2+4+\ldots$ and $1+3+\ldots$ depending of the parity of $n$ ) we have the values that we want, and it works because each trapezium or triangle has a segment of size 1 that it's not horizontal and it has one vertex not marked.

This post has been edited 1 time. Last edited by sopaconk, May 18, 2025, 1:37 AM
Reason: I don't know how to put images

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a