Description
1 Bijective or not?
Decide whether the following functions are bijections or not. Please prove your claims.
(a) f(x) = 105x
(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,…,(p1)/2}
(c) f(x) = {x}, where the domain is D = {0,…,n} and the range is P(D), the powerset of D
(that is, the set of all subsets of D).
(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.
CS 70, Fall 2018, Homework 7 1
(b) S
i2A 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,…,ik1), 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?
CS 70, Fall 2018, Homework 7 2
(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?
CS 70, Fall 2018, Homework 7 3
