Painting a $7\times7$ Grid

Probability Level 4

You have a square grid and are given 7 different colors of paint, and are asked to use each of the colors 7 times. (i.e. paint 7 squares red, 7 squares blue, etc.)

You decide to do this in such a way that you minimize the maximum number of colors any row or column can have.

If/when you succeed, what is the maximum number of colors in any given row or column?

Try other Painting nxn grid problems

0 1 2 3 4 5 6 7

1 solution

Geoff Pilling
Apr 12, 2016

Here is a solution for a maximum of 3 colors in each column and row:

And now for my attempt at an explanation for why it can't be done with 1 or 2 colors...

First off, it can quite easily be seen that if you paint 7 squares the same color, and you add up the total number of rows and columns they occupy, you will always come up with a total greater than or equal to 6.

Now suppose you label each column with the number of colors it contains, and each row with the number of colors it contains, and add up all the resulting numbers. By the above observation, the minimum number you can arrive at is 42 (7 colors * the minimum total of rows and columns they can each occupy).

However, if you were able to find a solution where each row/column could be painted with two or fewer squares, and labeled each column and row with the number of colors it contained, you'd arrive at a maximum total of 28 (7 rows * 2 colors/row + 7 columns * 2 colors/column), far fewer than the minimum number (42) calculated above.

Hopefully that makes sense? If not, see Calvin's solution, below... :)

One additional observation: From the above you can conclude that any solution for a maximum of 3 colors per row must necessarily have exactly 3 colors in each row.

Calvin's solution to why it can't be done with 1 or 2 colors:

Proof by contradiction. Suppose that it can be done with a maximum of 2 colors in each row / column.

For each row and column, we find the number of colors in it. We are interested in this sum over all rows and columns, which we denote by $S$ .

Since there is a maximum of 2 colors, and a total of 14 rows and columns, we get that $S \leq 2 \times 14 = 28$ .

Let's consider another approach of calculating $S$ . For each color, let's count the total number of rows and columns that it appears in. If we use only 1 row, then we need at least 7 columns.
If we use only 2 rows, then we need at least 4 columns. If we use only 3 rows, then we need at least 3 columns. We can continue to show that the total number of rows and columns is at least 6 for a given color.

Since each color needs at least 6 rows and columns, and there are 7 colors, thus $S \geq 6 \times 7 = 42$ .

This is a contradiction since $28 \geq S \geq 42$ .

Great problem!

The explanation of why we can't do it with 2 different colors could be expressed in a much clearer manner.

In the last 2 sentences, it is not immediately clear what you are trying to say, and why we arrive at a contradiciton.

Calvin Lin Staff - 5 years, 2 months ago

Thanks! Yeah, I was thinking that myself, but thought that at least a vague description of my thought process was better than none. Let me think of a better way to explain it.

Geoff Pilling - 5 years, 2 months ago

Here is my suggestion:

Proof by contradiction. Suppose that it can be done with a maximum of 2 colors in each row / column.

For each row and column, we find the number of colors in it. We are interested in this sum over all rows and columns, which we denote by $S$ .

Since there is a maximum of 2 colors, and a total of 14 rows and columns, we get that $S \leq 2 \times 14 = 28$ .

Since each color needs at least 6 rows and columns, and there are 7 colors, thus $S \geq 6 \times 7 = 42$ .

This is a contradiction since $28 \geq S \geq 42$ .

Calvin Lin Staff - 5 years, 2 months ago

@Calvin Lin – Ah very nice! Don't want to take credit for this solution, so I'll reference it in mine! :)

Geoff Pilling - 5 years, 2 months ago

I have updated the solution above accordingly. I'm still not 100% satisfied with the explanation, but hopefully it's a bit cleaner... :/

Geoff Pilling - 5 years, 2 months ago

If you find out that the solution about the impossibility of coloring with 2 colors is unclear then it may mean that it is unclear because is not articulate enough why it is impossible. And if it is not articulate enough why it is impossible it means that it is not pointed exactly where and what makes it impossible so in order to understand better it should be useful to consider constructing such a case by using 2 colors and point out clearly what makes it impossible. So , consider a construction of such a coloring by starting from 1 column or row which will be colored therefore with two colors. I for one took a column and now observe that this can be done in a number of 7/2 = 3 ways. This means that there will be a color , name it a , which will repeat between 4 and 6 times in that column and just consider those 3 cases for such a coloring . Observe that for any of these cases color a that repeats m times will need other 6 squares to be colored for each of it's rows and now it can be tried to color them and see if based on the conditions such a coloring works though this can be considered generally for all cases . For a coloring then taking the m rows there will be just 1 color available. If that color is used in a number of those m rows , name it for example n , then there will be a number of 6 * n rows which will be colored using just that respective color and the color a which is already used in the row therefore the minimum number of colors available shall be greater or equal to 6*n. If therefore there is a color which repeats in 2 of those m rows there will be 12 squares that need to be colored using that color and the remaining available 7 - m colors a but even for the case in which 7 - m is the biggest that is in which color a would repeat the minimum in a column (4 times) it is impossible to color it. Since even for the minimal case (of 4 colors in a row) is impossible it is also impossible for the other cases. Observe that this is more or less the same solution as Calvin's (which also I think would require to be chiseled a little) but that it is a concrete consideration of the abstractions involved due to the generality of proof that is found there and I hope now it's clear why it is impossible but also it should be showed how you arrived at that construction which works.

A A - 5 years, 1 month ago

Well, to be honest, I didn't have a very systematic way of arriving at the answer, just played around a bit until I found the solution. At one point I was trying to prove why it couldn't be done with three colors... :-P Thank you for your insights into the problem!

If someone has a systematic way to arrive at a solution, I would love to hear about it! :)

Geoff Pilling - 5 years, 1 month ago

Yes , that it can be said , I have seen at a pretty great number of solutions for the problems around here. I didn't arrived at that systematic thing either because by accident I put the wrong answer before thinking a lot at it and I double what you said. I would too love to see a systematic solution at this problem. And I too , before entering the wrong answer , considered why it can't be done with 3 colors by extension of the approach in 2 and at more general level and great beautiful problem.

A A - 5 years, 1 month ago

Painting a 7 × 7 7\times7 7 × 7 Grid

1 solution

0 pending reports

Painting a $7\times7$ Grid