Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions

Let $n=2t+1$. Then there are $(t+1)^{2}$ black squares in a row that is an even number of rows away from the bottom row (i.e. in the first,third,fifth... row counting from the bottom). But each of these squares must be covered by a different tromino- so at least $(t+1)^{2}= \frac{(n+1)^{2}}{4}$ trominos are required. If $n=3,5$, then this means that the task is impossible since there is not enough room on the board for this many trominos. For $n=7$ an arrangement can be found (split the board into 3 3x4 rectangles, tile them in the obvious fashion, and then fill in all but a remaining white square). It uses 16 tiles. (Notice that $16=\frac{(7+1)^{2}}{4}$). Now suppose that there is a tiling for $n=k$ ($k$ odd) that uses $\frac{(k+1)^{2}}{4}$ tiles. Then add to this a $2$x$(k+2)$ and a $2$x$k$ rectangle. Each of these can be covered (its black squares covered) by cutting a $2$x$3$ rectangle off one end, putting 2 trominos on it and then a line of trominos covering the 2 black squares in each $2$x$2$ square. Between these two rectangles, we have used an extra $k+2$ trominos. So a $(k+2)$x$(k+2)$ rectangle can be tiled (have its black squares covered) using $\frac{(k+1)^{2}}{4}+k+2=\frac{(k+3)^{2}}{4}$ tiles. So by induction, for all odd $n\geq 7$, we can tile the black squares of an $n$x$n$ board using $\frac{(n+1)^{2}}{4}$ trominos. We have also shown this to be the minimum.

Let $n=2k+1$. I claim that any odd $n \geq 7$ works and the minimum number of trominos is $(k+1)^2$. Estimation Consider an $n \times n$ table and label the rows $1,2, \dots, n$ from top to bottom. Consider an odd row. Each tromino covers exactly one black cell in this row. But there are $k+1$ black cells in this row so we need at least $k+1$ trominos for this row. Since trominos from each odd row are distinct, the number of trominos at least $(k+1)^2$. This immediately proves $n=1,3,5$ are impossible since in these cases, the number of cells covered by trominos $3(k+1)^2 > n^2$. Construction We proceed by induction on odd numbers $\geq 7$. Base case: $n=7$ [asy][asy] /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */ import graph; size(6cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -0.3066666666666637, xmax = 12.84, ymin = 3, ymax = 10.906666666666675; /* image dimensions */ pen wrwrwr = rgb(0.3803921568627451,0.3803921568627451,0.3803921568627451); pen rvwvcq = rgb(0.08235294117647059,0.396078431372549,0.7529411764705882); draw((2.52,4.14)--(7.78,4.14)--(7.78,9.4)--(2.52,9.4)--cycle, linewidth(2) + wrwrwr); draw((2.52,9.4)--(4.0228571428571325,9.4)--(4.022857142857132,7.897142857142854)--(3.2714285714285634,7.897142857142854)--(3.2714285714285642,8.648571428571428)--(2.52,8.64857142857143)--cycle, linewidth(4) + rvwvcq); draw((4.0228571428571325,9.4)--(5.525714285714275,9.4)--(5.525714285714273,7.897142857142853)--(4.774285714285702,7.897142857142853)--(4.774285714285701,8.648571428571426)--(4.022857142857132,8.648571428571428)--cycle, linewidth(4) + rvwvcq); draw((5.525714285714275,9.4)--(5.525714285714273,7.897142857142853)--(7.028571428571429,7.897142857142853)--(7.02857142857143,8.648571428571428)--(6.277142857142856,8.648571428571426)--(6.277142857142856,9.4)--cycle, linewidth(4) + rvwvcq); draw((6.277142857142856,9.4)--(6.277142857142856,8.648571428571426)--(7.02857142857143,8.648571428571428)--(7.028571428571429,7.897142857142853)--(7.78,7.897142857142853)--(7.78,9.4)--cycle, linewidth(4) + rvwvcq); draw((2.52,8.64857142857143)--(2.52,7.145714285714274)--(4.022857142857132,7.145714285714274)--(4.022857142857132,7.897142857142854)--(3.2714285714285634,7.897142857142854)--(3.2714285714285642,8.648571428571428)--cycle, linewidth(4) + rvwvcq); draw((4.022857142857132,8.648571428571428)--(4.022857142857132,7.145714285714274)--(5.525714285714273,7.1457142857142735)--(5.525714285714273,7.897142857142853)--(4.774285714285702,7.897142857142853)--(4.774285714285701,8.648571428571426)--cycle, linewidth(4) + rvwvcq); draw((5.525714285714273,7.897142857142853)--(6.277142857142855,7.897142857142853)--(6.277142857142855,6.3942857142857)--(4.7742857142857,6.3942857142857)--(4.774285714285702,7.1457142857142735)--(5.525714285714273,7.1457142857142735)--cycle, linewidth(4) + rvwvcq); draw((7.028571428571429,7.897142857142853)--(7.0285714285714285,7.145714285714274)--(6.277142857142855,7.1457142857142735)--(6.277142857142855,6.3942857142857)--(7.78,6.394285714285699)--(7.78,7.897142857142853)--cycle, linewidth(4) + rvwvcq); draw((3.2714285714285634,7.145714285714274)--(3.271428571428563,6.394285714285701)--(4.022857142857131,6.394285714285701)--(4.022857142857131,5.642857142857133)--(2.52,5.642857142857132)--(2.52,7.145714285714274)--cycle, linewidth(4) + rvwvcq); draw((3.2714285714285634,7.145714285714274)--(3.271428571428563,6.394285714285701)--(4.022857142857131,6.394285714285701)--(4.022857142857131,5.642857142857133)--(4.7742857142857,5.642857142857132)--(4.774285714285702,7.1457142857142735)--cycle, linewidth(4) + rvwvcq); draw((6.277142857142855,6.3942857142857)--(6.277142857142856,4.891428571428563)--(5.525714285714272,4.891428571428563)--(5.5257142857142725,5.642857142857132)--(4.7742857142857,5.642857142857132)--(4.7742857142857,6.3942857142857)--cycle, linewidth(4) + rvwvcq); draw((6.277142857142855,6.3942857142857)--(6.277142857142856,5.642857142857132)--(7.028571428571429,5.642857142857132)--(7.028571428571429,4.8914285714285635)--(7.78,4.891428571428562)--(7.78,6.394285714285699)--cycle, linewidth(4) + rvwvcq); draw((6.277142857142856,5.642857142857132)--(6.277142857142855,4.14)--(7.78,4.14)--(7.78,4.891428571428562)--(7.028571428571429,4.8914285714285635)--(7.028571428571429,5.642857142857132)--cycle, linewidth(4) + rvwvcq); draw((4.7742857142857,5.642857142857132)--(4.774285714285699,4.14)--(6.277142857142855,4.14)--(6.277142857142856,4.891428571428563)--(5.525714285714272,4.891428571428563)--(5.5257142857142725,5.642857142857132)--cycle, linewidth(4) + rvwvcq); draw((3.271428571428563,5.642857142857133)--(3.2714285714285625,4.8914285714285635)--(4.02285714285713,4.8914285714285635)--(4.022857142857131,4.14)--(4.774285714285699,4.14)--(4.7742857142857,5.642857142857132)--cycle, linewidth(4) + rvwvcq); draw((2.52,5.642857142857132)--(2.52,4.14)--(4.022857142857131,4.14)--(4.02285714285713,4.8914285714285635)--(3.2714285714285625,4.8914285714285635)--(3.271428571428563,5.642857142857133)--cycle, linewidth(4) + rvwvcq); /* draw figures */ draw((2.52,4.14)--(7.78,4.14), linewidth(2) + wrwrwr); draw((7.78,4.14)--(7.78,9.4), linewidth(2) + wrwrwr); draw((7.78,9.4)--(2.52,9.4), linewidth(2) + wrwrwr); draw((2.52,9.4)--(2.52,4.14), linewidth(2) + wrwrwr); draw((7.78,9.4)--(7.78,4.14), linewidth(2) + wrwrwr); draw((7.02857142857143,9.4)--(7.0285714285714285,4.14), linewidth(2) + wrwrwr); draw((6.277142857142856,9.4)--(6.277142857142855,4.14), linewidth(2) + wrwrwr); draw((5.525714285714275,9.4)--(5.5257142857142725,4.14), linewidth(2) + wrwrwr); draw((4.774285714285702,9.4)--(4.774285714285699,4.14), linewidth(2) + wrwrwr); draw((3.2714285714285647,9.4)--(3.271428571428563,4.14), linewidth(2) + wrwrwr); draw((4.0228571428571325,9.4)--(4.022857142857131,4.14), linewidth(2) + wrwrwr); draw((2.52,8.64857142857143)--(7.78,8.648571428571428), linewidth(2) + wrwrwr); draw((2.52,7.897142857142855)--(7.78,7.897142857142853), linewidth(2) + wrwrwr); draw((2.52,7.145714285714274)--(7.78,7.145714285714273), linewidth(2) + wrwrwr); draw((2.52,6.394285714285701)--(7.78,6.394285714285699), linewidth(2) + wrwrwr); draw((2.52,5.642857142857132)--(7.78,5.64285714285713), linewidth(2) + wrwrwr); draw((2.52,4.8914285714285635)--(7.78,4.891428571428562), linewidth(2) + wrwrwr); draw((2.52,9.4)--(4.0228571428571325,9.4), linewidth(4) + rvwvcq); draw((4.0228571428571325,9.4)--(4.022857142857132,7.897142857142854), linewidth(4) + rvwvcq); draw((4.022857142857132,7.897142857142854)--(3.2714285714285634,7.897142857142854), linewidth(4) + rvwvcq); draw((3.2714285714285634,7.897142857142854)--(3.2714285714285642,8.648571428571428), linewidth(4) + rvwvcq); draw((3.2714285714285642,8.648571428571428)--(2.52,8.64857142857143), linewidth(4) + rvwvcq); draw((2.52,8.64857142857143)--(2.52,9.4), linewidth(4) + rvwvcq); draw((4.0228571428571325,9.4)--(5.525714285714275,9.4), linewidth(4) + rvwvcq); draw((5.525714285714275,9.4)--(5.525714285714273,7.897142857142853), linewidth(4) + rvwvcq); draw((5.525714285714273,7.897142857142853)--(4.774285714285702,7.897142857142853), linewidth(4) + rvwvcq); draw((4.774285714285702,7.897142857142853)--(4.774285714285701,8.648571428571426), linewidth(4) + rvwvcq); draw((4.774285714285701,8.648571428571426)--(4.022857142857132,8.648571428571428), linewidth(4) + rvwvcq); draw((4.022857142857132,8.648571428571428)--(4.0228571428571325,9.4), linewidth(4) + rvwvcq); draw((5.525714285714275,9.4)--(5.525714285714273,7.897142857142853), linewidth(4) + rvwvcq); draw((5.525714285714273,7.897142857142853)--(7.028571428571429,7.897142857142853), linewidth(4) + rvwvcq); draw((7.028571428571429,7.897142857142853)--(7.02857142857143,8.648571428571428), linewidth(4) + rvwvcq); draw((7.02857142857143,8.648571428571428)--(6.277142857142856,8.648571428571426), linewidth(4) + rvwvcq); draw((6.277142857142856,8.648571428571426)--(6.277142857142856,9.4), linewidth(4) + rvwvcq); draw((6.277142857142856,9.4)--(5.525714285714275,9.4), linewidth(4) + rvwvcq); draw((6.277142857142856,9.4)--(6.277142857142856,8.648571428571426), linewidth(4) + rvwvcq); draw((6.277142857142856,8.648571428571426)--(7.02857142857143,8.648571428571428), linewidth(4) + rvwvcq); draw((7.02857142857143,8.648571428571428)--(7.028571428571429,7.897142857142853), linewidth(4) + rvwvcq); draw((7.028571428571429,7.897142857142853)--(7.78,7.897142857142853), linewidth(4) + rvwvcq); draw((7.78,7.897142857142853)--(7.78,9.4), linewidth(4) + rvwvcq); draw((7.78,9.4)--(6.277142857142856,9.4), linewidth(4) + rvwvcq); draw((2.52,8.64857142857143)--(2.52,7.145714285714274), linewidth(4) + rvwvcq); draw((2.52,7.145714285714274)--(4.022857142857132,7.145714285714274), linewidth(4) + rvwvcq); draw((4.022857142857132,7.145714285714274)--(4.022857142857132,7.897142857142854), linewidth(4) + rvwvcq); draw((4.022857142857132,7.897142857142854)--(3.2714285714285634,7.897142857142854), linewidth(4) + rvwvcq); draw((3.2714285714285634,7.897142857142854)--(3.2714285714285642,8.648571428571428), linewidth(4) + rvwvcq); draw((3.2714285714285642,8.648571428571428)--(2.52,8.64857142857143), linewidth(4) + rvwvcq); draw((4.022857142857132,8.648571428571428)--(4.022857142857132,7.145714285714274), linewidth(4) + rvwvcq); draw((4.022857142857132,7.145714285714274)--(5.525714285714273,7.1457142857142735), linewidth(4) + rvwvcq); draw((5.525714285714273,7.1457142857142735)--(5.525714285714273,7.897142857142853), linewidth(4) + rvwvcq); draw((5.525714285714273,7.897142857142853)--(4.774285714285702,7.897142857142853), linewidth(4) + rvwvcq); draw((4.774285714285702,7.897142857142853)--(4.774285714285701,8.648571428571426), linewidth(4) + rvwvcq); draw((4.774285714285701,8.648571428571426)--(4.022857142857132,8.648571428571428), linewidth(4) + rvwvcq); draw((5.525714285714273,7.897142857142853)--(6.277142857142855,7.897142857142853), linewidth(4) + rvwvcq); draw((6.277142857142855,7.897142857142853)--(6.277142857142855,6.3942857142857), linewidth(4) + rvwvcq); draw((6.277142857142855,6.3942857142857)--(4.7742857142857,6.3942857142857), linewidth(4) + rvwvcq); draw((4.7742857142857,6.3942857142857)--(4.774285714285702,7.1457142857142735), linewidth(4) + rvwvcq); draw((4.774285714285702,7.1457142857142735)--(5.525714285714273,7.1457142857142735), linewidth(4) + rvwvcq); draw((5.525714285714273,7.1457142857142735)--(5.525714285714273,7.897142857142853), linewidth(4) + rvwvcq); draw((7.028571428571429,7.897142857142853)--(7.0285714285714285,7.145714285714274), linewidth(4) + rvwvcq); draw((7.0285714285714285,7.145714285714274)--(6.277142857142855,7.1457142857142735), linewidth(4) + rvwvcq); draw((6.277142857142855,7.1457142857142735)--(6.277142857142855,6.3942857142857), linewidth(4) + rvwvcq); draw((6.277142857142855,6.3942857142857)--(7.78,6.394285714285699), linewidth(4) + rvwvcq); draw((7.78,6.394285714285699)--(7.78,7.897142857142853), linewidth(4) + rvwvcq); draw((7.78,7.897142857142853)--(7.028571428571429,7.897142857142853), linewidth(4) + rvwvcq); draw((3.2714285714285634,7.145714285714274)--(3.271428571428563,6.394285714285701), linewidth(4) + rvwvcq); draw((3.271428571428563,6.394285714285701)--(4.022857142857131,6.394285714285701), linewidth(4) + rvwvcq); draw((4.022857142857131,6.394285714285701)--(4.022857142857131,5.642857142857133), linewidth(4) + rvwvcq); draw((4.022857142857131,5.642857142857133)--(2.52,5.642857142857132), linewidth(4) + rvwvcq); draw((2.52,5.642857142857132)--(2.52,7.145714285714274), linewidth(4) + rvwvcq); draw((2.52,7.145714285714274)--(3.2714285714285634,7.145714285714274), linewidth(4) + rvwvcq); draw((3.2714285714285634,7.145714285714274)--(3.271428571428563,6.394285714285701), linewidth(4) + rvwvcq); draw((3.271428571428563,6.394285714285701)--(4.022857142857131,6.394285714285701), linewidth(4) + rvwvcq); draw((4.022857142857131,6.394285714285701)--(4.022857142857131,5.642857142857133), linewidth(4) + rvwvcq); draw((4.022857142857131,5.642857142857133)--(4.7742857142857,5.642857142857132), linewidth(4) + rvwvcq); draw((4.7742857142857,5.642857142857132)--(4.774285714285702,7.1457142857142735), linewidth(4) + rvwvcq); draw((4.774285714285702,7.1457142857142735)--(3.2714285714285634,7.145714285714274), linewidth(4) + rvwvcq); draw((6.277142857142855,6.3942857142857)--(6.277142857142856,4.891428571428563), linewidth(4) + rvwvcq); draw((6.277142857142856,4.891428571428563)--(5.525714285714272,4.891428571428563), linewidth(4) + rvwvcq); draw((5.525714285714272,4.891428571428563)--(5.5257142857142725,5.642857142857132), linewidth(4) + rvwvcq); draw((5.5257142857142725,5.642857142857132)--(4.7742857142857,5.642857142857132), linewidth(4) + rvwvcq); draw((4.7742857142857,5.642857142857132)--(4.7742857142857,6.3942857142857), linewidth(4) + rvwvcq); draw((4.7742857142857,6.3942857142857)--(6.277142857142855,6.3942857142857), linewidth(4) + rvwvcq); draw((6.277142857142855,6.3942857142857)--(6.277142857142856,5.642857142857132), linewidth(4) + rvwvcq); draw((6.277142857142856,5.642857142857132)--(7.028571428571429,5.642857142857132), linewidth(4) + rvwvcq); draw((7.028571428571429,5.642857142857132)--(7.028571428571429,4.8914285714285635), linewidth(4) + rvwvcq); draw((7.028571428571429,4.8914285714285635)--(7.78,4.891428571428562), linewidth(4) + rvwvcq); draw((7.78,4.891428571428562)--(7.78,6.394285714285699), linewidth(4) + rvwvcq); draw((7.78,6.394285714285699)--(6.277142857142855,6.3942857142857), linewidth(4) + rvwvcq); draw((6.277142857142856,5.642857142857132)--(6.277142857142855,4.14), linewidth(4) + rvwvcq); draw((6.277142857142855,4.14)--(7.78,4.14), linewidth(4) + rvwvcq); draw((7.78,4.14)--(7.78,4.891428571428562), linewidth(4) + rvwvcq); draw((7.78,4.891428571428562)--(7.028571428571429,4.8914285714285635), linewidth(4) + rvwvcq); draw((7.028571428571429,4.8914285714285635)--(7.028571428571429,5.642857142857132), linewidth(4) + rvwvcq); draw((7.028571428571429,5.642857142857132)--(6.277142857142856,5.642857142857132), linewidth(4) + rvwvcq); draw((4.7742857142857,5.642857142857132)--(4.774285714285699,4.14), linewidth(4) + rvwvcq); draw((4.774285714285699,4.14)--(6.277142857142855,4.14), linewidth(4) + rvwvcq); draw((6.277142857142855,4.14)--(6.277142857142856,4.891428571428563), linewidth(4) + rvwvcq); draw((6.277142857142856,4.891428571428563)--(5.525714285714272,4.891428571428563), linewidth(4) + rvwvcq); draw((5.525714285714272,4.891428571428563)--(5.5257142857142725,5.642857142857132), linewidth(4) + rvwvcq); draw((5.5257142857142725,5.642857142857132)--(4.7742857142857,5.642857142857132), linewidth(4) + rvwvcq); draw((3.271428571428563,5.642857142857133)--(3.2714285714285625,4.8914285714285635), linewidth(4) + rvwvcq); draw((3.2714285714285625,4.8914285714285635)--(4.02285714285713,4.8914285714285635), linewidth(4) + rvwvcq); draw((4.02285714285713,4.8914285714285635)--(4.022857142857131,4.14), linewidth(4) + rvwvcq); draw((4.022857142857131,4.14)--(4.774285714285699,4.14), linewidth(4) + rvwvcq); draw((4.774285714285699,4.14)--(4.7742857142857,5.642857142857132), linewidth(4) + rvwvcq); draw((4.7742857142857,5.642857142857132)--(3.271428571428563,5.642857142857133), linewidth(4) + rvwvcq); draw((2.52,5.642857142857132)--(2.52,4.14), linewidth(4) + rvwvcq); draw((2.52,4.14)--(4.022857142857131,4.14), linewidth(4) + rvwvcq); draw((4.022857142857131,4.14)--(4.02285714285713,4.8914285714285635), linewidth(4) + rvwvcq); draw((4.02285714285713,4.8914285714285635)--(3.2714285714285625,4.8914285714285635), linewidth(4) + rvwvcq); draw((3.2714285714285625,4.8914285714285635)--(3.271428571428563,5.642857142857133), linewidth(4) + rvwvcq); draw((3.271428571428563,5.642857142857133)--(2.52,5.642857142857132), linewidth(4) + rvwvcq); /* dots and labels */ clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy][/asy] Now to induct from $n$ to $n+2$ just consider the following, [asy][asy] /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */ import graph; size(6cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = 0.37333333333333646, xmax = 13.52, ymin = 2.02666666666667, ymax = 9.933333333333339; /* image dimensions */ pen wrwrwr = rgb(0.3803921568627451,0.3803921568627451,0.3803921568627451); pen rvwvcq = rgb(0.08235294117647059,0.396078431372549,0.7529411764705882); draw((7.78,2.6371428571428766)--(7.78,3.3885714285714377)--(8.531428571428568,3.38857142857143)--(8.531428571428568,4.14)--(9.28285714285714,4.14)--(9.282857142857138,2.6371428571428353)--cycle, linewidth(4) + rvwvcq); draw((8.531428571428568,4.14)--(7.0285714285714285,4.14)--(7.0285714285714285,2.6371428571428766)--(7.78,2.6371428571428766)--(7.78,3.3885714285714377)--(8.531428571428568,3.38857142857143)--cycle, linewidth(4) + rvwvcq); draw((5.5257142857142725,2.6371428571428757)--(5.5257142857142725,4.14)--(7.0285714285714285,4.14)--(7.028571428571429,3.3885714285714377)--(6.277142857142856,3.3885714285714372)--(6.277142857142856,2.6371428571428757)--cycle, linewidth(4) + rvwvcq); draw((5.5257142857142725,4.14)--(4.022857142857131,4.14)--(4.022857142857132,2.6371428571428743)--(4.7742857142857,2.6371428571428748)--(4.774285714285699,3.3885714285714372)--(5.525714285714271,3.388571428571437)--cycle, linewidth(4) + rvwvcq); draw((2.52,2.637142857142873)--(2.52,4.14)--(4.022857142857131,4.14)--(4.022857142857132,3.3885714285714363)--(3.2714285714285634,3.388571428571436)--(3.2714285714285634,2.637142857142874)--cycle, linewidth(4) + rvwvcq); draw((9.28285714285714,4.14)--(7.78,4.14)--(7.78,4.891428571428562)--(7.78,5.64285714285713)--(8.53142857142857,5.642857142857126)--(8.53142857142857,4.89142857142856)--(9.28285714285714,4.891428571428561)--cycle, linewidth(4) + rvwvcq); draw((7.78,5.64285714285713)--(7.78,7.145714285714273)--(8.531428571428568,7.145714285714275)--(8.531428571428568,6.3942857142857)--(9.28285714285714,6.394285714285698)--(9.28285714285714,5.642857142857129)--(8.53142857142857,5.642857142857126)--cycle, linewidth(4) + rvwvcq); draw((7.78,7.145714285714273)--(7.78,8.648571428571428)--(8.531428571428572,8.64857142857143)--(8.53142857142857,7.897142857142855)--(9.282857142857141,7.897142857142852)--(9.28285714285714,7.145714285714272)--(8.531428571428568,7.145714285714275)--cycle, linewidth(4) + rvwvcq); draw((7.78,9.4)--(9.282857142857143,9.4)--(9.282857142857141,7.897142857142852)--(8.53142857142857,7.897142857142855)--(8.531428571428572,8.64857142857143)--(7.78,8.648571428571428)--cycle, linewidth(4) + rvwvcq); /* draw figures */ draw((2.52,3.388571428571436)--(7.78,3.3885714285714377), linewidth(2) + wrwrwr); draw((8.53142857142857,9.4)--(8.531428571428568,4.14), linewidth(2) + wrwrwr); draw((7.78,3.3885714285714377)--(8.531428571428568,3.38857142857143), linewidth(2) + wrwrwr); draw((2.52,3.388571428571436)--(2.52,4.14), linewidth(2) + wrwrwr); draw((7.78,9.4)--(8.53142857142857,9.4), linewidth(2) + wrwrwr); draw((9.28285714285714,4.14)--(9.282857142857143,9.4), linewidth(2) + wrwrwr); draw((8.53142857142857,9.4)--(9.282857142857143,9.4), linewidth(2) + wrwrwr); draw((9.28285714285714,4.14)--(8.531428571428568,4.14), linewidth(2) + wrwrwr); draw((2.52,2.637142857142873)--(7.78,2.6371428571428766), linewidth(2) + wrwrwr); draw((2.52,3.388571428571436)--(2.52,2.637142857142873), linewidth(2) + wrwrwr); draw((7.78,2.6371428571428766)--(9.282857142857138,2.6371428571428353), linewidth(2) + wrwrwr); draw((9.282857142857138,2.6371428571428353)--(9.28285714285714,4.14), linewidth(2) + wrwrwr); draw((8.531428571428568,3.38857142857143)--(9.282857142857141,3.3885714285714146), linewidth(2) + wrwrwr); draw((8.531428571428568,3.38857142857143)--(8.531428571428572,2.6371428571428646), linewidth(2) + wrwrwr); draw((7.78,3.3885714285714377)--(7.78,2.6371428571428766), linewidth(2) + wrwrwr); draw((7.78,8.648571428571428)--(9.282857142857141,8.648571428571428), linewidth(2) + wrwrwr); draw((7.78,7.897142857142853)--(9.282857142857141,7.897142857142852), linewidth(2) + wrwrwr); draw((7.78,7.145714285714273)--(9.28285714285714,7.145714285714272), linewidth(2) + wrwrwr); draw((7.78,6.394285714285699)--(9.28285714285714,6.394285714285698), linewidth(2) + wrwrwr); draw((7.78,5.64285714285713)--(9.28285714285714,5.642857142857129), linewidth(2) + wrwrwr); draw((7.78,4.891428571428562)--(9.28285714285714,4.891428571428561), linewidth(2) + wrwrwr); draw((7.78,4.14)--(8.531428571428568,4.14), linewidth(2) + wrwrwr); draw((7.78,4.14)--(7.78,3.3885714285714377), linewidth(2) + wrwrwr); draw((7.0285714285714285,4.14)--(7.0285714285714285,2.6371428571428766), linewidth(2) + wrwrwr); draw((6.277142857142856,2.6371428571428757)--(6.277142857142855,4.14), linewidth(2) + wrwrwr); draw((5.5257142857142725,2.6371428571428757)--(5.5257142857142725,4.14), linewidth(2) + wrwrwr); draw((4.774285714285699,4.14)--(4.7742857142857,2.6371428571428748), linewidth(2) + wrwrwr); draw((4.022857142857131,4.14)--(4.022857142857132,2.6371428571428743), linewidth(2) + wrwrwr); draw((3.271428571428563,4.14)--(3.2714285714285634,2.637142857142874), linewidth(2) + wrwrwr); draw((2.52,4.14)--(7.78,4.14), linewidth(2) + wrwrwr); draw((7.78,4.14)--(7.78,9.4), linewidth(2) + wrwrwr); draw((8.531428571428568,4.14)--(8.531428571428568,3.38857142857143), linewidth(2) + wrwrwr); draw((7.78,2.6371428571428766)--(7.78,3.3885714285714377), linewidth(4) + rvwvcq); draw((7.78,3.3885714285714377)--(8.531428571428568,3.38857142857143), linewidth(4) + rvwvcq); draw((8.531428571428568,3.38857142857143)--(8.531428571428568,4.14), linewidth(4) + rvwvcq); draw((8.531428571428568,4.14)--(9.28285714285714,4.14), linewidth(4) + rvwvcq); draw((9.28285714285714,4.14)--(9.282857142857138,2.6371428571428353), linewidth(4) + rvwvcq); draw((9.282857142857138,2.6371428571428353)--(7.78,2.6371428571428766), linewidth(4) + rvwvcq); draw((8.531428571428568,4.14)--(7.0285714285714285,4.14), linewidth(4) + rvwvcq); draw((7.0285714285714285,4.14)--(7.0285714285714285,2.6371428571428766), linewidth(4) + rvwvcq); draw((7.0285714285714285,2.6371428571428766)--(7.78,2.6371428571428766), linewidth(4) + rvwvcq); draw((7.78,2.6371428571428766)--(7.78,3.3885714285714377), linewidth(4) + rvwvcq); draw((7.78,3.3885714285714377)--(8.531428571428568,3.38857142857143), linewidth(4) + rvwvcq); draw((8.531428571428568,3.38857142857143)--(8.531428571428568,4.14), linewidth(4) + rvwvcq); draw((5.5257142857142725,2.6371428571428757)--(5.5257142857142725,4.14), linewidth(4) + rvwvcq); draw((5.5257142857142725,4.14)--(7.0285714285714285,4.14), linewidth(4) + rvwvcq); draw((7.0285714285714285,4.14)--(7.028571428571429,3.3885714285714377), linewidth(4) + rvwvcq); draw((7.028571428571429,3.3885714285714377)--(6.277142857142856,3.3885714285714372), linewidth(4) + rvwvcq); draw((6.277142857142856,3.3885714285714372)--(6.277142857142856,2.6371428571428757), linewidth(4) + rvwvcq); draw((6.277142857142856,2.6371428571428757)--(5.5257142857142725,2.6371428571428757), linewidth(4) + rvwvcq); draw((5.5257142857142725,4.14)--(4.022857142857131,4.14), linewidth(4) + rvwvcq); draw((4.022857142857131,4.14)--(4.022857142857132,2.6371428571428743), linewidth(4) + rvwvcq); draw((4.022857142857132,2.6371428571428743)--(4.7742857142857,2.6371428571428748), linewidth(4) + rvwvcq); draw((4.7742857142857,2.6371428571428748)--(4.774285714285699,3.3885714285714372), linewidth(4) + rvwvcq); draw((4.774285714285699,3.3885714285714372)--(5.525714285714271,3.388571428571437), linewidth(4) + rvwvcq); draw((5.525714285714271,3.388571428571437)--(5.5257142857142725,4.14), linewidth(4) + rvwvcq); draw((2.52,2.637142857142873)--(2.52,4.14), linewidth(4) + rvwvcq); draw((2.52,4.14)--(4.022857142857131,4.14), linewidth(4) + rvwvcq); draw((4.022857142857131,4.14)--(4.022857142857132,3.3885714285714363), linewidth(4) + rvwvcq); draw((4.022857142857132,3.3885714285714363)--(3.2714285714285634,3.388571428571436), linewidth(4) + rvwvcq); draw((3.2714285714285634,3.388571428571436)--(3.2714285714285634,2.637142857142874), linewidth(4) + rvwvcq); draw((3.2714285714285634,2.637142857142874)--(2.52,2.637142857142873), linewidth(4) + rvwvcq); draw((9.28285714285714,4.14)--(7.78,4.14), linewidth(4) + rvwvcq); draw((7.78,4.14)--(7.78,4.891428571428562), linewidth(4) + rvwvcq); draw((7.78,4.891428571428562)--(7.78,5.64285714285713), linewidth(4) + rvwvcq); draw((7.78,5.64285714285713)--(8.53142857142857,5.642857142857126), linewidth(4) + rvwvcq); draw((8.53142857142857,5.642857142857126)--(8.53142857142857,4.89142857142856), linewidth(4) + rvwvcq); draw((8.53142857142857,4.89142857142856)--(9.28285714285714,4.891428571428561), linewidth(4) + rvwvcq); draw((9.28285714285714,4.891428571428561)--(9.28285714285714,4.14), linewidth(4) + rvwvcq); draw((7.78,5.64285714285713)--(7.78,7.145714285714273), linewidth(4) + rvwvcq); draw((7.78,7.145714285714273)--(8.531428571428568,7.145714285714275), linewidth(4) + rvwvcq); draw((8.531428571428568,7.145714285714275)--(8.531428571428568,6.3942857142857), linewidth(4) + rvwvcq); draw((8.531428571428568,6.3942857142857)--(9.28285714285714,6.394285714285698), linewidth(4) + rvwvcq); draw((9.28285714285714,6.394285714285698)--(9.28285714285714,5.642857142857129), linewidth(4) + rvwvcq); draw((9.28285714285714,5.642857142857129)--(8.53142857142857,5.642857142857126), linewidth(4) + rvwvcq); draw((8.53142857142857,5.642857142857126)--(7.78,5.64285714285713), linewidth(4) + rvwvcq); draw((7.78,7.145714285714273)--(7.78,8.648571428571428), linewidth(4) + rvwvcq); draw((7.78,8.648571428571428)--(8.531428571428572,8.64857142857143), linewidth(4) + rvwvcq); draw((8.531428571428572,8.64857142857143)--(8.53142857142857,7.897142857142855), linewidth(4) + rvwvcq); draw((8.53142857142857,7.897142857142855)--(9.282857142857141,7.897142857142852), linewidth(4) + rvwvcq); draw((9.282857142857141,7.897142857142852)--(9.28285714285714,7.145714285714272), linewidth(4) + rvwvcq); draw((9.28285714285714,7.145714285714272)--(8.531428571428568,7.145714285714275), linewidth(4) + rvwvcq); draw((8.531428571428568,7.145714285714275)--(7.78,7.145714285714273), linewidth(4) + rvwvcq); draw((7.78,9.4)--(9.282857142857143,9.4), linewidth(4) + rvwvcq); draw((9.282857142857143,9.4)--(9.282857142857141,7.897142857142852), linewidth(4) + rvwvcq); draw((9.282857142857141,7.897142857142852)--(8.53142857142857,7.897142857142855), linewidth(4) + rvwvcq); draw((8.53142857142857,7.897142857142855)--(8.531428571428572,8.64857142857143), linewidth(4) + rvwvcq); draw((8.531428571428572,8.64857142857143)--(7.78,8.648571428571428), linewidth(4) + rvwvcq); draw((7.78,8.648571428571428)--(7.78,9.4), linewidth(4) + rvwvcq); /* dots and labels */ clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy][/asy] This pattern can be made arbitrarily large and attached to the lower right corner of the $n \times n$ table. Moreover, we made this construction such that equality from our estimation holds. That is when in odd rows/columns each black cells are covered by exactly one tromino. So our induction is complete.

Let $n=2k+1$. Color the black squares red and blue so that blue squares are in rows with $k+1$ black squares and red squares are in rows with $k$ black squares. A tromino can't cover multiple blue squares. There are $(k+1)^2$ blue squares. So, there are at least $(k+1)^2$ trominos. For $k=1, 2$, $3(k+1)^2>(2k+1)^2$, so the space the trominoes need to take up is bigger than the board, so it's impossible. We will prove by induction that for $k\geq 3$ it's possible to cover the black squares with $(k+1)^2$ blue squares. We can check that this is possible for $k=3$. For the inductive step, we basically need to show that we can cover the outer $2$-wide $L$ shape with $2k+1$ trominoes, since the rest of the board is a square with side length $2k-1$ which can be tiled with $k^2$ trominoes. We can also prove this claim by induction. By putting a tromino at each tip of the $L$ shape, we reduce it to an $L$ shape with side length $2k-1$, which can be covered with $2k-1$ trominoes. We can use a base case of $n=5$ where we can cover the legs with $2\times 3$ grids and cover the corner with $1$ tromino.

Call a black square even if there are an even number of squares from this black square to any side of the chessboard. For example, all black squares on the edge are black squares. Note that no two even squares may be covered by the same tromino and that there are exactly $\left(\frac{n+1}{2}\right)^2$ even squares. Thus, we need at least $\left(\frac{n+1}{2}\right)^2$ trominos. Note that this also means that $n=3$ and $n=5$ do not work because we need at least $4$ and $9$ trominos, covering $12$ and $27$ squares respectively. We claim that al black squares can be covered in $\left(\frac{n+1}{2}\right)^2$ trominos for all $n\ge 7.$ We will proceed with induction. Base Case: When $n=7$ we can cover like this: Induction Hypothesis: Suppose for $n=2k-1$ we can make a tiling. Induction Step: Then adding on something like this will do the job. Thus, we can always tile an $n\times n$ chessboard with $\left(\frac{n+1}{2}\right)^2$ trominos when $n\ge 7$ and furthermore, it will be optimal.

This took me way too long. Consider the $\left(\frac{n+1}{2}\right)^2$ black squares that are an even distance from all sides of the chessboard. Each tile can contain at most one of these but each square must be tiled, so we must use at least $\left(\frac{n+1}{2}\right)^2$ tiles. Then clearly this implies that $n=1,3,5$ fail by bounding. For $n=7$ consider the tiling attached below. For $n>7$ take a construction for $n-2$ and add on two rows and columns; note that we can tile these in just $n$ tiles by placing two $2\times 3$ rectangles in the corner (which takes up $4$ tiles) and adding on one more tile for every $2\times 2$ square (of which there are $n-2$). Then by induction we can reach $\left(\frac{n+1}{2}\right)^2$ for all $n\ge 7$. We are done. $\blacksquare$

Solved with NTGuy, everythingpi3141592

The answer is $\boxed{n \ge 7}$. Throughout the solution, we will refer to cells in the $n\times n$ board with coordinates, where the bottom left cell is $(1,1)$ and the top right is $(n,n)$. Claim: If $a$ and $b$ are even positive integers, we can tile any $a \times b$ rectangle that has squares colored alternately black and white with non-overlapping trominos to cover all the black squares. Proof: It clearly suffices to show this for $a = b = 2$, as otherwise, we can split $ a\times b$ into a bunch of $2 \times 2$ squares. But $a = b = 2$ is evident by taking a tromino containing both of the black squares. $\square$ Claim: We can tile any $2 \times 3$ rectangle that has squares colored alternately black and white with non-overlapping trominos to cover all the black squares. Proof: Just fully tile the $2\times 3$ rectangle with trominos. $\square$ Claim: The result in the problem is true for $n = 7$. Proof: See the attachment below (the white square is the only one not in a tromino and any three adjacent squares all with the same color form a tromino). $\square$ Claim: If the result in the problem is true for odd $n$, then it is true for $n + 2$ also. Proof: Suppose it is true for $n$. Now fix any $(n+2) \times (n+2)$ squared colored as according to the problem. Fill the bottom left $n \times n$ square with trominos to cover all its black squares. Now, with trominos, cover all the black squares of the $2\times (n-1)$ rectangle with corners $(1,n+1), (n-1, n + 1), (n-1,n+2), (1, n + 2)$, the $2\times (n-3)$ rectangles with vertices $(n+1, 1), (n+1, n-3), (n+2, n-3), (n+2, 1)$, the $2\times 3$ rectangle with corners $(n,n+1), (n+2, n+1), (n+2, n+2) (n, n + 2)$, and the $2\times 3$ rectangle with corners $(n+1, n-2), (n+1, n), (n+2, n), (n+2, n - 2)$. These rectangles clearly don't overlap, and their union combined with the bottom left $n \times n $ square cover the whole $(n+2) \times (n+2)$ board, so all black squares are covered by the trominos, so $n + 2$ also works. $\square$ Thus, the problem is true for all $n \ge 7$ inductively. Now we prove that $n \ge 7$ must hold. Suppose otherwise. Note that $n = 1$ obviously fails, so assume $n > 1$. From our second claim, $n = 5$ being false implies $n =3 $ is also false, so it suffices to prove that $n = 5$ fails. Suppose otherwise. Notice that every tromino must contain at most two black squares and any tromino in a $5\times 5$ grid containing exactly two black squares must contain one of the squares $(2,2), (2,4), (4,2) , (4,4)$. This means that at most four trominos contain exactly two black squares and the rest contain one. Let $t$ be the number of trominos that contain exactly two black squares. Note that there are thirteen black squares, so we have at least $13 - 2t$ trominos with one black square. Thus, the number of trominos is at least $13 - t \ge 9$, which cover at least $9\cdot 3 = 27 > 5^2$ squares, a contradiction. Therefore, $n \ge 7$ and we are done.