robertj@garfield.UUCP (01/31/86)
This posting regards the poster who asked the persons on net.math to find the sum of the sequence 1 + 3 + 6 + 10 + 15 + ....... +an presumably this meant that he wanted us to find the sum of the sequence defined recursively as: a1 = 1 ak = a(k-1) + k 1<k<=n and it was the sum k=n _____ - _ ak _ ______ k = 1 which was desired. The tricky part of this though is not finding the sum but making the leap of faith to the above given definition of the sequence ( this is probably what the test wanted however ). The interesting thing here is that there is no truly mathematical way to make this jump ( at least not that I have heard of ) and I would like to exhibit a famous ( but hopefully not too famous example of where the obvious breaks down ). 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. The "correct" answer (in this sense) is "31". However any IQ test in which you answered "31" you would probably be put down as a low-grade moron then and there so when in doubt answer "32" ! Any other interesting sequences with both intuitive and counter- intuitive but "natural" continuations ( random sequences are not interesting in other words, use your intuition as to what I mean ). Robert Janes
verma@ucla-cs.UUCP (02/02/86)
In article <748@garfield.UUCP> robertj@garfield.UUCP (Robert Janes) writes: >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. No matter how hard I tried, I could not get eight. With four I could get as high as eleven, not thirty-two. Please tell me what you are talking about... TS Verma
rvdb@hou2c.UUCP (R.VANDERBEI) (02/04/86)
> 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. > The "correct" answer (in this sense) is "31". > However any IQ test in which you answered "31" you would probably be put > down as a low-grade moron then and there so when in doubt answer "32" ! > > Robert Janes It seems to me that the sequence breaks down when k=3 and n=7. Perhaps you meant to state the same problem for a sphere in 4-space using hyperplanes for lines.
lambert@boring.UUCP (02/05/86)
In article <8675@ucla-cs.ARPA> verma@ucla-cs.UUCP (Thomas S. Verma ) writes: > In article <748@garfield.UUCP> robertj@garfield.UUCP (Robert Janes) writes: >> 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. [...] > Please tell me what you are talking about... Undoubtedly, robertj was referring to the sequence mentioned in article <1226@lll-crg.ARpA> by cralle@lll-crg.UUCP (R.(Bob) K. Cralle): > [...] and so the series goes: > 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.) -- Lambert Meertens ...!{seismo,okstate,garfield,decvax,philabs}!lambert@mcvax.UUCP CWI (Centre for Mathematics and Computer Science), Amsterdam
ins_akaa@jhunix.UUCP (02/06/86)
>> 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. >> The "correct" answer (in this sense) is "31". >> Robert Janes >It seems to me that the sequence breaks down when k=3 and n=7. >Perhaps you meant to state the same problem for a sphere in 4-space >using hyperplanes for lines. No, the question should be where n is the same as above, k is 1,2,3, etc..., and instead of k being the number of lines, k is the number of points on the circle's edge; these points are all connected to each other and the resulting lines divide the circle into the n regions. -- "We are going to give a little something, a few little years more, to socialism, because socialism is defunct. It dies all by iself. The bad thing is that socialism, being a victim of its... Did I say socialism?" -Fidel Castro Kenneth Arromdee BITNET: G46I4701 at JHUVM and INS_AKAA at JHUVMS CSNET: ins_akaa@jhunix.CSNET ARPA: ins_akaa%jhunix@hopkins.ARPA UUCP: ...allegra!hopkins!jhunix!ins_akaa
victor@klipper.UUCP (02/06/86)
>>> 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
tim@ism780c.UUCP (Tim Smith) (02/06/86)
I believe he meant to select k points on the circle, and connect them in all possible ways. Then you get the sequence 1,2,4,8,16,31,etc ( assuming no three lines intersect at a common point inside the circle ). -- Tim Smith sdcrdcf!ism780c!tim || ima!ism780!tim || ihnp4!cithep!tim
rab@well.UUCP (Bob Bickford) (02/06/86)
. In article <595@hou2c.UUCP>, rvdb@hou2c.UUCP writes: > > > It seems to me that the sequence breaks down when k=3 and n=7. > Perhaps you meant to state the same problem for a sphere in 4-space > using hyperplanes for lines. | | . . . . . . . | . .. | . 2 . . | . . . . | . 1 . . 3 . | . . . . . ... . . ... . . . . . . | . . 5 . . | . . . . | . 4 . 6 . | . . . . | . . . . | . . . . | . . 7 . . | . . .. | . . . . . . . . .. | I think you get the idea. Sorry I can't do a better circle on short notice....... The lines obviously don't have to cross as near the center as I have drawn them. Robert Bickford (rab@well.uucp) ================================================ | I doubt if these are even my own opinions. | ================================================
rab@well.UUCP (Bob Bickford) (02/06/86)
.
okay, I admit it, I wasn't answering the question as asked.
fifty lashes with a wet noodle!
Now then, how *do* you get eight sections with three lines?
Robert Bickford (rab@well.uucp)
================================================
| I doubt if these are even my own opinions. |
================================================mikeb@natmlab.OZ (Michael Buckley) (02/26/86)
>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.