Take the 2-minute tour ×


I'm not quite sure what title to give to this question or what tags to use, because this isn't really my area of expertise and I'm unfamiliar with the terminology. It is a problem that came up while trying to write a program to enumerate some graphs, however there is no graph theory left in this problem.

Let me first start by giving definitions for the different components. I have a set $C$ and two functions: $s:C\rightarrow \mathbb{N}$ and $r:C\rightarrow \mathbb{N}$. The values for these functions are completely known. It is also true that $\forall c \in C: r(c)=s(c) \vee r(c)=\frac{s(c)}{2}$. I don't know whether this will make a difference for the solution of my problem, but it might be relevant information.

I am now interested in finding all possible functions $m:C\rightarrow \mathbb{N}$ that satisfy the following conditions:

  • $\sum_{c\in C}\frac{s(c)}{m(c)}=\sum_{c \in C}\frac{s(c)}{4}$
  • $\forall c \in C: r(c) \mid m(c)$

I really need an algorithm to find all possible solution, but of course I'm also interested in any theoretical results that could help me find such an algorithm. As I said, I'm not really at home in this type of problems, so I have no idea what to look for and where to start. The first conditions makes it impossible to have an infinite number of solutions, but in some cases I have some better upper bounds and lower bounds available for the value of the function $m$ in certain points. It would be nice if this could be taken into account, but I think it would not be the bottle-neck if I just filtered the solutions to take these bounds into account.

Any help is greatly appreciated. And of course I will try my best to clarify anything in my explanation that isn't clear.

Edit: Let me first say that $C$ will always be finite.

A small example might also be more clarifying. Suppose we have $C=\{1,2\}$, the function $s:C\rightarrow\mathbb{N};c\mapsto 2$ and the function $r:C\rightarrow\mathbb{N};c\mapsto 1$.

We then have three possible solutions for $m$:

  • $m(1)=3$, $m(2)=6$
  • $m(1)=4$, $m(2)=4$
  • $m(1)=6$, $m(2)=3$
share|improve this question
Is $C$ a finite set? I.e., can one loop over all elements of $C$ in an algorithm? –  Jesko Hüttenhain Jul 14 '11 at 8:35
Yes, $C$ is most definitely finite and in most cases really small (at least size 2 but only in rare cases larger than 30). I'll have a look at your answer, Thanks already for answering. –  nvcleemp Jul 14 '11 at 9:25
add comment

1 Answer

up vote 2 down vote accepted

I will assume that $C$ is finite for my answer.

Let $n,d:C\to\mathbb{N}$ such that $n\equiv\left.m/r\right.$ and $r\equiv\left.s/d\right.$. In other words, $\mathrm{im}(d)\subseteq\{1,2\}$. Let $C_1:=d^{-1}(1)$ and $C_2:=C\setminus C_1 = d^{-1}(2)$. Now, we want to find a function $n$ such that

$R := \displaystyle \sum_{c\in C} \frac{d(c)}{n(c)} = \sum_{c\in C} \frac{s(c)\cdot d(c)}{s(c)\cdot n(c)} = \sum_{c\in C} \frac{s(c)}{r(c)\cdot n(c)}= \sum_{c\in C} \frac{s(c)}{m(c)} = \sum_{c\in C} \frac{s(c)}{4} =: S$

Claim. This problem has a solution if and only if $2\le S\le|C_1|+2|C_2|$.
Proof. We consider $S\in\mathbb{Q}$ and perform induction on $r$, where $C=\{c_1,\ldots,c_r\}$. In the case $r=1$, the statement is clear. Assume now that $S>|C_1|+2|C_2|$. Then, no matter how we choose $n(c_r)$, by induction we can not find a valid solution for $S'=S-d(c_r)/n(c_r)$ on $C'=\{c_1,\ldots,c_{r-1}\}$.

In the case where $S\le|C_1|+2|C_2|$ however, a solution can be calculated by setting $n\equiv 1$, so $R=|C_1|+2|C_2|$. We then have to decrease $R$ until it achieves the desired value.

For $d=1,2$ we can decrease $R$ by $dr-1$ in the following way: Pick $\{c_1,\ldots,c_r\}\subseteq C_d$ and set $n(c_i):=dr$ for all $i$. The following python code

def n(c):
    D = 2*c[2] + c[1] - c[0]
    for d in (1,2):
        j,r = 0,c[d]
        ctr = c[d]
        while r > 0 and D != 0:
            if d*r-1 <= D:
                D -= d*r-1
                n[d-1][j:j+r] = [d*r]*r
                j += r
                ctr -= r
                r = ctr
                r -= 1
    print n[0]+n[1]

expects input of the form $(S,|C_1|,|C_2|)$ and returns the function $n$, with my notation. In your example above, $S=1$, $|C_1|=0$ and $|C_2|=2$, the output is

>>> n((1,0,2))
[4, 4]

which is the second of your solutions. I think this should work.

share|improve this answer
I might be missing something obvious, but what exactly do you mean by $|S|$? It is not the absolute value of the rational number $S$, right? –  nvcleemp Jul 14 '11 at 9:50
Err, those are really not supposed to be there. It should be just $S$, I will edit it. –  Jesko Hüttenhain Jul 14 '11 at 11:53
Then there seems to be a problem with the condition that $|C|\leq S$. As can be seen in the example I added in my original question this is not a necessary condition. But it doesn't seem like you really need this. –  nvcleemp Jul 14 '11 at 12:22
Indeed, let me fix that up. –  Jesko Hüttenhain Jul 14 '11 at 13:56
I was working under the assumption that $S\in\mathbb{N}\setminus\{1\}$. You allow $S\in\mathbb{N}\cup\left\{\frac{1}{2},\frac{1}{4}\right\}$, but these additional three special cases can be easily handled by multiplying $n$ with $2$, $4$ or $8$. –  Jesko Hüttenhain Jul 16 '11 at 22:19
show 2 more comments

Your Answer


