CS70-Homework 7 Solved

Bijective or not?

Decide whether the following functions are bijections or not. Please prove your claims.

(a)     f(x)= 10 5x

(i)      for domain R and range R

(ii)     for domain Z[{p} and range R

(b)    f(x)= p mod x, where p 2 is a prime

(i)      for domain N\{0} and range {0,...,p}

(ii)     for domain {(p+1)/2,...,p} and range {0,...,(p          1)/2}

(c)     f(x)={x}, where the domain isD).D ={0,...,n} and the range is P(D), the powerset of D (that is, the set of all subsets of

(d)    Consider the number X = 1234567890, and obtain X0 by shuffling the order of the digits of X. Is f(i)=(i+1)st digit of X0 a bijection from {0,...,9} to itself?

2      Counting Tools

Are the following sets countable or uncountable? Please prove your claims.

(a)    A⇥B, where A and B are both countable.

(b)   Si2A Bi, where A,Bi are all countable.

(c)    The set of all functions f from N to N such that f is non-decreasing. That is, f(x) f(y) whenever x  y.

(d)   The set of all functions f from N to N such that f is non-increasing. That is, f(x) f(y) whenever x  y.

(e)    The set of all bijective functions from N to N.

3       Impossible Programs

Show whether the following programs can exist or not.

(a)    A program P that takes in any program F, input x and output y and returns true if F(x) outputs y and false otherwise.

(b)   A program P that takes in two programs F and G and returns true if F and G halt on the same inputs, and false otherwise.

4     Undecided?

Let us think of a computer as a machine which can be in any of n states {s1,...,sn}. The state of a 10 bit computer might for instance be specified by a bit string of length 10, making for a total of 210 states that this computer could be in at any given point in time. An algorithm A then is a list of k instructions (i0,i2,...,ik 1), where each il is a function of a state c that returns another state u and a number j. Executing A(x) means computing

                            (c1, j1)= i0(x),                  (c2, j2)= ij1(c1),                  (c3, j3)= ij2(c2),                 ...

until j`           k for some `, at which point the algorithm halts and returns c` 1.

(a)    How many iterations can an algorithm of k instructions perform on an n-state machine (at most) without repeating any computation?

(b)   Show that if the algorithm is still running after 2n2k2 iterations, it will loop forever.

(c)    Give an algorithm that decides whether an algorithm A halts on input x or not. Does your contruction contradict the undecidability of the halting problem?

5       Clothing Argument

(a)    There are four categories of clothings (shoes, trousers, shirts, hats) and we have ten distinct items in each category. How many distinct outfits are there if we wear one item of each category?

(b)   How many outfits are there if we wanted to wear exactly two categories?

(c)    How many ways do we have of hanging four of our ten hats in a row on the wall? (Order matters.)

(d)   We can pack four hats for travels. How many different possibilities for packing four hats are there? Can you express this number in terms of your answer to part (c)?

(e)    If we have exactly 3 red hats, 3 green hats and 4 turquoise hats, and hats of the same colour are indistinguishable, how many distinct sets of three hats can we pack?