Hosted by The Math Forum
Problem of the Week 969
Detecting a Black Hole
MacPoW Home ||
Forum PoWs ||
Teachers' Place ||
Student Center ||
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.
© Copyright 2002 Stan Wagon. Reproduced with
© 1994- The Math Forum at NCTM. All rights reserved.
Home || The Math Library || Quick Reference || Search || Help
30 October 2002