Author 
Topic: Numb3rs (Read 11587 times) 

ecoist
Senior Riddler
Gender:
Posts: 405


Numb3rs
« on: Apr 22^{nd}, 2007, 11:33am » 
Quote Modify

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.


IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: Numb3rs
« Reply #1 on: Apr 22^{nd}, 2007, 11:48pm » 
Quote Modify

Frobenius?


IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Numb3rs
« Reply #2 on: Apr 23^{rd}, 2007, 1:23am » 
Quote Modify

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.

« Last Edit: Apr 23^{rd}, 2007, 1:27am by Aryabhatta » 
IP Logged 



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Numb3rs
« Reply #3 on: Apr 23^{rd}, 2007, 9:33am » 
Quote Modify

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


IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Numb3rs
« Reply #4 on: Apr 23^{rd}, 2007, 9:50am » 
Quote Modify

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.


IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Numb3rs
« Reply #5 on: Apr 23^{rd}, 2007, 10:16am » 
Quote Modify

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)

« Last Edit: Apr 23^{rd}, 2007, 10:17am by Aryabhatta » 
IP Logged 



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Numb3rs
« Reply #6 on: Apr 23^{rd}, 2007, 10:30am » 
Quote Modify

Or, show that the map f(c)=(a1)(b1)1c on the set {0,...,(a1)(b1)1} interchanges representable integers with nonrepresentable integers.


IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Numb3rs
« Reply #7 on: Apr 23^{rd}, 2007, 1:30pm » 
Quote Modify

on Apr 23^{rd}, 2007, 10:30am, ecoist wrote:Or, show that the map f(c)=(a1)(b1)1c on the set {0,...,(a1)(b1)1} interchanges representable integers with nonrepresentable integers. 
 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.

« Last Edit: Apr 23^{rd}, 2007, 2:03pm by Aryabhatta » 
IP Logged 



Benny
Uberpuzzler
Gender:
Posts: 1024


Re: Numb3rs
« Reply #8 on: Dec 30^{th}, 2009, 8:36am » 
Quote Modify

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 And, in Wolfram : Frobenius Number Coin Problem

« Last Edit: Dec 30^{th}, 2009, 8:55am by Benny » 
IP Logged 
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.



