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 KN for monochromatic KM (open your browser wide!)
|KN,KM||KN edges||KM edges||# KM||# colorings||# edge-checks|
|K5,K3||C(5,2) = 10||C(3,2) = 3||C(5,3) = 10||210 = 1024||3*10*1024 = 30,720|
|K6,K3||C(6,2) = 15||C(3,2) = 3||C(6,3) = 20||215 = 32,768||3*20*32,768 = 1,966,080|
|K100,K10||C(100,2) = 4950||C(10,2) = 45||C(100,10) = 17,310,309,456,440||24950 ~ 101490.1||45*C(100,10)*24950 ~ 101504.99|
Take a look-see at the last number in that table: 101504.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 H20, compared to the ocean of 101504.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 K100 with no monochromatic K10 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, 101490.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) K10 that are in K100. 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 K100 and K10 to have practically intractable problems. In Puzzle I and Puzzle II, we found out that the magical threshold for K3 is crossed by moving from 5 to 6 vertices. It turns out that mathematicians currently know that the threshold for K4 is crossed by moving from 17 to 18 vertices. But the threshold for K5 is only known to lie between 43 and 49. The threshold for K6 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 K5] 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 K6], we should attempt to destroy the aliens.
OK, so now that you have despaired of solving our K100,K10 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 K10. So across all of the practically infinite number of colorings of K100, what is the proportion of all those colorings in which any one particular K10 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 K10 is red is (1/2)45 = 1/35,184,372,088,832. Similarly, the chance that any WHOLE K10 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 K10 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 K10, the proportion of bad colorings is quite small. But there are a large number of K10 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 K10 to worry about, and chance that any particular K10 is monochromatic), we have exactly what we need to compute the answer to the following question: “Across all of the 24950 colorings of K100, what is the average number of monochromatic K10 per coloring?” The answer is, the number of K10, times the probability per K10, 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 K100,what is the average number of monochromatic K10 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 K10 it had). And what whole number is less than one? Zero. As in Zero monochromatic K10, which is what we are looking for. Therefore, the answer to the question “Does there exist a 2-edge coloring of K100 with Zero monochromatic K10?” is
So what is that coloring of K100? 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 K10? 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 K10, 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 K100 with no monochromatic K10, 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!)