A robot starts at (0,0) and may move by (±1,±1). Can it reach (1,0)? Characterize all reachable integer points.
Quant ResearchLevel: FoundationReachability invariant
A robot starts at (0,0) and may move by (±1,±1). Can it reach (1,0)? Characterize all reachable integer points.
Hints
- Look at parity rather than distance.
- Express a target in the two diagonal basis vectors.
Answer
Every move changes x and y parity together, so x+y remains even. Thus (1,0) is impossible. Conversely if x,y have equal parity, use (x+y)/2 moves along (1,1) and (x-y)/2 along (1,-1), reversing directions for negative counts.
Source and licence: Lehman, Leighton & Meyer — Mathematics for Computer Science (2018-06-06) · CC-BY-SA-3.0 · answer: Quantoros editorial