The answer is \[ \begin{cases} n & n=k \text{ or } n = 2k-1 \\ 2(n-k+1) & k < n < 2k-1. \end{cases} \]For constructions, for $n \in \{k, 2k-1\}$ we can just use a straightforward construction with one domino per column. As for the intermediate values, observe that one can construct it when $n = k+1$ by simply filling in the perimeter of the $(k+1) \times (k+1)$ square with four dominoes, then one can inductively obtain the next values $n = k+2, k+3, \dots$ by adding a new domino to each row and column, hence increasing the count by $2$. Now we prove this is optimal. The problem is clear if $k=n$ so assume now $k+1 \le n \le 2k-1$. Call a row (resp column) \emph{bare} if it contains no horizontal (resp vertical) domino. First note that if there are either no bare rows or no bare columns, then we need at least $n$ dominoes. Now consider a vertical domino $D$ (say) in some column $C$, and assume it is in the left half of the board. Then the column to the left of $C$ must also contain a domino, otherwise we could add the domino exactly to the left of $D$. Inductively, then, every column left of $C$ is not bare. Similarly, if $C$ had been on the right half of the board, then all columns to the right of $C$ are not bare. The upshot of this is that the bare columns form a contiguous block. Similarly, so do the rows. Now assume we have fewer that $2(n-k+1)$ dominos. It follows that either there are $k$ bare columns or $k$ bare rows. WLOG there are $k$ bare columns, then intersecting them with a bare row gives a place where we can add an additional domino, contradiction.

Cute problem, however very similar to this one.

The case $n=k$ is trivial. The model I found is the same v_Enhance presented above, but I have a slightly different way to prove that the required number is $\min \{n,2(n-k+1)\}$. Let's consider a maximal arrangement (one where you can't add any tile) and let's label the rows and the columns with numbers from $1$ to $n$. Now let's color the rows and the columns labeled with numbers from $n-k+1$ to $k$ with blue. If there is any vertical tile on a blue column, then it is clear that the rows which contain its cells cannot contain horizontal tiles and therefore each other column must contain one vertical tile (in order to cover the eventual empty spaces) and this gives at least $n$ tiles. The same happens if we look at the blue rows. It remains to see what happens when there is no vertical tile on a blue column and no horizontal tile on a blue row. Let's pick the column labeled with $\lfloor n/2 \rfloor$. To make impossible the presence of a vertical tile on this column we must have two rows $a$ and $b$ with $a<n+1-k<k<b$ and $b-a<k$ which contain tiles that cross our columns. Now just look at the rows $1,2,...,a$ and $b,b+1,...,n$ which are at least $n-k+1$. Each one must contain at least one horizontal tile. Then do the same thing for the row labeled with $\lfloor n/2 \rfloor$ to get at least $n-k+1$ vertical tiles. Done!

EGMO 2016/5 wrote: Let $k$ and $n$ be integers such that $k\ge 2$ and $k \le n \le 2k-1$. Place rectangular tiles, each of size $1 \times k$, or $k \times 1$ on a $n \times n$ chessboard so that each tile covers exactly $k$ cells and no two tiles overlap. Do this until no further tile can be placed in this way. For each such $k$ and $n$, determine the minimum number of tiles that such an arrangement may contain. Let $f(n, k)$ denote the desired minimum. Answer: $f(n, k)=n$ for $n \in \{k, 2k-1\}$ and $f(n, k)=2(n-k+1)$ for all $k<n<2k-1$. Construction: For $n \in \{k, 2k-1\}$ just take one horizontal tile in each row. For $n=k+1$, take four tiles to cover the boundary of the grid; for all $k+1 \leqslant n<2k-1$, place tiles in the new row and column, inductively, to get a total of $2(n-k+1)$ tiles. Bound: For $n=k$ the claim is obviously true; for $k+1 \leqslant n \leqslant 2k-1$, we shall show the bound. Call a row or a column, which does not contain a tile entirely, good. If no row (or column) is good, then we must have at least $n$ tiles, which is in lieu with the claim. Otherwise, suppose there are $r$ good rows and $c$ good columns. If the number of tiles is strictly less than $\min (2k-1, 2(n-k+1))$ then, either the number of horizontal tiles, or the number of vertical tiles is less than $n-k+1$ so $\operatorname{max} \{r,c \} \geqslant k$. WLOG, $r \geqslant c$; then we have $k$ good rows. Claim: No two consecutive good rows are separated by rows. (Proof) Assume to the contrary, then all intermediate rows have a horizontal tile. So, for both of the rows, one of their cells adjacent to a cell from the horizontal tile of the adjacent intermediate row, must be contained by a vertical tile. However, this shows that the length of the board is $n \geqslant 1+2k,$ a contradiction. $\square$ Finally, take any good column and intersect it with the $k$ consecutive good rows; these $k$ cells can be filled by a tile, yielding the desired contradiction. $\blacksquare$

We claim that the answer is $k$ for $n=k$, $2(n-k+1)$ for $k<n<2k-1$, and $2k-1$ for $n=2k-1$. The $n=k$ case is not hard to see, so we'll assume that $n>k$ in the following. Also a domino is a $1\times k$ or $k\times 1$ tile. The key idea is that each row or column can harbor at most one domino since $n\le 2k-1$. Call a row or column good if it has a domino. We must now bound the number of good rows. The key claim is the following. Claim: Let $v$ be a good row or column, and let $S$ be the side of the square that's parallel to $v$ and closest to $v$ (if $S$ is not unique, the statement holds for either choice of $S$). Then, all row or columns from $S$ to $v$ are good. Proof of Claim: Suppose $v$ is horizontal and $S$ is the south side. Consider the set of squares below the domino in $v$. No vertical square can touch those squares, else $S$ would not be the closest side, the north side would be. Thus, if any of those rows was not good (no dominoes in it), we could fill a domino directly parallel to $v$ to contradict the fact that the board couldn't have any dominoes added to it. Thus, all the rows from the south side to $v$ are good. $\blacksquare$ Let $a$ be the number of columns from the north side down that are good, $b$ for the east side, $c$ for south, and $d$ for west. Note that $a+b+c+d$ is the number of dominoes. We see that there is a $(n-a-c)\times (n-b-d)$ rectangle of empty squares, so since it is unfilled, either $a+c=n$ or $b+d=n$, or $n-a-c,n-b-d\le k-1$. In the former case, we have that every row (or column) is filled, so there are $n$ dominoes. In the latter case, we have $a+b+c+d\ge 2(n-k+1)$. Thus, if $k<n<2k-1$, then the number of dominoes is at least $2(n-k+1)$, and if $n=2k-1$, the number of dominoes is at least $2k-1$. It now suffices to provide a construction. If $n=2k-1$, simply left align a domino in the top row, the right align in next row, left align in next row and so on. Now consider the case $k<n<2k-1$. Start with an empty $(k-1)\times(k-1)$ square and add four dominoes around the perimeter to get a $(k+1)\times(k+1)$ square. Place these dominoes in that configuration on the lower left corner of the $n\times n$ square, and for each of the other $2(n-k-1)$ rows and columns, put a domino in each one. This clearly works, and achieves the value of $2(n-k+1)$.

Does this work? We claim the minimum is \[ f(n,k)= \begin{cases} n &\qquad \text{if } n\in \{k,2k-1\} \\ 2(n-k+1) &\qquad\text{if } k < n < 2k-1. \end{cases} \]We first show equality is achievable. If $n=k$, we fill the entire grid. If $n=2k-1$, alternatively put tiles in the leftmost and rightmost possible positions in each row. If $k<n<2k-1$, put 4 tiles around the outer border in each of the 2 rows and 2 columns, and keep doing this till we have an inner empty $(k-1)\times (k-1)$ square. Assume $n\not \in \{k,2k-1\}$. Notice that every row or column has at most 1 tile. Call a row or column fat if there is a tile in that row or column. Note that the answer is the number of fat rows and columns. Say some row, WLOG in the top half, is fat. Then there can be no tiles that have an endpoint directly above this tile, since they would intersect the tile in the fat row. So there is empty space in the $k$ tiles one above the fat tile, and no tiles cross these cells vertically. Hence, there must be a tile in the row directly above the fat row. This means that there are some $1\le a,b,c,d \le n$ such that every column from 1 to $a$ and every column from $b$ to $n$ and every row from 1 to $c$ and every column from $d$ to $n$ is fat. So there is an inner $(b-a-1) \times (d-c-1)$ rectangle which is empty. This means $b-a-1\le k-1$ and $d-c-1\le k-1$, and we want to maximize the total number of fat rows and columns; \[ a+(n-b+1)+c+(n-d+1) = 2n - (b-a-1) - (d-c-1).\]Hence, this is minimized when $b-a-1=d-c-1=k-1$, which means the total number of fat rows and columns is $2n-(k-1)-(k-1)=2(n-k+1)$.

Here is a new solution. The answer is $n$ for the values $n=k$ or $n=2k-1$, and $n=2(n-k+1)$ for all other values of $n$. My construction is the same as everyone else. We will partition the $n \times n$ chessboard by the following method: place a line $\ell_1$ dividing columns $k$ and $k+1$, and place a second line $\ell_2$ dividing columns $(n-k)$ and $(n-k+1).$ Divide the rows of the chessboard similarly; note that our four lines construct a smaller square in the middle of the chessboard. Suppose some tile (horizontal without loss of generality) passes through the center square; then there must be at least one horizontally oriented tile on each row of the chessboard, so there must be at least $n$ tiles. Now suppose no tile passes through the center square. Consider the rightmost vertical tile $t_1$ left of $\ell_1$ and the leftmost vertical tile $t_2$ right of $\ell_2$, and suppose the tiles have distance $d$. Now $d \leq k-1$, and furthermore note that all columns left of $t_1$ and right of $t_2$ must contain a vertical domino. Hence the total number of vertical dominoes is at least $n-d \geq n-k+1$. Similarly the number of horizontal dominoes is also at least $n-k+1$, as desired.

The answer is $n$ for $k=n, \frac{n+1}{2}$ and $2(n-k+1)$ otherwise. The constructions for the first two cases are obvious; for the others, the idea basically is to have one central empty square $(k-1) \times (k-1)$ and in every other row and column to have exactly one horizontal and vertical tile, respectively (this can be described inductively: start with the empty square and on each move add $4$ tiles on the perimeter of the previous square - one per each of the $4$ new rows and columns). Now, proceed to the proof of the bound. Suppose that there are $r>0$ "empty" rows and $c>0$ "empty" columns ("empty" means not containing a whole tile; otherwise $r=0$ or $c=0$ and there at least $n \geq 2(n-k+1)$ tiles). If we consider the last "non-empty" column on the left side of the board, then all columns to the left of it are also "non-empty" (there can't be a horizontal tile placed entirely on the left side of the board, as $k \geq \frac{n+1}{2}$); we can say this for the right side of the board as well, so the middle $c$ columns are empty and thus $c \leq k-1$ (otherwise a horizontal tile can be placed as these columns are empty), so there are at least $n-k+1$ vertical tiles. The same bound holds for the horizontal tiles and we are done.

The answer is $2(n-k+1)$ except when $n=k$ or $2k-1$ and it is $n$ instead. For the construction, when $n=k$ it is obvious, for $n=2k-1$ take $2k-1$ vertical rectangles that alternate between being at the bottom and the top. For all others, take a "ring" of side length $k+1$ and put it in the bottom left corner and then fill in the rectangles above and to the right of it. Now to prove the bound, for $n=k$ it is obvious, then first if there is some direction which has a rectangle in every row/column then we get the bound $\ge n.$ Now suppose there isn't. We show that there must be at least $n-k+1$ rectangles in each direction. Consider some column without any vertical rectangles. It must be blocked by some horizontal rectangles: number the rows from top to bottom and consider the one in the $i$th row where $i$ is as large as possible and $\le k$ (one must exist since otherwise we can just place a vertical rectangle there). If there are no further horizontal rectangles in this column, then the gap between it and the bottom wall must have height $\le k-1$ (otherwise place a vertical rectangle there) as well as the gap between it and the top wall by construction. Then no vertical rectangles can appear in the gap (of width $k$) between this rectangle and either wall, so either the rectangle given by this one translated directly up or down can be placed in any row, or it is blocked by another horizontal rectangle in the same row. Thus every row has a horizontal rectangle, contradiction. Thus there is another further horizontal rectangle. Consider the immediately next one, in the $j$th row. We know $j-i-1\le k-1,$ as otherwise we could place a vertical rectangle between these two horizontal ones. We also know that the gaps between the first rectangle and the top wall and the gaps between the second rectangle and the bottom wall must be filled with horizontal rectangles, similar to the above reasoning. Thus the rows $1,2,\dots,i-1,i,j,j+1,\dots,n$ all have horizontal rectangles in them, which is $n-(j-i-1)$ total. This is $\ge n-k+1,$ so there are at least $n-k+1$ horizontal rectangles. Similarly there are at least $n-k+1$ vertical rectangles, so $2(n-k+1)$ total. Combining these two bounds $2(n-k+1)$ and $n$ and our result for $n=k$ gives the desired result.

below solution is the reason why you should not do writeups while distracted at school: The answer is $n$ when $n=k$ or $2k-1=n$ and $2(n-k+1)$ otherwise. The former two cases' constructions are trivial and will not be outlined here. For the latter case, the construction is forming a square with side length $k+1$ using four tiles and tiling the remaining along the rows. Suppose by contradiction there is a way to do it with less than $2(n-k+1)$ tiles. By Pigeonhole, either there are fewer than $n-k+1$ vertical tiles or there are fewer than $n-k+1$ horizontal tiles. WLOG suppose it is vertical. Label the tiles from left to right as $a_1,a_2 \cdots a_j$ and the two sides as $a_0$ and $a_{j+1}.$ Take any two $a_i$ and $a_{i+1}$ that are not adjacent. If $a_i$ and $a_{i+1}$ have $k$ rows between each other, the space in between must be filled up by $n$ horizontal tiles, contradicting minimality. Observe then that the nearest tile to each side must be adjacent to it or at least $k+1$ from it. Take the lowest $i$ such that $a_i$ and $a_{i+1}$ are not adjacent. WLOG suppose $a_{i+1}$ is placed lower than $a_i.$ Take any vertical $1 \cdot k$ row that is a horizontal translation of $a_{i+1}$ to the left between $a_i$ and $a_{i+1}.$ This row must be blocked by a horizontal shift, and it can only be done from a horizontal tile which goes through a square beneath $a_i$ and touches $a_{i+1}.$ Similarly do the same but above $a_{i+1}.$ The sum of these two horizontal tiles ($2k$) minus their overlapping range must be $\le n,$ so the range between $a_i$ and $a_{i+1} \ge 2k-n.$ In other words, $a_i$ is at least $k-(2k-n+1)=n-k-1$ away from $a_0.$ Clearly there must exist at least one $a_i,$ and it cannot be $n-k-1$ away from both $a_0$ and $a_n$ at the same time unless $n$ is even and it is the middle row, in which case we can clearly see minimality is easily contradicted. Therefore for some $i,$ either $a_i$ is connected to $a_0$ through adjacent rows, or it is connected to $a_n$ through adjacent rows, yielding $n-k-1+1=n-k$ vertical tiles. For there to be only these tiles, there will exist a gap of width $k$ between the rightmost $a_i$ and side $a_{i+1},$ forming a contradiction. Therefore this cannot exist and there are at least $n-k+1$ vertical tiles. (Note: To resolve the above contradiction, put a tile at the very right)

Posting for reference, Call the tiles : vertical dominoes and horizontal dominoes ( the meaning of each one is the intuitive one ). for $k=n$, the answer is $n$ which is to tile all rows or all columns. Lemma 1 : There's a contiguous set of columns with vertical dominoes starting from the left, and similarly from the right. To prove this we prove another result, given a vertical domino in the left half, i.e at row $i\leq n/2$ of the grid the whole prefix of columns ending at $i$ has vertical dominoes. if $i=1$ it's trivial. Let $i$ be such column, the parallel sub-column of $i-1$-th column to the vertical domino at $i$ has length $k$ thus there's a domino in column$i-1$ since if not we can still add a domino ( contradicting the configuration ). Now apply induction to find the prefix. Lemma 1 comes after considering the rightmost column $i$ with vertical domino such that $i\leq n/2$, thus getting the needed prefix ( the contiguous block), and similarly we find a suffix ( contiguous block from the right ). Now let $f,k,l$ respectively the length of the left prefix, the length of right prefix, and $l:=n-k-f$. if $l\geq k$ : By definition of $f,k$ there's no vertical domino in $f+1,\cdot\cdot\cdot,k-1$, and since $l\geq k$ thus at least every row contains a horizontal domino ( else we can add it ) thus we need at least $i+f+n$ domino. if $l>0$ and $l<k$ : then $i+k\geq n-k+1$, using the same reasoning on horizontal domines we get that need at least $n-k+1$ horizontal dominoes which yields at least $2(n-k+1)$ dominoes. Constructions are similar to the ones by v_Enhance.