Alice has three pins, labeled A, B and C, respectively, located at the origin of the coordinate plane. In a move, Alice may move a pin to an adjacent lattice point at distance 1 away. What is the least number of moves that Alice can make in order for triangle ABC to have area 2024?
Analytic:
Assumption 1: without the grid constraint, the optimum solution would be an equilateral triangle.
Assumption 2: moving in straight lines better than zig zagging, because zig zagging only gets you √2 units for 2 zigzag moves.
Suppose you want an equilateral triangle whose points are (-a,0), (a,0) and (0,b) with Area = 2024
Distance from (a,0) to (0,b) must be 2a.
a^2 + b^2 = 4a^2
b = a√3
Area = √3*a^2 = 2024
a = √(2024/√3) ≈ 34.184
b ≈ 59.2087
Try (-34,0), (34,0) and (0,59), but this area is only 2006 < 2024
Moving either point on the x-axis increases area to 2035.5; moving the point on the y-axis increases area to 2040.
Either way, the number of moves is 34+34+59+1 = 128
----
Programmatic way:
Start with all 3 pins at the Origin.
As the triangle grows, pick the vertex with the largest angle (ie opposite the longest side), and test move it in each of the 4 directions. Whichever produces the largest area, make that the next move.
Keep a running tally of:
move number, area, (x,y) coordinates of the 3 points.
The program output finds:
128 moves, area=2035.5, (-34, 0),(0, 59),(35, 0)
def areaHeron(a,b,c):
""" input 3 float numbers, the 3 sides of a triangle
output the area """
if c >= a+b or b >= a+c or a >= b+c:
return 0
s = (a+b+c)/2 # semiperimeter
return (s*(s-a)*(s-b)*(s-c))**(1/2)
def dist(p1,p2):
"""The 2 p's are 2 element lists with x and y coordinates of points 1,2 respectively; output the distance between the two points """
return ((p2[0] - p1[0])**2 + (p2[1] - p1[1])**2 )**.5
def areaCoord(p):
""" p is list of 3 [x,y] lists; output the area of the triangle """
a = p[0]
b = p[1]
c = p[2]
return round(areaHeron(round(dist(a,b),7), round(dist(a,c),7), round(dist(b,c),7)),5)
def maxAngle(p):
a = dist(p[0],p[1])
b = dist(p[0],p[2])
c = dist(p[1],p[2])
d = max(a,b,c)
if d == a:
return 2
elif d == b:
return 1
elif d == c:
return 0
return 'error'
counter = 0
area = 0
p = [[0,0],[0,0],[0,0]]
history = [ [counter, area, p] ]
while area < 2024:
p = history[-1][2]
x = maxAngle(p)
newareas = [[],[],[],[]]
newpts = [[p[x][0]+1,p[x][1]],
[p[x][0]-1,p[x][1]],
[p[x][0],p[x][1]+1],
[p[x][0],p[x][1]-1]]
for i in range(4):
q = p[:]
q[x] = newpts[i]
newareas[i] = areaCoord(q)
bestindex = newareas.index(max(newareas))
q[x] = newpts[bestindex]
counter += 1
p = q[:]
area = areaCoord(p)
history.append([counter, area, p])
print(counter, area)
print(history[-1])
|
|
Posted by Larry
on 2025-02-26 17:39:03 |
Analytic and a program
