Find minimum $x+y+z$ given $3x=4y=7z$ and $x, y, z \in \mathbb N^+$

Question

Given that $x, y, z$ are positive integers and that $$3x=4y=7z$$ find the minimum value of $x+y+z$. The options are:

A) 33

B) 40

C) 49

D) 61

E) 84

My attempt:

$y=\frac{3}{4}x, z=\frac{3}{7}x$.

Substituting these values into $x+y+z$, I get $\frac{117}{28}x$. I have no idea how to continue. $x$ in this case would have to be 28, meaning that the sum is $117$, which is not one of the options

Answer 1

Turns out you made a mistake.
$x+y+z=x+\frac 34x +\frac 37x=\frac {61}{28}x$.
Substituting $x=28$ gives us $\frac {61}{28}*28= 61$.
Option $D$ $(61)$ is correct.

---

You could do this in another way:
$LCM (3, 4, 7)= 3*4*7 = 84$
$\therefore 3*28=4*21=7*12$
So, Let $f(x)=x+y+z$
$f_{min}(x)= 28+21+12$
$\therefore f_{min}(x)= 61$.

Both methods are valid. Use whichever you find easier to remember.

Answer 2

This is a classical problem from integer programming. There are exact algorithmic solutions available (although they are slow, as it is known that this a NP-hard problem). You can look for "branch and bound" or "branch and cut" or eventually total unimodularity. It basically works by a cleaver extension of the classicalm simplex algorithm in ordinary linear programming.

Answer 3

You can think of the smallest value that $3x$, $4y$, and $7z$ can be as the smallest multiple of three that is also a multiple of 4 and 7, or as the $gcm(3,4,7)$, which equals $84$. So if the minimum value of $3x$ is $84$, the minimum value of $x$ is $28$. Using the same method you find that $y$ equals $21$ and that $z$ equals $12$therefore the minimum value of $x+y+z$ is $28+21+12$, which equals $61$.