Math Challenge by QuantumQuest #3

In summary: I'm sorry but I didn't understand how this sequence is formed and how it relates to the number of triangles formed from the three randomly chosen vertices. Can you please clarify? Thank you.In summary, the probability that the center of a regular polygon with 2n+1 sides lies in the interior of a triangle formed from three randomly chosen vertices is given by n+1/4n-2. This is determined by finding the number of possible triangles and the number of triangles that do not satisfy the requirements, which can be represented by a triangular number sequence. The generalization for other polygons involves finding the number of symmetry lines and the number of possible triangles that do not cross these lines.
  • #1
19,412
9,961
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?
 
Last edited:
  • Like
Likes QuantumQuest and Charles Link
Physics news on Phys.org
  • #2
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:

upload_2017-5-28_5-51-10.png

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
 
  • Like
Likes QuantumQuest
  • #3
Greg Bernhardt said:
This is a "B" level challenge

Can we have a 'C' level challenge, this is too hard for me ? :cry:
 
  • #4
@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
ddddd28 said:
0 1 4 6 0's

or this
ddddd28 said:
1 2 4 3 1's
etc.

Also it is somewhat hard for me to follow the generalization

ddddd28 said:
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.
 
  • #5
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...
 
  • #6
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.
 
  • #7
I have a question about what you mean by centre. Does the centre mean centroid or orthocentre or incentre ?
 
  • #8
@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.

ddddd28 said:
Do you have an answer to the question?

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

ddddd28 said:
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

ddddd28 said:
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.
 
  • #9
Buffu said:
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.
 
  • #10
QuantumQuest said:
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.
 
  • Like
Likes QuantumQuest
  • #11
QuantumQuest said:
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 nth 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}##
QuantumQuest said:
any polygon
This is actually not accurate, any polygon except Concave polygon.
 
  • #12
ddddd28 said:
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.

ddddd28 said:
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.
 
  • #13
upload_2017-5-29_20-0-42.png

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.
 
  • #14
ddddd28 said:
This is what I meant saying "Concave polygon".

Greg Bernhardt said:
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.

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

What do you mean?
 
  • #15
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.
 
  • #16
ddddd28 said:
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?

ddddd28 said:
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.
 
  • #17
For a general polygon we would first need a definition of the center.
 
  • Like
Likes QuantumQuest
  • #18
mfb said:
For a general polygon we would first need a definition of the center.
Do you think the center of mass is a legitimate center?
 
  • #19
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.
 

1. What is the goal of "Math Challenge by QuantumQuest #3"?

The goal of "Math Challenge by QuantumQuest #3" is to solve mathematical equations and puzzles in order to progress through different levels and ultimately win the game.

2. How difficult are the mathematical challenges in this game?

The difficulty of the mathematical challenges in this game varies depending on the level. Some may be relatively easy while others may require more advanced mathematical knowledge and critical thinking skills.

3. Is this game suitable for all ages?

Yes, "Math Challenge by QuantumQuest #3" is suitable for all ages. The game offers different levels of difficulty to cater to different age groups and skill levels.

4. Can I play this game on my smartphone or tablet?

Yes, "Math Challenge by QuantumQuest #3" is available for both smartphones and tablets. It can be downloaded from the app store for iOS and Google Play for Android devices.

5. Are there any rewards or prizes for completing this game?

While there are no physical rewards or prizes for completing "Math Challenge by QuantumQuest #3", the satisfaction of solving challenging mathematical puzzles and improving one's skills can be considered a reward in itself.

Similar threads

  • Math Proof Training and Practice
Replies
7
Views
3K
  • Math Proof Training and Practice
Replies
13
Views
3K
  • Math Proof Training and Practice
Replies
26
Views
4K
  • Math Proof Training and Practice
Replies
28
Views
6K
  • Math Proof Training and Practice
2
Replies
49
Views
7K
  • Math Proof Training and Practice
2
Replies
61
Views
9K
  • Math Proof Training and Practice
Replies
8
Views
2K
  • Math Proof Training and Practice
Replies
8
Views
3K
  • Math Proof Training and Practice
3
Replies
82
Views
11K
  • Math Proof Training and Practice
2
Replies
40
Views
14K
Back
Top