What is the maximum number of parts into which 3-dimensional space can be divided by 5 planes?

[ Editor: The discussion started from the series 1 2 4 8 16 31 57 99 163 256
  386 562 ..., the number of regions into which a circle is cut when n
  points on it are each joined to every other point (no three lines
  meeting at a point); it looks like the powers of 2 until it fails at
  31. ]

In the selections for the International Mathematical Olympiad [Editor:
"Mathematics Olympiade" in the original] a problem I had to solve was
[ Editor: the one above for 5 planes; the original quotes it as "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 n-dimensional space can be divided into [Editor: "kan
be divided in" in the original] 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 into [Editor: "in" in the original] 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

  j =  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

[ Editor: the row label is "i" in the original; powers written 2**k in
  the original are written 2^k here, also in the next contribution. ]

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

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
   <lee@UKMA.BITNET>