22
$\begingroup$

Consider the set of all the rectangles with dimensions $2^a\times 2^b\,a,b\in \mathbb{Z}^{\ge 0}$. We want to tile an $n\times n$ square by rectangles from this set (you can use a rectangle several times). What is the minimum number of rectangles we need?

If $f(n)$ is the sum of digits of $n$ in base $2$, I think we need at most $f(n)^2$ rectangles. I have an example for this number: write $n=2^{a_1}+2^{a_2}+...2^{a_{f(n)}}$ and split each side to segments with length $2^{a_1},2^{a_2},...,2^{a_{f(n)}}$ and consider $f(n)^2$ rectangles obtained this way.

On the other hand, you need at least $f(n)$ rectangles to tile a raw (or column) so I think you need $f(n)^2$ rectangles, but I can't prove it.

Any ideas?

$\endgroup$
4
  • $\begingroup$ By $f(n)$ do you mean the sum of the bits in the binary representation of $n$? $\endgroup$ Apr 3, 2019 at 20:18
  • $\begingroup$ @JohnWaylandBales yes f(n) is the least number such that $n=2^{a_1}+2^{a_2}+...2^{f(n)}$ $\endgroup$
    – ali
    Apr 3, 2019 at 20:23
  • $\begingroup$ You mean $f(n)$ is the least number such that $n = 2^{a_1} + 2^{a_2} + \cdots + 2^{a_{f(n)}}$ right? Because $f(n)$ counts the number of terms, but it is not the highest exponent. $\endgroup$
    – antkam
    Apr 4, 2019 at 3:51
  • $\begingroup$ @antkam yes i edited the question $\endgroup$
    – ali
    Apr 4, 2019 at 4:36

3 Answers 3

18
+50
$\begingroup$

MAJOR UPDATE:

What I am about to show is not a proof for the minimum number of rectangles. However, in some cases I found the number of rectangles can be less than $f(n)^2$. The smallest $N×N$ grid that I have found that can have less than $f(n)^2$ rectangles is $15×15$, which is displayed below: $$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 1&1&1&1&2&2&3&4&4&4&4&4&4&4&4\\ \hline 1&1&1&1&2&2&3&4&4&4&4&4&4&4&4\\ \hline 1&1&1&1&2&2&3&4&4&4&4&4&4&4&4\\ \hline 1&1&1&1&2&2&3&4&4&4&4&4&4&4&4\\ \hline 1&1&1&1&2&2&3&5&5&5&5&5&5&5&5\\ \hline 1&1&1&1&2&2&3&5&5&5&5&5&5&5&5\\ \hline 1&1&1&1&2&2&3&6&6&6&6&6&6&6&6\\ \hline 1&1&1&1&2&2&3&7&8&9&9&10&10&10&10\\ \hline 11&11&11&11&11&11&11&11&8&9&9&10&10&10&10\\ \hline 12&12&12&12&12&12&12&12&8&9&9&10&10&10&10\\ \hline 12&12&12&12&12&12&12&12&8&9&9&10&10&10&10\\ \hline 13&13&13&13&13&13&13&13&8&9&9&10&10&10&10\\ \hline 13&13&13&13&13&13&13&13&8&9&9&10&10&10&10\\ \hline 13&13&13&13&13&13&13&13&8&9&9&10&10&10&10\\ \hline 13&13&13&13&13&13&13&13&8&9&9&10&10&10&10\\ \hline \end{array}$$

The method used in the above $15×15$ square can be generalized not just to other squares but to rectangles as well. In order to make full use of this method, I will expand the op's method to rectangles. Let the length of a rectangle be equal to $m$ units and the width be $n$ units. Then the number of base-2 rectangles used to cover a $m × n$ rectangle by the op's method is $f(m)f(n)$. My method isn't fundamentally different from the op's method. It splits the $m×n$ rectangle into five sub-rectangles, then the op's method is applied to each of the five rectangles. In some cases the number of base-2 rectangles that covers the five sub-rectangles is less than the number of base-2 rectangles that cover original $m$×$n$ rectangle using the op's method. The five rectangles are arranged so that their are two pairs of rectangles that occupy the corners and one rectangle that is in the middle (not touching the perimeter). Each pair of rectangles are the same size and orientation but in opposite corners. (Top left and bottom right or Top right and bottom left.) The length and width of the five rectangles are constructed from two other unit lengths $a$ and $b$. $a$ is the smallest number such that $m+a$ is a power of two. $b$ is the smallest number such that $n+b$ is a power of two. This means that $f(m+a)$ and $f(n+b)$ are each one. The length and width of the two rectangles in the first pair are $f\left(\frac{m+a}{2}\right)$ and $f\left(\frac{n-b}{2}\right)$ respectively. The length and width of the two rectangles in the second pair are $f\left(\frac{m-a}{2}\right)$ and $f\left(\frac{n+b}{2}\right)$ respectively. The formula for the total number of base-2 rectangle used is $2f\left(\frac{m+a}{2}\right) f\left(\frac{n-b}{2}\right)+2f\left(\frac{m-a}{2}\right) f\left(\frac{n+b}{2}\right)+f(a)f(b)$.

Note that if a square with a length of $n$ units is of the form $2^xy$ where $x,y\in\Bbb{N}|x\ge 1,y\ge 1$ and $y$ is odd. Then the number of base-2 rectangles used for both the op's method and my method are the the same as the number of base-2 rectangles used for a square of length $y$ because each of the dimensions of the sub-rectangles can be multiplied by $2^x$. For example if we want to determine how many base-2 rectangles is rectangles are required to cover a $30×30$ square using my method. We just use the $15×15$ example near the top of this post and multiply the length and width of each base-2 rectangle by $2$. So this means the $30×30$ square requires the same number of base-2 rectangles as the $15×15$ square. So the problem can be simplified to just rectangles where $m$ and $n$ are odd.

A simple inequality can be made which would indicate which method uses less base-2 rectangles. Let $N_l$ be the number of ones in the number for length of the rectangle in binary and $N_w$ be the number of ones in the width in binary $\bigl($or more simply $N_l=f(m)$ and $N_w=f(n)\bigr)$. Also Let $Z_l$ be the number of zeros in the number for length of the rectangle in binary, $Z_w$ be the number of zeros in the width in binary. My method uses less rectangles than the op when $$2f\left(\frac{m+a}{2}\right) f\left(\frac{n-b}{2}\right)+2f\left(\frac{m-a}{2}\right) f\left(\frac{n+b}{2}\right)+f(a)f(b)\lt f(m)f(n)$$

$$f\left(\frac{m+a}{2}\right)=1$$ $$f\left(\frac{n+b}{2}\right)=1$$ $$f\left(\frac{m-a}{2}\right)=N_l-1$$ $$f\left(\frac{n-b}{2}\right)=N_w-1$$ $$f(m)=N_l$$ $$f(n)=N_w$$ $$f(a)=Z_l+1$$ $$f(b)=Z_w+1$$

With the above substitutions the inequality can be changed to:

$$2(N_l-1)+2(N_w-1)+(Z_l+1)(Z_w+1)\lt N_lN_w$$ $$2N_l+2N_w-4+(Z_l+1)(Z_w+1)\lt N_lN_w$$ $$(Z_l+1)(Z_w+1)\lt N_lN_w-2N_l-2N_w+4$$ $$(Z_l+1)(Z_w+1)\lt (N_l-2)(N_w-2)$$

In the specific case of the square (where the length equals the width) my method uses less base-2 rectangles than the op when the number ones in the binary representation of the length is at least four more than than the number of zeros. To get the maximum utility out of my method the inequality shouldn't only be applied to the entire length and width of the main square it should also be applied to components of the square. For example consider the square $1927×1927$. The binary representation of 1927 is 11110000111. There are three more ones than zeros in this number so my method would normally break even with the op, covering the square with 49 base-2 rectangles. There is a way to cover the square using less base-2 rectangles by spliting the square into four rectangles $1920×1920$, $1920×7$, $7×1920$, and $7×7$. Splitting this way doesn't change the net result of the op's method. The first three sub rectangles satisfies the inequality. If I use my method on the first three sub rectangles I use 13, 11, and 11 base-2 rectangles respectively. Using the op's method on the last sub rectangle then counting up all of the base-2 rectangles I can cover the $1927×1927$ square using 44 base-2 rectangles.(13+11+11+9) So if a combination of sub-strings in the binary value of the length and width satisfies the inequality like it did three times with the sub rectangles then my method will use less base-2 rectangles than the op's method. Finding the minimum number of base-2 rectangles for some squares will inevtably involve searching for the best way to split the square.

For large enough squares the worst digit combination where my method does no better than the op is a block of three ones and the rest are alternating zeros and ones. For example the square $\require{enclose}\enclose{horizontalstrike}{343×343}$, its binary representation is 101010111. This square requires 36 base-2 rectangles and is tied for most number of required base-2 rectangles amoung the nine digit squares. This means that a upper bound can be made for the minimum number of rectangles required. Let $\enclose{horizontalstrike}{d_l}$ be the number of digits in the binary representation of the length of the rectangle. ($\enclose{horizontalstrike}{d_l=N_l+Z_l}$) Let $\enclose{horizontalstrike}{d_w}$ be the number of digits in the binary representation of the width of the rectangle. ($\enclose{horizontalstrike}{d_w=N_w+Z_w}$) Then the upper bound is: $$\enclose{horizontalstrike}{\left(\left\lceil\frac{d_l}{2}\right\rceil+1\right)\left(\left\lceil\frac{d_w}{2}\right\rceil+1\right)}$$

I conjecture that the combination of my method and the op's method is the optimal way of minimizing the number of base-2 rectangles. The only way that someone might use be able to use less rectangles is to find a another way of spliting the square into sub-rectangles such that using the op's method on those sub-rectangles uses less base-2 rectangles than using my method and the op's method on the whole square.

Rob Pratt's(RP's) post shows that there is a third method for covering the $n×n$ square with less base-2 rectangles than my method or the op's method for some $n×n$ squares. In order to describe how many rectangles RP's method uses I will continue to use the the term $b$ from my method (where $b$ is the smallest number such that $b+n$ is a power of 2). I will also need a new sets of terms $c_k$ and $s_k$ where $k\in\Bbb{N}|1\le k\le f(b)$. $c_1$ is the value of left most ones digit of b in binary form. $c_2$ is the value of the second ones digit from the left of b in binary form. $c_3$ is the value of the third ones digit from the left of b in binary form. Etc. $s_v=\sum_{j=1}^vc_v$. For example if $n=23$ then $b=9$, $c_1=8$, $c_2=1$, $s_1=8$, $s_2=9$. RP's method uses $$2f\left(\frac{n+b}{2}\right)f\left(\frac{n-b}{2}\right)+f\left(\frac{n+b}{2}\right)f\left(\frac{n-b}{2}+s_k\right)+f\left(\frac{n-b}{2}\right)f\left(\frac{n+b}{2}-s_k\right)+f(b)f(b-s_k)$$

base-2 rectangles. Each $f(•)f(•)$ product contains the length and width of each of the sub-rectangles that covers the square inside the f function. RP's method has $k$ ways of covering the $n×n$ square one for each $s$ element. Obviously the particular $s_k$ element that uses the least number of base-2 rectangles according to the above formula is the one that is used for the minimum. A sufficient condition for when RP's method uses less base-2 rectangles than both my method and the op's method when the binary representation of $n$ has at least three more ones than zeros, the second digit to the left is a zero, and the spliting method that was mentioned for the $1927×1927$ square doesn't apply.

$\endgroup$
4
  • 1
    $\begingroup$ absolutely brilliant!! IMHO well worth the bounty. :) $\endgroup$
    – antkam
    Apr 11, 2019 at 2:02
  • $\begingroup$ What does your method obtain for $n\in\{23,30,31\}$? $\endgroup$
    – RobPratt
    Mar 5, 2020 at 22:36
  • $\begingroup$ @Rob_Pratt 16,13, and 17 base-2 rectangles respectively $\endgroup$
    – quantus14
    Mar 5, 2020 at 23:30
  • $\begingroup$ @RobPratt I realized that the way I explained it in my edited post it doesn't show how n=30 is 13 base-2 rectangles with my method. I will edit accordingly. $\endgroup$
    – quantus14
    Mar 5, 2020 at 23:37
3
+100
$\begingroup$

For fixed $n$, you can solve this problem via integer linear programming as follows. Let $R$ be the set of rectangles. For $i\in\{1,\dots,n\}, j\in\{1,\dots,n\}$, let $R_{i,j}\subset R$ be the subset of rectangles that contain cell $(i,j)$. Let binary decision variable $x_r$ indicate whether rectangle $r\in R$ is used. The problem is to minimize $\sum_r x_r$ subject to: \begin{align} \sum_{r \in R_{i,j}} x_r &= 1 &&\text{for $i\in\{1,\dots,n\}, j\in\{1,\dots,n\}$} \\ x_r &\in \{0,1\} &&\text{for $r \in R$} \end{align}

Here are several optimal values that differ from $f(n)^2$: \begin{matrix} n &15 &23 &30 &31 &46 &47 &55 &59 &60 &61 &62 &63\\ \hline f(n)^2 &16 &16 &16 &25 &16 &25 &25 &25 &16 &25 &25 &36\\ \text{optimal} &13 &15 &13 &17 &15 &19 &20 &20 &13 &20 &17 &21\\ \end{matrix}

For example, here is an optimal solution for $n=23$ with $15$ rectangles (shown here with hex values $0$ through $E$ for compactness): \begin{matrix} 0&0&0&0&0&0&0&0&A&A&A&A&8&B&B&B&B&B&B&B&B&9&9\\ 5&5&5&5&5&5&5&5&A&A&A&A&8&B&B&B&B&B&B&B&B&9&9\\ 5&5&5&5&5&5&5&5&A&A&A&A&8&B&B&B&B&B&B&B&B&9&9\\ 5&5&5&5&5&5&5&5&A&A&A&A&8&B&B&B&B&B&B&B&B&9&9\\ 5&5&5&5&5&5&5&5&A&A&A&A&8&B&B&B&B&B&B&B&B&9&9\\ 3&3&3&3&3&3&3&3&A&A&A&A&8&B&B&B&B&B&B&B&B&9&9\\ 3&3&3&3&3&3&3&3&A&A&A&A&8&B&B&B&B&B&B&B&B&9&9\\ C&E&E&E&E&D&D&7&A&A&A&A&8&B&B&B&B&B&B&B&B&9&9\\ C&E&E&E&E&D&D&7&A&A&A&A&8&B&B&B&B&B&B&B&B&9&9\\ C&E&E&E&E&D&D&7&A&A&A&A&8&B&B&B&B&B&B&B&B&9&9\\ C&E&E&E&E&D&D&7&A&A&A&A&8&B&B&B&B&B&B&B&B&9&9\\ C&E&E&E&E&D&D&7&A&A&A&A&8&B&B&B&B&B&B&B&B&9&9\\ C&E&E&E&E&D&D&7&A&A&A&A&8&B&B&B&B&B&B&B&B&9&9\\ C&E&E&E&E&D&D&7&A&A&A&A&8&B&B&B&B&B&B&B&B&9&9\\ C&E&E&E&E&D&D&7&A&A&A&A&8&B&B&B&B&B&B&B&B&9&9\\ C&E&E&E&E&D&D&1&A&A&A&A&8&B&B&B&B&B&B&B&B&9&9\\ C&E&E&E&E&D&D&6&6&6&6&6&6&6&6&6&6&6&6&6&6&6&6\\ C&E&E&E&E&D&D&6&6&6&6&6&6&6&6&6&6&6&6&6&6&6&6\\ C&E&E&E&E&D&D&6&6&6&6&6&6&6&6&6&6&6&6&6&6&6&6\\ C&E&E&E&E&D&D&6&6&6&6&6&6&6&6&6&6&6&6&6&6&6&6\\ C&E&E&E&E&D&D&4&4&4&4&4&4&4&4&4&4&4&4&4&4&4&4\\ C&E&E&E&E&D&D&4&4&4&4&4&4&4&4&4&4&4&4&4&4&4&4\\ C&E&E&E&E&D&D&2&2&2&2&2&2&2&2&2&2&2&2&2&2&2&2\\ \end{matrix}

$\endgroup$
2
  • $\begingroup$ I should have mentioned this earlier but good job finding this. As of when this comment being posted you are the only one who has helped me with this problem. If no one else posts am answer by the end of the bounty grace period you will receive the bounty. Also I have made a formula for your method in my most recent edit that I just made, you might want to take a look. $\endgroup$
    – quantus14
    Mar 8, 2020 at 23:13
  • $\begingroup$ Thanks. I added a few more values $< f(n)^2$ just now. $\endgroup$
    – RobPratt
    Mar 9, 2020 at 23:35
0
$\begingroup$

NOTE:This doesn't work, the induction hypothesis is too strong (and false).

Lets first consider a more general question, where we tile a rectangle $R$ by smaller rectangles, where all vertices are points in an (ambient) integer lattice.

We have a row of rectangles $T_i$ touching the bottom edge of $R$, and each of these has a top edge $e_i$. For each $T_i$ we define the number $\lambda(T_i)$ to be the minimal number of our tiling rectangles that intersect any column starting in $T_i$.

Our first claim is that for the total number of rectangles in $R$, denoted $r(R)$, we have $$\sum_i \lambda(T_i) \leq r(R)$$

Lets prove this by induction on the height of the rectangle $R$ (drawing a picture may help see whats happening). First, if the height is $1$, then we are done trivially.

So now for the inductive step, let $R_0$ have height $n$, and consider the edges $e_i$ that have minimal height, and define $a$ to be this height. This is to say, they border the $a$th row, if the first row is the bottom row of $R_0$. Say that we have $k$ minimal edges $e_i$ bordering this row.

We now consider the new rectangle $R_0'$ we obtain by chopping off the first $a$ rows of $R$. On one hand, this has strictly smaller height, so we have, by induction and our definition of $k$: $$\sum_i \lambda(T_i') \leq r(R_0)-k$$

But each rectangle on the bottom row of $R_0'$ is either one of the rectangles of $R_0$, chopped, but not removed, or a rectangle of $R_0$ lying above one of our minimal edges $e_i$.

Now note if our original $T_i$ is chopped but not removed, $\lambda(T_i)=\lambda(T_i')$, and if our original $T_j$ is removed (so top edge has minimal height), then $\lambda(T_j')=\lambda(T_j)-1$, where $T_j'$ is any of the rectangles lying directly over $T_j$. Thus, adding $k$ to both sides of our previous equality, we have:

$$\sum_i \lambda(T_i) \leq \sum_i \lambda(T_i')+k\leq r(R_0)$$

So we are done by induction.

So for your case, note that each column must have at least $f(n)$ rectangles in it, and note the bottom row has at least $f(n)$ rectangles. This follows since $f(n)$ is the minimal number of powers of two needed to express $n$. Thus, $f(n)^2\leq r(R)$ in your case.

$\endgroup$
3
  • $\begingroup$ I think your original claim is false.I don't know how to send a picture in comment but you can easily draw $3\times 4$ counter examples(two horizontal dominos and two vertical dominos in first two rows and two $1\times1$square and a domino on the third row).the problem is on your induction step the rectangles above two removed rectangle may not be distinict. $\endgroup$
    – ali
    Apr 5, 2019 at 9:41
  • $\begingroup$ your last statement have counter example too.if each row intersect k rectangle and each column intersect k rectangle doesn't mean we need $k^2$ rectangle. $\endgroup$
    – ali
    Apr 5, 2019 at 9:43
  • $\begingroup$ True, I'll leave this up in case someone can make this approach work. $\endgroup$
    – Chris H
    Apr 5, 2019 at 10:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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