I want to create a compression scheme for 2-bit numbers such that it will reduce the size of any sequence by at least one bit. How can I prove this is not possible?
There are 4 possible two-bit numbers and 3 possible shorter bit sequences (the empty sequence of bits and the sequences 0 and 1). By the pigeonhole principle, this means that any mapping from two-bit sequences to shorter sequences must have at least two sequences compressed to the same shorter sequence. As a result, when you want to decompress this shorter sequence, you will not be able to do so because you won't know which of the original two-bit sequences it came from.
This can be generalized to show that n-bit sequences cannot be losslessly compressed to bit sequences of length less than n. This earlier answer details why this is.
Hope this helps!