Coin Problem

A classic number theory problem asked in Goldman Sachs

Suppose you have an infinite stock of $a bills and $b bills such that g.c.d(a,b)=1. Find the largest amount of money (integer) that cannot be represented using $a and $b denominations.

---

Try to solve this problem yourself before moving on to the solution below

.
.
.

.

.

---

Solution

Short answer : ab - a -b

Long answer :

Let the max number which cannot be represented using a and b denominations be x

Now, notice that we can denote the number x+a = pa + yb , for some p >= 0 & y >=0
Since x can’t be represented as : (some positive number) * a + (some positive number)*b , p = 0

So,

\(x+a=yb \)

\(x + b = za\)

for some y and z

This implies,

\(a(z+1) = b(y+1)\)

Since a and b are co-prime, z=nb-1 and y=na-1 , where n is an integer
This gives x = nab-a-b

If n>1, let n=j+k , j>0 and k > 0

\(x= jab+kab-a-b\)

\(x= a(jb-1) +b(ka-1)\)

which cannot be true

Therefore n = 1 and x= ab - a - b

.

.

😃 Over to you: Were you able to solve this?

---

👉 If you liked this post, don’t forget to leave a like ❤️. It helps more people discover this newsletter on Substack and tells us that you appreciate solving these weekly questions. The button is located towards the bottom of this email.

👉 If you love reading this newsletter, feel free to share it with friends!