Limit of a Combinatorial Function

Question

I need help with the following problem, proposed by Iurie Boreico:

Two players, $A$ and $B$, play the following game: $A$ divides an $n \times n $ square into strips of unit width (and various integer lengths). After that, player $B$ picks an integer $k$, $1 \leq k \leq n$, and removes all strips of length $k$. Let $l(n)$ be the largest area that $B$ can remove, regardless how $A$ divides the square into strips. Evaluate $$ \lim_{n \to \infty} \frac{l(n)}{n}. $$

Some progress that I made on this problem:

Observe that there is at most $l(n)/k$ strips of length $k$. So,

$l(n)n - \sum_{k = 1}^n l(n) \pmod k = \sum_{k = 1}^n k \lfloor l(n)/k \rfloor \geq n^2$.

Now I'm stumped on how to asymptotically bound the left hand side, and I cannot find this problem posted anywhere online. Any solutions, observations, progress is appreciated.

Answer 1

The limit is at least $2/\sqrt 3\approx 1.1547$. Write $\alpha=1/\sqrt 3$. If any strip length $\alpha n$ or more is used more than once, then obviously area $2\alpha$ can be chosen. On the other hand, if those large lengths are used at most once, they use up at most $1/3$ of the board. Then by pigeons at least one of the other strip lengths has total length at least $\frac{2n^2/3}{\alpha n}=2\alpha$.

This argument can certainly be sharpened by considering which strip lengths can be used at most twice, at most three times, etc.. The precise answer is certainly greater than $2/\sqrt 3$.

Also note that I didn't use the square structure of the board but only integer partitions of $n^2$. It would be nice to know whether or not the limit for square boards is equal to the limit for partitions.

Answer 2

If $B$ can remove an area not more than $c n$, then there exist at most 1 bricks of size between $cn/2$ and $n$, at most 2 bricks of size between $cn/3$ and $cn/2$, and so on. Totally, the whole size does not exceed $$\frac{n^2}2 (1-c^2/4+2(c^2/4-c^2/9)+\dots+o(1)),$$ $2\leq 1 +c^2 (\pi^2 /6-1) +o(1)$, thus the limit is at least $\sqrt{\frac{6} {\pi^2 - 6} }=1.245\dots$. I see no immediate reason why this is not achievable.

Answer 3

I had an analysis which, when corrected gives the same answer of $\sqrt{\frac{6}{\pi^2-6}} \approx 1.24521$ obtained in other answers, but by a (needlessly) more complicated approach. That agrees well with the computational results below. The data around $n=2000$ seems to range from $\frac{56}{45} \approx 1.244$ at $n=44\cdot 45=1980$ up to $\frac{420}{337} \approx 1.246$ at $n=5\cdot337=1685.$ These exact ratios occur again at $45^2=2025$ and $6\cdot337=2022.$

I've left my now corrected answer since it solves another problem as well: Given $n$ define $m=m(n)$ to be the minimal integer such that we can partition $n^2$ and have for each $k$ that the sum of the parts of size $k$ is at most $m.$ So the difference here is that parts up to $m$ are allowed. This might be breaking up a strip of unit width and length $n^2.$ It turns out that $$\lim_{n \to \infty}\frac{m(n)}{n}=\frac{\sqrt{12}}{\pi}\approx 1.10265779.$$

---

The given problem concerns $l(n)$ defined as the smallest $m$ so that the integer $n^2$ can be partitioned into parts of size at most $n$ in such a way that that, for each $k$, the sum of the parts of size $k$ is at most $m.$ In other words, $\sum_{k=1}^n\lfloor \frac{m}{k}\rfloor k \geq n^2$ with an added geometric requirement. I suspect this requirement is easily satisfied, see the example below with $n,m=15,18$.

Consider instead this question: Given an integer $m$ find $N=N_m$ the largest integer such that we can partition $N$ into integer parts so that, for each $k,$ the sum of the parts equal to $k$ is no larger than $m.$ Thus $N_m=N=\sum_{k=1}^m\lfloor\frac{m}{k}\rfloor k.$ It turns out that asymptotically $N_m=m^2\frac{\pi^2}{12}+O(m\log{m}).$

For example, with $m=18$ we have $$N_{18}=\sum_{k=1}^{18}k\lfloor\frac{18}{k}\rfloor=277$$ from the partition $1^{18}2^93^64^45^36^37^28^29^210^1\cdots18^1.$

If we keep $m=18$ but start restricting the largest part to $n$ we get $277,259,242,226,211$ respectively for $n=18,17,16,15,14.$ Since $226 \gt 15^2$ we might have a chance to split a $15 \times 15$ square into strips as in the proposed problem giving $l(15)=18.$ Indeed a greedy dissection gives rows $[15],[14,1],[13,2],[12,3],[11,4],[10,5],[9,6],[9,6],[8,7],[8,7],[6,5,4],[5,4^2,2],[3^5],[2^7,1],[1^{15}]$ with an extra $1$ left over.

Digression: For $m=17$ vs. $m=16$ one has $205,190,176$ vs. $204,189,175$ for $n=15,14,13$ respectively. So $l(14)=18$ and $l(13)=16$

---

Ignore for now the restriction that the top part size is $n \lt m.$ Then $$N_m=\sum_{k=1}^m\lfloor\frac{m}{k}\rfloor k=\sum_{k=1}^m\frac{m-r_k}{k}k=m^2-\sum_{k=1}^mr_k$$ where $r_k = m \bmod k.$

As one might hope, the sequence $N_m$ is in the OEIS as A024916 where the asymptotics are explained.

If we restrict the largest part to be $n$ then we have instead $nm-\sum_{k=1}^nr_k = N_m-(m-n)m+\sum_{r=1}^{m-n}r.$ Now if $m=cn$ we have $N_m=c^2n^2\frac{\pi^2}{12}+O(n\log n)$ so the thing we want to exceed $n^2$ is $$\frac{{c}^{2}{\pi}^{2}-6\,{c}^{2}+6}{12}n^2+O(n\log{n}).$$ So, finally, $$c=\sqrt{\frac{6}{\pi^2-6}}\ .$$

---

Here are the actual ratios from $400 \leq n \leq 2000.$

An important disclaimer is this is actually for partitions of $n^2$ into parts at most $n.$ I suspect that it would not make a difference. There are so many small numbers that I suspect a greedy process would easily fill the square. However I didn't check. It might be interesting to allow larger parts. That would give a lower bound.

Some random observations:

• The ratio is $\frac{66}{53}$ for all multiples $n=53j \lt 2000.$ So $37$ times up to $2000.$

• The ratio is $\frac{56}{45}$ for all multiples $n=45j \lt 45^2$ with $j \leq 28$ and also $30,33,36,39,42,45.$ So $33$ times under $2000.$

These are the most frequent exact ratios up to $2000$ except $\frac54$ which occurs $47$ times. The last one is $n=384.$

Answer 4

Here is another way to get the bound obtained by Fedor Petrov.

One observation is that from the covering of the board using strips of size $1 \times i$ and $1 \times n-i$ to cover row $r$ for rows $1 \leq r \leq n$, then $l(n) \leq (n-1) + (n-1) = 2n-2$. From the Pigeonhole principle, we also have that $n \leq l(n)$. So, $n \leq l(n) \leq 2n-2$.

As stated in the OP, we have that

$$ l(n)n - \sum_{k = 1}^n l(n) \pmod k \geq n^2. $$

We will try to get a bound the second sum. To make notation more simple, we let $l(n) = L$. Splitting the sum from $1 \leq k \leq L/2$ and $L/2 < k \leq n$, we have that \begin{align*} \sum_{n \geq k > L/2} l(n) \pmod k & = \sum_{n \geq k > L/2} L - k \\ & = \left ( n - \frac{L}{2} \right ) \left ( \frac{3L}{4} - \frac{n}{2} \right) + O(L) \\ & = nL - \frac{n^2}{2} - \frac{3L^2}{8} + O(L). \end{align*} For the second sum, we have that \begin{align*} \sum_{k \leq L/2} L \pmod k & = \sum_{i = 2}^L \sum_{\frac{L}{i+1} < k \leq \frac{L}{i}} L \pmod k\\ & = \sum_{i = 2}^L \sum_{\frac{L}{i+1} < k \leq \frac{L}{i}} L - ik \\ & = \sum_{i = 2}^L \frac{L^2}{2i(i+1)^2} + L \cdot O\left (\frac{1}{i+1} \right) \\ & = O(L \log L) + \frac{L^2}{2} \sum_{i = 2}^L \frac{1}{i(i+1)^2}. \end{align*} Since $$\sum_{i = 2}^L \frac{1}{i(i+1)^2} = \sum_{i = 2}^\infty \frac{1}{i(i+1)^2} - \sum_{i \geq L+1} \frac{1}{i(i+1)^2} = \frac{7}{4} - \frac{\pi^2}{6} + O \left (\frac{1}{L^2}\right ).$$

So, $$\sum_{k \leq L/2} L \pmod k = O(L \log L) + \left ( \frac{7}{8} - \frac{\pi^2}{12} \right ) L^2.$$

Adding our two expressions together, we have that $$\sum_{k = 1}^n L \pmod k = nL - \frac{n^2}{2} + \left ( \frac{1}{2} - \frac{\pi^2}{12} \right ) L^2 + O(L \log L).$$

Hence,

\begin{align*} nL - \sum_{k = 1}^n l(n) \pmod k & \geq n^2 \\ \left ( \frac{\pi^2}{12} - \frac{1}{2} \right ) L^2 + O(L \log L) & \geq \frac{n^2}{2} \\ \left ( \frac{L}{n} \right )^2 & \geq \frac{6}{\pi^2 - 6} + o(1) \\ \frac{L}{n} & \geq \sqrt{ \frac{6}{\pi^2 - 6} } + o(1). \end{align*} Taking the limit as $n \to \infty$, we find that the limit is $\boxed{\geq \sqrt{6/(\pi^2 - 6)}}$.

The only upper bound I've arrived at is $2$ which can be achieved by the first observation.