|
Author |
Message |
|
TAGS:
|
|
|
SVP
Joined: 18 Nov 2004
Posts: 1544
Followers: 2
Kudos [?]:
9
[0], given: 0
|
Question Stats:
0% (00:00) correct
 0% (00:00) wrong based on 0 sessions
I have a generic question on how to do something faster.
Say we have a eqn :
Y = (-3/5) X + 30
where 0<= X <=50 and 0<= Y <=30.......Both X,Y are integers only.
Ques is to find out how many solutions are there for this eqn i.e. how many integer (X,Y) pairs are there. I know one can enumerate and then count the number of solutions. I wud be interested to know if someone knows some trick that can make this process of counting etc go quickly.
|
|
|
|
|
|
|
Manager
Joined: 22 Apr 2005
Posts: 130
Location: Los Angeles
Followers: 1
Kudos [?]:
4
[0], given: 0
|
Re: PS: Generic Ques [#permalink]
 09 May 2005, 10:44
|
|
|
|
|
|
SVP
Joined: 25 Nov 2004
Posts: 1582
Followers: 4
Kudos [?]:
13
[0], given: 0
|
Re: PS: Generic Ques [#permalink]
09 May 2005, 18:11
since value of y can be only integer, there are 11 solutions because x can only be ultiples of 5 so the values of y are also 11 integers.
value of x: 0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50.
value of y: 30, 27,........................................., 0.
i know i am going to enumerate, but it's not time consuming. but about advance mathematics, i have no idea however i love it, i love it, i love it. if i get a chance to take advance mathmatics/econometrics, i will definitely take.
|
|
|
|
|
|
Manager
Joined: 22 Apr 2005
Posts: 130
Location: Los Angeles
Followers: 1
Kudos [?]:
4
[0], given: 0
|
Here is a bit of theory for you.
Diophantine equation of type 1 is
Ax + By = C
Finding one solution x0, y0 to this equation gives us all solutions.
x(t) = x0 - Bt
y(t) = y0 + At
Where t is an integer variable.
If you are given constrains m <= x < = M and n <= y <= N you know that x(t) will be decreasing with t growing and y(t) will be growing.
Compare A and B to find out who will be growing/decreasing faster and pick (x0,y0) solution accordinly so that x0 is the closed integer to M from the bottom or y0 is the closed integer to n from the top.
After that find out maximum t so that x(t) or y(t) is still with the interval of the given constrain. Count values for t, check that the other part is still in the constrain.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
close
