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.