Recitation 5 3 Problem: a robot A robot lives on a two dimensional grid and is free to walk around. However each move it makes is always one step north or south and one step east or west. Its purpose in life is to reach point (1,0). Unfortunately, the robot was born at point(0, 0). Prove that it will point(1,0)looks like Solution. The approach that seems reasonable is to use induction on the number n of moves made by the robot. But we must be careful in selecting the inductive hypothesis P(n). If it simply corresponds to what we want to prove -that is, if it simply is"after n steps the robot is not at point (1,0)"- we are bound to encounter the same problems as in class against the g-Number Puzzle. So, we must prove something stronger Trying out several paths that the robot might take, we soon see that the robot can reach only points that lie on the line r+y=0 and every other parallel of it. One way to describe this set of positions is to say that a point(, y)belongs to it iff the sum + y is even. We are now ready to prove the following theorem, which is stronger than the one we were asked to prove Theorem. The sum of the robots coordinates is always even Proof. The proof is by(simple) induction on the number n e n of moves made by the robot. The inductive hypothesis P(n)is this: after n moves, the sum of the robot's coor- dinates is even Base case: We show that P(O)is true. Indeed, after O steps, the robot is still at its birthpoint (0,0), and the sum of its coordinates is 0+0=0, as required Inductive step: We show that P(m) implies P(n+1), for all n E N. So, fix any n E N and assume that P() is true; that is, after its nth move, the robot is at a position(a, y) such that a +y is even. After the n+lst moves, the robot will have moved one step north or south(which changes So, if(a',y)is the new point, we have r west(which also changes its y-coordinate by 1) its X-coordinate by 1)and one step east x=x±1 o that the new sum of coordinates x+y=(x±1)+(y±1)=(x+y)+(±1)+(±1)]=(x+y)+d where d E(2,,+2. In all cases, I'+y is a sum of two even numbers. So, P(n +1) holds Therefore, by induction, P(n) is true for all n E N. The theorem holds Now, to prove that the robot never reaches point (1,0), we just need to observe that the sum 1+0=l is not evenRecitation 5 4 3 Problem: A robot A robot lives on a two dimensional grid and is free to walk around. However each move it makes is always one step north or south and one step east or west. Its purpose in life is to reach point (1, 0). Unfortunately, the robot was born at point (0, 0). Prove that it will never see how point (1, 0) looks like. Solution. The approach that seems reasonable is to use induction on the number n of moves made by the robot. But we must be careful in selecting the inductive hypothesis P(n). If it simply corresponds to what we want to prove —that is, if it simply is “after n steps the robot is not at point (1, 0)”— we are bound to encounter the same problems as in class against the 9­Number Puzzle. So, we must prove something stronger. Trying out several paths that the robot might take, we soon see that the robot can reach only points that lie on the line x+y = 0 and every other parallel of it. One way to describe this set of positions is to say that a point (x, y) belongs to it iff the sum x + y is even. We are now ready to prove the following theorem, which is stronger than the one we were asked to prove. Theorem. The sum of the robot’s coordinates is always even. Proof. The proof is by (simple) induction on the number n ∈ N of moves made by the robot. The inductive hypothesis P(n) is this: after n moves, the sum of the robot’s coor￾dinates is even. Base case: We show that P(0) is true. Indeed, after 0 steps, the robot is still at its birthpoint (0, 0), and the sum of its coordinates is 0 + 0 = 0, as required. Inductive step: We show that P(n) implies P(n + 1), for all n ∈ N. So, fix any n ∈ N and assume that P(n) is true; that is, after its nth move, the robot is at a position (x, y) such that x + y is even. After the n+1st moves, the robot will have moved one step north or south (which changes its x­coordinate by 1) and one step east or west (which also changes its y­coordinate by 1). So, if (x� , y� ) is the new point, we have x� = x ± 1 and y� = y ± 1 so that the new sum of coordinates is x� + y� = (x ± 1) + (y ± 1) = (x + y) + [(±1) + (±1)] = (x + y) + d where d ∈ {−2, 0, +2}. In all cases, x� + y� is a sum of two even numbers. So, P(n + 1) holds. Therefore, by induction, P(n) is true for all n ∈ N. The theorem holds. Now, to prove that the robot never reaches point (1, 0), we just need to observe that the sum 1 + 0 = 1 is not even