An ant starts at the origin of the coordinate plane. The ant only has enough energy to walk for 10 units along either the x- or y-axis before stopping. These lines are the two ant highways.
However, if it goes off the highway, more energy is needed for the same distance. That is, the further the ant deviates, the greater the energy consumption, as represented by the factor 1+0.4d, where d is the distance to the nearest highway. For example, if the ant is 1 unit away from the nearest highway, it uses 1.4 times the energy on the highway to walk 1 meter.
What is the area of the set of points the ant can reach before getting tired and stopping?
The problem is analogous (even isomorphic) to the paths of rays of light in a medium with an index of refraction gradient.
There's a technical paper that's above my head:
So I wrote a program of numeric integration based on calculating light ray paths using Huygen's wavelets. Two points on the wave front (the ant's left and right legs) are used to calculate the speed. The average of these two is the speed, and the difference is used to change the ant's direction. The variable delta is used both to set the distance between the ant's feet and the energy the ant uses in one iteration.
DefDbl A-Z
Dim crlf$
Private Sub Form_Load()
Form1.Visible = True
pi = Atn(1) * 4
Text1.Text = ""
crlf = Chr$(13) + Chr$(10)
ScaleHeight = ScaleHeight * 1.3
ScaleWidth = ScaleWidth * 1.3
delta = 0.001
For y = 0 To 20
If y = 10 Then
c = 0
Else
c = RGB(60, 255, 60)
End If
Line (1, y + 1)-(21, y + 1), c
Line (y + 1, 1)-(y + 1, 21), c
Next
prevx = 99999
px = 0
For veerY = 0.01 To 10 - delta / 2 Step delta
For off0 = 0 To 0
used = veerY
y = veerY
offVert = off0
x = delta / 2
Do
xL = x - Cos(offVert) * delta / 2
xR = x + Cos(offVert) * delta / 2
yL = y + Sin(offVert) * delta / 2
yR = y - Sin(offVert) * delta / 2
speedL = 1 / (1 + 0.4 * xL)
speedR = 1 / (1 + 0.4 * xR)
speed = (speedL + speedR) / 2
theta = Atn((speedL - speedR))
xNew = x + speed * Sin(offVert) * delta / 2
yNew = y + speed * Cos(offVert) * delta / 2
offVert = offVert + 2 * theta
xNew = xNew + speed * Sin(offVert) * delta / 2
yNew = yNew + speed * Cos(offVert) * delta / 2
' Line (x + 11, 11 - y)-(xNew + 11, 11 - yNew), 0
plotLine x, y, xNew, yNew
xSav = x: ySav = y
x = xNew
y = yNew
used = used + delta
Loop Until used >= 10 Or x > y
If used >= 10 Then
If Int(x / 0.1) < prevx Then
prevx = Int(x / 0.1)
Text1.Text = Text1.Text & x & " " & 10 - y & " " & (10 - y) / x ^ (1.6) & " " & Sqr(1 - x * x / 100) & crlf
End If
If px = 0 Then
px = x
Else
fract = (10 - used) / delta
x = xSav + fract * (xNew - xSav)
y = ySav + fract * (yNew - ySav)
totArea = totArea + (px - x) * (y - x)
px = x
End If
End If
Next off0
DoEvents
Next veerY
Text1.Text = Text1.Text & crlf & totArea & " " & totArea * 8
Text1.Text = Text1.Text & crlf & " done"
End Sub
Sub plotLine(x1, y1, x2, y2)
xx1 = x1: xx2 = x2: yy1 = y1: yy2 = y2
Line (xx1 + 11, 11 - yy1)-(xx2 + 11, 11 - yy2), 0
xx1 = -xx1: xx2 = -xx2
Line (xx1 + 11, 11 - yy1)-(xx2 + 11, 11 - yy2), RGB(60, 60, 255)
yy1 = -yy1: yy2 = -yy2
Line (xx1 + 11, 11 - yy1)-(xx2 + 11, 11 - yy2), RGB(60, 60, 255)
xx1 = -xx1: xx2 = -xx2
Line (xx1 + 11, 11 - yy1)-(xx2 + 11, 11 - yy2), RGB(60, 60, 255)
xx1 = y1: xx2 = y2: yy1 = x1: yy2 = x2
Line (xx1 + 11, 11 - yy1)-(xx2 + 11, 11 - yy2), RGB(60, 60, 255)
xx1 = -xx1: xx2 = -xx2
Line (xx1 + 11, 11 - yy1)-(xx2 + 11, 11 - yy2), RGB(60, 60, 255)
yy1 = -yy1: yy2 = -yy2
Line (xx1 + 11, 11 - yy1)-(xx2 + 11, 11 - yy2), RGB(60, 60, 255)
xx1 = -xx1: xx2 = -xx2
Line (xx1 + 11, 11 - yy1)-(xx2 + 11, 11 - yy2), RGB(60, 60, 255)
End Sub
The octant area and total area found are shown for differing finenesses of delta:
With delta = .01:
22.6942848049259 181.554278439407
With delta = .003:
22.7268654467222 181.814923573778
With delta = .001:
22.7364579195898 181.891663356719
With delta = .0003:
22.7398039990453 181.918431992363
The calculations were done in the black area. The uncolored area near the origin was also counted as the numeric integration was from the curve at the top of the black area to the line y=x, as the uncolored area is accessible to the ant by going directly to any point in it (though a curved path would be quicker, it would not be one starting along--or really near-- and then tangent to a road).
From the above, I'd estimate the area asked for is about 181.9. Complicating things is the fact that the Riemann sums' rectangle heights are based on the low end of the function in that range of x values.
With the rectangle heights alternating low and high values and delta = .003, the octant and total areas are
22.7274128046052 181.819302436841
and with delta = .001,
22.7369897744468 181.895918195574
I'd say the area sought is between 181.9 and 182.0.
The second illustration shows separate individual paths. In this case the paths are continued beyond the line y=x (not included in the program producing the first illustration, so as not to duplicate areas) showing that when so extended they curve back but don't go beyond the original area, so we didn't undercount. The cusp of the closest points to the origin do seem to be at or about 4,4.
Going from the origin at a 45° angle or other angle fills in the lens shaped areas near the origin, but does not add outside the already demarcated outer bounds.
The curve does not seem to be a conic section or any polynomial. The outer extremities seem to be pointed rather than rounded (i.e., discontinuous slope or tangent line). Wondering about the shape made me think of seeing what a continuation of the boundary might be: what if there were only one ant highway and the speed (or energy expenditure) depended only on the x coordinate? You can
click here to see it. It's certainly not a conic or any polynomial plot, indicating even the portion used in the actual puzzle (with y coordinate over about 4.0) together with its 90° flip is not, also.
Edited on August 24, 2018, 6:50 pm
|
|
Posted by Charlie
on 2018-08-24 18:42:13 |
heuristic computer solution
