Partitioning $[1,v-1]$ into sets of size three such that the sum of each set is $3v/2$

54 Views Asked by At

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.

2

There are 2 best solutions below

2
On BEST ANSWER

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}.

8
On

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.