

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 >= (a1)(b1) is representable as ax+by with nonnegative x and y. Also (a1)(b1) 1 is not representable. Let us try to count the number of numbers in 1, 2, ..., ab1 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,..., ab1 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 xx' must be a multiple of b and yy' must be a multiple of a, which is not possible in the region of interest) Thus we have a 11 map between the points (x,y) and the numbers representable as ax+by with nonnegative x and y. The number of such numbers is (a1)(b1)/2 + a1 + b1 (the lattice points below ax+by =ab and the a1 on the y axis and b1 on the x axis) Thus the number of positive numbers _not_ representable is exactly (a1)(b1)/2 So we must have that (a1)(b1) = 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 nonnegative 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,.., ab1}, 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)=(a1)(b1)1c on the set {0,...,(a1)(b1)1} interchanges representable integers with nonrepresentable integers. 

Title: Re: Numb3rs Post by Aryabhatta on Apr 23^{rd}, 2007, 1:30pm on 04/23/07 at 10:30:19, ecoist wrote:
This follows immediately from the following statement: If c is not representable as ax+by for nonnegative 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) = (a1)(b1) 1 c = a*(b1) b  ax'  by' = a(b1x') + b(y'1) It is easy to see that b1x' >= 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) = ababc maps representable numbers to nonrepresentable 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) 

Powered by YaBB 1 Gold  SP 1.4! Forum software copyright © 20002004 Yet another Bulletin Board 