3
$\begingroup$

Each square of a 100 x 100 square board was painted some color, so that no line (row or column) has more than 4 different colors. What is the maximum number of colors that could have been used? Explain why it is not possible to use more colors and give an example of coloring that uses the maximum number of colors.

I found a configuration using 301 different colors, but I can't prove that it is the best. Configuration This is my configuration, the black points are all different colors, so the number of colors is $98*3 + 2*2 + 2 + 1= 301$, because 3 different colors in 98 columns, the 2 on the edges, the other 1 + 1 in each edge and the blue is only one color so one more.

$\endgroup$
3
  • $\begingroup$ Your construction has $96$ instead of $98$, right? $\endgroup$
    – RobPratt
    Sep 17 at 3:45
  • $\begingroup$ OK, I see now that it’s just a sloppy drawing and a complicated way to count. You have $3$ black in each of the $100$ columns and $1$ blue, yielding $3\cdot100+1=301$. $\endgroup$
    – RobPratt
    Sep 17 at 13:34
  • $\begingroup$ Yeah, I counted it so because I wanted to be more specific, by the way do you know of any app where I can draw the board? I drew it with paint. $\endgroup$
    – RickSanchez
    Sep 17 at 14:14

1 Answer 1

Reset to default
3
$\begingroup$

Let's assume that $302$ colors have been used on the board. Since, no rows can admit $5$ (or more) colors, at least $2$ rows must contain exactly $4$ colors so that all the ($4 \times 2$) colors are distinct. In other words, $8$ colors must have been used to paint the squares of those two rows. Now, consider a column of the board. As two squares of this column have already picked 2 distinct colors, this column can admit at most $2$ more colors. Therefore this board can have at most $2 \times 100 +8$ distinct colors, which is less than $302.$ Hence, the maximum is $301$.

Please note that the first claim of the proof wouldn't be valid if we were working with $301$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .