EQUILIBR - Editorial

editorial
, ,
1

PROBLEM LINK:

Div 1
Div 2
Practice

Author: Full name
Tester: Full name
Editorialist: Oleksandr Kulkov

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Analytic geometry, probability theory

PROBLEM:

Consider n uniformly distributed real values that sum up to k. You are to calculate the probability that it will be possible to assign directions to vectors in 2-dimensional space in such way that their sum will be equal to 0.

Important note

Here we have to be very precise on what me mean by uniform, since definition from problem statement is kind of misleading. There can be many distributions such that probability of any picked set of lengthes will be equal to 0 and it even may be that in such distributions there will be different answers. To be totally correct here we should say that if G is set of all possible sets of lengthes and X \subset G is its measurable subset then probability of uniformly chosen element of G to be in X must be equal to \frac{\mu(X)}{\mu(G)}. Here \mu(X) and \mu(G) should be considered to be multi-dimensional measures (or volumes) of X and G. If we additionally say that distribution of random values is continuous, i.e. it has probability density function, then for each r \in G probability density is constant and equal to \tfrac{1}{\mu(G)}.

QUICK EXPLANATION:

It can be proven that answer is 1-n/2^{n-1}.

EXPLANATION:

Let a_1,\dots,a_n be generated lengths. If vectors r_1,\dots,r_n having those lengths are sorted by their polar angle and sum up to 0 then we can form a convex polygon by starting from (0,0) and attaching every new vector to the end of the previous one. It directly follows from the fact that their sum can be obtained in such a way and that it equals 0.

Now when can we make up a convex polygon of vectors with given lengthes? Answer is if and only if the largest length is smaller than sum of others. It obviously is necessary condition but it’s also sufficient one, because if given lengthes satisfy that condition, you can to be precise make up at least inscribed polygon, that is to find radius r for which each length correspond to some arc of the circle. It can be done by binary search if you want to construct it, but that’s not necessary for this particular problem.

Since sum of lengthes is fixed to k, we should just count the probability of every side being at most k/2. We should note that random events of a_i>k/2 and a_j>k/2 for i \neq j are incompatible, thus:

\mathbb P(a_1 > k/2 ~or~ a_2 > k/2 ~or~\dots~or~a_n>k/2)=\mathbb P(a_1 > k/2) + \dots + \mathbb P (a_n>k/2)

And due to simmetry it equals to n \cdot \mathbb P(a_n > k/2). For figuring probability we can write that:

\mathbb P(a_n > k/2) = \mathbb P(a_1+\dots+a_{n-1} < k/2)=\left(~\idotsint\limits_{\substack{0< x_1,\\ \dots\\0< x_{n-1},\\x_1+\dots+x_{n-1}< k/2}} dx_1 \dots dx_{n-1}\right)/\left(~\idotsint\limits_{\substack{0< x_1,\\ \dots\\0< x_{n-1},\\x_1+\dots+x_{n-1}< k}} dx_1 \dots dx_{n-1}\right)

As you see, we consider geometrically similar sets here. Their linear sizes relate to each other as 1:2 thus volumes of k-th degree will relate as 1:2^k. We are interested in volumes of degree n-1 so needed number is equal to 1/2^{n-1}. From this we get that probability of impossibility to form a polygon is equal to n/2^{n-1} thus the final answer is 1-n/2^{n-1}.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.

2

“If given lengths satisfy that condition, you can to be precise make up at least inscribed polygon, that is to find radius r for which each length correspond to some arc of the circle. It can be done by binary search if you want to construct it, but that’s not necessary for this particular problem.”

I was thinking of an extension to the current problem (finding the circle).
In this statement quoted above, can you please help me understand how binary search can be used to find radius r.

3

Hi! You can refer to this problem from hackerrank: https://www.hackerrank.com/contests/w23/challenges/enclosure

It focuses on this particular question. See the editorial, I suppose it should be well described there.

1 Like
4

Could you please explain further as to how were you able to come up with this number (upto k/2):

“Since sum of lengthes is fixed to k, we should just count the probability of every side being at most k/2.”

5

If one side (length a) is greater then sum of all the others (let it be b) and a+b=k then a>k/2. Otherwise if a< k/2 then b=k-a>k/2>a which is contradiction. Maybe I should be more strict with < and \leq but when we talk about probabilities on something based on real numbers, that almost always would be negligible.

1 Like
6

Can you prove that formed polygon will be Convex? I think polygon formed will not necessarily be convex.

[ps upvote this ans, cant comment <_<]

7

@zura it will always be possible to form a convex polygon in case of valid force vectors. That is you always have a counterpart of concave polygon that is convex and essentially adds up to zero vector that is of interest here. You can view the picture as an eg for 5 force vectors.

8

can any one tell me the how is mod working?
i did’nt get 11.16^-1%(1e9+7)
thanks

9

I don’t know how you got 11.16.

For this problem, it can be simplified as numerator by denominator ie) \frac{2^{n-1} - n}{2^{n-1}}. Both the numerator and denominator can be calculated as modulo 1e9+7. Calculate mod inverse of denominator and multiply with numerator.

1 Like
10

Their linear sizes relate to each other as 1:2 thus volumes of k-th degree will relate as 1:2k. We are interested in volumes of degree n−1 so needed number is equal to 1/2n−1. From this we get that probability of impossibility to form a polygon is equal to n/2n−1 thus the final answer is 1−n/2n−1.

Any reference to understand this part(basically how the integral gets to the final answer)?

1 Like
11

Strict explanation yields some stuff about mathematical measures. If I try to explain in very simplimistic (and not really mathematically correct) way, you can assume that your set is composed of infinitely many rectangular cells. What happens to the area of rectangle if you multiply both sides by 2? It will increase in 2^2 times. For parallelepiped increase will be in 2^3 times, and so on. In this problem you may assume that you kind of increased each dimension of each cell composing the set twice, thus you got increase in 2^{n-1} times since you work in \mathbb R^{n-1}.

1 Like
12

Thanks for answering,I get that part but how

ℙ(a1+⋯+an−1<k/2) is equal to the integral shown in the first place?

13

@kiquance you can see the link below to get a little intuition on how to relate P(a1+a2+…+an<m) to areas.

http://mathforum.org/library/drmath/view/71633.html

Hope it helps.

1 Like
14

Thanks for the link. Much needed. Editorial should contain some links like this.