Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!mhuxn!ihnp4!houxm!whuxl!whuxlm!akgua!gatech!seismo!mcvax!vu44!botter!klipper!victor
From: victor@klipper.UUCP
Newsgroups: net.math
Subject: Re: Counter-Intuitive Sequences (+ Problem)
Message-ID: <541@klipper.UUCP>
Date: Wed, 5-Feb-86 21:21:51 EST
Article-I.D.: klipper.541
Posted: Wed Feb  5 21:21:51 1986
Date-Received: Sun, 9-Feb-86 07:13:15 EST
References: <748@garfield.UUCP> <8675@ucla-cs.ARPA> <6761@boring.UUCP>
Reply-To: victor@klipper.UUCP (L. Victor Allis)
Organization: VU Informatica, Amsterdam
Lines: 63

>>> Consider the following sequence: 1, 2, 4, 8, 16,.... what is the next term?	
>>> Invariably the response is "32".
>>> This however does not have to be the case and an alternate sequence arises
>>> very naturally. Consider the sequence of n where n is the number of regions
>>> the interior of a circle can be divided into using k lines where k starts
>>> at 0. If you do that for the first five k you get the above sequence.
>>> Suggestive isn't it ? However it turns out that for k=6 n=31 and the 
>>> intuitive result falls flat on its face.
>> 
>> I do not understand what you mean.  I drew a circle.  I saw one region.
>> I then drew a chord.  I saw two regions.  I drew another chord.  I saw
>> four regions.  Now the third chord could go in two non-isomorphic places.
>> One gave six regions, the other gave seven.  [...]
>
>> 1 2 4 8 16 31 57 99 163 256 386 562...  [isn't the 256 curious--one late!]
>
>> What does the series represent? If you have n points on a circle & and you
>> connect every point to every other point the series gives the number of areas
>> those lines cut the circle into. (more than two lines intersecting at a point
>> not allowed.)

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