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 4dimensional space, for
instance (the lattice consists of every point with integral coordinates).
The equation given defines a 3D 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
32755=15), and now one has a fullybounded problem  a convex
hyperparallelpiped. An even more stringent constraint is possible, since
32775=13; therefore x1,x2 <= 13, x3,x4 <= 15.
At this point I'd probably bruteforce 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 8sided 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 3dimensional, 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 4space. 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 lightningquick:
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 3D 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 dotproducts can be
computed almost in one's head:
(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).

#191, ewill3@earthlink.net
It's still legal to go .sigless. 

Back to top 


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+r1, N).)
 Christopher Heckman

Thanks..... 

Back to top 


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+r1, N).)
 Christopher Heckman 

Back to top 


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 (n1)
choose 3, or (n1)!/3!/(n13)!. 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. 

Back to top 


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) 

Back to top 


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 

Back to top 


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... 

Back to top 


Google


Back to top 



The time now is Sun Feb 25, 2018 6:04 am  All times are GMT

