wu :: forums
« wu :: forums - no-3-on-a-line gridpoint clusters »

Welcome, Guest. Please Login or Register.
Mar 28th, 2024, 7:36am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: Eigenray, SMQ, Icarus, william wu, ThudnBlunder, Grimbal, towr)
   no-3-on-a-line gridpoint clusters
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: no-3-on-a-line gridpoint clusters  (Read 621 times)
JocK
Uberpuzzler
*****






   


Gender: male
Posts: 877
no-3-on-a-line gridpoint clusters  
« on: Jan 29th, 2005, 4:27pm »
Quote Quote Modify 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

Email

Re: no-3-on-a-line gridpoint clusters  
« Reply #1 on: Jan 30th, 2005, 11:52am »
Quote Quote Modify Modify Remove 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: male
Posts: 877
Re: no-3-on-a-line gridpoint clusters  
« Reply #2 on: Jan 30th, 2005, 12:33pm »
Quote Quote Modify 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

Email

Re: no-3-on-a-line gridpoint clusters  
« Reply #3 on: Jan 30th, 2005, 3:04pm »
Quote Quote Modify Modify Remove 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: male
Posts: 877
Re: no-3-on-a-line gridpoint clusters  
« Reply #4 on: Jan 31st, 2005, 1:04pm »
Quote Quote Modify 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.
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board