Ultra cool problem $\color{black}\rule{25cm}{1pt}$ The minimum is $(n-k)^2$. We start off with stating an invariant. Invariant: Every tractor will make the same number of right and up turns. This is easily seen since they all end up in the upper right corner and the total amount of squares that every tractor must pass through is $2n-1$. Now we number the tractors from $1$ to $k$ and color in the the grid with white, except for the lower-left corner, which we color as black. We number the rows from top to bottom from $1$ to $n$, and the columns from left to right with $1$ to $n$. A trajectory is a path from the lower-left corner to the upper-right corner. The strategy to minimize is the following algorithm: Algorithm #1: All the tractors will go once at a time. The first tractor goes one up and then alternately does one right turn and then goes one up, as it goes into different squares, the white squares turn into black ones. The even numbered tractors will always go into the right direction unless their upper neighbor is colored white or they are in the last column in which case they go into the upwards direction, we color their trajectories with red and change all the squares on the trajectory into black as the tractor goes along. The odd numbered tractors will always go upwards unless their neighbor on their right side is colored white or they are in the first row in which case they go into the right direction, we color in their trajectories with blue and change all the squares on the trajectory into black as the tractor goes along. By this way we cover as much squares as possible. Let $Z_k$ denote the covered squares in black with $k$ trajectories and let $E_k$ be the rest of the square which isn't covered in black. Obviously $E_k = n^2-Z_k$. This obviously implies that we want a more maximized $Z_k$, which our algorithm does maximize. Since it is obvious that we are going to have that the red trajectories are going to concur in the first row and the first column of the square grid, and so do blue trajectories in the last column and the last row, we are going to use $b_k$ to use the number for which $k$ red trajectories collide and how many times and we are going to use $c_k$ to see how many times we have that blue trajectories collided and how many times. To calculate $b_k$ we use the following algorithm. Algorithm #2 Let's start off with a white $n\times n$ square. Every second we are going to add a red trajectory, when two trajectories collide color the squares in which they collide with a shade of red, the more trajectories collide the darker the shade of red. By this algorithm we notice that $b_k = 4+8+12+\dots+4(k-1)=\sum_{t=1}^{k-1} 4t=2(k-1)k$, since for every collision $3$ more appear, thus the factor of $4$. To calculate $c_k$ is simple, we use another algorithm. Algorithm #3 Let's start off with a white $n\times n$ square, where the bottom-left and the upper-right corner are with a constant black color and are invariant despite any changes. Every second we add blue trajectories and when they collide we color the squares in which they collide with a shade of blue, the more they collide the darker the shade. Since we are going to have $k$ collisions on the bottom left and the upper right we must have that $k-1$ corners are repeated thus we have that $c_k=2(k-1)+b_k$, we have $2(k-1)$ because of the corner and $b_k$ appears because of the algorithm, this is because for every collision $3$ more appear, thus we have $b_k$. We simplify $c_k=2(k-1)+2(k-1)k=2(k-1)(k+1)=2(k^2-1)$ Now we must go into a parity case, we look at the parity of $k$ in $Z_k$. 1.$k \equiv 0 \pmod{2}$ Set $k=2t$. Since we must have that the number of red trajectories and blue trajectories is the same we have that: $$Z_{2t}=(2n-1)2t-b_t-c_t-2$$this must hold since the total of squares passed is $(2n-1)2t$ and because of the algorithm the last row and the first column have repetitions but the others don't, the $-2$ is there to count in the double counting of the bottom-left and the upper-right corner in $b_t$ and $c_t$, since they are both contained in $b_t$ and $c_t$. So now we have that: $$Z_{2t}=(2n-1)2t-2(t-1)t-2(t^2-1)-2=2n.2t-4t^2$$plugging this into $E_{2t}$ we have that: $$E_{2t}=n^2-2n.2t+4t^2=(n-2t)^2$$ 2.$k \equiv 1 \pmod{2}$ Set $k=2t+1$. We have that: $$Z_{2t+1}=(2n-1)(2t+1)-b_{t+1}-c_t-2$$we choose $b_{t+1}$ instead of $b_{t}$ since $b_{t+1}$ covers more area because of the algorithm. Here is the proof that this is more efficient. $\color{red}\rule{25cm}{0.5pt}$ We number in the squares in the first column and the last row with $1,2,\dots ,n$, where in the first column we start from the bottom-left corner and label it with $1$ and count upwards, while in the last row we go into the right direction. Define a jump of a trajectory to be its a break in the chain of a series of the same moves from the last change. So for the red trajectories we have the series of jumps: $$1 \rightarrow 2 \rightarrow 4 \rightarrow 6 \rightarrow \dots$$while for the blue trajectories we have this series of jumps: $$1 \rightarrow 3 \rightarrow 5 \rightarrow 7 \rightarrow \dots$$The area that's cornered by the red trajectories is significantly greater than the area that's cornered by the blue trajectories. Both areas are triangular numbers and their difference is $\sum_{t=1}^{x+1} t - \sum_{t=1}^{x} t = x+1$, this all holds because of the jumps which reduce the area cornered by the blue trajectories since the jumps are bigger in the relation to the red jumps. $\color{red}\rule{25cm}{0.5pt}$ Now we have that: $$Z_{2t+1}=2n.2t+2n-4t-1-4t^2$$This gives us that: $$E_{2t+1}=n^2-2n.2t+4t^2-2n+4t+1$$$$E_{2t+1}=(n-2t)^2-2(n-2t)+1$$$$E_{2t+1}=(n-2t-1)^2$$ Now we have seen in both cases that the minimum is $\text{min} \; E_k = (n-k)^2$ . . .

You seem to overcomplicate the problem by a lot . The answer is $(n-k)^2$. Part 1: Example of the equality cases. Shown below is an example for $n=8, k=3$. [asy][asy] size(5.5cm,0); defaultpen(fontsize(12pt)); int i; fill((0,0)--(8,0)--(8,8)--(7,8)--(7,1)--(0,1)--cycle,palered); fill((0,1)--(7,1)--(7,8)--(6,8)--(6,2)--(0,2)--cycle,paleblue); fill((0,2)--(6,2)--(6,8)--(5,8)--(5,3)--(0,3)--cycle,lightgreen); for(i=0;i<=8;++i){ draw((i,0)--(i,8) ^^ (0,i)--(8,i)); } draw(shift(0.5,0.5)*((0,0)--(7,0)--(7,7)),heavyred+linewidth(1.5)); draw(shift(0.5,0.5)*((0.15,0)--(0.15,1)--(6,1)--(6,6.85)--(7,6.85)) ,heavyblue+linewidth(1.5)); draw(shift(0.5,0.5)*((0,0)--(0,2)--(5,2)--(5,7)--(7,7)),darkgreen+linewidth(1.5)); [/asy][/asy] The main idea is to let each tractor gradually \emph{peels off} the grid from the lower right corner, eventually leaving with the uncovered $(n-k)\times (n-k)$ square. Remark: There are numerous equality cases. Shown above is probably the most natural example. Part 2: Proof of optimality. We will prove that at most $2nk-k^2$ squares have been covered. Consider the diagram below, which demonstrate the proof for $n=8, k=3$. [asy][asy] size(8cm,0); defaultpen(fontsize(10pt)); int i; for(i=0;i<=7;++i){ for(int j=0;j<=7;++j){ pen p = paleblue; if((i+j)%2 !=0){ p = palered; } fill((i,j) -- (i+1,j) -- (i+1,j+1) -- (i,j+1)--cycle,p); } } for(i=0 ;i<=8 ;++i){ draw((i,0)--(i,8) ^^ (0,i)--(8,i)); } draw(shift(0.5,0.5)*((0,-0.5)--(0,2)--(1,2)--(2,2)--(2,5)--(6,5)--(6,7)--(7.5,7)) ,gray+linewidth(1)); for(i=1;i<=8;++i){ pen p = heavyblue + linewidth(1.5); if(i % 2 == 0){ p= heavyred+linewidth(1.5); } draw((-0.3,i+0.3)--(i+0.3,-0.3), p); label("$\leq"+ string(min(i,3)) + "$",(i+0.3,-0.3),dir(290)); } for(i=1;i<=7;++i){ pen p = heavyblue+linewidth(1.5); if(i%2==0){ p = heavyred+linewidth(1.5); } draw((i-0.3,8.3)--(8.3,i-0.3),p); label("$\leq"+string(min(8-i,3)) + "$", (8.3,i-0.3),dir(-20)); } [/asy][/asy] The key idea is that if you partition the board into $2n-1$ diagonals, then each tractor will meet each diagonal exactly once. Thus, we can bound the number of cells covered as $$(1+2+\hdots+(k-1)) + \underbrace{(k+k+\hdots+k)}_{2(n-k)+1\ k\text{'s}} + ((k-1)+(k-2)+\hdots+1)$$which evaluates to $2nk-k^2$. Remark (On an alternative approach): An alternative approach claimed by TLP.39 is that you perform induction on $n$ as follows: remove one tractor as well as the cells it plows (which will split the plot into two pieces), carefully connect those two pieces, and use the induction hypothesis on $(n-1,k-1)$. However, the details are cumbersome and I have not worked on it yet.

Thought about this last night. Really beautiful problem, rate it a 11/10. The answer is $(n-k)^2$. Let the (centers of the) squares on the grid be coordinates, from $(1,1)$ to $(n,n)$. We claim that we can cover everything other than a square of size $n-k$ in the bottom right corner. Indeed, this can be done by placing the $j$th tractor as such: it goes from $(1,1)$ to $(j,1)$, then to $(j,n-j)$, then to $(n,n-j)$, and finally to $(n,n)$. Note that this process, at each step, ensures that the remaining squares are the bottom right $(n-j)\times(n-j)$ square. To show this is optimal, we focus on ONLY what we want: the uncovered squares. In particular, we induct on $k$ and $n$ simultaneously. We shall keep $n-k$ constant: Base Case. $k=0$. In this case, the result is clear. Induction Hypothesis. Assume the result is true for some $n$ and $k$. We prove it for $n+1$ and $k+1$. Induction Step. Imagine we laid down the first tractor's path and then just cut out the squares on which he travelled. We claim by downshifting the top left piece by 1 square and then moving it right one square, we get an $(n-1)\times(n-1)$ grid, after which our result is clear. Indeed, it suffices to show this for columns, as the result is symmetric. Assume that there are $p$ squares above the tractor's path in column $x$. That means that if we draw a horizontal line where the tractor last moves up in column $x$, we see that the path never goes below that, and the path intersects column $x+1$ in the same point. In particular, below that line, there are $n-x-1$ squares, so there are that many squares in column $x+1$ below the path. Thus, as there will only be $n-1$ columns, we get a perfect match column wise. Repeating by flipping the grid on $y=x$, we get the result for rows, finishing the problem.

MarkBcc168 wrote: You seem to overcomplicate the problem by a lot . The answer is $(n-k)^2$. Part 1: Example of the equality cases. Shown below is an example for $n=8, k=3$. [asy][asy] size(5.5cm,0); defaultpen(fontsize(12pt)); int i; fill((0,0)--(8,0)--(8,8)--(7,8)--(7,1)--(0,1)--cycle,palered); fill((0,1)--(7,1)--(7,8)--(6,8)--(6,2)--(0,2)--cycle,paleblue); fill((0,2)--(6,2)--(6,8)--(5,8)--(5,3)--(0,3)--cycle,lightgreen); for(i=0;i<=8;++i){ draw((i,0)--(i,8) ^^ (0,i)--(8,i)); } draw(shift(0.5,0.5)*((0,0)--(7,0)--(7,7)),heavyred+linewidth(1.5)); draw(shift(0.5,0.5)*((0.15,0)--(0.15,1)--(6,1)--(6,6.85)--(7,6.85)) ,heavyblue+linewidth(1.5)); draw(shift(0.5,0.5)*((0,0)--(0,2)--(5,2)--(5,7)--(7,7)),darkgreen+linewidth(1.5)); [/asy][/asy] The main idea is to let each tractor gradually \emph{peels off} the grid from the lower right corner, eventually leaving with the uncovered $(n-k)\times (n-k)$ square. Remark: There are numerous equality cases. Shown above is probably the most natural example. Part 2: Proof of optimality. We will prove that at most $2nk-k^2$ squares have been covered. Consider the diagram below, which demonstrate the proof for $n=8, k=3$. [asy][asy] size(8cm,0); defaultpen(fontsize(10pt)); int i; for(i=0;i<=7;++i){ for(int j=0;j<=7;++j){ pen p = paleblue; if((i+j)%2 !=0){ p = palered; } fill((i,j) -- (i+1,j) -- (i+1,j+1) -- (i,j+1)--cycle,p); } } for(i=0 ;i<=8 ;++i){ draw((i,0)--(i,8) ^^ (0,i)--(8,i)); } draw(shift(0.5,0.5)*((0,-0.5)--(0,2)--(1,2)--(2,2)--(2,5)--(6,5)--(6,7)--(7.5,7)) ,gray+linewidth(1)); for(i=1;i<=8;++i){ pen p = heavyblue + linewidth(1.5); if(i % 2 == 0){ p= heavyred+linewidth(1.5); } draw((-0.3,i+0.3)--(i+0.3,-0.3), p); label("$\leq"+ string(min(i,3)) + "$",(i+0.3,-0.3),dir(290)); } for(i=1;i<=7;++i){ pen p = heavyblue+linewidth(1.5); if(i%2==0){ p = heavyred+linewidth(1.5); } draw((i-0.3,8.3)--(8.3,i-0.3),p); label("$\leq"+string(min(8-i,3)) + "$", (8.3,i-0.3),dir(-20)); } [/asy][/asy] The key idea is that if you partition the board into $2n-1$ diagonals, then each tractor will meet each diagonal exactly once. Thus, we can bound the number of cells covered as $$(1+2+\hdots+(k-1)) + \underbrace{(k+k+\hdots+k)}_{2(n-k)+1\ k\text{'s}} + ((k-1)+(k-2)+\hdots+1)$$which evaluates to $2nk-k^2$. Remark (On an alternative approach): An alternative approach claimed by TLP.39 is that you perform induction on $n$ as follows: remove one tractor as well as the cells it plows (which will split the plot into two pieces), carefully connect those two pieces, and use the induction hypothesis on $(n-1,k-1)$. However, the details are cumbersome and I have not worked on it yet. I have the exact same solution but I initially found the solution with induction and found it a little more intuitive.

This reminds me of a Ukranian problem from 2004, from a journal, that was posted on AoPS in 2006 I think, I saw it recently, it had no comments. The problem had 2 tractors on the opposite corners, and could move to a neighboring cell, and were plowing land