| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 202.1 | | SPRITE::OSMAN | | Mon Jan 28 1985 12:50 | 3 |
| As a motivating hint, and the reason I find the problem interesting, is the
fact that n is larger than 2 but smaller than infinity. Anyone know
the answer. Anyone have an intuitive explanation ?
|
| 202.2 | | R2ME2::GILBERT | | Mon Jan 28 1985 17:55 | 3 |
| It's interesting that the number is larger than 6 and less than infinity.
Also, I can think of no simple, efficient program to find the number.
Care to post yours?
|
| 202.3 | | SPRITE::OSMAN | | Wed Jan 30 1985 09:55 | 22 |
| It took me awhile to come up with a computer program to solve the n points
on a line problem. The resultant program isn't complicated, however.
What took awhile was figuring out how to explain the problem to a computer.
Every time I tried to come up with a program and failed, I went back to
trying solving it the "old fashioned" way :
Now, let's see. We can put the first two points such that
0<p1<1/2 and 1/2<p2<1
Now we'll slide p1 over a bit to make room for p3. So
0<p1<1/3 and 1/3<p3<1/2 and 1/2<p2<1
etc.
After going through this exercise a number of times, I finally organized
my thinking enough to be able to write a program.
If this hint doesn't help, I'll be glad to post my program.
|
| 202.4 | | TURTLE::GILBERT | | Wed Jan 30 1985 13:34 | 6 |
| Unless I misunderstand the original problem, ...
There are actually three places where p3 could be placed (since p1 and p2
divide the line into three segments). Then there are four places where
p4 can be placed, and five for p5, .... The recursive descent program for
this should really burn CPU time.
|
| 202.5 | | SPRITE::OSMAN | | Wed Jan 30 1985 15:04 | 7 |
| The recursion turns out to be not as gruesome as that. What happens is
that by the time you get up to six or so, instead of there being seven
places to try, five of them have been reduced to negative sizes, and
hence you only have to investigate two.
This fact may actually lead to the intuitive explanation we're looking
for !
|
| 202.6 | | SPRITE::OSMAN | | Thu Jun 13 1985 17:41 | 15 |
| I've posted the source and executable for the program that solves the
points-on-the-line problem.
You can copy and run it from
TOOLS::SYS$NOTES:POINTS.EXE.
Please let me know if it fails to run.
The source is there too. It's
TOOLS::SYS$NOTES:POINTS.B32
/Eric
|
| 202.7 | | TURTLE::GILBERT | | Thu Jun 13 1985 19:38 | 7 |
| The following should provide a more precise re-statement of the problem.
Find the largest n for which an n-tuple of values (p , p ,..., p ) exists,
0 1 n-1
such that 0 < p < 1, and the set { [kp ] | i<k } = { i | i<k } for all k < n,
i i
where [x] is the greatest integer not exceeding x.
|
| 202.8 | | JARETH::EDP | Always mount a scratch monkey. | Mon Oct 22 1990 17:32 | 7 |
| At the math dinner on 19 October 1990, Stan gave us the answer to this
one. 16 such numbers can be found, but 17 cannot. Reference:
Berlekamp and Graham, "Irregularities in the Distributions of Finite
Sequences", _Journal of Number Theory_ 2 (1970): 152-161.
-- edp
|
| 202.9 | Stan is wrong, 17 numbers can be found... | HANNAH::OSMAN | see HANNAH::IGLOO$:[OSMAN]ERIC.VT240 | Thu Nov 01 1990 16:09 | 27 |
| ...and have been found, by my 1983 Bliss program that still runs today !
On our vax, the program exhausted all possibilities in less than 15 minutes,
and proved that 18 numbers can't be found, but 17 can. This is the same
program mentioned above that I wrote back in 1983.
Here are the 17 numbers:
Place 17 points as follows:
(0) 0/1 < P1 < 1/17
(9) 7/13 < P2 < 6/11
(14) 11/13 < P3 < 6/7
(4) 4/15 < P4 < 3/11
(12) 12/17 < P5 < 5/7
(7) 5/12 < P6 < 3/7
(15) 12/13 < P7 < 13/14
(2) 2/15 < P8 < 1/7
(10) 8/13 < P9 < 5/8
(5) 1/3 < P10 < 6/17
(13) 10/13 < P11 < 11/14
(3) 1/5 < P12 < 3/14
(8) 8/17 < P13 < 1/2
(16) 16/17 < P14 < 1/1
(1) 1/15 < P15 < 2/17
(11) 11/17 < P16 < 11/16
(6) 6/17 < P17 < 7/17
|
| 202.10 | | JARETH::EDP | Always mount a scratch monkey. | Mon Nov 05 1990 09:58 | 6 |
| Re .9:
I checked; the numbers look good. Now you must publish.
-- edp
|
| 202.11 | maybe we're both right | HANNAH::OSMAN | see HANNAH::IGLOO$:[OSMAN]ERIC.VT240 | Tue Nov 06 1990 16:32 | 23 |
|
Except that Scientific American already published it.
The history is, I read an article in Scientific American (Gardner or
Hoftstaedter), which said that 18 points can not be found.
Then I wrote my program which confirmed that result, by exhaustively failing
to find 18 points, but finding 17 points.
The 17 points as output by my program are those illustrated above.
So... my findings agree with what was already published, so either Stan
misquoted, or we misinterpreted Stan, or Stan read an erroneous source.
There is the possibility that we misinterpreted Stan. I forget his
equation, but if it said n=0 through n=16, then perhaps the QUANTITY of
points being 17 goes with the LABEL n=16, in which case the largest possible
n is 16 which corresponsds with the largest number of points which is
17.
I don't have the replies in front of me (I'm typing in the dark so to speak).
/Eric
|