Constrained solutions of a particular equation
in [Math]
|
Prev: pseudosphere poles = 5,000 km? in deriving speed of light from purely math considerations ; Chapt 19 #196; ATOM TOTALITY
Next: random process similar to random walk
From: A-Man on 23 Jun 2010 22:28 Hello...My today's question is as follows. Consider the 4 variable equation v + x + y - z = 4. If I desire to find solutions to it, I can easily do it by assigning arbitary values to x, y and z and solving for v. But what I wish for, is to find solutions where the variables all belong to the set {1,2,3}. How to do that systematically? Also if I generalize the problem, keep my equation as v + x + y - z = b, b any positive even integer and search for solutions within {1,2,...,n} is there a systematic way to do that. Thanks.
From: James Waldby on 24 Jun 2010 11:04 On Thu, 24 Jun 2010 02:28:17 -0400, A-Man wrote: > Hello...My today's question is as follows. Consider the 4 variable > equation v + x + y - z = 4. If I desire to find solutions to it, I can > easily do it by assigning arbitary values to x, y and z and solving for > v. But what I wish for, is to find solutions where the variables all > belong to the set {1,2,3}. How to do that systematically? Also if I > generalize the problem, keep my equation as v + x + y - z = b, b any > positive even integer and search for solutions within {1,2,...,n} is > there a systematic way to do that. Thanks. Gerry Myerson replied to your similar question (in thread "solutions of a particular equation") with: > Get a copy of Guy, Unsolved Problems In Number Theory, and look at > Problem E14 and all the references therein. There has been a lot of > work on this kind of problem. Did you follow up on that? You might also look at Rado's theorem, Schur's theorem, and Van der Waerden's theorem, in Wikipedia. If your question is less theoretical and more about how to write a program to [for example] enumerate all solutions (x,y,z) with x, y, z in nondecreasing order, then perhaps ask the question in comp.programming or in <http://groups.google.com/group/algogeeks>. There's a simple O(n^2) method but I don't know what the best complexity is. -- jiw
From: Robert Israel on 24 Jun 2010 21:33 A-Man <shahabfaruqi(a)gmail.com> writes: > Hello...My today's question is as follows. Consider the 4 variable equation > v + x + y - z = 4. If I desire to find solutions to it, I can easily do it > by assigning arbitary values to x, y and z and solving for v. But what I > wish for, is to find solutions where the variables all belong to the set > {1,2,3}. How to do that systematically? Also if I generalize the problem, > keep my equation as v + x + y - z = b, b any positive even integer and There's no need for b to be even. > search for solutions within {1,2,...,n} is there a systematic way to do > that. Thanks. Writing v+x+y=u, your equation becomes u = b + z, where 3 <= u <= 3 n. The constraints 1 <= z <= n implies b + 1 <= u <= b + n. Thus there are solutions for max(3, b+1) <= u <= min(3 n, b + n). For each integer u in this interval, z = u - b. To get v + x + y = u, note that 2 <= x + y <= 2 n so max(1, u - 2 n) <= v <= min(n, u - 2). Then for each v in this interval, we take any integer x with 1 <= x <= min(n, u - v - 1) and y = u - v - x. In your case n=3, b=4, 5 <= u <= 7. For u=5, z = 1, 1 <= v <= 3 and we get solutions (v,x,y,z) = (1,1,3,1), (1,2,2,1), (1,3,1,1), (2,1,2,1), (2,2,1,1), (3,1,1,1) For u=6, z = 2, 1 <= v <= 3 and we get solutions (1,2,3,2), (1,3,2,2), (2,1,3,2), (2,3,1,2), (3,1,2,2), (3,2,1,2) For u=7, z=3, 1 <= v <= 3 and we get solutions (1,3,3,3), (2,2,3,3), (2,3,2,3), (3,1,3,3), (3,2,2,3), (3,3,1,3) -- Robert Israel israel(a)math.MyUniversitysInitials.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada
From: A-Man on 26 Jun 2010 23:14
Thanks...you missed (2,2,2,2) though. Regards. |