Author |
Topic: Numb3rs (Read 11836 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.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print