# Haselbauer-Dickheiser Test no. 3: Circle divided by lines between a blue dots

This is the test no. 3 from Haselbauer-Dickheiser Test.

3.

These three circles below all have blue dots on their circumference which are connected by straight lines. These lines divide the circles into smaller regions. The first circle, with two blue dots, is separated into two regions. The second circle, with three blue dots, is separated into four regions. The third circle, with four blue dots, is separated into 8 regions. Given a circle where seven blue dots are placed anywhere on its circumference, what would be the maximum number of regions into which it could be divided?

(Original image)

57.

This is a well-known problem called

Moser's circle problem. The sequence given by "maximal number of regions with $$n$$ blue dots" for increasing values of $$n$$ is $$1,2,4,8,16,31,57,\dots$$ (OEIS A000127). It's famously deceptive because the first few terms make it look like it's going to be simply the powers of 2, as another answer guessed, but it isn't.

• Well done, you got me again! – Weather Vane Sep 18 at 14:49
• What are other deceptive sequences? (non-trivial ones that have real applications)? – smci Sep 18 at 23:07
• @smci Dunno. This is my go-to example for a sequence that seems to go one way and actually goes another. – Rand al'Thor Sep 19 at 5:12

An answer from @Randal'Thor was posted while I prepared this.

57

Which I obtained by counting successive diagrams.
This is confirmed by the sequence

2,4,8,16,31,57
which is shown by OEIS to be A000127
Maximal number of regions obtained by joining n points around a circle by straight lines.

• this is what I thought of by seeing the picture but the thing is if each point is connected by the line then there is? 42 lines right? the region formula I got is wrong? – Sayed Mohd Ali Sep 18 at 14:55
• @SayedMohdAli that linked page gives the forrmula $(n^4 - 6n^3 + 23n^2 - 18n + 24)/24$ – Weather Vane Sep 18 at 15:00
• @SayedMohdAli the numbers of lines is half that because each each is shared by two points. So $n(n-1)/2$ – Weather Vane Sep 18 at 15:08
• I saw later :P previously I calculated number of lines wrong it should be 7*6/2 and I did 7*6... but later I corrected it :P I created sets. but my ideas was exactly same as yours but with little more research I got another way.. :D +1 – Sayed Mohd Ali Sep 18 at 19:06

Regions of a Circle Cut by Chords to n Points ---------------------------------------------- n points are distributed round the circumference of a circle and each point is joined to every other point by a chord of the circle. Assuming that no three chords intersect at a point inside the circle we require the number of regions into which the circle is divided.

With no lines the circle has just one region. Now consider any collection of lines. If you draw a new line across the circle which does not cross any existing lines, then the effect is to increase the number of regions by 1. In addition, every time a new line crosses an existing line inside the circle the number of regions is increased by 1 again.

So in any such arrangement
number of regions = 1 + number of lines + number of interior intersections

= 1 + C(n,2) + C(n,4)
Note that the number of lines is the number of ways 2 points can be chosen from n points. Also, the number of interior intersections is the number of quadrilaterals that can be formed from n points, since each quadrilateral produces just 1 intersection where the diagonals of the quadrilateral intersect.
Examples:
n=4 Number of regions = 1 + C(4,2) + C(4,4) = 8
n=5 Number of regions = 1 + C(5,2) + C(5,4) = 16
n=6 " " = 1 + C(6,2) + C(6,4) = 31
n=7 " " = 1 + C(7,2) + C(7,4) = 57

• I will update the answer counting :P the total lines wait. – Sayed Mohd Ali Sep 18 at 14:39
• It is asking for the number of regions, not the number of lines. – Jaap Scherphuis Sep 18 at 14:41
• In case you are still wondering, the region formula you previously used does not apply to this case. It assumes that every pair of lines intersect in a unique point, and counts all the regions. In this case we have points where more than 2 lines intersect (the blue points). We also have lines intersecting outside the circle (e.g. non-adjacent edges) leading to extra regions outside the circle that we are not interested in counting here. – Jaap Scherphuis Sep 18 at 15:29

64 - the number appears to be doubling with each additional point.

• Nope. This is a famously deceptive sequence. – Rand al'Thor Sep 18 at 14:43