solving a Diophantine like equation

53 Views Asked by At

In my project, I modeled my problem to a mathematical equation like below

AX + BY + CZ + DK = 160

X, Y, Z, K ∈ [8, 40, 48, 80, 88, 120]

A, B, C, D are coefficients

The goal is to find the combination of (X, Y, Z, K) with their corresponding coefficient values. Is there any way to solve this problem ?

----------edit----------

All coefficients A, B, C, D > 0. The goal is to find X an A, Y and B, Z and C, K and D. The difference is that X, Y, Z, K are from the set [8, 40, 48, 80, 88, 120], and the A, B, C, D can be any value greater than zero.

1

There are 1 best solutions below

8
On BEST ANSWER

(form of the problem changed so I'm editing this)

Since the coefficients can repeat, we're actually solving the problem $$8a+40b+48c+80d+88e+120f=160$$ where each of $a,\ldots,f$ is greater than or equal to zero. Since $8+40+48+80>160$, at most three of the variables will be non-zero.

We also need to be able to write four non-zero terms, so $a+b+c+d+e+f\ge 4$.

A helpful first step is to divide by $8$, giving

$$a+5b+6c+10d+11e+15f=20$$

Two observations: we're really looking at $$5b+6c+10d+11e+15f\le 20$$ since $a$ can be any non-negative integer.

Secondly, at most one of $\{d,e,f\}$ is greater than zero (and none of them can be greater than $1$).

These two points reduce the problem to a manageable one; there are essentially four cases corresponding to $$(d,e,f) \in \{(0,0,0),(0,0,1),(0,1,0),(1,0,0)\}$$

These can either be done by hand or coded (I found $18$ solutions to this).