Ponder This

October 1999

<<September October November>>

Ponder This Challenge:

Background and notation:
A "directed graph" consists of a collection of "vertices" {A,B,C,....} and "edges" {(B,C),...}.
An edge goes from one vertex to another: (B,C) goes from the source B to the destination C. There may or may not be another edge from C to B. In the present problem no edge will go from a vertex to itself (loops), nor will two edges have the same source and same destination (multiple edges).
A "path of length two" from B to C is a pair of edges (B,D) and (D,C) where the destination of the first edge is the source of the second.

Our particular directed graph has between 30 and 40 vertices, inclusive. For any two nodes B and C, there is either an edge (B,C) or exactly one path of length two from B to C, but not both.
This is true even if C=B: there is exactly one path of length two from B to B.

The question: How many vertices are in the graph?

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

  

Challenge: 10/01/99 @ 12:00 AM EST
Solution: 11/01/99 @ 12:00 AM EST
List Updated: 11/01/99 @ 12:00 AM EST

People who answered correctly:

Alamaru Krishal/Krishna (10.1.1999 @ 7:48 PM EST)
Lawrence T. Hoff (10.1.1999 @ 11:17 PM EST)
Aleksandar Basaric (10.2.1999 @ 6:13 AM EST)
Alan Nash (10.2.1999 @ 5:10 PM EST)
Jimmy Hu (10.4.1999 @ 2:28 AM EST)
Brett Maune (10.4.1999 @ 10:11 PM EST)
H.P.Ravikiran (10.8.1999 @ 10:23 AM EST)
John D. Valois (10.10.1999 @ 11:25 PM EST)
Mani Aulakh (10.11.1999 @ 5:24 AM EST)
David Radcliffe (10.12.1999 @ 6:49 PM EST)
David Morley (10.12.1999 @ 11:14 PM EST)
msk (10.15.1999 @ 12:04 PM EST)
"algor" (10.17.1999 @ 1:46 PM EST)
Meg Meek (10.17.1999 @ 5:14 PM EST)
Mihai Cioc (10.18.1999 @ 9:46 AM EST)
Ibrahim Okuyucu (10.21.1999 @ 12:43 PM EST)
Gundars Kokts (10.26.1999 @ 5:19 PM EST)
Ming-Wei Wang (10.26.1999 @ 6:16 PM EST)
Dave Biggar (10.28.1999 @ 10:11 AM EST)
Surender Baswana (10.28.1999 @ 5:21 AM EST)
Michael Moyer (10.30.1999 @ 4:43 PM EST)

Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.