Suppose I take a perfect cube of graphite. I'm sure we can all degree that this is low in information, since it can be easily described in just a few formula.
Now suppose I whack it as hard as I can with a sledge hammer.
What are we left with? Well, a shattered pile of bits. Some large, some small, each requiring a whole load more information to describe than the original cube.
Now, if I can increase the information in something just by smacking it with a sledgehammer; what exactly is the information increase problem?