gilje@stolaf.UUCP (Mark A. Gilje) (10/05/84)
The first two were easy I know and have heard from others. In case you didn't get them, the first is n(n+1)(2n+1)/6 which is the sum of the squares from 1 to n. The second answer comes from the fact that 1,000,000,000 = 10^9 = 2^9 * 5^9. For all of you who found the first one too easy, try this one. 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. Good luck! Send answers to me and if you get the answer, buy yourself a Mars bar! Mark Gilje stolaf!gilje w
dgc@ucla-cs.UUCP (10/12/84)
>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. This problem appeared in the Fifteenth William Lowell Putnam Mathematical Competition, held on March 5, 1955. This is a university level competition, sponsored by the Mathematical Association of America. Among former winners and "honorable mentioners" are some of the most distinguished mathematicians and physicsists of today. 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 David G. Cantor Arpa: dgc@ucla-locus.arpa UUCP: ...!{cepu, ihnp4, randvax, sdcrdcf, trwspp, ucbvax}!ucla-cs!dgc
thomas@utah-gr.UUCP (Spencer W. Thomas) (10/19/84)
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. =S
jhputtick@watrose.UUCP (James Puttick) (10/22/84)
The problem stated 'n-gon', not 'regular n-gon'. Thus, for a regular hexagon, there will indeed be just one point of intersection; but with a bit of work we can make a 6-sided figure with the appropriate nuymber of intersections. I don't believe 'n-gon' implies regularity.
chuck@dartvax.UUCP (Chuck Simmons) (10/23/84)
<Someone should put a stop light at that intersection!> >> >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. >> >>...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"... > >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. There are only 13 intersections if it is a regular hexagon. It seems reasonable that for arbitrary n-gons, we should be able to find some skewed irregular version which has all "n choose 4" intersections. But it would be soothing to see a simple proof that this is so. Unfortunately, my math isn't that good. -- Chuck dartvax!chuck __ / \ / \ / / \____/ Now if this was a mac, I could draw the intersections.
dgc@ucla-cs.UUCP (10/30/84)
------------------------------------------------------------------------ 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