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$
  • $\begingroup$ one needs at least three independent equations to solve it. How is this possible to solve? $\endgroup$ – Babai Jul 23 '14 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$ – Barry Cipra Jul 23 '14 at 19:10
  • 3
    $\begingroup$ Also, sort of off-topic, but those are some very expensive fruits. $\endgroup$ – hexaflexagonal Jul 23 '14 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$ – hexaflexagonal Jul 23 '14 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$ – Barry Cipra Jul 23 '14 at 20:21
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.

| cite | improve this answer | |
$\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$

| cite | improve this answer | |
$\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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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