Shri's Mid Level Mathematical Logic Problem

[shrig94]

Let P be a convex polygon with n sides, n >= 3\. Any set of n-3 diagonals of P that do not
intersect in the interior of the polygon determine a triangulation of P into n-2 triangles.
If P is regular and there is a triangulation of P consisting of only isosceles triangles, find
all the possible values of n.

[balliztik1]

To create an isosceles triangle, you need two sides of equal length and a base of any length. When triangulating a regular n-gon, you make (n - 2) triangles. These triangles will be isosceles only under two conditions:

-The triangle uses two sides of the polygon as legs, and the diagonal as a base.
-The triangle uses two diagonals as legs, and a side as a base.

The limit of isosceles triangulation, then, is such that the number of diagonals does not exceed more than half of n.

```
n / 2 >= (n - 3)
n >= 2n - 6
-n >= -6
n <= 6
```
Isosceles triangulation, then, only works for n = 4, 5, and 6.

…Except that's not true. Nvm this whole post.

[jna]

Homework?

[shrig94]

nah, competitive math fun.
@♪♫♪:

> To create an isosceles triangle, you need two sides of equal length and a base of any length. When triangulating a regular n-gon, you make (n - 2) triangles. These triangles will be isosceles only under two conditions:
>
> -The triangle uses two sides of the polygon as legs, and the diagonal as a base.
> -The triangle uses two diagonals as legs, and a side as a base.
>
> The limit of isosceles triangulation, then, is such that the number of diagonals does not exceed more than half of n.
>
> ```
> n / 2 >= (n - 3)
> n >= 2n - 6
> -n >= -6
> n <= 6
> ```
> Isosceles triangulation, then, only works for n = 4, 5, and 6.
>
> …Except that's not true. Nvm this whole post.

Its a proof.
I lol'ed.

[DrNova]

D) All of the above

[shrig94]

@DrNova:

> D) All of the above

For some reason I thought someone would say that, except with an E instead of D.

[DrNova]

E=None of the above, which is the wrong awnser

[shrig94]

Actually, none of the above posts had the correct answer, therefore, E is the correct answer.

I actually had to do this problem. It was an easy visualization, but it is hard to prove in such a way that you can get 10 marks.

[DrNova]

You lie.

[shrig94]

lolwut

Well, lets see, I know that any polygon has n-3 diagonals that do not touch (according to the proof).

Also, according to the proof, n-2 triangles should appear.

It is just a continuing pattern.

But it is hard to prove in words.


[balliztik1]

But you said isosceles. That third one isn't isosceles. Lemme draw something real quick.

And I think I can prove the numeric bits.

[](http://www.freemmorpgmaker.com/files/imagehost/#3e7b349a7183383d862eb90cb8ff13e7.png)

It works for many values. There are few where it doesn't work. If you have a shape of n-sides, draw diagonals as I have done, such that you skip only one vertex when creating it. If n is even, you create a shape of n / 2 in the center of the larger shape. If n is odd, you create a shape of (n + 1) / 2 in the center of the larger shape. If n is odd, the sides of that interior shape are not all equal. If it is even, then they are. Using recursion, you just whittle away at the number of remaining sides until you have just 3 left. There's just one "trap" in this recursive statement, that I've found: If n is odd, and (n + 1) / 2 is even, then isosceles triangulation is impossible.

Here's a little code I worked up to do it.

```
Private Sub Form_Load()
Dim x As Integer, n As Integer, bool As Boolean
For n = 4 To 10000
    x = n
    Do
        If x = 2 Or x = 3 Or x = 5 Then
            bool = True
            Exit Do
        End If
        If x  2 = x / 2 Then
            x = x / 2
        Else
            x = (x + 1) / 2
            If x  2 = x / 2 Then
                bool = False
                Exit Do
            End If
        End If
    Loop
    Text2.text = Text2.text + CStr(n) + " " + CStr(bool) + vbNewLine
Next
End Sub
```
http://www.freemmorpgmaker.com/files/imagehost/pics/ea7594f48c9c47ed32abba75d813da0f.txt

Text file of first 5563 (Textbox overloaded after that. xD)

As for why this works, it has been proven that the sum of the angles of an n-gon is (n - 2) * 180\. Since a triangle is 180 degrees, you would therefore have (n - 2) triangles within a given shape.

To prove the number of diagonals is simple. When you create a diagonal in the optimal way, you are skipping one vertex. What this leaves is an isosceles triangle, of course. That triangle's legs are the sides of the n-gon. The triangle's base, though, is on the interior. There's one less base than sides used forming the triangle, so you effectively get a new interior shape with (n - 1) sides. A triangle has 3 sides and no non-adjacent vertices. Therefore, 3 is the last value you can have. You effectively subtract 1 x times until you get to 3.

```
n - (1 * x) = 3
```
Reorganizing the equation, you get this:

```
n - 3 = 1 * x
n - 3 = x

```
X, the number of diagonals, must therefore be (n - 3).