A322740 -id:A322740 - cp's OEIS frontend

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

Bert Dobbelaere, Apr 30 2018

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

			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)

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

For optimal Golomb rulers, see A003022.

Cf. A193838, A193839, A271490, A322740.

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

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

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

A322742 Sorted list of 120 distinct triangle areas corresponding to the unique solution to the problem of placing 10 points on a grid rectangle of minimal area, such that all triangles formed by any 3 of the points have distinct areas > 0.

Original entry on oeis.org

1, 2, 3, 4, 7, 8, 9, 14, 15, 19, 20, 21, 23, 24, 26, 27, 28, 30, 31, 33, 34, 35, 36, 37, 39, 40, 42, 43, 45, 46, 47, 49, 50, 52, 53, 55, 56, 58, 59, 61, 65, 67, 68, 69, 70, 74, 75, 77, 78, 79, 80, 81, 84, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 100, 101, 106, 107, 111

Offset: 1

Hugo Pfoertner, Dec 24 2018

The sequence gives the areas multiplied by 2.
For more information see A322740.
The coordinates of the 10 grid points on the minimal 19 X 18 rectangle are (0,3), (1,9), (2,18), (5,0), (5,10), (12,17), (15,13), (17,4), (18,0), (19,5).

Hugo Pfoertner, Table of n, a(n) for n = 1..120

Cf. A303331, A322740, A322741.

X=[0,1,2,5,5,12,15,17,18,19];Y=[3,9,18,0,10,17,13,4,0,5];n=0;a=vector(binomial(#X,3));for(i=1,#X-2,for(j=i+1,#X-1,for(k=j+1,#X,a[n++]=X[i]*(Y[j]-Y[k])+X[j]*(Y[k]-Y[i])+X[k]*(Y[i]-Y[j]))))
vecsort(abs(a))

A322741 Sorted list of 84 distinct triangle areas corresponding to the unique solution to the problem of placing 9 points on a grid rectangle of minimal area, such that all triangles formed by any 3 of the points have distinct areas > 0.

Original entry on oeis.org

1, 3, 4, 6, 8, 9, 11, 12, 13, 15, 16, 17, 18, 19, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 33, 34, 39, 42, 43, 44, 45, 46, 48, 49, 50, 51, 54, 56, 58, 59, 64, 66, 67, 70, 73, 80, 87, 91, 92, 94, 95, 98, 99, 100, 104, 106, 107, 110, 113, 114, 116, 117, 121, 123, 127, 130, 132, 134, 139, 140, 141, 143, 145, 146, 148, 152, 156, 159, 161, 162, 168, 174, 178

Offset: 1

Hugo Pfoertner, Dec 24 2018

The sequence gives the areas multiplied by 2.
For more information see A322740.
The coordinates of the 9 grid points on the minimal 18 X 11 rectangle are (0,3), (1,9), (2,0), (3,10), (4,11), (12,2), (17,11), (18,1), (18,4).

Cf. A303331, A322740, A322742.

X=[0,1,2,3,4,12,17,18,18];Y=[3,9,0,10,11,2,11,1,4];n=0;a=vector(binomial(#X, 3)); for(i=1, #X-2, for(j=i+1, #X-1, for(k=j+1, #X, a[n++]=X[i]*(Y[j]-Y[k])+X[j]*(Y[k]-Y[i])+X[k]*(Y[i]-Y[j]))))
vecsort(abs(a))

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

A322742 Sorted list of 120 distinct triangle areas corresponding to the unique solution to the problem of placing 10 points on a grid rectangle of minimal area, such that all triangles formed by any 3 of the points have distinct areas > 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A322741 Sorted list of 84 distinct triangle areas corresponding to the unique solution to the problem of placing 9 points on a grid rectangle of minimal area, such that all triangles formed by any 3 of the points have distinct areas > 0.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI