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. 
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.
Best Answer
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$.