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.

© Copyright 2002 Stan Wagon. Reproduced with permission.

[Privacy Policy] [Terms of Use]

_____________________________________
Home || The Math Library || Quick Reference || Search || Help 
_____________________________________

© 1994-2014 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Drexel University School of Education.The Math Forum is a research and educational enterprise of the Drexel University School of Education.


30 October 2002