0
$\begingroup$

Given a set of positive integers :

$ \\ D = \{ D_1, D_2, ..., D_n\}$

and a non-negative integer $P$, where $P$ is divisible by every element in $D$, then find a set of non-negative integers:

$C = \{ C_1, C_2,..., C_n\}$

such that

$S > P $

where
$S = \displaystyle \sum_{i = 1}^nC_iD_i$
and for all $i$ where $C_i > 0 $,

$\ S - D_i < P$

There can be multiple solutions, any solution can suffice.

For example, if

$D = \{2, 6, 9 \}$
$P = 18$

$ C $ can be:

$C = \{0, 2, 1 \}$

since $ S = 0*2 + 2*6 + 1*9 = 21 > 18 $
and $ 21 - 6 = 15 < 18 $ and $ 21 - 9 = 12 < 18 $

What can be some approaches to tackle this? For starters, is there a way to ensure that there even exists a solution? There can be examples where there is no solution.

$\endgroup$
3
  • $\begingroup$ What approaches have you considered? What progress have you made so far? $\endgroup$
    – D.W.
    Commented Feb 14, 2020 at 0:46
  • $\begingroup$ @D.W. I have tried approaching it by finding 2 integers Ci and Cj such that the condition is satisfied. The result gives that if there are Di and Dj such that Di < Dj and 2*Di > Dj, then we can have Ci = P/Di - 1 and Cj = 1 rest all zero. $\endgroup$ Commented Feb 14, 2020 at 14:58
  • 1
    $\begingroup$ Thanks for the edits, I find that a lot clearer. I suggest you start by trying to solve the special case $n=2$ first. Can you do that? What's the context where you encountered this? Can you credit the source where you originally saw it? $\endgroup$
    – D.W.
    Commented Feb 14, 2020 at 15:31

1 Answer 1

1
$\begingroup$

If all of $D$ divide $P$, then $P$ is also multiple of $\gcd(D)$. Any sum like $S$ is a multiple of $\gcd(D)$ too, so you can divide everything by $\gcd(D)$ and consider just the case where the $D_i$ are relatively prime. For definiteness, take $D$ sorted in increasing order. In that case you have just:

$\begin{equation*} P = c \cdot \prod_{1 \le k \le n} D_k \end{equation*}$

For the Frobenius problem sums like $S$ with non-negative $C_i$ can represent all numbers greater than a function $g(D)$, and it can be shown that $g(D) < D_n^2$ (computing the exact value of $g(D)$ is NP-complete). So, if $P > D_n^2$ (the other $D_k$ would have to be small indeed for this to be false), any number $S \ge P$ can be represented, and also any number $S - D_i$, pick say $S = P + 1$ to satisfy your condition.

To get a set of $C_i$, you can now use the greedy algorithm: Take $C_n = \lfloor S / D_n \rfloor$ (as large as possible), $S \leftarrow S - C_n D_n$, and repeat for the next largest.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.