1
$\begingroup$

Suppose that $v \equiv 4\;(\bmod 12)$. In general, is it possible to partition the integer interval $[1,v-1]$ into integer partitions of $3v/2$ with three distinct parts (with each part in $[1,v-1]$)? In other words, is it possible in general to partition $[1,v-1]$ into sets of size three such that the sum of each set is $3v/2$?

An exhaustive search for $v = 16$ gives $\{6,8,10\}, \{1,11,12\}, \{2,9,13\}, \{3,7,14\}, \{4,5,15\}$ as a valid partition.

$\endgroup$
2
$\begingroup$

What you're asking about is actually true more generally for all $v \equiv 4 \pmod 6$, as I'll demonstrate below, including with an example.

First, as already suggested in the comments to the answer by Ross Millikan, you can more easily see what's being requested by reducing each of the values in $[1, v - 1]$ by $\frac{v}{2}$ to get a set $[\frac{2 - v}{2}, \frac{v - 2}{2}]$ where you want the sum of the $3$ values to be $0$. This is because if $a,b,c$ are values from the original set where $a + b + c = \frac{3v}{2}$, then $\left(a - \frac{v}{2}\right) + \left(b - \frac{v}{2}\right) + \left(c - \frac{v}{2}\right) = 0$.

The partition of the new set can be done in $2$ stages. First, use

$$\{\frac{2 - v}{2} + i, i + 1, \frac{v - 4}{2} - 2i\} \tag{1}\label{eq1}$$

for $i \in \left[0, \frac{v-10}{6}\right]$. For the set $\left[1,v-1\right]$, add $\frac{v}{2}$ to each set element in \eqref{eq1} to get $\{1 + i, \frac{v}{2} + i + 1, v - 2 - 2i\}$.

Next, use

$$\{\frac{1 - v}{3} + i, \frac{4 - v}{6} + i, \frac{v - 2}{2} - 2i\} \tag{2}\label{eq2}$$

for $i \in \left[0, \frac{v - 4}{6}\right]$. For the set $\left[1,v-1\right]$, \eqref{eq2} becomes $\{\frac{v + 2}{6} + i, \frac{v + 2}{3} + i, v - 1 - 2i\}$.

You can confirm that the $3$ elements in both \eqref{eq1} and \eqref{eq2} add up to $0$. Also, all values in $\left[\frac{2-v}{2},\frac{v-2}{2}\right]$ are represented exactly one time each. In particular, the values $\left[\frac{2-v}{2},\frac{-2-v}{3}\right]$ are the first elements in \eqref{eq1}. The values $\left[\frac{1-v}{3},\frac{-2-v}{6}\right]$ are the first elements in \eqref{eq2}. The values $\left[\frac{4-v}{6},0\right]$are the second elements in \eqref{eq2}. The values $\left[1,\frac{v-4}{6}\right]$ are the second elements in \eqref{eq1}. Every other value from $\frac{v+2}{6}$ to $\frac{v-2}{2}$ are the third elements in \eqref{eq2}. Finally, every other value from $\frac{v+8}{6}$ to $\frac{v-4}{2}$ are the third elements in \eqref{eq1}.

For $v = 34$, this gives the sets $\{-16,1,15\}$, $\{-15,2,13\}$, $\{-14,3,11\}$, $\{-13,4,9\}$, $\{-12,5,7\}$ using \eqref{eq1}, and $\{-11,-5,16\}$, $\{-10,-4,14\}$, $\{-9,-3,12\}$, $\{-8,-2,10\}$, $\{-7,-1,8\}$, $\{-6,0,6\}$ using \eqref{eq2}.

Consider $v = 40$ which matches your more specific requirement. This gives the sets $\{-19,1,18\}$, $\{-18,2,16\}$, $\{-17,3,14\}$, $\{-16,4,12\}$, $\{-15,5,10\}$, $\{-14,6,8\}$ using \eqref{eq1}, and $\{-13,-6,19\}$, $\{-12,-5,17\}$, $\{-11,-4,15\}$, $\{-10,-3,13\}$, $\{-9,-2,11\}$, $\{-8,-1,9\}$, $\{-7,0,7\}$ using \eqref{eq2}.

$\endgroup$
  • $\begingroup$ Looks good, thanks! Also to Ross Millikan for his comments. $\endgroup$ – user95224 Apr 18 at 6:24
  • $\begingroup$ @user95224 You are welcome. If you're interested, I'm fairly certain there's a pattern in my solution which you can generalize to handle other cases. $\endgroup$ – John Omielan Apr 18 at 6:29
1
$\begingroup$

For $v=4$ you only need one set and $\{1,2,3\}$ does the trick.

For $v=16$ you need five sets summing to $24$. $\{2,7,15\},\{1,9,14\},\{4,8,12\},\{3,10,11\},\{5,6,13\}$ works. I found this by splitting the numbers into thirds, small with average $3$, middle with average $8$, and large with average $13$. Each set has one number from each third. The numbers within a third were considered to range from $-2$ to $+2$ as the offset from the middle. I needed five groups that each summed to $0$ and had three of each offset between them. $-2+1+1$ and $+2-1-1$ suggested themselves along with $\pm2,0$ (twice) and $\pm1,0$. A little playing.

For $v=28$ we can again break the numbers into small, medium, and large. The offsets now range from $-4$ to $+4$ and we need nine sets. I think the fact that the range is divisible by $3$ makes it easy. Make three sets with offsets $+4,-1,-3$, rotating, three sets with offsets $-4,+1,+3$, rotating, and three sets with offsets $+2,0,-2$ and we are done. As the central values are $5,14,23$ the first set is $\{9,13,20\}$

I haven't found a general approach.

$\endgroup$
  • $\begingroup$ I think I may be misunderstanding your algorithm. Since $(v-1) + (v-2) = 2v-3 > 3v/2$ for any $v>6$, at the start we can only take one number off the top, meaning we are left with many options as to how to partition the remaining sum into two parts. $\endgroup$ – user95224 Apr 17 at 22:42
  • $\begingroup$ I read it as three sets, not sets of size three. I'll rework $\endgroup$ – Ross Millikan Apr 17 at 22:45
  • 1
    $\begingroup$ This is an interesting approach. So for $v = 40$, you essentially have to partition $\pm 1, \pm 2, \dots, \pm 6$ into sets of size three summing to zero. I wonder if this can be done in general $\endgroup$ – user95224 Apr 18 at 0:08
  • 1
    $\begingroup$ But that is true even for $v=28$. $4$ is large enough it needs two negatives, which it gets. But you are right it may get hard. $\endgroup$ – Ross Millikan Apr 18 at 0:14
  • 1
    $\begingroup$ That works well. Now just add $\{0,0,0\}$ and you are done. Each of your triplets gives three sets and all zeros adds the last. $\endgroup$ – Ross Millikan Apr 18 at 0:46

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.