All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Ant highway (Posted on 2018-08-17)
An ant is at a crossroads of a square grid of highways spaced 1 meter apart.

The ant can walk 1 meter in 15 seconds along a highway, but off-road it can only travel half as fast.

Find the area of the region composed of all points the ant can reach in at most 30 seconds.

Note: an ant highway is just a line with no thickness.

 No Solution Yet Submitted by Jer No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 No Subject | Comment 2 of 3 |
My first thought was that when a path crossed a highway there would be a section of highway travelled before the walking resumed offroad. The angle would be such that Snell's law would dictate what in an optical medium would be total internal reflection, which in this case would be an angle of 30° with the normal to the highway. Tabulating travel times varying the angle confirms 30° from the normal (i.e., 60° to the highway). But instead of reflection, it would follow the highway.

Then I thought about multiple highway crossings. An angle can't be 30° to the normal to each of two orthogonal lines. Some playing around with numbers led me to the conclusion that the fastest way to traverse one unit square would be to go to the intersection and make a right-angle turn. This results in never going farther than one of the four adjacent blocks or one of the eight blocks that are adjacent along a side to those four closer blocks.

The program first considers the eight blocks that are not immediately adjacent to the ant. It considers only one half of one of these blocks, the dividing line being the diagonal bisecting the two highway blocks that the ant might take along its periphery. The fraction of this triangle is the same as the fraction of the square, by symmetry. In turn it is the fraction of each of the squares.

Next it considers the fraction of each inner block. Again only half of each block is considered. In this case the time is calculated using two paths: one directly from the initial highway the ant is on, and one via a right-angle turn onto a second highway. Whichever is faster is compared to a time limit of 2 units of time (15-second units).

By the way I used squares of side length 1, and speeds of 2 (on road) and 1 (off road). The 15 seconds is irrelevant. The program considers the whole possible area (4 nearest squares plus the 8 that are adjacent sharing an edge) point by point, to be included within the shape.

Form1.Visible = True

pi = Atn(1) * 4
angle = pi / 6

Text1.Text = ""
crlf = Chr\$(13) + Chr\$(10)

delta = 0.005
For xsupp = delta / 2 To 1 Step delta
For y = delta / 2 To xsupp Step delta
t = (1 + xsupp) - y * Tan(angle) + 2 * y / Cos(angle)
If t <= 2 Then
goodct = goodct + 1
PSet (3 - (1 + xsupp), 3 - y), 0
PSet (3 - (1 + y), 3 - xsupp), 0
PSet (3 - (1 + xsupp), 3 + y), 0
PSet (3 - (1 + y), 3 + xsupp), 0
PSet (3 + (1 + xsupp), 3 - y), 0
PSet (3 + (1 + y), 3 - xsupp), 0
PSet (3 + (1 + xsupp), 3 + y), 0
PSet (3 + (1 + y), 3 + xsupp), 0

PSet (3 - y, 3 - (1 + xsupp)), 0
PSet (3 - xsupp, 3 - (1 + y)), 0
PSet (3 - y, 3 + (1 + xsupp)), 0
PSet (3 - xsupp, 3 + (1 + y)), 0
PSet (3 + y, 3 - (1 + xsupp)), 0
PSet (3 + xsupp, 3 - (1 + y)), 0
PSet (3 + y, 3 + (1 + xsupp)), 0
PSet (3 + xsupp, 3 + (1 + y)), 0

Else
PSet (3 - (1 + xsupp), 3 - y), RGB(255, 255, 100)
PSet (3 - (1 + y), 3 - xsupp), RGB(255, 255, 100)
PSet (3 - (1 + xsupp), 3 + y), RGB(255, 255, 100)
PSet (3 - (1 + y), 3 + xsupp), RGB(255, 255, 100)
PSet (3 + (1 + xsupp), 3 - y), RGB(255, 255, 100)
PSet (3 + (1 + y), 3 - xsupp), RGB(255, 255, 100)
PSet (3 + (1 + xsupp), 3 + y), RGB(255, 255, 100)
PSet (3 + (1 + y), 3 + xsupp), RGB(255, 255, 100)

PSet (3 - y, 3 - (1 + xsupp)), RGB(255, 255, 100)
PSet (3 - xsupp, 3 - (1 + y)), RGB(255, 255, 100)
PSet (3 - y, 3 + (1 + xsupp)), RGB(255, 255, 100)
PSet (3 - xsupp, 3 + (1 + y)), RGB(255, 255, 100)
PSet (3 + y, 3 - (1 + xsupp)), RGB(255, 255, 100)
PSet (3 + xsupp, 3 - (1 + y)), RGB(255, 255, 100)
PSet (3 + y, 3 + (1 + xsupp)), RGB(255, 255, 100)
PSet (3 + xsupp, 3 + (1 + y)), RGB(255, 255, 100)
End If
totct = totct + 1
DoEvents
Next
Next

Text1.Text = Text1.Text & crlf & goodct / totct

For x = delta / 2 To 1 Step delta
For y = delta / 2 To x Step delta
t1 = 1 + y - (1 - x) * Tan(angle) + 2 * (1 - x) / Cos(angle)
t2 = 2 * y / Cos(angle) + x - y * Tan(angle)
If t2 < t1 Then
t = t2
c = RGB(90, 90, 255)
Else
t = t1
c = 0
End If
If t <= 2 Then
goodctInner = goodctInner + 1
Else
c = RGB(255, 255, 100)
End If
totctInner = totctInner + 1
PSet (3 - x, 3 - y), c
PSet (3 + x, 3 - y), c
PSet (3 - x, 3 + y), c
PSet (3 + x, 3 + y), c
PSet (3 - y, 3 - x), c
PSet (3 + y, 3 - x), c
PSet (3 - y, 3 + x), c
PSet (3 + y, 3 + x), c

Next
Next

Text1.Text = Text1.Text & crlf & 4 * goodctInner / totctInner
Text1.Text = Text1.Text & crlf & 4 * goodctInner / totctInner + 8 * goodct / totct

Text1.Text = Text1.Text & crlf & " done"

End Sub

The text output of the program using delta = 0.0005 is:
0.366206866206866
3.85693985693986
6.78659478659479

The first number is the fraction of each of the outer eight blocks that is part of the area, compared with a calculated (see below) 1/(1+sqrt(3)) ~= .366025403784438.

The second number is the total area of the inner four blocks that is part of the shape; it's about 0.143 units less than the 4 that it would be if all parts of the blocks were included.

The third line shows the total area of the shape as 6.786 or 6.787. I'm sure someone can work out the shapes involved and calculate a more precise answer.

The picture (click here) shows the twelve blocks with eligible points. Areas not part of the shape are shown in yellow; areas that are part of the shape are either black or blue. The points in the blue areas are accessible to the ants by using only a portion of one unit of highway, while the black areas require the ant to go all the way to the end of his nearest block and continue along another segment before going offroad; some may be accessible either way, and are included in the blue area. Going offroad is always at a 60° angle (30° off 90°). The only points within the inner four blocks are in the four kites of inaccessability in the four corners.

Two other graphs further illustrate and explain the shape:

the areas accessible only by going directly to the ant's own nearest highway block are still shown in blue

but

the areas that are accessible either by going directly off the ant's nearest highway or by going all the way to the end of the block, making a right-angle turn and then going off road (ant's choice), are shown in a greyish color.

Areas requiring two segments (linear blocks) are still black.

Looking at the graph, I see straight lines forming equilateral triangles from which I deduce that the outer eight blocks contribute 8/(1+sqrt(3)) ~=  2.92820323027551 to the area of the figure. As mentioned above, the central four blocks add an area of 3.857, bringing the total area of the shape to  6.785 square meters. (I trust this better than the counting-pixels method above, as at least a part of the answer is calculated geometrically.)

Later calculation (all geometric, based on observation):

Each of the four chunks taken out of the corners of the central 2x2 area seems to be two hypotenuse-to-hypotenuse right triangles one of whose angles is 15° and whose longer leg is sqrt(3)*(1-1/sqrt(3))/2, so its (that is, the right triangle's) area is 3*((1-1/sqrt(3))/2)^2 / 2 * tan(15°). As there are four chunks, each with two of these right triangles the total taken out of the central area of 4 is 12*((1-1/sqrt(3))/2)^2 * tan(15°) ~= .143593539448981, making the contribution of the central four squares 4 - .143593539448981 = 3.85640646055102.

The overall area of the shape is then

8/(1+sqrt(3)) + 4 - 12*((1-1/sqrt(3))/2)^2 * tan(15°) ~= 6.78460969082653.

 Posted by Charlie on 2018-08-17 14:23:48

 Search: Search body:
Forums (2)