Suppose we have a compression function

c, which takes a bit string s to a compressed string c(s).

(a) Show that for any integer N, there must be a string s of length N for which length(c(s)) ≥ N; that is, no effective compression is done.

(b) Compress some already compressed files (try compressing with the same utility several times in sequence). What happens to the file size?

(c) Given a compression function c as in (a), give a function c

such that for all bit strings s, length(c

(s)) ≤ min(length(c(s)), length(s)) + 1; that is, in the worst case, compression with c

expands the size by only 1 bit.