$N$ vessels initially contain $3$ stones each. What is the probability of having at least $3$ stones in the first vessel after moving a uniformly random selection from the first vessel to the second, then from the second vessel to the third, and so on back to the first vessel?

Input

• A positive integer $N$.
• Your code must work for inputs up to and including $10$, but may crash, error, or give incorrect output for larger inputs.

Output

• A probability $p$, so $0 \le p \le 1$.
• Your output is valid if rounding it to $6$ decimal places results in the output shown in the relevant test case.
• This is the probability of the first vessel containing greater than or equal to $3$ stones after the following process:
  • Start with $N$ vessels containing $3$ stones each.
  • For each vessel from $1$ to $N$ in order:
    • Choose uniformly randomly between $0$ and all of the stones from the vessel, and move them to the next vessel.
    • Note that when moving from vessel $N$, they are moved back to vessel $1$.

Examples

Input 1

When there is only $1$ vessel, all of the stones moved from it are moved back into it, resulting in exactly $3$ stones in vessel $1$, so the probability of there being at least $3$ stones in vessel $1$ is $1$.

Input 2

When there are $2$ vessels, the process goes like this:

• $0$, $1$, $2$, or $3$ stones are taken from vessel $1$ and added to vessel $2$. For example, $2$ stones may be taken from vessel $1$ and added to vessel $2$.
• There are now $5$ stones in vessel $2$, so $0$, $1$, $2$, $3$, $4$, or $5$ stones are taken from vessel $2$ and moved back to vessel $1$.

There are $22$ ways that this process can happen, and $16$ of those ways result in $3$ or more stones in vessel $1$. This means that the probability of there being at least $3$ stones in vessel $1$ is $16/22=0.727273$ (rounded to $6$ decimal places).

Input 3

When there are $3$ vessels, the process goes like this:

• $0$, $1$, $2$, or $3$ stones are taken from vessel $1$ and added to vessel $2$. For example, $2$ stones may be taken from vessel $1$ and added to vessel $2$.
• There are now $5$ stones in vessel $2$, so $0$, $1$, $2$, $3$, $4$, or $5$ stones are taken from vessel $2$ and added to vessel $3$. For example, $5$ stones may be taken from vessel $2$ and added to vessel $3$.
• There are now $8$ stones in vessel $3$, so $0$, $1$, $2$, $3$, $4$, $5$, $6$, $7$, or $8$ stones are taken from vessel $3$ and moved back to vessel $1$.

There are $140$ ways that this process can happen, and $102$ of those ways result in $3$ or more stones in vessel $1$. The probability of there being at least $3$ stones in vessel $1$ is $102/140=0.728571$ (rounded to $6$ decimal places).

Test cases

Test cases are in the format input : output, and are rounded to $6$ decimal places. For example, an output of 0.727272727 is equivalent to an output of 0.727273 when rounded.

1 : 1.000000
2 : 0.727273
3 : 0.728571
4 : 0.736842
5 : 0.743789
6 : 0.749164
7 : 0.753344
8 : 0.756657
9 : 0.759336
10 : 0.761542

Scoring

This is a code golf challenge. Your score is the number of bytes in your code. Lowest score for each language wins.

Explanations are optional, but I'm more likely to upvote answers that have one.

posted 7 months ago

CC BY-SA 4.0

7mo ago

trichoplax‭

1020 reputation 83 17 129 471