6
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ You might consider near optimal strategies for A. I get that the limit (if it exists) is between 1 and 11/6. Gerhard "That's With Moderately Clever Play" Paseman, 2018.04.24. $\endgroup$ Apr 24, 2018 at 23:42
  • $\begingroup$ Do you know that $\lim_{n\to\infty}\frac{l(n)}{n}>1$? $\endgroup$ Apr 25, 2018 at 0:11
  • $\begingroup$ It's likely as if you try a strategy with 1 strip each of n,n-1,.. n-k, you have to make up the k^2/2 area among the other lengths. Gerhard "N Divides Only So Much" Paseman, 2018.04.24. $\endgroup$ Apr 25, 2018 at 0:40

4 Answers 4

5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ That comes close to the data provided by Aaron Meyerowitz. I will be surprised to see this improved significantly. Gerhard "Now We Have A Strategy" Paseman, 2018.04.25. $\endgroup$ Apr 25, 2018 at 20:26
3
$\begingroup$

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.$

enter image description here

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.$

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ You can modify your first observation by e.g. replacing one of the n-1 stripes by a stripe with n/2 +- 1. You can replace more than 1/12 the stripes this way, which is how I arrived at 11/6 for a tentative upper bound. Gerhard "They Make Me Look Thinner" Paseman, 2018.04.25. $\endgroup$ Apr 25, 2018 at 23:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.