Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!watmath!clyde!burl!ulysses!bellcore!decvax!genrad!panda!talcott!harvard!seismo!munnari!natmlab!mikeb From: mikeb@natmlab.OZ (Michael Buckley) Newsgroups: net.math Subject: Re: Counter-Intuitive Sequences (+ Problem) Message-ID: <387@natmlab.OZ> Date: Wed, 26-Feb-86 00:31:21 EST Article-I.D.: natmlab.387 Posted: Wed Feb 26 00:31:21 1986 Date-Received: Sat, 1-Mar-86 00:53:43 EST References: <748@garfield.UUCP> <8675@ucla-cs.ARPA> <6761@boring.UUCP> <541@klipper.UUCP> Reply-To: mikeb@natmlab.UUCP (Michael Buckley) Organization: CSIRO Div Maths and Stats & Div App Phys, Sydney, Australia Lines: 114 >In the selections for the International Mathematics Olympiade a problem I >had to solve was : > > What is the maximum number of different parts the 3-dimensional > space kan be divided in by 5 planes. > >The answer is 26. > >The way I found that is the following. >Let R(n,j) be the number of parts the n-dimensional space kan be divided in >by j hyperplanes. Then : > > R(n+1,j) = R(n+1,j-1) + R(n,j-1). (1) > R(1,i) = i+1 (2) > R(n,0) = 1 (3) > >(2) is obvious, considering a line divided in i+1 sections by i points. >(3) is even more obvious, since the undivided space is one part. >(1) is the thing I just 'saw'. Since I was only 14 years old at that time, >and only the answer was required I did not have to prove it. > >Thus: > > n = 1 2 3 4 5 > > i = 0 1 1 1 1 1 > 1 2 2 2 2 2 > 2 3 4 4 4 4 > 3 4 7 8 8 8 > 4 5 11 15 16 16 > 5 6 16 26 31 32 > 6 7 22 42 57 63 > >At the moment I do not see how to prove it (It is 02.00 am), but I am *sure* >the formula is right. Who can prove that ??? >The above given series is exactly the one for n = 4. > >By the way, it seems that R(n, 2n+1) = 2**(2n). Any proofs ? > >L. Victor Allis >Free University of Amsterdam >The Netherlands Carl Lee has already pointed out that (1), (2) and (3) can be used to prove by induction that j j j j R(n,j) = ( ) + ( ) + ( ) + ............ + ( ) (4) 0 1 2 n and that (1) can be justified by considering the number of regions cut into two parts by a new hyperplane. This derivation of (4) has appeared in the mathematical literature; see references below as well as those in Watson (1966). It is possible to prove (4) a little more directly as follows. First note that the maximum number of regions, R(n,j), will be acheived by any set of j hyperplanes P(1), P(2), ...., P(j) for which these two conditions hold - (A) No two of the hyperplanes ar parallel and (B) All of the j-choose-n points of intersection of the hyperplanes are distinct. Let x(1), x(2), ..., x(n) be Cartesian coordinates of points in our n-space and let I(i) be the 'x(1)-x(2)-...-x(i-1)-x(i+1)-...-x(n) hyperplane', i=1,2,...,n. That is, I(i) is the set of points for which x(i) = 0. Each I(i) is an (n-1)-dimensional hyperplane and (A) and (B) certainly hold for the set of hyperplanes I(1), I(2), ..., I(n). Shift and/or rotate P(1), P(2), ..., P(j) if necessary so that (A) and (B) hold for the n+j hyperplanes P(1), P(2), ..., P(j), I(1), I(2), ..., I(n). The origin point - x(1) = x(2) = ... = x(n) = 0 - lies on all of the planes I(i) and so cannot lie on any of the planes P(k), because of (B). Therefore this points lies in exactly one of the D(n,j) regions into which the space has been divided - it is not on a boundary. Imagine starting with this set of one point and gradually expanding it in the following way. Let it first include all points for which x(1) = x(2) = ... = x(n-1) = 0 and -a <= x(n) <= a, and let a move from 0 to infinity. A new region will be 'discovered' when and only when one of a certain set of points is included in our set. These points are those which lie on I(1), I(2), ..., I(n-1) and one of the P(k) and their number is ensured to be exactly j by (A) and (B). The number of regions now intersecting with our set (i.e. 'discovered') is 1 + j. Now expand in a second direction - include points satisfying x(1) = x(2) = ... = x(n-2) = 0 and a <= x(n-1) <= a, letting a move from 0 to infinity. A new region will be 'discovered' when and only when certain points are included in our set. These points are intersections of I(1), I(2), ..., I(n-2) and two of the P(k). There are exactly 'j-choose-2', or j(j-1)/2, of these because of (A) and (B). The number of points now discovered is 1 + j + j(j-1)/2. Continuing in this fashion we arrive at (4). Whether this derivation has been used before I don't know. The form of (4) kind of suggests it, so it probably has, I suspect. Several people have noticed that if T(j) is defined as the maximum number of regions a disc can be divided into by the j(j-1)/2 lines joining j points on its circumference then T(j-1) looks a lot like D(4,j). This is in fact true for all j, but why it should be is not at all obvious to me. REFERENCES : Harding, E.F., The number of partitions of a set of N points in k dimensions induced by hyperplanes, "Proc. Edinburgh Math. Soc." (2) 15 (1967), 285-289. Schlafli, L., "Theorie der vielfachen Kontinuitat" (Berne,1852), "Ges. Math. Abh." Vol. I, p.209 (Basel,1950). Watson, D., On partitions of N points, "Proc. Edinburgh Math. Soc." (2) 16 (1969) 263-264.