0
$\begingroup$

I have the following definition of the 3-PARTITION problem taken from this paper: https://www.sciencedirect.com/science/article/pii/0166218X93900853

Given $3m$ positive integers $a_1, a_2,...,a_{3m}$ and a positive integral bound $B$, the integers $a_i, i = 1, \dots , 3m$ satisfy the the conditions:

$$\frac{B}{4} < a_i < \frac{B}{2}$$

and

$$\sum\limits_{i=1}^{3m}a_i = mB$$

Can $I = \{1,2,\dots,3m\}$ be partitioned into $m$ disjoint sets $I_1,I_2,\dots,I_m$ such that for $j, \dots, m$.

$$\sum_{i \in I_j} a_i = B$$

So this all makes sense- basic 3 partition problem. However, the next line says this:

"Notice that the conditions $\frac{B}{4} < a_i < \frac{B}{2}$ imply that every set $I_j$ with $\sum_{i\in I_J}a_i = B$ must contain exactly three elements."

I must be missing something because I do not understand how this implies that every set $I_j$ will contain exactly 3 elements?

$\endgroup$

1 Answer 1

1
$\begingroup$

If $I_j$ contains two or fewer elements, then $\sum_{i \in I_j} a_i<2\dfrac{B}{2}=B$. If $I_j$ contains four or more elements, then $\sum_{i \in I_j} a_i>4\dfrac{B}{4}=B$. So in neither case can $\sum_{i \in I_j}$ be equal to $B$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .