Cram is a

mathematical game A mathematical game is a game whose rules, strategies, and outcomes are defined by clear mathematical parameters. Often, such games have simple rules and match procedures, such as Tic-tac-toe and Dots and Boxes. Generally, mathematical games ne ...

played on a sheet of

graph paper Graph paper, coordinate paper, grid paper, or squared paper is writing paper that is printed with fine lines making up a regular grid. The lines are often used as guides for plotting graphs of functions or experimental data and drawing curves. I ...

. It is the impartial version of

Domineering Domineering (also called Stop-Gate or Crosscram) is a mathematical game that can be played on any collection of squares on a sheet of graph paper. For example, it can be played on a 6×6 square, a rectangle, an entirely irregular polyomino, or a ...

and the only difference in the rules is that each player may place their dominoes in either orientation, but it results in a very different game. It has been called by many names, including "plugg" by

Geoffrey Mott-Smith The Mott-Smith Trophy, named for writer and cryptographer Geoffrey Mott-Smith, is awarded to the player with the best overall individual performance in the Spring Nationals, the spring event of the American Contract Bridge League (ACBL) North Amer ...

, and "dots-and-pairs." Cram was popularized by

Martin Gardner Martin Gardner (October 21, 1914May 22, 2010) was an American popular mathematics and popular science writer with interests also encompassing scientific skepticism, micromagic, philosophy, religion, and literatureespecially the writings of Lewis ...

in ''

Scientific American ''Scientific American'', informally abbreviated ''SciAm'' or sometimes ''SA'', is an American popular science magazine. Many famous scientists, including Albert Einstein and Nikola Tesla, have contributed articles to it. In print since 1845, it i ...

''.

Rules

The game is played on a sheet of

, with any set of designs traced out. It is most commonly played on rectangular board like a 6×6 square or a

checkerboard A checkerboard (American English) or chequerboard (British English; see spelling differences) is a board of checkered pattern on which checkers (also known as English draughts) is played. Most commonly, it consists of 64 squares (8×8) of altern ...

, but it can also be played on an entirely irregular

polygon In geometry, a polygon () is a plane figure that is described by a finite number of straight line segments connected to form a closed ''polygonal chain'' (or ''polygonal circuit''). The bounded plane region, the bounding circuit, or the two toge ...

or a cylindrical board. Two players have a collection of

domino Dominoes is a family of tile-based games played with gaming pieces, commonly known as dominoes. Each domino is a rectangular tile, usually with a line dividing its face into two square ''ends''. Each end is marked with a number of spots (also ca ...

es which they place on the grid in turn. A player can place a domino either horizontally or vertically. Contrary to the related game of

, the possible moves are the same for the two players, and Cram is then an

impartial game In combinatorial game theory, an impartial game is a game in which the allowable moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric. In other words, the only difference betw ...

. As for all impartial games, there are two possible conventions for victory: in the normal game, the first player who cannot move loses, and on the contrary, in the

misère Misère ( French for "destitution"), misere, bettel, betl, or (German for "beggar"; equivalent terms in other languages include , , ) is a bid in various card games, and the player who bids misère undertakes to win no tricks or as few as possi ...

version, the first player who cannot move wins.

Symmetry play

The winning

strategy Strategy (from Greek στρατηγία ''stratēgia'', "art of troop leader; office of general, command, generalship") is a general plan to achieve one or more long-term or overall goals under conditions of uncertainty. In the sense of the "art ...

for normal Cram is simple for even-by-even boards and even-by-odd boards. In the even-by-even case, the second player wins by

symmetry Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definit ...

play. This means that whichever move Player 1 makes, Player 2 has a corresponding symmetric move across the horizontal and vertical axes. In a sense, player 2 'mimics' the moves made by Player 1. If Player 2 follows this strategy, Player 2 will always make the last move, and thus win the game. In the even-by-odd case, the first player wins by similar symmetry play. Player 1 places his first domino in the center two squares on the grid. Player 2 then makes his move, but Player 1 can play symmetrically thereafter, thus ensuring a win for Player 1. Symmetry play is a useless strategy in the

version, because in that case it would only ensure the player that he ''loses''.

Normal version

Grundy value

Since Cram is an

, the

Sprague–Grundy theorem In combinatorial game theory, the Sprague–Grundy theorem states that every impartial game under the normal play convention is equivalent to a one-heap game of nim, or to an infinite generalization of nim. It can therefore be represented as ...

indicates that in the normal version any Cram position is equivalent to a nim-heap of a given size, also called the ''Grundy value''. Some values can be found in Winning Ways for your Mathematical Plays, in particular the 2 × ''n'' board, whose value is 0 if ''n'' is even and 1 if ''n'' is odd. The symmetry strategy implies that even-by-even boards have a Grundy value of 0, but in the case of even-by-odd boards it only implies a Grundy value greater or equal to 1.

Known values

In 2009, Martin Schneider computed the grundy values up to the 3 × 9, 4 × 5 and 5 × 7 boards.Das Spiel Juvavum
Martin Schneider, Master thesis, 2009 In 2010, Julien Lemoine and Simon Viennot applied to the game of Cram algorithms that were initially developed for the game of Sprouts. It allowed them to compute the grundy-values up to the 3 × 20, 4 × 9, 5 × 9, 6 × 7 and 7 × 7 boards.Computation records of normal and misère Cram
Julien Lemoine and Simon Viennot web site The sequence of currently known Grundy values for 3 × ''n'' boards, from n=1 to n=20 is: 1, 1, 0, 1, 1, 4, 1, 3, 1, 2, 0, 1, 2, 3, 1, 4, 0, 1, 0, 2. It doesn't show any apparent pattern. The table below details the known results for boards with both dimensions greater than 3. Since the value of an ''n'' × ''m'' board is the same as the value of a ''m'' × ''n'' board, we give only the upper part of the table.

Misère version

Misère Grundy-value

The misère Grundy-value of a game G is defined by Conway in

On Numbers and Games ''On Numbers and Games'' is a mathematics book by John Horton Conway first published in 1976. The book is written by a pre-eminent mathematician, and is directed at other mathematicians. The material is, however, developed in a playful and unpre ...

as the unique number n such that G+n is a second player win in misère play. Even if it looks very similar to the usual Grundy-value in normal play, it is not as powerful. In particular, it is not possible to deduce the misère Grundy-value of a sum of games only from their respective misère grundy-values. In 2009, Martin Schneider computed the misère grundy values up to the 3 × 9, 4 × 6, and 5 × 5 board. In 2010, Julien Lemoine and Simon Viennot extended these results up to the 3 × 15, 4 × 9 and 5 × 7 boards, along with the value of the 6 × 6 board. The sequence of currently known misère Grundy values for 3 × ''n'' boards, from n=1 to n=15 is: 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1. This sequence is conjectured to be periodic of period 3. The adjacent table details the known misère results for boards with both dimensions greater than 3.

References

* {{cite book , first1=Elwyn R. , last1=Berlekamp , authorlink=Elwyn Berlekamp , first2=John H. , last2=Conway , author2-link=John Horton Conway , first3=Richard K. , last3=Guy , author3-link=Richard K. Guy , title= Winning Ways for Your Mathematical Plays , publisher=A K Peters, Ltd. , year=2003 Abstract strategy games Mathematical games Combinatorial game theory Paper-and-pencil games