Olympiad workbook
- Exam
- Olympiad workbook
- Subject
- IOQM
- Chapter
- Straight Lines
Olympiad workbook · IOQM · Straight Lines
A bug travels in the coordinate plane moving only along the lines...
A bug travels in the coordinate plane moving only along the lines that are parallel to the axis or axis. Let and . Consider all possible paths of the bug from to of length at most 14 . How many points with integer coordinates lie on at least one of these paths?

Correct answer
87
Step-by-step solution
Least number of steps required to move from to is 10 . Let we denote any step towards positive axis by and negative -axis by .

So all steps are the permutations of . In this way, all points of the rectangular grid are covered. If we introduce one step in negative axis or positive axis, movement will be completed in 12 steps. Similarly, if we introduce two steps in negative -axis or in positive -axis or one in each direction the movement will be completed in 14 steps (maximum allowed).
Maximum number of points with integer coordinates
So all steps are the permutations of . In this way, all points of the rectangular grid are covered. If we introduce one step in negative axis or positive axis, movement will be completed in 12 steps. Similarly, if we introduce two steps in negative -axis or in positive -axis or one in each direction the movement will be completed in 14 steps (maximum allowed).
Maximum number of points with integer coordinates