5
$\begingroup$

To make payments, the Pythagoreans use coins in no more than three denominations. The three denominations are in whole Oboloi amounts, and the sum of the squares of the two smaller denominations equals the square of the largest denomination. The amount of $1,000$ Oboloi, and any larger whole Oboloi sum, can be obtained using the three distinct types of coins. However, the exact amount of $999$ Oboloi can not be obtained (and hence requires change).

What coin denominations do the Pythagoreans use?

Improve this question
$\endgroup$
4
  • $\begingroup$ Is this a Project Euler style puzzle, where the tricky part is figuring out how to write the program? I don't have much hope for an analytic solution. $\endgroup$
    – Lopsy
    Commented Feb 22, 2015 at 21:21
  • 1
    $\begingroup$ @Lopsy - this particular three coin problem does have an analytical solution. $\endgroup$
    – Johannes
    Commented Feb 23, 2015 at 2:11
  • $\begingroup$ If the amount of 999 Oboloi can not be exactly obtained with their 3 types of coin, what do they use for change? $\endgroup$
    – KSmarts
    Commented Feb 23, 2015 at 22:16
  • $\begingroup$ @KSmarts - To make a 999 Oboloi net payment requires a payment of 16 coins (8 each of 65 Oboloi and 72 Oboloi) and a return of one 97 Oboloi coin. $\endgroup$
    – Johannes
    Commented Feb 24, 2015 at 16:13

1 Answer 1

Reset to default
12
$\begingroup$

Answer: The three denominations are $65$, $72$ and $97$.

  • How did I detect this answer? I searched the list of primitive Pythagorean triples at [link to triple list], while using the Frobenius applet available at [applet link]. Based on my search I know that the answer to the puzzle is unique; still, I would like to see a clean mathematical argument for this (that is not based on enumeration).

  • Even proving that all values from $1000$ onwards are representable is very tedious. I checked $65$ underlying individual cases with a computer program.

  • The proof that the value $999$ is not representable is doable. Suppose that there exist non-negative integers $x,y,z$ with $65x+72y+97z=999$. By considering the equation modulo 9, we get that $x\equiv z \pmod9$. By considering the equation modulo 2, we get that $x+z$ must be odd. Since $0\le x\le15$ and $0\le z\le10$, this only leaves a handful of subcases with $x=z+9$ or $z=x+9$; none of these subcases yields an integral value for $y$.

  • I have also found a [scientific paper] that provides an explicit formula for the Frobenius number of primitive Pythagorean triples:
    $$ F(m^2-n^2, 2mn, m^2+n^2)=(m−1)(m^2−n^2)+(m−1)(2mn)−(m^2+n^2).$$ By setting $m=9$ and $n=4$, we recover the solution $65$, $72$ and $97$ for the Pythagorean coin puzzle as stated above.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ The closed form of the paper gives that m divides 999, so there are only 8 candidate values of m to consider, each with at most 2 candidate values of n. $\endgroup$
    – Peter Taylor
    Commented Mar 8, 2016 at 13:25
  • 1
    $\begingroup$ In fact, since m > n for a primitive triple, it turns out that each candidate value of m only has 1 candidate value of n. $\endgroup$
    – Peter Taylor
    Commented Mar 8, 2016 at 23:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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