A pairing that is not a symmetry

A pairing strategy is the cheapest argument in the subject. Pair up the free squares, answer every move with its partner’s, and the second player never runs out of replies — so the position is a second-player win, with no search and no value computed. The strategy that is a symmetry is where this ladder starts, and the seven rungs since have been a long argument about what a pairing has to satisfy.

The requirement, in the form the ladder settled on, is three clauses: an involution on the free squares, with no fixed square and no domino meeting its own image. Every one of them is a statement about a permutation. Not one of them mentions the board.

A symmetry that is not a pairing closed on exactly that gap:

Every map this ladder has tried is a rigid motion of the rectangle, and the requirement … mentions nothing of the kind. A position could have a pairing that is not geometric: an arbitrary involution on its free squares, found by search rather than read off the shape.

It could, and 63 shapes to ten cells do.

What the wider search is #

The narrow search takes the eight maps of the square, keeps the ones carrying the shape to itself, and tests the three clauses on each. The wider one skips the first two steps: it enumerates every fixed-point-free involution of the cells and tests the same three clauses on each, unchanged.

The clauses being unchanged is what makes the two counts comparable, and it is worth insisting on. A pairing found by the wider search is a pairing in exactly the sense the ladder has been using for seven rungs — the same test, on more candidates.

What a permutation passing them turns out to be is a fact worth having in advance. The second clause says every domino has an image and the third says no domino is its own; together they say the map carries edges of the adjacency graph to edges. A bijection that preserves edges and is its own inverse preserves non-edges too, so it is an automorphism of the adjacency graph. That is the whole of why a non-geometric pairing is possible: a shape’s adjacency graph can be more symmetric than the shape.

That distinction is easy to state and easy to underrate, because on the shapes this subject usually draws it is empty. A rectangle’s adjacency graph has exactly the symmetries the rectangle has, which is why Cram can be taught entirely on rectangles without the question ever arising, and why seven rungs of this ladder could search eight maps without anybody noticing that the requirement asked for more. The graph and the drawing come apart only when the shape is irregular enough that two squares play the same role in the adjacency pattern without sitting in mirror-image places on the board — and irregular shapes are exactly what a played game produces. A Cram position after four moves is not a rectangle.

And the strategy the map licenses is the same strategy. Answer each move with the image of the domino just played. The three clauses are what make that reply always available: the position stays invariant under the map after every one of the second player’s turns, the image of a legal domino is a domino, and it is a different domino from the one just played. Nothing in the argument consults the geometry, which is the point — the argument was never about geometry, and this ladder’s search was.

The answer to the rung below’s question is yes. Of the 12,871 shapes to ten cells, the rigid motions pair 43 and the full involution search pairs 102 — 59 shapes that had no pairing at all now have one, found by a search that considers 8,853,914 candidates where the old one considered eight per shape.

The smallest one, and what it is #

The first shape where this happens has six cells, and it is worth looking at rather than counting.

It is the staircase: a full bottom row, two squares above its left end, one above those. The shape has a Grundy value of nought, so the second player wins it, and until now this ladder had no argument for that beyond running the search.

Look at what the map does. It pairs the top-left corner with the bottom-right, the middle-left square with the middle-bottom, and — the interesting pair — the bottom-left corner with the centre.

The pairing is the anti-diagonal reflection with its two fixed squares exchanged. The reflection is a genuine symmetry of the staircase and the ladder has always had to refuse it, because it fixes two squares and the first clause forbids a fixed square. The repair is the obvious one and nobody could make it while searching over motions: leave the reflection alone on the four squares it moves, and swap the two it fixes.

That is legal precisely because those two squares are not adjacent. They sit a knight’s-move apart — lattice distance two — so the pair {bottom-left, centre} is not a domino, and swapping them cannot violate the third clause. Had the reflection’s two fixed squares been neighbours, the swap would have been a domino mapped to itself and the repair would have failed. The condition that decides whether a reflection can be rescued is the distance between its fixed squares, and no reading of the shape’s symmetry group contains that number.

Sixty-three shapes, sixty-four maps #

The staircase is the smallest case and it is not the only kind. Sixty-three shapes to ten cells carry a pairing no rigid motion gives, and between them they carry sixty-four such maps — so exactly one shape has two of them, a ten-cell shape in a five-by-five box.

That distribution is worth reading, because it is not what a reader expects from a search over 945 candidates per shape. Widening the search from eight maps to 945 does not produce a flood of pairings; it produces, on the shapes that get one at all, almost always exactly one. A pairing remains a rare and rigid thing — the three clauses are extremely demanding, and relaxing the requirement that the map be a motion does not make them less so. What changes is only that the demand can now be met by permutations nobody was enumerating.

The rate rises sharply with size, and that is the one trend the sweep does show. At four cells the wider search finds nothing the narrow one missed. At six cells it finds one shape. At eight, six. At ten, fifty-two. The shape count itself roughly quadruples between eight cells and ten, so the share is rising too, and the reason is straightforward: a bigger shape has more squares that can play interchangeable roles in the adjacency graph without being related by any motion of the square.

Whether that trend continues is the question the model cannot reach, and it matters for the residue rather than for the finding. If the wider search’s share keeps doubling every two cells it will still be accounting for a small minority of second-player wins at fourteen cells, because the count of second-player wins is growing faster than either search’s yield.

The parity wall #

Before the residue can be read, one large class has to come out of the denominator, and it comes out before any search runs.

An involution of a set of odd size has a fixed point — there is nowhere else for the last element to go — so the first clause kills every odd shape before the second and third are consulted. Sizes five, seven and nine hold 706 second-player wins between them and a pairing argument is unavailable on all of them, not because nobody has found the map but because there is none.

The second player still wins all 706, and something decides them. The values of every small board is the census that says which, and it says it by evaluating the position — which is the expensive answer a pairing exists to avoid. So the parity wall is a statement about the cheap argument’s reach rather than about the game: it says the argument is unavailable on a sixth of the second-player wins in the sweep, and says nothing at all about why those positions are lost.

This is the sharpest thing the ladder knows about the limits of the argument, and it is worth separating from everything else on this page: the wider search changes nothing here. Widening the class of maps cannot help a shape whose obstruction is the number of squares.

What is left #

Restricted to the shapes where a pairing is even possible, the rigid motions explain 43 of 3,837 second-player wins and the full search explains 102. The improvement is a factor of 2.4 and the absolute figure is 2.7 per cent.

So the page has two answers and they point opposite ways.

The rung below’s question has a positive answer. The geometric pairings are not the only ones a Cram position has. They were the only ones anybody had looked for, exactly as suspected, and the shapes that have a non-geometric pairing are not exotic — the smallest is six squares and it is the first shape a reader would draw if asked for something that is nearly symmetric.

And the hope behind the question has a negative one. A pairing argument accounts for a few per cent of the second-player wins in Cram, and it accounted for a few per cent before. Nothing about the residue changed. Whatever explains the other 3,735 even-sized second-player wins is not a pairing, and it was not a pairing under a wider notion of pairing either.

That is the more useful of the two answers, and it closes a line of questions rather than opening one. The suspicion behind the rung below was that the ladder’s search had been too narrow and that a proper search would turn a curiosity into a method — a cheap test that settles a real share of positions, worth putting in front of a solver. It would not. The obstruction was never the class of maps considered; it is that most second-player wins in Cram are second-player wins for reasons that have no symmetry in them at all, and are found by the board falling into independent regions or by nothing shorter than the search itself.

What the solver computed, and how #

The catalogue is every polyomino of at most ten cells up to translation, which is 12,871 shapes. Each is evaluated by the ordinary Cram recursion over a bitmask of occupied squares, memoised, with the Grundy value taken as the mex over placements of a domino on two adjacent free squares; a shape is a second-player win when that value is nought.

For each shape the narrow search builds the eight maps of the square, keeps those carrying the cell set to itself, discards any that is not an involution, and hands each survivor to the three-clause test. The wider search generates every fixed-point-free involution of the $n$ cells directly — there are $(n - 1)!!$ of them, which is 945 at ten cells — and hands each to the same test function. The two searches differ in what they enumerate and in nothing else.

Three things are asserted rather than reported, and the figures fail to build if any stops holding. Every pairing the wider search finds must land on a shape the solver calls a second-player win, which is the soundness of the three clauses and is the claim most at risk from widening the class. Every pairing the narrow search finds must also be found by the wider one, or the two are not measuring the same object. And no odd-sized shape may come back with a pairing, which is arithmetic and is the check that the enumeration is doing what it says.

The witness’s reading — that its map is the anti-diagonal reflection with the fixed squares exchanged — is asserted too: the reflection must have exactly two fixed squares, they must not be adjacent, and the found map must be the one that swaps them.

Where the model stops #

Ten cells. The counts here are a census of small shapes and the trend across sizes is short: the wider search finds nothing at four cells, one shape at six, six at eight and fifty-two at ten. Whether the share it adds keeps rising is a question this sweep cannot answer, and the growth in candidates is $(n-1)!!$, so twelve cells is 10,395 involutions per shape against 945 and the shape count roughly quadruples.

Normal play throughout. Every pairing argument on this site depends on the last player to move winning, and it depends on it twice: the strategy guarantees the second player always has a reply, which is a statement about running out of moves rather than about the position.

And the figures cannot show what a reader most wants from a page about a wider search, which is a shape whose non-geometric pairing has no near-geometric description. The witness here is a reflection with a repair, and the other 62 have not been classified — the search reports the map and does not ask what it resembles. Whether every non-geometric pairing on these shapes is a near-symmetry patched at its fixed points, or whether some are unrelated to any motion, is a question the census does not answer and the next rung is about.

Who found what, and when #

The pairing strategy for Cram on a board with a centre is folklore and is older than the theory that surrounds it — it belongs to the same family of arguments as the strategy-stealing proofs, in that it names a winner and no move. What this site has added over seven rungs is not the strategy but the test: the exact list of clauses a proposed pairing has to satisfy, arrived at by finding pairings that failed.

That list was built by repair. The check that was not a check is where the third clause was added, after a solver disagreed with a check that had passed for two rungs; the missing condition was the self-paired domino, and without it the check accepted 1,026 losing positions on one rectangle alone. A symmetry that is not a pairing is where the quarter turn was found to pass every clause anybody had written down and fail two that had not been written — and where the property a pairing really needs, that the map be its own inverse, became visible only because a map was tried that lacked it.

The clause list is therefore the ladder’s product, and this page is the first rung to take it literally. Seven rungs assembled a requirement stated purely in terms of a permutation, and then went on searching the eight maps of the square, because that is where the requirement came from and because a rectangle never punishes the confusion. The finding here is not that a wider search was possible; it is that the ladder had already written down the wider search and had not read its own sentence as an instruction.

Where the ladder goes next #

The pairing anchor has eight rungs: the strategy that is a symmetry, looking for the symmetry, the symmetry one move away, a check in front of a search, the check that was not a check, the other pairings, the symmetry that is not one, and now the pairing that is not a symmetry.

The rung above is the classification of the 64 extra maps. This page has one of them in hand and reads it as a reflection with its fixed squares exchanged; whether that is the general shape is a question about the other 63, and it is well posed. For each extra map, ask whether some rigid motion of the square agrees with it off a small set, and record how large that set is. If the answer is always “a motion, patched at its fixed points”, then the wider search has found no genuinely new kind of object and the right description of a Cram pairing is a symmetry with its fixed points paired off — which would be a better statement of the requirement than the three clauses and would make the wider search unnecessary. If some map agrees with no motion anywhere, that map is the interesting one and it is the whole of the next rung.

Two neighbours are worth the trip. Looking for the symmetry is where a shape is first searched rather than a symmetry proposed, and it is the page whose method this one takes to its limit. And a check in front of a search is where a pairing check was priced as firing rate times subtree saved, which is the measurement that decides whether any of this is worth putting in a solver — and at 102 shapes in 12,871 the answer is still no.