Problem

Source: Romanian 2018 TST Day 1 Problem 3

Tags: combinatorics, combinatorial geometry, ratio



Divide the plane into $1$x$1$ squares formed by the lattice points. Let$S$ be the set-theoretic union of a finite number of such cells, and let $a$ be a positive real number less than or equal to 1/4.Show that S can be covered by a finite number of squares satisfying the following three conditions: 1) Each square in the cover is an array of $1$x$1$ cells 2) The squares in the cover have pairwise disjoint interios and 3)For each square $Q$ in the cover the ratio of the area $S \cap Q$ to the area of Q is at least $a$ and at most $a {(\lfloor a^{-1/2} \rfloor)} ^2$