» Join 130,000+ other members in chatting. » Make lots of new friends here. » Keep up-to-date with current events. » Participate in Club outings. » Download lots of Free Stuff!

Registration just takes 2mins and is absolutely free so join our community today!

In a magical country of Wishno, people only use 8 cent and 3 cent coins as their cash. However it is not a very good system, it cannot achieve certain values of money, like 1 cent for example. What is the largest value, in terms of cents, that the country of Wishno cannot attain from 8 cent and 3 cent coins. Justify your answer.

In a magical country of Wishno, people only use 8 cent and 3 cent coins as their cash. However it is not a very good system, it cannot achieve certain values of money, like 1 cent for example. What is the largest value, in terms of cents, that the country of Wishno cannot attain from 8 cent and 3 cent coins. Justify your answer.

Layman method:

Observing the pattern of values it could form (in cents):

3 6 8 9 11 12 14 15 16 17 18 19 20 21 22...

The largest value is 13 cents.

Mathematical prove:

The values of money could be expressed in terms of 3a+8b. Where a is the number of 3 cents, b is the number of 8 cents coin used. a and b are integers.

When b=0, any multiple of 3 could be expressed in the form of 3a. Thus largest value cannot be a multiple of 3.

When a=2n, n>1 (IE: Any even numbers), value could be easily expressed in the form of 2(3n+4b). Thus the largest value must not be a multiple of 2 as well (if value is larger than 6,)

To solve for other prime numbers, a key idea that is required is that all prime numbers can be expressed as 6n+1, or 6n-1.

The smallest prime number in the form of 6n-1 that 3a+8b can form is 11, where a=1,b=1. 11 can be expressed in the form of 6n-1, where n=2.
By increasing a in increment of 2. We can form other prime numbers in the form of 6n-1 if the prime is larger than 11.

The smallest prime number in the form of 6n+1 that 3a+8b can form is 19. Where b=2, a=1.
Similarly, increasing a in increment of 2. We can form other primes in the form of 6n+1.

Thus from this, we can conclude that the only primes that could not be formed is 5,7,13.

Another issue is that, all numbers that only comprises of these numbers (25, 35, 49, 65...) COULD be expressed in the form of either 6n+1 or 6n-1. (Lazy to write prove, too long.)

As the largest value is required. The largest value of x that is not possible is 13 cents.

__________________
Currently just a wanderer...

Last edited by Tetrahedron; 29th October 2012 at 01:19 PM.

How about odd multiples of 5,7,13 le? Good that you covered all prime numbers but the odd multiples of them?

Bah. Everything will be too long. But just to shorten things down.

If a prime is already possible. Then any multiples will be possible, regardless of even and odd.
n(3a+8b) = 3(an)+8(bn)

The only problem in the proof is the numbers in the form of (5^a)(7^b)(13^c), where a,b,c are integers. But it COULD be proven that the numbers are always in the form of 6n+1 or 6n-1. Just that I am lazy.

__________________
Currently just a wanderer...

Last edited by Tetrahedron; 29th October 2012 at 05:06 PM.

Bah. Everything will be too long. But just to shorten things down.

If a prime is already possible. Then any multiples will be possible, regardless of even and odd.
n(3a+8b) = 3(an)+8(bn)

The only problem in the proof is the numbers in the form of (5^a)(7^b)(13^c), where a,b,c are integers. But it COULD be proven that the numbers are always in the form of 6n+1 or 6n-1. Just that I am lazy.

Hahas that is the problem with your solution here, way to complex, too many case to consider.
Here's mine:

Consider you have a set of money already, let say there is no 3 cent coins in it but only 8 cent coins. To increase its value by 1,take away one 8 cent coin and place in three 3 cent coins, in net, there will be an increase in 1.
Now if you have no 8 cent coins but at least five 3 cent coins, to increase your value by 1, take away the five 3 cent coins and add two 8 cent coins.
Now consider you have one 8 cent coin and two 3 cent coins, a value of 14 cents, you can increase it by 1 and when you have 15 cents, you can increase it by 1 again and so on so for.
This is so as one can see that there must be at least five 3 cent coins or at least one 8 cent for values 15 cents and above.(Use 3a+8b>15 if you still cannot convince yourself)
Therefore by induction, we can get any value from 14 cents.
To show 13 is now not possible, consider that it is possible and hence 13=3a+8b. So if we divide 13 by 3, we should get a multiple of 8, but we get 1 instead, a contradiction. So it is not possible.
This hence completes the proof to show that 13 is the largest impossible value.

Hahas that is the problem with your solution here, way to complex, too many case to consider.
Here's mine:

Consider you have a set of money already, let say there is no 3 cent coins in it but only 8 cent coins. To increase its value by 1,take away one 8 cent coin and place in three 3 cent coins, in net, there will be an increase in 1.
Now if you have no 8 cent coins but at least five 3 cent coins, to increase your value by 1, take away the five 3 cent coins and add two 8 cent coins.
Now consider you have one 8 cent coin and two 3 cent coins, a value of 14 cents, you can increase it by 1 and when you have 15 cents, you can increase it by 1 again and so on so for.
This is so as one can see that there must be at least five 3 cent coins or at least one 8 cent for values 15 cents and above.(Use 3a+8b>15 if you still cannot convince yourself)
Therefore by induction, we can get any value from 14 cents.
To show 13 is now not possible, consider that it is possible and hence 13=3a+8b. So if we divide 13 by 3, we should get a multiple of 8, but we get 1 instead, a contradiction. So it is not possible.
This hence completes the proof to show that 13 is the largest impossible value.

Ahh induction. Nice way of presenting.

I used brute force to solve the question. So I guess that works too?