I believe the pigeon hole principle does not realy apply here, since we are looking for an algorithm that encodes just one file. For example, if we have two pro

I believe the pigeon hole principle does not realy apply here, since we are looking for an algorithm that encodes just one file. For example, if we have two programs and input: ( C, n) and ( D, n) which can both be encoded in n-1 bits and ( C, n) maps into the set of n bit strings with a leading 0 and ( D, n) into the set of strings with leading 1, then counting the number of bits, I end at 2^n-1 possible states for both the programs and the output. Effectively one bit is hidden in the choice of C or D.