All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Inscribed circle and Line Choice (Posted on 2010-06-27)
(A) Out of 100 straight lines having respective lengths 1, 2, 3, ......, 99, 100; determine the total number of ways in which four straight lines may be chosen which will form a quadrilateral in which a circle may be inscribed.

(B) Out of 101 straight lines having respective lengths 1, 2, 3, ......, 99, 100, 101; determine the total number of ways in which four straight lines may be chosen which will form a quadrilateral in which a circle may be inscribed.

 No Solution Yet Submitted by K Sengupta No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 start of analysis; computer finish (spoiler) | Comment 1 of 3

According to the Pitot theorem, a quadrilateral is inscribable with a circle if and only if the two totals of opposite pairs of sides are equal, so for example, sides in the order 1,4,6,3 would allow that quadrilateral to be inscribed with a circle, as 1+6 = 4+3. Another way of looking at it is that the average of one pair of opposite sides must equal the average of the other.

In the smallest such set, the smallest number 1 must be paired with the highest, 4, to allow space for 2 and 3 to add to the same total. Next comes 1 and 5, which allows 2+4, but 3+3 is disallowed as we're not allowed two lines with the same length. Then 1+6 allows placement with 2+5 or 3+4. After tha, 1+7 still allows only two more: 2+6 and 3+5.

So with smallest side 1, the numbers of possibilities are:

1+1+2+2+ ... +48+48+49 = 48(48+1)/2 + 49

Starting with smallest side 2, there are:

1+1+2+2+ ... +48+48 = 48(48+1)/2

Starting with 3:

1+1+2+2+ ... +47+47+48 = 47(47+1)/2 + 48

etc.

until

Starting with 97:

1

Rather than add all these up, the following program just brute forces the smallest side a, the largest side c and the two intervening sides b and d with b<d, doing this for the two cases--max = 100 and max = 101:

CLS
FOR max = 100 TO 101
ct = 0
FOR a = 1 TO max
FOR c = a + 1 TO max
t = a + c
FOR b = a + 1 TO c - 1
d = t - b
IF d <= b THEN EXIT FOR
ct = ct + 1
NEXT
NEXT c
NEXT a
PRINT ct
NEXT max

producing

79625
82075

as the two answers.

 Posted by Charlie on 2010-06-27 19:43:50

 Search: Search body:
Forums (0)