Maximum chocolate in a square grid There is a $625 \times 625$ square grid. We have to place chocolates in such a way so that each row and each column contains maximum of $3$ chocolates. What is the maximum number of chocolates we can put in that grid in total?
 A: Since each single piece of chocolate increases by one the number of pieces in one row and one column, the maximal number is clearly $625 \cdot 3 \,\,$. As correctly noted, the strategy of putting $3×3$ squares of chocolate down the diagonal does not give the maximal number, as after $208$ squares we are left with the last row and the last column, and this allows only one piece more. 
However, from this position ($208$ of these
 $3×3$ squares along the diagonal), it is sufficient to randomly choose two pieces with different column and row and move them to the last column without changing their rows. This results in three different columns that lack one piece to arrive to three (one of these column is the last one), and a single blank row (the last one) with no pieces. Placing three pieces at the crossing of these three columns with the last row, we achieve the maximal number of pieces. 
A: Why not just place $3 \times 3$ squares of chocolate down the diagonal? This is a tri-diagonal matrix. Doing this ensures that the maximum number of chocolates per row and column are met. 
A: The below $5 \times 5$ block has three ones in each row and column.  Put $125$ of these down the diagonal.

