Given a positive integer $n$, determine the maximum number of lattice points in the plane a square of side length $n +\frac{1}{2n+1}$ may cover.
Problem
Source: Danube 2012 p1
Tags: lattice points, square, covering, combinatorial geometry, combinatorics
22.07.2019 22:30
I tried using AM-GM to maximize this, but it didn't work. Can someone help?
23.07.2019 01:29
Bump $~~~~$
23.07.2019 21:35
Can someone help fast?
09.10.2019 04:01
help pls anyone
09.10.2019 16:13
Lemma: Among any $ 5 $ lattice points, there are at least two of them placed at a distance of at least $ \sqrt 5. $ Obs: This is a classical casey computational problem. The brute-froce approach is to suppose there exists a counterexample to the lemma, apply the Euclidean distance to the Cartesian representation of any two of these points to obtain sets representing the possible placements of the points, and intersect those sets to obtain the empty set which would be a contradiction. Notice that $ \frac{1}{3}< -1+\sqrt{\frac{5}{2}} , $ which implies that $ \sqrt 5 >(1+1/3 )\sqrt{2} . $ The $ \text{RHS} $ of this last inequality represents the diagonal of a square of side length $ 1+1/3. $ If this square would cover $ 5 $ lattice points, then, the distance of its diagonal would be at least the maximum distance any of these points may have which, would contradict the lemma. So, the number of lattice points that a square of side $ 1+1/3 $ may cover is at most $ 4.\quad \text{(i)} $ Let be a natural number $ n\ge 2, $ and let be a square $ S $ of length $ n+\frac{1}{1+2n} $ that contains exactly $ i $ lattice points in its interior and has $ b $ lattice points on its boundary. Let $ H $ be the convex hull of the lattice points covered by $ S. $ Quickly observe that $ H $ is bounded by $ S, $ which means that the area of $ H $ at most the area of $ S.\quad\text{(ii)} $ Also, by the nature of lattice points, $ b $ is at most the floor of the perimeter of $ H $ which, a result of the defition of convexity, is at most the floor of the perimeter of $ S.\quad\text{(iii)} $ Therefore, $$ i+b\stackrel{\text{Pick's theorem}}{=}\mathcal{A}_{H} +\frac{b}{2}+1\stackrel{\text{(ii) and (iii)}}{\le } \left\lfloor\left( n+\frac{1}{1+2n} \right)^2 +\frac{1}{2}\left\lfloor 4\left( n+\frac{1}{1+2n} \right) \right\rfloor +1\right\rfloor\le $$$$ \le\left\lfloor n^2+\frac{2n}{1+2n} +\frac{1}{(1+2n)^2} +2n+1 \right\rfloor\le\left\lfloor (1+n)^2+\frac{1+4n}{1+4n+4n^2} \right\rfloor =(1+n)^2. $$So, the number of lattice points that a square of side $ n+\frac{1}{1+2n} $ may cover is at most $ (1+n)^2.\quad\text{(iv)} $ For the final verification, consider the sequence of squares characterized by the Cartesian vertices: $ (0,0),(0,n+\frac{1}{1+2n}),(n+\frac{1}{1+2n},n+\frac{1}{1+2n}),(n+\frac{1}{1+2n},0) , $ for any natural numbers $ n. $ These indeed cover $ (1+n)^2 $ lattice points. $ \text{(v)} $ With $ \text{(i),(iv)} $ and $ \text{(v)} , $ the proof is finished.