Solution to Puzzle Number 7

Here are the solutions to Puzzle Number 7: Molecular Tagging. To briefly recap, the object of the puzzle was to determine whether a set of four molecules of type A, which could form a single bond type with up to three other such molecules, was the most effective alphabet for molecular tagging, or whether it was instead a set of three molecules of type B, which could form up to two polar bonds (of opposite polarity) with up to two other B molecules. Scott successfully solved this puzzle, although there were some hiccoughs along the way as he and I hammered out the details of what I was exactly asking for (the hiccoughs in no way reflect badly on Scott's talents as a puzzle solver - they were all due to ambiguities in my puzzle writing). So, congratulations to Scott not only for solving the puzzle, but also for helping me work out improvements in the puzzle presentation.

The first stage in solving this puzzle is to move past the chemical presentation of the problem and recognize that it is really a combinatorics problem with two types of graphs. If each molecule is treated as a node in a larger network of molecules (networks of four nodes for type A and three nodes for type B), then the type A networks are undirected graphs and, due to the polarity of the bonds, type B networks can be viewed as directed graphs.

Type A network with all bonds

Type B network with all bonds

A cursory look at the graphs reveals that each has 64 total configurations (each bond can either be present or not and each graph has 6 bonds, yielding 2^6 = 64 configurations). However, there are two major constraints that are not taken into account by such a cursory examination: the graphs must be connected, and there is no vertex labeling, which means we must also eliminate graphs which are isomorphically the same (which basically means they are equivalent networks through some rotation, either of the whole network or about some of the bonds). Once all unconnected and isomorphically identical networks have been eliminated, we are left with a kind of molecular alphabet for each network type. As Scott pointed out in his solution, selecting between the alphabets requires the additional unstated assumption that the cost of bond activation and subsequent reading of the bond's presence and (if applicable) polarity is the same for each molecule type (an assumption which Scott pointed out was "a laughable claim indeed"... sometimes I think he's a little too clever for his own good). While Scott was correct that such an assumption might be stretching the bounds of what is a reasonable hypothetical problem, for the purposes of this puzzle we can assume those costs are negligibly different and concentrate on which molecular alphabet is capable of encoding more information.

While there may be an elegant way of mathematically determining the number of isomorphically distinct graphs with a set number of nodes, these networks are small enough that it is also possible to do an exhaustive analysis by hand. Doing such an analysis leads to the discovery that, despite an equal number of total graph configurations, the B networks have more than double the number of isomorphically distinct structures (there are six isomorphically distinct connected A networks and thirteen isomorphically distinct connected B networks). Thus, molecule B is the best choice for your company to invest in.

The six isomorphically distinct connected A networks

The 13 isomorphically distinct connected B networks