Author |
Topic: Numb3rs (Read 11833 times) |
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
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 22nd, 2007, 11:48pm » |
Quote Modify
|
Frobenius?
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Numb3rs
« Reply #2 on: Apr 23rd, 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 >= (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.
|
« Last Edit: Apr 23rd, 2007, 1:27am by Aryabhatta » |
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Numb3rs
« Reply #3 on: Apr 23rd, 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 23rd, 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 23rd, 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 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)
|
« Last Edit: Apr 23rd, 2007, 10:17am by Aryabhatta » |
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Numb3rs
« Reply #6 on: Apr 23rd, 2007, 10:30am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Numb3rs
« Reply #7 on: Apr 23rd, 2007, 1:30pm » |
Quote Modify
|
on Apr 23rd, 2007, 10:30am, 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.
|
« Last Edit: Apr 23rd, 2007, 2:03pm by Aryabhatta » |
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: Numb3rs
« Reply #8 on: Dec 30th, 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 30th, 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.
|
|
|
|