Problem 2 (9 pts.)
Recall the toBinary algorithm from Tutorial 7 problem 3, which finds the binary representation of
a given integer n>0. For example, toBinary (13) = (1,1,0,1), and 1-23 +1-22 +0-2¹ +1-20 =
8 +4+0+1=13.
toBinary (n) :
1: if n 1 then.
2:
return (n)
3:
4:
5:
6:
else
(nd,no)
toBinary ([n/2])
= parity (n)
return (nd, no, I)
In Tutorial 7 we showed by induction that for any n20, if toBinary (n) = (na,....no) for some
d20, then we have n2 = n.
d
Note that toBinary takes in any integer n20 and spits out a binary number, which is an element
of {0,1}* (that is, an element of Uo0,1}). In other words, toBinary is a function from the
domain of Z2" to the codomain of {0, 1}*.
→
Use the result from Tutorial 7 to prove that toBinary : Z20 {0,1}* is one-to-one via a proof
by contrapositive.
Recall that we did an example of such a proof in the second lecture on functions and on PS3; use
those proofs to help structure your proof.
Grading Notes. While a detailed rubric cannot be provided in advance as it gives away solution
details, the following is a general idea of how points are distributed for this problem. We give
partial credit where we can.
(7) Correctness. If your proof is not correct, this is where you'll get docked. You'll need
(1) a statement that the proof is proceeding by contrapositive,
(1) the definition of one-to-one in its contrapositive form,
(5) other facts to prove f is one-to-one.
(2) Communication. We need to see a mix of notation and intuition, preferably in the "column"
format with the notation on the left, and the reasons on the right. If you skip too many steps
at once, or we cannot follow your proof, or if your solution is overly wordy or confusing, this
is where you'll get docked.
