lee@ukma.UUCP (Carl Lee) (02/11/86)
L. Victor Allis writes: >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 ? I was delighted to read your note about partitioning space, since it has always been one of my favorite problems. When I was in high school, I saw a film made by Polya, who used this problem to illustrate his principles of mathematical discovery. There is a nice treatment of this in his book, Mathematics and Plausible Reasoning, Volume 1 (Induction and Analogy in Mathematics), Princeton, 1973, pp.43-52 and 54. Consider the formula R(2,j) = R(2,j-1) + R(1,j-1). The basic idea is that when you add a new jth line in general position, the increase in the number of regions equals the number of old regions that are split by the new line, which in turn equals the number of pieces that the new line is divided up into by the intersections with the old j-1 lines (and these intersections are, of course, points). Similarly with the formula R(3,j) = R(3,j-1) + R(2,j-1). When you add a new jth plane in general position, the increase in the number of regions equals the number of old regions that are split by the new plane, which in turn equals the number of pieces that the new plane is divided up into by the intersections with the old j-1 planes (and these intersections are lines). Once you know R(n+1,j) = R(n+1,j-1) + R(n,j-1), R(1,i) = i+1 and R(n,0) = 1, you can figure out the formulas for R(2,j) and R(3,j) fairly easily. Then with the aid of a good guess or a simple application of the calculus of finite differences, you can arrive at the formula R(n,j) = 1 + j/1! + j(j-1)/2! + j(j-1)(j-2)/3! + ... + j(j-1)...(j-n+1)/n! which is easy to prove by induction once you have it. Now, looking at R(n,2n+1), we see that it equals 1 + (2n+1)/1! + (2n+1)(2n)/2! + ... + (2n+1)(2n)...(n+2)/n! which equals 2n+1 2n+1 2n+1 ( ) + ( ) + ... + ( ) 0 1 n But this is half of the sum 2n+1 2n+1 2n+1 2n+1 2n+1 ( ) + ( ) + ... + ( ) + ( ) + ... + ( ) = 2**(2n+1) 0 1 n n+1 2n+1 (e.g., see Pascal's triangle). Carl W. Lee, Department of Mathematics, University of Kentucky cbosgd!ukma!lee lee@UKMA.BITNET lee@uky.csnet