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

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.

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.

## 0 comments:

Post a Comment