Tim wants to place $1600$ points inside a unit square such that there is at least one point inside every rectangle of area $\frac{1}{200}$ and with sides parallel to those of the
square. Is it possible to do it? If your answer is yes, please give an example and show that it works. If your answer is no, please prove it is impossible.
A rectangle of area $\frac{1}{200}$ may be $\frac{1}{10} \times \frac{1}{20}$ or $\frac{1}{200} \times \frac{1}{1}$ or $\frac{1}{1} \times \frac{1}{200}$, … .
In my research, to make sure that every rectangle of area $\frac{1}{1} \times\frac{1}{200}$ or $\frac{1}{200} \times \frac{1}{1}$ contains at least one point, we need to make sure that in every row and column of the grid of $200 \times 200$ must contains at least one point. This strategy needs $200 \times 200=40,000$ points.
I would appreciate any help, especially a hint or approach that I can use to find the rest of the solution on my own!
Best Answer
Let's assume $(0,0), (0,1),(1,0),$ and $(1,1)$ are the corners of the unit square.
Place $200$ points on the coordinates $(\frac{i}{200}, \frac{1}{2})$, where $0 \leq i \leq 199$. Then, every rectangular with sides $x$ (horizontal side) and $y$ (vertical side) such that $\frac{1}{200} \leq x \leq \frac{1}{100}$, and hence $\frac{1}{2} \leq y \leq \frac{1}{1}$, contains a point (why?).
Next, place $200$ points on the coordinates $(\frac{2i}{200}, \frac{1}{4})$ and $(\frac{2i}{200}, \frac{3}{4})$, where $0 \leq i \leq 99$. Then, every rectangular with sides $x$ (horizontal side) and $y$ (vertical side) such that $\frac{1}{100} \leq x \leq \frac{1}{50}$, and hence $\frac{1}{4} \leq y \leq \frac{1}{2}$, contains at least a point (why?).
Next, place $200$ points on the coordinates $(\frac{4i}{200}, \frac{1}{8})$, $(\frac{4i}{200}, \frac{3}{8})$, $(\frac{4i}{200}, \frac{5}{8})$, $(\frac{4i}{200}, \frac{7}{8})$, where $0 \leq i \leq 49$. Then, every rectangular with sides $x$ (horizontal side) and $y$ (vertical side) such that $\frac{1}{50} \leq x \leq \frac{1}{25}$, and hence $\frac{1}{8} \leq y \leq \frac{1}{4}$, contains at least a point (why?).
Finally, place $200$ points on the coordinates $(\frac{8i}{200}, \frac{1}{16})$, $(\frac{8i}{200}, \frac{3}{16})$, $(\frac{8i}{200}, \frac{5}{16})$, $(\frac{8i}{200}, \frac{7}{16})$, $(\frac{8i}{200}, \frac{9}{16})$, $(\frac{8i}{200}, \frac{11}{16})$, $(\frac{8i}{200}, \frac{13}{16})$, $(\frac{8i}{200}, \frac{15}{16})$, where $0 \leq i \leq 24$. Then, every rectangular with sides $x$ (horizontal side) and $y$ (vertical side) such that $\frac{1}{25} \leq x \leq \frac{1}{10 \sqrt 2}$, and hence $\frac{1}{10\sqrt 2} \leq y \leq \frac{1}{8}$, contains at least a point because every rectangular with sides $x$ (horizontal side) and $y$ (vertical side) with $\frac{1}{25} \leq x \leq \frac{1}{10 \sqrt 2}$ intersects a line that is divided into $16$ equal segments and $\frac{1}{16} \leq \frac{1}{10 \sqrt 2}$. Note that the same reasoning applies to all the "why?"s above.
So far, we have placed $200 \times 4$ points. By the same argument and adding $800$ more points in a completely similar way but in the $90^{\circ}$-rotated coordinate system (or simply where the axes are swapped), we can prove the same about every rectangular with sides $x$ (vertical side) and $y$ (horizontal side) such that $\frac{1}{200} \leq x \leq \frac{1}{10\sqrt 2}$. Moreover, note that the smaller side of any rectangular of area $\frac{1}{200}$ must be less than or equal to $\frac{1}{10\sqrt 2}.$
We are done.