Maths Olympiad Prep

Library / /182 of 196

Geometry Difficulty 6.5 National Olympiad Prove it Soviet Union

Problem:
Given a lattice of regular hexagons. A bug crawls from vertex AA to vertex BB along edges of the hexagons, taking the shortest possible path (or one of them). Prove that it travels a distance at least AB/2AB/2 in one direction. If it travels exactly AB/2AB/2 in one direction, how many edges does it traverse?

Solution

Solution:

Figure 1

Suppose vertex AA is that marked * at the bottom left. Without loss of generality, BB is in a 6060 degree sector as shown. Assume the edges have unit length. The vertices can be partitioned into two sets (marked \circ and \cdot in the diagram). Each set forms a skewed lattice with axes at 6060 degrees. Any path must alternate between the two lattices.
If BB is on the same lattice as AA, then we can give BB coordinates (m,n)(m, n) relative to AA and the shortest path from AA to BB must move mm units east and nn units east of north. The shortest path between a lattice point and the next lattice point east is evidently one edge in direction 33 followed by one edge in direction 22. Similarly, the shortest path between a lattice point and the next lattice point east of north is one edge in direction 11, followed by one edge in direction 22. So a shortest path from AA to BB must have {m+n}\{m + n\} edges in direction 22.
BB is a distance 3(m+n/2)\sqrt{3}(m + n/2) east of AA and a distance 3n/23n/2 north of AA, so AB2=3m2+3mn+3n2<4m2+8mn+4n2=4(m+n)2AB^2 = 3m^2 + 3mn + 3n^2 < 4m^2 + 8mn + 4n^2 = 4(m + n)^2. So in this case the bug must travel more than AB/2AB/2 in direction 22.
Now suppose BB is on the other lattice. Let CC be the lattice point immediately north of AA and DD the lattice point in direction 33 from AA. Then a shortest path from AA to BB must either be AA to CC and then a shortest path from CC to BB, or AA to DD and then a shortest path from DD to BB. Take BB to have coordinates (m,n)(m, n) relative to CC or DD.
In the first case, AB2=(3(m+n/2))2+(3n/2+1)2=3m2+3mn+3n2+3n+1AB^2 = (\sqrt{3}(m + n/2))^2 + (3n/2 + 1)^2 = 3m^2 + 3mn + 3n^2 + 3n + 1 and a shortest path has m+nm + n units in direction 22. But 4(m+n)2>3m2+3mn+3n2+3n+14(m + n)^2 > 3m^2 + 3mn + 3n^2 + 3n + 1, if m2+n2+5mn>3n+1m^2 + n^2 + 5mn > 3n + 1, which is true for m,nm, n at least 11. If m=0m = 0 and n=1n = 1, then a shortest path has 22 units in direction 11 and AB=7<4AB = \sqrt{7} < 4. If m=1m = 1 and n=0n = 0, then AB=2AB = 2 and a shortest path has 11 unit in each direction. So in this case (the only one so far) we have equality.
It remains to consider the case where the path starts out towards DD. In this case AB2=(3(m+n/2)+3/2)2+(3n/21/2)2=3m2+3mn+3n2+3m+1AB^2 = (\sqrt{3}(m + n/2) + \sqrt{3}/2)^2 + (3n/2 - 1/2)^2 = 3m^2 + 3mn + 3n^2 + 3m + 1 and a path has m+nm + n units in direction 22. But 4(m+n)2>3m2+3mn+3n2+3m+14(m + n)^2 > 3m^2 + 3mn + 3n^2 + 3m + 1 for m2+n2+5mn>3m+1m^2 + n^2 + 5mn > 3m + 1, which is true for m,nm, n at least 11. If m=1m = 1, n=0n = 0, then a shortest path has 22 units in direction 33 and AB=7<4AB = \sqrt{7} < 4. Finally, if m=0m = 0 and n=1n = 1, then a shortest path has 11 unit in each direction and AB=2AB = 2.
Thus the answer to the final question is 33, because the only cases where the bug travels exactly AB/2AB/2 in one direction are where it goes to the opposite vertex of a hexagon it is on.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.