Before I arrived in the US, I struggled with one subject during a whole year in my home university. Discrete math. It is definitely not that hard, but the approach the professor took leaded most of my class to fail – I think only three guys passed the subject on continuous evaluation –
So, blind and with very few material me and most of my classmates were to take an exam of the whole subject in June. Not a big deal you may argue, but it was right after the second semester exams. Stressed as hell I finally passed the subject thanks to Rosen’s book, Discrete Mathematics and its applications (not an amazon affiliate link) and some help from Berkeley’s online course.
It truly taught me a couple of things that will always make me think, aside from obviously a lot of combinatorics, number theory and advance graph theory that truly matters, but having already taken graph theory and cryptography, it was not that hard.
One of these things that actually left me thinking was counting. The rule of sum, the rule of product and the pigeonhole principle can apply to many problems, and simple as they are, applied to infinite sets they allow us to show a number of things, and I want to focus in how far we are from the future even though we know that something is waiting for us right there. Weird, huh?
Let us explain this with a simple example. Forgive me if I have some details wrong, I just want to make the big picture clear.
Computer screens are essentially several tiny dots that get filled with a color within a very very wide range of tonalities. This is essentially what allows us to show any image that can be imagined on a screen.
This tiny dots are not filled with a color by themselves. The computer fills them assigning a certain value. The way the computer likes to think about this is usually using the RGB color space. The red, green and blue colors use 8 bits each, which have integer values from 0 to 255. This makes 256*256*256=16777216 possible colors. Each pixel in the LCD monitor displays colors this way, by combination of red, green and blue LEDs (light emitting diodes). When the red pixel is set to 0, the LED is turned off. When the red pixel is set to 255, the LED is turned fully on.
Easy thus far. What about thinking of it from a different perspective? If we can control the device that picks a number between 0 and 16777216 (and we can), we could try assigning every simple pixel on the screen every single number. So we would have every possible combination of colored dots on the screen. What’s this? All possible images that can be shown. Either from the past or from the future. How your computer screen will be in 30 minutes – it’s there. Imagine a picture of Hitler and your grandmother kissing in the middle of Kakariko Village from Zelda OOT – it will be there. A picture of what you saw when you were 5 years old and you went for the first time to school – I assume the human eye can capture a much wider range of colors but essentially, you would get the picture. Now think of a bigger screen with smaller dots. See where I want to get?
Let us extrapolate this to very different situations. Imagine you could build an infinite binary file. Even if it is not infinite, it will work in our example. If we had a 64mb binary file and we are able to write all the combinations of 0s and 1s, then we are able to create any program that could fit in that size. If the size is not a problem (it really is not) whatever thing you can imagine would be represented there. Firefox 20000? There it is. Windows Longhorn? There it is. Ubuntu Sacred Unicorn? Yup.
If the binary file example did not convince you, you can think sets of characters to be distributed in a lot of space in a source file. You would end up with all possible programs for all possible languages. Interesting.
Then, why don’t we just focus our efforts on this? First let’s try to understand the rule of product.
When you decide to order pizza, you must first choose the type of crust: thin or deep dish (2 choices). Next, you choose the topping: cheese, pepperoni, or sausage (3 choices).Using the rule of product, you know that there are 2 × 3 = 6 possible combinations of ordering a pizza – Wikipedia
And here’s where discrete math helped me to understand the enormous amount of possibilities that we are creating doing this. We can illustrate how the previous examples would work according to the rule of product.
1080p resolution is the new trend. That is 1080 rows of pixels with 1920 pixels in each row. 2073600 pixels that have to be filled with all possible combinations of 16777216 colors. I like to think of this problem as putting golf balls of a certain color on a lot of beakers.
In this case when we decide to fill this, we have 16777216 options on each step, since colors may be repeated, this makes the astonishing number of 16777216 ^ 2073600 of possible images to create. Some studies say that there are 2.0 × 10^83 atoms… in the visible universe.
The binary file
Let’s say we pick up a rusty old pendrive of 1gb. This is 8,589,934,592 bits. In this case, we do not have as many options to fill the spaces. In fact 2 options, 1 or 0 is all we need to make this as complex as it gets.
So 2 options, so much space, we can repeat options and this is.. 2 ^ 8,589,934,592.
Jesus christ. Goddamn. Oh my gosh. According to worldwidewebsize.com, the internet contains more or less 45 billion pages as of December 2011.
2^9000 is this, just so you get the picture.
The problem here is to build stuff that can produce this amount of data, where do we store this data and how the hell can we distinguish the useful combinations from the trash ones. I am not very versed in this at all, nonetheless I am sure some of you guys can probably help with this.
In case you want to learn more, infinitary combinatorics kind of studies this type of operations to a deeper level.