1998 s3 q12

Watch this thread
username53983805
Badges: 9
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#1
Report Thread starter 3 months ago
#1
Name:  1998 s3 q12.png
Views: 25
Size:  42.4 KB
My plan was to find the probability that given we are at one of A,B,C or D we cannot travel to every other village from that village, and then use that to find P.

So our possibilities given we are at A and we cannot travel to all of B,C and D are:
- can travel to only two of the three (a)
- can travel to only one of the three (b)
- cannot travel to any of the three (c)

Considering (a): If we are able to travel to B,D but not C, all roads connecting to C must be blocked with probability p. Thus three of the six roads are blocked with this probability. Of the other three, we have three possible combinations of the three remaining roads so that we ensure we can travel to both B and D.
Hence P(a)=(1-p)^{3}p^{3}+2(1-p)^{2}p^{4}=(1-p)^{2}p^{3}(1+p).

Considering (b): If we can only travel to B, the only road which can be blocked with probability 1-p is the road directly connecting A to B.
Thus P(b)=(1-p)p^{5}.

Considering (c): P(c)=p^{6}.

Hence the probability that we cannot travel to all of B,C and D when we are at A is equal to 3(1-p)^{3}p^{3}(1+p)+3(1-p)p^{5}+p^{6}=p^{3}(p^{3}-3p+3).

Even though I'd still have some fiddling around to do using this expression before I found P, I've clearly had a few gaps in my thinking. Could someone point out where I've gone wrong?
Last edited by username53983805; 3 months ago
0
reply
mqb2766
Badges: 19
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#2
Report 3 months ago
#2
Note I get
1 - p^3(...)
so p cubed multiplied by the given expression. It doesnt make sense for it to be p^2 as there would be no p^6 term (this could happen in theory, but not for this combination).

Not 100% sure of what youre doing, but the form of the answer is obviously
P = 1 - probability of at least one village not connected

When you have 0, 1 or 2 routes blocked, all villages must be connnected.
Similarly when you have 4, 5 or 6 routes blocked, at least one village is not connected.
The only slight complexity is when you have 3 routes blocked, but then the only way for the villages not to be connected are if the 3 blocked routes all lead into the same village.

So its just a slightly modified binomial on the n=6 routes where you split up the 6C3 term, assuming the p^3 rather than p^2 is correct. Sum up the 4, 5, 6 routes blocked and the 3 routes blocked going into the same village and subtract from 1.
Last edited by mqb2766; 3 months ago
0
reply
MouldyVinegar
Badges: 7
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#3
Report 3 months ago
#3
The worked solutions are in the 1998 solutions thread

(Original post by username53983805)
Considering (b): If we can only travel to B, the only road which can be blocked with probability 1-p is the road directly connecting A to B.
Thus P(b)=(1-p)p^{5}.
I'm assuming you mean unblocked not blocked. This is also not necessarily the case. If the roads AB (A to B) and CD (C to D) are unblocked, you can only travel to B from A, but there are 2 roads unblocked. Furthermore, you could have it such that only AC or only AD are unlocked, leading to 3 total permutations of that form.
Last edited by MouldyVinegar; 3 months ago
0
reply
mqb2766
Badges: 19
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#4
Report 3 months ago
#4
(Original post by username53983805)
Name:  1998 s3 q12.png
Views: 25
Size:  42.4 KB
My plan was to find the probability that given we are at one of A,B,C or D we cannot travel to every other village from that village, and then use that to find P.

So our possibilities given we are at A and we cannot travel to all of B,C and D are:
- can travel to only two of the three (a)
- can travel to only one of the three (b)
- cannot travel to any of the three (c)

Considering (a): If we are able to travel to B,D but not C, all roads connecting to C must be blocked with probability p. Thus three of the six roads are blocked with this probability. Of the other three, we have three possible combinations of the three remaining roads so that we ensure we can travel to both B and D.
Hence P(a)=(1-p)^{3}p^{3}+2(1-p)^{2}p^{4}=(1-p)^{2}p^{3}(1+p).

Considering (b): If we can only travel to B, the only road which can be blocked with probability 1-p is the road directly connecting A to B.
Thus P(b)=(1-p)p^{5}.

Considering (c): P(c)=p^{6}.

Hence the probability that we cannot travel to all of B,C and D when we are at A is equal to 3(1-p)^{3}p^{3}(1+p)+3(1-p)p^{5}+p^{6}=p^{3}(p^{3}-3p+3).

Even though I'd still have some fiddling around to do using this expression before I found P, I've clearly had a few gaps in my thinking. Could someone point out where I've gone wrong?
Had a bit more think about what you were trying last night, and arguably the main thing "wrong" is that you're focussing on the vertices of the tetrahedron (villages) rather than the edges (routes). As per the previous post, modelling whether a particular route is feasible (all villages can be reached) or not (at least one village cannot be reached) is what the question is asking, so you really want to consider the 2^6 different edge configurations (route exists or not) and work out their probability and which set (feasible/unfeasible) they belong to. This fairly naturally suggests an adapted binomial (pascals triangle) on the routes where n=6.

If you were to try and do what youre suggesting a few things
* For the cannot travel to any other village from A. BCD could be fully connected (1-p)^3 but only the connections from A missing p^3. So it would not be p^6. There are the other cases of BCD being partially connected. Also if you then extended your reasoning to start at B, C and D, would you be quadruple counting the p^6 case?
* For the can only travel to one village. This could occur in 3 cases AB, AC, AD and as before, for AB for instance, CD could be connected but you'd still only be able to travel to B from A. So your probability is again incorrect.
* When you consider starting at B, C, D are you going to multiply by 4 (which would be wrong) or ....
* For me, the basic thing was to represent "at least one village not reachable". This is fairly natural when you think about the ediges / binomial. When you start trying to break it down in terms of starting at a village and thinking of the route combinations that make that village reachable, its more complex. Then the further division into travel to 1, 2 or 3 doesnt really give a "simple" approach.

Nothing is unfixable in the above, but its going to be a long slog and mistakes will be almost certain. Modelling the edges (routes) is the way to go. Its much simpler and is fairly clearly hinted at in the question/desired solution. You can pretty much write down the solution once you've reasoned about the 6, 5, 4, 3 edges configurations:
1 - (p^6 + 6*p^5*(1-p) + 15*p^4*(1-p)^2 + 4*p^3*(1-p)^3)
1 - p^3(p^3 + 6*p^2*(1-p) + 15*p*(1-p)^2 + 4*(1-p)^3)
Then just expand and combine the bracketed expression of cubics. You could have summed up the 0,1,2,3 edge configurations as well.
Last edited by mqb2766; 3 months ago
0
reply
username53983805
Badges: 9
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#5
Report Thread starter 3 months ago
#5
(Original post by mqb2766)
Had a bit more think about what you were trying last night, and arguably the main thing "wrong" is that you're focussing on the vertices of the tetrahedron (villages) rather than the edges (routes). As per the previous post, modelling whether a particular route is feasible (all villages can be reached) or not (at least one village cannot be reached) is what the question is asking, so you really want to consider the 2^6 different edge configurations (route exists or not) and work out their probability and which set (feasible/unfeasible) they belong to. This fairly naturally suggests an adapted binomial (pascals triangle) on the routes where n=6.

If you were to try and do what youre suggesting a few things
* For the cannot travel to any other village from A. BCD could be fully connected (1-p)^3 but only the connections from A missing p^3. So it would not be p^6. There are the other cases of BCD being partially connected. Also if you then extended your reasoning to start at B, C and D, would you be quadruple counting the p^6 case?
* For the can only travel to one village. This could occur in 3 cases AB, AC, AD and as before, for AB for instance, CD could be connected but you'd still only be able to travel to B from A. So your probability is again incorrect.
* When you consider starting at B, C, D are you going to multiply by 4 (which would be wrong) or ....
* For me, the basic thing was to represent "at least one village not reachable". This is fairly natural when you think about the ediges / binomial. When you start trying to break it down in terms of starting at a village and thinking of the route combinations that make that village reachable, its more complex. Then the further division into travel to 1, 2 or 3 doesnt really give a "simple" approach.

Nothing is unfixable in the above, but its going to be a long slog and mistakes will be almost certain. Modelling the edges (routes) is the way to go. Its much simpler and is fairly clearly hinted at in the question/desired solution. You can pretty much write down the solution once you've reasoned about the 6, 5, 4, 3 edges configurations:
1 - (p^6 + 6*p^5*(1-p) + 15*p^4*(1-p)^2 + 4*p^3*(1-p)^3)
1 - p^3(p^3 + 6*p^2*(1-p) + 15*p*(1-p)^2 + 4*(1-p)^3)
Then just expand and combine the bracketed expression of cubics. You could have summed up the 0,1,2,3 edge configurations as well.
I had another go at the question before looking at your hints and I quickly realised how my original method made little to no sense to use (as, for instance, A could only be connected to B, but we could still choose suitable roads such that we could travel to every other village) and instead opted to think in terms of edges rather than vertices which made it so much simpler, and I was able to get the correct expression shortly after (my solution ended up being basically identical to what you'd said).
Last edited by username53983805; 3 months ago
0
reply
mqb2766
Badges: 19
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#6
Report 3 months ago
#6
(Original post by username53983805)
I had another go at the question before looking at your hints and I quickly realised how my original method made little to no sense to use (as, for instance, A could only be connected to B, but we could still choose suitable roads such that we could travel to every other village) and instead opted to think in terms of edges rather than vertices which made it so much simpler, and I was able to get the correct expression shortly after (my solution ended up being basically identical to what you'd said).
Its 20 odd years ago, but it did strike me as being a bit of an "odd" question in that if you've got the right approach, its 4 or 5, relatively simple lines (once youve argued about how the number of routes map to "at least one unconnected", which isnt hard either), but as you found, you can easily spend a fair bit of time on the wrong approach.
Last edited by mqb2766; 3 months ago
0
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest

Were exams easier or harder than you expected?

Easier (46)
26.14%
As I expected (58)
32.95%
Harder (64)
36.36%
Something else (tell us in the thread) (8)
4.55%

Watched Threads

View All