3
$\begingroup$

Apple cost 97 dollars. Orange cost 56 and lemon cost 3. The total amount spent is 16047 dollars and total fruits bought is 240 and each one is bought atleast one. Calculate how many of each have been bought?

I tried to make these equations: x+ y+ z=240 , 97x+56y+ 3z=16047 but I can't proceed further.

$\endgroup$
18
  • $\begingroup$ one needs at least three independent equations to solve it. How is this possible to solve? $\endgroup$
    – Babai
    Jul 23, 2014 at 19:07
  • 2
    $\begingroup$ @Susobhan, the OP is presumably looking for positive integer solutions. It's possible there's more than one, but clearly at most finitely many. $\endgroup$ Jul 23, 2014 at 19:10
  • 3
    $\begingroup$ Also, sort of off-topic, but those are some very expensive fruits. $\endgroup$ Jul 23, 2014 at 19:13
  • 2
    $\begingroup$ @Susobhan, the exhaustive approach is one way to go about solving, but Dave is presumably looking for something more elegant. Unfortunately, I don't know enough about solving Diophantine equations to be of much more help here. :/ $\endgroup$ Jul 23, 2014 at 19:15
  • 2
    $\begingroup$ @DivergentQueries, well the exhaustive-search approach mentioned by Susobhan is arguably more elementary, in that it's clear how and why it works. (If I were going to write a quick and dirty computer program to solve just this one problem and no other, I would loop through the values of $15327-94x$, looking for ones divisible by $53$ rather than trying to implement the Euclidean Algorithm.) What I was really asking is how much explanation the OP wants or needs. $\endgroup$ Jul 23, 2014 at 20:21

3 Answers 3

1
$\begingroup$

I was able to use this answer to a similar problem to solve your problem in a methodical non-trial-and-error way.

$$\begin{align} x + y + z &= 240 \\ 97x + 56y + 3z &= 16047 \end{align}$$

Combine these two equations to eliminate $x$. Rewrite as a congruence. Subtract the largest multiple of the modulus to simplify the congruence. Rearrange the congruence.

$$\begin{align} 41y + 94z & = 7233 \\ 7233 - 94z & \cong 0 mod 41 \\ 17 - 94z & \cong 0 mod 41 \\ 94z & \cong 17 mod 41 \end{align}$$

Now we start using the repetitive technique in the linked answer.

Rewrite the congruence as an equation with an integer solution. Introduce variables as needed; these are denoted by capital letters. Keep simplifying and rewriting until the fractions are gone.

$$\begin{align} 94z & = 41J + 17 \\ J & = \frac{94z - 17}{41} = 2z + \frac{12z - 17}{41} \\ \text{Let } K & = \frac{12z - 17}{41} \\ \text{Then } z & = \frac{41K + 17}{12} = 3K + \frac{5K + 17}{12} \\ \text{Let } L & = \frac{5K + 17}{12} \\ \text{Then } K & = \frac{12L - 17}{5} = 2L + \frac{2L - 17}{5} \\ \text{Let } M & = \frac{2L - 17}{5} \\ \text{Then } L & = \frac{5M + 17}{2} = 2M + \frac{M + 17}{2} \\ \text{Let } N & = \frac{M + 17}{2} \\ \text{Then } M & = 2N - 17 \end{align}$$

$J$, $K$, $L$, $M$, $N$ all $\in \mathbb N$

Now start plugging back in from bottom up:

$$\begin{align} L & = 2M + \frac{M + 17}{2} \\ & = 2(2N - 17) + \frac{2N - 17 + 17}{2} \\ & = 5N - 34 \\ \\ K & = 2L + \frac{2L - 17}{5} \\ & = 2(5N - 34) + \frac{2(5N - 34) - 17}{5} \\ & = 12N - 85 \\ \\ z & = 3K + \frac{5K + 17}{12} \\ & = 3(12N - 85) + \frac{5(12N - 85) + 17}{12} \\ & = 41N - 289 \end{align}$$

We are given that $x$, $y$, $z$ all $\gt 0$, so $41N \gt 289$, so $N \ge 8$. Pick $N = 8$ because it's the smallest. Then:

$$\begin{align} N & = 8 \\ \\ z & = 41N - 289 \\ & = 39 \\ \\ y & = \frac{7233 - 94z}{41} \\ & = \frac{7233 - 94(39)}{41} \\ & = 87 \\ \\ x & = 240 - y - z \\ & = 240 - 87 - 39 \\ & = 114 \end{align}$$

Final solution:$$\require\enclose \enclose{box}{ \begin{align} x & = 114 \\ y & = 87 \\ z & = 39 \end{align}}$$

Checking:$$\begin{align} 97x + 56y + 3z & = 97(114) + 56(87) + 3(39) \\ & = 16047 \end{align}$$

If we try $N \ge 9$, we have: $$\begin{align} N & \ge 9 \\ z & = 41N - 289 \\ & \ge 41(9) - 289 \\ & \ge 80 \\ y & = \frac{7233 - 94z}{41} \\ & \le \frac{7233 - 94(80)}{41} \\ & \le -7 \end{align}$$

So the solution above is the only one.

$\endgroup$
0
$\begingroup$

From a purely algebraic point of view (forgive me but this is the only way I can think in mathematics), using the two equations you wrote, you could eliminate $x$ and $y$ as a function of $z$. This leads to $$x=\frac{2607+53 z}{41} $$ $$y=\frac{7233-94 z}{41} $$ and you need to find the integer values of $z$ which make $x$ and $y$ integers, greater or equal to $1$. The equation giving $y$ restricts the domain to $1 \le z \le 76$.

One thing you can do, even if not elegant, is to minimize $$\Phi(z)=(x-\lfloor x\rfloor )^2+(y-\lfloor y\rfloor )^2$$ or to solve $$\Psi(z)=(x-\lfloor x\rfloor )+(y-\lfloor y\rfloor )$$ which have a single solution corresponding to $z=39$ and $\Phi(39)=\Psi(39)=0$

$\endgroup$
0
$\begingroup$

You mention in the comments that you derived a third equation from the first two, $94x+53y= 15327$, and you are looking for solutions where $x,y \in \mathbb{N}$. This is known as a linear Diophantine equation in two variables (with the additional constraint that $x$ and $y$ must be positive). You can find a complete procedure for solving such equations here. If you are curious about why this procedure works or if you find yourself confused by the Wolfram page, a more complete explanation is found in this lecture.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .