Problem 2: good diagonals and triangles in 2006-gon

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

w

12 users

TOPICS

No tags match your search

M

No tags match your search

M

Problem 2: good diagonals and triangles in 2006-gon

G H J

Reveal topic tags

Extremal combinatorics

L

G H BBookmark kLocked kLocked NReply

Source: IMO 2006, 1. day

The post below has been deleted. Click to close.

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

7579 posts

ZetaX

#1 h Jul 12, 2006, 12:10 PM • 11 Y

Y by Davi-8191, anantmudgal09, A_Math_Lover, Adventure10, jhu08, son7, HWenslawski, megarnie, ImSh95, Mango247, cubres

Let $P$ be a regular $2006$ -gon. A diagonal is called good if its endpoints divide the boundary of $P$ into two parts, each composed of an odd number of sides of $P$ . The sides of $P$ are also called good.
Suppose $P$ has been dissected into triangles by $2003$ diagonals, no two of which have a common point in the interior of $P$ . Find the maximum number of isosceles triangles having two good sides that could appear in such a configuration.

Z K Y

The post below has been deleted. Click to close.

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

75 posts

#2 h Jul 12, 2006, 1:46 PM • 5 Y

Y by Adventure10, jhu08, ImSh95, Mango247, cubres

This problem isn't too hard, but unfortunately I spend most of my time on 3rd problem and didn't manage to solve it.

I have an additional question.. In how many ways can this (maximum) number be achieved?

Z K Y

The post below has been deleted. Click to close.

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

297 posts

Xixas

#3 h Jul 12, 2006, 3:50 PM • 7 Y

Y by anser, Adventure10, jhu08, Wizard0001, ImSh95, Mango247, cubres

Call a triangle good if it has two good sides and is isosceles. It is clear that those good sides must be equal. Let one of those triangles be $ABC$ and consider arc $AB$ containing odd number of sides of the 2006gon (we inscribe our polygon into a circle). Take any side in this arc and find the smallest good triangle whose one of two equal good sides cut off an arc containing this side. If this side is not $AB$ then we can pair our side with another one symmetric with respect to this smallest good triangle (located in the arc cut off by the other of the two of its equal sides). But we can't pair up all sides in arc $AB$ since there is odd number of them. So there is at least one of them whose smallest good triangle is $ABC$ . The same holds for $BC=AB$ . So every good triangle corresponds to at least two sides of 2006gon. Hence there are no more than $1003$ good triangles. The example with $1003$ is trivial.

Hope this is correct. I've created and written this solution down during last 15 minutes so my leader will have a hard time with it

Z K Y

The post below has been deleted. Click to close.

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

2 posts

#4 h Jul 12, 2006, 5:47 PM • 5 Y

Y by Adventure10, jhu08, ImSh95, Mango247, cubres

I solved this one using monovariance, which worked well although the proof was a bit too long for my own taste. I think I was a bit unclear about one thing so I'll probably not get a 7, but hopefully a 6.

Z K Y

The post below has been deleted. Click to close.

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

732 posts

#5 h Jul 12, 2006, 5:57 PM • 4 Y

Y by jhu08, ImSh95, Adventure10, cubres

Yes I found this problem to be quite straightforward ... since each "good triangle" has exactly two good sides, it is pretty logical to attempt to correspond each good side to a side of the polygon, which works easily.

Z K Y

The post below has been deleted. Click to close.

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

2607 posts

#6 h Jul 12, 2006, 6:21 PM • 5 Y

Y by jhu08, ImSh95, Adventure10, Mango247, cubres

First, no matter how we dissect the $2006$ -gon into (non-intersecting) triangles, we are bound to use $2003$ diagonals (easy induction on number of sides).

Next, we consider the maximum number of "good" triangles we can make by considering $m$ consecutive sides (the points are $0,1,2,\ldots,m$ ), together with a diagonal $0-m$ . Easy induction (again):

$m=1$ : 0;
$m=2$ : 1;
$m=3$ : 1;
$m=4$ : 2;
$m=5$ : 2;
$m=6$ : 3;
$m=7$ : 3;
$m=8$ : 4;
$m=9$ : 4;
etc.

The pattern is obvious. For the induction step, just break $0,1,\ldots,m$ into $0,1,\ldots,k$ and $k,\ldots,m$ . Also, you need to watch out for the cases $m=4k+2$ (there's a triangle with good sides, the base of which is the diagonal).

I have left out some more or less trivial observations, but I hope it's clear.

Z K Y

The post below has been deleted. Click to close.

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

785 posts

manuel

#7 h Jul 12, 2006, 11:40 PM • 5 Y

Y by Adventure10, jhu08, ImSh95, Mango247, cubres

prefect radio...
for odd $m$ , are there other configurations that produce maximum number of good triangles other than the one where each good triangle has two sides of the polygon?

Z K Y

The post below has been deleted. Click to close.

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

146 posts

Sathej

#8 h Jul 13, 2006, 4:31 AM • 4 Y

Y by jhu08, ImSh95, Adventure10, cubres

Hello Manuel,
I think that for odd n, there are no other configurations possible.Xixam, your solution looks to be on the right track.However,as you said, it requires some more fine-tuning.I have made reasonable progress on this problem using a different approach (similar to darktreb's lines of thinking).I'll post it when it is all ready. Anyway,I am out of station for a couple of days and I'll think over this and get back.By the way, I am not an IMO 2006 participant(Infact,I have never been to even a Regional Olympiad,now am in college).
Regards,
Sathej

Z K Y

The post below has been deleted. Click to close.

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

abbas_mehrabian

33 posts

abbas_mehrabian

#9 h Jul 14, 2006, 7:32 PM • 5 Y

Y by Adventure10, jhu08, ImSh95, Mango247, cubres

Perfect_radio, I think you've missed something!

You must also take care of the case where $m>1003$ and $m$ is odd, since in this case you can use the diagonal as a side of a good triangle.

Considering this case too, I think the sequence will be like this: $a_{m}= \frac{m}{2}$ if $m$ is even, otherwise $\frac{m-1}2$ if $m < 1003$ and $\frac{m+1}2$ if $m >1003$

Z K Y

The post below has been deleted. Click to close.

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

2607 posts

#10 h Jul 15, 2006, 1:21 PM • 4 Y

Y by Adventure10, jhu08, ImSh95, cubres

abbas_mehrabian, thank you for pointing out my slip-up. But the idea is good (hopefully), so I think it would have got me at least $3$ points.

The bad part about this solution is that it is very hard to write.

Z K Y

The post below has been deleted. Click to close.

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

26 posts

shunka

#11 h Jul 15, 2006, 3:51 PM • 6 Y

Y by JonathasDavid, Adventure10, jhu08, ImSh95, Mango247, cubres

I did not like the way the official solution handles the last part of the problem.

Here is a suggestion.

Once it is proved that the number of good trianlges "below" a diagonal of "size" n is at most n/2 one can continue as follows (size of a diagonal is the smaller of the two numbers of sides of the 2006-gon cut off by the diagonal)

Let T be a triangle of the triangulation that contains the center of the 2006-gon and let the "sizes" of diagonals used in T be a,b,c. If a,b,c are even then the number of good trianlges is at most (a+b+c)/2. If two of a,b and c are odd (say a and b), then the number of good triangles is at most 1+(a-1)/2+(b-1)/2 + c/2 = (a+b+c)/2 (here the +1 is for the triangle T that may be good). Done.

EDIT: Of course, note that a+b+c = 2006

Z K Y

The post below has been deleted. Click to close.

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

26 posts

shunka

#12 h Jul 15, 2006, 5:07 PM • 4 Y

Y by jhu08, ImSh95, Adventure10, cubres

Now when I read it, I am not sure I like the first part of the official solution of Problem 2 either.

Here is a suggestion.

Claim. The number of good triangles "below" a diagonal of size c is at most c/2.

Proof by strong induction. The value c=1 is clear. Let AB be a diagonal of size c, and let C be the point on the short side of the boundary ("below" the diagonal AB) such that ABC is a triangle in the partition. Let a and b be the sizes of the diagonals BC and AC, respectively (note that a+b=c). If ABC is not a good triangle then the number of good triangles "below" AB is at most a/2+b/2 = (a+b)/2 = c/2. If ABC is a good triangle then a and b must be odd (there is no diagonal "below" AB that is as long as AB). Thus in this case the number of good trianlges is at most 1+(a-1)/2 + (b-1)/2 = (a+b)/2 = c/2. Done.

Z K Y

The post below has been deleted. Click to close.

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

236 posts

#13 h Jul 16, 2006, 6:36 PM • 5 Y

Y by Adventure10, jhu08, ImSh95, cubres, and 1 other user

Suppose we divide the polygon in $2004$ triangles.

Consider a graph $G$ whose vertices are the $2004$ triangles. You connect two vertices iff the corresponding triangles share a non-good diagonal. Note that the degree of a given vertex is the number of its non-good sides.

So a good triangle (defined as a isosceles triangle with two good sides) must have degree $1$ .

Each vertex of $G$ must have degree $1$ or $3$ . To see that, consider a triangle $ABC$ . Let $a\pi/1003$ , $b\pi/1003$ and $c\pi/1003$ be respectively the measures of the arcs $BC$ , $CA$ and $AB$ that doesn't contain $A$ , $B$ and $C$ , respectively. $AB$ is a good side iff $c$ is odd. But $a+b+c = 2006$ , so the number of good sides of $ABC$ must be even, and thus the number of non-good sides is odd.

$G$ is acyclic, since it is the subgraph of the graph $H$ obtained connecting every pair of triangles sharing a side, which is certainly connected, has $2004$ vertices and $2003$ edges (the diagonals), and consequently is a tree.

So each connected component of $G$ is a tree itself, with all vertices having degree $1$ or $3$ . Let $n$ be the number of its vertices, $k$ of which with degree $1$ and $n-k$ with degree $3$ . Since it has $n-1$ edges, $k+3(n-k) = 2(n-1) \iff k = (n+2)/2$ . This proves also that $n$ is even. And note that if $G$ is connected then $n = 2004$ and there are $1003$ vertices of degree $1$ and consequently, at most $1003$ good triangles.

But $G$ is not necessarily connected. Let $G_{1}$ , $G_{2}$ , $\ldots$ , $G_{k}$ be its connected components. We consider two of these components $G_{i}$ and $G_{j}$ neighbours if there exists two vertices $v \in V(G_{i})$ and $w \in V(G_{j})$ that represents triangles sharing a good side. Now the graph ${\cal G}$ with vertices $G_{1}$ , $G_{2}$ , $\ldots$ , $G_{k}$ and edges connecting neighbours is also a tree and hence has $k-1$ edges. Note that the edges in $H$ connecting $G_{i}$ and $G_{j}$ must connect triangles with degree $1$ . But it's not so hard to see that at most one of two triangles that share a good side $a$ is good (just consider two triangles $ABC$ and $ABD$ with $AB$ good and draw a diagram - consider also that a good triangle must have two good sides). So, if $G_{i}$ has $n_{i}$ vertices, of the $(n_{1}+2)/2+(n_{2}+2)/2+\cdots+(n_{k}+2)/2 = (n_{1}+n_{2}+\cdots+n_{k})/2+k = 1002+k$ vertices with degree $1$ , $k-1$ don't yield good triangles, leaving at most $1002+k-(k-1) = 1003$ good triangles.

It's not hard to come up with an example with $1003$ good triangles: number the vertices counterclockwise from $1$ to $2006$ and draw the diagonals $2,4$ , $4,6$ , $\ldots$ , $2004,2006$ . Then draw the other diagonals at your will (but always obtaining $2004$ triangles in the end, mind you

).

Z K Y

The post below has been deleted. Click to close.

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

667 posts

#14 h Jul 17, 2006, 3:58 AM • 5 Y

Y by jhu08, ImSh95, Adventure10, Mango247, cubres

Who can help me?I'm confused!

if we consider regular-2n-gon
we draw the diagonals from one vertice to each other $n-3$ vertex .in this case ,every triangle is good ,isn't it ?
where is the mistake of my statement?I'm cofused.

EDIT:I know what is my mistake.

This post has been edited 1 time. Last edited by Hawk Tiger, Jul 19, 2006, 6:37 AM

Z K Y

The post below has been deleted. Click to close.

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

1160 posts

#15 h Jul 17, 2006, 2:16 PM • 5 Y

Y by Adventure10, jhu08, ImSh95, Mango247, cubres

In fact, my solution is really similar cyshyne:

Obviosly in contest time I would have done the typical one...

We draw a chord from the center of a triangle to the center of other if they share a good side, Also if a triangle has a side of the original 2006-agon, we conect it to a new vertex draw on the middle of its side... Then every vertex has degree 0 or 2, and there are 2006 vertex with degree 1 (those at the sides)

Now since this graph is a forest all trees must be simply strips, and every strip concist of two endpoints (which must be at the sides) and a set of triangles $T_{1},T_{2}...,T_{m}$ sucha that $T_{i}$ shares a side with $T_{i+1}$ and $T_{1}$ and $T_{n}$ have two original sides as sides.

Since endpoitns are different for each strip, we will be done If we prove that there is at most one isoceles triangle per strip... Look at the smallest isoceles good triangle, well it is clear that it is the only...lol

All this is inspired by the construction of the tree of the dissection which is a classical tool, only this time we focus on good sides...

So thats all, hope you like it...

Z K Y

The post below has been deleted. Click to close.

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

1312 posts

#16 h Apr 17, 2010, 10:12 AM • 5 Y

Y by jhu08, ImSh95, Adventure10, Mango247, cubres

ZetaX wrote:

Let $P$ be a regular $2006$ -gon. A diagonal is called good if its endpoints divide the boundary of $P$ into two parts, each composed of an odd number of sides of $P$ . The sides of $P$ are also called good.
Suppose $P$ has been dissected into triangles by $2003$ diagonals, no two of which have a common point in the interior of $P$ . Find the maximum number of isosceles triangles having two good sides that could appear in such a configuration.

Let $\rho(2n)$ be the maximal number of good triangles in a regular $2n$ -gon. A diagonal will split the $2n$ -gon in two parts with $x$ and $y$ sides such that $x+y = 2n$ . Let $\alpha(k)$ be the maximal number of triangles you can make when you have a "part" of the $2n$ -gon with $k$ sides that is "cut off": That is, there is a diagonal seperating this part from the rest.

It is now obvious that $\rho(2n) = \max_{x,y \ge 2, x+y = 2n} \{ \alpha(x) + \alpha(y) \}$
Now an algorithm to find an upper bound on $\alpha(k)$ when $k \le n$ . I'll prove that $\alpha(k) \le \lfloor \frac{k}{2} \rfloor$ :
Split the part with $k$ sides into two parts with $i$ and $k-i$ sides. Let $\beta(k,i)$ be $1$ when this forms a good triangle and $0$ otherwise.
Case $k$ is even: Then in order for $\beta(k,i) = 1$ $i$ must be odd. If $\beta(k,i) = 0$ then $\alpha(k) = \alpha(i) + \alpha(k-i) \le \lfloor \frac{i}{2} \rfloor + \lfloor \frac{k-i}{2} \rfloor \le \lfloor \frac{i+(k-i)}{2} \rfloor = \lfloor \frac{k}{2} \rfloor$ . If $\beta(k,i) = 1$ then $\alpha(k) = \alpha(i) + \alpha(k-i) + 1\le \frac{i-1}{2} + \frac{k-i-1}{2} + 1 = \frac{k}{2} = \lfloor \frac{k}{2} \rfloor$
Case $k$ is odd: Then since $k \le 2n-k$ we see that $\beta(k,i)$ and we find $\alpha(k) \le \lfloor \frac{k}{2} \rfloor$ as earlier.

Now I'll prove that $\alpha(k) \le \lfloor \frac{k+1}{2} \rfloor, 2 \le k \le 2n-2$ . Assume the opposite and let $m$ be the smallest value such that $\alpha(m) > \lfloor \frac{m+1}{2} \rfloor$ . Wlog assume that $m > n$ .
Case $m$ is odd: Then $\alpha(m) = \alpha(i) + \alpha(m-i) + \beta(m,i)$ . If $\beta(m,i) = 0$ we get a contradiction since $m$ was the smallest value. So $\beta(m,i) = 0$ which requires $i = 2n-m$ or $m-i = 2n-m$ . Wlog $i = 2n-m$ . Then $\alpha(2n-m) + \alpha(2m-2n) + 1$ . But $m > n \Rightarrow 2n-m < n$ , so $\alpha(2n-m) \le \frac{2n-m-1}{2}$ . And $m < 2n \Rightarrow 2m-2n < m$ , so $\alpha(2m-2n) \le m-n$ , by the assumption that $m$ was the smallest. So $\alpha(m) \le \frac{m+1}{2}$ . Contradiction.
Case $m$ is even: If $\beta(m,i) = 0$ then there is a trivial contradiction as earlier. So $\beta(m,i) = 1$ , and $\alpha(m) = \alpha ( \frac{m}{2} ) + \alpha ( \frac{m}{2} ) +1$ , where $\frac{m}{2}$ is odd. But $m < 2n \Rightarrow \frac{m}{2} < n$ , so $\alpha(m) \le 2 \frac{m-1}{2}+1 = m$ . And we have the contradiction.

From here it is trivial that $\rho(2n) \le n$ . An example which gives $\rho(2n)=n$ could be $n$ triangles with sidelengths $1,1$ .

Z K Y

The post below has been deleted. Click to close.

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

339 posts

leader

#17 h Apr 12, 2014, 4:02 PM • 5 Y

Y by jhu08, ImSh95, Adventure10, cubres, and 1 other user

Call a triangle super if it is in the configuration and it is iscosceles with 2 good sides.
Let $ABC$ be one super triangle with $AB=BC$ then $AB,BC$ are good sides. Now we will find the set $f(ABC)$ as follows:
Consider for each good diagonal $PQ$ that $g(PQ)$ is the vertex of he polygon such that $g(PQ)PQ$ is a triangle in the configuration( $g(PQ)$ is on the minor arc $PQ$ of the circumcircle $k$ of the polygon.

Now consider $g(AB)=P1$ then one of $P1A,P1B$ is good and WLOG let $P1A$ be good then $P2=g(P1A)$ now we continue the proccess finding $P3,P4,...,Pr$ where the algoritham will terminate when $PrP(r-1)$ is a side of the polygon. Now put $PrP(r-1)$ in $f(ABC)$ .
Next do the same procedure for side $BC$ .
Now lets prove that $PrP(r-1)$ is not in any other $f(S)$ where $P\not = ABC$ . First if we assume the contradictory than all vertices of such $S$ must be sume of the vertices from $A,B,P1,P2,P3,....,Pr$ .

if vertices of $S$ are $K,L,M$ with $A,K,L,M,B$ in that order on $k$ then $\angle KLM>\angle ALM>90$ so if $S$ is a super triangle we have that $KL=LM$ and $KL,LM$ are good sides. However only one of the sides of the polygon formed by $A,B,P1,P2,...,Pr$ is good that is not $AB$ there fore such $K,L,M$ don't exist.
This proves that $f(R)$ where $R$ is a super triangle are all distinct. This gives a maximum of $1003$ triangles which can be achieved with an easy example.

Z K Y

The post below has been deleted. Click to close.

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

NewAlbionAcademy

910 posts

NewAlbionAcademy

#18 h May 25, 2014, 12:53 AM • 5 Y

Y by jhu08, ImSh95, Adventure10, cubres, and 1 other user

Here is an inductive solution which should work.

Let a diagonal cut the $2006$ -gon into a $m+1$ -gon and $n+1$ -gon with $m+n=2006$ . Then the key is that if $m\le 1003$ , then that $m+1$ -gon can contain at most $\lfloor{\dfrac{m}{2}}$ good triangles and if $m > 1003$ , then that $m+1$ -gon can contain at most $\lfloor{\dfrac{m+1}{2}}$ good triangles (same for $n$ ).

This is easy by induction, and the rest follows easily.

Z K Y

The post below has been deleted. Click to close.

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

TheStrangeCharm

290 posts

TheStrangeCharm

#19 h May 30, 2014, 1:39 AM • 5 Y

Y by jhu08, ImSh95, Adventure10, Mango247, cubres

Strong induction solution that seems very simple:

*THIS IS INCORRECT BECAUSE THE POLYGON MAY NO LONGER BE REGULAR AFTER INDUCTION

solution

This post has been edited 4 times. Last edited by TheStrangeCharm, Feb 17, 2015, 3:10 PM

Z K Y

The post below has been deleted. Click to close.

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

366 posts

#20 h Jun 24, 2014, 8:50 PM • 6 Y

Y by Kayak, jhu08, ImSh95, Adventure10, Mango247, cubres

Call a diagonal "fine" if it is good and it is part of an isosceles triangle. (The fine diagonals come "in pairs"). Take the minor arc determined by a fine diagonal. Notice that it cannot be completely covered by other minor arcs determined by other fine diagonals, since these fine diagonals would come in pairs and so would constitute an even number of sides. Therefore, we can assign to each fine diagonal a side of the polygon that isn't contained in any other minor arc of a fine diagonal. Therefore there are at most 2006 fine diagonals, and so the answer is 1003.

Z K Y

The post below has been deleted. Click to close.

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

82 posts

#21 h Nov 17, 2014, 9:07 PM • 6 Y

Y by jhu08, ImSh95, Adventure10, Mango247, cubres, and 1 other user

We trivialy get that answer for $n=6$ is $3$ , and we now prove the problem by strong induction.Suposse that for every $n \equiv 2 \pmod 4$ and $n<2006$ the answer is $\frac{n}{2}$ . Call a triangle nice if it satysfies the conditions.Suposse that every nice triangle contains side of $P$ .We trivialy get that here the answer is $1003$ .Now, the other case:Observe any nice triangle made only from diagonals.Its diagonals divide $P$ into $P_1$ , $P_2$ , $P_3$ .Let $P_1$ and $P_2$ be $x+1-gons$ , and $x+1$ is even. $P_3$ has odd number of sides.Now we apply induction to $P_1$ and $P_2$ (we can do that because diagonals don't intersect each other) and get that the answer is $x+2$ .Now we need to find the maximal $x$ and that is obviously $1001$ so the answer is $1003$ .Note that here $x$ represents the number of sides that the diagonals cut off.

Z K Y

The post below has been deleted. Click to close.

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

1963 posts

ABCDE

#22 h Sep 28, 2016, 8:18 PM • 6 Y

Y by anser, jhu08, ImSh95, Adventure10, Mango247, cubres

We will show that the answer is $n$ for all regular $2n$ -gons $A_1A_2\ldots A_{2n}$ . For the construction, any triangulation with the diagonals $A_{2i}A_{2i+2}$ works (take all indices mod $2n$ ).

Now, we strong induct on $n$ . The result clearly holds for $n=2$ . Call a diagonal bad if it's not good, a triangle good if it is isosceles and has two sides, and the length of a diagonal the (smaller) number of sides between its two endpoints. Note that any good triangle has two good sides and one bad side. If there are no bad diagonals of length greater than 2, then the only possible good triangles are those that consist of three consecutive vertices, and we clearly have at most $n$ of those.

Otherwise, take a good diagonal $A_mA_{m+2k}$ , where $k<n$ . We claim that there are at most $k$ good triangles in any triangulation of $A_mA_{m+1}\ldots A_{m+2k}$ . Indeed, consider a regular $2k+2$ -gon $B_0B_1\ldots B_{2k}B_{2k+1}$ , and triangulate it such that $B_0B_{2k}$ is in the triangulation and $B_0B_1\ldots B_{2k}$ is triangulated in the same way as $A_mA_{m+1}\ldots A_{m+2k}$ . Note that triangle $A_{m+p}A_{m+q}A_{m+r}$ is good iff $B_pB_qB_r$ is good, so there are at most $k+1-1=k$ good triangles by induction, as desired. Taking a bad diagonal with length greater than 2 and applying this twice, we are done.

Z K Y

The post below has been deleted. Click to close.

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

Generic_Username

1088 posts

Generic_Username

#23 h Jan 2, 2017, 4:17 AM • 5 Y

Y by jhu08, ImSh95, Adventure10, Mango247, cubres

Hopefully this works?

We claim that the answer is $n$ for any regular $2n$ -gon.

Call a diagonal excellent if it divides the boundary of $P$ into a part composed of $2$ sides of $P.$ Define an opposite diagonal to a diagonal $A_iA_j$ be a diagonal with one of $\{A_i,A_j\}$ as a vertex with the same length as $A_iA_j.$

Clearly, a construction for $n$ is to simply take $n$ adjacent excellent edges and to arbitrarily triangulate the $n$ -gon formed in the middle. Now assume that a good edge exists. Evidently a good edge cannot serve as the base of an isosceles triangle because of symmetry reasons.

Let fan $A_iA_j$ be a subset of $P$ bounded by adjacent sides of $P$ and a single diagonal $A_iA_j$ such that $A_iA_{i+1}\cdots A_j$ are listed in clockwise order. Let the length of this fan be $j-i\mod n.$

Claim: Each fan with length $k$ can produce at most $\left\lfloor\dfrac{k}{2}\right\rfloor$ isosceles triangle with vertices solely from the vertices from the fan.

Proof: We use strong induction. Evidently this is true for $k=2,3.$ Now for any fan, since diagonals are nonintersecting in a triangulation, we can partition any fan $A_iA_j$ of length $>2$ into smaller fans. Let $i=k_0,j=k_{m+1},$ and the the fans be $A_iA_{k_1},A_{k_1}A_{k_2},\cdots, A_{k_m}A_j.$

Case 1: The index $x$ is such that $A_{k_{x}}A_{k_{x+1}},A_{k_{x+1}}A_{k_{x+2}}$ are opposite, good edges.

Firstly, if $A_{k_{x+2}}A_{k_{x+3}}$ is also an opposite, good edge of $A_{k_{x+1}}A_{k_{x+2}},$ at most one of $A_{k_{x}}A_{k_{x+1}}A_{k_{x+2}},A_{k_{x+1}}A_{k_{x+2}}A_{k_{x+3}}$ can form an isosceles triangle since diagonals are nonintersecting. Now the fans $A_{k_{x}}A_{k_{x+1}},A_{k_{x+1}}A_{k_{x+2}}$ can produce at most $\dfrac{k_{x+1}-k_{x}-1}{2}+\dfrac{k_{x+2}+k_{x+1}-1}{2}$ isosceles triangle by the induction hypothesis, using the fact that the lengths of these fans are odd. But we need to add the $1$ isosceles triangle formed by $A_{k_x}A_{k_{x+1}}A_{k_{x+2}}$ itself, so this produces at most $\dfrac{k_{x+2}-k_x}{2}$ isosceles triangles.

Case 2: The opposite of case 1. Then simply note that $\left\lfloor\dfrac{k_{x+1}-k_x}{2}\right\rfloor<\dfrac{k_{x+1}-k_{x}}{2}.$

Now summing all of the inequalities we get from cases 1 and 2, we may conclude.

The problem then directly follows from the claim, since $P$ itself is a fan.

Z K Y

The post below has been deleted. Click to close.

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

3223 posts

#24 h Apr 1, 2017, 3:12 PM • 4 Y

Y by jhu08, ImSh95, Adventure10, cubres

We will show that the maximum number of isosceles triangles with two good sides (call them good isosceles triangles) is $1003$ , and the construction is trivial.

Note that the two good sides in such an isosceles triangle must be equal. Now, on any semicircle consider $n$ points $P_1,P_2,...P_n$ in that order such that the distances $P_1P_2,P_2P_3,...P_{n-1}P_n$ are equal. The key insight is that regardless of how far apart the points actually are, two corresponding triangulatons will have good sides connecting the same pairs of vertices as $\sin$ is injective on $[0,0.5\pi]$ , so let $f(n)$ be the maximal number of isosceles triangles with two good sides in this configuration.

First we will prove $f(n) =\lfloor \dfrac{n-1}{2}\rfloor$ by strong induction on $n$ . The base cases $n=1,2,3,4$ can be checked easily.

Now, suppose first that $n$ is not three mod four, and suppose that when $P_1P_2...P_n$ is triangulated, side $P_1P_n$ is contained in triangle $P_1P_iP_n$ . Then since $n$ isn't three mod four, $P_1P_i,P_iP_n$ can't be equal and both subtend an odd number of sides, so $P_1P_iP_n$ isn't good. Then $P_1P_iP_n$ splits the $n$ -gon into two halves $P_1P_2...P_i, P_iP_{i+1}...P_n$ . Doing this for all $i$ , we can see that $f(n) = \text{max} (f(i) + f(n-i+1)) = \text{max} \left( \lfloor \dfrac{i-1}{2} \rfloor + \lfloor \dfrac{n-i}{2}\rfloor \right)$ . Since $\lfloor a\rfloor + \lfloor b \rfloor \le \lfloor a+b\rfloor$ , we easily get $f(n)\le \lfloor \dfrac{n-1}{2}\rfloor$ , and since $n\ge 5$ , we can achieve equality for odd $n$ by choosing $i$ odd, and we can achieve equality for even $n$ by any choice of $i$ . Next, suppose $n=4k+3$ , and we can do the same thing, except when $i=2k+2$ , $P_1P_iP_n$ is good, which adds one to our count. In other words, we have $f(n) = \text{max}_{1\le i\le 2k+1} (f(i)+f(n-i+1), 2f(2k+2)+1)$ , and it's easy to again show that $f(n) = \lfloor \dfrac{n-1}{2} \rfloor$ .

Now, the original problem is easy. Suppose that $O$ is the circumcenter of $P_1P_2...P_{2006}$ . If $O$ is not strictly inside any triangle of the triangulation, then some edge of the triangulation is a diameter which splits $\mathcal P$ into two sets of $1004$ points each, hence the number of good triangles is at most $2f(1004)=1002$ .

Otherwise, $O$ is within some triangle $P_iP_jP_k$ , where the vertices of the triangle subtend $a,b,c$ sides respectively with $a+b+c=2006$ , implying that they create groups of equally spaced vertices of size $a+1,b+1,c+1$ , each group within a common semicircle. Suppose $P_iP_jP_k$ isn't a good isosceles triangle, meaning that the number of good isosceles triangles is at most $f(a+1)+f(b+1)+f(c+1) = \lfloor \dfrac{a}{2} \rfloor + \lfloor \dfrac{b}{2}\rfloor + \lfloor \dfrac{c}{2}\rfloor \le \lfloor \dfrac{a+b+c}{2}\rfloor=1003$ . The other scenario is that $P_iP_jP_k$ is good, so $P_iP_jP_k$ splits the circle into arcs containing equally spaced vertices of length $a+1,a+1,b+1$ for $a$ odd. Then clearly the number of isosceles good triangle is at most $1 + 2f(a+1)+f(b+1)=1 + 2\lfloor \dfrac{a}{2} \rfloor + \lfloor \dfrac{b}{2} \rfloor = 1 + 2\lfloor \dfrac{a-1}{2} \rfloor + \lfloor \dfrac{b}{2} \rfloor \le 1 + \lfloor \dfrac{2a+b-2}{2}\rfloor=1003$ , so once again we're done.

This post has been edited 2 times. Last edited by tastymath75025, Aug 8, 2018, 10:10 PM

Z K Y

The post below has been deleted. Click to close.

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

1979 posts

#25 h Jul 14, 2017, 8:18 PM • 5 Y

Y by jhu08, ImSh95, Adventure10, Mango247, cubres

I think this works but I am not too sure. It'd be nice if someone can confirm or point out a flaw.

IMO 2006/2 wrote:

Let $P$ be a regular $2006$ -gon. A diagonal is called good if its endpoints divide the boundary of $P$ into two parts, each composed of an odd number of sides of $P$ . The sides of $P$ are also called good.
Suppose $P$ has been dissected into triangles by $2003$ diagonals, no two of which have a common point in the interior of $P$ . Find the maximum number of isosceles triangles having two good sides that could appear in such a configuration.

Answer: $\boxed{1003}$ .

For convenience, we shall replace the notion of "isosceles"; and thereafter the statement of the problem to arbitrary cyclic convex polygons.

For any $n$ -gon, call a side good if the minor arc it subtends has an even number of vertices. Call a triangle with vertices taken from this polygon as isosceles if both minor arcs made by it's legs have an equal number of vertices of the polygon. We show that the maximum number $f(n)$ of good isosceles triangles we can have in an $n$ -gon is $\boxed{f(n) \le \lfloor \tfrac{n}{2} \rfloor}$ for all $n \geqslant 3$ .

Proceed by strong induction; base cases are immediate to check. For any triangulation of an $n$ -gon, let $ABC$ be one good isosceles triangle with $AB=AC$ . Let arc $AB$ and $AC$ contain $c$ vertices and arc $BC$ contain $d$ vertices respectively. Let $d$ be the minimal possible.

Note that neither of sides $AB, AC$ can be the leg or base of any good isosceles triangle in this triangulation. Also, $BC$ cannot be a leg of any good isosceles triangle; it can be a base if and only if $n \equiv 0 \pmod{2}$ . Hence, we conclude that $f(n)=2\left \lfloor \tfrac{c}{2} \right \rfloor+\left \lfloor \tfrac{d+2}{2} \right \rfloor+1$ if $n$ is even and $f(n)=2\left \lfloor \tfrac{c}{2} \right \rfloor+\left \lfloor \tfrac{d}{2} \right \rfloor+1$ otherwise. In any case; as $n=2c+d+3$ we get $f(n) \le \left \lfloor \tfrac{n}{2} \right \rfloor$ for all $n \geqslant 3$ .

Hence, we cannot have more than $1003$ good isosceles triangles in the original problem. However, $1003$ such triangles are possible; consider diagonals joining alternate vertices and any arbitrary triangulation of the inner polygon they form. $\blacksquare$

This post has been edited 1 time. Last edited by anantmudgal09, Jul 14, 2017, 8:19 PM

Z K Y

The post below has been deleted. Click to close.

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

38 posts

Zawadx

#26 h Nov 27, 2018, 6:00 PM • 12 Y

Y by Kayak, Durjoy1729, mastermind.hk16, sunstar, InCtrl, jhu08, TFIRSTMGMEDALIST, ImSh95, Qingzhou_Xu, Adventure10, Mango247, cubres

A solution inspired by Sperner's Lemma.

Consider all the good sides to be doors. Starting at an isosceles triangle with two good sides (henceforth good triangles), we have two paths to choose from. These paths can't loop back and meet (without exiting the polygon), as then our loop would encircle the vertex of the good triangle, one of the vertices of the polygon itself! So each path from an isosceles triangle leads out of the polygon, passing through one of its sides. Also, since a triangle can have at most two good sides, the path can't branch. So each good triangle corresponds to exactly two sides where their paths lead out of the polygon. So we have at most $1003$ good triangles.

Z K Y

The post below has been deleted. Click to close.

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

386 posts

#28 h Aug 11, 2020, 1:14 PM • 3 Y

Y by jhu08, ImSh95, cubres

So obviously we are going to take the minimalistic approach here.

We say that a triangle is good if all his sides are good.

We denote with $A_1A_2A_3\dots A_{2004}A_{2005} A_{2006}$ the $2006$ -gon.
To achieve the maximum we are going to define the following action.

We say that a $2^k$ -disection of a regular $n$ -gon is taking that $n$ -gon and transfroming it into a regular $\left\lfloor\frac{n}{2^k}\right\rfloor$ -gon, with of course as many lines as we want, such that they don't intersect.

So we perform a $2$ -disection to a regular $2006$ -gon and we get a $1003$ -gon, but we won't indefinantly disect the $1003$ since we wouldn't have $2003$ diagonals.
So we now do the following, we shall claim by the following construction that the maximum is $1003$ .

Construction:
We shall connect all the diagonals $A_1A_{2k+1}$ , where $k \leq 1002$ , and we shall connect the diagonals $A_{2k+1}A_{2k+3}$ , where $k \leq 1001$ , hence the total sum is $2003$ .
By any other construction where we have more good triangles we have that the diagonal count is less than $2003$ .
Thus we have that the maximum is $1003$ triangles.

Z K Y

The post below has been deleted. Click to close.

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

480 posts

#29 h Aug 4, 2021, 5:57 PM • 4 Y

Y by jhu08, centslordm, ImSh95, cubres

I claim the maximum number of these triangles is $1003$ . In particular, I will prove the stronger claim that for any $2s$ -gon that is dissected by $2s-3$ diagonals, the maximum number of isosceles triangles with two good sides is $s$ .

The construction is to label all the vertices in clockwise order $v_1, v_2\ldots v_{2s}$ , and then we connect all pairs of vertices $v_{2i-1}$ and $v_{2i+1}$ where $v_{-1} = v_{2s-1}$ , and $v_{2s+1} = v_1$ . After that, we connect $v_1$ with all the remaining odd vertices which gives us $s$ good triangles.

First, define a "good" triangle to be an isosceles triangle with $2$ good sides and appears in this configuration.
Next, define a $x-y-z$ triangle with $x+y+z = 2s$ to be a triangle inside the hexagon such that the $3$ sides "contain" $x$ , $y$ , and $z$ sides of the hexagon. (see attachments)
Additionally, define a $n$ -arc to be $n$ consecutive sides of the $2n$ -gon with the leftmost and rightmost sides connected by a line. We will call this connecting line to be the "base". (see attachments)
Finally, let $f(n)$ to be the maximum number of good triangles in an $n$ -arc, and $g(x, y, z) = 1$ if $x+y+z = 2s$ and if an $x-y-z$ is a good triangle, and $0$ otherwise.

Claim: For positive integers $k \le s$ , $f(k) \le \left\lfloor\frac{k}{2}\right\rfloor$ .

Proof: I will use strong induction with base cases of $f(1) \le 0$ and $f(2), f(3) \le 1$ being trivial. For the inductive step, assume for all positive integers $k < n$ that $f(k)$ is the desired result, and I will prove for $f(n)$ .

First, notice that there must exist a triangle that contains the base of the $n$ -arc, and let it be an $x-y-(2s-n)$ triangle with $x+y = n$ (we use $2s-n$ because it is the opposite of the $n$ -arc). Notice that this dissects the $n-arc$ until a $x$ -arc, a $y$ -arc, and a $x-y-n$ triangle. Therefore, we have that $f(n) = \max\left(f(1)+f(n-1)+g(1, n-1, 2s-n), f(2)+f(n-2)+g(2, n-2, 2s-n)\ldots ,f\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+f\left(\left\lceil\frac{n}{2}\right\rceil\right)+g\left(\left\lfloor\frac{n}{2}\right\rfloor, \left\lceil\frac{n}{2}\right\rceil, 2s-n\right)\right).$ We have two cases:

Case 1: $n$ is even.

Notice that if $x+y = n$ , then they are either both odd or even. Therefore, if we let them be odd, we have $f(x)+f(y) \le \frac{x-1}{2}+\frac{y-1}{2} = \frac{x+y}{2}-1$ , while if $x$ and $y$ are even, we have $f(x)+f(y) \le \frac{x}{2}+\frac{y}{2} = \frac{x+y}{2}$ . However, $g(x, y, 2s-n)$ can only be $1$ if $x = y$ and they are both odd since $2s-n \ge n > x, y$ , so the maximum value $f(n)$ can achieve will just be $\max\left(\frac{x+y}{2}-1+1, \frac{x+y}{2}\right) = \frac{x+y}{2} = \left\lfloor\frac{n}{2}\right\rfloor$ .

Case 2: $n$ is odd.

Notice that one of $x$ or $y$ is odd and the other is even, so $x \ne y$ and $x, y \ne 2s-n$ , so $g(x, y, 2s-n) = 0$ for all possible $x+y = n$ . Additionally, WLOG $x$ is odd, we have $f(x)+f(y) \le \frac{x-1}{2}+\frac{y}{2} = \frac{x+y}{2}-\frac{1}{2} = \left\lfloor\frac{n}{2}\right\rfloor$ , so the maximum value of $f(n)$ in this case is also the floor of $\frac{n}{2}$ .

Therefore, the inductive step is proven and so is this claim. $\square$

Claim: For positive integers $k > s$ , $f(k) \le \left\lceil\frac{k}{2}\right\rceil$ .

Proof: Similarly to the last claim, I will prove by induction.

For the base case of $k = s+1$ , we again have that $f(k) = \max\left(f(1)+f(k-1)+g(1, k-1, 2s-k), \ldots ,f\left(\left\lfloor\frac{k}{2}\right\rfloor\right)+f\left(\left\lceil\frac{k}{2}\right\rceil\right)+g\left(\left\lfloor\frac{k}{2}\right\rfloor, \left\lceil\frac{k}{2}\right\rceil, 2s-k\right)\right).$ Notice that for any positive integers $x,y$ s.t. $x+y = k$ , $x, y \le s$ , so the following is identical to the previous proof as all $f(x) \le \left\lfloor\frac{x}{2}\right\rfloor$ , except for the case where $k$ is odd and we have the case where $y = 2s-k = s-1, x = 2$ , where we get $g(x, y, 2s-k) = 1, f(x) \le 1, f(y) \le \frac{s-2}{2}$ and they sum to $\frac{s}{2}+1 = \left\lceil\frac{k}{2}\right\rceil$ as desired.

For the inductive step, we will proceed similarly yet again and prove for $f(n)$ given everything smaller than it, and we split it into two cases.

Case 1: $n$ is even.

This has almost the exact same proof except we consider when WLOG $x < y, y > s, x+y = n$ , we have that $f(x)+f(y) \le \left\lfloor\frac{x}{2}\right\rfloor+\left\lceil\frac{y}{2}\right\rceil = \frac{x+y}{2} = \left\lceil\frac{n}{2}\right\rceil$ . However, $g(x, y, 2s-n) = 1$ iff $x = y = \frac{n}{2} \le s$ , so we have $f(n) \le \max\left(\left\lceil\frac{n}{2}\right\rceil, \left\lfloor\frac{n}{2}\right\rfloor-1+1, \left\lfloor\frac{n}{2}\right\rfloor\right) = \left\lceil\frac{n}{2}\right\rceil.$
Case 2: $n$ is odd.

Yet again, everything else is mostly the same except for when $x < y = 2s-n \le s$ , we have $f(x)+f(y)+g(x, y, 2s-n) \le \frac{x}{2}+\frac{y-1}{2}+1 = \frac{x+y}{2}+\frac{1}{2} = \left\lceil\frac{n}{2}\right\rceil$ . Additionally, if $x < s < y$ and $y$ is odd, we have $f(x)+f(y)+g(x, y, 2s-n) \le \frac{x}{2}+\frac{y+1}{2}+0 = \left\lceil\frac{n}{2}\right\rceil$ so $f(n) \le \max\left(\left\lceil\frac{n}{2}\right\rceil, \left\lfloor\frac{n}{2}\right\rfloor\right) = \left\lceil\frac{n}{2}\right\rceil.$
Therefore, the inductive step is proven and so is the claim. $\square$

Finally, notice that every dissection includes one that creates an $2s-2$ -arc, and thus creates a $1-1-2s-2$ triangle which is good. If we let $S_{2s}$ be the total number of good triangles in a $2s$ -gon, we have $S_{2s} = 1+f(2s-2) \le 1+\left\lceil\frac{2s-2}{2}\right\rceil = s$ . Because we proved $s$ is attainable and it is the maximum value, we see that for $2s = 2006$ , the maximum number of good triangles is $\frac{2006}{2} = 1003$ . $\blacksquare$

Remarks: A nice recursion problem that I probably made too tedious for myself as my solution is ridiculously long lol.

Attachments:

Z K Y

The post below has been deleted. Click to close.

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

579 posts

#30 h Aug 19, 2021, 3:31 AM • 3 Y

Y by centslordm, ImSh95, cubres

We claim the answer is $\frac{2006}{2}$ . This is clearly achievable by drawing the lines $0\to 2\to 4 \to \cdots$ . We now prove optimality.

Each good triangle has two sides of odd arc-length and one with even arc-length, and we denote a triangle's size as the odd arc-length. In order of increasing arc-length, mark one blank edge purple on each of the odd arcs. We now prove that this process is possible.

$\textbf{Claim: }$ At each step, the next good triangle $A$ has an even number of edges marked on each odd length arc.
$\textbf{Proof: }$ The only triangles that could've marked these two arcs are those entirely enclosed (since the ones that have marked are smaller than $A$ ). Since each triangle marks exactly two, there are clearly an even number of edges. $\blacksquare$ .

Since there are an even number of marked edges, and an odd number of choices, there is always at least one choice on each arc. Thus, at each step we can mark a new purple edge. At the end, there are at most 2016 purple edges, so there are at most $\frac{2006}{2}=1003$ good triangles and we are done. $\blacksquare$ .

Z K Y

The post below has been deleted. Click to close.

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

1446 posts

#31 h Feb 1, 2022, 11:58 PM • 4 Y

Y by pog, hakN, ImSh95, cubres

We claim the answer for a $2n$ -gon is $n$ . This makes the answer for the original problem $1003$ . This is clearly achievable. We use strong induction, with the base case $n=2$ being trivial. Suppose the statement is true for all $n<k$ , we prove it is true for $n=k$ .

Let $AB$ be a particular diagonal that isn't good (which clearly exists), and suppose that it breaks up the boundary of $P$ into segments with $2x$ and $2y$ sides, respectively, and breaks $P$ into two polygons with $2x+1$ and $2y+1$ sides.

Claim: If a polygon with $2x+1$ sides is one of the broken up polygons, it can be broken up into at most $x$ isosceles triangles with two good sides.
Proof. Consider the regular polygon with $2x+2$ sides that is drawn by taking the polygon with $2x+1$ sides, erecting a triangle on the outside of this polygon on the bad diagonal, and making it regular. Notice that any isosceles triangle with two good sides that appears in the original $2x+1$ -side polygon must appear in this polygon. By the induction hypothesis, there are at most $x+1$ such triangles in the $2x+2$ -gon. Moreover, the erected triangle in the $2x+2$ -gon is an isosceles triangle with two good sides that the $2x+1$ -gon doesn't have. This proves the claim. $\blacksquare$

Using the claim, the two broken-up polygons combined have at most $x+y=k$ isosceles triangles with two sides. This finishes the induction.

Z K Y

The post below has been deleted. Click to close.

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

awesomeming327.

1676 posts

awesomeming327.

#32 h Mar 9, 2022, 12:18 AM • 2 Y

Y by ImSh95, cubres

The feeling when your proof is so overkill it's like 5 pages

Suppose polygon $P$ was a regular $2n$ -gon, and we claim that the number of isosceles triangles with two good segments is at most $n.$ We proceed with strong induction.

Base Case: When $P$ is a square, the only possible triangulation is drawing the diagonal, which creates two isosceles triangles that have two good segments each.

Induction Hypothesis: Suppose the claim is true for all $n\le k-1.$

Induction Step: Given any triangulation, we assign a number to each segment, including the sides of the polygon. Sides will receive a number of one. For diagonals, the number they receive relates to the division of the boundary of the polygon by this diagonal. The boundary of the polygon will be divided into two parts, and the number of sides on the smaller part will be the number that this diagonal receives. We also call this number the value of that diagonal. Good segments have an odd value and non-good ones have an even value.

Draw any diagonal that is part of the triangulation. Suppose this diagonal's value is $a.$ This diagonal splits the boundary of the polygon into two parts. Suppose $a$ is odd. This implies that the polygon defined by the either part of the boundary and this diagonal has an even number of sides.

Start with any one of these smaller polygons, and let this polygon have $2b$ sides $F$ . Then we draw a new regular $2b$ -gon $G$ . If any diagonal of $F$ is good with respect to the $2k$ -gon then if we consider the portion of the divided boundary of the $2k$ -gon contained in $F,$ this has an odd number of sides in both the $2k$ -gon and $F,$ so it's good with respect to $F.$

Now, if we make a one-to-one correspondence from vertices of $F$ to vertices of $G$ is such a way that sides are preserved, then this one-to-one correspondence preserves goodness of segments, so looking at the criterion "triangles with two good segments as sides," we see that by the induction hypothesis, there are at most $b$ of them.

On the other hand, if we take the polygon defined by the other part of the boundary and this diagonal from the beginning, suppose we get a $2c$ -gon. The maximum number of isosceles triangles is $c.$ Now, we claim that for the smaller polygon out of the $2b$ -gon and the $2c$ -gon, which we WLOG assume is $F,$ there are at most $b-1$ isosceles triangles with two good segments.

We'll show that for a diagonal in this $2k$ -gon with value $r$ , the polygon $F$ defined by the smaller portion of the divided boundary of the $2k$ -gon and this diagonal has a maximum number of isosceles triangles with two good sides as $\lfloor{\frac{r}{2}}\rfloor$ .

Base Case: The claim is true when the value is one, since there's no triangle to consider and also true when the value is two, since there's only one triangle.

Induction Hypothesis: Suppose the claim is true for all $r\le s-1.$

Induction Step: Now let $r=s.$ Suppose $s$ is odd. Firstly, consider the longest segment of $F,$ also a diagonal of the $2k$ -gon. We can always inscribe this in a circle. In the circle, call the endpoints of this diagonal $A,B.$ All the other points are actually in the minor arc $AB$ of this circle, so $AB$ is longer than every diagonal in $F.$ In addition to the fact that the midpoint of arc $AB$ is not a vertex, due to there being an odd number of chords. This means $AB$ cannot be the side of any isosceles triangle.

However, it's unavoidable that $AB$ is a part of a triangle in the triangulation, so suppose $ABC$ is a triangle in the triangulation of $F.$ $AC$ and $AB$ are each diagonals in the $2k$ -gon, so by the induction hypothesis, the maximum number of isosceles triangles with two good sides is the arithmetic mean of the floors of the values of $AC$ and $AB.$ Since the sum of the values is odd, WLOG let $AC=2p+1$ and $AB=2q,$ and so the maximum number of isosceles triangles with two good sides is $p+q=\lfloor{\frac{2p+2q+1}{2}}\rfloor$ as desired.

Now suppose $s=2t$ is even. $AB$ can be a part of an isosceles triangle now. If $t$ is even, then the only isosceles triangle $AB$ can be a part of has two legs with value $t,$ which makes this isosceles triangle not have two good segments. Construct triangle $ABC$ again, and let $AC=p, AB=q.$ Then by the induction hypothesis, the maximum number of isosceles triangles with two good segments is simply $\lfloor{\frac{p}{2}}\rfloor+\lfloor{\frac{q}{2}}\rfloor\le \lfloor{\frac{p+q}{2}}\rfloor=\lfloor{\frac{s}{2}}\rfloor$ as desired.

If $t$ is odd, then again the only isosceles triangle $AB$ can be a part of has two legs with value $t.$ If this is true, then the triangle $ABC$ is itself an isosceles triangle with two good segments. However, let $AB=AC=t=2q+1.$ By the induction hypothesis, the maximum number of isosceles triangles with two good segments is $\lfloor{\frac{2q+1}{2}}\rfloor+\lfloor{\frac{2q+1}{2}}\rfloor+1=2q+1=\frac{s}{2}.$ If $ABC$ isn't isosceles the proof follows similarly to the one for when $t$ is even.

This concludes our proof that for a diagonal in this $2k$ -gon with value $r$ , the polygon $F$ defined by the smaller portion of the divided boundary of the $2k$ -gon and this diagonal has a maximum number of isosceles triangles with two good sides as $\lfloor{\frac{r}{2}}\rfloor$

We apply this back into our problem: it is indeed true that for the smaller polygon out of the $2b$ -gon and the $2c$ -gon, which we WLOG assume is $F,$ there are at most $b-1$ isosceles triangles with two good segments. The $2c$ -gon has at most $c$ isosceles triangles with two good segments, so there are in total at most $b-1+c$ of them. Note that $2b+2c$ counts every side in the $2k$ -gon and the diagonal twice, so $2b+2c=2k+2,$ or $b+c-1=k.$

Recall that we assumed $a,$ the value of the diagonal, which is also equal to $b,$ is odd. What if there aren't any good segments as diagonals? Then, the only isosceles triangles with two good segments must have two sides as sides of the $2k$ -gon, and each side of the $2k$ -gon can only belong to one triangle in the triangulation, so there are at most $k$ isosceles triangles with two good segments.

This concludes our proof that the number of isosceles triangles with two good segments is at most $n.$

We now give a construction for this number being equal to $n.$ Let our $2n$ -gon have vertices $A_1,A_2,\dots,A_{2n}.$ We connect $A_1A_3,A_3A_5,\dots,A_{2n-3}A_{2n-1},A_{2n-1}A_1$ and that alone creates our desired $n$ triangles. Therefore our answer is $1003.$

Z K Y

The post below has been deleted. Click to close.

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

5000 posts

#33 h May 3, 2022, 2:39 PM • 4 Y

Y by ImSh95, mijail, Mango247, cubres

The answer is $1003$ .
Refer to good diagonals as odd and non-good diagonals as even. Call an isosceles triangle with two odd sides desirable, and call a desirable triangle large if it contains the center of $P$ —clearly at most one such triangle exists—and note that no "half" of $P$ can contain the entirety of any large triangle. It can easily be seen that any desirable triangle must have both of its legs odd, and its base even.
To attain $1003$ , label the vertices $1,\ldots,2006$ in clockwise order and draw a diagonal between vertices $(1,3),(3,5),\ldots,(2005,1)$ , which forms $1003$ desirable triangles. Then triangulate the rest of the polygon arbitrarily, which can be easily seen to generate no more desirable triangles. We now prove that $1003$ is an upper bound.
For $k \leq 2006$ , define a $k$ -dome to be the shape formed from taking the convex hull of $k$ consecutive vertices of $P$ , and refer to the base of a $k$ -dome to be its "long edge"—its only edge that's not an edge of $P$ . We have the following key claim:

Claim: Let $D$ be a $k$ -dome. Then, any triangulation of $D$ which contains no large triangles contains at most $\lfloor k/2 \rfloor$ desirable triangles.
Proof: This is by strong induction on $k$ , with the degenerate base case of $k=1$ (just a line) being obvious. Now, for a some triangulation of the $k$ -dome $D$ , let $T$ be the triangle which contains its base as an edge. Then drawing in $T$ and nothing else partitions $D$ into $T$ , as well as an $a$ -dome and a $b$ -dome, both without large triangles, where $a+b=k$ and $a,b<k$ .

If $T$ is desirable and the base of $D$ is a leg of $T$ , then $k>1003$ , else the base of $D$ is its largest diagonal. But then $T$ contains the center of $P$ and is large, which is forbidden. As such, if $T$ is desirable, the base of $D$ must be the base of $T$ as well, so its legs are odd, hence $a$ and $b$ are both odd. In this case, by inductive hypothesis there are at most
$\lfloor a/2 \rfloor+\lfloor b/2 \rfloor+1=\lfloor (a+b)/2 \rfloor-1+1=\lfloor k/2 \rfloor$ desirable triangles in a triangulation of $D$ .
Otherwise, by inductive hypothesis there are simply at most
$\lfloor a/2 \rfloor+\lfloor b/2 \rfloor\leq \lfloor k/2 \rfloor$ desirable triangles in a triangulation of $D$ .

This proves the claim.

Now, consider any triangulation of $P$ , and take the following cases:

If the triangulation contains a large triangle $T$ , then drawing $T$ only splits $P$ into $T$ , two $a$ -domes, and a $b$ -dome, with $a$ odd, and $2a+b=2006$ . None of the domes can contain a large triangle, as at most one exists and it lies outside the domes by construction, hence there are at most
$\lfloor b/2 \rfloor+2\lfloor a/2 \rfloor+1=\lfloor (2a+b)/2 \rfloor-1+1=\lfloor 2006/2 \rfloor=1003$ desirable triangles in this triangulation.
If no large triangles are in this triangulation, then we simply apply our claim to $k=2006$ to conclude that at most $1003$ desirable triangles exist.

As such, there can be at most $1003$ desirable triangles in a triangulation of $P$ , so we're done. $\blacksquare$

This post has been edited 1 time. Last edited by IAmTheHazard, May 3, 2022, 2:43 PM

Z K Y

The post below has been deleted. Click to close.

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

107 posts

#34 h Jul 4, 2022, 3:06 PM • 1 Y

Y by cubres

The answer is $1003$ . Say that the regular polygon has vertices $A_1,A_2,\ldots,A_{2006}$ , and define a triangle to be valid if it is an isosceles triangle containing two good sides (i.e., it will be counted in the answer to the problem). Define a turtle shell of size $n$ to be a polygon with $n$ consecutive edges of the polygon; i.e., the polygon $A_iA_{i+1}\ldots A_{i+n}$ (indices taken $\mod{2006}$ ). To construct $1003$ , we take the triangles $A_1A_2A_3, A_3A_4A_5, \ldots, A_{2005}A_{2006}A_1$ and then take an arbitrary triangulation of the remaining $1003$ -gon. We now prove that this is maximal. Our first main idea is the following:
Claim: Let $f(n)$ be the maximal number of valid triangles in a triangulation of a turtle shell of size $n$ . Then, $f(n) = \left\lfloor{\frac{n}{2}}\right\rfloor$ , if $n \leq 1003$ .
Proof. We use strong induction. It is clear that $f(0) = f(1) = 0$ and $f(2) = 1$ . Now, assume that for all $i < k$ , $f(i) = \left\lfloor{\frac{i}{2}}\right\rfloor$ . We will show that $f(k) =\left\lfloor{\frac{k}{2}}\right\rfloor$ . Say that the given polygon has vertices $A_0, A_1, \ldots, A_k$ . There must exist a triangle that with vertices $A_0,A_k,$ and $A_j$ for some $0 < j < k$ . This triangle divides a turtle into two seperate turtles; in particular, this implies that the number of valid triangles is at most $f(j) + f(k-j) + 1$ if $A_0A_jA_k$ is valid and at most $f(j) + f(k-j)$ otherwise. In particular, we have: $f(k) \leq \max_{1 \leq j \leq k-1} \left(f(j) + f(k-j) + \begin{cases*} 1 & $A_0A_jA_k$ \textit{valid} \\ 0 & \text{otherwise} \end{cases*} \right)$ Furthermore, note that $A_0A_jA_k$ can only be valid if $j = k-j$ and $j$ is odd. Therefore, if $k \neq 2 \pmod{4}$ , then we have $f(k) \leq \max\limits_{1 \leq j \leq k-1} (f(j) + f(k-j))$ and it is not difficult to show that $f(k) \leq \left\lfloor{\frac{a}{2}}\right\rfloor$ in this case. If $k \equiv 2 \pmod{4}$ , the only special case we must consider is $j = \frac{k}{2}$ ; however, in this case, we have $f(k) = 2\left(\left\lfloor{\frac{k}{4}}\right\rfloor\right) + 1 = \frac{k}{2}$ which finishes (as the rest of the cases are similar to the case where $k \equiv 0 \pmod{4}$ ). $\blacksquare$
Now, we use our second key idea, which is to take a triangle that contains the center of the polygon (the center can be in the interior or on one of the sides). It is clear that this triangle divides the polygon into three turtle shells of size $\leq 1003$ , in which we can use our inductive claim. Furthermore, the sizes of these turtle shells sum to $2006$ ; let the sizes be $a,b,c$ . If all of $a,b,c$ is even, then the triangle cannot be valid by definition, so we have that the maximum number of valid triangles is bounded by $f(a) + f(b) + f(c) \leq \left\lfloor{\frac{a}{2}}\right\rfloor + \left\lfloor{\frac{b}{2}}\right\rfloor + \left\lfloor{\frac{c}{2}}\right\rfloor = \frac{a+b+c}{2} = 1003$ and similarly, if two of $a,b,c$ are odd, then the triangle may be valid, but the total number of valid triangles is bounded by $f(a) + f(b) + f(c) + 1 \leq \left\lfloor{\frac{a}{2}}\right\rfloor + \left\lfloor{\frac{b}{2}}\right\rfloor + \left\lfloor{\frac{c}{2}}\right\rfloor + 1 = \frac{a+b+c-2}{2}+1 = 1003$ so we have exhausted all cases (by considering parity) and we are done.

This post has been edited 1 time. Last edited by ETS1331, Jul 4, 2022, 3:06 PM

Z K Y

The post below has been deleted. Click to close.

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

7586 posts

#35 h Jul 24, 2022, 9:36 PM • 1 Y

Y by cubres

The answer is $1003$ , the construction being trivial (just take $1003$ of the smallest isosceles triangle). Ignore the rest of the diagonals; only the triangles which satisfy the condition matter. Then, for each triangle, color the regions which are adjacent to the same length sides red, and color the region adjacent to the base blue. Call a triangle large if it is not fully contained by any red region. Suppose that there are $n$ large triangles. The $2n$ red regions corresponding to these large triangles are all disjoint; let the size of a red region be the number of sides it is touching (a degenerate red region has size $1$ ). Then note that all the red regions are non-intersecting and also that the sum of their sizes is at most $2006$ . I claim that if a red region has size $2s+1$ , then it will be able to contain at most $s$ triangles. This will immediately imply the conclusion.

To see this, we use strong induction. Consider all $k$ large triangles (here, we alter the definition, so that large triangles can be contained by the largest red region). Clearly the sizes of the $2k$ regions they form is at most $2s+1$ . But now by induction they contain at most $\frac{2s+1}{2}-k$ triangles which means that the region itself contains at most $s$ triangles. The base case is trivial (a degenerate region), so we are done. $\blacksquare$

Note: I implicitly assumed that the size of a red region is at most $1003$ and odd, but this is always true.

This post has been edited 2 times. Last edited by asdf334, Jul 24, 2022, 9:46 PM

Z K Y

The post below has been deleted. Click to close.

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

109 posts

#36 h Jan 10, 2023, 9:02 PM • 4 Y

Y by Mango247, Mango247, Mango247, cubres

The answer is 1003. The construction is to pair up adjacent sides of $P$ , build an isosceles triangle for each pair (using the pair's two edges as two of the sides), and arbitrarily triangulate the 1003-gon that remains in the middle.

Consider a graph $G$ where each vertex is either a triangle of the dissection or an imaginary vertex representing the region immediately outside a particular side of $P$ , and the edges are good diagonals of the triangulation (linking the two vertices corresponding to the regions on each side of the good diagonal). Clearly each triangle vertex has degree 0 or 2, and each imaginary vertex has degree 1, so $G$ is a union of isolated vertices and path graphs. The isolated vertices correspond to triangles with no good side, so they cannot be part of the count. Excluding them, there are exactly 1003 path graphs forming $G$ , each beginning and ending at an imaginary vertex (since there are 2006 imaginary vertices total and each path has 2). Each path graph correspond to a chain of triangles, with adjacent triangles in the chain sharing a good diagonal as a side.

Claim: There is at most one good isosceles triangle in each chain.
Proof: Take the smallest good isosceles triangle $T$ (in terms of the length of the two equal sides) in the chain, and it is easy to see all other good isosceles triangles in the chain have to be strictly smaller since they must lie in one of the two regions formed by $P$ and the two equal sides of $T$ . $\square$

Since there are 1003 chains and each can contain up to one good isosceles triangle, there are at most 1003 good isosceles triangles, as desired.

This post has been edited 1 time. Last edited by SHZhang, Jan 27, 2023, 12:14 AM
Reason: grammar

Z K Y

The post below has been deleted. Click to close.

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

577 posts

#38 h Dec 26, 2023, 5:50 AM • 1 Y

Y by cubres

Construction: Take $1003$ pairs of disjoint consecutive sides of $P$ , and use them to form $1003$ good triangles.

Bound: Let there be $d$ good diagonals.

Consider a triangulation $\mathcal{T}$ of $P$ . Let $G$ be the graph on the triangles in $\mathcal{T}$ , where adjacency is determined by adjacency of triangles and all edges that correspond to pairs of triangles that share a good diagonal are deleted. Note that

$V(G)$ has size $2004$ ,
each vertex of $G$ has degree $1$ or $3$ , and
$G$ is a forest with $d+1$ connected components.

Claim: $T_i$ has $(|V(T_i)|+2)/2$ vertices of degree $1$ .
Proof. Trivial by handshake lemma.
:yoda:

:yoda:

Note that good triangles correspond to vertices with degree $1$ . The number of connected components that share an edge is $d$ . Thus the number of isosceles good triangles is at most $\left(\sum_{i=0}^d (|V(T_i)|+2)/2\right)-d = (2004+2(d+1))/2-d = 1003,$ as desired.

Z K Y

The post below has been deleted. Click to close.

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

44 posts

#39 h Aug 13, 2024, 11:30 AM • 1 Y

Y by cubres

Each good triangle has a two good sides, so if we can map every good side to a polygon side then we can conclude the maximum is $n$ which follows by construction linking vertex $A_{2k}$ to vertex $A_{2k+2}$ . A map gets properly defined using non-intersecting diagonals.
Comment : quite easy for a P2.

Z K Y

The post below has been deleted. Click to close.

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

517 posts

#40 h Feb 26, 2025, 5:35 AM • 1 Y

Y by cubres

We claim that $\boxed{1003}$ is the maximum. Let a triangle be "good" if and only if it is an isosceles triangle described in the problem statement. Note that these good triangles must have their two congruent sides being good.

First, we show by induction that triangulating a figure consisting of $k$ consecutive sides of some regular polygon can have at most at most $\left \lfloor \frac{k}{2} \right \rfloor$ such isosceles triangles. The base case, $k=3,$ is trivial so assume that the proposition holds for all $k \leq r$ where $r \geq 3$ is a positive integer. Then for $k=r+1,$ consider which vertices a vertice at one side of the figure connects to. Let $S$ be the set of the diagonals that connect them. Then clearly if some edge in $S$ creates a figure with an odd amount of edges (we only count the edges that are the side length of the original regular polygon), by the inductive hypothesis we lose at least $1/2$ from the floor. For a good triangle created from edges from $S$ to occur, we need at least $2$ of such sides described previously. This makes us lose at least $1$ from the floors. But, it is clear that at most one good triangle is created from edges from $S,$ so adding up the $1$ s cancel and we are done.

However, if edge in $S$ is not good, then there are no good triangles created from edges from $S,$ and it follows that we can sum the floors to get at most $\frac{r+1}{2} = \left \lfloor \frac{r+1}{2} \right \rfloor$ good triangles, as $r+1$ would be even. Thus the induction is complete.

Now, consider some triangulation that has a good triangle that does not use a side length of the polygon. Then this triangle disects the boundary of $P$ into three regions, some of them have odd side lengths. Say these regions have $a, a, b$ side lengths from the boundary, then from above there are at most $K=1+\left \lfloor \frac{a}{2} \right \rfloor+\left \lfloor \frac{a}{2} \right \rfloor+\left \lfloor \frac{b}{2} \right \rfloor$ good triangles. But, at least one of $a, b$ are odd. But $2a+b=2006$ so $a$ is odd, and it follows that $K = 1+2\cdot \left(\frac{a}{2}-\frac12 \right)+ \frac{b}{2} = \frac{2a+b}{2} = 1003.$ Hence the bound is proven.

Now, for the construction just create $1003$ triangles with two side lengths two consecutive side lengths of $P.$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a