The Coin Problem

An interesting problem is the following:

In a land with only denominations of $6 and $11, what is the largest integral expense that cannot be paid.

Examples of expenses that cannot be paid in this strange land are 1, 2, 3, 4, 5, 7, 8, 9, 10. However, how do we find the largest such instance? It is a nice puzzle; try it for a while before reading on. (try a brute force approach if nothing works! the answer is not too big).

The first step is to change the problem into something that can mathematically manipulated. One way to do this is :

Screen Shot 2017-04-18 at 4.57.04 PM

I constructed the following method to solve this:

Screen Shot 2017-04-18 at 5.02.06 PM.png

Screen Shot 2017-04-18 at 4.59.45 PM.png

 

 

The answer comes out to be $49 ! This is the Frobenius Number for 6 and 11.

The problem can be posed more generally: what is the largest integer not expressible as a positive linear combination of a given pair of positive integers X and Y(with GCD of X and Y to be 1). It is worth investigating this problem; it has a remarkably neat answer. It comes out to be simple formula in X and Y and so the above problem was actually quite simple to solve if the general problem was solved. However, the above method, though cannot furnish a general answer, is an algorithm to find the Frobenius Number for any given pair of X and Y. Now it may seem pointless to have such a long algorithm to find something that can be found through a formula and it is undeniable that it is unpractical to use this algorithm, but the sense of joy on discovering it is reward enough!

Actually the above problem can be generalized even further. Instead of having only two denominations, we can pose the problem for n positive integers instead. Now this doesn’t have a general formula and it has to be calculated using an algorithm.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s