## Colombian Variant of Langford's Problem [DRAFT!]Here is a new variation of Langford's Problem -- TheColombian Variant. In this n=8 example, no complete pair smaller than 7 is inside the 7's. I.E. one or the other end of each pair [1..6] is outside the 7's. This Langford variant was cooked up by Bernardo Recamán Santos and Freddy Barrera in Bogotá, Colombia.
Here is a diagram that helps visualize pairings for a solution for n=8, where 7 is the
You can see that the numbers inside the 7's are all different: 1, 5, 4, 6, 3, 8, 2 ! ## Where did this idea come from?This is not an arbitrary or silly notion. Obviously, the 8's can't fit inside the 7's, and the 7's can't fit inside the 8's. While the 6's could fit inside the 8's, the 6's can't fit inside the 7's, and so on. This leads to the question - what if we look at cases where each pair other than 7 or 8 has one 'foot' inside the 7 pair and the other 'foot' outside? Investigating, Bernardo and Freddy found that there were such solutions, just as some classic solutions are planar while others are not. Freddy enumerated the variant up to 20! Exercise: Are there solutions such that all pairs smaller than n (rather than n-1), can have one of the pair in, the other out? If not, why not? Exercise: Is there a solution such that the pair of 1's (ie 1_1) are outside of the 7's, and yet the other constraints are met? If not, why not? ## When are solutions Feasible?Same as classic, when n is of the form 4k or 4k-1. Columbian Variant solutions are a subset of the solutions to the original problem.## EnumerationFreddy Barrera was first to do this. After the team contacted me, I wanted to independently confirm their results. My first impulse was to take my available sets of Langford solutions and filter for the ones that met the constraints. This immediately confirmed their results up to 12. (I used a perl script to check that there was only one of each number between the sentinels in each solution.)
Then I realized it should be easy hack the [Editorial note: I wondered if it might be possible that the two 1's are /both/ outside the sentinels. There are no doubt classic solutions like this, but those solutions probably have a pair of 2's or 3's inside the sentinels, and therefore not a CV.] ## Table of Number of SolutionsOEIS format:0, 0, 1, 1, 0, 0, 3, 10, 0, 0, 76, 140, 0, 0, 2478, 5454, 0, 0, 105704, 267312, 0, 0. 3 4 7 8 11 12 15 16 19 20 We must register this sequence on [OEIS]. Table format:
3 = 1 4 = 1 7 = 3 8 = 10 11 = 76 12 = 140 15 = 2478 16 = 5454 19 = 105704 20 = 267312 Missing entries are all zero values. ## NotationLet's use 'C(n)' to refer to the number of solutions for the Colombian Variant for given values of n, eg, C(16) = 5454. C(n) does not have the tuple value, since the variant is not defined for triplets, etc. That is, C(3,n) is undefined (meaningless?). I will add a 'C' column to the table on the main page ASAP. ## Other VisualizationsThis new ortho-graphic is mine, and can be done for any Langford solution, whether Colombian, Planar, or Classic. Inspired by the official logo for G4G14, by Scott Kim.
The above is a Colombian Variant solution for n=12, in pain text below: 7 10 12 9 6 4 2 11 7 2 4 6 10 9 8 12 5 3 1 11 1 3 5 8 There are 140 such solutions,i.e. C(12)=140. Without the Colombian constraint, there are 108144 solutions for L(2,12).
## Any Closing Remarks?Langford's Problem Home Page |