Diophantine equation with three variables

Question

The question is:

Nadir Airways offers three types of tickets on their Boston-New York flights. First-class tickets are \$140, second-class tickets are \$110, and stand-by tickets are \$78. If 69 passengers pay a total of $6548 for their tickets on a particular flight, how many of each type of ticket were sold?

Now I set up my equation as

$140x+110y+78z=6548$

But I'm confused how to go from here. I know I need to find the GCD in order to evaluate that the equation has a solution and then set up my formulas for $x=x_{0}+\frac{b}{d}(n)$ and $y=y_{0}-\frac{a}{d}(n)$

Ive solved Diophantine equations before but only in the form $ax+by=c$. How do I continue from here? I'm not interested in the solution, I can do that by myself, but I would like to know the process from solving these types of Diophantine equations.

Answer 1

Combining the comments:

$140x+110y+78z=6548$

and

$x + y + z = 69$

$\implies 78x + 78y + 78z = 69*78 = 5382$

$\implies 62x + 32y = 1166 \implies 31x + 16y = 69*78 = 583$

And we can quickly deduce that $x = 9, y = 19, z = 41$ (by simple inspection in my case - using that we only have integer values for $x,y,z$.

Answer 2

If the $\gcd$ of the ticket prices does not divide the total revenue, then you are correct that there will be no integer solution. However you are not immediately guaranteed a solution if the $\gcd$ does divide the revenue, because we are constrained to non-negative numbers of tickets. So we could potentially run into a Frobenius-coin-type failure.

Here the total number of tickets reduces this to a simple "two-coin" problem:

\begin{align} &&140x+110y+78z &= 6548\\ \text{divide by }\gcd(x,y,z)=2&& 70x+55y+39z &= 3274\\ &&x+y+z &= 69\\ \text{multiply by }39 && 39x+39y+39z &= 2691\\ \text{subtract eqns} && 31x+16y &= 583\\ \bmod 16 && 31x\equiv 15x \equiv -1x&\equiv 583\equiv 7\\ \bmod 16 && x&\equiv -7\equiv 9\\ \text{test }x=25 && 31\cdot25 &= 775>583 \\ \text{thus }x=9 && 31\cdot 9 +16y&= 583 \\ && y= (583-279)/16 &= 19\\ && z= 69-(19+9) &= 41\\ \end{align}

In the reduced equation $31x+16y = 583$, since $583>(31{-}1)\cdot (16{-}1)$ the coin problem issue could not apply - the total is big enough to guarantee a solution.