wu :: forums « wu :: forums - Numb3rs » Welcome, Guest. Please Login or Register. Mar 20th, 2023, 9:41pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    putnam exam (pure math) (Moderators: SMQ, william wu, Grimbal, towr, Icarus, Eigenray)    Numb3rs « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Numb3rs  (Read 11772 times)
ecoist
Senior Riddler

Gender:
Posts: 405
 Numb3rs   « on: Apr 22nd, 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 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.
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »