We color some unit squares in a $ 99\times 99 $ square grid with one of $ 5 $ given distinct colors, such that each color appears the same number of times. On each row and on each column there are no differently colored unit squares. Find the maximum possible number of colored unit squares.
I thought about it: Because $[\frac{198}{5}]=39$, every colour is in at most 39 lines. If there is a colour that is in 39 lines, let it be in $x$ rows and $y$ columns, where $x+y=39$. Then this colour is used at most $xy$ times. It's well known that the maximum of $xy$ is achieved when x and y are almost the same, so $x=20,$ $y=19$. Therefore the maximum is $5.380=1900$. We can achieve it if we colour $5$ rectangles $20\cdot 19$ in diagonal line $5$ different colours
Best Answer
If I understand you correctly, each column/row can contain some cells coloured in one color and rest of them is empty (also row can be empty).
Therefore each column/row have assigned one of five colors or is empty. Coloured cells can appear only on the intersection of row and column with the same colour assigned.
Now, from 99 rows we can pick at most 19 rows for each colour. The same thing could be done for columns. In this moment we can colour $5\times 19\times 19=1805$ cells.
Now comes the tricky part:
We have then 95 rows and columns assigned to colors and 4 rows and columns not assigned. From these rows and columns we can pick one row or column for each colour. This would give additional $19$ cells for each color. After this operation we have 2 (if we pick 3 columns and 2 rows or vice versa) or 0 (if we pick 4 columns and 1 row or vice versa) cells, that doesn't belong to any row or column assigned to any color - it's clear, that we can't distribute evenly between colors.
Therefore finally we have $5\times 19\times 20=1900$ cells, that could be coloured.