Problem of the Month Archive | Math Magic is a web site devoted to original mathematical recreations. If you have a math puzzle, discovery, or observation, please e-mail me about it. You can also send answers to the problem of the month. |

For game theory novices, the question is who wins starting from a single rectangle. For example, consider the example where is playing . Then wins no matter who starts on a 4×4 board (the unique winning move for is ). It is harder to see, but the first player can win on a 6×4 board (the unique winning move for is , and there are many winning moves for ). For each of the 15 pairs of tetrominoes, who wins starting from small rectangles? Which winning moves are unique?

For game theory experts, the question is who wins starting with more than one rectangle. To help determine this, each rectangle can be assigned a value, roughly how many moves a given polyomino wins by. Positions in which neither player can win going first are assigned value 0. In the example above, a 9×1 board has value 2 (since 2 copies of will fit), and a 3×3 board has value -1 (since 1 copy of will fit). For larger rectangles, the values are not numbers, but can be symbolized inductively with brace notation, indicating what values each player can move to. For example, a 4×2 board has value {1 | 0} since can move to a position of value 1 (by moving to ) and can move to a position with value 0 (by moving to ).

Simplifying games in brace notation is relatively hard. We give a few simple rules here that will help with most small rectangles. If a<b, {a | b} is the "simplest" number between a and b, which means the integer with the smallest absolute value if there is one, or the dyadic rational with the smallest denominator. If a>b, {a | b}, cannot be simplified, and is said to have temperature a-b. Since they pop up so often, we give a special names to {0 | 0} = *, the game with only one move by either player, and {0,* | 0,*} = **, the game with one or two moves by either player. These are equivalent to Nim piles, and have temperature 0.

When playing with more than one rectangle, a player should play in the rectangle with the highest temperature, since they have the most to gain. For example, continue our example by starting from rectangles of size 4×3, 4×2, and 7×2. The values of these rectangles are {2 | -1}, {1 | 0}, and {½ | -2} respectively. If starts, the game will go like this: , leaving value (2) + (-2) + (1) = 1, a win for . If starts, the game will go like this: , leaving value (-1) + (½) + (0) = -½, a win for . For each of the 15 pairs of tetrominoes, what are the values of small rectangles?

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|

1 | 0 | 0 | 0 | * | * | * | * | ** | ** | ** | 0 | *** | *** |

2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |

3 | 0 | * | * | * | * | ** | ** | ** | 0 | *** | *** | ||

4 | 0 | * | 0 | * | 0 | * | |||||||

5 | 0 | * |

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|

1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 3 | 3 |

2 | 0 | -1 | {1 | -1} | {* | -1} | {* | -1} | {* | -2} | |||||||

3 | -2 | {2 | -1} | {0 | -2} | {0 | -3} | |||||||||

4 | |||||||||||||

5 |

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|

1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 3 | 3 |

2 | 0 | -1 | {1 | 0} | {1 | -1} | {1 | -1} | {½ | -2} | |||||||

3 | -1 | {2 | -1} | {2 | -1 + {0,*}} | ||||||||||

4 | {{2|1} | 1} | ||||||||||||

5 |

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|

1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 3 | 3 |

2 | 0 | -1 | {1 | 0} | {1 | -1} | {1 | -1} | {½ | -2} | |||||||

3 | -1 | {2 | -1} | {2 | -1} | {2 | -2} | {1 | -1½} | ||||||||

4 | 1 | ||||||||||||

5 |

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|

1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 3 | 3 |

2 | -1 | -1 | {1 | -1} | {1 | -1} | {1 | -2} | {½ | -2} | |||||||

3 | -1 | {2 | -½} | {2 | -½} | {2 | -1} | |||||||||

4 | 0 | ||||||||||||

5 |

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|

1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

2 | 0 | * | ** | ** | 0 | *** | **** | * | 0 | ***** | *** | *** | |

3 | ** | 0 | *** | * | 0 | ||||||||

4 | 0 | 0 | |||||||||||

5 |

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|

1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

2 | 0 | * | {1 | 0} | {1 | 0,*} | {1 | *} | {1+* | {0,*,{-1|1}} | |||||||

3 | {0,* | 0} | {1 | *} | |||||||||||

4 | |||||||||||||

5 |

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|

1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

2 | 0 | * | {1 | 0} | {1 | 0,*} | {1 | *} | {1+* | {0,*,{-1|1}} | |||||||

3 | {0,* | 0} | {1 | *} | {2 | {1|0}} | ||||||||||

4 | |||||||||||||

5 |

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|

1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

2 | -1 | * | {1 | -1} | {1 | -1} | {0,* | -2} | {1+* | -1+*} | |||||||

3 | {0,* | 0} | {1 | *} | {2 | 1+*} | ||||||||||

4 | |||||||||||||

5 |

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|

1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

2 | 0 | * | * | ** | 0 | *** | * | * | 0 | *** | *** | ** | |

3 | * | ** | *** | **** | 0 | ||||||||

4 | 0 | ** | 0 | ||||||||||

5 | 0 |

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|

1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

2 | 0 | * | * | ** | 0 | *** | * | * | 0 | *** | *** | ** | |

3 | * | ** | {0,{1|0} | *} | ||||||||||

4 | 0 | ||||||||||||

5 |

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|

1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

2 | -1 | * | {0 | -1} | {0,* | -1} | {* | -2} | ||||||||

3 | * | ** | {1 | *} | ||||||||||

4 | |||||||||||||

5 |

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|

1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

2 | 0 | * | * | ** | 0 | *** | * | * | 0 | *** | *** | ** | |

3 | * | ** | 0 | *** | * | * | 0 | ||||||

4 | 0 | * | ** | *** | |||||||||

5 | 0 | *** |

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|

1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

2 | -1 | * | {0 | -1} | {0,* | -1} | {* | -2} | ||||||||

3 | * | ** | 0 | 0 | |||||||||

4 | |||||||||||||

5 | 0 |

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|

1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

2 | * | * | ** | 0 | *** | * | * | 0 | *** | *** | ** | ** | |

3 | * | ** | 0 | *** | * | * | 0 | *** | *** | ** | ** | ||

4 | * | 0 | *** | ** | * | 0 | |||||||

5 | 0 | 0 | 0 | ||||||||||

6 | **** |

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 6/12/06.