brainbuster

back

return to brainbusters

enlarge image

Image 1: Office layout

the brainbuster

Please note: this competition is now CLOSED.

An engineer works in an office as laid out in Image 1.

There are a number of square rooms with corridors on the ouside and between them.

Every corridor is 10m in length. The engineer starts at point A and wants to walk down every corridor. What is the shortest continuous path that they can take?

Give your answer as the total length, and the route (eg AFKL etc).

the entries

Many thanks to all of you who entered the brainbuster.

This one again attracted a large number of entries.

As with exam papers, the advice is "read the question"... We asked for BOTH the total length AND the route, but several respondents answered only one part of the question. And we asked for the length walked, not the number of corridors.

Quite a few people gave the distance as 380m, and we also saw 370m, 350m, 310m and, somewhat bizarrely, 100m given.

Even though only about half of the entrants gave a completely correct solutions, there were a considerable number of right answers, with a variety of different possible routes. The winning entry was pulled out of the trusty ecm hat.

the solution

Here is the answer as provided by our winner:

Partition the nodes in the graph into sets;

X = {G, H, I, L, M, N},
Y = {B, C, D, F, J, K, O, Q, R, S},
Z = {A, E, P, T}

so that the set of all nodes is

X [union] Y [union] Z

And X, Y, Z are disjoint;

X [intersection] Y = { },
Y [intersection] Z = { },
Z [intersection] X = { }.

Then, referring to the graph, the nodes in;

X all have 4 arcs entering each node;
Y all have 3 arcs entering each node;
Z all have 2 arcs entering each node.

Assume that a solution exists for which each node is entered and left the least possible number of times(as will be shown).
Such a solution would pass along every path at least once, and would automatically be best possible.

In such a solution,

Each node in X will be entered twice and left twice, along different paths; Each node in Y will be entered once and left once, along different paths; then entered once and then left once down which one path has previously been passed; Each node in Z will be entered once and left once, along different paths.

Let S be the total number of times that nodes are entered and left in such a solution. One has that

S = 4.|X| + 4.|Y| + 2.|Z| = 72

Compute the length of the path corresponding to this optimal solution by reasoning that each path is shared between two nodes, and that each path is 10 metres in length;

Optimal path length = S/2 x 10 metres = 360 metres

Establish the existence of a solution by example; such an optimal path, beginning at A, is;

ABGLQRMHCDINSTOJEDCBAFGHIJONMLKFKPQRS

and the lucky winner is...

Congratulations to Adam Bach, a Mathematics graduate from the University of York, currently employed as a Software Development Engineer, who wins £200 of Firebox vouchers.

Many thanks again to all entrants - do try brainbuster no. 31!