Given natural numbers $a$ and $b$, such that $a<b<2a$. Some cells on a graph are colored such that in every rectangle with dimensions $A \times B$ or $B \times A$, at least one cell is colored. For which greatest $\alpha$ can you say that for every natural number $N$ you can find a square $N \times N$ in which at least $\alpha \cdot N^2$ cells are colored?
Problem
Source: All Russian Olympiad 2015 11.8
Tags: combinatorics
MathPanda1
11.12.2015 22:55
utkarshgupta wrote: Some cells on a graph are colored such that in every rectangle with dimensions $A \times B$ or $B \times A$, at least one cell is colored.For which greatest $\alpha$ can you say that for every natural number $N$ you can find a square $N \times N$ in which at least $\alpha \cdot N^2$ cells are colored? Doesn't this mean that $\alpha=1$? You can just color every square. Do you mean For which greatest $\alpha$ can you say that for every natural number $N$ you can find a square $N \times N$ in which at most $\alpha \cdot N^2$ cells are colored?
62861
11.12.2015 23:21
MathPanda1 wrote: utkarshgupta wrote: Some cells on a graph are colored such that in every rectangle with dimensions $A \times B$ or $B \times A$, at least one cell is colored.For which greatest $\alpha$ can you say that for every natural number $N$ you can find a square $N \times N$ in which at least $\alpha \cdot N^2$ cells are colored? Doesn't this mean that $\alpha=1$? You can just color every square. Do you mean For which greatest $\alpha$ can you say that for every natural number $N$ you can find a square $N \times N$ in which at most $\alpha \cdot N^2$ cells are colored? You're not finding a coloring; you're finding $\alpha$. You need to find the largest $\alpha$ that works for all valid colorings.
anantmudgal09
16.04.2016 23:14
I have the answer. Will post full solution later.
$\alpha=\frac{1}{2a^2-2ab+b^2}$
rterte
24.05.2016 06:57
utkarshgupta wrote: Given natural numbers $a$ and $b$, such that $a<b<2a$. Some cells on a graph are colored such that in every rectangle with dimensions $A \times B$ or $B \times A$, at least one cell is colored. For which greatest $\alpha$ can you say that for every natural number $N$ you can find a square $N \times N$ in which at least $\alpha \cdot N^2$ cells are colored? What do $A$ and $B$ stands for. Or they are equivalent to $a$ and $b$. Btw, anyone has the original problem statementin Russian
RagvaloD
24.05.2016 16:10
rterte wrote: utkarshgupta wrote: Given natural numbers $a$ and $b$, such that $a<b<2a$. Some cells on a graph are colored such that in every rectangle with dimensions $A \times B$ or $B \times A$, at least one cell is colored. For which greatest $\alpha$ can you say that for every natural number $N$ you can find a square $N \times N$ in which at least $\alpha \cdot N^2$ cells are colored? What do $A$ and $B$ stands for. Or they are equivalent to $a$ and $b$. Btw, anyone has the original problem statementin Russian $A=a,B=b$ Official solution on russian here
Gems98
17.07.2016 20:02
Can you describe me in English? Please
mathcool2009
19.01.2017 03:44
Define a "tall" rectangle as a rectangle which spans $a$ columns and $b$ rows.
Define a "flat" rectangle as a rectangle which spans $b$ columns and $a$ rows.
The answer is $\alpha = 1/D = \dfrac{1}{a^2 + (b-a)^2}$.
First, we will show that $\alpha \le 1/D$ by providing a construction in which $\alpha = 1/D$. Simply take a lattice with basis vectors $(a, b-a)$ and $(-(b-a), a)$ and mark all these cells. To show that this works, you can either just draw it out or you can make a more formal argument. Consider any $b$ consecutive rows; call this the "river". Since neither of the two basis vectors are large enough to jump over the river, the river must contain at least one marked cell. Now consider any $a$ consecutive columns, forming a tall rectangle. Neither of the two basis vectors are large enough to jump over this tall rectangle horizontally, so this tall rectangle must contain at least one marked cell. Similarly you can prove that each flat rectangle contains at least one marked cell.
Now for the reverse implication. We wish to prove that any configuration of marked cells which satisfies the problem statement has $\alpha \ge 1/D$. Let $N$ be a large integer. Choose an $N$ by $N$ square and restrict your attention to the marked cells inside the square. Let $R$ be the set of tall rectangles contained in the square and let $M$ be the set of marked cells contained in the square. The basic idea is to construct a graph from $N$ to $R$, drawing an edge between a rectangle and a marked cell if and only if the marked cell is inside the rectangle. However, this is too wasteful.
The less basic idea is: for each tall rectangle $r$, arbitrarily choose a marked cell $m$ inside $r$ such that $m$ is one of the topmost marked cells in $r$. We will show that each marked cell can be chosen at most $D$ times; this will imply the desired result.
Consider any marked cell $A$. Suppose $A$ is chosen from rectangle $r$. Let $S$ be the set of the $a$ rows above $A$. Clearly the intersection of $r$ with $S$ must contain no marked cells. Suppose $A$ has coordinates $(0,0)$; then let $B$ be one of the marked cells in $S$ with the smallest nonnegative $x$-coordinate and let $C$ be one of the marked cells in $S$ with the largest negative $x$-coordinate. If $r$ intersects all the $a$ rows of $S$, then $r$ must be between $B$ and $C$. However, the horizontal distance between $B$ and $C$ is at most $b-1$ (otherwise one could fit a flat rectangle between $B$ and $C$). Therefore there are at most $(b-a)(b-a) + (a)(a) = D$ possibilities for $r$ given $A$.
Since there are $~N^2$ choices for $r$, we must have at least $~\dfrac{N^2}{D}$ marked cells in the square. QED
Pathological
03.07.2019 23:33
Here is a different way to finish, after finding the answer of $\frac{1}{a^2+(b-a)^2}$. For the construction, use the same one as mathcool2009 used above. Now, let's situate our grid in the Cartesian plane such that the bottom-left corner of every one of the cells is a lattice point. Now, let's concentrate on a $b \times b$ region $R$, with sides situated on lines of the grid. Let's call the central $(2a - b) \times (2a-b)$ the core of the $b \times b$. Lemma. Either the core of $R$ contains at least one colored cell or the rest of $R$ contains at least two colored cells. Proof. This is straightforward, just apply the condition on the topmost and bottommost $a \times b$ sub-grids of $R$, and the leftmost and rightmost $b \times a$ sub-grids of $R$. Simple casework finishes from here. $\blacksquare$ Note that $R$ and the core of $R$ together contain $b^2 + (2a-b)^2 = 4a^2 - 4ab + 2b^2 = 2(a^2+(b-a)^2)$. Furthermore, the lemma above implies that they collectively contain at least $2$ cells. From here, an easy density argument can be used to finish. $\square$