#### Archive

Category Archives for "Recreational Math"

## Polyform

In recreational mathematics, a polyform is a plane figure constructed by joining together identical basic polygons.

The basic polygon is often (but not necessarily) a convex plane-filling polygon, such as a square or a triangle. More specific names have been given to polyforms resulting from specific basic polygons, as detailed in the table below. For example, a square basic polygon results in the well-known polyominoes.

Construction rules The rules for joining the polygons together may vary, and must therefore be stated for each distinct type of polyform. Generally, however, the following rules apply:

1. Two basic polygons may be joined only along a common edge.

2. No two basic polygons may overlap.

3. A polyform must be connected (that is, all one piece; see connected graph, connected space). Configurations of disconnected basic polygons do not qualify as polyforms.

4. The mirror image of an asymmetric polyform is not considered a distinct polyform (polyforms are “double sided”).

Generalizations Polyforms can also be considered in higher dimensions. In 3-dimensional space, basic polyhedra can be joined along congruent faces. Joining cubes in this way produces the polycubes. One can allow more than one basic polygon.

The possibilities are so numerous that the exercise seems pointless, unless extra requirements are brought in. For example, the Penrose tiles define extra rules for joining edges, resulting in interesting polyforms with a kind of pentagonal symmetry. When the base form is a polygon that tiles the plane, rule 1 may be broken.

For instance, squares may be joined orthogonally at vertices, as well as at edges, to form polyplets or polykings.

Types and applications Polyforms are a rich source of problems, puzzles and games. The basic combinatorial problem is counting the number of different polyforms, given the basic polygon and the construction rules, as a function of n, the number of basic polygons in the polyform. Well-known puzzles include the pentomino puzzle and the Soma cube

## Dots and Boxes

Dots and Boxes (also known as Boxes, Squares, Paddocks, Square-it, Dots and Dashes, Dots, Smart Dots, Dot Boxing, or, simply, the Dot Game) is a pencil and paper game for two players (or sometimes, more than two) first published in 1889 by Édouard Lucas.

Game of dots and boxes on the 2×2 board. Starting with an empty grid of dots, players take turns, adding a single horizontal or vertical line between two unjoined adjacent dots.

A player who completes the fourth side of a box earns one point and takes another turn. (The points are typically recorded by placing in the box an identifying mark of the player, such as an initial). The game ends when no more lines can be placed. The winner of the game is the player with the most points.

The board may be of any size. When short on time, 2×2 boxes (created by a square of 9 dots) is good for beginners, and 6×6 is good for experts. In games with an even number of boxes, it is conventional that if the game is tied then the win should be awarded to the second player (this offsets the advantage of going first).

The diagram on the right shows a game being played on the 2×2 board. The second player (B) plays the mirror image of the first player’s move, hoping to divide the board into two pieces and tie the game. The first player (A) makes a sacrifice at move 7; B accepts the sacrifice, getting one box. However, B must now add another line, and connects the center dot to the center-right dot, causing the remaining boxes to be joined together in a chain as shown at the end of move 8. With A’s next move, A gets them all, winning 3–1.

At the start of a game, play is more or less random, the only strategy is to avoid adding the third side to any box. This continues until all the remaining (potential) boxes are joined together into chains – groups of one or more adjacent boxes in which any move gives all the boxes in the chain to the opponent.

A novice player faced with a situation like position 1 in the diagram on the left, in which some boxes can be captured, takes all the boxes in the chain, resulting in position 2. But with their last move, they have to open the next (and larger) chain, and the novice loses the game, An experienced player faced with position 1 instead plays the double-cross strategy, taking all but 2 of the boxes in the chain, leaving position 3. This leaves the last two boxes in the chain for their opponent, but then the opponent has to open the next chain. By moving to position 3, player A wins.

The double-cross strategy applies however many long chains there are. Take all but two of the boxes in each chain, but take all the boxes in the last chain. If the chains are long enough then the player will certainly win.

Therefore, when played by experts, Dots and Boxes becomes a battle for control: An expert player tries to force their opponent to start the first long chain. Against a player who doesn’t understand the concept of a sacrifice, the expert simply has to make the correct number of sacrifices to encourage the opponent to hand him the first chain long enough to ensure a win. If the other player also knows to offer sacrifices, the expert also has to manipulate the number of available sacrifices through earlier play. There is never any reason not to accept a sacrifice, as if it is refused, the player who offered it can always take it without penalty.

Thus, the impact of refusing a sacrifice need not be considered in your strategy. Experienced players can avoid the chaining phenomenon by making early moves to split the board. A board split into 4×4 squares is ideal. Dividing limits the size of chains- in the case of 4×4 squares, the longest possible chain is four, filling the larger square.

A board with an even number of spaces will end in a draw (as the number of 4×4 squares will be equal for each player); an odd numbered board will lead to the winner winning by one square (the 4×4 squares and 2×1 half-squares will fall evenly, with one box not incorporated into the pattern falling to the winner). A common alternate ruleset is to require all available boxes be claimed on your turn.

This eliminates the double cross strategy, forcing even the experienced player to take all the boxes, and give his opponent the win. In combinatorial game theory dots and boxes is very close to being an impartial game and many positions can be analyzed using Sprague–Grundy theory. Dots and boxes need not be played on a rectangular grid. It can be played on a triangular grid or a hexagonal grid. Investigations on a triangular variation of the game have even been carried out by Raffles Institution students. There is also a variant in Bolivia when it is played in a Chakana or Inca Cross grid, which adds more complications to the game. Dots-and-boxes has a dual form called “strings-and-coins”.

This game is played on a network of coins (vertices) joined by strings (edges). Players take turns to cut a string. When a cut leaves a coin with no strings, the player pockets the coin and takes another turn. The winner is the player who pockets the most coins. Strings-and-coins can be played on an arbitrary graph. A variant played in Poland allows a player to claim a region of several squares as soon as its boundary is completed.

## Hexapawn

Hexapawn is a deterministic two-player game invented by Martin Gardner. It is played on a rectangular board of variable size, for example on a 3×3 board or on a chessboard. On a board of size n×m, each player begins with m pawns, one for each square in the row closest to them.

The goal of each player is to advance one of their pawns to the opposite end of the board or to prevent the other player from moving.

Hexapawn on the 3×3 board is a solved game; if both players play well, the first player to move will always lose. Also it seems that any player cannot capture all enemy’s pawns. Indeed, Gardner specifically constructed it as a game with a small game tree, in order to demonstrate how it could be played by a heuristic AI implemented by a mechanical computer. A variant of this game is octapawn.

Rules As in chess, each pawn may be moved in two different ways: it may be moved one square forward, or it may capture a pawn one square diagonally ahead of it. A pawn may not be moved forward if there is a pawn in the next square.

Unlike chess, the first move of a pawn may not advance it by two spaces. A player loses if he/she has no legal moves or the other player reaches the end of the board with a pawn. Dawson’s chess Whenever a player advances a pawn to the penultimate rank (unless it is an isolated pawn) there is a threat to proceed to the final rank by capture.

The opponent’s only sensible responses are therefore either to capture the advanced pawn or to advance the threatened one, the latter only being sensible in the case that there is one threatened pawn rather than two. If one restricts 3× hexapawn with the additional rule that the capture is always compulsory, the result is the game Dawson’s chess. Dawson’s chess reduces to the impartial game denoted .137 in Conway’s notation.

This means that it is equivalent to a Nim-like game in which:

• on a turn, the player may remove one to three objects from a heap,

• removing just one object is a legal move only if the removed object is the only object in the heap, and

• when removing three objects from a heap of five or more, the player may also split the remainder into two heaps

## Phutball

Phutball (short for philosopher’s football) is a two-player board game described in Elwyn Berlekamp, John Horton Conway, and Richard Guy’s Winning Ways for your Mathematical Plays.

Rules Phutball is played on the intersections of a 19×15 grid using one white stone and as many black stones as needed. In this article the two players are named Ohs (O) and Eks (X). The board is labeled A through P (omitting I) from left to right and 1 to 19 from bottom to top from Ohs’ perspective.

Rows 0 and 20 represent “off the board” beyond rows 1 and 19 respectively. Given that specialized phutball boards are hard to come by, the game is usually played on a 19×19 Go board, with a white stone representing the football and black stones representing the men.

The objective is to score goals by using the men (the black stones) to move the football (the white stone) onto or over the opponent’s goal line. Ohs tries to move the football to rows 19 or 20 and Eks to rows 1 or 0. At the start of the game the football is placed on the central point, unless one player gives the other a handicap, in which case the ball starts nearer one player’s goal. Players alternate making moves. A move is either to add a man to any vacant point on the board or to move the ball. There is no difference between men played by Ohs and those played by Eks.

The football is moved by a series of jumps over adjacent men. Each jump is to the first vacant point in a straight line horizontally, vertically, or diagonally over one or more men. The jumped men are then removed from the board (before any subsequent jump occurs).

This process repeats for as long as there remain men available to be jumped and the player desires. Jumping is optional, there is no requirement to jump. Note that in contrast to checkers, multiple men in a row are jumped and removed as a group. The diagram on the right illustrates a jump.

• Ohs moves the football from K6-G9-G11-J11. • The men on J7, H8, G10, and H11 are removed.

• The jump from K6-G9-J9-G7 would not be legal, as that would jump the man on H8 twice.

If the football ends the move on or over the opponent’s goal line then a goal has been scored. If the football passes through your goal line, but ends up elsewhere due to further jumps, the game continues. Strategy • Carefully set up sequences of jumps can be “spoiled” by extending them at critical moments.

• A jump to the left or right edge can be blocked by leaving no vacant points.

• When you jump, it is usually bad to leave an easily used return path for your opponent to “undo” your progress. The game is sufficiently complex that checking whether there is a win in one (on an m×n board) is NP-complete. It is not known whether any player has a winning strategy or both players have a drawing strategy.

## Sprouts

Sprouts is a pencil-and-paper game with interesting mathematical properties. It was invented by mathematicians John Horton Conway and Michael S. Paterson at Cambridge University in 1967. A 2-spot game of Sprouts The game is played by two players, starting with a few spots drawn on a sheet of paper.

Players take turns, where each turn consists of drawing a line between two spots (or from a spot to itself) and adding a new spot somewhere along the line. The players are constrained by the following rules.

• The line may be straight or curved, but must not touch or cross itself or any other line.

• The new spot cannot be placed on top of one of the endpoints of the new line. Thus the new spot splits the line into two shorter lines.

• No spot may have more than three lines attached to it. For the purposes of this rule, a line from the spot to itself counts as two attached lines and new spots are counted as having two lines already attached to them. In so-called normal play, the player who makes the last move wins.

In misère play, the player who makes the last move loses. The diagram on the right shows a 2-spot game of normal-play Sprouts. After the fourth move, most of the spots are dead–they have three lines attached to them, so they cannot be used as endpoints for a new line.

There are two spots (shown in green) that are still alive, having fewer than three lines attached. However, it is impossible to make another move, because a line from a live spot to itself would make four attachments, and a line from one live spot to the other would cross lines. Therefore, no fifth move is possible, and the first player loses. Live spots at the end of the game are called survivors and play a key role in the analysis of Sprouts. Analysis Suppose that a game starts with n spots and lasts for exactly m moves.

Each spot starts with three lives (opportunities to connect a line) and each move reduces the total number of lives in the game by one (two lives are lost at the ends of the line, but the new spot has one life). So at the end of the game there are 3n−m remaining lives. Each surviving spot has only one life (otherwise there would be another move joining that spot to itself), so there are exactly 3n−m survivors.

There must be at least one survivor, namely the spot added in the final move. So 3n−m ≥ 1; hence a game can last no more than 3n−1 moves. By enumerating all possible moves, one can show that the first player when playing with the best possible strategy will always win in normal-play games starting with n = 3, 4, or 5 spots. The second player wins when n = 0, 1, 2, or 6. At Bell Labs in 1990, David Applegate, Guy Jacobson, and Daniel Sleator used a lot of computer power to push the analysis out to eleven spots in normal play and nine spots in misère play.

Josh Purinton and Roman Khorkov have extended this analysis to sixteen spots in misère play. Julien Lemoine and Simon Viennot have calculated normal play outcomes up to thirty-two spots, plus five more games between thirty-four and forty-seven spots.

They have also announced a result for the seventeen-spot misère game. The normal-play results are all consistent with the pattern observed by Applegate et al. up to eleven spots and conjectured to continue indefinitely, that the first player has a winning strategy when the number of spots divided by six leaves a remainder of three, four, or five. The results for misère play do not follow as simple a pattern: up to seventeen spots, the first player wins in misère Sprouts when the remainder (mod 6) is zero, four, or five, except that the first player wins the one-spot game and loses the four-spot game.