Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site ucla-cs.ARPA
Path: utzoo!watmath!clyde!bonnie!akgua!sdcsvax!sdcrdcf!trwrba!cepu!ucla-cs!dgc
From: dgc@ucla-cs.UUCP
Newsgroups: net.puzzle
Subject: Re: High School Math problems:Answers and a toughie!
Message-ID: <1783@ucla-cs.ARPA>
Date: Mon, 29-Oct-84 21:41:50 EDT
Article-I.D.: ucla-cs.1783
Posted: Mon Oct 29 21:41:50 1984
Date-Received: Thu, 25-Oct-84 03:48:27 EDT
References: <1975@stolaf.UUCP> <1590@ucla-cs.ARPA> <1214@utah-gr.UUCP>
Organization: UCLA CS Dept.
Lines: 42

------------------------------------------------------------------------
    In article <1590@ucla-cs.ARPA> dgc@ucla-cs.UUCP writes:
    >
    >    >Find the greatest number of intersections in an n-gon if all
    >    >vertices are connected. Ex.  If you draw lines connecting all four
    >    >vertices of a quadrilateral, you get one intersection.
    >
    >The answer to the problem is implicitly stated in the problem.
    >Specifically, every four distinct vertices give rise to one intersection
    >and conversely, each intersection determines four distinct vertices.  So
    >the the answer is the number of ways one can choose four vertices from
    >the given n. That is, it is "n choose 4" which is
    >
    >           n(n-1)(n-2)(n-3)
    >           ----------------
    >                  24
    >

    I'm afraid it's more complicated than that.  For example, this
    formula gives 15 for a hexagon, but a simple picture shows only 13. 
    This is because of the three diagonals that intersect in a single
    point at the center.

    I don't have the answer, but it looks like it's back to the drawing
    board.
------------------------------------------------------------------------
The point is the problem asked for the "greatest" number of
intersections.  This means that you shouldn't have triple (or more
intersections) because by slightly perturbing the vertices you will get
more intersections.  Alternatively, a k-fold intersection should count
as k(k-1)/2 simple intersections (which is what you get if you slightly
perturb the vertices to a "general" position).  In the example, the
triple intersection counts as 3 simple intersections, which makes the
general formula correct.

If you don't count multiple intersections this way, then the answer
cannot depend upon n, alone.

David G. Cantor

Arpa: dgc@ucla-locus.arpa
UUCP: ...!{cepu, ihnp4, randvax, sdcrdcf, trwspp, ucbvax}!ucla-cs!dgc