Sunday puzzle 5: Solution

The plugs, between them, have three A connectors, 4 each of the B, C, D and E connectors and 5 F connectors. If we build a stack out of them all in the allowed way, then every junction between two adapters must contribute two copies of the same type of connection, so the number of connectors of a type not appearing at the top or bottom of the stack must be even. Since we have an odd number of A and F connectors it follows that at least one A connector and at least one F connector must appear at the ends of the stack. Since the ends cannot then be plugged together (as one would be an A connector, incompatible with the other, F, connector the stack could not form a ring. However this does not establish that such a stack can be formed, only that if it can it must have an A connector at one end, leaving two other A connectors in the middles somewhere, and an F connector at the other end, leaving two junctions each consisting of two F connectors somewhere else in the middle, and all the other connectors paired in a consistent way.

The easiest way to show this is possible is to exhibit a physically possible stack, for example:

A – D:D – C:C – B:B – F:F – C:C – E:E – B:B – D:D – F:F – E:E – A:A – F

Paging Euler

This puzzle can be framed in terms of graph theory, the mathematicians’ version of networks which are now central to real world problems in scheduling, security, computer and communications networks, transport planning and even social media (the infamous “Social graph” used to model interactions on Facebook et al). Each label is a node in a graph and each adapter is an edge joining the nodes which label its ends. Building a stack of adapters (or a ring) consists of choosing a path around the network which does not cross any edge twice. This constraint makes sure that we only use each adapter once in our construction. A stack (or ring) containing every adapter in our collection must cross every edge exactly once. This reminds us of Euler’s famous Koenigsburg bridge problem which is explained brilliantly on Ted-Ed. A path in a network which crosses every edge in the network exactly once is called an Eulerian path. If it also starts and ends in the same place it is called an Eulerian loop. It isn’t obvious, but turns out to be true, that a connected network has an Eulerian loop if and only every node in the network has an even number of neighbours, and has an Eulerian path if and only if either every node has an even number of neighbours or exactly two of the nodes have an odd number of neighbours!