A303331 a(n) is the minimum size of a square integer grid allowing all triples of n points to form triangles of different areas.

0, 1, 1, 2, 4, 6, 9, 11, 15, 19

Offset

1,4

Comments

Place n points on integer coordinates of a square grid of dimension L x L, so that no 3 points are collinear and the areas of the triangles formed by the binomial(n,3) possible triples are all different. a(n) is the minimum L for which this can be achieved. (Note that there are (L+1)^2 lattice points.)

The fact that all triangle areas are multiples of 1/2 and the maximum area supported by the grid is L^2/2 provides us with a lower bound for a(n).

The problem can be considered a 2-dimensional extension of a Golomb ruler and scales to higher dimensions. In general, consider k points on integer coordinates of a D-dimensional hypercube, forming binomial(k,D+1) D-simplices of which the volumes are all different. For D = 1, we recognize the Golomb ruler; for D = 2, we have the problem defined above.

Just like for Costas arrays (another 2-D extension of Golomb rulers), no 2 displacement vectors can be identical, as the diagonal of a parallelogram cuts the shape in triangles of identical area.

a(11) <= 24, a(12) <= 29. - Hugo Pfoertner, Nov 05 2018

Links

Table of n, a(n) for n=1..10.

IBM Research, Ponder This Challenge October 2018. Similar problem for rectangular grids.

Formula

a(n+1) >= a(n) (trivial).

a(n) >= sqrt(n*(n-1)*(n-2)/6) for n >= 2 (proven lower bound).

Example

For n = 5, a solution satisfying unequal triangle areas is {(0,4),(1,1),(3,0),(3,3),(4,3)}, which can be verified by considering the binomial(5,3) = 10 possible triangles by selecting vertices from this set. Each coordinate is contained in the range [0..4]. No smaller solution is possible without creating areas that are no longer unique, hence a(5) = 4.
From Jon E. Schoenfield, Apr 30 2018: (Start)
Illustration of the above solution:
                        vertices   area
  4   1  .  .  .  .     --------   ----
                          1 2 3     2.5
  3   .  .  .  4  5       1 2 4     4.0
                          1 2 5     5.5
  2   .  .  .  .  .       1 3 4     4.5
                          1 3 5     6.5
  1   .  2  .  .  .       1 4 5     0.5
                          2 3 4     3.0
  0   .  .  .  3  .       2 3 5     3.5
  y                       2 4 5     1.0
    x 0  1  2  3  4       3 4 5     1.5
(End)

Prog

(Python)
def addNewAreas(plist, used_areas):
....# Attempt to add last point in plist. 'used_areas' contains all (areas*2)
....# between preplaced points and is updated
....m=len(plist)
....for i in range(m-2):
........for j in range(i+1, m-1):
............k=m-1
............p, q, r=plist[i], plist[j], plist[k]
............# Area = s/2 - using s enables us to use integers
............s=(p[0]*q[1]-p[1]*q[0]) + (q[0]*r[1]-q[1]*r[0]) + (r[0]*p[1]-r[1]*p[0])
............if s<0:
................s=-s
............if s in used_areas:
................return False # Area not unique
............else:
................used_areas[s]=True
....return True
def solveRecursively(n, L, plist, used_areas):
....m=len(plist)
....if m==n:
........#print plist (uncomment to show solution)
........return True
....newlist=plist+[None]
....if m>0:
........startidx=(L+1)*plist[m-1][0] + plist[m-1][1] + 1
....else:
........startidx=0
....for idx in range(startidx, (L+1)**2):
............newlist[m]=( idx/(L+1) , idx%(L+1) )
............newareas=dict(used_areas)
............if addNewAreas(newlist, newareas):
................if solveRecursively(n, L, newlist, newareas):
....................return True
....return False
def A303331(n):
....L=0
....while not solveRecursively(n, L, [], {0:True}):
........L+=1
....return L
def A303331_list(N):
....return [A303331(n) for n in range(1, N+1)]
# Bert Dobbelaere, May 01 2018

Crossrefs

For optimal Golomb rulers, see A003022.

Cf. A193838, A193839, A271490, A322740.

Sequence in context: A300416 A353134 A038107 * A233776 A195526 A153196

Adjacent sequences: A303328 A303329 A303330 * A303332 A303333 A303334

Keyword

nonn,hard,more

Author

Bert Dobbelaere, Apr 30 2018

Status

approved