I personally feel that this question ventures strongly into discreet mathematics. Be that as it may, it seems very appropriate for a computer science board.
The original Gallery of Babel post (formerly a function challenge) raised an interesting question. How many 10x10 images exist when we only have 16 colors to choose from. The answer was quickly found to be:
16**100 (16 choices on 100 pixels).
Many scholars believe there are only 10*100 atoms in the universe... needless to say, we can't display all the images. It's logical to say that if I were to create a program that could generate these 10x10 images, I could never store all of the images anywhere. Does that mean that my program could generate a 10x10 image that can't be found anywhere else in the universe?
Before you answer that, consider this. I have a 10x10 image that is all black pixels. Then imagine I add another column to the side of it, this column is all white pixels; giving us an 10x11 image. Could we not view this 10x11 image as 2 10x10 images with 10 overlapping rows and 9 overlapping columns? With an 11x11 image, we now have 4 10x10 images.
So here's a few thoughts for you...
How quickly would this sucker grow? Starting with a 10x10 image (our base case) adding 1 row or 1 column only adds 1 more image. Adding 1 row and 1 column adds 4 (11x11). Anyone have any thoughts on an algorithm that can predict the growth?
Here's another question, what is the smallest image that someone can create that will have ALL 10x10 images inside it? What if we allow our big image to rotate?
Here's a more intriguing question, what if the bigger image were 3-dimensional, like a torus for example. Having wrap-around certainly changes things.
These are some of the thoughts I've been toying with for the last few weeks. Let me know what you think!
I am more interested in general discussion than concrete answers! Am I the only one who is reminded of the 4 color theorem?
This post has been edited by atraub: 31 January 2011 - 01:54 PM