Brain teasers

Not sure if software engineering is for you? If you enjoy solving complex problems then it just might be. Have a go at these brain teasers. Right or wrong, the important thing is that you relish having a go!


Pool table balls

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.

Puzzle 1 starting position

Figure 1: Correct starting arrangement

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.

Puzzle 1 alternative starting position

Figure 2: Alternative 'inverse' starting arrangement

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

Hint

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!

Puzzle 1 standard position solution

Solution

Answer 1

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.

Puzzle 1 standard position solution

Figure 3: Example of worst case arrangement requiring 8 swaps

Answer 2

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.

Puzzle 1 alternative position solution

Figure 4: Example of worst case starting arrangement requiring 4 swaps


Flight controller

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.

Hint

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?

Solution

The correct answer is: 10 cities.

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.

flights solution