![]() Instead of thinking about people around a table like this Our problem was initially about seating teams around a table, but we can easily turn it into a question about coloring the nodes of a graph. This particular polynomial is called a “chromatic polynomial,” because it answers the question: How many ways can you color the nodes of a network (or graph) so that no two adjacent nodes are the same color? Not only does it tell us the numeric answers we want, it also uncovers some of the structure underlying our puzzle. This expression may seem like a strange answer to the question “How many ways can we seat different teams at a square table so that no two teammates are sitting next to each other?” But this polynomial conveys a lot of information about our problem. Since these two situations cover all the possibilities, we add them together to find the total number of possible seatings, just as before: q( q – 1) 2+ q( q – 1)( q – 2) 2. And the bottom can be any color that isn’t one of the two different colors used at the right or left, again leaving q – 2 options. Now, the left can’t be the same as the top or the right, so we have q – 2 options there. Here’s the diagram showing the number of options for each side when the left and right are the same color:Īgain we have q options for the top and q – 1 for the right. Suppose we have q different colors to choose from. Regardless of how many colors we have to choose from, there will always be two cases to consider: the left and right being the same color, and the left and right being different colors. We can now use this strategy for 4, 5, or any q different colors. Since these two scenarios cover all possibilities, we just add them to get 12 + 6 = 18 total possible seatings.Īdding a third color complicated our puzzle, but our hard work will be rewarded. This case yields 3 × 2 × 1 × 1 = 6 possible seatings. And since the right and the left are two different colors, that leaves only one color for the bottom (the same color as the top). For the left, we still have only one option, but for a different reason: It can’t be the same color as the top, which is adjacent, and it can’t be the same color as the right, by assumption. But do you see the problem with that reasoning?Īgain we have three options for the top and two options for the right. What happens at the bottom of our square? It’s tempting to say there is only one option for the last seat, since it is adjacent to both the left and right seats. Once that choice is made, we can choose either of the two remaining colors for the right and left spots. There are now three colors to choose from for the top. How many different seatings are possible if adjacent seats can’t be the same color? Drawing all the possibilities would take a lot of diagrams, so let’s try our counting argument instead. ![]() Imagine there are red, blue and yellow players. Now let’s add a third team with a third color. That gives 2 × 1 × 1 × 1 = 2 total seatings, just as we determined with our diagrams. Using the “fundamental counting principle,” we know that the total number of possibilities is the product of the number of possibilities for each choice. Now, for the bottom seat, there is again only one option: the color we started with. Once we make that choice, we have one option (the other color) for both the right and the left seats. ![]() Let’s start at the top: We have two options, red or blue, for that seat. ![]() There’s a way we can see that there are only two possible seatings without drawing all the different pictures. Suppose a red player is seated at the top of our diagram, as shown here. Let’s start by imagining the players as red and blue. How many different ways can the teams be seated? To prevent cheating, you avoid seating players next to someone from their own team. Suppose a game requires seating two teams of players at a square table. Here’s a simple puzzle that illustrates how. That’s a neat algebra trick, but what is it actually good for? It turns out that polynomials excel at uncovering hidden structure, a fact Huh used to great effect in his proof. For example, you may remember that x 2 + 2 xy + y 2 = ( x + y) 2. But it was also a question about polynomials - those familiar expressions from math class involving sums of variables raised to different powers.Īt some point in school you were probably asked to combine, factor and simplify polynomials. The problem was about complex mathematical objects called “matroids” and combinations of points and lines, or graphs. In 2015, the poet-turned-mathematician June Huh helped solve a problem posed about 50 years earlier.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |