There are two coins 5 cents and 17 cents. From these two coins, you
can perform any operation adding, substracting, multiplying etc. I
need to find which is the biggest number I can not obtain from these
two coins.
Thank you

---

Clarification of Question by unlimitedxp-ga on 10 Nov 2004 22:06 PST

There are two coins. 5 and 17. You can add 5 + 17 + 5 + 5 = 32. You
can also multiply 5 * 5 * 5 * 5 = 625. You can do any operations with
these two numbers in order to get the biggest number from these two
numbers, and after that  there must be a number that you cannot obtain
from these two numbers. It must be greater than 32, 625. I do not
really know how to start off. There must be some way to obtain this
number. I tried to solve it by using an aliquot divisors of a number,
which are all of its divisors except the number itself, but then I
realize that won't works. For eample Asum(A)= B, ASum(B)= C, ASum(C)
=A. Then I tried to solve it by using matrix algebra arranging  N x N
coins (for example: 9 or 16 or 25) in a square with N rows and N
columns.  From each row find the largest one and call the smallest of
these  "A".   From each column find the smallest and let "B" be the
largest of these.

---

Clarification of Question by unlimitedxp-ga on 10 Nov 2004 22:07 PST

youngan-ga
Do you know a better way to solve it, take for example by permutations
or combination ways.Thank you

---

Clarification of Question by unlimitedxp-ga on 10 Nov 2004 23:05 PST

Dear racecar-ga
Can you give me time to check the result, tomorrow with the profesor?
Thank you

i do not think the question at hand is clear, what exactly are you
implying by the biggest number you cannot obtain?

63 is the biggest amount that cannot be obtained with only 5 and 17
denomination coins.  You can get any number if you're allowed to have
negative numbers of coins.  For example, you could get say 2 by
subtracting 3 5's from one 17.  There are only numbers you can't get
if the numbers of coins must be non-negative.  You can see that you
can definitely get any number 80 or bigger, because by using from 0 to
16 5's you can get any number you want mod 17.  But 63 is 12 mod 17,
and you need 16 5's to get 12 mod 17.  You can check that all the
numbers from 64 to 79 are possible.

In general, the answer to this type of problem will be, given 2 values
x and y, the largest number you cannot make from some sum of them is
(x-1)(y-1)-1.  That is, if the numbers are relatively prime.  If
they're not relatively prime, the answer is infinity.

You can make any number you want !!
what is difficult is to obtain the number 1
while there is no commun divider between 17 and 5 , the bizout theorm
tell us that there exists too unic relative integers a and b so that :
17*a+5*b = 1
using the euclidian algorithm we find that a = -2 and b = 7
so 17+17-5-5-5-5-5=1
to obtain 2 just do (17+17-5-5-5-5-5)+(17+17-5-5-5-5-5)=2
for 3 (17+17-5-5-5-5-5)+(17+17-5-5-5-5-5)+(17+17-5-5-5-5-5)=3
and so on

Rectification :
In the last part : 5+5+5+5+5+5+5-17-17=1
2= (5+5+5+5+5+5+5-17-17)+(5+5+5+5+5+5+5-17-17)
3= (5+5+5+5+5+5+5-17-17)+(5+5+5+5+5+5+5-17-17)+(5+5+5+5+5+5+5-17-17)
and so on

aniss - the question I think unlimitedxp is trying to ask is, "Given
5-cent and 17-cent coins, what is the largest amount you cannot make
using the two types of coin?"  Obviously this number does not exist if
negative numbers are involved.

unlimitedxp - I'd like to clarify the reasoning behind my answer, so
it makes sense to you.  Also, in realizing why it works, I'd like to
simplify (x-1)(y-1)-1 to xy-x-y, which is really xy-(x+y), or the
product of the two numbers minus their sum.  We will prove that this
is an unreachable number with a proof by contradiction.  This is an
unreachable number because if ax+by=xy-x-y (a and b are both positive
integers), then (a+1)x+(b+1)y=xy, or cx+dy=xy where c and d are 2 or
greater.  Manipulate this equation a little more to get that x=cx/y+d,
x(1-c/y)=d, x=d/(1-c/y), and simplified, finally, x=dy/(y-c).  We know
that d, y, and c are all integers here, meaning that dy is an integer
and y-c is an integer.  In particular, y-c is an integer which does
not divide dy!  But this means that x is the quotient of an integer
and an integer which does not divide it, which makes x not an integer.
 Since we know that x is in fact an integer, this means that our
assumption is not true, so xy-x-y is not some combination of while x
and y-cent coins.  The number is unreachable.  Why is it the largest
unreachable?  After a certain amount of xs and ys, you reach a point
where you can construct 1s.  In this specific example, if you have 17s
and 5s, aniss has shown that adding 2 17s to a number and subtracting
7 5s we reach 1.  So if I wanted, for example, to reach 86, I could
easily do it, as I know that 85=5*17.  To reach 86 I just subtract 2
17s to get 3*17, and add 7 5s to get 3*17+7*5=86.  Since 64 is
6*17+2+5, we have plenty of 17s to subtract before we reach the next
possible problem number, namely 71 (as 70=14*5).  Once we get to 71,
we realize that from 14*5 we can also get rid of 10 5s and add 3 17s
to add one to our total and find that 71=4*5+3*17.  Then 72=11*5+1*7,
73=1*5+4*7, 74=8*5+2*7, 75=15*5, 76=5*5+3*7... etc.
I hope this makes sense.  Ask further questions if you don't
understand the method in which I reached this.

Since you permit addition, subtraction and multiplication, you can use
the fact that 5 * 7 - 17 * 2 = 1. But becuase you are not allowed to
use the numbers 7 and 2, you must do it like this:

       5 + 5 + 5 + 5 + 5 + 5 + 5 - 17 - 17 = 1.

Once you can create 1, you can repeat the above set of operations any
number of times to create any number. Examples:

1) Repeat it            63 times to create            63.
2) Repeat it 1,234,567,890 times to create 1,234,567,890.

In other words, you can create any positive integer.

If you permit the operations to be in any order, then it is possible to create 

  5 + 5 + 5 + 5 + 5 + 5 + 5 - 17 - 17 - 5 - 5 - 5 - 5 - 5 - 5 - 5 + 17 + 17 = 0.

Note that, to be strict, I am avoiding using any shortcut or even
parentheses. The first group of seven 5's and two 17's creates 1 and
the second group of the same numbers creates the -1.


In the same manner it is possible to create all the negative integers.

Finally, since in your problem statement you wrote "you can perform
any operation adding, substracting, multiplying etc." I assume that
the "etc." permits the inclusion of division. Therefore, you can
divide any integer that you create by any other non-zero integer and
get any fraction.

Have fun