I don't think it is 100% foolproof, even if no filesystem trickery is used. The random number generator used is likely not perfect and so the data should be compressible. I mean it would probably be quite difficult, but maybe possible.
> RANDOM.ORG offers true random numbers to anyone on the Internet. The randomness comes from atmospheric noise, which for many purposes is better than the pseudo-random number algorithms typically used in computer programs.
Theorem: No program can compress without loss all files of size >= N bits, for any given integer N >= 0.
Proof: Assume that the program can compress without loss all files of size >= N bits. Compress with this program all the 2^N files which have exactly N bits. All compressed files have at most N-1 bits, so there are at most (2^N)-1 different compressed files [2^(N-1) files of size N-1, 2^(N-2) of size N-2, and so on, down to 1 file of size 0]. So at least two different input files must compress to the same output file. Hence the compression program cannot be lossless.
This proof of the impossibility of a compressor that can compress any file has been known for decades.
An example of an algorithm that does compress 2% (actually 1/32 ~= 3%) of random files: just drop the initial five bits of the file, and replace them with zeros upon decompression. There's a 1/32 chance they were all zeros, in which case you win. The difficult part is encoding the decompression procedure into a program of less than five bits. :-)
No, you'd need to be able to create a custom algo for that file with that probability. Quite a difference.
(* ) There's a little bit of leeway here because the challenge as stated isn't actually precise about the execution environment. You could probably sneak in a small number of illicit bits by negotiating out-of-band whether the decompressor is to be a C program, ELF binary, Perl script, etc. It's not obvious how to make this useful though.
While you're obviously correct about the information theory aspect of this, in this particular challenge, the contestant enjoys the privilege of pruning his decompressor to match just the one file. All the other "if" statements can be thrown away. So now a lossy algorithm can be used, that just happens not to be lossy on that one particular file.
Another way to say this is that although you have the 'privilege' of a designing a custom decompressor for this one file, this is not really a benefit since your custom decompressor counts against the space limit. (in contrast to the typical information-theoretic setting where the channel can have an arbitrary pre-specified decoder).
Not a good bet to take.
> my point is that this is not information-theoretically relevant.
Exactly. This whole post is about the challenger trying to be clever with the rules and trying to sidestep the core information theory.
You could get 6% if you can also do the same on the end of the file. There's a 1 in 16 chance that any random sequence of data will start or end with 5 zeros. The same trick could be done for 1s to bring it up to 12%. In other words, 12% of sequences will either begin or end with 5 ones or 5 zeros.
Since you can inspect the data before writing the decompressor, if we can figure out how to pad the beginning or end of a byte sequence with five 1s or five 0s in 5 bytes or less, then your expected outcome is $625 (minus $100 to play). Using 6 bytes would give you an expected outcome of $312.5, 7 bytes would give you an expected outcome of $156.
7*'0'+a
That's 7 bytes. It's not really a executable decompressor, but it does capture the necessary steps required to decompress.
Pre-file we can communicate as much as we want without being penalized. We can say for instance that we want our bitstring to be interpreted as an elf binary to be run in ubuntu 14, with specific libraries installed. Or we can say that it will be a zip file. Or we can say that it should be pre-concatenated with 0's. We can specify hundreds of thousands of lines of code that should be compiled now, and then later be executed with the bitstring as input.
Then we get the file, and now every bit we communicate is penalized. If we have asked for a turing-complete format we may now send a decoder specific for the file.
Similar cheats would be to leverage hardware instructions (imagine if x86 had a "pad with N zeros" instruction that fit in 7 bits). That's still cheating because the information is hiding in the architecture.
Assume that you split a m byte string into k byte decompressor and l byte input data. If k+l < m, that is you actually compress, then there are only 2^(k+l) possible output strings. And since
sum_{i=0}^{m-1} 2^i = 2^m -1
But consider a more strongly formulated problem, where you must provide the decompresser and then a file is randomly selected to be put through it - as long as it's still a matter of compressing one particular file it is statistically possible to win (especially at $5000:$100) - The idea being that you can reinterpret data to make certain outputs cheaper while others more expensive.