Motto: Înţteleptul îţi comunică o idee, omul obişnuit vorbeşte despre întâmplări, iar prostul îţi spune ce-a mâncat (proverb mongol)
C. Detectarea unei găuri negre
Să considerăm o reţea cu 26 noduri notate A, B, ..., Z, şi un sistem de comunicaţie care permite trimiterea de mesaje de la nodul i la nodul j, pentru o mulţime fixată de perechi (i,j).
Pentru orice pereche (i,j) se poate determina – cu o singură întrebare – dacă este posibilă comunicarea de la i la j.
Construiţi o procedură care să determine dacă sistemul are (cel puţin) o gaură neagră: un nod cu proprietatea că oricare alt nod poate trimite mesaje la el, dar de aici nu se pot trimite mesaje la nici un alt nod.
Condiţia de bază este ca numărul de întrebări să fie minim (pentru cel mai nefavorabil caz).
O modalitate simplă (forţă brută) de a verifica dacă A este gaură neagră solicită maxim 50 întrebări (25 întrebări pentru un sens, 25 pentru sensul opus). Deci, pentru toată reţeaua, o decizie ar necesita până la 26*50=1300 întrebări.
Sursă: Macalestear POTW 969.
Logic
Detecting a Black Hole
Imagine a network of 26 nodes, A, B, ..., Z, and a communications system that allows messages to be sent from node i to node j for only some of the pairs i and j. For any pair i, j you can, with one query, learn whether direct communication from i to j is possible. Devise a procedure to determine whether the system has a black hole: a node such that every other node can send messages directly to it, but it cannot send messages to any other node. The idea is to minimize the number of queries (in the worst case).
An obvious way is to check by brute force whether A is a black hole; it might take 50 queries to discover that it is not. Continuing in this way might require 26*50, or 1300, queries to resolve the issue.