Computer Network Triangle Puzzle – Probability the Network Stays Connected

Δίκτυο Υπολογιστών: Με πόση Πιθανότητα Παραμένει Συνδεδεμένο;

Το σχήμα δείχνει συνδέσεις ανάμεσα σε αρκετούς υπολογιστές ενός δικτύου. Κάθε υπολογιστής μπορεί να στείλει μηνύματα σε οποιονδήποτε άλλο, ίσως περνώντας μέσα από ενδιάμεσους υπολογιστές. Υπάρχει ένας κεντρικός υπολογιστής συνδεδεμένος με 8 εξωτερικούς· οι εξωτερικοί είναι ζευγαρωμένοι σε 4 ζεύγη, και κάθε ζεύγος συνδέεται επίσης με μια γραμμή μεταξύ των δύο υπολογιστών του. Έτσι σχηματίζονται 4 τρίγωνα, όλα με κοινή κορυφή τον κεντρικό υπολογιστή.

Για κάθε σύνδεση στο δίκτυο ρίχνουμε ένα νόμισμα. Αν φέρει κορώνα, η σύνδεση παραμένει· αν φέρει γράμματα, η σύνδεση αφαιρείται. Όλες οι ρίψεις είναι ανεξάρτητες.

Ποια είναι η πιθανότητα ότι, μετά από όλες τις ρίψεις, κάθε υπολογιστής μπορεί ακόμα να στείλει μήνυμα σε οποιονδήποτε άλλο;

(A) 1/4096    (B) 1/16    (C) 3/32    (D) 81/256    (E) 91/128

Λύση

Το δίκτυο αποτελείται από 4 ίδια τρίγωνα, καθένα με έναν εξωτερικό υπολογιστή αριστερά, έναν δεξιά, και τον κεντρικό υπολογιστή στην κορυφή. Κάθε τρίγωνο έχει 3 συνδέσεις. Επάνω σε κάθε σύνδεση ρίχνουμε ανεξάρτητα ένα νόμισμα (πιθανότητα 1/2 να αφαιρεθεί).

Θέλουμε, στο τέλος, το δίκτυο να παραμένει πλήρως συνδεδεμένο. Παρατηρούμε ότι το δίκτυο χαλάει αν σε κάποιο τρίγωνο χαθούν τουλάχιστον δύο συνδέσεις:

• Αν χαθούν και οι τρεις συνδέσεις, και οι δύο εξωτερικοί αποκόπτονται πλήρως.
• Αν χαθούν δύο συνδέσεις, τότε είτε ένας εξωτερικός μένει τελείως απομονωμένος, είτε οι δύο εξωτερικοί συνδέονται μόνο μεταξύ τους αλλά όχι με τον υπόλοιπο κεντρικό υπολογιστή. Σε κάθε περίπτωση, κάποιοι υπολογιστές δεν μπορούν να επικοινωνήσουν με τους άλλους.

Άρα, για να παραμείνει συνδεδεμένο ολόκληρο το δίκτυο, σε κανένα από τα τέσσερα τρίγωνα δεν πρέπει να χαθούν 2 ή 3 συνδέσεις· δηλαδή, σε κάθε τρίγωνο πρέπει να χαθεί το πολύ μία σύνδεση.

Πιθανότητα σε ένα τρίγωνο

Σε ένα τρίγωνο, υπάρχουν 3 ανεξάρτητες συνδέσεις. Η πιθανότητα να χαθούν το πολύ μία είναι:

P(0 χαμένες) + P(1 χαμένη) = \(\binom{3}{0} \left(\frac{1}{2}\right)^3 + \binom{3}{1} \left(\frac{1}{2}\right)^3 = \frac{1}{8} + \frac{3}{8} = \frac{4}{8} = \frac{1}{2}.\)

Άρα κάθε τρίγωνο είναι «καλό» (το πολύ μία χαμένη σύνδεση) με πιθανότητα 1/2. Τα τέσσερα τρίγωνα είναι ανεξάρτητα, επομένως

P(όλα τα τρίγωνα καλά) = \(\left(\frac{1}{2}\right)^4 = \frac{1}{16}.\)

Και αυτή είναι ακριβώς η πιθανότητα ότι, μετά τη διαδικασία, όλοι οι υπολογιστές μπορούν να επικοινωνούν μεταξύ τους.

Σωστή απάντηση: (B) 1/16.

Computer Network Puzzle: Will the Network Stay Connected?

Problem

The diagram shows connections between several computers in a network. Every computer can send messages to any other computer, possibly relayed through some other computers. There is one central computer connected to 8 outer computers. The outer computers are arranged in 4 pairs, and each pair is connected by an extra link between the two machines. Thus the network consists of 4 triangles that all share the central computer.

For every connection in the network, a fair coin is flipped. If it lands heads, the connection stays; if it lands tails, the connection is removed. All flips are independent.

What is the probability that after this is done, every computer can still send messages to any other computer?

(A) 1/4096    (B) 1/16    (C) 3/32    (D) 81/256    (E) 91/128

Solution

The network is made of 4 congruent triangles, each with two outer computers and the central computer. Each triangle has 3 connections. We flip a coin on each connection independently.

The network fails to stay fully connected if, in some triangle, two or more connections are removed:

• If all three connections are removed, both outer computers are isolated.
• If exactly two connections are removed, then either one outer computer is completely isolated, or the two outers are connected only to each other but not to the rest of the network through the center.

So, for the entire network to remain connected, in every triangle at most one connection may be removed.

Probability for a single triangle

In one triangle, there are 3 independent edges. The probability that at most one of them is removed is

P(0 removed) + P(1 removed) = \(\binom{3}{0}\left(\frac{1}{2}\right)^3 + \binom{3}{1}\left(\frac{1}{2}\right)^3 = \frac{1}{8} + \frac{3}{8} = \frac{1}{2}.\)

Thus each triangle is “good” (loses at most one connection) with probability 1/2. The four triangles behave independently, so

P(all four triangles are good) = \(\left(\frac{1}{2}\right)^4 = \frac{1}{16}.\)

This is exactly the probability that the whole network remains connected.

Correct answer: (B) 1/16.