A polygon $\prod$ is given in the $OXY$ plane and its area exceeds $n.$ Prove that there exist $n+1$ points $P_{1}(x_1, y_1), P_{2}(x_2, y_2), \ldots, P_{n+1}(x_{n+1}, y_{n+1})$ in $\prod$ such that $\forall i,j \in \{1, 2, \ldots, n+1\}$, $x_j - x_i$ and $y_j - y_i$ are all integers.
Problem
Source: China TST 1988, problem 7
Tags: geometry, geometric transformation, vector, analytic geometry, combinatorics, lattice
27.06.2005 14:36
Divide the plane into unit squares. Let $O$ be the origin. Let $U$ be one of the unit squares, with vertices $XYZT$ where $X$ is the lower-left one. Then consider the translation $t_U$ with vector $XO$. It maps $U$ onto the unit square $S$ with lower-left vertex $O$. Note that for each point $M$ in $U$, the vector $Mt(M)$ has integer coordinates (since it is $XO$). The common part of the given polygon and $U$, say $P_U$, which is a polygon, is map to a congruent polygon $t(P_U)$, so that it has the same area. Now, except for a part with area $0$ (the intersection of the given polygon with the lines with equation $x=k$ of $y=k$, where $k$ is an integer), the area of the given polygon is the sum of the areas of the polygons $P_U$, where the sum is over all the unit squares $U$. But all the $t(P_U)$ are in $S$, which has area $1$. Since the sum of the areas is greater than $n$, the pigeon-hole principle ensures that a point, say $M$, of $S$, is covered at least $n+1$ times by the $t(P_U)$. It means that there exists $M_1, \cdots, M_{n+1}$ pairwise distinct points in the given polygon such that each of them has image $M$ by the appropriate translation. Since all the translations have vectors with integer coordinates and that a composition of translation is a translation obtained by summing the vectors, it follows that the vector $M_iM_j$ has integer coordinates for all $i<j$. Pierre.
18.08.2009 03:04
Translate all unit squares of the integer lattice in the plane onto one particular one, With overlaps or not, the portions of the interior of the polygon will cover (at least) one point (at least) $ n+1$ times. The back-translates of that point in the interior of the polygon will yield the required points.
31.07.2018 21:24
Is it possible to state solution like this? Divide the plane into unit squares.Take some random unit sqare.Then color that polygon with red.Now start packing squares with color on top of chosen square (translate it on top).When we are finished volume of red color is bigger than n(cm).Take random point in chosen square and if there are more than n points of red color that are above (and collinear with it ) then we are done.Otherwise there are less than n points above every point so volume is less that or equal to n contradiction.
25.01.2022 23:36
Nice problem! Solved with Dimath27 . The key idea is divided the plane into unit squares and after this, select the squares that cut the polygon, turn them into paper and put one on top of the other so we are left with an unit square divided in finite areas. If exists an area that was in at least $n$ squares we can go through this area with a pin and we get at least $n$ point that satisfy the problem (because when we put the unit squares back in their places, the point distances are compositions of vertical or horizontal translations of size $1$). But this area always exists since otherwise each area is repeated at most $n-1$ times and adding the areas of the unit squares we obtain that the area of the polygon is at most $n-1$. Contradiction! $\blacksquare$
15.10.2023 23:31
18.10.2023 00:34
Have the lattice lines seperate the polygon into different sections and merge them all into a $1\times 1$ cell. By Pigeonhole, there exists a point $P$ that is overlapped by $n+1$ different regions. After translating the regions back, the $n+1$ points created by this operation would satisfy the given conditions. $\square$
18.11.2023 05:23
For a point $P_0=(x_0,y_0)$ in the coordinate plane, define $\bf{F} (P_0)$ to be $(\{x_0\},\{y_0\})$, where $\{r\}$ of a real number $r$ denotes the fractional part of $r$. The problem is asking us to prove that given a polygon $\Pi$ with area greater than $n$, there is a point $P_0\in [0,1]\times[0,1]$ such that are $n+1$ points $P_1$, $P_2$, $\dots$, $P_{n+1}$ in $\Pi$ such that $P_0=\bf{F} (P_1)=\bf{F} (P_2)=\dots=\bf{F} (P_{n+1})$. Assume for the sake of contradiction that there is no such point $P_0$. This means that over all points $Q$ in $\Pi$, the values of $\bf{F}(Q)$ "cover" each point in the unit square $[0,1]\times[0,1]$ at most $n$ times each, meaning that the area of $\Pi$ is at most $1*1*1=n$, a contradiction by problem conditions. Therefore, there must exist at least $n+1$ such points as described in the problem, and we are done.
26.12.2023 19:44
Consider the mapping of polygon $\Pi$ under $(x,y) \mapsto (x-\lfloor x \rfloor, x-\lfloor y \rfloor)$, where we also take multiplicities into account. By Pigeonhole, there exists at least one point covered at least $n+1$ times, which we set as our origin. $\blacksquare$
14.07.2024 06:08
Consider taking the fractional part of each coordinate in the polygon. Then, there will be overlaps in a $1\times 1$ unit square. Specifically, since the area of this polygon is greater than $n$, there is at least one point which has $n+1$ points mapped to it. All of these $n+1$ points work as $P_1,P_2,\ldots, P_{n+1}$ because having the same fractional part means the difference of their coordinates must be integers.
29.11.2024 21:05