wu :: forums
« wu :: forums - Numb3rs »

Welcome, Guest. Please Login or Register.
Mar 28th, 2024, 2:13pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: Eigenray, SMQ, Grimbal, Icarus, william wu, towr)
   Numb3rs
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Numb3rs  (Read 11798 times)
ecoist
Senior Riddler
****





   


Gender: male
Posts: 405
Numb3rs  
« on: Apr 22nd, 2007, 11:33am »
Quote Quote Modify 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: male
Posts: 2276
Re: Numb3rs  
« Reply #1 on: Apr 22nd, 2007, 11:48pm »
Quote Quote Modify Modify

Frobenius?
IP Logged
Aryabhatta
Uberpuzzler
*****






   


Gender: male
Posts: 1321
Re: Numb3rs  
« Reply #2 on: Apr 23rd, 2007, 1:23am »
Quote Quote Modify 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: male
Posts: 405
Re: Numb3rs  
« Reply #3 on: Apr 23rd, 2007, 9:33am »
Quote Quote Modify Modify

Aargh!  My mistake!  I should have said something like 142 is not in S.  Sorry about that!
IP Logged
Aryabhatta
Uberpuzzler
*****






   


Gender: male
Posts: 1321
Re: Numb3rs  
« Reply #4 on: Apr 23rd, 2007, 9:50am »
Quote Quote Modify 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: male
Posts: 1321
Re: Numb3rs  
« Reply #5 on: Apr 23rd, 2007, 10:16am »
Quote Quote Modify 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: male
Posts: 405
Re: Numb3rs  
« Reply #6 on: Apr 23rd, 2007, 10:30am »
Quote Quote Modify 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: male
Posts: 1321
Re: Numb3rs  
« Reply #7 on: Apr 23rd, 2007, 1:30pm »
Quote Quote Modify 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: male
Posts: 1024
Re: Numb3rs  
« Reply #8 on: Dec 30th, 2009, 8:36am »
Quote Quote Modify 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.
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

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