Hey can someone explain how to solve EQUILIBR from July Long challenge. The answer (i.e., probability) seems to be 1-\frac{n}{2^{n-1}} if I understood the solutions but couldn’t figure out why.
1 Like
If N = 2, only way for sum to be zero is (k/2, k/2). Probability of a point in a continuous region is zero.
For N > 2:
Idea is if one of the magnitude is greater than k/2 => then there is no way to get sum of vectors to zero. Alternatively, if all the magnitude is less than k/2 => There is always a way to get sum to zero. Try to prove this using three vectors and generalise. You may need to resolve the vectors in two dimensions using sin and cos.
Since the values can be real magnitude and there is a constraint, the possible values will form a hyperplane. So we need to find, what fraction of this possible solution space will have atmost one dimension greater than k/2.
For first dimension to violate the condition, it can be calculated using integrals to be \frac{1}{2^{n−1}}, n different directions are there. So answer is 1−\frac{n}{2^{n−1}}
@tamiliitCan you give rigorous math proof (i.e integration) on how we get that term by integration .I was thinking along the same lines but couldn’t find it.
I don’t know this is right or not but what I think of this question is as consider a closed polygon which is drawn from those vectors and its centre must lie inside it and probability of making a polygon whose centre lies inside it is 1-(n/(2^n-1))
Couple of observations here -
- Forces are balanced when they form closed polygon
If a1, a2, … are sides of polygon and sum of sides is k,
the polygon is possible only when none of the sides is greater than k/2
***PROOF*** -
*For n sides to form a closed polygon, sum of any n-1 sides should be greater than the remaining one side
i.e, X1 < X2 + X3 + ... + Xn
since X1 + X2 + ... + Xn = k, substituting value of RHS in above equation
X1 < k - X1
2X1 < k
X1 < k/2
- Lets try to compute probability of loosing here
A key observation is that only one of the vectors can be given length greater than k/2
(thats because sum of other n-1 is itself less than k/2 because total sum is k)
- So if we fix vector 1 to have side greater than k/2 and probability of loosing turns out to be p,
then,
Probe of winning = 1 - n*p
(thats because there are n options to fix a vector that will have side greater than k/2)
So the problem can be solved if we find p in step 3
To find p, vector 1 needs to have magnitude greater than k/2. Lets give vector 1 a magnitude of k/2
After the we have k - k/2 = k/2 magnitude left to be divided into n vectors
This problem is equivalent of following -
Consider a number line of [0, k] with segment [0, k/2] being blocked (because given to first vector)
What is the probability of putting n-1 cuts such that all cuts lie in (k/2, k] segment
If we think logically putting each of these (n-1) cuts is independent of one another (infinitely many real numbers between any range)
Also probability of a cut lying in second half of a number line is 1/2
Hence p = (1/2) ^ (n-1)
Answer to problem = 1 - n * [ (1/2) ^ (n-1) ]
The answer here turns out to be independent of k which perfectly makes sense.
This is because k here is the length of our line segment here and the cuts are real numbers.
Since the number of REAL numbers between [a,b] and [c,d] is same (infinite), the length of line doesn’t matter here
3 Likes
Thank you very much for the clear explanation.
To represent total cases/favorable cases, we can use volumes of n-d figures.
To find total number of possible cases (all possible n-tuples), one can easily see the recurrence relation :
f(k,n) = \int_0^k f(k - x, n - 1)dx and f(k, 1) = 1 where we consider all different permutations of (x_1, x_2, ...,x_n) to be different.
using this, it is easy to find, in a closed form, the total number of cases for a given k and n to be \frac{k^{n -1}}{(n - 1)!}
Now, to find number of favorable cases, note the following.
A given tuple (x_1, x_2, ...,x_n) is favorable (meaning directions can be assigned such that all vectors cancel out) if it can be the sides of a closed n-sided polygon. The condition for the latter is \sum_{i = 1}^{n} x_i \geq 2 * x_i \text{ } \forall \text{ } 1 \leq i \leq n;
Now to select all such n-tuples, select x_1, x_2, ..., x_{n - 1} to form the tuple (x_1, x_2, ..., x_{n - 1}, k - x_1 - x_2 - ... -x_{n - 1})
Applying the condition of a closed polygon, one obtains the following inequalities :
\frac{k}{2} \leq \sum_{i = 1}^{n - 1} x_i \leq k; and 0 \leq x_i \leq \frac{k}{2} \forall 1 \leq i \leq (n - 1);
This represents the volume of an n-d figure and can either be calculated by integrating recursively or can be proved by induction. Finally total no of favorable cases comes out to be \frac{k^{n -1}}{(n - 1)!} - n * \frac{\left(\frac{k}{2}\right)^{n - 1}}{(n - 1)!}
Thus the probability comes out to be 1 - \frac{n}{2^{n - 1}}
2 Likes
"To find total number of possible cases (all possible n-tuples), one can easily see the recurrence relation :
f(k,n) = \int_0^k f(k - x, n - 1)dx and f(k, 1) = 1"
Wut O.O ?! How can one easily observe this? :o
number of ways to divide k into n parts = sum_over(1st part is x, and then divide k - x into n - 1 parts). Since x does not vary discretely but continuously, we have to integrate rather than sum. For n = 3, this is basically the area bounded by x = 0, y = 0 and x + y = k.
1 Like
I saw the formula from this http://tutorial.math.lamar.edu/Classes/CalcIII/SurfaceIntegrals.aspx to calculate surface integral.
The term inside the square root is a constant. It will be present in both the numerator and denominator. So I eliminated it.
Integrals will be of form for:
For x_1 + x_2 + x_3 + x_4 = k
Denominator - \int_{0}^{k} \int_{0}^{k - x_1} \int_{0}^{k - x_1 - x_2} dx_3dx_2dx_1
Numerator - \int_{k/2}^{k} \int_{0}^{k - x_1} \int_{0}^{k - x_1 - x_2} dx_3dx_2dx_1
Evaluating such a formula for n = 3, n=4, n=5 will give an idea how the formula will look for any n.
in test case of EQUILIBR we have given 5 vectors & sum of magnitude of vectors is also 5
then possible case could be: {5,0,0,0,0} after arranging it we got 5 case.
next {4,1,0,0,0} after arrnging we got 20 case.
next {3,2,0,0,0} again we got 20 after arranging.
next {3,1,1,0,0} here we got 30 case after arranging.
next {2,2,1,0,0} here we got again 30 case.
next {2,1,1,1,0} here we got 20 case.
next{1,1,1,1,1} here we got 1 case after arranging.
so total we got 126 case in which polygon is formed (k/2 less condition) there 51 case.
i dont understand how we got p=11 & q=16
please help me in @ EQUILIBR problem???
@akash_92 it is given that the magnitude of the vector can be any non-negative real number, hence there are infinite cases for n=5 and k=5, not 126 and the formula is derived either by integration or by logical approach given above.
You are considering only integers.
The vectors can have any non negative real magnitude.
How did u find the closed for m of that integration?
I had to use n integrals to find out that formula,is there any simpler way to do it?
" the total number of cases for a given k and n to be k^n−1/(n−1)! "
But for real numbers the total number of cases is infinity and noncountable.
I have a doubt regarding n = 2 . Since we are allowed to choose the directions for the vectors. Wouldn’t all the points lying on the circumference of the circle of radius k/2 satisfy the criterion?
** EDIT **
I realized my mistake. We just had to find distributions of lengths of n vectors which sum upto k and can be assigned directions such that their vector sum is 0.
I mistook it as to find all vectors whose magnitude sum upto k and vector sum is 0. BTW is there a closed form or how to approach this modified version.
@vivek_1998299 Induction is the simplest way i think. I just observed a pattern and showed it with induction ! 
@batura_dima Indeed the total number of cases is infinite and noncountable. But we can represent it with a volume in n-d space. For example, for the case n = 3, it is represented by the area in 1st quadrant under the line x + y = k. Each point in this region represents a 3-tuple.