Try
A robot stands at an integer grid point. One command moves it two units right and one up; another moves it one right and two up. Write these displacement vectors as u=(2,1) and v=(1,2). For now the grid has no walls, obstacles or forbidden intermediate coordinates.
Starting at the origin, can it reach (1,1)? Both commands increase the sum of the coordinates by 3, while the requested point has sum 2. No amount of trying different command orders can repair that mismatch. This is an obstruction proved for every finite route, not merely a failure to find a route in a limited search.
Now ask about (0,3). Its coordinate sum passes the same check. Does that guarantee a route? Keep your answer tentative until the rules specify whether reverse commands are available.
Predict
Compare two models. In the forward-only model, commands are u and v. In the reversible model, commands also include −u and −v. Predict which model reaches (0,3), and whether reversing a command changes the remainder of the coordinate sum modulo 3.
An invariant is a property preserved by every allowed move. Here it is the remainder of x+y, not the value of x+y itself. A reverse command changes the sum by −3 and therefore preserves the same remainder. From an arbitrary starting point S, compare the target sum with the sum at S; testing every target against remainder zero would incorrectly assume that every route starts at the origin.
Experiment
Build this route with arrows on squared paper. Each row is a state, not just a final answer. Label the reverse command explicitly.
| Command just taken | State | Coordinate sum | Remainder modulo 3 |
|---|
| Start | (0,0) | 0 | 0 |
|---|
| v | (1,2) | 3 | 0 |
|---|
| v | (2,4) | 6 | 0 |
|---|
| −u | (0,3) | 3 | 0 |
|---|
Thus the reversible model succeeds. The forward-only model cannot take the last command. Prove impossibility there without assuming that this particular route was the only candidate: any nonempty forward route increases the first coordinate, whereas the target first coordinate is zero.
Change the target to (5,4). Three forward commands work: u,u,v. Reverse their order and inspect which intermediate states change. Vector addition explains the shared endpoint; it does not say that the intermediate route is identical.
Understand
Let (x,y) now denote displacement from the chosen start, not necessarily the absolute target coordinates. If m and n are the net counts of u and v, the endpoint equations are 2m+n=x and m+2n=y. Solving by subtraction gives
m=(2x−y)/3, n=(2y−x)/3.
In the reversible model these counts may be negative. If x+y is divisible by 3, then 2x−y=3x−(x+y) and 2y−x=3y−(x+y) are divisible by 3 too. Both counts are integers. Take m forward u commands when m is positive, or −m reverse u commands when it is negative; do the analogous construction for n. This is a finite legal route because all integer intermediate states are permitted. Together with the invariant argument, it proves both necessity and sufficiency: reversible reachability is equivalent to the displacement sum being divisible by 3.
In the forward-only model, actual command counts must be nonnegative. The complete criterion is therefore the same divisibility condition together with 2x−y≥0 and 2y−x≥0. Necessity follows from the equations for any route; sufficiency follows by executing the resulting nonnegative counts. This is a constructive theorem, stronger than checking a preserved remainder.
For displacement (0,3), the equations give m=−1,n=2, explaining precisely why reverses help. For (5,4), they give m=2,n=1. Net coefficients are uniquely determined because these two linear equations have a unique solution. The order of commands need not be unique, and a reversible route can add cancelling command pairs without changing its net coefficients.
Do not transfer this sufficiency proof to a board with walls without checking it. For example, restrict states to the square with coordinates between 0 and 2. From (0,2), every one of the four possible first commands exits that square. The target (2,0) has the same sum and an unrestricted route, yet is unreachable on this board. The modular obstruction remains necessary; the construction of intermediate states has failed.
Apply
Start at (2,−1) and target (6,4). First compute displacement (4,5); do not apply the formulas to (6,4). Its coefficients are m=1,n=2, so a forward route exists and has three commands. Check one ordered route and then justify why every forward route has that same number of commands.
Next replace the generators by (3,1) and (1,3). The sum remainder modulo 4 is preserved, but (2,2) is not reachable even with reverse moves: solving the equations requires half a command of each kind. Derive the actual integer-coefficient criterion in practice. The lesson is not that invariants are unreliable; it is that a necessary invariant must be paired with a separate sufficiency proof before being called a complete classification.
Continue
For each new reachability problem, write the allowed state set and both the permitted and forbidden directions before searching. Then separate three obligations: prove an obstruction, solve for candidate move counts, and verify a legal route under the actual intermediate-state restrictions. Finite experiments can suggest the invariant and expose counterexamples. The general proof explains why the conclusion holds beyond every tested route.
