[atraub]

Quick foreward:
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!

EDIT:
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

[Nikitin]

With wrap-around, each picture is defined by a single pixel which represents its upper-left corner. So there are (h*w) such images in 2D, and (h*w*d) in 3D. With rotation, each image also requires a choice of vertical and horizontal direction. In 2D there are 8 such choices, in 3D there are 24. So if you want a 3D wrap-around, there are 24*h*w*d unique images that can be constructed.

hwd = height / width / depth

Quote

Am I the only one who is reminded of the 4 color theorem?

What does it have to do with what you're asking?

This post has been edited by Nikitin: 31 January 2011 - 03:40 PM

[macosxnerd101]

The four color theorem is Graph Theory, and states that given a plane separated into contiguous regions, no more than four colors are required to color the Graph so that no two adjacent regions have the same color. Your question, while still Discrete Math related, falls under the field of combinatorics rather than Graph Theory.

The relevant combinatorics equations you want to be looking at are:
Order Matters
-With Repetition: n^r
-Without repetition: n!/(n-r)!

Order Doesn’t Matter
-With Repetition: (n+r-1 choose r) = (n+r-1 choose n-1)
-Without Repetition: n!/r!(n-r)!

Specifically, in this case, the n^r equation is the one of interest.

[AdamSpeight2008]

I'm very sure that that is not entire true. I read an article in either New Scientist or Scientific America there are fractal shapes that violate the 4 colour theorem.

[atraub]

I said I was reminded of the 4 color theorem, not that the 2 problems are mathematically related. I haven't heard that there are any flat shapes that violate the 4 color theorem, however I'd be very interested to read that article if you can find it.

macosxnerd101, I think I'm not completely following. n^r represents how many different combinations of 10x10 16 color image exists. Do you think that the surface area of a larger image containing all possible combinations could not be smaller than n^r?

[AdamSpeight2008]

Scientific American Jan 2003 Page 14

http://www.sciamdigi...7002D7FA6F0ACC4

[macosxnerd101]

If you have 16 colors (n), choosing 100 of them allowing repeats and order does matter, then you get 16^100 permutations.

[atraub]

As I was in the shower I couldn't help but reflect on the crap I was catching about the 4 color theorem comment. I asked myself, "Why do these two problems feel so similar when they are clearly very different?"

Maybe they're not so different if you look at them from the right perspective. They both started from simple questions.

• How many colors is the minimum I need to draw in a map where no edges share a color?
  
• What is the smallest image that contains all possible images of a given w, h, with a set of colors?

Both questions involve trying to find the smallest solution to a problem that is very visual. Both have also proven to be a bit more difficult than one might imagine on a surface glance. I also find myself wondering if the solution for this question will be any more pleasing than the 4 color theorem's solution? That's just me thinking out loud though.

macosxnerd101, I don't understand your answer. I realize that there exist 16**100 possible 10x10 images with 16 colors. I just don't see where you're going with that in regards to the question I posed. What does that have to do with the size of a larger image containing all possible 10x10 16 color ones? I'm probably just failing to see the forest through the trees.

Nikitin, I get your thinking about the 3D image, but I'm worried you're thinking too mathematically and not practically. If we create a 3D image (let's say a cube), and stick images inside the cube, we can't see them... So it seems reasonable to only consider surface area rather than total area.

This post has been edited by atraub: 31 January 2011 - 09:36 PM

[macosxnerd101]

Sorry for the confusion. I misunderstood your question.

This is still a combinatorics problem. We have 16^100 possibilities, and a width x height grid. We know that given width > 9 and height > 9, we can fit (width-9) * (height-9) 10x10 images (allowing overlap) on the grid. So to choose how many images could fit on the grid, we could set up the combinatorial formula of m choose k where:

m = 16^(width * height)
k = (width-9) * (height-9)

For a 3D grid, you would do 16^(lwh) choose (width-9)(height-9)(length-9).

Edit: I was thinking volume as well. If you wanted to cover surface area only, you would replace (width-9) with the constant 6, for 6 faces on a cube.

[atraub]

This question gets more and more interesting. For example, what if we use a Torus rather than a cube, and how small could we make it? Would the numbers we generate actually work in practice, or would we find that the 'perfect' combination that we try to generate won't exist, and thus the number would be slightly larger? Rotating a Torus would be silly, but flipping adds more possibilities. I feel like a Torus works better because I don't think an image should overlap the edge of a cube. I feel like corners cause even more issue.

Am I the only one who feels the excitement in this problem?

This post has been edited by atraub: 31 January 2011 - 10:04 PM

[macosxnerd101]

atraub, on 01 February 2011 - 02:00 AM, said:

This question gets more and more interesting. For example, what if we use a Torus rather than a cube, and how small could we make it?

As long as we knew the surface area, this wouldn't make a difference from the 2D plane.

Sorry, atraub, combinatorics is one field of math I haven't taken to. I always wrote code as my work for a lot of these problems on tests in Discrete rather than work through them mathematically.

[Nikitin]

atraub, on 31 January 2011 - 09:27 PM, said:

If we create a 3D image (let's say a cube), and stick images inside the cube, we can't see them... So it seems reasonable to only consider surface area rather than total area.

Then take the formula I gave for 2D wrap-around - 8*h*w. That's what you get with torus.

Quote

Am I the only one who feels the excitement in this problem?

Most likely.

[atraub]

macosxnerd101, no worries. Clearly, it's not my strongest field either. I find this problem to be an interesting topic of thought and conversation. I don't believe there's enough data to come up with a concrete answer to a question like this.

Nikitin, I've been respectful towards you. I'd appreciate you responding in kind. As for the 2D wrap around being equal to 8*w*h, I wouldn't be so quick to jump on that one. You make the assumption that we have no repeated images when we rotate the master image. Ideally, this would be true but realistically, it's not. Somewhere in the image exist pictures that are the same when rotated and mirrored (for example, a solid color). What this means for us is that a given 25x25 image might not have 5000 unique 10x10 images inside it, because there could (and probably is) some repeated images. An image that contains all combinations of 10x10 images MUST have images inside it that remain the same when rotated. Thus, 8*w*h would determine the number of 10x10 images inside the bigger one, but NOT the number of unique ones. This problem is not so easily simplified.

This post has been edited by atraub: 01 February 2011 - 08:03 AM

[Nikitin]

The formula I gave counts the total number of images and it can be used to count the number of unique ones. Simply account for the number of palindrome-images that get overcounted.

8*h*w = 16^100 + 2*16^75 - 2*16^50 + 3*16^25

Since h*w is at a maximum when (h=w), the left side becomes (8*h^2) and the final answer is approximated to 5.7e59, which is a reasonable approximation for a problem which is practical and not mathematical.

Here, I'll even put a smiley,

This post has been edited by Nikitin: 01 February 2011 - 02:52 PM

[atraub]

It's a mathematical problem that begs for a practical solution. Care to elaborate on where you got your numbers from?

Not that your word isn't gospel to me, I'm just curious. Teach us how to fish

This post has been edited by atraub: 01 February 2011 - 03:01 PM