Hosted by The Math Forum

Problem of the Week 969

Detecting a Black Hole

MacPoW Home ||  Forum PoWs ||  Teachers' Place ||  Student Center ||  Search MacPoW

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.

Source: A quite well known problem, but nevertheless amusing to those who do not know it.