|
%I #41 Dec 26 2018 11:57:25
%S 0,1,1,2,4,6,9,11,15,19
%N a(n) is the minimum size of a square integer grid allowing all triples of n points to form triangles of different areas.
%C 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.)
%C 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).
%C 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.
%C 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.
%C a(11) <= 24, a(12) <= 29. - _Hugo Pfoertner_, Nov 05 2018
%H IBM Research, <a href="https://www.research.ibm.com/haifa/ponderthis/challenges/October2018.html">Ponder This Challenge October 2018</a>. Similar problem for rectangular grids.
%F a(n+1) >= a(n) (trivial).
%F a(n) >= sqrt(n*(n-1)*(n-2)/6) for n >= 2 (proven lower bound).
%e 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.
%e From _Jon E. Schoenfield_, Apr 30 2018: (Start)
%e Illustration of the above solution:
%e vertices area
%e 4 1 . . . . -------- ----
%e 1 2 3 2.5
%e 3 . . . 4 5 1 2 4 4.0
%e 1 2 5 5.5
%e 2 . . . . . 1 3 4 4.5
%e 1 3 5 6.5
%e 1 . 2 . . . 1 4 5 0.5
%e 2 3 4 3.0
%e 0 . . . 3 . 2 3 5 3.5
%e y 2 4 5 1.0
%e x 0 1 2 3 4 3 4 5 1.5
%e (End)
%o (Python)
%o def addNewAreas(plist, used_areas):
%o ....# Attempt to add last point in plist. 'used_areas' contains all (areas*2)
%o ....# between preplaced points and is updated
%o ....m=len(plist)
%o ....for i in range(m-2):
%o ........for j in range(i+1,m-1):
%o ............k=m-1
%o ............p,q,r=plist[i],plist[j],plist[k]
%o ............# Area = s/2 - using s enables us to use integers
%o ............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])
%o ............if s<0:
%o ................s=-s
%o ............if s in used_areas:
%o ................return False # Area not unique
%o ............else:
%o ................used_areas[s]=True
%o ....return True
%o def solveRecursively(n, L, plist, used_areas):
%o ....m=len(plist)
%o ....if m==n:
%o ........#print plist (uncomment to show solution)
%o ........return True
%o ....newlist=plist+[None]
%o ....if m>0:
%o ........startidx=(L+1)*plist[m-1][0] + plist[m-1][1] + 1
%o ....else:
%o ........startidx=0
%o ....for idx in range(startidx, (L+1)**2):
%o ............newlist[m]=( idx/(L+1) , idx%(L+1) )
%o ............newareas=dict(used_areas)
%o ............if addNewAreas(newlist, newareas):
%o ................if solveRecursively(n, L, newlist, newareas):
%o ....................return True
%o ....return False
%o def A303331(n):
%o ....L=0
%o ....while not solveRecursively(n, L, [], {0:True}):
%o ........L+=1
%o ....return L
%o def A303331_list(N):
%o ....return [A303331(n) for n in range(1,N+1)]
%o # _Bert Dobbelaere_, May 01 2018
%Y For optimal Golomb rulers, see A003022.
%Y Cf. A193838, A193839, A271490, A322740.
%K nonn,hard,more
%O 1,4
%A _Bert Dobbelaere_, Apr 30 2018
| 