Let $n \geq 2$ be a positive integer. Let $\mathcal{R}$ be a connected set of unit squares on a grid. A bar is a rectangle of length or width $1$ which is fully contained in $\mathcal{R}$. A bar is special if it is not fully contained within any larger bar. Given that $\mathcal{R}$ contains special bars of sizes $1 \times 2,1 \times 3,\ldots,1 \times n$, find the smallest possible number of unit squares in $\mathcal{R}$. Srinivas Arun
Problem
Source: ELMO Shortlist 2024/C4
Tags: Elmo, combinatorics
MarkBcc168
22.06.2024 18:49
The answer is
$$ f(n) = \begin{cases}
3t^2 - t & \text{ if } x = 3t-1 \\
3t^2 + t & \text{ if } x = 3t \\
3t^2 + 3t + 1 & \text{ if } x = 3t+1 \\
\end{cases}$$
Bound.
Let $ k = \lfloor \frac n3 \rfloor$. We only consider (the union of) bars of size $1 \times (k+1), \cdots, 1 \times n$. Some are vertical, and some are horizontal. Note if two bars have the same orientation, then they are disjoint.
Thus, we have
\begin{align*}\#\text{cells} &\geq (k+1)+(k+2)+\dots+n - \#(\text{overlap cells}) \\
&= \frac{(n+k+1)(n-k)}2 - \#(\text{horizontal bars})
\cdot \#(\text{vertical bars}) \\
&\geq \frac{(n+k+1)(n-k)}2 - \left\lfloor \frac{(n-k)^2}4\right\rfloor
\end{align*}We can check with casework with $n$ mod 3 that this shows the number of cells is at least $f(n)$; note $n-k$ is odd iff $n\equiv 1\pmod 3$.
Construction
The construction basically follows the equality case above. Here is the diagram for $n=21$.
[asy][asy]
size(5.5cm);
int n = 21;
int k = n # 3;
int l = (n-k) # 2;
for(int i=0; i<=n; ++i){
draw((i,0)--(i,-(k+l)), mediumgray);
}
for(int j=0; j<=k+l; ++j){
draw((0,-j)--(n,-j), mediumgray);
}
for(int i=0; i<n-k-l; ++i){
draw(box((0,-i),(n-i, -(i+1))), linewidth(1));
}
for(int i=0; i<l; ++i){
draw(box((i,0), (i+1,-(k+l-i))), linewidth(1));
}
[/asy][/asy]
Let $k=\lfloor\tfrac n3\rfloor$, and let $l = \lfloor\tfrac{n-k}2\rfloor$. We then
Stack bars of size $1\times n$, $\dots$, $1\times (k+l+2)$, $1\times (k+l+1)$ horizontally (from top to bottom) so that their leftmost cells share the same column.
Stack bars of size $(k+1)\times 1$, $(k+2)\times 1$, $\dots$, $(k+l)\times 1$ vertically so that their topmost cells is exactly the top bar.
Bars of size $1\times 2$, $1\times 3$, $\dots$, $1\times k$ are guaranteed to be included.
This construction matches all equalities in the bound above.
YaoAOPS
24.06.2024 11:12
Stranger construction + the same bounding but written in a way such that the fact it simplifies nice comes out like a miracle. The answer gives away too much so the sol below is likewise hidden.
The answer is $3k^2 + 3k + 1$ for $3k + 1$, $3k^2 + 5k + 2$ for $3k + 2$, and $3k^2 + 7k + 4$ for $3k + 3$.
Construction
Take the base case of $k = 0$ by taking a $1 \times 1, 1 \times 2$ and an $L$ shape.
We strengthen to the claim of also containing a $1 \times 1$ bar.
To induct up from $t$ to $t + 3$, attach an $L$ shape with legs of length $t+3, t+2$ (for a total of $t+2$ blocks) to the Young Tableaux. This increases the length of all the earlier bars by $1$, adds a new $1 \times 1$ bar, and adds a $1 \times t+3$ and $1 \times t+2$ length bar.
[asy][asy]
size(5cm);
pen pa, pb; pa = purple+white;
pb = green+white;
filldraw(unitsquare, pa);
filldraw(shift(1,0)*unitsquare, pa); filldraw(shift(2,0)*unitsquare, pa); filldraw(shift(3,0)*unitsquare, pa); filldraw(shift(4,0)*unitsquare, pa); filldraw(shift(0,1)*unitsquare, pa); filldraw(shift(0,2)*unitsquare, pa); filldraw(shift(0,3)*unitsquare, pa); filldraw(shift(0,4)*unitsquare, pa); filldraw(shift(0,5)*unitsquare, pa);
filldraw(shift(1,1)*unitsquare, pb); filldraw(shift(1,2)*unitsquare, pb); filldraw(shift(1,3)*unitsquare, pb); filldraw(shift(2,1)*unitsquare, pb);
[/asy][/asy]
Bounding
Suppose that bars of length $1 \times 2, \dots, 1 \times t$ are required. For each bar, mark some row or column that contains it. Let $r$ be the number of rows and $c$ be the number of columns. WLOG let $r < c$.
Now, consider the $r-2$ bars with length less than $r$. These bars can be only filled to their max.
If $r' < r, c' < c$ are the rows which contain a bar that isn't one of the $r-2$, then there are at least \[ \frac{t(t+1)}{2} - 1 - r'c' - (2 + \dots + r-1) \]elements.
Note that $r' + c' \le (t-r+1)$ so $r'c' \le \min\{\frac{(t-r+1)^2}{4}, r(t+1-2r) \}$.
This gives us one bound \[ \frac{t(t+1)}{2} - 1 - \frac{(t-r+1)^2 + 2((r-1)r - 2)}{4} \]which is concave in $r$, so taking the smallest $r$ possible works.
On the other hand, \[ \frac{t(t+1)}{2} - 1 - \frac{4r(t+1-2r) + 2((r-1)r - 2)}{4} \]is minimized at $r = \frac{2t+1}{6}$
As such, the function is minimized at the point we swap between the two $\min$ functions, or $r = \frac{t}{3} = \frac{t+1}{3}$.
We then get a value of at least \begin{align*} \frac{t(t+1)}{2} - 1 - \frac{t+1}{3} \cdot \left(t+1 - \frac{2(t+1)}{3}\right) - \frac{(t+1)(t-2)}{18} + 1 &= \\ \frac{t(t+1)}{2} - \frac{(t+1)^2}{9} - \frac{(t+1)(t-2)}{18} &= \\ \frac{1}{18} \left(9t(t+1) - 2(t+1)^2 - (t+1)(t-2)\right) &= \\ \frac{1}{18} \left(9t^2 + 9t - 2t^2 - 4t - 2 - t^2 + t + 2\right) &= \\ \frac{t^2}{3} + \frac{t}{3} \\ \end{align*}Then we have that $\frac{(3k+1)^2}{3} + \frac{3k+1}{3} = 3k^2 + 3k + \frac{2}{3}$, $\frac{(3k+2)^2}{3} + \frac{3k+2}{3} = 3k^2 + 5k + 2$, and $\frac{(3k+3)^2}{3} + \frac{3k+3}{3} = 3k^2 + 7k + 4$.
Remark: This is actually why equality holds for the latter two cases but not for the first.