Currency

Difficulty:
★★★☆☆

Problem:

Suppose there is a country whose currency is in only two denominations: $5 bills and $7 bills. What is the maximum amount that you cannot pay with these two types of bills?


Solution:

This is how I solved it (this is a Frobenius coin problem  -- scroll down to read about James Joseph Sylvester's generalized solution!).

Notice that you can pay any amount in the form 5x + 7y, where x and y are non-negative integers. Multiples of 7 have the following properties:

• When 7 is multiplied by an integer whose last digit is 1, the last digit of the product is 7.
• When 7 is multiplied by an integer whose last digit is 2, the last digit of the product is 4.
• When 7 is multiplied by an integer whose last digit is 3, the last digit of the product is 1.
• When 7 is multiplied by an integer whose last digit is 4, the last digit of the product is 8.
• When 7 is multiplied by an integer whose last digit is 5, the last digit of the product is 5.
• ... and so on.

Suppose y is an integer whose last digit is 1. Then the last digit of 5x + 7y is either 7 or 2. Similarly, if the last digit of y is 2, the last digit of 5x + 7y is either 4 or 9, and so on.

This means that 5x + 7y can be any integer greater than or equal to 7 × 1 = 7 whose last digit is 7 or 2. Given this, it can also be any integer greater than or equal to 7 × 2 = 14 whose last digit is 7, 2, 4 or 9. As you go down the bulletted list, you can see that 5x + 7y can also be any integer greater than or equal to  7 × 3 = 21 whose last digit is 7, 2, 4, 9, 1 or 6, and so on. So if we let z = 5x + 7y, the following are the possible values of z.

• z ≥ 7 whose last digit ∊ {7, 2}
• z ≥ 14 whose last digit ∊ {7, 2, 4, 9}
• z ≥ 21 whose last digit ∊ {7, 2, 4, 9, 1, 6}
• z ≥ 28 whose last digit ∊ {7, 2, 4, 9, 1, 6, 8, 3}
• z ≥ 35 whose last digit ∊ {7, 2, 4, 9, 1, 6, 8, 3, 5, 0}
• Any integer whose last digit ∊ {5, 0} (i.e. any multiple of 5)

From this you can see that every z ≥ 24 is "covered." The maximum integer that cannot be z is 23.

This solution involves a bit of brute forcing and isn't always applicable to arbitrary denominations. Sylvester's generalized solution (and proof) is as follows:

... TBD