wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> no-3-on-a-line gridpoint clusters
        
(Message started by: JocK on Jan 29^th, 2005, 4:27pm)

Title: no-3-on-a-line gridpoint clusters
Post by JocK on Jan 29^th, 2005, 4:27pm

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 (x_j, y_j) can be written:

S = N^-1 [sum]_j=1..N [(x_j-X)² + (y_j-Y)²]

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.

Title: Re: no-3-on-a-line gridpoint clusters
Post by packo on Jan 30^th, 2005, 11:52am

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.

[hide]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...[/hide]

Title: Re: no-3-on-a-line gridpoint clusters
Post by JocK on Jan 30^th, 2005, 12:33pm

on 01/30/05 at 11:52:41, 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 ::[hide] 24 S = N² - 4 [/hide]:: ... ;)

Nice work!

Title: Re: no-3-on-a-line gridpoint clusters
Post by packo on Jan 30^th, 2005, 3:04pm

oops, forgot about those...got 'em now, don't you think?

[hide] {"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"}[/hide]

Title: Re: no-3-on-a-line gridpoint clusters
Post by JocK on Jan 31^st, 2005, 1:04pm

on 01/30/05 at 15:04:29, 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 = N² - 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?