What is the trick of "adding a huge number" for in the reduction from 3-Partition?

Question

Problem: To prove the $\textsf{NP-Completeness}$ of the problem of "Packing Squares (with different side length) into A Rectangle", $\textsf{3-Partition}$ is reduced to it, as shown in the following figure.

In the $\textsf{3-Partition}$ instance, there are $n$ elements $(a_1, \cdots, a_i, \cdots, a_n)$. The target sum $t$ is $t = \frac{\sum a_i}{n/3}$.

In the reduction, $B$ is a huge (constant) number and each $a_i$ is represented by a $(B + a_i) \times (B + a_i)$ square. The blank in the rectangle will be filled by unit ($1 \times 1$) squares.

---

Questions: I don't quite understand the trick of "adding a huge number $B$" in the reduction. I guess it is used to force that any packing scheme will give a solution to $\textsf{3-Partition}$. But how?

Question 1: What is the trick of "adding a huge number" for in the reduction from $\textsf{3-Partition}$? Specifically, why does this reduction work? Why is this trick necessary, i.e., why wouldn't the reduction work if we left out $B$ (set $B=0$)?

I tried to identify the flaw of the proof of "any packing gives a 3-partition" but could not get the key point.

Actually I have also seen other reductions from $\textsf{3-Partition}$ that also use this trick. So,

Question 2: What is the general purpose of this trick of "adding a huge number" in the reductions from $\textsf{3-Partition}$ (if there is)?

---

Note: This problem is from the video lecture (from 01:15:15) by Prof. Erik Demaine. I should have first checked the original paper "Packing squares into a square". However, it is not accessible to me on the Internet. If you have a copy and would like to share, you can find my mailbox in my profile. Thanks in advance.

Answer 1

The large $B$ is here to ensure that the squares follow the pattern shown in the figure.

In the part "there exists a packing $\Rightarrow$ there exists a 3-partition". You need to exhibit tripples of integers with sum $=t$. This is easy if the coding squares in the packing are arranged 3-by-3 as in the picture, but how do you know this is the case? For instance, with very slightly smaller blue squares, you could have two small squares side by side in the same column, and then you'd be in trouble.

One way to use the trick of the $B$ constant is to say that it is not possible to have any horizontal line crossing strictly more than $n/3$ squares (such a line has length $(B+t)\frac n3$, a square has size at least $B$, and $B > t\frac n3$). So each horizontal line meets a 1st square, a 2nd square, etc., and then you can show (again using the large $B$), that the $i$th squares of each lines must all meet in the same column. Once you've got this, then you get a 3-partition.

About Question 2, it is obviously hard to give a formal answer, but the general pattern is the following:with 3-partition, you need to introduce some kind of slackness to allow that any integer in an interval $[min,max]$ can be somehow encoded and embeded in a slot (which must then correspond to the maximum possible size). But then a common issue is having two integers fitting in the same slot, or more generally other overlapping issues (as with the squares here). This is solved by making sure that the $min$ is large enough compared to the slot size (we often need $min > max/2$, or $min > max*(n-1)/(n)$ here): this is easily achieved with an additive constant $B$.

Edit Sample instance where $B$ is necessary: Let the instance of 3-partition be $(10,7,2,10,9,2)$ with $t=20$. This is a no-instance. However, with $B=0$, you have a valid packing of the $40\times 20$ rectangle: use a first column with four squares $(10,7,2,2)$, the last two being side-by-side, and a second column with only $(10,9)$. This is not possible with, say, $B=100$, and a $240 \times 320$ rectangle.