Non-Intersecting Chords

We start by fixing a point $P$ on the circle. We can neglect the probability that this point will be an endpoint of one of the chords. Now, we generate two red, two blue, two green, and two purple points on the circle at random, points of the same color being the endpoints of one chord. Again, we can neglect the probability that any two points coincide.

Imagine starting at $P$ and going once clockwise around the circle. While doing so, write down the colors in the order in which you encounter them. There are exactly $8! / 2^4 = 2520$ different sequences of colors you may obtain, and by symmetry each sequence is equally likely.

Whether or not two of the chords intersect is clearly uniquely determined by the sequence of colors. (I.e., only the relative positions of the points matter, not their actual coordinates.) Thus, the probability we seek can be computed as $g/2520$ , where $g$ is the number of color sequences such that no two chords intersect.

Such sequences are closely related to correctly parenthesized expressions. Let's take any sequence of colors and rewrite it as follows: The first occurrence of red will be denoted by '(', and the second one by ')'. The same goes for green and '[' + ']', blue and '{' + '}', and purple and '<' + '>'. Clearly, no two chords intersect if and only if we obtain an 8-character string that is correctly parenthesized. Or, in other words, if two pairs of parentheses overlap, the corresponding two chords intersect. For example, if we obtain the string "({}[)]<>", we can be certain that the red chord and the green chord have to intersect.

Thus, we are left with counting all correctly parenthesized strings that contain 4 parenthesis types, each of them once. Let's use $C_n$ to denote the general case, so that $C_4$ is what we want.

Clearly $C_1=1$ and $C_2=4$ .

For $C_3$ the first character has to be a left parenthesis. We have 3 possibilities for its type. WLOG let the type be '('. Now there are three ways how the string can look like: a) "()xxxx", b) "(xx)yy", or c) "(xxxx)". In cases a) and c) there are $C_2=4$ possibilities for "xxxx", in case b) there are two ways to choose the parenthesis type used in xx, and then $C_1=1$ possibilities for each of xx and yy. Thus, $C_3=3\cdot(4+2+4)=30$ .

Similarly we compute $C_4 = 4\cdot(C_3 + 3C_1C_2 + 3C_2C_1 + C_3) = 336$ .

Thus the probability we seek is $C_4 / 2520 = 2/15$ and the answer is $2+15=\fbox{17}$ .

In this example we have 4 chords and 8 unique points on the circle. To assist with the solution let's first abstract this to the case of 2n unique points (n chords).

For purposes of clarity we can label the points $p_1, p_2, ..., p_{2n}$ in a clockwise fashion around the circle.

Starting with the first point $p_1$ , what other points can we connect it to? We cannot connect it to $p_3$ as it will leave $p_2$ requiring a connection that will intersect with the chord from $p_1$ to $p_3$ . ( example image )

In fact, we can only connect $p_1$ to $p_2, p_4$ , or $p_{2i}$ for i in {1, ...., n}, otherwise, we would be left with an odd number of points between $p_1$ and the point it is connected to which would require a chord to intersect with the chord coming from $p_1$

So for any i in {1, ..., n} if we connect $p_1$ to $p_{2i}$ we have then decided the circle into 2 sections. One contains $(2i - 2) = 2(i-1)$ points and the other contains $(2n - 2i) = 2(n-i)$ points.

Let us define $C_n$ to be the number of chords that can be drawn between any 2n points (n chords) on the circle without there being an intersection.

In our case above, once we have selected an arbitrary i in {1,...,n} the remaining possibilities for chords would then be $C_{i-1} \times C_{n-i}$ . Note that the chords drawn on one side of the first division are independent of those drawn on the other side as none of the chords can cross the first chord that was drawn from $p_1$ to $p_{2i}$

We know that any chord drawn between $p_1$ and $p_{2i}$ for any i in {1,....,n} will be the start of a valid solution, we are left with the following identity for $C_n$ : $C_n = \displaystyle \sum_{i=1}^n C_{i-1} \times C_{n-i}$

In our case we want to calculate $C_4$ , because there are 4 chords. We also know that $C_1 = 1$ as with 2 points there is only one way to connect the chords (remember n = the number of chords, which implies 2n = the number of points).

So using the identity above we can derive $C_4 = 14$ . Now the $C_n$ numbers represent the Catalan Numbers. These numbers can be used to solve a variety of interesting combinatorics problems.

We now know that there are 14 ways to connect the 8 points in 4 chords so that none of the lines intersects. We now need to find out the probability of this occurring. To derive this, we'll need to know how many ways we can connect 8 dots with 4 lines.

This part of the problem actually relies on a concept called the double factorial (for odd numbers). For this problem we don't need to know about the double factorial, but it does make for some interesting reading.

Let $A_n$ be the number of combinations that we can link 2n points with n chords so that each chord touches 2 distinct points and no point is included on more than one chord.

For n = 1 we have 2 points and only one possible chord so $A_n = 1$

Now assume that n is any natural number and we have 2n points. if we pick any point on the circle. We can now connect it to (2n - 1) other points. after doing so we are left with 2n-2 points left that need to be connected. Therefore we have the recursive identity:

$A_{n+1} = (2n - 1) \times A_n$

This produces the sequence 1, 3, 5, 15, 105, ... which is the sequence of double factorials for odd numbers.

Using the formula above with $A_1 = 1$ , we get $A_4 = 105$

So the probability the original problem asked for is $\frac {C_4}{A_4} = \frac {14}{105}$ which can be reduced to $\frac {2}{15}$

The solution to the problem is then 2 + 15 = 17

We can simplify the problem greatly by considering it in the following way: given $8$ points chosen uniformly at random from around the unit circle, what is the probability that if each point is connected to exactly one other point by a chord, none of the resulting chords intersect?

Because the points are chosen uniformly at random from an infinite set (there are infinitely many points on the circumference of the unit circle), the probability that a point is chosen twice is $0$ , and so we can consider only cases where we have $8$ distinct points.

$\\$

We first find how many ways there are to connect the $8$ points in the previously-described way. Because the method we are going to use makes no mention of the arrangement of the points (except for the fact that they are distinct), and because each arrangement happens with equal probability, we only need to look at one possible arrangement to solve the problem. Pick one of the $8$ points and call it $A_1$ . There are $7$ points that we can connect $A_1$ to. Pick one of them and call it $B_1$ . Construct $\overline{A_1B_1}$ . Now find the next point clockwise of $A_1$ which does not have a chord extending from it and call it $A_2$ . There are $5$ points to connect it to. Pick one and call it $B_2$ . Construct $\overline{A_2B_2}$ . Repeating this process to find $\overline{A_3B_3}$ and $\overline{A_4B_4}$ , we find that there are $7\cdot5\cdot3\cdot1 = 105$ possible arrangements for the chords. Because of the way we counted the chords (beginning with the counter-clockwise-most endpoint of a chord and only using another endpoint if it is clockwise of the first one), we can be sure that we have not double-counted any chords, and so we are done.

$\\$

Now we must find how many such arrangements have no intersecting chords. Label the points $A,B,C,...,H$ in clockwise order around the circle. We will call two points "partners" if there is a chord connecting them. We will proceed via casework with cases based on $A$ 's partner:

B: If $B$ is $A$ 's partner, there are $3$ choices for $C$ 's partner, namely $D,F,H$ . The other choices do not allow for a configuration with no intersections. If we construct $\overline{CD}$ , we will have $2$ choices for $E$ 's partner (we cannot pick $G$ ), each of which defines a unique arrangement with no intersecting chords. If we construct $\overline{CF}$ , we only have one choice for $D$ 's partner ( $E$ ), which gives only $1$ arrangement. If we construct $\overline{CH}$ , we are in a situation almost identical to that with $\overline{CD}$ , which gives $2$ arrangements. Thus, this case yields a total of $5$ valid arrangements.

D: $C$ must be $B$ 's partner, and so we have $2$ choices for $E$ 's partner, each of which defines a unique, valid arrangement. This case gives $2$ valid arrangements.

F: By symmetry, this case is equivalent to D , and so it yields $2$ valid arrangements.

H: By symmetry, this case is equivalent to B , and so it yields $5$ valid arrangements.

$\\$

We see that we have a total of $5+2+2+5=14$ valid arrangements out of a total of $105$ possible arrangements of chords, which means that the probability that no pair of chords intersects is $\frac{14}{105}=\frac{2}{15}$ . Thus, our answer is $2+15=\fbox{17}$ .

Each choice of points corresponds to an arrangement of the letters A,A,B,B,C,C,D,D around a circle. There are (8C2) (6C2) (4C2)/8 = 315 such arrangements. Arrangements that correspond to a set of chords with no intersections must have at least 2 same-letter adjacent pairs (i.e. AA or BB). So we can break the problem into cases:

If there are exactly 2 same-letter adjacent pairs, there are 4C2=6 ways to choose these pairs and 3 ways to arrange the remaining letters without having intersecting chords, for a total of 12 arrangements.

If there are exactly 3 same-letter adjacent pairs, there are 4C3=4 ways to choose the pairs and 6 ways to properly arrange the pairs and the remaining two letters, for a total of 24.

If there are exactly 4 same-letter adjacent pairs, there are 4!/4=6 ways to order the pairs around the circle.

Thus our probabilitiy is (12+24+6)/315 = 2/15, so a+b=17.

We consider 8 points in a sequence 1, 2, 3, 4, 5, 6, 7, 8.

Now the first chord is connected to 1 and to one of (8-1) other possible points. Similarly, the other chord is connected to one of (8-3) other possible points. [As 2 points have already been occupied] So the number of ways of connecting all the chords = 7 5 3*1 = 105

1(2(3)4(5(6)7)8), or more concisely as, ( () ( () ) ), with a left bracket signifying a start point and a right bracket signifying an end point is a possible configuration.

The trick to counting the number of brackets that correspond to non-intersecting chords is to subtract the number of "bad" bracket strings from the total number of bracket strings. We note that "bad" bracket strings occur when, working from left to right, the number of right brackets exceeds the number left brackets. For example, () )( ().

The first time we encounter a right bracket out of place, we shall invert every bracket thereafter: left becomes right and right becomes left. For example, the "bad" string, () )( (), becomes, () )) )(.

The result of this exercise is that we end up with (4-1) left brackets and (4+1) right brackets, and as each one of these strings corresponds to a unique "bad" bracket string, we can determine that there are C(8, 4+1) "bad" bracket strings in total.

Hence there are C(8,4)-C(8,5)=(8 7 6 5/ 4 3 2 1)-(8 7 6 5 4/5 4 3 2 1) =14 non-intersecting chords.

So, the probability of all chords that are non-intersecting =14/105= 2/15

a/b = 2/15. Thus a+b=17.

Although this looks like a geometry problem it is actually a combinatorics one.

We'll assume no two points coincide (the probability of that is technically zero). Now, if the order if points around the circle is $1,2,3,4,5,6,7,8$ for example then it doesn't matter exactly how far spaced apart each point, it's only the order of points that's significant.

So the question becomes: how many ways can we order the numbers $1$ to $8$ around a circle so that the lines $\{1,2\}, \{3,4\}, \{5,6\}, \{7,8\}$ don't coincide?

Well, by inspection we can draw all possible arrangements of lines, see this diagram .

The number under each image is how many possible rotations we can do on it to obtain a distinct pattern; so the total possible number of layouts is $14$ .

Now, for each layout we can assign the four pairs $\{1,2\}$ etc. in any order, i.e. $4!$ ways.

And then for each assignment we can order each pair in two ways, i.e. $2^4$ orderings per assignment.

There are $8!$ total possible ways of assigning the numbers $1$ - $8$ to a diagram.

This gives us a total ratio of valid positions of: $\frac{14 \cdot 4! \cdot 2^4}{8!} = \boxed{\frac{2}{15}}$

The probability we want to know is equal to the probability that with 8 points, chosen randomly (uniform) on a circle, divided into 4 connected pairs, that these connecting chords do not intersect.

There are 3 different configurations in which this happens. Starting at the top of the circle and going clockwise, we encounter points 1 through 8 in ascending order. The three configurations are as follows: {(1, 2), (3, 4), (5, 6), (7, 8)}, {(1, 2), (3, 4), (5, 8), (6, 7)}, and {(1, 2), (3, 8), (4, 7), (5, 6)}. The first configuration has 2 variants, the second configuration has 8, and the third configuration 4.

There are 105 possible divisions of 8 points into 4 pairs, so the probability is 14/105=2/15. The answer is therefore 2+15=17.

Note that drawing chords one by one is the same as connecting 8 points on a circle. We want to connect them such that no chord intersects. You should recognize this resulting problem as an application to a very famous series: the Catalan Numbers. Since we have 4 chords, the number of ways to connect the points such that no chord intersects is the 4th Catalan Number, which is 14.

The total number of ways to connect them is $\dfrac{\binom{8}{2}\cdot\binom{6}{2}\cdot\binom{4}{2}\cdot\binom{2}{2}}{4!}=105$ , therefore the probability is $\dfrac{14}{105}=\dfrac{2}{15}$ and the answer is $2+15=\boxed{17}$ .

This problem reduces to a simple counting. Draw 8 random points on the circle. Pick one. From there, we have 7 points to connect to. Then we pick a third point and have 5 points to connect to. So, there are $7\times 5 \times 3 = 105$ ways to draw the 4 chords. For $n$ chords, we would have $(2n-1)!!$ chords. The number of non-intersecting choices of $n$ chords is equal to the $n$ th Catalan number: $C_n = \frac{1}{n+1}\binom{2n}{n}$ . In our case, we have $\frac{1}{5}\binom{8}{4} = 14$ . Thus, our answer is $\frac{14}{105} = \frac{2}{15}$ . The general solution would be $\frac{(2n-1)!!}{C_n}$ . A great resource for Catalan numbers and fun bijection problems by Richard Stanley can be found here .

First of all it is important to notice that is the order of the points that matters and not how we choose the 8 points (i.e. a chord divides the unit circle in two arcs, if we draw a new cord such that its extremal points lie on different arcs, no matter how, the two cords are going to intersect). Therefore we can work only on how we connect the points and (because of convenience) we can suppose that the eight points form a regular octagon.

First of all we count the number of ways in which we can connect the 8 points.

Starting from $(1,0)$ and proceeding anti-clockwise... the first free point we encounter is $(1,0)$ and can be connected with $7$ different points, leaving us with $6$ points. Then the next free point we encounter can be connected only with $5$ different free points and so on, until we are left only with two points (and we will have to connect them). Therefore we have: $7 \cdot 5 \cdot 3 \cdot 1$ possibilities.

Not all of them give us no intersections between chords. Now we count how many situations give us no intersections.

To do this we will invent a way to build a pattern with no intersections: we choose $4$ of the $8$ points and we will call them special points. They have to be chosen in such a way that starting from $(1,0)$ and proceeding anti-clockwise all the way through the number of special points we encounter is always less or equal than the number of normal points. Now it's done: starting from $(1,0)$ and proceeding anti-clockwise every time we encounter a special point we join it to the last free point we have encountered. It is easy to see that every required situation can be built in this way and there is a bijection between the required situations and the buildable situations. Therefore the number of situations with no intersections is the same as the number of ways in which we can order $4$ normal points and $4$ special points such that the number of special points we encounter is always less or equal than the number of normal points.

This is a well known problem an refers to the Catalan numbers in particular in finding how many Dyck words are of length $8$ (that is the $5$ -th Catalan Number): $14$

the result is: $\frac{ 7 \cdot 5 \cdot 3}{14}=\frac{15}{2}$

And the answer is $\fbox{17}$

Let's select 8 points on a circle and label them $A_1, A_2, B_1, B_2, C_1, C_2, D_1, D_2$ in some order, we'll call this a permutation. There are $8!$ ways to do this, but how many of them also satisfy the condition that $A_1A_2, B_1B_2, C_1C_2\ and\ D_1D_2$ do not intersect (we'll call such permutations "valid")?

An important thing to notice: if we write down the labels of the points of a valid permutation in clockwise order and divide this string in two parts by "cutting out" $A_1$ , $A_2$ and everything between them, both $B_1$ and $B_2$ will be located in the same part, just like $C_1$ and $C_2$ , and $D_1$ and $D_2$ will. If we cut the segment between $B_1$ and $B_2$ , the same will hold, etc. This is pretty natural, since if we see something like $X_1 \dots Y_1 \dots X_2 \dots Y_2$ , then it's obvious that $X_1X_2$ and $Y_1Y_2$ will intersect.

Therefore, if we replace all $*_1$ with "(" (i.e. opening brackets) and all $*_2$ with ")", we'll get a correct string of brackets (i.e. one that can be found by removing everything except the brackets from a valid algebraic expression). The number of correct strings of brackets utilising $n$ pairs of brackets is equal to the $n$ th Catalan number, $C_n = \frac{1}{n+1} \times \binom{2n}{n}$ .

To account for the fact that there are $4!$ ways assign a letter from $\{A, B, C, D\}$ to each of the brackets (such that matching brackets have matching letters), we multiply the 4th Catalan number with $4!$ ; to account for the fact that, for each letter, there are two ways to decide which is going to be $*_1$ , and which $*_2$ , we multiply the answer with $2^4$ .

Therefore, the total number of valid permutations is $C_4 \times 4! \times 2^4 = 5376.$ The total number of all permutations is $8! = 42 320$ . Therefore, the probability is $\frac{5376}{42 320} = \frac{2}{15}$ , and $2 + 15 = \boxed{17}$ , which is the final answer.