Equal-area triangulations

The post below has been deleted. Click to close.

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

62861

3564 posts

62861

#1 h Jul 7, 2016, 11:12 PM • 4 Y

Y by anantmudgal09, DapperPeppermint, Adventure10, Mango247

A triangulation of a convex polygon $\Pi$ is a partitioning of $\Pi$ into triangles by diagonals having no common points other than the vertices of the polygon. We say that a triangulation is a Thaiangulation if all triangles in it have the same area.

Prove that any two different Thaiangulations of a convex polygon $\Pi$ differ by exactly two triangles. (In other words, prove that it is possible to replace one pair of triangles in the first Thaiangulation with a different pair of triangles so as to obtain the second Thaiangulation.)

Proposed by Bulgaria

This post has been edited 1 time. Last edited by 62861, Jul 20, 2016, 7:44 AM
Reason: added proposer

Z K Y

The post below has been deleted. Click to close.

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

cjquines0

510 posts

cjquines0

#2 h Jul 29, 2016, 5:19 PM • 1 Y

Y by Adventure10

For lack of a solution.

Official solution 1

This post has been edited 1 time. Last edited by cjquines0, Jul 29, 2016, 5:20 PM

Z K Y

The post below has been deleted. Click to close.

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

v_Enhance

6872 posts

v_Enhance

#3 h Mar 27, 2017, 12:52 AM • 8 Y

Y by tenplusten, Ankoganit, WizardMath, anantmudgal09, v4913, HamstPan38825, Adventure10, Mango247

Finally got around to solving this...

First, we prove the following ``chain lemma'' on the structure of Thai-angulations.

Lemma: In a Thai-angulation $\Pi$ every triangle uses at least one side of $\Pi$ . (Thus in any Thai-angulation the set of triangles forms a ``chain''.)

Proof. Assume for contradiction that some triangles $XYZ$ , $YAZ$ , $ZBX$ , $XCY$ are present in $\Pi$ , with $AZBXCY$ convex and all four triangles having the same area. By a suitable affine transformation we may assume $XYZ$ is equilateral.

$[asy] size(6cm); pair X = dir(90); pair Y = dir(210); pair Z = dir(330); pair A = 0.94*Y+1.06*Z-0.6*X; pair B = 1.05*Z+0.95*X-0.6*Y; pair C = 1.08*X+0.92*Y-0.6*Z; draw(X--Y--Z--cycle, blue); draw(A--B--C--cycle, heavygreen); draw(A--Z--B--X--C--Y--cycle, red); dot("$X$", X, dir(X)); dot("$Y$", Y, dir(Y)); dot("$Z$", Z, dir(Z)); dot("$A$", A, dir(A)); dot("$B$", B, dir(B)); dot("$C$", C, dir(C));[/asy]$

Now the distance from $A$ to $YZ$ equals the distance from $X$ to $YZ$ , from which it follows that $\angle BAC < \angle YAZ \le 60^{\circ}$ and similarly for the other three, but the sum of the degrees of $ABC$ is $180^{\circ}$ . $\blacksquare$

We define a convex polygon to be squishy if two of its sides are parallel and congruent; any two such sides will be called a good pair. We prove the following by induction on the number of sides $n$ of of the polygon $\Pi$ .

Claim: For any convex polygon $\Pi$ ,

If $\Pi$ is not squishy it has at most one Thai-angulation, and
If $\Pi$ is squishy then any two Thai-angulations differ by exactly two triangles, which are adjacent and use a good pair. In particular there are at most two Thai-angulations.

The base case $n=4$ is immediate so we now address the inductive step. This is divided into two halves, showing there exists a common diagonal, and then showing that this lets us induct downwards.

Lemma: If $\Pi$ has two distinct Thai-angulations $\mathcal T_1$ and $\mathcal T_2$ , and $n \ge 5$ , then there is a common diagonal $d$ .

Proof. Let $\Pi = P_1 P_2 \dots P_n$ . Since $n \ge 5 > 2+2$ , we can assume WLOG that $P_1$ has diagonals in both $\mathcal T_1$ and $\mathcal T_2$ (since by chain lemma each Thai-angulation has exactly two vertices without a diagonal). We claim that there must be a common diagonal at $P_1$ .

Assume for contradiction this is not the case. Let $P_1 P_i$ and $P_1 P_j$ be diagonals of $\mathcal T_1$ with $i$ minimal and $j$ maximal (possibly $i = j$ ). Define $P_1 P_k$ and $P_1 P_\ell$ analogously.

Then from $[P_1 P_2 P_i] = [P_1 P_2 P_k]$ we have $P_1 P_2 \parallel P_i P_k.$ Similarly $P_1 P_n \parallel P_j P_\ell.$
$[asy] size(6cm); pair P_2 = dir(220); pair P_1 = dir(270); pair P_n = dir(310); pair P_i = dir(140); pair P_j = dir(70); pair P_k = P_i+1.9*(P_1-P_2); pair P_l = P_j+2.4*(P_1-P_n); draw(P_1--P_2--P_k--cycle, red); draw(P_1--P_n--P_l--cycle, red); draw(P_1--P_2--P_i--cycle, blue); draw(P_1--P_n--P_j--cycle, heavygreen); draw(P_i--P_k, dashed+blue); draw(P_j--P_l, dashed+heavygreen); dot("$P_{\ell}$", P_l, dir(P_l)); dot("$P_2$", P_2, dir(P_2)); dot("$P_1$", P_1, dir(P_1)); dot("$P_n$", P_n, dir(P_n)); dot("$P_i$", P_i, dir(P_i)); dot("$P_j$", P_j, dir(P_j)); dot("$P_k$", P_k, dir(P_k)); [/asy]$

But then for convexity reasons the sides/diagonals $P_i P_j$ and $P_k P_\ell$ must intersect in the interior or boundary of $\Pi$ . So $i \le j \implies \ell \le k$ which is absurd. $\blacksquare$

We may now complete the induction, though the details require significant care. Suppose $\Pi$ has two Thai-angulations with common diagonal $d = AB$ , dividing $\Pi$ into $\Pi_1$ and $\Pi_2$ . The inductive hypothesis now implies that each $\Pi_k$ has at most two Thai-angulations. So to complete the inductive step we need the following.

Lemma: If $\Pi_k$ has two Thai-angulations differing by a pair of triangles, then $\Pi_k$ has a good pair not including $d$ .

Proof. Indeed suppose $ABCD$ is a parallelogram ( $CD$ being a side of $\Pi_k$ ), so that $\{CD, d\}$ is a good pair. In other words $\Pi_k$ has Thaingulations differing by the pairs $\{\triangle ACB, \triangle ACD\}$ and $\{\triangle BDA, \triangle BDC\}$ . Then by chain lemma on $\triangle ABC$ and $\triangle ABD$ , it follows that both $AD$ and $BC$ must also be sides of $\Pi_k$ , so $\{AD, BC\}$ is a good pair. $\blacksquare$

In particular, it's impossible for both $\Pi_1$ and $\Pi_2$ to have two Thai-angulations; indeed, for convexity reasons at most one of $\Pi_1$ and $\Pi_2$ has a good pair not containing $d$ . Thus all parts of the main claim follow, solving the problem.

Z K Y

The post below has been deleted. Click to close.

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

anantmudgal09

1979 posts

anantmudgal09

#4 h Nov 28, 2017, 9:10 PM • 1 Y

Y by Adventure10

CantonMathGuy wrote:

A triangulation of a convex polygon $\Pi$ is a partitioning of $\Pi$ into triangles by diagonals having no common points other than the vertices of the polygon. We say that a triangulation is a Thaiangulation if all triangles in it have the same area.

Prove that any two different Thaiangulations of a convex polygon $\Pi$ differ by exactly two triangles. (In other words, prove that it is possible to replace one pair of triangles in the first Thaiangulation with a different pair of triangles so as to obtain the second Thaiangulation.)

Proposed by Bulgaria

Does this work? If so, then I think the problem is quite simple.

Note that each triangulation has $n-2$ triangles, so each triangle in a Thaiangulation has the same area.

Lemma. Any triangle in a Thaiangulation shares a side with $\Pi$ .

(Proof) Suppose $ABC$ is a counter-example; pick vertices $X, Y, Z$ of $\Pi$ opposite to $A, B, C$ in sides $BC, CA, AB$ of $\triangle ABC$ with $[ABC]=[BCX]=[CAY]=[ABZ].$ Consider an affine transformation making $ABC$ equilateral. The convexity of $AZBXCY$ is preserved.

WLOG, $YZ=\max \{XY, YZ, ZX\}$ , then $\angle YXZ>60^{\circ}$ , but $\angle YXZ<\angle BCX<\angle BAC=60^{\circ}$ , hence the contradiction! $\blacksquare$

Lemma. No triangulation of $\Pi$ contains two parallelograms.

(Proof) Suppose $ABCD$ and $WXYZ$ are two such parallelograms. If they share a triangle, then it is easy to find three vertices among these eight that are collinear. So $AB, BC, CD, DA$ split $\Pi$ into four portions and $WXYZ$ lies entirely in one of them. Suppose that portion is cut off by $AD$ . Consequently, $ABCDWXYZ$ is a convex polygon in that order, so $180^{\circ}=\angle ZWX+\angle WZX=\angle DWX+\angle AZY-\angle DWZ-\angle AZW<360^{\circ}-\angle AZW-\angle DWZ$ so $\angle AZW+\angle DWZ<180^{\circ}$ but lines $AZ$ and $DW$ must meet on the same side of $AD$ as $X,Y$ ; hence we get a contradiction! $\blacksquare$

Lemma. Suppose $\triangle ABC, \triangle ACD$ belong to a Thaiangulation $\mathcal{T}$ of $\Pi$ and $AB, BC, CD$ are sides of $\Pi$ . Then for any other Thaiangulation $\mathcal{T}'$ of $\Pi$ , either they both belong to it, or $ABCD$ is a parallelogram and $\triangle BCD, \triangle ABD$ belong to it.

(Proof) Consider points $X, Y$ in $\Pi$ with $\triangle BCX, \triangle CDY \in \mathcal{T}'$ . Then $[BCX]=[ABC]$ so $AX \parallel BC$ . Also $[CAD]=[CDY]$ so $AY \parallel CD$ . Moreover, $[CDY]<[CDX]$ since $\triangle CDY$ and $\triangle BCX$ have no common interior points. However, it is easy to show $X, D$ lie on the same side of angle $YAB$ , a contradiction! $\blacksquare$

Now, we can delete these two triangles if they are common and proceed by induction. Otherwise, we can flip them, and again proceed by induction (this time not encountering a possible "flip" by lemma 2). In any case, the two Thaiangulations are either identical, or differ in exactly two places.

(It's hard to explain without pictures, oops.)

Strategies

Z K Y

The post below has been deleted. Click to close.

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

william122

1576 posts

william122

#5 h Aug 18, 2020, 1:59 AM • 1 Y

Y by Eliot

Solved with JNEW, brian6liu

The result is clear for $3,4$ vertices, so suppose $\Pi$ has $\ge 5$ vertices.

Claim: Every triangle in a Thaiangulation has a side of $\Pi$ .
Proof: Suppose otherwise. Then, we have a triangles $ABC$ , $BCX$ , $ACY$ , $ABZ$ with the same area in our Thaiangulation where the three latter triangles lie outside $ABC$ and $AZBXCY$ is a convex hexagon.

Take an affine transformation sending $ABC$ to an equilateral, and consider the lines $\ell_A,\ell_B,\ell_C$ which are homotheties of $BC,CA,AB$ w/ scale factor 2 wrt $A,B,C$ respectively. Also, consider $A',B',C'$ to be the reflections of $A,B,C$ over $BC,CA,AB$ . Now, directing lengths clockwise, consider the lengths of $XA',YB',ZC'$ . By convexity, line $XY$ intersects the triangle, so $XA'<YB'$ . Likewise, $YB'<ZC'<XA'$ , so $XA'<XA'$ , which is a contradiction, as desired.

Claim 2: If two Thaiangulations share a diagonal, then they differ by at most two triangles. Also, the difference in two triangles is formed by choosing a diagonal of a parallelogram in the Thaiangulation.
Proof: For both claims, we use strong induction on the number of vertices. $n=3,4$ are obvious. First, note that given a diagonal of a Thaiangulation, we can "build up" the Thaiangulation by iteratively choosing new vertices to draw diagonals to. More precisely, if our "current" diagonal is $A_iA_j$ , then the other triangle containing $A_iA_j$ is either $A_iA_{i+1}A_j$ or $A_iA_{j-1}A_j$ . We add whichever one has the correct area to our Thaiangulation, and continue this process until $\Pi$ is completely Thaiangulated.

If we are given a diagonal which splits $\Pi$ into two smaller polygons, each one can be individually Thaiangulated, by building up from the selected diagonal. First, the second claim follows immediately since $\Pi$ can admit two Thaiangulations iff one of the polygons has a parallelogram in its Thaiangulation, by induction. Also, note that the claim is clear by induction if one of the polygons can only be Thaiangulated one way, so it suffices to show we can't have a parallelogram in each section.

If there are two disjoint parallelograms, $A_iA_{i+1}A_{j-1}A_j$ and $A_xA_{x+1},A_yA_{y+1}$ , then either $\angle\widehat{A_iA_{i+1},A_xA_{x+1}}$ or $\angle\widehat{A_yA_{y+1},A_{j-1}A_j}$ will form a reflex angle, contradicting $\Pi$ 's convexity. So, when building the Thaiangulation, we have at most one parallelogram which induces at most a 2 triangle difference, and the claim is proven.

Now, it remains to show that any two Thaiangulations $S,T$ share a diagonal. In fact, we claim that any vertex part of a diagonal in both $S,T$ is part of such a common diagonal (such a vertex exists because $\Pi$ has at least $5$ vtxs). Let's call the common vertex $A_i$ .

When building up the Thaiangulation, the triangles which contain $A_i$ consist of: a triangle w/ side $A_{i-1}A_i$ , followed by a number of consecutive triangles w/ $A_i$ as an endpoint, followed by a triangle w/ side $A_iA_{i+1}$ . If we assume that $S,T$ do not intersect, then the two "consecutive parts" must be disjoint. Now, suppose that $S$ has triangles $A_{j_0}A_{i-1}A_i,A_{k_0}A_iA_{i+1}$ and $T$ has $A_{j_1}A_{i-1}A_i,A_{k_1}A_iA_{i+1}$ . Since the consecutive parts are disjoint, we have that $j_0\neq j_1$ , $k_0\neq k_1$ . So, as all 4 of these triangles have the same area, we must have $A_{j_0}A_{j_1}\parallel A_{i-1}A_i$ and $A_{k_0}A_{k_1}\parallel A_iA_{i+1}$ . However, $j_0<k_0$ , $j_1<k_1$ , so this scenario is impossible by the convexity of $\Pi$ .

Hence, $S,T$ must share a diagonal at $A_i$ , and we are done by our 2nd claim.

This post has been edited 1 time. Last edited by william122, Aug 18, 2020, 2:12 AM

Z K Y

The post below has been deleted. Click to close.

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

SnowPanda

186 posts

SnowPanda

#6 h Sep 16, 2020, 5:10 AM

Y by

Does this work?

Z K Y

The post below has been deleted. Click to close.

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

Idio-logy

206 posts

Idio-logy

#7 h Dec 26, 2020, 1:38 PM

Y by

Say a triangle is a thaiangle if it is a triangle in a Thaigulation of $\Pi$ . Throughout the solution, $[S]$ means the unsigned area of the polygon $S$ , and $\text{dist}(X,\ell)$ means the distance from point $X$ to line $\ell$ . We first prove two important lemmas.

Lemma 1
Lemma 2

The rest of the solution

This post has been edited 1 time. Last edited by Idio-logy, Dec 26, 2020, 4:03 PM
Reason: hide

Z K Y

The post below has been deleted. Click to close.

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

L567

1184 posts

L567

#8 h Oct 4, 2021, 5:26 AM

Y by

Not as difficult as I expected

We can in fact classify all convex polygons which have at least two Thaiangulations(They have exactly two in fact). They are the ones which are formed by taking a parallelogram and adding triangles with half its area onto it with the two Thaiangulations differing in which diagonal of the parallelogram is used. This obviously implies the problem.

Color the two triangulations red and blue. If there is a diagonal of both colors, then it essentially splits the polygon into two smaller ones and we will consider these. So assume for now that if the red and blue stuff have something in common, it must be a side of the polygon. This also means that every side of the polygon must be part of two different triangles, one red and one blue. Also assume the remaining polygon has at least $n \ge 4$ sides, because if not, then the whole polygon has only one Thaiangulation.

Let $x,y,z$ denote the number of triangles in the triangulation which share $0,1,2$ sides with the polygon respectively.

Claim 1: $x = 0$

Proof: Suppose not, then there is a triangle $ABC$ and points $D,E,F$ outside it such that $[ABC] = [BCD] = [ACE] = [ABF]$ . Instead define $F' = BF \cap CE$ and now an annoying and sad computation shows that $d(F', BC) \le d(A,BC)$ , and therefore $F$ cannot exist. (or, looking at other solutions here, be clever and do an affine transform

). $\square$

Now, for the main part.

Claim 2: $y = 0$

Proof: Suppose not and let $PAB$ be such a blue triangle containing side $AB$ and let $P'AB$ be the red triangle containing $AB$ . Since both have equal area, we have $AB || PP'$ . Since $AB$ is the only side it shares with the polygon, we may find a vertex $Q$ on the opposite side of $AP$ as of $P'$ . Now, let $N$ be the point such that $AQN$ is a blue triangle in the triangulation. We must have $N$ above $AQ$ since otherwise it intersects the previous triangle. But then the corresponding point $Q'$ must be such that $QQ' || AN$ , but this can be seen to be impossible since this would then intersect the red triangle $ABP'$ . $\square$

Now, we have there are a total of $n-2$ triangles, so $x+y+z = n-2$ and also counting by sides, we have $2z + y = n$ , since we have $x = y = 0$ , we get $n = 4$ , meaning $ABPP'$ is the whole remaining polygon and therefore, because areas are equal, it must be a parallelogram.

But it is not possible that $\Pi$ had more than one parallelogram because after fixing one, the other one must lie within the region created by its sides, but then this will cause the original parallelogram to lie outside the edges of the other. So, there is exactly one parallelogram, and $\Pi$ looks as we claimed and hence has exactly $2$ Thaiangulations, which differ by $2$ triangles, as desired. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

Inconsistent

1455 posts

Inconsistent

#9 h Aug 10, 2022, 3:06 AM • 1 Y

Y by Mango247

If you had put this on the combo shortlist by accident, I wouldn't even have been able to tell.

First of all, notice with four sides the polygon must be a parallelogram. Then notice there cannot be two parallelograms in the same figure, so if two Thaiangulations share a side we may induct down on the number of edges by splitting on the shared edge. Hence assume two Thaiangulations have distinct edge sets and the polygon has more than four sides. Take any vertex $X$ and take an affine transform sending $X$ to the origin so that its two adjacent vertices lie and the axes respectively, and so that the polygon lies entirely in the first quadrant. Now order the vertices excluding $X$ in increasing order of their argument with respect to the x-axis. Let the third vertex of the triangle containing the x-axis and the y-axis in the Thaiangulations be $A, B$ and $C, D$ respectively, such that when $s(P)$ denotes the sum of the coordinates of a point $P$ , $s(A) < s(B)$ and $s(C) < s(D)$ . We are guaranteed strictness since the Thaiangulations do not share edges. Next notice that $s$ is unimodal over the vertices of $\Pi$ in the argument order, and notice $AB$ is horizontal and $CD$ is vertical, so this implies $B$ occurs strictly before $A$ and $C$ occurs strictly before $D$ in argument since otherwise we can intersect vertices the segments $XA$ and $B-(1, 0)$ within the polygon, which is a violation of convexity.

Assume that $C \neq (1, 0)$ and $A \neq (0, 1)$ . Now, since either $(0, 1)-D$ or $(0, 1)-C$ cannot intersect $(1, 0)-A$ within the polygon since the diagonals of the Thaiangulation do not intersect, it follows that $A$ occurs at or before $D$ by convexity and similarly $B$ occurs at or before $C$ . Combining, we find that $B$ occurs before $A$ which occurs at or before $D$ , while $B$ occurs at or before $C$ which occurs before $D$ when travelling around the polygon counterclockwise. However by the unimodality of $s$ , the maximum of $s$ at or after $C$ and at or before $A$ . So $A$ occurs at or after $C$ , and the maximum of $s$ lies between them inclusive. however this implies $s(D) > s(C) \geq s(B)$ and $s(B) > s(A) \geq s(D)$ , which together is a contradiction.

Now WLOG $C = (1, 0)$ , then the area of every triangle is $\frac{1}{2}$ from the triangle $(0, 0)-(0, 1)-C$ , so $AB$ is $y = 1$ and $CD$ is $x = 1$ . It also follows that $A = (0, 1)$ from the Thaiangulation containing $(0, 0)-(0, 1)-C$ , since otherwise $(0, 0),A,D$ would be collinear.

It follows from this argument that the two adjacent edges of any vertex must be part of the same triangle in one of the two Thaiangulations. Hence, $BC$ are adjacent on the polygon and identically $AD$ are adjacent, and we have the condition $DC || AX, AB || XC$ , so applying the same result at $A, C$ locally, we have that $AX || BC$ so $B = D = (1, 1)$ , so there are no other vertices in the polygon and the polygon must be a square. Undoing any affine transforms, it implies the polygon must be a parallelogram, which does not have at least five vertices. Now simply undo the induction to finish.

This post has been edited 1 time. Last edited by Inconsistent, Aug 10, 2022, 3:08 AM
Reason: edit

Z K Y

The post below has been deleted. Click to close.

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

Eyed

1065 posts

Eyed

#10 h Nov 2, 2022, 12:58 AM

Y by

First writeup I've done in a while oops

Claim 1: Each triangle $ABC$ in a Thaiangulation shares at least one side with $\Pi$ .

Proof: Assume not; then there exists $X,Y,Z$ such that $[ZBC] = [YAC] = [XAB] = [ABC]$ , so $AZBXCY$ is convex. Affine transform $\triangle ABC$ to an equilateral triangle. Now, $\angle BZC + \angle AYC + \angle AXB \geq 180$ , so $AZBXCY$ can't be convex.

Consider side $AB$ of $\Pi$ , and assume two Thaiangulations have different triangles with side $AB$ . Let the first one contain $\triangle ABC$ and the second contain $\triangle ABD$ . Now, $AB || CD$ .

Claim: $AC$ is a side of $\Pi$ .

Proof: Assume not. Let $T\neq B$ such that $AT$ is a side. Now, let $X$ be the point in $\Pi$ such that $\triangle XAT$ is in the second Thaiangulation. Now, if the area of the triangle containing $AT$ in the first Thaiangulation was $K$ , then
$[XAT] = K \leq [ATC]$ This is impossible since $\angle TAB < 180$ , and $X$ lies on the opposite side of $CD$ as $AB$ .

Similarly, $BD$ is a side of $\Pi$ . Now, define $X, Y$ such that $\triangle YBD$ is part of the Thaiangulation containing $\triangle ABC$ and $\triangle XAC$ is part of the Thaiangulation containing $\triangle ABD$ . This means
$[ACX] = [ACB] = [BDA] = [BDY] \implies AC || BX, BD || AY.$ If $X\neq D, Y \neq C$ , then let $X', Y'$ be the points closer to $D,C$ respectively such that $XX'$ and $YY'$ are sides of $\Pi$ . Now, the second thaiangulation contains a triangle $\triangle XX'E$ with area equal to $[AXX']$ , so $AE || XX'$ . Since $BX || AC$ and $X'$ lies on the opposite side of $A$ wrt $BX$ , we have ray $X'X$ hits $AC$ . Thus, ray $X'X$ hits line $AB$ , or else no $E$ on $\Pi$ exists such that $AE || XX'$ .

Similarly, ray $Y'Y$ hits line $AB$ . This means that $\Pi$ isn't convex.

So now, either $X = D$ or $Y = C$ , wlog $X = D$ . Then, $AC || BD$ , so $Y \in AC \implies Y = C$ , and $ABDC$ is a parallelogram. Now, if these two thaiangulations differ at another place, it will form a new parallelogram $EFGH$ with the same area and $EF, GH$ as sides of $\Pi$ . This is however impossible by convexity.

Thus every two Thaiangulations differ by at most two triangles.

Z K Y

The post below has been deleted. Click to close.

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

YaoAOPS

1503 posts

YaoAOPS

#11 h Sep 26, 2023, 2:21 PM

Y by

Only g8 I will ever solve. :blush:

combigeo

This follows immediately for $n = 3$ . Now consider $n \ge 4$ .
Call a triangle having two edges as consecutive sides of the polygon a corner polygon. We now classify corner triangles.

Claim: Any triangle in a Thai-angulation has one edge on the side of the polygon.
Proof. Suppose such a triangle $T$ exists without any edge on the side of the polygon. Then the entire polygon has area at least four times of $T$ and lies within a larger triangle with $T$ as vertices on its side.
Take an affine transformation that maps $T$ to equilateral triangle $ABC$ . It remains to show that triangle $T'$ from scaling it by $4$ around $T$ contains at least one of the desired points, to get a contradiction.
Smooth until two of the edges of the larger triangle lie on $T'$ .
We can project the third point onto the third edge of the large triangle as $A$ and $B$ .
We then have a mobius transform that maps $A$ 's x coordinate to $B$ 's x coordinate. Checking three points, this implies that the third intersection point either lies inside or on $T'$ .
If the point inside, the result follows.
Furthermore, the point lies on with equality only holds when $A = B$ , which holds when the entire larger triangle is equilateral. In this case, the result follows as the polygon has less area than the triangle. $\blacksquare$

Claim: Any Thai-angulation has exactly two corner triangles for $n > 3$ sides.
Proof. Each of the $n$ sides lies on one of the $n - 2$ triangles in the triangulation, and no triangle has $3$ such sides.
There must be two such triangles as a result. $\blacksquare$
Now, FTSOC suppose that $\Pi$ has two Thai-angulations that don't differ by exactly two triangles.
We first prove something about the triangles in these two Thai-angulations.

Claim: A convex polygon can not have two non-intersecting parallelograms.
Proof. Follows by convexity and considering rotations. $\blacksquare$

Claim: All triangles in those two Thai-angulations must be distinct.
Proof. We prove this inductively on the number of vertices.
Suppose not. Then this common triangle divides the polygon into two remaining parts. One of them doesn't have a parallelogram and has exactly one Thai-angulation, the other has only two Thai-angulations.
However, it follows inductively that those two other Thai-angulations differ by exactly two pairs of triangles, contradiction. $\blacksquare$
Now we get a contradiction.

Claim: $\Pi$ must have four sides.
Proof. For a triangle in a Thai-angulation, define its sliding(s) as the one or two polygons that result in fixing the edge(s) on $\Pi$ and sliding the other vertex parallel until meeting another vertex.
Thus, it follows since all triangles are distinct that the slidings of a triangle in one Thai-angulation appear in the other Thai-angulation.
FTSOC suppose that $n > 4$ . Since each thai-angulation has at most $2$ corner triangles, we can choose two consecutive edges such that they are never part of a corner triangle.
Then consider the two triangles containing these two edges in one Thai-angulation. The vertices of one of the triangle must all occur before the other vertices when reading vertices counterclockwise.
However, then the operation of sliding breaks this ordering of the vertices, implying that the triangles intersect, contradiction. $\blacksquare$

This post has been edited 3 times. Last edited by YaoAOPS, Sep 26, 2023, 4:20 PM

Z K Y

The post below has been deleted. Click to close.

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

Leo.Euler

577 posts

Leo.Euler

#13 h Oct 7, 2023, 6:21 AM

Y by

Claim: In any Thai-angulation of $\Pi$ , each triangle must share a side with $\Pi$ .
Proof. Assume not. Then, there exists a convex hexagon $AYCXBZ$ whose vertices are a subset of $V(\Pi)$ such that $[XYZ] = [AYZ] = [BXZ] = [CXY].$ Take an affine transformation such that the image of $XYZ$ is equilateral. Note that $A$ and $X$ have equal distance from $YZ$ , from which it follows that $\angle A \le 60^{\circ}$ , and analogous bounds hold for $\angle B$ and $\angle C$ . Thus, $\angle A + \angle B + \angle C \le 180^{\circ}$ , which contradicts the convexity of $AYCXBZ$ .
:yoda:

Claim: In any Thai-angulation of $\Pi$ , each triangle shares exactly two sides with $\Pi$ .
Proof. Assume for contradiction that a triangle $ABC$ in the first Thai-angulation with $AB$ the only side common to $\Pi$ . Note that the second Thai-angulation contains $\triangle ABC'$ of the same area, and thus $\overline{AB} \parallel \overline{CC'}$ . Now let $P$ be a vertex on the opposite side of $\overline{AC}$ as $C'$ . Consider triangle $APX$ in the first Thai-angulation. Then there similarly exists triangle $APX'$ in the second Thai-angulation with $\overline{AP} \parallel \overline{XX'}$ . Now greedily make sure that none of the constructed triangles overlap, which results in a contradiction.
:yoda:

Let $a$ denote the number of triangles in a Thai-angulation of $\Pi$ , and let $\Pi$ have $n$ vertices. Counting the number of triangles, we have $a=n-2$ , and counting the number of sides, we have $2a=n$ , thus $n=4$ . Recycling the argument in the prior claim, we have that $\Pi$ is a quadrilateral with at least one pair of parallel sides, and by the area condition it must be a parallelogram. Hence consider the (exactly!) two Thai-angulations of $\Pi$ , and note that they differ by exactly two triangles, as desired.
:starwars:

Z K Y

The post below has been deleted. Click to close.

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

awesomehuman

496 posts

awesomehuman

#14 h Jul 29, 2024, 7:43 PM

Y by

Claim:
Every triangle in a Thaiangulation of $\Pi$ shares an edge with $\Pi$ .

Proof:
Let $\Pi=A_0\dots A_n$ .
Assume toward a contradiction $\triangle A_iA_jA_k$ is a triangle in the Thaiangulation that doesn't share an edge with $\Pi$ . Then, there are points $I$ , $J$ , $K$ such that $A_i\in JK$ , $A_j\in KI$ , $A_K\in IJ$ and $\Pi\setminus {A_i, A_j, A_k}$ is strictly bounded by $IJK$ . Each of $IA_jA_k$ , $JA_kA_i$ , and $KA_iA_j$ contains a triangle in the Thaiangulation.
It suffices to show
$\min([IA_jA_k], [JA_kA_i], [KA_iA_j])\le [A_iA_jA_k].$ Take an affine transformation such that $A_iA_jA_k$ is equilateral. WLOG assume $\angle A_jIA_k\ge60^\circ$ . Then, $[IA_jA_k]\le [A_iA_jA_k]$ as desired.

Claim:
Let $\Pi$ have adjacent vertices $A$ and $B$ . Let $\ell_A$ and $\ell_B$ be parallel lines through $A$ and $B$ , respectively. If $\Pi\setminus \{A, B\}$ is strictly between $\ell_A$ and $\ell_B$ , then $\Pi$ has at most $1$ Thaiangulation.

Proof:
Let $\Pi = AP_1P_2\dots P_nB$ . We will prove the claim by induction on $n$ . The base case $n=1$ is obvious.

Let $\mathcal{T}$ be a Thaiangulation of $\Pi$ . Let $\delta$ be the triangle in the Thaiangulation that has edge $AB$ . Take an affine transformation so that $\ell_A,\ell_B\perp AB$ . Reflect $P_1$ over $AB$ to get $X$ . Let $\mathcal{T}'=T\cup\{\triangle ABX\}$ .

Then, every triangle in $\mathcal{T}'$ shares an edge with $XAP_1P_2\dots P_nB$ . So, the third point of $\delta$ is $P_1$ or $P_n$ . WLOG assume it is $P_1$ .

Assume toward a contradiction $P_1P_n\parallel AB$ . We have
$[BP_nP_{n-1}]<[BP_nP_{n-2}]<\dots<[BP_nP_1]<[BP_nA]=[BP_1A]=[\delta].$ Therefore, the triangle with edge $BP_n$ has lower area than $\delta$ , a contradiction.

So, $P_1P_n\not\parallel AB$ , so $[ABP_n]\neq [\delta]$ . Therefore, every Thaiangulation of $\Pi$ contains $\delta$ . By induction, there is is at most $1$ Thaiangulation $\mathcal{S}$ of $P_1P_2\dots P_nB$ . So, the only Thaiangulation of $\Pi$ is $\mathcal{S}\cup\{\delta\}$ .

Assume toward a contradiction that $\Pi=A_0\dots A_{n-1}$ (indices are taken modulo $n$ and the vertices appear in counterclockwise order) has two Thaiangulations $\mathcal{S}$ and $\mathcal{T}$ that differ by more than $2$ triangles. Assume $n$ is minimal.

Claim:
No diagonal appears in $\mathcal{S}$ and $\mathcal{T}$ .

Proof:
Assume toward a contradiction some diagonal $A_iA_j$ appears in both $\mathcal{S}$ and $\mathcal{T}$ . Either $\Pi_1=A_iA_{i+1}\dots A_j$ or $\Pi_2=A_jA_{j+1}\dots A_i$ is bounded by two parallel lines through $A_i$ and $A_j$ . Assume WLOG $\Pi_1$ is bounded by parallel lines $\ell_i$ and $\ell_j$ through $A_i$ and $A_j$ respectively. Then, $\Pi_1$ has at most $1$ Thaiangulation. Therefore, $\Pi_1$ has the same trianngles in $\mathcal{S}$ and $\mathcal{T}$ . So, $\Pi_2$ has two Thaiangulations that differ by more than $2$ triangles, which contradicts $n$ being minimal.

Claim:
Every triangle $\triangle A_{i-1}A_iA_{i+1}$ is in $\mathcal{S}$ or $\mathcal{T}$ .

Proof:
Assume toward a contradiction that some triangle of this form doesn't appear in $\mathcal{S}$ or $\mathcal{T}$ . WLOG assume that triangle is $A_{n-1}A_0A_1$ . Let $1<x_S,y_S<n-1$ be the integers such that
$\triangle A_{n-1}A_0A_{x_S},\triangle A_0A_{1}A_{y_S}\in \mathcal{S}.$ Define $x_T, y_T$ similarly. Because the triangles don't cross, $x_S>y_S$ and $x_T>y_T$ . Therefore, $A_{x_S}A_{x_T}\parallel A_{n-1}A_0$ and $A_{y_S}A_{y_T}\parallel A_0A_1$ even though $A_{n-1}A_0$ , $A_0A_1$ , $A_{y_S}A_{y_T}$ , and $A_{x_S}A_{x_T}$ appear counterclockwise in that order, which is impossible.

There are $n$ triangles of the form $\triangle A_{i-1}A_iA_{i+1}$ . Because every triangle in a Thaiangulation shares an edge with the polygon, each of $\mathcal{S}$ and $\mathcal{T}$ has two triangles of this form. So, $\mathcal{S}$ and $\mathcal{T}$ cover at most $4$ triangles of that form. Therefore, $n\le 4$ , which implies the problem statement.

Z K Y