Congratulations to any who attempted the assigned counting problems in the previous post. If you are ready, you can read on for the correct answers, if not, you can go back and try them out for yourselves (or go back and start at the beginning).

In the following table, “#edge-checks” means the number of individual edge colors that must be checked for a totally exhaustive search of all colorings of K_{N} for monochromatic K_{M} (open your browser wide!)

K_{N},K_{M} |
K_{N} edges |
K_{M} edges |
# K_{M} |
# colorings | # edge-checks |
---|---|---|---|---|---|

K_{5},K_{3} |
C(5,2) = 10 |
C(3,2) = 3 |
C(5,3) = 10 |
2^{10} = 1024 |
3*10*1024 = 30,720 |

K_{6},K_{3} |
C(6,2) = 15 |
C(3,2) = 3 |
C(6,3) = 20 |
2^{15} = 32,768 |
3*20*32,768 = 1,966,080 |

K_{100},K_{10} |
C(100,2) = 4950 |
C(10,2) = 45 |
C(100,10) = 17,310,309,456,440 |
2^{4950} ~ 10^{1490.1} |
45*C(100,10)*2^{4950} ~ 10^{1504.99} |

Take a look-see at the last number in that table: 10^{1504.99}. “Ten to the 1504.99th power” means a number with over 1500 digits. That’s big. Bigger, for instance, than the largest number Excel can handle. To give an idea how large that number is, if you take the age of the universe (as pinned down by the latest & greatest data, 13.7 billion years), and live that out 13.7 billion times, you would have a number of years with, um (hold on a sec, carry the one…) 21 digits, a puny number which is not even one molecule of H_{2}0, compared to the ocean of 10^{1504.99}. Or how about a larger number, say the number of electrons in the whole universe. Scientists estimate that number to have about 79 digits. What if every electron had a complete replica of our whole universe inside of it? The total number of electrons would then be a wimpy 158 digits. Our 1504-digit number is so much bigger, the human mind is really incapable of conceiving just how big it is.

My point is this: if your plan to find a 2-edge coloring of K_{100} with no monochromatic K_{10} involves “let’s just try all the colorings and see what we find”, you are in big trouble. Looking closely at those numbers, it is evident that the real problem is the huge number of colorings involved, 10^{1490.1}. Maybe if we just tried one or two colorings, we would get lucky. Scaling back the problem in this way, “trying out one coloring” would involve checking all 45 edges of each of the 17,310,309,456,440 (17 trillion) K_{10} that are in K_{100}. Multiplying just those two numbers together gets us 778,963,925,539,800 edges to check, for just one single coloring. How many edges can you check per second? How many can a computer check per second? How about, to be generous, I allow that a computer can check a million edges per second. Then you can check through one coloring in (number of checks, checks per second, seconds per hour, hours per day, days per year…) just under 600 years. You better get started! And you better hope your great-grandchildren train their great-grandchildren to keep your program running — and you better hope you get lucky on your first try!

Note that you don’t even have to increase N and M to K_{100} and K_{10} to have practically intractable problems. In Puzzle I and Puzzle II, we found out that the magical threshold for K_{3} is crossed by moving from 5 to 6 vertices. It turns out that mathematicians currently know that the threshold for K_{4} is crossed by moving from 17 to 18 vertices. But the threshold for K_{5} is only known to lie between 43 and 49. The threshold for K_{6} is known to lie between 102 and 165. And they’re not expecting to be able to close those gaps easily. The late, great mathematician Paul Erdős famously said (with my [notation inserted]):

Imagine an alien force, vastly more powerful than us landing on Earth and demanding the [threshold for K

_{5}] or they will destroy our planet. In that case, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they asked for [threshold for K_{6}], we should attempt to destroy the aliens.

OK, so now that you have despaired of solving our K_{100},K_{10} problem manually, let me work a little magic for you and give you the answer. Before we embark on the futile exercise of trying out just one coloring, let’s think about how likely we are to get lucky with just one coloring. We know that there are 45 edges in every K_{10}. So across all of the practically infinite number of colorings of K_{100}, what is the proportion of all those colorings in which any one particular K_{10} is, say, all-red? Well the chance that the first edge is red is 1/2. The chance that the second edge is red is 1/2, … the chance that the 45th edge is red is 1/2. So the chance that the WHOLE K_{10} is red is (1/2)^{45} = 1/35,184,372,088,832. Similarly, the chance that any WHOLE K_{10} is blue also 1/35,184,372,088,832. Adding them together, we can see that the proportion of colorings in which any one particular K_{10} is monochromatic (red or blue) is 2/35,184,372,088,832 = 1/17,592,186,044,416

(you remember how to reduce fractions, don’t you?)

So for any one particular K_{10}, the proportion of bad colorings is quite small. But there are a large number of K_{10} to worry about: 17,310,309,456,440 of them, to be exact, each of which is equally subject to that one in 17,592,186,044,416 chance of being monochromatic. It turns out that, armed with these two numbers (# of K_{10} to worry about, and chance that any particular K_{10} is monochromatic), we have exactly what we need to compute the answer to the following question: “Across all of the 2^{4950} colorings of K_{100}, what is the **average** number of monochromatic K_{10} per coloring?” The answer is, the number of K_{10}, times the probability per K_{10}, which is exactly

17,310,309,456,440 / 17,592,186,044,416

There is something very special about that number. Notice that the numerator is a hair smaller (relatively speaking) than the denominator. In fact, that number turns out to be about 0.98. Hmmm. Think again about what question 0.98 is answering: Across all of the colorings of K_{100},what is the **average** number of monochromatic K_{10} per coloring? The number of 0.98 is that average, and it is important to note that 0.98 is less than 1.

Note that an average is computed from multiple numbers. Because this particular average turns out to be less than 1, we know that some of the numbers that went into the average must be less than 1 (if all the numbers in the average were 1 or more, then there is no way for the average to be less than 1!). We also know that all the numbers that went into this average are whole numbers (because they are counts, for each coloring, of how many monochromatic K_{10} it had). And what whole number is less than one? Zero. As in Zero monochromatic K_{10}, which is what we are looking for. Therefore, the answer to the question “Does there exist a 2-edge coloring of K_{100} with Zero monochromatic K_{10}?” is

Yes

So what is that coloring of K_{100}? I dunno. I could flip 4950 coins and give you a coloring, and how are you going to double-check whether my coloring fills the bill? Do you have the computing resources, programming chops, and longevity required to check all 17 trillion K_{10}? I doubt it. So how do I know the answer is yes? Because the laws of probability allowed me to compute the average number (over all colorings) of monochromatic K_{10}, and since that average was less than 1, I know that there must be at least one coloring out there that contributed a 0 to that average (actually, probably quite a few colorings!). But I don’t pretend to be able to show you such a coloring in defense of my claim.

If you’re not on board yet, here’s an analogy that might help. Suppose you discovered a newspaper article from 1850, that reported a poll of a number of married couples, asking how many children they had, and the average number of children reported was 0.98. You don’t have access to the original poll data, or the names or addresses of the polled couples, or the names of their children — in this case you don’t even need to know how many couples were polled. But given an average number of children per couple of 0.98, you can be fully certain (assuming the pollsters competently applied basic arithmetic) that at least one couple reported 0 children (otherwise, how could the average sink below 1?)

So that’s it, that’s the end. This is what I was driving for all along. This is an example of an existence proof which is non-constructive. I proved that there does exist some 2-edge coloring of K_{100} with no monochromatic K_{10}, but the proof didn’t involve me handing you a coloring, and saying “Look, check it yourself, and you will see that none of them are monochromatic!” It is a rigorous and certain proof, despite the fact that relied on the laws of probability to compute the average of 0.98 that cracked the case. This type of certain proof using the laws of probability is called The Probabilistic Method, and you can read more about it at Wikipedia, if you feel like a challenge.

I hope you enjoyed the ride, and I hope your children (if you challenged them with these puzzles) learned a lot about math as well. If you have any feedback that would improve the presentation, drop me a comment, and I’ll be glad to try to improve!

(Continue this way for the Epilogue!)

Puzzle III.2: Combinations « Blogorrhea, on October 15, 2006 at 8:27 pm said:[…] Puzzle III.3: Final Answer […]

the forester, on October 17, 2006 at 4:14 am said:This one was a fun read — especially if you don’t bother to check all the math! :-)

Here’s what I’d be interested in reading more about:

Call me a blockhead, but that just doesn’t seem right to me. The universe is huge. The number of cells in my body is huge. The number of electrons in a single cell in my body is huge. So how can the number of electrons in the entire universe be less than a number of edge checks in a silly little proof?

Don’t get me wrong — I’m not asking for more edge-checking. Instead, I’m interested in hearing additional comparisons of Big Figures against the number of electrons in the universe. For example — somewhere out there is the largest single posited number ever in a mathematical paper. What is that number, how’d it get so big, how do electrons in the universe compare against it, and why haven’t you made a name for yourself yet by positing an even bigger number (say, the former +1)?

Years ago I read a report that explained that the question “What is the cheapest airline fare between A and B?” is unanswerable. There are simply too many combinations with too many fare structures, yielding basically an infinite number of answers — making the cheapest-fare question an impossible one to answer.

Unless, of course, somewhere out there you can actually find an airline ticket for $0.

But then, an astute sale-watcher and coupon-clipper like my wife could probably finagle an airline company into paying

herto fly — so the question becomes unanswerable again.RubeRad, on October 17, 2006 at 9:15 am said:Congratulations! Your mind is beginning to wrap around the concept of combinatorial explosion. This is what people are talking about when they say “exponential growth”. Of course, when people say that, they almost never understand what exponential growth really is, and the growth they are hyperbolizing is almost never actually exponential.

D’oh! I was going answer you with a link from your own blog, but it turns out it was actually just an email in which you told me about the Nov 17, 2003 discovery of the 40th known Mersenne prime, which is over six million (decimal) digits long. A Mersenne prime is just any prime which is one less than a power of two, like 127=128-1. Since then, four more Mersenne primes have been found, the most recent just last month, at just under 10 million (decimal) digits long.

Both of these numbers were discovered by the Great Internet Mersenne Prime search (GIMP), a cooperative parallel computing project where any regular joe can download and run a program, effectively donating spare CPU cycles for the use of the research project. If you participate, and your computer finds a record prime, you could win some cash money! A GIMP participant has already won the $50,000 prize for the first million-digit prime. Still unclaimed is the $100,000 bounty for the first prime with at least 10 million digits (and more!)

Big numbers are cheap and plentiful to obtain, but in some ways very difficult (practically impossible) to handle, which is what makes cryptology possible. For instance, the Advanced Encryption Standard uses 256-bit (77 digit) keys.

I like to ruminate on how these numbers, which seem “big” to us, are not big in any absolute sense. Take any biggest number, and add 1, and you have a bigger number. Or add it to itself. Or multiply it by itself. Or raise it to an exponent of itself. And yet the biggest number that we can (not really) conceive of in this way, is as concrete and familiar to God, as 1 and 2 are to us.

the forester, on October 17, 2006 at 12:58 pm said:Since we’re having so much fun floccinaucinihilipilificating, here’s a well-written and entertaining article you’ll appreciate (although its references to the Bible and creation/evolution are flippant and uninformed):

Who Can Name the Bigger Number?

You’ll particularly enjoy the conclusion, which argues that we’re not floccinaucinihilipilificating at all. I even found it moderately convincing.

By the way, isn’t the Turing Machine essentially the same concept you’ve described in these posts?

RubeRad, on October 18, 2006 at 6:46 am said:That was a great article; I’m going to follow that guy’s blog for a while. A Turing Machine is simply a theoretical model of a computer (developed, interestingly, before any actual computers, and not for the purpose of designing computers, but for studying computability/decidability). One relationship would be that Turing Machines can only answer yes/no questions. A Turing Machine could certainly be built to answer any particular question “Is there an edge-coloring of this K_N which has no monochromatic K_M?” by exhaustive search. My point is that such a solution is not theoretically impossible, only practically impossible.

Note also that, if we bump N to 101, the computation of the average number of monochromatic K_M across all colorings becomes 1.09, and our proof fails. We cannot be certain that an average of 1.09 included no zeroes. So our proof fails. The answer to the question with N=101 does not suddenly become NO, however, but DON’T KNOW — at least as far as this analysis goes. It so happens that mathematicians have pinned the threshold for monochromatic K_10 to between N=798 and 23,556. Let’s hope those aliens don’t show up!

Puzzle III.4: Epilogue « Blogorrhea, on October 18, 2006 at 9:17 am said:[…] Comment on Puzzle III.3: Final Answer by RubeRadComment on Puzzle III.3: Final Answer by the foresterComment on Puzzle III.3: Final Answer by RubeRadComment on Obedience is better than… by the foresterComment on Puzzle III.3: Final Answer by the foresterComment on Sacra-licious by Mike SComment on Sacra-licious by RubeRadComment on Sacra-licious by Albino HayfordComment on Puzzle III.3: Final Answer by Puzzle III.2: Combinations « BlogorrheaComment on Puzzle I by Puzzle III.3: Big Numbers « Blogorrhea […]