Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Challenge Math Challenge by QuantumQuest #3

Tags:
  1. May 22, 2017 #1
    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: May 28, 2017
  2. jcsd
  3. May 27, 2017 #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
     
  4. May 28, 2017 #3
    Can we have a 'C' level challenge, this is too hard for me ? :cry:
     
  5. May 28, 2017 #4

    QuantumQuest

    User Avatar
    Gold Member

    @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
    or this
    etc.

    Also it is somewhat hard for me to follow the generalization

    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.
     
  6. May 28, 2017 #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...
     
  7. May 28, 2017 #6

    QuantumQuest

    User Avatar
    Gold Member

    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.
     
  8. May 28, 2017 #7
    I have a question about what you mean by centre. Does the centre mean centroid or orthocentre or incentre ?
     
  9. May 28, 2017 #8

    QuantumQuest

    User Avatar
    Gold Member

    @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.

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

    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

    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.
     
  10. May 28, 2017 #9

    QuantumQuest

    User Avatar
    Gold Member

    The problem refers to the center of polygon.
     
  11. May 28, 2017 #10
    I am very sorry QuantumQuest. It is completely my fault, I did not see that question says regular polygon, my fault. Sorry.
     
  12. May 29, 2017 #11

    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}##
    This is actually not accurate, any polygon except Concave polygon.
     
  13. May 29, 2017 #12

    QuantumQuest

    User Avatar
    Gold Member

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

    No, it is absolutely accurate. We talk about polygons in plane i.e. 2-d.
     
  14. May 29, 2017 #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.
     
  15. May 29, 2017 #14

    QuantumQuest

    User Avatar
    Gold Member

    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.

    What do you mean?
     
  16. May 29, 2017 #15
    Of course, I noticed it. I just refered 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.
     
  17. May 29, 2017 #16

    QuantumQuest

    User Avatar
    Gold Member



    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?

    If you want to do any kind of generalization then it's OK for me but the problem gives and asks for specific things.
     
  18. May 29, 2017 #17

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    For a general polygon we would first need a definition of the center.
     
  19. May 30, 2017 #18
    Do you think the center of mass is a legitimate center?
     
  20. May 30, 2017 #19

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Math Challenge by QuantumQuest #3
Loading...