If every file is just a number, how can lossless compression work at all?

There is no flaw. Your argument is correct and it is a real theorem: no lossless compressor can shrink every input. For any compressor, some inputs must get longer.

The counting argument you gave is exactly the proof, and it is worth appreciating that you derived it yourself.

What you have not noticed is that this does not conflict with compression working, because real compressors do not claim to shrink everything. They shrink some inputs — a very particular subset — and expand the rest slightly.

And the subset they shrink is the one we care about. Text, images, audio, source code, logs, executables: all deeply patterned, all a vanishingly small fraction of the space of possible bit strings. Almost all bit strings are noise, almost none of them are ever stored in a file, and a compressor is a bet that its input comes from the patterned corner rather than from the enormous random middle.

So compression is not magic, it is exploitation of a bias in which files actually exist.

The practical consequence you can verify in a minute: compress a file twice.

The second pass will not shrink it and will usually make it slightly larger. The first pass removed the redundancy; what came out looks like noise, which is exactly the input type that compressors expand.

Same reason a zip full of photos or video barely shrinks — those formats already compressed the data, and there is nothing left to find. If you have ever wondered why zipping an archive of media achieves nothing, this is why, and it is your own argument in practical form.

It also explains why claims of a universal compressor that shrinks any input, repeatedly, are a reliable signal of nonsense. Applied twice it would compress everything to one bit.

The concrete way to see the trade is to look at how the shrinking is bought.

Suppose you have data made of four symbols. Fixed-length coding gives each one two bits, so a thousand symbols cost two thousand bits regardless of content.

Now suppose one symbol is far more common than the others. Give it a one-bit code, and give the rarest ones three-bit codes. Common data now costs less than two bits per symbol on average — you have compressed it. But data that happens to be full of the rare symbols now costs more than two bits per symbol. You have not created anything; you have moved cost from likely inputs to unlikely ones.

That is the entire mechanism, and it makes the theorem obvious rather than surprising. Every bit saved on a common input is a bit spent on a rare one.

Worth adding the formal name for the limit, since it gives you something to look up: the entropy of the source.

There is a specific number of bits per symbol below which you cannot go without losing information, determined by the probability distribution of the data. Good compressors get close to it. Nothing gets below it, ever.

That number is also a genuinely useful practical tool — it tells you how much benefit is even available before you spend a week choosing an algorithm.