© Friederike Hofmann, MATH+
Authors: Alex McDonough (UC Davis), Ulrich Reitebuch (FU Berlin), Martin Skrodzki (TU Delft)
Challenge
The games department of the Christmas Research Center is constantly developing new games to keep the children of the world from getting bored. This year, it has come up with a game especially for only children: it is a solitaire game played on a board with n\times 3 fields.
Each field can hold exactly one token. There are three different types of tokens and n tokens of each type: squares, circles, and diamonds. For each type, the n tokens are labeled with numbers 1 to n .
A placement of all tokens on the board is called stable if:
(a) In no row a square is to the right of a circle or a diamond. In no row a circle is to the right of a diamond.
(b) In columns, the vertical relations on labels as given in Figure 1 hold:
Figure 1: The vertical relations on labels.
That is, the numbered squares, circles, and diamonds have to be placed according to the inequalities given in Figure 1. For instance,
-
-
- a square numbered i can be below a circle or diamond numbered j with i\leq j ,
- but a if a circle numbered i is under a square, then the square’s label needs to be j with i<j .
-
(c) In rows, the horizontal relations on labels as given in Figure 2 hold, even if the respective tokens are not next to each other:
Figure 2: The horizontal relations on labels.
Examples of a stable and an unstable placement for the 2\times 3 board is depicted in Figure 3:
Figure 3: A stable and an unstable placement on the 2\times 3 board. The left placement of the tokens is stable; all relations are satisfied. The right placement of the tokens is unstable: while all columns as well as the lower row satisfy all relations, the upper row violates rule (c), since the circle with larger number is placed to the right of the circle with the smaller number (marked in red).
Note that while there are restrictions on labels across different types of tokens when placed vertically, there are only restrictions on horizontal labels within one token type. That is, if two tokens of the same type are in the same row, they have to be ordered from left to right according to their label (even if they are not next to each other). In rows, two tokens of different types only have to satisfy rule (a), independent of their labeling. That is, a square labeled 5 can be left of a circle labeled 3 .
Question: How many stable placements of the tokens are there on a 4\times 3 board?
Possible answers:
- 1
- 2
- 3
- 4
- 3\cdot 4
- 3!\cdot 4
- 4!\cdot 3
- 3!\cdot 4!
- (3\cdot 4)!/3!^4
- (3\cdot 4)!
Project reference:
The presented task is part of an open question in a current combinatorics project.
In the project, we investigate an object called the neighborhood grid, which has connections to finding relationships in data sets (for more details, see: https://arxiv.org/abs/1710.03435). Roughly speaking, the data structure will speed-up the performance of specific algorithms such as particle or cell simulations by providing fast, approximate answers to the question: For a given particle or cell, what are the nearest other particles or cells around it?