Math Challenge by QuantumQuest #3

[Greg Bernhardt]

Submitted and judged by: @QuantumQuest
Solution credit awarded to: @ddddd28

RULES:
1) In order for a solution to count, a full derivation or proof must be given. Answers with no proof will be ignored.
2) It is fine to use nontrivial results without proof as long as you cite them and as long as it is "common knowledge to all mathematicians". Whether the latter is satisfied will be decided on a case-by-case basis.
3) If you have seen the problem before and remember the solution, you cannot participate in the solution to that problem.
4) You are allowed to use google, wolframalpha or any other resource. However, you are not allowed to search the question directly. So if the question was to solve an integral, you are allowed to obtain numerical answers from software, you are allowed to search for useful integration techniques, but you cannot type in the integral in wolframalpha to see its solution.

CHALLENGE:
Note: This is a "B" level challenge. We ask that advanced members make use of spoiler tags and allow for less experience members an opportunity to solve. Thanks!

Three different vertices are chosen randomly from the set of vertices of a regular polygon having $2n + 1$ sides. Assume that all choices have equal probability. What is the probability that the center of polygon lies in the interior of the triangle that is formed from the three randomly chosen vertices?

 

[ddddd28]

The probability that the center of polygon lies in the interior of the triangle that is formed from the three randomly chosen vertices is n+1/ 4n-2. (2n+1 is the number of the vertices.)
In order to evaluate the probability, I found how many options of triangles there are and how many triangles don't satisfy the requirements.
To make explanations easier I will base on this sketch:

please notice: the 0 point will be always on the horizontal axis, and the center in 0,0
To figure out how many triangles can be created, one has to understand that the quantity is equal to the number of combinations of 3 vertices that are ordered by size (with no repetitions)
for instance: (0,1,2) is ok but (4,3,5) and (3,3,5) are not.
Let's show all the possible combinations in a pentagon:
0 1 2
0 1 3
0 1 4 6 0's
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4 3 1's
1 3 4
2 3 4 1 2's
-------------
10 triangles
If we do the same to some other polygons, we will discover a very nice sequence:
0's 1's 2's 3's 4's...
1 3 sides
3 1 4 sides
6 3 1 5 sides
10 6 3 1 6 sides
15 10 6 3 1
21 21 10 6 3 1
Maybe, you recognize the sequence:
Triangular numbers
According to wikipedia the summation of n triangular numbers is n(n+1)(n+2)/6
but, as you can see for n sides, there are only n-2 triangular numbers so the formula becomes: n(n-1)(n-2)/6, and since there are 2n+1 sides, so it becomes n(2n+1)(2n-1)/3
----------------------------------------
Let's find the number of triangles that don't satisfy the conditions:
Since there is a symmetry( a line from each point 0, 1, 2, 3, 4), it is enough to find how many triangles don't cross the symmetry axis (and therefore the center is not in the triangle). In this example triangle (0,1,2) is above the symmetry line 0' and the only triangle that the center is not inside it.
How many triangles do we have like (0,1,2)? just as much as the amount of symmetry lines (5).
More generally, if there are 2n+1 sides, the symmetry line 0' passes through "n+0.5" point. The closiest point to "n+0.5" is n, of course, or 2 in the pentagon. The question is how many triangles are there in the general situation?
Let's look:
The first point must be 0. The next one could be one of these: n, n-1, n-2, ... ,2, 1
If we choose point 1, so there are left n-1 points bigger than 1 to select. 2 - n-2 3- n-3 ... for n there is no point.
Thus, we get: n-1 +n-2 + n-3 + ... +1 options for triangles, or put it another way: (1+(n-1))(n-1)/2 = n(n-1)/2 since there are 2n+1 symmetry axis, we obtain:
n(n-1)(2n+1)/2
Putting it together
p=1- (n(n-1)(2n+1)/2)/(n(2n+1)(2n-1)/3)= 1- 1.5(n-1)/(2n-1)= n+1/ 4n-2

 

[Buffu]

This is a "B" level challenge

Can we have a 'C' level challenge, this is too hard for me ?

 

[QuantumQuest]

@ddddd28

You follow a "brute force" logic beginning from a certain polygon and then try to generalize for other types of polygons, taking all the possible combinations for the three vertices. While you can solve it this way and it is absolutely acceptable, I need some explanations: what is this

0 1 4 6 0's

or this

1 2 4 3 1's

etc.

Also it is somewhat hard for me to follow the generalization

If we do the same to some other polygons, we will discover a very nice sequence:
0's 1's 2's 3's 4's...
1 3 sides
3 1 4 sides
6 3 1 5 sides
10 6 3 1 6 sides
15 10 6 3 1
21 21 10 6 3 1

I can see the way you're trying to tackle it but I think that you must do some corrections to the sketch and also describe somewhat more clearly the generalization to other polygons.

 

[ddddd28]

0 1 4 6 0's
This means that there are 6 combinations of 3 vertices which begin with zero.
I tried to to find the overall amount of combinations in each polygon, by understanding how many combinations starting with a specific number are there. Then, trying other polygons, I could conclude that the sequence describing the amount of combinations starting with a specific number is 1,3,6,10,...
The table just sums up the findings:
0's 1's 2's 3's 4's...
1....... triangle
3 ////1.......square
6 ////3/// 1...... pentagon
10// 6 ////3// 1.....hexagon
15//10///6//// 3 ////1.... septagon
21// 15/ 10/// 6 ///3/// 1... 8-gon
It means: The septagon have 15 combinations starting with 0, 10 combinations starting with 1 and so on.
I believe that the generalization is quite straightforward. As for the triangle, it is obvious that there is one single combination. 0,1,2
For the square, you have 4 combinations: 012 013 023 123
I used brute force only in the first part of my proof, assuming it's too difficult to explain the logic of why this sequence describes the situation.
Do you have an answer to the question? It is nerve-racking not to know whether your efforts worth something...

 

[QuantumQuest]

At this point I'll give a hint for anyone trying to solve the problem: For an efficient and short solution, try to find in which way you can pick the three vertices of the triangle in any polygon, in order to eliminate the need of examining all the formed triangles in each type of polygon.

 

[Buffu]

I have a question about what you mean by centre. Does the centre mean centroid or orthocentre or incentre ?

 

[QuantumQuest]

@ddddd28

There is a clear format problem in your lists, so I could not understand what exactly you talk about. Now, as I told you before I can see the way you follow and it is correct. So, you find the number of all triangles that is $\frac {n(n - 1)(n - 2)}{6}$ and because the problem states that we are talking about polygons with $2n + 1$ sides the previous expression becomes $\frac {n(2n + 1)(2n - 1)}{3}$. Then you calculate the probability of center of polygon to be inside the formed triangle as the difference of not-surviving-the-test triangles from 1. So, your solution is correct.

Do you have an answer to the question?

I have personally solved the problem in a contest decades before so I know the answer.

It is nerve-racking not to know whether your efforts worth something...

Your efforts definitely worth but I have some remarks about the way you presented your solution

If you want to tabulate numbers and data in general please use latex. There is a great guide here at PF https://www.physicsforums.com/help/latexhelp/. This way there will be no ambiguity about what you write. Also, use latex for any formulas and / or calculations. As an example it is more difficult for anyone to make sense of this

p=1- (n(n-1)(2n+1)/2)/(n(2n+1)(2n-1)/3)= 1- 1.5(n-1)/(2n-1)= n+1/ 4n-2

than if you write it in a clear, unambiguous way using latex.

As a final remark I would say don't use bold (B) characters in all your text. You can use it to point out something important or an expression etc. but it is best not to use it along all text.

 

[QuantumQuest]

I have a question about what you mean by centre. Does the centre mean centroid or orthocentre or incentre ?

The problem refers to the center of polygon.

 

[Buffu]

The problem refers to the center of polygon.

I am very sorry QuantumQuest. It is completely my fault, I did not see that question says regular polygon, my fault. Sorry.

 

[ddddd28]

At this point I'll give a hint for anyone trying to solve the problem: For an efficient and short solution, try to find in which way you can pick the three vertices of the triangle in any polygon, in order to eliminate the need of examining all the formed triangles in each type of polygon.

On reflection, the short solution is quite simple to understand.
I will explain it by construction of n sided polygon:
Assume we have a triangle. Then we bring a fourth point. How many new triangles can we construct? The new ones include the fourth point and two points of the original triangle. So, we need to know how many groups of two points we can choose from 3 points, which happens to be the binomial coefficient. $\binom{3}{2}$
In a similar vein, there are $\binom{4}{2}$ triangles for the fifth point. In general, for the n_th point, there are $\binom{n-1}{2}$ triangles.
The summation of all possible triangles in n polygon is, therefore:
1+$\binom{3}{2}$+$\binom{4}{2}$+$\binom{5}{2}$+...+$\binom{n-1}{2}$

any polygon

This is actually not accurate, any polygon except Concave polygon.

 

[QuantumQuest]

On reflection, the short solution is quite simple to understand.
I will explain it by construction of n sided polygon:
Assume we have a triangle. Then we bring a fourth point. How many new triangles can we construct? The new ones include the fourth point and two points of the original triangle. So, we need to know how many groups of two points we can choose from 3 points, which happens to be the binomial coefficient...

Yes, it may be shorter but still more complex compared to what I mean. You still introduce a fourth point that is not necessary.

This is actually not accurate, any polygon except Concave polygon.

No, it is absolutely accurate. We talk about polygons in plane i.e. 2-d.

 

[ddddd28]

This is what I meant saying "Concave polygon".
"You still introduce a fourth point that is not necessary." - just an example to visualize the formula I get.

 

[QuantumQuest]

This is what I meant saying "Concave polygon".

Three different vertices are chosen randomly from the set of vertices of a regular polygon having $2n+1$ sides

Take a more careful look at the wording of the problem - I've used bold face type for the important word. I'm really curious about how you did not notice that before solving the problem. Regular Polygons are never concave by definition.

"You still introduce a fourth point that is not necessary." - just an example to visualize the formula I get.

What do you mean?

 

[ddddd28]

I'm really curious about how you did not notice that before solving the problem.

Of course, I noticed it. I just referred to:

try to find in which way you can pick the three vertices of the triangle in any polygon

My solution of finding the amount of triangles in a polygon works to irregular polygons as well, as long as it is not a concave polygon.
By the way, I think it is quite interesting to generalize the formula to concave polygons too.

 

[QuantumQuest]

Of course, I noticed it. I just referred to:

try to find in which way you can pick the three vertices of the triangle in any polygon

I don't really see the point of what you write here. Isn't it obvious to you that "any polygon" I said is in the context of the problem that clearly states about regular polygons? What else could I refer to?

My solution of finding the amount of triangles in a polygon works to irregular polygons as well, as long as it is not a concave polygon.
By the way, I think it is quite interesting to generalize the formula to concave polygons too.

If you want to do any kind of generalization then it's OK for me but the problem gives and asks for specific things.

 

[mfb]

For a general polygon we would first need a definition of the center.

 

[ddddd28]

For a general polygon we would first need a definition of the center.

Do you think the center of mass is a legitimate center?

 

[mfb]

It is certainly an interesting point, but then you cannot make a general statement for general polygons as the answer will depend on the shape. As extreme case, you can find polygons where a triangle has to include a specific vertex to cover the center of mass.