Problem 3 (50 points) This solution is based on a known puzzle, "catch a spy". The purpose is for us to practice using a theorem prover, like Dafny, to do a formal proof that is not related to program. The puzzle and its solution are effectively provided to you (and you can consult resources online for this). We are not asking you to findia solution for the puzzle. We are asking you to use Dafny to prove formally that the provided solution for the puzzle is indeed correct. The spy exists on a one-dimensional line. His location is described by the expression a+t*b, where a, bEN are unknown constants and t EN is the number of seconds since he pirated your work. Unfortunately, he has also stolen U of T's cloak of invisibility, so our only means to find him is to physically query a single location every second. That is, at every second, we may ask "is the spy at location n" and get back a "yes" or "no" answer We can catch the spy as follows. The set Nx N of pairs of natural numbers is countable, so there exists a function unpar: N N N that covers all pairs of natural numbers. Our strategy is to check the location z+tx y at time t, where (z, y) = unpar(i). Since there exists some to such that (a, b) = unpar(to), then at time to we will check the location a+to*b and therefore catch the spy Complete the implementation of unpair according to our strategy above, and prove that the while loop terminates (i.e. that we eventually catch the spy) function method unpair(i: nat): nat II TODO function method pick(i: nat): nat var (x, y) unpair(i); := method catchTheSpy (a: nat, b: nat) var i := 0; while a + i * b !-pick (i) You may use any valid implementation of unpar : N N N, but the Cantor pairing function is suggested. The Cantor pairing function essentially lists all pairs who's sums are 0, then all pairs who's sums are 1, and so on unpair (0) = (0, 0) unpair (1) = (0, unpair (2) -(1, 1) 0) unpair(3) = (0, 2) unpair (4) -( 1) unpair (5) = (2, 0) Problem 3 (50 points) This solution is based on a known puzzle, "catch a spy". The purpose is for us to practice using a theorem prover, like Dafny, to do a formal proof that is not related to program. The puzzle and its solution are effectively provided to you (and you can consult resources online for this). We are not asking you to findia solution for the puzzle. We are asking you to use Dafny to prove formally that the provided solution for the puzzle is indeed correct. The spy exists on a one-dimensional line. His location is described by the expression a+t*b, where a, bEN are unknown constants and t EN is the number of seconds since he pirated your work. Unfortunately, he has also stolen U of T's cloak of invisibility, so our only means to find him is to physically query a single location every second. That is, at every second, we may ask "is the spy at location n" and get back a "yes" or "no" answer We can catch the spy as follows. The set Nx N of pairs of natural numbers is countable, so there exists a function unpar: N N N that covers all pairs of natural numbers. Our strategy is to check the location z+tx y at time t, where (z, y) = unpar(i). Since there exists some to such that (a, b) = unpar(to), then at time to we will check the location a+to*b and therefore catch the spy Complete the implementation of unpair according to our strategy above, and prove that the while loop terminates (i.e. that we eventually catch the spy) function method unpair(i: nat): nat II TODO function method pick(i: nat): nat var (x, y) unpair(i); := method catchTheSpy (a: nat, b: nat) var i := 0; while a + i * b !-pick (i) You may use any valid implementation of unpar : N N N, but the Cantor pairing function is suggested. The Cantor pairing function essentially lists all pairs who's sums are 0, then all pairs who's sums are 1, and so on unpair (0) = (0, 0) unpair (1) = (0, unpair (2) -(1, 1) 0) unpair(3) = (0, 2) unpair (4) -( 1) unpair (5) = (2, 0)