-3
$\begingroup$

This is continuation of this Q&A. Given a regular hexagon with center at point O:

enter image description here

Question: How many self-intersecting polygonal chains are there that connect 7 points?

The self-intersecting polygonal chain passes through each point once and chains should be non-isomorphic.

Improve this question
$\endgroup$
4
  • $\begingroup$ What is a reason of down-vote? $\endgroup$
    – Nick
    Dec 2, 2020 at 10:24
  • 4
    $\begingroup$ It does not feel much like a puzzle to me, as it mostly seems like boring case-work (especially if we have to subtract the non-intersecting ones), without much clever insight needed. $\endgroup$
    – Jaap Scherphuis
    Dec 2, 2020 at 10:36
  • $\begingroup$ Then again, maybe I'm biased because of this question about paths in a 3x3 square which was similar and involved way too many cases to be fun to answer. $\endgroup$
    – Jaap Scherphuis
    Dec 2, 2020 at 11:23
  • $\begingroup$ @JaapScherphuis subtracting the non-intersecting is easy. There's only 6 of them. It's removing the ones that cross over the midpoint without stopping that's the annoying part. $\endgroup$
    – Ben Barden
    Dec 2, 2020 at 18:58

1 Answer 1

Reset to default
1
$\begingroup$

Edit: this answer is not correct. It solves for undirected cycles (and I believe does so correctly) but the number for chains is different. I will not be solving for chains. Answer left in place in case it is somehow useful for future attempts.

This is pretty basic math, if a bit convoluted. There are 6 non-intersecting polygonal chains that cover all 7 points (depending on which direction you point the slice). Anything else would intersect.

Further, the chords that cross the center are non-legal, as they'd cause the center point to be touched more than once.

The total number of polygonal chains if you ignore those limitations? Simply 6!/2. You start at A. You have 6 options of where to go. After that 5, after that 4, and so on. Then you cut the result in half to acknowledge that it's not a directed graph.

The number of graphs where a line cross over the midpoint is equivalent to the number where B and E is one point, plus where C and F are one point, plus where A and D are one point, less the number where more than one of those is true. In this case, that means 3x5!/2 - x. Th x is the cases where two of those are true (subtract once, because it counts once rather than twice), less the case where all three are true (which shows up 3 times in the minuend, but three times also in the subtrahend, so we need to add it back in because it's supposed to show up once).

So, the total number of cases where it crosses the midpoint at least once without stopping is (3x5! - 3x4! + 3!)/2. The non-intersecting is, as mentioned, 6.

The final result is (6! - 3x5! + 3x4! - 3!)/2 - 6, which (I believe) comes to 207

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ There are more than 6 non-intersecting ones, for example abcdefo, bacdefo, abcdeof, bacdeof, abcdoef, bacdoef, abcdofe, bacdofe, abcodef, abcofed, abcofde, abcodfe, bacodfe, bacofde, and possibly more that I missed. "You start at A" - What about starting at O (and then A)? $\endgroup$
    – Jaap Scherphuis
    Dec 2, 2020 at 20:09
  • $\begingroup$ @JaapScherphuis Ah! You're right. I was looking at cycles, rather than chains. Ugh. You're also right that the answer for chains is a lot uglier. $\endgroup$
    – Ben Barden
    Dec 3, 2020 at 14:22

Not the answer you're looking for? Browse other questions tagged or ask your own question.