Combinatorics in a $n \times n$ grid

Question

Natural number $n>2018$ is given. Numbers $1,2,\ldots,n^2$ are written (in an arbitrary order) into the fields of the $n\times n$ grid. Prove that it is possible to choose $n$ fields so that there's one field in each row and column and that there aren't any four consecutive terms of an arithmetic sequence in the chosen fields.

I have no idea how to start this. My attempts to find any correlations between the amount of four term sequences and the amount of fields chosen were all unsuccessful and I'm stuck.

Answer 1

I think that the problem boils down to proving that the number of choices of n fields containing four consecutive terms of an arithmetic sequence is smaller than n!

Answer 2

Sketch (probabilistic method): Let $S$ be the set of arithmetic sequences of length 4 among the numbers $1,2,\cdots, n^2$. Clearly, for large $n$, $|S| \sim \frac{n^2}{3} \cdot \frac{n^2}{2} = \frac16 n^4$, since there are approximately $\frac{n^2}{3}$ choices for the common difference and on average $\frac{n^2}{2}$ choices for the linear shift. Now choose the $n$ fields uniformly at random (over the total space of $n!$). For a fixed $s \in S$, the chosen $n$ fields contain the 4 terms of $s$ with probability at most $\frac{1}{n(n-1)(n-2)(n-3)} \sim n^{-4}$. A simple union-bound gives us a probability of at least $$1 - \sum_{s \in S}\frac{1}{n(n-1)(n-2)(n-3)} \sim 1 - \sum_{s \in S} n^{-4} \sim 1 - (\frac{1}{6}n^4)(n^{-4}) = \frac{5}{6} > 0$$ that the chosen $n$ fields avoid all elements of $S$, i.e. all the arithmetic sequences of length 4.