Just a little bit [!! or a lot!] more preparation in addition to last time, and we can get back on track solving the puzzle at hand (if you’re jumping in midstream, you should go back to the beginning!)

Let’s count some quantities which are significant to our form of puzzles:

- How many edges does K
_{N}have? - How many triangles (K
_{3}) does K_{N}have? - How many K
_{M}does K_{N}have? - How many colorings does K
_{N}have? - How long would it take to exhaustively check all colorings of K
_{N}for a coloring with no monochromatic K_{M}?

Understand here that for our particular puzzles, I am interested in N=5, N=6, and N=100,M=10, but the counting techniques will be universally applicable.

Q1: What is an edge, but a pair of vertices (since we are dealing with complete graphs)? So if we count the number of ways that we can choose a pair of vertices that define an edge, we have N choices for the first vertex, and (since one vertex is already chosen) N-1 choices for the second vertex. Thus we multiply to get N*(N-1). Does this formula work? For K_{5} that gives us 5*(5-1) = 5*4 = 20. It is pretty easy to tell with a quick count that K_{N} actually has only 10 edges, so what went wrong? Why is our count twice as big as it should be? It’s because we counted every edge twice. For instance the edge {2,5} was counted once when vertex 2 was the first choice, and 5 the second, and then it was counted again with 5 as the first choice and 2 as the second. Accounting for this double-counting, the correct formula is thus N*(N-1)/2.

Let’s test it against some other complete graphs: K_{3} by definition has three vertices. The formula predicts that it would have 3*(3-1)/2 = 3*2/2 = 3 edges, which is exactly how many edges a triangle has. Even smaller, K_{2} is simply two vertices connected by all possible edges — which is one edge. And the formula predicts 2*(2-1)/2 = 2*1/2 = 1, which is correct. It is not valid to apply the formula to K_{1} or K_{0}, because the derivation of the formula assumed there are at least a first and a second vertex to pick from, but the formula does serendipitously predict 0 edges in both cases. I’ll let you verify the correctness of the formula for K_{4} and K_{6} (and higher if you want), so that you can just believe it to compute the number of edges in K_{100}.

Q2: We will proceed in the same fashion to determine how many triangles K_{N} has. We can choose 3 vertices in N*(N-1)*(N-2) ways, but we know we will need to account for overcounting. How many times is every triangle counted? More specifically, how many times is triangle 123 counted? Well, here are all the equivalent triangles that get counted separately, which we want to count only once: 123, 132, 213, 231, 312, 321. That’s 6. Does that ring any bells? Those are all the possible permutations of 123, so it’s not surprising that the amount of overcounting is 3! = 3*2*1 = 6. Every triangle gets overcounted 6 times, so we need to correct our formula by dividing by 6: N*(N-1)*(N-2)/3!

Now let’s verify. K_{5} should have 5*4*3/3! = 60/6 = 10 triangles. Go up yonder and count the triangles, and if you count carefully, you’ll see that it’s correct. I’ll let you in on a secret: here’s a gratuitously clever way to count triangles in K_{5}: every edge is defined by 2 vertices. 5-2=3. Thus for every choice of two vertices there are three other vertices that didn’t get chosen, and which form a triangle. So there are just as many triangles (10) as edges (10). For K_{5}, anyways. How many triangles in K_{3}? Since K_{3} is a triangle, it is self-evident that the correct answer is 1. And the formula predicts 3*2*1/3! = 3!/3! = 1. Again, I’ll let the reader verify that the formula is also correct for K_{4} and K_{6}, and then compute a believeable answer for K_{100} (which is not actually a quantity we need to know).

Q3: Looking back at question one, we see that the overcounting of the number of edges is not simply 2, but 2!, the number of ways to order two objects. And when selecting 3 objects, we overcount by a factor of 3!. That pattern holds true generally; when selecting M objects, we start with N choices, then N-1 choices, then N-2 choices…, we are following the process for selecting a permutation — an ordered subset of objects. So the amount of overcounting is the number of ways to order that many objects, which is M!.

So that’s half the problem solved: we know our formula will need to divide by M!. The top of the fraction is also analogous. In order to get ordered subsets of M, we choose from N, then from N-1, then from N-2, … until we have made M choices. It turns out that at our last step we will have (N-M+1) choices, so our general formula is:

C(N,M) = N*(N-1)*(N-2)*…*(N-M+1) / M!

“C(N,M)” reads “the number of combinations of M objects out of N”, or “N choose M”. Combinations are just like permutations, but unordered (hence the division by M!). This general formula answers the previous two questions as well; notice that when M=2, there are two terms (N*(N-1)) on top, and 2! on the bottom (Q1), and when M=3, there are three terms on the top, and 3! on the bottom. So the reader exercise is then to apply the general formula and compute C(100,10). As a hint, if you write out the fraction with 10 terms on the top and 10! on the bottom, you will be able to reduce the fraction by cancelling out all of the factors on the bottom. You still might want to resort to a calculator, or to a spreadsheet (the Excel formula is COMBIN(N,M)).

Q4: Counting the colorings works somewhat differently than all the other counting we have done, because for the first time we are not counting subsets of vertices. But by now we already have the principle down. To count the *number of colorings*, we will count the number of *ways to choose a coloring*, one edge at a time. How many choices for the first edge? 2 (red, blue). How many choices for the second edge? Still 2 — unlike before, our later choices are not contingent on our earlier choices, but rather they are independent. It’s going to be two choices every time, so the only question is how many times? Well, we answered that back in Q1: N*(N-1)/2. So we multiply that many 2’s all together, and that’s how many colorings. Another name for that is exponentiation: 2^(N*(N-1)/2), pronounced “two to the (N*(N-1)/2)”.

Let’s verify first on the small scale. How many colorings of K_{3}? There are 3 edges, thus 2^3 = 2*2*2 = 8 colorings. Call the edges abc, and I’ll show them to you: **abc ****ab****c**** ****a****b****c**** ****a****bc ****a****bc**** ****a****b****c**** ****a****b****c**** abc**.

How many colorings of K_{4}, which has 6 edges? 2^6 = 2*2*2*2*2*2 = 64. If you’re careful, you can write them all out. Reader exercises: how many colorings of K_{5}, K_{6}, and K_{100}?

Q5: This post is way overlong by now, so fortunately this will be quick. I choose to measure “how long to exhaustively search all colorings” by counting the number of edges that have to be checked for whether they are red or blue. To search exhaustively, you need to:

- Search every coloring (all 2^(N*(N-1)/2) of them)
- For each coloring, check every one of the K
_{M}(all N*(N-1)*…*(N-M+1)/M! of them) to see if it is monochromatic - For each K
_{M}, you have to inspect all of its edges (for a K_{3}, all three edges, for a K_{M}, all M*(M-1)/2 of them)

So you multiply those three numbers (#colorings, #subsets, #edges per subset) together, and that’s how long a brute force, exhaustive search will take. For Puzzle I, searching all colorings of K_{5} for monochromatic K_{3} would require checking the colors of this many edges:

[2^(5*4/2)] * [5*4*3/3!] * [3*2/2] = [2^10] * [10] * [3] = 1024*10*3 = 30720

You can compute (or try to compute) the number of edge-color-checks required for an exhaustive search of all colorings of K_{6} for K_{3} as in Puzzle II, or Puzzle III with K_{100} and K_{10} (warning: the numbers get kinda big)!

Next time, I promise, I will finally reveal the supercool answer, so stay tuned!

Puzzle III.3: Big Numbers « Blogorrhea, on October 15, 2006 at 4:39 pm said:[…] Puzzle III.2: Combinations […]

Puzzle III.1: Permutations « Blogorrhea, on December 7, 2006 at 8:18 am said:[…] Next time, we’ll ask (and answer) questions of the form: If we were to search all the colorings of K5 (or K6 (or K100)) for one that had no monochromatic K3 (or K10), how long would it take? […]