3
$\begingroup$

I am currently doing research in Combinatorial Geometry and I have been able to reduce a quite complicated problem relating to extending the Newton-Gregory problem of kissing spheres to a simple number theory problem and then checking every case to see that a conjecture of mine holds.

In any case, for background reasons which are not necessary for me to get into, I need to determine the explicit sets of 4 positive integers which when summed together give 12. Order does not matter as I will need to permute the set of 4 positive integers in each case to satisfy a different case for verifying my conjecture by exhaustion. So, I am not interested in some abstract "there are this many ways", I am actually interested in generating the explicit sets of numbers. I have been able to come up with the following so far:

$$\{1,1,5,5\},\{2,2,4,4\},\{3,3,3,3\},\{2,2,3,5\},\{1,2,4,5\},\{1,3,3,5\},\{1,3,4,4\},\{2,3,3,4\}$$

Any ideas for how to solve this? I can clarify any ambiguities as needed!

EDIT: I forgot to mention the following important detail:

I only want to consider integers from the set $\{2,3,4,5\}$ in summing to 12, since these correspond to the degree of a vertex and I have proved that for my particular problem that all vertices have either degree 2, 3, 4, or 5.

  • 0
    you may be interested in http://www.site.uottawa.ca/~ivan/F49-int-part.pdf2012-06-04
  • 0
    If you will be permuting the four entries anyway, then you actually want to generate all possibilities *with order* (so that you want to also generate 1,5,1,5 and 5,5,1,1 as distinct from 1,1,5,5). In that case, the [stars and bars](http://en.wikipedia.org/wiki/Stars_and_bars_%28combinatorics%29) method will give you not only the formula, but a method for producing the actual tuples.2012-06-04
  • 0
    @ArturoMagidin: I forgot to mention a very important detail which is that I only want to consider summing numbers from the set $\{2,3,4,5\}$. Does this change the stars and bars method?2012-06-04
  • 0
    @SamuelReid: Yes. But you can simply generate all the possibilities and discard any with too-large entries.2012-06-04

2 Answers 2

2

You want $a+b+c+d = 12$ where $2 \leq a \leq b \leq c \leq d \leq 5$. Let $a_1 = a-2$, $b_1 = b-2$, $c_1 = c-2$ and $d_1 = d-2$. This gives us that $$a_1 + b_1 + c_1 + d_1 = 4$$ where $0 \leq a_1 \leq b_1 \leq c_1 \leq d_1 \leq 3$.

Let $b_1 = a_1 + b_2$, $c_1 = b_1 + c_2$ and $d_1 = c_1 + d_2$. Then we need $$a_1 + (a_1 + b_2) + (a_1 + b_2 + c_2) + (a_1 + b_2 + c_2 + d_2) = 4$$ i.e. $$4a_1 + 3b_2 + 2 c_2 + d_2 = 4$$ where $0 \leq a_1,b_2,c_2,d_2$.

Note that $a = a_1 +2$, $b = a_1 + b_2 + 2$, $c = a_1 + b_2 + c_2 + 2$ and $d = a_1 + b_2 + c_2 + d_2 + 2$

Now all we want is $$4a_1 + 3b_2 + 2 c_2 + d_2 = 4$$ such that $0 \leq a_1 \leq b_1 \leq c_1 \leq d_1 \leq 3$.

This means $a_1 \leq 1$.

If $a_1 = 1$, then $b_2 = c_2 = d_2 = 0$. Hence the solution is $$(a,b,c,d) = (3,3,3,3)$$

If $a_1 = 0$, then $$3b_2 + 2 c_2 + d_2 = 4$$ where $0 \leq b_2,c_2,d_2$.

This means $b_2 \leq 1$.

If $b_2 = 1$, then $c_2 = 0$ and $d_2 = 1$. Hence, the solution is $$(a,b,c,d) = (2,3,3,4)$$

If $b_2 = 0$, then $$2c_2 + d_2 = 4$$ where $0 \leq c_2,d_2$. This gives us $(c_2,d_2) = (2,0)$, $(c_2,d_2) = (1,2)$ and $(c_2,d_2) = (0,4)$. But $d_1 \leq 3$. Hence, the last solution is not possible.

Hence, these now give the solutions $$(a,b,c,d) = (2,2,4,4)$$ $$(a,b,c,d) = (2,2,3,5)$$

Hence, the only four possible solutions for $a+b+c+d = 12$, with the constraint that $a,b,c,d \in \{2,3,4,5\}$ are

$$(a,b,c,d) = (3,3,3,3)$$ $$(a,b,c,d) = (2,3,3,4)$$ $$(a,b,c,d) = (2,2,4,4)$$ $$(a,b,c,d) = (2,2,3,5)$$

  • 0
    Except... you're not supposed to get any 6's, and you are missing things like (1,1,5,5)...2012-06-04
  • 0
    @ArturoMagidin I didn't respect the upper bound. Now I have changed it. $(1,1,5,5)$ is not acceptable. (The OP wants the numbers to be between $2$ and $5$).2012-06-04
  • 0
    @Mavis: Oh; since *he* listed (1,1,5,5) among his answers, I missed that.2012-06-04
  • 0
    @ArturoMagidin: I really confused myself while I was answering this question and it turns out that the question I asked is the problem I actually need to answer. In any case, with Marvis' response I was able to figure out the question which I did need to answer which I had not asked here. Sorry for the confusion, I appreciate the help.2012-06-04
1

Since order does not matter, assume $a \geq b \geq c \geq d \geq 1$ and $a + b + c + d = 12$. All you have to do is a case-by-case exhaustion of what possible values you can have. For example, the largest possible value of $a$ is $9$, in which case $b = c = d = 1$. If $a = 8 \dots$