From: Severian Subject: Re: Contest problem Date: Fri, 10 Mar 2000 18:11:45 +0000 Newsgroups: sci.math Summary: [missing] Carl Johan wrote: > > I would be interested in insights on the following contest problem (from the > USA mathematical olympiad around 1980 I believe, though I am not certain)! > Especially interesting to me would be solutions using the following theorem > though I have got stuck myself trying to use it. > > Theorem: In R(n), S(1),S(2)...S(m), being convex sets, are given, each n+1 > having a common point. Then all m sets have a common point. This is Helly's theorem. -- Severian --------------------------------------------------------------- Victor Meldrew: "The police can use sperm now as a way of fingerprinting people." Mrs Warboys: "I don't see what was wrong with the old inkpads." --------------------------------------------------------------- David Renwick, _One Foot in the Grave_ ============================================================================== From: rino Subject: Re: Contest problem Date: Fri, 10 Mar 2000 11:39:49 -0800 Newsgroups: sci.math In article <8ab689$6nn$1@merkurius.lu.se>, "Carl Johan" wrote: >Theorem: In R(n), S(1),S(2)...S(m), being convex sets, are given, each n+1 >having a common point. Then all m sets have a common point. Helly's theorem, explained for 3 D case at http://nrich.maths.org.uk/mathsf/journalf/aams/q71.html The method to extend to more dimensions is similar. * Sent from RemarQ http://www.remarq.com The Internet's Discussion Network * The fastest and easiest way to search and participate in Usenet - Free! ============================================================================== From: matthew thomas gealy Subject: Re: Contest problem Date: Fri, 10 Mar 2000 13:45:29 -0600 Newsgroups: sci.math > Theorem: In R(n), S(1),S(2)...S(m), being convex sets, are given, each n+1 > having a common point. Then all m sets have a common point. We also want m >= n+1, clearly Proof for S(i) closed; the general case shouldn't be much harder: Induct. The statement is trivial for n=1, as convex sets are intervals. The statement is similarly trivial if m = n+1, for any n Consider a collection S(1), ... , S(m+1) satisfying the property. Inductively, S(1), ... , S(m) all have a point in common. Call their intersection T; T is convex and non-empty. Suppose S(1), ... , S(m+1) have no point in common. Then T and S(m+1) are disjoint closed convex sets. By a version of Hahn-Banach, we may find a hyperplane P disjoint from both and separating them. Now any n of S(1), ... , S(m) have a common point inside of S(m+1), so using convexity and connecting to T, any n of S(1), ... , S(m) have a common point inside of P. But now S(1) intersect P, ... , S(m) intersect P satisfy the inductive hyposthesis in P=R^(n-1), so we conclude that S(1), ... , S(m) have a point in common in P. This contradicts the disjointness of P and T, so all of S(1), ... , S(m+1) have a point in common. I'm not sure if you would consider Hahn-Banach to be an extremal principal or not; it certainly relies heavily on the convexity of the sets, but there is nothing explicitly so. Matthew ============================================================================== From: "Carl Johan" Subject: Re: Contest problem Date: Sat, 11 Mar 2000 10:26:19 +0100 Newsgroups: sci.math I know that is Hellys theorem. Thanks for pointers on it and how to prove it anyway. As you see in my first post, that is presented as a theorem, something I know, and what I wish to deduce is instead: Problem: On the real line, some sets S(1),S(2)...,S(n) are given each being the union of 2 closed intervals. Each 3 have a common point. Prove that some point is common to at least half of the intervals! This is not Hellys theorem, and I'm not sure it can be deduced using it, but it would be interesting for me to see any solution of this problem, particuarly if is is possible to use Hellys theorem! /cjr