Problem 44885. Bridge and Torch Problem - Probability

Details of the problem ...

There are four people who wants to cross the bridge. But we don't know exactly who will cross the bridge in which time. However, we know that a person can cross the bridge in n1 minutes (n1 is randomly selected from the range 1:n, n is the first input). All crossing times are integers. They use Crossing Model to cross the bridge. In each turn, they randomly select the person(s) who will cross the bridge. What is the probability that they will cross the bridge less than or equal to t minutes (t is the second input).

Let's assume first input n = 3. That means people will cross the bridge in 1, 2 or 3 minutes. all of them can cross the bridge in 1 minute or maybe all of them can cross the bridge in 3 minutes. Possibilities are listed below.

crossingTimeList = [
1	1	1	1
1	1	1	2
1	1	1	3
1	1	2	2
1	1	2	3
1	1	3	3
1	2	2	2
1	2	2	3
1	2	3	3
1	3	3	3
2	2	2	2
2	2	2	3
2	2	3	3
2	3	3	3
3	3	3	3]

If first line is the case, all of the people will cross the bridge in 1 minute. There will be 108 cases ( 108 = 4C2 X 2C1 X 3C2 X 3C1 ) taking 5 minutes. All of them will be less than or equal to 10 minutes (which is input 2).

If ninth line is the case, one person will cross the bridge in one minute, one person will cross the bridge in two minutes, and others will cross the bridge in 3 minutes. 8 out of 108 ways will take less than or equal to 10 minutes.

If last one is the case, all of them will cross the bridge in three minutes indicates that all of the journeys will take 15 minutes (longer than input2 or 10 minutes).

Result of the crossingTimeList are as follow

result = [
108	108
108	108
060	108
108	108
054	108
026	108
108	108
304	108
008	108
000	108
108	108
000	108
000	108
000	108
000	108]

As a result 722 out of 1620 ways will take <= 10 minutes (722/1620=0.4457).

Assumption 1: for this problem only four people will cross the bridge

Assumption 2: crossing times are integer

Crossing Model: 2 out of 4 people will cross the bridge, one of them will return. two out of 3 people will cross the bridge, one out of three people will return. Remaining two people will cross the bridge.