### PROBLEM LINK:

**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:

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

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.