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

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