James has 773500 gold coins to purchase a number of hats and ties…

I have trouble with this one question. Much thanks for the answer!

James has 773500 gold coins to purchase a number of hats and ties. Each hat costs 299 gold coins, and each tie costs 208 gold coins. If the number of hats that James buys is at least twice the number of ties, how many ways can James spend his gold coins? Indicate one of the ways in which James could buy the hats and ties.

• Does he have to spend all the coins? If not, one of the ways is very easy-don't buy anything. It changes the solution to the first part considerably. – Ross Millikan Feb 26 '13 at 21:51
• If I had that many gold coins, I wouldn't spend them all on expensive hats and ties. – mrf Feb 26 '13 at 22:17

For no particularly good reason, note that our numbers are all divisible by $13$. So effectively it is the same problem if the hats cost $23$, the ties cost $16$, and the total fortune is $59500$.

There is some ambiguity, as it is not clear whether all the money has to be spent. Assume it must. Then we are looking for non-negative integer solutions of $23x+16y=59500$, with the side condition that $x\ge 2y$.

There is a general procedure for finding one integer solution to such an equation: use the Extended Euclidean Algorithm to find a solution of $23s+16t=1$ in integers, then multiply by $59500$.

Or else we can get lucky, and note that $(3)(23)+(1)(16)=85$ and $59500=(85)(700)$. So a solution in integers is $(x_0,y_0)$, where $x_0=2100$ and $y_0=700$.

Thus all integer solutions have the shape $$x=2100- 16t, \qquad y=700+23t,$$ where $t$ is an integer, positive, zero, or negative.

Finally, we need to make sure that $x\ge 2y$ (and that $x$, $y$ are non-negative). This will give us three linear inequalities in $t$, one of them superfluous.

• No luck is needed: there's an "obvious" particular solution, see my answer. – Math Gems Feb 26 '13 at 23:45

Hint  It's easy. Canceling $\,13\,$ we get $\rm\:23 x + 16 y = 7n,\ n = 8500,\:$ which has an obvious solution, namely, note $\rm\:23-16 = 7,\:$ therefore $\rm\:23n-16n = 7n,\:$ so $\rm\:(x,y)= (n,-n)\:$ is a particular solution, and the general solution is $\rm\:(x,y) = (n,-n)+k(-16,23) = (n-16k,\,23k-n).$