Country Connected By One Way Roads

Discrete Mathematics Level pending

The country of Indiapolis has \(2015\) towns. Each pair of towns is connected by a one way road, i.e. given any two towns \(A\) and \(B\), one can either directly travel from \(A\) to \(B\) or from \(B\) to \(A\) via that road but not both. A triple of towns \((A, B, C)\) is called good if one can directly travel from \(A\) to \(B\), then from \(B\) to \(C\), and then from \(C\) to \(A\). Let \(N\) be the maximum possible number of good triples of towns. Find the last three digits of \(N-280\).

Details and assumptions
- Each pair of cities are connected by exactly road.
- Traveling directly from city \(A\) to \(B\) means traveling from \(A\) to \(B\) via the road that connects them. The problem statement says that given two cities \(A\) and \(B\), one can either directly travel from \(A\) to \(B\) or from \(B\) to \(A\), but not both.
- You're not allowed to change roads when you're not in a city.
- This problem is not original.

×

Problem Loading...

Note Loading...

Set Loading...