Since he offers $5000 but you only need to pay $100 to participate it is quite easy to win money with the challenge. Ask for a file of 2 bits in length. If it is "11" then compress it to "1". Otherwise compress it to "0X" where X is the contents of the file. Now you have a 1 in 4 chance of winning the challenge. Since you pay $100 but win $5000, this earns good money. Plus it would be hard to argue that this is cheating.
The problem is that you need to supply the decompressor as well. It would depend on how exactly he wants the decompressor be encoded, but the same strategy may still apply with modifications (although it would not work if the required encoding is as a bash script, since lg(100/5000) gives you just 2 bits to play with). [Or you could ask him to modify the challenge such that you are allowed to send him an encrypted decompressor before he sends you the data, and doesn't count towards the total file size (encrypted because otherwise he'll see your strategy and send you a file that it doesn't work on)]
tl;dr: although you can't compress random with probability > 1/2, you can compress random data with probability > 100/5000.
As I said, you can also win the original challenge with this method. The original challenge is not fully specified. In particular it is not specified how the decompressor is to be encoded. There are encodings for the decompressor for which the strategy that I described does work, and encodings for which it does not work.
The interesting attribute of this method is that it does genuinely compress the file: it doesn't store data in hidden attributes like the method of the OP (which stores information in the file lengths).
The problem is that you need to supply the decompressor as well. It would depend on how exactly he wants the decompressor be encoded, but the same strategy may still apply with modifications (although it would not work if the required encoding is as a bash script, since lg(100/5000) gives you just 2 bits to play with). [Or you could ask him to modify the challenge such that you are allowed to send him an encrypted decompressor before he sends you the data, and doesn't count towards the total file size (encrypted because otherwise he'll see your strategy and send you a file that it doesn't work on)]
tl;dr: although you can't compress random with probability > 1/2, you can compress random data with probability > 100/5000.