It turns out today is the one year anniversary since I started writing this blog! I wasn't really sure I'd keep it up, but here it is a year and some 25 posts later, and I've still got a healthy standing reserve of about 6 more topics to get printed! Last year, my unofficial goal was two a month. I wonder if I can get my average up to 3 per this time around?

To celebrate, I've got another puzzle that turned into a much more aggressively analyzed problem than it'd ever need to be, which are one of my most favorite things to write about- This one concerns dandelions.

It might be disappointing to some people that this post isn't actually about flowers. But really, given the general tenor of this site, wouldn't it be more surprising if it were? In any case, this is another math puzzle post. In this one, we have a shape like this:

To celebrate, I've got another puzzle that turned into a much more aggressively analyzed problem than it'd ever need to be, which are one of my most favorite things to write about- This one concerns dandelions.

It might be disappointing to some people that this post isn't actually about flowers. But really, given the general tenor of this site, wouldn't it be more surprising if it were? In any case, this is another math puzzle post. In this one, we have a shape like this:

Doesn't it look like a dandelion?

Anyway, the idea is that there are 9 cells in total, with groups of three denoted by the lines linking cells. Additionally, we have the numbers 1 through 9. The goal is to place the numbers into the cells so that all cells on a straight line of three add up to the same value.

It might be a small or large intuitive leap, but it's reasonable to start by noting that it makes sense to pair the smallest and largest numbers in order- like 1 and 9, 2 and 8, etc. Since the middle will be added uniformly to all pairs of 2, if we can make all the satellite groups add up to the same value, then the middle can be anything. If we group repeatedly like this, then it's fairly easy to see that we'll end up with 5 as left over, naturally going to the middle, with all lines adding to 15:

Anyway, the idea is that there are 9 cells in total, with groups of three denoted by the lines linking cells. Additionally, we have the numbers 1 through 9. The goal is to place the numbers into the cells so that all cells on a straight line of three add up to the same value.

It might be a small or large intuitive leap, but it's reasonable to start by noting that it makes sense to pair the smallest and largest numbers in order- like 1 and 9, 2 and 8, etc. Since the middle will be added uniformly to all pairs of 2, if we can make all the satellite groups add up to the same value, then the middle can be anything. If we group repeatedly like this, then it's fairly easy to see that we'll end up with 5 as left over, naturally going to the middle, with all lines adding to 15:

Simple enough, right? However, there's more solutions, too. I'm going to ignore swapping satellite pairs radially. Symmetric solutions are usually pretty boring. Instead, let's look at other ways to shift the cells so that the sums themselves change.

We'll start by revisiting the notion that led us to placing 5 in the center in the original case- the fact that the center is added to all pairs, and thus is effectively removed from the algebraic considerations. Noting this, let's rearrange the cells to more casually represent the problem:

We'll start by revisiting the notion that led us to placing 5 in the center in the original case- the fact that the center is added to all pairs, and thus is effectively removed from the algebraic considerations. Noting this, let's rearrange the cells to more casually represent the problem:

On the left, the have a singular cell representing the central number, which is added to all sums. The columns of two that make up the remainder of the cells are the pairs which are added together along lines in addition to the center. We can see that if the sums along these columns are all the same value, then the puzzle in this form is solved, since the addition of the center cell is uniform:

Given that that is the case, we ought to be able to construct a solution for this puzzle for any set of pairs which contains 4 pairs which all sum to the same value. In any such case, that consumes 8 of the 9 options to fill cells, and the remaining option becomes the center cell. As such, we can note that we can shift the counting-ordered set as above in two ways to immediately gain solutions:

Looking at it this way, we're essentially taking the counting ordered set and shifting it into two partitioned groups of 4, with the remaining unallocated number, for all intents and purposes, ignored.

Looking at the three main solution dispositions we have, we see that we have three candidates: the middle number, and the first and last number. For each of these choices, we can see a clear pattern- they all allow pairing of elements sequentially. For example, when taking 9 as the center element, we can match the set {5,6,7,8} and {4,3,2,1}, which are both in sequential order. Consider, then, if we were to take 8 as the center. Then we must, at some point, find a match for 9. The very least pair sum possible would have 9 and 1 matched, adding up to 10. But then, when you go to pair 2, the only possible choice would be 8, which, of course, is not possible. If you were to pair 9 with any number but 1, you'd need to match 1, but since it's not matched with 9, and any sum with 9 must be greater than 10, there is no possible match for 1 that's consistent.

You can, of course, apply similar reasoning to other centers which do not leave consecutive sequences available. Consecutive sequences are immune to this sort of contradiction because the uniform change between elements in the two sets lets you match ascending and descending orders. This of course leads to the immediate opportunity for an extension, in that we can automatically solve a puzzle of this sort with any number of 'arms', by simply aligning matching ascending and descending sets. We know the prior reasoning holds, because the only way to divide the new, longer set into two equally long consecutive sets is to take the first, last, or middle element.

It's possible, then, to go even further. We can describe, generally, sets which satisfy the puzzle requirements with a generally relationship. In fact, we can even relax the relationship on the addition. Let's instead specify some general operation ⊕ which remits a set of well defined results on some set. Note that, in the spirit of addition in the original formulation, we want this operation to be symmetric, as the lines on which the additions occur are undirected. Though we might attribute some special 'orderedness' to the central element, it is fairly evident that symmetry of the outer lines in and group of three means that the ambiguity of the position of the central element lead to an implicit indication that the whole operation should be symmetric.

Now, we can redefine the puzzle in terms of correspondences of this function- we'll say a solution is one in which, for a set of size m = 2n + 1, we can select one central element c, and n many unordered pairs (p1,p2) such that p1 ⊕ c ⊕ p2 for all such pairs is equivalent, under whatever equivalency is defined on ⊕. To examine such a set to see if solutions exist within it, we must determine if such pairs exist and center exist. Because of the symmetry of ⊕, inherited from the structure of the puzzle, we can see that this simplifies down to the examination of p1 ⊕ p2, as we observed in the original puzzle case.

We can start by examining the operation table of p1 ⊕ p2, for all elements of the propositional set. Because each pair must 'add' to a common value, regardless of c, we can note that we must be able to find that value in a row and column set for all but one value, which shall become the center, when we find it. Note that the center may in fact have solutions states- e.g. there may be a case in which every single element pi. can find a matching element for some sum. Indeed, this is the case in the original puzzle, as we could pick any number 1-9 for initial inclusion, and derive a potential solution from that assumption.

One way we may approach this solution-identification technique is to start by selecting out from the operation table possible candidates for the sum. To get the idea how we can do this, let's start by looking at an example function table. Let's start by defining our operation:

Looking at the three main solution dispositions we have, we see that we have three candidates: the middle number, and the first and last number. For each of these choices, we can see a clear pattern- they all allow pairing of elements sequentially. For example, when taking 9 as the center element, we can match the set {5,6,7,8} and {4,3,2,1}, which are both in sequential order. Consider, then, if we were to take 8 as the center. Then we must, at some point, find a match for 9. The very least pair sum possible would have 9 and 1 matched, adding up to 10. But then, when you go to pair 2, the only possible choice would be 8, which, of course, is not possible. If you were to pair 9 with any number but 1, you'd need to match 1, but since it's not matched with 9, and any sum with 9 must be greater than 10, there is no possible match for 1 that's consistent.

You can, of course, apply similar reasoning to other centers which do not leave consecutive sequences available. Consecutive sequences are immune to this sort of contradiction because the uniform change between elements in the two sets lets you match ascending and descending orders. This of course leads to the immediate opportunity for an extension, in that we can automatically solve a puzzle of this sort with any number of 'arms', by simply aligning matching ascending and descending sets. We know the prior reasoning holds, because the only way to divide the new, longer set into two equally long consecutive sets is to take the first, last, or middle element.

It's possible, then, to go even further. We can describe, generally, sets which satisfy the puzzle requirements with a generally relationship. In fact, we can even relax the relationship on the addition. Let's instead specify some general operation ⊕ which remits a set of well defined results on some set. Note that, in the spirit of addition in the original formulation, we want this operation to be symmetric, as the lines on which the additions occur are undirected. Though we might attribute some special 'orderedness' to the central element, it is fairly evident that symmetry of the outer lines in and group of three means that the ambiguity of the position of the central element lead to an implicit indication that the whole operation should be symmetric.

Now, we can redefine the puzzle in terms of correspondences of this function- we'll say a solution is one in which, for a set of size m = 2n + 1, we can select one central element c, and n many unordered pairs (p1,p2) such that p1 ⊕ c ⊕ p2 for all such pairs is equivalent, under whatever equivalency is defined on ⊕. To examine such a set to see if solutions exist within it, we must determine if such pairs exist and center exist. Because of the symmetry of ⊕, inherited from the structure of the puzzle, we can see that this simplifies down to the examination of p1 ⊕ p2, as we observed in the original puzzle case.

We can start by examining the operation table of p1 ⊕ p2, for all elements of the propositional set. Because each pair must 'add' to a common value, regardless of c, we can note that we must be able to find that value in a row and column set for all but one value, which shall become the center, when we find it. Note that the center may in fact have solutions states- e.g. there may be a case in which every single element pi. can find a matching element for some sum. Indeed, this is the case in the original puzzle, as we could pick any number 1-9 for initial inclusion, and derive a potential solution from that assumption.

One way we may approach this solution-identification technique is to start by selecting out from the operation table possible candidates for the sum. To get the idea how we can do this, let's start by looking at an example function table. Let's start by defining our operation:

Note that this operation satisfies the prior prerequisites- it symmetric and well defined. Now, lets define a set over which it will act:

S = [1,3,5,7,9,11,13]

Then we can specify the operation table thus:

S = [1,3,5,7,9,11,13]

Then we can specify the operation table thus:

The 'X's down the main diagonal indicate that an element cannot be paired with itself. Now, from the structure of the problem, we must select out at least 2n of the 2n+1 total elements in the source set for pairing, the remaining element may become the center. We can look at the operation table and, for each possible output, record which inputs possess a match that can produce that value:

Looking at this table, we can observe that, for all possible outputs of the operation except 0, there is more than one 'hole' where an input lacks a suitable partner to sum to this value. 0, on the other hand, has exactly one hole, corresponding to pi = 5. We can say, then, that 0 is the only valid candidate for a solution sum ( Σ) in this setting, and that if there is a potential solution embedded with Σ = 0, then the 'center' (C) for that solution must be 5. Note that this sort of deduction is not always possible- there may be solution candidates for which all pi possess suitable mates. In that case, further deduction may be necessary to isolate solution sets, and specific sums may have more than one associated solution, including differing centers. We'll get to that later.

So, in this version of the puzzle, we have Σ = 0, and C = 5. That leaves us with the partial remaining set [1,3,7,9,11,13] to pair off. To this end, we write out, for each pi, the set of potential partners which ⊕ to Σ:

So, in this version of the puzzle, we have Σ = 0, and C = 5. That leaves us with the partial remaining set [1,3,7,9,11,13] to pair off. To this end, we write out, for each pi, the set of potential partners which ⊕ to Σ:

From these sets, we have a space which can be deductively searched for solutions. This particular case makes an interesting example because we have a set in which each pi has a plethora of mates available to it (center not withstanding, of course). In several example cases, we may have a collection of members which have only one potential pair, leading to radically reduced searching, either by truncating checks with a contradiction (for example, if 3 and 7 were to both ⊕ with only 1 to Σ, they cannot bot have 1, so there's not a solution in that case) or by allowing immediate reduction of possibilities.

In the current case, let's look at the deduction. We can start by trying to pair 1 and 3. We'll denote this match and remove 1 and 3 from the available candidates:

In the current case, let's look at the deduction. We can start by trying to pair 1 and 3. We'll denote this match and remove 1 and 3 from the available candidates:

Then, because it looks convenient, let's do 7 and 9 as a pair:

And the final pair, 11 and 13, is self-evident.

So, we've found a solution set: (1,3)(7,9)(11,13)5. However, as you may suspect, this is not the sole solution. In fact, there are 5 others, for 6 in total:

I. (1,3)(7,9)(11,13)5

II. (1,3)(7,11)(9,13)5

III. (1,7)(3,9)(11,13)5

IV. (1,7)(3,11)(9,13)5

V. (1,13)(3,9)(7,11)5

VI. (1,13)(3,11)(7,9)5

All of which can be determined by a deductive space search on the sets of candidates.

Just for an alternative case, let's now look at a different case:

a ⊕ b = a +b

S = [1,2,3,4,5,6,7]

In this case, we get the following operation table:

So, we've found a solution set: (1,3)(7,9)(11,13)5. However, as you may suspect, this is not the sole solution. In fact, there are 5 others, for 6 in total:

I. (1,3)(7,9)(11,13)5

II. (1,3)(7,11)(9,13)5

III. (1,7)(3,9)(11,13)5

IV. (1,7)(3,11)(9,13)5

V. (1,13)(3,9)(7,11)5

VI. (1,13)(3,11)(7,9)5

All of which can be determined by a deductive space search on the sets of candidates.

Just for an alternative case, let's now look at a different case:

a ⊕ b = a +b

S = [1,2,3,4,5,6,7]

In this case, we get the following operation table:

Which can be cast to the following, indicating included potential sum candidates:

From which we can identify the following valid center candidates:

The possibilities are Σ = 7, 8, or 9; with C = 7, 4, or 1, respectively. This result is coherent with our observations from the original puzzle- the center for an arithmetically consecutive set will be the end, middle, or first element. Additionally, this construction illustrates more cleanly why our sums possessed such clean relationships: in the normal arithmetic case, the inclusion chart will always bear this symmetry.

For a final example, I want to use the case of the following:

a ⊕ b = a + b mod 6

S = [1,2,3,4,5,6,7,8,9]

Here, rather than offer up the whole operation table, I want to show the deduction for a specific sum- Σ = 2. If you were to examine the table, you would find that it has exactly 1 hole, corresponding to C = 4, and the following set of match options:

For a final example, I want to use the case of the following:

a ⊕ b = a + b mod 6

S = [1,2,3,4,5,6,7,8,9]

Here, rather than offer up the whole operation table, I want to show the deduction for a specific sum- Σ = 2. If you were to examine the table, you would find that it has exactly 1 hole, corresponding to C = 4, and the following set of match options:

So, we can see immediately that we have the following pairs: (1,7)(2,6)(3,5), because they're all singular pairs. We can then mark these elements off the list:

And run straight into a wall: 8 and 9 both remain, but possess no unclaimed potential mates, but as the last two unpaired elements, ought to match o one another. However, we can see right away that this is untenable: 8+9 mod 6 = 5. So, in this case, even though we can find precisely 2n potential matches and one oddball for the center, we do not have a solution (for Σ = 2, if you examine the full space of options, it turns out that 0-5 all have either 2n+1 or 2n potential matches, and so are all candidates, but that Σ = 0, 1, or 2 remit no solutions, and Σ = 3, 4, or 5 remit 4, 2 and 4 each, respectively).

That prompts us to ask the question, can we readily determine a) whether or not there exists a solution (either for a given Σ, or for any Σ) and b) how many solutions exist within a given space. The first insight along this road (aside from acknowledging that we could make a searching sweep of the whole space to answer both questions, but would prefer a more analytic approach) is to note that, although we have been using numerical inputs and outputs, we can eliminate the numerical functionality and regress to abstract functions, as the only requirements are the symmetric and well-definition of the function. As such, we'll be examining 'cases' far more abstractly from here on out.

Let's take a look at how we're going to approach this- we'll start by divorcing the inputs from the outputs. We decided early on that we could define the operation any way we liked, so long as it was symmetric, so there's no imperative to require the input be of the same type as the output. To that proposition, we'll be looking at more generalized functions for the most part, such as the following:

That prompts us to ask the question, can we readily determine a) whether or not there exists a solution (either for a given Σ, or for any Σ) and b) how many solutions exist within a given space. The first insight along this road (aside from acknowledging that we could make a searching sweep of the whole space to answer both questions, but would prefer a more analytic approach) is to note that, although we have been using numerical inputs and outputs, we can eliminate the numerical functionality and regress to abstract functions, as the only requirements are the symmetric and well-definition of the function. As such, we'll be examining 'cases' far more abstractly from here on out.

Let's take a look at how we're going to approach this- we'll start by divorcing the inputs from the outputs. We decided early on that we could define the operation any way we liked, so long as it was symmetric, so there's no imperative to require the input be of the same type as the output. To that proposition, we'll be looking at more generalized functions for the most part, such as the following:

In this function, we've taken the input and represented it as a set of characters- a through f, and the output by integers, 0 to 4. Note that these numbers do not necessarily mean the actual number, they are symbolic. We could replace them with Greek characters, for instance. Numbers are just easier to write and type.

Now, we recognize two general facts about the operations tables at this point. First, the actual values in the table are inconsequential, only the relationship among them is important (i.e. if we replaced 1 with α). Second, the order in which the elements are listed is similarly unimportant: so long as the function is preserved, we are free to rearrange rows and columns, and the table will remain valid. For instance, we can alter the above instance by swapping the positions of c and d, to acquire this altered table:

Now, we recognize two general facts about the operations tables at this point. First, the actual values in the table are inconsequential, only the relationship among them is important (i.e. if we replaced 1 with α). Second, the order in which the elements are listed is similarly unimportant: so long as the function is preserved, we are free to rearrange rows and columns, and the table will remain valid. For instance, we can alter the above instance by swapping the positions of c and d, to acquire this altered table:

on which all relationships are identical, but the precise layout is different. We can rearrange it to our hearts content, and it will still represent the same function.

With that in mind, let us now look at an arbitrary puzzle. We'll draw from the set {a, b, c, d, e, f, g}, but the same reasoning applies to all set sizes, and variance among sets is assumed, without loss of generality. Then say we have, for a given (unspecified) operation, a solution:

S = (a,d)(b,e)(c,f)g

Σ = ΣS

We can make a mostly vacuous, but notable point; we know what some of the entries on the table must be:

a ⊕ d = ΣS

b ⊕ e = ΣS

c ⊕ f = ΣS

The remainder of the entries are unknown- including for g, which my have plenty of matches to ΣS, but this single solution allows us insight into only the 6 pairs. It was noted earlier that there is no harm in arranging input order on the table however we please, and so we can freely choose to consider the product with the following set order: [a,d,b,e,c,f,g], resulting in the following partial table:

With that in mind, let us now look at an arbitrary puzzle. We'll draw from the set {a, b, c, d, e, f, g}, but the same reasoning applies to all set sizes, and variance among sets is assumed, without loss of generality. Then say we have, for a given (unspecified) operation, a solution:

S = (a,d)(b,e)(c,f)g

Σ = ΣS

We can make a mostly vacuous, but notable point; we know what some of the entries on the table must be:

a ⊕ d = ΣS

b ⊕ e = ΣS

c ⊕ f = ΣS

The remainder of the entries are unknown- including for g, which my have plenty of matches to ΣS, but this single solution allows us insight into only the 6 pairs. It was noted earlier that there is no harm in arranging input order on the table however we please, and so we can freely choose to consider the product with the following set order: [a,d,b,e,c,f,g], resulting in the following partial table:

Which possesses and immediately notifiable pattern, better expressed visually than linguistically:

Sums of the given solution state arranged along alternating one-off-diagonal slots in the table. Because of the generality of our approach, we can now make the following statement: If there is a solution for a given operation, the we must be able to re-align the order of the elements in the source set such that the product table bears this pattern. A consequent result of this is that if one cannot form such a pattern, then no solution exists.

Further, let's begin with a similar, but certainly different partial chart:

Further, let's begin with a similar, but certainly different partial chart:

In this case, we have the same pattern as above, but do we have a solution based just on this table? In fact, we do- the structure reflects back, and from this table organization, we can pull an associated solution:

S = (a,f)(b,d)(c,g)e

At this point, we have two theorems, essentially: the existence of a solution implies that one can construct a table fitting the above pattern, and the existence of a patter implies the existence of a solution. Therefor, we can conclude that a solution exists if and only if we can arrange the table so that it fits this pattern.

This is an interesting structure, however, we can identify an even better one- say we've got the solution (a,g)(b,f)(c,e)d, so that:

S = (a,f)(b,d)(c,g)e

At this point, we have two theorems, essentially: the existence of a solution implies that one can construct a table fitting the above pattern, and the existence of a patter implies the existence of a solution. Therefor, we can conclude that a solution exists if and only if we can arrange the table so that it fits this pattern.

This is an interesting structure, however, we can identify an even better one- say we've got the solution (a,g)(b,f)(c,e)d, so that:

Then, we can take this table and, as we've been doing, reorganize it. This time, rather than align matches by one another, we set each solution pair at opposite ends of the list, with the 'center' element in the middle position. Thus, (a,g)(b,f)(c,e)d becomes {a,b,c,d,e,f,g} (a tidy choice on my part), and the resulting table is:

Which is quite an auspicious form. Additionally, since we began with the original structure, and merely rearranged the order of the elements, per our prior theorem regarding the existence of a solution, a solution exists if and only if the function contains an embedding of this pattern as well. This suggests a first method of both identifying the existence of solutions and identifying the solutions themselves.

If we were to make up a set of all possible reorganizations of these two tables- the minimal embedding necessary for a solution to exist- and then overlay those isomorphic embeddings on the selected function, we would be able instantly to read off a solution if such exists corresponding to that form of the embedding. That's a little bit of an abstruse way of putting it, so let's be a little more clear.

First, we find all possible organizations of this minimal embedding. Note that we need not consider versions of the function with more ΣS, as the diagonal is the minimal- adding more may increase the number of solutions, but they will be caught independently by the overlapping version of the minimal rule which corresponds to the 'additional' ΣS positions. Once we have this set of all possible solution organizations, we can overlay them with the operation chart, and note than any overlay which highlights a group of common ΣS as a solution organization, with the reversal of whatever transformation generated the overlay converting the initial ordering to the solution order.

At first brush, this may seem like a combinatorially difficult problem, given that we are essentially generating the set of all possible organizations of the input set, with a given rule. However, we have a few major things going for us- thing one is that swapping any set of 'matched' pairs' elements results in identical conformation. Likewise, taking and pair in a give organization (even if separated) and swapping it for another pair also gives the same sorting. If we recall that we had m = 2n+1 elements in the set, or n pairs with 1 extra left out element, then we have an immediate overlap which reduces the number of possible configurations (m!) by 2n and n!, respectively. The remaining number can still be considerably large, especially for large m, but it is less problematic than it initially seems.

Another way to look at this calculation is to notice that we will have a total of (m2 - m)/2 product slots to fill (the area of a triangular half below or above the main diagonal, since the table is reflected about the identity line). Converting this via m = 2n+1, we get (n2 + n)/2. From there, we have n many slots we need to fill, for a total space size of:

(n2 + n)x(n2 + n -2)x(n2 + n - 4)x... x(n2 - n)/(2n)

though not all of these possible arrangements are solutions, necessarily, so this is an upper bound for the search. Still not very comforting in scope.

However, there is an alternate perspective that can assist us in this analysis- we can take a new representation from this table by considering entries which match the currently examined sum ΣS to be marks on a connectivity table, thereby recasting each set of potential sums as a graph. In this new formulation, what we want to do is find a set of pairs (vivj) within the graph which all share an edge, and which are all independent of one another (and allowing for one extra node as the center). Essentially, the problem becomes one of decomposing the graph into a set of subgraphs: n many of size 2, and one of size 1.

For a tree, this is very simple to do. A tree can be decomposed by starting with the leaves, which have order 1. As such, they have exactly one possible match, so if a solution exists, the leaf must be paired with its sole connecting member. We can then truncate from the tree all leaves and their neighbors. At this point, we can check to see if there is more than one node which has, due to removing the given pairs, been rendered to order 0. We will refer to these singular nodes as being 'orphaned' by the pruning process. Thus, if we have two or more orphaned nodes, there cannot be a solution embedded in the graph. We can accommodate exactly one orphan by making it the center, however, and will, for any appropriate input set (i.e. an odd number of inputs, matching the puzzle) have at least one orphan for the center from any pairing process.

The ease with which trees are partitioned in this way leads us to wonder if we might be able to extract a tree from any graph which will contain a pairing solution if one exists. That is to say, we would like to be able to generate a spanning tree from a graph which will always contain a solution if the original graph contains a solution. We'll focus on connected components, because we can look at each individually, an establish a total solution if we find exactly one orphan among all components.

The first step in approaching that problem is to establish that such a tree exists in the first place. To do so, we begin by assuming a solution (we want to prove the existence of a tree containing the solution), by doing so, we can infer that there exists a set of subgraphs which are the paired elements connected only to their mate, and one orphaned node, as below, embedded in the full graph G:

If we were to make up a set of all possible reorganizations of these two tables- the minimal embedding necessary for a solution to exist- and then overlay those isomorphic embeddings on the selected function, we would be able instantly to read off a solution if such exists corresponding to that form of the embedding. That's a little bit of an abstruse way of putting it, so let's be a little more clear.

First, we find all possible organizations of this minimal embedding. Note that we need not consider versions of the function with more ΣS, as the diagonal is the minimal- adding more may increase the number of solutions, but they will be caught independently by the overlapping version of the minimal rule which corresponds to the 'additional' ΣS positions. Once we have this set of all possible solution organizations, we can overlay them with the operation chart, and note than any overlay which highlights a group of common ΣS as a solution organization, with the reversal of whatever transformation generated the overlay converting the initial ordering to the solution order.

At first brush, this may seem like a combinatorially difficult problem, given that we are essentially generating the set of all possible organizations of the input set, with a given rule. However, we have a few major things going for us- thing one is that swapping any set of 'matched' pairs' elements results in identical conformation. Likewise, taking and pair in a give organization (even if separated) and swapping it for another pair also gives the same sorting. If we recall that we had m = 2n+1 elements in the set, or n pairs with 1 extra left out element, then we have an immediate overlap which reduces the number of possible configurations (m!) by 2n and n!, respectively. The remaining number can still be considerably large, especially for large m, but it is less problematic than it initially seems.

Another way to look at this calculation is to notice that we will have a total of (m2 - m)/2 product slots to fill (the area of a triangular half below or above the main diagonal, since the table is reflected about the identity line). Converting this via m = 2n+1, we get (n2 + n)/2. From there, we have n many slots we need to fill, for a total space size of:

(n2 + n)x(n2 + n -2)x(n2 + n - 4)x... x(n2 - n)/(2n)

though not all of these possible arrangements are solutions, necessarily, so this is an upper bound for the search. Still not very comforting in scope.

However, there is an alternate perspective that can assist us in this analysis- we can take a new representation from this table by considering entries which match the currently examined sum ΣS to be marks on a connectivity table, thereby recasting each set of potential sums as a graph. In this new formulation, what we want to do is find a set of pairs (vivj) within the graph which all share an edge, and which are all independent of one another (and allowing for one extra node as the center). Essentially, the problem becomes one of decomposing the graph into a set of subgraphs: n many of size 2, and one of size 1.

For a tree, this is very simple to do. A tree can be decomposed by starting with the leaves, which have order 1. As such, they have exactly one possible match, so if a solution exists, the leaf must be paired with its sole connecting member. We can then truncate from the tree all leaves and their neighbors. At this point, we can check to see if there is more than one node which has, due to removing the given pairs, been rendered to order 0. We will refer to these singular nodes as being 'orphaned' by the pruning process. Thus, if we have two or more orphaned nodes, there cannot be a solution embedded in the graph. We can accommodate exactly one orphan by making it the center, however, and will, for any appropriate input set (i.e. an odd number of inputs, matching the puzzle) have at least one orphan for the center from any pairing process.

The ease with which trees are partitioned in this way leads us to wonder if we might be able to extract a tree from any graph which will contain a pairing solution if one exists. That is to say, we would like to be able to generate a spanning tree from a graph which will always contain a solution if the original graph contains a solution. We'll focus on connected components, because we can look at each individually, an establish a total solution if we find exactly one orphan among all components.

The first step in approaching that problem is to establish that such a tree exists in the first place. To do so, we begin by assuming a solution (we want to prove the existence of a tree containing the solution), by doing so, we can infer that there exists a set of subgraphs which are the paired elements connected only to their mate, and one orphaned node, as below, embedded in the full graph G:

Because we are examining connected components, we can identify that some set of paths exists between all these subgraphs which exist outside the set of edges illustrated above:

The red lines, of course, just one hypothetical such collection, but you get the point. From this illustration we can see that, because the graph is connected, and because we can find the subgraphs illustrated when there is a solution, we also have a connected graph when we contract all pairs to one node each:

Now, since this new contracted graph is connected, it will have a tree containing all the contracted nodes:

This tree has, by definition, n edges (G possessed 2n+1 nodes, 2n of those were contracted to n many, for n+1 nodes, and a tree has exactly one less edge than nodes). Now, if we return the contracted nodes to their prior state, we add in only edges which were between paired nodes, of which there was one per pair, or n many. Consequently, the newly un-contracted graph will have 2n edges total, which is one less than the number of nodes (2n+1, same as G) and is therefor, unambiguously, a tree as well as an embedded subgraph of G. Thus, if there is a solution, S, in G, there will be a tree (T) which contains that solution. Consequently, because T is known to contain a solution by pruning this tree, we will obtain a solution, as the pruning process is certain, by deduction, to extract a solution from a tree which contains one.

Note that such solutions are not necessarily unique, as we are allowed at least one orphan, but may at some point have to choose between different choices for orphaning. For instance:

Note that such solutions are not necessarily unique, as we are allowed at least one orphan, but may at some point have to choose between different choices for orphaning. For instance:

We can readily identify 2 solutions for this graph:

Both are valid pruning solutions, but depend on whether we include d or e as the orphan. Another important observation here is that if we decide, on a tree, to include a given leaf, it will have a specific partner. This is a direct result of the fact that leaves have order of one. This same reasoning applies to newly formed leaves after each round of pruning occurs, meaning that each round is a process of grounded deduction, ensuring that a solution will be extracted if it exists, which leaves us only the task of finding this tree in order to prune it.

One way to search for such a tree is to consider organizations of G by including and excluding the various member edges in the graph, and analyzing the resultant graphs by pruning. Lets look at the complexity if we approach it this way. In the original graph of m nodes, we have at most m(m-1)/2 edges, which would mean (√2)m(m-1) total binary inclusions possible. However, we only want to examine trees, which means that every subgraph we examine must have m-1 (2n) edges. We can thus reduce the total complexity by noting that we need only fill in edges until we have m-1 full. This means that we can selectively include edges until we have m-1 of them, then check. The end result of this procedure will yield us a combination set bounded by:

((m2 - m)/2) x ((m2 - m)/2 - 1) x ((m2 - m)/2 - 2) x ... x ((m2 - m)/2 - (m-2))

= ((m2 - m)/2) x ((m2 - m - 2)/2) x ((m2 - m - 4)/2) x ... x ((m2 - m - 2(m-2))/2)

= (m2 - m) x (m2 - m - 2) x (m2 - m - 4) x ... x (m2 - 3m + 4))/(2m-1)

which is fairly large, but is certainly less than (√2)m(m-1), because it excludes numbers of edges less than and greater than m-1, and considerably less than other combinatorial methods we've looked at. And what's more, there are a couple of additional savings: first, this is only for a complete graph segment, in general, we will have a more sparse graph, of say k edges, which will instead have a number of cases given by:

(k) x (k - 1) x (k - 2)x ... x(k - m + 2), or

k!/(k - m + 1)!

which is, naturally, the number of combinations for placing m-1 many items in k bins. This is a radical improvement over the previous attempts, but we would still like to do better, since this is a combinatorial problem, though a reduced one.

One question we might ask ourselves, in pursuit of greater efficiency, is how to determine in advance of searching for a solution whether or not one exists. To this point, we can look back at the function graphs we used in examining the permutations of the ancillary graph connectivity function. Lets say we we write the array as a binary matrix, such that the main diagonal is labeled with ones, as are all entries which sum to the desired Σ. Then, the embedded form we want will be represented as:

One way to search for such a tree is to consider organizations of G by including and excluding the various member edges in the graph, and analyzing the resultant graphs by pruning. Lets look at the complexity if we approach it this way. In the original graph of m nodes, we have at most m(m-1)/2 edges, which would mean (√2)m(m-1) total binary inclusions possible. However, we only want to examine trees, which means that every subgraph we examine must have m-1 (2n) edges. We can thus reduce the total complexity by noting that we need only fill in edges until we have m-1 full. This means that we can selectively include edges until we have m-1 of them, then check. The end result of this procedure will yield us a combination set bounded by:

((m2 - m)/2) x ((m2 - m)/2 - 1) x ((m2 - m)/2 - 2) x ... x ((m2 - m)/2 - (m-2))

= ((m2 - m)/2) x ((m2 - m - 2)/2) x ((m2 - m - 4)/2) x ... x ((m2 - m - 2(m-2))/2)

= (m2 - m) x (m2 - m - 2) x (m2 - m - 4) x ... x (m2 - 3m + 4))/(2m-1)

which is fairly large, but is certainly less than (√2)m(m-1), because it excludes numbers of edges less than and greater than m-1, and considerably less than other combinatorial methods we've looked at. And what's more, there are a couple of additional savings: first, this is only for a complete graph segment, in general, we will have a more sparse graph, of say k edges, which will instead have a number of cases given by:

(k) x (k - 1) x (k - 2)x ... x(k - m + 2), or

k!/(k - m + 1)!

which is, naturally, the number of combinations for placing m-1 many items in k bins. This is a radical improvement over the previous attempts, but we would still like to do better, since this is a combinatorial problem, though a reduced one.

One question we might ask ourselves, in pursuit of greater efficiency, is how to determine in advance of searching for a solution whether or not one exists. To this point, we can look back at the function graphs we used in examining the permutations of the ancillary graph connectivity function. Lets say we we write the array as a binary matrix, such that the main diagonal is labeled with ones, as are all entries which sum to the desired Σ. Then, the embedded form we want will be represented as:

Now, lets assume we have the precise minimum number of sums required for a solution within such a connectivity matrix. Then we have precisely a matrix with zeros in all cells not on the two diagonals:

Now, because this matrix will be subject to constraints based on the puzzle terms, we can make a couple observations. First, we note that the determinant of such an array is 0. Earlier, we established a rule that we may retain a valid connectivity array by symmetric movement of corresponding rows and columns. Consequently, any reordering of the elements of the solution space will leave the determinant of the connectivity array unchanged, as swapping a pair of rows or columns in a matrix inverts the sign of the derivative, and each reordering of the list results in a pair of swaps. Therefor, any connection array which has the minimum number of links required for a solution must have determinant zero, as it can be permuted into the prototypical array above.

This provides a potential reducing test for us- though there may be (and in fact, are) insoluble groups whose determinant is zero, if the determinant is not zero, then the list as posed is definitely not soluble. While this notion is fairly interesting in its own right, the far more salient point for me was the observation that this kind of test structure may be more effective in certain situations- selecting out n many of the connections and checking to see if they are a valid choice. Indeed, it comes to light on observation that if we have n connections, then writing out the set of connected pairs is equivalent to checking the solution- all elements should be directly paired with their match, and there should be one orphaned node only. Essentially, counting the number of 1-node trees in the graph is equivalent to verifying the solution.

What this means is that we can instead cycle through sets of selections from the complete connectivity graph, which has all valid connections listed, by selecting out n many of the candidate connections at a time, and computing the pairing list of the array for those selections. The selection of edges for inclusion prevents an exhaustive search of isomorphic configurations. The net result is that if you have k many connections total, then you need only check k!/(k - n/2)! cases, which may be considerably faster than the previous versions, depending on the ratio of connections to elements in the list. Because the identification of a solution when the n many selections are known is trivial, this approach finds solutions just as easily as positive identification of answers.

Going forward, I have a sneaking suspicion that this check can be extended to determine, without selecting out the minimum number of connections, whether there is an embedded pairing or not within a function. I believe that soluble arrays may always have positive or 0 determinants, but have as yet been unable to prove this conclusively, or find counter examples. Ideally, I'll be able to construct a proof using addition of minimal cases to do so. We'll have to see if I get that solved in the next year!

What this means is that we can instead cycle through sets of selections from the complete connectivity graph, which has all valid connections listed, by selecting out n many of the candidate connections at a time, and computing the pairing list of the array for those selections. The selection of edges for inclusion prevents an exhaustive search of isomorphic configurations. The net result is that if you have k many connections total, then you need only check k!/(k - n/2)! cases, which may be considerably faster than the previous versions, depending on the ratio of connections to elements in the list. Because the identification of a solution when the n many selections are known is trivial, this approach finds solutions just as easily as positive identification of answers.

Going forward, I have a sneaking suspicion that this check can be extended to determine, without selecting out the minimum number of connections, whether there is an embedded pairing or not within a function. I believe that soluble arrays may always have positive or 0 determinants, but have as yet been unable to prove this conclusively, or find counter examples. Ideally, I'll be able to construct a proof using addition of minimal cases to do so. We'll have to see if I get that solved in the next year!