A really nice one, it is hard to explain without pictures but I will try to give a sketch of the proof. Initially take the adjacent squares with the maximum lenght of the smaller path between them and assume that this small path's lenght is lesser than one quarter of the total path. Now, divide into two parts, first if at least one of these two squares is not on an edge and second both of them are on an edge. First case is really simple, a casework using the maximality of these two squares leads directly to a contradiction. (Yet, it's hard to explain it without too many pictures so i'm leaving this part now, if a problem occurs, tell me and i will answer it.) The main part is the second part. Let's look at the picture, the squares we have selected are the ones with a red and black edge connected to them. (since there is no edge between them, the edges that pass from them must be like red and black edges) Start from one of the black edges and go along with the path without passing through our selected squares. We can't reach a red edge before we reach the other black edge. So divide the path into two parts, the black edges and the path connects them without passing through our selected squares; and the red edges and the path connects them without passing through our selected squares. Say the first part black path and the second part red path. We can say from the maximality that the red path is the smaller one. Otherwise we could find a bigger smaller part by taking the squares that are on the just right of our selected squares.The squares that are on the black path are black squares and the others are red squares, two selected squares are also black. Claim 1: Red squares are a connected set and there is no black squares inside red squares. Moreover there is no red square that is adjacent to the edge of the big square. Proof: Easy properties that can be proved by using the black squares are also connected. So I'm again leaving the proof. Therefore, the red squares has a shape like the grey colored squares in the picture. Say P to the polygon that formed of the edges of the shape of red squares. Now let's define a f function for the edges of lenght 1 on P (like the yellow edge on picture) A be an edge like that, one side of A is a red square and one side is a black square from the claim 1. Start from the edge next to the upside selected square say this edge A_1, go along P from the direction that doesn't pass through the edge of downside selected square and tell the i th reached edge lenght 1 A_i. (For example in the picture the yellow edge is A_7, while the downside selected squares' edge is A_24) Claim 2: If i>j, the black path between the upside black edge (the one that drawn on picture) and the black square that contains A_i is longer than the one with the square that contains A_j. Proof: Again start from the upside black edge and go along the black path, assume that we first reached A_i. Since A_i and A_j are on the edge of P and the black path can't go inside P, it is clear that it's impossible to connect A_j and the downside black edge. Contradiction. So claim 2 is true. Moreover the same for the red path is also true, I mean If i>j, the red path between the upside black edge (the one that drawn on picture) and the red square that contains A_i is longer than the one with the square that contains A_j. f(A_i) is equal to the lenght of the path between the two squares that contain A_i as an edge and passing through the upside red and black edges (on the picture again). From claim 2, f(A_i) is a non decreasing function. Because of the maximality of the first selected squares, f(A_i) must be either lesser than one quarter or more than 3 quarter of the total path. Claim 3: There is an i such that f(A_{i+1})-f(A_i) is bigger than the half of the total path. Proof: f(A_1)=1 and f(the downside selected squares' edge)= Total path-1. So f(A_i) starts to be more than 3 quarter of the total path at some i, take the smallest such i. Then, f(A_{i-1}) is lesser than 1 quarter of the total path. Result follows. Now we have a little to do remaining. Assume that for i, f(A_{i+1})-f(A_i) is bigger than the half of the total path. There are 3 cases i) A_i and A_{i+1} are not perpendicular to each other. The red path between the red squares that contains A_i and A_{i+1} is lesser than one quarter of the total path, so the black path between the black squares that contain A_i and A_{i+1} must be bigger than one quarter of the total path. Moreover the other path between the black squares that contain A_i and A_{i+1} includes the whole red path, so it can't be the smaller path between the black squares that contain A_i and A_{i+1} because of the maximality of the first selected squares. So it's again a contradiction! ii) A_i and A_{i+1} are perpendicular and has an angle 90 degrees in P. The path between the black squares that contain A_i and A_{i+1} as an edge is longer than the half of the total path. Let's look at the black square that is a neighbour to the both black squares that contain A_i and A_{i+1} as an edge. Say this square X, an argument like in claim 2 shows us that the black path between the black squares that contain A_i and A_{i+1} as an edge passes through X. So the black path between X and one of the black squares that contain A_i and A_{i+1} as an edge must be bigger than one quarter of the total path. So it's again a contradiction as in i) iii) A_i and A_{i+1} are perpendicular and has an angle 270 degrees in P. since the red path is lesser than one half, this is absurd. Finally we are done, if it is unclear, I am sorry. I can answer your questions if you ask.

Attachments:

very very nice problem . here's my solution: it's easy to see that $n$ must be even for such a path to exist, so from now for comfort we write it as $2n$. this closed path divides the area of the square into two parts, inside and outside. if we consider each square in the inside part as a vertice of a graph and connect two vertices if their corresponding squares are adjacent, we get a tree. (one can easily show that this graph is connected and does not have any cycles). by pick's theorem we get that this tree has $2n^2-1$ vertices. the maximum degree of this tree is $4$, since each square can be adjacent to at most $4$ squares. Lemma: if the maximum degree of a tree is $4$, then there is an edge in it that divides the graph into two parts, each having at least $\frac{n-1}{4}$ vertices. Proof:if an edge has the above property, we call it good. let $v$ be an arbitrary vertex and make it the root of the tree. let it's neighbors be $v_1$ (possibly $v_2,v_3,v_4$). let the subgraph of our tree with the root $v_i$ be $V_i$. now, by pigeonhole principle, one of the $V_i$'s, has at least $\frac{n-1}{4}$ vertices, namely $V_1$. if the edge $vv_1$ is not good, we conclude that $V_1$ must have at least $\frac{3(n-1)}{4}$ vertices except $v_1$. now do the same, again by pigeonhole principle, we get that in one of the subgraphs with roots neighbours of $v_1$, there is at least $\frac{n-1}{4}$ vertices. if the edge $v_1v_2$ is not good, again we conclude that this subgraph must have at least $\frac{3(n-1)}{4}$ vertices except $v_2$ and so on. this process must stop somewhere and we must get a good edge, since if not, we get a graph with infinite vertices. so the proof is complete. now back to the main problem, there is an edge $ab$ dividing the graph into two parts each having at least $\frac{n^2-1}{2}$ vertices. this edge cuts the lattice edge between two vertices, namely $t$ and $s$. we claim that $t$ and $s$ have the desired property. delete the edge $ab$ of the graph. now we have two trees, each having at least $\frac{n^2-1}{2}$ vertices. again using pick's theorem, we easily find that each of the two paths connecting $t$ and $s$ have at least $n^2$ edges, so the proof is complete.

This beautiful problem has a solution using this problem as its main idea : https://artofproblemsolving.com/community/c6h85771p499536