List one of the ways in which Mario could buy the stars and comets. Note: Mario needs to spend all of his gold coins

Question

Mario has 773500 gold coins to purchase a number of stars and comets. Each star costs 299 gold coins, and each comet costs 208 gold coins. If the number of stars that Mario buys is at least twice the number of comets, how many ways can Mario spend his gold coins? List one of the ways in which Mario could buy the stars and comets. Note: Mario needs to spend all of his gold coins

I think we have to use the linear diophantine equation theorem for this question. But I really can't figure out how to apply it. Can someone please help me? This is a past math contest question.

Answer 1

Suppose you've found 1 answer, let this be (x,y). Since 299 = 13*23, and 208 = 13*16, we have that any (x-16t, y+23t) is also a solution where t is an integer. Therefore, you should next impose the condition that x always more than 2y, to find the set of solutions.

Answer 2

299x + 208y = 773500

299x/208 + 208y/208 = 773500/208 (Simplifying)

91x/208 - 156/208 = 3718 -x -y

7x/16 - 3/4 = k(constant)

*7 => 49x/16 - 21/4 = k

x/16 - 1/4 = k - 3x + 5

x/16 - 1/4 = c (constant)

=> x = 16*(c + 1/4)

 = 16c + 4

c x y

1 20 3690

2 36 3667

3 52 3644

4 68 3621

..... ..... .....

119 1908 976

120 1924 953

We can easily see that the values of x and y are forming an AP.

For c=120, the value of x goes over the double of y for the first time, so this is the first solution.

Similarly continuing, you can find out the rest of the solutions by counting the terms of y, till it is positive.

Answer 3

Buy $x$ stars and $y$ comets. The equation is $$299x+208y=773500$$ Divide by $\gcd(299,208)=13$: $$23x+16y=59500$$ Use the Euclidean algorithm to find a particular solution: $$x_0=416500,y_0=-595000$$ The general solution is $$x=416500-16t,y=-595000+23t$$ From the constraints $x\ge 2y$ and $y\ge0$ we get the bounds $$25911\ge t\ge25870$$ The number of solutions is $$25911-25869=42$$ For example Mario could buy $2580$ stars and $10$ comets, or $1924$ stars and $953$ comets.