Date: 13 Jan 1995 12:15:47 -0500 From: Cathy Brady Subject: combinations problem In the Family Math book, there is an activity called Rainbow Logic. It's like battleship in that one player sets up a matrix and the other player(s) have to match their matrices by asking questions. The matrix, if it's 3x3, has three pieces of each color which can be put on the board in any position, just so long as each square shares a border with a square with the same color. The players ask "What colors are in column one? (or row three, or column three...)" and the person who is it tells them the color(s) but not in any order. The game can also be played with a 2x2 grid (with 2 colors) or a 4x4 grid (with 4 colors). By drawing the grids, I found that the number of possible layouts for 2x2 is 4, and the number of possible for 3x3 is 72, and for 4x4 - well, I got tired of drawing, but it's over 250. So my question is: Is there a formula for the number of layouts for an nxn grid with n colors where each color is connected by at least one border? Cathy Brady
Date: 17 Jan 1995 00:42:38 GMT From: Dr. Math Subject: Re: combinations problem Hello there! I've got to ask you a question about this before I dive in: when you say each color is connected by at least one border, what exactly does that mean? Does that mean that each region of the same color must be connected? We await your reply.
Date: 16 Jan 1995 19:48:53 -0500 From: Cathy Brady Subject: Re: combinations problem YES
Date: 17 Jan 1995 02:34:53 GMT From: Dr. Math Subject: Re: combinations problem Okay, we've been doing some thinking. We think we've tackled the 4x4 question, and we've come up with a little on the general formula. It looks like finding a closed form general formula might get kind of hairy. Also, we've come up with something different than you got for the 3x3 case. Anyway, the first thing we (fellow Math Doctor Ethan Magness and I) did was to eliminate all the different rotations and color changes, and call them all essentially the same pattern. Once you figure out what the "fundamental" patterns are, you can rotate them four different ways, and then choose the colors two different ways. In general, with an nxn array, you'll always figure out how many different fundamental layouts there will be, and then you'll rotate it four ways and choose the colors n! (which means n(n-1)(n-2)...(2)(1)) ways. So if there are f different fundamental arrays, there are 4fn! total different layouts for your final answer. But there's a complication, because sometimes you'll end up duplicating a pattern by rotating it. For instance, in the 2x2 case, there's only one fundamental array you can make, one that has one color on the top row and the other color on the bottom row. When you rotate this array though, you'll see that rotating it 180 degrees will produce the same array as not rotating it at all. So we've got to get rid of half of these, so we say that there are .5 different fundamental layouts, and then we multiply by 4n!, i.e. 8, and we end up with your answer, 4. In the 3x3 case, we can have three different fundamental layouts. However, if you look at the one that has three straight pieces arranged in columns, you'll notice that again, rotating it 180 degrees has the same effect as not rotating it at all. So really, we'll say we have 2.5 different fundamental arrays, and that the total is 2.5 x 4 x 6 = 60 different layouts. We did this for the 4x4 case too, and we found that there were 28.25 different fundamental arrays you could have (we simplified the process a little by noticing that some of the arrangements were just reflections of each other, and by first looking at arrangements that contained a long four-in-a-row piece across the top). So we found that you would have 28.25 x 4 x 24 = 2712 different total arrangements. Anyway, this is as far as we've gotten, and getting much farther would probably require a lot more insight than we've gotten so far. But it's a pretty cool question, and I encourage you to keep thinking about it! If you find anything else interesting about it, let us know! -Ken "Dr." Math
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.