October 2018

[LaurV]

Hm... according with what the talk is talking here, I may have to waste my weekend playing with triangles... (didn't start yet, but it is really tempting!)

[axn]

Originally Posted by bsquared

(on the max-sized grid)

There is no "the" max-sized grid, right? If I'm not mistaken, these are the allowable grids (of points).

10x67
11x61
12x55
13x51
14x47
15x43
16x41
17x38
18x36
19x34
20x32
21x31
22x29
23x28
24x27
25x26

[a1call]

Find a solution for N=11 and the L1*L2<=600.

Largest near square grid is a matrix of 25x24=600
Largest maximally elongated possible grid is a matrix of 6x100.

For 6 <= L1 <=100
L2 <= 600\L1

[axn]

Originally Posted by a1call

Largest near square grid is a matrix of 25x24=600
Largest maximally elongated possible grid is a matrix of 6x100.

For 6 <= L1 <=100
L2 = 600\L1

Right, that's the length of the grid. I'm talking about the points. n points x m points = (n-1) length x (m-1) length

Also, for placing N points successfully, you'll need at least (N-1) points x (N-1) points grid.

[a1call]

There are only 11 points placed on a grid with a maximum of 600 cells. Any 3 point subset of the 11 points forms a triangle. There are 165 different 3-combinations of 11 points, forming 165 triangles none of which may have the same area as any other.

[bsquared]

Originally Posted by axn

There is no "the" max-sized grid, right? If I'm not mistaken, these are the allowable grids (of points).

10x67
11x61
12x55
13x51
14x47
15x43
16x41
17x38
18x36
19x34
20x32
21x31
22x29
23x28
24x27
25x26

Yes, you're right. I used L1,L2 = 23,26, corresponding to your 24x27 grid of points. I haven't tried the more elongated ones yet, maybe I should.

Best solution so far is now at 163 on the dimension 23x26 grid.

[LaurV]

Scratch that! I am stupid! (I thought I solved it)

(advantages of being supermod, haha, can remove posts where my mouth was talking without me...)

[Batalov]

It is a fun puzzle!
A solution for n points contains n (n-1)-point solutions in it.

Without the L1*L2<=600 constraint it is easy to find a sparse set, e.g.
[[26,11], [32,10], [0,24], [17,0], [34,6], [32,18], [2,14], [31,2], [7,3], [21,25], [10,25]]

Now, need to tighten the cage...

[Batalov]

Tightening the solution "from above".

I have a few S=700 solutions, S=663 and an S=644 solution...

[a1call]

Just not to have misdirected anyone, it's not clear to me if the grid size of L1xL2<=600 is based on the L's being counted from 0 or 1.
If the former then an actual grid cell number of 26x25=650 or less would be valid.

[Batalov]

Originally Posted by a1call

Just not to have misdirected anyone, it's not clear to me if the grid size of L1xL2<=600 is based on the L's being counted from 0 or 1.
If the former then an actual grid cell number of 26x25=650 or less would be valid.

It is perfectly clear when you follow the worked example for (note) 3x3 N=4 solution.
Because it uses dots with coordinates ranging from 0 to 3, you have your answer right there.

It is like a Go board: for which the grid has only 18x18 squares (in terms of this IBM problem, its area is 324), but you can use 19x19 positions to put a stone!