wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Numb3rs
        
(Message started by: ecoist on Apr 22^nd, 2007, 11:33am)

Title: Numb3rs
Post by ecoist on Apr 22^nd, 2007, 11:33am

The numbers a and b, b>a, are positive integers. Let S={ax+by | x, y nonnegative integers}. There are exactly 77 positive integers which are not in S, one of which is 144. Determine a and b.

Title: Re: Numb3rs
Post by Barukh on Apr 22^nd, 2007, 11:48pm

[hide]Frobenius[/hide]?

Title: Re: Numb3rs
Post by Aryabhatta on Apr 23^rd, 2007, 1:23am

Looks like it is not possible...

Since there are exactly 77 not representable, we must have that gcd(a,b) = 1 (otherwise that number would be infinite)

It is well known that any number which is >= (a-1)(b-1) is representable as ax+by with non-negative x and y. Also (a-1)(b-1) -1 is not representable.

Let us try to count the number of numbers in 1, 2, ..., ab-1 which are representable in such a way

Consider the line ax + by = ab.
Any lattice point which lies in the region
R = {ax + by < ab AND x >= 0 AND y >= 0 }
gives us a number in 1,2,..., ab-1 representable as ax + by. Also any positive number < ab which is representable as ax+by corresponds to such a point (in fact to (x,y))

Also, two points (x,y) and (x',y') in R cannot map to the same number c. (using (a,b) =1 , we can show that x-x' must be a multiple of b and y-y' must be a multiple of a, which is not possible in the region of interest)

Thus we have a 1-1 map between the points (x,y) and the numbers representable as ax+by with non-negative x and y.

The number of such numbers is (a-1)(b-1)/2 + a-1 + b-1

(the lattice points below ax+by =ab and the a-1 on the y axis and b-1 on the x axis)

Thus the number of positive numbers _not_ representable is exactly (a-1)(b-1)/2

So we must have that (a-1)(b-1) = 1x2x7x11

So (a,b) = (2,155) or (3,78 ) or (8,23), (12, 15)

Given the fact that 144 is not representable, it looks like there are no such a and b.

Title: Re: Numb3rs
Post by ecoist on Apr 23^rd, 2007, 9:33am

Aargh! My mistake! I should have said something like 142 is not in S. Sorry about that!

Title: Re: Numb3rs
Post by Aryabhatta on Apr 23^rd, 2007, 9:50am

If 142 is not representable, then it must be (8,23)

142 = 8x + 23y

y must be even.

So 71 = 4x + 23z.

z must be odd = 2s+1 say, s >= 0

71 = 4x + 23*(2s+1) = 4x + 46s + 23
48 = 4x + 46s.

Which is not possible.

Thus a = 8 and b = 23.

Title: Re: Numb3rs
Post by Aryabhatta on Apr 23^rd, 2007, 10:16am

Here is a follow up question:

Let a,b be positive integers such that (a,b) = 1.

Let c be an integer such that 0 < c < ab.

Show that: c is not representable as ax + by for non-negative x,y if and only if c = ax' + by' for some 0 <= x' < b and y' < 0

(This gives us a method to find all non representable numbers in {1,2,.., ab-1}, and give a method to count them if needed)

Title: Re: Numb3rs
Post by ecoist on Apr 23^rd, 2007, 10:30am

Or, show that the map f(c)=(a-1)(b-1)-1-c on the set {0,...,(a-1)(b-1)-1} interchanges representable integers with non-representable integers.

Title: Re: Numb3rs
Post by Aryabhatta on Apr 23^rd, 2007, 1:30pm

on 04/23/07 at 10:30:19, ecoist wrote:

Or, show that the map f(c)=(a-1)(b-1)-1-c on the set {0,...,(a-1)(b-1)-1} interchanges representable integers with non-representable integers.

This follows immediately from the following statement:

If c is not representable as ax+by for non-negative x,y, then there exists an x', 0 <= x' < b and a y' < 0 such that c = ax' + by'

If c is not representable then c = ax' + by' for y' < 0 and 0 <= x' < b

then f(c) = (a-1)(b-1) -1 -c = a*(b-1) -b - ax' - by' = a(b-1-x') + b(-y'-1)

It is easy to see that b-1-x' >= 0 and -y'-1 >= 0

Thus if c is not representable, then f(c) is. Also, at least one of c and f(c) is not representable as c + f(c) isn't representable.

Thus the map f(c) = ab-a-b-c maps representable numbers to non-representable and vice versa.

Title: Re: Numb3rs
Post by BenVitale on Dec 30^th, 2009, 8:36am

Isn't true that for a number r in the set R, any integer greater than r can be written in the form :

am + bn

and that we cannot have an integer x is less than r?

I'm referring to Frobenius coin problem (http://en.wikipedia.org/wiki/Coin_problem)

And, in Wolfram : Frobenius Number (http://mathworld.wolfram.com/FrobeniusNumber.html)

Coin Problem (http://mathworld.wolfram.com/CoinProblem.html)