Hosted by The Math Forum

Problem of the Week 923

Diameter 2 Airlines

_____________________________________________
MacPOW Home || Math Forum POWs || Search MacPOW
_____________________________________________

If a country has 25 towns, what is the smallest k such that a flight schedule connecting the towns can be set up so that:

  1. for each town A there are exactly k direct flights leaving A, and they go to k distinct towns;
  2. if there is no direct flight from A to B, there is a town C with flights from C to A and C to B.

Note:
In the original problem, from the Vietnamese Olympiad, flights go both ways. That is, if there is a flight from A to B then there is a flight from B to A and the underlying graph is undirected.

Another interesting problem is to consider the graph directed. Then part (b) should say: if there is no direct flight from A to B, there is a town C with flights from A to C and C to B.

Source: Vietnamese 1997 Olympiad Selection (in Crux Mathematicorum Sept 2000).
© Copyright 2000 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.

16 November 2000