Search   Memberlist   Usergroups
 Page 1 of 1 [7 Posts]
Author Message
The Ghost In The Machine1
science forum Guru

Joined: 25 Mar 2005
Posts: 1551

Posted: Sat Jul 15, 2006 7:00 pm    Post subject: Re: How many different ways of this this equation....

On Mon, 10 Jul 2006 03:48:56 -0700, aliprinter wrote:

 Quote: I need help to solve this question... How many different ways of this equation... x1 + x2 + x3 + x4 = 32 if x1, x2 >= 5, x3, x4 >= 7 Thanks...

Define "ways". One could embed a lattice into a 4-dimensional space, for
instance (the lattice consists of every point with integral coordinates).
The equation given defines a 3-D subspace; the four inequalities cut this
space.

Since 5+5+7+7 = 24, many solutions are at least in theory possible. One
can define additional constraints such as x1, x2, x3, x4 <= 15 (since
32-7-5-5=15), and now one has a fully-bounded problem -- a convex
hyperparallelpiped. An even more stringent constraint is possible, since
32-7-7-5=13; therefore x1,x2 <= 13, x3,x4 <= 15.

At this point I'd probably brute-force it in the integer lattice. A
simple C program gives 165 solutions, all with x1, x2 <= 13,
x3, x4 <= 15, as it turns out, even if I merely assume x1, x2, x3, x4 <=
32, which just chews up CPU to no real point, though with such a simple
problem there's not much CPU anyway.

The program itself is almost trivial. Bear in mind, however, that the
program is possible only because the problem is fully bounded; blithely
writing a program for an unbounded problem is a recipe for failure, or at
least misunderstanding.

---- 8< ------ >8 -----
#include <stdio.h>

int main()
{
int x1, x2, x3, x4;

for(x1 = 5; x1 <= 32; x1++)
{
for(x2 = 5; x2 <= 32; x2++)
{
for(x3 = 7; x3 < 32; x3++)
{
for(x4 = 7; x4 < 32; x4++)
{
if(x1+x2+x3+x4==32)
{
printf("%d %d %d %d\n",
x1, x2, x3, x4);
}
}
}
}
}

return 0;
}
---- 8< ------ >8 -----

(The program as written doesn't count the solutions, merely lists them;
one can pipe the output to 'wc', or modify this program to count the
solutions.)

If one is in the real space, then "ways" makes little sense, but one can
try to calculate the volume of the cut of the hyperparallelpiped, perhaps
(a bit like slicing a cube, only in 4 space). I'd have to model the
problem to see what that cut looks like; that actually could get quite
interesting.

A priori, I would expect an 8-sided solid at most. My main difficulty is
defining a proper Euclidean coordinate mapping from the space defined by
x1+x2+x3+x4=32, which is 3-dimensional, into ordinary R^3 space. This is
probably most easily done by contemplating the axis starting with the norm
to this space, then three additional vectors in the space.

u1 = (1,1,1,1)
u2 = (1,-1,0,0)
u3 = (0,1,-1,0)
u4 = (0,0,1,-1)

These vectors should span all of 4-space. I'll admit I don't have an
elegant method of checking this statement apart from grinding out the
actual axis, so:

n1 = norm(u1) = (.5,.5,.5,.5)
n2 = norm(u2 - n1(u2 . n1)) = norm( (1,-1,0,0) - 0) = (A,-A, 0, 0)
where A = sqrt(2)/2.

n3 = norm(u3 - n1(u3 . n1) - n2(u3 . n2))
= norm( (0,1,-1,0) - 0 - (-A)(A,-A,0,0)
= norm( (0,1,-1,0) + (A)(A,-A,0,0))
= norm( (0,1,-1,0) + (0.5, -0.5, 0, 0) )
= norm( (0.5,0.5,-1,0) )
= (B,B,-2*B,0)

where B = 0.5/sqrt(1.5) = 1/sqrt(6).

n4 = norm(u4 - n1(u4 . n1) - n2(u4 . n2) - n3(u4 . n3))
= norm((0,0,1,-1) - 0 - 0 - (-2*B)(B,B,-2*B,0) )
= norm( (0,0,1,-1) + (2*B)(B,B,-2*B,0) )
= norm( (0,0,1,-1) + (1/3,1/3,-2/3,0) )
= norm( (1/3, 1/3, 1/3, -1) )
= (C,C,C,-3*C)

where C = sqrt(1/12).

To check, multiply all pairs and verify they're mutually perpendicular;
this can be done lightning-quick:

n1 . n2 = 0
n1 . n3 = 0
n1 . n4 = 0
n2 . n3 = 0
n2 . n4 = 0
n3 . n4 = B*C + B*C - 2*B*C = 0

Were I to have erred in my initial setup (e.g., u4' = (1,0,-1,0) = u2+u3,
which won't work; the actual verification is left to the reader) one of
the intermediates would have yielded a zero, so we're good to go.

(OK, dumb question: what's the *name* of this method? I know it's been
done before...)

I now have a transformation which, when coupled with the projection
defined by setting n1 = 0 in this new basis, should yield an interesting
solid. I'll call these coordinates y1, y2, y3, y4. Also, I'll use
notations ()_X and ()_Y, to try to reduce confusion as to which coordinate
system I'm using.

x1 == 5 is a 3-D space; the norm is of course
(1,0,0,0)_X = (.5, A, B, C)_Y. Therefore this equation is equivalent to

(1/2)*y1 + A*y2 + B*y3 + C*y4 = 5.

and its counterpart, x1 == 13, is

(1/2)*y1 + A*y2 + B*y3 + C*y4 = 13.

The rest can be written by inspection, since the dot-products can be

(1/2)*y1 - A*y2 + B*y3 + C*y4 = 5.
(1/2)*y1 - A*y2 + B*y3 + C*y4 = 13.

(1/2)*y1 -2*B*y3 + C*y4 = 7.
(1/2)*y1 -2*B*y3 + C*y4 = 15.

(1/2)*y1 - 3*C*y4 = 7.
(1/2)*y1 - 3*C*y4 = 15.

This slices out a convex, closed region of R^4 space. At this point I'll
admit I have no idea how to compute the vertices of this
polyhedron/hyperpolyhedron. The projection is accomplished by setting
y1=32, giving

A*y2 + B*y3 + C*y4 >= -11
A*y2 + B*y3 + C*y4 <= -3
-A*y2 + B*y3 + C*y4 >= -11
-A*y2 + B*y3 + C*y4 <= -3
-2*B*y3 + C*y4 >= -9
-2*B*y3 + C*y4 <= -3
-3*C*y4 >= -9
-3*C*y4 <= -3

Perhaps someone can help *me* at this point. The best I can do is to
attempt to maximize various functions of the form

P*y2 + Q*y3 + R*y4

over this space (a maxim of linear programming is that the maximum of
these sorts of functions must be at a vertex, unless a degeneracy is
encountered, in which case an edge or the entire face hits the maximum).

--
It's still legal to go .sigless.
aliprinter
science forum beginner

Joined: 10 Jul 2006
Posts: 2

Posted: Tue Jul 11, 2006 4:26 pm    Post subject: Re: How many different ways of this this equation....

Proginoskes yazdi:
 Quote: Tom wrote: I need help to solve this question... How many different ways of this equation... x1 + x2 + x3 + x4 = 32 if x1, x2 >= 5, x3, x4 >= 7 Thanks... Well if x are reals, then presumably there's infinite different solutions. If x are integers.. then can't you change it to x1+x2+x3+x4 = 8 (x1,x2,x3,x4 >= 0) ... and then you use the formula that tells you how many nonnegative integer solutions there are to y1 + y2 + ... + yr = N (namely C(N+r-1, N).) --- Christopher Heckman

Thanks.....
Proginoskes
science forum Guru

Joined: 29 Apr 2005
Posts: 2593

Posted: Mon Jul 10, 2006 10:45 pm    Post subject: Re: How many different ways of this this equation....

Tom wrote:
 Quote: I need help to solve this question... How many different ways of this equation... x1 + x2 + x3 + x4 = 32 if x1, x2 >= 5, x3, x4 >= 7 Thanks... Well if x are reals, then presumably there's infinite different solutions. If x are integers.. then can't you change it to x1+x2+x3+x4 = 8 (x1,x2,x3,x4 >= 0)

.... and then you use the formula that tells you how many nonnegative
integer solutions there are to

y1 + y2 + ... + yr = N

(namely C(N+r-1, N).)

--- Christopher Heckman
Keith A. Lewis
science forum Guru

Joined: 24 Mar 2005
Posts: 478

Posted: Mon Jul 10, 2006 5:34 pm    Post subject: Re: How many different ways of this this equation....

"aliprinter" <aliprinter@gmail.com> writes in article <1152528536.005672.308060@p79g2000cwp.googlegroups.com> dated 10 Jul 2006 03:48:56 -0700:
 Quote: I need help to solve this question... How many different ways of this equation... x1 + x2 + x3 + x4 = 32 if x1, x2 >= 5, x3, x4 >= 7

(Assuming all integer variables.) Here's how to solve.

First, transform into variables which are >= 1. The sum of these will be
different, considerably less than 32 in this case. We'll call it n.

Now you have n indistinguishable balls to distribute among 4 distinguishable
bins, with at least 1 in every bin. The number of ways to do this is (n-1)
choose 3, or (n-1)!/3!/(n-1-3)!. Think of it as making 3 "cuts" in a stack
of size n.

--Keith Lewis klewis {at} mitre.org
The above may not (yet) represent the opinions of my employer.
Tom111
science forum Guru Wannabe

Joined: 21 Jan 2006
Posts: 173

Posted: Mon Jul 10, 2006 11:34 am    Post subject: Re: How many different ways of this this equation....

 Quote: I need help to solve this question... How many different ways of this equation... x1 + x2 + x3 + x4 = 32 if x1, x2 >= 5, x3, x4 >= 7 Thanks...

Well if x are reals, then presumably there's infinite different solutions.
If x are integers.. then can't you change it to
x1+x2+x3+x4 = 8 (x1,x2,x3,x4 >= 0)
Narcoleptic Insomniac
science forum Guru

Joined: 02 May 2005
Posts: 323

Posted: Mon Jul 10, 2006 11:25 am    Post subject: Re: How many different ways of this this equation....

On Jul 10, 2006 5:48 AM, aliprinter wrote:

 Quote: I need help to solve this question... How many different ways of this equation... x1 + x2 + x3 + x4 = 32 if x1, x2 >= 5, x3, x4 >= 7 Thanks...

I'm not absolutely certain on this, but for starters I'm
thinking

x_1 = 32 - x_2 - x_3 - x_4 <= 32 - 5 - 7 - 7 = 13

...so 5 <= x_1 <= 13 and similarly 5 <= x_2 <= 13,
7 <= x_3 <= 15, and 7 <= x_4 <= 15.

That gives at least 9 possibilites for each x_1 through
x_4 so my guess would be no more than 36 solutions.

Regards,
Kyle Czarnecki
aliprinter
science forum beginner

Joined: 10 Jul 2006
Posts: 2

 Posted: Mon Jul 10, 2006 10:48 am    Post subject: How many different ways of this this equation.... I need help to solve this question... How many different ways of this equation... x1 + x2 + x3 + x4 = 32 if x1, x2 >= 5, x3, x4 >= 7 Thanks...

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [7 Posts]
 The time now is Sat Dec 15, 2018 11:46 am | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics Help me plaese with this equation.. Rjames2 Math 0 Fri Oct 13, 2006 3:23 pm Differential equation bamford Symbolic 0 Thu Aug 10, 2006 3:44 pm I need to know how it this equation was rearranged Alicia Math 3 Thu Jul 20, 2006 8:31 pm How to solve this PDE (laplace equation)? wandering.the.cosmos@gmai Research 0 Sun Jul 09, 2006 4:20 am how to efficiently solve a relatively large scale linear ... zhaohf_2000@yahoo.com Research 0 Thu Jul 06, 2006 6:02 pm