Prove that for every positive integer $n$ there exists a (not necessarily convex) polygon with no three collinear vertices, which admits exactly $n$ diffferent triangulations. (A triangulation is a dissection of the polygon into triangles by interior diagonals which have no common interior points with each other nor with the sides of the polygon)
Problem
Source: RMM 2019 P4
Tags: combinatorial geometry, combinatorics
24.02.2019 15:03
Funny problem. I think the following is self-explanatory
An explicit construction is below
27.02.2019 06:08
03.03.2019 22:19
Thinking inductively motivated this construction:
20.06.2020 09:56
Proposed by Morteza Saghafian, Iran
30.03.2022 15:44
Do it inductively, for $n = 1$, take a triangle and for $n = 2$, take a square, and label one of the vertices as the "corner" and build upon this. Suppose the polygon so far is $A_1A_2A_3 \cdots A_{n+2}$ with $n$ triangulations, index it such that $A_1$ is the corner and label the vertices clockwise. Pick a point $A_{n+3}$ in between the rays $A_nA_{n+1}$ and $A_1A_{n+1}$, I claim this has $n+1$ triangulations. To see this, the triangle containing $A_{n+1}A_{n+3}$ can have the other vertex only as $A_1$ or $A_{n+2}$, because of how the polygon was constructed. If it's $A_{n+2}$, then by induction, there are $n$ ways to triangulate the remaining thing and if its $A_1$, then there is a unique triangulation, so a total of $n+1$ triangulations for the new polygon. $\blacksquare$
08.04.2024 20:36
We prove this inductively for $N \ge 2$. Take a base case of a diamond $AB_1B_2C$, which satisfies $N = 2$. Then for each successive case, we append a triangle on $B_iB_{i+1}$ to get $SB_{i+1}B_{i+2}$ where $SB_{i+1}, SB_{i+2}$ are rays that only cover $A$. We also guarentee that $SB_{i+2}$ is convex with respect to earlier sides and $S, B_{i+2}, B_i$ are collinear. Then rename $S$ to $B_{i+1}$ and delete the old $B_{i+1}$. This guarentees that either $B_{i+2}$ is connected to $A$, in which case by convexity there's exactly one way to do it. Else, $B_{i+1}$ is connected to $B_i$ so there's inductively $N + 1$ ways.