Maximum number of regions formed by points on a circle












5












$begingroup$


The question is :



6 points are located on a circle and lines are drawn connecting these points, each pair of points connected by a single line. What can be the maximum number of regions into which the circle is divided?



My answer is 32 . But the actual answer is 31 how ??






geometry combinatorics







share|cite|improve this question











$endgroup$












  • $begingroup$
    arbelos.co.uk/Papers/Chords-regions.pdf
    $endgroup$
    – Bumblebee
    Jan 6 '17 at 4:30
















5












$begingroup$


The question is :



6 points are located on a circle and lines are drawn connecting these points, each pair of points connected by a single line. What can be the maximum number of regions into which the circle is divided?



My answer is 32 . But the actual answer is 31 how ??






geometry combinatorics







share|cite|improve this question











$endgroup$












  • $begingroup$
    arbelos.co.uk/Papers/Chords-regions.pdf
    $endgroup$
    – Bumblebee
    Jan 6 '17 at 4:30














5












5








5


1



$begingroup$


The question is :



6 points are located on a circle and lines are drawn connecting these points, each pair of points connected by a single line. What can be the maximum number of regions into which the circle is divided?



My answer is 32 . But the actual answer is 31 how ??






geometry combinatorics







share|cite|improve this question











$endgroup$




The question is :



6 points are located on a circle and lines are drawn connecting these points, each pair of points connected by a single line. What can be the maximum number of regions into which the circle is divided?



My answer is 32 . But the actual answer is 31 how ??






geometry combinatorics




geometry combinatorics






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Jan 20 '11 at 9:32









Aryabhata

70.2k6156246




70.2k6156246










asked Jan 20 '11 at 9:05









EgalitarianEgalitarian

183139




183139












  • $begingroup$
    arbelos.co.uk/Papers/Chords-regions.pdf
    $endgroup$
    – Bumblebee
    Jan 6 '17 at 4:30


















  • $begingroup$
    arbelos.co.uk/Papers/Chords-regions.pdf
    $endgroup$
    – Bumblebee
    Jan 6 '17 at 4:30
















$begingroup$
arbelos.co.uk/Papers/Chords-regions.pdf
$endgroup$
– Bumblebee
Jan 6 '17 at 4:30




$begingroup$
arbelos.co.uk/Papers/Chords-regions.pdf
$endgroup$
– Bumblebee
Jan 6 '17 at 4:30










3 Answers
3






active

oldest

votes


















0












$begingroup$

Answer is located here:




  • http://testfunda.com/Answers/ViewQuestion.aspx?QID=0e9eb0f3-8a80-4609-8be4-b022545c8224






share|cite|improve this answer









$endgroup$













  • $begingroup$
    This link is just a repetition of the question.
    $endgroup$
    – Alex
    Oct 6 '16 at 11:06





















6












$begingroup$

In general the maximum number of regions you can get from $n$ points is given by



$${n choose 4} + {n choose 2} + 1$$



This can be proved using induction (other combinatorial proofs exist too). For more information (including at least two proofs), see this: Dividing a circle into areas.



This is an oft cited puzzle to show the perils of generalizing based on first few values. We get powers of $2$ till $n=5$, after which we get $31$.






share|cite|improve this answer











$endgroup$





















    1












    $begingroup$

    The more general case is stated far more elegantly here: Number or regions formed when $n$ points on a circle are joined. But sometimes having a concrete example helps, and I hope this does.



    Note that a new region is formed




    1. when a new chord is drawn

    2. whenever that new chord intersects another chord


    We'll assume there are no 3-way intersections for the moment. However, it seems like 2 points divide the circle into 2 areas, 3 into 4, 4 into 8, 5 into 16, and so the pattern keeps working. Here is what happens for $n=6$:
    Let's draw a circle with points $a_1$, $a_2$, $a_3$, $a_4$ and $a_5$. Now put $a_6$, without loss of generality, between $a_1$ and $a_5$.





    • $a_1a_6$ and $a_5a_6$ each add one section to the circle, no more. That's 2.

    • we'll also ignore any intersections with other segments inside the circle for the moment and note $a_2a_6$/$a_3a_6$/$a_4a_6$ also create at least one more section. That's 3.


    • $a_3a_6$ runs across a few lines, but which? $a_1$ and $a_2$ are on one side of it, but $a_4$ and $a_5$ are on the other. Therefore ($a_1$ or $a_2$) to ($a_4$ or $a_5$) may cross $a_3a_6$ inside the circle, but no others. That's 4.


    • $a_2a_6$ runs across a few lines too: $a_1$ and $a_3$/$a_4$/$a_5$ are on each side. Therefore $a_1a_3$, $a_1a_4$, and $a_1a_5$ all may intersect with $a_2a_6$ to create another region. That's 3.


    • $a_4a_6$ is similar to $a_2a_6$. $a_4a_6$ will intersect $a_1a_5$, $a_2a_5$, and $a_3a_5$. That's 3.


    Thus the maximum number of additional regions moving from $n=5$ points to $n=6$ points is 2+3+4+3+3, or 15.



    I included a diagram below to show what lines are added with a 6th point. I hope it helps you see things.



    Example of 6th point added to Moser circle problem






    share|cite|improve this answer









    $endgroup$













      Your Answer





      StackExchange.ifUsing("editor", function () {
      return StackExchange.using("mathjaxEditing", function () {
      StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
      StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
      });
      });
      }, "mathjax-editing");

      StackExchange.ready(function() {
      var channelOptions = {
      tags: "".split(" "),
      id: "69"
      };
      initTagRenderer("".split(" "), "".split(" "), channelOptions);

      StackExchange.using("externalEditor", function() {
      // Have to fire editor after snippets, if snippets enabled
      if (StackExchange.settings.snippets.snippetsEnabled) {
      StackExchange.using("snippets", function() {
      createEditor();
      });
      }
      else {
      createEditor();
      }
      });

      function createEditor() {
      StackExchange.prepareEditor({
      heartbeatType: 'answer',
      autoActivateHeartbeat: false,
      convertImagesToLinks: true,
      noModals: true,
      showLowRepImageUploadWarning: true,
      reputationToPostImages: 10,
      bindNavPrevention: true,
      postfix: "",
      imageUploader: {
      brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
      contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
      allowUrls: true
      },
      noCode: true, onDemand: true,
      discardSelector: ".discard-answer"
      ,immediatelyShowMarkdownHelp:true
      });


      }
      });














      draft saved

      draft discarded


















      StackExchange.ready(
      function () {
      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f18271%2fmaximum-number-of-regions-formed-by-points-on-a-circle%23new-answer', 'question_page');
      }
      );

      Post as a guest















      Required, but never shown

























      3 Answers
      3






      active

      oldest

      votes








      3 Answers
      3






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes









      0












      $begingroup$

      Answer is located here:




      • http://testfunda.com/Answers/ViewQuestion.aspx?QID=0e9eb0f3-8a80-4609-8be4-b022545c8224






      share|cite|improve this answer









      $endgroup$













      • $begingroup$
        This link is just a repetition of the question.
        $endgroup$
        – Alex
        Oct 6 '16 at 11:06


















      0












      $begingroup$

      Answer is located here:




      • http://testfunda.com/Answers/ViewQuestion.aspx?QID=0e9eb0f3-8a80-4609-8be4-b022545c8224






      share|cite|improve this answer









      $endgroup$













      • $begingroup$
        This link is just a repetition of the question.
        $endgroup$
        – Alex
        Oct 6 '16 at 11:06
















      0












      0








      0





      $begingroup$

      Answer is located here:




      • http://testfunda.com/Answers/ViewQuestion.aspx?QID=0e9eb0f3-8a80-4609-8be4-b022545c8224






      share|cite|improve this answer









      $endgroup$



      Answer is located here:




      • http://testfunda.com/Answers/ViewQuestion.aspx?QID=0e9eb0f3-8a80-4609-8be4-b022545c8224







      share|cite|improve this answer












      share|cite|improve this answer



      share|cite|improve this answer










      answered Jan 20 '11 at 9:12







      anonymous



















      • $begingroup$
        This link is just a repetition of the question.
        $endgroup$
        – Alex
        Oct 6 '16 at 11:06




















      • $begingroup$
        This link is just a repetition of the question.
        $endgroup$
        – Alex
        Oct 6 '16 at 11:06


















      $begingroup$
      This link is just a repetition of the question.
      $endgroup$
      – Alex
      Oct 6 '16 at 11:06






      $begingroup$
      This link is just a repetition of the question.
      $endgroup$
      – Alex
      Oct 6 '16 at 11:06













      6












      $begingroup$

      In general the maximum number of regions you can get from $n$ points is given by



      $${n choose 4} + {n choose 2} + 1$$



      This can be proved using induction (other combinatorial proofs exist too). For more information (including at least two proofs), see this: Dividing a circle into areas.



      This is an oft cited puzzle to show the perils of generalizing based on first few values. We get powers of $2$ till $n=5$, after which we get $31$.






      share|cite|improve this answer











      $endgroup$


















        6












        $begingroup$

        In general the maximum number of regions you can get from $n$ points is given by



        $${n choose 4} + {n choose 2} + 1$$



        This can be proved using induction (other combinatorial proofs exist too). For more information (including at least two proofs), see this: Dividing a circle into areas.



        This is an oft cited puzzle to show the perils of generalizing based on first few values. We get powers of $2$ till $n=5$, after which we get $31$.






        share|cite|improve this answer











        $endgroup$
















          6












          6








          6





          $begingroup$

          In general the maximum number of regions you can get from $n$ points is given by



          $${n choose 4} + {n choose 2} + 1$$



          This can be proved using induction (other combinatorial proofs exist too). For more information (including at least two proofs), see this: Dividing a circle into areas.



          This is an oft cited puzzle to show the perils of generalizing based on first few values. We get powers of $2$ till $n=5$, after which we get $31$.






          share|cite|improve this answer











          $endgroup$



          In general the maximum number of regions you can get from $n$ points is given by



          $${n choose 4} + {n choose 2} + 1$$



          This can be proved using induction (other combinatorial proofs exist too). For more information (including at least two proofs), see this: Dividing a circle into areas.



          This is an oft cited puzzle to show the perils of generalizing based on first few values. We get powers of $2$ till $n=5$, after which we get $31$.







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited Jan 20 '11 at 9:25

























          answered Jan 20 '11 at 9:18









          AryabhataAryabhata

          70.2k6156246




          70.2k6156246























              1












              $begingroup$

              The more general case is stated far more elegantly here: Number or regions formed when $n$ points on a circle are joined. But sometimes having a concrete example helps, and I hope this does.



              Note that a new region is formed




              1. when a new chord is drawn

              2. whenever that new chord intersects another chord


              We'll assume there are no 3-way intersections for the moment. However, it seems like 2 points divide the circle into 2 areas, 3 into 4, 4 into 8, 5 into 16, and so the pattern keeps working. Here is what happens for $n=6$:
              Let's draw a circle with points $a_1$, $a_2$, $a_3$, $a_4$ and $a_5$. Now put $a_6$, without loss of generality, between $a_1$ and $a_5$.





              • $a_1a_6$ and $a_5a_6$ each add one section to the circle, no more. That's 2.

              • we'll also ignore any intersections with other segments inside the circle for the moment and note $a_2a_6$/$a_3a_6$/$a_4a_6$ also create at least one more section. That's 3.


              • $a_3a_6$ runs across a few lines, but which? $a_1$ and $a_2$ are on one side of it, but $a_4$ and $a_5$ are on the other. Therefore ($a_1$ or $a_2$) to ($a_4$ or $a_5$) may cross $a_3a_6$ inside the circle, but no others. That's 4.


              • $a_2a_6$ runs across a few lines too: $a_1$ and $a_3$/$a_4$/$a_5$ are on each side. Therefore $a_1a_3$, $a_1a_4$, and $a_1a_5$ all may intersect with $a_2a_6$ to create another region. That's 3.


              • $a_4a_6$ is similar to $a_2a_6$. $a_4a_6$ will intersect $a_1a_5$, $a_2a_5$, and $a_3a_5$. That's 3.


              Thus the maximum number of additional regions moving from $n=5$ points to $n=6$ points is 2+3+4+3+3, or 15.



              I included a diagram below to show what lines are added with a 6th point. I hope it helps you see things.



              Example of 6th point added to Moser circle problem






              share|cite|improve this answer









              $endgroup$


















                1












                $begingroup$

                The more general case is stated far more elegantly here: Number or regions formed when $n$ points on a circle are joined. But sometimes having a concrete example helps, and I hope this does.



                Note that a new region is formed




                1. when a new chord is drawn

                2. whenever that new chord intersects another chord


                We'll assume there are no 3-way intersections for the moment. However, it seems like 2 points divide the circle into 2 areas, 3 into 4, 4 into 8, 5 into 16, and so the pattern keeps working. Here is what happens for $n=6$:
                Let's draw a circle with points $a_1$, $a_2$, $a_3$, $a_4$ and $a_5$. Now put $a_6$, without loss of generality, between $a_1$ and $a_5$.





                • $a_1a_6$ and $a_5a_6$ each add one section to the circle, no more. That's 2.

                • we'll also ignore any intersections with other segments inside the circle for the moment and note $a_2a_6$/$a_3a_6$/$a_4a_6$ also create at least one more section. That's 3.


                • $a_3a_6$ runs across a few lines, but which? $a_1$ and $a_2$ are on one side of it, but $a_4$ and $a_5$ are on the other. Therefore ($a_1$ or $a_2$) to ($a_4$ or $a_5$) may cross $a_3a_6$ inside the circle, but no others. That's 4.


                • $a_2a_6$ runs across a few lines too: $a_1$ and $a_3$/$a_4$/$a_5$ are on each side. Therefore $a_1a_3$, $a_1a_4$, and $a_1a_5$ all may intersect with $a_2a_6$ to create another region. That's 3.


                • $a_4a_6$ is similar to $a_2a_6$. $a_4a_6$ will intersect $a_1a_5$, $a_2a_5$, and $a_3a_5$. That's 3.


                Thus the maximum number of additional regions moving from $n=5$ points to $n=6$ points is 2+3+4+3+3, or 15.



                I included a diagram below to show what lines are added with a 6th point. I hope it helps you see things.



                Example of 6th point added to Moser circle problem






                share|cite|improve this answer









                $endgroup$
















                  1












                  1








                  1





                  $begingroup$

                  The more general case is stated far more elegantly here: Number or regions formed when $n$ points on a circle are joined. But sometimes having a concrete example helps, and I hope this does.



                  Note that a new region is formed




                  1. when a new chord is drawn

                  2. whenever that new chord intersects another chord


                  We'll assume there are no 3-way intersections for the moment. However, it seems like 2 points divide the circle into 2 areas, 3 into 4, 4 into 8, 5 into 16, and so the pattern keeps working. Here is what happens for $n=6$:
                  Let's draw a circle with points $a_1$, $a_2$, $a_3$, $a_4$ and $a_5$. Now put $a_6$, without loss of generality, between $a_1$ and $a_5$.





                  • $a_1a_6$ and $a_5a_6$ each add one section to the circle, no more. That's 2.

                  • we'll also ignore any intersections with other segments inside the circle for the moment and note $a_2a_6$/$a_3a_6$/$a_4a_6$ also create at least one more section. That's 3.


                  • $a_3a_6$ runs across a few lines, but which? $a_1$ and $a_2$ are on one side of it, but $a_4$ and $a_5$ are on the other. Therefore ($a_1$ or $a_2$) to ($a_4$ or $a_5$) may cross $a_3a_6$ inside the circle, but no others. That's 4.


                  • $a_2a_6$ runs across a few lines too: $a_1$ and $a_3$/$a_4$/$a_5$ are on each side. Therefore $a_1a_3$, $a_1a_4$, and $a_1a_5$ all may intersect with $a_2a_6$ to create another region. That's 3.


                  • $a_4a_6$ is similar to $a_2a_6$. $a_4a_6$ will intersect $a_1a_5$, $a_2a_5$, and $a_3a_5$. That's 3.


                  Thus the maximum number of additional regions moving from $n=5$ points to $n=6$ points is 2+3+4+3+3, or 15.



                  I included a diagram below to show what lines are added with a 6th point. I hope it helps you see things.



                  Example of 6th point added to Moser circle problem






                  share|cite|improve this answer









                  $endgroup$



                  The more general case is stated far more elegantly here: Number or regions formed when $n$ points on a circle are joined. But sometimes having a concrete example helps, and I hope this does.



                  Note that a new region is formed




                  1. when a new chord is drawn

                  2. whenever that new chord intersects another chord


                  We'll assume there are no 3-way intersections for the moment. However, it seems like 2 points divide the circle into 2 areas, 3 into 4, 4 into 8, 5 into 16, and so the pattern keeps working. Here is what happens for $n=6$:
                  Let's draw a circle with points $a_1$, $a_2$, $a_3$, $a_4$ and $a_5$. Now put $a_6$, without loss of generality, between $a_1$ and $a_5$.





                  • $a_1a_6$ and $a_5a_6$ each add one section to the circle, no more. That's 2.

                  • we'll also ignore any intersections with other segments inside the circle for the moment and note $a_2a_6$/$a_3a_6$/$a_4a_6$ also create at least one more section. That's 3.


                  • $a_3a_6$ runs across a few lines, but which? $a_1$ and $a_2$ are on one side of it, but $a_4$ and $a_5$ are on the other. Therefore ($a_1$ or $a_2$) to ($a_4$ or $a_5$) may cross $a_3a_6$ inside the circle, but no others. That's 4.


                  • $a_2a_6$ runs across a few lines too: $a_1$ and $a_3$/$a_4$/$a_5$ are on each side. Therefore $a_1a_3$, $a_1a_4$, and $a_1a_5$ all may intersect with $a_2a_6$ to create another region. That's 3.


                  • $a_4a_6$ is similar to $a_2a_6$. $a_4a_6$ will intersect $a_1a_5$, $a_2a_5$, and $a_3a_5$. That's 3.


                  Thus the maximum number of additional regions moving from $n=5$ points to $n=6$ points is 2+3+4+3+3, or 15.



                  I included a diagram below to show what lines are added with a 6th point. I hope it helps you see things.



                  Example of 6th point added to Moser circle problem







                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered Jan 11 at 3:45









                  aschultzaschultz

                  1921415




                  1921415






























                      draft saved

                      draft discarded




















































                      Thanks for contributing an answer to Mathematics Stack Exchange!


                      • Please be sure to answer the question. Provide details and share your research!

                      But avoid …



                      • Asking for help, clarification, or responding to other answers.

                      • Making statements based on opinion; back them up with references or personal experience.


                      Use MathJax to format equations. MathJax reference.


                      To learn more, see our tips on writing great answers.




                      draft saved


                      draft discarded














                      StackExchange.ready(
                      function () {
                      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f18271%2fmaximum-number-of-regions-formed-by-points-on-a-circle%23new-answer', 'question_page');
                      }
                      );

                      Post as a guest















                      Required, but never shown





















































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown

































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown







                      -

                      Popular posts from this blog

                      Mario Kart Wii

                      Image
                      Please consider supporting The Cutting Room Floor on Patreon. Thanks for all your support! Mario Kart Wii From The Cutting Room Floor Jump to: navigation, search Mario Kart Wii Developer : Nintendo Publisher : Nintendo Platform : Wii Released in JP : April 10, 2008 Released in US : April 27, 2008 Released in EU : April 11, 2008 Released in AU : April 24, 2008 Released in KR : April 30, 2009 This game has unused animations. This game has unused areas. This game has unused code. This game has unused objects. This game has unused modes / minigames. This game has unused graphics. This game has unused models. This game has unused items. This game has unused music. This game has regional differences. This game has a notes page This game has a prerelease article Mario Kart Wii is the sixth game in the series (not counting Arcade editions), which intro...
                      Read more

                      Partial Derivative Guidance.

                      Image
                      0 $begingroup$ I was given this tricky problem in which I'm confuse on how to solve it and I would like some help: Let $v(x,y)$ be continuously differentiable function. Let the function $u(s,t)$ be given by $u(s,t) = sin(s)*v(s-2t,t^2)$ . Compute $du/ds$ and $du/dt$ in terms of $v$ and it's partial derivatives. My attempt (which is wrong): Using chain rule: $du/ds=(du/dx)(dx/ds) + (du/dy)(dy/ds)$ $du/dt=(du/dx)(dx/dt) + (du/dx)(dy/dt)$ So, $du/ds = sin(s)*v(x,y)*s + sin(s)*v(x,y)*0$ $du/dt = 2t*sin(s)*v(x,y) - 2*sin(s)*v(x,y)$ Thanks, calculus multivariable-calculus share | cite | improve this question edited Jan 19 at 19:38...
                      Read more

                      Understanding the size os this class of aleatory events

                      Image
                      0 1 $begingroup$ Hi I am having problems to understand this: I have: $Omega = [0,1]$ , $Lambda =$ all subsets with defined length Let $A_{0}$ = {A $subset$ [0,1]: A is finite union of intervals} 1º: My doubt is that $A_{0}$ is a algebra but its not a sigma algebra. Why? Also, A = $(0,1/2) cup (1/2,3/4) cup (3/4,7/8) cup ... cup(1-1/2^{n},1-1/2^{n+1})...$ 2º: So the class of aleatory events would be bigger than $A_{0}$ . Why? How the set A is greater than $A_{0}$ ? measure-theory share | cite | improve this question asked Jan 8 at 19:17 Diogo Bastos Diogo Bastos 116 6 ...
                      Read more