Consider $2011^2$ points arranged in the form of a $2011 \times 2011$ grid. What is the maximum number of points that can be chosen among them so that no four of them form the vertices of either an isosceles trapezium or a rectangle whose parallel sides are parallel to the grid lines?
Problem
Source:
Tags: geometry, trapezoid, rectangle, parallelogram, combinatorics unsolved, combinatorics
31.12.2011 19:41
Color the diagonal and one row complete, now there aren't isoceles trapezoids. If we have at least $4022$ points, we can look horizontally and see that there are at least $n-1$ different lengts in a row with $n$ points. Adding we have $2011$ lengths in all the rows, but there are only $2010$ possible (from $1$ to $2010$), so we will have a parallellogram, which is an isoceles trapezoid.
08.05.2017 01:10
Hello, the above solution assumes that a parallelogram is an isosceles trapezoid, but I think by most conventional definitions, this isn't true. Assuming this, is there a solution to this new problem?
03.06.2018 10:51
If the trapezium has to have its parallel sides parallel to the grid lines, then at least $3n -3$ points are needed: for example, take the entire first row (the upper one), first column (the left-most one) and the first diagonal (the one starting from the upper left corner) and simply remove from the considered points the upper left corner. Proof: We want to reduce the case $n \times n$ to a case $n_0 \times n_0$ with $n_0 \leq n$, which can be supposed to be true as a strong induction hypothesis. If there is a full row or a full column, it is easy to see that we can't put more than $2n-1$ points in total (that means $2$ points on the same other row), because otherwise we will form a rectangle. Consider the row with the biggest number of considered points. It has at most $n-1$ points. Suppose it has $k$ points. On that $k$ columns (the ones containing that $k$ points) we can't have more than $k$ other points. Now eliminate that $k$ columns. We have a $n-1 \times n-k$ rectangle remaining (note that the row with $k$ points doesn't have points on the other $n-k$ points, so we exclude that row from the $n \times n-k$ rectangle to obtain the $n-1 \times n-k$ rectangle). In this rectangle we repeat the presented procedure again (take the columns as rows and rows as columns), and at the end we will remain with a $k \times k$ rectangle or a $n-k \times n-k$, which can be suppose to have at most $3k-3$ or $3n-3k-3$ points (the induction hypothesis). Therefore, at most $3n-3$ points can be considered. It is important to note that the example presented can be modified to have every only $k$ points considered on each row for every $k \leq n-1$.
03.06.2018 11:44
I think that the above bound is wrong. It completely ignores the "isosceles trapezium" part of the condition. I think that the bound is \(\frac{5n-3}{2}\). For a proof of this bound, consider the points on any given row. It is well-known that if there are \(x\) selected points on this row, then there are at least \(2x-3\) points on this row are the midpoints of some two distinct points on this row. But then, if a midpoint from one row is directly above (or below) a midpoint from another row, then we get that the points corresponding to the midpoints mentioned form an isosceles trapezoid, thus we get a contradiction. Thus, if there are \(a_k\) points on row \(k\), then there are \(2a_k-3\) midpoints on this row, and since there are only \(2(n)-3\) possible midpoints all in all in the \(nxn\) grid, we get the upper bound by \(\displaystyle \sum_{i=1}^n (2a_i-3) \leq 2n-3\). I don't know about the construction, though. Update: Okay, well no construction for now. Can anyone provide a construction tho
04.06.2018 09:20
Look at the bolded points: XXOOOOOOOOO XOXOOOOOOOO OXXOOOOOOOO OXOXOOOOOOO OOXXOOOOOOO OOXOXOOOOOO OOOXXOOOOOO OOOXOXOOOOO OOOOXXOOOOO OOOOXOXOOOO OOOOOXXXXXXX They form a isosceles trapezium.
07.06.2018 19:01
Well done boiiii
19.09.2020 13:05
ManuelKahayon wrote: I think that the above bound is wrong. It completely ignores the "isosceles trapezium" part of the condition. Could you please explain how is this so? Sincerely, Aayam
19.09.2020 13:23
ManuelKahayon wrote: I think that the above bound is wrong. It completely ignores the "isosceles trapezium" part of the condition. What i do wonder is that because $3n-3=\frac{6n-6}{2}$ and so comparing your bound to this one, its clear that for $n \geq 3$ the bound given by @MK4J is better (equal too sometimes but yeah) and since it clearly works, i really do not see any reason as to why we should prefer the the $\frac{5n-3}{2}$ bound over this one, since we dont its not just theoretically weaker but we do not even have a construction for it! Have i said anything wrong dear mathlinkers? ( I do not mean any offense ) Sincerely, Aayam
19.09.2020 14:40
Could someone maybe try to prove the $3n-3$ bound by contradiction (assume that there exists a configuration with atleast $3n-2$ points)? I do agree with the fact that @MK4J 's proof is absolutely not satisfying . Sincerely, Aayam
20.03.2024 22:22
sorry for bump but is there any configuration?