At the beginning of a game of English pool, 7 yellow balls, 7 red balls and a black ball are arranged in a triangle in the pattern shown below. A wooden frame, known as the rack, is used to get the balls into the triangle formation before the game can start.

Before the game begins you place the balls at random into the rack. You then need to rearrange them to the formation above before the game can start. For the purposes of this brain teaser you can only rearrange the balls by choosing one pair of balls at a time, and swapping their positions. This action constitutes a swap. No other actions, such as three way cyclic moves, are allowed.

- What is the maximum number of swaps you would ever need to make to get the balls from a random starting position into the formation shown above?

Many players also consider the inverse arrangement of red and yellow balls to be a perfectly valid starting arrangement. This is shown below.

- What is the maximum number of swaps required to get from a random starting arrangement to either the ‘correct’ or the ‘alternative’ arrangement?

If you’re having trouble with the first part, try working out how many swaps would be needed to get the arrangement of balls shown below to the correct starting position. But you are on your own for the second part!

Assuming the worst possible arrangement where all the yellows are where the reds should be (and vice versa), with the added problem of the black ball being out of position. Such an arrangement is shown in Fig 3 below. You would require 1 swap to get the black into position and then 7 swaps to swap over the 7 pairs of reds and yellows. **Total: 8 swaps**.

Here's an example of the worst case arrangement requiring 8 swaps.

Previously it was possible for all reds and yellows to be out of position. But with the alternative arrangement it isn’t possible for more than half of all red and yellow balls to be out of position because if they’re out of position for one arrangement they are, by definition, in the correct position for the other arrangement. For example, Fig 3 shows something which is 8 swaps away from the ‘correct’ arrangement, but is only a single swap away from the ‘alternative’ arrangement.

The answer is that in the worst case a single swap is needed to get the black into position, followed by 3 swaps to get the remaining colours into one or other of the two arrangements. **Total: 4 swaps**.

Here's an example of a worst case starting arrangement requiring 4 swaps.

You are the owner of a small airline and you need to create an efficient network of flight paths to allow for the airline to expand. The cities in your region are all quite small, and each has only one airport which can allocate you space for flights to at most three other cities. The airport authorities also insist that all routes operate in both directions. In addition, your customers find more than one layover on a flight is completely unacceptable. Therefore, from any one city you must be able to connect to any other city with at most two flights.

- Given these constraints, how many cities can your airline connect to?
- Describe the flight network, or draw a diagram showing the connections.

Try thinking of the lower and upper bounds for the answer. Four cities arranged as three spokes from a central hub will clearly work, and you should be able to extend that network further. But as you keep adding cities, can you still draw a network that satisfies all the conditions?

It is relatively easy to see that 10 cities is the upper limit. Consider starting with a central hub, adding 3 spokes from there and 2 further cities joined to each spoke. You cannot try to add more cities beyond that as you will never be able to connect back to the central hub with just two flights.

So 10 cities is the upper limit on what is possible. Unfortunately the simplistic construction we used to come to that conclusion does not give a network diagram that satisfies the conditions. It is possible to draw one, though. Here’s how you can visualise the solution.

®

Metaswitch is the world’s leading cloud native communications software company. The company develops commercial and open-source software solutions that are constructively disrupting the way that service providers build, scale, innovate and account for communication services. By working with Metaswitch, visionary service providers are realizing the full economic, operational and technology benefits of becoming cloud-based and software-centric. Metaswitch’s award-winning solutions are powering more than 1,000 service providers in today’s global, ultra-competitive and rapidly changing communications marketplace.

Visit our careers website or email careers@metaswitch.com.

Join the Metaswitch Communities website for access to all our support features.

- If you have an urgent problem with a production system, call 24/7 support.
- If you have an issue with your Metaswitch products, check or raise a ticket.
- If you need to speak to a Metaswitch representative, contact support.

Send us a message or ask our Sales team for a quote

Email our Corporate Communications team or call +1 415 513 1500.

100 Church Street, Enfield, EN2 6BQ, UK

Tel: +44 20 8366 1177

Fax: +44 20 8363 1468

Get directions

Net Promoter, NPS, and the NPS-related emoticons are registered service marks, and Net Promoter Score and Net Promoter System are service marks, of Bain & Company, Inc., Satmetrix Systems, Inc. and Fred Reichheld.

Icons made by Freepik from www.flaticon.com.