Here is a new variation of Langford's Problem -- The Colombian 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 sentinel pair.
Colombian Variant, showing sentinel pair.
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.
Enumeration
Freddy 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 standard algorithm to extend the 'fit' test which checks to see if a pair fits into the arrangement. In addition to the pair of positions being vacant, I also checked that the two numbers in the pair would not both be contained (positioned) inside the two sentinels. I ran this hack and confirmed Freddy's result through 15.
[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.]
Let'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 Visualizations
This 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.
Crude initial drawing of CV for n=12 using the orthographic form, by John Miller, Dec 2019
The above is a Colombian Variant solution for n=12, in pain text below:
There are 140 such solutions,i.e. C(12)=140. Without the Colombian constraint, there are 108144 solutions for L(2,12).
A graphic of Colombian Variant Solution for 16, by Freddy Barrera
A number of Solutions for 11, by Freddy Barrera. Red added by JM to show guarded sections.
Cute drawing of the Trival solution for N=4, made with Open Office Draw -jm
