A circle is bisected into 2 equal regions by its diameter. For any chord to be drawn, it must not cross the diameter (the end points of this diameter can not be used, either). As an explicit example above, 4 points are chosen on the left and 3 on the right, and the chords are interconnected among those points.
If 77 points are picked anywhere, except on the endpoints of given diameter, on the circle arc, what is the least possible number of chords, according to this rule?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Let there be x points on the left half and 7 7 − x points on the right half. Chords can only be formed using points on the same half of the circle, so the total number of chords formed is c ( x ) = ( 2 x ) + ( 2 7 7 − x ) = 2 ( x ) ( x − 1 ) + 2 ( 7 7 − x ) ( 7 7 − x − 1 ) = 2 2 x 2 − 1 5 4 x + 5 8 5 2 = x 2 − 7 7 x − 2 9 2 6
This will be minimized when its derivative is 0: c ′ ( x ) = 2 x − 7 7 = 0 implies x = 3 8 . 5 . Since x must be an integer, we check 3 8 and 3 9 : c ( 3 8 ) = 1 4 4 4 c ( 3 9 ) = 1 4 4 4
Intuitively this makes sense: the number of chords is minimized when the points are split as close to half-and-half as possible. This means 38 on one side and 39 on the other (and it doesn't matter if it's 38 on the left or 38 on the right).
If there are more points on one side, we can reduce by shifting the points to other side. Therefore minimum points occur when those points are equal or it's plus 1.
Problem Loading...
Note Loading...
Set Loading...
In order to minimize the chords in this case, we must maximize number of chords that cross the line.
Given a and b be the number of points on the left and right regions respectively, the number of chords that cross the line. equals a b , where a + b = 7 7
And in order to maximize such product, it must be closest to a square form. Since 7 7 is odd, the best we could do is taking a , b as consecutive numbers. Thus, a b = 3 9 × 3 8 .
Then the total number of chords from all points = ( 2 7 7 ) = 7 7 × 3 8 .
Finally, the least number of chords = 7 7 × 3 8 − 3 9 × 3 8 = 3 8 2 = 1 4 4 4 .