- What is the maximum number of dots in the array that can be colored green?
- How many colors would be needed if every rectangle must have four different colors at its corners?
- Repeat for a 4x4 array of dots.
- Repeat for a 5x5 array of dots.

Solutions were received from Kirk Bresniker, Alan O'Donnell, Dan Chirica, and Joseph DeVincentis. I'd intended for "any angle" to be interpreted just that way, but I hadn't considered it might be tough to start working out the off-angle rectangles, so I received various solutions. A few are included below.

From Joseph DeVincentis:

For a 3x3, 2 colors are needed, and up to 6 dots can be green: GGA AGG GAG It is impossible to have 7 green dots because then one row would be entirely green, and any two dots in the same row elsewhere would make a rectangle, and there are enough other dots that two must be in the same row. If every rectangle must have four different colors, no matter how large the array, all the dots must be different colors. Any two dots are part of a rectangle, so if any two dots are the same color, there must be a rectangle which does not have four different colors. For a 4x4, 2 colors are needed, but I have only been able to do it with 8 of each color: AAGG GAAG GGAA GAGA It is impossible to have 10 dots the same color. This would require either one row of four dots all the same color, or two rows of three. If there is a row of four dots the same color, only one dot in each other row can be that color, for a maximum of seven dots. If there are two rows of three dots, there is only one other-colored dot in each row, so there must be two columns with dots in both those rows, making a rectangle. Trying to get 9 of a color leads me to failed solutions like this, where one of the squares of edge sqrt(5) is all the same color: AGGG GAAG GGAA GAGA In a 5x5, three colors are required. If you use only two colors, then each row must have at least three dots of one color. This means that there must be one color which appears at least three times in at least three rows. Each pair of such rows must have dots of this color in exactly one common column (since there are only five columns, and if they have two common columns it forms a rectangle). So the first two such rows collectively contain a dot in every row, and the third row has nowhere to put its three dots of that color, since it can only overlap each other row by one dot (making two). I'm not sure what is the most possible dots of one color, but I managed to use 10: ABGGG GABAA BGABG ABGAB GGBGA Joe

From Alan O'Donnell: The maximum number of nodes of any particular colour is 3n-3, where n is the length edge of the square grid. This corresponds to 1 row containing n-1 of that colour, and the column which doesn't contain that colour has n-1 of that colour too. We are then left with n-1 rows/columns that can each only have 1 more of the given colour. Any other variations of optimal grids are simply the ones below with rows or columns interchanged.

So, for n=3 (3x3), we have 6 greens (denoted as '1') 2 1 1 1 1 2 1 2 1 for n=4 we have 9 greens: 2 1 1 1 1 1 2 2 1 2 1 2 1 2 2 1 and n=5 -> 12 greens. Note that with 2 colours, we need 3 colours! (2x12 < 25, so expected...) 2 1 1 1 1 1 1 2 2 2 1 2 1 2 3 1 2 3 1 2 1 2 2 3 1Update 3/4/05: Joseph points out:

Although he has no all-green rectangles, he has some all-color-2 rectangles (marked by X below)

2 1 1 1 1 1 X 2 1 X 1 X 1 2 X 1 2 1 1 1 1 1 1 2 X 2 1 X 1 2 3 1 2 3 1 X 1 2 X 3 1These can easily be remedied, by changing one 2 to a 3 in these two solutions. This has the side-effect of making the 4x4 solution require three colors in order to get 9 squares of a single color, when it can otherwise be done in two colors.

Mail to Ken