2
$\begingroup$

As a teenager I was given this problem which took me a few years to solve. I'd like to know if this hae ever been published. When I presented my solution I was told that it was similar to one of several he had seen.

The problem:

For an n dimensional space, develop a formula that evaluates the maximum number of n dimensional regions when divided by k n-1 dimensional (hyper)planes.

Example: A line is partitioned by points: 1 point, 2 line segments. 10 points, 11 line segments, and so one.

  • 3
    The proper term should be (hyper)plane, not boundary. Any surface can be a boundary.2010-08-11

3 Answers 3

4

Section 3 of http://www.macalester.edu/~bressoud/pub/Art_of_Counting/Art_of_Counting.pdf discusses the problem for $n=3$ and poses the problem of generalizing to higher dimensions. This article states that the first published solution was by Jakob Steiner in 1826. Other references are cited.

2

Though not discussed in the full generality you describe, the problem is discussed at length for n = 1, 2, and 3 in Mathematics for High School Teachers: An Advanced Persepective by Usiskin, Peressini, Machisotto, and Stanley (section 5.1.4; © 2003; published by Pearson Education). Specifically, the text uses that problem as an example for discussing how induction can be applied to prove the formulae using the geometry of the problem in the inductive step (when you add the next (n-1)-dimensional boundary object, how many additional regions are created?).

  • 1
    @Jamie: I should add that I had seen versions of this problem before *Mathematics for High School Teachers* was published, so it is a commonly-used problem.2010-08-11
2

I presume you are asking for the number of regions into which $n$-space is divided into by $k$ hyperplanes "in general position". See the notes of Richard Stanley on hyperplane arrangements. The answer to your problem is Proposition 2.4, and there are lots more goodies too!

  • 0
    Interestingly, it's a different Richard Stanley (MIT) than the Richard Stanley who is the 4th author on the book I cited (Berkeley).2010-08-11