Using the Invariant Principle to prove a coordinate can't be reached

Dec 2019
2
0
Nigeria
An object moves on the two-dimensional integer grid. It starts out at (0,0) and is allowed to move in any of these four ways: 1. (+2,-1): Up 2, Left 1 2. (-2,+1): Down 2, Right I 3. (+1, +3): Up 1, Right 3 4. (-1,-3): Down 1, Left 3 (a) Describe how this situation can be modeled as a state machine. (b) Use the Invariant Principle to prove that this object can never reach (1,1).
 

Attachments

skipjack

Forum Staff
Dec 2006
21,481
2,470
The robot has coordinates (x, y) = m(1, -2) + n(3, 1), where m and n are integers (each move changes m by 1 or n by 1).

As 2x + y = 7n is always divisible by 7, x = y = 1 can't occur.
 
Dec 2019
2
0
Nigeria
The robot has coordinates (x, y) = m(1, -2) + n(3, 1), where m and n are integers (each move changes m by 1 or n by 1).

As 2x + y = 7n is always divisible by 7, x = y = 1 can't occur.
Thanks for your quick response, can you please explain better. I don't understand the divisible part
 

romsek

Math Team
Sep 2015
2,961
1,674
USA
The robot has coordinates (x, y) = m(1, -2) + n(3, 1), where m and n are integers (each move changes m by 1 or n by 1).

As 2x + y = 7n is always divisible by 7, x = y = 1 can't occur.
I think you've got the x and y coordinates reversed.

x + 2y = 7n, not vice versa.

For OP, skipjack has shown that for any valid position (x, y), x + 2y = 7n, i.e. is a multiple of 7.

So is (1,1) a valid position?

1 + 2(1) = 3, which is not a multiple of 7, so (1,1) is not a valid position.
 

skipjack

Forum Staff
Dec 2006
21,481
2,470
I think you've got the x and y coordinates reversed.
That's a matter of interpretation. I initially used (y, x) coordinates, as the initial post seemed to be using "up" and "down" in relation to the first coordinate, but I decided that switching to writing (x, y) would be clearer, with "up" and "down" still relating to y.