There are 5 computers. For each pair of computers, a coin is flipped. If it is heads, then a link is built between the computers; if it is tails, there's no link between the two. Every message that a computer receives is automatically sent to every computer to which it is linked. Find the probability that every computer is able to receive messages from every other computer.

I don’t really know how to start the problem. I think I could use cases for heads and tails but I don’t know how to. Can somebody please help me?

(Original source: ARML 2006 Individual Round, Problem I-8.)

  • 4
    $\begingroup$ What have you tried? And please write a title that is more specific. Your title could related to billions of questions unrelated to random graph theory... $\endgroup$ – David G. Stork Feb 14 at 18:11
  • 3
    $\begingroup$ Welcome to MSE. Please include your own thoughts and the effort made thus far, so that people can work with you accordingly. (Please add those in the body of the question instead of commenting.) $\endgroup$ – Lee David Chung Lin Feb 14 at 18:11
  • 1
    $\begingroup$ Try a smaller example first, for just 3 computers. Is there a way to extend what you do there to the larger problem? $\endgroup$ – Dark Malthorp Feb 14 at 18:17
  • $\begingroup$ There are $2^{\binom52}=1024$ possibilities, which can be checked by brute force. Would such a solution satisfy you? If not, what sort of solution are you looking for? $\endgroup$ – Greg Martin Feb 14 at 18:40
  • $\begingroup$ (A brute force calculation shows that the probability in question is 578/1024, or a tiny bit over 57%.) $\endgroup$ – Greg Martin Feb 14 at 18:47

Looks like the correct probability is $f(5)=91/128 \approx 0.71$, from here.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.