Skip to content
Get started

Directing links without a loop

EasyCombinatorics4 min

Five servers are joined by direct links between every pair of servers except one pair, AA and BB, which has no link, so there are 99 links. Each link is given a direction (data flows one way along it). Of the 29=5122^9 = 512 ways to direct the links, how many create no directed cycle?

Show hints (3)+
  1. With no directed cycle, the servers can be ranked so that every link points down the ranking.
  2. For a fully linked network the ranking is unique. What changes when AA and BB are not linked?
  3. Two rankings give the same directions only if they differ by swapping AA and BB while they sit next to each other.

Answer

Reveal answer →

96

Create a free account to see the full worked solution and track your progress.

Interview format: Prop Trading, Systematic & Data-Driven Trading

Related questions