A file compressor is great for shrinking stored files, but it depresses me whenever I see a file grow instead of shrink. So what I am looking for is a file compression algorithm that never inflates any files, although it is allowed that some files (not all of course!) have the same length after "compression". Ideally it should work on files of all sizes, but I would be satisfied with a compressor that operates only on files larger than 1MB.
Can you provide such an algorithm? No programming knowledge is required for this problem.
The puzzle, as described above, is impossible.
Either the "compressed" file needs to have a header (and thus may be larger than the origonal), or compressing and then uncompressing the file may not result in the origonal file.
Proof: Take a large file. Compress it with the magic algorithm, repeatedly, untill it compresses no more. Call this file A.
Compress this file once more. At this stage, you have 2 options:
Option 1: Add additional information to say "The following file is not compressed" and include the rest of the file as-is. This breaks the criteria, as it must, by definition, be larger than the uncompressed file (File A), since it contains the marker, plus the uncompressible file.
Option 2: Leave the uncompressible file exactly as-is - that is, identical to file A. Now run this through the uncompressor - you will get a different file. In other words, uncompress(compress(x)) may not be x.
QED.
Provably impossible
