Let a chessboard table $2016\times 2016$. We need to find the smallest number $n$ such that for any choice of n cells of the table, we could find four of them such that, centers of such four cells are vextex of a parallelogram.
One of my friend ask me to answer this, but I have no idea for such difficult question. How to I find that such smallest number and prove it?
Any set of 4032 cells will contain a parallelogram. Not requiring distinct slope&distance for point pairs allows a degenerate solution for 4031 cells, just select all cells to the bottom and far left for a set without parallelograms.
More interesting -- What is the maximal number of points that can be selected so that all slope&distance sets between point pairs is distinct?
But why start with such a large grid? Solve it for the $4 \times 4$, $5 \times 5$, $6 \times 6$ grids first. To prevent a parallelogram, you pretty much need to prevent point pairs from sharing the same slope and distance. Not quite -- three points in a row could give a duplicate slope&distance, but let us ignore degenerate solutions for now.
Finding the total number of distinct slope&distance sets in an $n \times n$ grid yields $4, 12, 24, 40, 60, 84, 112, 144, ...$, or $4 T_n$ (OEIS A46092). The maximal points that could be picked without going over that number is $2(n-1)$. $4030$ points in a $2016 \times 2016$ grid isn't immediately ruled out by the pigeonhole principle.
A $5 \times 5$ grid can have 8 cells where all slope&distance for point pairs is distinct. Can 10 points be selected from a $6 \times 6$ grid?
A related problem is to 4-color a $18 \times 18$ grid with no 1-color rectangles.