9
$\begingroup$

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.

image illustrating the problem

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)

Improve this question
$\endgroup$
0

3 Answers 3

Reset to default
19
$\begingroup$

The answer is

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.

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

An answer from @Randal'Thor was posted while I prepared this.
My (independent) answer is

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Sayed Mohd Ali
    Sep 18, 2019 at 14:55
  • $\begingroup$ @SayedMohdAli that linked page gives the forrmula $(n^4 - 6n^3 + 23n^2 - 18n + 24)/24$ $\endgroup$
    – Weather Vane
    Sep 18, 2019 at 15:00
  • 1
    $\begingroup$ @SayedMohdAli the numbers of lines is half that because each each is shared by two points. So $n(n-1)/2$ $\endgroup$
    – Weather Vane
    Sep 18, 2019 at 15:08
  • $\begingroup$ 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 $\endgroup$
    – Sayed Mohd Ali
    Sep 18, 2019 at 19:06
3
$\begingroup$

My answer is reference

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ I will update the answer counting :P the total lines wait. $\endgroup$
    – Sayed Mohd Ali
    Sep 18, 2019 at 14:39
  • $\begingroup$ It is asking for the number of regions, not the number of lines. $\endgroup$
    – Jaap Scherphuis
    Sep 18, 2019 at 14:41
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jaap Scherphuis
    Sep 18, 2019 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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