Skip to content
Quantoros

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

Related questions