4
$\begingroup$

To make payments, the Non-Pythagoreans use coins in three denominations of 999, 1000, and 1001 Oboloi. What is the largest integer amount of Oboloi that can not be represented by using these three types of coins?

Comment 1: valid representations use non-negative numbers of coins

Comment 2: Pythagorean coins

$\endgroup$
10
$\begingroup$

I think the answer is

498500
because $498500=498\times999+998$ and in modular arithmetic we have $1000\equiv1\pmod{999}$ and $1001\equiv2\pmod{999}$, so the remainder of $998$ cannot be made by fewer than $499$ additions of positive numbers less than or equal to $2$.

$\endgroup$
8
$\begingroup$

This problem is an instance of the Frobenius coin problem. In fact, the coin values form an arithmetic sequence, whose Frobenius number has the special form:

$$ g(a, a+d, \ldots, a+sd) = \left(\left\lfloor\frac{a-2}{s}\right\rfloor+1\right)a + (d-1)(a-1)-1 $$

Here we have:

$$ \begin{align} g(999, 1000, 1001) &= \\ g(999, 999+1, 999+2\times 1) &= \left(\left\lfloor\frac{999-2}{2}\right\rfloor+1\right)999 + (1-1)(999-1)-1 \\ &= 498\ 500 \end{align} $$

Thus the largest denomination that cannot be made with the Non-Pythagorean coins is $498\ 500$.

$\endgroup$
  • $\begingroup$ With a name like "Frobenius," you'd expect the coins to be denominated in Zorkmids, not Oboloi... $\endgroup$ – Mason Wheeler Sep 15 '15 at 18:33
2
$\begingroup$

The amounts can be written as 999$x$ + 1000$y$ + 1001$z$. If we want to add 1 to it:

  • We can increase $y$ and decrease $x$ by 1.

  • We can increase $z$ and decrease $y$ by 1.

  • If neither can be done ($x$ and $y$ = 0), we can increase $x$ by 500 and decrease $z$ by 499 at the very least.

So, 1001*498=498498 can't rise to 498499 and any amount starting from 499499 can be obtained. Taking 499499 and decreasing $z$s in return for $y$s (the opposite of the second scenario), we can decrement the amount by 1 every time (until 499000). Later, we decrement those new $y$s in return for $x$es (the opposite of the first scenario) until we get to 498501, which is obtainable. By this logic, 498500 is the greatest unobtainable amount.

$\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.