Question

Hi

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$

Answer 1

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):
    n=([1]*c[1],[1]*c[2])
    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
            else:
                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.