Problem 6.3 A robot named Wall-E wanders around a two-dimensional grid. He starts out at (D, 0) and is allowed to take four different types of steps: 1. (+2,1) 2. (+1,2) 3. (+l,+l) 4. (-341) Thus, for example, Wall-E might walk as follows. The types of his steps are listed above the arrows. 3 2 4 (Cum5 (2,1)(3,0)(4,2)~ (1,_2)_..._ Wall-E's true love, the fashionable and high-powered robot, Eve, awaits at (0, 2). (a) Describe a state machine model of this problem. Make sure to indicate what are the states and what are the transitions. (b) Will Wall-E ever nd his true love? If yes, nd a path from Wall-E to Eve. If no, use the Invariant Principle to prove that no such path exists, being sure to clearly state and prove your preserved invariant. Hint: The value x y is not preserved, but how can it change? Problem 7.8 Let m,n be integers, not both zero. Dene a set of integers, Lm'm recursively as follows: - Base cases: m,n E In\". ' Constructor cases: If j, k E me then 1. j E Lm'", 2. j + k E Lm'\". Let L be an abbreviation for Lm'" in the rest of this problem. (a) Prove by structural induction that every common divisor of m and in also divides every member of L. (b) Prove that any integer multiple of an element of L is also in L. (C) Show that if j,k E L and k 1: 0, then rem(j,k) E L. ((1) Show that there is a positive integer g E L that divides every member of L. Hint: The least positive integer in L. (e) Conclude that g from part (d) is ged(m,n), the greatest common divisor, of m and n