Don't Cross the Line

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?


The answer is 1444.

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.

3 solutions

In order to minimize the chords in this case, we must maximize number of chords that cross the line.

Given a a and b b be the number of points on the left and right regions respectively, the number of chords that cross the line. equals a b ab , where a + b = 77 a + b = 77

And in order to maximize such product, it must be closest to a square form. Since 77 77 is odd, the best we could do is taking a , b a,b as consecutive numbers. Thus, a b = 39 × 38 ab = 39\times 38 .

Then the total number of chords from all points = ( 77 2 ) = 77 × 38 \binom{77}{2} = 77 \times 38 .

Finally, the least number of chords = 77 × 38 39 × 38 = 3 8 2 = 1444 77\times 38 - 39\times 38 = 38^2 = \boxed{1444} .

Jordan Cahn
Jun 5, 2018

Let there be x x points on the left half and 77 x 77-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 ) = ( x 2 ) + ( 77 x 2 ) = ( x ) ( x 1 ) 2 + ( 77 x ) ( 77 x 1 ) 2 = 2 x 2 154 x + 5852 2 = x 2 77 x 2926 c(x) = {x \choose 2} + {77-x \choose 2} = \frac{(x)(x-1)}{2} + \frac{(77-x)(77-x-1)}{2} = \frac{2x^2 - 154x + 5852}{2} = x^2 - 77x - 2926

This will be minimized when its derivative is 0: c ( x ) = 2 x 77 = 0 c'(x) = 2x - 77 = 0 implies x = 38.5 x = 38.5 . Since x x must be an integer, we check 38 38 and 39 39 : c ( 38 ) = 1444 c ( 39 ) = 1444 c(38) = 1444\\c(39) = 1444

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).

Takahiro Waki
Jun 7, 2018

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.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...