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

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.