Coloring problem

Question

Let $m$ respectively $n$ parallel lines and consider the $m n$ intersection points which is colored by $2018$ colors. Find the minimum of $m$ and $n$ such that there exists a parallelogram with vertexes of the same colours for any coloring.

Answer 1

$\textbf{NOTE}$: This solution is not mine, so please give this answer credit for this solution.

Let's first consider the case of 3 colors. What is the minimum $m,n$ to guaranteed a monochromatic parallelogram?

Such a parallelogram will occur in a grid of 19 columns ($m$) by 4 rows ($n$).

By the pigeonhole principle, each column must have a repeated colour point. Ignoring any later repeats, classify the columns according to the first two repeat colour positions; there are 6 options: (1,2),(1,3),(1,4),(2,3),(2,4) and (3,4). So since there are also 3 colour options for the repeated colours there are only 6×3=18 different options for repeated colour by position. Therefore, by the pigeonhole principle again, in a 19×4 grid we must have a suitable parallelogram with identically coloured corners.

For $n$ colors, using the same approach, we would adopt a grid of $(n+1)$ rows and then require $n{n+1 \choose 2}+1 = n(n+1)n/2 +1 = (n^3+n^2)/2 + 1$ columns to find a parallelogram with same-coloured corners.