Mr. P has friends in the following ten cities:
Bangalore (Karnataka, India)
Beechworth (Victoria, Australia)
Delta (Colorado, USA)
Flint (Michigan, USA)
Fort Collins (Colorado, USA)
Grand Junction (Colorado, USA)
Mobile (Alabama, USA)
Mountain View (Wyoming, USA)
Mumbai City (Maharashtra, India)
Pune (Maharashtra, India)
He wishes to set up airline service between the cities with the following restrictions:
For any two cities, A and B, you should be able to take a trip starting at A and visit all the other cities exactly once ending at B.
What is the smallest number of connections (between 2 cities) that is needed to accomplish this?
Extra Credit: If there were 1,001 cities instead of just ten, what is the smallest number of connections needed?
For example, if there were four cities A, B, C, and D.
You would need the following six connections: AB, BC, CD, DA, AC, and BD.
For cities A and B: A - C - D - B.
For cities A and C: A - B - D - C
For cities A and D: A - B - C - D
For cities B and C: B - A - D - C
For cities B and D: B - C - A - D
For cities C and D: C - A - B - D
Here is a picture of the six connections:
Solution to the Problem:
The answer to the problem of ten cities is 15 connections, and the answer to the extra credit of 1,001 cities is 1,502 connections.The problem was solved by both Colin Bowey and Kelly Stubblefield. Here is Colin's excellent solution:
Here is my 15 connect solution using two pentagons, a pentagon inside a pentagon connected together with one connection for each point,
or a pentagon based pyramid with the top cut off.
I'm fairly confident that the solution to the Extra credit for the minimum number of connections for 1,001 cities is 1,502.
To visualise the connections of larger numbers of cities, I found it easier to imagine it as a loop (or belt) made up of connected squares (each point or corner of a square has 3 connections).
If there is an even number of cities it is a simple loop of squares.
If there is an odd number of cities it is a loop (belt) of squares with a special bow shaped buckle made of two triangles that meet at a point (the extra / odd city) with four connections.
Each pair of cities added an even number of cities, requires 3 new connections.
If a single city is added to an even number of cities, it requires 2 new connections.
So therefore;
If number of cities is even, the minimum number of connections is = number of cities x 3/2.
If the number cities is odd the minimum number of connections = (( Number of cities - 1) x 3/2 ) + 2.
I'm fairly confident that the solution to the Extra credit for the minimum number of connections for 1,001 cities is 1,502.
To visualise the connections of larger numbers of cities, I found it easier to imagine it as a loop (or belt) made up of connected squares (each point or corner of a square has 3 connections).
If there is an even number of cities it is a simple loop of squares.
If there is an odd number of cities it is a loop (belt) of squares with a special bow shaped buckle made of two triangles that meet at a point (the extra / odd city) with four connections.
Each pair of cities added an even number of cities, requires 3 new connections.
If a single city is added to an even number of cities, it requires 2 new connections.
So therefore;
If number of cities is even, the minimum number of connections is = number of cities x 3/2.
If the number cities is odd the minimum number of connections = (( Number of cities - 1) x 3/2 ) + 2.
Here is Kelly's excellent diagram:
Mümtaz Keskin sent me a solution for the extra credit, so I included it below along with the diagram for ten cities:
Here are the solutions from those who were close to solving the problem (including mine):
Click here for Veena Mg's solution
Click here for Mr. P's solution
Click here for Colin Bowey's first solutions
Correctly solved by:
| 1. Colin (Yowie) Bowey | Beechworth, Victoria, Australia |
| 2. Kelly Stubblefield | Mobile, Alabama |
| 3. Mümtaz Keskin | Turkey |
Honorable Mention:
| 1. Veena Mg (20 connections) | Bangalore, Karnataka, India |
| 2. Colin (Yowie) Bowey (20 connections and 17 connections) | Beechworth, Victoria, Australia |
| 3. Mr. P (18 connections) | Fort Collins, Colorado |