Author |
Topic: no-3-on-a-line gridpoint clusters (Read 657 times) |
|
JocK
Uberpuzzler
Gender: 
Posts: 877
|
 |
no-3-on-a-line gridpoint clusters
« on: Jan 29th, 2005, 4:27pm » |
 Quote  Modify
|
You are asked to place N points on a square grid such that:
a) no three points line up (i.e. no three co-linear points), and
b) the size S of the cluster (the square of the radius of gyration*) is as small as possible
For N = 4, 6 and 8 one obtains the following optimal configurations:
o o
o o N = 4, S = 1/2
o o .
o . o
. o o N = 6, S = 4/3
. o o .
o . . o
o . . o
. o o . N = 8, S = 5/2
Question 1 (not so hard):
Can you find a cluster of 12 points with size S < 6 ?
Question 2 (somewhat harder):
Can you find a cluster of 20 points with size S < 17 ?
Question 3 (ultra hard):
How does S(N) behave asymptotically for N [to] [infty] ?
---------------------
* The square of the radius of gyration of N points with integer coordinates (xj, yj) can be written:
S = N-1 [sum]j=1..N [(xj-X)2 + (yj-Y)2]
where (X,Y) denotes the centre of gravity (average of the x- and y-coordinates of all N points). For simple symmetrical patterns like the three depicted above, the centre of gravity coincides with the cluster centre of symmetry.
|
| « Last Edit: Jan 30th, 2005, 12:38pm by JocK » |
 IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
packo
Guest
|
|
Re: no-3-on-a-line gridpoint clusters
« Reply #1 on: Jan 30th, 2005, 11:52am » |
Quote Modify
 Remove
|
I have some difficulties to understand the mathematical translation of your definition for the cluster size. I fact, I don't think they say the same.
In the first case (N=4) and with te first equation, you would calculate 16 square distances (some of these are distances between non-pairs, i.e. the distance between one point) and divide it by 32. S=0.5
What I see, is 6 pairs (4 with distance 1 and 2 with square distance 2). In my opinion, using your definition results in S=4/3. Also the simplification seems a bit fishy to me.
If I'm not correct, please explain (I'm still just a student ;)).
I did solve the problem (only using symmetrical grids), using your equation, I think. At least the grids will stay the same, but S-values would be different.
N=12
S=35/6
S(my idea)=160/28
{"0", "1", "0", "0", "1", "0"},
{"0", "0", "1", "1", "0", "0"},
{"1", "0", "0", "0", "0", "1"},
{"1", "0", "0", "0", "0", "1"},
{"0", "0", "1", "1", "0", "0"},
{"0", "1", "0", "0", "1", "0"}
N=20
S=33/2
S(my idea)=842/66
{"0", "1", "0", "1", "0", "0", "0", "0", "0", "0"},
{"0", "0", "0", "0", "1", "0", "0", "0", "0", "1"},
{"0", "0", "1", "0", "0", "0", "0", "1", "0", "0"},
{"0", "0", "0", "0", "1", "0", "0", "0", "0", "1"},
{"0", "0", "0", "0", "0", "0", "1", "0", "1", "0"},
{"0", "1", "0", "1", "0", "0", "0", "0", "0", "0"},
{"1", "0", "0", "0", "0", "1", "0", "0", "0", "0"},
{"0", "0", "1", "0", "0", "0", "0", "1", "0", "0"},
{"1", "0", "0", "0", "0", "1", "0", "0", "0", "0"},
{"0", "0", "0", "0", "0", "0", "1", "0", "1", "0"}
Your relation (for symmetrical grids) would be as follows:
S = (1/24)*N^2 - 1/6
The relation for mine is a bit more difficult, so I'll take a look at that later, maybe...
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: no-3-on-a-line gridpoint clusters
« Reply #2 on: Jan 30th, 2005, 12:33pm » |
Quote Modify
|
on Jan 30th, 2005, 11:52am, packo wrote:I have some difficulties to understand the mathematical translation of your definition for the cluster size. I fact, I don't think they say the same.
|
|
I think the equations are correct, but you are right that things are stated confusingly. (In particular it is confusing to relate the size to the average square distance between pairs, as indeed the definition requires the inclusion of 'pairs' of the same point.)
I will simplify the problem statement accordingly.
As far as your patterns are concerned: these are not correct. On several instances more than two points are aligned (along lattice directions corresponding to knight moves).
I will react later to the equation you mentioned :: 24 S = N2 - 4 :: ... ;)
Nice work!
|
| « Last Edit: Jan 30th, 2005, 12:34pm by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
packo
Guest
|
|
Re: no-3-on-a-line gridpoint clusters
« Reply #3 on: Jan 30th, 2005, 3:04pm » |
Quote Modify
Remove
|
oops, forgot about those...got 'em now, don't you think?
{"0", "1", "0", "1", "0", "0"},
{"0", "0", "0", "1", "0", "1"},
{"1", "1", "0", "0", "0", "0"},
{"0", "0", "0", "0", "1", "1"},
{"1", "0", "1", "0", "0", "0"},
{"0", "0", "1", "0", "1", "0"}
{"0", "0", "0", "0", "1", "1", "0", "0", "0", "0"},
{"0", "0", "1", "0", "0", "0", "0", "1", "0", "0"},
{"0", "1", "0", "0", "0", "0", "0", "0", "1", "0"},
{"0", "0", "0", "1", "0", "0", "1", "0", "0", "0"},
{"1", "0", "0", "0", "0", "0", "0", "0", "0", "1"},
{"1", "0", "0", "0", "0", "0", "0", "0", "0", "1"},
{"0", "0", "0", "1", "0", "0", "1", "0", "0", "0"},
{"0", "1", "0", "0", "0", "0", "0", "0", "1", "0"},
{"0", "0", "1", "0", "0", "0", "0", "1", "0", "0"},
{"0", "0", "0", "0", "1", "1", "0", "0", "0", "0"}
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: no-3-on-a-line gridpoint clusters
« Reply #4 on: Jan 31st, 2005, 1:04pm » |
Quote Modify
|
on Jan 30th, 2005, 3:04pm, packo wrote:...got 'em now, don't you think?
|
|
Excellent!
- Are these the only solutions, or are alternative patterns with the same size possible?
- What makes you think patterns with smaller size are not possible?
- All above patterns (N = 4, 6, 8, 12 and 20) satisfy 24 S = N2 - 4. But does the same relationship hold for all N? What about odd N? And what about the asymptotic values for large N? Anything you can prove in this context?
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print