a) Each square has its own unique upper left corner and lower right corner, so the minimum number is $n=5$. We can see that this is possible with the square below. [asy][asy]pair shadered(pair w){ real a,b; a=w.y; b=w.x; fill((a,b)--(a+1,b)--(a+1,b+1)--(a,b+1)--cycle,red); return (a,b);} pair shadeblue(pair w){ real a,b; a=w.y; b=w.x; fill((a,b)--(a+1,b)--(a+1,b+1)--(a,b+1)--cycle,blue); return (a,b);} shadeblue((0,0)); shadeblue((0,1)); shadeblue((0,3)); shadeblue((0,4)); shadeblue((1,0)); shadeblue((2,0)); shadeblue((2,3)); shadeblue((2,4)); shadeblue((3,1)); shadeblue((3,3)); shadeblue((3,4)); shadeblue((4,0)); shadeblue((4,1)); shadeblue((4,2)); shadeblue((4,4)); shadered((0,2)); shadered((1,1)); shadered((1,2)); shadered((1,3)); shadered((1,4)); shadered((2,1)); shadered((2,2)); shadered((3,0)); shadered((3,2)); shadered((4,3)); for(int i=0; i<=5; i=i+1){draw((i,0)--(i,5));} for(int j=0;j<=5;j=j+1){draw((0,j)--(5,j));} [/asy][/asy] b) We prove that every row and column must contain a red square. If there is an all-blue row, for instance, then on top or bottom of this row there are at least two more rows. We'll assume here that they are on top, but if they're below, we can just flip the grid. The four $2\times 2$ squares with this all-blue row as its bottom must be different, but they all have the bottom two squares blue. There are only 4 such $2\times 2$ squares, so these four squares must be them. But this includes an all-blue square. Since there's two rows above the all-blue row, there's a row above the all-blue $2\times 2$ square; the square that is above and intersecting this all-blue square also has its bottom two tiles blue, which is impossible since in order to get all sixteen $2\times 2$ squares in the grid, we must have all unique squares. So our assumption was wrong, and every row (and similarly every column) must have a red tile. Now look at the bottom row. If the very right tile is red, then look the bottom row and left column. Otherwise, look at the bottom row and the right column. In either case, we've shown that there's a tile in the bottom row, and a different tile in the column we're looking at. So there are at least two red tiles here. But the rest is the upper-right or upper-left $4\times 4$ square, which contains all upper-right or upper-left squares of all the $2\times 2$ squares exactly once. Thus by symmetry, this $4\times 4$ square contains exactly 8 red tiles. So we must have at least $10$ red tiles. The arrangement above shows that $10$ is attainable.

Sorry for bumping, but can someone explain this part of tenniskidperson's proof Quote: Now look at the bottom row. If the very right tile is red, then look the bottom row and left column. Otherwise, look at the bottom row and the right column. In either case, we've shown that there's a tile in the bottom row, and a different tile in the column we're looking at. So there are at least two red tiles here. But the rest is the upper-right or upper-left $4\times 4$ square, which contains all upper-right or upper-left squares of all the $2\times 2$ squares exactly once. Thus by symmetry, this $4\times 4$ square contains exactly 8 red tiles. So we must have at least $10$ red tiles. The arrangement above shows that $10$ is attainable. Specific parts I don't understand are what he means by the upper-right or upper-left $4 \times 4$ square, which contains all upper-right or upper-left squares of all the $2\times 2$ squares exactly once.