 All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars  perplexus dot info  Ant highway with energy loss (Posted on 2018-08-24) 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?

 No Solution Yet Submitted by Jer No Rating Comments: ( Back to comment list | You must be logged in to post comments.) heuristic computer solution | Comment 2 of 9 | 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:

The above link seems no longer to be working. The Wikipedia article is here.

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\$

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 Please log in:

 Search: Search body:
Forums (1)