Ant on a Triangular Grid

Geometry Level 5

If an ant starts on a vertex of a grid composed of equilateral triangles (whose bases run east and west) and crawls the shortest route to a point that is 8 triangle bases east and 4 triangle heights north of its starting point, then it will pass through 16 equilateral triangles:

Find the number of triangles an ant will pass through if it crawls the shortest route to a point that is 1000 triangle bases east and 550 triangle heights north of its starting point instead.

Inspiration


The answer is 2500.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

David Vreken
Dec 14, 2019

On a square grid, an ant that crawls x x units east and y y units north for relatively prime x x and y y will pass through a total of 1 1 starting square (colored gray below), x 1 x - 1 squares to the right of each vertical intersection (colored blue below), and y 1 y - 1 squares above each horizontal intersection (colored green below) for a total of S = 1 + ( x 1 ) + ( y 1 ) = x + y 1 S = 1 + (x - 1) + (y - 1) = x + y - 1 squares.

If x and y are not relatively prime, the diagram can be split up into gcd ( x , y ) \gcd(x, y) identical x gcd ( x , y ) × y gcd ( x , y ) \frac{x}{\gcd(x, y)} \times \frac{y}{\gcd(x, y)} rectangles.

Applying the above equation, the number of squares the ant would pass through is S = gcd ( x , y ) × ( x gcd ( x , y ) + y gcd ( x , y ) 1 ) S = \gcd(x, y) \times (\frac{x}{\gcd(x, y)} + \frac{y}{\gcd(x, y)} - 1) or

S = x + y gcd ( x , y ) S = x + y - \gcd(x, y)

A equilateral triangular grid can be transformed into a square grid, where each square is 2 2 triangles, and the number of triangular bases east is reduced to x 1 2 y x - \frac{1}{2}y squares east.

Substituting x 1 2 y x - \frac{1}{2}y and y y into the equation above and multiplying it by 2 2 , the number of triangles that ant would pass through is T = 2 ( ( x 1 2 y ) + y gcd ( x 1 2 y , y ) ) T = 2((x - \frac{1}{2}y) + y - \gcd(x - \frac{1}{2}y, y)) or

T = 2 x + y 2 gcd ( x 1 2 y , y ) T = 2x + y - 2 \cdot \gcd(x - \frac{1}{2}y, y)

Therefore, for x = 1000 x = 1000 and y = 550 y = 550 , the ant would pass through T = 2 1000 + 550 2 gcd ( 1000 1 2 550 , 550 ) = 2500 T = 2 \cdot 1000 + 550 - 2 \cdot \gcd(1000 - \frac{1}{2} \cdot 550, 550) = \boxed{2500} triangles.

I got 2400.... not by ths method, this is a good method

Nikola Alfredi - 1 year, 5 months ago
Chris Lewis
Dec 11, 2019

The ant enters a new triangle every time it crosses a line. Things are trickier if the ant's path hits an intersection in the grid - but we get around that by splitting the path up at these points. The ant first hits an intersection after crawling 40 40 triangles east and 22 22 triangles north (bonus question: why not 20 20 triangles east and 11 11 triangles north?). During this journey, it crosses 21 21 east-west lines, 39 39 NW-SE (ish) lines, and 40 40 SW-NE (ish) lines, entering a total of 21 + 39 + 40 = 100 21+39+40=100 triangles on its way. It then repeats this path 24 24 more times, for a total of 25 × 100 = 2500 25 \times 100=\boxed{2500} triangles along its path.

Why not 22??

Aatmoshru Goswami - 1 year, 5 months ago

Really nice solution! One comment: The ant crosses many more NW-SE lines than SW-NE lines. In the picture provided for the 8 × 4 8 \times 4 grid, you can count 10 10 of the first type and 6 6 of the second type (perhaps adjusting slightly for the starting and ending points).

For the 40 × 22 40 \times 22 grid example, there are 40 + 22 / 2 = 51 40 + 22/2 = 51 NW-SE lines and 40 22 / 2 = 29 40 - 22/2 = 29 SW-NE lines, rather than 40 40 of each. So the count is more like 21 + 50 + 29 = 100 21 + 50 + 29 = 100 than 21 + 39 + 40 = 100 21 + 39 + 40 = 100 .

Matthew Feig - 1 year, 5 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...